实现最简单的 React DOM Diff 算法

本文写于 2022 年 08 月 22 日

定义 VNode 与 VNodeList 类型

首先我们定义一个简单的 VNode 类型。

type Flag = "Placement" | "Deletion";

interface VNode {
  key: string;
  flag?: Flag;
  index?: number;
}

type VNodeList = VNode[];

• 这里 flag 代表了操作类型，如果是 "Placement" 意味着移动或者创建新的节点，如果是 "Deletion" 则是移除该节点
• index 则是该 Node 在 VNodeList 中的 index（将数组存入 Map 之后会用到该属性）

构造测试数据

这里我们再构造两个 VNodeList 用于模拟用于 diff 的前后两颗虚拟 DOM 树。

const before: VNodeList = [{ key: "a" }, { key: "d" }];

const after: VNodeList = [{ key: "d" }, { key: "c" }];

我们期待他的输出应该是：

[
  { key: "c", index: 1, flag: "Placement" },
  { key: "a", index: 0, flag: "Deletion" },
];

完成 diff 函数

接下来该实现我们的超简单 diff 算法了，该函数签名如下。

function diff(before: VNodeList, after: VNodeList): VNodeList;

VNode 的三种操作

首先我们明确一个思路。

在 VNodeList 的 diff 过程当中，对于每个节点来说，只存在三种操作：创建、删除、向右移动。（这里为什么不存在向左移动呢？因为如果节点右移，那么我们就可以将向左移动理解为原地不动。）

然后我们就可以开始遍历 after 数组了，不过在此之间，可以通过 Hash 结构将 before 数组储存起来，这样我们遍历的时候可以直接通过 key 去寻找相同的节点。

function diff(before: VNodeList, after: VNodeList): VNodeList {
  const retList: VNodeList = [];

  const beforeMap: Map<string, VNode> = new Map();
  before.forEach((item, index) => {
    item.index = index;
    beforeMap.set(item.key, node);
  });

  for (let i = 0; i < after.length; i++) {
    const afterNode = after[i];
    afterNode.index = i;

    const beforeNode = beforeMap.get(afterNode.key);

    // TODO
  }

  return retList;
}

判断创建与删除

当我们从缓存中取到了 beforeNode 之后，会先进行一次判断：

1. 如果没有 beforeNode，说明是全新节点，需要创建
2. 如果有 beforeNode，说明是需要移动的节点

// ...
// const beforeNode = beforeMap.get(afterNode.key);

if (!beforeNode) {
  afterNode.flag = "Placement";
  retList.push(afterNode);
  continue;
}

beforeMap.delete(beforeNode.key);

// ...
// 循环结束

beforeMap.forEach((item) => {
  item.flag = "Deletion";
  retList.push(item);
});

创建节点非常简单，只需要修改 flag，而后将其放入需要 return 的结果数组即可进入下一个循环。

而需要移动的节点，则可以直接从 map 中删除，这样在循环结束后，map 中还剩下的 node 就是需要删除的了。

最后没有被以上条件筛选掉的话，就是需要进行我们的“右移”判断的 VNode 了。

右移判断

首先，我们使用一个变量来记录上一次右移的 beforeNode 的 index。

因为当前我们所遍历到的 afterNode，一定是当前遍历过的 VNode 中最右边的。

那么如果当前 VNode 所对应的 beforeNode，一定在上次右移的 beforeNode 的左边，可上次右移的 beforeNode 又在当前 afterNode 的左边。

相当于：

node1 -> node2

node2 -> node1

所以可以清晰的判断出 node1 是需要右移的。

即 beforeNode.index < lastPlacedIndex，则右移当前节点，否则当前节点位置不变。

let lastPlacedIndex = 0;

//  for (let i = 0; i < after.length; i++) {
// ...
// beforeMap.delete(beforeNode.key);

const oldIndex = beforeNode.index!;

if (oldIndex < lastPlacedIndex) {
  afterNode.flag = "Placement";
  retList.push(afterNode);
  continue;
}

lastPlacedIndex = oldIndex;

// ...
// 循环结束

完整代码入下：

function diff(before: VNodeList, after: VNodeList): VNodeList {
  const retList: VNodeList = [];

  const beforeMap: Map<string, VNode> = new Map();
  before.forEach((node, i) => {
    node.index = i;
    beforeMap.set(node.key, node);
  });

  let lastPlacedIndex = 0;

  for (let i = 0; i < after.length; i++) {
    const afterNode = after[i];
    afterNode.index = i;
    const beforeNode = beforeMap.get(afterNode.key);

    if (!beforeNode) {
      afterNode.flag = "Placement";
      retList.push(afterNode);
      continue;
    }

    beforeMap.delete(beforeNode.key);

    const oldIndex = beforeNode.index!;

    if (oldIndex < lastPlacedIndex) {
      afterNode.flag = "Placement";
      retList.push(afterNode);
      continue;
    }

    lastPlacedIndex = oldIndex;
  }

  beforeMap.forEach((item) => {
    item.flag = "Deletion";
    retList.push(item);
  });

  return retList;
}

如此这般操作，我们就成功实现了一个超级简单版的 React DOM Diff 算法。

（完）