Constructor
new ve.dm.Change([start], [transactions], [stores], [selections])
#
DataModel change.
A change is a list of transactions to be applied sequentially on top of a certain history state, together with a set that includes all new store values (annotations and DOM elements) introduced by those transactions.
It can be thought of more abstractly as a function f: D1 -> D2 a document in a specific start state D1, modifying parts of the document to produce a specific end state D2.
For two changes f: D1 -> D2 and g: D2 -> D3 we define f.concat(g): D1 -> D3 as the change obtained by applying f then g. By associativity of functions, a.concat(b.concat(c)) = a.concat(b).concat(c) for any consecutive changes a, b, c. Writing
x * y := x.concat(y) ,
we have a * (b * c) = (a * b) * c, so we can just write either as a * b * c.
For a change f: D1 -> D2 we define f.reversed() as the change D2 -> D1 such that f.concat(f.reversed()) is the identity change D1 -> D1. Writing
inv(x) := x.reversed() ,
we have f * inv(f) = the identity change on D1 .
Given two changes f: D1 -> D2 and g: D1 -> D3 , We would like to define f.rebasedOnto(g) ("f rebased onto g") as a change that maps D3 onto some D4: conceptually, it is f modified so it can be applied after g. This is a useful concept because it allows changes written in parallel to be sequenced into a linear order. However, for some changes there is no reasonable way to do this; e.g. when f and g both change the same word to something different. In this case we make f.rebasedOnto(g) return null and we say it conflicts.
Given f: D1 -> D2 , g: D2 -> D3, and x: D1 -> D4, we give three guarantees about rebasing:
- x.rebasedOnto(f) conflicts if and only if f.rebasedOnto(x) conflicts.
- If there is no conflict, f.concat(x.rebasedOnto(f)) equals x.concat(f.rebasedOnto(x)).
- If there is no conflict, x.rebasedOnto(f).rebasedOnto(g) equals x.rebasedOnto(f * g).
We can consider a conflicting transaction starting at some document D to be 0: D->null, and regard any two conflicting transactions starting at D to be equal, and just write 0 where D1 is clear from context. Then, writing
x|y := x.rebasedOnto(y),
we can write our guarantees. Given f: D1 -> D2 , g: D2 -> D3, and x: D1 -> D4:
- Change conflict well definedness: x|f = 0 if and only if f|x = 0.
- Change commutativity: f * g|f equals g * f|g .
- Rebasing piecewise: if (x|f)|g != 0, then (x|f)|g equals x|(f * g) .
These guarantees let us reorder non-conflicting changes without affecting the resulting document. They also let us move in the inverse direction ("rebase under"), from sequential changes to parallel ones, for if f: D1 -> D2 and g: D2 -> D3, then g|inv(f) maps from D1 to some D4, and conceptually it is g modified to apply without f having been applied.
Note that rebasing piecewise is not equivalent for changes that conflict: if a change conflicts f, it might not conflict with f*g. For example, if x|f = 0 then
(x|f)|inv(f) = 0 but x|(f * inv(f)) = x.
Parameters:
| Name | Type | Attributes | Default | Description |
|---|---|---|---|---|
start |
number |
optional |
0 | Length of the history stack at change start |
transactions |
Array.<ve.dm.Transaction> |
optional |
Transactions to apply |
|
stores |
Array.<ve.dm.HashValueStore> |
optional |
For each transaction, a collection of new store items |
|
selections |
Object |
optional |
{} | For each author ID (key), latest |
- Source:
Methods
addToHistory(documentModel)
#
Append change transactions to history
Parameters:
| Name | Type | Description |
|---|---|---|
documentModel |
ve.dm.Document |
- Source:
Throws:
-
If this change does not start at the top of the history
- Type
- Error
applyTo(surface, [applySelection])
#
Apply change to surface
Parameters:
| Name | Type | Attributes | Default | Description |
|---|---|---|---|---|
surface |
ve.dm.Surface | Surface in change start state |
||
applySelection |
boolean |
optional |
false | Apply a selection based on the modified range |
- Source:
clone() → {ve.dm.Change}
#
concat(other) → {ve.dm.Change}
#
Build a composite change from two consecutive changes
Parameters:
| Name | Type | Description |
|---|---|---|
other |
ve.dm.Change | Change that starts immediately after this |
- Source:
Returns:
Composite change
- Type
- ve.dm.Change
Throws:
-
If other does not start immediately after this
- Type
- Error
concatRebased(other) → {ve.dm.Change}
#
Build a composite change from two parallel changes
Parameters:
| Name | Type | Description |
|---|---|---|
other |
ve.dm.Change | Change parallel to this |
- Source:
Returns:
Composite change
- Type
- ve.dm.Change
Throws:
-
If this change and other have different starts
- Type
- Error
firstAuthorId() → {number|null}
#
null}
#
- Source:
Returns:
The first author in a transaction or selection change, or null if empty
- Type
-
number
|
null
getLength() → {number}
#
getStore(n) → {ve.dm.HashValueStore}
#
Get the store items introduced by transaction n
Parameters:
| Name | Type | Description |
|---|---|---|
n |
number | The index of a transaction within the change |
- Source:
Returns:
The store items introduced by transaction n
- Type
- ve.dm.HashValueStore
getStores() → {Array.<ve.dm.HashValueStore>}
#
Get the stores for each transaction
- Source:
Returns:
Each transaction's store items (shallow copied store)
- Type
- Array.<ve.dm.HashValueStore>
isEmpty() → {boolean}
#
- Source:
Returns:
True if this change has no transactions or selections
- Type
- boolean
mostRecent(start) → {ve.dm.Change}
#
Build a change from the last (most recent) transactions
Parameters:
| Name | Type | Description |
|---|---|---|
start |
number | Start offset |
- Source:
Returns:
Subset of this change with only the most recent transactions
- Type
- ve.dm.Change
push(other)
#
Push another change onto this change
Parameters:
| Name | Type | Description |
|---|---|---|
other |
ve.dm.Change | Change that starts immediately after this |
- Source:
Throws:
-
If other does not start immediately after this
- Type
- Error
pushTransaction(transaction, storeLength)
#
Push a transaction, after having grown the hash value store if required
Parameters:
| Name | Type | Description |
|---|---|---|
transaction |
ve.dm.Transaction | The transaction |
storeLength |
number | The corresponding store length required |
- Source:
rebasedOnto(other) → {ve.dm.Change|null}
#
null}
#
Rebase this change onto other (ready to apply on top of other)
Parameters:
| Name | Type | Description |
|---|---|---|
other |
ve.dm.Change | Other change |
- Source:
Returns:
Rebased change applicable on top of other, or null if rebasing fails
- Type
-
ve.dm.Change
|
null
Throws:
-
If this change and other have different starts
- Type
- Error
removeFromHistory(doc)
#
Remove change transactions from history
Parameters:
| Name | Type | Description |
|---|---|---|
doc |
ve.dm.Document |
- Source:
Throws:
-
If this change does not end at the top of the history
- Type
- Error
reversed() → {ve.dm.Change}
#
Get the change that backs out this change.
Note that applying it will not revert start or remove stored items
- Source:
Returns:
The change that backs out this change
- Type
- ve.dm.Change
serialize([preserveStoreValues]) → {Object}
#
Serialize the change to a JSONable object
Store values can be serialized, or kept verbatim (which only makes sense if they are serialized already, i.e. the Change object was created by #deserialize without deserializing store values).
Parameters:
| Name | Type | Attributes | Default | Description |
|---|---|---|---|---|
preserveStoreValues |
boolean |
optional |
false | If true, keep store values verbatim instead of serializing |
- Source:
Returns:
JSONable object
- Type
- Object
Serialize the change to a JSONable object
Store values can be serialized, or kept verbatim (which only makes sense if they are serialized already, i.e.
squash() → {ve.dm.Change}
#
Get a Change with all this Change's Transactions compacted into one (or zero)
The Change has the same effect when applied as this Change does, but it may cause rebase conflicts where this change does not.
TODO: introduce a "histLength" feature so the new change can be considered as having length > 1.
- Source:
Returns:
One-Transaction version of this Change (or empty change)
- Type
- ve.dm.Change
Get a Change with all this Change's Transactions compacted into one (or zero)
The Change has the same effect when applied as this Change does, but it may cause rebase conflicts where this change does not.
summarize() → {string}
#
Get a human-readable summary of the change
- Source:
Returns:
Human-readable summary
- Type
- string
toJSON([key]) → {Object}
#
Called automatically by JSON.stringify, see #serialize.
Parameters:
| Name | Type | Attributes | Description |
|---|---|---|---|
key |
string |
optional |
Key in parent object |
- Source:
Returns:
JSONable object
- Type
- Object
truncate(length) → {ve.dm.Change}
#
Build a change from the first (least recent) transactions of this change.
Always removes selections.
Parameters:
| Name | Type | Description |
|---|---|---|
length |
number | Number of transactions |
- Source:
Returns:
Subset of this change with only the least recent transactions
- Type
- ve.dm.Change
unapplyTo(surface)
#
Unapply change to surface, including truncating history and store
Parameters:
| Name | Type | Description |
|---|---|---|
surface |
ve.dm.Surface | Surface in change end state |
- Source:
deserialize(data, [preserveStoreValues], [unsafe]) → {ve.dm.Change}static
#
Deserialize a change from a JSONable object
Store values can be deserialized, or kept verbatim; the latter is an optimization if the Change object will be rebased and reserialized without ever being applied to a document.
Parameters:
| Name | Type | Attributes | Default | Description |
|---|---|---|---|---|
data |
Object | Change serialized as a JSONable object |
||
preserveStoreValues |
boolean |
optional |
false | Keep store values verbatim instead of deserializing |
unsafe |
boolean |
optional |
Use unsafe deserialization (skipping DOMPurify), used via #unsafeDeserialize |
- Source:
Returns:
Deserialized change
- Type
- ve.dm.Change
Deserialize a change from a JSONable object
Store values can be deserialized, or kept verbatim; the latter is an optimization if the Change object will be rebased and reserialized without ever being applied to a document.
getTransactionInfo(tx) → {ve.dm.Change.TransactionInfo|null}static
#
null}static
#
Get info about a transaction if it is a "simple replacement", or null if not
A simple replacement transaction is one that has just one retain op
Parameters:
| Name | Type | Description |
|---|---|---|
tx |
ve.dm.Transaction | The transaction |
- Source:
Returns:
Info about the transaction if a simple replacement, else null
- Type
-
ve.dm.Change.TransactionInfo
|
null
Get info about a transaction if it is a "simple replacement", or null if not
A simple replacement transaction is one that has just one retain op
rebaseTransactions(transactionA, transactionB) → {Array.<any>}static
#
Rebase parallel transactions transactionA and transactionB onto each other
Recalling that a transaction is a mapping from one ve.dm.ElementLinearData state to another,
suppose we have two parallel transactions, i.e.:
- transactionA mapping docstate0 to some docstateA, and
- transactionB mapping docstate0 to some docstateB .
Then we want rebasing to give us two new transactions:
- aRebasedOntoB mapping docstateB to some docstateC, and
- bRebasedOntoA mapping docstateA to docstateC ,
so that applying transactionA then bRebasedOntoA results in the same document state as applying transactionB then aRebasedOntoB .
However, it is useful to regard some transaction pairs as "conflicting" or unrebasable. In this implementation, transactions are considered to conflict if they have active ranges that overlap, where a transaction's "active range" means the smallest single range in the start document outside which the contents are unchanged by the transaction. (In practice the operations within the transaction actually specify which ranges map to where, giving a natural and unambiguous definition of "active range". Also, the identity transaction on a document state has no active range but is trivially rebasable with any parallel transaction).
For non-conflicting transactions, rebasing of each transaction is performed by resizing the inactive range either before or after the transaction to accommodate the length difference caused by the other transaction. There is ambiguity in the case where both transactions have a zero-length active range at the same position (i.e. two inserts in the same place); in this case, transactionA's insertion is put before transactionB's.
It is impossible for rebasing defined this way to create an invalid transaction that breaks tree validity. This is clear because every position in the rebased transaction's active range has the same node ancestry as the corresponding position before the rebase (else a tag must have changed both before and after that position, contradicting the fact that the transactions' active ranges do not overlap).
Also it is clear that for a pair of non-conflicting parallel transactions, applying either one followed by the other rebased will result in the same final document state, as required.
Parameters:
| Name | Type | Description |
|---|---|---|
transactionA |
ve.dm.Transaction | Transaction A |
transactionB |
ve.dm.Transaction | Transaction B, with the same document start state |
- Source:
Returns:
[ aRebasedOntoB, bRebasedOntoA ], or [ null, null ] if conflicting
- Type
- Array.<any>
Rebase parallel transactions transactionA and transactionB onto each other
Recalling that a transaction is a mapping from one ve.dm.ElementLinearData state to another,
suppose we have two parallel transactions, i.e.:
- transactionA mapping docstate0 to some docstateA, and
- transactionB mapping docstate0 to some docstateB .
rebaseUncommittedChange(history, uncommitted) → {ve.dm.Change.RebasedChange}static
#
Rebase a change on top of a parallel committed one
Since a change is a stack of transactions, we define change rebasing in terms of transaction rebasing. We require transaction rebasing to meet the three guarantees described above for change rebasing. To be precise, given any transactions a:D1->D2, b:D2->D3 and x:D1->D4, we require that:
- Transaction conflict well definedness: a|x = 0 if and only if x|a = 0.
- Transaction commutativity: a * x|a equals x * a|x .
- Rebasing piecewise: if (x|a)|b != 0, then (x|a)|b equals x|(a * b) .
Given committed history consisting of transactions a1,a2,…,aN, and an uncommitted update consisting of transactions b1,b2,…,bM, our approach is to rebase the whole list a1,…,aN over b1, and at the same time rebase b1 onto a1*…*aN. Then we repeat the process for b2, and so on. To rebase a1,…,aN over b1, the following approach would work:
a1' := a1|b1 a2' := a2|(inv(a1) * b1 * a1') a3' := a3|(inv(a2) * inv(a1) * b1 * a1' * a2') ⋮
That is, rebase a_i under a_i-1,…,a_1, then over b1,…,bM, then over a'1,…,a_i-1' .
However, because of the way transactions are written, it's not actually easy to implement transaction concatenation, so we would want to calculate a2' as piecewise rebases
a2' = ((a2|inv(a1))|b1)|a1'
which is unsatisfactory because a2|inv(a1) may well conflict even if a2|(inv(a1) * b1 * a1') as a whole would not conflict (e.g. if b1 modifies only parts of the document distant from a1 and a2).
So observe that by transaction commutivity we can rewrite a2' as:
a2' := a2|(inv(a1) * a1 * b1|a1) = a2|(b1|a1)
and that b1|a1 conflicts only if a1|b1 conflicts (so this introduces no new conflicts). In general we can write:
a1' := a1|b1 b1' := b1|a1 a2' := a2|b1' b1'' := b1'|a2 a3' := a3|b1'' b1''' := a1''|a3
Continuing in this way, we obtain a1',…,aN' rebased over b1, and b1''''''' (N primes) rebased onto a1 * … * aN . Iteratively we can take the same approach to rebase over b2,…,bM, giving both rebased lists as required.
If any of the transaction rebases conflict, then we rebase the largest possible non-conflicting initial segment b1,…,bK onto all of a1,…,aN (so clearly K < M).
If there are two parallel inserts at the same location, then ordering is ambiguous. We resolve this by putting the insert for the transaction with the highest author ID first (Javascript less-than is used, so comparisons with a null author ID do not fail). If the author IDs are the same, then A's insertion is put before B's.
Parameters:
| Name | Type | Description |
|---|---|---|
history |
ve.dm.Change | Committed history |
uncommitted |
ve.dm.Change | New transactions, with same start as history |
- Source:
Returns:
Rebase a change on top of a parallel committed one
Since a change is a stack of transactions, we define change rebasing in terms of transaction rebasing.
unsafeDeserialize(data) → {ve.dm.Change}static
#
Deserialize a change from a JSONable object without sanitizing DOM nodes
Parameters:
| Name | Type | Description |
|---|---|---|
data |
Object |
- Source:
Returns:
Deserialized change
- Type
- ve.dm.Change
Type Definitions
RebasedChange
#
Type:
Properties:
| Name | Type | Description |
|---|---|---|
rebased |
ve.dm.Change | Rebase onto history of uncommitted (or an initial segment of it) |
transposedHistory |
ve.dm.Change | Rebase of history onto initial segment of uncommitted |
rejected |
ve.dm.Change
|
null
|
Unrebasable final segment of uncommitted |
- Source:
TransactionInfo
#
Properties:
| Name | Type | Description |
|---|---|---|
start |
number | The start offset of the replacement |
end |
number | The end offset of the replacement (after replacement) |
docLength |
number | The total length of the document (after replacement) |
authorId |
number | The author ID |
uniformInsert |
ve.dm.Change.UniformTextInfo
|
null
|
The insertion as uniform text, or null if not |
- Source:
UniformTextInfo
#
Properties:
| Name | Type | Description |
|---|---|---|
text |
string | The code units, in a single string |
annotations |
string | Annotation hashes for all text |
annotationString |
string | Comma-separated annotation hashes |
- Source: