Diff算法的設(shè)計思路

試想，Diff算法需要考慮多少種情況呢？大體分三種，分別是：

節(jié)點屬性變化，比如：

// 更新前
<ul>
  <li key="0" className="before">0</li>
  <li key="1">1</li>
</ul>

// 更新后
<ul>
  <li key="0" className="after">0</li>
  <li key="1">1</li>
</ul>

節(jié)點增刪，比如：

// 更新前
<ul>
  <li key="0">0</li>
  <li key="1">1</li>
  <li key="2">2</li>
</ul>

// 更新后 情況1 —— 新增節(jié)點
<ul>
  <li key="0">0</li>
  <li key="1">1</li>
  <li key="2">2</li>
  <li key="3">3</li>
</ul>

// 更新后 情況2 —— 刪除節(jié)點
<ul>
  <li key="0">0</li>
  <li key="1">1</li>
</ul>

節(jié)點移動，比如：

// 更新前
<ul>
  <li key="0">0</li>
  <li key="1">1</li>
</ul>

// 更新后
<ul>
  <li key="1">1</li>
  <li key="0">0</li>
</ul>

該如何設(shè)計Diff算法呢？考慮到只有以上三種情況，一種常見的設(shè)計思路是：

• 首先判斷當前節(jié)點屬于哪種情況
• 如果是增刪，執(zhí)行增刪邏輯
• 如果是屬性變化，執(zhí)行屬性變化邏輯
• 如果是移動，執(zhí)行移動邏輯

按這個方案，其實有個隱含的前提—— 不同操作的優(yōu)先級是相同的。但在日常開發(fā)中，節(jié)點移動發(fā)生較少，所以Diff算法會優(yōu)先判斷其他情況。

基于這個理念，主流框架（React、Vue）的Diff算法都會經(jīng)歷多輪遍歷，先處理常見情況，后處理不常見情況。

所以，這就要求處理不常見情況的算法需要能給各種邊界case兜底。

換句話說，完全可以僅使用處理不常見情況的算法完成Diff操作。主流框架之所以沒這么做是為了性能考慮。

本文會砍掉處理常見情況的算法，保留處理不常見情況的算法。

這樣，只需要40行代碼就能實現(xiàn)Diff的核心邏輯。

Demo介紹

首先，我們定義虛擬DOM節(jié)點的數(shù)據(jù)結(jié)構(gòu)：

type Flag = 'Placement' | 'Deletion';

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

key是node的唯一標識，用于將節(jié)點在變化前、變化后關(guān)聯(lián)上。

flag代表node經(jīng)過Diff后，需要對相應(yīng)的真實DOM執(zhí)行的操作，其中：

• Placement對于新生成的node，代表對應(yīng)DOM需要插入到頁面中。對于已有的node，代表對應(yīng)DOM需要在頁面中移動
• Deletion代表node對應(yīng)DOM需要從頁面中刪除

index代表該node在同級node中的索引位置

注：本Demo僅實現(xiàn)為node標記flag，沒有實現(xiàn)根據(jù)flag執(zhí)行DOM操作。

我們希望實現(xiàn)的diff方法，接收更新前與更新后的NodeList，為他們標記flag：

type NodeList = Node[];

function diff(before: NodeList, after: NodeList): NodeList {
  // ...代碼
}

比如對于：

// 更新前
const before = [
  {key: 'a'}
]
// 更新后
const after = [
  {key: 'd'}
]

// diff(before, after) 輸出
[
  {key: "d", flag: "Placement"},
  {key: "a", flag: "Deletion"}
]

{key: "d", flag: "Placement"}代表d對應(yīng)DOM需要插入頁面。

{key: "a", flag: "Deletion"}代表a對應(yīng)DOM需要被刪除。

執(zhí)行后的結(jié)果就是：頁面中的a變?yōu)閐。

再比如：

// 更新前
const before = [
  {key: 'a'},
  {key: 'b'},
  {key: 'c'},
]
// 更新后
const after = [
  {key: 'c'},
  {key: 'b'},
  {key: 'a'}
]

// diff(before, after) 輸出
[
  {key: "b", flag: "Placement"},
  {key: "a", flag: "Placement"}
]

由于b之前已經(jīng)存在，{key: "b", flag: "Placement"}代表b對應(yīng)DOM需要向后移動（對應(yīng)parentNode.appendChild方法）。abc經(jīng)過該操作后變?yōu)?code>acb。

由于a之前已經(jīng)存在，{key: "a", flag: "Placement"}代表a對應(yīng)DOM需要向后移動。acb經(jīng)過該操作后變?yōu)?code>cba。

執(zhí)行后的結(jié)果就是：頁面中的abc變?yōu)閏ba。

Diff算法實現(xiàn)

核心邏輯包括三步：

• 遍歷前的準備工作
• 遍歷after
• 遍歷后的收尾工作

function diff(before: NodeList, after: NodeList): NodeList {
  const result: NodeList = [];

  // ...遍歷前的準備工作

  for (let i = 0; i < after.length; i++) {
    // ...核心遍歷邏輯
  }

  // ...遍歷后的收尾工作

  return result;
}

遍歷前的準備工作

我們將before中每個node保存在以node.key為key，node為value的Map中。

這樣，以O(1)復(fù)雜度就能通過key找到before中對應(yīng)node：

// 保存結(jié)果
const result: NodeList = [];
  
// 將before保存在map中
const beforeMap = new Map<string, Node>();
before.forEach((node, i) => {
  node.index = i;
  beforeMap.set(node.key, node);
})

遍歷after

當遍歷after時，如果一個node同時存在于before與after（key相同），我們稱這個node可復(fù)用。

比如，對于如下例子，b是可復(fù)用的：

// 更新前
const before = [
  {key: 'a'},
  {key: 'b'}
]
// 更新后
const after = [
  {key: 'b'}
]

對于可復(fù)用的node，本次更新一定屬于以下兩種情況之一：

• 不移動
• 移動

如何判斷可復(fù)用的node是否移動呢？

我們用lastPlacedIndex變量保存遍歷到的最后一個可復(fù)用node在before中的index：

// 遍歷到的最后一個可復(fù)用node在before中的index
let lastPlacedIndex = 0;  

當遍歷after時，每輪遍歷到的node，一定是當前遍歷到的所有node中最靠右的那個。

如果這個node是可復(fù)用的node，那么nodeBefore與lastPlacedIndex存在兩種關(guān)系：

注：nodeBefore代表該可復(fù)用的node在before中的對應(yīng)node

• nodeBefore.index < lastPlacedIndex

代表更新前該node在lastPlacedIndex對應(yīng)node左邊。

而更新后該node不在lastPlacedIndex對應(yīng)node左邊（因為他是當前遍歷到的所有node中最靠右的那個）。

這就代表該node向右移動了，需要標記Placement。

• nodeBefore.index >= lastPlacedIndex

該node在原地，不需要移動。

// 遍歷到的最后一個可復(fù)用node在before中的index
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) {
  // 存在可復(fù)用node
  // 從map中剔除該 可復(fù)用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 {
  // 不存在可復(fù)用node，這是一個新節(jié)點
  afterNode.flag = 'Placement';
  result.push(afterNode);
}

遍歷后的收尾工作

經(jīng)過遍歷，如果beforeMap中還剩下node，代表這些node沒法復(fù)用，需要被標記刪除。

比如如下情況，遍歷完after后，beforeMap中還剩下{key: 'a'}：

// 更新前
const before = [
  {key: 'a'},
  {key: 'b'}
]
// 更新后
const after = [
  {key: 'b'}
]

這意味著a需要被標記刪除。

所以，最后還需要加入標記刪除的邏輯：

beforeMap.forEach(node => {
  node.flag = 'Deletion';
  result.push(node);
});

完整代碼見在線Demo地址

總結(jié)

整個Diff算法的難點在于lastPlacedIndex相關(guān)邏輯。

跟著Demo多調(diào)試幾遍，相信你能明白其中原理。

到此這篇關(guān)于React實現(xiàn)核心Diff算法的示例代碼的文章就介紹到這了,更多相關(guān)React Diff算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論