【校招VIP】深入探究Vue diff算法- 校招VIP

转载声明：文章链接：https://blog.csdn.net/A_D_H_E_R_E/article/details/120293410

1.虚拟dom
虚拟 DOM （ Virtual DOM ）是对 DOM 的 JS 抽象表示，它们是 JS 对象，能够描述 DOM 结构和关系。应用的各种状态变化会作用于虚拟DOM ，最终映射到 DOM 上。
优点
1. 虚拟 DOM 轻量、快速：当它们发生变化时通过新旧虚拟 DOM 比对可以得到最小 DOM 操作量，从
而提升性能

patch(vnode, h('div#app', obj.foo))

2. 跨平台：将虚拟dom更新转换为不同运行时特殊操作实现跨平台

const patch = init([snabbdom_style.default])
 
patch(vnode, h('div#app', {style:{color:'red'}}, obj.foo))

3. 兼容性：还可以加入兼容性代码增强操作的兼容性
1.1 真实dom和虚拟dom的对照
真实dom

<div>
    <p>Hello World</p>
</div>

虚拟dom

let vnode = {
    tag: 'div',
    children:[ {tag:'p', text:'Hello World'}]
}

2. diff算法
2.1 patch函数
2.1.1 patch实现
所在文件 patch core\vdom\patch.js
首先进行树级别比较，可能有三种情况：增删改。
1. new VNode 不存在就删；
2. old VNode 不存在就增；
3. 都存在就执行 diff 执行更新

return function patch (oldVnode, vnode, hydrating, removeOnly) {
    // 如果新的虚拟dom树不存在，则删除
    if (isUndef(vnode)) {
      if (isDef(oldVnode)) invokeDestroyHook(oldVnode)
      return
    }
    let isInitialPatch = false
    const insertedVnodeQueue = []
 
    //  如果老的vdom不存在，则新增
    if (isUndef(oldVnode)) {
      // empty mount (likely as component), create new root element
      isInitialPatch = true
      createElm(vnode, insertedVnodeQueue)
    } else {
 
      // 如果传入的是真实节点，在进行初始化操作
      const isRealElement = isDef(oldVnode.nodeType)
 
      if (!isRealElement && sameVnode(oldVnode, vnode)) {
        // patch existing root node
        // 存在新旧vdom
        patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly)
      } else {
        // 初始化过程，创建新的dom, 追加到body, 删除数组
        if (isRealElement) {
          // mounting to a real element
          // check if this is server-rendered content and if we can perform
          // a successful hydration.
 
          // 如果存在真实的节点，存在data-server-render属性
          if (oldVnode.nodeType === 1 && oldVnode.hasAttribute(SSR_ATTR)) {
            // 当旧的Vnode是服务端渲染元素，hydrating记为true
            oldVnode.removeAttribute(SSR_ATTR)
            hydrating = true
          }
           // 需要用hydrate函数将虚拟DOM和真实DOM进行映射
          if (isTrue(hydrating)) {
            // 需要合并到真实DOM上
            if (hydrate(oldVnode, vnode, insertedVnodeQueue)) {
              // 调用insert钩子
              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.'
              )
            }
          }
          // either not server-rendered, or hydration failed.
          // create an empty node and replace it
          
          // 如果不是服务端渲染元素或者合并到真实DOM失败，则创建一个空的Vnode节点去替换它
          oldVnode = emptyNodeAt(oldVnode)
        }
 
        // replacing existing element
        const oldElm = oldVnode.elm
        const parentElm = nodeOps.parentNode(oldElm)
 
        // create new 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)
        )
 
        // 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)
        }
      }
    }
 
    invokeInsertHook(vnode, insertedVnodeQueue, isInitialPatch)
    return vnode.elm
  }

3. patchVnode
比较两个 VNode ，包括三种类型操作：属性更新、文本更新、子节点更新
具体规则如下：
1. 新老节点均有 children 子节点，则对子节点进行 diff 操作，调用 updateChildren
2. 如果老节点没有子节点而新节点有子节点，先清空老节点的文本内容，然后为其新增子节点。
3. 当新节点没有子节点而老节点有子节点的时候，则移除该节点的所有子节点。
4. 当新老节点都无子节点的时候，只是文本的替换。

let i
    const data = vnode.data
    if (isDef(data) && isDef(i = data.hook) && isDef(i = i.prepatch)) {
      i(oldVnode, vnode)
    }
 
    // 看看新旧节点是否有孩子队列
    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)
    }
 
    // 判断是否是元素， 没有文本则是Element
    if (isUndef(vnode.text)) {
 
      // 都有孩子
      if (isDef(oldCh) && isDef(ch)) {
        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)) {
        // 只有老节点有孩子
        removeVnodes(oldCh, 0, oldCh.length - 1)
      } else if (isDef(oldVnode.text)) {
        // 老节点有文本
        nodeOps.setTextContent(elm, '')
      }
    } else if (oldVnode.text !== vnode.text) {
      // 新旧都是文本，且不相同
      nodeOps.setTextContent(elm, vnode.text)
    }
    if (isDef(data)) {
      if (isDef(i = data.hook) && isDef(i = i.postpatch)) i(oldVnode, vnode)
    }
  }

4. updateChildren
重点来了！！！！
updateChildren 主要作用是用一种较高效的方式比对新旧两个 VNode 的 children 得出最小操作补丁。执行一个双循环是传统方式，vue 中针对 web 场景特点做了特别的算法优化，我们看图说话：

分四种情况：
1. 老头结点和新头结点相同，直接patchVnode
2. 老尾结点和新尾巴结点相同，直接patchVnode
3. 老头结点和新尾结点相同，patchVnode的同时还要把老头结点放到老尾结点后面去
4. 老尾结点和新头结点相同，patchVnode的同时将老尾结点放到老头结点前面去

如果以上四种情况都不符合：
则在老的节点队列中寻找循环寻找与新头结点满足sameVnode的节点，然后移到老头结点前面去，新头结点下标向后移一位
当然也有可能找不到这样的节点，那么就新建一个节点，并且将它放到老节点队列最前面去

最后老节点队列和新节点队列长度可能不一样，就会有一个队列没有遍历完，那么就会有有一下两种情况：
批量增加（老节点遍历完了，还有没遍历的新节点就批量创建增加上去）
批量删除（新节点遍历完了，还有没遍历的老节点就批量删除掉）
直接上源码

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
    const canMove = !removeOnly
 
    if (process.env.NODE_ENV !== 'production') {
      checkDuplicateKeys(newCh)
    }
 
    /**
     * 两边向中间靠拢，dfs
     */
    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if (isUndef(oldStartVnode)) {
        // 老的开始节点不存在，下标后移一位
        oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
 
      } else if (isUndef(oldEndVnode)) {
        // 老的尾节点不存在，下标前移一位
        oldEndVnode = oldCh[--oldEndIdx]
 
      } else if (sameVnode(oldStartVnode, newStartVnode)) {
        // 新旧的开始节点相同，同时+1
        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
        oldStartVnode = oldCh[++oldStartIdx]
        newStartVnode = newCh[++newStartIdx]
 
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
        // 新旧的结束节点相同， 同时-1
        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 {
        // 4种猜想都没有找到相同的，才被迫进行循环查找
 
        if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
        
        // 查找在老的数组中的索引key
        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 {
            // 只有key相同，但是内容不相同
            // 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)
    }
  }