How to deeply analyze the diff algorithm in Vue3

Today, I will introduce you to how to analyze the diff algorithm in Vue3 in depth. The content of the article Xiaobian think good, now to share with you, think there is a need for friends can understand, hope to help everyone, the following with the idea of Xiaobian to read together.

1.0 diff No key child node

When processing is marked UNKEYED_FRAGMENT.

The minimum common length commonLength is first obtained from the old and new self sequences.

Loop through patches for common parts.

Patch ends and the remaining old and new nodes are processed.

If oldLength > newLength, the old node needs to be unmounted

Otherwise, it means that there are new nodes and mount is required;

The omitted code is posted here.

const patchUnkeyedChildren = (c1, c2,... res) => { c1 = c1 || EMPTY_ARR c2 = c2 || EMPTY_ARR //Get the length of the old and new child nodes const oldLength = c1.length const newLength = c2.length // 1. Gets the common length. minimum length const commonLength = Math.min(oldLength, newLength) let i // 2. patch common part for (i = 0; i

< commonLength; i++) { patch(...) } // 3. 卸载旧节点 if (oldLength >

newLength) { // remove old unmountChildren(...) } else { // mount new // 4. Otherwise mount the new child node mountChildren(...) } }

As you can see from the above code, the logic is still very simple and rude when dealing with keyless child nodes. To be precise, the efficiency of processing non-key child nodes is not high.

Because whether you patch the common part directly or mount Children directly to the new node (actually traversing the child nodes and performing patch operations), you are actually patching recursively, which will affect performance.

2.0 diff has key child node sequence

When diff has a key subsequence, it will be subdivided. It will mainly be judged through the following circumstances:

The starting position node type is the same.

End position node type same.

After the same part is processed, there are new nodes.

After the same part is processed, there are old nodes that need to be unloaded.

The first part is the same as the second part, but the middle part has reusable disordered nodes.

At the beginning, three corrections will be presented, namely:

i = 0, pointing to the beginning of the new and old sequences

e1 = oldLength - 1, pointing to the end of the old sequence

e2 = newLength - 1, pointing to the end of the new sequence

let i = 0const l2 = c2.lengthlet e1 = c1.length - 1 // prev ending indexlet e2 = l2 - 1 // next ending index

Here's how to start diff processing.

2.1 Same starting node type

For nodes of the same starting position type, diff traversal from left to right.

If the new node type is the same as the old node type, patch processing is performed.

Node types are different, break, jump out of traversal diff

// i