首页 > 编程学习 > 实现最简单的 React DOM Diff 算法

实现最简单的 React DOM Diff 算法

发布时间:2022/8/22 21:40:59

实现最简单的 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 算法。

(完)

Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号