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

Posted on by hackdl

专栏分享：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  {
  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 - 1 ；e2 = c2.length - 1

sync from start 前序对比

从头部开始正序比对

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

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

 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

sync from end 后序对比

从尾部开始倒序比对

如果是相同的虚拟节服务器托管网点，则调用patch对比元素打补丁（先复用节点、再比较属性、再递归比较子节点），e1-1，e2-1

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

// sync from end 从尾部开始处理 O(n)
//   a (b c)
// d e (b c)
while (i

common sequence+mount 同序列加挂载

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

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


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

common sequence+unmount 同序列加卸载

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

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


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

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 ，若当前节点是最后一个新的子节点，则 anchor 为 null，即插入到容器最后面；否则 anchor 为当前节点的下一个节点，即插入到 anchor 节点之前

// 优化完毕************************************
// 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 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

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

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

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

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

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net

服务器托管，北京服务器托管，服务器租用，机房机柜带宽租用

服务器托管

咨询：董先生

电话13051898268 QQ/微信93663045！

上一篇:
下一篇: