Deep into the virtual Dom and Vue2 Diff algorithm

This paper mainly analyzes Diff rules in Vue2 from the source layer. But before that, it’s worth reviewing the virtual Dom.

Virtual Dom concept

Virtual DOM (Virtual DOM) is a JS abstract representation of THE DOM. They are JS objects that describe the DOM structure and relationships. application

Various state changes in the virtual DOM are applied to the VIRTUAL DOM and eventually mapped to the DOM.

Here I have drawn a simple description of the relationship between the virtual Dom and the real Dom in Vue, as well as reactive data. We operate the responsive data to drive the virtual Dom through JS, and the virtual Dom generates the corresponding real Dom under the patch method. In Vue, virtual Dom is abstracted to perform update more efficiently, and patch layer can also perform compatibility and cross-platform processing according to different platforms.

In Vue, the minimum DOM operation can be obtained by comparing the old and new virtual DOM, and the asynchronous update strategy can reduce the refresh frequency to improve performance.

patch(vnode, h('div', obj.foo))
Copy the code

• Vue 1 has fine-grained data change detection that does not require a virtual DOM, but that fine-grained approach incurs a lot of overhead. Instead of using code names, Vue in this article refers to Vue2 versions.
• The virtual Dom in Vue is based on the SNabbDOM.

Patch

Let’s track how Vue operates when Dom/ component updates are made. For those unfamiliar with the Vue source directory and structure, check out my other article, “Preparation for Reading Vue source code.”

1. The patch is invoked

Find the component update lifecycle function and find where patch is called. The directory is SRC >core>instance>lifecycle. Js and you can see this code in vue.prototype. _update

const vm: Component = this const prevEl = vm.$el const prevVnode = vm._vnode const restoreActiveInstance = setActiveInstance(vm) vm._vnode = vnode // Vue.prototype.__patch__ is injected in entry points // based on the rendering backend used. if (! prevVnode) { // initial render vm.$el = vm.__patch__(vm.$el, vnode, hydrating, false /* removeOnly */) } else { // updates vm.$el = vm.__patch__(prevVnode, vnode) }Copy the code

Vm. __patch__ is the process of patch-making, using vm.__patch__ to get the real Dom node. Let’s dig deeper and take a look at where this __Patch__ method comes from. Earlier we said that __Patch__ is handled differently depending on the platform. It is easy to find in the SRC \ platforms \ web \ the index in the runtime js, Vue patches are being added to the prototype method.

import { patch } from './patch'
...
// install platform patch function
Vue.prototype.__patch__ = inBrowser ? patch : noop
Copy the code

At the same time, there is also a judgment of platform, if in the browser environment, it is patch.

2. The patch method is created

Directly into patch.js in the same directory, we find a factory function createPatchFunction.

import * as nodeOps from 'web/runtime/node-ops' import { createPatchFunction } from 'core/vdom/patch' import baseModules  from 'core/vdom/modules/index' import platformModules from 'web/runtime/modules/index' // the directive module should be applied last, after all // built-in modules have been applied. const modules = platformModules.concat(baseModules) export const patch:  Function = createPatchFunction({ nodeOps, modules })Copy the code

The createPatchFunction is used to pass in platform-specific node operations and attribute operations to get a platform-specific patch method. RemoveChild, removeChild, insertBefore, nextSibling…

3. Find where createPatchFunction is defined.

SRC \core\vdom\patch.js, this file has more than 800 lines and four core methods. SameVnode, sameInputType, createKeyToOldIdx and createPatchFunction.

Finally, the path method we get from the platform node operation is returned in createPatchFunction, around line 700.

return function patch (oldVnode, vnode, hydrating, removeOnly) {}
Copy the code

4. The realization of the patch

Enter the patch function and let’s see that the oldVnode and vnode parameters represent the old and new nodes respectively. Below I use a simple legend (added later) and a snippet of source code to correspond to the scene, making it easier to understand. I have added comments for key locations.

This. Patch (oldVnode, vnode) {exp1, exp2, vnode}} , so normally when we write new Vue(), we go where exp3 is.

The location of exp3 performs isRealElement judgment. If it is a real node, it goes through the initialization process. Since this is a process that is not part of dom Diff, we won’t go into depth here. Go directly to patchVnode. The patch operation is performed when both the old and new nodes exist.

// exp1: The new node does not exist, indicating that the node needs to be deleted. if (isUndef(vnode)) { if (isDef(oldVnode)) invokeDestroyHook(oldVnode); return; }Copy the code

// exp2: If the old node does not exist, create a node. if (isUndef(oldVnode)) { // empty mount (likely as component), create new root element isInitialPatch = true; createElm(vnode, insertedVnodeQueue); } else {// exp3: const isRealElement = isDef(oldvNode.nodeType);} else {// exp3: const isRealElement = isDef(oldvNode.nodeType); if (! isRealElement && sameVnode(oldVnode, vnode)) { // patch existing root node patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly); } else {// Initialize the real Dom node if (isRealElement) {if (oldvNode.nodeType === 1 && oldvNode.hasattribute (SSR_ATTR)) { oldVnode.removeAttribute(SSR_ATTR); hydrating = true; } if (isTrue(hydrating)) { if (hydrate(oldVnode, vnode, insertedVnodeQueue)) { invokeInsertHook(vnode, insertedVnodeQueue, true); return oldVnode; } else if (process.env.NODE_ENV ! == "production") { warn( "The client-side rendered virtual DOM tree is not matching " + "server-rendered content. This is likely caused by incorrect " + "HTML markup, for example nesting block-level elements inside " + "<p>, or missing <tbody>. Bailing hydration and performing " + "full client-side render." ); }} // Convert the real Dom to Vnode oldVnode = emptyNodeAt(oldVnode); } // replacing existing element const oldElm = oldVnode.elm; const parentElm = nodeOps.parentNode(oldElm); ParentElm createElm(vnode, insertedVnodeQueue, oldelm._leavecb? null : parentElm, nodeOps.nextSibling(oldElm) ); // update parent placeholder node element, recursively if (isDef(vnode.parent)) { let ancestor = vnode.parent; const patchable = isPatchable(vnode); while (ancestor) { for (let i = 0; i < cbs.destroy.length; ++i) { cbs.destroy[i](ancestor); } ancestor.elm = vnode.elm; if (patchable) { for (let i = 0; i < cbs.create.length; ++i) { cbs.create[i](emptyNode, ancestor); } // #6513 // invoke insert hooks that may have been merged by create hooks. // e.g. for directives that uses the "inserted" hook. const insert = ancestor.data.hook.insert; if (insert.merged) { // start at index 1 to avoid re-invoking component mounted hook for (let i = 1; i < insert.fns.length; i++) { insert.fns[i](); } } } else { registerRef(ancestor); } ancestor = ancestor.parent; } // destroy old node if (isDef(parentElm)) {removeVnodes([oldVnode], 0, 0); } else if (isDef(oldVnode.tag)) { invokeDestroyHook(oldVnode); }}}Copy the code

\

5. PatchVnode (Tree level Diff)

The patchVnode method is defined in patch.js. I will not post the entire source code here to save space. We directly put forward the key fragments in the patchVnode method for analysis. Skip some of the previous code on cache optimization and focus on the diff part.

  function patchVnode(
    oldVnode,
    vnode,
    insertedVnodeQueue,
    ownerArray,
    index,
    removeOnly
  ) { ... }
Copy the code

The role of patchVnode is to analyze the types of the current two nodes (oldVnode and VNode).

• If it is an element, update the attributes and attributes of both parties. Comparing the children of both sides at the same time, a recursive process called depth-first.
• If both sides are text, the text is updated directly

Get both children first, both of which are oldVnode and newVnode. The exp1 position, the code that compares the attributes of both parties is relatively simple in VUe2 and will be updated whether needed or not. Vue3 has made a big improvement in this area.

const oldCh = oldVnode.children; const ch = vnode.children; If (isDef(data) &&isPatchable (vnode)) {for (I = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode); if (isDef((i = data.hook)) && isDef((i = i.update))) i(oldVnode, vnode); }Copy the code

Next comes the first level of diff tree node level processing, immediately following the if above.

If (isUndef(vnode.text)) {if (isDef(oldCh) &&isdef (ch)) {// exp1: if (oldCh! == ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly); } else if (isDef(ch)) {if (process.env.node_env! == "production") { checkDuplicateKeys(ch); } if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, ""); AddVnodes (ELM, null, ch, 0, ch. Length-1, insertedVnodeQueue); } else if (isDef(oldCh)) {// exp3: removeVnodes(oldCh, 0, oldch.length-1); } else if (isDef(oldvnode.text)) {// exp4: elm (elm, ""); } } else if (oldVnode.text ! == vnode.text) {// exp5: nodeops.settextContent (elm, vnode.text); }Copy the code

Here I have drawn a simple diagram, which can be understood in terms of EXP1-EXP4.

• If the old node does not have child nodes but the new node does, the new nodes need to be added in batches.
• If the old node has child nodes but the new node does not, it indicates that these nodes need to be deleted in batches.

• If both parties have child nodes, the rearrangement operation, updateChildren(), is performed. The blue and orange wire frames in the figure. The diff process for the child node starts with updateChildren().

6. UpdateChildren (Node-level DIff)

At the node level diff, it’s high frequency execution. So there has to be an efficient way to compare and patch. Here, Vue also makes a special treatment for the Web platform.

Let’s start with some diagrams to illustrate the diff rules.

• There is a variable mark on both sides of the left and right heads and tails of the old and new vNodes, which converge towards the middle during traversal. The loop ends when oldStartIdx > oldEndIdx or newStartIdx > newEndIdx.
• If oldStartVnode and newEndVnode satisfy sameVnode. OldStartVnode has been moved to the end of oldEndVnode, and the real DOM node needs to be moved to the end of oldEndVnode while patchVnode is being performed.

• If oldEndVnode and newStartVnode satisfy sameVnode, oldEndVnode precedes oldStartVnode, When patchVnode is being performed, the corresponding DOM of oldEndVnode should be moved to the front of the corresponding DOM of oldStartVnode.
• If none of the above situations is true, find the same node as newStartVnode in old VNode. If patchVnode exists, move elmToMove to the front of the DOM corresponding to oldStartIdx.

• It is also possible that newStartVnode cannot find a consistent sameVnode in the old VNode, in which case createElm will be called to create a new DOM node.

The position of the above judgment has been annotated in the source code, interested can study carefully.

Function updateChildren(parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {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, idxInOld, vnodeToMove, refElm; const canMove = ! removeOnly; if (process.env.NODE_ENV ! == "production") { checkDuplicateKeys(newCh); While (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {// correct // start for null ++ // end for null -- if (isUndef(oldStartVnode)) { oldStartVnode = oldCh[++oldStartIdx]; // Vnode has been moved left } else if (isUndef(oldEndVnode)) { oldEndVnode = oldCh[--oldEndIdx]; } else if (sameVnode(oldStartVnode, newStartVnode)) { insertedVnodeQueue, newCh, newStartIdx ); oldStartVnode = oldCh[++oldStartIdx]; newStartVnode = newCh[++newStartIdx]; } else if (sameVnode(oldEndVnode, newEndVnode)) {patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx ); oldEndVnode = oldCh[--oldEndIdx]; newEndVnode = newCh[--newEndIdx]; } else if (sameVnode(oldStartVnode, NewEndVnode)) {// Vnode moved right patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx ); canMove && nodeOps.insertBefore( parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm) ); oldStartVnode = oldCh[++oldStartIdx]; newEndVnode = newCh[--newEndIdx]; } else if (sameVnode(oldEndVnode, NewStartVnode)) {// Vnode moved Left patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx ); canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm); oldEndVnode = oldCh[--oldEndIdx]; newStartVnode = newCh[++newStartIdx]; } else {// there is no sameNode at the beginning of the array, If (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx); idxInOld = isDef(newStartVnode.key) ? oldKeyToIdx[newStartVnode.key] : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx); // New Element createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx ); } else {// find the same node vnodeToMove = oldCh[idxInOld]; If (sameVnode(vnodeToMove, newStartVnode)) {// Update patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx ); oldCh[idxInOld] = undefined; canMove && nodeOps.insertBefore( parentElm, vnodeToMove.elm, oldStartVnode.elm ); } else {// same key but different element. Treat as new element // createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx ); } } newStartVnode = newCh[++newStartIdx]; } if (oldStartIdx > oldEndIdx) {refElm = isUndef(newCh[newEndIdx + 1])? null : newCh[newEndIdx + 1].elm; addVnodes( parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue ); } else if (newStartIdx > newEndIdx) {removeVnodes(oldCh, oldStartIdx, oldEndIdx); }}Copy the code

When oldStartIdx > oldEndIdx ends, the old VNode has been traversed, but the new node has not. This shows that there are actually more new VNodes than old vnodes, and the DOM corresponding to the remaining Vnodes needs to be inserted into the real DOM

Call addVnodes (batch call createElm interface).