First, diff algorithm

Diff algorithm is an efficient algorithm to compare tree nodes in the same layer, which avoids layer by layer traversal of the tree and reduces time complexity.

Diff algorithm has two characteristics:

  • Peer comparisons, not across layers.
  • Diff cycles are drawn in from the sides to the middle.

Second, Vue Diff algorithm

The core of Vue's virtual DOM diff lies in the patch process

2.1 Mark the start and end positions of the old and new VNodes

let oldStartIndex = 0;
let oldEndIndex = oldChildren.length - 1;
let oldStartVnode = oldChildren[0];
let oldEndVnode = oldChildren[oldEndIndex];
let newStartIndex = 0;
let newEndIndex = newChildren.length - 1;
let newStartVnode = newChildren[0];
let newEndVnode = newChildren[newEndIndex];
Copy the code

2.2 Mark the node position and cycle the node

  • If the current oldStartVnode and newStartVnode nodes are the same, the new node is directly used to reuse the old node to reuse patchVnode. Update oldStartVnode, newStartVnode, oldStartIndex++, and newStartIndex++.
  • If the current oldEndVnode and newEndVnode nodes are the same, the new node is directly used to reuse the old node, perform patchVnode reuse, and update oldEndVnode, newEndVnode, oldEndIndex–, and newEndIndex–.
  • If the current oldStartVnode and newEndVnode nodes are the same, the new node is directly used to reuse the old node, and then the patchVnode is moved to oldEndVnode. Update oldStartVnode, newEndVnode, oldStartIndex++, newEndIndex–.
  • If the current oldEndVnode and newStartVnode nodes are the same, the new node is directly used to reuse the old node, and the patchVnode is reused to move the old node before oldStartVnode. Update oldStartVnode, newEndVnode, oldEndIndex–, newStartIndex–.
  • If they are not, the same node will not be reused, and key comparison will be performed. If the conditions are met, patchVnode will be performed, and DOM will be moved to the real DOM corresponding to oldStartVnode. If no dom is found, it will be created again.

2.3 Recursive processing

Vue Diff diagram

  • The first step:Create four Pointers: start pointer and end pointer for the old Vnode and start pointer and end pointer for the new Vnode.
  • The second step:Compare the start pointer of the old Vnode with the start pointer of the new Vnode, i.eAandEIs found to be different from the same node.
  • Step 3:Then compare the end pointer of the old Vnode with the end pointer of the new Vnode, i.eDandF, still not the same node.
  • Step 4:Then compare the start pointer of the old Vnode with the end pointer of the new Vnode, i.eAandFIs not the same node.
  • Step 5:Then compare the end pointer of the old Vnode with the start pointer of the new Vnode, i.eEandDIs not the same node.
  • Step 6:None of the four comparison methods mentioned above are the same node. The following is to find whether there is and in the old VnodeEA node with the same node.
  • Step 7:The old Vnode does not exist. ProcedureENode, then a new Vnode is inserted before the old Vnode starts pointerENode.
  • Step 8:After the operation of the first node, the pointer moves back, and the comparison continues. Repeat steps 2 to 7, and the result is add, delete, and move.
  • Step 9:Passes if the same node is foundpatchVnodeCarry out the two nodes in more detaildiff.

conclusion

Each diff calls the updateChildren method to compare and then recurses until all the children of the old Vnode and the new Vnode are compared. DomDiff’s process is more like the comparison of two trees. Every time the same node is found, the child nodes are compared layer by layer, which is a deep recursive traversal comparison process.