Reach &&vue virtualdom’s Diff algorithm unification path snabbdom.js interpretation

  diff, javascript, react.js, vue.js

VirtualDOM is an important optimization scheme made by react for the performance bottleneck of DOM rearranging and redrawing under the component development scenario. Its most valuable core function is how to identify and save the differences between the new and old node data structures, namely diff algorithm. There is no doubt that the complexity and efficiency of diff algorithm are the key factors that determine the performance improvement effect of VirtualDOM. Therefore, after the VirtualDOM scheme was put forward, the community has continuously emerged with improved algorithms for diff, citing Stuart Zhengmei’s classic introduction:

At first, the classic depth-first traversal DFS algorithm has a complexity of o (n 3) and has a high diff cost. then, cito.js was born. it will have a significant impact on all future algorithms of virtual DOM. It uses the algorithm of comparing the two ends at the same time to raise diff speed to several levels. This is followed by kivi.js, which proposes two optimization schemes based on cito.js. key is used to realize movement tracking and key-based editing length distance algorithm application (algorithm complexity is O (n 2)). However, this diff algorithm is too complicated, so the successor snabbdom simplified kivi.js, removed the edit length distance algorithm and adjusted the two-end comparison algorithm. The speed is slightly lost, but the readability is greatly improved. After that, the famous vue2.0 integrated snabbdom’s entire library.

Therefore, the mainstream diff algorithm of VirtualDOM tends to be consistent at present. In the main diff idea, snabbdom and react have basically the same reconilation method.

Virtual dom central idea

If you don’t understand the idea of building virtual dom, you can refer to this exquisite article, Boxing Reach Down to A Feelings in jQuery.
The way to optimize the development of virtual dom is to realize stateless components through vnode, and to update UI in combination with undirectional data flow. The overall code structure is as follows:

var newVnode = render(vnode, state)
 var oldVnode = patch(oldVnode, newVnode)
 state.dispatch('change')
 var newVnode = render(vnode, state)
 var oldVnode = patch(oldVnode, newVnode)

Virtual dom library selection

Among many virtual dom libraries, we chose snabbdom library for many reasons:

1.snabbdom is ranked high in performance, although benchmark is not highly referenced
2。 Snabbdom is rich in examples.
3.snabbdom has a certain ecological circle, such as Motorcycle.js, Cycle-Snabbdom, Cerebral
4.snabbdom is very elegant to implement. It uses the recursive method to call patch. Compared with the code with obvious trace of infernojs optimization, snabbdom is more readable.
5. In the reading process, we found that snabbdom’s modularity and plug-in support are excellent.

How snabbdom Works

Let’s look at the basic usage of snabbdom.

// snabbdom in. /snabbdom.js
 var snabbdom = require('snabbdom')
 //initialize snabbdom to get patch.  Later, we can see the subtleties of snabbdom's design.
 var patch = snabbdom.init([
 require('snabbdom/modules/class'),
 require('snabbdom/modules/props'),
 require('snabbdom/modules/style'),
 require('snabbdom/modules/eventlisteners')
 ])
 // h is a wrapper function that generates vnode, factory mode?  A finer wrapper for generating vnode is to use jsx
 //in engineering, we usually use webpack or browserify to compile jsx.
 var h = require('snabbdom/h')
 //Construct a virtual dom. In practice, we usually want a stateless vnode
 //and we create vnode through state
 // react uses an object with the render method as a component that can accept props and state
 //In snabbdom, we can also achieve similar effects.
 // function component(state){return h(...)}
 var 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!  ')
 ]
 )
 //get the initial container, notice that the container is a dom element.
 var container = document.getElementById('container')
 //put vnode patch into container
 // patch function will process the first parameter. if the first parameter is not vnode, it will be wrapped as vnode.
 //after patch, vnode changed, representing the current state of virtual dom.
 patch(container, vnode)
 //Create a new vnode
 var newVnode =
 h(
 'div#container.two.classes',
 {on: {click: anotherEventHandler}},
 [
 h('span', {style: {fontWeight: 'normal', fontStyle: 'italics'}},
 'This is now italics'),
 ' and this is still just normal text',
 h('a', {props: {href: '/bar'}}, 'I\'ll take you places!  ')
 ]
 )
 //add a newVnode patch to vnode. now newvnode represents the status of vdom.
 patch(vnode, newVnode)

Definition of vnode

To read the vdom implementation, first make clear the definition of vnode

The definition of vnode is the attribute vnode has in./vnode.js.

1.tagName can be custom tag, can be’ div’,’span’,etc, which represents the tag name of this virtual dom.
2.data, virtual dom data, they are similar to the semantics of prop and attr of dom element. However, virtual dom can contain more flexible data.
For example, using the. /modules/class.js plug-in, we easily toggle a class name in data

h(‘p’, {class: {‘hide’: hideIntro}})

    • children,
      Children corresponding to element, but this is children of vdom. The implementation of vdom focuses on the patch for children.
    • Text, corresponding to element.textContent, defines a string in children, then we will create a textNode for this string
    • Elm, reference to dom element
    • Key, used to prompt the children patch process, which will be described in detail later.

    H parameter

    This is followed by the wrapping of the h function.

    H is implemented in./h.js.

    There are three points to note in the wrapper function

    • For svg packaging, creating svg requires namespace
    • Text into string type
    • Converts stringlelement in vdom.children to textNode

    Docking with dom api

    Implemented at. /htmldomapi.js

    Adapter mode is adopted to package dom api, and then htmldomapi is used as the default browser interface.
    This design is very clever. When extending the compatibility of snabbdom, only the browser interface used by snabbdom.init needs to be changed, and the implementation of methods such as patch does not need to be changed.

    Patch parsing of snabbdom

    The core content of snabbdom is implemented in./snabbdom.js. Snabbdom’s core implementation is less than 300 lines (233 sloc), very short.

    The virtual dom diff algorithm of snabbdom and the support of virtual dom lifecycle hook are implemented in snabbdom.
    virtual dom diff
    Vdom diff is the core algorithm of virtual dom, and the implementation principle of snabbdom is consistent with react official document Reconciliation.
    To sum up, there are:

    • The complexity of the two tree structures is increased to o (n 3) by performing complete diff and patch, which is almost unavailable.
    • Heuristic diff for two number structures will greatly save overhead.

    A well-read article React’s diff algorithm also illustrates the process of inspiration, but unfortunately there is no actual code reference. Now, let’s look at the application of heuristic rules according to snabbdom code. after the end, you will understand how simple the implementation of virtual dom is.

    First came the return statement of init function in snabbdom.js

    return function(oldVnode, vnode) {
     var i, elm, parent;
     // insertedVnodeQueue exists in the whole patch process
     //used to collect newly inserted vnode in patch
     var insertedVnodeQueue = [];
     //We need to run prepatch hook before proceeding with patch
     // cbs is the init function variable, that is, the closure of the function in this return statement
     //here, we ignore lifecycle hook and only focus on vdom diff algorithm.
     for (i = 0;   i < cbs.pre.length;   ++i) cbs.pre[i]();
     
     //if oldVnode is not vnode (oldVnode is dom element on the first call)
     //then use the emptyNodeAt function to wrap it as vnode
     if (isUndef(oldVnode.sel)) {
     oldVnode = emptyNodeAt(oldVnode);
     }
     
     // sameVnode is the core of the above "value is not worth patch"
     // sameVnode implementation is very simple, see if the key and sel of the two vnode are the same respectively.
     // ()=>{vnode1.key === vnode2.key && vnode1.sel === vnode2.
     //It is meaningless to compare semantically different structures, such as diff a' div' and' span'
     //instead, div should be removed and a new span inserted according to span vnode.
     // diff vnode with two different keys is also meaningless.
     //key is specified to distinguish element
     //for element with different keys, the data of oldVnode should not be changed according to newVnode.
     //Instead, remove the oldVnode and add the newVnode.
     if (sameVnode(oldVnode, vnode)) {
     // oldVnode and vnode have the same sel and key respectively, then the two vnode are worth comparing
     //patchVnode updates oldVnode according to vnode
     patchVnode(oldVnode, vnode, insertedVnodeQueue);
     } else {
     //If it is not worth going to patch, we will be violent.
     //remove oldVnode, create elm based on newVnode, and add to parent
     elm = oldVnode.elm;
     parent = api.parentNode(elm);
     
     //createlm creates element from vnode
     createElm(vnode, insertedVnodeQueue);
     
     if (parent !  == null) {
     //Add the newly created element to parent
     api.insertBefore(parent, vnode.elm, api.nextSibling(elm));
     //remove oldVnode at the same time
     removeVnodes(parent, [oldVnode], 0, 0);
     }
     }
     
     //After the end, call insert hook that inserts vnode.
     for (i = 0;   i < insertedVnodeQueue.length;  ++i) {
     insertedVnodeQueue[i].data.hook.insert(insertedVnodeQueue[i]);
     }
     
     //The whole patch ends, calling post hook in cbs
     for (i = 0;   i < cbs.post.length;   ++i) cbs.post[i]();
     return vnode;
     };
     ```
     
     # # # Then we read the patch process
     
     ```
     function patchVnode(oldVnode, vnode, insertedVnodeQueue) {
     var i, hook;
     //As before, the preptchhook is called before the patch, but this is the preptchhook defined by vnode in data, not the globally defined preptchhook.
     if (isDef(i = vnode.data) && isDef(hook = i.hook) && isDef(i = hook.prepatch)) {
     i(oldVnode, vnode);
     }
     
     var elm = vnode.elm = oldVnode.elm, oldCh = oldVnode.children, ch = vnode.children;
     
     //if oldVnode and vnode reference the same, there is no need to compare.  In a well-designed vdom, we execute this return statement most of the time.
     if (oldVnode === vnode) return;
     //If the two references are different, then the new vnode has been created
     //As before, let's first see if these two vnode values are worth patch.
     if (!  sameVnode(oldVnode, vnode)) {
     //Are these four statements the same as those in the init return function?
     var parentElm = api.parentNode(oldVnode.elm);
     elm = createElm(vnode, insertedVnodeQueue);
     api.insertBefore(parentElm, elm, oldVnode.elm);
     removeVnodes(parentElm, [oldVnode], 0, 0);
     return;
     }
     //These two vnode are worth going to patch
     //Let's patch vnode first. Patch's method is to call the global update hook first
     //then call update hook defined by vnode.data
     if (isDef(vnode.data)) {
     for (i = 0;   i < cbs.update.length;   ++i) cbs.update[i](oldVnode, vnode);
     i = vnode.data.hook;
     if (isDef(i) && isDef(i = i.update)) i(oldVnode, vnode);
     }
     // patch text and children of two vnode
     //view vnode.text definition
     // vdom stipulates that vnode with text attribute should not have children
     //a good way to write < p>foo:<b>123</b></p > is to
     //h ('p',' foo:', h ('b',' 123')) instead of
     // h('p', 'foo:', [h('b', '123')])
     if (isUndef(vnode.text)) {
     // vnode is not text node, let's see if they have children.
     if (isDef(oldCh) && isDef(ch)) {
     //both vnode have children, then updateChildren is called.
     if (oldCh !  == ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue);
     } else if (isDef(ch)) {
     //only the new vnode has children, then add children of vnode.
     if (isDef(oldVnode.text)) api.setTextContent(elm, '');
     addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue);
     } else if (isDef(oldCh)) {
     //only the old vnode has children, then remove oldCh
     removeVnodes(elm, oldCh, 0, oldCh.length - 1);
     } else if (isDef(oldVnode.text)) {
     //neither has children, and oldVnode.text is not empty, vnode.text is not defined, then elm.textContent is empty.
     api.setTextContent(elm, '');
     }
     } else if (oldVnode.text !  == vnode.text) {
     // vnode is a text node, we change the corresponding elm.textContent
     //Here we use api.setText api
     api.setTextContent(elm, vnode.text);
     }
     if (isDef(hook) && isDef(i = hook.postpatch)) {
     i(oldVnode, vnode);
     }
     }

    Is the implementation of patch simple and clear? Even think “ah? This is the patch over “feeling. Of course, we still have one more thing to do. This is the highlight-Update Children.

    Last reading updateChildren*

    UpdateChildren’s code is long and dense, but the algorithm is very simple.
    OldCh is a children array containing oldVnode, and newCh is the same.
    We first traverse two arrays (while statements) and maintain four variables.

    • Traversing the header index of oldCh-oldStartIdx
    • Traversing the tail index of oldCh-oldEndIdx
    • Traverse newCh’s header index-newStartIdx
    • The tail index of traversing newCh-newEndIdx

    Stop traversal when oldStartIdx > oldEndIdx or newStartIdx > newOldStartIdx.

    There are five comparisons in the traversal process
    The first four comparisons

    • OldStartVnode and newStartVnode, the relative positions of elm and newstartvnode are unchanged. if the sameVnode is compared, these two vnode are patch.
    • OldEndVnode and newEndVnode, the same as above, the relative position of elm is unchanged, and the same patch detection is performed.
    • OldStartVnode and newEndVnode. if oldStartVnode and newEndVnode are worth comparing, this–oldStartVnode.elm in oldCh has moved to the right. Then execute API. insertbefore (parentelm, oldstartvnode.elm, API. nextsibling (oldenvnode.elm)) to adjust its position.
    • OldEndVnode and newStartVnode are the same as above, but this is oldVnode.elm moving to the left and its position needs to be adjusted.

    The last comparison

    Using vnode.key, in the structure of ul>li*n, we are likely to use key to mark the uniqueness of li, then we will come to the last case. At this time, we first generate an index-key table (createKeyToOldIdx), and then make changes according to this table.

    Change rules

    If newVnode.key is not in the table, then this newVnode is the new vnode, insert it
    If the newVnode.key is in the table, then the corresponding oldvode exists. we need to patch the two vnodes, and after the patch, set the oldvode to undefined (oldch [idxinold] = undefined), and at the same time, transform the oldVnode.elm position to the current oldStartIdx, so as not to affect the next traversal.

    After the traversal, check the four variables, remove the remaining oldCh or add the remaining newCh
    Patch summary
    After reading the init function return statement, patch,updateChildren, we can understand the whole diff and patch process.

    Some functions createElm,removeVnodes are not important

    lifecycle hook

    After reading the implementation of the virtual dom diff algorithm, we may wonder, where is the patch about style, class, attr? These implementations are in modules and work through lifecycle.
    Snabbdom’s life cycle hook function is defined in core doc-hook.
    If you look at the class in modules again, you will find that the class module patch elm’s class through two hook hooks. The two hooks are create and update.
    Returning to the init function, these two hooks are registered at the beginning of the function body

    for (i = 0;   i < hooks.length;  ++i) {
     cbs[hooks[i]] = [];
     for (j = 0;   j < modules.length;  ++j) {
     if (modules[j][hooks[i]] !  == undefined)
     cbs[hooks[i]].push(modules[j][hooks[i]]);
     }
     }

    Create hook is called in createElm. Createlm is the only way to add vnode, so insertedVnodeQueue.push only occurs in createlm.