First, a brief introduction to the virtual DOM and diff algorithms

A brief introduction to the DIff algorithm

/ / the old node
<div class="box">
    <h3>I am heading</h3>
    <ul>
        <li>milk</li>
        <li>coffee</li>
        <li>coke</li>
    </ul>
</div>
Copy the code

into

/ / the new node
<div class="box">
    <h3>I am heading</h3>
    <span>I am a new span</span>
    <ul>
        <li>milk</li>
        <li>coffee</li>
        <li>coke</li>
        <li>Sprite</li>
    </ul>
</div>
Copy the code

In vUE, the new node renders the SPAN tag to the DOM via v-if, and then pushes a Sprite into the array. There is a problem. You can’t remove all the old nodes and replace them with new ones.

Faced with the above problems, here is our diff algorithm. In fact, we just need to insert the SPAN tag and Sprite into the position of the old node, then this is the diff algorithm, it can carry out fine comparison, to achieve the minimum update.

A brief introduction to the virtual DOM

Real DOM

<div class="box">
    <h3>I am heading</h3>
    <ul>
        <li>milk</li>
        <li>coffee</li>
        <li>coke</li>
    </ul>
</div>
Copy the code

Virtual DOM

{
    "sel": "div"."data": {
        "class": { "box": true}},"children": [{"sel": "h3"."data": {},
            "text": "I am the title."
        },
        {
            "sel": "ul"."data": {},
            "children": [{"sel": "li"."data": {}, "text": "Milk" },
                { "sel": "li"."data": {}, "text": "Coffee" },
                { "sel": "li"."data": {}, "text": "Coke"}]}]}Copy the code

In short, the virtual DOM is a representation of the real DOM abstracted into data.

The following will be introduced:

  • Snabbdom profile
  • hFunction introduction and handwritten snabbDOMhFunction (how the virtual DOM is generated by the render function (h function))
  • The snabbdomdiffAlgorithm principle
  • How does the virtual DOM passdiffBecomes the real DOM (covered indiffAmong the algorithms)

Snabbdom profile

Snabbdom is a famous virtual DOM library, is the originator of diff algorithm, Vue source code reference snabbDOM. Diff algorithm and update strategy of child node are introduced.

The official git:github.com/snabbdom/sn…

This tutorial does not examine how the DOM becomes a virtual DOM, but belongs to the principle of template compilation.

H function introduction

The h function is used to generate a virtual node (vNode), for example by calling h:

H (' a ', {props: {href: 'http://www.baidu.com'}}, 'baidu')Copy the code

You get a virtual node like this.

{' sel ':' a 'and' data ': {props: {href:' http://www.baidu.com '}}, 'text' : 'a baidu'}Copy the code

This represents the actual DOM node:

<a href="http://www.baidu.com">Copy the code

A virtual node has the following attributes:

{children:undefined, data:{}, elm:undefined, sel:'div', text:' I am a box '}Copy the code
  • Children: The array type of the children of the current element.
  • Data: attributes, styles, etc.
  • Elm: the corresponding real virtual node, if yesundefinedIndicates that the current node has not actually been rendered into the DOM.
  • Key: Unique identifier, such as the key attribute in vUE
  • Text: indicates the literal attribute of a node

Let’s look at how snabbDOM uses the H function to render virtual nodes into the DOM.

import {init} from 'snabbdom/build/init' import {classModule} from 'snabbdom/build/modules/class' import {propsModule} from 'snabbdom/build/modules/props' import {styleModule} from 'snabbdom/build/modules/style' import {eventListenersModule} from 'snabbdom/build/modules/eventlisteners' import {h} from 'snabbdom/build/h' const patch = init([ // Init patch function with chosen modules 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")// represents the real DOM node, which must declare the element through an HTML page under a static resource configured by WebPack. Const myVnode = h('p', {props:{class:{p1:true}, 'I'm p')//myVnode is a virtual node patch(container, The myVnode //patch function compares the DOM rendered in the page with the myVode virtual node to be compared, and then renders the virtual node into the DOM.Copy the code

hFunctions can be nested to produce the virtual DOM, for example:

h('ul', {}, [
  h('li', {}, [
    h('p',{},'p1'),
    h('p',{},'p2')
  ]),
  h('li', {}, 'p3')
])
Copy the code

The resulting virtual DOM tree looks like this:

After looking at the general usage method and concept, the following start writing h function:

Disclaimer: This function is low edition, only write the core function!

Import vnode from ". / vnode "/ / form a h (' div ', {}, 'text') / / form 2 h (' div ', {}, []) / / form three h (' div ', {}, h (), export the default function  (sel, data, c) { if (arguments.length ! = = 3) {throw the Error (" h function parameters must be 3 ")} else if (typeof c = = = 'string' | | typeof c = = = 'number') {/ / the first form: direct return to return Vnode (sel, data, undefined, c, undefined)} else if (array.isarray (c)) {// let children = [] for (let i = 0; i < c.length; I ++) {// Instead of executing c[I], the test case already executed if (! (c[I] &&c [I].hasownProperty ('sel'))) {throw Error(" argument not h function ")} // Collect children children. Push (c[I])} return vnode(sel, data, children, undefined, Undefined)} else if (typeof c === 'object' &&c. hasownProperty ('sel')) {// let children = [c] return vnode(sel, Data, children, undefined, undefined)} else {throw Error(" Error ")}}Copy the code

The following is the core function patch. The general thinking is as follows:

import vnode from "./vnode" import createElement from './createElement' import patchVnode from './patchVnode' export Default function (oldVnode, newVnode) {// If it is a real node, wrap it as a virtual node. if (! oldVnode.sel) { oldVnode = vnode(oldVnode.tagName.toLowerCase(), {}, [], undefined, If (oldvNode. key === newvNode. key && oldvNode. sel === newvNode. sel) {console.log(' Is the same node, Make a fine comparison '); // Maintain a function to recursively patchVnode(oldVnode, newVnode)} else {console.log(' Delete old, insert new '); ParentNode let newVnodeElm = createElement(newVnode) Inserted into the old node before oldVnode. Elm. ParentNode. The insertBefore (newVnodeElm, oldVnode. Elm)}}Copy the code

PatchVnode function (Fine comparison)

import createElement from "./createElement"; import updateChildren from "./updateChildren"; export default function patchVnode(oldVnode, NewVnode) {if (oldVnode === newVnode) return if (newvNode.text! = = '&& (! newVnode.children || ! Newvnode.children.length) {// console.log(' New node has text property! '); if (newVnode.text ! == oldvNode.text) {// console.log(' New node old node text attribute same! '); Oldvnode.elm.innertext = newvNode. text}} else {// console.log('newVnode has no text property '); // Check whether the old node has the children attribute, if so, we need to do the most complicated case calculation. if (oldVnode.children && oldVnode.children.length) { updateChildren(oldVnode.elm, oldVnode.children, newVnode.children) } else { oldVnode.elm.innerText = "" for (let i = 0; i < newVnode.children.length; i++) { let ch = createElement(newVnode[i]) oldVnode.elm.appendChild(ch) } } } }Copy the code

The updateChildren function, and then the heart of the diff algorithm.

There are four ways to compare. If none of them hit, use the for loop to compare

import createElement from "./createElement"; import patchVnode from "./patchVnode"; function isSameNode(a, b) { return a.sel === b.sel && a.key === b.key } export default function updateChildren(parentElm, oldch, newch) { let oldStartIdx = 0; let oldEndIdx = oldch.length - 1; let oldStartVnode = oldch[0]; let oldEndVnode = oldch[oldEndIdx]; let newStartIdx = 0; let newEndIdx = newch.length - 1; let newStartVnode = newch[newStartIdx]; let newEndVnode = newch[newEndIdx]; let keyMap = null; While (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {// leave undefined if (! oldStartVnode || ! oldch[oldStartIdx]) { oldStartVnode = oldch[++oldStartIdx] } else if (! oldEndVnode || ! oldch[oldEndIdx]) { oldEndVnode = oldch[--oldEndIdx] } else if (! newStartVnode || ! newch[newStartIdx]) { newStartVnode = newch[++newStartIdx] } else if (! newEndVnode || ! Newch [newEndIdx]) {newEndVnode = newch[--newEndIdx]} else if (isSameNode(oldStartVnode, newStartVnode)) { Console. log(' Hit 1: New and old '); patchVnode(oldStartVnode, newStartVnode) oldStartVnode = oldch[++oldStartIdx] newStartVnode = newch[++newStartIdx] } else if (isSameNode(oldEndVnode, newEndVnode)) { // console.log('sel:',oldEndVnode.sel,newEndVnode.sel); // console.log('key:',oldEndVnode.key,newEndVnode.key); Console. log(' Hit 2: New and old '); PatchVnode (oldEndVnode, newEndVnode) oldEndVnode = oldch[--oldEndIdx] newEndVnode = newch[--newEndIdx] } else if (isSameNode(oldStartVnode, newEndVnode)) { console.log(oldStartVnode, newEndVnode, 'inner'); Console. log(' Hit 3: New and old '); // Compare nodes. PatchVnode (oldStartVnode, newEndVnode) // Sequential replacement: Move the old node to the end of the old node. parentElm.insertBefore(oldStartVnode.elm, oldStartVnode.elm.nextsibling) oldStartVnode = oldch[++oldStartIdx] newEndVnode = newch[--newEndIdx] } else if (isSameNode(newStartVnode, oldEndVnode)) {console.log(' Hit 4: New before and old after '); // Compare nodes. PatchVnode (newStartVnode, oldEndVnode) // Sequential replacement: Move the old node to the front of the old one. parentElm.insertBefore(oldEndVnode.elm, Oldstartvnode. elm) oldEndVnode = oldch[--oldEndIdx] newStartVnode = newch[++newStartIdx]} else Make a keyMap so that you don't have to iterate over old objects every time. if (! keyMap) { keyMap = {} for (let i = oldStartIdx; i <= oldEndIdx; i++) { let key = oldch[i].key if (key ! == undefined) { keyMap[key] = i } } } let idxInOld = keyMap[newStartVnode.key] if (idxInOld === undefined) { // Parentelm. insertBefore(createElement(newStartVnode), parentelm. insertBefore(createElement(newStartVnode), ElmToMove = oldch[idxInOld] // console.log(elmToMove, elmToMove, elmToMove) 'elmToMove'); // Set this item to undefined to indicate that the item has been processed. patchVnode(elmToMove, newStartVnode) oldch[idxInOld] = undefined; parentElm.insertBefore(elmToMove.elm, oldStartVnode.elm) } newStartVnode = newch[++newStartIdx] console.log(keyMap, 'keyMap'); }} // There are several possibilities when the while condition ends: // 1. The new children is finished, but the old children is not finished, indicating that the old children will be deleted. // old: 1,2,3,4, 5 new: 1,2,3 // 2. The new children is not finished, but the old children is finished, indicating that the old children will be added. // new: 1,2,3,4, 5 if (newStartIdx <= newEndIdx) {console.log(' newStartIdx '); // let before =! newch[newStartIdx + 1]? null : newch[newStartIdx + 1].elm let before = ! oldch[oldStartIdx] ? null : oldch[oldStartIdx].elm for (let i = newStartIdx; i <= newEndIdx; I++) {// insertBefore's second argument, if null, means the same as appendChild. If it's not null, Parentelm. insertBefore(createElement(newch[I]), Before)}} else if (oldStartIdx <= oldEndIdx) {console.log(' oldStartIdx <= oldEndIdx '); for (let i = oldStartIdx; i <= oldEndIdx; i++) { if (oldch[i]) { parentElm.removeChild(oldch[i].elm) } } } }Copy the code

The createElement function (mount to the DOM tree)

// Make the virtual DOM into a real DOM // Check whether the text and child attributes can not co-exist // check whether the DOM is a text // recurse the child of the DOM, Export default function createElement(vnode) {console.log(' to change the virtual DOM into the real DOM'); Let domNode = document.createElement(vnode.sel) // check whether it is a text if (vnode.text! = = "" &&! vnode.children) { domNode.innerText = vnode.text } else if (Array.isArray(vnode.children) && vnode.children.length) { for (let i = 0; i < vnode.children.length; I ++) {let ch = vnode.children[I] let chNode = createElement(ch) domNode.appendChild(chNode)}} vnode.elm = domNode return domNode }Copy the code