Analysis of the principle of diff algorithm

Source: https://blog.csdn.net/m0_64023259/article/details/125476986 (added my own comments and understanding and reduced some descriptions)

Concept

The diff algorithm can be regarded as a comparison algorithm, and the object of comparison is the old and new virtual DOM. The diff algorithm can find the difference between the old and new virtual DOM, and update the real DOM according to the compared result.

What is virtual DOM?

1. An object used to describe the real DOM
2. There are six properties:
   sel (current node label name)
   data (properties of the current node)
   children (other child label nodes under the current node)
   elm (the real node corresponding to the current virtual node)
   key (the key of the current node)
   text (the text under the current node)

let vnode = {<!-- -->
    sel: 'ul', // current node label name
    data: {<!-- -->}, // attributes of the current node
    children: [ // Other child node labels under the current node
        {<!-- -->
            sel: 'li', data: {<!-- --> class: 'item' }, text: 'son1'
        },
        {<!-- -->
            sel: 'li', data: {<!-- --> class: 'item' }, text: 'son2'
        },
    ],
    elm: undefined, // the real node corresponding to the current virtual node
    key: undefined, // the key of the current node
    text: undefined // the text under the current node
}

3. Virtual DOM can be understood as a state of real DOM. When the real DOM changes, the virtual DOM can provide the state of the real DOM before and after the change. By comparing these two states, you can get the difference between the real DOM that needs to be updated, and achieve minimum update. In some complex DOM change scenarios, Updating the real DOM by comparing the virtual DOM will be more efficient than updating the real DOM directly, which is the significance of the existence of the virtual DOM and the diff algorithm.

What is the h function?

1. The h function passed in the render function
2. The h function can accept multiple types of parameters, but only the vnode function is executed inside the function. The parameters passed in when executing the vnode function are determined according to the parameters of the h function passed in.
3. The vnode function only does one thing, that is, converts the parameters passed into the h function into an object, which is the virtual DOM
4. After executing the h function, the virtual DOM will be generated internally through the vnode function, and the h function will return the virtual DOM

// vnode.js vnode (label name of node, attribute of node, child node of node, text of node, real node of current node)
export default function (sel, data, children, text, elm) {<!-- -->
    const key = data.key
    return {<!-- -->sel, data, children, text, elm, key}
}

Comparison rules and process of diff

Through two different virtual nodes, a simplified version of the diff algorithm code introduction and the specific process of diff comparison

// The first parameter is sel (label name) The second parameter is data (the attribute of the node), and the third parameter is children (the child nodes of the current node)
const myVnode1 = h("h1", {<!-- -->}, [
  h("p", {<!-- -->key: "a"}, "a"),
  h("p", {<!-- -->key: "b"}, "b"),
]);
?
const myVnode2 = h("h1", {<!-- -->}, [
  h("p", {<!-- -->key: "c"}, "c"),
  h("p", {<!-- -->key: "d"}, "d"),
]);

patches

The first step in comparing two virtual DOMs is to execute patch. Pass the two virtual DOMs into the patch as parameters.

The main function of patch is to compare the root nodes of two virtual DOMs, and operate the real DOM according to the comparison results.

The core code is as follows:

// patch.js

import vnode from './vnode' // Convert real DOM to virtual DOM
import patchDetails from './patchVnode; // function to compare child nodes
import createEle from './createEle' // generate real DOM according to the incoming virtual DOM

/**
 * @description is used to compare the root nodes of two virtual DOMs, and operate the real DOM according to the comparison results
 * @param {*} oldVnode // parameter one old node
 * @param {*} newVnode // parameter 2 new node
 */
export function patch(oldVnode, newVnode) {<!-- -->
// 1. Determine whether oldVnode is a virtual node, if not, convert it to a virtual node
if(!oldVnode.sel) {<!-- -->
// Convert to a virtual node vnode (label name of the node, attributes of the node, child nodes of the node, text of the node, real node of the current node)
oldVnode = vnode(oldVnode.tagName.toLowerCase(), {<!-- -->}, [], undefined, oldVnode)
}
\t
// 2. Determine whether oldVnode and newVnode are the same node
if(oldVnode.key == newVnode.key & amp; & amp; oldVnode.sel == newVnode.sel) {<!-- -->
// When the key and label name are the same, the root node is the same node, and then compare the child nodes
patchDetails(oldVnode, newVonde)
} else {<!-- -->
// When it is not the same root node, insert a new newVnode
const newVnode = createEle(newVnode) // NewVnode needs to be converted into real DOM before inserting
// insert operation
oldVnode.elm.parentNode.insertBefore(newVnode, oldVnode.elm)
// Delete oleVnode
oldvnode.elm.parentNode.removeChild(oldVnode.elm)
}

}

// createEle.js

/**
 * @description Generate real DOM according to the incoming virtual DOM
 * @param {*} vnode // incoming virtual DOM
 * @returns real node // Return real DOM
 */
export default function createEle(vnode) {<!-- -->
// Create an element node
const realNode = document.createElement(vnode.sel)
\t
// child node conversion
if(vnode.text & amp; & amp; (vnode.children == undefined || (vnode.children & amp; & amp; vnode.children.length == 0)) ) {<!-- -->
// only text in the child node
realNode.innerText = vnode.text
} else if(Array.isArray(vnode.children) & amp; & amp; vnode.children.length > 0) {<!-- -->
// There are other nodes in the child node, add elements recursively
for(let i = 0; i < vnode.children.length; i ++ ) {<!-- -->
const children = createEle(vnode.children[i] // Transform virtual child node DOM into real DOM
realNode.appendChild(childrenNode) // Create child node elements for the node
}
}

// Supplement the elm (real DOM of virtual DOM) attribute of virtual DOM
vnode.elm = realNode
return vnode.elm
}

patchVnode (patchDetails)

It is used to compare the child nodes of two virtual nodes and update the real DOM nodes corresponding to their child nodes

// patchVnode.js

// Judging that the node has children but no text
function hasChildren(node) {<!-- -->
return !node.text & amp; & amp; (node.children & amp; & amp; node.children.length > 0)
}

// Judging that the node has text and no childrn
function hasText(node) {<!-- -->
return node. text & amp; & amp; (node. children == undefined || (node. children & amp; & amp; node. children. length == 0))
}

/**
 * @description Compare the child nodes of two virtual nodes, and update the real DOM node corresponding to its child nodes
 * @param {*} oldVnode // The old node passed in
 * @param {*} newVnode // new node passed in
 * @returns
 */
export function patchDetails(oldVnode, newVnode) {<!-- -->
// Determine whether the two nodes are the same object, if yes, return directly
if(oldVnode == newVnode) return

// simple version
// Determine whether there is only text and no children in the new node
if(hasText(newVnode)) {<!-- -->
// If the text of the old and new nodes is different, replace it
if(oldVnode.text !== newVnode.text) {<!-- -->
oldVnode.elm.innerText = newVnode.text
}
}else if(hasChildren(newVnode)) {<!-- -->
// Judging that there are only children and no text in the new node
// There is text in the old node but no children
if(hasText(oldVnode)) {<!-- -->
// Delete the text of the old node and add the children of the new node
oldVnode.elm.innerText = ''
for(let i = 0; i<newVnode.children.length; i ++ ) {<!-- -->
oldVnode.elm.appendChild(createEle(newVnode.children[i]))
}
}else if(hasChildren(oldVnode)) {<!-- -->
// There are children but no text in the old node
// Then compare the two node children and update the corresponding real DOM node
updateChildren(oldVnode.children, newVnode.children, oldVnode.elm)
}
}
}

updateChildren (comparing children of old and new nodes)

Four pointers will be introduced in the comparison process, pointing to the first node and the last node in the oldVnode sub-node list (hereinafter referred to as the old front and old back) and pointing to the first node and the last node in the newVnode sub-node list A node (hereinafter referred to as new front and new back)

When comparing, each comparison performs hit search in the following order

• Comparison between old and new nodes (1)
• Comparison of old post and new post nodes (2)
• Comparison of old front and new back nodes (3)
• Comparison of old and new front nodes (4)

In the above four cases, if the virtual Dom corresponding to the two pointers in a certain case is the same, then we call it a hit. After the hit, the search will not continue, the pointer will move, (the real Dom may also be operated, when 3 or 4 hits, the real Dom mobile node will be operated), and then the next comparison will start. If there is no hit, go to the oldVnode child node list to search for the node pointed by the current new front pointer. If found, then operate the real Dom to move the node. If not found, add a new real Dom node to insert.

This mode of comparison continues until the termination condition is met.

That is, if the old front pointer moves to the back of the old back pointer or the new front pointer moves to the back of the new back pointer, we can understand that the old child node is processed first and the new child node is processed.

Then we can predict that one of the old and new child nodes will be processed first. After the comparison, we will decide whether to insert the real Dom or delete the real Dom according to the pair of front and rear pointers that have not been processed.

• If the old child nodes are processed first and the new child nodes are left, it means that there are new nodes to be added. Insertion will be performed based on the virtual nodes between the final new front and new back
• If the new child nodes are processed first and the old child nodes remain, it means that there are nodes to be deleted. The deletion will be performed based on the virtual nodes between the final old front and old back

// updateChildren.js
?
import patchDetails from "./patchVnode"
import createEle from "./createEle";
?

// Determine whether two virtual nodes are the same virtual node. The condition is whether the label name and key of the node are equal
function isSame(a, b) {<!-- -->
  return a.sel == b.sel & amp; & amp; a.key == b.key;
}


/**
 * @description Compare the list of child nodes and update the real Dom
 * @param {*} oldCh old virtual Dom child node list
 * @param {*} newCh new virtual Dom child node list
 * @param {*} parent The real Dom corresponding to the old and new virtual nodes
 * @returns
 */
?
export default function updateChildren(oldCh, newCh, parent) {<!-- -->
  // Define four pointers old before old after new before new after
  let oldStartIndex = 0;
  let oldEndIndex = oldCh. length - 1;
  let newStartIndex = 0;
  let newEndIndex = newCh. length - 1;
?
  // The nodes corresponding to the four pointers
  let oldStartNode = oldCh[oldStartIndex];
  let oldEndNode = oldCh[oldEndIndex];
  let newStartNode = newCh[newStartIndex];
  let newEndNode = newCh[newEndIndex];
?
  // The hash table of the key and index of each child node in oldCh is used to find nodes in oldCh when none of the four comparison rules match
  const keyMap = new Map();
?
  /**
   * Start traversing the two children arrays for detailed comparison
   * Comparison rules: old front-new front, old back-new back, old front-new back, old back-new front
   * The pointer moves after the comparison
   * Until the pointer does not meet the following conditions, which means that there is no unprocessed child node between a pair of front and back pointers, then stop the comparison and directly operate the DOM
   */
?
  while (oldStartIndex <= oldEndIndex & amp; & amp; newStartIndex <= newEndIndex) {<!-- -->
    // These four cases are to allow the pointer to skip empty nodes during the movement
    if (oldStartNode == undefined) {<!-- -->
      oldStartNode = oldCh[++oldStartIndex];
    } else if (oldEndNode == undefined) {<!-- -->
      oldEndNode = oldCh[--oldEndIndex];
    } else if (newStartNode == undefined) {<!-- -->
      newStartNode = newCh[++newStartIndex];
    } else if (newEndNode == undefined) {<!-- -->
      newEndNode = newCh[--newEndIndex];
    } else if (isSame(oldStartNode, newStartNode)) {<!-- -->
      console.log("method1");
      // The old front - the new front are the same virtual node
?
      // Two child nodes compare their child nodes and update dom (recursive entry point)
      patchDetails(oldStartNode, newStartNode);
      // pointer moves
      oldStartNode = oldCh[++oldStartIndex];
      newStartNode = newCh[++newStartIndex];
    } else if (isSame(oldEndNode, newEndNode)) {<!-- -->
      console.log("method2");
      // The old post - the new post are the same virtual node
?
      // Two child nodes compare their child nodes and update dom (recursive entry point)
      patchDetails(oldEndNode, newEndNode);
      // pointer moves
      oldEndNode = oldCh[--oldEndIndex];
      newEndNode = newCh[--newEndIndex];
    } else if (isSame(oldStartNode, newEndNode)) {<!-- -->
      console.log("method3");
      // The old front - the new back are the same virtual node
?
      // Two child nodes compare their child nodes and update dom (recursive entry point)
      patchDetails(oldStartNode, newEndNode);
?
      /**
       * This step has one more operation to move (real) nodes
       * The child node pointed by the current pointer needs to be moved behind the real node corresponding to oldEndIndex (that is, the tail of the unprocessed real node)
       * Note: This step is to operate the real node
       */
      parent.insertBefore(oldStartNode.elm, oldEndNode.elm.nextSibling);
?
      // pointer moves
      oldStartNode = oldCh[++oldStartIndex];
      newEndNode = newCh[--newEndIndex];
    } else if (isSame(oldEndNode, newStartNode)) {<!-- -->
      console.log("method4");
      // After the old - before the new is the same virtual node
?
      // Two child nodes compare their child nodes and update dom (recursive entry point)
      patchDetails(oldEndNode, newStartNode);
      /**
       * This step has one more operation to move (real) nodes
       * Different from method3 in moving position
       * Need to move the child node pointed by the current pointer to the front of the real node corresponding to oldStartIndex (that is, the top of the unprocessed real node)
       * Note: This step is to operate the real node
       */
      parent.insertBefore(oldEndNode.elm, oldCh[oldStartIndex].elm);
?
      // pointer moves
      oldEndNode = oldCh[--oldEndIndex];
      newStartNode = newCh[++newStartIndex];
    } else {<!-- -->
      console.log("does not match");
      // None of the four rules match
?
      // Generate keyMap
      if (keyMap. size == 0) {<!-- -->
        for (let i = oldStartIndex; i <= oldEndIndex; i ++ ) {<!-- -->
          if (oldCh[i].key) keyMap.set(oldCh[i].key, i);
        }
      }
?
      // Search the node pointed to by the current newStartIndex in oldCh
      if (keyMap.has(newStartNode.key)) {<!-- -->
        // found
?
        // Get the virtual node in oldCh first
        const oldMoveNode = oldCh[keyMap.get(newStartNode.key)];
        // Two child nodes compare their child nodes and update dom (recursive entry point)
        patchDetails(oldMoveNode, newStartNode);
?
        // Move this node (the real node is moved)
        parent.insertBefore(oldMoveNode.elm, oldStartNode.elm);
?
        // The virtual node is set to undefined (remember the first four conditions, because the child nodes will be empty here, so those four conditions are added)
        oldCh[keyMap.get(newStartNode.key)] = undefined;
          
      } else {<!-- -->
        // not found, insert directly
        parent.insertBefore(createEle(newStartNode), oldStartNode.elm);
      }
?
      // pointer moves
      newStartNode = newCh[++newStartIndex];
    }
  }
?
  /**
   * Insert and delete nodes
   * After the end of while, there are still unprocessed child nodes between a pair of front and back pointers, then the insertion or deletion operation will be performed
   * There are unprocessed child nodes in the double pointer of oldCh, delete them
   * There are unprocessed child nodes in the double pointer of newCh, insert operation
   */
  if (oldStartIndex <= oldEndIndex) {<!-- -->
    // delete
    for (let i = oldStartIndex; i <= oldEndIndex; i ++ ) {<!-- -->
      // Add judgment because oldCh[i] may be undefined
      if(oldCh[i]) parent. removeChild(oldCh[i].elm);
    }
  } else if (newStartIndex <= newEndIndex) {<!-- -->
    /**
     * insert
     * The point to note here is where to insert, that is, the second parameter of appendChild
     * should be inserted from the position corresponding to oldStartIndex
     */
    for (let i = newStartIndex; i <= newEndIndex; i ++ ) {<!-- -->
      // oldCh[oldStartIndex] exists and is inserted from the head
      parent.insertBefore(createEle(newCh[i]), oldCh[oldStartIndex] ? oldCh[oldStartIndex].elm : undefined);
    }
  }
}

Summary

The diff algorithm compares the virtual DOM, and the virtual DOM is tree-like, so the algorithm is full of recursion. In fact, the diff algorithm is a
patch (compare the root node) –> patchVnode (the root node is the same node, then compare the child nodes) –> updateChildren (if there are child nodes, compare the two child nodes and update the real DOM node) – -> patchVnode (the root node is the same node, then compare the child nodes) –> updateChildren (if there are child nodes, compare the two child nodes, and update the real DOM node) –> patchVnode such a circular recursion process

Why is it recommended to use key?

• The condition for judging whether two virtual nodes are the same is whether the label name and key are the same
• After adding the key, it can be more clearly judged whether the two nodes are the same virtual node, if yes, judge whether the child node has changed, and update the real DOM if there is a change, if not, continue to compare
• If the key is not added, the label names of two different nodes are exactly the same, so they will be judged as the same node. As a result, when the child nodes of the two nodes are compared and found to be different, a lot of operations on the real DOM will be added, thus Causes the page to redraw and reflow more frequently

// Determine whether two virtual nodes are the same virtual node. The condition is whether the label name and key of the node are equal
function isSame(a, b) {<!-- -->
  return a.sel == b.sel & amp; & amp; a.key == b.key;
}
// and the last else of the while loop in updateChildren

Reasonable use of keys can effectively reduce changes in the real DOM, thereby reducing the frequency of page redrawing and reflow, thereby improving the efficiency of page updates.