关于前端:浅读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 = 0let newStartIdx = 0let oldEndIdx = oldCh.length - 1let oldStartVnode = oldCh[0]let oldEndVnode = oldCh[oldEndIdx]let newEndIdx = newCh.length - 1let 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源码的摸索画上句号。