Virtual DOM and diff algorithms

Virtual DOM and DIFF algorithms are not new to us. No matter what framework we use in development, they are inseparable from virtual DOM and DIff.

When someone asks you: Do you know about virtual DOM and diff algorithms? I’m sure most of you can tell a little bit about it. But, please ask yourself, do you really know the virtual DOM and diff algorithm?

This sharing will take you to explore the secrets of virtual DOM and diff algorithms. We will demystify the Diff algorithm with code demos and hand-written implementation code. Each line of core code is arranged clearly, from simple to deep, step by step, so that everyone can understand, full of dry goods!

A simple understanding of virtual DOM and diff algorithm

Virtual DOM: Describes the real DOM as a JS object

<div class="box">
  <h3>I'm a headline</h3>
  <ul>
    <li>java</li>
    <li>php</li>
    <li>python</li>
  </ul>
</div>
Copy the code

{
  "sel": "div"."data": { "class": { "box": true}},"children": [{"sel": "h3"."data": {},
      "text": "I am a title."}, {"sel": "ul"."data": {},
      "children": [{"sel": "li"."data": {}, "text": "java" },
        { "sel": "li"."data": {}, "text": "php" },
        { "sel": "li"."data": {}, "text": "python"},],},],};Copy the code

Diff: Minimum update

into

<div class="box">
  <h3>I'm a headline</h3>
  <span>I'm a new SPAN</span>
  <ul>
    <li>java</li>
    <li>php</li>
    <li>python</li>
    <li>javascript</li>
  </ul>
</div>
Copy the code

This scenario often occurs in actual development, so how does the diff algorithm deal with it? However, when it comes to large DOM structures, there are still many performance issues. If you want to put a table in your living room, you can’t tear it down and redecorate it.

When we look at the DOM structure, there is actually one more span, one more Li, and nothing else changes. The core of the DIff algorithm is to carry out fine comparison and achieve the minimum update.

Second, the snabbdom

Snabbdom profile
How does the H function of snabbdom work
Feel the Diff algorithm

2.1 snabbdom profile

Snabbdom is a Swedish word meaning speed.

Snabbdom is a famous virtual DOM library, is the originator of diff algorithm, Vue source code reference snabbDOM

Snabbdom making address

2.1.1 Setting up an SNabbDOM Environment

Snabbdom, webpack, webpack-cli, webpack-dev-server: snabbDOM, webpack, webpack-cli, webpack-dev-server

"dependencies": {
"snabbdom": "^ 3.0.3." "."webpack": "^ 5.48.0"."webpack-cli": "^" 3.3.12."webpack-dev-server": "^ 3.11.2"
}
Copy the code

Create SRC /index.js. 4. Create WWW /index.html

<! DOCTYPEhtml>
<html lang="en">
<head>
  <meta charset="UTF-8" />
  <meta http-equiv="X-UA-Compatible" content="IE=edge" />
  <meta name="viewport" content="Width = device - width, initial - scale = 1.0" />
  <title>Document</title>
</head>
<body>
  <div id="container"></div>
  <script src="xuni/bundle.js"></script>
</body>
</html>
Copy the code

5. Create a webpack. Config. Js

```javascript module.exports = { entry: "./src/index.js", output: { publicPath: "xuni", filename: "bundle.js", }, devServer: { port: 9999, contentBase: "www", }, }; ` ` `Copy the code

Copy the github demo code to index.js

import {
  init,
  classModule,
  propsModule,
  styleModule,
  eventListenersModule,
  h,
} from "snabbdom";

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");

const someFn = () = > {
console.log(1)}const vnode = h("div#container.two.classes", {
  on: {
    click: someFn
  }
}, [
  h("span", {
    style: {
      fontWeight: "bold"}},"This is bold"),
  " and this is just normal text",
  h("a", {
    props: {
      href: "/foo"}},"I'll take you places!"),]);// Patch into empty DOM element -- This modifies the DOM as a side effect
  patch(container, vnode);

const newVnode = h(
  "div#container.two.classes",
  { on: { click: someFn } },
  [
    h(
      "span",
      { style: { fontWeight: "normal".fontStyle: "italic"}},"This is now italic type"
    ),
    " and this is still just normal text",
    h("a", { props: { href: "/bar"}},"I'll take you places!"),]);// Second `patch` invocation
patch(vnode, newVnode); // Snabbdom efficiently updates the old view to the new state
Copy the code

Notice that we need to put thesomeFnLet me define it. If the following information is displayed, the environment is basically set up:

2.2 Virtual DOM and H functions

Virtual DOM

Use JavaScript objects to describe the DOM hierarchy. All properties in the DOM have corresponding properties in the virtual DOM.
Diff happens in the virtual DOM

The new virtual DOM diff with the old virtual DOM, figure out how to minimize updates, and finally reflect the real DOM.
Study 1: How is the virtual DOM generated by rendering functions (h functions)

Handwriting h function.
Study 2: Principles of diff algorithm

Handwriting diff algorithm.
Study 3: How does the virtual DOM diff into the real DOM

The fact that the virtual DOM becomes the real DOM is covered by the diff algorithm.

Note: How the DOM becomes a virtual DOM is a template compilation principle that we won’t discuss here.

2.2.1 h function

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

For example, call h like this:

h('a', {props: { href: 'https://www.baidu.com' }}, 'Google it, you still don't know.')
Copy the code

The resulting virtual node looks like this:He represents real DOM nodes:

<a href='https://www.baidu.com'>Google it, you still don't know</a>
Copy the code

Field Description:

{
  children: undefined./ / child elements
  data: {}, // Attribute styles, etc
  elm: undefined.// There is no corresponding DOM node, there is no tree
  key: undefined.// Unique identifier
  sel: 'div'./ / selector
  text: 'I am a box' / / text
}
Copy the code

The patch function (described below) is used to tree the virtual DOM.

import {
  init,
  classModule,
  propsModule,
  styleModule,
  eventListenersModule,
  h,
} from "snabbdom";

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");

// Create a virtual node
const vnode = h('a', { props: { href: 'https://www.baidu.com'}},'Google it, you still don't know.')

// Put the virtual node on the tree
patch(container, vnode)

console.log(vnode)
Copy the code

H functions can be nested to create a virtual DOM tree.

const vnode = h('ul', {}, [
  h('li', { style: { color: '#f00'}},'java'),
  h('li'.'php'),
  h('li'.'python'),])Copy the code

Original H function TS version of the core code

h.ts

export function h(sel: string) :VNode;
export function h(sel: string, data: VNodeData | null) :VNode;
export function h(sel: string, children: VNodeChildren) :VNode;
export function h(
  sel: string,
  data: VNodeData | null,
  children: VNodeChildren
) :VNode;
export function h(sel: any, b? :any, c? :any) :VNode {
  let data: VNodeData = {};
  let children: any;
  let text: any;
  let i: number;
  if(c ! = =undefined) {
    if(b ! = =null) {
      data = b;
    }
    if (is.array(c)) {
      children = c;
    } else if (is.primitive(c)) {
      text = c;
    } else if(c && c.sel) { children = [c]; }}else if(b ! = =undefined&& b ! = =null) {
    if (is.array(b)) {
      children = b;
    } else if (is.primitive(b)) {
      text = b;
    } else if (b && b.sel) {
      children = [b];
    } else{ data = b; }}if(children ! = =undefined) {
    for (i = 0; i < children.length; ++i) {
      if (is.primitive(children[i]))
        children[i] = vnode(
          undefined.undefined.undefined,
          children[i],
          undefined); }}if (
    sel[0= = ="s" &&
    sel[1= = ="v" &&
    sel[2= = ="g" &&
    (sel.length === 3 || sel[3= = ="." || sel[3= = ="#")
  ) {
    addNS(data, children, sel);
  }
  return vnode(sel, data, children, text, undefined);
}

Copy the code

vnode.ts

export function vnode(
  sel: string | undefined,
  data: any | undefined,
  children: Array<VNode | string> | undefined,
  text: string | undefined,
  elm: Element | Text | undefined
) :VNode {
  const key = data === undefined ? undefined : data.key;
  return { sel, data, children, text, elm, key };
}
Copy the code

From the code in h.ts, h can be used in many ways:

h('div')
h('div'.'words')
h('div', [])
h('div', h())
h('div', {}, 'words')
h('div', {}, [])
h('div', {}, h())
Copy the code

Next to the handwriting h function link, we only realize the castrated version of h function here, only to achieve the case of 3 parameters, because the original code is to a, B, C three parameters assigned.

Handwritten h function

Look at the original TS code, copy JS code. Because we’re not focusing on TS today.

Just stick to the trunk functionality, drop the implementation details, and make sure everyone understands how the core is implemented.

vnode.js

// Very simple, just pass the parameters together to return the composite object
export default function (sel, data, children, text, elm) {
  const key = data === undefined ? undefined : data.key;
  return {
    sel, data, children, text, elm, key
  }
}
Copy the code

h.js

import vnode from './vnode.js'

export default function (sel, data, c) {
  if (arguments.length ! = =3) {
    throw new Error('Sorry, we are an emasculated version of the H function that only implements the case with 3 arguments, QAQ')}if (typeof c === 'string' || typeof c === 'number') {
    return vnode(sel, data, undefined, c, undefined)}else if (Array.isArray(c)) {
    const children = []
    for (let i = 0; i < c.length; i++) {
      // Check that c[I] is an object
      if(! (typeof c[i] === 'object' && c[i].hasOwnProperty('sel'))) {
        throw new Error('There are items in the array parameters that are not h functions')
      }
      children.push(c[i])
    }
    return vnode(sel, data, children, undefined.undefined)}else if (typeof c === 'object' && c.hasOwnProperty('sel')) {
    const children = [c]
    return vnode(sel, data, children, undefined.undefined)}throw new Error('Sorry, wrong parameter')}Copy the code

Thus, we have implemented a castrated version of the h function, directly to the example:

import h from "./mysnabbdom/h.js";

const vnode = h('div', {}, [
  h('h2', {}, 'I am a title'),
  h('div', {}, h('p', {}, 'I'm a P')),
  h('ul', {}, [
    h('li', {}, 'java'),
    h('li', {}, 'php'),
    h('li', {}, 'python'),]])console.log(vnode)
Copy the code

Down, down, down

Perfect finish!

2.3 Feel the DIff algorithm

All about diff. So what did Diff do? Through this chapter (examples and demonstrations), you will have a better understanding of the Diff algorithm and what it does. Here’s an example:

const container = document.getElementById("container");
const btn = document.getElementById("btn");

const vnode1 = h('ul', {}, [
  h('li', {}, 'A'),
  h('li', {}, 'B'),
  h('li', {}, 'C'),
  h('li', {}, 'D'),
])

patch(container, vnode1)

// Change vnode1 to vnode2 when the button is clicked
btn.onclick = function () {
  const vnode2 = h('ul', {}, [
    h('li', {}, 'A'),
    h('li', {}, 'B'),
    h('li', {}, 'C'),
    h('li', {}, 'D'),
    h('li', {}, 'E'),
  ])
  patch(vnode1, vnode2)
}
Copy the code

Effect:

We successfully replaced vnode1 with vnode2. So what’s going on inside the Diff algorithm? Given what we already know, Diff should know that ABCD doesn’t change, so is that true? How do you verify that? Take a look at the graph below:

Obviously, we changed li’s text manually, and when we clicked the button, the text didn’t change (it didn’t change to ABCD), so Diff knew ABCD didn’t change, so he reused and kept them. Diff is the minimum number of updates.

So, is Diff really that smart? Look at the following example:

const container = document.getElementById("container");
const btn = document.getElementById("btn");

const vnode1 = h('ul', {}, [
  h('li', {}, 'A'),
  h('li', {}, 'B'),
  h('li', {}, 'C'),
  h('li', {}, 'D'),
])

patch(container, vnode1)

// Change vnode1 to vnode2 when the button is clicked
btn.onclick = function () {
  const vnode2 = h('ul', {}, [
    h('li', {}, 'E'),
    h('li', {}, 'A'),
    h('li', {}, 'B'),
    h('li', {}, 'C'),
    h('li', {}, 'D'),
  ])
  patch(vnode1, vnode2)
}
Copy the code

Let’s put an E in front and see what happens.

Like… Nothing wrong with it. So the question is, does diff insert the E in front of it, or does diff insert a node after it and replace the text in turn? A=>E B=>A C=>B D=>C “=>E

Not to keep you in suspense, let’s do it the same way:

We see that E is not inserted in front, so it’s not that smart. But is Diff really that stupid? Let’s continue with the following example:

const vnode1 = h('ul', {}, [
  h('li', { key: 'A' }, 'A'),
  h('li', { key: 'B' }, 'B'),
  h('li', { key: 'C' }, 'C'),
  h('li', { key: 'D' }, 'D'),
])

patch(container, vnode1)

// Change vnode1 to vnode2 when the button is clicked
btn.onclick = function () {
  const vnode2 = h('ul', {}, [
    h('li', { key: 'E' }, 'E'),
    h('li', { key: 'A' }, 'A'),
    h('li', { key: 'B' }, 'B'),
    h('li', { key: 'C' }, 'C'),
    h('li', { key: 'D' }, 'D'),
  ])
  patch(vnode1, vnode2)
}
Copy the code

We added a key, and when you saw that, something clicked in your head. The picture above!

It’s intuitive to see that after adding key, Diff actually inserts E in front of it. Because we told Diff that A is A, B is B… The purpose of the key is to serve the minimum number of updates, which is why the list must have a key when we write the project.

Here’s another example:

const vnode1 = h('ul', {}, [
  h('li', { key: 'A' }, 'A'),
  h('li', { key: 'B' }, 'B'),
  h('li', { key: 'C' }, 'C'),
  h('li', { key: 'D' }, 'D'),
])

patch(container, vnode1)

// Change vnode1 to vnode2 when the button is clicked
btn.onclick = function () {
  const vnode2 = h('ol', {}, [
    h('li', { key: 'A' }, 'A'),
    h('li', { key: 'B' }, 'B'),
    h('li', { key: 'C' }, 'C'),
    h('li', { key: 'D' }, 'D'),
  ])
  patch(vnode1, vnode2)
}
Copy the code

We added a key, and when you saw that, something clicked in your head. The picture above!

We’ve replaced ul with OL, and the whole DOM has been replaced.

One last example:

const vnode1 = h('div', {}, [
  h('p', { key: 'A' }, 'A'),
  h('p', { key: 'B' }, 'B'),
  h('p', { key: 'C' }, 'C'),
  h('p', { key: 'D' }, 'D'),
])

patch(container, vnode1)

// Change vnode1 to vnode2 when the button is clicked
btn.onclick = function () {
  const vnode2 = h('div', {}, h('div', {}, [
    h('p', { key: 'A' }, 'A'),
    h('p', { key: 'B' }, 'B'),
    h('p', { key: 'C' }, 'C'),
    h('p', { key: 'D' }, 'D'),
  ]))
  patch(vnode1, vnode2)
}
Copy the code

Results: 1, the minimum update is really too powerful, really is the minimum update! Of course, key is important. The key is the unique identifier of the node, telling the Diff algorithm that they are using a DOM node before and after the change. 2. Fine comparison is performed only when the same virtual node is used. Otherwise, it is violence to delete the old and insert the new. How to define the same virtual node: Same selectors and same keys. 3. Only same-layer comparison, not cross-layer comparison. Even if it is the same piece of virtual node, but across layers, sorry, finer comparison does not diff you, but deletes the old and inserts the new violently.

Diff isn’t that awesome, you may ask. But does it really affect efficiency? A: This is a reasonable optimization mechanism because you will not encounter any of these operations in real development. You don’t write code like this in development:

<ul v-if='flag'>
   <li>A</li>
   <li>B</li>
   <li>C</li>
</ul>
<ol v-else>
   <li>A</li>
   <li>B</li>
   <li>C</li>
</ol>

<div>
   <div v-if='flag'>
      <p></p>
      <p></p>
      <p></p>
   </div>
   <p v-if='! flag'></p>
   <p v-if='! flag'></p>
   <p v-if='! flag'></p>
</div>
Copy the code

Although this chapter is just a taste of the Diff algorithm, I’m sure you will learn something

Write diff by hand

Let’s take a quick look at the source code before we write it. From the original demo, we can see that the init method is called to return the patch function.

import {
  init,
  classModule,
  propsModule,
  styleModule,
  eventListenersModule,
  h,
} from "snabbdom";

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
]);
Copy the code

Init. ts source code screenshot

Patch method

return function patch(oldVnode: VNode | Element, vnode: VNode) :VNode {
    let i: number.elm: Node, parent: Node;
    const insertedVnodeQueue: VNodeQueue = [];/ / don't have to see
    for (i = 0; i < cbs.pre.length; ++i) cbs.pre[i]();/ / don't have to see

    if(! isVnode(oldVnode)) { oldVnode = emptyNodeAt(oldVnode); }if (sameVnode(oldVnode, vnode)) {
      patchVnode(oldVnode, vnode, insertedVnodeQueue);
    } else{ elm = oldVnode.elm! ; parent = api.parentNode(elm)as Node;

      createElm(vnode, insertedVnodeQueue);

      if(parent ! = =null) { api.insertBefore(parent, vnode.elm! , api.nextSibling(elm)); removeVnodes(parent, [oldVnode],0.0); }}for (i = 0; i < insertedVnodeQueue.length; ++i) { insertedVnodeQueue[i].data! .hook! .insert! (insertedVnodeQueue[i]);/ / don't have to see
    }
    for (i = 0; i < cbs.post.length; ++i) cbs.post[i]();/ / don't have to see
    return vnode;
  };
Copy the code

Looking at the source code of patch method, we can know the simple process:

3.1 Creating the Patch Function

import vnode from './vnode.js'
import api from './htmldomapi.js'

// Is not a virtual node
function isVnode(vnode) {
  return vnode.sel === ' '|| vnode.sel ! = =undefined;
}

// Wrap the oldVnode as a virtual node
function emptyNodeAt(elm) {
  return vnode(
    api.tagName(elm).toLowerCase(),
    {},
    [],
    undefined,
    elm
  );
}

// Is it the same virtual node
function sameVnode(vnode1, vnode2) {
  return vnode1.sel === vnode2.sel && vnode1.key === vnode2.key
}

export default function patch(oldVnode, newVnode) {
  // Check whether it is a virtual node
  if(! isVnode(oldVnode)) {// If it is not a virtual node, wrap it as a virtual node
    oldVnode = emptyNodeAt(oldVnode)
  }

  if (sameVnode(oldVnode, newVnode)) {
    // Fine comparison
  } else {
    // Forcibly insert new, delete old}}Copy the code

Where, inside the vNode is defined before the Vnode function, API is the DOM operation API, here will not put the code, you should be able to understand. Now that we have implemented some of the functions in the above flowchart, we come to the first difficult part, which is to insert the new and delete the old.

3.2 the createElement method function

Let’s consider the simplest case, where the third argument to h is text.

import h from './mysnabbdom/h'
import patch from './mysnabbdom/patch'

const container = document.getElementById("container");

const vnode1 = h('h1', {}, 'hello')

patch(container, vnode1)
Copy the code

// Actually create the node, create the VNode as a DOM, and insert it before the pivot element
function createElement(vnode, pivot) {
  // Create a DOM node
  let domNode = document.createElement(vnode.sel)
  // Have child nodes or text
  if(vnode.text ! = =' ' && (vnode.children === undefined || vnode.children.length === 0)) {
    // Inside it is text
    domNode.innerText = vnode.text
    // Call insertBefore on pivot's parent element to insert the new node domNode before pivot
    pivot.parentNode.insertBefore(domNode, pivot)
  }
}

export default function patch(oldVnode, newVnode) {
  // Check whether it is a virtual node
  if(! isVnode(oldVnode)) {// If it is not a virtual node, wrap it as a virtual node
    oldVnode = emptyNodeAt(oldVnode)
  }

  if (sameVnode(oldVnode, newVnode)) {
    // Fine comparison
  } else {
    // Forcibly insert new, delete old
    createElement(newVnode, oldVnode.elm)
  }

}
Copy the code

The page has successfully displayed Hello. We finished our first climb up the tree.

Let’s consider the case where the third argument to h is an array.

const vnode1 = h('ul', {}, [
  h('li', {}, 'A'),
  h('li', {}, 'B'),
  h('li', {}, 'C'),
  h('li', {}, 'D'),
])

patch(container, vnode1)
Copy the code

Since there are many children, we need to recursively create the node, and we need to recurse with an end condition, which is when the third argument to h is text. We don’t pass the second parameter createElement. We create the node using createElement. We don’t insert the node.

function createElement(vnode) {
  // Create a DOM node
  let domNode = document.createElement(vnode.sel)
  // Have child nodes or text
  if(vnode.text ! = =' ' && (vnode.children === undefined || vnode.children.length === 0)) {
    // Inside it is text
    domNode.innerText = vnode.text
    // Add the elm attribute
    vnode.elm = domNode
  } else if (Array.isArray(vnode.children) && vnode.children.length > 0) {
    // Create nodes recursively
  }
  // Return the elm pure DOM object
  return vnode.elm
}
Copy the code

In the meantime, we’ll modify the first simple example above:

function patch(oldVnode, newVnode) {
  // Check whether it is a virtual node
  if(! isVnode(oldVnode)) {// If it is not a virtual node, wrap it as a virtual node
    oldVnode = emptyNodeAt(oldVnode)
  }

  if (sameVnode(oldVnode, newVnode)) {
    // Fine comparison
  } else {
    // Forcibly insert new, delete old
    let newVnodeElm = createElement(newVnode)
    oldVnode.elm.parentNode.insertBefore(newVnodeElm, oldVnode.elm)
  }

}
Copy the code

We successfully displayed hello on the page.

The purpose of this modification is to make createElement do nothing but create nodes for subsequent recursion. So, we can start writing recursions.

import vnode from './vnode.js'
import api from './htmldomapi.js'

// Is not a virtual node
function isVnode(vnode) {
  return vnode.sel === ' '|| vnode.sel ! = =undefined;
}

// Wrap the oldVnode as a virtual node
function emptyNodeAt(elm) {
  return vnode(
    api.tagName(elm).toLowerCase(),
    {},
    [],
    undefined,
    elm
  );
}

// Is it the same virtual node
function sameVnode(vnode1, vnode2) {
  return vnode1.key === vnode2.key && vnode1.sel === vnode2.sel
}

// Actually create the node, create vNode as DOM without inserting
function createElement(vnode) {
  // Create a DOM node
  let domNode = document.createElement(vnode.sel)
  // Have child nodes or text
  if(vnode.text ! = =' ' && (vnode.children === undefined || vnode.children.length === 0)) {
    // Inside it is text
    domNode.innerText = vnode.text
  } else if (Array.isArray(vnode.children) && vnode.children.length > 0) {
    // Create nodes recursively
    for (let i = 0; i < vnode.children.length; i++) {
      // Get the current children
      let ch = vnode.children[i]
      Call createElement means that the DOM is created, and its ELM attribute points to the created DOM, but not yet on the tree
      let chDom = createElement(ch)
      / / on the tree
      domNode.appendChild(chDom)
    }
  }
  // Add the elm attribute
  vnode.elm = domNode
  // Return the elm pure DOM object
  return vnode.elm
}

export default function patch(oldVnode, newVnode) {
  // Check whether it is a virtual node
  if(! isVnode(oldVnode)) {// If it is not a virtual node, wrap it as a virtual node
    oldVnode = emptyNodeAt(oldVnode)
  }

  if (sameVnode(oldVnode, newVnode)) {
    // Fine comparison
  } else {
    // Forcibly insert new, delete old
    let newVnodeElm = createElement(newVnode)

    if (oldVnode.elm.parentNode && newVnodeElm) {
      oldVnode.elm.parentNode.insertBefore(newVnodeElm, oldVnode.elm)
    }
  }
}
Copy the code

Page displayed successfully:

Example 2:

const vnode1 = h('ul', {}, [
  h('li', {}, 'A'),
  h('li', {}, 'B'),
  h('li', {}, 'C'),
  h('li', {}, [
    h('div', {},'DD1'),
    h('div', {},'DD2'),
    h('div', {},'DD3'),
  ]),
])

patch(container, vnode1)
Copy the code

So now we’re done with our recursion.

Oh, by the way, we haven’t removed the old node yet, just add one line of code.

if (oldVnode.elm.parentNode && newVnodeElm) {
   oldVnode.elm.parentNode.insertBefore(newVnodeElm, oldVnode.elm)
   // Delete the old node
   oldVnode.elm.parentNode.removeChild(oldVnode.elm)
}
Copy the code

Let’s add the button and change the DOM:

import h from './mysnabbdom/h'
import patch from './mysnabbdom/patch'

const container = document.getElementById("container");
const btn = document.getElementById("btn");

const vnode1 = h('ul', {}, [
  h('li', {}, 'A'),
  h('li', {}, 'B'),
  h('li', {}, 'C'),
])

patch(container, vnode1)

btn.onclick = function () {
  const vnode2 = h('ol', {}, [
    h('li', {}, 'AA'),
    h('li', {}, 'BB'),
    h('li', {}, 'CC'),
  ])

  patch(vnode1, vnode2)
}
Copy the code

Over.

3.3 DIff Process when the old and new nodes are the same node

First, the flow chart:

3.3.1 newVnode Has Text

if (sameVnode(oldVnode, newVnode)) {
    // It is the same object in memory
    if (oldVnode === newVnode) return
    if(newVnode.text ! = =undefined && (newVnode.children === undefined || newVnode.children.length === 0)) {
      // The new vNode has a text attribute
      if(newVnode.text ! == oldVnode.text) { oldVnode.elm.innerText = newVnode.text } }else {
      // The new vNode has no text attribute}}Copy the code

We have implemented the newVnode with text. The following two pieces of code can implement the effect.

/ / the first paragraph
const vnode1 = h('h2', {}, 'hh')

patch(container, vnode1)

btn.onclick = function () {
  const vnode2 = h('h2', {}, 'xx')
  patch(vnode1, vnode2)
}

/ / the second paragraph
const vnode1 = h('h2', {}, [
  h('p', {}, 'A'),
  h('p', {}, 'B'),
  h('p', {}, 'C'),
])

patch(container, vnode1)

btn.onclick = function () {
  const vnode2 = h('h2', {}, 'xx')
  patch(vnode1, vnode2)
}
Copy the code

3.3.2 newVnode Without Text (With children)

1. OldVnode has no children

if (sameVnode(oldVnode, newVnode)) {
    // It is the same object in memory
    if (oldVnode === newVnode) return
    if(newVnode.text ! = =undefined && (newVnode.children === undefined || newVnode.children.length === 0)) {
      // The new vNode has a text attribute
      if(newVnode.text ! == oldVnode.text) { oldVnode.elm.innerText = newVnode.text } }else {
      // The new vNode has no text attribute
      if(oldVnode.children ! = =undefined && oldVnode.children.length > 0) {
        // There are many children in my family
        // The most complicated case
      } else {
        The old one has no children. The new one has children
        // Step 1: Clear the contents of the old node
        oldVnode.elm.innerText = ' '
        // Step 2: create a tree on the DOM by traversing the new vNode child nodes
        for (let i = 0; i < newVnode.children.length; i++) {
          const dom = createElement(newVnode.children[i])
          oldVnode.elm.appendChild(dom)
        }
      }
    }
}
Copy the code

Effect:

const vnode1 = h('h2', {}, 'hh')

patch(container, vnode1)

btn.onclick = function () {
  const vnode2 = h('h2', {}, [
    h('p', {}, 'A'),
    h('p', {}, 'B'),
    h('p', {}, 'C')
  ])
  patch(vnode1, vnode2)
}
Copy the code

OldVnode has children

This is the core of the Diff algorithm. In order to facilitate subsequent operations, we first separate out the above code and add the patchVnode method:

function patchVnode(oldVnode, newVnode) {
  // It is the same object in memory
  if (oldVnode === newVnode) return
  if(newVnode.text ! = =undefined && (newVnode.children === undefined || newVnode.children.length === 0)) {
    // The new vNode has a text attribute
    if(newVnode.text ! == oldVnode.text) { oldVnode.elm.innerText = newVnode.text } }else {
    // The new vNode has no text attribute
    if(oldVnode.children ! = =undefined && oldVnode.children.length > 0) {
      // There are many children in my family
      // The most complicated case
    } else {
      The old one has no children. The new one has children
      // Step 1: Clear the contents of the old node
      oldVnode.elm.innerText = ' '
      // Step 2: facilitate the creation of a DOM tree on the new vNode child node
      for (let i = 0; i < newVnode.children.length; i++) {
        let dom = createElement(newVnode.children[i])
        oldVnode.elm.appendChild(dom)
      }
    }
  }
}

export default function patch(oldVnode, newVnode) {
  // Check whether it is a virtual node
  if(! isVnode(oldVnode)) {// If it is not a virtual node, wrap it as a virtual node
    oldVnode = emptyNodeAt(oldVnode)
  }
  if (sameVnode(oldVnode, newVnode)) {
    patchVnode(oldVnode, newVnode)
  } else {
    // Forcibly insert new, delete old
    let newVnodeElm = createElement(newVnode)
    if (oldVnode.elm.parentNode && newVnodeElm) {
      oldVnode.elm.parentNode.insertBefore(newVnodeElm, oldVnode.elm)
      // Delete the old node
      oldVnode.elm.parentNode.removeChild(oldVnode.elm)
    }
  }
}
Copy the code

3.3.3 Analyzing diFF algorithm updating child Node Operations (Important)

Diff provides four matching lookups (four Pointers) : 1, the new before and the old before 2, the new after and the old after 3, the new after and the old before (involving the mobile node, the node pointing to the new after, move to the old after) 4, the new before and the old after (involving the mobile node, the node pointing to the new before, move to the old before) hit judgment from top to bottom, hit a judgment will not hit again. If none of them hit, loop around.

1. If newStart and oldStart match 1, the pointer will be moved after patch, newStart++, oldStart++

Added the updateChildren method.

function updateChildren(parentElm, oldCh, newCh) {
  let oldStartIdx = 0 / / the old before
  let newStartIdx = 0 / / new front
  let oldEndIdx = oldCh.length - 1 / / after the old
  let newEndIdx = newCh.length - 1 / / new after
  let oldStartVnode = oldCh[0] // Old former node
  let oldEndVnode = oldCh[oldEndIdx] // Old back node
  let newStartVnode = newCh[0] // New front node
  let newEndVnode = newCh[newEndIdx] // New post-node
}

function patchVnode(oldVnode, newVnode) {
  // It is the same object in memory
  if (oldVnode === newVnode) return
  if(newVnode.text ! = =undefined && (newVnode.children === undefined || newVnode.children.length === 0)) {
    // The new vNode has a text attribute
    if(newVnode.text ! == oldVnode.text) { oldVnode.elm.innerText = newVnode.text } }else {
    // The new vNode has no text attribute
    if(oldVnode.children ! = =undefined && oldVnode.children.length > 0) {
      // There are many children in my family
      // The most complicated case
      updateChildren(oldVnode.elm, oldVnode.children, newVnode.children)
    } else {
      The old one has no children. The new one has children
      // Step 1: Clear the contents of the old node
      oldVnode.elm.innerText = ' '
      // Step 2: facilitate the creation of a DOM tree on the new vNode child node
      for (let i = 0; i < newVnode.children.length; i++) {
        let dom = createElement(newVnode.children[i])
        oldVnode.elm.appendChild(dom)
      }
    }
  }
}
Copy the code

Start a loop:

function updateChildren(parentElm, oldCh, newCh) {
  let oldStartIdx = 0 / / the old before
  let newStartIdx = 0 / / new front
  let oldEndIdx = oldCh.length - 1 / / after the old
  let newEndIdx = newCh.length - 1 / / new after
  let oldStartVnode = oldCh[0] // Old former node
  let oldEndVnode = oldCh[oldEndIdx] // Old back node
  let newStartVnode = newCh[0] // New front node
  let newEndVnode = newCh[newEndIdx] // New post-node
  
  // Start the loop
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    if (sameVnode(oldStartVnode, newStartVnode)) {
      patchVnode(oldStartVnode, newStartVnode)
      // Move the pointer
      oldStartVnode = oldCh(++oldStartIdx)
      newStartVnode = newCh(++newStartIdx)
    }
  }
}
Copy the code

If not, move on to the next situation.

2. If newEnd and oldEnd hit 1, the pointer is moved after patch, newEnd–, oldEnd–

if (sameVnode(newEndVnode, oldEndVnode)) { // New queen and old queen
    patchVnode(oldEndVnode, newEndVnode)
    // Move the pointer
    oldEndVnode = oldCh[--oldEndIdx]
    newEndVnode = newCh[--newEndIdx]
}
Copy the code

If not, move on to the next situation.

If 3 is matched, move the node pointed to after oldEnd, oldStart++, newEnd–

if (sameVnode(newEndVnode, oldStartVnode)) { // The new and the old
    patchVnode(oldStartVnode, newEndVnode);
    // When the new queen matches the old one, the node must be moved. Move the node pointed to by the new node to the node behind the old node
    // Move node: Whenever a node is inserted that is already in the DOM tree, it will be moved
    parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling);
    oldStartVnode = oldCh[++oldStartIdx];
    newEndVnode = newCh[--newEndIdx];
}
Copy the code

If not, move on to the next situation.

4. If newStart and oldEnd match 4, move the node pointing to oldStart to oldStart –, newStart++

if (sameVnode(newStartVnode, oldEndVnode)) { // New before and old after
    patchVnode(oldEndVnode, newStartVnode);
    // When the new front and the old back hit, the node is moved. Move the node pointed to by the new front (old back) to the old front of the old node
    // Move node: Whenever a node is inserted that is already in the DOM tree, it will be moved
    parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm);
    oldEndVnode = oldCh[--oldEndIdx];
    newStartVnode = newCh[++newStartIdx];
}
Copy the code

NewStart++ = newStart++; newStart++ = newStart++;

const vnode1 = 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'),
])

patch(container, vnode1)

btn.onclick = function () {
  const vnode2 = h('ul', {}, [
    h('li', { key: 'B' }, 'B'),
    h('li', { key: 'Q' }, 'Q'),
    h('li', { key: 'A' }, 'A'),
    h('li', { key: 'D' }, 'D'),
  ])
  patch(vnode1, vnode2)
}
Copy the code

Through this process, we can write the following code:

let keyMap = null;
// Start the loop
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    // The first step is not to judge the four hits, but to skip the things marked with undefined
    if (oldStartVnode == null) {
      oldStartVnode = oldCh[++oldStartIdx];
    } else if (oldEndVnode == null) {
      oldEndVnode = oldCh[--oldEndIdx];
    } else if (newStartVnode == null) {
      newStartVnode = newCh[++newStartIdx];
    } else if (newEndVnode == null) {
      newEndVnode = newCh[--newEndIdx];
    } else if (sameVnode(oldStartVnode, newStartVnode)) { // The new and the old
      patchVnode(oldStartVnode, newStartVnode)
      // Move the pointer
      oldStartVnode = oldCh[++oldStartIdx]
      newStartVnode = newCh[++newStartIdx]
    } else if (sameVnode(newEndVnode, oldEndVnode)) { // New queen and old queen
      patchVnode(oldEndVnode, newEndVnode)
      // Move the pointer
      oldEndVnode = oldCh[--oldEndIdx]
      newEndVnode = newCh[--newEndIdx]
    } else if (sameVnode(newEndVnode, oldStartVnode)) { // The new and the old
      patchVnode(oldStartVnode, newEndVnode);
      // When the new queen matches the old one, the node must be moved. Move the node pointed to by the new node to the node behind the old node
      // Move node: Whenever a node is inserted that is already in the DOM tree, it will be moved
      parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling);
      oldStartVnode = oldCh[++oldStartIdx];
      newEndVnode = newCh[--newEndIdx];
    } else if (sameVnode(newStartVnode, oldEndVnode)) { // New before and old after
      patchVnode(oldEndVnode, newStartVnode);
      // When the new front and the old back hit, the node is moved. Move the node pointed to by the new front (old back) to the old front of the old node
      // Move node: Whenever a node is inserted that is already in the DOM tree, it will be moved
      parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm);
      oldEndVnode = oldCh[--oldEndIdx];
      newStartVnode = newCh[++newStartIdx];
    } else {
      // This is an elegant way to replace each iteration
      if(! keyMap) { keyMap = {}for (let i = oldStartIdx; i <= oldEndIdx; i++) {
          const key = oldCh[i].key
          if (key) {
            keyMap[key] = i
          }
        }
      }
      // Find the sequence number of the current item (newStartIdx) mapped in keyMap
      const idxInOld = keyMap[newStartVnode.key];
      if(! idxInOld) {// If idxInOld is undefined, it is a new entry and needs to be inserted
        // The added item (newStartVnode) is not a real DOM node
        const dom = createElement(newStartVnode)
        parentElm.insertBefore(dom, oldStartVnode.elm);
      } else {
        // indicates that the item is not new and needs to be moved
        const elmToMove = oldCh[idxInOld];
        patchVnode(elmToMove, newStartVnode);
        // Set this item to undefined to indicate that I am done with this item
        oldCh[idxInOld] = undefined;
        / / moveparentElm.insertBefore(elmToMove.elm, oldStartVnode.elm); } newStartVnode = newCh[++newStartIdx]; }}Copy the code

6. After the while loop ends

After the loop ends, there are two situations:

newStartIdx<=newEndIdx

Note newVnode has unprocessed nodes, so you need to add these nodes

oldStartIdx<=oldEndIdx

Note There are still nodes in the oldVnode that need to be deleted

// The loop ends
if (newStartIdx <= newEndIdx) {
  // Indicates that newVndoe has unprocessed nodes, so these nodes need to be added
  const before = oldCh[oldStartIdx] == null ? null : oldCh[oldStartIdx].elm;
  for (let i = newStartIdx; i <= newEndIdx; i++) {
    constdom = createElement(newCh[i]) parentElm.insertBefore(dom, before); }}else if (oldStartIdx <= oldEndIdx) {
  // Indicates that the oldVnode has unprocessed nodes, so these nodes need to be deleted
  for (let i = oldStartIdx; i <= oldEndIdx; i++) {
    if(oldCh[i]) { parentElm.removeChild(oldCh[i].elm); }}}Copy the code

At this point, the diff algorithm is complete!!

Use the example above to demonstrate:

const vnode1 = 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'),
])

patch(container, vnode1)

btn.onclick = function () {
  const vnode2 = h('ul', {}, [
    h('li', { key: 'B' }, 'B'),
    h('li', { key: 'Q' }, 'Q'),
    h('li', { key: 'A' }, 'A'),
    h('li', { key: 'D' }, 'D'),
  ])
  patch(vnode1, vnode2)
}
Copy the code

Iv. Overall code of Patch function

import vnode from './vnode.js'
import api from './htmldomapi.js'

// Is not a virtual node
function isVnode(vnode) {
  return vnode.sel === ' '|| vnode.sel ! = =undefined;
}

// Wrap the oldVnode as a virtual node
function emptyNodeAt(elm) {
  return vnode(
    api.tagName(elm).toLowerCase(),
    {},
    [],
    undefined,
    elm
  );
}

// Is it the same virtual node
function sameVnode(vnode1, vnode2) {
  return vnode1.key === vnode2.key && vnode1.sel === vnode2.sel
}

// Actually create the node, create vNode as DOM without inserting
function createElement(vnode) {
  // Create a DOM node
  let domNode = document.createElement(vnode.sel)
  // Have child nodes or text
  if(vnode.text ! = =' ' && (vnode.children === undefined || vnode.children.length === 0)) {
    // Inside it is text
    domNode.innerText = vnode.text
  } else if (Array.isArray(vnode.children) && vnode.children.length > 0) {
    // Create nodes recursively
    for (let i = 0; i < vnode.children.length; i++) {
      // Get the current children
      let ch = vnode.children[i]
      Call createElement means that the DOM is created, and its ELM attribute points to the created DOM, but not yet on the tree
      let chDom = createElement(ch)
      / / on the tree
      domNode.appendChild(chDom)
    }
  }
  // Add the elm attribute
  vnode.elm = domNode
  // Return the elm pure DOM object
  return vnode.elm
}

function patchVnode(oldVnode, newVnode) {
  // It is the same object in memory
  if (oldVnode === newVnode) return
  if(newVnode.text ! = =undefined && (newVnode.children === undefined || newVnode.children.length === 0)) {
    // The new vNode has a text attribute
    if(newVnode.text ! == oldVnode.text) { oldVnode.elm.innerText = newVnode.text } }else {
    // The new vNode has no text attribute
    if(oldVnode.children ! = =undefined && oldVnode.children.length > 0) {
      // There are many children in my family
      // The most complicated case
      updateChildren(oldVnode.elm, oldVnode.children, newVnode.children)
    } else {
      The old one has no children. The new one has children
      // Step 1: Clear the contents of the old node
      oldVnode.elm.innerText = ' '
      // Step 2: facilitate the creation of a DOM tree on the new vNode child node
      for (let i = 0; i < newVnode.children.length; i++) {
        let dom = createElement(newVnode.children[i])
        oldVnode.elm.appendChild(dom)
      }
    }
  }
}

function updateChildren(parentElm, oldCh, newCh) {
  let oldStartIdx = 0 / / the old before
  let newStartIdx = 0 / / new front
  let oldEndIdx = oldCh.length - 1 / / after the old
  let newEndIdx = newCh.length - 1 / / new after
  let oldStartVnode = oldCh[0] // Old former node
  let oldEndVnode = oldCh[oldEndIdx] // Old back node
  let newStartVnode = newCh[0] // New front node
  let newEndVnode = newCh[newEndIdx] // New post-node

  let keyMap = null

  // Start the loop
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    // The first step is not to judge the four hits, but to skip the things marked with undefined
    if (oldStartVnode == null) {
      oldStartVnode = oldCh[++oldStartIdx];
    } else if (oldEndVnode == null) {
      oldEndVnode = oldCh[--oldEndIdx];
    } else if (newStartVnode == null) {
      newStartVnode = newCh[++newStartIdx];
    } else if (newEndVnode == null) {
      newEndVnode = newCh[--newEndIdx];
    } else if (sameVnode(oldStartVnode, newStartVnode)) { // The new and the old
      patchVnode(oldStartVnode, newStartVnode)
      // Move the pointer
      oldStartVnode = oldCh[++oldStartIdx]
      newStartVnode = newCh[++newStartIdx]
    } else if (sameVnode(newEndVnode, oldEndVnode)) { // New queen and old queen
      patchVnode(oldEndVnode, newEndVnode)
      // Move the pointer
      oldEndVnode = oldCh[--oldEndIdx]
      newEndVnode = newCh[--newEndIdx]
    } else if (sameVnode(newEndVnode, oldStartVnode)) { // The new and the old
      patchVnode(oldStartVnode, newEndVnode);
      // When the new queen matches the old one, the node must be moved. Move the node pointed to by the new node to the node behind the old node
      // Move node: Whenever a node is inserted that is already in the DOM tree, it will be moved
      parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling);
      oldStartVnode = oldCh[++oldStartIdx];
      newEndVnode = newCh[--newEndIdx];
    } else if (sameVnode(newStartVnode, oldEndVnode)) { // New before and old after
      patchVnode(oldEndVnode, newStartVnode);
      // When the new front and the old back hit, the node is moved. Move the node pointed to by the new front (old back) to the old front of the old node
      // Move node: Whenever a node is inserted that is already in the DOM tree, it will be moved
      parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm);
      oldEndVnode = oldCh[--oldEndIdx];
      newStartVnode = newCh[++newStartIdx];
    } else {
      if(! keyMap) { keyMap = {}for (let i = oldStartIdx; i <= oldEndIdx; i++) {
          const key = oldCh[i].key
          if (key) {
            keyMap[key] = i
          }
        }
      }
      // Find the sequence number of the current item (newStartIdx) mapped in keyMap
      const idxInOld = keyMap[newStartVnode.key];
      if(! idxInOld) {// If idxInOld is undefined, it is a new entry and needs to be inserted
        // The added item (newStartVnode) is not a real DOM node
        const dom = createElement(newStartVnode)
        parentElm.insertBefore(dom, oldStartVnode.elm);
      } else {
        // indicates that the item is not new and needs to be moved
        const elmToMove = oldCh[idxInOld];
        patchVnode(elmToMove, newStartVnode);
        // Set this item to undefined to indicate that I am done with this item
        oldCh[idxInOld] = undefined;
        // Move, insertBefore can also move.parentElm.insertBefore(elmToMove.elm, oldStartVnode.elm); } newStartVnode = newCh[++newStartIdx]; }}// The loop ends
  if (newStartIdx <= newEndIdx) {
    // Indicates that newVndoe has unprocessed nodes, so these nodes need to be added
    const before = oldCh[oldStartIdx] == null ? null : oldCh[oldStartIdx].elm;
    for (let i = newStartIdx; i <= newEndIdx; i++) {
      constdom = createElement(newCh[i]) parentElm.insertBefore(dom, before); }}else if (oldStartIdx <= oldEndIdx) {
    // Indicates that the oldVnode has unprocessed nodes, so these nodes need to be deleted
    for (let i = oldStartIdx; i <= oldEndIdx; i++) {
      if(oldCh[i]) { parentElm.removeChild(oldCh[i].elm); }}}}export default function patch(oldVnode, newVnode) {
  // Check whether it is a virtual node
  if(! isVnode(oldVnode)) {// If it is not a virtual node, wrap it as a virtual node
    oldVnode = emptyNodeAt(oldVnode)
  }
  if (sameVnode(oldVnode, newVnode)) {
    patchVnode(oldVnode, newVnode)
  } else {
    // Forcibly insert new, delete old
    let newVnodeElm = createElement(newVnode)
    if (oldVnode.elm.parentNode && newVnodeElm) {
      oldVnode.elm.parentNode.insertBefore(newVnodeElm, oldVnode.elm)
      // Delete the old node
      oldVnode.elm.parentNode.removeChild(oldVnode.elm)
    }
  }
}
Copy the code

If this article was helpful, please give it a thumbs up

Virtual DOM and diff algorithms

Virtual DOM and diff algorithms

A simple understanding of virtual DOM and diff algorithm

Second, the snabbdom

2.1 snabbdom profile

2.1.1 Setting up an SNabbDOM Environment

2.2 Virtual DOM and H functions

2.2.1 h function

Original H function TS version of the core code

Handwritten h function

2.3 Feel the DIff algorithm

Write diff by hand

3.1 Creating the Patch Function

3.2 the createElement method function

3.3 DIff Process when the old and new nodes are the same node

3.3.1 newVnode Has Text

3.3.2 newVnode Without Text (With children)

3.3.3 Analyzing diFF algorithm updating child Node Operations (Important)

Iv. Overall code of Patch function

Related Posts

Vue instruction 2

Canvas implements cool matrix digital rain effects

Front-end technology selection of the best artifact!