Shulou(Shulou.com)05/31 Report--

This article mainly explains "how to achieve the core Diff algorithm in React". Interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn "how React implements the core Diff algorithm".

Design idea of Diff algorithm

Just imagine, how many situations does the Diff algorithm need to consider? It can be divided into three categories, namely:

Node attribute changes, such as:

/ / 0 1 stroke before update / 0 1 after update

Add and delete nodes, such as:

/ / pre-update 0 1 2 stroke / post-update case 1-new node 0 1 2 3 stroke / post-update case 2-delete node 0 1

Node movement, such as:

/ / 0 1 stroke before update / 1 0 after update

How to design the Diff algorithm? Considering that there are only three situations mentioned above, a common design idea is:

First of all, determine which situation the current node belongs to.

If it is adding or deleting, execute the logic of adding and deleting.

If it is an attribute change, execute the attribute change logic

If it is mobile, execute the mobile logic

According to this scheme, there is an implicit premise that different operations have the same priority. However, in daily development, node movement occurs less, so the Diff algorithm will give priority to other situations.

Based on this idea, the Diff algorithms of the mainstream frameworks (React, Vue) will go through multiple rounds of traversal, dealing with common situations first and then dealing with unusual situations.

Therefore, this requires that algorithms that deal with unusual situations need to be able to cover all kinds of boundary case.

In other words, Diff operations can be done using only algorithms that deal with unusual situations. The reason why mainstream frameworks do not do this is for performance considerations.

This article will cut off the algorithms that deal with common situations and retain the algorithms that deal with unusual situations.

In this way, it takes only 40 lines of code to implement the core logic of Diff.

Demo introduction

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

Type Flag = 'Placement' |' Deletion';interface Node {key: string; flag?: Flag; index?: number;}

Key is the unique identity of node, which is used to associate nodes before and after changes.

Flag represents the actions that need to be performed on the corresponding real DOM after the node passes through the Diff, where:

Placement for the newly generated node, it means that the corresponding DOM needs to be inserted into the page. For existing node, it means that the corresponding DOM needs to be moved in the page

Deletion indicates that the corresponding DOM of node needs to be deleted from the page.

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

Note: this Demo is only implemented as node tag flag, and does not implement DOM operation according to flag.

The diff method we want to implement, receives the NodeList before and after the update, and marks flag for them:

Type NodeList = Node []; function diff (before: NodeList, after: NodeList): NodeList {/ /. Code}

For example, for:

/ / const before before update = [{key:'a'}] / / after update const after = [{key:'d'}] / / diff (before, after) output [{key: "d", flag: "Placement"}, {key: "a", flag: "Deletion"}]

{key: "d", flag: "Placement"} means that d needs to be inserted into the page corresponding to DOM.

{key: "a", flag: "Deletion"} means that a corresponding DOM needs to be deleted.

The result of execution is that an in the page becomes d.

Another example is:

/ / pre-update const before = [{key:'a'}, {key:'b'}, {key:'c'},] / / after update const after = [{key:'c'}, {key:'b'}, {key:'a'}] / / diff (before, after) output [{key: "b", flag: "Placement"}, {key: "a", flag: "Placement"}]

Since b already exists before, {key: "b", flag: "Placement"} means that b needs to move backward corresponding to DOM (corresponding to the parentNode.appendChild method). Abc becomes acb after this operation.

Since an already exists before, {key: "a", flag: "Placement"} means that a needs to move backward corresponding to DOM. Acb becomes cba after this operation.

The result of execution is that the abc in the page becomes cba.

Implementation of Diff algorithm

The core logic includes three steps:

Preparatory work before traversing

Traversing after

The finishing touches after traversing

Function diff (before: NodeList, after: NodeList): NodeList {const result: NodeList = []; / /. Preparation before traversal for (let I = 0; I

< after.length; i++) { // ...核心遍历逻辑 } // ...遍历后的收尾工作 return result;}遍历前的准备工作 我们将before中每个node保存在以node.key为key，node为value的Map中。 这样，以O(1)复杂度就能通过key找到before中对应node： // 保存结果const result: NodeList = []; // 将before保存在map中const beforeMap = new Map();before.forEach((node, i) =>

{node.index = I; beforeMap.set (node.key, node);}) traversing after

When traversing an after, if a node exists in both before and after (key is the same), we call the node reusable.

For example, for the following example, b is reusable:

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

For reusable node, this update must be one of the following two situations:

Do not move

move

How can you tell if a reusable node is moving?

We use the lastPlacedIndex variable to save the index of the last reusable node in before that we traversed:

/ / the indexlet lastPlacedIndex of the last reusable node traversed in before = 0

When traversing the after, the node traversed in each round must be the rightmost of all the node currently traversed.

If this node is a reusable node, there are two relationships between nodeBefore and lastPlacedIndex:

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

NodeBefore.index

< lastPlacedIndex 代表更新前该node在lastPlacedIndex对应node左边。 而更新后该node不在lastPlacedIndex对应node左边（因为他是当前遍历到的所有node中最靠右的那个）。 这就代表该node向右移动了，需要标记Placement。 nodeBefore.index >

= lastPlacedIndex

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

/ / the last reusable node traversed is indexlet lastPlacedIndex = 0; for (let I = 0; I) in before

< after.length; i++) {const afterNode = after[i];afterNode.index = i;const beforeNode = beforeMap.get(afterNode.key);if (beforeNode) { // 存在可复用node // 从map中剔除该 可复用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 { // 不存在可复用node，这是一个新节点 afterNode.flag = 'Placement'; result.push(afterNode);}遍历后的收尾工作 经过遍历，如果beforeMap中还剩下node，代表这些node没法复用，需要被标记删除。 比如如下情况，遍历完after后，beforeMap中还剩下{key: 'a'}： // 更新前const before = [ {key: 'a'}, {key: 'b'}]// 更新后const after = [ {key: 'b'}] 这意味着a需要被标记删除。 所以，最后还需要加入标记删除的逻辑： beforeMap.forEach(node =>

{node.flag = 'Deletion'; result.push (node);}); at this point, I believe you have a better understanding of "how React implements the core Diff algorithm". You might as well do it! Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.