Comparing all the nodes in two trees, the traditional way is to compare each node in two trees in sequence, so the time is O(n^3).

For example, there are three nodes, and the time required to compare each node in the tree is O(n^3). Where n is the number of nodes.

  • patch(oldVnode, newVnode)
  • Patch, render the changed content of the new node into the real DOM, and finally return the new node as the old node for the next processing
  • Check whether the old and new VNodes have the same key and SEL.
  • If it is not the same node, delete the previous content and re-render
  • If the node is the same, check whether the new VNode has a text. If the text is different from that of the oldVnode, update the text directly
  • If the new VNode has children, check whether the children have changed
  • Diff process is only compared at the same level, time complexity O(n)

100, 100

100, 1000000

patch

  • Function:

    • Pass in the old and new VNodes, compare the differences, and render the differences into the DOM
    • Return the new VNode as the oldVnode for the next patch()

  • Execution process:

    • Executed firstThe moduleIn thehookfunctionpre
    • If oldVnode and VNode are the same (same key and SEL)
      • Call patchVnode() to find the node differences and update the DOM
    • If oldVnode is a DOM element
      • Convert DOM elements into OLdvNodes
      • Call createElm() to convert vNode to a real DOM and log to vNode.elm
      • Insert the newly created DOM element into the parent
      • Removing an old node
      • The triggerThe userSet up thecreate hookfunction

  • Source: SRC /snabbdom.ts

    return function patch(oldVnode: VNode | Element, vnode: VNode) :VNode {
  let i: number.elm: Node, parent: Node;
  // Save the queue of newly inserted nodes in order to trigger the hook function
  const insertedVnodeQueue: VNodeQueue = [];
  // Execute the module's Pre hook function
  for (i = 0; i < cbs.pre.length; ++i) cbs.pre[i]();

  // If oldVnode is not VNode, create VNode and set elm
  if(! isVnode(oldVnode)) {// Convert the DOM element to an empty VNode
    oldVnode = emptyNodeAt(oldVnode);
  }
  // If the new and old nodes are the same node (key and SEL are the same)
  if (sameVnode(oldVnode, vnode)) {
    // Find the node differences and update the DOM
    patchVnode(oldVnode, vnode, insertedVnodeQueue);
  } else {
    // If the old and new nodes are different, vNode creates the corresponding DOM
    // Get the current DOM elementelm = oldVnode.elm! ; parent = api.parentNode(elm);// Trigger init/create hook function to create DOM
    createElm(vnode, insertedVnodeQueue);

    if(parent ! = =null) {
      // If the parent node is not empty, insert the DOM corresponding to the vnode into the documentapi.insertBefore(parent, vnode.elm! , api.nextSibling(elm));// Remove the old node
      removeVnodes(parent, [oldVnode], 0.0); }}// Execute the user-set insert hook function
  for (i = 0; i < insertedVnodeQueue.length; ++i) { insertedVnodeQueue[i].data! .hook! .insert! (insertedVnodeQueue[i]); }// Execute the module's POST hook function
  for (i = 0; i < cbs.post.length; ++i) cbs.post[i]();
  / / return vnode
  return vnode;
};
Copy the code

patchVnode

  • Function:

    • patchVnode(oldVnode, vnode, insertedVnodeQueue)
    • Compare oldVnode and VNode differences and render the differences into the DOM

  • Execution process:

    • The user-set prePatch hook function is first executed
    • Execute the CREATE hook function
      • The module’s CREATE hook function is first executed
      • The user-set CREATE hook function is then executed
    • ifvnode.textundefined
      • ifoldVnode.children 和 vnode.childrenHave a value
        • callupdateChildren()
        • Diff algorithm is used to compare and update child nodes
      • ifvnode.childrenHave a value,oldVnode.childrenThere is no value
        • Clearing DOM elements
        • calladdVnodes()To add child nodes in batches
      • ifoldVnode.childrenHave a value,vnode.childrenThere is no value
        • callremoveVnodes()To remove child nodes in batches
      • ifoldVnode.textHave a value
        • Empty the content of the DOM element
    • If you set it upvnode.textAnd and andoldVnode.textRanging from
      • If the old node has children, remove them all
      • To set the DOM elementtextContent 为 vnode.text
    • Finally, execute the user-set PostPatch hook function

  • Source: SRC /snabbdom.ts

    function patchVnode(oldVnode: VNode, vnode: VNode, insertedVnodeQueue: VNodeQueue) {
  consthook = vnode.data? .hook;// Execute the user-set prepatch hook function firsthook? .prepatch? .(oldVnode, vnode);constelm = vnode.elm = oldVnode.elm! ;let oldCh = oldVnode.children as VNode[];
  let ch = vnode.children as VNode[];
  // Return if the old and new vNodes are the same
  if (oldVnode === vnode) return;
  if(vnode.data ! = =undefined) {
    // Execute the module's update hook function
    for (let i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode);
    // Execute the user-set update hook functionvnode.data.hook? .update? .(oldVnode, vnode); }// If vnode.text is not defined
  if (isUndef(vnode.text)) {
    // If both new and old nodes have children
    if (isDef(oldCh) && isDef(ch)) {
      // Use the diff algorithm to compare child nodes and update child nodes
      if(oldCh ! == ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue); }else if (isDef(ch)) {
      // If the new node has children, the old node has no children
      // Empty the dom element if the old node has text
      if (isDef(oldVnode.text)) api.setTextContent(elm, ' ');
      // Add child nodes in batches
      addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue);
    } else if (isDef(oldCh)) {
      // If the old node has children, the new node has no children
      // Remove child nodes in batches
      removeVnodes(elm, oldCh, 0, oldCh.length - 1);
    } else if (isDef(oldVnode.text)) {
      // If the old node has text, clear the DOM element
      api.setTextContent(elm, ' '); }}else if(oldVnode.text ! == vnode.text) {// If vnode.text is not set
    if (isDef(oldCh)) {
      // If the old node has children, remove it
      removeVnodes(elm, oldCh, 0, oldCh.length - 1);
    }
    // Set the DOM element's textContent to vnode.textapi.setTextContent(elm, vnode.text!) ; }// Finally execute the user-set postpatch hook functionhook? .postpatch? .(oldVnode, vnode); }Copy the code

updateChildren

  • Function:

    • The core of the diff algorithm, comparing the children of the old and new nodes, updates the DOM

  • Execution process:

    • To compare the difference between two trees, we can take each node of the first tree and compare it to each node of the second tree, but in order of n^3 time.
    • In DOM manipulation we rarely move/update a parent node to a child node
    • So you just need to compare the nodes at the same level, and then compare the nodes at the next level, so the time complexity of the algorithm is O(n).

  • When comparing nodes of the same level, the start and end nodes of the new and old node arrays will be marked with index, and the index will be moved during traversal
  • In theStart and end nodesWhen you compare, there are four cases
    • OldStartVnode/newStartVnode (old start node/new start node)
    • OldEndVnode/newEndVnode (old end node/new end node)
    • OldStartVnode/oldEndVnode (old start node/new end node)
    • OldEndVnode/newStartVnode (old end node/new start node)

  • The start node is compared to the end node. The two cases are similar
    • OldStartVnode/newStartVnode (old start node/new start node)
    • OldEndVnode/newEndVnode (old end node/new end node)
  • If oldStartVnode and newStartVnode are samevNodes (same key and SEL)
    • Call patchVnode() to compare and update nodes
    • Move the old start and new start indexes back oldStartIdx++ / oldEndIdx++

  • OldStartVnode/newEndVnode (old start node/new end node) same
    • Call patchVnode() to compare and update nodes
    • Move the oldStartVnode DOM element to the right – update the index

  • OldEndVnode/newStartVnode (old end node/new start node) same
    • Call patchVnode() to compare and update nodes
    • Move the oldEndVnode DOM element to the left
    • Update the index

  • If it’s not four of the above
    • Iterate over the new node, using the newStartNode key to find the same node in the old node array
    • If not, newStartNode is the new node
      • Create a DOM element corresponding to the new node and insert it into the DOM tree
    • If we find it,
      • Determine whether the SEL selector of the new node is the same as that of the old node found
      • If they are different, the nodes are modified
        • Re-create the corresponding DOM element and insert it into the DOM tree
      • If so, move the DOM element corresponding to elmToMove to the left

  • End of the cycle
    • The loop ends when all children of the old node are traversed first (oldStartIdx > oldEndIdx)
    • All children of the new node are traversed first (newStartIdx > newEndIdx), and the loop ends
  • If the array of the old node is traversed first (oldStartIdx > oldEndIdx), the new node has a surplus, and the remaining nodes are batch inserted to the right

​

- If the array of the new node is traversed first (newStartIdx > newEndIdx), it indicates that the old node has surplus. Delete the remaining nodes in batchesCopy the code