Virtual DOM and comparison algorithm

This article is compiled in recent study, the content is about Vue2.0 virtual DOM and comparison algorithm explanation. This article continues to be explained as easily as possible. If any part is not explained clearly, or there are mistakes in the writing, please criticize and correct

Recently, I am still sorting out what I have learned in Vue. Write Vue again from 0. The content of this article will be used in that article.

The theoretical knowledge

Why do you need the virtual DOM

The DOM is big, it has a lot of elements in it. It is a waste of time and performance to operate. So we need to introduce the concept of the virtual DOM

What is the virtual DOM

To put it simply, the virtual DOM is to simulate the real DOM with objects in JS, and then transform it into the real DOM through methods

advantages

  1. In the endReal DOMonPart of the change, to ensure the efficiency of rendering
  2. Performance improvement (vs. real DOM manipulation)

The official start of the

Train of thought

  1. We need to get a node to mount our render results
  2. We need to put objects (Virtual node), render as real nodes. Insert into the obtained node (of course there is a lot of tedious process in this process. More on that later.)
  3. In the process of updating, we need to comparedomElement attributes that can be reused. Update if you can’t reuse it

webpackconfiguration

// webpack.config.js
const path = require('path')
const HtmlWebpackPlugin = require('html-webpack-plugin')
module.exports = {
  entry: './src/vdomLearn/index.js'.// Import file
  output: {  // Output file
    filename: 'bundle.js'.path: path.resolve(__dirname,'dist'),},devtool: 'source-map'.// Source mapping
  plugins: [ / / the plugin
      new HtmlWebpackPlugin({
        template: path.resolve(__dirname,'public/index.html'),})],}// package.json
"scripts": {
    "start": "webpack-dev-server"."build": "webpack"
  },
Copy the code

Get the node and render for the first time

Let’s start by looking at our template Html. Nothing important, just a div with id=’#app’ (as the mounted node)


      
<html lang="zh">
<head>
    <meta charset="UTF-8">
    <meta name="viewport"
          content="Width =device-width, user-scalable=no, initial-scale=1.0, maximum-scale=1.0, minimum-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Vue</title>
</head>
<body>
<div id="#app">

</div>
</body>
</html>
Copy the code

We create a file named index.js to be used as the entry file

// Get the mounted node
let app = document.getElementById('#app')

// Create a virtual node with dead data
let oldNode = h('div', {id:'container'},
 h('span', {style: {color:'red'}},'hello')
 'hello'              
)

// The render function mounts the virtual node we created to the corresponding node
render(oldNode,app)
Copy the code

Why is it called that? H follows the name in Vue. The rest are mostly English translations

Specific goals

With the index.js file above, we know the target.

  1. We need ahMethods to putVirtual DOMBecome a real DOM
  2. We need one morerenderMethod to mount the node we created toappon

So let’s start writing these two methods

For the convenience of management. Let’s create a new folder called vDOM. There is an index.js file that serves as the total export

// vdom/index.js
import h from './h'
import {render} from './patch';

export {
  h,render
}
Copy the code

H method

For easy administration, we create a file called vnode.js. Used to hold content related to virtual nodes

// vdom/vNode.js
// Put virtual nodes
/** * Create virtual DOM * @param props * @param props * @param key Only one * @param children * @param text Text content // Returns a virtual node * @ returns {{children: *, tag: *, text: *, key: *, props: *}} * /
export function vNode(tag,props,key,children,text=' ') {
  return {
    tag,
    props,
    key,
    children,
    text
  }
}
Copy the code
// vdom/h.js
import {vNode} from './vNode';

// Render related
/** * h: CreateElement @param props * @param props * @param children *, text: *, key: *, props: *}} Returns a dummy DOM */
export default function h(tag,props,... children){
    / /... Is ES6 grammar
  let key = props.key / / logo
  delete props.key   // There is no key attribute in the property
    
    If the child node is an object, then it is a node. If not, the proof is a text
  children = children.map(child= >{
    if (typeof child === 'object') {console.log(child)
      return child
    }else {
      return vNode(undefined.undefined.undefined.undefined,child)
    }
  })
  // Key function Only one Indicates whether two virtual nodes are the same
  // Returns a virtual node
  return vNode(tag,props,key,children)
}
Copy the code

Render method

The render method converts the virtual node into a real node and mounts it to the app node. We put it in a file called patch.js

// vdom/patch.js
/** * render as a real node and mount * @param vNode virtual DOM * @param container
export function render(vNode, container) { // Turn virtual nodes into real nodes
  let el = createElem(vNode)
  container.appendChild(el) // Add the created real node to the app
}
Copy the code

After passing in the virtual node, we create the real node based on the virtual node. So let’s write a method called createElem to turn the virtual node into the real one

createElemmethods

// vdom/patch.js

/ /... I've omitted the render method above
/ * * * according to create real virtual node * @ param vNode virtual DOM * @ returns {any | Text} * / return true node
function createElem(vNode) {
  let { tag, props, children, text, key } = vNode
  if (typeof tag === 'string') { // div span, etc
    vNode.el = document.createElement(tag) // Create node Mount the created real node to the virtual node
    updateProperties(vNode)  // Update property methods
    // See if there is a child. If there is a child, render the child
    children.forEach(child= > {
      return render(child, vNode.el)
    })
  } else { // undefined vnode. el corresponds to the real DOM element in the virtual node
    vNode.el = document.createTextNode(text)
  }
  return vNode.el
}
Copy the code

The difficulty to explain

The part I find difficult to understand is the for traversal, where children are virtual child nodes (created using method H). If it has a tag attribute, it is proved to be a node. It may contain other nodes. So we’re going to iterate over children. Take each virtual child node, continue rendering, and mount the real DOM on all virtual child nodes. If it is text, create a text node directly. Then return the real DOM.

updatePropertiesmethods

In the process of creating a real node, let’s think about it for the future. Write a property called updateProperties to update or initialize the DOM (props)

// vdom/patch.js

/ /... I've omitted the render and createElem methods above
/** * Update or initialize DOM props * @param vNode * @param oldProps */
function updateProperties(vNode, oldProps = {}) {
  let newProps = vNode.props || {}// The current old attribute may also have no attribute in case the program fails and gives an empty object
  let el = vNode.el // The real node gets the real DOM we just mounted on the virtual node

  let oldStyle = oldProps.style || {}
  let newStyle = newProps.style || {}

  If the old style does not exist in the new style, it is null
  for (let key in oldStyle) {
    if(! newStyle[key]) { el.style[key] =' '}}// Delete attributes that do not exist in the new attributes in the update process
  for (let key in oldProps) {
    if(! newProps[key]) {delete el[key]
    }
  }

  // Consider whether you have had one before
  for (let key in newProps) {
    if (key === 'style') {
      for (let styleName in newProps.style) {
        // color red
        el.style[styleName] = newProps.style[styleName]
      }
    } else if (key === 'class') { // Handle the class attribute
      el.className = newProps.class
    } else {
      el[key] = newProps[key] // Key is an attribute such as id}}}Copy the code

** Is actually very simple

  1. Sets styles from the old property that do not exist in the new property to null
  2. Delete properties from the old property that do not exist in the new property
  3. Add/update new attributes that the old attributes do not have

Summarize and string together the process again

So here we go. This completes the process from creation of the virtual DOM to rendering

Let’s go over the process again

  1. Through the firsthMethod to combine the attributes passed in toVirtual dom
  2. throughrenderMethod, the incomingVirtual domRender and mount
  3. In the rendering process, we usedcreateElemMethod to create a real node,And mounted to the EL property of the virtual nodeAnd returns the real node
  4. In the implementationcreateElemMethod of process, we also need toAttributes of nodesMake modifications and updates. So we createdupdatePropertiesIs used to update node properties
  5. After all the methods are executed, it goes back tohMethod to mount the real node we createdappon

This is the entire process from getting the node to rendering the first time

The results show

Dom update and comparison algorithm

Above we described how to convert the virtual DOM into the real DOM. Let’s talk about dom updates

Let’s look at the index file

import {h,render,patch} from './vdom'

// Get the mounted node
let app = document.getElementById('#app')

// Create a virtual node with dead data
let oldNode = h('div', {id:'container'},
 h('span', {style: {color:'red'}},'hello')
 'hello'              
)

// The render function mounts the virtual node we created to the corresponding node
render(oldNode,app)

// We set a timer to update the DOM with the patch method
// Update the real DOM element by comparing the new node with the old one
setTimeout((a)= >{
  patch(oldNode,newNode)
},1000)

Copy the code

We update the DOM with a patch method

Export this method in a vDOM /index file

import h from './h'
import {render,patch} from './patch';

export {
  h,render,patch
}

Copy the code

Patch file

Thought analysis

What we need to do is DOM update operation, need to receive two parameters (old and new DOM), in accordance with the principle of reuse can be reused (reuse ratio new rendering efficiency is higher). Then update the properties. Then compare the child nodes. And optimize the response

patch domCompare and update

// vdom/patch.js
/ /... I left out the top one

@param oldNode @param newNode */
export function patch(oldNode, newNode) {
  // newNode is passed as an object. OldNode is a virtual node on which el is the real node
  // 1 is the same as the parent label
  if(oldNode.tag ! == newNode.tag) {// You must get the father to replace the son
    // Replace the parent of the old node by creating a real node with createElem
    oldNode.el.parentNode.replaceChild(createElem(newNode), oldNode.el)
  }
  // Compare the text to change the text content
  if(! oldNode.tag) {// Prove that it is a text node
    if(oldNode.el.textContent ! == newNode.text) { oldNode.el.textContent = newNode.text } }// Compare attributes like tags
  let el = newNode.el = oldNode.el    // The old and new labels are reused directly
  updateProperties(newNode, oldNode.props) // Update attributes

  // The child must have a root node to start the comparison
  let oldNodeChildren = oldNode.children || []
  let newNodeChildren = newNode.children || []
  // There are three situations: old and new, old and new, old and new
  if (oldNodeChildren.length > 0 && newNodeChildren.length > 0) {
    // Update the old and new
      // What is el? This is the real node rendered by two virtual nodes
    updateChildren(el, oldNodeChildren, newNodeChildren)
  } else if (oldNodeChildren.length > 0) {
    // There is nothing new but old
    el.innerHTML = ' '
  } else if (newNodeChildren.length > 0) {
    // The old have no new
    for (let i = 0; i < newNodeChildren.length; i++) {
      let child = newNodeChildren[i]
      el.appendChild(createElem(child)) // Add the new son to the old node}}return el  // Return the real node
}

Copy the code

I’ve written the simpler parts of this code. A little bit more difficult is that in the process of child comparison, both the old and new nodes have children. We need another method for updating old and new kids

updateChildrenmethods

** Updates the children of old and new nodes

/ * * * tools function, used to compare the two nodes are the same * @ param oldVnode * @ param newVnode * @ returns {Boolean | Boolean} * /
function isSameVnode(oldVnode, newVnode) {
  // If the labels and keys are the same, the virtual node can be reused
  return (oldVnode.tag === newVnode.tag) && (oldVnode.key === newVnode.key)
}


// Virtual Dom core code
/** ** @param parent parent DOM element * @param oldChildren old virtual DOM * @param newChildren new virtual DOM */
function updateChildren(parent, oldChildren, newChildren) {
  // How to compare? Compare them one by one and take out the ones that are missing and delete them or add them back
  let oldStartIndex = 0  // Old node index
  let oldStartVnode = oldChildren[0]  // Start value of the old node
  let oldEndIndex = oldChildren.length - 1 // The old node ends the index
  let oldEndVnode = oldChildren[oldEndIndex] // End value of the old node

  let newStartIndex = 0  // New node index
  let newStartVnode = newChildren[0]  // Start value of new node
  let newEndIndex = newChildren.length - 1 // The new node ends the index
  let newEndVnode = newChildren[newEndIndex] // End value of the new node
  @param child; @returns {{}} returns the mapping
  function makeIndexByKey(child) {
    let map = {}
    child.forEach((item, index) = > {
      map[item.key] = index
    })
    return map   // {a:0,b:1,c:2}
  }
  let map = makeIndexByKey(oldChildren)
  // Start comparing
  while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
    // This is mainly used to resolve array collapse caused by else operation
    if(! oldStartVnode) { oldStartVnode = oldChildren[++oldStartIndex] }else if(! oldEndVnode) { oldEndVnode = oldChildren[--oldStartIndex]// Let's start with this
      // The above code works in an else. Skipping undefined makes no sense
        // Start with the head and then start with the tail
    } else if (isSameVnode(oldStartVnode, newStartVnode)) { // Iterate over the previous insertions from the beginning
      patch(oldStartVnode, newStartVnode) // Update the old property with the new property
      // Move to start the next comparison
      oldStartVnode = oldChildren[++oldStartIndex]
      newStartVnode = newChildren[++newStartIndex]
    } else if (isSameVnode(oldEndVnode, newEndVnode)) { // start with the tail
      patch(oldEndVnode, newEndVnode) // Update the old property with the new property
      oldEndVnode = oldChildren[--oldEndIndex]
      newEndVnode = newChildren[--newEndIndex]
    } else if (isSameVnode(oldStartVnode, newEndVnode)) {
      // In reverse order
      // reverse order old head new tail
      patch(oldStartVnode, newEndVnode) // abc cba
      // This step is the key to insert the node immediately following an element of the old flashback nextSibling:
      // Parent is a real dom element of a parent
      parent.insertBefore(oldStartVnode.el, oldEndVnode.el.nextSibling)
      oldStartVnode = oldChildren[++oldStartIndex]
      newEndVnode = newChildren[--newEndIndex]
    } else if (isSameVnode(oldEndVnode, newStartVnode)) {
      // bring the tail to the front
      patch(oldEndVnode, newStartVnode)
      // The element to be inserted inserts the element position
      parent.insertBefore(oldEndVnode.el, oldStartVnode.el)
      oldEndVnode = oldChildren[--oldEndIndex]
      newStartVnode = newChildren[++newStartIndex]
    } else {
      // Compare the first item of the new node with that of the old node. If not, insert it directly in front of the old node
      // Move the old node if it is found.
      // If the old node is still available, delete it directly
      // Map is used here
      let movedIndex = map[newStartVnode.key]
      console.log(movedIndex)
      if (movedIndex === undefined) { // Can not find the condition
        // vnode. el corresponds to the real DOM element in the virtual node
        parent.insertBefore(createElem(newStartVnode), oldStartVnode.el)
      } else {    // Find the condition
        // Move this element
        let moveVnode = oldChildren[movedIndex]
        patch(moveVnode, newStartVnode)
        oldChildren[movedIndex] = undefined
        parent.insertBefore(moveVnode.el, oldStartVnode.el)
      }
      newStartVnode = newChildren[++newStartIndex]
    }
  }
  // If there are still new nodes after the comparison, insert the new nodes directly after the comparison
  if (newStartIndex <= newEndIndex) {
    for (let i = newStartIndex; i <= newEndIndex; i++) {
      // Get the node to insert
      let ele = newChildren[newEndIndex + 1] = =null ? null : newChildren[newEndIndex + 1].el
      // It is possible to plug forward or back
      parent.insertBefore(createElem(newChildren[i]), ele)
      // parent.appendChild(createElem(newChildren[i]))}}// Delete the redundant old ones after sorting
  if (oldStartIndex<= oldEndIndex){
    for (leti = oldStartIndex; i<=oldEndIndex; i++){let child = oldChildren[i]
      if(child ! = =undefined) {// If undefined is deleted, an error will be reported
        parent.removeChild(child.el)
      }
    }
  }

  // Try not to use indexes as keys, which may result in recreating all the children of the current element
  // They have the same tag and key and need to re-render the two nodes
  // Not as efficient as reuse
}

Copy the code

The isSameVnode function is used to verify that the two nodes are the same if they have the same label and the same key.

Focuses on

So let’s start with this else if. That is, the judgment condition starts with isSameVnode(oldStartVnode, newStartVnode).

The core is to simulate the operation of adding, deleting and changing the flashback of the linked list. But we did some optimization

I’m going to start with this else if and then I’m going to start with an else if at the end. The new node. The node to be updated to

  1. else ifThe things that have been done. isStart from scratchFor example, the old node is 1, 2, 3, 4. The new node is 1, 2, 3, 5. Began to callpatchMake update judgment. It determines if it’s the same node. Then update the text attribute child node. Update the old node content to 1, 2, 3, 5 until the end.
  2. else ifThe things that have been done. isStart at the tailFor example, the old node is 5, 2, 3, 4. The new node is 1, 2, 3, 4. Method as above
  3. else ifThe things that have been done. isThe inverse order was optimized. For example, the old node is 1, 2, 3, 4. The new node is 4, 3, 2, 1. When the above two conditions are not met, the first term of the old node is compared with the last term of the new node. When finished, insert it in front of the old node. By using theinsertBeforeAPI. Two parameters,a, the element to be inserted. ** Two: ** The position to insert the element
  4. else ifThe things that have been done. isBring the end node to the front. Old node 1 2 3 5. New node 5 1 2 3.

So those are the four else ifs. Easier to understand. That is to simulate linked list operations

And then we have the else

If the above conditions are not met, it is proved that the new node is out of order. In this way, we can reuse the principle of reuse, from the beginning, if the old node exists, move (note the array collapse). Create if it does not exist. Delete the excess.

steps

  1. Take advantage of what we createdmapI’m looking for the elements I want to compare
  2. If none is found, the element is created and inserted.
  3. As soon as you find itpatchThis element moves this element and sets its original position toundefined. To prevent array collapse
  4. Move the element to be compared
  5. Because we set it upundefinedSo we have to judge at the beginning.That’s why we put the if else if up front

After the while. The functions of the following two ifs are simply stated. Because of the judgment condition of while. So when one node is longer than the other node. There will be some that are not compared, and these must be new or old and redundant. Just add or delete

Plus, why not recommend indexes as keys

For example

Node A: A B C D B: b A D R

Index 0 1 2 3 B: 0 1 2 3

In the judgment condition, their indexes are different, resulting in the perception that they are not the same node.

This recreates and renders the node, which is not as efficient as simply reusing it. This is especially true when the node is large (with many children)

conclusion

This article, starting from 0, describes the process of creating a render diff for virtual nodes. There are other configurations that are not said. The use of Webpack packaging, webpack-dev-server and other plug-ins rapid development.