【源码系列#06】Vue3 Diff算法

  • 【源码系列#06】Vue3 Diff算法已关闭评论
  • 29 次浏览
  • A+
所属分类:Web前端
摘要

专栏分享:vue2源码专栏,vue3源码专栏,vue router源码专栏,玩具项目专栏,硬核💪推荐🙌
欢迎各位ITer关注点赞收藏🌸🌸🌸


专栏分享:vue2源码专栏vue3源码专栏vue router源码专栏玩具项目专栏,硬核💪推荐🙌
欢迎各位ITer关注点赞收藏🌸🌸🌸

Vue2 Diff算法可以参考此篇文章【Vue2.x源码系列08】Diff算法原理

前后元素不一致

两个不同虚拟节点不需要进行比较,直接移除老节点,将新的虚拟节点渲染成真实DOM进行挂载即可

// 判断两个虚拟节点是否是相同节点,标签名相同 && key是一样的 export function isSameVnode(n1, n2) {   return n1.type === n2.type && n1.key === n2.key }  //  核心的patch方法,包括初始化DOM 和 diff算法 const patch = (n1, n2, container) => {   if (n1 == n2) return    // 判断两个元素是否相同,不相同卸载在添加   if (n1 && !isSameVnode(n1, n2)) {     unmount(n1) // 删除老的     n1 = null   }    const { type, shapeFlag } = n2   switch (type) {     case Text:       processText(n1, n2, container)       break     default:       if (shapeFlag & ShapeFlags.ELEMENT) {         processElement(n1, n2, container)       }   } } 

前后元素一致

两个相同的虚拟节点,先复用节点,再比较两个节点的属性和孩子节点

判断是否是相同的虚拟节点:type类型相同 && key相同

  1. 处理文本类型的虚拟节点
// 处理文本,初始化文本和patch文本 const processText = (n1, n2, container) => {   if (n1 === null) {     // 初始化文本     const el = (n2.el = hostCreateText(n2.children))     hostInsert(el, container)   } else {     // patch文本,文本的内容变化了,我可以复用老的节点     const el = (n2.el = n1.el)     if (n1.children !== n2.children) {       hostSetText(el, n2.children) // 文本的更新     }   } } 
  1. 处理元素类型的虚拟节点
// 处理元素,初始化元素和patch元素 const processElement = (n1, n2, container) => {   if (n1 === null) {     // 初始化元素     mountElement(n2, container)   } else {     // patch元素     patchElement(n1, n2)   } }  // 对比元素打补丁,先复用节点、再比较属性、再比较儿子 const patchElement = (n1, n2) => {   let el = (n2.el = n1.el)   let oldProps = n1.props || {} // 对象   let newProps = n2.props || {} // 对象    patchProps(oldProps, newProps, el)   patchChildren(n1, n2, el) }  // 对比属性打补丁 const patchProps = (oldProps, newProps, el) => {   for (let key in newProps) {     // 新的里面有,直接用新的盖掉即可     hostPatchProp(el, key, oldProps[key], newProps[key])   }   for (let key in oldProps) {     // 如果老的里面有新的没有,则是删除     if (newProps[key] == null) {       hostPatchProp(el, key, oldProps[key], undefined)     }   } }  const patchChildren = (n1, n2, el) => {   // 核心Diff算法 } 

子元素比较情况

新儿子 旧儿子 操作方式
文本 数组 (删除老儿子,更新文本内容)
文本 文本 (更新文本内容)
文本 (更新文本内容)
数组 数组 (diff算法)
数组 文本 (清空文本,挂载元素)
数组 (挂载元素)
数组 (删除所有子节点)
文本 (清空文本)
(不做任何处理)
// 删除所有的子节点 const unmountChildren = children => {   for (let i = 0; i < children.length; i++) {     unmount(children[i])   } }  // 对比子节点打补丁   el: 虚拟节点对应的真实DOM元素 const patchChildren = (n1, n2, el) => {   const c1 = n1.children   const c2 = n2.children   const prevShapeFlag = n1.shapeFlag // 之前的   const shapeFlag = n2.shapeFlag // 之后的    if (shapeFlag & ShapeFlags.TEXT_CHILDREN) {     if (prevShapeFlag & ShapeFlags.ARRAY_CHILDREN) {       // 文本	数组	(删除所有子节点,更新文本内容)       unmountChildren(c1)     }     if (c1 !== c2) {       // 文本	文本	| 文本 空 (更新文本内容)       hostSetElementText(el, c2)     }   } else if (shapeFlag & ShapeFlags.ARRAY_CHILDREN) {     if (prevShapeFlag & ShapeFlags.ARRAY_CHILDREN) {       // 数组 数组 (diff算法;全量比对)       patchKeyedChildren(c1, c2, el)     } else {       if (prevShapeFlag & ShapeFlags.TEXT_CHILDREN) {         // 数组 文本  清空文本,挂载元素)         hostSetElementText(el, '')       }       // 数组 文本 | 数组 空 (清空文本,挂载元素)       mountChildren(c2, el)     }   } else {     // 空 数组     if (prevShapeFlag & ShapeFlags.ARRAY_CHILDREN) {       unmountChildren(c1)     } else if (prevShapeFlag & ShapeFlags.TEXT_CHILDREN) {       // 空 文本       hostSetElementText(el, '')     }   } } 

核心Diff算法

前序比对、后序比对、同序列加挂载、同序列加卸载的目的都是:尽可能减少后面乱序比对的元素

在正式介绍diff算法之前,我们先了解几个问题

  1. 如何判断是否是相同的虚拟节点?

    答:虚拟节点的 type类型相同 && key相同 即可

  2. c1、c2 指的是什么?

    答:patch对比元素打补丁,先复用节点、再比较属性、最后比较儿子节点。c1指的是旧的儿子节点;c2指的是新的儿子节点

  3. e1、e2 指的是什么?

    答:尾指针,初始值分别指向新旧孩子的最后一个节点,e1 = c1.length - 1e2 = c2.length - 1

sync from start 前序对比

从头部开始正序比对

如果是相同的虚拟节点,则调用patch对比元素打补丁(先复用节点、再比较属性、再递归比较子节点),i+1

终止条件:新旧虚拟节点不一致,或, 双方有一方 i 大于 尾指针,停止循环

【源码系列#06】Vue3 Diff算法

 h('div',[      h('li', { key: 'a' }, 'a'),      h('li', { key: 'b' }, 'b'),      h('li', { key: 'c' }, 'c')  ]) :   h('div',[      h('li', { key: 'a' }, 'a'),      h('li', { key: 'b' }, 'b'),      h('li', { key: 'd' }, 'd'),      h('li', { key: 'e' }, 'e'),      h('li', { key: 'f' }, 'f'),  ]) 
// diff算法;全量比对,比较两个儿子数组的差异 const patchKeyedChildren = (c1, c2, container) => {   let i = 0   // 结尾位置   let e1 = c1.length - 1   let e2 = c2.length - 1    // 特殊处理,尽可能减少比对元素   // sync from start 从头部开始处理 O(n)   // (a b) c   // (a b) d e   while (i <= e1 && i <= e2) {     // 有任何一方停止循环则直接跳出     const n1 = c1[i]     const n2 = c2[i]     // vnode type相同 && key相同     if (isSameVnode(n1, n2)) {       patch(n1, n2, container) // 这样做就是比较两个节点的属性和子节点     } else {       break     }     i++   } } 

sync from end 后序对比

从尾部开始倒序比对

如果是相同的虚拟节点,则调用patch对比元素打补丁(先复用节点、再比较属性、再递归比较子节点),e1-1,e2-1

终止条件:新旧虚拟节点不一致,或, 双方有一方 i 大于 尾指针,停止循环

【源码系列#06】Vue3 Diff算法

// sync from end 从尾部开始处理 O(n) //   a (b c) // d e (b c) while (i <= e1 && i <= e2) {   const n1 = c1[e1]   const n2 = c2[e2]   if (isSameVnode(n1, n2)) {     patch(n1, n2, container)   } else {     break   }   e1--   e2-- } 

common sequence+mount 同序列加挂载

分为 头部挂载 和 尾部挂载 两种场景

i 比 e1 大说明有要新增的,i 和 e2 之间的是新增的节点

【源码系列#06】Vue3 Diff算法
【源码系列#06】Vue3 Diff算法

// common sequence + mount 同序列加挂载 // i要比e1大说明有新增的;i和e2之间的是新增的部分 // (a b c) // (a b c) d e //     (a b c) // e d (a b c) if (i > e1) {   if (i <= e2) {     while (i <= e2) {       const nextPos = e2 + 1       // 根据下一个人的索引来看参照物       const anchor = nextPos < c2.length ? c2[nextPos].el : null       patch(null, c2[i], container, anchor) // 创建新节点 扔到容器中       i++     }   } } 

common sequence+unmount 同序列加卸载

分为 头部卸载 和 尾部卸载 两种场景

i 比 e2 大说明有要卸载的,i 到 e1 之间的就是要卸载的节点

【源码系列#06】Vue3 Diff算法
【源码系列#06】Vue3 Diff算法

// common sequence + unmount 同序列加卸载 // i比e2大说明有要卸载的;i到e1之间的就是要卸载的 // (a b c) d e // (a b c) // e d (a b c) //     (a b c) else if (i > e2) {   if (i <= e1) {     while (i <= e1) {       unmount(c1[i])       i++     }   } } 

unknown sequence 乱序对比

keyToNewIndexMap:新节点中 key -> newIndex 的 Map 映射表,子元素中如果存在相同的 key 或者 有多个子元素没有 key,值会被后面的索引覆盖

newIndexToOldIndexMap:记录新节点是否被比对过的数组映射表,初始值均为0。作用:已对比过的新节点只需移动位置;未对比过的新节点则需新创建

  1. 遍历老的乱序节点,看一下其是否存在于新的乱序节点里面,判断条件:keyToNewIndexMap.get(oldChild.key)是否有值,如果有则 patch 比较差异;如果没有则要删除老节点

  2. 在 patch 比较差异之前,我们要给 newIndexToOldIndexMap[newIndex - s2] 赋值,只是乱序比对的话,赋值为1打个标识即可。这里我们赋值为相同key的老节点索引+1,即newIndexToOldIndexMap[newIndex - s2] = i + 1(这里可能有点绕,结合代码理解)。用于后续的最长递增子序列

  3. 到这只是进行了新老属性、儿子的比对 和 多余老节点的卸载操作,下面我们再执行节点位置移动和多余新节点的挂载操作

  4. 倒序遍历新的乱序节点,看一下新节点是否被比对过,判断条件: newIndexToOldIndexMap[i] 值是否存在非0值,如果不为0则只需移动节点位置;如果为0则要创建挂载新节点

  5. 那么移动节点的具体位置和挂载新节点的位置如何去计算?判断条件:当前节点是否是最后一个新的子节点,let anchor = index + 1 < c2.length ? c2[index + 1].el : null,若当前节点是最后一个新的子节点,则 anchor 为 null,即插入到容器最后面;否则 anchor 为当前节点的下一个节点,即插入到 anchor 节点之前

【源码系列#06】Vue3 Diff算法

// 优化完毕************************************ // unknown sequence 乱序比对 // (a b) 【c d e w】 (f g) // (a b) 【e d c v】 (f g) let s1 = i let s2 = i const keyToNewIndexMap = new Map() // 新节点中 key -> newIndex 的 Map 映射表,子元素中如果存在相同的key 或者 有多个子元素没有key,值会被后面的索引覆盖 for (let i = s2; i <= e2; i++) {   keyToNewIndexMap.set(c2[i].key, i) }  const toBePatched = e2 - s2 + 1 // 新的节点中乱序比对总个数 // 一个记录是否比对过的数组映射表,作用:已对比过的节点需移动位置;未对比过的节点需新创建 const newIndexToOldIndexMap = new Array(toBePatched).fill(0)  // 遍历老的乱序节点 看一下其是否存在于新的乱序节点里面,如果有则patch比较差异;如果没有则要删除老节点 for (let i = s1; i <= e1; i++) {   const oldChild = c1[i] // 老的节点   let newIndex = keyToNewIndexMap.get(oldChild.key) // 用老的节点去新的里面找   if (newIndex == undefined) {     unmount(oldChild) // 多余老节点删掉   } else {     // 新的位置对应的老的位置,如果数组里放的值 >0 说明已经pactch过了。+1的目的:防止i为0     newIndexToOldIndexMap[newIndex - s2] = i + 1 // 用来标记当前乱序新节点索引 对应的 全部老节点的加1后的索引,最长递增子序列会用到     patch(oldChild, c2[newIndex], container)   } } // 到这只是新老属性和儿子的比对 和 多余老节点卸载操作,没有移动位置  // 乱序节点需要移动位置,倒序遍历乱序节点 for (let i = toBePatched - 1; i >= 0; i--) {   let index = i + s2 // i是乱序节点中的index,需要加上s2代表全部新节点中的index   let current = c2[index] // 找到当前节点   let anchor = index + 1 < c2.length ? c2[index + 1].el : null   if (newIndexToOldIndexMap[i] === 0) {     // 创建新元素     patch(null, current, container, anchor)   } else {     // 不是0,说明已经执行过patch操作了     hostInsert(current.el, container, anchor)   }   // 目前无论如何都做了一遍倒叙插入,性能浪费,可以根据刚才的数组newIndexToOldIndexMap来减少插入次数   // 用最长递增子序列来实现,vue3新增算法,vue2在移动元素的时候则会有性能浪费 } 

目前无论如何都做了一遍倒叙插入,性能浪费。

思考一下!我们是不是可以只移动一部分节点。既减少了移动次数,又能保证节点顺序是正确的呢?

例如旧节点 1, 3, 4, 2,新节点 1, 2, 3, 4。那我们完全可以只将 2 移动到 3 前面,只需移动一次!就能保证顺序是正确的!!!

可以用 vue3 新增算法 - 最长递增子序列 来实现,下一篇文章吃透透!!!