关于vue.js:Vue中的diff算法深度解析

39次阅读

共计 34134 个字符,预计需要花费 86 分钟才能阅读完成。

模板 tamplate 通过 parseoptimizegenerate 等一些列操作之后,把 AST 转为 render function code 进而生成虚构 VNode, 模板编译阶段根本曾经实现了,那么这一章,咱们来探讨一下Vue 中的一个算法策略 –dom diff 首先来介绍下什么叫dom diff

什么是虚构 dom

咱们通过后面的章节学习曾经晓得,要晓得渲染 实在 DOM的开销是很大的,比方有时候咱们批改了某个数据,如果 间接渲染 到实在 dom 上会引起 整个 dom 树 重绘 重排,有没有可能咱们只更新咱们批改的那一小块 dom 而不要更新整个 dom 呢?

为了解决这个问题,咱们的解决方案是 – 依据 实在 DOM生成一颗 virtual DOM,当virtual DOM 某个节点的数据扭转后会生成一个新的 Vnode,而后Vnode 和 oldVnode 作比照,发现有不一样的中央就间接批改在实在的 DOM 上,而后使 oldVnode 的值为 Vnode。这也就是咱们所说的一个 虚构 dom diff的过程

图示

传统的 Diff 算法所消耗的工夫复杂度为 O(n^3), 那么这个O(n^3) 是怎么算进去的?

  1. 传统 diff 算法工夫复杂度为 n(第一次 Old 与新的所有节点比照)—-O(n)
  2. 传统 diff 算法工夫复杂度为 n(第二次 Old 树的所有节点与新的所有节点比照)—-O(n^2)
  3. 新树的生成,节点可变编辑,工夫复杂度为 n(遍历以后树)—-O(n^3)

第一次比照 (1:n)

第二次比照 (1:n)

第 n 次比照 (n:n)

到这里那么 n 个节点与 n 个节点暴力比照就比照完了,那么就开启第三轮可编辑树节点遍历,更改之后的树由 vdom(old)vdom(new)

故而传统 diff 算法 O(n^3) 是这么算进去的, 然而这不是咱们明天钻研的重点。

古代 diff 算法

古代 diff 算法 策略说的是,同层级比拟,广度优先

那么这里的话咱们要深刻源码了,在深刻源码之前咱们在心中应该造成这样一个概念,整个 diff 的流程是什么?咱们再比照着源码解读

diff 算法流程图

深刻源码

咱们在 Vue 初始化的时候调用 lifecycleMixin 函数的时候,会给 Vue 的原型上挂载 _update 办法

_update

Vue.prototype._update = function (vnode: VNode, hydrating?: boolean) {
    const vm: Component = this
    if (vm._isMounted) {
      // 会调用申明周期中的 beforeUpdate 回调函数
      callHook(vm, 'beforeUpdate')
    }
    const prevEl = vm.$el
    const prevVnode = vm._vnode
    const prevActiveInstance = activeInstance
    activeInstance = vm
    vm._vnode = vnode
    // Vue.prototype.__patch__ is injected in entry points
    // based on the rendering backend used.
    // 若组件自身的 vnode 未生成, 间接用传入的 vnode 生成 dom
    if (!prevVnode) {
      // initial render
      vm.$el = vm.__patch__(
        vm.$el, vnode, hydrating, false /* removeOnly */,
        vm.$options._parentElm,
        vm.$options._refElm
      )
      // no need for the ref nodes after initial patch
      // this prevents keeping a detached DOM tree in memory (#5851)
      vm.$options._parentElm = vm.$options._refElm = null
    } else {
      // 对新旧 vnode 进行 diff
      // updates
      vm.$el = vm.__patch__(prevVnode, vnode)
    }
    activeInstance = prevActiveInstance
    // 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}

咱们在这里能够看到 vm.$el = vm.__patch__ 办法,追根溯源 _patch_ 的定义:

参考 vue 实战视频解说:进入学习

Vue.prototype.__patch__ = inBrowser ? patch : noop

可见这里是一个浏览器环境的甄别,如果在浏览器环境中,咱们会执行 patch,不在的话会执行 noop,这是一个 util 外面的一个办法,用来跨平台的,咱们这里临时不思考,接着咱们去看 patch 的具体实现 ./patch 文件,

import * as nodeOps from 'web/runtime/node-ops'
import {createPatchFunction} from 'core/vdom/patch'
import baseModules from 'core/vdom/modules/index'
import platformModules from 'web/runtime/modules/index'
const modules = platformModules.concat(baseModules)

export const patch: Function = createPatchFunction({nodeOps, modules})

createPatchFunction 函数

/** * 创立 patch 办法 */
export function createPatchFunction (backend) {
  let i, j
  const cbs = {}

  const {modules, nodeOps} = backend

  for (i = 0; i < hooks.length; ++i) {cbs[hooks[i]] = []
    for (j = 0; j < modules.length; ++j) {if (isDef(modules[j][hooks[i]])) {cbs[hooks[i]].push(modules[j][hooks[i]])
      }
    }
  }

  function emptyNodeAt (elm) {return new VNode(nodeOps.tagName(elm).toLowerCase(), {}, [], undefined, elm)
  }

  /**   * 创立一个回调办法, 用于删除节点   *    *    */
  function createRmCb (childElm, listeners) {function remove () {if (--remove.listeners === 0) {removeNode(childElm)
      }
    }
    remove.listeners = listeners
    return remove
  }

  function removeNode (el) {const parent = nodeOps.parentNode(el)
    // element may have already been removed due to v-html / v-text
    if (isDef(parent)) {nodeOps.removeChild(parent, el)
    }
  }

  /**   * 通过 vnode 的 tag 判断是否是原生 dom 标签或者组件标签   * 用于创立实在 DOM 节点时, 预先判断 tag 的合法性   */
  function isUnknownElement (vnode, inVPre) {
    return (
      !inVPre &&
      !vnode.ns &&
      !(
        config.ignoredElements.length &&
        config.ignoredElements.some(ignore => {return isRegExp(ignore)
            ? ignore.test(vnode.tag)
            : ignore === vnode.tag
        })
      ) &&
      config.isUnknownElement(vnode.tag)
    )
  }

  let creatingElmInVPre = 0

  // 创立一个节点
  function createElm (
    vnode,
    insertedVnodeQueue,
    parentElm,
    refElm,
    nested,
    ownerArray,
    index
  ) {
    // 节点曾经被渲染, 须要应用一个克隆节点
    if (isDef(vnode.elm) && isDef(ownerArray)) {
      // This vnode was used in a previous render!
      // now it's used as a new node, overwriting its elm would cause
      // potential patch errors down the road when it's used as an insertion
      // reference node. Instead, we clone the node on-demand before creating
      // associated DOM element for it.
      vnode = ownerArray[index] = cloneVNode(vnode)
    }

    // 创立组件节点 详见本文件中的 createComponent 办法
    vnode.isRootInsert = !nested // for transition enter check
    if (createComponent(vnode, insertedVnodeQueue, parentElm, refElm)) {return}

    const data = vnode.data
    const children = vnode.children
    const tag = vnode.tag
    /**     * 如果要创立的节点有 tag 属性, 这里做一下校验     * 如果该节点下面有 v -pre 指令, 间接给 flag 加 1     * 如果没有 v -pre 须要调用 isUnknownElement 判断标签是否非法, 而后给出正告     */
    if (isDef(tag)) {if (process.env.NODE_ENV !== 'production') {if (data && data.pre) {creatingElmInVPre++}
        if (isUnknownElement(vnode, creatingElmInVPre)) {
          warn(
            'Unknown custom element: <' + tag + '> - did you' +
            'register the component correctly? For recursive components,' +
            'make sure to provide the"name"option.',
            vnode.context
          )
        }
      }

      vnode.elm = vnode.ns
        ? nodeOps.createElementNS(vnode.ns, tag)
        : nodeOps.createElement(tag, vnode)
      setScope(vnode)

      /* istanbul ignore if */
      if (__WEEX__) {
        // in Weex, the default insertion order is parent-first.
        // List items can be optimized to use children-first insertion
        // with append="tree".
        const appendAsTree = isDef(data) && isTrue(data.appendAsTree)
        if (!appendAsTree) {if (isDef(data)) {invokeCreateHooks(vnode, insertedVnodeQueue)
          }
          insert(parentElm, vnode.elm, refElm)
        }
        createChildren(vnode, children, insertedVnodeQueue)
        if (appendAsTree) {if (isDef(data)) {invokeCreateHooks(vnode, insertedVnodeQueue)
          }
          insert(parentElm, vnode.elm, refElm)
        }
      } else {createChildren(vnode, children, insertedVnodeQueue)
        if (isDef(data)) {invokeCreateHooks(vnode, insertedVnodeQueue)
        }
        insert(parentElm, vnode.elm, refElm)
      }

      if (process.env.NODE_ENV !== 'production' && data && data.pre) {creatingElmInVPre--}
    } else if (isTrue(vnode.isComment)) {vnode.elm = nodeOps.createComment(vnode.text)
      insert(parentElm, vnode.elm, refElm)
    } else {vnode.elm = nodeOps.createTextNode(vnode.text)
      insert(parentElm, vnode.elm, refElm)
    }
  }
  /**   * 创立组件   * 如果组件实例曾经存在, 只须要初始化组件并从新激活组件即可   */
  function createComponent (vnode, insertedVnodeQueue, parentElm, refElm) {
    let i = vnode.data
    if (isDef(i)) {const isReactivated = isDef(vnode.componentInstance) && i.keepAlive
      if (isDef(i = i.hook) && isDef(i = i.init)) {i(vnode, false /* hydrating */, parentElm, refElm)
      }
      // after calling the init hook, if the vnode is a child component
      // it should've created a child instance and mounted it. the child
      // component also has set the placeholder vnode's elm.
      // in that case we can just return the element and be done.
      if (isDef(vnode.componentInstance)) {initComponent(vnode, insertedVnodeQueue)
        if (isTrue(isReactivated)) {reactivateComponent(vnode, insertedVnodeQueue, parentElm, refElm)
        }
        return true
      }
    }
  }

  /**   * 初始化组件   * 次要的操作是已插入的 vnode 队列, 触发 create 钩子, 设置 style 的 scope, 注册 ref   */
  function initComponent (vnode, insertedVnodeQueue) {if (isDef(vnode.data.pendingInsert)) {insertedVnodeQueue.push.apply(insertedVnodeQueue, vnode.data.pendingInsert)
      vnode.data.pendingInsert = null
    }
    vnode.elm = vnode.componentInstance.$el
    if (isPatchable(vnode)) {invokeCreateHooks(vnode, insertedVnodeQueue)
      setScope(vnode)
    } else {
      // empty component root.
      // skip all element-related modules except for ref (#3455)
      registerRef(vnode)
      // make sure to invoke the insert hook
      insertedVnodeQueue.push(vnode)
    }
  }

  /**   * 激活组件   */
  function reactivateComponent (vnode, insertedVnodeQueue, parentElm, refElm) {
    let i
    // hack for #4339: a reactivated component with inner transition
    // does not trigger because the inner node's created hooks are not called
    // again. It's not ideal to involve module-specific logic in here but
    // there doesn't seem to be a better way to do it.
    let innerNode = vnode
    while (innerNode.componentInstance) {
      innerNode = innerNode.componentInstance._vnode
      if (isDef(i = innerNode.data) && isDef(i = i.transition)) {for (i = 0; i < cbs.activate.length; ++i) {cbs.activate[i](emptyNode, innerNode)
        }
        insertedVnodeQueue.push(innerNode)
        break
      }
    }
    // unlike a newly created component,
    // a reactivated keep-alive component doesn't insert itself
    insert(parentElm, vnode.elm, refElm)
  }

  /**   * 插入节点, 有父节点的插入到后面, 没有的插入到前面   */
  function insert (parent, elm, ref) {if (isDef(parent)) {if (isDef(ref)) {if (ref.parentNode === parent) {nodeOps.insertBefore(parent, elm, ref)
        }
      } else {nodeOps.appendChild(parent, elm)
      }
    }
  }

  function createChildren (vnode, children, insertedVnodeQueue) {if (Array.isArray(children)) {if (process.env.NODE_ENV !== 'production') {checkDuplicateKeys(children)
      }
      for (let i = 0; i < children.length; ++i) {createElm(children[i], insertedVnodeQueue, vnode.elm, null, true, children, i)
      }
    } else if (isPrimitive(vnode.text)) {nodeOps.appendChild(vnode.elm, nodeOps.createTextNode(String(vnode.text)))
    }
  }

  function isPatchable (vnode) {while (vnode.componentInstance) {vnode = vnode.componentInstance._vnode}
    return isDef(vnode.tag)
  }

  function invokeCreateHooks (vnode, insertedVnodeQueue) {for (let i = 0; i < cbs.create.length; ++i) {cbs.create[i](emptyNode, vnode)
    }
    i = vnode.data.hook // Reuse variable
    if (isDef(i)) {if (isDef(i.create)) i.create(emptyNode, vnode)
      if (isDef(i.insert)) insertedVnodeQueue.push(vnode)
    }
  }

  // set scope id attribute for scoped CSS.
  // this is implemented as a special case to avoid the overhead
  // of going through the normal attribute patching process.
  function setScope (vnode) {
    let i
    if (isDef(i = vnode.fnScopeId)) {nodeOps.setStyleScope(vnode.elm, i)
    } else {
      let ancestor = vnode
      while (ancestor) {if (isDef(i = ancestor.context) && isDef(i = i.$options._scopeId)) {nodeOps.setStyleScope(vnode.elm, i)
        }
        ancestor = ancestor.parent
      }
    }
    // for slot content they should also get the scopeId from the host instance.
    if (isDef(i = activeInstance) &&
      i !== vnode.context &&
      i !== vnode.fnContext &&
      isDef(i = i.$options._scopeId)
    ) {nodeOps.setStyleScope(vnode.elm, i)
    }
  }

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

  // 递归调用销毁钩子
  function invokeDestroyHook (vnode) {
    let i, j
    const data = vnode.data
    if (isDef(data)) {if (isDef(i = data.hook) && isDef(i = i.destroy)) i(vnode)
      for (i = 0; i < cbs.destroy.length; ++i) cbs.destroy[i](vnode)
    }
    if (isDef(i = vnode.children)) {for (j = 0; j < vnode.children.length; ++j) {invokeDestroyHook(vnode.children[j])
      }
    }
  }

  /**   * 删除多个节点   * 文本节点能够间接删除, 其余节点须要触发两个钩子   */
  function removeVnodes (parentElm, vnodes, startIdx, endIdx) {for (; startIdx <= endIdx; ++startIdx) {const ch = vnodes[startIdx]
      if (isDef(ch)) {if (isDef(ch.tag)) {removeAndInvokeRemoveHook(ch)
          invokeDestroyHook(ch)
        } else { // Text node
          removeNode(ch.elm)
        }
      }
    }
  }

  function removeAndInvokeRemoveHook (vnode, rm) {if (isDef(rm) || isDef(vnode.data)) {
      let i
      const listeners = cbs.remove.length + 1
      if (isDef(rm)) {
        // we have a recursively passed down rm callback
        // increase the listeners count
        rm.listeners += listeners
      } else {
        // directly removing
        rm = createRmCb(vnode.elm, listeners)
      }
      // recursively invoke hooks on child component root node
      if (isDef(i = vnode.componentInstance) && isDef(i = i._vnode) && isDef(i.data)) {removeAndInvokeRemoveHook(i, rm)
      }
      for (i = 0; i < cbs.remove.length; ++i) {cbs.remove[i](vnode, rm)
      }
      if (isDef(i = vnode.data.hook) && isDef(i = i.remove)) {i(vnode, rm)
      } else {rm()
      }
    } else {removeNode(vnode.elm)
    }
  }

  // diff 操作外围算法
  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
    // 在 transition 中 不能挪动节点
    const canMove = !removeOnly
    // 查看是否有反复的 key
    if (process.env.NODE_ENV !== 'production') {checkDuplicateKeys(newCh)
    }

    // 一共分四种状况探讨, 旧列表第一个与新列表第一个比照, 旧列表最初一个与新列表最初一个比照
    // 而后新列表第一个和旧列表最初一个比照, 新列表最初一个和旧列表第一个比照
    // 之所以要穿插头尾比照, 是为了避免最差的状况呈现
    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)) {patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
        oldStartVnode = oldCh[++oldStartIdx]
        newStartVnode = newCh[++newStartIdx]
      } else if (sameVnode(oldEndVnode, newEndVnode)) {patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
        oldEndVnode = oldCh[--oldEndIdx]
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
        patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)
        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)
        canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
        oldEndVnode = oldCh[--oldEndIdx]
        newStartVnode = newCh[++newStartIdx]
      } else {
        // 以上四种状况都不满足时, 应用新列表第一个 vdom 的 key 去旧列表查找
        // 如果能够找到 key 雷同的元素, 间接进行 patch 而后进入下一次循环
        // 找不到则插入一个新节点
        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)
            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(parentElm, oldCh, oldStartIdx, oldEndIdx)
    }
  }

  /**   * 查看是否有反复的 key   * 一个很简略的遍历查找反复值的操作   * 其实这个 seenKeys 我感觉改成数组会更好, 写成 object 又给每个 key 的 value 置为 true 蛮奇怪的   */
  function checkDuplicateKeys (children) {const seenKeys = {}
    for (let i = 0; i < children.length; i++) {const vnode = children[i]
      const key = vnode.key
      if (isDef(key)) {if (seenKeys[key]) {
          warn(`Duplicate keys detected: '${key}'. This may cause an update error.`,
            vnode.context
          )
        } else {seenKeys[key] = true
        }
      }
    }
  }

  /**   * 在旧的子节点列表寻找类似节点(只查找第一个)   */
  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
    }
  }

  function patchVnode (oldVnode, vnode, insertedVnodeQueue, removeOnly) {
    // 如果 oldVnode 跟 vnode 完全一致,那么不须要做任何事件
    if (oldVnode === vnode) {return}

    const elm = vnode.elm = oldVnode.elm

    if (isTrue(oldVnode.isAsyncPlaceholder)) {if (isDef(vnode.asyncFactory.resolved)) {hydrate(oldVnode.elm, vnode, insertedVnodeQueue)
      } else {vnode.isAsyncPlaceholder = true}
      return
    }
    // 如果 oldVnode 跟 vnode 都是动态节点,且具备雷同的 key
    // 当 vnode 是克隆节点或是 v -once 指令管制的节点时
    // 只须要把 oldVnode.elm 和 oldVnode.child 都复制到 vnode 上,也不必再有其余操作
    // reuse element for static trees.
    // note we only do this if the vnode is cloned -
    // if the new node is not cloned it means the render functions have been
    // reset by the hot-reload-api and we need to do a proper re-render.
    if (isTrue(vnode.isStatic) &&
      isTrue(oldVnode.isStatic) &&
      vnode.key === oldVnode.key &&
      (isTrue(vnode.isCloned) || isTrue(vnode.isOnce))
    ) {
      vnode.componentInstance = oldVnode.componentInstance
      return
    }

    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)
    }
    // 如果 vnode 不是文本节点或正文节点
    if (isUndef(vnode.text)) {
      // 如果 oldVnode 和 vnode 都有子节点,且 2 方的子节点不完全一致,就执行 updateChildren
      if (isDef(oldCh) && isDef(ch)) {if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
      } else if (isDef(ch)) {
        // 如果只有 vnode 有子节点,那就创立这些子节点
        if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')
        addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
        // 如果只有 oldVnode 有子节点,那就把这些节点都删除
      } else if (isDef(oldCh)) {removeVnodes(elm, oldCh, 0, oldCh.length - 1)
        // 如果 oldVnode 和 vnode 都没有子节点,然而 oldVnode 是文本节点或正文节点,就把 vnode.elm 的文本设置为空字符串
      } else if (isDef(oldVnode.text)) {nodeOps.setTextContent(elm, '')
      }
      // 如果 vnode 是文本节点或正文节点,然而 vnode.text != oldVnode.text 时,只须要更新 vnode.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)
    }
  }

  function invokeInsertHook (vnode, queue, initial) {
    // delay insert hooks for component root nodes, invoke them after the
    // element is really inserted
    if (isTrue(initial) && isDef(vnode.parent)) {vnode.parent.data.pendingInsert = queue} else {for (let i = 0; i < queue.length; ++i) {queue[i].data.hook.insert(queue[i])
      }
    }
  }

  let hydrationBailed = false
  // list of modules that can skip create hook during hydration because they
  // are already rendered on the client or has no need for initialization
  // Note: style is excluded because it relies on initial clone for future
  // deep updates (#7063).
  const isRenderedModule = makeMap('attrs,class,staticClass,staticStyle,key')

  // Note: this is a browser-only function so we can assume elms are DOM nodes.
  function hydrate (elm, vnode, insertedVnodeQueue, inVPre) {
    let i
    const {tag, data, children} = vnode
    inVPre = inVPre || (data && data.pre)
    vnode.elm = elm

    if (isTrue(vnode.isComment) && isDef(vnode.asyncFactory)) {
      vnode.isAsyncPlaceholder = true
      return true
    }
    // assert node match
    if (process.env.NODE_ENV !== 'production') {if (!assertNodeMatch(elm, vnode, inVPre)) {return false}
    }
    if (isDef(data)) {if (isDef(i = data.hook) && isDef(i = i.init)) i(vnode, true /* hydrating */)
      if (isDef(i = vnode.componentInstance)) {
        // child component. it should have hydrated its own tree.
        initComponent(vnode, insertedVnodeQueue)
        return true
      }
    }
    if (isDef(tag)) {if (isDef(children)) {
        // empty element, allow client to pick up and populate children
        if (!elm.hasChildNodes()) {createChildren(vnode, children, insertedVnodeQueue)
        } else {
          // v-html and domProps: innerHTML
          if (isDef(i = data) && isDef(i = i.domProps) && isDef(i = i.innerHTML)) {if (i !== elm.innerHTML) {
              /* istanbul ignore if */
              if (process.env.NODE_ENV !== 'production' &&
                typeof console !== 'undefined' &&
                !hydrationBailed
              ) {
                hydrationBailed = true
                console.warn('Parent:', elm)
                console.warn('server innerHTML:', i)
                console.warn('client innerHTML:', elm.innerHTML)
              }
              return false
            }
          } else {
            // iterate and compare children lists
            let childrenMatch = true
            let childNode = elm.firstChild
            for (let i = 0; i < children.length; i++) {if (!childNode || !hydrate(childNode, children[i], insertedVnodeQueue, inVPre)) {
                childrenMatch = false
                break
              }
              childNode = childNode.nextSibling
            }
            // if childNode is not null, it means the actual childNodes list is
            // longer than the virtual children list.
            if (!childrenMatch || childNode) {
              /* istanbul ignore if */
              if (process.env.NODE_ENV !== 'production' &&
                typeof console !== 'undefined' &&
                !hydrationBailed
              ) {
                hydrationBailed = true
                console.warn('Parent:', elm)
                console.warn('Mismatching childNodes vs. VNodes:', elm.childNodes, children)
              }
              return false
            }
          }
        }
      }
      if (isDef(data)) {
        let fullInvoke = false
        for (const key in data) {if (!isRenderedModule(key)) {
            fullInvoke = true
            invokeCreateHooks(vnode, insertedVnodeQueue)
            break
          }
        }
        if (!fullInvoke && data['class']) {
          // ensure collecting deps for deep class bindings for future updates
          traverse(data['class'])
        }
      }
    } else if (elm.data !== vnode.text) {elm.data = vnode.text}
    return true
  }

  function assertNodeMatch (node, vnode, inVPre) {if (isDef(vnode.tag)) {return vnode.tag.indexOf('vue-component') === 0 || (!isUnknownElement(vnode, inVPre) &&
        vnode.tag.toLowerCase() === (node.tagName && node.tagName.toLowerCase())
      )
    } else {return node.nodeType === (vnode.isComment ? 8 : 3)
    }
  }
  /**   * 这里返回一个 patch 函数供后续对 vnode 进行 patch 操作   * 这里的 patch 操作是指, 将 oldVnode 对应的实在 DOM 更改为 vnode 对应的实在 DOM, 所须要的最低性能开销的操作(或者说是较低)   * 参数中的 oldVnode 是更新前的旧节点, vnode 是将要更新的新节点, hydrating 是一个 flag 标识是否与原生 DOM 混合, removeOnly 是在过渡动画中应用   */
  return function patch (oldVnode, vnode, hydrating, removeOnly, parentElm, refElm) {
    // 这里很简略, 如果新节点不存在, 旧节点也不存在, 无需任何操作, 如果新节点不存在, 但旧节点存在, 阐明须要删除旧节点, 调用一个销毁钩子
    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
      isInitialPatch = true
      createElm(vnode, insertedVnodeQueue, parentElm, refElm)
    } else {
      // 走到这里 阐明新旧节点都存在, 这时比较复杂, 分几种状况解决 
      // 先通过 nodeType 判断是否是真正的节点, 真正的节点 nodeType 取值范畴是 1~12
      // vue 里罕用的根本只有三种 1 代表是 dom 元素节点 3 是文本节点 8 是正文节点
      const isRealElement = isDef(oldVnode.nodeType)
      if (!isRealElement && sameVnode(oldVnode, vnode)) {
        // patch existing root node
        // 惯例状况下, 新旧节点是类似节点, 对新旧节点做具体的比照操作
        patchVnode(oldVnode, vnode, insertedVnodeQueue, removeOnly)
      } else {if (isRealElement) {
          // 当新旧节点不是类似节点, 旧节点是一个实在节点时
          // mounting to a real element
          // check if this is server-rendered content and if we can perform
          // a successful hydration.
          // 服务端渲染非凡解决
          if (oldVnode.nodeType === 1 && oldVnode.hasAttribute(SSR_ATTR)) {oldVnode.removeAttribute(SSR_ATTR)
            hydrating = true
          }

          // 须要用 hydrate 函数将虚构 DOM 和实在 DOM 进行映射
          if (isTrue(hydrating)) {if (hydrate(oldVnode, vnode, insertedVnodeQueue)) {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
          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(parentElm, [oldVnode], 0, 0)
        } else if (isDef(oldVnode.tag)) {invokeDestroyHook(oldVnode)
        }
      }
    }

    invokeInsertHook(vnode, insertedVnodeQueue, isInitialPatch)
    return vnode.elm
  }
}

能够看到 patch 接管的参数

  1. oldVnode:旧的虚构节点
  2. vnode:新的虚构节点
  3. hydrating:是否映射
  4. removeOnly:标识
  5. parentElm:父节点
  6. refElm:被插入之后的占位符

那么外围 diff 代码在于 sameVnodecreateElmpatchVNode咱们顺次开展来说

sameVnode

顾名思义能够看判断两个节点是不是同一个节点

function sameVnode (a, b) {
  return (
    a.key === b.key && (
      (
        a.tag === b.tag &&
        a.isComment === b.isComment &&
        isDef(a.data) === isDef(b.data) &&
        sameInputType(a, b)
      ) || (isTrue(a.isAsyncPlaceholder) &&
        a.asyncFactory === b.asyncFactory &&
        isUndef(b.asyncFactory.error)
      )
    )
  )
}
/** * 节点 key 必须雷同 * tag、正文、data 是否存在、input 类型是否雷同 * 如果 isAsyncPlaceholder 是 true,则须要 asyncFactory 属性雷同 */

createElm

// 创立一个节点
  function createElm (
    vnode,
    insertedVnodeQueue,
    parentElm,
    refElm,
    nested,
    ownerArray,
    index
  ) {
    // 节点曾经被渲染, 须要应用一个克隆节点
    if (isDef(vnode.elm) && isDef(ownerArray)) {
      // This vnode was used in a previous render!
      // now it's used as a new node, overwriting its elm would cause
      // potential patch errors down the road when it's used as an insertion
      // reference node. Instead, we clone the node on-demand before creating
      // associated DOM element for it.
      vnode = ownerArray[index] = cloneVNode(vnode)
    }

    // 创立组件节点 详见本文件中的 createComponent 办法
    vnode.isRootInsert = !nested // for transition enter check
    if (createComponent(vnode, insertedVnodeQueue, parentElm, refElm)) {return}

    const data = vnode.data
    const children = vnode.children
    const tag = vnode.tag
    /**     * 如果要创立的节点有 tag 属性, 这里做一下校验     * 如果该节点下面有 v -pre 指令, 间接给 flag 加 1     * 如果没有 v -pre 须要调用 isUnknownElement 判断标签是否非法, 而后给出正告     */
    if (isDef(tag)) {if (process.env.NODE_ENV !== 'production') {if (data && data.pre) {creatingElmInVPre++}
        if (isUnknownElement(vnode, creatingElmInVPre)) {
          warn(
            'Unknown custom element: <' + tag + '> - did you' +
            'register the component correctly? For recursive components,' +
            'make sure to provide the"name"option.',
            vnode.context
          )
        }
      }

      vnode.elm = vnode.ns
        ? nodeOps.createElementNS(vnode.ns, tag)
        : nodeOps.createElement(tag, vnode)
      setScope(vnode)

      /* istanbul ignore if */
      if (__WEEX__) {
        // in Weex, the default insertion order is parent-first.
        // List items can be optimized to use children-first insertion
        // with append="tree".
        const appendAsTree = isDef(data) && isTrue(data.appendAsTree)
        if (!appendAsTree) {if (isDef(data)) {invokeCreateHooks(vnode, insertedVnodeQueue)
          }
          insert(parentElm, vnode.elm, refElm)
        }
        createChildren(vnode, children, insertedVnodeQueue)
        if (appendAsTree) {if (isDef(data)) {invokeCreateHooks(vnode, insertedVnodeQueue)
          }
          insert(parentElm, vnode.elm, refElm)
        }
      } else {createChildren(vnode, children, insertedVnodeQueue)
        if (isDef(data)) {invokeCreateHooks(vnode, insertedVnodeQueue)
        }
        insert(parentElm, vnode.elm, refElm)
      }

      if (process.env.NODE_ENV !== 'production' && data && data.pre) {creatingElmInVPre--}
    } else if (isTrue(vnode.isComment)) {vnode.elm = nodeOps.createComment(vnode.text)
      insert(parentElm, vnode.elm, refElm)
    } else {vnode.elm = nodeOps.createTextNode(vnode.text)
      insert(parentElm, vnode.elm, refElm)
    }
  }

此段代码就是创立 实在 dom的目标,下一章谈判到。

patchVnode

  function patchVnode (oldVnode, vnode, insertedVnodeQueue, removeOnly) {
    // 如果 oldVnode 跟 vnode 完全一致,那么不须要做任何事件
    if (oldVnode === vnode) {return}

    const elm = vnode.elm = oldVnode.elm

    if (isTrue(oldVnode.isAsyncPlaceholder)) {if (isDef(vnode.asyncFactory.resolved)) {hydrate(oldVnode.elm, vnode, insertedVnodeQueue)
      } else {vnode.isAsyncPlaceholder = true}
      return
    }
    // 如果 oldVnode 跟 vnode 都是动态节点,且具备雷同的 key
    // 当 vnode 是克隆节点或是 v -once 指令管制的节点时
    // 只须要把 oldVnode.elm 和 oldVnode.child 都复制到 vnode 上,也不必再有其余操作
    // reuse element for static trees.
    // note we only do this if the vnode is cloned -
    // if the new node is not cloned it means the render functions have been
    // reset by the hot-reload-api and we need to do a proper re-render.
    if (isTrue(vnode.isStatic) &&
      isTrue(oldVnode.isStatic) &&
      vnode.key === oldVnode.key &&
      (isTrue(vnode.isCloned) || isTrue(vnode.isOnce))
    ) {
      vnode.componentInstance = oldVnode.componentInstance
      return
    }

    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)
    }
    // 如果 vnode 不是文本节点或正文节点
    if (isUndef(vnode.text)) {
      // 如果 oldVnode 和 vnode 都有子节点,且 2 方的子节点不完全一致,就执行 updateChildren
      if (isDef(oldCh) && isDef(ch)) {if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
      } else if (isDef(ch)) {
        // 如果只有 vnode 有子节点,那就创立这些子节点
        if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')
        addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
        // 如果只有 oldVnode 有子节点,那就把这些节点都删除
      } else if (isDef(oldCh)) {removeVnodes(elm, oldCh, 0, oldCh.length - 1)
        // 如果 oldVnode 和 vnode 都没有子节点,然而 oldVnode 是文本节点或正文节点,就把 vnode.elm 的文本设置为空字符串
      } else if (isDef(oldVnode.text)) {nodeOps.setTextContent(elm, '')
      }
      // 如果 vnode 是文本节点或正文节点,然而 vnode.text != oldVnode.text 时,只须要更新 vnode.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)
    }
  }

具体代码性能曾经解释的很分明了,这里的 addVnodesremoveVnodes就是新增与移除虚构节点,外围代码咱们次要关注一个updateChildren

updateChildren

// diff 操作外围算法
  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
    // 在 transition 中 不能挪动节点
    const canMove = !removeOnly
    // 查看是否有反复的 key
    if (process.env.NODE_ENV !== 'production') {checkDuplicateKeys(newCh)
    }

    // 一共分四种状况探讨, 旧列表第一个与新列表第一个比照, 旧列表最初一个与新列表最初一个比照
    // 而后新列表第一个和旧列表最初一个比照, 新列表最初一个和旧列表第一个比照
    // 之所以要穿插头尾比照, 是为了避免最差的状况呈现
    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)) {patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
        oldStartVnode = oldCh[++oldStartIdx]
        newStartVnode = newCh[++newStartIdx]
      } else if (sameVnode(oldEndVnode, newEndVnode)) {patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
        oldEndVnode = oldCh[--oldEndIdx]
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
        patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)
        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)
        canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
        oldEndVnode = oldCh[--oldEndIdx]
        newStartVnode = newCh[++newStartIdx]
      } else {
        // 以上四种状况都不满足时, 应用新列表第一个 vdom 的 key 去旧列表查找
        // 如果能够找到 key 雷同的元素, 间接进行 patch 而后进入下一次循环
        // 找不到则插入一个新节点
        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)
            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(parentElm, oldCh, oldStartIdx, oldEndIdx)
    }
  }

这里利用了 while 循环与 双指针比照 新旧虚构 dom

定义指针变量

  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] // 新列表起点值

定义循环

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)) {patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
        oldStartVnode = oldCh[++oldStartIdx]
        newStartVnode = newCh[++newStartIdx]
      } else if (sameVnode(oldEndVnode, newEndVnode)) {patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
        oldEndVnode = oldCh[--oldEndIdx]
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
        patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)
        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)
        canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
        oldEndVnode = oldCh[--oldEndIdx]
        newStartVnode = newCh[++newStartIdx]
      } else {
        // 以上四种状况都不满足时, 应用新列表第一个 vdom 的 key 去旧列表查找
        // 如果能够找到 key 雷同的元素, 间接进行 patch 而后进入下一次循环
        // 找不到则插入一个新节点
        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)
            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]
      }
    }

检测 oldStartVnode、oldEndVnode

if (isUndef(oldStartVnode)) {oldStartVnode = oldCh[++oldStartIdx]
} else if (isUndef(oldEndVnode)) {oldEndVnode = oldCh[--oldEndIdx]
}

如果 oldStartVnode 不存在,oldCh起始点向后挪动。如果 oldEndVnode 不存在,oldCh终止点向前挪动。

oldStartVnode 和 newStartVnode 是雷同节点

else if (sameVnode(oldStartVnode, newStartVnode)) {patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
  oldStartVnode = oldCh[++oldStartIdx]
  newStartVnode = newCh[++newStartIdx]
}

如果oldStartVnodenewStartVnode 是雷同节点,则patchVnode,同时彼此向后挪动一位

oldEndVnode 和 newEndVnode 是雷同节点

else if (sameVnode(oldEndVnode, newEndVnode)) {patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
  oldEndVnode = oldCh[--oldEndIdx]
  newEndVnode = newCh[--newEndIdx]
}

如果oldEndVnodenewEndVnode 是雷同节点,则patchVnode,同时彼此向前挪动一位

oldStartVnode 和 newEndVnode 是雷同节点

else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
  patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)
  canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
  oldStartVnode = oldCh[++oldStartIdx]
  newEndVnode = newCh[--newEndIdx]
}

如果 oldStartVnodenewEndVnode 是雷同节点,则先 patchVnode,而后把oldStartVnode 移到 oldCh 最初的地位即可,而后 oldStartIdx 向后挪动一位,newEndIdx向前挪动一位

oldEndVnode 和 newStartVnode 是雷同节点

else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
  patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)
  canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
  oldEndVnode = oldCh[--oldEndIdx]
  newStartVnode = newCh[++newStartIdx]
}

如果 oldEndVnodenewStartVnode 是雷同节点,则先 patchVnode,而后把oldEndVnode 移到 oldCh 最前的地位即可,而后 newStartIdx 向后挪动一位,oldEndIdx向前挪动一位

key 不雷同执行 createElm 办法

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)
}

如果以上条件都不匹配,则查找 oldVnode 中与 vnode 具备雷同 key 的节点,并将查找的后果赋值给 elmToMove。如果找不到雷同key 的节点,则示意是新创建的节点

key 雷同,就认为是同一节点

vnodeToMove = oldCh[idxInOld]
if (sameVnode(vnodeToMove, newStartVnode)) {patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue)
  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)
}
newStartVnode = newCh[++newStartIdx]

若为同一类型就调用 patchVnode,就将对应下标处的oldVnode 设置为 undefined,把vnodeToMove 插入到 oldCh 之前,newStartIdx持续向后挪动。如果两个 vnode 不雷同,视为新元素,执行 createElm创立。

如果老 dom 的开始索引大于完结索引,新 dom 数组大于老 dom 数组,示意新增会调用 addVnodes 办法

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

如果老 dom 的开始索引小于完结索引,新 dom 数组小于老 dom 数组,示意新增会调用 removeVnodes 办法

else if (newStartIdx > newEndIdx) {removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
}

总结

因为 古代 diff 算法策略 同层级比拟,广度优先 ,故而古代算法复杂度为O(n) 这一章咱们讲述了 传统 diff 算法复杂度 ,O(n^3) 到古代的 O(n) 的实现的一个思路,下一章就开始解说比照过后的 vdom 如何 映射 实在 dom

正文完
 0