前提： 最近又看了看vue3的diff算法的一些源码分析。总结一波关键点进行回溯记忆
image.png
一、没有key的节点，不需要diff核心算法
patchUnkeyedChildren方法简要代码
const patchChildren: PatchChildrenFn = (n1, n2,...) => {
const { patchFlag, shapeFlag } = n2
if (patchFlag & PatchFlags.KEYED_FRAGMENT) {
patchKeyedChildren(){}
} else if (patchFlag & PatchFlags.UNKEYED_FRAGMENT) {
1. 遍历新旧中最短的节点，依次patch，如果不是相同节点，直接卸载
const commonLength = Math.min(c1.length, c2.length)
for (let i = 0; i < commonLength; i++) {
patch(c1[i],c2[i])
}
2. 变长了就新增，变短了就删除节点
将commonLength作为 start开始循环 卸载或者，新增节点
c1.length > c2.length? unmountChildren(c1,...,commonLength) : mountChildren(c2,...,commonLength)
}
}
二、对于有key的节点，会用到diff算法：patchKeyedChildren
以下内容都是 patchKeyedChildren方法简要代码
1. 前后对比记住三个变量 i ， e1 ， e2
let i = 0;
let e1 = c1.length - 1
let e2 = c2.length - 1
从前往后遍历，i增加. 遇到不一样的节点暂停。i 的值就很重要了。
while (i <= e1 && i <= e2) {
const n1 = c1[i]
const n2 = c2[i]
if (isSameVNodeType(n1, n2)) {
patch（...）
} else {
break
}
i++
}
再从后往前遍历，原元素递减，遇到相同的也暂停。
while (i <= e1 && i <= e2) {
const n1 = c1[e1]
const n2 = c2[e2]
if (isSameVNodeType(n1, n2)) {
patch（...）
} else {
break
}
e1--
e2--
}
上面前后循环对比得到结论： i = 2， e1 = 4 ， e2 = 4
从结论来思考如果是单纯的增加元素，或者减少元素呢
单纯在末尾新增一个元素c
e1 ：a b
e2 ：a b c
得到： i = 2, e1 = 1, e2 = 2
单纯在头部新增元素c, d, k
e1 ：a b
e2 ：c d k a b
得到： i = 0, e1 = -1, e2 = 2
//
单纯在末尾减少一个元素c
e1 ：a b c
e2 ：a b
得到： i = 2, e1 = 2, e2 = 1
单纯在头部减少一个元素c
e1 ：a b c
e2 ：b c
得到： i = 0, e1 = 0, e2 = -1
中间新增或减少
e1 ：a b c
e2 ：a c
得到： i = 1, e1 = 1, e2 = 0
从上面可以看出规律: 单纯的新增元素时： i > e1, 单纯的减少元素时： i > e2. 如果 i 比e1 e2 小，那就不是单纯新增或减少了.
代码为证：
if (i > e1) {
if (i <= e2) {
while (i <= e2) {
创建新的节点
patch(null,...)
i++
}
} else if (i > e2) {
单纯的减少元素 直接去掉元素
while (i <= e1) {
unmount(c1[i], parentComponent, parentSuspense, true)
i++
}
} else {
//
}
单纯新增减少元素不会涉及到diff算法的核心算法。其他情况else才需要用到
1. 核心算法记住几个变量
以下代码都是else里面的
1. 第一步遍历到的index，存起
const s1 = i
const s2 = i
2. 前后对比循环后，,通过map 记录 c2 没有比较过的节点的位置角标
const keyToNewIndexMap: Map<string | number, number> = new Map()
/* */
for (i = s2; i <= e2; i++) {
const nextChild = c2[i]
if (nextChild.key != null) {
keyToNewIndexMap.set(nextChild.key, i)
}
}
3. c2 中待处理的节点数目
const toBePatched = e2 - s2 + 1
4. 证明是否移动
let moved = false
5.记录节点在 c2 中的最大索引，假如节点在 c2 中的索引位置小于这个最大索引，代表有元素需要移动
let maxNewIndexSoFar = 0
6.针对未比较的C2 节点建立一个数组，每个子元素都是0 [ 0, 0, 0, 0, 0, 0]
初始情况，0 代表新增
const newIndexToOldIndexMap = new Array(toBePatched)
for (i = 0; i < toBePatched; i++) {
newIndexToOldIndexMap[i] = 0
}
通过开篇的图，结合以上代码，我们可以得出这些值
c2 中待处理的节点有：d，e，c，h。对应索引是2,3,4,5
keyToNewIndexMap: [ 2 ， 3 ，4 ，5 ]
toBePatched = 4
newIndexToOldIndexMap： [0,0,0,0]
2. 记住上面的变量后，下面就是最重要的环节了
已处理的节点
let patched = 0
let j
for (i = s1; i <= e1; i++) {
// 如果已处理的数量大于待处理节点数，直接删剩余的
// if (patched >= toBePatched) {
// unmount(prevChild, parentComponent, parentSuspense, //true)
// continue
// }
const prevChild = c1[i]
let newIndex
1. 通过key匹配新旧节点，newIndex就是标识节点在c2中的位置
此时上面得到的keyToNewIndexMap开始发挥作用
if (prevChild.key != null) {
newIndex = keyToNewIndexMap.get(prevChild.key)
} else {
3. 如果,老节点的key不存在，遍历剩下的所有新节点。什么情况下老节点的key会不存在呢？？
for (j = s2; j <= e2; j++) {
// newIndexToOldIndexMap里面本身初始化的都是0
// 这里=== 0 代表 新节点没有被patch
if ( newIndexToOldIndexMap[j - s2] === 0 &&
isSameVNodeType(prevChild, c2[j] as VNode)
) {
3.1 找到与当前老节点对应的新节点，记录newIndex
newIndex = j
break
}
}
}
2.1 newIndex 无值，代表没有找到与老节点对应的新节点，删除节点
//拓展：void 0是undefined备选方案。字节更少
// void 后面随便跟上一个表达式，返回的都是 undefined
if (newIndex === void 0) {
unmount()
} else {
2.2 注意：i + 1,0 有特殊用途。把老节点的索引，记录在存放新节点的数组中
newIndexToOldIndexMap[newIndex - s2] = i + 1
2.3 看这里：记录maxNewIndexSoFar
如果某节点的索引大于之前节点的索引
代表有元素移动了moved = true
if (newIndex >= maxNewIndexSoFar) {
maxNewIndexSoFar = newIndex
} else {
moved = true
}
2.4 找到新的节点进行patch节点 ，
建立对应关系，执行patch将旧dom上的el（真实dom的引用）和其他给到新节点
patch(prevChild)
patched++
}
}
以上代码实现：
- 遍历c1待处理的节点, 在c2中有没有相同key的节点
没有就直接删掉unmount，有就记录改节点的索引
在找的过程中发现旧节点没有key？？那就嵌套遍历新节点c2找到对应关系
- 把旧节点在c1的位置（非索引，因为0要代表新增节点），存放在newIndexToOldIndexMap
我们可以得到以下的结论
3 4 5
c d e
d e c h
eg: 节点c 在原位置是3，索引是2。
这里存在它在新节点中的位置，（h为新增，原位置没有）
newIndexToOldIndexMap：[4, 5, 3, 0]
通过newIndexToOldIndexMap求得最小递增子序列
这是一个优化点
求解一个稳定递增的序列，即不需要移动的序列,其他未在稳定序列的节点，进行移动。实现最小化移动元素
newIndexToOldIndexMap [4, 5, 3, 0] --> 最长递增子序列是 [4, 5]
对应的索引是 [0, 1]
increasingNewIndexSequence = [0, 1]
3. 最后一步遍历c2，该移动的移动该新增的新增
const increasingNewIndexSequence = moved
? getSequence(newIndexToOldIndexMap)
: EMPTY_ARR
j = increasingNewIndexSequence.length - 1
注意：这里是从后往前遍历
i = 3 s2 = 2
nextIndex = 5
anchor 是找到h节点的后一个，也就是f节点插入。小于新节点长度实际上就是移动到最后
for (i = toBePatched - 1; i >= 0; i--) {
const nextIndex = s2 + i
const nextChild = c2[nextIndex]
const anchor =
nextIndex + 1 < c2.length ? (c2[nextIndex + 1] as VNode).el : parentAnchor
1. 这里 === 0 表示 c2 中的节点在 c1 中没有对应的节点，就新增它
if (newIndexToOldIndexMap[i] === 0) {
patch(null)
} else if (moved) {
2. 移动， 怎么最小化移动呢？最长递增子序列对应的元素不需要移动
// j < 0 --> 最长递增子序列为 []
if (j < 0 || i !== increasingNewIndexSequence[j]) {
move(nextChild, container, anchor)
} else {
j--
}
}
}
具体怎么移动呢？
上面代码有一个anchor，反向遍历，找到新节点的需要移动的节点的同级下个兄弟节点，执行dom的insetBefore操作：源码move方法
源码部分引入insert后，改为了hostInsert
insert: hostInsert,
const move: MoveFn = (vnode, container, anchor,) => {
hostInsert(vnode.anchor!, container, anchor)
}
所有dom的操作在这里runtime-dom
这里为什么要提这个move呢。主要是因为强调一下vnode上的el属性的重要性，在第二步的时候将真实dom的引用给到新节点el，才能通过节点执行dom的方法
image.png
总结
- 在前后对比时，会判断是否是相同节点isSameVNodeType.判断条件是相同的type和相同的key
export function isSameVNodeType(n1: VNode, n2: VNode): boolean {
return n1.type === n2.type && n1.key === n2.key
}
想一想，如果在v-for里面用index作为key（或者用index拼接其他值作为key），第一步的前后对比都失去了意义
新增一个c，都是以index为key
0 1
a b
0 1 2
c a b
从后往前遍历时是会发现新旧节点b的key不同。无法复用
所以老老实实用数据唯一id作为key吧
-
vue2 的时间复杂度是O(n) ， vue3 用到了最长递增子序列，时间复杂度是O(nlogn)，但是因为找出了最长递增子序列，减少了dom移动的开销，能够提高性能
tip: vue双端比较由嵌套循环变为一个循环，用空间换时间 -
Virtual DOM 带来了 分层设计，它对渲染过程的抽象，使得框架可以渲染到 web(浏览器) 以外的平台，以及能够实现 SSR 等。
至于 Virtual DOM 相比原生 DOM 操作的性能，这并非 Virtual DOM 的目标，确切地说，如果要比较二者的性能是要“控制变量”的，例如：页面的大小、数据变化量等 -
看完文章可以发现，上面代码对节点的操作都用到了patch函数,patch做了什么呢？？
patch概念：如果旧的 VNode 存在，则会使用新的 VNode 与旧的 VNode 进行对比，试图以最小的资源开销完成 DOM 的更新，这个过程就叫 patch
const patch: PatchFn = (n1, n2) => {
1. 旧元素存在，但是不是同类型直接卸载
if (n1 && !isSameVNodeType(n1, n2)) {
unmount(n1)
n1 = null
}
2. 根据新元素的类型，创建不同的节点，比如processElement
const { type, ref, shapeFlag } = n2
switch (type) {
case Text:
processText(n1, n2, container, anchor)
break
case Fragment:
processFragment(n1,n2, ...)
break
default:
if (shapeFlag & ShapeFlags.ELEMENT) {
processElement(n1，n2，...)
}
}
// 每次patch都要重新设置ref，这也就是为什么在编译阶段不对含有ref的节点进行提升的原因
// 因为ref是当作动态属性来看待的
if (ref != null && parentComponent) {
setRef(ref, n1 && n1.ref, parentSuspense, n2 || n1, !n2)
}
}
再看processElement,上一步节点不一致，就将n1置为null，所以在下面判断新增新节点
const processElement = ( n1: VNode | null,n2: VNode) => {
if (n1 == null) {
mountElement(n2,...)
} else {
patchElement(n1,n2,...)
}
}
patchElement方法会将VNode上的真实dom引用el属性给到新节点，el很重要，有了它才能执行dom操作
如果n2下面有children子节点，会再次进入 patchChildren,回到文章开头
const patchElement = (n1, n2,...) => {
const el = (n2.el = n1.el!)
...省略代码
patchChildren(n1,n2)
}
引用
最长递增子序列怎么算出来的？
Vue3.0 Diff核心算法详解
渲染器
这里说明一下，渲染器这篇文章非常细致地讲解了渲染器的设计过程，并不代表vue完全就是这样
-
文中提到的子节点是数组（不管是不是v-for生成）会自动生成key，一度让我迷惑：以为没有key会自动生成key，然后进行diff核心比较。看源码后发现没有key就是null，就会走patchUnkeyedChildren，如果不移动节点，key都是null也会通过isSameVNodeType判断进行复用
-
文中提到旧的节点为多个，只有新节点也为多个才进行核心diff，这一点在vue3代码我没看到，从代码上看：只关心有key无key。
2021-6-18新增：这一点是在react代码里有：单节点diff，源码部分reconcileChildFibers
单个节点就是isObject ，执行reconcileSingleElement判断是否可以复用
function reconcileChildFibers(
returnFiber: Fiber,
currentFirstChild: Fiber | null,
newChild: any){
const isObject = typeof newChild === 'object' && newChild !== null;
if (isObject) {
case REACT_ELEMENT_TYPE:
return placeSingleChild(
reconcileSingleElement(),
);
}
}
-
vue函数式组件和有状态的组件（类组件）更新有什么区别 ？
（1）类组件在实例上挂在更新方法，可以在外部执行更新。函数式组件只能由props数据驱动更新，判断是否更新的条件是：是否有preNode
（2）VNode 的 children 属性本应该用来存储子节点，但是对于组件类型的 VNode 来说，它的子节点都应该作为插槽存在，并且我们选择将插槽内容存储在单独的 slots 属性中，而非储在 children 属性中函数式组件的 使用 children 属性存储产出的 VNode ，slots属性存储插槽数据 有状态组件类型使用其 children 属性存储组件实例，用 slots 属性存储插槽数据
4.关于vue2的diff在文中 双端比较这一节非常清晰
可以对比查看vue2的源码updateChildren
网友评论