takeaway

Today I will share what I have learned: the implementation principle of Virtual DOM

The virtual DOM

What is the virtual DOM

Virtual DOM (Virtual DOM) is a common JS object to describe the DOM object, because it is not a real DOM object, so it is called Virtual DOM

2. Why the virtual DOM

It is troublesome to operate DOM manually, and browser compatibility issues also need to be considered. Although there are libraries such as jQuery to simplify DOM operation, with the complexity of DOM operation of the project, various MVVM frameworks have emerged in order to simplify DOM complex operation. The MVVM framework solves the problem of synchronizing views and state

In order to simplify the operation of the view, we can use a template engine, but the template engine does not solve the problem of tracking state changes. For example, when the data changes, it cannot obtain the last state, but can only be deleted and recreated. So the Virtual DOM came along

The advantage of the Virtual DOM is that you don’t need to update the DOM immediately when the state changes, you just need to create a Virtual tree to describe the DOM,

Will the Virtual DOM interior figure out how to effectively (diff) update the DOM

The virtual DOM can maintain the state of the program, keeping track of the last state

The role of the virtual DOM

  1. Maintain the relationship between view and state: The virtual DOM can record the last DOM state change and only update the location of the change

  2. Improved rendering performance in complex views: Compared to traditional DOM, virtual DOM performs better in terms of performance

  3. In addition to DOM rendering, it can also realize SSR server rendering (nuxt.js/Next-js), Native application (Weex/React Native), small program (MPvue /uni-app), etc

Common virtual DOM libraries

Common virtual DOM libraries include Snabbdom and Virtual-DOM

Snabbdom

Since the virtual DOM of VUe2 is based on Snabbdom, let’s take a look at Snabbdom. Start by defining an HTML file

// index.html<! DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, Initial-scale =1.0"> <title>snabbdom-demo</title> </head> <body> <div id="app"></div> <script src="./src/basicusage.js"></script> </body> </html>Copy the code

Import Snabbdom

Snabbdom is imported through commonJS specification. Here we import Snabbdom through import. Note: Cannot resolve dependency ‘snabbDOM’ Cannot resolve dependency ‘snabbDOM’ Cannot resolve dependency ‘snabbDOM’ Cannot resolve dependency ‘Snabbdom 0.7.4

/ / import
// import snabbdom from 'snabbdom'
import { h, thunk, init } from 'snabbdom'
Copy the code

As you can see, importing snabbDOM through import cannot be directly imported through the first method. This is because in the SOURCE code of SNabbDOM, objects are not exported through export default, so they can only be exported in curly braces. The core of Snabbdom provides only the most basic functionality, exporting only three functions: init(), h(), and thunk()

Init () is a higher-order function that returns patch();

H () returns the virtual node VNode, which is common in VUE and used in previous reactive principles.

Thunk () is an optimization strategy that can be used when dealing with immutable data

The use of snabbdom

import { h, thunk, init } from 'snabbdom'

// 1. hello world
// Parameters: array, module
// Return value: the patch function, which compares the difference between two VNodes and updates it to the real DOM
let patch = init([])
// First argument: label + selector
// The second argument: if it is a string, it is the content of the tag
let vnode = h('div#container.cls'.'Hello World')

let app = document.querySelector('#app')
// The first argument can be a DOM element, which is internally converted to a vNode
// The second argument: vnode
// Return value: VNode
let oldVnode = patch(app, vnode)
Copy the code

Here is the first example, in which they initialize patch using init in snabbDOM, and then create a div element with the id of container and class of CLS using h. This element is the created VNode with the content of Hello World. Then the two VNodes are compared by the initialized patch function. The first parameter in patch is DOM. The patch function will automatically convert dom elements to VNodes and update them to the view. In this case, you can find the location of #app in index.html, and the content has been changed to Hello World

Let’s assume a scenario where at some point we need to fetch data from the server and then pass it into a page for presentation

// The hypothetical moment

vnode = h('div'.'Hello Snabbdom')

patch(oldVnode, vnode)
Copy the code

Here, we saved the vnode processed by the patch function last time and saved it to oldVnode. Then, we modified the content of the original Vnode through h function, compared it with patch function, and updated the data to the view.

The example above is to create a div node, which we need to do when we want to create a virtual DOM node with child nodes

import { h, thunk, init } from 'snabbdom'

// 2. Place child elements h1,p in div

let patch = init([])

let vnode = h('div#container', [
    h('h1'.'Hello Snabbdom'),
    h('p'.'Hello P')])let app = document.querySelector('#app')

let oldVnode = patch(app, vnode)

setTimeout(() = > {
    // Clear page elements
    // patch(oldVnode, null)
    patch(oldVnode, h('! '))},2000)

Copy the code

The main difference here is that when vNode is created, the second parameter of h function is an array, which contains all the child nodes and their contents. Meanwhile, patch function is used to compare and render them in the page. When we want to clear the contents of the specified position on the page, we can set the second parameter in the patch function to h(‘! ‘), through the h function to set the comment node, change the corresponding content. (The official website passes null as the second parameter, this practice is wrong, the page will error)

Snabbdom module

Snabbdom provides six commonly used modules

Of course we can expand the modules we want

Use of modules

Import the required module. Register module 3 in init(). When creating a VNode using the h function, you can set the second parameter to an object and move the rest of the parameters backCopy the code
import { h, thunk, init } from 'snabbdom'
// Import the module
import style from 'snabbdom/modules/style'
import eventlisteners from 'snabbdom/modules/eventlisteners'
// Register module
let patch = init([
    style,
    eventlisteners
])
// Use the second argument to h to pass in the data required by the module
let vnode = h('div', {
    style: {
        backgroundColor: 'red'
    },
    on: {
        click: eventHandler
    }
}, [
    h('h1'.'Hello Snabbdom'),
    h('p'.'Hello P')])let app = document.querySelector('#app')

patch(app, vnode)

function eventHandler() {
    console.log('Click on me! ~ ')}Copy the code

Here we import the module through import, which is located in snabbDOM /modules. Then we register the module by passing the imported module in an array through init(). Then we pass the second parameter in h to the data the module needs. These two data are both objects. Finally, patch is used to compare the two VNodes and render the page. The page effect is as follows

Snabbdom source code analysis

The core of SNabbDOM is to use h function to create vNodes, init to set the module and create patches, use patch function to compare two VNodes and update the content into the DOM, so we mainly analyze these three TS files

H function

We first saw h functions in VUE, but vue implements a component mechanism for h functions as opposed to SNabbDOM

new Vue({
	router,
    store,
    render:h= > h(App)
}).$mount('#app')
Copy the code

The h function, first seen in HyperScript, uses javascript to create hypertext

In snabbDOM, the h function is not used to create hypertext, but to create vNodes

Function overloading

Javascript does not support function overloading, whereas typescript does

Let’s take a look at the source code, here I will annotate the source code, easy to understand

import {vnode, VNode, VNodeData} from './vnode';
export type VNodes = Array<VNode>;
export type VNodeChildElement = VNode | string | number | undefined | null;
export type ArrayOrElement<T> = T | T[];
export type VNodeChildren = ArrayOrElement<VNodeChildElement>
import * as is from './is';

function addNS(data: any, children: VNodes | undefined, sel: string | undefined) :void {
  data.ns = 'http://www.w3.org/2000/svg';
  if(sel ! = ='foreignObject'&& children ! = =undefined) {
    for (let i = 0; i < children.length; ++i) {
      let childData = children[i].data;
      if(childData ! = =undefined) {
        addNS(childData, (children[i] as VNode).children asVNodes, children[i].sel); }}}}// overloading the h function
export function h(sel: string) :VNode;
export function h(sel: string, data: VNodeData) :VNode;
export function h(sel: string, children: VNodeChildren) :VNode;
export function h(sel: string, data: VNodeData, children: VNodeChildren) :VNode;
export function h(sel: any, b? : any, c? : any) :VNode {
  var data: VNodeData = {}, children: any, text: any, i: number;
  // Three parameters
  if(c ! = =undefined) {
    data = b;
    // array indicates child elements (child nodes)
    if (is.array(c)) { children = c; }
    // string or number
    else if (is.primitive(c)) { text = c; }
    // vnode
    else if(c && c.sel) { children = [c]; }}// Two parameters
  else if(b ! = =undefined) {
    // array indicates child elements (child nodes)
    if (is.array(b)) { children = b; }
    // string or number
    else if (is.primitive(b)) { text = b; }
    // vnode
    else if (b && b.sel) { children = [b]; }
    else{ data = b; }}if(children ! = =undefined) {
    // Handle primitive values in children (string/number)
    for (i = 0; i < children.length; ++i) {
      // Create a virtual text node
      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= = =The '#')) {// SVG adds a namespace
    addNS(data, children, sel);
  }
  / / return VNode
  return vnode(sel, data, children, text, undefined);
};
export default h;

Copy the code

Source through the way of function overloading, define the parameters of the different functions of the same name, in the following function implementation, the first to determine the third parameter, if present, instructions to the three parameters, the second parameter b into the data, then to determine c, judge c types of arrays, strings, Numbers, or vnode, And assign the corresponding children or text according to the judgment result. If the third parameter c does not exist, judge whether B exists; if so, judge it in the same way as C. In the end, judge whether children is empty, process the original value in children and create a virtual text node, judge SVG below, and add namespace, addNS method above. Adding a namespace to a child node in SVG is implemented through a circular call to the addNS method, which is then returned through the vNode function

Vnode function

The vnode method is called at the end of the h function. Let’s look at the vnode method

import {Hooks} from './hooks';
import {AttachData} from './helpers/attachto'
import {VNodeStyle} from './modules/style'
import {On} from './modules/eventlisteners'
import {Attrs} from './modules/attributes'
import {Classes} from './modules/class'
import {Props} from './modules/props'
import {Dataset} from './modules/dataset'
import {Hero} from './modules/hero'

export type Key = string | number;

export interface VNode {
  / / selector
  sel: string | undefined;
  // Node data: properties/styles/events
  data: VNodeData | undefined;
  // Child node, mutually exclusive with text
  children: Array<VNode | string> | undefined;
  // Record the actual Dom corresponding to the vNode
  elm: Node | undefined;
  // The contents of the node are mutually exclusive with children
  text: string | undefined;
  / / optimization
  key: Key | undefined;
}

exportinterface VNodeData { props? : Props; attrs? : Attrs;class? :Classes; style? : VNodeStyle; dataset? : Dataset; on? : On; hero? : Hero; attachData? : AttachData; hook? : Hooks; key? : Key; ns? : string;// for SVGsfn? :() = > VNode; // for thunksargs? :Array<any>; // for thunks
  [key: string]: any; // for any other 3rd party module
}

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

export default vnode;

Copy the code

The corresponding module file is referenced in this method, and then two interfaces, VNode and VNodeData, are defined. VNode is used to restrict objects to have the same properties, including the selector, node data, child nodes, the corresponding real DOM of VNode, node content, and optimized key. VNodeData is the relevant parameter required in the module. In the following VNode method, 5 parameters are passed. The final key parameter is declared as data, and the six parameter values are returned as objects

The init function

Since the patch function is created through the init function, let’s first look at the init function

In init, we pass in two parameters, the second parameter is optional, which is used to convert the API of the virtual node. Firstly, we collect the hooks in the module and save them to CBS, where CBS is the corresponding hook function in the module. Then we define some auxiliary functions internally, and finally return a patch function. The two parameters are the old node and the new node.

The patch function

Since the version we learned is 0.7.4, the patch function is defined in snabbdom.ts, and the higher version may be in init.ts

The patch function is used to compare the surprise between two VNodes, and the comparison process is as follows:

Compare whether the old and new VNodes are the same (the key and SEL of the nodes are the same). If they are not the same, delete the previous content and re-render. If they are the same, then determine whether the new Vnode has text. If the new Vnode has children, the diff algorithm is used to determine whether the child node has changed. Diff algorithm only performs peer comparisonCopy the code

Let’s take a look at the patch function

// init returns the patch function inside, renders the VNode into a real DOM, and returns the vnode
  return function patch(oldVnode: VNode | Element, vnode: VNode) :VNode {
    let i: number, elm: Node, parent: Node;
    // Save the queue of newly inserted nodes in order to trigger the hook function
    const insertedVnodeQueue: VNodeQueue = [];
    // Execute the pre hook function
    for (i = 0; i < cbs.pre.length; ++i) cbs.pre[i]();
    // oldVnode is not VNode, create VNode, and set elm
    if(! isVnode(oldVnode)) { oldVnode = emptyNodeAt(oldVnode); }// If the new and old nodes are the same node (key and SEL are the same)
    if (sameVnode(oldVnode, vnode)) {
      // Find the node differences and update the DOM
      patchVnode(oldVnode, vnode, insertedVnodeQueue);
    } else {
      // If the new node is different from the old one, create the corresponding DOM
      // Get the current DOM element
      elm = oldVnode.elm as Node;
      parent = api.parentNode(elm);
      // Create the corresponding VNode DOM element and trigger the init/create hook function
      createElm(vnode, insertedVnodeQueue);

      if(parent ! = =null) {
        // The parent node is not empty. Insert the dom corresponding to the vnode into the document
        api.insertBefore(parent, vnode.elm as Node, api.nextSibling(elm));
        // Remove the old node
        removeVnodes(parent, [oldVnode], 0.0); }}// Execute the user-set insert hook function
    for (i = 0; i < insertedVnodeQueue.length; ++i) {
      (((insertedVnodeQueue[i].data as VNodeData).hook as Hooks).insert as any)(insertedVnodeQueue[i]);
    }
    // Execute the module's POST hook function
    for (i = 0; i < cbs.post.length; ++i) cbs.post[i]();
    return vnode;
  };
  
  function emptyNodeAt(elm: Element) {
    const id = elm.id ? The '#' + elm.id : ' ';
    const c = elm.className ? '. ' + elm.className.split(' ').join('. ') : ' ';
    return vnode(api.tagName(elm).toLowerCase() + id + c, {}, [], undefined, elm);
  }
  
  function sameVnode(vnode1: VNode, vnode2: VNode) :boolean {
    return vnode1.key === vnode2.key && vnode1.sel === vnode2.sel;
  }
Copy the code

Patch is returned by init function. In patch function, module’s Pre hook is called first, and then it checks whether the first parameter passed is of type VNode. If not, emptyNodeAt is called and converted to a Vnode. The implementation of emptyNodeAt is also very simple. Note that it only preserves class and style. This is a bit different from the toVnode implementation because it does not need to store much information, such as prop Attribute, etc. Then call sameVnode to determine whether it is the sameVnode node, the specific implementation is also very simple, here just determine whether the key and sel are the same. If they are the same, patchVnode is called, if not, createElm is called to create a new DOM node, then if there is a parent node, it is inserted into the DOM, and the old DOM node is removed to complete the update. Finally, insert hooks on elements and post hooks on modules are called. The focus here is on patchVnode and createElm. Let’s first look at createElm to see how the DOM node is created.

CreateElm function

function createElm(vnode: VNode, insertedVnodeQueue: VNodeQueue) :Node {
    let i: any, data = vnode.data;
    if(data ! = =undefined) {
      // Execute the user-set init hook function
      if(isDef(i = data.hook) && isDef(i = i.init)) { i(vnode); data = vnode.data; }}// Convert vNodes to real DOM objects (not rendered to the page)
    let children = vnode.children, sel = vnode.sel;
    if (sel === '! ') {
      / /! Creating a comment node
      if (isUndef(vnode.text)) {
        vnode.text = ' ';
      }
      vnode.elm = api.createComment(vnode.text as string);
    } else if(sel ! = =undefined) {
      // The selector is not empty
      // Parse the selector
      // Parse selector
      const hashIdx = sel.indexOf(The '#');
      const dotIdx = sel.indexOf('. ', hashIdx);
      const hash = hashIdx > 0 ? hashIdx : sel.length;
      const dot = dotIdx > 0 ? dotIdx : sel.length;
      consttag = hashIdx ! = = -1|| dotIdx ! = = -1 ? sel.slice(0.Math.min(hash, dot)) : sel;
      const elm = vnode.elm = isDef(data) && isDef(i = (data as VNodeData).ns) ? api.createElementNS(i, tag)
                                                                               : api.createElement(tag);
      if (hash < dot) elm.setAttribute('id', sel.slice(hash + 1, dot));
      if (dotIdx > 0) elm.setAttribute('class', sel.slice(dot + 1).replace(/\./g.' '));
      // Execute the module's CREATE hook function
      for (i = 0; i < cbs.create.length; ++i) cbs.create[i](emptyNode, vnode);
      // If there are child nodes in the vNode, create the dom element corresponding to the child vnode and append it to the DOM tree
      if (is.array(children)) {
        for (i = 0; i < children.length; ++i) {
          const ch = children[i];
          if(ch ! =null) {
            api.appendChild(elm, createElm(ch asVNode, insertedVnodeQueue)); }}}else if (is.primitive(vnode.text)) {
        // Vnode text is string/number, create a text node and append to the DOM tree
        api.appendChild(elm, api.createTextNode(vnode.text));
      }
      i = (vnode.data as VNodeData).hook; // Reuse variable
      if (isDef(i)) {
        // Execute the user passed hook create
        if (i.create) i.create(emptyNode, vnode);
        // Add the vNode to the queue in preparation for the insert hook
        if(i.insert) insertedVnodeQueue.push(vnode); }}else {
      vnode.elm = api.createTextNode(vnode.text as string);
    }

    // Returns the newly created DOM
    return vnode.elm;
  }
Copy the code

As you can see from the mind map and code, the element’s init hook is called first, and then there are three cases:

If the current element is a comment node, createComment is called to create a comment node, which is then mounted to vNode.elm

If there is no selector and just plain text, call createTextNode to create the text and mount it to vNode.elm

If there is a selector, the selector is parsed to get tag, ID, and class, and then createElement or createElementNS is called to generate the node and mount it to vNode.elm. Call create hook on Module, if there are children, iterate over all child nodes and create dom recursively with createElm. Mount the DOM to the current ELM through appendChild. If no children exists but text does, create text using createTextNode. Finally call create hook on the calling element and vNode that holds the Insert hook, because the insert hook will not be called until the DOM is actually mounted on the document. Using an array saves you from having to traverse the vNode tree when you actually need to call it.

AddVnodes and removeVnodes

function addVnodes(parentElm: Node, before: Node | null, vnodes: Array<VNode>, startIdx: number, endIdx: number, insertedVnodeQueue: VNodeQueue) {
  for (; startIdx <= endIdx; ++startIdx) {
    const ch = vnodes[startIdx];
    if(ch ! =null) { api.insertBefore(parentElm, createElm(ch, insertedVnodeQueue), before); }}}function removeVnodes(parentElm: Node, vnodes: Array<VNode>, startIdx: number, endIdx: number) :void {
  for (; startIdx <= endIdx; ++startIdx) {
    let i: any, listeners: number, rm: () = > void, ch = vnodes[startIdx];
    if(ch ! =null) {
      if (isDef(ch.sel)) {
        // Call destory hook
        invokeDestroyHook(ch);
        // Count the number of times you need to call removecallBack before removing the DOM
        listeners = cbs.remove.length + 1;
        rm = createRmCb(ch.elm as Node, listeners);
        // Call module is remove hook
        for (i = 0; i < cbs.remove.length; ++i) cbs.remove[i](ch, rm);
        // Call vnode's remove hook
        if (isDef(i = ch.data) && isDef(i = i.hook) && isDef(i = i.remove)) {
          i(ch, rm);
        } else{ rm(); }}else { // Text node
        api.removeChild(parentElm, ch.elm asNode); }}}}// Call destory hook
// If there is a recursive call to children
function invokeDestroyHook(vnode: VNode) {
  let i: any, j: number, data = vnode.data;
  if(data ! = =undefined) {
    if (isDef(i = data.hook) && isDef(i = i.destroy)) i(vnode);
    for (i = 0; i < cbs.destroy.length; ++i) cbs.destroy[i](vnode);
    if(vnode.children ! = =undefined) {
      for (j = 0; j < vnode.children.length; ++j) {
        i = vnode.children[j];
        if(i ! =null && typeofi ! = ="string") {
          invokeDestroyHook(i);
        }
      }
    }
  }
}

// The DOM will be removed only if all remove hooks have called remove callback
function createRmCb(childElm: Node, listeners: number) {
  return function rmCb() {
    if (--listeners === 0) {
      constparent = api.parentNode(childElm); api.removeChild(parent, childElm); }}; }Copy the code

These two functions are used to add and remove vNodes

patchVnode

What this function does is diff the two vNodes passed in, and if there are any updates, feed them back to the DOM.

Call the prepatch hook on the vNode first, and return if the two vNodes are identical. Then call the Update hooks on module and VNode. Then will be divided into the following cases to do processing:

If the old vnode has text, clear it first. If the old vnode has text, clear it first. Then call addVnodes, the new vnode does not have children, call removeVnodes to remove children, and the new vnode does not have text. Remove old vNode text exists text, update text ‘

updateChildren

function updateChildren(parentElm: Node, oldCh: Array<VNode>, newCh: Array<VNode>, insertedVnodeQueue: VNodeQueue) {
  let oldStartIdx = 0,
    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: any;
  let idxInOld: number;
  let elmToMove: VNode;
  let before: any;

  // Walk through oldCh newCh to compare and update the nodes
  // A maximum of one node can be processed in each round of comparison. The algorithm complexity is O(n).
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    // If there are empty nodes among the four nodes being compared, the index of the empty node is advanced to the middle, and the next loop continues
    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];
      // The old and new start nodes are the same, directly call patchVnode to update, subscript to the middle
    } else if (sameVnode(oldStartVnode, newStartVnode)) {
      patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue);
      oldStartVnode = oldCh[++oldStartIdx];
      newStartVnode = newCh[++newStartIdx];
      // Same logic as above
    } else if (sameVnode(oldEndVnode, newEndVnode)) {
      patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue);
      oldEndVnode = oldCh[--oldEndIdx];
      newEndVnode = newCh[--newEndIdx];
      // The old start node is equal to the new node node, indicating that the node is moved to the right. Call patchVnode to update
    } else if (sameVnode(oldStartVnode, newEndVnode)) {
      // Vnode moved right
      patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue);
      // The old start node equals the new end node, indicating that the node has been moved to the right
      Since the new node is at the end, it is added after the old end node (which moves to the left with updateChildren)
      // Note that the DOM needs to be moved because the node is moved to the right. Why insert it after oldEndVnode?
      // Can be divided into two cases:
      // 1. When the loop starts, the index has not moved, so it is reasonable to move to the end of oldEndVnode
      // 2. Part of the loop has already been executed, because each comparison ends with the index moving towards the center and one node at a time,
      // Now that the left and right sides of the subscript have been processed, we can treat the start to end area of the subscript as a whole that has not started the loop.
      // So it makes sense to insert after oldEndVnode (for the current loop, also the very last, same as 1)
      api.insertBefore(parentElm, oldStartVnode.elm as Node, api.nextSibling(oldEndVnode.elm as Node));
      oldStartVnode = oldCh[++oldStartIdx];
      newEndVnode = newCh[--newEndIdx];
      // The old end node equals the new start node, indicating that the node is moved to the left
    } else if (sameVnode(oldEndVnode, newStartVnode)) {
      // Vnode moved left
      patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue);
      api.insertBefore(parentElm, oldEndVnode.elm as Node, oldStartVnode.elm as Node);
      oldEndVnode = oldCh[--oldEndIdx];
      newStartVnode = newCh[++newStartIdx];
      // If none of the above four conditions match, the following two conditions may exist
      // 1. This node is newly created
      // 2. This node is in the middle of the original position (oldStartIdx and endStartIdx)
    } else {
      // If oldKeyToIdx does not exist, create a key-to-index mapping
      // There are also all sorts of subtle optimizations that are created only once, and no mapping is required for what is already done
      if (oldKeyToIdx === undefined) {
        oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
      }
      // get the corresponding index under oldCh
      idxInOld = oldKeyToIdx[newStartVnode.key as string];
      // If the subscript does not exist, the node is newly created
      if (isUndef(idxInOld)) {
        // New element
        // Insert in front of oldStartVnode (for the current loop, the first)
        api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm as Node);
        newStartVnode = newCh[++newStartIdx];
      } else {
        // Find the node that needs to be moved if it is an existing node
        elmToMove = oldCh[idxInOld];
        // The key is the same, but seletor is different. You need to call createElm to create a new DOM node
        if(elmToMove.sel ! == newStartVnode.sel) { api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elmas Node);
        } else {
          // Otherwise call patchVnode to update the old vnode
          patchVnode(elmToMove, newStartVnode, insertedVnodeQueue);
          // Empty the currently processed vNodes in oldCh and skip the next time the loop reaches this subscript
          oldCh[idxInOld] = undefined as any;
          // Insert in front of oldStartVnode (for the current loop, the first)
          api.insertBefore(parentElm, elmToMove.elm as Node, oldStartVnode.elm asNode); } newStartVnode = newCh[++newStartIdx]; }}}// After the loop ends, there are two possible scenarios
  // 1. OldCh is completely processed, newCh has new nodes, and a new DOM needs to be created for each remaining item
  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);
      // 2. NewCh has been processed completely, while oldCh still has old nodes, which need to be removed
    } else{ removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx); }}}Copy the code

In Update Dren, the DIFF algorithm is implemented, and here we mainly analyze the DIFF algorithm

Since we rarely move or update a parent node to a child node during DOM manipulation, we only need to compare nodes of the same class, which will optimize the time complexity

When comparing nodes of the same level, the beginning and end nodes of the new and old node arrays are first indexed, and the index is moved during traversal

When comparing the start and end nodes, four conditions occur

  1. OldStartVnode/newStartVnode (old start node/new start node)
  2. OldEndVnode/newEndVnode (old end node/new end node)
  3. OldStartVnode/oldEndVnode (old start node/new end node)
  4. OldEndVnode/newStartVnode (old end node/new start node)

When oldStartVnode and newStartVnode are compared, sameVnode will be called to determine whether they are the same node, that is, to compare key and SEL. If they are the same, patchVnode will be directly called to compare internal differences and update them into DOM. Then move the index to compare the next node; If the next node is not the same, oldEndVnode and newEndVnode will be compared. SameVnode will also be called to determine whether the same node is the same. Then patchVnode will be called to compare internal differences, update to DOM, and then move forward the index to compare the last node.

When oldStartVnode is compared with oldEndVnode, sameVnode is also called to determine whether it is the same node. If so, the old start node is moved to the last position, and the index of the old node is moved backward, and the index of the new node is moved forward to continue the comparison

When oldEndVnode is compared with newStartVnode, sameVnode is also called to determine whether it is the same node. If it is the same, the old start node is moved to the front, and the index of the old node is moved forward, and the index of the new node is moved backward to continue the comparison

If none of the above four conditions are satisfied:

Use newStartVnode to find the node with the same key value in the old node. If not, it means it is a new node. Create the corresponding DOM element and insert it into the front of the node array. Create the corresponding DOM element and insert it to the front of the node array. If a node with the same key is found and sel is the same, move the node directly to the front of the array

Finally, judge the number of old nodes and new nodes. If the number of new nodes > the number of old nodes, it indicates that the remaining nodes that have not been traversed are new nodes and are inserted to the end of the node array

If the number of new nodes is less than the number of old nodes, the remaining nodes that are not traversed are nodes that need to be deleted

That’s how the DIff algorithm works, as well as how update Dren works.

conclusion

The above is my understanding of snabbDOM. If there is something wrong, please point it out. Thank you