diff 算法用来计算出 Virtual DOM 中改变的部分, 然后针对该部分进行 DOM 操作, 而不用重新渲染整个页面, 渲染整个 DOM 结构的过程中开销是很大的, 需要浏览器对 DOM 结构进行重绘与回流, 而 diff 算法能够使得操作过程中只更新修改的那部分 DOM 结构而不更新整个 DOM, 这样能够最小化操作 DOM 结构, 能够最大程度上减少浏览器重绘与回流的规模.
虚拟 DOM
diff 算法的基础是 Virtual DOM,Virtual DOM 是一棵以 JavaScript 对象作为基础的树, 每一个节点称为 VNode, 用对象属性来描述节点, 实际上它是一层对真实 DOM 的抽象, 最终可以通过渲染操作使这棵树映射到真实环境上, 简单来说 Virtual DOM 就是一个 JS 对象, 用以描述整个文档.
在浏览器中构建页面时需要使用 DOM 节点描述整个文档.
- <div class="root" name="root">
- <p>1</p>
- <div>11</div>
- </div>
如果使用 JS 对象去描述上述的节点以及文档, 那么便类似于下面的样子, 当然这不是 vue 中用以描述节点的对象, Vue 中用以描述一个节点的对象包括大量属性, 例如 tag,data,children,text,elm,ns,context,key,componentOptions,componentInstance,parent,raw,isStatic,isRootInsert,isComment,isCloned 等等, 具体的属性可以参阅 Vue 源码的 / dev/src/core/vdom/vnode.JS.
- {
- type: "tag",
- tagName: "div",
- attr: {
- className: "root"
- name: "root"
- },
- parent: null,
- children: [{
- type: "tag",
- tagName: "p",
- attr: {},
- parent: {} /* 父节点的引用 */,
- children: [{
- type: "text",
- tagName: "text",
- parent: {} /* 父节点的引用 */,
- content: "1"
- }]
- },{
- type: "tag",
- tagName: "div",
- attr: {},
- parent: {} /* 父节点的引用 */,
- children: [{
- type: "text",
- tagName: "text",
- parent: {} /* 父节点的引用 */,
- content: "11"
- }]
- }]
- }
当选用 diff 算法进行部分更新的时候就需要比较旧 DOM 结构与新 DOM 结构的不同, 此时就需要 VNode 来描述整个 DOM 结构, 首先根据真实 DOM 生成 Virtual DOM, 当 Virtual DOM 某个节点的数据改变后会生成一个新的 Vnode, 然后通过 newVNode 和 oldVNode 进行对比, 发现有不同之处便通过在 VNode 中 elm 属性相对应的真实 DOM 节点进行 patch 修改于真实 DOM, 然后使旧的 Virtual DOM 赋值为新的 Virtual DOM.
diff 算法
当数据发生改变时, set 方法会让调用 Dep.notify 通知所有订阅者 Watcher 数据发生更新, 订阅者就会调用 patch 进行比较, 然后将相应的部分渲染到真实 DOM 结构.
时间复杂度
首先进行一次完整的 diff 需要 O(n^3)的时间复杂度, 这是一个最小编辑距离的问题, 在比较字符串的最小编辑距离时使用动态规划的方案需要的时间复杂度是 O(mn), 但是对于 DOM 来说是一个树形结构, 而树形结构的最小编辑距离问题的时间复杂度在 30 多年的演进中从 O(m^3n^3)演进到了 O(n^3), 关于这个问题如果有兴趣的话可以研究一下论文 https://grfia.dlsi.ua.es/ml/algorithms/references/editsurvey_bille.pdf.
对于原本想要提高效率而引入的 diff 算法使用 O(n^3)的时间复杂度显然是不太合适的, 如果有 1000 个节点元素将需要进行十亿次比较, 这是一个昂贵的算法, 所以必须有一些妥协来加快速度, 对比较通过一些策略进行简化, 将时间复杂度缩小到 O(n), 虽然并不是最小编辑距离, 但是作为编辑距离与时间性能的折中是一个比较好的解决方案.
diff 策略
上边提到的 O(n)时间复杂度是通过一定策略进行的, React 中提到了两个假设, 在 Vue 中同样适用:
两个不同类型的元素将产生不同的树.
通过渲染器附带 key 属性, 开发者可以示意哪些子元素可能是稳定的.
通俗点说就是:
只进行统一层级的比较, 如果跨层级的移动则视为创建和删除操作.
如果是不同类型的元素, 则认为是创建了新的元素, 而不会递归比较他们的孩子.
如果是列表元素等比较相似的内容, 可以通过 key 来唯一确定是移动还是创建或删除操作.
比较后会出现几种情况, 然后进行相应的操作:
此节点被添加或移除 ->添加或移除新的节点.
属性被改变 ->旧属性改为新属性.
文本内容被改变 ->旧内容改为新内容.
节点 tag 或 key 是否改变 ->改变则移除后创建新元素.
分析
实现 diff 算法的部分在 Vue 源码中的 dev/src/core/vdom/patch.JS 文件中, 不过 Vue 源码的实现比较复杂, 文章分析比较核心的代码部分, 精简过后的最小化版本, commit id 为 43b98fe.
在调用 patch 方法时, 会判断是否是 VNode,isRealElement 其实就是根据有没有 nodeType 来判断是不是真实 DOM,VNode 是不存在这个字段的, 如果不是真实 DOM 元素, 并且这两个节点是相同的, 那就就会进入这个 if 内部, 调用 patchVnode 对 children 进行 diff 以决定该如何更新.
- // line 714
- const isRealElement = isDef(oldVnode.nodeType)
- if (!isRealElement && sameVnode(oldVnode, vnode)) {
- // patch existing root node
- patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly)
- }else{
- // ...
- }
接下来看一下 sameVnode 方法, 判断如何算是相同节点.
- // line 35
- 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 必须相同, 如果都是 undefined 则也是相同的.
DOM 元素的标签必须相同.
如果满足以上条件, 那么就认为是相同的 VNode, 因此就可以进行 patchVnode 操作, 如果不是就认为是完全新的一个 VNode, 就会在上边的判断后执行下面的 createElm.
梳理一下逻辑, 当进入 patch 之后有两种分支可以走, 如果是第一次 patch, 即组件第一次挂载的时候, 或者发现元素的标签不相同了, 那么就认为是不同的元素, 直接进行 createElm 创建新的 DOM 元素进行替换, 否则, 就是对已存在的 DOM 元素进行更新, 那么通过 patchVnode 进行 diff, 有条件的更新以提升性能, 这样其实就实现了策略中原则的第一条, 即两个不同类型的元素将产生不同的树, 只要发现两个元素的类型不同, 我们直接删除旧的并创建一个新的, 而不是去递归比较.
在认为这是两个相同的 VNode 之后, 就需要比较并更新当前元素的差异, 以及递归比较 children, 在 patchVnode 方法中实现了这两部分.
- // line 501
- function patchVnode (oldVnode, vnode, insertedVnodeQueue, removeOnly) {
- // ...
- 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)
- }
- //...
- }
cbs.update 主要是用来更新 attributes 的, 这里的 cbs 其实是从 hooks 中来的, hooks 在 33 行有如下定义, const hooks = ['create', 'activate', 'update', 'remove', 'destroy'], 其是在 VNode 更新的各个阶段进行相应的操作, 这里 cbs.update 包含如下几个回调: updateAttributes,updateClass,updateDOMListeners,updateDOMProps,updateStyle,update,updateDirectives, 其主要都是更新当前结点的一些相关 attributes.
之后需要更新孩子节点, 这时候分两种情况:
如果孩子不是 textNode, 那么需要再分三种情况处理.
如果当前孩子是 textNode 那么直接更新 text 即可.
对孩子是 VNode 的三种情况:
有新孩子无旧孩子, 直接创建新的.
有旧孩子无新孩子, 直接删除旧的.
新旧孩子都有, 那么调用 updateChildren.
- if (isUndef(vnode.text)) {
- if (isDef(oldCh) && isDef(ch)) {
- if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
- } else if (isDef(ch)) {
- if (process.env.NODE_ENV !== 'production') {
- checkDuplicateKeys(ch)
- }
- if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')
- addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
- } else if (isDef(oldCh)) {
- removeVnodes(oldCh, 0, oldCh.length - 1)
- } else if (isDef(oldVnode.text)) {
- nodeOps.setTextContent(elm, '')
- }
- } else if (oldVnode.text !== vnode.text) {
- nodeOps.setTextContent(elm, vnode.text)
- }
当新旧孩子都存在, 那么便调用 updateChildren 方法, 对于每一个孩子节点, 我们依然有这么几种可能:
更新了节点
删除了节点
增加了节点
移动了节点
updateChildren 是 diff 的核心算法, 源代码实现如下.
- // line 404
- 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, newCh, newStartIdx)
- oldStartVnode = oldCh[++oldStartIdx]
- newStartVnode = newCh[++newStartIdx]
- } else if (sameVnode(oldEndVnode, newEndVnode)) {
- patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
- oldEndVnode = oldCh[--oldEndIdx]
- newEndVnode = newCh[--newEndIdx]
- } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
- patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
- canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
- oldStartVnode = oldCh[++oldStartIdx]
- newEndVnode = newCh[--newEndIdx]
- } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
- patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
- canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
- oldEndVnode = oldCh[--oldEndIdx]
- newStartVnode = newCh[++newStartIdx]
- } else {
- 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, newCh, newStartIdx)
- 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(oldCh, oldStartIdx, oldEndIdx)
- }
- }
其对新旧两个 children 数组分别在首位各用了一个指针, 总共四个指针, 由于指针仅仅对数组进行了一次遍历, 因此时间复杂度是 O(n), 举个简单例子说明 diff 过程.
- old VNode: a(oldStartIdx) b c d e f(oldEndIdx)
- new VNode: b(newStartIdx) f g(newEndIdx)
- DOM Node: a b c d e f
首先指针相互比较, 即四种对比, 分别为 oldStartIdx 和 newStartIdx,oldStartIdx 和 newEndIdx,oldEndIdx 和 newStartIdx,oldEndIdx 和 newEndIdx, 如果没有相等的则继续. 此时分为两种情况, 有 key 和无 key, 无 key 则直接创建新的 DOM Node 插入到 a(oldStartIdx)之前, 此处认为 key 存在, 有 key 的话取 newStartIdx 的 key 值, 到 old VNode 去找, 记录此时的 oldKeyToIdx, 随即调整 VNode, 将 b 移动到 a 之前, 然后找到 old VNode 中 oldKeyToIdx 对应的节点值设置为 undefined,newStartIdx 指针向中间靠拢, 即 ++newStartIdx.
- old VNode: a(oldStartIdx) undefined c d e f(oldEndIdx)
- new VNode: b f(newStartIdx) g(newEndIdx)
- DOM Node: b a c d e f
循环继续, 此时对比 oldStartIdx 和 newStartIdx,oldStartIdx 和 newEndIdx,oldEndIdx 和 newStartIdx,oldEndIdx 和 newEndIdx, 发现 newStartIdx 与 oldEndIdx 相同, 将 DOM Node 中的 f 进行移动调整到 DOM Node 中的 a(oldStartIdx)之前, 此时 newStartIdx 与 oldEndIdx 指针向中间靠拢, 即 ++newStartIdx 与 --oldEndIdx.
- old VNode: a(oldStartIdx) undefined c d e(oldEndIdx) f
- new VNode: b f g(newStartIdx)(newEndIdx)
- DOM Node: b f a c d e
循环继续, 此时对比 oldStartIdx 和 newStartIdx,oldStartIdx 和 newEndIdx,oldEndIdx 和 newStartIdx,oldEndIdx 和 newEndIdx, 并没有相同的情况, 取 newStartIdx 的 key 值, 到 old VNode 去找, 没有发现相同的值, 则直接创建一个节点插入到 DOM Node 中的 a(oldStartIdx)之前, newStartIdx 指针向中间靠拢, 即 ++newStartIdx.
- old VNode: a(oldStartIdx) undefined c d e(oldEndIdx) f
- new VNode: b f g(newEndIdx) (newStartIdx)
- DOM Node: b f g a c d e
此时循环结束, 有两个选择:
如果
oldStartldx> oldEndldx
, 说明老节点遍历完成了, 新的节点比较多, 所以多出 来的这些新节点, 需要创建出来并添加到真实 DOM Node 后面.
如果
newStartldx>newEndldx
, 说明新节点遍历完成了, 老的节点比较多, 所以多 出来的这些老节点, 需要从真实 DOM Node 中删除这些节点.
此时我们符合场景二, 所以需要从真实 DOM Node 中删除 [oldStartldx,oldEndldx] 区间 中的 Node 节点, 根据上述内容, 即需要删除 a c d e 四个节点, 至此 diff 完成.
- old VNode: a(oldStartIdx) undefined c d e(oldEndIdx) f
- new VNode: b f g(newEndIdx) (newStartIdx)
- DOM Node: b f g
diff 完成之后便是将 new VNode 作为 old VNode 以便下次 diff 时使用, 此外关于组件的 diff, 组件级别的 diff 算法比较简单, 节点不相同就进行创建和替换, 节点相同的话就会对其子节点进行更新, 最后关于调用 createElm 来根据 VNode 创建真实的 DOM 元素, 如果是一个组件, 那么 createComponent 会返回 true, 因此不会进行接下来的操作, 如果不是组件, 会进行节点创建工作, 并会递归对孩子创建节点.
每日一题
https://github.com/WindrunnerMax/EveryDay
参考
- https://github.com/aooy/blog/issues/2
- https://www.zhihu.com/question/66851503
- https://juejin.im/post/6844903607913938951
- https://juejin.im/post/6844903592483094535
- https://reactjs.org/docs/reconciliation.html
- https://www.cnblogs.com/lilicat/p/13448827.html
- https://www.cnblogs.com/lilicat/p/13448915.html
- https://github.com/lihongxun945/myblog/issues/33
- https://www.cnblogs.com/xujiazheng/p/12101764.html
- https://blog.csdn.net/dongcehao/article/details/106987886
- https://blog.csdn.net/qq2276031/article/details/106407647
- https://github.com/Advanced-Frontend/Daily-Interview-Question/issues/151
- https://leetcode-cn.com/problems/edit-distance/solution/bian-ji-ju-chi-by-leetcode-solution/
来源: http://www.bubuko.com/infodetail-3655415.html