Virtual DOM

What is the Virtual DOM

The Virtual DOM is essentially a JS object with properties such as Tag props, Text Children. These object properties are used to describe the properties of DOM nodes. Finally, the JS object can be converted to the real DOM through a series of operations. Here is a virtual DOM object

var a = {
  tag: 'div'.props: {},
  children: [{tag: 'div'.props: {}, text: 'hello world'}}]// <div>
// 
      

        hello world 
      

// </div>
Copy the code

Why the Virtual DOM

  1. Improved rendering performance. A real DOM element is very large, and when we manipulate the DOM in large numbers and frequently, it can cause performance problems. The virtual DOM can update the view reasonably through diff algorithm
  2. Cross-platform. Virtual DOM is based on JavaScript objects and does not depend on the real platform environment, so it has the ability to cross platform, such as browser platform, Weex, Node, etc.

If you want to know more about the virtual DOM, you can look at the virtual DOM in Snabbdom. vue, which borrows from the SnabbDOM

All nodes mentioned above refer to virtual nodes

How to implement virtual DOM and diff algorithm in VUE

The Diff algorithm

When we modify the data, we manipulate the entire DOM. This is obviously very performance costly. Can we compare the changes that need to be corrected before and after? To modify the DOM specifically. This reduces browser redrawing and rearrangement

Diff’s comparison

When we use the DIff algorithm to compare the old and new nodes, we will only compare them at the same level, not across levels. You can see the figure for details

We’ve transformed the first HTML into the second HTML

<div>
  <ul>
      <li>A</li>
      <li>B</li>
      <li>C</li>
  </ul>
<div>Template compilation, into the following h (' h1, {}, [h (' div '{key:' A '}, 'A'), h (' div '{key:}' B ', 'B'), h (' div '{key:}' C ', 'C')])<div>
  <ul>
      <li>C</li>
      <li>B</li>
      <li>A</li>
  </ul>
</div>Template compilation, into the following h (' h1, {}, [h (' div '{key:}' C ', 'C'), h (' div '{key:}' B ', 'B'), h (' div '{key: 'A'}, 'A'),]) // Diff only compares div to div and ul to ul. It is not possible to compare div and UL.Copy the code

H function

The main function of h function is to convert real nodes into virtual nodes. Here we implement a simple H function. H function must pass three arguments, for the sake of simple code, only the core function (h function in VUE can pass any argument)

import vnode from './vnode.js'
// console.log(vnode(div))
export default function h(sel, data, c) {
  if(arguments.length ! = =3) {
    throw new Error("Please enter three parameters")}// Check the type of parameter c
  if(typeof c === 'string' || typeof c === 'number') {
    return vnode(sel, data, undefined, c, undefined)}else if (Array.isArray(c)) {
    let children = []
    for(let i=0; i<c.length; i++) {if(!typeof c[i] === 'object' && c.hasOwnProperty(sel)){
        throw new Error("Please enter the correct parameters")
      }
      children.push(c[i])
    }
    return vnode(sel, data, children, undefined.undefined)}else if(typeof c === 'object' && c.hasOwnProperty(sel)) {
    return vnode(sel, data, [c], undefined.undefined)}else {
    throw new Error("Please enter the correct parameters")}}Copy the code

VNode function

VNode generates the real virtual DOM

export default function(sel,data,children,text,elm) {
  const key = data.key
  return {
    sel,data,children,text,elm,key
  }
}
Copy the code

After doing this, we turn the node into a virtual DOM

The general idea of diff algorithm

Step 1 Check whether the two nodes have the same tag and key. 2. Check whether the two nodes are the same. If they are the same, do not perform step 3. Determines whether the new node has child elements. If not, replace text directly. Step 4. Check whether the old node contains child elements. If not, directly replace the child elements of the old node with the child elements of the new node. Step 5. If the old node also has child elements. So fine comparison (which is a core part of the DIff algorithm)

Patch method

Click the button to compare the two virtual nodes. The patch method only makes a simple interception, and the first element is different, so it will directly replace by violence. If it is the same, then the patchvnode method will be called to carry out the steps 1, 2, 3 and 4 above

import vnode from './vnode.js' import createElement from './createElement.js' import patchVnode from './patchVnode.js' export default function patch(oldVnode, NewVnode) {if (oldVnode sel = = '| | oldVnode. Sel = = = undefined) {/ / that's a real dom object oldVnode = vnode(oldVnode.tagName.toLowerCase(),{},[],undefined, oldVnode) } if(oldVnode.key === newVnode.key && oldVnode.sel === newVnode.sel) { patchVnode(oldVnode, Let newVnodeElm = createElement(newVnode) if(oldvNode.elm! = undefined) { oldVnode.elm.parentNode.insertBefore(newVnodeElm, oldVnode.elm) } oldVnode.elm.parentNode.removeChild(oldVnode.elm) // console.log("1111") } }Copy the code

PatchVnode method

Here, The patchVnode mainly performs the diff 1, 2, 3, and 4 steps (step 5 is the updateChildren method later). The patchVonde method mainly compares the first layer. If there are children below, go to Step 5(Update child)

import createElement from './createElement.js'
import updateChildren from './updateChildren.js'
export default function patchVnode(oldVnode, newVnode) {
  if(oldVnode === newVnode) return 
    if(newVnode.text ! = =undefined && (newVnode.children === undefined || newVnode.children.length === 0)) {
         // The new node has text
         if(newVnode.text ! = oldVnode.text) { oldVnode.elm.innerText = newVnode.text } }else {
      if(oldVnode.children ! =undefined && oldVnode.children.length > 0) {
      // If both have child elements, perform a fine comparison
        updateChildren(oldVnode.elm, oldVnode.children, newVnode.children)
      }else {
        oldVnode.elm.innerHTML = ' '
        for(let i = 0; i<newVnode.children.length; i++) {let dom = createElement(newVnode.children[i])
          oldVnode.elm.appendChild(dom)
        }
      }
    }
}
Copy the code

CreateElement method method

This method is used to convert our virtual nodes into real DOM

export default function createElement (vnode) {
  let domNode = document.createElement(vnode.sel)
  if(vnode.text! =' ' && (vnode.children == undefined || vnode.children.length == 0)) {
    domNode.innerText = vnode.text
  }else if(Array.isArray(vnode.children) && vnode.children.length > 0) {// createElement()
    for (let i = 0; i < vnode.children.length; i++) {
      const ch = vnode.children[i]
      let chDom = createElement(ch)
      domNode.appendChild(chDom)
    }
  }
  vnode.elm = domNode
  return vnode.elm
}
Copy the code

Refined comparison (Step 5)

We call one element of the old node the last element of the old node the last element of the old node the last element of the new node the new former node and the last element of the new node the new post-node and there are five main cases of refinement

  1. Old node === new node
  2. Old rear node === new rear node
  3. New back node === old front node
  4. New front node === Old back node
  5. If the above four cases are not satisfied, all the child elements of the old node are traversed to find whether there are elements of the new node

The above five cases are executed in sequence. If one of these conditions is satisfied, the subsequent comparison will not be made, and it will go to the next node for comparison

Is a

Old node === new node

Case 2

Old rear node === new rear node

Is three

New back node === old front node

Is four

New front node === Old back node

Is five

None of the above four cases are satisfied

updateChildren

import patchVnode from "./patchVnode.js";
import createElement from "./createElement.js";
function checkSameVnode(a, b) {
  return a.sel === b.sel && a.key === b.key;
}
export default function updateChildren(parentElm, oldCh, newCh) {
  // console.log(' I am update')
  / / the old before
  let oldStartIdx = 0;
  / / new front
  let newStartIdx = 0;
  / / after the old
  let oldEndIdx = oldCh.length - 1;
  / / new after
  let newEndIdx = newCh.length - 1;
  // Old former node
  let oldStartVnode = oldCh[0];
  // Old back node
  let oldEndVnode = oldCh[oldEndIdx];
  // New front node
  let newStartVnode = newCh[0];
  // New post-node
  let newEndVnode = newCh[newEndIdx];

  let keyMap = null;
  // console.log('33333')
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    // console.log(oldStartVnode, )
    // The new is the same as the old
    if (oldCh[oldStartIdx] === void 0 || oldStartVnode == null) {
      oldStartVnode = oldCh[++oldStartIdx];
    } else if (oldEndVnode === null || oldCh[oldEndIdx] === void 0) {
      oldEndVnode = oldCh[++oldEndIdx];
    } else if (newStartVnode === null || newCh[newStartIdx] == void 0) {
      newStartVnode = newCh[++newStartIdx];
    } else if (newEndVnode === null || newCh[newEndIdx] === void 0) {
      newEndVnode = newCh[++newEndIdx];
    } else if (checkSameVnode(oldStartVnode, newStartVnode)) {
      // console.log('4454')
      patchVnode(oldStartVnode, newStartVnode);
      oldStartVnode = oldCh[++oldStartIdx];
      newStartVnode = newCh[++newStartIdx];
    } else if (checkSameVnode(oldEndVnode, newEndVnode)) {
      // console.log('1111111')
      // New queen and old queen
      patchVnode(oldEndVnode, newEndVnode);
      oldEndVnode = oldCh[--oldEndIdx];
      newEndVnode = newCh[--newEndIdx];
    } else if (checkSameVnode(oldStartVnode, newEndVnode)) {
      // The new and the old
      patchVnode(oldStartVnode, newEndVnode);
      parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling);
      oldStartVnode = oldCh[++oldStartIdx];
      newEndVnode = newCh[--newEndIdx];
    } else if (checkSameVnode(oldEndVnode, newStartVnode)) {
      // New before and old after
      patchVnode(oldEndVnode, newStartVnode);
      parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm);
      oldEndVnode = oldCh[--oldEndIdx];
      newStartVnode = newCh[++newStartIdx];
    } else {
      // There are no matches
      if(! keyMap) { keyMap = {};for (let i = oldStartIdx; i <= oldEndIdx; i++) {
          const key = oldCh[i].key;
          if(key ! = =void 0) { keyMap[key] = i; }}}const idxInOld = keyMap[newStartVnode.key];
      if (idxInOld === void 0) {
        / / new
        parentElm.insertBefore(createElement(newStartVnode),oldStartVnode.elm)
      } else {
        // Not entirely new
        const eleToMove = oldCh[idxInOld];
        patchVnode(eleToMove, newStartVnode);
        oldCh[idxInOld] = void 0; parentElm.insertBefore(eleToMove.elm, oldStartVnode.elm); } newStartVnode = newCh[++newStartIdx]; }}// At the end
  if (newStartIdx <= newEndIdx) {
    // There are still nodes to deal with

    for (leti = newStartIdx; i <= newEndIdx; i++) { parentElm.insertBefore(createElement(newCh[i]), oldCh[oldStartIdx].elm); }}else if (oldStartIdx <= oldEndIdx) {
    for (let i = oldStartIdx; i <= oldEndIdx; i++) {
      if(oldCh[i]) { parentElm.removeChild(oldCh[i].elm); }}}}Copy the code

See github on the home page for the complete code implementation