Expand all

ve.dm.Change

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:

  1. x.rebasedOnto(f) conflicts if and only if f.rebasedOnto(x) conflicts.
  2. If there is no conflict, f.concat(x.rebasedOnto(f)) equals x.concat(f.rebasedOnto(x)).
  3. 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:

  1. Change conflict well definedness: x|f = 0 if and only if f|x = 0.
  2. Change commutativity: f * g|f equals g * f|g .
  3. 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 Description
start number optional

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 ve.dm.Selection
Source:
DataModel change.

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
Append change transactions to history

applyTo(surface, [applySelection]) #

Apply change to surface

Parameters:

Name Type Attributes Description
surface ve.dm.Surface

Surface in change start state
applySelection boolean optional

Apply a selection based on the modified range
Source:
Apply change to surface

clone() → {ve.dm.Change} #

Create a clone of this Change

Source:

Returns:

Clone of this change

Type
ve.dm.Change
Create a clone of this 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
Build a composite change from two consecutive changes

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
Build a composite change from two parallel changes

firstAuthorId() → {number|null} #

Source:

Returns:

The first author in a transaction or selection change, or null if empty

Type
number | null

getLength() → {number} #

Source:

Returns:

The number of transactions

Type
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
Get the store items introduced by transaction n

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>
Get the stores for each transaction

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
Build a change from the last (most recent) transactions

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
Push another change onto this change

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:
Push a transaction, after having grown the hash value store if required

rebasedOnto(other) → {ve.dm.Change|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
Rebase this change onto other (ready to apply on top of other)

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
Remove change transactions from history

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
Get the change that backs out this 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 Description
preserveStoreValues boolean optional

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
Get a human-readable summary of the change

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
Called automatically by JSON.stringify, see #serialize.

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
Build a change from the first (least recent) transactions of this 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:
Unapply change to surface, including truncating history and store

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 Description
data Object

Change serialized as a JSONable object
preserveStoreValues boolean optional

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 #

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:

  1. Transaction conflict well definedness: a|x = 0 if and only if x|a = 0.
  2. Transaction commutativity: a * x|a equals x * a|x .
  3. 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:

Type
ve.dm.Change.RebasedChange

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
Deserialize a change from a JSONable object without sanitizing DOM nodes

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: