Virtual DOM 原理

1. 利用 JavaScript 创建 DOM 树
2. 树的 diff，同层对比，输出 patchs(listDiff / diffChildren / diffProps)
   1. 没有新的节点，返回
   2. 新的节点 tagName 与 key 不变，对比 props，继续递归遍历子树
      1. 对比属性（对比新旧属性列表）
      2. 都存在的是否有变化
      3. 是否出现旧列表中没有的新属性
   3. tagName 和 key 值变化了，则直接替换成新节点
3. 渲染差异
   1. 遍历 patchs，把需要更改的节点取出来
   2. 局部更新 DOM

// diff 算法的实现
function diff(oldTree, newTree) {
    const patchs = {}; // 差异收集
    dfs(oldTree, newTree, 0, patchs);
    return patchs;
}

function dfs(oldNode, newNode, index, patchs) {
    let curPatchs = [];
    if (newNode) {
        // 当新旧节点的 tagName 和 key 完全一致时
        if (oldNode.tagName === newNode.tagName && oldNode.key === newNode.key) {
            // 继续对比属性差异
            const props = diffProps(oldNode.props, newNode.props);
            curPatchs.push({ type: "changeProps", props });

            // 递归进入下一层级比较
            diffChildren(oldNode.children, newNode.children, index, patchs);
        } else {
            curPatchs.push({ type: "replaceNode", node: newNode });
        }
    }

    // 构建出整个差异树
    if (curPatchs.length) {
        if (patchs[index]) {
            patchs[index] = patchs[index].concat(curPatchs);
        } else {
            patchs[index] = curPatchs;
        }
    }
}

// 属性对比实现
function diffProps(oldProps, newProps) {
    const propsPatchs = [];
    // 遍历新旧属性列表
    // 查找删除项
    // 查找修改项
    // 查找新增项
    for (const key in oldProps) {
        if (!newProps.hasOwnProperty(key))
            propsPatchs.push({ type: "remove", prop: oldProps[key] }); // 移除
        else if (oldProps[key] !== newProps[key])
            propsPatchs.push({
                type: "change",
                prop: oldProps[key],
                value: newProps[k],
            }); // 修改
    }

    for (const key in newProps) {
        if (!oldProps.hasOwnProperty(key))
            propsPatchs.push({ type: "add", prop: newProps[key] }); // 新增
    }
    return propsPatchs;
}

// 对比子级差异
function diffChildren(oldChild, newChild, index, patchs) {
    // 标记子级的删除/新增/移动
    let { change, list } = diffList(oldChild, newChild, index, patchs);
    if (change.length) {
        if (patchs[index]) patchs[index] = patchs[index].concat(change);
        else patchs[index] = change;
    }

    // 根据 key 获取原本匹配的节点，进一步递归从头开始对比
    oldChild.map((item, i) => {
        let keyIndex = list.indexOf(item.key);
        if (keyIndex) {
            let node = newChild[keyIndex];
            // 进一步递归对比
            dfs(item, node, index, patchs);
        }
    });
}

// 对比列表，主要也是根据 key 值查找匹配项
// 对比出新旧列表的新增/删除/移动
function diffList(oldList, newList, index, patchs) {
    let change = [];
    let list = [];
    const newKeys = newList.map((item) => item.key);
    oldList.forEach((item) => {
        if (newKeys.includes(item.key)) list.push(item.key);
        else list.push(null);
    });

    // 标记删除
    for (let i = list.length - 1; i >= 0; i--) {
        if (!list[i]) {
            list.splice(i, 1);
            change.push({ type: "remove", index: i });
        }
    }

    // 标记新增和移动
    newList.forEach((item, i) => {
        const { key } = item;
        const index = list.indexOf(key);
        if (index === -1 || key === null) {
            // 新增
            change.push({ type: "add", node: item, index: i });
            list.splice(i, 0, key);
        } else if (index !== i) {
            // 移动
            change.push({ type: "move", form: index, to: i });
            move(list, index, i);
        }
    });

    return { change, list };
}