This article is a study note about virtual DOM and diff algorithm, the purpose is to better understand the underlying principle of Vue, the length is long, so it is divided into several chapters, will be updated in the future.

The last article “virtual DOM and DIff algorithm -01” we implemented the H function by hand, this article focuses on the DIff algorithm.

Characteristics of diFF algorithm

• If you are adding nodes to the very end of the array, the preceding nodes are left unchanged

Patch (vnode1, vnode2) only appends one node

const vnode1 = h("div", {}, [
  h("div"."Qilixiang"),
  h("div"."East wind breaking")])const vnode2 = h("div", {}, [
  h("div"."Qilixiang"),
  h("div"."East wind breaking"),
  h("div"."Orchid Pavilion Preface")])Copy the code

You can directly change “Qilixiang” to “Qilibuxiang” in the browser debugging tool, and then click the button to execute patch(vnode1, vnode2), and you will find that “Qilibuxiang” remains unchanged.

• The key is important because it identifies the node and tells the DIff algorithm whether the node is the same before and after the change

and

will not be changed. If you add a node to the beginning of the array, all nodes will be changed

const vnode1 = h("div", {}, [
  h("div", { key: 1 }, "Qilixiang"),
  h("div", { key: 2 }, "East wind breaking")])const vnode2 = h("div", {}, [
  h("div", { key: 3 }, "Orchid Pavilion Preface"),
  h("div", { key: 1 }, "Qilixiang"),
  h("div", { key: 2 }, "East wind breaking")])Copy the code

• Fine comparison is performed only when the same virtual node is used. Otherwise, delete the old node and insert a new node

The two nodes are judged to be the same according to the comparison selector, that is, whether the sel value and key value are the same. If they are both equal, the two nodes are judged to be the same virtual node

• Only same-level comparisons are made

The hierarchy of the old node and the new node should be the same. For example, in the following example, the new node has more layers of divs than the old node, so the refined comparison is not carried out and the old node is directly deleted and the new node is inserted

const vnode2 = h("div", {}, [
  h('div', [
    h("div", { key: 3 }, "Orchid Pavilion Preface"),
    h("div", { key: 1 }, "Qilixiang"),
    h("div", { key: 2 }, "East wind breaking")]])Copy the code

Handwritten patch function

The diff algorithm is implemented by the patch function. Before writing, let’s first clarify what the patch function does

Functional analysis

The patch function is defined in init.ts in the SRC directory of the snabbDOM

// init.ts
return function patch(oldVnode: VNode | Element, vnode: VNode) :VNode {
    / /... Ignore some code
    // Use the isVnode function to check whether the old node is a virtual node
    if(! isVnode(oldVnode)) { oldVnode = emptyNodeAt(oldVnode);// If not, wrap it with emptyNodeAt as a virtual node
    }
    // Use the sameVnode function to check whether the old and new nodes are the same node
    if (sameVnode(oldVnode, vnode)) {
      / / the same...
    } else {
      / / different...
    }
    / /... Ignore some code
  };
Copy the code

The following flow chart is obtained according to the source code

Handwriting on the tree for the first time

Create patch.js file and introduce vnode function to wrap oldVnode of non-virtual node as virtual node

// patch.js
import vnode from './vnode.js'
import creatElement from './creatElement.js'

export default (oldVnode, newVnode) => {
  // Check whether the oldVnode is a virtual node
  if (oldVnode.sel === undefined) {
    // If an oldVnode is not a virtual node, wrap it as a virtual node
    oldVnode = vnode(oldVnode.tagName.toLowerCase, {}, [], undefined, oldVnode)
  } 
  // Check whether oldVnode and newVnode are the same node
  if (oldVnode.sel === newVnode.sel && oldVnode.key === newVnode.key) {
    // Same node
  } else {
    // Not the same node
    const domNode = creatElement(newVnode)
    // Add the new node to the treeoldVnode.elm.parentNode? .insertBefore(domNode, oldVnode.elm)// Delete the old nodeoldVnode.elm.parentNode? .removeChild(oldVnode.elm) } }Copy the code

Create createlement. js and introduce the creatElement function in patch.js to create a new node and assign the elm attribute of the corresponding virtual node to the created node

/** * createlement. js * creates a vNode as a real DOM node (but not an orphan node on the tree) */
export default function createElement (vnode) {
  const domNode = document.createElement(vnode.sel)
  vnode.elm = domNode
  // Check whether vNode has children or text
  if(vnode.children ! = =undefined && vnode.children.length && vnode.text === undefined) {
    // There are child nodes
    vnode.children.forEach(item= > {
      // Calling createElement means that the DOM is created and the elm attribute of the virtual node points to the DOM.
      // But the DOM is an orphan node and is not yet on the tree
      const childNode = createElement(item)
      item.elm = childNode
      domNode.appendChild(childNode)
    })
  } else {
    // Inside is text
    domNode.innerText = vnode.text
    vnode.elm = domNode
  }
  return domNode
}
Copy the code

So far, we have completed all contents except “fine comparison” in the patch function flowchart above. Next, I will start the detailed comparison of oldVnode and newVnode when they are the same node. This part will have more illustrations, which will inevitably lead to a long page. I will continue to share in the next part

One More Thing

This article has found some useful methods for inserting nodes, so here is an extended summary

• InnerHTML: Gets the HTML content inside the tag
• OuterHTML (properties) : Gets the contents of the internal HTML, including the target tag
• AppendChild (function) : Adds child nodes to the end of the target tag and returns the parameter node
• InsertBefore (function) : returns the first argument by adding the first argument to the second argument position of the target node
• InsertAdjacentHTML (function) : Adds nodes to the specified location of the target node