乐趣区

关于前端:浅读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 源码的摸索画上句号。

退出移动版