Snabbdom: Virtual DOM and Diff algorithm

Because to learn Vue source code, its DIff algorithm is around but a knowledge point. In the learning process, I have learned about the library Snabbdom, which should be improved by Vue, so I can better understand the DIff algorithm of Vue

Snabbdom

The famous virtual DOM library is the ancestor of diff algorithm

What is the Diff algorithm

The diff algorithm is used to calculate the changed parts of the Virtual Dom. Because the Vue React framework only uses state changes to automatically update views, it calculates the smallest changes when data changes, rather than re-rendering the entire page, to save performance.

Diff effect display

Description: The page content is originally rendered with five elements in the array [A, B, C, D, E]. When the button is clicked, the data changes to [Q, A, B, C, D, E], and the page elements change accordingly with minimal changes. How to judge the minimum change in usage. Since the smallest change, that the same A, B, C, D, E node is certainly didn’t do any processing, if we put these nodes after initialization page rendering, through the console change for any content, click the button after the content of these nodes without any processing, we can know the nodes to be skipped the diff processing, didn’t do any processing, It is concluded that when the data changes, the page also adopts the minimum performance update operation.

Tips: If you don’t care about performance, of course you can wipe it all out and re-render it with new data.

The effect is shown below.

What is the virtual DOM

Use JS objects to describe the DOM hierarchy. All properties in the DOM have corresponding properties in the virtual DOM.

See Diff’s strength above, then why add a noun: virtual DOM. Because it involves a comparison algorithm between old and new nodes. For the sake of performance, the real DOM can not be directly compared, so it needs to be converted to the virtual DOM. The virtual DOM is basically a JS object, but it describes the structure of DOM elements according to certain rules, so it is called the virtual DOM. Its structure is roughly similar to the following.

The page elements are as follows

<div id="app">
  <p class="text">hello world!!!</p>
</div>
Copy the code

This is what happens when you convert to the virtual DOM

{
  tag: 'div'.props: {
    id: 'app'
  },
  chidren: [{tag: 'p'.props: {
        className: 'text'
      },
      chidren: [].text: 'hello world!!! '}}]Copy the code

I read some articles, the structure is similar, but the details are different. Don’t worry, if you write the diff algorithm yourself, the corresponding rules for changing the real DOM into the virtual DOM can be customized.

Analysis of the

How is the virtual DOM generated by the render function (h function)

The h function is used to generate virtual nodes (vNodes)

Call h like this

h("li", {key:'A'.class: { class: 'mine'}},"A")
Copy the code

You get a virtual node like this
The corresponding real DOM node looks like this:
```
<li class="mine">A</li>
Copy the code
```

What are the properties of a virtual node

{
  children: undefined./ / item
  data: {},                / / properties, and so on
  elm: undefined.// The corresponding real DOM node
  key: undefined.// Unique key attribute
  sel: div,                Sign / / table
  text: 'I'm an empty box'     // Internal text content
}
Copy the code

Principle of Diff algorithm
1. Core function patch
2. It takes two arguments: the first argument can be an element selected by the old virtual node or element selector, and the second argument is the new virtual node
3. When the first parameter is the element selected by the element selector, render the page directly by processing the virtual node of the second parameter
4. If the first parameter is a virtual node, you need to compare it with the second virtual node parameter to process different node processing logic
How does the virtual DOM diff into the real DOM

In fact, the return of the virtual DOM to the real DOM is covered in the diff algorithm

Code implementation

H function implementation

Morphological analysis:

Simple processing, there are three forms (there is a parameter length judgment processing in the source code, here is simply three parameters)

Form (1) :Js h("div", {}," text ")
Form (2) :js h("div", {} , [])
Form (3) :js h("div", {} , h())

Code implementation

// First there is a function that returns a virtual node object based on the parameters received, as follows
function vNode(sel, data, children, text, elm){
  return {
    sel, 
    data, 
    children, 
    text,
    elm, 
    key: data.key
  }
}

// The low version of the h function must accept three arguments
function h(sel,data,c){
  // Check the number of parameters
  if(arguments.length ! = =3) {throw new Error('Parameters must be three')}// Check the type of c
  if(typeof c === "string" || typeof c === "number") {// In the form 1, call vNode directly to return the result
    return vNode(sel, data, undefined,c,undefined)}else if(Array.isArray(c)){
    2 / / form
    let children = []
    for (let index = 0; index < c.length; index++) {
      const element = c[index]; // call h again, return the result
      // Element must be an object
      if(typeofelement ! = ="object" && element.hasOwnProperty('sel')) {throw new Error("One of the array arguments passed in is not an H function.")}// There is no need to execute element because h is already executed when hasOwnProperty is called and element is a virtual node
      children.push(element)
    }
    return vNode(sel, data, children, undefined.undefined)}else if(typeof c === "object" && c.hasOwnProperty('sel')) {/ / 3
    C has already called h when hasOwnProperty is called above, and returns a virtual node
    let children = c
    return vNode(sel, data,children,undefined.undefined)}else {
    throw new Error("Parameter format error")}}Copy the code

Implementation of patch function

tips

You can see from the initial DIff GIF, it’s really a minimal update, and of course the key is important, because the key is the unique identifier of this node, telling the DIff algorithm that it’s the same DOM before and after the update

In addition, only when the node is the same, fine comparison is carried out, otherwise it is violent deletion of the old, insert the new. Extension question: how to define the same virtual node? Answer: The selectors are the same and the key is the same

Only the same layer comparison, not cross-layer comparison. Even if it is the same piece of virtual node, but cross layer, sorry, fine comparison does not go through you, but violent delete old, insert new

Question: : Diff is not a hand in hand, so does this really affect efficiency?

A: Some operations in the actual VUE development, the above 2 and 3 will not encounter extreme cases, so this is a reasonable optimization mechanism

For example, no one would write a code snippet like this

<div>
  <section v-if="isFlag">
    <p>A</p>
    <p>B</p>
    <p>C</p>
  </section>
  <p v-if=! "" isFlag">A</p>
  <p v-if=! "" isFlag">B</p>
  <p v-if=! "" isFlag">C</p>
</div>
Copy the code

Step analysis:

patch( oldVNode, newVNode )

When the patch function is called, it checks whether the oldVnode is a virtual node. If the oldVnode is a DOM node, it wraps the oldVnode as a virtual node.
OldVNode and newVNode are the same node, and how are they the same node?
If oldVNode and newVNode are not the same node, delete the old one and insert the new one

Note: When a node is created, its children need to be created and inserted recursively
If oldVNode and newVNode are the same node, a fine comparison is required
Continue refined comparison and judgment processing
Are oldVNode and newVNode the same object in memory? If so, skip it and do nothing
If not, check whether newVNode has the text attribute
If newVNode has a text attribute, check whether the text attribute in newVNode is the same as that in oldVNode
1. If it’s the same, what’s good
2. Alter the innerText of oldVNode to the text property of newVNode. Elm alter the innerText of elm to the text property of newVNode. Because when innerText is changed to newVNode’s text, the children property in the old node is automatically removed **)
If newVNode does not have the text attribute, it means that newVNode has the children attribute. Check whether oldVNode has the children attribute
If oldVNode doesn’t have children, that means oldVNode has text, The innerText in oldvNode. elm is emptied and the children child DOM node is inserted into oldvNode. elm
If oldVNode has children, here is oldVNode newVNode has children nodes, and this is the end judgment comparison.
Here we need to mention the four hit lookup. NewVNode header and tail: new before and new after, oldVNode header and tail: old before and old after. Why this algorithm is good is because it fits people’s programming habits.
Define four Pointers newStartIndex, newEndIndex, oldStartIndex, oldEndIndex, and four Pointers corresponding to four nodes: NewStartNode, newEndNode, oldStartNode, oldEndNode; The while loop is executed when oldStartIndex<=oldEndIndex && newStartIndex <= newEndIndex,

The comparison sequence is successively new before new after new, new after old, new after old, new before old, new before old, new before old, hit a direct next cycle, otherwise the next hit, if four are not hit, in separate processing
1. NewStartNode: Check whether newStartNode and oldStartNode are the same node
  1. If it is: Call patchVNode(oldStartNode, newStartNode) function for node processing, and newStartIndex++ oldStartIndex++, The corresponding newStartNode and oldStartNode are also updated
  2. If not: go to the second step, compare the new after, the old after
2. Old after new: Check whether newEndNode and oldEndNode are the same node
  1. If yes, call patchVNode(oldEndNode, newEndNode) function for node processing, and –oldEndIndex and –newEndIndex, corresponding oldEndNode and newEndNode should also be updated
  2. If not, proceed to the third step, compare the new after, the old before
3. Check whether newEndNode and oldStartNode are the same node
  1. If so, call patchVNode(oldStartNode, newEndNode) for node processing and move the old node to the end of the unprocessed node (oldEndvNode.elm), note: InsertBefore The existing node deletes the original node information, and newEndIndex– and ++oldStartIndex, oldStartNode and newEndNode are updated
  2. If not, proceed to step 4, comparing the new before and the old after
4. Check whether newStartNode and oldEndNode are the same node
  1. If yes, call patchVNode(oldEndNode, newStartNode) for node processing and move the old node to the front of the old unprocessed node (i.e. Oldstartvnode.elm), note: InsertBefore The existing node deletes the original node information, and oldEndIndex– and ++newStartIndex, oldEndNode and newStartNode are updated
  2. If not, it needs to be dealt with separately and proceed to Step 5
5. If none is hit, you need to determine whether the current newStartNode appears in the old node
  1. If not, it is new, so create the newStartNode as a real DOM and insert it before oldStartvNode. elm, then update the ++newStartIndex and newStartNode Pointers
  2. If so, the position has changed, then fetch the node corresponding to the current newStartNode in oldChildren, (that is, find newStartNode subscript in oldChildren, such as k, and call patchVNode(oldChildren[k], newStartNode) to update the node). Then set the current oldChildren subscript k to undefined. If undefined is encountered in the next loop, add the judgment lift and skip processing. Also, insert the node information before the current oldStartvNode. elm (that is, before the unprocessed node), and update the ++newStartIndex and newStartNode Pointers
  3. Question answer: why insert the item before the unprocessed node after setting it as undefined? Because the updated information only updates the information in the old node and does not move its position, so after the node at the old subscript is set to undefined, the updated node information saved before is moved to the front of the unprocessed node
6. Repeat the preceding operations until the loop condition oldStartIndex<=oldEndIndex && newStartIndex <= newEndIndex is not met
7. At the end of the loop, you have to make a judgment
  1. ifThe new front is less than or equal to the new rearNote These nodes requirenew, the new position is in front of the unprocessed node, loop between the current newStartIndex and newEndIndex, and add it in front of oldStartvNode. elm
    1. Question: why oldStartvNode. elm?
  2. If the former is less than or equal to the latter, these nodes need to be deleted

Flowchart screenshot

If you can’t see clearly above, please refer to the picture below:

Finish writing the function

function patch(oldVNode, newVNode){
  // Determine whether the first argument passed in is a Dom node or a virtual node
  if(oldVNode.sel == "" || oldVNode.sel == undefined) {// The first argument passed in is the DOM node, which is wrapped as a virtual node
    oldVNode = vNode(oldVNode.tagName.toLowerCase(), {}, [], undefined, oldVNode)
  }
  // Check whether oldVNode and newVnode are the same node
  if(checkSameNode(newVNode, oldVNode)){
    patchVNode(oldVNode, newVNode)
  }else{
    // Not the same node, need to force insert new, delete old
    // Insert the page here before the old node
    let newVNodeElm = creatElement(newVNode)
    if(oldVNode.elm.parentNode && newVNodeElm){
      oldVNode.elm.parentNode.insertBefore(newVNodeElm, oldVNode.elm)
      // Delete the old node
      oldVNode.elm.parentNode.removeChild(oldVNode.elm)
    }
  }
}

function vNode(sel, data, children, text, elm){
  return {
    sel, data, children, text, elm, key: data.key
  }
}

// Check if it is the same node
function checkSameNode(a,b){
  return a.sel === b.sel && a.key === b.key
}

// The vNode is an orphan node
export default function createElement(vNode){
  let domNode = document.createElement(vNode.sel)
  // Does it have child nodes or text?
  if(vNode.text ! = =' ' && (vNode.children == undefined || vNode.children.length === 0)) {// It contains text
    domNode.innerText = vNode.text
  }else if(Array.isArray(vNode.children) && vNode.children.length > 0) {// It contains child nodes, which need to be recursed
    for (let index = 0; index < vNode.children.length; index++) {
      // Get the current children
      const element = vNode.children[index];
      // Create its DOM, once the call to createElement means that the DOM is created, and its ELM property points to it
      // The dom created is not yet on the tree and is an orphan node
      let elementDom = createElement(element)
      domNode.appendChild(elementDom)
    }
  }
  // Add the elm attribute
  vNode.elm = domNode
  / / returns the elm
  return vNode.elm
}

// Compare the same virtual node
function patchVNode(oldVNode, newVNode){
  // Check whether old and new vNodes are the same object
  if(oldVNode === newVNode){
    console.log("It's the same object.")
    return 
  }
  // Check whether newVNNode contains a text attribute
  if(newVNode.text ! = =undefined && (newVNode.children === undefined || newVNode.children.length == 0)) {// newVNode has a text attribute
    if(newVNode.text ! == oldVNode.text ){ oldVNode.elm.innerText = newVNode.text } }else {
    // newVNode does not have a text attribute, that is, a children attribute
    // Check whether oldVNode has children
    if(oldVNode.children ! = =undefined && oldVNode.children.length >0) {// Old has children, which is the most complicated case, newVNode, oldVNode both have children
      updateChildren(oldVNode.elm, oldVNode.children, newVNode.children)
    }else{
      // oldVNode has no children,newVNode has children
      oldVNode.elm.innerText = ""
      newVNode.children.forEach(item= > {
        let domNode = createElement(item)
        oldVNode.elm.appendChild(domNode)
      })
    }
  }
}

// oldVNode and newVNode both have the children attribute
function updateChildren(parentElm, oldChildren, newChildren){
  / / the old before
  let oldStartIndex = 0
  / / new front
  let newStartIndex = 0
  / / after the old
  let oldEndIndex = oldChildren.length - 1
  / / new after
  let newEndIndex = newChildren.length - 1
  // Old former node
  let oldStartVNode = oldChildren[0]
  // Old back node
  let oldEndVNNode = oldChildren[oldEndIndex]
  // New front node
  let newStartVNode = newChildren[0]
  // New post-node
  let newEndVNode = newChildren[newEndIndex]
  // Set of keys in the old node
  let keyMap
  while(oldStartIndex<=oldEndIndex && newStartIndex <= newEndIndex){
    // If the old start node does not exist, undefined was set earlier
    if(oldStartVNode == null) {// Note that undefined == null is true
      oldStartVNode = oldChildren[++oldStartIndex]
    }else if(oldEndVNNode == null){
      oldEndVNNode = oldChildren[--oldEndIndex]
    }else if(newStartVNode == null){
      newStartVNode = newChildren[++newStartIndex]
    }else if(newEndVNode == null){
      newEndVNode = newChildren[--newEndIndex]
    }
    if(checkSameNode(newStartVNode, oldStartVNode)){
      // The new node is the same as the old node
      console.log("① The new one is the same as the old one")
      patchVNode(oldStartVNode, newStartVNode)
      oldStartVNode = oldChildren[++oldStartIndex]
      newStartVNode = newChildren[++newStartIndex]
    }else if(checkSameNode(newEndVNode, oldEndVNNode)){
      // The new node is the same as the old node
      console.log("② The new queen is the same as the old queen")
      patchVNode(oldEndVNNode, newEndVNode)
      oldEndVNNode = oldChildren[--oldEndIndex]
      newEndVNode = newChildren[--newEndIndex]
    }else if(checkSameNode(newEndVNode, oldStartVNode)){
      // The new node is the same as the old node
      console.log(③ The new queen is the same as the old one.)
      patchVNode(oldStartVNode, newEndVNode)
      // When the new queen matches the old one, it is necessary to move the node. Move the node pointed by the new one to the old one
      // TODO query: why not set undefined? Does insertBefore affect whether the node will be deleted after moving?
      parentElm.insertBefore(oldStartVNode.elm, oldEndVNNode.elm.nextSibling)
      oldStartVNode = oldChildren[++oldStartIndex]
      newEndVNode = newChildren[--newEndIndex]
    }else if(checkSameNode(newStartVNode, oldEndVNNode)){
      // The new node is the same as the old node
      console.log("④ The new front is the same as the old one")
      // To move the node, move the new node to the front of the old node
      patchVNode(oldEndVNNode, newStartVNode)
      // TODO query: why not set undefined? Does insertBefore affect whether the node will be deleted after moving?
      // Note that insertBefore deletes the original node information
      parentElm.insertBefore(oldEndVNNode.elm, oldStartVNode.elm)
      oldEndVNNode = oldChildren[--oldEndIndex]
      newStartVNode = newChildren[++newStartIndex]
    }else {
      console.log("None of them hit.")
      // Continue to see if there are any left
      if(! keyMap){ keyMap = {}for (let index = oldStartIndex; index < oldEndIndex; index++) {
          const key = oldChildren[index].key
          if(key ! = =undefined){
            keyMap[key] = index
          }
        }
      }
      // Find the location of the current item (newStartIndex) in the keyMap
      const idxInOld = keyMap[newStartVNode.key]
      if(idxInOld == null) {// If idxInOld is undefined, it is a new project
        parentElm.insertBefore(createElement(newStartVNode), oldStartVNode.elm)
      }else{
        console.log("If it's not undefined it's not a new item and needs to be moved.")
        // If undefined, the project is not new and needs to be moved
        const elmToMove = oldChildren[idxInOld]
        patchVNode(elmToMove, newStartVNode)
        // Set this item to undefined to indicate that the item has been processed
        oldChildren[idxInOld] = undefined
        // Move, insertBefore can also move
        // Move to the front of oldStartIndex
        parentElm.insertBefore(elmToMove.elm, oldStartVNode.elm)
      }
      newStartVNode = newChildren[++newStartIndex]
    }
  }
  // At the end of the loop, the number of new nodes is less than or equal to that of new nodes
  // Insert the node to be added before the new node
  if(newStartIndex <= newEndIndex){
    console.log('New node needs new')
    for (let index = newStartIndex; index <= newEndIndex; index++) {
      parentElm.insertBefore(createElement(newChildren[index]), oldStartVNode.elm)
    }
  }else if(oldStartIndex <= oldEndIndex){
    console.log("Old nodes need to be deleted.")
    // At the end of the loop, these nodes need to be deleted
    for (let index = oldStartIndex; index <= oldEndIndex; index++) {
      // There is a node marked undefined
      oldChildren[index] && parentElm.removeChild(oldChildren[index].elm)
    }
  }
}

Copy the code

The end of the

The resources

Virtual DOM and Diff algorithms for Vue source code Parsing

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Snabbdom: Virtual DOM and Diff algorithm

Snabbdom

What is the Diff algorithm

Diff effect display

What is the virtual DOM

Analysis of the

Code implementation

H function implementation

Morphological analysis:

Code implementation

Implementation of patch function

tips

Step analysis:

Flowchart screenshot

Finish writing the function

The end of the

The resources

Recommended reading

Snabbdom: Virtual DOM and Diff algorithm

Snabbdom

What is the Diff algorithm

Diff effect display

What is the virtual DOM

Analysis of the

Code implementation

H function implementation

Morphological analysis:

Code implementation

Implementation of patch function

tips

Step analysis:

Flowchart screenshot

Finish writing the function

The end of the

The resources

Recommended reading

Related Posts

Why use a state management tool like VUEX

What is the PWA?

Vue Application of Unit Testing strategies and Practices 04 – Vuex Unit Testing