Diff algorithm execution process

Before describing the execution process of the DIFF algorithm, the first thing we need to know is what is the comparison object of the diFF algorithm of the virtual DOM? And how to describe the virtual DOM, do you really create a DOM tree comparison or something else?

  • The diff algorithm in the virtual DOM needs to compare the differences between each node of the two trees
  • Instead of manipulating the DOM directly when the data changes, the real DOM is described as a JS object
  • When the data changes, first compare whether the JS object has changed, find all changed positions, and then minimize the update of the changed position
The execution process of diFF algorithm:

  1. Run patch function to pass in the old and new nodes, such as PACTH (oldVnode, vNode).

  2. Check whether the oldVnode and vnode are the same. Note that snabbDOM converts oldvNodes and vNodes into vNode objects before recalling old and new nodes. Then the same judgment is still the same node (vnode.key && vnode.sel).

  3. If the two nodes are different, insert a new node (vNode) into the parent node, then delete the old node (oldVnde). (Differences are best handled)

  4. If the key&& SEL of two nodes are the same, it is necessary to compare the text and child nodes (array) of the two nodes to find the difference.

  5. If the text of the new node is different from that of the old node, you only need to update the text content and delete all the children of the old node. (Differences are best handled)

  6. If only the new node has the child node array, reset the text of the old node to empty and add the new node array. (Differences are best handled)

  7. If only the old node has child node arrays, delete all child node arrays. (Differences are best handled)

  8. If both new and old nodes have arrays of child nodes, and the child nodes are different (same key&& SEL, but different array of child nodes, most complicated processing logic)

  9. In this step, it is found that the new parent node array comparison, so it must be a loop traversal. So this is the next thing you can look at the snabbDOM source code and see that there are a couple of variables

    // The starting and ending positions of the old and new node arrays
let oldStartIdx = 0;
let newStartIdx = 0;
let oldEndIdx = oldCh.length - 1;
let newEndIdx = newCh.length - 1;
​
// The data corresponding to the starting and ending positions of the old and new node arrays
let oldStartVnode = oldCh[0];
let oldEndVnode = oldCh[oldEndIdx];
let newStartVnode = newCh[0];
let newEndVnode = newCh[newEndIdx];
Copy the code

  10. Based on Step 9, you can see that this step returns to step 3 of the execution flow when traversing the comparison node content.

The simple pseudo-code implementation flow is as follows. Code comments may help to understand the flow:
function init () {
  function updateChildren (oldCh,newCh){
    // The following parameters help you understand that traversal is a subscript movement
    let oldStartIdx = 0;
    let newStartIdx = 0;
    let oldEndIdx = oldCh.length - 1;
    let oldStartVnode = oldCh[0];
    let oldEndVnode = oldCh[oldEndIdx];
    let newEndIdx = newCh.length - 1;
    let newStartVnode = newCh[0];
    let newEndVnode = newCh[newEndIdx];
    let oldKeyToIdx: KeyToIndexMap | undefined;
    let idxInOld: number;
    let elmToMove: VNode;
    let before: any;
​
    // Compare nodes of the same level
    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if (oldStartVnode == null) {
        oldStartVnode = oldCh[++oldStartIdx]; // Vnode might have been moved left
      } else if (oldEndVnode == null) {
        oldEndVnode = oldCh[--oldEndIdx];
      } else if (newStartVnode == null) {
        newStartVnode = newCh[++newStartIdx];
      } else if (newEndVnode == null) {
        newEndVnode = newCh[--newEndIdx];
      } else if (sameVnode(oldStartVnode, newStartVnode)) {
        // The new and old start positions are the same
        patchVnode(oldStartVnode, newStartVnode);
        oldStartVnode = oldCh[++oldStartIdx];
        newStartVnode = newCh[++newStartIdx];
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
        // The new and old start positions are the same
        patchVnode(oldEndVnode, newEndVnode);
        oldEndVnode = oldCh[--oldEndIdx];
        newEndVnode = newCh[--newEndIdx];
      } else if (sameVnode(oldStartVnode, newEndVnode)) {
        // Same node and the new and old start positions are different, if the same interaction position
        // Vnode moved right
        patchVnode(oldStartVnode, newEndVnode);
        api.insertBefore();
        oldStartVnode = oldCh[++oldStartIdx];
        newEndVnode = newCh[--newEndIdx];
      } else if(sameVnode(oldEndVnode, newStartVnode)) {/ peer node and the new and old start positions are different, if the same interaction position// Vnode moved left
        patchVnode(oldEndVnode, newStartVnode);
        api.insertBefore();
        oldEndVnode = oldCh[--oldEndIdx];
        newStartVnode = newCh[++newStartIdx];
      } else {
        // createKeyToOldIdx gets the keys of all the old nodes in the array. This is probably the most troublesome place to compare
        if (oldKeyToIdx === undefined) {
          oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
        }
        // The final theoretical scenario is to insert the new node into the parent element of the old node
        // Find the old node idea node array key
        // Find the new start node's key is not empty and insert the parent element
        idxInOld = oldKeyToIdx[newStartVnode.key as string];
        if (isUndef(idxInOld)) {
          // New element
          api.insertBefore();
        } else {
          elmToMove = oldCh[idxInOld];
          if(elmToMove.sel ! == newStartVnode.sel) { api.insertBefore(); }else {
            patchVnode(elmToMove, newStartVnode);
            oldCh[idxInOld] = undefined asany; api.insertBefore(); } } newStartVnode = newCh[++newStartIdx]; }}// Wrap up the loop
    if (oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx) {
      if (oldStartIdx > oldEndIdx) {
        before = newCh[newEndIdx + 1] = =null ? null : newCh[newEndIdx + 1].elm;
        addVnodes();
      } else{ removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx); }}}function patchVnode(oldVnode,vnode) {
    if (oldVnode === vnode) return;
    if (isUndef(vnode.text)) { 
      if (isDef(oldCh) && isDef(ch)) {
        // If the child nodes of the old and new nodes exist and are different, compare the child nodes one by one, if you want to traverse
        if(oldCh ! == ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue); }else if (isDef(ch)) {
        // Only the array of children of the new node has values
        // Reset the text parameters
        if (isDef(oldVnode.text)) api.setTextContent(elm, "");
        addVnodes();
      } else if (isDef(oldCh)) {
        // Only the array of children of the old node has values to remove all children
        removeVnodes();
      } else if (isDef(oldVnode.text)) {
        // Only the text of the old node has values for the reset argument
        api.setTextContent(elm, ""); }}else if(oldVnode.text ! == vnode.text) {if (isDef(oldCh)) {
        // If the array of children of the old node is not empty, delete it
        removeVnodes()
      }
      api.setTextContent(elm, vnode.text!);
    }
  }
​
  return patch(oldVnode,vnode) {
    if(! isVnode(oldVnode)) {// Convert oldVnode to VNode for the first time
      oldVnode = emptyNodeAt(oldVnode)
    }
    // Compare two nodes to see if they are the same key && sel
    if (sameVnode(oldVnode, vnode)) { 
      // Compare the new and old node parameters
      patchVnode(oldVnode, vnode);
    } else {
      // Find out if the parent element exists
      // Create a node
      createElm(vnode);
      // Insert new nodes and remove old nodes
      if(parent ! = =null) { api.insertBefore(parent, vnode.elm! , api.nextSibling(elm)); removeVnodes(parent, [oldVnode],0.0); }}return vnode
  }
}
Copy the code
At the same time, I sorted out a flow chart: