Diff and patch mechanism for data status update

Data update view

As mentioned earlier, the Watcher object in the corresponding Dep is triggered when the model is manipulated. The Watcher object calls the corresponding UPDATE to modify the view. Finally, a patch process is performed between the newly generated VNode and the old VNode, and the “differences” are obtained by comparison. Finally, these “differences” are updated to the view.

This chapter will introduce the patch process. Because the patch process itself is complicated, there will be more content in this chapter. But don’t be afraid.

cross-platform

Thanks to the use of Virtual DOM, vue.js has the ability to cross platform. Virtual DOM is just some JavaScript objects after all.

This relies on an adaptation layer that encapsulates the apis of different platforms and provides them with the same interface.

const nodeOps = { setTextContent (text) { if (platform === 'weex') { node.parentNode.setAttr('value', text); } else if (platform === 'web') { node.textContent = text; } }, parentNode () { //...... }, removeChild () { //...... }, nextSibling () { //...... }, insertBefore () { //...... }}Copy the code

For example, we now have a nodeOps object as described above, which implements the API corresponding to the current platform according to the platform, and provides a consistent interface externally for the Virtual DOM to call.

Some of the API

Next, we will introduce some other apis that will be used during patch, and they will eventually call the corresponding functions in nodeOps to manipulate the platform.

Insert is used to insert a child node under the parent node or before the ref child node if ref is specified.

function insert (parent, elm, ref) {
    if (parent) {
        if (ref) {
            if (ref.parentNode === parent) {
                nodeOps.insertBefore(parent, elm, ref);
            }
        } else {
            nodeOps.appendChild(parent, elm)
        }
    }
}

Copy the code

CreateElm is used to create a new node, tag exists to create a tag node, otherwise create a text node.

function createElm (vnode, parentElm, refElm) { if (vnode.tag) { insert(parentElm, nodeOps.createElement(vnode.tag), refElm); } else { insert(parentElm, nodeOps.createTextNode(vnode.text), refElm); }}Copy the code

AddVnodes is used to batch call createElm to create new nodes.

function addVnodes (parentElm, refElm, vnodes, startIdx, endIdx) { for (; startIdx <= endIdx; ++startIdx) { createElm(vnodes[startIdx], parentElm, refElm); }}Copy the code

RemoveNode is used to remove a node.

function removeNode (el) { const parent = nodeOps.parentNode(el); if (parent) { nodeOps.removeChild(parent, el); }}Copy the code

RemoveVnodes calls removeNode in batches to remove nodes.

function removeVnodes (parentElm, vnodes, startIdx, endIdx) { for (; startIdx <= endIdx; ++startIdx) { const ch = vnodes[startIdx] if (ch) { removeNode(ch.elm); }}}Copy the code

patch

First of all, the core diff algorithm of patch can be used to compare the “difference” between two trees. Let’s take a look. Suppose we have the following two trees, they are new and old VNodes respectively, and we need to compare them during the patch process.

Diff algorithm is a fairly efficient algorithm with only O(n) time complexity because it compares tree nodes of the same layer rather than searching and traversing the tree layer by layer, as shown in the figure below.

Nodes in squares of the same color in this diagram are compared, and those “differences” are updated to the view. It’s very efficient because it only compares at the same level.

The process of patch is quite complicated, so let’s take a look at it with a simple code.

function patch (oldVnode, vnode, parentElm) {
    if (!oldVnode) {
        addVnodes(parentElm, null, vnode, 0, vnode.length - 1);
    } else if (!vnode) {
        removeVnodes(parentElm, oldVnode, 0, oldVnode.length - 1);
    } else {
        if (sameVnode(oldVNode, vnode)) {
            patchVnode(oldVNode, vnode);
        } else {
            removeVnodes(parentElm, oldVnode, 0, oldVnode.length - 1);
            addVnodes(parentElm, null, vnode, 0, vnode.length - 1);
        }
    }
}

Copy the code

The main function of patch is to compare two VNodes and update the “difference” to the view, so the input parameter includes the old and new vnodes and the element of the parent node. Let’s walk through the logic step by step. Functions like addVnodes and removeVnodes will be covered later.

First of all, when oldvNodes (old VNodes) do not exist, it is equivalent to replacing the existing nodes with new vNodes. Therefore, addVnodes are directly used to add these nodes to parentElm in batches.

if (! oldVnode) { addVnodes(parentElm, null, vnode, 0, vnode.length - 1); }Copy the code

Similarly, if a vNode (new vNode) does not exist, it is equivalent to removing the old node, so use removeVnodes to delete nodes in batches.

else if (! vnode) { removeVnodes(parentElm, oldVnode, 0, oldVnode.length - 1); }Copy the code

Finally, when both oldVNode and vNode exist, it is necessary to determine whether they are sameVnode (the same node). If yes, perform patchVnode (comparing vNodes); otherwise, delete the old nodes and add new ones.

if (sameVnode(oldVNode, vnode)) {
    patchVnode(oldVNode, vnode);
} else {
    removeVnodes(parentElm, oldVnode, 0, oldVnode.length - 1);
    addVnodes(parentElm, null, vnode, 0, vnode.length - 1);
}

Copy the code

sameVnode

When two vNodes belong to sameVnode (the same node)?

function sameVnode () { return ( a.key === b.key && a.tag === b.tag && a.isComment === b.isComment && (!! a.data) === (!! b.data) && sameInputType(a, b) ) } function sameInputType (a, b) { if (a.tag ! == 'input') return true let i const typeA = (i = a.data) && (i = i.attrs) && i.type const typeB = (i = b.data) && (i = i.attrs) && i.type return typeA === typeB }Copy the code

SameVnode is simple, but only if key, tag, isComment, and data are defined (or not) at the same time, and if the tag type is input, the type is the same. Some browsers do not support dynamic type modification. So they are considered different types).

patchVnode

The function patchVnode was left in the previous patch process, which is also the most complicated one. Let’s have a look now. Because this function fires under sameVnode conditions, it is “matched”.

function patchVnode (oldVnode, vnode) { if (oldVnode === vnode) { return; } if (vnode.isStatic && oldVnode.isStatic && vnode.key === oldVnode.key) { vnode.elm = oldVnode.elm; vnode.componentInstance = oldVnode.componentInstance; return; } const elm = vnode.elm = oldVnode.elm; const oldCh = oldVnode.children; const ch = vnode.children; if (vnode.text) { nodeOps.setTextContent(elm, vnode.text); } else { if (oldCh && ch && (oldCh ! == ch)) { updateChildren(elm, oldCh, ch); } else if (ch) { if (oldVnode.text) nodeOps.setTextContent(elm, ''); addVnodes(elm, null, ch, 0, ch.length - 1); } else if (oldCh) { removeVnodes(elm, oldCh, 0, oldCh.length - 1) } else if (oldVnode.text) { nodeOps.setTextContent(elm, '') } } }Copy the code

First, if the old and new vNodes are the same, there is no need to make any changes.

if (oldVnode === vnode) {
    return;
}

Copy the code

When the old and new VNodes are isStatic and have the same key, just “take” componentInstance and elm from the old VNode. IsStatic is the same as the static nodes that are marked when “compiled” so that the comparison process can be skipped.

if (vnode.isStatic && oldVnode.isStatic && vnode.key === oldVnode.key) {
    vnode.elm = oldVnode.elm;
    vnode.componentInstance = oldVnode.componentInstance;
    return;
}

Copy the code

Next, when the new VNode is a text node, text is set directly with setTextContent. NodeOps is an adaptation layer that provides different methods to manipulate the DOM of different platforms, implementing cross-platform implementation.

if (vnode.text) {
    nodeOps.setTextContent(elm, vnode.text);
}

Copy the code

When a new VNode is a non-text node, there are several cases.

oldCh 与 chBoth exist and are not the same, useupdateChildrenFunction to update child nodes, which we’ll focus on later.
If onlychIf the old node is a text node, the text of the node is cleared first, and then thechBatch insert The nodes are added to node ELM.
It should only beoldchIf yes, the old node needs to pass throughremoveVnodesClear them all.
The final case is to clear the text content of the node when only the old node is a text node.

if (oldCh && ch && (oldCh ! == ch)) { updateChildren(elm, oldCh, ch); } else if (ch) { if (oldVnode.text) nodeOps.setTextContent(elm, ''); addVnodes(elm, null, ch, 0, ch.length - 1); } else if (oldCh) { removeVnodes(elm, oldCh, 0, oldCh.length - 1) } else if (oldVnode.text) { nodeOps.setTextContent(elm, '') }Copy the code

updateChildren

The next step is to talk about the update Dren function.

function updateChildren (parentElm, oldCh, newCh) { 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, idxInOld, elmToMove, refElm; while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) { if (! oldStartVnode) { oldStartVnode = oldCh[++oldStartIdx]; } else if (! oldEndVnode) { oldEndVnode = oldCh[--oldEndIdx]; } else if (sameVnode(oldStartVnode, newStartVnode)) { patchVnode(oldStartVnode, newStartVnode); oldStartVnode = oldCh[++oldStartIdx]; newStartVnode = newCh[++newStartIdx]; } else if (sameVnode(oldEndVnode, newEndVnode)) { patchVnode(oldEndVnode, newEndVnode); oldEndVnode = oldCh[--oldEndIdx]; newEndVnode = newCh[--newEndIdx]; } else if (sameVnode(oldStartVnode, newEndVnode)) { patchVnode(oldStartVnode, newEndVnode); nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm)); oldStartVnode = oldCh[++oldStartIdx]; newEndVnode = newCh[--newEndIdx]; } else if (sameVnode(oldEndVnode, newStartVnode)) { patchVnode(oldEndVnode, newStartVnode); nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm); oldEndVnode = oldCh[--oldEndIdx]; newStartVnode = newCh[++newStartIdx]; } else { let elmToMove = oldCh[idxInOld]; if (! oldKeyToIdx) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx); idxInOld = newStartVnode.key ? oldKeyToIdx[newStartVnode.key] : null; if (! idxInOld) { createElm(newStartVnode, parentElm); newStartVnode = newCh[++newStartIdx]; } else { elmToMove = oldCh[idxInOld]; if (sameVnode(elmToMove, newStartVnode)) { patchVnode(elmToMove, newStartVnode); oldCh[idxInOld] = undefined; nodeOps.insertBefore(parentElm, newStartVnode.elm, oldStartVnode.elm); newStartVnode = newCh[++newStartIdx]; } else { createElm(newStartVnode, parentElm); newStartVnode = newCh[++newStartIdx]; } } } } if (oldStartIdx > oldEndIdx) { refElm = (newCh[newEndIdx + 1]) ? newCh[newEndIdx + 1].elm : null; addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx); } else if (newStartIdx > newEndIdx) { removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx); }}Copy the code

Don’t worry when you see so much code, let’s go through it bit by bit.

First we define oldStartIdx, newStartIdx, oldEndIdx, and newEndIdx as indexes on both sides of the old and new vNodes. OldStartVnode, newStartVnode, oldEndVnode, and newEndVnode point to the vnodes corresponding to these indexes respectively.

This is followed by a while loop, in which oldStartIdx, newStartIdx, oldEndIdx, and newEndIdx gradually converge to the center.

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) 

Copy the code

First, when oldStartVnode or oldEndVnode does not exist, oldStartIdx and oldEndIdx continue to move closer to the center and update the corresponding oldStartVnode and oldEndVnode Pointers. OldStartIdx, newStartIdx, oldEndIdx, and newEndIdx moves are all accompanied by oldStartVnode, newStartVnode, oldEndVnode, and newEndVnode The next part will only talk about Idx movement.

if (! oldStartVnode) { oldStartVnode = oldCh[++oldStartIdx]; } else if (! oldEndVnode) { oldEndVnode = oldCh[--oldEndIdx]; }Copy the code

In the next section, oldStartIdx, newStartIdx, oldEndIdx, and newEndIdx are compared in pairs, and there will be 2*2=4 cases in total.

 else if (sameVnode(oldStartVnode, newStartVnode)) {
    patchVnode(oldStartVnode, newStartVnode);
    oldStartVnode = oldCh[++oldStartIdx];
    newStartVnode = newCh[++newStartIdx];
} else if (sameVnode(oldEndVnode, newEndVnode)) {
    patchVnode(oldEndVnode, newEndVnode);
    oldEndVnode = oldCh[--oldEndIdx];
    newEndVnode = newCh[--newEndIdx];
} else if (sameVnode(oldStartVnode, newEndVnode)) {
    patchVnode(oldStartVnode, newEndVnode);
    nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm));
    oldStartVnode = oldCh[++oldStartIdx];
    newEndVnode = newCh[--newEndIdx];
} else if (sameVnode(oldEndVnode, newStartVnode)) {
    patchVnode(oldEndVnode, newStartVnode);
    nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm);
    oldEndVnode = oldCh[--oldEndIdx];
    newStartVnode = newCh[++newStartIdx];
} 

Copy the code

First, when oldStartVnode and newStartVnode are consistent with sameVnode, it indicates that the head of the old VNode and the head of the new VNode are the sameVnode, so patchVnode is directly performed. At the same time oldStartIdx and newStartIdx move back one bit.

Secondly, oldEndVnode and newEndVnode match sameVnode, that is, two vnodes end with the sameVnode. Do the same with patchVnode and move oldEndVnode and newEndVnode forward one bit.

And then there are two crossover cases.

When oldStartVnode and newEndVnode match sameVnode, the head of the old VNode and the tail of the new VNode are the same node. Move oldStartvNode. elm directly after oldEndvNode. elm. Then oldStartIdx moves back one bit and newEndIdx moves forward one bit.

Similarly, when oldEndVnode and newStartVnode match sameVnode, that is, when the tail of the old VNode and the head of the new VNode are the same node, Insert oldEndvNode. elm in front of oldStartvNode. elm. Similarly, oldEndIdx moves forward one bit and newStartIdx moves back one bit.

Finally, when the above situations do not meet the time, how to deal with this situation?

else { let elmToMove = oldCh[idxInOld]; if (! oldKeyToIdx) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx); idxInOld = newStartVnode.key ? oldKeyToIdx[newStartVnode.key] : null; if (! idxInOld) { createElm(newStartVnode, parentElm); newStartVnode = newCh[++newStartIdx]; } else { elmToMove = oldCh[idxInOld]; if (sameVnode(elmToMove, newStartVnode)) { patchVnode(elmToMove, newStartVnode); oldCh[idxInOld] = undefined; nodeOps.insertBefore(parentElm, newStartVnode.elm, oldStartVnode.elm); newStartVnode = newCh[++newStartIdx]; } else { createElm(newStartVnode, parentElm); newStartVnode = newCh[++newStartIdx]; } } } function createKeyToOldIdx (children, beginIdx, endIdx) { let i, key const map = {} for (i = beginIdx; i <= endIdx; ++i) { key = children[i].key if (isDef(key)) map[key] = i } return map }Copy the code

CreateKeyToOldIdx creates a map table with a key and index. Such as:

[
    {xx: xx, key: 'key0'},
    {xx: xx, key: 'key1'}, 
    {xx: xx, key: 'key2'}
]

Copy the code

CreateKeyToOldIdx converts to:

{
    key0: 0, 
    key1: 1, 
    key2: 2
}

Copy the code

We can quickly get the idxInOld index of nodes with the same key from oldKeyToIdx (the return value of createKeyToOldIdx) based on the value of a key, and then find the same node.

If the same node is not found, create a new node with createElm and move newStartIdx one bit back.

if (! idxInOld) { createElm(newStartVnode, parentElm); newStartVnode = newCh[++newStartIdx]; }Copy the code

Otherwise, if the node is found and it conforms to sameVnode, the two nodes will be patchVnode, and the old node at this position will be assigned with undefined (if there is a new node with the same key as this node, it can be detected that there is a duplicate key). At the same time, insert newStartvNode. elm before oldStartvNode. elm. Similarly, newStartIdx moves back one place.

else { elmToMove = oldCh[idxInOld]; if (sameVnode(elmToMove, newStartVnode)) { patchVnode(elmToMove, newStartVnode); oldCh[idxInOld] = undefined; nodeOps.insertBefore(parentElm, newStartVnode.elm, oldStartVnode.elm); newStartVnode = newCh[++newStartIdx]; }}Copy the code

If it does not match sameVnode, only a new node can be created and inserted into the child of parentElm, with newStartIdx moved one bit later.

else {
    createElm(newStartVnode, parentElm);
    newStartVnode = newCh[++newStartIdx];
}

Copy the code

The last step is easy. After the while loop ends, if oldStartIdx > oldEndIdx, the old nodes are compared, but there are more new nodes to insert into the real DOM. Call addVnodes to insert these nodes.

Similarly, if newStartIdx > newEndIdx is satisfied, it indicates that there are many old nodes after the comparison of new nodes. Remove these useless old nodes in batches by removeVnodes.

if (oldStartIdx > oldEndIdx) {
    refElm = (newCh[newEndIdx + 1]) ? newCh[newEndIdx + 1].elm : null;
    addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx);
} else if (newStartIdx > newEndIdx) {
    removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
}

Copy the code

Diff and patch mechanism for data status update

Data update view

cross-platform

Some of the API

patch

sameVnode

patchVnode

updateChildren

Related Posts

Here are the React component design modes you want to know.

My JS algorithm climb pit journey – binary summation

Vue development framework (detailed version)