40 lines of code to implement the React core Diff algorithm

Hello, everyone. I am Karsong.

Any framework that relies on the virtual DOM requires a Diff algorithm that compares the changes of nodes before and after.

There are numerous articles on the web explaining the logic of Diff’s algorithm. However, even if the author’s language is concise and well illustrated, I believe that most students will forget it before long after reading it.

Today, we’ll take a different approach to learning once and for all — implementing the React core Diff algorithm.

Not hard. Only 40 lines of code. Don’t believe it? To look down.

Welcome to join the Human high quality front-end framework research group, Band fly

Diff algorithm design ideas

Think about it, how many cases does the Diff algorithm have to consider? There are three kinds, namely:

Node attribute changes, such as:

/ / before update
<ul>
  <li key="0" className="before">0</li>
  <li key="1">1</li>
</ul>

/ / updated
<ul>
  <li key="0" className="after">0</li>
  <li key="1">1</li>
</ul>
Copy the code

Node addition and deletion, for example:

/ / before update
<ul>
  <li key="0">0</li>
  <li key="1">1</li>
  <li key="2">2</li>
</ul>

// Update case 1 -- new node
<ul>
  <li key="0">0</li>
  <li key="1">1</li>
  <li key="2">2</li>
  <li key="3">3</li>
</ul>

// Update case 2 -- delete node
<ul>
  <li key="0">0</li>
  <li key="1">1</li>
</ul>
Copy the code

Node movement, for example:

/ / before update
<ul>
  <li key="0">0</li>
  <li key="1">1</li>
</ul>

/ / updated
<ul>
  <li key="1">1</li>
  <li key="0">0</li>
</ul>
Copy the code

How do you design the Diff algorithm? Considering that there are only three cases above, a common design idea is:

First determine which case the current node belongs to
If it is add or delete, perform the add or delete logic
If it is a property change, perform the property change logic
If it is a move, perform the move logic

In this scenario, there is an implicit premise that the priority of different operations is the same. However, in daily development, node movement occurs rarely, so Diff algorithm will give priority to other cases.

Based on this concept, Diff algorithms of mainstream frameworks (React and Vue) go through multiple rounds of traversal, processing common cases first and then uncommon cases.

So, this requires that an algorithm that deals with unusual cases needs to be able to give a bottom pocket to all kinds of boundary cases.

In other words, it is perfectly possible to do Diff operations using algorithms that deal only with unusual cases. Mainstream frameworks don’t do this for performance reasons.

In this paper, algorithms for common cases will be cut down and those for uncommon cases will be retained.

Thus, it takes only 40 lines of code to implement the core logic of Diff.

The Demo is introduced

First, we define the data structure of the virtual DOM node:

type Flag = 'Placement' | 'Deletion';

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

A key is the unique identifier of a node and is used to associate a node before and after it changes.

Flag represents the operations that the node needs to perform on the corresponding real DOM after Diff, where:

Placement for a newly generated node, the corresponding DOM needs to be inserted into the page. For existing nodes, the corresponding DOM needs to be moved around the page
Deletion indicates that the DOM corresponding to a node needs to be deleted from the page

Index Indicates the index position of the node in the peer node

Note: This Demo only implements node flag, but does not implement DOM operations based on flag.

The diff method we want to implement receives the NodeList before and after the update and flags them:

type NodeList = Node[];

function diff(before: NodeList, after: NodeList) :NodeList {
  / /... code
}
Copy the code

For example:

/ / before update
const before = [
  {key: 'a'}]/ / updated
const after = [
  {key: 'd'}]Diff (before, after[{key: "d".flag: "Placement"},
  {key: "a".flag: "Deletion"}]Copy the code

{key: “d”, flag: “Placement”} indicates that the page corresponding to DOM of D needs to be inserted.

{key: “a”, flag: “Deletion”} indicates that DOM corresponding to A needs to be deleted.

The result: an A on the page changes to a D.

Such as:

/ / before update
const before = [
  {key: 'a'},
  {key: 'b'},
  {key: 'c'},]/ / updated
const after = [
  {key: 'c'},
  {key: 'b'},
  {key: 'a'}]Diff (before, after[{key: "b".flag: "Placement"},
  {key: "a".flag: "Placement"}]Copy the code

Since b already exists, {key: “b”, flag: “Placement”} means that B needs to be moved backward for the DOM (corresponding to the parentNode.appendChild method). After this operation, ABC becomes ACB.

Because a already exists, {key: “a”, flag: “Placement”} means that DOM of A needs to be moved backwards. After this operation, acB becomes CBA.

The result is that the ABC in the page is changed to CBA.

Diff algorithm implementation

The core logic consists of three steps:

Preparation before traversal
Traverse after
The finishing touches after traversal

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

  / /... Preparation before traversal

  for (let i = 0; i < after.length; i++) {
    / /... Core traversal logic
  }

  / /... The finishing touches after traversal

  return result;
}
Copy the code

Preparation before traversal

We store each node in before in a Map with node.key as key and node as value.

Key = O(1);

// Save the result
const result: NodeList = [];
  
// Save before in map
const beforeMap = new Map<string, Node>();
before.forEach((node, i) = > {
  node.index = i;
  beforeMap.set(node.key, node);
})
Copy the code

Traverse after

When traversing after, a node is said to be reusable if it exists both before and after (with the same key).

For example, b is reusable for example:

/ / before update
const before = [
  {key: 'a'},
  {key: 'b'}]/ / updated
const after = [
  {key: 'b'}]Copy the code

For reusable Nodes, this update must fall into one of two categories:

Don’t move
mobile

How do you tell if a reusable node is moving?

We use the lastPlacedIndex variable to hold the index of the last reusable node iterated over in before:

// Index of the last reusable node traversed in before
let lastPlacedIndex = 0;  
Copy the code

When traversing after, the node traversed in each turn must be the node most to the right of the node currently traversed.

If the node is reusable, then nodeBefore has two relationships with lastPlacedIndex:

Note: nodeBefore represents the node corresponding to the reusable node in before

nodeBefore.index < lastPlacedIndex

The node was to the left of the node corresponding to lastPlacedIndex before the update.

After the update, the node is not to the left of the node corresponding to lastPlacedIndex (because it is the right-most node of all the nodes currently traversed).

This means that the Node has moved to the right and the Placement needs to be marked.

nodeBefore.index >= lastPlacedIndex

The node is in place and does not need to be moved.

// Index of the last reusable node traversed in before
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) {
  // There are reusable nodes
  // Remove the reusable node from the map
  beforeMap.delete(beforeNode.key);

  const oldIndex = beforeNode.index as number;

  // Core judgment logic
  if (oldIndex < lastPlacedIndex) {
    / / move
    afterNode.flag = 'Placement';
    result.push(afterNode);
    continue;
  } else {
    / / does not movelastPlacedIndex = oldIndex; }}else {
  // There is no reusable node, this is a new node
  afterNode.flag = 'Placement';
  result.push(afterNode);
}
Copy the code

The finishing touches after traversal

After traversal, if there are nodes left in beforeMap, these nodes cannot be reused and need to be marked for deletion.

For example, after traversing, beforeMap leaves {key: ‘a’} :

/ / before update
const before = [
  {key: 'a'},
  {key: 'b'}]/ / updated
const after = [
  {key: 'b'}]Copy the code

This means that a needs to be marked for deletion.

So, finally, we need to add the tag deletion logic:

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

See online Demo address for complete code

conclusion

The difficulty of the whole Diff algorithm is the lastPlacedIndex logic.

Follow the Demo to debug a few times, I believe you can understand the principle.

40 lines of code to implement the React core Diff algorithm

Diff algorithm design ideas

The Demo is introduced

Diff algorithm implementation

Preparation before traversal

Traverse after

The finishing touches after traversal

conclusion

Related Posts

CSS box model full analysis + application

HTML Basics – Semantic tags – Browser rendering process – Notes and extensions

[Luffy]_leetcode202. Happiness number