前言

前置的渲染过程可以参考我的这篇文章【Vue 渲染流程揭秘】

VNode更新准备

在触发响应式状态更新后，effect会向vue的任务队列中推送一个等待执行的任务。（如果看过我前言中提到的文章，应该不会对下面将要提到ReactiveEffect类感到陌生）

const setupRenderEffect = () => {
	const componentUpdateFn = () => {} // 生成VNode的关键函数
	const effect = (instance.effect = new ReactiveEffect(componentUpdateFn))
	const update = (instance.update = effect.run.bind(effect))
	const job: SchedulerJob = (instance.job = effect.runIfDirty.bind(effect))
	job.i = instance
  	job.id = instance.uid
  	effect.scheduler = () => queueJob(job)
  	//...其它逻辑
}

在前言中的文章我们提到，最后会触发当前effect的scheduler方法。那我们跟一下scheduler的调用栈以及job的执行栈

// scheduler调用栈关键过程
effect.scheduler -> queueJob(job) -> queue.push(job) // queue是主更新队列，此时将job任务推入队列中等待任务执行

// job调用栈关键过程
job() -> effect.runIfDirty() -> effect.run() -> effect.fn() // 这个fn即是componentUpdateFn，相关内容可以参考前言中的文章

任务调度，触发job

function flushJobs() {
	// ...其它逻辑
	try {
		for (flushIndex = 0; flushIndex < queue.length; flushIndex++) {
			const job = queue[flushIndex]
			callWithErrorHandling(job, job.i, job.i ? ErrorCodes.COMPONENT_UPDATE : ErrorCodes.SCHEDULER) // 执行job任务
		}
	} finally {
		// ...其它逻辑
	}
	// ...其它逻辑
}
export function queueJob(job) {
	//...其它逻辑
	queue.push(job)
	queueFlush()
}

function queueFlush() {
  if (!currentFlushPromise) {
    currentFlushPromise = resolvedPromise.then(flushJobs)
  }
}

这里vue简单借助了事件循环的方式，将等待执行的job收束到微任务中进行执行。

扩展 nextTick

nextTick如何实现将回调函数延后到本地dom更新之后才执行的呢？

export function queueJob(job) {
	// ...其它逻辑
	queueFlush()
}
function queueFlush() {
	if(!currentFlushPromise) {
		currentFlushPromise = resolvedPromise.then(flushJobs)
	}
}
export function nextTick(fn) {
	const p = currentFlushPromise || resolvedPromise
	return fn ? p.then(this ? fn.bind(this) : fn) : p
}

触发响应式变化之后currentFlushPromise会被赋予resolvedPromise.then(flushJobs)，而nextTick最终会追加到其后面变成resolvedPromise.then(flushJobs).then(this ? fn.bind(this) : fn)。从而将nextTick任务的执行时机滞后到flushJobs这个更新渲染dom之后。

生成新的VNode，触发diff算法

调用render函数

我实际的testComponent组件的template的部分

<template>
  <div>doubleCount is : {{ doubleCount }}</div>
  <button @click="updateCount">点击增加功能</button>
</template>

接下来就是render函数中 _createElementVNode执行生成VNode

import { createElementVNode as __createElementVNode } from "/public/vue.esm-browser.js";
function _createElementVNode(...args) { return _interopVNode(__createElementVNode(...args)) }

patch开启新旧VNodeTree的比较

patch函数的前两个入参，n1旧VNodeTree, n2新VNodeTree

满足条件进入diff算法

vue3在对比新旧VNode进行替换的过程中，并不是将整个树都会进入到diff算法的范围内。

1. patchFlag & PatchFlags.STABLE_FRAGMENT是0的情况
   PatchFlags.STABLE_FRAGMENT = 1 << 6 (64)
   当使用v-for绑定并且具有明确的key，并且循环源是变量而非常量的时候，编译的时候会打上128的标签（PatchFlags.KEYED_FRAGMENT）

vue编译时对于v-for的处理（以下均为编译时才会触及的代码，可以选择不看）

再来看下createVNodeCall的返回值

v-for的type所走的生成render函数，其内部会通过push方法拼装出render字符串，最后在转成运行时可以执行的render函数

因为目前仅处于运行时，编译时的调试可能要放在vite中。所以本次仅简单列出对应的相关信息，否则牵扯的会与diff相关的脱离太多。

diff算法

以下关键代码所使用变量的值

let i = 0;
const l2 = c2.length
let e1 = c1.length - 1
let e2 = l2 - 1
// i 双端比较中的左指针
// c1 旧VNode数组 e1 双端比较中旧数组右指针
// c2 新VNode数组 e2 双端比较中新数组右指针
// l2 新VNode数组长度

1. 双端对比中的左端对比
   i变量不能大于新旧数组右端指针e1和e2

while (i <= e1 && i <= e2) {
	const n1 = c1[i]
	const n2 = (c2[i] = optimized ? cloneIfMounted(c2[i]) : normalizeVNode(c2[i]))
	if (isSameVNodeType(n1, n2)) {
		// ...patch的逻辑
	} else {
		break; // 当左端比较出现差异时，停止当前比较，然后开启双端比较中的右端比较
	}
	i++;
}

2. 双端对比中的右端对比
   e1与e2变量不能小于左端指针i

while (i <= e1 && i <= e2) {
	const n1 = c1[e1]
	const n2 = (c2[e2] = optimized ? cloneIfMounted(c2[i]) : normalizeVNode(c2[i]))
	if (isSameVNodeType(n1, n2)) {
		// ...patch的逻辑
	} else {
		break; // 当新旧数组右端比较出现差异时，停止比较，
	}
}

双端对比完成之后会出现以下三种情况

// 第一种
if (i > e1) {}
// 第二种
else if (i > e2) {}
// 第三种 i <= e1 && i <= e2
else {}

以上三种分别对应双端对比之后的三种情况
第一种 i > e1 代表双端对比之后，旧数组c1已被完全对比，即e2所剩部分为完全新增的部分

let c1 = ["a", "b", "c", "d"]
let c2 = ["a", "b", "s1", "s2", "c", "d"]
let i = 0;
let e1 = 3
let e2 = 5
// 双端对比之后 i -> 2, e1 -> 1，e2 -> 3 此时s1, s2均为新增

// 或者简单一点的对比
let c1 = ["a", "b", "c"]
let c2 = ["a", "b", "c", "d"]
let i = 0;
let e1 = 2;
let e2 = 3;
// 双端对比之后 i = 3, e1 -> 2, e2 -> 3 此时d为新增

第二种 i > e2 代表双端对比之后，新数组c2已被完全对比，即e1所剩部分为完全删除的部分

let c1 = ["a", "b", "s1", "s2", "c", "d"]
let c2 = ["a", "b", "c", "d"]
let i = 0;
let e1 = 5
let e2 = 3
// 双端对比之后 i -> 2, e1 -> 3, e2 -> 1, 此时s1，s2均为删除

// 或者简单一点的对比
let c1 = ["嘿嘿", "a", "b", "c"]
let c2 = ["a", "b", "c"]
let i = 0;
let e1 = 3;
let e2 = 2;
// 双端对比之后 i -> 0, e1 -> 0, e2 -> -1, 此时嘿嘿为删除

第三种 i <= e1 && i <= e2代表双端对比后所剩最长变化子串（下述代码注释请详细观看）
先说结论：会生成一个由c1索引位+1 所组成的数组值，代表从c1到c2的过程中复用c1的位置。存储值的位置是newIndexToOldIndexMap。

c1 -> [ S1, S2, S3 ] // 旧VNode所剩部分
c2 -> [ T1, S2, S3, T2 ] // 新VNode所剩部分
// 此时假设在双端对比之后i的值是2; e1 e2是c1 c2最后一个索引所对应的值（注意此处是需要算上i的值的）

// 1. 生成c2 VNode key与索引的关系(以下均按照VNode的名称作为key的值)
const keyToNewIndexMap = new Map()
for (let j = i; j <= e2; j++) {
	keyToNewIndexMap(key, j) // 伪代码 { T1: 2, S2 : 3, S3: 4, T2: 5 }
}
// 2. 生成与c2长度相同的数组，数组的元素将会保存与c2相同的c1 VNode所对应的索引位置
const newIndexToOldIndexMap = new Array({ length: c2.length }, () => 0) // 伪代码[0, 0, 0, 0]
// 3. 遍历c1，如果c1对应的VNode在c2中存在则将c1的索引值存储到newIndexToOldIndexMap中，没有的话就走移除的逻辑
let maxNewIndexSoFar = 0 // 用来记录匹配c1 与 c2是否相同过程中，c2索引位的值（如果newIndex < maxNewIndexSoFar则说明从c1到c2的过程中存在移动的过程）
let moved = false // 为true代表需要进行移动
let patched = 0; // 
for (let k = i; k <= e1; k++) {
	
	const prevChild = c1[k]
	let newIndex
	if (prevChild.key !== null) {
	  // 如果旧VNode存在key
		newIndex = keyToNewIndexMap.get(prevChild.key) // 从c2的key map中查找index值
	} else {
		// 如果旧VNode不存在key
		for (let j = i; j <= e2; j++) {
			if (
				newIndexToOldIndexMap[j - 1] === 0 && // c2此处的VNode没有标记过c2相同VNode的索引位
				isSameVNodeType(prevChild , c2[j]) // 新旧VNode的type和key是一样的（但因为if的判断是其没有key，那这里相等的前提应当也是要两者的key都是undefined）
			) {
				newIndex = j
				break;
			}
		}
	}
	if (newIndex === undefined) {
		unmount() // 删除VNode的逻辑
	} else {
		newIndexToOldIndexMap[newIndex - i] = k + 1; // 两个解释点：首先是为何+1，因为0是newIndexToOldIndexMap的初始值，所以通过加1来将索引为是0的情况区分开。其次是为何newIndex - i，因为newIndex是完整c1的索引值，映射到newIndexToOldIndexMap（双端对比后所剩部分的长度），存在一个左指针数值的差。
		
		// 通过下面的if-else判断来确定是否存在从c1到c2的过程中存在c1前后位置交换的情况
		if (newIndex >= maxNewIndexSoFar) {
			maxNewIndexSoFar = newIndex
		} else {
			moved = true // 存在则设置为true，开启后续的LIS算法。
		}
		patch() // 更新VNode的逻辑
		patched++; // 此时patched自增一
	}
}
// 4. moved为true则会进入LIS，最长递增子序列获取的算法
const increasingNewIndexSequence = moved
        ? getSequence(newIndexToOldIndexMap) // getSequence即vue中计算最长递增子序列的算法，会在LIS算法部分中分析
        : EMPTY_ARR
// 5. increasingNewIndexSequence保存newIndexToOldIndexMap这个序列中的最长递增序列的索引，并最终确定移动以及新增的部分
let j = newIndexToOldIndexMap.length - 1;
for(let i = c2.length - 1; i >= 0 ; i--) {
	if (newIndexToOldIndexMap[i] === 0) {
		// c1中不存在可复用的则直接新增
		patch()
	} else if (move) {
		if (j < 0 || i !== newIndexToOldIndexMap[j]) {
			// i !== newIndexToOldIndexMap[j] 即当前位置不是最长自增子序列的目标位置，则当前位置需要移动
			// i超出的j的范围亦是需要移动的部分，例 [0,1,3,4,2,6] i是0-5 [0, 1, 2, 3, 5] j是0-4
			move()
		} else {
			j-- 
		}
	}
}

最终通过patch，move，unmount实现最终真是dom的创建

LIS算法扩展

什么是LIS算法

LIS算法的目的是从目标序列中，找到一段最长的自增子序列（子序列相较于子串的区别是可以不连续）；当自增子序列越长，那相应的移动，删除，新增的步骤则会越少。vue通过LIS算法来优化c1到c2变化中所需移动的最小步骤。

思路拆解（动态规划）

1. dp[i] = dp[i-x] + 1 转移方程 i >= x&&x > 1, i-x 代表到i位置所能构成递增子序列的前一位索引
2. 目标一：生成一个数组p，p[i] = i - x。目标二：生成一个数组result，记录i，代表最长递增子序列索引
3. 处理 小1 -> 大 -> 小2 这样子交替变化的目标序列，如何确定按照大作为递增子序列的第二位更长还是使用小2更长呢？ 结论：result代表最长递增子序列，如果使用小2能够带来更长的递增子序列，那result会从 [小1， 大， …大之后]变成[小1， 小2， …小2之后]，也就是大与小2中间的部分如果能够被小2之后的完全替换则使用小2更长是真命题，否则使用小2更长则是伪命题。也就是result的最后一位会决定真正的最长递增子序列是什么（借助p中i与i - x的映射关系来确定最终的子序列索引）
4. 使用二分法或者普通的遍历来寻找小2替换的大的位置

源码实现

与源代码在变量定义上有些许出入，但仍保证结果的准确性

function getSequence(arr) {
	const p = arr.slice() // 目标一，p数组登场
	const result = [0] // 目标二，result数组登场
	for (let i = 0; i < arr.length; i++) {
		let j = result[result.length - 1]
		if (arr[i] > arr[j]) {
			p[i] = j; // 记录 i 所的上一位递增子序列的索引
			result.push(i); // 如果目标值大于递增子序列中的最后一个值，则继续推入result
			continue;
		}
		// 如果不满足递增子序列，则需要使用二分法查找对应替换的位置（最终u和v会是同一个值, 即第一个大于arr[i]的值的索引所处的result的位置）
		let u = 0;
		let v = result.length - 1;
		while (u > v) {
			const c = (u + v) >> 1 // 数学思想右移一位代表除2并向下取整，即二分法寻找中心位置
			if (arr[result[c]] < arr[i]) {
				// 如果中心位置小于目标值
				u = c + 1 // 下一次二分的左边界是当前中心位置 + 1
			} else {
				v = c // 反之则下一次二分的右边界是当前中心位置
			}
		}
		if (arr[result[u]] > arr[i]) {
			if (u > 0) {
				p[i] = result[u - 1] // 记录 i 所的上一位递增子序列的索引
			}
			result[u] = i
		}
	}
	// 恢复最终最长的result
	let k = result.length - 1;
	let v = result[k] // v代表当前result索引位应当赋予的值，result的最后一位代表这最长的结束，所以无需借助p来进行变化
	while (k >= 0) {
		result[k] = v;
		v = p[v] // 从p获取i对应的 i - x的值，并恢复 result[k - 1] = i - x
		k--;
	}
	return result
}

getSequence([0,1,3,4,2,6]) // 输出结果为 [0, 1, 2, 3, 5] 可以控制台复制打印查看此结果