preface

Interviewer :” Do you know the Virtual DOM and Diff algorithm? Please describe them “;

Me: “well,… Goose, that “, finished 😰, suddenly IQ is not online, did not organize good language did not answer or root answer not come out;

So this time I summarize the relevant knowledge points, so that you can have a clear cognition will also let you in the future encounter this situation can be calm, to cope with the ease, with ease:

Related knowledge:

  • Virtual DOM (Virtual DOM) :

    • What is the virtual DOM

    • Why use the virtual DOM

    • Virtual DOM library

  • The DIFF algorithm:
    • SnabbDom source
      • The init function
      • H function
      • The patch function
      • PatchVnode function
      • UpdateChildren function

Virtual DOM (Virtual DOM)

What is the virtual DOM

To sum up, the virtual DOM is a javaScript object used to describe the real DOM. If this is not enough, let’s take 🌰: use code to describe the real DOM and the virtual DOM respectively

True DOM.

<ul class="list">
    <li>a</li>
    <li>b</li>
    <li>c</li>
</ul>
Copy the code

Corresponding virtual DOM:


let vnode = h('ul.list', [
  h('li'.'a'),
  h('li'.'b'),
  h('li'.'c'),])console.log(vnode)
Copy the code

The console printed it outVnode:

H function to generate the virtual DOM this JS object (Vnode) source:

export interfaceVNodeData { props? : Props attrs? : Attrsclass? :Classes
    style? :VNodeStyle
    dataset? :Dataset
    on? :On
    hero? :Hero
    attachData? :AttachData
    hook? :Hooks
    key? :Key
    ns? :string // for SVGs
    fn? : ()=> VNode // for thunksargs? :any[] // for thunks
    [key: string] :any // for any other 3rd party module
}

export type Key = string | number

const interface VNode = {
    sel: string | undefined./ / selector
    data: VNodeData | undefined.// VNodeData VNodeData defined above
    children: Array<VNode | string> | undefined.// Child node, mutually exclusive with text
    text: string | undefined.// The text content in the middle of the tag
    elm: Node | undefined.// The converted real DOM
    key: Key | undefined // A string or a number
}

Copy the code
Supplement:

The h function above may be a little familiar to you, but it didn’t come to mind for a while. It doesn’t matter. Let me help you remember; The render function is used to render common realistic scenes in development:

// Create a vue instance of main.js in the vue project
new Vue({
  router,
  store,
  render: h= > h(App)
}).$mount("#app");

// Use render for the list in case 2
columns: [
    {
        title: "Operation".key: "action".width: 150.render: (h, params) = > {
            return h('div', [
                h('Button', {
                    props: {
                        size: 'small'
                    },
                    style: {
                        marginRight: '5px'.marginBottom: '5px',},on: {
                        click: () = > {
                            this.toEdit(params.row.uuid); }}},'edit')]); }}]Copy the code

Why use the virtual DOM

  • The MVVM framework addresses view and state synchronization issues
  • The template engine can simplify view operations without being able to track state
  • The virtual DOM tracks state changes
  • Reference on makingvirtual-domMotivation description of
    • The virtual DOM can maintain the state of the program, keeping track of the last state
    • Update the real DOM by comparing the two states
  • Cross-platform use
    • Browser platforms render the DOM
    • The server side renders SSR(nuxt.js/Next-js) with vue direction on the front and React direction on the latter
    • Weex/React Native
    • Small programs (MPvue /uni-app), etc
  • The real DOM has many properties, and creating DOM nodes is expensive
  • The virtual DOM is just a normal JavaScript object that doesn’t require much to describe properties and is very cheap to create
  • Improve rendering performance in complex views (high performance costs for dom manipulation, performance can be improved by reducing the scope of DOM manipulation)

Soul asking questionsIs using the virtual DOM necessarily faster than rendering the real DOM? The answer, of course, isnoListen to me:

Example: DOMA->DOMB when a node changes

The above situation:Example 1Is to create aDOMBAnd then replace itDOMA; Example 2Go to theCreate virtual DOM+DIFF algorithmThan to findDOMBwithDOMAIt’s not the same node, so I’m going to create oneDOMBAnd then replace itDOMA; It is obvious that 1 is faster than 2. The same result is that 2 also needs to create the virtual DOM+DIFF calculationWrong or not precise

For example, when the contents of a child node in the DOM tree change:

When some complex nodes, such as a parent node with more than one child node, when the content of only one child node changes, then we do not need to likeExample 1Re-render thisThe DOM treeAt this timeVirtual DOM+DIFF algorithmWe can get a good representation of that. We passExample 2useVirtual DOM+Diff algorithmFind the child node that has changed and update its contents

Summary: Improve rendering performance in complex view cases, because virtual DOM+Diff algorithm can accurately find the DOM tree changes and reduce DOM operations (rearrangement and redrawing).

Virtual dom library

  • Snabbdom
    • The virtual DOM used internally in vue.js2. X is a modified Snabbdom
    • Approximately 200SLOC(single line of code)
    • Extensible through modules
    • Source code is developed using TypeScript
    • One of the fastest Virtual DOM
  • virtual-dom

The Diff algorithm

After reading the above article, I believe that you have a preliminary concept of Diff algorithm. Yes,Diff algorithm is actually to find the difference between the two;

Diff algorithm should first clarify a concept that the object of DIFF is the virtual DOM, and updating the real DOM is the result of DIFF algorithm.

Next I will tear the snabbdom source code core part for everyone to open the heart of Diff, give a little patience, do not close the page, I know you are like this:

The core of snabbdom

  • init()Set the modulepatch()function
  • useh()Function to create JavaScript objects(Vnode)describeReal DOM
  • patch()To compareThe two VNodes are old and new
  • Update the changes toReal DOM tree

The init function

Init function to set the module, and then create the patch() function, we first through the scenario case to have a visual representation:

import {init} from 'snabbdom/build/package/init.js'
import {h} from 'snabbdom/build/package/h.js'

// 1. Import modules
import {styleModule} from "snabbdom/build/package/modules/style";
import {eventListenersModule} from "snabbdom/build/package/modules/eventListeners";

// 2. Register module
const patch = init([
  styleModule,
  eventListenersModule
])

// 3. Pass the second argument to h() to the data (object) used in the module.
let vnode = h('div', [
  h('h1', {style: {backgroundColor: 'red'}}, 'Hello world'),
  h('p', {on: {click: eventHandler}}, 'Hello P')])function eventHandler() {
  alert('Hurt, don't touch me.')}const app = document.querySelector('#app')

patch(app,vnode)
Copy the code

When init uses imported modules, it can create virtual DOM(Vnode) objects using the API provided by those modules in function H; Above, the style module and event module are used to make the virtual DOM created with style attributes and event attributes. Finally, the patch function is used to compare the two virtual DOM (the APP will be converted into the virtual DOM first) and update the view.

Let’s briefly look at the source code for init:

// src/package/init.ts
/* The first parameter is the module and the second parameter is the DOMAPI, which can convert the DOM to the API of other platforms. Init is a higher-order function. One function returns another function. It can cache modules and domApi arguments. OldValue and newValue(vnode) will be passed */
export function init (modules: Array<Partial<Module>>, domApi? : DOMAPI) {...return function patch (oldVnode: VNode | Element, vnode: VNode) :VNode {}}Copy the code

H function

CreateElement (createElement, createElement, createElement); createElement (createElement, createElement); createElement (createElement, createElement, createElement);

/ / h function
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 {
  var data: VNodeData = {}
  var children: any
  var text: any
  var i: number.return vnode(sel, data, children, text, undefined) // Finally return onevnodeFunction};
Copy the code
/ / vnode function
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 } // Finally generate the Vnode object
}
Copy the code

Summary: The h function is a vNode function, and the vNode function is regenerated into a VNode object (virtual DOM object).

Supplement:

In the h function source section involves a function overload concept, a brief explanation:

  • Functions with different number or type of arguments ()
  • There is no concept of overloading in JavaScript
  • Overloading exists in TypeScript, but overloading is implemented by adjusting parameters in code

The concept of overloading has nothing to do with the return value

  • Example 1(Function overload – Number of arguments)

function add(a:number,b:number){

console.log(a+b)

}

function add(a:number,b:number,c:number){

console.log(a+b+c)

}

add(1.2)

add(1.2.3)

Copy the code
  • Example 2(Function overloading – Parameter type)

function add(a:number,b:number){

console.log(a+b)

}

function add(a:number,b:string){

console.log(a+b)

}

add(1.2)

add(1.'2')

Copy the code

Patch function (core)

If you look at the front of the paving, see here you may be distracted, wake up ah, this is the core ah, up high brother;

  • pactch(oldVnode,newVnode)
  • Render the changing contents of the new node into the real DOM and return the new node as the old node for the next processing (core)
  • Comparing the old and newVNodeWhether the node is the same (the key and SEL of the node are the same)
  • If it is not the same node, delete the previous content and re-render
  • If the nodes are the same, determine a new oneVNodeIs there atextIf you have and andoldVnodethetextInstead of updating text content directly(patchVnode)
  • If the new VNode has children, check whether the children have changed(updateChildren, the most difficult and most difficult to implement)

Source:

return function patch(oldVnode: VNode | Element, vnode: VNode) :VNode {    
    let i: number, elm: Node, parent: Node
    const insertedVnodeQueue: VNodeQueue = []
    // cbs.pre is a set of pre hook functions for all modules
    for (i = 0; i < cbs.pre.length; ++i) cbs.pre[i]()
    The isVnode function checks whether oldVnode is a virtual DOM object
    if(! isVnode(oldVnode)) {// If not, convert Element to a virtual DOM object
        oldVnode = emptyNodeAt(oldVnode)
    }
    // The sameVnode function is used to determine whether two virtual DOM are the same.
    if (sameVnode(oldVnode, vnode)) {
        // Run patchVnode to compare the two nodes, which will be explained later (core)
        patchVnode(oldVnode, vnode, insertedVnodeQueue)
    } else {
        elm = oldVnode.elm! / /! OldVnode. Elm must have a value
        // parentNode gets the parent element
        parent = api.parentNode(elm) as Node

        // createElm is used to create a DOM element to insert into the vNode (new virtual DOM).
        createElm(vnode, insertedVnodeQueue)

        if(parent ! = =null) {
            // Insert the DOM element into the parent element and delete the old DOMapi.insertBefore(parent, vnode.elm! , api.nextSibling(elm))// Place the newly created element after the old DOM
            removeVnodes(parent, [oldVnode], 0.0)}}for (i = 0; i < insertedVnodeQueue.length; ++i) { insertedVnodeQueue[i].data! .hook! .insert! (insertedVnodeQueue[i]) }for (i = 0; i < cbs.post.length; ++i) cbs.post[i]()
    return vnode
}
Copy the code

Add 1: sameVnode function

function sameVnode(vnode1: VNode, vnode2: VNode) :boolean {Check whether the node is the same by key and SEL selectorsreturn vnode1.key === vnode2.key && vnode1.sel === vnode2.sel
}
Copy the code

patchVnode

  • Stage one triggerprepatchFunction andupdateFunction (both trigger prepatch, update only if they are not identical)
  • The second stage is to really compare the old and the newvnodeAreas of difference
  • Stage three, triggeringpostpatchFunction update node

Source:

function patchVnode(oldVnode: VNode, vnode: VNode, insertedVnodeQueue: VNodeQueue) {
    consthook = vnode.data? .hook hook? .prepatch? .(oldVnode, vnode)const elm = vnode.elm = oldVnode.elm!
    const oldCh = oldVnode.children as VNode[]
    const ch = vnode.children as VNode[]
    if (oldVnode === vnode) return
    if(vnode.data ! = =undefined) {
        for (let i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode) vnode.data.hook? .update? .(oldVnode, vnode) }if (isUndef(vnode.text)) { // The text attribute of the new node is undefined
        if (isDef(oldCh) && isDef(ch)) { // When both old and new nodes have children
            if(oldCh ! == ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue)// And their children execute the updateChildren function differently, which will be highlighted later (core)
        } else if (isDef(ch)) { // Only new nodes have children
            // When the old node has a text attribute, the "" is assigned to the real DOM's text attribute
            if (isDef(oldVnode.text)) api.setTextContent(elm, ' ') 
            // Insert all children of the new node into the real DOM
            addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
        } else if (isDef(oldCh)) { // Clear all children of the real DOM
            removeVnodes(elm, oldCh, 0, oldCh.length - 1)}else if (isDef(oldVnode.text)) { // Assign "to the text property of the real DOM
            api.setTextContent(elm, ' ')}}else if(oldVnode.text ! == vnode.text) {// If the text of the old node is different from that of the new node
        if (isDef(oldCh)) { // If the old node has child nodes, delete all child nodes
            removeVnodes(elm, oldCh, 0, oldCh.length - 1)
        }
        api.setTextContent(elm, vnode.text!) // Assign the text of the new node to the real DOM} hook? .postpatch? .(oldVnode, vnode)// Update the view
}
Copy the code

This may be a bit confusing, but here’s another mind map:

Off topic: An introduction to the Diff algorithm

Traditional DIff algorithm

  • Diff algorithm in the virtual DOM
  • Traditional algorithmFind the difference between each node of the two trees
  • N1 (number of dom1 nodes)*n2(number of dom2 nodes) will be run to compare, and the difference will be found and then updated

Snabbdom diff algorithm optimization

  • Snbbdom does the traditional DIff algorithm according to the characteristics of DOMTo optimize the
  • DOM manipulation rarely involves cross-level manipulation of nodes
  • Only compareThe same levelThe nodes of the

Now we will introduce how the updateChildren function compares the differences and similarities of child nodes, which is a core and difficult part of the Diff algorithm.

UpdateChildren (kernel within kernel: Determine differences between child nodes)

  • I’ve divided this function into three parts,Part 1: Declaring variables.Part 2: Comparison of nodes of the same level.Part 3: Finishing the loop(see below);

  • Compare nodes of the same leveltheFive kinds ofSituation:
    1. oldStartVnode/newStartVnode(Old start node/new start node) same
    2. oldEndVnode/newEndVnode(Old end node/new end node) same
    3. oldStartVnode/newEndVnodeSame as (old start node/new end node)
    4. oldEndVnode/newStartVnode(Old end node/new start node) same
    5. The special case is one, two, three, fourWill be executed whenoldVnodesLook insidenewStartVnodeThe same node and then shifted tooldStartVnodeIf not found in theoldStartVnodeTo create a
  • The execution process is a loop in which one of the above five situations is executed to complete the loop
  • The finishing touches at the end of the cycle: until oldStartIdx > oldEndIdx | | newStartIdx > newEndIdx (on behalf of the old or new nodes have finished traversal)

For a more intuitive understanding, let’s look at the implementation details of the five cases in which nodes of the same level are compared:

New start node and old Start node (Case 1)

  • ifCase 1 matches :(start from the start node of the old and new nodes.OldCh [oldStartIdx] and newCh [newStartIdx]forSameVnode (same key as SEL)Check whether the node is the same)
  • executepatchVnodeFind the difference between the two and update the graph; If there is no difference, do nothing and end the loop, okay
  • oldStartIdx++/newStartIdx++

New and old end nodes (Case 2)

  • ifCase 1 does not matchWill judgeCase 2, if :(starting from the end node of the old and new nodes,OldCh [oldEndIdx] and newCh [newEndIdx]Compare, executeSameVnode (same key as SEL)Check whether the node is the same)
  • performpatchVnodeFind the differences between the two and update the view; If there is no difference, do nothing and end the loop, okay
  • oldEndIdx--/newEndIdx--

Old start node/New end node (Case 3)

  • ifCase 1, 2,Case 3:(the start node of the old node is compared with the end node of the new node,OldCh [oldStartIdx] and newCh [newEndIdx]Compare, executeSameVnode (same key as SEL)Check whether the node is the same)
  • performpatchVnodeFind the differences between the two, update the view, and if there are no differences, do nothing, end the loop, okay
  • OldCh [oldStartIdx] corresponds to the real DOMDisplacement toOldCh [oldEndIdx] corresponds to the real DOMafter
  • oldStartIdx++/newEndIdx--;

Old End node/New start node (Case 4)

  • ifCase 1, 2, 3Case 4:(the end node of the old node is compared with the start node of the new node,OldCh [oldEndIdx] and newCh [newStartIdx]Compare, executeSameVnode (same key as SEL)Check whether the node is the same)
  • performpatchVnodeFind the differences between the two, update the view, and if there are no differences, do nothing, end the loop, okay
  • OldCh [oldEndIdx] corresponds to the real DOMDisplacement toOldCh [oldStartIdx] corresponds to the real DOMbefore
  • oldEndIdx--/newStartIdx++;

Find node in new start node/old node array (Case 5)

  • Look inside the old node, if you find andnewCh[newStartIdx]The same node (and calledCorresponding node [1]), the implementation ofpatchVnodeFind the differences between the two, update the view, and if there are no differences, do nothing, end the loop, okay
  • The actual DOM corresponding to the node [1]Displacement toOldCh [oldStartIdx] corresponds to the real DOMbefore

  • If the same node is not found, creates an andnewCh[newStartIdx]Node correspondingReal domInserted into theOldCh [oldStartIdx] corresponds to the real DOMbefore
  • newStartIdx++

Below we will introduce the end of cycle finishing touches (oldStartIdx > oldEndIdx | | newStartIdx > newEndIdx) :

  • All children of the new nodeFirst walk through (newStartIdx>newEndIdx), the loop ends
  • All children of the new nodeThe end of the traversal is to take the nodes that do not correspond to the same nodeChild nodesdelete

  • All children of the old nodeFirst walk through (oldStartIdx>oldEndIdx), the loop ends
  • All children of the old nodeThe end of the traversal is the extraChild nodesInserted into theThe old node ends the nodeThe former; (source:newCh[newEndIdx + 1].elm)Theta is the corresponding thetaThe real DOM of the old end nodeNewEndIdx +1 because we need -1 to match the same node, so we need to add it back to the end node

Finally, attached source code:

function updateChildren(parentElm, oldCh, newCh, insertedVnodeQueue) {
    let oldStartIdx = 0;                // The old node starts the node index
    let newStartIdx = 0;                // The new node starts the node index
    let oldEndIdx = oldCh.length - 1;   // The old node ends the node index
    let oldStartVnode = oldCh[0];       // The old node starts the node
    let oldEndVnode = oldCh[oldEndIdx]; // The old node ends the node
    let newEndIdx = newCh.length - 1;   // The new node ends the node index
    let newStartVnode = newCh[0];       // The new node starts the node
    let newEndVnode = newCh[newEndIdx]; // The new node ends the node
    let oldKeyToIdx;                    // Node movement is related
    let idxInOld;                       // Node movement is related
    let elmToMove;                      // Node movement is related
    let before;


    // Compare nodes of the same level
    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)) { // Check case 1
            patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue);
            oldStartVnode = oldCh[++oldStartIdx];
            newStartVnode = newCh[++newStartIdx];
        }
        else if (sameVnode(oldEndVnode, newEndVnode)) {   / / 2
            patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue);
            oldEndVnode = oldCh[--oldEndIdx];
            newEndVnode = newCh[--newEndIdx];
        }
        else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode Moved Right case 3
            patchVnode(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 Left Case 4
            patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue);
            api.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm);
            oldEndVnode = oldCh[--oldEndIdx];
            newStartVnode = newCh[++newStartIdx];
        }
        else {                                             / / 5
            if (oldKeyToIdx === undefined) {
                oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
            }
            idxInOld = oldKeyToIdx[newStartVnode.key];
            if (isUndef(idxInOld)) { // New element // Create a New node before the New node of the old node
                api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm);
            }
            else {
                elmToMove = oldCh[idxInOld];
                if(elmToMove.sel ! == newStartVnode.sel) {// Create a new node before the new node of the old node
                    api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm);
                }
                else {
                                                           // Find the same node in the old node array, compare the differences and update the view, then move the position
                    patchVnode(elmToMove, newStartVnode, insertedVnodeQueue);
                    oldCh[idxInOld] = undefined; api.insertBefore(parentElm, elmToMove.elm, oldStartVnode.elm); } } newStartVnode = newCh[++newStartIdx]; }}// Wrap up the loop
    if (oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx) {
        if (oldStartIdx > oldEndIdx) {
            // newCh[newEndIdx + 1]. Elm is the dom element corresponding to the end node in the old node array
            // newEndIdx+1 because newEndIdx needed -1 successfully earlier
            // newCh[newEndIdx + 1].elm (oldCh[oldEndIdx + 1].elm)
            before = newCh[newEndIdx + 1] = =null ? null : newCh[newEndIdx + 1].elm;
            // Insert the extra nodes in the new node array before
            addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx, insertedVnodeQueue);
        }
        else {
            // Delete nodes that do not match the same noderemoveVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx); }}}Copy the code

The key role

  • The Diff operation doesMore quickly;
  • Diff operation can be more accurate;(Avoid rendering errors)
  • Indexes are not recommendedAs a key

Let’s look at some examples of these effects:

Diff operation can be more accurate;(Avoid rendering errors):

Example: insert a z element between B and C of dom elements A, B, and C

No key setWhen key is set:

Diff operation can be more accurate;(Avoid rendering errors)

Example :a, B,c three DOM elements, modify an attribute of a element and add a new z element in front of a element

No key set:

A ->z(b->a,c->b,d-> C),b->a (c->b), d-> C (D -> C), c-> c (d-> C), c-> C (d-> C), c-> C (d-> C), d-> C (d-> C) Add a DOM element with text D at the end

Set the key:

When the key is set,a, B, C, and D all have corresponding keys,a->a,b-> B, C -> C, and D -> D. The content is the same without updating, and a DOM element whose text is Z is added at the end of traversal

Indexes are not recommendedAs a key:

Set index to key:

This is not efficient, we only want to find different nodes to update, and using the index as the key will increase the computation time, we can set the key to be consistent with the node text to solve this problem:

The last

If the description is wrong or unclear, please contact me in the comments below, I will update immediately, if there is a harvest, please give me a thumbs-up πŸ‘, this is a great support for me, thank you