Virtual DOM and diff algorithm

preface

The virtual DOM and the Diff algorithm, you’ll hear about them a lot sometimes, so what are they implemented? This is what I summarized when I studied virtual DOM and the Diff algorithm, and I’m going to give you an in-depth look at the virtual DOM and the Diff algorithm. From the basic use of snabbDOM, to their own implementation of a beggar snabbDOM, their own implementation of h function (create virtual DOM) patch function (update view by comparing the old and new virtual DOM), here I also draw a few giFs to help you understand diff’s four optimization strategies, the article is a little long, I hope you can read it patiently, and I will post all the code at the end, so you can try it out

Finally, I hope you can give xiao Lang a thumbs up

Past highlights:

Writing a simple VUE responsive style takes you through the principles of responsiveness

From use to implement their own simple Vue Router to see this line

The basics of a front end interview are small but you have to know them

1. Introduction

This section describes the Virtual DOM

It is a virtual tree structure object created by JavaScript according to the STRUCTURE of the DOM. It is an abstraction of the DOM, and it is more lightweight than DOM

Why use the Virtual DOM

Front-end optimization, of course, to avoid frequent operationsDOM, frequent operationDOMBrowser backflow and redrawing is possible, performance is very low, and manual operation is requiredDOMOr more troublesome, to consider browser compatibility issues, currentlyjQuerySo the library is simplifiedDOMOperation, but the project is complicated,DOMThe operations are still going to get complicated, the data operations are going to get complicated
Not all cases use virtualityDOMBoth improve performance and are intended for use on complex projects. If the operation is simple, use virtualDOMTo create a virtualDOMObject and so onDOMoperation
virtualDOMCross-platform rendering, server rendering, applet, and native applications all use virtualityDOM
Using the virtualDOMChanging the current state does not require an immediate updateDOMAnd the updated content is updated, and no operation is done for the unchanged content. The difference between the two is compared
The virtual DOM maintains the state of the program, tracking the last state

2. Snabbdom is introduced

Let’s start with snabbDOM

To understand the virtual DOM, let’s start with its ancestor, snabbDOM

Snabbdom is an open source project. The virtual DOM in Vue was originally borrowed from SNabbDOM. We can understand the virtual DOM of Vue by understanding the virtual DOM of SNabbDOM. Therefore, it is used to carry out the research of virtual DOM

Install using NPM

npm install snabbdom
Copy the code

Snabbdom is simple to use

So let’s write a simple example using snabbDOM

<body>
  <div id="app"></div>
  <script src="./js/test.js"></script>
</body>
Copy the code

Write test.js and use it

/* test.js */

/ / import snabbdom
import { h, init, thunk } from 'snabbdom'
// The init() method returns a patch function that compares the differences between the two virtual DOMs and updates it to the real DOM
// Pass an empty array []
let patch = init([])
// The h method is used to create the Virtual DOM
// The first parameter is the virtual DOM tag
// The second parameter is the data of the virtual DOM
// The third parameter is a sub-virtual DOM of the virtual DOM
// It has a couple of ways to pass the parameters
// And can be nested
let vnode = h('div#box'.'test', [
  h('ul.list', [
    h('li'.'I'm a Li'),
    h('li'.'I'm a Li'),
    h('li'.'I'm a Li'),),)// get the HTML div#app
let app = document.querySelector('#app')
// This is used to compare the differences between two virtual DOMs and then update the real DOM
let oldNode = patch(app, vnode)
// Let's simulate an asynchronous request
setTimeout(() = > {
  let vNode = h('div#box'.'Data retrieved', [
    h('ul.list', [
      h('li'.'I'm a Li'),
      h('li'.'Difference judged by PATH'),
      h('li'.'Updated data'),),)// Then compare the differences to determine whether to update
  patch(oldNode, vNode)
}, 3000)

Copy the code

You can see that the virtual DOM is updated to the real DOM, directly replacing the previous div#app

After 3 seconds, the difference of virtual DOM was compared to add to the real DOM. Here, the second and third Li were changed to render virtual DOM with h function, which was different from oldNode, so they were compared and updated

2. Introduce modules in snABbDOM

I’m going to go through a few modules here

Module name	Introduction to the
attributes	DOM custom property, including two booleans`checked` `selected`Through the`setAttribute()`Set up the
props	Is a DOM property property, passed`element[attr] = value`Set up the
dataset	is`data-`The starting attribute data-src…
style	Inline style
eventListeners	Used to register and remove events

With the above introduction, then we will use it simply

/* module_test.js */

// SnabbDOM init() h()
import { h, init } from 'snabbdom'

// Import the module
import attr from 'snabbdom/modules/attributes'
import style from 'snabbdom/modules/style'
import eventListeners from 'snabbdom/modules/eventlisteners'

// Init () registers the module to return the value that the patch function uses to compare the differences between the two virtual DOM and then add to the real DOM
let patch = init([attr, style, eventListeners])

// Render a virtual DOM using h()
let vnode = h(
  'div#app',
  {
    // Customize attributes
    attrs: {
      myattr: 'I'm a custom property',},// Inline styles
    style: {
      fontSize: '29px'.color: 'skyblue',},// Event binding
    on: {
      click: clickHandler,
    },
  },
  'I am the content'
)

// Click the method
function clickHandler() {
  // Get the current DOM
  let elm = this.elm
  elm.style.color = 'red'
  elm.textContent = 'I've been clicked'
}

// 获取到 div#app
let app = document.querySelector('#app')

// Patch compares the differences and adds them to the real DOM
patch(app, vnode)

Copy the code

And then it’s introduced into HTML

<body>
  <div id="app"></div>
  <script src="./js/module_test.js"></script>
  <script></script>
</body>
Copy the code

Let’s see what it looks like

You can see that the custom properties, inline styles, and click events are all rendered by h()

The above usage is simply gone, so let’s take a look at the source code in snabbDOM

3. Virtual DOM example

All this talk about h() and the virtual DOM so what does the rendered virtual DOM look like

Real DOM structure

<div class="container">
  <p>Ha ha</p>
  <ul class="list">
    <li>1</li>
    <li>2</li>
  </ul>
</div>
Copy the code

The structure of the virtual DOM

{ 
  / / selector
  "sel": "div"./ / data
  "data": {
    "class": { "container": true}},// DOM
  "elm": undefined.Vue :key is an optimization like Vue :key
  "key": undefined./ / child nodes
  "children": [{"elm": undefined."key": undefined."sel": "p"."data": { "text": "Ha ha"}}, {"elm": undefined."key": undefined."sel": "ul"."data": {
        "class": { "list": true}},"children": [{"elm": undefined."key": undefined."sel": "li"."data": {
            "text": "1"
          },
          "children": undefined
        },
        {
          "elm": undefined."key": undefined."sel": "li"."data": {
            "text": "1"
          },
          "children": undefined}]}]}Copy the code

Patch method in snabbDOM mentioned earlier

Diff (fine comparison) is performed on the new virtual DOM and the old virtual DOM to find out the minimum amount of update is in the virtual DOM comparison

It is not possible to tear down all the DOM and render it all over again

4. H function

We have experienced the use of the virtual DOM above, so let’s now implement a snabbDOM version

The function H is introduced

In snabbDOM, we also used the h function many times, mainly to create virtual nodes

Snabbdom is written in TS, so the h function has a method overload that makes it flexible to use

The following is the h function in snabbDOM, and you can see that there are several ways to take arguments

export declare function h(sel: string) :VNode;
export declare function h(sel: string, data: VNodeData) :VNode;
export declare function h(sel: string, children: VNodeChildren) :VNode;
export declare function h(sel: string, data: VNodeData, children: VNodeChildren) :VNode;
Copy the code

Implement vNode functions

Before I write h, I need to implement vnode. Vnode needs to be used in H. In fact, this vnode function is very simple to implement and has many types specified in TS, but I’m going to write it here and after in JS

/* vnode.js */

/** * returns the passed arguments as objects@param {string} Sel selector *@param {object} The data data *@param {array} Children Child node *@param {string} The text text *@param {dom} elm DOM
 * @returns object* /
export default function (sel, data, children, text, elm) {
  return { sel, data, children, text, elm }
}

Copy the code

Implement the simple h function

The h function written here only realizes the main function, without the implementation of overloading, directly realizes the 3 parameter H function

/* h.js */

/ / import vnode
import vnode from './vnode'

// Export the h method
// Here is the implementation of simple 3 parameters parameter write dead
/ * * * *@param {string} a sel
 * @param {object} b data
 * @param {any} C is the child node can be text, array */
export default function h(a, b, c) {
  // Check whether there are three parameters
  if (arguments.length < 3) throw new Error('Please check the number of parameters')
  // The third parameter has uncertainty to judge
  // 1. The third parameter is the text node
  if (typeof c === 'string' || typeof c === 'number') {
    // Call vnode and pass text in
    / / the return value {sel, data, children, text, elm} back out again
    return vnode(a, b, undefined, c, undefined)}// 2. The third argument is the array [h(),h()] [h(),text]
  else if (Array.isArray(c)) {
    // However, the array must contain the h() function
    // children returns results with collection
    let children = []
    // If h() returns a result, add it to chilren
    for (let i = 0; i < c.length; i++) {
      // the return of h() is {} and contains sel
      if(! (typeof c[i] === 'object' && c[i].sel))
        throw new Error('You can only pass h() if the third argument is an array.')
      / / satisfy the conditions for a push [{sel, data, and the children, text, elm}, {sel, data, children, text, elm}]
      children.push(c[i])
    }
    / / call vnode return {sel, data, children, text, elm} back again
    return vnode(a, b, children, undefined.undefined)}/ / 3. The third parameter is directly () function returns the {sel, data, children, text, elm}
  else if (typeof c === 'object' && c.sel) {
    / / this time at the time of using h () c = {sel, data, children, text, elm} directly into the children
    let children = [c]
    / / call vnode return {sel, data, children, text, elm} back again
    return vnode(a, b, children, undefined.undefined)}}Copy the code

Is very simple, he is also not recursive, like a nested, constantly collect {sel, data, children, text, elm}

Chirldren inside again set {sel, data, children, text, elm}

For example

/* index.js */

import h from './my-snabbdom/h'

let vnode = h('div', {}, 
  h('ul', {}, [
    h('li', {}, 'I'm a Li'),
    h('li', {}, 'I'm a Li'),
    h('li', {}, 'I'm a Li'),),)console.log(vnode)

Copy the code

<body>
  <div id="container"></div>
  <script src="/virtualdir/bundle.js"></script>
</body>
Copy the code

OK, the h function is fine, it generates the virtual DOM tree, it generates the virtual DOM, we’ll use it later

Let me just briefly describe the process

We all know that js function execution, of course, is the first to execute the innermost function

1. H (‘ li ‘, {}, ‘I am a li’) the first execution returns {sel, data, children, text, elm} three consecutive li is this
2. Then there is h (‘ ul ‘{}, []) into a second judge whether it is an array, and then put each item to determine whether objects and sel attributes, and then added to the children returned inside out {sel, data, children, text, elm}
3. The third is to perform h (‘ div ‘, {}, h ()), the third parameter is h () function directly = {sel, data, children, text, elm}, his children wrapped with []

It is returned to the vnode

5. The patch function

Introduction to the

In snabbDOM, we return a patch function through init(). We compare the two virtual DOM by patch and then add the real DOM tree. The middle comparison is diff we will talk about later

So what’s going on in Patch

Let’s write a simple patch as follows

1.patch

Write a sameVnode first

The key and SEL are used to compare the two virtual DOM

/* sameVnode.js */

/** * Determine whether the two virtual nodes are the same *@param {vnode} Vnode1 Virtual node1 *@param {vnode} Vnode2 Virtual node2 x@returns boolean* /
export default function sameVnode(vnode1, vnode2) {
  return (
    (vnode1.data ? vnode1.data.key : undefined) ===
      (vnode2.data ? vnode2.data.key : undefined) && vnode1.sel === vnode2.sel
  )
}

Copy the code

Write a basic patch

/* patch.js */

/ / import vnode
import vnode from './vnode'


/ / export patch
/ * * * *@param {vnode/DOM} oldVnode
 * @param {vnode} newVnode* /
export default function patch(oldVnode, newVnode) {
  // 1. Check whether oldVnode is a virtual DOM. Check whether sel exists
  if(! oldVnode.sel) {// Convert to the virtual DOM
    oldVnode = emptyNodeAt(oldVnode)
  }
  // Determine whether oldVnode and newVnode are the same virtual node
  // Judge by key and SEL
  if (sameVnode(oldVnode, newVnode)) {
    // The same virtual node calls the methods in patchVNode.js we wrote. }else {
    // If the virtual node is not the same, remove the old node and replace it with a new node. } newVnode.elm = oldVnode.elm// Return newVnode as the old virtual node
  return newVnode
}

/** * Convert to virtual DOM *@param {DOM} Elm DOM node *@returns {object}* /
function emptyNodeAt(elm) {
  // Pass sel and elm into vnode and return
  // Here the main selector is turned to lowercase to return vNode
  // # # # # # # # # #
  // data can also be passed ID and class
  return vnode(elm.tagName.toLowerCase(), undefined.undefined.undefined, elm)
}

Copy the code

Now it is time to deal with the question of whether it is the same virtual node

2.createElm

Let’s start with not the same virtual node

To do that, we’re going to have to write a method to create a node and we’re going to do that in createelm.js

/* createElm.js */

/** * Create element *@param {vnode} Vnode Node to be created */
export default function createElm(vnode) {
  // Select sel from the newly created VNode
  let node = document.createElement(vnode.sel)
  // A child node exists
  // The child node is text
  if( vnode.text ! = =' ' &&
    (vnode.children === undefined || vnode.children.length === 0)) {// Add text directly to node
    node.textContent = vnode.text

    // The child nodes are arrays
  } else if (Array.isArray(vnode.children) && vnode.children.length > 0) {
    let children = vnode.children
    // Go through the group
    for (let i = 0; i < children.length; i++) {
      // Get the child nodes of each array
      let ch = children[i]
      // Create nodes recursively
      let chDom = createElm(ch)
      // Add child nodes to yourself
      node.appendChild(chDom)
    }
  }
  // Update vnode elm
  vnode.elm = node
  / / returns the DOM
  return node
}

Copy the code

The above createElm uses a recursive method to create child nodes, and then we call the method of creating nodes in patch

/* patch.js */

// Import vnode createELm
import vnode from './vnode'
import createElm from './createElm'


/ / export patch
/ * * * *@param {vnode/DOM} oldVnode
 * @param {vnode} newVnode* /
export default function patch(oldVnode, newVnode) {
  // 1. Check whether oldVnode is a virtual DOM. Check whether sel exists
  if(! oldVnode.sel) {// Convert to the virtual DOM
    oldVnode = emptyNodeAt(oldVnode)
  }
  // Determine whether oldVnode and newVnode are the same virtual node
  // Judge by key and SEL
  if (sameVnode(oldVnode, newVnode)) {
    // The same virtual node calls the methods in patchVNode.js we wrote. }else {
    // If the virtual node is not the same, remove the old node and replace it with a new node
    // Here we recursively convert the real DOM node by createElm
    let newNode = createElm(newVnode)
    // The parent node of the old node
    if (oldVnode.elm.parentNode) {
      let parentNode = oldVnode.elm.parentNode
      // Add the node to the real DOM
      parentNode.insertBefore(newNode, oldVnode.elm)
      // Delete the old node
      parentNode.removeChild(oldVnode.elm)
    }
  }
  newVnode.elm = oldVnode.elm
  return newVnode
}
...
}

Copy the code

After recursively adding child nodes, we finally add them to the real DOM in patch and remove the old nodes

I wrote it here to see if the different nodes are actually added

/* index.js */

import h from './my-snabbdom/h'
import patch from './my-snabbdom/patch'


let app = document.querySelector('#app')

let vnode = h('ul', {}, [
  h('li', {}, 'I'm a Li'),
  h('li', {}, [
    h('p', {}, 'I am a P'.),
    h('p', {}, 'I am a P'.),
    h('p', {}, 'I am a P'.),
  ]),
  h('li', {}, 'I'm a Li'),])let oldVnode = patch(app, vnode)

Copy the code

<body>
  <div id="app">hellow</div>
  <script src="/virtualdir/bundle.js"></script>
</body>
Copy the code

Div# app was replaced and successfully replaced

3.patchVnode

Let’s now implement the processing of the same virtual DOM

In patchVnode

All the steps are written according to the previous flowchart. We compare two identical virtual DOM codes in PatchVNode.js

There are several situations when comparing two identical virtual node branches

/* patchVnode.js */

// Import vnode createELm
import createElm from './createElm'

/ * * * *@param {vnode} OldVnode Old virtual node *@param {vnode} NewVnode New virtual node *@returns* /
// Compare the same virtual node
export default function patchVnode(oldVnode, newVnode) {
  // 1. Check whether the objects are the same
  console.log('Same virtual node')
  if (oldVnode === newVnode) return
  // 2. Check whether newVnode has text
  // newVnode does not have children because newVnode has text
  if(newVnode.text && ! newVnode.children) {// Check whether the text is the same
    if(oldVnode.text ! == newVnode.text) {console.log('Different characters')
      // If newVnode is different, give the text in newVnode directly to elm.textContent
      oldVnode.elm.textContent = newVnode.text
    }
  } else {
    // 3. OldVnode has children, newVnode has no text but children
    if(oldVnode.children) { ... So here we have children for both the old node and the new node and we're going to use updateChildren and we're going to do that}else {
      console.log('Old has no children, new has children')
      // oldVnode has no children,newVnode has children
      // At this time oldVnode only has text
      // Clear oldVnode first
      oldVnode.elm.innerHTML = ' '
      // Iterate over the children in newVnode
      let newChildren = newVnode.children
      for (let i = 0; i < newChildren.length; i++) {
        // Get newVnode child node by recursion
        let node = createElm(newChildren[i])
        // Add to oldvNode.elm
        oldVnode.elm.appendChild(node)
      }
    }
  }
}

Copy the code

Following the flowchart coding, it is now time to handle the situation where children exist in both newVnode and oldVnode

Here we’re going to do a refinement comparison which is often called a diff

4.diff

We often hear diff(fine comparison), so let’s take a look at it first

Diff four optimization strategies

In this case, four Pointers are used, starting from 1 to 4 to hit the optimization strategy. If one is hit, the pointer moves (new front and old front move down, new back and old back move up). If none of the four strategies is hit, the next strategy is used

Hit: The SEL and key of the two nodes are the same

Before new and before old
New empress and old empress
New after and old before
Before the new and after the old

So let’s talk about what’s new

All four strategies are executed within a loop

while(old before <= old after && new before <= new after){... }Copy the code

As you can see, the old child node loops through first, which indicates that the new child node needs to add new child nodes

The new before and after nodes are the bytes that need to be added

Delete case 1

In this case, the new child node completes the loop first, indicating that the old child node has nodes that need to be deleted

Delete case 2

When we delete multiple, and none of the four strategies are satisfied, We have to go through the while loop and find the old child and we have to find the new child and we have to find the node and mark it undefined and the virtual node is undefined and actually the DOM has moved it around, and the node between the old before and the old after is the node that we need to remove

Complex case 1

When the fourth policy is triggered, it’s time to move the node, the old backward pointing node (marked undefined in virtual nodes), actually moving the new forward-pointing node in the DOM in front of the old front

Complex case 2

When the third policy is triggered, it is also time to move the node, the old forward-pointing node (marked undefined in virtual nodes), actually moving the new back-pointing node in the DOM behind the old backward node

Note a few points:

h('li',{key:'A'} : "A"})For example, the key here is the unique identification of this node
It exists to tell Diff that they are the same DOM node before and after the change.
Only if it is the same virtual node, do a detailed comparison; otherwise, the old one is forcibly deleted and the new one is inserted
The same virtual node not only has to have the same key but also the same selector as aboveh()Function to create a virtual node objectsel
Only comparisons are made on the same layer, not across layers

5.updateChildren

After reading the above introduction of Diff, I wonder if the illustration I drew is clear. Then let’s continue to complete patchVnode

We’re going to have to write an update dren to do that elaborate comparison

This file is the core of the Diff algorithm, which we use to compare oldVnode and newVnode with children

This is a bit of a twist, so please be patient with the comments, but the process is to follow Diff’s four strategies and deal with the missed cases

/* updateChilren.js */

// Import createElm patchVnode sameVnode
import createElm from './createElm'
import patchVnode from './patchVnode'
import sameVnode from './sameVnode'

/ / export updateChildren
/ * * * *@param {dom} ParentElm Specifies the parent node *@param {array} OldCh Old child node *@param {array} NewCh New child node */
export default function updateChildren(parentElm, oldCh, newCh) {
  Diff: diff: diff: diff: diff: diff: diff: diff: diff: diff: diff: diff
  // Old front and new front
  let oldStartIdx = 0,
    newStartIdx = 0
  let oldEndIdx = oldCh.length - 1 / / after the old
  let newEndIdx = newCh.length - 1 / / new after
  let oldStartVnode = oldCh[0] // The old former node
  let oldEndVnode = oldCh[oldEndIdx] // The old back-end node
  let newStartVnode = newCh[0] // New front node
  let newEndVnode = newCh[newEndIdx] // New post node
  let keyMap = null // For caching
  // Write the loop condition
  while (newStartIdx <= newEndIdx && oldStartIdx <= oldEndIdx) {
    console.log('- enter the diff -)

    // Diff's four policies are written in the following way. PathVnode is called
    // patchVnode and updateChildren call each other, but this is not an endless loop
    // The pointer is not called after the end of the call

    // This is to ignore the fact that we added undefined nodes. These nodes are actually moved
    if (oldCh[oldStartIdx] == undefined) {
      oldStartVnode = oldCh[++oldStartIdx]
    } else if (oldCh[oldEndIdx] == undefined) {
      oldEndVnode = oldCh[--oldEndIdx]
    } else if (newCh[newStartIdx] == undefined) {
      newStartVnode = newCh[++newStartIdx]
    } else if (newCh[newEndIdx] == undefined) {
      newEndVnode = newCh[--newEndIdx]
    }
    // Ignore all of the undefined. Here we judge four diff optimization strategies
    // 1. New front and old front
    else if (sameVnode(oldStartVnode, newStartVnode)) {
      console.log('1 hit')
      // Call patchVnode to compare the object text children of the two nodes
      patchVnode(oldStartVnode, newStartVnode)
      // Move the pointer
      newStartVnode = newCh[++newStartIdx]
      oldStartVnode = oldCh[++oldStartIdx]
    } // 2. New empress and old Empress
    else if (sameVnode(oldEndVnode, newEndVnode)) {
      console.log('2 hit')
      // Call patchVnode to compare the object text children of the two nodes
      patchVnode(oldEndVnode, newEndVnode)
      // Move the pointer
      newEndVnode = newCh[--newEndIdx]
      oldEndVnode = oldCh[--oldEndIdx]
    } // 3. New after and old before
    else if (sameVnode(oldStartVnode, newEndVnode)) {
      console.log('3 hit')
      // Call patchVnode to compare the object text children of the two nodes
      patchVnode(oldStartVnode, newEndVnode)
      // Strategy 3 is to move the old front node to the old back node
      // insertBefore if the reference node is empty, insert to the end as with appendChild
      parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling)
      // Move the pointer
      newEndVnode = newCh[--newEndIdx]
      oldStartVnode = oldCh[++oldStartIdx]
    }
    // 4. New before and old after
    else if (sameVnode(oldEndVnode, newStartVnode)) {
      console.log('4 hit')
      // Call patchVnode to compare the object text children of the two nodes
      patchVnode(oldEndVnode, newStartVnode)
      // Strategy 4 is also required to move nodes
      parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm)
      // Move the pointer
      newStartVnode = newCh[++newStartIdx]
      oldEndVnode = oldCh[--oldEndIdx]
    } else {
      console.log('Diff, all four optimization strategies are dead.')
      // When none of the four strategies hit
      // The keyMap is cached, so you don't have to iterate over the old object every time
      if(! keyMap) {// Initialize keyMap
        keyMap = {}
        // Iterate from oldStartIdx to oldEndIdx
        for (let i = oldStartIdx; i < oldEndIdx; i++) {
          // Take a key for each child object
          const key = oldCh[i].data.key
          // If the key is not undefined, add it to the cache
          if(! key) keyMap[key] = i } }// Determine whether the current item exists in the keyMap. The current item is new before (newStartVnode)
      let idInOld = keyMap[newStartIdx.data]
        ? keyMap[newStartIdx.data.key]
        : undefined

      // If there is a move operation
      if (idInOld) {
        console.log('Mobile node')
        // Fetch the item to be moved from the parent node
        let moveElm = oldCh[idInOld]
        // Call patchVnode for comparison and modification
        patchVnode(moveElm, newStartVnode)
        // Set this item to undefined
        oldCh[idInOld] = undefined
        // To move nodes, use insertBefore for existing nodes
        // Move the old before before, because between the old before and the old after will be deleted
        parentElm.insertBefore(moveElm.elm, oldStartVnode.elm)
      } else {
        console.log('Add new node')
        // Nonexistence is the new item
        // Create the DOM using createElm
        // Also add before the old
        parentElm.insertBefore(createElm(newStartVnode), oldStartVnode.elm)
      }

      // After processing the above add and move we want the new front pointer to continue down
      newStartVnode = newCh[++newStartIdx]
    }
  }
  // We haven't done the add and delete operations yet
  // The first step to complete the add operation is whether there are nodes between the new and new
  if (newStartIdx <= newEndIdx) {
    console.log('Go to Add Remaining Nodes')
    // This is a sign
    // let beforeFlag = oldCh[oldEndIdx + 1] ? oldCh[oldEndIdx + 1].elm : null
    let beforeFlag = newCh[newEndIdx + 1]? newCh[newEndIdx +1] : null
    // New contains the remaining nodes to be added
    for (let i = newStartIdx; i <= newEndIdx; i++) {
      // The child nodes in newCh also need to be converted from the virtual DOM to the DOM
      parentElm.insertBefore(createElm(newCh[i]), beforeFlag)
    }
  } else if (oldStartIdx <= oldEndIdx) {
    console.log('Go to delete redundant nodes')
    // There are still remaining nodes in old, and the nodes between the old and the old need to be deleted
    for (let i = oldStartIdx; i <= oldEndIdx; i++) {
      // Check whether the remaining nodes exist before deleting them
      if (oldCh[i].elm) parentElm.removeChild(oldCh[i].elm)
    }
  }
}

Copy the code

Here we have completed the basic writing. H function creates the virtual DOM, and patch compares the virtual DOM to update the view

6. Let’s test what we’ve written

In fact, when you write code, you are constantly debugging… Now just test a few

Code 1.

html

<body>
  <button class="btn">Strategy 3</button>
  <button class="btn">complex</button>
  <button class="btn">delete</button>
  <button class="btn">complex</button>
  <button class="btn">complex</button>
  <ul id="app">
    hellow
  </ul>

  <script src="/virtualdir/bundle.js"></script>
</body>
Copy the code

index.js

/* index.js */

import h from './my-snabbdom/h'
import patch from './my-snabbdom/patch'

let app = document.querySelector('#app')

let vnode = h('ul', {}, [
  h('li', { key: 'A' }, 'A'),
  h('li', { key: 'B' }, 'B'),
  h('li', { key: 'C' }, 'C'),
  h('li', { key: 'D' }, 'D'),
  h('li', { key: 'E' }, 'E'),])let oldVnode = patch(app, vnode)

let vnode2 = h('ul', {}, [
  h('li', { key: 'E' }, 'E'),
  h('li', { key: 'D' }, 'D'),
  h('li', { key: 'C' }, 'C'),
  h('li', { key: 'B' }, 'B'),
  h('li', { key: 'A' }, 'A'),])let vnode3 = h('ul', {}, [
  h('li', { key: 'E' }, 'E'),
  h('li', { key: 'D' }, 'D'),
  h('li', { key: 'C' }, 'C'),
  h('li', { key: 'A' }, 'A'),
  h('li', { key: 'B' }, 'B'),
  h('li', { key: 'K' }, 'K'),])let vnode4 = h('ul', {}, [
  h('li', { key: 'A' }, 'A'),
  h('li', { key: 'B' }, 'B'),
  h('li', { key: 'C' }, 'C'),])let vnode5 = h('ul', {}, [
  h('li', { key: 'E' }, 'E'),
  h('li', { key: 'C' }, 'C'),
  h('li', { key: 'V' }, 'V'),])let vnode6 = h('ul', {}, [
  h('li', { key: 'A' }, 'A'),
  h('li', { key: 'B' }, 'B'),
  h('li', { key: 'C' }, 'C'),
  h('li', { key: 'D' }, 'D'),
  h(
    'li',
    { key: 'E' },
    h('ul', {}, [
      h('li', { key: 'A' }, 'A'),
      h('li', { key: 'B' }, 'B'),
      h('li', { key: 'C' }, 'C'),
      h('li', { key: 'D' }, 'D'),
      h('li', { key: 'E' }, h('div', { key: 'R' }, 'R')))),]])let vnodeList = [vnode2, vnode3, vnode4, vnode5, vnode6]
let btn = document.querySelectorAll('.btn')
for (let i = 0; i < btn.length; i++) {
  btn[i].onclick = () = > {
    patch(vnode, vnodeList[i])
  }
}
Copy the code

2. Demonstrate

Strategy 3

complex

delete

complex

Complex (here is simple..)

7. Conclusion

I have written all the notes oh, you can check the picture I draw above is not clear, you can repeatedly look patiently ha

If you don’t feel much at all, you can write it yourself, and I’ll post all the code, okay

The code is also on Github

Complete code:

h.js

/* h.js */

/ / import vnode
import vnode from './vnode'

// Export the h method
// Here is the implementation of simple 3 parameters parameter write dead
/ * * * *@param {string} a sel
 * @param {object} b data
 * @param {any} C is the child node can be text, array */
export default function h(a, b, c) {
  // Check whether there are three parameters
  if (arguments.length < 3) throw new Error('Please check the number of parameters')
  // The third parameter has uncertainty to judge
  // 1. The third parameter is the text node
  if (typeof c === 'string' || typeof c === 'number') {
    // Call vnode and pass text in
    / / the return value {sel, data, children, text, elm} back out again
    return vnode(a, b, undefined, c, undefined)}// 2. The third argument is the array [h(),h()] [h(),text]
  else if (Array.isArray(c)) {
    // However, the array must contain the h() function
    // children returns results with collection
    let children = []
    // If h() returns a result, add it to chilren
    for (let i = 0; i < c.length; i++) {
      // the return of h() is {} and contains sel
      if(! (typeof c[i] === 'object' && c[i].sel))
        throw new Error('You can only pass h() if the third argument is an array.')
      / / satisfy the conditions for a push [{sel, data, and the children, text, elm}, {sel, data, children, text, elm}]
      children.push(c[i])
    }
    / / call vnode return {sel, data, children, text, elm} back again
    return vnode(a, b, children, undefined.undefined)}/ / 3. The third parameter is directly () function returns the {sel, data, children, text, elm}
  else if (typeof c === 'object' && c.sel) {
    / / this time at the time of using h () c = {sel, data, children, text, elm} directly into the children
    let children = [c]
    / / call vnode return {sel, data, children, text, elm} back again
    return vnode(a, b, children, undefined.undefined)}}Copy the code

patch.js

/* patch.js */

// Import vnode createELm patchVnode samevNode.js
import vnode from './vnode'
import createElm from './createElm'
import patchVnode from './patchVnode'
import sameVnode from './sameVnode'

/ / export patch
/ * * * *@param {vnode/DOM} oldVnode
 * @param {vnode} newVnode* /
export default function patch(oldVnode, newVnode) {
  // 1. Check whether oldVnode is a virtual DOM. Check whether sel exists
  if(! oldVnode.sel) {// Convert to the virtual DOM
    oldVnode = emptyNodeAt(oldVnode)
  }
  // Determine whether oldVnode and newVnode are the same virtual node
  // Judge by key and SEL
  if (sameVnode(oldVnode, newVnode)) {
    // The same virtual node calls the methods in patchVNode.js we wrote
    patchVnode(oldVnode, newVnode)
  } else {
    // If the virtual node is not the same, remove the old node and replace it with a new node
    // Here we recursively convert the real DOM node by createElm
    let newNode = createElm(newVnode)
    // The parent node of the old node
    if (oldVnode.elm.parentNode) {
      let parentNode = oldVnode.elm.parentNode
      // Add the node to the real DOM
      parentNode.insertBefore(newNode, oldVnode.elm)
      // Delete the old node
      parentNode.removeChild(oldVnode.elm)
    }
  }
  newVnode.elm = oldVnode.elm
  // console.log(newVnode.elm)

  // Return newVnode as the old virtual node
  return newVnode
}

/** * Convert to virtual DOM *@param {DOM} Elm DOM node *@returns {object}* /
function emptyNodeAt(elm) {
  // Pass sel and elm into vnode and return
  // Here the main selector is turned to lowercase to return vNode
  // # # # # # # # # #
  // data can also be passed ID and class
  return vnode(elm.tagName.toLowerCase(), undefined.undefined.undefined, elm)
}

Copy the code

createElm.js

/* createElm.js */

/** * Create element *@param {vnode} Vnode Node to be created */
export default function createElm(vnode) {
  // Select sel from the newly created VNode
  let node = document.createElement(vnode.sel)
  // A child node exists
  // The child node is text
  if( vnode.text ! = =' ' &&
    (vnode.children === undefined || vnode.children.length === 0)) {// Add text directly to node
    node.textContent = vnode.text
    // The child nodes are arrays
  } else if (Array.isArray(vnode.children) && vnode.children.length > 0) {
    let children = vnode.children
    // Go through the group
    for (let i = 0; i < children.length; i++) {
      // Get the child nodes of each array
      let ch = children[i]
      // Create nodes recursively
      let chDom = createElm(ch)
      // Add child nodes to yourself
      node.appendChild(chDom)
    }
  }
  // Update vnode elm
  vnode.elm = node
  / / returns the DOM
  return node
}

Copy the code

vnode.js

/* vnode.js */

/** * returns the passed arguments as objects@param {string} Sel selector *@param {object} The data data *@param {array} Children Child node *@param {string} The text text *@param {dom} elm DOM
 * @returns* /
export default function (sel, data, children, text, elm) {
  return { sel, data, children, text, elm }
}

Copy the code

patchVnode.js

/* patchVnode.js */

// Import vNode createELm patchVnode updateChildren
import createElm from './createElm'
import updateChildren from './updateChildren'
/ * * * *@param {vnode} OldVnode Old virtual node *@param {vnode} NewVnode New virtual node *@returns* /
// Compare the same virtual node
export default function patchVnode(oldVnode, newVnode) {
  // 1. Check whether the objects are the same
  // console.log(' same virtual node ')
  if (oldVnode === newVnode) return
  // 2. Check whether newVnode has text
  // newVnode does not have children because newVnode has text
  if(newVnode.text && ! newVnode.children) {// Check whether the text is the same
    if(oldVnode.text ! == newVnode.text) {console.log('Different characters')
      // If newVnode is different, give the text in newVnode directly to elm.textContent
      oldVnode.elm.textContent = newVnode.text
    }
  } else {
    // 3. OldVnode has children, newVnode has no text but children
    if (oldVnode.children) {
      updateChildren(oldVnode.elm, oldVnode.children, newVnode.children)
    } else {
      console.log('Old has no children, new has children')
      // oldVnode has no children,newVnode has children
      // At this time oldVnode only has text
      // Clear oldVnode first
      oldVnode.elm.innerHTML = ' '
      // Iterate over the children in newVnode
      let newChildren = newVnode.children
      for (let i = 0; i < newChildren.length; i++) {
        // Get newVnode child node by recursion
        let node = createElm(newChildren[i])
        // Add to oldvNode.elm
        oldVnode.elm.appendChild(node)
      }
    }
  }
}

Copy the code

sameVnode.js

/* sameVnode.js */

/** * Determine whether the two virtual nodes are the same *@param {vnode} Vnode1 Virtual node1 *@param {vnode} Vnode2 Virtual node2 x@returns boolean* /
export default function sameVnode(vnode1, vnode2) {
  return (
    (vnode1.data ? vnode1.data.key : undefined) ===
      (vnode2.data ? vnode2.data.key : undefined) && vnode1.sel === vnode2.sel
  )
}

Copy the code

updateChildren.js

/* updateChilren.js */

// Import createElm patchVnode sameVnode
import createElm from './createElm'
import patchVnode from './patchVnode'
import sameVnode from './sameVnode'

/ / export updateChildren
/ * * * *@param {dom} ParentElm Specifies the parent node *@param {array} OldCh Old child node *@param {array} NewCh New child node */
export default function updateChildren(parentElm, oldCh, newCh) {
  Diff: diff: diff: diff: diff: diff: diff: diff: diff: diff: diff: diff
  // Old front and new front
  let oldStartIdx = 0,
    newStartIdx = 0
  let oldEndIdx = oldCh.length - 1 / / after the old
  let newEndIdx = newCh.length - 1 / / new after
  let oldStartVnode = oldCh[0] // The old former node
  let oldEndVnode = oldCh[oldEndIdx] // The old back-end node
  let newStartVnode = newCh[0] // New front node
  let newEndVnode = newCh[newEndIdx] // New post node
  let keyMap = null // For caching
  // Write the loop condition
  while (newStartIdx <= newEndIdx && oldStartIdx <= oldEndIdx) {
    console.log('- enter the diff -)

    // Diff's four policies are written in the following way. PathVnode is called
    // patchVnode and updateChildren call each other, but this is not an endless loop
    // The pointer is not called after the end of the call

    // This is to ignore the fact that we added undefined nodes. These nodes are actually moved
    if (oldCh[oldStartIdx] == undefined) {
      oldStartVnode = oldCh[++oldStartIdx]
    } else if (oldCh[oldEndIdx] == undefined) {
      oldEndVnode = oldCh[--oldEndIdx]
    } else if (newCh[newStartIdx] == undefined) {
      newStartVnode = newCh[++newStartIdx]
    } else if (newCh[newEndIdx] == undefined) {
      newEndVnode = newCh[--newEndIdx]
    }
    // Ignore all of the undefined. Here we judge four diff optimization strategies
    // 1. New front and old front
    else if (sameVnode(oldStartVnode, newStartVnode)) {
      console.log('1 hit')
      // Call patchVnode to compare the object text children of the two nodes
      patchVnode(oldStartVnode, newStartVnode)
      // Move the pointer
      newStartVnode = newCh[++newStartIdx]
      oldStartVnode = oldCh[++oldStartIdx]
    } // 2. New empress and old Empress
    else if (sameVnode(oldEndVnode, newEndVnode)) {
      console.log('2 hit')
      // Call patchVnode to compare the object text children of the two nodes
      patchVnode(oldEndVnode, newEndVnode)
      // Move the pointer
      newEndVnode = newCh[--newEndIdx]
      oldEndVnode = oldCh[--oldEndIdx]
    } // 3. New after and old before
    else if (sameVnode(oldStartVnode, newEndVnode)) {
      console.log('3 hit')
      // Call patchVnode to compare the object text children of the two nodes
      patchVnode(oldStartVnode, newEndVnode)
      // Strategy 3 is to move the old front node to the old back node
      // insertBefore if the reference node is empty, insert to the end as with appendChild
      parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling)
      // Move the pointer
      newEndVnode = newCh[--newEndIdx]
      oldStartVnode = oldCh[++oldStartIdx]
    }
    // 4. New before and old after
    else if (sameVnode(oldEndVnode, newStartVnode)) {
      console.log('4 hit')
      // Call patchVnode to compare the object text children of the two nodes
      patchVnode(oldEndVnode, newStartVnode)
      // Strategy 4 is also required to move nodes
      parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm)
      // Move the pointer
      newStartVnode = newCh[++newStartIdx]
      oldEndVnode = oldCh[--oldEndIdx]
    } else {
      console.log('Diff, all four optimization strategies are dead.')
      // When none of the four strategies hit
      // The keyMap is cached, so you don't have to iterate over the old object every time
      if(! keyMap) {// Initialize keyMap
        keyMap = {}
        // Iterate from oldStartIdx to oldEndIdx
        for (let i = oldStartIdx; i < oldEndIdx; i++) {
          // Take a key for each child object
          const key = oldCh[i].data.key
          // If the key is not undefined, add it to the cache
          if(! key) keyMap[key] = i } }// Determine whether the current item exists in the keyMap. The current item is new before (newStartVnode)
      let idInOld = keyMap[newStartIdx.data]
        ? keyMap[newStartIdx.data.key]
        : undefined

      // If there is a move operation
      if (idInOld) {
        console.log('Mobile node')
        // Fetch the item to be moved from the parent node
        let moveElm = oldCh[idInOld]
        // Call patchVnode for comparison and modification
        patchVnode(moveElm, newStartVnode)
        // Set this item to undefined
        oldCh[idInOld] = undefined
        // To move nodes, use insertBefore for existing nodes
        // Move the old before before, because between the old before and the old after will be deleted
        parentElm.insertBefore(moveElm.elm, oldStartVnode.elm)
      } else {
        console.log('Add new node')
        // Nonexistence is the new item
        // Create the DOM using createElm
        // Also add before the old
        parentElm.insertBefore(createElm(newStartVnode), oldStartVnode.elm)
      }

      // After processing the above add and move we want the new front pointer to continue down
      newStartVnode = newCh[++newStartIdx]
    }
  }
  // We haven't done the add and delete operations yet
  // The first step to complete the add operation is whether there are nodes between the new and new
  if (newStartIdx <= newEndIdx) {
    console.log('Go to Add Remaining Nodes')
    // This is a sign
    // let beforeFlag = oldCh[oldEndIdx + 1] ? oldCh[oldEndIdx + 1].elm : null
    let beforeFlag = newCh[newEndIdx + 1]? newCh[newEndIdx +1] : null
    // New contains the remaining nodes to be added
    for (let i = newStartIdx; i <= newEndIdx; i++) {
      // The child nodes in newCh also need to be converted from the virtual DOM to the DOM
      parentElm.insertBefore(createElm(newCh[i]), beforeFlag)
    }
  } else if (oldStartIdx <= oldEndIdx) {
    console.log('Go to delete redundant nodes')
    // There are still remaining nodes in old, and the nodes between the old and the old need to be deleted
    for (let i = oldStartIdx; i <= oldEndIdx; i++) {
      // Check whether the remaining nodes exist before deleting them
      if (oldCh[i].elm) parentElm.removeChild(oldCh[i].elm)
    }
  }
}

Copy the code

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.

From understanding the virtual DOM and implementing the DIff algorithm

Virtual DOM and diff algorithm

1. Introduction

2. Snabbdom is introduced

Snabbdom is simple to use

2. Introduce modules in snABbDOM

3. Virtual DOM example

4. H function

5. The patch function

1.patch

2.createElm

3.patchVnode

4.diff

5.updateChildren

6. Let’s test what we’ve written

Code 1.

2. Demonstrate

7. Conclusion

From understanding the virtual DOM and implementing the DIff algorithm

Virtual DOM and diff algorithm

1. Introduction

2. Snabbdom is introduced

Snabbdom is simple to use

2. Introduce modules in snABbDOM

3. Virtual DOM example

4. H function

5. The patch function

1.patch

2.createElm

3.patchVnode

4.diff

5.updateChildren

6. Let’s test what we’ve written

Code 1.

2. Demonstrate

7. Conclusion

Related Posts

What does FaaS bring to the front end?

The WijmoJS front-end development kit has been updated to include a visual map component

191. Number of bits 1 (bit operation)