Vue source code explore the diff algorithm

Now the interview is not only the basic ability to compete, but also to examine your understanding of the source code, this article let us explore the Vue source diff algorithm.

You have baa have in at the time of the interview the interviewer asked what was the process of the diff algorithm, you will say, compiled template generated virtual dom, the comparison of old and newly generated virtual dom, compare the difference of place, and then apply colours to a drawing to real dom above, how many people are so answer, anyway I interview others when somebody else is replied, I am digging into the new generation of virtual DOM and the old specific is how to compare, the people hesitated to answer, now let us slowly explore the Vue source diff process, take you into the process of appreciation and pay.

First of all, what is the Diff algorithm

The diff algorithm

If we just need to add a new sofa to the living room or move the bed in the bedroom, for example, we need to renovate the house. So it is obviously impractical to renovate the whole house, and our usual approach is to make tiny changes on the basis of the original decoration. The same is true for DOM trees if you simply add a tag or modify the attributes or contents of a tag. Causing the entire DOM tree to be re-rendered is obviously a huge waste of performance and resources, even though our computers can perform hundreds of millions of calculations per second. In fact, we just need to find the differences between the old and new DOM trees and re-render just that area. So Diff algorithm came into being, Diff from different (different), the role of Diff algorithm, in summary, is: fine comparison, minimum update.

Examples of diff

<div class="box">
    <h3>I'm a headline</h3> 
    <ul> 
        <li>milk</li> <li>coffee</li> 
        <li>coke</li> 
    </ul>
</div>
Copy the code

It goes like this:

<div class="box">
  <h3>I'm a headline</h3>
  <span>I'm a new SPAN</span>
  <ul>
    <li>milk</li>
    <li>coffee</li>
    <li>coke</li>
    <li>Sprite</li>
  </ul>
</div>
Copy the code

As shown above, from the first DOM tree to the second DOM tree, we don't need to tear down the entire DOM and start from scratch. Instead, we need to add a SPAN tag and a Li tag to the original DOM tree.

True dom.

<div class="box">
  <h3>I'm a headline</h3>
  <ul>
    <li>milk</li>
    <li>coffee</li>
    <li>coke</li>
  </ul>
</div>
Copy the code

Virtual DOM

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

Before learning about the virtual DOM, let’s take a look at the virtual DOM library snabbDOM

Introduction to the

snabbdomIt’s a Swedish word that means speed.
snabbdomIt’s the famous virtualDOMLibrary, it isdiffThe father of algorithms,VueThe source code is used for referencesnabbdom
The officialGit:Github.com/snabbdom/sn…

The installation

The snabbDOM source code on Git is written in TypeScript, and a compiled JavaScript version is not available on Git
To use the built JavaScript version of the SNabbDOM library directly, you can download it from NPM: NPM I-S Snabbdom
When learning the base of the library, it is recommended that you read the original code, preferably with the library author’s original comments. This will greatly improve your ability to read source code.

Test environment setup

The snabbDOM library is a DOM library and cannot run in nodeJS environment, so we need to build webPack and webpack-dev-server development environment. The good news is that we don’t need to install any loader
Note that the latest version webpack@5 must be installed, not webpack@4, because webpack@4 does not have the ability to read exports in package.json.

npm i -D webpack@5 webpack-cli@3 webpack-dev-server@3

referencewebpackThe official website, write wellwebpack.config.jsfile

// https://webpack.docschina.org/
const path = require('path')

module.exports = {
  / / the entry
  entry: './src/index.js'./ / export
  output: {
    // Virtual package path, that is, the folder is not actually generated, but on port 8080 virtual generation, not really physical generation
    publicPath: 'xuni'.// The name of the packaged file
    filename: 'bundle.js'
  },
  devServer: {
    / / the port number
    port: 8080.// Static resources folder
    contentBase: 'www'}}Copy the code

The new directorysrc-> Create a filesrc/index.js-> Create a directorywww-> Create a filewww/index.html

/** src/index.js */ alert(123)
Copy the code

<! -- www/index.html -->
<! DOCTYPEhtml>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="Width = device - width, initial - scale = 1.0">
  <title>Document</title>
</head>
<body>
  <h1>Hello!!!!!!</h1>
  <script src="xuni/bundle.js"></script>
</body>
</html>
Copy the code

New commands in package.json ‘file:

{ "scripts": { "dev": "webpack-dev-server", } }

Terminal operationnpm run dev
Access:http://localhost:8080/ 和 http://127.0.0.1:8080/xuni/bundle.jsAs you can seewww/index.html 和 xuni/bundle.jsContents of the document
Run throughsnabbdomThe officialgitThe home pagedemoProgram, that is, to prove that the debugging environment has been set up successfully (copy the following code tosrc/index.jsC)

import { init } from 'snabbdom/init'
import { classModule } from 'snabbdom/modules/class'
import { propsModule } from 'snabbdom/modules/props'
import { styleModule } from 'snabbdom/modules/style'
import { eventListenersModule } from 'snabbdom/modules/eventlisteners'
import { h } from 'snabbdom/h' // helper function for creating vnodes

var 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
])

var container = document.getElementById('container')

var vnode = h('div#container.two.classes', { on: { click: function () {} } }, [
  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)

var newVnode = h(
  'div#container.two.classes',
  { on: { click: function () {} } },
  [
    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

Don’t forgetwww/index.htmlPlace adiv#container

<! DOCTYPEhtml>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <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

Refresh the page, and a paragraph of text appears

This is now italic type and this is still just normal textI’ll take you places!

Virtual DOM and h functions

Virtual DOM

virtualDOM:JavaScriptObject descriptionDOMThe hierarchy of.DOMAll attributes are virtualDOMThere are corresponding attributes in.
diffIt happens virtuallyDOMOn: new virtualDOMWith the virtualDOMfordiff(fine comparison), figure out how to minimize the amount of updates, and finally reflect the realDOM 上
The oldDOM

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

Updated DOM:

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

DOMHow to become virtualDOMBelongs to the template compilation principle category, this class will not study
What is the subject of this class?
- Study 1: How is the virtual DOM generated by the render function (h function)? – Handwriting h function
- Study 2: Principle of diff algorithm? – Handwritten diff algorithm
- Study 3: How does the virtual DOM become the real DOM through diff – in fact, the virtual DOM becomes the real DOM under the diff algorithm

H function

The basic use

hFunction is used to generateVirtual node (vnode)

Call it like thishfunction

    h('a', { props: { href: 'http://www.atguigu.com'}},Silicon Valley)
Copy the code

The resulting virtual node looks like this:

{ "sel": "a", "data": { "props": { "href": "#" } }, "text": "dom" }

It represents the realDOMNodes:

dom

What are the attributes of a virtual node?

{
  children: undefined.// Child node: undefined means there is no child node
  data: {}, // Attribute styles, etc
  elm: undefined.// The actual DOM node that corresponds to this element. Undefined means it is not on the tree yet
  key: undefined.// Uniquely identifies a node
  sel: 'div'.// selector node type (now it's a div)
  text: 'I am a box' / / text
}
Copy the code

demoCreate a virtual node and render the virtual node to the page. Copy the following code tosrc/index.js) :

import { init } from 'snabbdom/init'
import { classModule } from 'snabbdom/modules/class'
import { propsModule } from 'snabbdom/modules/props'
import { styleModule } from 'snabbdom/modules/style'
import { eventListenersModule } from 'snabbdom/modules/eventlisteners'
import { h } from 'snabbdom/h' // helper function for creating vnodes
// Create patch function
const patch = init([
  classModule,
  propsModule,
  styleModule,
  eventListenersModule
])
// Create a virtual node
const myVNode1 = h(
  'a',
  { props: { href: 'http://www.atguigu.com'.target: '_blank'}},Silicon Valley
)
const myVNode2 = h('div', { class: { box: true}},'I am a box')
// Put the virtual node on the tree
const container = document.getElementById('container')
// patch(container, myVNode1)
patch(container, myVNode2)
Copy the code

<! -- www/index.html -->
<! DOCTYPEhtml>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="Width = device - width, initial - scale = 1.0">
  <title>Document</title>
</head>
<body>
  <button id="btn">Press me to change the DOM</button>
  <div id="container"></div>
  <script src="xuni/bundle.js"></script>
</body>
</html>
Copy the code

Analysis:

Let’s start by changing the text content of each li tag in the browser (changing ABCD to 1234) as follows:

Then click the button and the following happens:

As you can see, in the code abovepatchThe function actually does the work of the originalvnode1A new node is added to the base
This suggests that:diffThe algorithm compares virtual nodes
We put theEPut it in frontA B C DInstead of1 2 3 4Then click the button

const vnode2 = h('ul', {}, [
  h('li', {}, 'E'),
  h('li', {}, 'A'),
  h('li', {}, 'B'),
  h('li', {}, 'C'),
  h('li', {}, 'D')])Copy the code

You find that the whole thing is replaced

This is because the virtual nodes are now compared in this order

E-a, a-b, b-c, c-d is the new nodeCopy the code

We give each node a unique identitykey:

const vnode1 = h('ul', {}, [
  h('li', { key: 'A' }, 'A'),
  h('li', { key: 'B' }, 'B'),
  h('li', { key: 'C' }, 'C'),
  h('li', { key: 'D' }, 'D')])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')])Copy the code

Repeat the above steps at this timeERepresents a new node:

That’s why the nodes are uniquely identified, right`key`After the page rendering efficiency will be greatly improved

tips

The diff algorithm is really a minimal update, and the key is important, because the key is the unique identifier of the node that tells the DIff algorithm that they are the same DOM node before and after the change
Only the same virtual node is used for virtualization comparison. Otherwise, the old node is forcibly deleted and the new node is forcibly inserted. Extension question: How to define the same virtual node? A: Same selector and same key
Comparisons are made within layers, not across layers. Even if it is the same piece of virtual nodes, if it is across layers, the DIff algorithm will not carry out fine comparison. Instead, they violently delete the old and insert the new.

Diff handles when the old and new nodes are not the same node

How to define whether the comparison is “the same node”?

/ / snabbdom source code
function sameVnode (vnode1: VNode, vnode2: VNode) :boolean {
  return vnode1.key === vnode2.key && vnode1.sel === vnode2.sel
}
Copy the code

If yes, the following two points must be met:

The old nodekeyTo the new nodekeyThe same;

The old node has the same selector as the new node

When a node is created, all child nodes are created recursively

/ / snabbdom source code
function createElm() {
  // ...
  if (is.array(children)) {
    for (i = 0; i < children.length; ++i) {
      const ch = children[i]
      if(ch ! =null) {
        api.appendChild(elm, createElm(ch as VNode, insertedVnodeQueue))
      }
    }
  } else if (is.primitive(vnode.text)) {
    api.appendChild(elm, api.createTextNode(vnode.text))
  }
  // ...
}
Copy the code

Write the createElement function

/ / the createElement method function
// Create vNode as DOM
// Is an orphan node and does not insert
export default function createElement(vnode) {
  // Create a DOM node that is now an orphan node
  let domNode = document.createElement(vnode.sel)
  // Does it have child nodes or text?
  if( vnode.text ! = =' ' &&
    (vnode.children === undefined || vnode.children.length === 0)) {// It contains text
    domNode.innerText = vnode.text
  } else if (Array.isArray(vnode.children) && vnode.children.length > 0) {
    // It contains child nodes, which are created recursively
    for (let i = 0; i < vnode.children.length; i++) {
      // Get the current child
      let ch = vnode.children[i]
      CreateElement means that the DOM is created, and its ELM attribute points to the created DOM, but it's not on the tree yet, so it's an orphan node
      let chDom = createElement(ch)
      / / on the tree
      domNode.appendChild(chDom)
    }
  }
  // Add the elm attribute
  vnode.elm = domNode
  // Return elm, elm is a pure DOM object
  return vnode.elm
Copy the code

Upper tree patch function

/ / patch function
import vnode from './vnode'
import createElement from './createElement'
export default function patch(oldVnode, newVnode) {
  // Check whether the first argument passed in is a DOM node or a virtual node.
  if (oldVnode.sel === ' ' || oldVnode.sel === undefined) {
    // The first argument passed in is the DOM node, which is wrapped as a virtual node
    oldVnode = vnode(
      oldVnode.tagName.toLowerCase(),
      {},
      [],
      undefined,
      oldVnode
    )
  }
  console.log(oldVnode, newVnode)
  // Check whether oldVnode and newVnode are the same node
  if (oldVnode.key === newVnode.key && oldVnode.sel === newVnode.sel) {
    console.log('It's the same node')}else {
    console.log('Not the same node, violent insert new, delete old')
    let newVnodeElm = createElement(newVnode)
    if (oldVnode.elm && newVnodeElm) {
      // Insert before the old node
      oldVnode.elm.parentNode.insertBefore(newVnodeElm, oldVnode.elm)
    }
    // Delete the old node
    oldVnode.elm.parentNode.removeChild(oldVnode.elm)
  }
}
Copy the code

Now write a test case to test it:

// Test the code
import h from './mysnabbdom/h'
import patch from './mysnabbdom/patch'

const myVnode1 = h('ul', {}, [
  h('li', {}, 'milk'),
  h('li', {}, 'coffee'),
  h('li', {}, [h('div', {}, [h('p', {}, 'Coca-Cola'), h('p', {}, Pepsi cola)])]),
  h('li', {}, h('p', {}, 'spirits')))const container = document.getElementById('container')
patch(container, myVnode1)

const btn = document.getElementById('btn')
const myVnode2 = h('section', {}, [
  h('h1', {}, 'I'm the new H1'),
  h('h2', {}, 'I'm the new H2')
])
btn.onclick = function () {
  patch(myVnode1, myVnode2)
}
Copy the code

Diff handles when the old and new nodes are not the same node

Different case of writing old and new node text

// patchVnode.js
export default function patchVnode(oldVnode, newVnode) {
  // Check whether the old and new vNodes are the same object
  if (oldVnode === newVnode) return
  // Check whether the new vNode has a text attribute
  if( newVnode.text ! =undefined &&
    (newVnode.children === undefined || newVnode.children.length === 0)) {// The new node has a text attribute
    console.log('New Vnode has text property')
    if(newVnode.text ! = oldVnode.text) {// If the text in the new virtual node is different from the text in the old virtual node, write the new text to the old ELM. If the old elm were children, the name would also disappear immediately
      oldVnode.elm.innerText = newVnode.text
    }
  } else {
    // The new node has no text property and children
    // Check whether the old virtual node has children
    if(oldVnode.children ! = =undefined && oldVnode.children.length > 0) {
      // Old vNodes have children, which is the most complicated case. Both old and new VNodes have children
    } else {
      // Old vNodes do not have children, new vnodes do
      // Clear the contents of the old vNode
      oldVnode.elm.innerText = ' '
      // Traverses the child nodes of the new vNode, creating the DOM, and ascending the tree
      for (let i = 0; i < newVnode.children.length; i++) {
        const dom = createElement(newVnode.children[i])
        oldVnode.elm.appendChild(dom)
      }
    }
  }
}
Copy the code

// patch.js
import vnode from './vnode'
import createElement from './createElement'
import patchVnode from './patchVnode'
export default function patch(oldVnode, newVnode) {
  // ...
  // Check whether oldVnode and newVnode are the same node
  if (oldVnode.key === newVnode.key && oldVnode.sel === newVnode.sel) {
    // console.log(' Same node ')
    patchVnode(oldVnode, newVnode)
  } else {
    // ...}}Copy the code

Try writing diff to update the child node

vnode.jsaddkeyattribute

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

Newly created nodes (newVnode.children[i].elmInsert into all unprocessed nodes (oldVnode.children[un].elm) before, not after all processed nodes

import createElement from './createElement'

export default function patchVnode(oldVnode, newVnode) {
  // ...
  if( newVnode.text ! =undefined &&
    (newVnode.children === undefined || newVnode.children.length === 0)) {// ...
  } else {
    // The new node has no text property and children
    // Check whether the old virtual node has children
    if(oldVnode.children ! = =undefined && oldVnode.children.length > 0) {
      // Old vNodes have children, which is the most complicated case. Both old and new VNodes have children
      // Start of all unprocessed nodes
      let un = 0
      for (let i = 0; i < newVnode.children.length; i++) {
        const ch = newVnode.children[i]
        // Iterate to see if there are any oldVnode nodes that are the same as it
        let isExist = false
        for (let j = 0; j < oldVnode.children.length; j++) {
          const oldCh = oldVnode.children[j]
          if (oldCh.sel === ch.sel && oldCh.key === ch.key) {
            isExist = true}}if(! isExist) {console.log(ch, i)
          const dom = createElement(ch)
          ch.elm = dom
          if (un < oldVnode.children.length) {
            oldVnode.elm.insertBefore(dom, oldVnode.children[un].elm)
          } else {
            oldVnode.elm.appendChild(dom)
          }
        } else {
          // Move the pointer to the node being processed down
          un++
        }
      }
    } else {
      // ...}}}Copy the code

The above code only implements the logic of adding nodes. If you want to add the implementation of deleting and updating nodes, this idea is obviously very troublesome

Diff algorithm child node update strategy

Four hits lookup (classic diff algorithm optimization strategy) : (1) the new and old before and after (2) after the new and old (3) new old before (before this hits, involves the mobile node, so the old point to the node, after moving to old) (4) before the new and old (such a hit, involves the mobile node, then after the old node, before moving to the front of the old

If you hit one, you’re not judging
If none of them hit, you need to use a loop to find them

New information

Deletion condition

Complex situation

Handwriting child node update policy

snabbdomThe source code

function updateChildren (parentElm: Node, oldCh: VNode[], newCh: VNode[], insertedVnodeQueue: VNodeQueue) {
  let oldStartIdx = 0
  let newStartIdx = 0
  let oldEndIdx = oldCh.length - 1
  let oldStartVnode = oldCh[0]
  let oldEndVnode = oldCh[oldEndIdx]
  let newEndIdx = newCh.length - 1
  let newStartVnode = newCh[0]
  let newEndVnode = newCh[newEndIdx]
  let oldKeyToIdx: KeyToIndexMap | undefined
  let idxInOld: number
  let elmToMove: VNode
  let before: any

  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    if (oldStartVnode == null) {
      oldStartVnode = oldCh[++oldStartIdx] // Vnode might have been moved left
    } 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)) {
      patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
      oldStartVnode = oldCh[++oldStartIdx]
      newStartVnode = newCh[++newStartIdx]
    } else if (sameVnode(oldEndVnode, newEndVnode)) {
      patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
      oldEndVnode = oldCh[--oldEndIdx]
      newEndVnode = newCh[--newEndIdx]
    } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved rightpatchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue) api.insertBefore(parentElm, oldStartVnode.elm! , api.nextSibling(oldEndVnode.elm!) ) oldStartVnode = oldCh[++oldStartIdx] newEndVnode = newCh[--newEndIdx] }else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved leftpatchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue) api.insertBefore(parentElm, oldEndVnode.elm! , oldStartVnode.elm!) oldEndVnode = oldCh[--oldEndIdx] newStartVnode = newCh[++newStartIdx] }else {
      if (oldKeyToIdx === undefined) {
        oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
      }
      idxInOld = oldKeyToIdx[newStartVnode.key as string]
      if (isUndef(idxInOld)) { // New element
        api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm!)
      } else {
        elmToMove = oldCh[idxInOld]
        if(elmToMove.sel ! == newStartVnode.sel) { api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm!) }else {
          patchVnode(elmToMove, newStartVnode, insertedVnodeQueue)
          oldCh[idxInOld] = undefined asany api.insertBefore(parentElm, elmToMove.elm! , oldStartVnode.elm!) } } newStartVnode = newCh[++newStartIdx] } }if (oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx) {
    if (oldStartIdx > oldEndIdx) {
      before = newCh[newEndIdx + 1] = =null ? null : newCh[newEndIdx + 1].elm
      addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
    } else {
      removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
    }
  }
}
Copy the code

implementupdateChildrenmethods

// updateChildren.js
import createElement from './createElement'
import patchVnode from './patchVnode'

// Check whether it is the same virtual node
function checkSameVnode(a, b) {
  return a.sel === b.sel && a.key === b.key
}

export default function updateChildren(parentElm, oldCh, newCh) {
  // console.log(' I am updateChildren')
  // console.log(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[oldStartIdx] // Old former node
  let oldEndVnode = oldCh[oldEndIdx] // Old back node
  let newStartVnode = newCh[newStartIdx] // New front node
  let newEndVnode = newCh[newEndIdx] // New post-node
  let keyMap = null
  // console.log(oldStartIdx, newEndIdx)
  // Start the loop
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    / / the console. The log (' nurture ')
    // The first step is not to judge the hit, but to pass the thing marked with undefined
    if (oldStartVnode === null || oldCh[oldStartIdx] === undefined) {
      oldStartVnode = oldCh[++oldStartIdx]
    } else if (oldEndVnode === null || oldCh[oldEndIdx] === undefined) {
      oldEndVnode = oldCh[--oldEndIdx]
    } else if (newStartVnode === null || newCh[newStartIdx] === undefined) {
      newStartVnode = newCh[++newStartIdx]
    } else if (newEndVnode === null || newCh[newEndIdx] === undefined) {
      newEndVnode = newCh[--newEndIdx]
    } else if (checkSameVnode(oldStartVnode, newStartVnode)) {
      // New and old
      console.log('① New and old hit ')
      patchVnode(oldStartVnode, newStartVnode)
      oldStartVnode = oldCh[++oldStartIdx]
      newStartVnode = newCh[++newStartIdx]
    } else if (checkSameVnode(oldEndVnode, newEndVnode)) {
      // New queen and old queen
      console.log('② New queen and old queen hit ')
      patchVnode(oldEndVnode, newEndVnode)
      oldEndVnode = oldCh[--oldEndIdx]
      newEndVnode = newCh[--newEndIdx]
    } else if (checkSameVnode(oldStartVnode, newEndVnode)) {
      // New after and old before
      console.log('③ Hit the old queen and the new queen ')
      patchVnode(oldStartVnode, newEndVnode)
      // When ③ new and old hit, move the node. Move the node pointed to by the new node to the node behind the old node
      // How do I move nodes? Whenever you insert a node that is already in the DOM tree, it is moved
      parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling)
      oldStartVnode = oldCh[++oldStartIdx]
      newEndVnode = newCh[--newEndIdx]
    } else if (checkSameVnode(oldEndVnode, newStartVnode)) {
      // New before and old after
      console.log('④ New before and old after hit ')
      patchVnode(oldEndVnode, newStartVnode)
      // When ④ new front and old rear hit, the node should be moved. Move the node pointed to by the new node to the node in front of the old node
      parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm)
      oldEndVnode = oldCh[--oldEndIdx]
      newStartVnode = newCh[++newStartIdx]
    } else {
      // None of the four hits were found
      // make keyMap, cache
      if(! keyMap) { keyMap = {}// Start with oldStartIdx and end with oldEndIdx to create keyMap
        for (let i = oldStartIdx; i <= oldEndIdx; i++) {
          const key = oldCh[i].key
          if(key ! = =undefined) {
            keyMap[key] = i
          }
        }
      }
      // console.log(keyMap)
      // Find the sequence number of the current item newStartIdx mapped in keyMap
      const idxInOld = keyMap[newStartVnode.key]
      if (idxInOld === undefined) {
        // If idxInOld is undefined, it is completely new
        // The added item (newStartVnode) is not a real DOM
        parentElm.insertBefore(createElement(newStartVnode), oldStartVnode.elm)
      } else {
        // If idxInOld is not undefined, it is not new and needs to be moved
        const elmToMove = oldCh[idxInOld]
        patchVnode(elmToMove, newStartVnode)
        // Set this to undefined to indicate that the processing is complete
        oldCh[idxInOld] = undefined
        // Move, call insertBefore
        parentElm.insertBefore(elmToMove.elm, oldStartVnode.elm)
      }
      // Move the pointer down to move only the new head
      newStartVnode = newCh[++newStartIdx]
    }
  }
  NewStartIdx is still smaller than newEndIdx
  if (newStartIdx <= newEndIdx) {
    // new there are still nodes left unprocessed
    // Insert the benchmark
    // const before = newCh[newEndIdx + 1] ? newCh[newEndIdx + 1].elm : null
    //
    for (let i = newStartIdx; i <= newEndIdx; i++) {
      // insertBefore automatically recognizes null, and if it is null, it automatically goes to the end of the queue. Consistent with appendChild
      // newCh[I] isn't really DOM yet, so createElement needs to be called
      parentElm.insertBefore(createElement(newCh[i]), oldCh[oldStartIdx].elm)
    }
  } else if (oldStartIdx <= oldEndIdx) {
    // old there are still nodes left unprocessed
    // Delete items between oldStartIdx and oldEndIdx in batches
    for (let i = oldStartIdx; i <= oldEndIdx; i++) {
      if (oldCh[i]) {
        parentElm.removeChild(oldCh[i].elm)
      }
    }
  }
}
Copy the code

Ok, let’s test this in the next unit test:

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

const myVnode1 = 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')])const container = document.getElementById('container')
// Climb the tree for the first time
patch(container, myVnode1)

const btn = document.getElementById('btn')
/ / the new node
const myVnode2 = h('ul', {}, [
  h('li', { key: 'QQ' }, 'QQB'),
  h('li', { key: 'C' }, 'C'),
  h('li', { key: 'D' }, 'D'),
  h('li', { key: 'B' }, 'B'),
  h('li', { key: 'F' }, 'F'),
  h('li', { key: 'G' }, 'G')
])
btn.onclick = function () {
  patch(myVnode1, myVnode2)
}
Copy the code

Vue source code explore the diff algorithm

The diff algorithm

Introduction to the

The installation

Test environment setup

Virtual DOM and h functions

Virtual DOM

H function

The basic use

That’s why the nodes are uniquely identified, rightkeyAfter the page rendering efficiency will be greatly improved

tips

Diff handles when the old and new nodes are not the same node

When a node is created, all child nodes are created recursively

Write the createElement function

Upper tree patch function

Diff handles when the old and new nodes are not the same node

Different case of writing old and new node text

Try writing diff to update the child node

Diff algorithm child node update strategy

New information

Deletion condition

Complex situation

Handwriting child node update policy

Related Posts

I wonder if it’s Internet Explorer after Flash

Gewu · Gewu – AntV released in 2021

Install the Flutter environment on MAC

That’s why the nodes are uniquely identified, right`key`After the page rendering efficiency will be greatly improved