Vue3 DIff algorithm graphical analysis

Hello everyone, I’m Jian Darui. This article mainly analyzes Vue3 Diff algorithm. From this article, you can know:

  • diffThe main process, the core logic
  • diffHow to reuse, move, and uninstall nodes
  • And there is a sample question, can be combined with the text for practice analysis

If you are not familiar with the patch process of Vnode and renderer, it is recommended to read the following two articles:

  • Vnode
  • Renderer analysis

1.0 diff 无keyChild nodes

When handling UNKEYED_FRAGMENT marked.

  • The minimum commonLength commonLength is first obtained from the old and new self sequences.

  • Loop through patch over the public part.

  • After the patch is complete, the remaining nodes are processed.

  • If oldLength > newLength, the old node needs to be unmounted

  • Otherwise, a node is added and needs to be mounted.

The omitted code is posted here.

const patchUnkeyedChildren = (c1, c2,... res) = > {
    c1 = c1 || EMPTY_ARR
    c2 = c2 || EMPTY_ARR
    // Get the length of the old and new child nodes
    const oldLength = c1.length
    const newLength = c2.length
    // 1. Get public length. Minimum length
    const commonLength = Math.min(oldLength, newLength)
    let i
    // 2. Patch public part
    for (i = 0; i < commonLength; i++) { 
      patch(...)
    }
    // 3. Uninstall the old node
    if (oldLength > newLength) {
      // remove old
      unmountChildren(...)
    } else {
      // mount new
      // 4. Otherwise, mount new child nodesmountChildren(...) }}Copy the code

As you can see from the code above, the logic is pretty straightforward when dealing with keyless children. To be exact, the efficiency of processing keyless child nodes is not high.

Since both the public patch and mountChildren of newly added nodes are performed recursively, performance will be affected.

2.0 diff 有keyChild node sequence

When diff has a key subsequence, subdivision is done. It will mainly be judged in the following situations:

  • The nodes at the start location are of the same type.
  • End Location The node type is the same.
  • A new node is added after the same part is processed.
  • After the same part is processed, some old nodes need to be uninstalled.
  • The beginning and end are the same, but there are reusable out-of-order nodes in the middle part.

At the beginning, Mr. Hui made three comments, namely:

  • i = 0, pointing to the beginning of the old and new sequence
  • e1 = oldLength - 1, pointing to the end of the old sequence
  • e2 = newLength - 1, pointing to the end of the new sequence

let i = 0
const l2 = c2.length
let e1 = c1.length - 1 // prev ending index
let e2 = l2 - 1 // next ending index
Copy the code

Let’s start diff processing by case.

2.1 Start Location Nodes of the same type

  • For nodes of the same starting position type, diff traversal is performed from left to right.

  • If the new and old nodes are of the same type, patch is processed

  • If the node type is different, break and diff is jumped

// i <= 2 && i <= 3
while (i <= e1 && i <= e2) {
  const n1 = c1[i]
  const n2 = c2[i]
  if (isSameVNodeType(n1, n2)) {
    // If the node type is the same, recursive patch is performed
    patch(...)
  } else {
    // Otherwise exit
    break
  }
  i++
}
Copy the code

Part of the code is omitted above, but the main logic is not affected.

As you can see from the code, traversal, using the three Pointers declared earlier in the function’s global context, traversal judgment.

Ensure sufficient traversal to the same starting position, I <= e1&&i <= e2.

Once a node of a different type is encountered, the diff traversal is skipped.

2.2 End Location The node types are the same

The diff ends at the same starting position and is then iterated from the end of the sequence.

In this case, the tail Pointers E1 and E2 need to be decrement.

// i <= 2 && i <= 3
// After the end: e1 = 0 e2 = 1
while (i <= e1 && i <= e2) {
  const n1 = c1[e1]
  const n2 = c2[e2]
  if (isSameVNodeType(n1, n2)) {
    // Same node type
    patch(...)
  } else {
    // Otherwise exit
    break
  }
  e1--
  e2--
}
Copy the code

It can be seen from the code that the diFF logic is basically the same as the first one, and the patch processing is performed in the same type.

Different types of break break out of the loop.

And decrement the tail pointer.

2.3 After the traversal of the same part is complete, a new node is added to a new sequence

After the processing of the above two cases, the nodes with the same parts at the beginning and end have been patched, and the next step is to patch the new nodes in the new sequence.

After the above two payment requests are processed, if a new node is added, I > E1&&I <= E2 may occur.

In this case, it means that there are new nodes in the new child node sequence.

In this case, patch is performed on the new node.

// 3. common sequence + mount
// (a b)
// (a b) c
// i = 2, e1 = 1, e2 = 2
// (a b)
// c (a b)
// i = 0, e1 = -1, e2 = 0
if (i > e1) {
  if (i <= e2) {
    const nextPos = e2 + 1
    NextPos < l2, indicating that the tail node has been patched,
    // Otherwise the parent node is taken as the anchor point
    const anchor = nextPos < l2 ? c2[nextPos].el : parentAnchor
    while (i <= e2) {
      patch(null, c2[i], anchor, ... others) i++ } } }Copy the code

As can be seen from the above code, the first parameter was not passed during patch, and eventually the logic of mount would be used.

You can see the process of patch analysis in this article

During the patch process, the I pointer will be incremented.

And get anchor points through nextPos.

If nextPos < L2, the patched node is used as the anchor; otherwise, the parent node is used as the anchor.

2.4 After the traversal of the same part, there are fewer nodes in the new sequence, and the uninstallation is performed

If I > E2&&i <= E1 occurs after the nodes with the same end are processed, it indicates that there are old nodes that need to be uninstalled.

// 4. common sequence + unmount
// (a b) c
// (a b)
// i = 2, e1 = 2, e2 = 1
// a (b c)
// (b c)
// i = 0, e1 = 0, e2 = -1
// Public sequence unloads the old
else if (i > e2) {
  while (i <= e1) {
    unmount(c1[i], parentComponent, parentSuspense, true)
    i++
  }
}
Copy the code

As you can see from the code, in this case the I pointer is incremented to unload the old node.

2.5 Disorder

In this case, it is complicated, but the core logic of DIFF is to build a maximum increasing subsequence through the position changes of old and new nodes, and the maximum subsequence can ensure the reuse of nodes through the minimum movement or patch.

So let’s see how that works.

2.5.1 Build a new child nodekey:indexmapping

// 5
// [i ... e1 + 1]: a b [c d e] f g
// [i ... e2 + 1]: a b [e d c h] f g
// i = 2, e1 = 4, e2 = 5

const s1 = i // s1 = 2
const s2 = i // s2 = 2

// 5.1 build key:index map for newChildren
// First build the mapping of key: index in the new subsequence for the new child node
// New child nodes created by map
const keyToNewIndexMap = new Map(a)// Traverses the new node and sets the key for the new node
// i = 2; i <= 5
for (i = s2; i <= e2; i++) {
  // Get the child nodes in the new sequence
  const nextChild = c2[i];
  if(nextChild.key ! =null) {
    Nextchild. key already exists
    // a b [e d c h] f g
    // e:2 d:3 c:4 h:5
    keyToNewIndexMap.set(nextChild.key, i)
  }
}
Copy the code

Combined with the above diagram and code, you can see:

  • After patch treatment with the same beginning and end, I = 2, E1 = 4, e2 = 5

  • After traversal, the key:index relationship of the new node in keyToNewIndexMap is E: 2, D: 3, C: 4, and H: 5

  • KeyToNewIndexMap is mainly used to determine the position of reusable nodes in the new subsequence by iterating through the old subsequence

2.5.2 Traversing the old subsequence from left to right,patchMatching nodes of the same type, remove nodes that do not exist

After the previous processing, a keyToNewIndexMap has been created.

Before you start traversing from left to right, you need to know what a few variables mean:

// 5.2 loop through old children left to be patched and try to patch
// matching nodes & remove nodes that are no longer present
// Start the patch loop from the left of the old child node.
// Patch matched nodes and remove nonexistent nodes

// Number of patch nodes
let patched = 0
// Number of nodes that require patch
// e2 = 5; s2 = 2; Knows the number of nodes for which patch is required
// toBePatched = 4
const toBePatched = e2 - s2 + 1
// Used to determine whether a node needs to be moved
// Moved = true when reusable nodes cross between old and new queues
let moved = false
// used to track whether any node has moved
// Records whether the node has been moved
let maxNewIndexSoFar = 0

// works as Map<newIndex, oldIndex>
// subscript mapping of old and new nodes
// Note that oldIndex is offset by +1
// Note that the index of the old node is offset by a subscript to the right

// and oldIndex = 0 is a special value indicating the new node has
// no corresponding old node.
// The old node Index = 0 is a special value used to indicate that the new node has no corresponding old node

// used for determining longest stable subsequence
// newIndexToOldIndexMap is used to determine the longest increasing subsequence
// Map of new and old subscripts
const newIndexToOldIndexMap = new Array(toBePatched)
// Initialize all values to 0
// [0, 0, 0, 0]
for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0
Copy the code
  • variablepatchedUsed to recordpatchThe nodes of the
  • variabletoBePatchedUsed to record what needs to be donepatchNumber of nodes
  • variablemovedUsed to record whether any reusable nodes have crossed
  • maxNewIndexSoFarUsed to record when old subsequences exist without settingkey, but the child node appears in a new subsequence, and can be reused, maximum subscript.
  • variablenewIndexToOldIndexMapUsed for mappingSubscripts of nodes in a new subsequenceCorresponding to theThe subscript of a node in an old subsequence
  • And willnewIndexToOldIndexMapInitialize to an array of all zeros,[0, 0, 0, 0]

Now that we know what these variables mean we can start traversing the subsequence from left to right.

When you iterate, you first iterate through the old subsequence, starting at S1 and ending at E1.

Patched will be accumulated during the traversal process.

Uninstalling the old node

Patched >= toBePatched, the number of children in the new subsequence is smaller than the number of nodes in the old subsequence.

The old child nodes need to be unmounted.

// Iterate over unprocessed old sequence neutron nodes
for (i = s1; i <= e1; i++) {
    // Get the old node
    // Get c d e one by one
    const prevChild = c1[i]
    // If the number of existing patches is greater than the number of nodes to be patched
    
    // patched Starts with 0
    // patched >= 4
    if (patched >= toBePatched) {
      // all new children have been patched so this can only be a removal
      // This means that all new nodes have been patched so that the old ones can be removed
      unmount(prevChild, parentComponent, parentSuspense, true)
      continue}}Copy the code

If prevChild.key exists, the prevChild subscript newIndex in the new subsequence is obtained using the keyToNewIndexMap we built earlier.

To obtainnewIndex
// New node subscript
let newIndex
if(prevChild.key ! =null) {
  // Old nodes must have keys,
  // Get the new child node of the same type in the new queue according to the old node key
  // This time because c, d, e are the original nodes and have keys
  // h is the new node. The old node does not get the corresponding index
  // So newIndex starts with the following situation
  /** * node newIndex * c 4 * d 3 * e 2 * */ 
  // You can get the newIndex
  newIndex = keyToNewIndexMap.get(prevChild.key)
}
Copy the code

Taking the figure as an example, it can be known that nodes C, D and E are reusable nodes in the traversal process, corresponding to positions 2, 3 and 4 in the new subsequence respectively.

Therefore, the values of newIndex can be 4, 3 and 2.

What if the old node does not have a key?

// key-less node, try to locate a key-less node of the same type
// If the old node does not have a key
// A new node of the same type without a key is found in the new node queue
// j = 2: j <= 5
for (j = s2; j <= e2; j++) {
  if (
    newIndexToOldIndexMap[j - s2] === 0 &&
    // Check whether the old and new nodes are the same
    isSameVNodeType(prevChild, c2[j])
  ) {
    // Get the index of the node of the same type
    newIndex = j
    break}}Copy the code

If the node does not have a key, it will also take a new subsequence and iterate to find two children without a key and of the same type as the old and new, and use the subscript of this node as the newIndex.

NewIndexToOldIndexMap [J-s2] === 0 Indicates that the node does not have a key.

If newIndex has not been retrieved, the prevChild does not exist in the new subsequence and needs to be uninstalled.

if (newIndex === undefined) {
  // There is no corresponding new node to uninstall the old node
  unmount(prevChild, parentComponent, parentSuspense, true)}Copy the code

Otherwise, build a keyToNewIndexMap based on the newIndex to determine the subscript positions of the old and new nodes.

Keep in mind that newIndex is derived from the subscript of the old node in the new subsequence.

// Handle the case where newIndex is obtained
// The Index Index of the new node is mapped to the old queue of the same type
// The subscript of the new node starts s2=2, and the corresponding subscript of the old node needs to be offset by one subscript
// 0 indicates that the current node has no corresponding old node
// start with s1 = 2, s2 = 2
// get subscript 2, the new c node corresponds to the location of the old C node subscript 3
// get subscript 1. The new d node corresponds to the location of the old d node with subscript 4
// the new e node corresponds to the position of the old e node with subscript 5
// [0, 0, 0, 0] => [5, 4, 3, 0]
// [2,3,4,5] = [5, 4, 3, 0]
newIndexToOldIndexMap[newIndex - s2] = i + 1
// newIndex will take 4, 3, 2
/** * newIndex maxNewIndexSoFar moved * 4 0 false * 3 4 true * 2 * * */ 
if (newIndex >= maxNewIndexSoFar) {
  maxNewIndexSoFar = newIndex
} else {
  moved = true
}
Copy the code

When constructing newIndex TooldIndexMap, the relationship between newIndex and maxNewIndexSoFa will be determined to determine whether the node moves.

The end of the last traversal of newIndexToOldIndexMap should be [5, 4, 3, 0], 0 indicates that there is no node corresponding to the heart sequence in the old sequence, and this node may be a new node.

If the relative positions of the old and new nodes remain constant in the sequence, maxNewIndexSoFar will increase as newIndex increases.

Means that the nodes have not crossed. There is no need to move reusable nodes.

Otherwise, the reusable node moves, and you need to move the reusable node.

At the end of the traversal, patch old and new nodes and cumulative them. Record that several nodes have been processed.

// Perform recursive patch
/** * old new * c c * d d * e e */
patch(
  prevChild,
  c2[newIndex],
  container,
  null,
  parentComponent,
  parentSuspense,
  isSVG,
  slotScopeIds,
  optimized
)
// It has been patched
patched++
Copy the code

After the above processing, the old node has been uninstalled, and the patch reuse has been carried out for the child nodes whose relative positions remain unchanged.

The next step is to move the reusable nodes and mount the new nodes in the new subsequence.

2.5.3 Moving a Reusable Node to Mount a New Node

This involves a core piece of code, which is the key to Vue3 DIff’s efficiency improvement.

The subscript mapping before and after the change of the old and new child nodes was recorded by newIndexToOldIndexMap.

Here a maximum increasing subsequence is obtained using the getSequence method. Used to record subscripts of child nodes whose relative positions have not changed.

According to this increasing subsequence, only the child nodes whose relative positions change before and after can be moved when the reusable nodes are moved.

Make minimal changes.

So what is a maximally increasing subsequence?
  • A subsequence is a sequence derived from an array that deletes (or does not delete) the elements of the array without changing the order of the rest of the elements.
  • The increasing subsequence is a subsequence derived from an array, and the relationship between each element is kept increasing one by one.
  • Such as:
  • An array of[3, 6, 2, 7)Is an array[0, 3, 1, 6, 2, 2, 7]Is the longest strictly increasing subsequence of.
  • An array of[2, 3, 7, 101]Is an array[10, 9, 2, 5, 3, 7, 101, 18]Maximal increasing subsequence of.
  • An array of[0, 1, 2, 3]Is an array[0, 1, 0, 3, 2, 3]Maximal increasing subsequence of.

As shown in the figure above, there are newly added nodes N and I, nodes G to be uninstalled, and reusable nodes C, D, E, and F among the unprocessed out-of-order nodes.

The relative position of node CDE does not change in the old and new subsequences. If node reuse is realized through minimal change, we can find the subscript position of F node before and after the change and insert F node before the new subsequence C node.

The purpose of the maximum-incrementing subsequence is to create an incrementing array by mapping old and new nodes before and after the change, so that you can know which nodes have not changed relative position before and after the change, and which nodes need to be moved.

The difference of the increasing subsequence in Vue3 is that it holds the subscripts of the reusable nodes in the newIndexToOldIndexMap. It is not an element in newIndexToOldIndexMap.

Let’s look at the code:

// move and mount
// generate longest stable subsequence only when nodes have moved
// The mobile node mounts the node
// Generate the longest increasing subsequence only when the node is moved
NewIndexToOldIndexMap = [5, 4, 3, 0]
/ / get increasingNewIndexSequence = [2]
const increasingNewIndexSequence = moved
  ? getSequence(newIndexToOldIndexMap)
  : EMPTY_ARR
// j = 0
j = increasingNewIndexSequence.length - 1
// looping backwards so that we can use last patched node as anchor
// Iterate backwards so that the latest patched node can be used as the anchor
// i = 3
for (i = toBePatched - 1; i >= 0; i--) {
  // 5 4 3 2
  const nextIndex = s2 + i
  // 节点 h  c  d  e 
  const nextChild = c2[nextIndex]
  // Get the anchor point
  const anchor =
    nextIndex + 1 < l2 ? c2[nextIndex + 1].el : parentAnchor
  // [5, 4, 3, 0] node H will be patched, actually mount
  // c, d, e will be moved
  if (newIndexToOldIndexMap[i] === 0) {
    // mount new
    // Mount new
    patch(
      null,
      nextChild,
      container,
      anchor,
      ...
    )
  } else if (moved) {
    // move if:
    // There is no stable subsequence (e.g. a reverse)
    // OR current node is not among the stable sequence
    // If there is no longest increasing subsequence or the current node is not in the middle of increasing subsequence
    // Move the node
    // 
    if (j < 0|| i ! == increasingNewIndexSequence[j]) { move(nextChild, container, anchor, MoveType.REORDER) }else {
      j--
    }
  }
}
Copy the code

As you can see from the above code:

  • throughnewIndexToOldIndexMapThe maximum increment subsequence obtained is[2]
  • j = 0
  • When traversing, traverse from right to left, so that you can get the anchor points, if any have already passedpatch, the sibling node is used as the anchor point, otherwise the parent node is used as the anchor point
  • newIndexToOldIndexMap[i] === 0“Indicates a new node. You need to do something on the nodemount, then just givepatchPass the first argument tonullCan. You can see that the first thing is going to be rightH nodesforpatch.
  • Otherwise it will judgemovedWhether it istrue. We know from the previous analysisNode C and node EThere is a shift in position in the back and forth.
  • So it’s going to move nodes. We know thatjAt this time for0.iAt this time for * *2**i ! == increasingNewIndexSequence[j]fortrueIt doesn’t moveC nodeBut rather the executionj--.
  • Because behindj < 0Will,D and E nodesMove.

So far, we have completed the study and analysis of Vue3 Diff algorithm.

Here is an example that you can practice with the analysis of this article:

You can just look at the first picture for analysis, and then compare it with the second and third pictures.

Graph one:

Figures 2 & 3:

conclusion

From the above learning analysis, it can be known that Vue3’s DIFF algorithm will first finish the patch processing of the same node, and then mount the new node and uninstall the old node.

If the subsequence is complicated, such as out of order, the reusable node will be identified first, and a maximum increasing subsequence will be constructed through the position mapping of the reusable node, and the node will be mounted & moved by the maximum increasing subsequence. In order to improve diFF efficiency, realize the maximum possibility of node reuse.