Standing on the shoulders of giants to see VUE, vUE design and implementation from Huo Chunyang. The author explains the underlying vuE3 implementation step by step in the form of questions. The idea is very clever, here will be the main logic in the book series, which is also my own record after reading, I hope that through this form can communicate with everyone to learn.

The opening

The fast algorithm is applied in VUe3, which uses the preprocessing in text Diff for reference. It first processes the pre-node and post-node at the same position of the old and new nodes. After all the nodes after the current node are processed, three situations occur:

After the same before and after the same node is processed, the old node is processed, the new node still has, and then you need to add, iterate over the remaining new nodes and insert them in front of the next node.

Similarly, after the same before and after the same node is processed, the new node is all processed, the old node still has, at this point, you need to uninstall, iterate over the old node uninstall.

When there are unprocessed nodes in both groups, you need to find out which ones need to be added and which ones need to be uninstalled. According to the chapter of simple Diff algorithm, traversing the old node to find the maximum index value, if the key of the new node does not show an increasing rule, it means that the node needs to be moved.

You can build an array of sourcers to store the remaining locations of the new node in the old node. A value of -1 indicates that this is a new node.

Then find the maximum increasing subsequence of sourcer and traverse from the end. When the value of the tail node and source is not equal, it means that it needs to move. Call patch to move, otherwise, only make S point to the next position until the whole traverse is completed.

That’s how fast Diff works.

11.1. Same pre-element and post-element

The old and new sets of nodes remain in the same position in the. No need to move them. The while loop looks for all the same before and after nodes and calls the patch function to update until the nodes have different key values.

function patchKeyedChildren(newChildren, oldChildren, container) {
  // Same front node
  let j = 0
  let oldVNode = oldChildren[j]
  let newVNode = newChildren[j]
  while (oldVNode.key === newVNode.key) {
    patch(oldVNode, newVNode, container)
    j++
    oldVNode = oldChildren[j]
    newVNode = newChildren[j]
  }
  // Same rear node
  let newEnd = newChildren.length - 1
  let oldEnd = oldChildren.length - 1
  let newEndVNode = newChildren[newEnd]
  let oldEndVNode = oldChildren[oldEnd]
  while (newEndVNode.key === oldEndVNode.key) {
    patch(oldEndVNode, newEndVNode, container)
    oldEnd--
    newEnd--
    oldEndVNode = oldChildren[oldEnd]
    newEndVNode = newChildren[newEnd]
  }
}
Copy the code

Case 1: After the same before and after nodes are processed, all the old nodes are processed, and the new nodes still have (new).

Satisfied condition

  1. OldEnd < j holds. The old node is removed
  2. EndEnd >= j; new node needs to be added

The value of anchorIndex is calculated as anchorIndex = newEnd + 1 when adding new nodes. If it is less than the number of new nodes, it means that the anchor element is in the new node, instead, it corresponds to the tail of the node, and the anchor point is not needed at this time

if (j > oldEnd && j <= newEnd) {
  const anchorIndex = newEnd + 1
  const anchor = anchorIndex < newChildren.length ? newChildren[anchorIndex].el : null
  while (j <= newEnd) {
    patch(null, newChildren[j++], container, anchor)
  }
}
Copy the code

Case 2: After the same before and after nodes are processed, the new nodes are completely processed, and the old nodes are still (deleted).

Satisfied condition

  1. J ≤ oldEnd holds. The old node still needs to be deleted
  2. J > newEnd Creates a new node
if (j > oldEnd && j <= newEnd) { / / new
    const anchorIndex = newEnd + 1
    const anchor = anchorIndex < newChildren.length ? newChildren[anchorIndex].el : null
    while (j <= newEnd) {
      patch(null, newChildren[j++], container, anchor)
    }
  } else if (j > newEnd && j <= oldEnd) { / / delete
    while (j <= oldEnd) {
      unmount(oldChildren[j++])
    }
  }
Copy the code

11.2. Determine whether DOM movement is required

In the past, two groups of nodes would eventually be processed by one group of nodes. In this case, simply mount and unmount the nodes.

Case 3: New nodes and old nodes need to be added or deleted

  1. Construct an array source whose length is equal to the number of pre-processed nodes of the new node, starting with -1, to store the index of the position of the new node in the old node
  2. Build an index table keyIndex for the new node, the mapping between the key of the storage node and the location index
  3. The old node is traversed, and the k of the old node goes to the index table to find the location of the new node, which is stored in K
  4. If k says that this node can be reused, call patch update to fill the source array, otherwise uninstall
let newStart = j
let oldStart = j
const count = newEnd - j + 1
const source = new Array(count).fill(-1)
const keyIndex = {} / / index table
for (let i = newStart; i <= newEnd; i++) {
  keyIndex[newChildren[i].key] = i
}
for (let i = oldStart; i <= oldEnd; i++) {
  oldVNode = oldChildren[i]
  const k = keyIndex[oldVNode.key]
  if (typeofk ! = ='undefined') {
    let newVNode = newChildren[k]
    patch(oldVNode, newVNode, container)
    source[k - newStart] = i
  } else {
    unmount(oldVNode)
  }
}
Copy the code
  1. How do I determine if a node needs to be moved

The index values encountered in the process of traversing the old node show an increasing trend, indicating that it is not necessary to move the node, but vice versa. Define a pos value that needs to be moved when k is less than pos, but does not need to be moved. Update the pos value

let moved = false
let pos = 0
for (let i = oldStart; i <= oldEnd; i++) {
  oldVNode = oldChildren[i]
  const k = keyIndex[oldVNode.key]
  if (typeofk ! = ='undefined') {
    let newVNode = newChildren[k]
    patch(oldVNode, newVNode, container)
    source[k - newStart] = i
    if (k < pos) {  // Determine that the node needs to be moved
      moved = true
    } else {
      pos = k
    }
  } else {
    unmount(oldVNode)
  }
}
Copy the code
  1. Add a quantity identifier that represents the number of nodes that have been updated. If the number of nodes that have been updated is larger than the number of nodes that need to be updated, redundant nodes need to be deleted

11.3. How do I move elements

Find the longest increasing subseries of source to find nodes that do not need to be moved. const seq = getSequence(sources)

Seq stores the index of the source.

Seq source KeyIndex New node old node0      2          3:1         p-3       p-2
1 (s)  3          4:2         p-4       p-3
       1          2:3         p-2       p-4
      -1          7:4         p-7  (i)  p-6
                             
Copy the code

Seq indicates that the index value does not need to be moved in the new node. Nodes 3 and 4 do not need to be moved, but only 2 and 7 need to be moved

Create two variables I and s to traverse the new node if seq[s]! If I is equal to I, you need to move, otherwise you just have to point s to the next position

If source[I] === -1 is added directly, mount it on the next node of the new node

const seq = getSequence(source)
let s = seq.length - 1
let i = count - 1
for (i; i >= 0; i--) {
  if (source[i] === -1) {
    const pos = i + newStart
    const newVNode = newChildren[pos]
    const nextPos = pos + 1
    const anchor = nextPos < newChildren.length ? newChildren[nextPos].el : null
    insert(null, newVNode, container, anchor)
  } else if(i ! == seq[s]) {const pos = i + newStart
    const newVNode = newChildren[pos]
    const nextPos = pos + 1
    const anchor = nextPos < newChildren.length ? newChildren[nextPos].el : null
    patch(newVNode.el, container, anchor)
  } else {
    s--
  }
}
Copy the code