VisualEditor/Internals/DM/TreeModifier

Classes: ve.dm.TreeModifier, ve.dm.TreeCursor

Recall that a ve.dm.Transaction object is defined as a sequence of linear operations (hereafter linOps) on the linear model. The changes to the linear model imply changes to the spanning tree. Naïvely we might hope to update both linear model and spanning tree in sync, like this:

• Apply the first linOp to the linear model
• Update the spanning tree accordingly
• Repeat for the second operation, and all subsequent operations.

However, this fails catastrophically because applying one linOp doesn’t necessarily preserve tree validity. For instance, consider a transaction to remove blockquote indentation from some existing content:

wrapWithDiv = new ve.dm.Transaction( [
   { type: 'retain', length: 10 },
   { type: 'replace', remove: [ { type: 'blockquote' } ], insert: [] },
   { type: 'retain', length: 1337 },
   { type: 'replace', remove: [ { type: '/blockquote' } ], insert: [] },
   { type: 'retain', length: 26 }
] )

The first ‘replace’ linOp removes the opening <blockquote> tag. So once that has been processed, the linear model contains an unbalanced closing </blockquote> tag that isn’t removed until later. There is no way to update the spanning tree to match this unfinished state, because the tags don’t balance — in fact, in this state, the linear model doesn’t represent a document tree at all.

The simplest way to remedy this would be:

• Deactivate the spanning tree
• Apply each linOp to the linear model
• Rebuild affected portions of the spanning tree

Indeed VisualEditor originally used this implementation. However, it has the drawback that portions of the spanning tree get rebuilt. This triggers corresponding deletion and recreation of view nodes and ultimately DOM nodes. Such rebuilding is computationally expensive, but more importantly we lose track of how nodes are changing: all we know is a tree branch of old nodes has been replaced with a tree branch of new nodes (even though most of the content in the branch is typically unchanged). This is a problem, because spanning tree nodes are supposed to emit events when they are changed, e.g. so footnotes can be renumbered.

TreeModifier works in a different way. It translates the list of linOps into a list of tree operations, each of which preserves tree balance (hereafter treeOps). Possible treeOps are:

• { type: ‘insertNode’, at: <path>, element: <object> }
• { type: ‘removeNode’, at: <path>, element: <object> }
• { type: ‘moveNode’, from: <path>, to: <path> }
• { type: ‘insertText’, at: <path>, data: <array> }
• { type: ‘removeText’, at: <path>, data: <array> }
• { type: ‘moveText’, from: <path>, to: <path>, length: <n> }

The insertNode and removeNode treeOps apply to empty nodes only. But moveNode can move a non-empty node.

While treeOps are defined on the spanning tree, each also corresponds to a linear model splice (two splices in the case of a move). This is the key feature: the treeOps make it possible to keep the linear model and spanning tree in sync while modifying incrementally.

Having move treeOps (instead of just doing remove+insert) means we can preserve moving nodes in the spanning tree, instead of destroying and rebuilding them. Ultimately this ends up meaning we can preserve view nodes and DOM nodes too.

Note there is not a 1-1 correspondence between linOps and treeOps. Also, whereas the linOp sequence describes a single pass through the document, the treeOp sequence can jump around the tree as needed. Therefore, each treeOp specifies the tree location “at”, where it operates (in the case of a move, two locations: “from” and “to”).

Worked example

In this example, the user has split a paragraph (as if the user had pressed Enter inside the paragraph), changed some text, removed bulleting, and blockquoted the content.

Old doc HTML :=

<ul><li><p>foobarbaz</p><p>qux</p></li></ul>

New doc HTML :=

<blockquote><p>foo</p><p>barBAZ</p><p>qux</p></blockquote>

Note these edits would more typically be multiple separate transactions (though they could actually happen this way when using paste, or squashed transactions), but the example is a good one for illustrating the different features of tree operations.

The linear operation sequence would look like this:

linearOps = [
  {
    type: 'replace',
    remove: [ { type: 'list' }, { type: 'listItem' } ],
    insert: [ { type: 'blockquote' } ]
  },
  { type: 'retain', length: 4 },
  {
    type: 'replace',
    remove: [],
    insert: [ { type: '/paragraph' }, { type: 'paragraph' } ]
  },
  { type: 'retain', length: 3 },
  {
    type: 'replace',
    remove: [ 'b', 'a', 'z' ],
    insert: [ 'B', 'A', 'Z' ]
  },
  { type: 'retain', length: 6 },
  {
    type: 'replace',
    remove: [ { type: '/listItem' }, { type: '/list' } ],
    insert: [ { type: '/blockquote' } ]
  }
]

Note that three of the four 'replace' linOps affect tree structure in interesting ways, implicitly replacing, reparenting and splitting content.

TreeModifier translates that linOp sequence into the corresponding treeOp sequence shown below (some properties have been omitted for clarity):

treeOps = [
   { type: 'insertNode', at: [ 0 ], element: { type: 'blockquote' } },
   { type: 'insertNode', at: [ 0, 0 ], element: { type: 'paragraph' } },
   { type: 'moveText', from: [ 1, 0 , 0 , 0 ], to: [ 0, 0, 0 ], length: 3 },
   { type: 'insertNode', at: [ 0, 1 ], element: { type: 'paragraph' } },
   { type: 'moveText', from: [ 1, 0, 0, 0 ], to: [ 0, 1, 0 ], length: 3 },
   { type: 'removeText', at: [ 1, 0, 0, 0 ], data: ['b', 'a', 'z' ] },
   { type: 'insertText', at: [ 0, 1, 3 ], data: [ 'B', 'A', 'Z' ] },
   { type: 'removeNode', at: [ 1, 0, 0 ], element: { type: 'paragraph'} },
   { type: 'moveNode', from: [ 1, 0, 0 ], to: [ 0, 2 ] },
   { type: 'removeNode', at: [ 1, 0 ], element: { type: 'listItem' } },
   { type: 'removeNode', at: [ 1 ], element: { type: 'list' } }
]

The number arrays represent paths to the node from the tree root, so say [ 1, 2, 3, 6 ] means the sixth offset inside the third child of the second child of the first child of the tree root. If inside a ContentBranchNode, 'offset' means the offset in the character content; otherwise, it means the offset in the child node array.

Paths represent the tree as modified by previous tree operations. This makes it simple to apply each operation incrementally; it also makes it possible to insert content into an inserted node.

Note how the tree operations work in this example:

• A new blockquote is created, then a paragraph inside, into which text is moved from the old first paragraph.
• Then a second paragraph is created, into which more text is moved (hence representing the paragraph split).
• The text replacement becomes a text removal inside the old node followed by a text insertion at the new node.
• Then the old first paragraph (which is now empty) is removed; and the old second paragraph is moved into the blockquote.
• Finally the old listItem and list nodes are removed.

Looking at the HTML diff, it can be verified that these steps result in the same changes as the linear transaction.

Algorithm for translating linOps to treeOps

Recall:

• A transaction consists of a sequence of linear operations (linOps) to be applied to the linear model of a particular document state, resulting in a new document state.
• The two main linear operations are ‘retain’, which simply steps over content, and ‘replace’, which splices content at the current offset.
• TreeModifier translates the linOp sequence into a sequence of tree operations (treeOps).
• There is not a 1-1 correspondence between linOps and treeOps: two linOps might give rise to three treeOps, say.
• Each treeOp operates either on a node or a text sequence.
• A node treeOp either inserts/removes a single empty node, or moves a single node (which need not be empty).
• A text treeOp either inserts/removes a block of text, or moves a block of text.
• Therefore, each treeOp also corresponds to a linear model splice (two splices in the case of move treeOps). So treeOps can be applied incrementally while keeping the linear model and spanning tree in sync.
• Each treeOp specifies the position(s) in the tree at which content is inserted, removed or moved.

Overview

The algorithm makes a single pass through the sequence of linOps, building a sequence of treeOps as it goes. It uses two pointers, the “remover” and “inserter”, which start at the beginning of the tree (just inside the document node) and make a single pass through the tree in document order as the linOps are processed.

When creating treeOps, the positions always correspond to the current pointer positions: removals always happen at the remover; insertions always happen at the inserter; and moves always go from the remover to the inserter.

In code, both remover and inserter are ve.dm.TreeCursor objects.

Pointer positions

Each pointer represents its current position as a (node, offset) pair, with the node referenced as an index path from the document node. So { path: [ 3, 4 ], offset: 0 } represents the zeroth offset inside documentNode.children[ 3 ].children[ 4 ] . Inside a ContentBranchNode, the offset is counted in characters from the start of the text content; elsewhere, the offset is counted in the children list. In code, these pointers are ve.dm.TreeCursor objects.

When appending treeOps, positions are calculated as follows:

• When an insertion treeOp is appended, its ‘at’ property is always based on the inserter position.
• When a removal treeOp is appended, its ‘at’ property is always based on the remover position.
• When a move treeOp is appended, its ‘from’ property is always based on the remover position, and its ‘to’ property is always based on the inserter position.
• All these positions are translated to take account of previous treeOps in the sequence. This means the code to actually apply the treeOps will not have to worry about translating positions.

The TreeModifier calculates the treeOps to modify the tree, without actually performing those modifications. So as it calculates, it needs to keep track of what changes it will apply, in order that it can translate positions correctly. It does this by keeping an adjustmentTree showing where nodes will be inserted/removed, and also tracking insertedPositions which is the current chain of nested new nodes being created (in which the translated inserter positions must logically lie).

Either pointer can be in front of the other, depending on the situation. There are important restrictions on the relative positions they can take.

Advancing a pointer n linear offsets

The linOps contain linear model offset lengths. These correspond cleanly to features encountered when walking the spanning tree in document order:

• Stepping into/out of a (structural) node consumes one offset.
• Stepping over text consumes the number of characters passed.
• Stepping across a node consumes its length. Note that length is actually cached in each spanning tree node object, but it is simply 2 + the sum of child node lengths, or for a ContentBranchNode, 2 + the text length. (The 2 accounts for the open and close tags)

For efficiency and cleanliness, the pointer steps across nodes rather than entering them where possible; e.g. if it needs to advance 40 linear offsets, and the next node has length 16, it can step across it, leaving 24 more linear offsets to advance.

Text treeOps and node treeOps

The treeOp is a text operation (removeText, insertText or moveText) if the relevant cursor is inside a ContentBranchNode. Otherwise, the operation is a node operation (removeNode, insertNode, or moveNode).

Translating linOps to treeOps

When the linOp says to remove n items:

Advance the remover n offsets.

• For any content stepped across, append a remove treeOp.
• Mark for deletion any node it steps into.
• For any node it steps out of that is marked for deletion, append a removeNode treeOp.

When the linOp says to insert n items:

• For each open tag, append an insertNode treeOp.
• For each close tag, do nothing (except stepping the inserter position out of either created content or existing content, as appropriate).
• For each range of character content, append an insertText treeOp.

When the linOp says to retain n items:

If the remover and the inserter are at the same offset, then advance both in sync without appending any tree operations.

Else advance the remover n offsets.

• For any content it steps across, append a move treeOp.
• Mark for deletion any node it steps into, and append a corresponding insert treeOp.
• For any node it steps out of, append a removeNode tree operation if the node is marked for deletion, and step the inserter out of its node. (This may cause the remover and the inserter to be at the same offset, in which case advance both in sync from here on).

Appending a remove treeOp

If the remover is inside a ContentBranchNode, append:

{
  type: ‘removeText’,
  at: <translated remover offset>,
  data: <array of linearized text to remove>
}

Else append:

{
  type: ‘removeNode’,
  at: <translated remover offset>,
  element: { type: <node to remove> }
}

Note the element in removeNode is implicitly empty.

Appending an insert treeOp

If the inserter is inside a ContentBranchNode, append:

{
  type: ‘insertText’,
  at: <translated inserter offset>,
  data: <array of linearized text to insert>
}

Else append:

{
  type: ‘insertNode’,
  at: <translated inserter offset>,
  element: { type: <node to insert> }
}

Appending a move treeOp

If the inserter is inside a ContentBranchNode, append:

{
  type: ‘moveText’,
  from: <translated remove offset>,
  to: <translated inserter offset>,
  length: <number of characters to move>
}

Else append:

{
  type: ‘moveNode’,
  from: <translated remove offset>,
  to: <translated inserter offset>
}

Note neither move treeOp specifies the actual content moved.