Vue-diff algorithm in detail

preface

Jquery era, we view through direct manipulation dom node updates, but as the complexity of the application, the code is also becoming more difficult to maintain, the most simple way is to the dom structure innerHTML directly to modify the page, the problem is not need to update the node can be set redraw rearrangement, cost performance.

It can be imagined that if only the modified part can be updated each time, the performance can be improved. Taking this as the starting point, the idea of vue.js node update is to abstract the real DOM into a virtual DOM tree with JavaScript objects as nodes, referred to as vNode, which can be used for node creation, deletion, modification and other operations. In this process, there is no need to operate the real DOM. Comparing vNode differences before and after the operation, that is, the use of diff algorithm, the minimum units to be modified will be obtained, and then only the real DOM of the difference part will be modified

Rather than triggering redrawing of the real DOM and modifying the innerHTML of an entire block with each operation, vNode reduces the number of unnecessary DOM operations and improves performance.

What is a VNode?

What is a vNode? A vNode is an abstraction of a real DOM node. Simply put, it is a JavaScript object that simulates a tree structure and uses attributes to describe various properties of the real DOM, such as the following real DOM:

<div class="test">
    <span class="demo">hello,VNode</span>
</div>
Copy the code

The corresponding vNode is:

{
    elm: div, // A reference to a real node
    tag: 'div', // Label of the node
    data: { // A storage node property object corresponding to the node's EL [prop] property, such as onclick, style
        class: 'test'
    },
    children: [ // Store an array of child nodes
        {
            tag: 'span',
            data: {
                class: 'demo'
            }
            text: 'hello,VNode'
        }
    ]
}
Copy the code

The diff is

When comparing old and new nodes, the comparison is only performed at the same level, not across levels, complexity O (n)

Example:

<! Before -- -- -- >
<div>           <! -- Level 1 -->
  <p>            <! -- Level 2 -->
    <b> aoy </b>   <! -- Level 3 -->   
    <span>diff</Span>
  </P> 
</div>

<! After -- -- -- >
<div>            <! -- Level 1 -->
  <p>             <! -- Level 2 -->
      <b> aoy </b>        <! -- Level 3 -->
  </p>
  <span>diff</Span>
</div>
Copy the code

If we operate dom directly manually, we may move the SPAN node directly below, which is the optimal operation. However, in diff algorithm, we first remove the SPAN node in P, and then create a new span after P. The new SPAN node is at level 2, and the old SPAN node is at level 3, which belongs to the comparison of different levels

Vue2. X diff source code analysis

How do I modify the view?

When some data is modified, the set method makes Dep call notify all the subscribers Watcher. Watcher executes vm._update by calling get, which patches the real DOM and updates the corresponding view.

   Vue.prototype._update = function (vnode, hydrating) {
    var vm = this;
    var prevEl = vm.$el;
    var prevVnode = vm._vnode;
    var 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);
    }
    restoreActiveInstance();
    // update __vue__ reference
    if (prevEl) {
      prevEl.__vue__ = null;
    }
    if (vm.$el) {
      vm.$el.__vue__ = vm;
    }
    // if parent is an HOC, update its $el as well
    if (vm.$vnode && vm.$parent && vm.$vnode === vm.$parent._vnode) {
      vm.$parent.$el = vm.$el;
    }
    // updated hook is called by the scheduler to ensure that children are
    // updated in a parent's updated hook.
  };
Copy the code

The process is as follows:

Specific source code analysis

The patch function

The core code is as follows:

return function patch (oldVnode, vnode, hydrating, removeOnly) {
    // If the vnode does not exist, it will be destroyed
    if (isUndef(vnode)) {
      if (isDef(oldVnode)) invokeDestroyHook(oldVnode)
      return
    }

    let isInitialPatch = false
    const insertedVnodeQueue = []

    if (isUndef(oldVnode)) {
      // empty mount (likely as component), create new root element
        // oldVode is not defined, then a new node is created for the root node
      isInitialPatch = true
      createElm(vnode, insertedVnodeQueue)
    } else {
        // flag whether oldVnode has a nodeType
      const isRealElement = isDef(oldVnode.nodeType)
      if(! isRealElement && sameVnode(oldVnode, vnode)) {// patch existing root node
          // If the old and new nodes are worthy of comparison, only patchVnode is required for further comparison
        patchVnode(oldVnode, vnode, insertedVnodeQueue, null.null, removeOnly)
      } else{...// replacing existing element
        const oldElm = oldVnode.elm
        const parentElm = nodeOps.parentNode(oldElm)

        // create new node
        // Create a node
        createElm(
          vnode,
          insertedVnodeQueue,
          // extremely rare edge case: do not insert if old element is in a
          // leaving transition. Only happens when combining transition +
          // keep-alive + HOCs. (#4590)
          oldElm._leaveCb ? null : parentElm,
          nodeOps.nextSibling(oldElm)
        )

        ...

        // destroy old node
        // Remove the old node
        if (isDef(parentElm)) {
          removeVnodes([oldVnode], 0.0)}else if (isDef(oldVnode.tag)) {
          invokeDestroyHook(oldVnode)
        }
      }
    }
	// Add a new node
    invokeInsertHook(vnode, insertedVnodeQueue, isInitialPatch)
    return vnode.elm
  }
Copy the code

Patch receives parameter oldVnode and vNode code old and new two nodes.

If the vnode is undefined or null, the oldVnode is destroyed
If oldVnode is not defined, it is the root node and a new node vnode is created directly

Both the old and new nodes are defined. If the old and new nodes are worthy of comparison, patchVnode is executed

/* Check whether two vNodes are the same node if the following conditions are met: Key Same tag (tag name of the current node) Same asyncFactory(Async Component Factory function) Same isComment (whether it is a comment node) Same data (object corresponding to the current node, If the label is input, the type must be the same */. If the label is input, the type must be the same
function sameVnode (a, b) {
  return (
    a.key === b.key &&
    a.asyncFactory === b.asyncFactory && (
      (
        a.tag === b.tag &&
        a.isComment === b.isComment &&
        isDef(a.data) === isDef(b.data) &&
        sameInputType(a, b)
      ) || (
        isTrue(a.isAsyncPlaceholder) &&
        isUndef(b.asyncFactory.error)
      )
    )
  )
}
Some browsers do not support dynamic modification of  types, so they are treated as different nodes */
function sameInputType (a, b) {
  if(a.tag ! = ='input') return true
  let i
  const typeA = isDef(i = a.data) && isDef(i = i.attrs) && i.type
  const typeB = isDef(i = b.data) && isDef(i = i.attrs) && i.type
  return typeA === typeB || isTextInputType(typeA) && isTextInputType(typeB)
}
Copy the code

If the comparison is not worthwhile, remove the old node oldVnode and add a new node vnode

patchVnode

When the two nodes are worth comparing, the patchVnode method will be executed, and the core code is as follows:

function patchVnode (oldVnode, vnode, insertedVnodeQueue, ownerArray, index, removeOnly) {
    if (oldVnode === vnode) {
      return
    }
    
     // Let vnode.elm refer to the real DOM. When elm changes, vnode.elm changes in sync
    const elm = vnode.elm = oldVnode.elm
   
    const oldCh = oldVnode.children
    const ch = vnode.children
    
    // VNode has no text content
    if (isUndef(vnode.text)) {
      if (isDef(oldCh) && isDef(ch)) {
          // Both old and new nodes have child nodes to perform updateChildren comparison
        if(oldCh ! == ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly) }else if (isDef(ch)) {
          // If only VNode has child nodes, clear elm text and insert new child nodes
        if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, ' ')
        addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
      } else if (isDef(oldCh)) {
          // Only oldVnode has child nodes. Remove the old node directly
        removeVnodes(oldCh, 0, oldCh.length - 1)}else if (isDef(oldVnode.text)) {
          // If the old node has text content, empty the text content directly
        nodeOps.setTextContent(elm, ' ')}}else if(oldVnode.text ! == vnode.text) {// Both have text nodes and are not equal. Replace them with vNode text content
      nodeOps.setTextContent(elm, vnode.text)
    }
    ...
  }
Copy the code

Comparison of old and new nodes:

OldVnode and vnode reference the same object, do not change, directly return
Vnode has text nodes, and the text of the old and new nodes are not equal, then set the text node of ELM to vnode.text
Vnode without text node:
- If both the old and new nodes have child nodes, call updateChildren to compare the child nodes
- If vnode has child nodes and oldVnode does not, delete the elm text content and insert the child nodes of Vnode
- If a VNode has no child node and an oldVnode has child nodes, remove the child nodes of an oldVnode
- If oldVnode has text nodes, delete elm text content directly

Next, update Dren

updateChildren

  function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
    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, vnodeToMove, refElm

    // removeOnly is a special flag used only by <transition-group>
    // to ensure removed elements stay in correct relative positions
    // during leaving transitions
    constcanMove = ! removeOnlyif(process.env.NODE_ENV ! = ='production') {
      checkDuplicateKeys(newCh)
    }

    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if (isUndef(oldStartVnode)) { // oldStartVnode is nul or undefined
        oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
      } else if (isUndef(oldEndVnode)) {
        oldEndVnode = oldCh[--oldEndIdx]
      } else if (sameVnode(oldStartVnode, newStartVnode)) {
        patchVnode(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 {
        if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
        idxInOld = isDef(newStartVnode.key)
          ? oldKeyToIdx[newStartVnode.key]
          : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
        if (isUndef(idxInOld)) { // New element
          createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
        } else {
          vnodeToMove = oldCh[idxInOld]
          if (sameVnode(vnodeToMove, newStartVnode)) {
            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)
    }
  }
  // Pass node through oldCh to find the node that oldCh matches node
  function findIdxInOld (node, oldCh, start, end) {
    for (let i = start; i < end; i++) {
      const c = oldCh[i]
      if (isDef(c) && sameVnode(node, c)) return i
    }
  }
Copy the code

OldVnode and vnode

Fetch the child node, corresponding to oldCh, newCh

It goes something like this:

OldCh and newCh, the children of the old and new nodes, are passed in
OldCh and newCh each have two starting and ending variables StartIdx and EndIdx. There are 4 ways to compare two variables to each other. If none of these 4 ways match, if key is set, the comparison will be performed by key. Once StartIdx > EndIdx, the comparison ends, indicating that at least one of oldCh and newCh has been traversed.

NodeOps. InsertBefore is called whenever the DOM is manipulated during the comparison process, which has the same function as insertBefore

Specific comparison rules:

If sameVnode(oldStartVnode, newStartVnode) and sameVnode(oldEndVnode,newEndVnode) are true, no dom movement is required
When oldStartVnode and newEndVnode are worth comparing, the real DOM node oldStartvNode. elm comes after oldEndvNode. elm
When oldEndVnode and newStartVnode are worth comparing, the real DOM node oldEndvNode. elm is moved to the front of oldStartvNode. elm
If none of the preceding conditions is met, generate a hash table based on the oldCh key. If newStartVnode has a key, find the node that matches the key in the hash table. If the key is not set, findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx) is called each time through oldCh to find a matching node.

No matter whether the key is set or not, it will search for matched nodes. If the key is not set, it needs to traverse the difference search, which is relatively inefficient

Divided into two cases:
- If the matching node is found through the above operations, determine whether newStartVnode and the matching node are sameVnode. If so, move the matching node to the front of oldStartvNode. elm in the real DOM, and set the corresponding position of the old node to undefined. If not, create the newStartVnode real node and insert it in front of oldStartvNode.elm
- If no matching node is found, the real node is created with newStartVnode and inserted in front of oldStartvNode.elm
At the end, there are two cases:
1. oldStartIdx > oldEndIdx, it can be considered thatoldChI’m going to walk through it, newCh may be just walking through it, newCh may not be walking through it, if not,newStartIdxandnewEndIdxBetween vNodes are new,refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elmIf refElm is nullnewStartIdxandnewEndIdxIf the refElm is not null, the new vNodes are inserted before the refElm.
2. newStartIdx > newEndIdx, it can be considered thatnewChLet’s go through it. At this timeoldStartIdxandoldEndIdxCall between vNodes that no longer exist in the new child noderemoveVnodesDelete them from the DOM.
If this process is still confusing, here’s an example of the diff process:

Suppose oldCh, newCh is as follows:

Step 1:

oldS = a    oldE = d
newS = b    newE = c
Copy the code

In the fourth case of the above rule, regardless of whether the key is set in newS or not, it will search for the node B matching it, match B in oldCh, move B to the front of oldS, that is, a, oldCh where B was set to NULL, ++newS

Step 2:

oldS = a    oldE = d
newS = e    newE = c
Copy the code

If the fourth rule is met, newS = e, where oldCh has no matching E, e is directly added to oldS (a), ++newS

Step 3:

oldS = a    oldE = d
newS = d    newE = c
Copy the code

If the third rule is met and oldE matches newS, oldE is moved in front of oldS, that is, D is moved in front of A, –oldE, ++newS

Step 4:

oldS = a    oldE = c
newS = c    newE = c
Copy the code

If the first rule is satisfied, oldE matches newE without moving –oldE, –newE, now newS>newE, newCh completes traversal, removing the node between oldS and oldE, i.e., a, and null of the original b position

End of simulation.

Vue3. X Diff algorithm optimization

The virtual DOM in VUe2 is a full comparison
Vue3 added PatchFlag

When comparing with the last virtual node, only the node with the patch Flag is compared, and the specific content type of the current node to be compared can be known based on the flag information

Verify this with a small number of DOM template nodes:

<div> <p> Exercise </p> <p> Body </p> {{MSG}} </div>Copy the code

The template is compiled as follows:

vue2.x

ffunction render() {
  var _vm = this;
  var _h = _vm.$createElement;
  var _c = _vm._self._c || _h;
  return _c('div', [_c('p', [_vm._v("Exercise")]), _c('p', [_vm._v("Body")]), _vm._v(
    "\n " + _vm._s(_vm.msg) + "\n")])}Copy the code

vue3.x

import { createVNode as _createVNode, toDisplayString as _toDisplayString, createTextVNode as _createTextVNode, openBlock as _openBlock, createBlock as _createBlock } from "vue"

export function render(_ctx, _cache, $props, $setup, $data, $options) {
  return (_openBlock(), _createBlock("div".null, [
    _createVNode("p".null."Exercise"),
    _createVNode("p".null."Body"),
    _createTextVNode("" + _toDisplayString(_ctx.msg), 1 /* TEXT */)))}Copy the code

_createTextVNode(" " + _toDisplayString(_ctx.msg), 1 /* TEXT */)

Compared with vue2.x, it can be seen that {{MSG}} node is marked 1 by the compiler during compilation, indicating that the content is of text type. When comparing with the last virtual DOM, only the node with flag is compared, and the content type of the node is also determined by flag information. It is more efficient than full comparison of VUe2. X

The Patch Flag types are as follows:

export const enum PatchFlags {
  /** * Indicates an element with dynamic textContent (children fast path) */
  TEXT = 1./ / text

  /** * Indicates an element with dynamic class binding. */
  CLASS = 1 << 1./ / 2 classes

  /** * Indicates an element with dynamic style * The compiler pre-compiles static string styles into static objects * + detects and hoists inline static objects * e.g. style="color: red" and :style="{ color: 'red' }" both get hoisted as * const style = { color: 'red' } * render() { return e('div', { style }) } */
  STYLE = 1 << 2./ / 4 styles

  /** * Indicates an element that has non-class/style dynamic props. * Can also be on a component that has any dynamic props (includes * class/style). when this flag is present, the vnode also has a dynamicProps * array that contains the keys of the props that may change so the runtime * can diff them faster (without having to worry about removed props) */
  PROPS = 1 << 3./ / 8

  /** * Indicates an element with props with dynamic keys. When keys change, a full * diff is always needed to remove the old key. This flag is mutually * exclusive with CLASS, STYLE and PROPS. */
  FULL_PROPS = 1 << 4./ / 16

  /** * Indicates an element with event listeners (which need to be attached * during hydration) */
  HYDRATE_EVENTS = 1 << 5./ / 32

  /** * Indicates a fragment whose children order doesn't change. */
  STABLE_FRAGMENT = 1 << 6./ / 64

  /** * Indicates a fragment with keyed or partially keyed children */
  KEYED_FRAGMENT = 1 << 7./ / 128

  /** * Indicates a fragment with unkeyed children. */
  UNKEYED_FRAGMENT = 1 << 8./ / 256

  /** * Indicates an element that only needs non-props patching, e.g. ref or * directives (onVnodeXXX hooks). since every patched vnode checks for refs * and onVnodeXXX hooks, it simply marks the vnode so that a parent block * will track it. */
  NEED_PATCH = 1 << 9./ / 512

  /** * Indicates a component with dynamic slots (e.g. slot that references a v-for * iterated value, or dynamic slot names). * Components with this flag are always force updated. */
  DYNAMIC_SLOTS = 1 << 10./ / 1024

  /** * Indicates a fragment that was created only because the user has placed * comments at the root level of a template.  This is a dev-only flag since * comments are stripped in production. */
  DEV_ROOT_FRAGMENT = 1 << 11./ / 2048

  /** * SPECIAL FLAGS ------------------------------------------------------------- * Special flags are negative integers.  They are never matched against using * bitwise operators (bitwise matching should only happen in branches where * patchFlag > 0), and are mutually exclusive. When checking for a special * flag, simply check patchFlag === FLAG. */

  /** * Indicates a hoisted static vnode. This is a hint for hydration to skip * the entire sub tree since static content never needs to be updated. */
  HOISTED = -1./** * A special flag that indicates that the diffing algorithm should bail out * of optimized mode. For example, on block fragments created by renderSlot() * when encountering non-compiler generated slots (i.e. manually written * render functions, which should always be fully diffed) * OR manually cloneVNodes */
  BAIL = -2
}

export const PatchFlagNames = {
  [PatchFlags.TEXT]: `TEXT`,
  [PatchFlags.CLASS]: `CLASS`,
  [PatchFlags.STYLE]: `STYLE`,
  [PatchFlags.PROPS]: `PROPS`,
  [PatchFlags.FULL_PROPS]: `FULL_PROPS`,
  [PatchFlags.HYDRATE_EVENTS]: `HYDRATE_EVENTS`,
  [PatchFlags.STABLE_FRAGMENT]: `STABLE_FRAGMENT`,
  [PatchFlags.KEYED_FRAGMENT]: `KEYED_FRAGMENT`,
  [PatchFlags.UNKEYED_FRAGMENT]: `UNKEYED_FRAGMENT`,
  [PatchFlags.NEED_PATCH]: `NEED_PATCH`,
  [PatchFlags.DYNAMIC_SLOTS]: `DYNAMIC_SLOTS`,
  [PatchFlags.DEV_ROOT_FRAGMENT]: `DEV_ROOT_FRAGMENT`,
  [PatchFlags.HOISTED]: `HOISTED`,
  [PatchFlags.BAIL]: `BAIL`
}

Copy the code

Think about:

The diff algorithm updateChildren compares the children of the old and new nodes, which is a 50/50 search algorithm that reduces time complexity compared to simply beginning to end
The diff comparison results in the smallest modification unit, and then the real DOM is updated. Why not make a one-time comparison and then modify the DOM? If so, there will be a problem that the modified units need to be recorded, which requires space to store these intermediate values, increasing complexity and wasting space
From the point of view of search, hash search is more convenient, but in fact, from the overall code, virtual node is mainly an increase, deletion and change operation, and using hash may take up more space, to measure, sacrifice a little time consumption. It’s worth more than trading hash space for time.

References:

Explain the DIff algorithm of VUE

Analyze the diff algorithm of vue2.0

VirtualDOM with Diff (Vue implementation)

Vue-diff algorithm in detail