Vue virtual DOM diff algorithm

Small knowledge, big challenge! This paper is participating in theEssentials for programmers”Creative activities.

TIP 👉 A man who has no foresight will have immediate concern. The Analects of Confucius · Duke Wei Ling

VNode

– A VNode is a Virtual node that describes a DOM element. If the VNode has children it is a Virtual DOM – SRC /package/vnode.ts

export interface VNode {
    / / selector
    sel: string | undefined;
    // Node data: attributes/styles/events etc
    data: VNodeData | undefined;
    // Child nodes, and text are mutually exclusive
    children: Array<VNode | string> | undefined;
    // Record the actual DOM corresponding to the vNode
    elm: Node | undefined;
    // The contents of this node are mutually exclusive with children
    text: string | undefined;
    / / optimization
    key: Key | undefined;
}
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 }
}
Copy the code

patch

• Function:

  • Pass in the old and new VNodes, compare the differences, and render the differences into the DOM

  • Return the new VNode as the oldVnode for the next patch()

• Execution process:

  • Start by executing the hook function pre in the module

  • If oldVnode and VNode are the same (same key and SEL)

    • Call patchVnode() to find the node differences and update the DOM

  • If oldVnode is a DOM element

    • Convert DOM elements into OLdvNodes

    • Call createElm() to convert vNode to a real DOM and log to vNode.elm

    • Insert the newly created DOM element into the parent

    • Removing an old node

    • Triggers the user-set CREATE hook function

return function patch (oldVnode: VNode | Element, vnode: VNode) :VNode {
    let i: number, elm: Node, parent: Node
    // Save the queue of newly inserted nodes in order to trigger the hook function
    const insertedVnodeQueue: VNodeQueue = []
    // Execute the module's Pre hook function
    for (i = 0; i < cbs.pre.length; ++i) cbs.pre[i]()
      // If oldVnode is not VNode, create VNode and set elm
    if(! isVnode(oldVnode)) {// Convert the DOM element to an empty VNode
        oldVnode = emptyNodeAt(oldVnode)
    }
    // If the new and old nodes are the same node (key and SEL are the same)
    if (sameVnode(oldVnode, vnode)) {
        // Find the node differences and update the DOM
        patchVnode(oldVnode, vnode, insertedVnodeQueue)
    } else {
        // If the old and new nodes are different, vNode creates the corresponding DOM
        // Get the current DOM element
        elm = oldVnode.elm!
        parent = api.parentNode(elm) as Node
              // Trigger init/create hook function to create DOM
        createElm(vnode, insertedVnodeQueue)
        
        if(parent ! = =null) {
            // If the parent node is not empty, insert the DOM corresponding to the vnode into the documentapi.insertBefore(parent, vnode.elm! , api.nextSibling(elm))// Remove the old node
            removeVnodes(parent, [oldVnode], 0.0)}}// Execute the user-set insert hook function
    for (i = 0; i < insertedVnodeQueue.length; ++i) { insertedVnodeQueue[i].data! .hook! .insert! (insertedVnodeQueue[i]) }// Execute the module's POST hook function
    for (i = 0; i < cbs.post.length; ++i) cbs.post[i]()
    return vnode
}
Copy the code

patchVnode

• Function:

  • patchVnode(oldVnode, vnode, insertedVnodeQueue)

  • Compare oldVnode and VNode differences and render the differences into the DOM

• Execution process:

  • The user-set prePatch hook function is first executed

  • Execute the CREATE hook function

    • The module’s CREATE hook function is first executed

    • The user-set CREATE hook function is then executed

  • If vnode.text is not defined

    • If oldvNode. children and vnode.children both have values

      • Call updateChildren ()

      • Diff algorithm is used to compare and update child nodes

    • If vnode.children has a value, oldvNode. children has no value

      • Clearing DOM elements

      • Call addVnodes() to add child nodes in batches

    • If oldvNode. children has a value, vnode.children has no value

      • callremoveVnodes()To remove child nodes in batches

    • If oldvNode. text has a value

      • Empty the content of the DOM element

    • If vnode.text is set and differs from oldvNode. text

      • If the old node has children, remove them all

      • Set the textContent of the DOM element to vNode.text

    • Finally, execute the user-set PostPatch hook function

function patchVnode (oldVnode: VNode, vnode: VNode, insertedVnodeQueue: VNodeQueue) {
    consthook = vnode.data? .hook// Execute the user-set prepatch hook function firsthook? .prepatch? .(oldVnode, vnode)const elm = vnode.elm = oldVnode.elm!
    const oldCh = oldVnode.children as VNode[]
    const ch = vnode.children as VNode[]
        // Return if the old and new vNodes are the same
    if (oldVnode === vnode) return
    if(vnode.data ! = =undefined) {
        // Execute the module's update hook function
        for (let i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode)
        // Execute the user-set update hook functionvnode.data.hook? .update? .(oldVnode, vnode) }// If vnode.text is not defined
    if (isUndef(vnode.text)) {
        // If both new and old nodes have children
        if (isDef(oldCh) && isDef(ch)) {
            // Call updateChildren to compare and update child nodes
            if(oldCh ! == ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue) }else if (isDef(ch)) {
            // If the new node has children, the old node has no children
            // Empty the dom element if the old node has text
            if (isDef(oldVnode.text)) api.setTextContent(elm, ' ')
            // Add child nodes in batches
            addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
        } else if (isDef(oldCh)) {
            // If the old node has children, the new node has no children
            // Remove child nodes in batches
            removeVnodes(elm, oldCh, 0, oldCh.length - 1)}else if (isDef(oldVnode.text)) {
                // If the old node has text, clear the DOM element
                api.setTextContent(elm, ' ')}}else if(oldVnode.text ! == vnode.text) {// If vnode.text is not set
            if (isDef(oldCh)) {
                // If the old node has children, remove it
                removeVnodes(elm, oldCh, 0, oldCh.length - 1)}// Set the DOM element's textContent to vnode.text
            api.setTextContent(elm, vnode.text!)
    }
    // Finally execute the user-set postpatch hook functionhook? .postpatch? .(oldVnode, vnode) }Copy the code

updateChildren

• Function:

  • The core of the diff algorithm, comparing the children of the old and new nodes, updates the DOM

• Execution process:

  • To compare the difference between two trees, we can take each node of the first tree and compare it to each node of the second tree, but in order of n^3 time.

  • In DOM manipulation we rarely move/update a parent node to a child node

  • So you just need to compare the nodes at the same level, and then compare the nodes at the next level, so the time complexity of the algorithm is O(n).

• When comparing nodes of the same level, the start and end nodes of the new and old node arrays will be marked with index, and the index will be moved during traversal

• When comparing the start and end nodes, there are four cases

  • OldStartVnode/newStartVnode (old start node/new start node)

  • OldEndVnode/newEndVnode (old end node/new end node)

  • OldStartVnode/oldEndVnode (old start node/new end node)

  • OldEndVnode/newStartVnode (old end node/new start node)

• The start node is compared to the end node. The two cases are similar

  • OldStartVnode/newStartVnode (old start node/new start node)

  • OldEndVnode/newEndVnode (old end node/new end node)

• If oldStartVnode and newStartVnode are samevNodes (same key and SEL)

  • Call patchVnode() to compare and update nodes

  • Move the old start and new start indexes back oldStartIdx++ / oldEndIdx++

• OldStartVnode/newEndVnode (old start node/new end node) same

– Call patchVnode() to compare and update nodes

• Move the oldStartVnode DOM element to the right

– Update index

• OldEndVnode/newStartVnode (old end node/new start node) same

• Call patchVnode() to compare and update nodes

• Move the oldEndVnode DOM element to the left

• Update the index

• If it’s not four of the above

  • Iterate over the new node, using the newStartNode key to find the same node in the old node array

  • If not, newStartNode is the new node

  • Create a DOM element corresponding to the new node and insert it into the DOM tree

  • If we find it,

  • Determine whether the SEL selector of the new node is the same as that of the old node found

  • If they are different, the nodes are modified

  • Re-create the corresponding DOM element and insert it into the DOM tree

  • If so, move the DOM element corresponding to elmToMove to the left

• End of the cycle

• The loop ends when all children of the old node are traversed first (oldStartIdx > oldEndIdx)

• All children of the new node are traversed first (newStartIdx > newEndIdx), and the loop ends

• If the array of the old node is traversed first (oldStartIdx > oldEndIdx), the new node has a surplus, and the remaining nodes are batch inserted to the right

• If the array of the new node is traversed first (newStartIdx > newEndIdx), it indicates that the old node has surplus. Delete the remaining nodes in batches