6.组件更新及diff算法

[Zijue]

组件更新

当依赖的属性变化时，会重新执行effect函数，我们再次调用render方法生成新的虚拟DOM，进行diff操作。

    const setupRenderEffect = (instance, container) => {
        effect(() => { // 每次状态变化后，都会重新执行effect
            if (!instance.isMounted) {
                ...
            } else {
                const prevTree = instance.subTree; // 获取数据没变时（初始化时组件的）subTree
                // 再次调用render，此时使用的是最新的数据渲染
                const nextTree = instance.render.call(instance.proxy, instance.proxy);
                instance.subTree = nextTree; // 将新的subTree赋给instance.subTree供后续更新使用
                // 执行diff算法
                patch(prevTree, nextTree, container);
            }
        })
    };

元素更新流程

前后元素不一致

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

        const { createApp, h, reactive, toRefs, ref } = VueRuntimeDOM;
        const App = {
            setup() { // setup中返回的是对象，那么这个对象会被用于渲染使用；如果返回的是函数，会作为render方法
                const state = reactive({ name: 'zijue', age: 18 });
                const flag = ref(true);
                setTimeout(() => {
                    flag.value = false;
                }, 1000);
                return { ...toRefs(state), flag }
            },
            render({ name, age, flag }) { // 前后元素不一致
                if (flag.value) {
                    return h('div', { style: { color: 'red' } }, `hi, ${name.value}`); // div
                } else {
                    return h('p', { style: { color: 'blue' } }, `hello, ${name.value}`); // p
                }
            }
        }
        createApp(App).mount('#app');

runtime-core/src/renderer.ts

    const isSameVnode = (n1, n2) => {
        return n1.type === n2.type && n1.key === n2.key;
    };
    const unmount = (vnode) => {
        hostRemove(vnode.el);
    };
    const patch = (n1, n2, container) => {
        // 判断n1、n2是否为同一个元素；通过type和key判断
        if (n1 && !isSameVnode(n1, n2)) { // 如果type和key不一样则直接删除老节点后渲染新节点
            unmount(n1);
            n1 = null; // 如果n1为空，则直接重新渲染n2
        }
        ...
    };

前后元素一致

前后虚拟节点一样，则复用DOM元素，并且更新属性和子节点。

        const { createApp, h, reactive, toRefs, ref } = VueRuntimeDOM;
        const App = {
            setup() {
                const state = reactive({ name: 'zijue', age: 18 });
                const flag = ref(true);
                setTimeout(() => {
                    flag.value = false;
                }, 1000);
                return { ...toRefs(state), flag }
            },
            render({ name, age, flag }) { // 前后元素一致
                if (flag.value) {
                    return h('div', { style: { color: 'red' } }, `hi, ${name.value}`);
                } else {
                    return h('div', { style: { color: 'blue' } }, `hello, ${name.value}`);
                }
            }
        }
        createApp(App).mount('#app');

runtime-core/src/renderer.ts

    const patchProps = (el, oldProps, newProps) => {
        // 两个循环，第一次循环遍历新属性更新到旧节点上，第二次循环遍历旧属性清空新属性中没有的项
        if (oldProps !== newProps) {
            for (let key in newProps) {
                const prev = oldProps[key];
                const next = newProps[key];
                if (prev !== next) {
                    hostPatchProp(el, key, prev, next);
                }
            };
            for (let key in oldProps) {
                if (!(key in newProps)) {
                    hostPatchProp(el, key, oldProps[key], null);
                }
            }
        }
    };
    const patchChildren = (n1, n2, container) => {
        ...
    };
    const patchElement = (n1, n2, container) => { // 走到这里说明前后两个元素能够复用
        let el = n2.el = n1.el; // 复用DOM

        const oldProps = n1.props || {};
        const newProps = n2.props || {};
        patchProps(el, oldProps, newProps); // 更新属性
        patchChildren(n1, n2, el); // 更新子节点；diff算法
    };

1. 新子节点是文本，直接新的替换旧的

这其中又分为两种情况：老节点是文本和老节点是数组；如果老节点是数组，需要先删除老的子节点，否则直接替换；

            // 1.1.新旧子节点都是文本
            render({ name, age, flag }) {
                if (flag.value) {
                    return h('div', { style: { color: 'red' } }, `hi, ${name.value}`);
                } else {
                    return h('div', { style: { color: 'blue' } }, `hello, ${name.value}`);
                }
            }

            // 2.2.新子节点是文本，旧子节点是数组
            render({ name, age, flag }) {
                if (flag.value) {
                    return h('div', { style: { color: 'red' } }, [
                        h('li', 'A'),
                        h('li', 'B'),
                    ]);
                } else {
                    return h('div', { style: { color: 'blue' } }, `hello, ${name.value}`);
                }
            }

    const patchChildren = (n1, n2, container) => {
        const c1 = n1.children;
        const c2 = n2.children;
        const prevShapeFlag = n1.shapeFlag;
        const shapeFlag = n2.shapeFlag;
        // 1.新子节点是文本，直接新的替换旧的
        if (shapeFlag & ShapeFlags.TEXT_CHILDREN) {
            if (prevShapeFlag & ShapeFlags.ARRAY_CHILDREN) { // 旧子节点是数组，先删除
                unmountChildren(c1);
            }
            if (c1 !== c2) {
                hostSetElementText(container, c2); // 直接替换
            }
        } else { // 新子节点是数组
            ...
        }
    };

2. 新子节点是数组，老子节点是文本

将老子节点的父节点清空，然后挂载所有新子节点；

    const patchChildren = (n1, n2, container) => {
        const c1 = n1.children;
        const c2 = n2.children;
        const prevShapeFlag = n1.shapeFlag;
        const shapeFlag = n2.shapeFlag;
        // 1.新子节点是文本，直接新的替换旧的
        if (shapeFlag & ShapeFlags.TEXT_CHILDREN) {
            if (prevShapeFlag & ShapeFlags.ARRAY_CHILDREN) { // 旧子节点是数组，先删除
                unmountChildren(c1);
            }
            if (c1 !== c2) {
                hostSetElementText(container, c2); // 直接替换
            }
        } else { // 新子节点是数组
            if (prevShapeFlag & ShapeFlags.ARRAY_CHILDREN) { // 3.新旧子节点都是数组
                ...
            } else { // 2.新子节点是数组，旧子节点是文本
                hostSetElementText(container, ''); // 先将父节点清空
                mountChildren(c2, container); // 然后挂载新的子节点
            }
        }
    };

3. 新老子节点都是数组

对于双方都是数组的情况，我们首先需要了解两个对比的方法：

• sync from start：从头开始一个个比，遇到不同的就停止；

• sync from end：从尾开始一个个比，遇到不同就停止；

    const patchKeyedChildren = (c1, c2, container) => {
        // diff 算法
        let i = 0; // 新旧子节点默认都是从头开始比对
        let e1 = c1.length - 1; // 旧子节点最后一个元素的下标
        let e2 = c2.length - 1; // 新子节点最后一个元素的下标
        // sync from start  从头开始一个个比，遇到不同的就停止
        while (i <= e1 && i <= e2) {
            const n1 = c1[i];
            const n2 = c2[i];
            if (isSameVnode(n1, n2)) { // 是同一个元素，继续对比这两个子节点的属性和子节点
                patch(n1, n2, container);
            } else { // 不同直接跳出循环，然后从尾部对比
                break;
            }
            i++;
        }
        // sync from end    从尾开始一个个比，一样是遇到不同的就停止
        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--;
        }
    };

根据上面两种方法比对新老子节点数组，有以下几种情况：

4. common sequence + mount：同序列挂载；新节点在不破坏老节点顺序的基础上增加新的节点；

可以发现，不管是从头部插入还是从尾部添加新的元素，i和e1的关系始终满足i > e1；

        if (i > e1) { // common sequence + mount    老的少，新的多
            if (i <= e2) { // 表示有新增的部分
                // 如何判断是添加到尾部还是插入到前面？
                // 判断 e2 + 1 与 c2.length 的大小；如果向后追加 e2 + 1 > c2.length 肯定成立
                const nextPos = e2 + 1;
                const anchor = nextPos < c2.length ? c2[nextPos].el : null; // 获取插入位置节点
                while (i <= e2) {
                    patch(null, c2[i++], container, anchor);
                }
            }
        }

5. common sequence + unmount：同序列卸载；新节点在不破坏老节点顺序的基础上减少节点；

同样可以发现，不管是在头部删除，还是尾部删除元素，i和e2的关系始终满足i > e2；

        if (i > e1) {
            ...
        } else if (i > e2) { // common sequence + unmount   老的多，新的少
            while (i <= e1) { // 表示有需要删除的部分
                unmount(c1[i++]);
            }
        } 

6. unknown sequence：乱序比对，diff中的核心算法，采用了最长递增子序列算法；

如上图虚线框中所示，这种乱序的该如何对比呢？

1). 以新节点建立元素key与下标索引的映射表；

            // A B [C D E Q] F G
            // A B [E C D H] F G
            // i = 2, e1 = 5, e2 = 5
            const s1 = i;
            const s2 = i;
            // 1.根据新节点生成一个索引的映射表
            const keyToNewIndexMap = new Map();
            for (let i = s2; i <= e2; i++) {
                const nextChild = c2[i];
                keyToNewIndexMap.set(nextChild.key, i);
            }

2). 遍历老节点数组，删除新节点中没有的老节点，即Q节点；并更新新节点中存在的老节点的属性及子节点，同时标识出来且同新节点的下标联系起来。如何理解这句话，我们看图：

            // 2.有了映射表之后，需要知道哪些可以被patch，哪些不能，哪些需要删除
            // 2.1.计算有几个新节点需要被patch
            const toBePatched = e2 - s2 + 1; // 4
            // 2.2.创建一个与需要patch等长的数组，用0填充
            const newIndexToOldIndexMap = new Array(toBePatched).fill(0); // [0, 0, 0, 0]
            // 2.3.遍历老节点，删除新节点中没有的，更新能复用元素并标记已patch
            for (let i = s1; i <= e1; i++) {
                const prevChild = c1[i];
                const newIndex = keyToNewIndexMap.get(prevChild.key); // 获取老节点在新节点中的下标索引
                if (newIndex == undefined) { // 老节点中有，新节点中没有的，直接删除
                    unmount(prevChild);
                } else {
                    // 将patch过的新节点对应下标与该节点在老节点中的位置一一映射（构建新老索引的关系）；
                    // 映射完成后，值为0表示该新节点未patch即老节点中没有
                    newIndexToOldIndexMap[newIndex - s2] = i + 1; // [5, 3, 4, 0]
                    patch(prevChild, c2[newIndex], container); // 更新相同元素的属性与子节点
                }
            }

3). 经过之前的两步，我们已经更新了新老节点中都有的元素，剩下的工作只需要移动和新增元素。那么如何移动效率才最高呢？Vue3中采用算法求解最长递增子序列处理这个问题。接下来我们看看其原理（不深究其算法），是如何做的？

假设，我们需要求解如上图所示数组的最长递增子序列，下面通过图示的方法展示算法的实现过程：

采用如上图所示的方式，从头到尾遍历完整个数组，最终我们会得到一个（贪婪模式下）递增序列的索引数组seq，与记录当一个节点索引位置的数组p。整个的变化过程如下图所示：

在得到了贪婪模式下的递增序列索引数组seq和记录上一个节点位置的p后，就可以通过倒序查找的方式，得到我们需要的最长递增子序列。原理就是在知晓最后一个人，且每个人都知道自己的前一个人是谁，那么整个队列的顺序就可以始终如一，不管在队列中随机添加人员，都不会影响整个队列的顺序。

4). 实现代码如下：

const getSeq = (arr) => {
    let len = arr.length;
    const result = [0]; // 用来存放最长递增子序列的索引
    const p = arr.slice(0); // 用来存索引，用于记录自己前一个节点的下标
    let resultLastIndex;

    for (let i = 0; i < len; i++) {
        const arrI = arr[i]; // 获取数组中的每一项，但是其中值为0是无意义，需要忽略
        if (arrI !== 0) {
            resultLastIndex = result[result.length - 1];
            // 索引数组中最后一个对应的数组的值与当前数组拿出来的值进行对比，
            // arr[resultLastIndex] < arrI，将当前的索引添加到索引数组result中
            if (arr[resultLastIndex] < arrI) {
                p[i] = resultLastIndex; // 在放入之前记住前一个的索引
                result.push(i);
                continue; // 如果是比最后一项大，后续逻辑就不用走了
            }
            // 二分查找，找到已存入索引数组中对应的值第一个大于当前数组下标对应的值的下标
            let start = 0;
            let end = result.length - 1;
            let middle;
            while (start < end) { // 最终start == end
                middle = ((start + end) / 2) | 0; // 向下取整
                if (arr[result[middle]] < arrI) {
                    start = middle + 1;
                } else {
                    end = middle;
                }
            }
            if (arrI < arr[result[start]]) {
                if (start > 0) {
                    p[i] = result[start - 1]; // 替换的时候记录我替换那个的前一个的索引
                }
                result[start] = i; // 直接用当前的索引替换到老的索引
            }
        }
    }
    // 从结果的最后一项开始，倒序查找回来
    len = result.length;
    let last = result[len - 1];
    while (len-- > 0) {
        result[len] = last;
        last = p[last]; // 通过最后一项倒序查找
    }
    return result;
};
console.log(getSeq([2, 3, 1, 5, 6, 8, 7, 9, 4]));

最后，通过求得的最长递增子序列完成新老子节点的更新：

            // 2.4.求解最长递增子序列
            // 这里是求解[5, 3, 4, 0]的最长递增子序列，即求解不需要移动的元素有哪些
            let increasingNewIndexSeq = getSeq(newIndexToOldIndexMap); // [1, 2]
            let j = increasingNewIndexSeq.length - 1; // 取出最后一个的索引
            for (let i = toBePatched - 1; i >= 0; i--) {
                let currentIndex = i + s2; // 获取h节点的位置
                let childNode = c2[currentIndex];
                let anchor = currentIndex + 1 < c2.length ? c2[currentIndex + 1].el : null;
                // 如果以前不存在这个节点就创造出来，再进行插入操作
                if (newIndexToOldIndexMap[i] == 0) {
                    patch(null, childNode, container, anchor);
                } else {
                    if (increasingNewIndexSeq[j] !== i) {
                        hostInsert(childNode.el, container, anchor); // 存在直接将节点进行插入操作
                        // dom操作是具有移动性的，用的是以前的元素，但是都做了一遍重新插入
                    } else {
                        j--;
                    }
                }
            }