关于前端:浅读vue源码2x之diff算法

在我响应式原理那篇文章中，咱们曾经理解到，当 vue 实例被检测的属性扭转时，会产生视图更新，即调用 updateComponent 函数对视图进行从新渲染。

updateComponent = () => {vm._update(vm._render(), hydrating)
}

在该函数中，执行 vm._render()时，会去获取相干属性最新状况，从而失去一个新的 Vnode。

而在 vm._update()函数中，会将新节点挂载到实在 DOM 元素上。须要留神的是，该函数并不是简略粗犷地把旧的 Vnode 节点删除，再间接挂上新的 Vnode 节点，而是会调用 diff 算法，这也是 vue 高效更新视图的外围。

进入 vm._update() 函数(core/instance/lifecycle.js)

Vue.prototype._update = function (vnode: VNode, hydrating?: boolean) {
  const vm: Component = this
  const prevEl = vm.$el// vue 实例挂载的实在 dom 节点
  const prevVnode = vm._vnode// 旧的 vnode 节点
  const prevActiveInstance = activeInstance
  activeInstance = vm
  vm._vnode = vnode// 新的 vnode 节点
  // Vue.prototype.__patch__ is injected in entry points
  // based on the rendering backend used.
  if (!prevVnode) {// 第一次将 vue 实例挂载到 dom 节点
    // initial render
    vm.$el = vm.__patch__(vm.$el, vnode, hydrating, false /* removeOnly */)
  } else {// 节点的更新，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}
  // updated hook is called by the scheduler to ensure that children are
  // updated in a parent's updated hook.
}

抓住问题的外围，咱们只关注 vm.patch()函数。

在 core/platform/web/runtime/index.js，曾经将 Vue.prototype.patch指向 patch() 函数。

所以咱们进入 core/vdom/patch.js

return function patch (oldVnode, vnode, hydrating, removeOnly) {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)
  } else {const isRealElement = isDef(oldVnode.nodeType)// 只有实在 dom 元素才有 nodeType 属性
    if (!isRealElement && sameVnode(oldVnode, vnode)) {// 都为虚构节点且同类型
      // patch existing root node
      patchVnode(oldVnode, vnode, insertedVnodeQueue, removeOnly)
    } else {...// oldVnode 为实在 dom 节点，或两个虚构节点不为同类型}
  }
  invokeInsertHook(vnode, insertedVnodeQueue, isInitialPatch)
  return vnode.elm
}

输出：新旧 Vnode 节点。(首次渲染 oldVnode 为实在 dom 元素)
输入：节点已挂载到的实在 dom 节点。
先看一下 Vnode 节点有哪些属性。(core/vdom/vnode.js)

constructor (
  tag?: string,
  data?: VNodeData,
  children?: ?Array<VNode>,
  text?: string,
  elm?: Node,
  context?: Component,
  componentOptions?: VNodeComponentOptions,
  asyncFactory?: Function
) {
  this.tag = tag// 标签名
  this.data = data// 数据信息
  this.children = children// 子节点
  this.text = text// 文本
  this.elm = elm// 虚构节点挂载到的实在 dom 节点
  this.ns = undefined
  this.context = context
  this.fnContext = undefined
  this.fnOptions = undefined
  this.fnScopeId = undefined
  this.key = data && data.key
  this.componentOptions = componentOptions
  this.componentInstance = undefined
  this.parent = undefined
  this.raw = false
  this.isStatic = false// 是否为动态节点
  this.isRootInsert = true
  this.isComment = false// 是否为正文节点
  this.isCloned = false
  this.isOnce = false
  this.asyncFactory = asyncFactory
  this.asyncMeta = undefined
  this.isAsyncPlaceholder = false
}

而后回到 patch(preVnode,vnode) 函数

return function patch (oldVnode, vnode, hydrating, removeOnly) {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)
  } else {const isRealElement = isDef(oldVnode.nodeType)// 只有实在 dom 元素才有 nodeType 属性
    if (!isRealElement && sameVnode(oldVnode, vnode)) {// 都为虚构节点且同类型
      // patch existing root node
      patchVnode(oldVnode, vnode, insertedVnodeQueue, removeOnly)
    } else {...// oldVnode 为实在 dom 节点，或两个虚构节点不为同类型}
  }
  invokeInsertHook(vnode, insertedVnodeQueue, isInitialPatch)
  return vnode.elm
}

整个函数，针对新旧节点，分为四种状况：

1. 当新节点不存在：

若旧节点存在，则销毁旧节点，否则间接返回。

2. 当旧节点不存在：

直接插入新节点。

3. 当新旧节点都为虚构节点且同类型：

调用 parchVnode()函数，更新节点。

4.oldVnode 为实在 dom 节点，或两个虚构节点不为同类型：

间接挂载新节点，或销毁旧节点，插入新节点。

而 diff 算法的高效，在于第三种状况，即 节点的更新。

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

通过 sameVnode() 函数来判断是否是同一类型：即只有当 key、tag、isComment（是否为正文节点）、data 同时定义（或不定义），同时满足当标签类型为 input 的时候 type 雷同的状况。

接下来看看要害的 patchVnode() 函数。

function patchVnode (oldVnode, vnode, insertedVnodeQueue, removeOnly) {if (oldVnode === vnode) {// 新旧节点完全相同
    return
  }
  const elm = vnode.elm = oldVnode.elm// 要被挂载到的 DOM 节点
  if (isTrue(oldVnode.isAsyncPlaceholder)) {// 异步占位
    if (isDef(vnode.asyncFactory.resolved)) {hydrate(oldVnode.elm, vnode, insertedVnodeQueue)
    } else {vnode.isAsyncPlaceholder = true}
    return
  }
  // 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 &&// 两者 key 雷同
    (isTrue(vnode.isCloned) || isTrue(vnode.isOnce))// 新节点为克隆节点或有 v -once 属性
  ) {
    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)
  }
  if (isUndef(vnode.text)) // 新节点不为文本节点
    if (isDef(oldCh) && isDef(ch)) {// 新旧节点的子节点都存在
      if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
    } else if (isDef(ch)) {// 只有新节点的子节点存在
      if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')
      addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
    } else if (isDef(oldCh)) {// 只有旧节点的子节点存在
      removeVnodes(elm, 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)
  }
}

看下来，该函数针对新旧节点的状况分为以下几个解决分支：

1. 新旧节点完全相同，不解决。

2. 旧节点为异步占位，不解决。

3. 新旧节点为动态节点，且两者的 key 完全相同，且新节点为克隆节点或蕴含 v -once 属性，将旧节点的 componentInstance 函数赋给新节点。

4. 当新节点为文本节点时，间接把文本挂载到 dom 元素上。

5. 当新节点不为文本节点时：

(1)新旧节点的子节点都不存在，若旧节点为文本节点，则清空 dom 元素的文本。

(2)只有旧节点的子节点存在，则革除旧节点的所有子节点。

(3)只有新节点的子节点存在，清空旧节点的文本，插入新节点的子节点。

(4)当新旧节点的子节点都存在且不等，调用 updateChildren()函数。

接下来看看 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
  const canMove = !removeOnly
  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 {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)
  }
}

很长，但咱们逐渐剖析。

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

首先咱们定义 oldStartIdx,oldEndIdx,newStartIdx,newEndIdx 为新旧子节点序列的首尾索引，oldStartVnode,oldEndVnode,newStartVnode,newEndVnode 为上四个索引对应的实在节点。

接着，进入 while 循环，终止条件是 oldStartIdx > oldEndIdx 或 newStartIdx > newEndIdx。

if (isUndef(oldStartVnode)) {oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
} else if (isUndef(oldEndVnode)) {oldEndVnode = oldCh[--oldEndIdx]

当 oldStartVnode 或者 oldEndVnode 不存在的时候，oldStartIdx 与 oldEndIdx 持续向两头聚拢，并更新对应的 oldStartVnode 与 oldEndVnode 的指向。

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]

头节点雷同，再次调用 patchVnode()函数，对应索引后移。
尾节点雷同，再次调用 patchVnode()函数，对应索引前移。

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]

当旧节点的子节点序列头节点与新节点的子节点序列尾节点雷同时，首先再次调用 patchVnode() 函数，接着将以后的 oldStartVnode 插入到 oldEndVnode 前面，最初挪动相干的两个索引。

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]

当旧节点的子节点序列尾节点与新节点的子节点序列首节点雷同时，首先再次调用 patchVnode() 函数，接着将以后的 oldEndVnode 插入到 oldStartVnode 后面，最初挪动相干的两个索引。

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

当以上状况都不满足时，会进入该 else 分支。
首先进入 createKeyToOldIdx() 函数：

function createKeyToOldIdx (children, beginIdx, endIdx) {
  let i, key
  const map = {}
  for (i = beginIdx; i <= endIdx; ++i) {key = children[i].key
    if (isDef(key)) map[key] = i
  }
  return map
}

返回一个对于以后旧节点子节点序列的，key 与 index 索引对应的一个 map 表。
例如：

[{xx: xx, key: 'key0'},
  {xx: xx, key: 'key1'},
  {xx: xx, key: 'key2'}
]

在通过 createKeyToOldIdx 转化当前会变成：

{
  key0: 0,
  key1: 1,
  key2: 2
}

当初，咱们就能够先剖析以下代码了：

if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)// 提供一个 map 构造
idxInOld = isDef(newStartVnode.key)// 找到以后 newStartVnode 的 key 在 oldCh 中对应的索引
  ? oldKeyToIdx[newStartVnode.key]
  : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)// 对应 newStartVnode 的 key 不存在的状况

先创立一个 key 与 index 索引的 map 表，找到以后 newStartVnode 的 key 在旧子节点序列 oldCh 上对应的索引。
注：findIdxInold()函数用来应答 newStartVnode 的 key 不存在的状况，此函数中会依据 newStartVnode 对以后旧节点的子节点序列再做一次遍历。代码如下：

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

if (isUndef(idxInOld)) { // New element
  createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
}

如果 idxInOld 不存在，阐明在以后的 newStartVnode 是新增的，此时依据 newStartVnode 创立一个新节点插入到 oldStartVnode 后面。(最初会将 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]

如果 idxInOld 存在，比拟新旧节点：
(1)当两者是同类型节点：

首先，再次调用 patchVnode()，接着，销毁 idxInOld 指向的节点即 vnodeToMove，最初，将 vnodeToMove 插入到 oldStartVnode 后面。(最初会将 newStartIdx 索引后移)
(2)当两者不是同类型节点：
依据 newStartVnode 创立一个新节点插入到 oldStartVnode 后面。(最初会将 newStartIdx 索引后移)
最初，咱们来到 while 循环完结后的收尾阶段。

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

如果 oldStartIdx > oldEndIdx，阐明老节点比对完了，然而新节点还有多的，须要将新节点插入到实在 DOM 中去，调用 addVnodes 将这些节点插入即可。

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

如果 newStartIdx > newEndIdx 条件，阐明新节点比对完了，老节点还有多，将这些无用的老
节点通过 removeVnodes 批量删除即可。
至此，咱们实现了对 diff 算法的解析，再从头梳理一下：
首先，diff 算法的终点是 patch() 函数，用于比拟新旧节点。针对比对的不同状况，只有当节点为同一类型时，会触发节点的更新，即 patchVnode() 函数 (其余状况为粗犷的增删)。
接着，在 patchVnode() 函数中，针对节点的比对状况，只有当新节点不为文本节点且蕴含子节点时，会触发对两者子节点的比对，即 updateChildren() 函数 (其余状况为不解决, 批改元素文本和革除元素文本)
最初，在 updateChildren() 函数中，针对新旧节点的子节点序列的比对状况，做出不同的解决。例如，旧节点的挪动，删除和新节点的插入。
到此为止，咱们曾经钻研了 vue 三大外围中的两个，即响应式原理和 diff 算法，而剩下的模板编译, 将会波及到编译原理的常识，着实简单，等有工夫再去缓缓钻研。但对框架的摸索，不应该只停留在源码浏览，我将会实现一个简易版的 vue 放到 github 上，为这两个星期对 vue 源码的摸索画上句号。

关于前端:浅读vue源码2x之diff算法

Just My Socks（注册教程 内含优惠码）

Just My Socks（注册教程内含优惠码）