Follow me on my blog shymean.com

The latest in combing the core implementation of some front-end frameworks, about the Diff algorithm this piece, found that most of the current articles are to translate the source code again, and on such details as “why to define multiple cursors”, “end to end comparison”, and did not give a good explanation. So I’m going to clean up the snabbDOM source code and answer some of the questions mentioned earlier.

If you only care about the core implementation of the DIff algorithm, you can directly jump to the chapter of new and old nodes of patchVnode diff

Using the process

Parcel Sets up the development environment

Since the repository does not provide a development environment like Dev, you can quickly build one using Pracel

First clone the repository and run NPM install && NPM run build to package it

Then create a demo directory under the project examples directory and create index.js and index.html

// index.html
<button id="change">change</button>
<div id="container"></div>
<script src="./index.js"></script>
Copy the code
import { init, classModule, propsModule, styleModule, eventListenersModule, h } from ".. /.. /build/index";

const patch = init([
  classModule, // makes it easy to toggle classes
  propsModule, // for setting properties on DOM elements
  styleModule, // handles styling on elements with support for animations
  eventListenersModule // attaches event listeners
]);

const container = document.getElementById("container");

const renderItem = (item) = >{
  return h("div", {key:item}, item);
}
const oldList = ["A"."B"."C"."D"."E"].map(renderItem);
const newList = ["B"."A"."C"."F"."G"."D"].map(renderItem);
const vnode = h("div", {}, oldList);
patch(container, vnode);

document.getElementById("change").onclick = () = >{
  const newVnode = h("div", {}, newList);
  patch(vnode, newVnode);
}
Copy the code

Then launch parcel index.html in the examples/demo directory.

Relevant concepts

Snabbdom provides only a few basic interfaces, which can be used in the following process,

  • useinitAnd built-in module initializationpatchmethods
  • usehMethod to create a vNode
  • Initialize thepatch(container, vnode)Container is the application root node
  • updatepath(vnode, newVnode)

A VNode is a JS object that describes the actual DOM and contains some major information

export interface VNode {
  sel: string | undefined; // To distinguish between different types of nodes
  data: VNodeData | undefined; // Configure data, which can carry some hooks or other information
  children: Array<VNode | string> | undefined; / / child nodes
  elm: Node | undefined; // Corresponding DOM instance
  text: string | undefined; / / text
  key: Key | undefined; // key, unique identifier in sibling nodes
}
Copy the code

The h method returns a vNode based on SEL, data, and children

export function h(
  sel: string,
  data: VNodeData | null,
  children: VNodeChildren
) :VNode
Copy the code

Patch method is constructed by init method, which is the core of the whole framework and also the focus of this paper

Convergence of patch inlet

Say first process

  • In the first place to judgeoldVnodeVnode,
    • If not, the container DOM node is initialized, and an empty vNode is created using the DOM nodeoldVnode
  • throughsameVnodeCheck whether the old and new VNodes are the same
    • If not, passcreateElm(newVnode)Build the real DOM tree by traversing the virtual DOM tree, and then replace the container DOM passed in with the new DOM
    • If so, newVnode can reuse the DOM instance of oldVnode,vnode.elm = oldVnode.elmAnd then gopatchVnodeprocess

Looking at the code, since the insert hook is not called until the node is inserted into the DOM, an insertedVnodeQueue list is used to collect all the inserted VNodes while traversing the tree

  function patch(oldVnode: VNode | Element, vnode: VNode) :VNode {
    let i: number.elm: Node, parent: Node;
    const insertedVnodeQueue: VNodeQueue = [];
    for (i = 0; i < cbs.pre.length; ++i) cbs.pre[i]();

    if(! isVnode(oldVnode)) { oldVnode = emptyNodeAt(oldVnode); }if (sameVnode(oldVnode, vnode)) {
      patchVnode(oldVnode, vnode, insertedVnodeQueue);
    } else{ elm = oldVnode.elm! ; parent = api.parentNode(elm)as Node;

      // Initialize the DOM tree based on vNode
      createElm(vnode, insertedVnodeQueue);

      if(parent ! = =null) { api.insertBefore(parent, vnode.elm! , api.nextSibling(elm));// The oldVnode DOM instance will be removed
        removeVnodes(parent, [oldVnode], 0.0); }}for (i = 0; i < insertedVnodeQueue.length; ++i) { insertedVnodeQueue[i].data! .hook! .insert! (insertedVnodeQueue[i]); }for (i = 0; i < cbs.post.length; ++i) cbs.post[i]();
    return vnode;
  };
Copy the code

CreateElm and patchVnode can be used separately to see the difference between initialization and update

Snabbdom uses similar programming conventions to C, declaring variables in the function header and only assigning values in subsequent code

CreateElm creates a DOM tree recursively

The main function is to create a DOM node according to the VNode SEL. If there are child nodes, the preceding traversal is performed. The recursive call createElm gets the corresponding DOM node of the child node, and then inserts it into the parent DOM node

As you can see, the DOM creation operation is performed at the same time as recursion. For ease of reading, the source code below has been deleted

  function createElm(vnode: VNode, insertedVnodeQueue: VNodeQueue) :Node {
    let i: any;
    let data = vnode.data;
    const children = vnode.children;
    const sel = vnode.sel;
    if (sel === "!") {
      if (isUndef(vnode.text)) {
        vnode.text = ""; } vnode.elm = api.createComment(vnode.text!) ; }else if(sel ! = =undefined) {
      // Parse the tag according to sel
      const elm = (vnode.elm =
        isDef(data) && isDef((i = data.ns))
          ? api.createElementNS(i, tag, data)
          : api.createElement(tag, data));
			// Create child nodes recursively
      if (is.array(children)) {
        for (i = 0; i < children.length; ++i) {
          const ch = children[i];
          if(ch ! =null) {
            // Add the DOM corresponding to the child node to the parent DOM
            api.appendChild(elm, createElm(ch asVNode, insertedVnodeQueue)); }}}else if(is.primitive(vnode.text)) { api.appendChild(elm, api.createTextNode(vnode.text)); }}else{ vnode.elm = api.createTextNode(vnode.text!) ; }return vnode.elm;
  }
Copy the code

This gives you the complete DOM tree corresponding to a VNode.

PatchVnode diff Old and new nodes

As mentioned above, when the types of old and new nodes are the same, the process of patchVnode will be entered, mainly to judge the list of child nodes corresponding to the old and new nodes

function patchVnode(oldVnode: VNode, vnode: VNode, insertedVnodeQueue: VNodeQueue) {

  constelm = (vnode.elm = oldVnode.elm)! ;const oldCh = oldVnode.children as VNode[];
  const ch = vnode.children as VNode[];
  // If the nodes are the same in memory, no comparison is performed
  if (oldVnode === vnode) return;

  if (isUndef(vnode.text)) {
    if (isDef(oldCh) && isDef(ch)) {
      // Old and new child nodes exist at the same time, if the child nodes are the same in memory, no comparison is made
      if(oldCh ! == ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue); }else if (isDef(ch)) {
      // If there are only new nodes, they are all new nodes
      if (isDef(oldVnode.text)) api.setTextContent(elm, "");
      // Then insert the new node
      addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue);
    } else if (isDef(oldCh)) {
      // If only old nodes exist, remove all of them
      removeVnodes(elm, oldCh, 0, oldCh.length - 1);
    } else if (isDef(oldVnode.text)) {
      api.setTextContent(elm, ""); }}else if(oldVnode.text ! == vnode.text) {// If the new node is a text node, remove the old node and insert a new text node
    if (isDef(oldCh)) {
      removeVnodes(elm, oldCh, 0, oldCh.length - 1); } api.setTextContent(elm, vnode.text!) ; } hook? .postpatch? .(oldVnode, vnode); }Copy the code

The case of text nodes, only new nodes, or only old nodes is easier to understand, while the case of both old and new nodes contains the entire core of the diff in Update Dren.

Before looking at the source code, what is the main purpose of comparing old and new nodes?

The core of the whole DIff algorithm is to compare the old and new nodes and reduce the overhead caused by DOM operation as much as possible. In order to achieve this goal, the existing old nodes need to be reused as much as possible. In other words

  • Each old child node list contains the DOM instance that has been created
  • Each new child node is waiting to be taken from the DOM instance that has been createdfindThe one that belongs to me
    • If you can find it, reuse it
    • If not, create a new DOM instance
  • Finally, if there are unused DOM instances in the old child nodes, they need to be removed from the page

It can be seen that the key idea is to find suitable old nodes for the new node. According to the method of patchVnode, two VNodes of the same type can reuse their DOM nodes.

BF version

The simplest way to think about it is to iterate through the list of new nodes, get the type of each new node, and then find a matching one from the list of old nodes

To simplify things, suppose you need to rebuild a new list from the old one below

  • The old list is['A','B','C','D','E']
  • The new list is['B','A','C','F','G','D']

From the perspective of God, first determine the nodes, A, B, C, D nodes exist, can reuse the old DOM; New F and G nodes need to be created. The old E node needs to be removed

Write a violent version with only the above requirements in mind

var oldChildren = ['A'.'B'.'C'.'D'.'E']
var newChildren = ['B'.'A'.'C'.'F'.'G'.'D']

function createKeyToOldIdx(arr){
    var map = arr.reduce((acc, oldChild,index) = >{
        acc[oldChild] = index
        return acc
    },{})
    return map
}

var parentElm = oldChildren.slice()
newChildren.forEach((newChild, idx) = >{
    var map = createKeyToOldIdx(parentElm)
    var oldIdx = map[newChild]
    if(oldIdx===undefined) {
      	// Add a new node
        parentElm.splice(idx, 0, newChild)
    }else if(oldIdx ! == idx) {// Move the position
        parentElm.splice(oldIdx,1) 
        parentElm.splice(idx, 0, newChild)
    }
    console.log(idx, parentElm) 
})

// Remove nonexistent nodes
parentElm =  parentElm.filter(child= >{
    return newChildren.includes(child)
})
console.log(parentElm)

// Old list ['A','B','C','D','E']
// New list ['B','A','C','F','G','D']

// The initial parentElm is the same as the old list ['A','B','C','D','E']

ParentElm: B A C D E
ParentElm: B A C D E
ParentElm: B A C D E
ParentElm: B A C F D E
ParentElm: B A C F G D E
ParentElm: B A C F G D E
ParentElm: B A C F G D

// Finally parentElm is consistent with the new list
Copy the code

In this implementation,

  • Iterate through the list of new nodes to see if there is a corresponding old node,

    • If they exist, the order is adjusted to meet their position in the new node list;
    • If it does not exist, it is created and inserted into the position of the new node list

  • Then remove the node that is not in the new node list

Since parentElm keeps the latest node order, the new node’s position in the old list must be found by createKeyToOldIdx in each iteration, resulting in O(mn) complexity.

Molecular dismantling problem

Therefore, it is necessary to improve the above algorithm to reduce the operation steps as much as possible

  • Move the old B node to the front of the A node, and the first three nodes are in the same order as the new node
  • Create the DOM of new F and insert it in front of old D
  • Create a new DOM for G and insert it in front of the old D
  • Delete the DOM of old E

You can update the old DOM tree to the new ONE in just four steps. With this background in mind, read on to the updateChildren source code. The minimum operation required to change one list into another can actually be found at edit Distance, [letcode] (leetcode-cn.com/problems/ed…

With that in mind, let’s look at the simplest case

["A"]
["A"] The two lists are identical and do nothing ["A"[] [A] []"A"] add B to ["A"]
["B"[delete A add BCopy the code

Then look at the following special cases

In this case, the same nodes can be ignored to simplify the problem to the case of continuous subarrays. The steps required to solve this problem = the steps required to solve the subproblem

["A"]
["A"."B"] There are two ways to split the first way ["A"] - > ["A"] subproblems1And [] - > ["B"]2, requires operation1Second kind []->["A"] subproblems1And ["A"] - > ["B"]2, requires operation3It can be seen that the first method requires fewer steps, so it can be used as the optimal solutionCopy the code

With this in mind, break down the following problem for the same first or last node

/ / new
["A"."B"];
["A"."C"."B"]; Subproblems ["B"] - > ["C"."B"[] -> ["C"]

/ / delete
["A"."C"."B"]
["A"."B"] sub-question ["C"] - > []/ / modify
["A"."C"."B"]
["A"."D"."B"] sub-question ["C"] - > ["D"]

["A"."B"]
["A"."C"] sub-question ["B"] - > ["C"]

["A"."B"]
["C"."B"] sub-question ["A"] - > ["C"]
Copy the code

The old head node is equal to the new tail node, or the old tail node is equal to the new head node, in which case, it is only necessary to adjust the beginning and end nodes of the old and new array to handle the same head node or tail node. The steps required to solve this problem = move the node (once) + the steps required to solve the sub-problem

["A"."B"];
["C"."B"."A"]; First, convert the old node to ["B"."A"], and then deal with the sub-problem [""] - > ["C"]

["A"."B"]
["C"."D"."A"]; First, convert the old node to ["B"."A"], and then deal with the sub-problem ["B"] - > ["C"."D"]
Copy the code

Not satisfying the subproblem of the above case,

["A"."B"]
["C"."A"."B"."D"] add C to make ["C"."A"."B"], and then the subproblem []->["D"]

["A"."B"]
["C"."A"."D"] add C to make ["C"."A"."B"], and then the subproblem ["B"] - > ["D"]

["A"."B"]
["C"."D"] add C to make ["C"."A"."B"], and then the subproblem ["A"."B"] - > ["D"] For the subproblem, add D first to become ["D"."A"."B"], and then the subproblem ["A"."B"] - > [] ["A"."C"."B"]
["C"."D"] originally add C first, before adding C, need to check whether there is any in the old node, if so, perform the move operation, become ["C"."A"."B"] - > ["C"."D"] Dealing with sub-problems ["A"."B"] - > ["D"], repeat the above procedureCopy the code

With this divide-and-conquer mentality, at each step we can break down the problem into smaller problems, so we can easily calculate the minimum number of steps to go back to the problem above

If there is an old node in B, move it directly, and the first three nodes become the same, using one-step move operation ['A'.'B'.'C'.'D'.'E']
['B'.'A'.'C'.'F'.'G'.'D'] completed DOM node ['B'.'A'.'C'.'D'.'E'] subproblem, start == end, move, use one move operation ['D'.'E']
['F'.'G'.'D'] completed DOM node ['B'.'A'.'C'.'E'.'D'] subproblem, satisfy tail == tail, use0Step ['E'.'D']
['F'.'G'.'D'] subproblem, completely not satisfied, need to add two steps, remove one step ['E']
['F'.'G'] add F ['B'.'A'.'C'.'F'.'E'.'D'] add G ['B'.'A'.'C'.'F'.'G'.'E'.'D'] delete E ['B'.'A'.'C'.'F'.'G'.'D']
Copy the code

Is it closer to the better practice we mentioned above? The E node will be removed later, so the move D step is unnecessary. Otherwise, the operation required is basically the same as the previous observation from god’s perspective.

This is a key step. We split the DOM update problem into the smallest sub-problems, and the order of the nodes that have already been processed does not change.

Take a look at a more complex example, source Snabbdom underlying Diff algorithm in detail

First = = | | = = the end, use0Step [old"A"."B"."C"."D"."E"."F"."G"New []"A"."F"."E"."M"."O"."I"."E"."B"."G"] Full DOM node ["A"."B"."C"."D"."E"."F"."G"] subproblems, tail first = = | | end = = first, need to move, use2First move, convert to head == head and tail == tail ["B"."C"."D"."E"."F"]
["F"."E"."M"."O"."I"."E"."B"] Full DOM node ["A"."F"."C"."D"."E"."B"."G"] subproblem, satisfy tail == tail, use0Step ["C"."D"."E"]
["E"."M"."O"."I"."E"] Full DOM node ["A"."F"."C"."D"."E"."B"."G"] sub-problem, completely inconsistent with, need4A new and2Remove, ["C"."D"]
["E"."M"."O"."I"] add E to complete DOM node ["A"."F"."E"."C"."D"."E"."B"."G"] add M ["A"."F"."E"."M"."C"."D"."E"."B"."G"] add O ["A"."F"."E"."M"."O"."C"."D"."E"."B"."G"] add I ["A"."F"."E"."M"."O"."I"."C"."D"."E"."B"."G"] remove C ["A"."F"."E"."M"."O"."I"."D"."E"."B"."G"] D ["A"."F"."E"."M"."O"."I"."E"."B"."G"]
Copy the code

The procedure is similar, then implement an optimized version, because there is no insertBefore and removeChild interface, during the test need to ensure that each element is unique.


var a = ["A"."B"."C"."D"."E"];
var b = ["B"."A"."C"."F"."G"."D"];

var oldStartIdx = 0
var newStartIdx = 0
var oldEndIdx = a.length - 1
var newEndIdx= b.length - 1

var oldStart = a[0]
var oldEnd = a[oldEndIdx]
var newStart = b[0]
var newEnd = b[newEndIdx]

var parentElm = a.slice()

function createKeyToOldIdx(a) {
    var map = a.reduce((acc, oldChild, index) = > {
        acc[oldChild] = index;
        return acc;
    }, {});
    return map;
}

var oldKeyToIdx = createKeyToOldIdx(a)

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    if(oldStart===undefined) {
        oldStart = a[++oldStartIdx]
    }else if(oldEnd === undefined){
        oldEnd = a[--oldEndIdx]
    }else if(newStart === undefined){
        newStart = b[++newStartIdx]
    }else if(newEnd === undefined){
        newEnd === b[--newEndIdx]
    }else if(oldStart === newStart) {
        oldStart = a[++oldStartIdx]
        newStart = b[++newStartIdx]
    }else if(oldEnd === newEnd){
        oldEnd = a[--oldEndIdx]
        newEnd = b[--newEndIdx]
    }else if(oldStart === newEnd){
      	// Move to the back
        parentElm.splice(oldStartIdx, 1)
        parentElm.splice(oldEndIdx, 0, oldStart)
        oldStart = a[++oldStartIdx]
        newEnd = b[--newEndIdx]
    }else if(oldEnd === newStart){
      	// Move to the front
        parentElm.splice(oldEndIdx, 1)
        parentElm.splice(oldStartIdx, 0, oldEnd)
        oldEnd = a[--oldEndIdx]
        newStart = b[++newStartIdx]
    }else {
        // If no old node exists, start with newStart
        var idxInOld = oldKeyToIdx[newStart]
        if(idxInOld===undefined) {console.log(oldStartIdx, newStart)
            // insertBefore is not implemented, so we can only temporarily get the corresponding IDX and insert it through splice.
            InsertBefore (newStart, oldStart)
            let idx = parentElm.indexOf(oldStart)
            parentElm.splice(idx,0,newStart)
        }else {
            var elmToMove = a[idxInOld]
            a[idxInOld] = undefined
            parentElm.splice(idxInOld, 1)
            parentElm.splice(oldStartIdx, 0,elmToMove)
        }
        newStart = b[++newStartIdx]
    }
    console.log(parentElm)
}

if (oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx) {
    if (oldStartIdx > oldEndIdx) {
        // Insert new nodes in batches
        var sub = b.slice(newStartIdx, newEndIdx+1)
        var before = b[newEndIdx+1]
        InsertBefore (node, before
        var idx = parentElm.indexOf(before)
        parentElm = [...parentElm.slice(0,idx),... sub,parentElm.slice(idx)] }else {
        // Delete unnecessary old nodes in batches
        for(vari = oldStartIdx; i <= oldEndIdx; ++i){var child= a[i]
            / / same as above, using the node here. ParentNode. RemoveChild can remove nodes directly, without having to pass independence idx
            var idx = parentElm.indexOf(child)
            parentElm.splice(idx,1)}}}console.log(parentElm)
Copy the code

There are many judgments in this implementation

  • Use new start index, new end index, new start node, and new end node to end the subproblem scope of the new node list
  • Use old start index, old end index, old start node, old tail node to end the subproblem scope of the old node list
  • The first four judgments are skipped to ensure the existence of the old and new nodesundefinedThe nodes of the
  • The next two judgmentsoldStart === newStartand(oldEnd === newEndUsed to determine whether old head == new head or old tail == new tail. If so, update the cursor to directly narrow the subproblem
  • The next two judgmentsoldStart === newEndandoldEnd === newStartUsed to determine if old head == new tail or old tail == new head, if so, the move operation is performed, while updating the cursor to narrow the sub-problem scope
  • The final judgment, used to deal with general subproblems, is to first check whether the new start node has any old nodes that can be reused
    • If not, create a node to insert
    • If so, the move operation is performed

Does this code look familiar? Yes, it’s a simplified version of Update Dren

UpdateChildren source code and existing problems

Now that you look at the updateChildren source code, it’s easy to understand the initial set of variables. The main purpose is to operate after each step, so the DOM node scope needs to be operated. If the scope is small, fewer DOM operations need to be performed, which also achieves the purpose of performance optimization

function updateChildren(parentElm: Node, oldCh: VNode[], newCh: VNode[], insertedVnodeQueue: VNodeQueue) {
    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;

    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      // The first type of judgment ensures that the old and new nodes exist
      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];
       // The second type determines whether the start or end nodes are the same
      } else if (sameVnode(oldStartVnode, newStartVnode)) {
        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue);
        oldStartVnode = oldCh[++oldStartIdx];
        newStartVnode = newCh[++newStartIdx];
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue);
        oldEndVnode = oldCh[--oldEndIdx];
        newEndVnode = newCh[--newEndIdx];
      } else if (sameVnode(oldStartVnode, newEndVnode)) {
        // If the first and last nodes are the same, execute the move operation
        // Vnode moved rightpatchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue); api.insertBefore( parentElm, oldStartVnode.elm! , api.nextSibling(oldEndVnode.elm!) ); oldStartVnode = oldCh[++oldStartIdx]; newEndVnode = newCh[--newEndIdx]; }else if (sameVnode(oldEndVnode, newStartVnode)) {
        // Vnode moved leftpatchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue); api.insertBefore(parentElm, oldEndVnode.elm! , oldStartVnode.elm!) ; oldEndVnode = oldCh[--oldEndIdx]; newStartVnode = newCh[++newStartIdx]; }else {
        // Find reusable DOM nodes based on key
        if (oldKeyToIdx === undefined) {
          oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
        }
        idxInOld = oldKeyToIdx[newStartVnode.key as string];
        if (isUndef(idxInOld)) {
          // If there are no reusable nodes, create a new oneapi.insertBefore( parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm! ) ; }else {
          // If there are reusable nodes, perform the move operation
          elmToMove = oldCh[idxInOld];
          if(elmToMove.sel ! == newStartVnode.sel) { api.insertBefore( parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm! ) ; }else {
            patchVnode(elmToMove, newStartVnode, insertedVnodeQueue);
            oldCh[idxInOld] = undefined asany; api.insertBefore(parentElm, elmToMove.elm! , oldStartVnode.elm!) ; } } newStartVnode = newCh[++newStartIdx]; }}if (oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx) {
      if (oldStartIdx > oldEndIdx) {
        // If the old node is used up and the new node is still available, insert the new node
        before = newCh[newEndIdx + 1] = =null ? null : newCh[newEndIdx + 1].elm;
        addVnodes(
          parentElm,
          before,
          newCh,
          newStartIdx,
          newEndIdx,
          insertedVnodeQueue
        );
      } else {
        // If the new node is used up and the old node is still available, remove itremoveVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx); }}}Copy the code

According to the above analysis, the step of moving nodes is not optimal, because the operation of deleting useless nodes is performed at the end, above

['A'.'B'.'C'.'D'.'E']
['B'.'A'.'C'.'F'.'G'.'D']
Copy the code

In this example, D would be moved after E, and then E would be deleted, which would be useless. Because the nodes that are removed do not affect the entire DIff, one possible approach is to adjust the code order and remove them earlier

  • To traverse the old and the new node, remove not use node ahead of time, there will be more round, after the problem can be simplified as [‘ A ‘, ‘B’, ‘C’, ‘D’] – > [‘ B ‘, ‘A’, ‘C’, ‘F’, ‘G’, ‘D’]
  • Perform the above diff operation again
  • Finally, innewStartIdx <= newEndIdxTo insert an unprocessed VNode

Whether to use this option depends on whether the performance gain from executing one more cycle to remove unwanted nodes is greater than the gain from reducing the cycle by using the additional moves that might be involved, but it is clear that neither Snabbdom nor Vue use this option to remove unwanted nodes early.

Now that we know about the internal implementation, let’s answer the question we deliberately avoided above: What does vNode.key do?

It can be seen in sameVnode

function sameVnode(vnode1: VNode, vnode2: VNode) :boolean {
  const isSameKey = vnode1.key === vnode2.key; // Both are undefined or strings equal
  constisSameIs = vnode1.data? .is === vnode2.data? .is;const isSameSel = vnode1.sel === vnode2.sel;

  return isSameSel && isSameKey && isSameIs;
}
Copy the code

One function of key is to judge whether two VNodes are the same or not. Participating in some judgments in the above diff process, two VNodes with the same SEL will return true in the case that keys are not defined, which is often referred to as in-place reuse, only updating DOM related information, but not participating in the movement operation

In createKeyToOldIdx you can see if the key is defined

function createKeyToOldIdx(
  children: VNode[],
  beginIdx: number,
  endIdx: number
) :KeyToIndexMap {
  const map: KeyToIndexMap = {};
  for (let i = beginIdx; i <= endIdx; ++i) {
    constkey = children[i]? .key;// undefined is not handled
    if(key ! = =undefined) {
      map[key as string] = i; }}return map;
}
// Returns the index of the old node based on the key
idxInOld = oldKeyToIdx[newStartVnode.key as string];
if (isUndef(idxInOld)) {
  / /... Creating a New node
}else {
  / /... Mobile operating
}
Copy the code

If a key is defined, the corresponding DOM node is found in the old list and moved. In other words, a key is used to uniquely mark a list of sibling nodes, so that when a new node is built, it is used to find existing nodes based on the key, rather than reusing them in place and removing nodes where the key does not exist.

For example

When not to use the key to [h (‘ div ‘, {}, ‘1’), h (‘ div ‘, {}, ‘2’)] to [h (‘ div ‘, {}, ‘2’), h (‘ div ‘, {}, ‘1’)], will amend the first text node of the DOM to ‘2’, Rather than moving the order of the two DOM nodes, which seemed more efficient when the DOM nodes were simpler

When using the key [h (‘ div ‘{key:’ 1 ‘}, ‘1’), h (‘ div ‘{key:’ 2 ‘}, ‘2’)] is modified to [h (‘ div ‘{key:’ 2 ‘}, ‘2’), h (‘ div ‘{key:’ 1 ‘}, ‘1’)]. It searches the list of old nodes according to the key of the first new node (‘2’ in this case), finds the corresponding DOM node (the second DOM node), and moves the position. It seems that simple text changes are not cost-effective; But if the children of the two nodes are more complex, switching the order is more cost-effective.

To summarize

  • Instead of using keys, reuse existing DOM of the same type wherever possible
  • Use key, search the old node based on the change of key, modify the order to move the operation, and eliminate the elements that the key does not exist

Handle different DOM properties through modules

The built-in Module Module contains hook methods. When a VNode performs create, update, and remove operations, it passes in the old and new VNodes and executes them, and then performs some operations on the DOM instances of the old and new VNodes

export type Module = Partial<{
  pre: PreHook; create: CreateHook; update: UpdateHook; destroy: DestroyHook; remove: RemoveHook; post: PostHook; } >Copy the code

ClassModule, for example

function updateClass(oldVnode: VNode, vnode: VNode) :void {
  let cur: any;
  let name: string;
  const elm: Element = vnode.elm as Element;
  // 'VNodeData' supports passing 'class' fields, similar to '{class: {active: true, selected: false}}', where 'true' indicates adding style classes and 'false' indicates removing style classes
  let oldClass = (oldVnode.data as VNodeData).class;
  let klass = (vnode.data as VNodeData).class;

  if(! oldClass && ! klass)return;
  if (oldClass === klass) return;
  oldClass = oldClass || {};
  klass = klass || {};
  // Remove the old style class from the new DOM instance
  for (name in oldClass) {
    if (oldClass[name] && !Object.prototype.hasOwnProperty.call(klass, name)) {
      // was `true` and now not providedelm.classList.remove(name); }}// Add or remove new style classes
  for (name in klass) {
    cur = klass[name];
    if(cur ! == oldClass[name]) { (elm.classListas any)[cur ? "add" : "remove"](name); }}}export const classModule: Module = { create: updateClass, update: updateClass };

Copy the code

During init, the incoming built-in module is parsed and placed in a CBS variable via a closure. At the corresponding time during patch, the relevant method can be called to pass in the old and new VNodes and process the real DOM properties

  const cbs: ModuleHooks = {
    create: [].update: [].remove: [].destroy: [].pre: [].post: [],};constapi: DOMAPI = domApi ! = =undefined ? domApi : htmlDomApi;

  for (i = 0; i < hooks.length; ++i) {
    cbs[hooks[i]] = [];
    for (j = 0; j < modules.length; ++j) {
      const hook = modules[j][hooks[i]];
      if(hook ! = =undefined) {
        (cbs[hooks[i]] asany[]).push(hook); }}}Copy the code

This design eliminates the need to focus on DOM manipulation details during diff, and it’s interesting.

summary

Although this paper is named Snabbdom source code analysis, in fact, it only focuses on patch-related processes

  • To initialize, use newVnode, increateElm, the DOM tree is constructed by preordering traversal
  • When updating, for different types of OldvNodes and newvNodes, a new DOM tree is created based on newVnode and then the old oldVnode is removed
  • Update for oldvNodes and newvNodes of the same typepatchVnodeoperation
    • Remove only the old child node list
    • Only the list of new child nodes exists
    • If both exist and they are different, the updateChildren operation is executed, which contains the implementation of the diff algorithm
  • The core idea of DIFF algorithm is to narrow the scope of detection after each step of operation through the idea of divide and conquer

Snabbdom implementation is very concise, is a very readable source. Now it’s much easier to go back and look at the Vue source code.

After Fiber was used in React, the recursive diff was abandoned and the whole diff process was divided into patch and commit phases. However, the core idea of using DIff to reduce DOM operations was similar. The Fiber and DIff implementation of React will be rearranged next.

Relevant reference

  • Snabbdom bottom Diff algorithm in detail
  • Virtual DOM algorithm library -Snabbdom