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

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

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

// 更新前
<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é)點(diǎn)增刪，比如：

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

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

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

節(jié)點(diǎn)移動(dòng)，比如：

// 更新前
<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è)計(jì)Diff算法呢？考慮到只有以上三種情況，一種常見的設(shè)計(jì)思路是：

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

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

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

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

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

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

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

Demo介紹

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

type Flag = 'Placement' | 'Deletion';

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

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

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

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

index代表該node在同級(jí)node中的索引位置

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

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

type NodeList = Node[];

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

比如對(duì)于：

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

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

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

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

執(zhí)行后的結(jié)果就是：頁(yè)面中的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對(duì)應(yīng)DOM需要向后移動(dòng)（對(duì)應(yīng)parentNode.appendChild方法）。abc經(jīng)過該操作后變?yōu)?code>acb。

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

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

Diff算法實(shí)現(xiàn)

核心邏輯包括三步：

• 遍歷前的準(zhǔn)備工作
• 遍歷after
• 遍歷后的收尾工作

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

  // ...遍歷前的準(zhǔn)備工作

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

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

  return result;
}

遍歷前的準(zhǔn)備工作

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

這樣，以O(1)復(fù)雜度就能通過key找到before中對(duì)應(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

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

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

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

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

• 不移動(dòng)
• 移動(dòng)

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

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

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

當(dāng)遍歷after時(shí)，每輪遍歷到的node，一定是當(dāng)前遍歷到的所有node中最靠右的那個(gè)。

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

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

• nodeBefore.index < lastPlacedIndex

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

而更新后該node不在lastPlacedIndex對(duì)應(yīng)node左邊（因?yàn)樗?strong>當(dāng)前遍歷到的所有node中最靠右的那個(gè)）。

這就代表該node向右移動(dòng)了，需要標(biāo)記Placement。

• nodeBefore.index >= lastPlacedIndex

該node在原地，不需要移動(dòng)。

// 遍歷到的最后一個(gè)可復(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) {
    // 移動(dòng)
    afterNode.flag = 'Placement';
    result.push(afterNode);
    continue;
  } else {
    // 不移動(dòng)
    lastPlacedIndex = oldIndex;
  }

} else {
  // 不存在可復(fù)用node，這是一個(gè)新節(jié)點(diǎn)
  afterNode.flag = 'Placement';
  result.push(afterNode);
}

遍歷后的收尾工作

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

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

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

這意味著a需要被標(biāo)記刪除。

所以，最后還需要加入標(biāo)記刪除的邏輯：

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

完整代碼見在線Demo地址

總結(jié)

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

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

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