Vue’s diff algorithm

The special attribute of key is mainly used in the virtual DOM algorithm of Vue. When comparing old vNodes with new ones, without keys, Vue minimizes dynamic elements and reuses them in place as much as possible. This can cause some rendering errors. And it doesn’t work when we try to trigger some transition animations. Because Vue determines that the element has not changed.

With a key, it recalculates the sorted element sequence based on the change in the key. It also removes elements where the key does not exist.

Its principle lies in the DIff algorithm of Vue. And our key plays a role in its patch process.

function patch(oldVnode, vnode) {
    // some code
    if (sameVnode(oldVnode, vnode)) {
        patchVnode(oldVnode, vnode);
    } else {
        const oEl = oldVnode.el; // The real element node corresponding to the current oldVnode
        let parentEle = api.parentNode(oEl); / / the parent element
        createEle(vnode); // Generate new elements based on Vnode
        if(parentEle ! = =null) {
            api.insertBefore(parentEle, vnode.el, api.nextSibling(oEl)); // Add the new element to the parent element
            api.removeChild(parentEle, oldVnode.el); // Remove the old element node
            oldVnode = null; }}// some code
    return vnode;
}

// Author: Windlany
/ / link: https://juejin.cn/post/6844903607913938951
Copy the code

Peer comparison

If the two nodes are the same, the patchVnode() method is used for further comparison.

If the two nodes are different, replace the old Vnode with the new one. If two parents are different, but their children are the same, no child comparison is made. That’s the same-level comparison.

patchNode()

patchVnode (oldVnode, vnode) {
    const el = vnode.el = oldVnode.el
    let i, oldCh = oldVnode.children, ch = vnode.children
    if (oldVnode === vnode) return
    if(oldVnode.text ! = =null&& vnode.text ! = =null&& oldVnode.text ! == vnode.text) { api.setTextContent(el, vnode.text) }else {
        updateEle(el, vnode, oldVnode)
    	if(oldCh && ch && oldCh ! == ch) { updateChildren(el, oldCh, ch) }else if (ch){
            createEle(vnode) //create el's children dom
    	}else if (oldCh){
            api.removeChildren(el)
    	}
    }
}

// Author: Windlany
/ / link: https://juejin.cn/post/6844903607913938951
Copy the code

The above is different processing according to different situations.

  • If the old and new nodes point to the same object, directreturnDo nothing.
  • If both have text nodes and they are different, the new one replaces the old one.
  • ifoldVnodeThere are child nodes, and newVnodeIf no, delete the child node.
  • On the other hand, ifVnodeThere are child nodes, andoldVnodeIf no, add the child node.
  • If both have child nodes, proceedupdateChildren()Comparison.

The diff algorithm is in the updateChildren() function.

updateChildren()

updateChildren (parentElm, oldCh, newCh) {
    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
    let idxInOld
    let elmToMove
    let before
    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
        if (oldStartVnode == null) {   // For vnode.key comparisons, oldVnode = null
            oldStartVnode = oldCh[++oldStartIdx]
        }else if (oldEndVnode == null) {
            oldEndVnode = oldCh[--oldEndIdx]
        }else if (newStartVnode == null) {
            newStartVnode = newCh[++newStartIdx]
        }else if (newEndVnode == null) {
            newEndVnode = newCh[--newEndIdx]
            // oldS is compared with S
        }else if (sameVnode(oldStartVnode, newStartVnode)) {
            patchVnode(oldStartVnode, newStartVnode)
            oldStartVnode = oldCh[++oldStartIdx]
            newStartVnode = newCh[++newStartIdx]
            // compare oldE with E
        }else if (sameVnode(oldEndVnode, newEndVnode)) {
            patchVnode(oldEndVnode, newEndVnode)
            oldEndVnode = oldCh[--oldEndIdx]
            newEndVnode = newCh[--newEndIdx]
            // oldS is compared with E
        }else if (sameVnode(oldStartVnode, newEndVnode)) {
            patchVnode(oldStartVnode, newEndVnode)
            api.insertBefore(parentElm, oldStartVnode.el, api.nextSibling(oldEndVnode.el))
            oldStartVnode = oldCh[++oldStartIdx]
            newEndVnode = newCh[--newEndIdx]
            // compare oldE with S
        }else if (sameVnode(oldEndVnode, newStartVnode)) {
            patchVnode(oldEndVnode, newStartVnode)
            api.insertBefore(parentElm, oldEndVnode.el, oldStartVnode.el)
            oldEndVnode = oldCh[--oldEndIdx]
            newStartVnode = newCh[++newStartIdx]
        }else {
           // The comparison with key
            if (oldKeyToIdx === undefined) {
                oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) // Create index table with key
            }
            idxInOld = oldKeyToIdx[newStartVnode.key]
            if(! idxInOld) { api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el) newStartVnode = newCh[++newStartIdx] }else {
                elmToMove = oldCh[idxInOld]
                if(elmToMove.sel ! == newStartVnode.sel) { api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el) }else {
                    patchVnode(elmToMove, newStartVnode)
                    oldCh[idxInOld] = null
                    api.insertBefore(parentElm, elmToMove.el, oldStartVnode.el)
                }
                newStartVnode = newCh[++newStartIdx]
            }
        }
    }
    if (oldStartIdx > oldEndIdx) {
        before = newCh[newEndIdx + 1] = =null ? null : newCh[newEndIdx + 1].el
        addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx)
    }else if (newStartIdx > newEndIdx) {
        removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
    }
}
Copy the code

This function does the following:

  • willVnodeThe child nodes of theVnodeChildren(hereinafter referred to as Vch) 和 oldNodeThe child nodes of theOldNodeChildren (hereinafter referred to as oldCh)Extract it.
  • Vch 和 oldChEach variable has two heads and two tailsstartIdx 和 endIdx. Their two variables are compared to each other. There are four ways to compare. If none of the four matches, check whether it is setkey. If it’s set up, it will be usedkeyCompare. In the process of comparison, the variable will move to the middle, oncestartIdx > endIdxShow thatoldCh 和 VchAt least one of them has been traversed, and the comparison ends.

Next up:

Here are vNodes and OLDVNodes

Take them out and assign the head and tail variables respectively.

OldS will be sameNode compared with S and E. OldE will make sameNode comparisons with S and E.

  • Once one pair is a match, then it’s realDOMWill move to the corresponding node. These two Pointers will move in the middle.
  • If none of the four groups match, there are two scenarios.
    • If both old and new child nodes existkey, then will be based onoldCh 的 keyGenerate aThe hash table. withS 的 keyContrast that with that. If we get a match, we’re going to determine thisSAnd whether the nodesameNode. If so, be realDOMMove the successful node to the front. Otherwise it would beSThe corresponding generated node is inserted intoDOMIn the correspondingoldSPosition.SPointer moves to the middle and is matchedoldIs set tonull 。
    • If there is nokey, then directlySGenerate new nodes to insert realDOM.

That is, without a key, only 4 matches will be performed, and even if there are reusable nodes in the middle of the pointer, they cannot be reused.

Next, take a look at the matching process shown above:

OldS matches S

Put node A in the DOM first. It’s already the first one.

Olds matches E

Put node B in the DOM last.

OldE matches S

It was supposed to move C to S. In the real DOM, node C is already in the second position. So do nothing.

OldS > oldE ends the match.

Insert the remaining node D into the DOM according to its index.

There are two situations where a match ends.

  • oldS > oldEinstructionsoldChIterate through first, then you need to put the extraVchAccording to theindexAdded to theDOMIn the.
  • S > EinstructionsVchLet’s go through it. You need to deleteoldChRedundant nodes in.