https://mp.weixin.qq.com/s/uU2wcs3AX-RRvbu_loQXAQ

Diff 干嘛的

比较前后 DOM 节点变化

设计思路

需求情况

1. 节点属性变化
2. 节点增删
3. 节点移动

思路

1. 判断情况
2. 根据情况进行对应的逻辑处理

   前提

   上面思路基于优先级全都相同，实际开发不是这样

   按这个方案，其实有个隐含的前提—— 「不同操作的优先级是相同的」。但在日常开发中，「节点移动」发生较少，所以Diff算法会优先判断其他情况。 基于这个理念，主流框架（React、Vue）的Diff算法都会经历多轮遍历，先处理「常见情况」，后处理「不常见情况」。 所以，这就要求「处理不常见情况的算法」需要能给各种边界case兜底。 换句话说，完全可以仅使用「处理不常见情况的算法」完成Diff操作。主流框架之所以没这么做是为了性能考虑。 本文会砍掉「处理常见情况的算法」，保留「处理不常见情况的算法」。 这样，只需要40行代码就能实现Diff的核心逻辑。

code

虚拟节点模拟

/* 
Placement对于新生成的node，代表对应DOM需要插入到页面中。对于已有的node，代表对应DOM需要在页面中移动
Deletion代表node对应DOM需要从页面中删除
*/
type Flag = "Placement" | "Delection";
interface Node {
    key: string; //node的唯一标识，用于将节点在变化前、变化后关联上
    flag?: Flag;
    index?: number;
}

如果一个node同时存在于before与after（key相同），我们称这个node可复用。

完整代码

/* 
Placement对于新生成的node，代表对应DOM需要插入到页面中。对于已有的node，代表对应DOM需要在页面中移动
Deletion代表node对应DOM需要从页面中删除
*/
type Flag = "Placement" | "Deletion";
interface _Node {
    key: string; //node的唯一标识，用于将节点在变化前、变化后关联上
    flag?: Flag;
    index?: number;
}
type NList = _Node[]; //NodeList
/**
 *  接受前后的 NodeList 为他们打上标记
 * @param before 更新前的 NodeList
 * @param after
 */
function diff(before: NList, after: NList): NList {
    /* 遍历前的准备工作 */
    //保存结果
    const result: NList = [];
    //将before 保存到 map 中,以O(1)复杂度就能通过key找到before中对应node
    const beforeMap = new Map<string, _Node>();
    before.forEach((node, i) => {
        node.index = i;
        beforeMap.set(node.key, node);
    });
    /* 遍历 after */
    // 遍历到的最后一个可复用node在before中的index
    let lastPlacedIndex = 0;
    for (let i = 0; i < after.length; i++) {
        const afterNode = after[i];
        afterNode.index = i;
        //代表该可复用的node在before中的对应node
        const beforeNode = beforeMap.get(afterNode.key);
        if (beforeNode) {
            // 存在可复用node
            // 从map中剔除该 可复用node
            beforeMap.delete(beforeNode.key);
            const oldIndex = beforeNode.index as number;
            /* 遍历核心逻辑 */
            if (oldIndex < lastPlacedIndex) {
                // 移动
                afterNode.flag = "Placement";
                result.push(afterNode);
                continue;
            } else {
                // 不移动
                lastPlacedIndex = oldIndex;
            }
        } else {
            // 不存在可复用node，这是一个新节点
            afterNode.flag = "Placement";
            result.push(afterNode);
        }
    }
    /* 遍历完收尾 */
    // beforeMap 如果还有 node，就说明这些不能复用，标记删除就好了
    beforeMap.forEach(node => {
        node.flag = "Deletion";
        result.push(node);
    });
    return result;
}
//效果
// 更新前
const before = [{ key: "a" }];
// 更新后
const after = [{ key: "d" }];
/* [
    // diff(before, after) 输出
    ({ key: "d", flag: "Placement" }, { key: "a", flag: "Deletion" })
]; 
 */
// 更新前
// const before: NList = [{ key: "a" }, { key: "b" }, { key: "c" }];
// 更新后
// const after = [{ key: "c" }, { key: "b" }, { key: "a" }];
const df = diff(before, after);
df;