## Preface

learned React、Vue2 Of diff Algorithm , It's time to learn again Vue3 It's time ,Vue3 Came out for a while , I can't say without understanding ~

This article is mainly divided into two parts ：

One 、diff The general flow and implementation idea of the algorithm

Two 、 Deep source , Look at the implementation

## The core diff Ideas

We all know , Usually when we compare, only when it is the same parent element , Only if the parent element is the same node , To go down . Let's assume that their parents are the same , Start by comparing the child nodes directly . In order to distinguish the ideas in different scenes , Each part gives different examples .

### Pretreatment optimization

Let's take a look at the following two groups of simple node comparison , stay Vue3 First of all, the traversal of the head and tail will be carried out in , Carry out pretreatment optimization .

#### 1、 Traverse from the beginning

First, the start node is traversed , Judge whether the first node of the new and old is consistent , In agreement , perform patch Methods update differences , And then continue to compare , otherwise break Jump out of . You can see in the figure below ,A vs A It's the same , And then compare B,B It's the same , And then compare C vs D, It's different , So jump out of the current cycle .

#### 2、 The tail starts

Then we start to traverse from the back to the front , Look for the same elements ,G vs G, Agreement , Then perform patch Back to front ,F vs F Agreement , Keep going diff, until E and C atypism , Out of the loop .

#### 3、 One side has dealt with it

At present, there is a new node left in the new node , Then we will judge whether the traversal of the old node is completed , And then add it . Below C Node is to add .

If it is an old node, there is still a redundant node , Then it will judge whether the new node has been traversed , And then unload it . Below I Node is to unload .

Here we are , Someone must want to ask , Why do that ？

But we all know intuitively why , Usually when we modify the list , There are some common scenes , For example, the addition of middle nodes in the list 、 Delete 、 Modify etc. , If you use this method to find , Can reduce the diff Time for , You don't even have to diff To achieve the results we want , And it can also reduce the follow-up diff Complexity . This preprocessing optimization strategy , yes Neil Fraser Proposed , Want to know more , You can get to know .

There should be some understanding here , So the next scenario that we haven't come to is the situation that there are still many child nodes left in the new and old nodes . Let's think about it again , If we are to do such a demand , What are we going to do ？

I first thought of Vue2 The way , New and old nodes go through the search and then move . But if so , It's like following Vue2 It's not necessarily better than . stay Vue2 Ergodic time , We're using cross traversal . What are the main problems to be solved in this way ？ A simple example ：

If this example is in the process we just started , It won't do anything , however Vue2 When we go traversal, we will do cross head and tail traversal , And then one by one they match to , And for the first time it matched to G Node time , It will G Node move to A In front of the node , Subsequent matching ABF Node time , Just go to patch, But you don't have to move 了 , Because the G Node move to A Front and back , real DOM The order of nodes is consistent with the new node .

According to the previous idea I went to traverse , You need to move four times , Pictured ：

So here comes the question , Next, how can we continue to optimize on the basis of previous optimization ？

```
It's like we find the increasing node of the column , You know which nodes are stable .
Here we introduce a concept , It's called the longest increasing subsequence .
Official explanation ： In a given array , Find a set of increasing numbers , And as long as possible .
It's kind of hard to understand , Let's take a concrete example ：
const arr = [10, 9, 2, 5, 3, 7, 101, 18]
=> [2, 3, 7, 18, 30]
This array is arr The longest increasing subsequence of
```

To learn more about it, take a look at this question ： The longest enhancer sequence

So if we can find it , The old nodes in the new node sequence have the same order , You know , Which nodes don't need to move , Then you just need to insert the nodes that are not here . Before that , Let's find all the nodes first , Find the corresponding sequence .

#### 3、 Find the coordinates of the old node corresponding to the new node

One last new example , want diff These two groups of nodes , Above is the old node , Here's the new node ~ Through the bedding above , We learned that , To find such an array [2, 3, newly added , 0], But because the initial value of the array is 0, It represents the new meaning , So we take this coordinate +1, What's new is 0, That is to say [3, 4, 0, 1], We can think of it as the second 1 position , The first 2 position , The first 3 The meaning of bit is .

It's easy to find this array , Let's go through the old nodes first , Find the corresponding new node , And then add it to the coordinates of the new node . We're starting to traverse , In the process of traversing , Will execute patch And unload operations , As shown in the table below ：

The current old coordinate subscript | The coordinates of the new node currently found | The old node array corresponding to the new node coordinate ( The initial value is 0, On behalf of the new , Add in the coordinates +1) |
---|---|---|

0 | 3 | [0, 0, 0, 1] |

1 | nothing | uninstall |

2 | 0 | [3, 0, 0, 1] |

3 | 1 | [3, 4, 0, 1] |

After traversing the array , The final array is [3, 4, 0, 1], And then we'll find that its longest enhancer sequence is 3, 4, It corresponds to the first node D And the second node E, So these two nodes don't need to move .

Finally, we traverse the new node , If our current node is in the longest enhancer sequence , It doesn't move , by 0 Then directly add , The rest moves to the current position .

The general process is over here , We are following the source code for an in-depth understanding of it ~

## Source code

Source file path ：packages/runtime-core/src/renderer.ts

Source warehouse address ： vue-next

### patchChildren

We from `patchChildren`

Method start , Compare the child nodes .

```
const patchChildren: PatchChildrenFn = () => {
// Get the child nodes under the current old and new nodes
const c1 = n1 && n1.children
const prevShapeFlag = n1 ? n1.shapeFlag : 0
const c2 = n2.children
const { patchFlag, shapeFlag } = n2
// fragment There are two types of static tags ： Child nodes have key、 The child node has no key
if (patchFlag > 0) {
if (patchFlag & PatchFlags.KEYED_FRAGMENT) {
// All or part of the child nodes have key
patchKeyedChildren()
return
} else if (patchFlag & PatchFlags.UNKEYED_FRAGMENT) {
// Child nodes don't have key
patchUnkeyedChildren()
return
}
}
// There are three possibilities for child nodes ： Text node 、 Array （ At least one child node ）、 No child node
if (shapeFlag & ShapeFlags.TEXT_CHILDREN) {
// Match to the current text node ： Unload the previous node , Set the text node for it
unmountChildren()
hostSetElementText()
} else {
// old Child nodes are arrays
if (prevShapeFlag & ShapeFlags.ARRAY_CHILDREN) {
if (shapeFlag & ShapeFlags.ARRAY_CHILDREN) {
// Now? (new) It's also an array （ At least one child node ）, direct full diff（ call patchKeyedChildren()）
} else {
// Otherwise, there are currently no child nodes , Directly unload all the current child nodes
unmountChildren()
}
} else {
// old The child nodes of are text or not
if (prevShapeFlag & ShapeFlags.TEXT_CHILDREN) {
// Empty text
hostSetElementText(container, '')
}
// Now? (new) The node of is more than one child node , Directly add
if (shapeFlag & ShapeFlags.ARRAY_CHILDREN) {
// Create a new child node
mountChildren()
}
}
}
}
```

We can describe this code directly in text ：

1、 Get the child nodes under the current old and new nodes (c1、c2)

2、 Use `patchFlag`

Carry out position and judgment `fragment`

Whether the child node of has key（patchFlag I'll talk about it later ）

3、 With or without key, As long as the match is successful, it must be an array , Yes key/ Some have key Call `patchKeyedChildren`

methods diff Calculation , nothing key Call `patchUnkeyedChildren`

Method

4、 No fragment node , So there are three possibilities for child nodes ： Text node 、 Array ( At least one child node )、 No child node

5、 If new The children of are ** Text node **：old If there are child nodes, they will be unloaded directly , And set the text node for it

6、 otherwise new The children of are ** Array or Nodeless **, On this basis ：

7、 If old The child nodes of are arrays , that new If the child node of is also an array , call `patchKeyedChildren`

Method , direct full diff, otherwise new No child node , Unload directly

8、 Last old The child nodes of are text nodes or No nodes （ At this point, the new node may be an array , There may be no nodes ）, So when old The child nodes of are text nodes , Then clear the text ,new If the node is an array , Directly add

9、 At this point, all the situations have been dealt with , But really diff Not yet. , Let's have a look key Under the circumstances , Whether to carry out diff Of

### patchUnkeyedChildren

No, key It's easy to deal with , Directly on the abridged version of the source code

```
const patchUnkeyedChildren = () => {
c1 = c1 || EMPTY_ARR
c2 = c2 || EMPTY_ARR
const oldLength = c1.length
const newLength = c2.length
// Get the minimum length of the old and new nodes
const commonLength = Math.min(oldLength, newLength)
let i
// Traversing old and new nodes , Conduct patch
for (i = 0; i < commonLength; i++) {
// If the new node has been mounted ( It's been dealt with all sorts of ways ), directly clone One copy , Otherwise create a new vnode node
const nextChild = (c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i]))
patch()
}
// If the number of old nodes is greater than the number of new nodes
if (oldLength > newLength) {
// Unload redundant nodes directly
unmountChildren( )
} else {
// old length < new length => Create directly
mountChildren()
}
}
```

Let's continue with the text to describe the logic ：

1、 First, we will get the shortest common length of the old and new nodes

2、 Then traverse the common part , Go straight ahead patch

3、 If the number of old nodes is greater than the number of new nodes , Unload redundant nodes directly , Otherwise, create a new node

### patchKeyedChildren

here we are Diff The core part of the algorithm comparison , Let's look at a preview first , Take a look at the process ~ And then `patchKeyedChildren`

Split the source code inside , Step by step .

```
const patchKeyedChildren = () => {
let i = 0
const l2 = c2.length
let e1 = c1.length - 1 // prev ending index
let e2 = l2 - 1 // next ending index
// 1. Head traversal , If the same node is encountered, continue , Different nodes jump out of the loop
while (i <= e1 && i <= e2) {}
// 2. Do tail traversal , If the same node is encountered, continue , Different nodes jump out of the loop
while (i <= e1 && i <= e2) {}
// 3. If the old node has been traversed , And the new node has something left , Then traverse the rest to add
if (i > e1) {
if (i <= e2) {}
}
// 4. If the new node has been traversed , And the old nodes are left , Then unload it directly
else if (i > e2) {
while (i <= e1) {}
}
// 5. Old and new nodes are not traversed completely
else {
// 5.1 Create a map, Store key value pairs for the remaining new nodes , The mapping relationship ：key => index
// 5.2 Traverse the remaining old nodes , Comparison of old and new data , Remove old nodes that are not used
// 5.3 Take the longest incrementing subsequence move or Add mount
}
}
```

**1、 The first step is to traverse the head , If the same node is encountered, continue , Subscript + 1, Different nodes jump out of the loop **

```
// 1. sync from start
// (a b) c
// (a b) d e
while (i <= e1 && i <= e2) {
const n1 = c1[i]
// If the new node has been mounted ( Has gone through all kinds of processing ), directly clone One copy , Otherwise create a new vnode node
const n2 = (c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i]))
// Same node , Then continue patch Method
if (isSameVNodeType(n1, n2)) {
patch()
} else {
break
}
i++
}
```

here i = 2, e1 = 6, e2 = 7, Old nodes left C、D、E、F、G, The new node is left D、E、I、C、F、G

Here is a method to judge whether it is the same node `isSameVNodeType`

, It's by type and key To judge , stay Vue2 China is through key and sel( Attribute selector ) To see if it's the same element . The type here refers to ShapeFlag, It's also a flag bit , It's about classifying different types of elements , such as ： Elements 、 Components 、fragment、 Slots and so on

```
export function isSameVNodeType(n1: VNode, n2: VNode): boolean {
return n1.type === n2.type && n1.key === n2.key
}
```

**2、 The second step is tail traversal , If the same node is encountered, continue ,length - 1, Different nodes jump out of the loop **

```
// 2. sync from end
// a (b c)
// d e (b c)
// Do tail traversal , If the same node is encountered, continue , Different nodes jump out of the loop
while (i <= e1 && i <= e2) {
const n1 = c1[e1]
const n2 = (c2[e2] = optimized
? cloneIfMounted(c2[e2] as VNode)
: normalizeVNode(c2[e2]))
if (isSameVNodeType(n1, n2)) {
patch()
} else {
break
}
e1--
e2--
}
```

here i = 2, e1 = 4, e2 = 5, Old nodes left C、D、E, The new node is left D、E、I、C

**3、 If the old node has been traversed , And the new node has something left , Then traverse the rest to add **

```
// 3.common sequence + mount
// (a b)
// (a b) c
// i = 2, e1 = 1, e2 = 2
// (a b)
// c (a b)
// i = 0, e1 = -1, e2 = 0
if (i > e1) {
if (i <= e2) {
const nextPos = e2 + 1
const anchor = nextPos < l2 ? (c2[nextPos] as VNode).el : parentAnchor
while (i <= e2) {
patch(null, c2[i]) // New node ( Pseudo code )
i++
}
}
}
```

Because of the legend above (i < e1) I can't get to this logic , So we can look directly at the code comments ( The notes are really very detailed ,`patchKeyedChildren`

I keep all the original notes in it ). If the old node is traversed , There are new nodes left at the beginning or at the end , Then add nodes ( By reference ,`patch`

It will be dealt with internally ).

**4、 If the new node has been traversed , The redundant nodes need to be unloaded **

```
// 4.common sequence + unmount
// (a b) c
// (a b)
// i = 2, e1 = 2, e2 = 1
// a (b c)
// (b c)
// i = 0, e1 = 0, e2 = -1
else if (i > e2) {
while (i <= e1) {
unmount(c1[i], parentComponent, parentSuspense, true)
i++
}
}
```

Because of the legend above (i < e2) Still can't get to this logic , So we can continue to look at the original annotation .i > e2 It means that the new node is traversed , If the new node is traversed , There are old nodes left at the beginning or at the end , The node is unloaded `unmount`

.

**5、 The new and old nodes are not traversed **

```
// 5. unknown sequence
// [i ... e1 + 1]: a b [c d e] f g
// [i ... e2 + 1]: a b [e d c h] f g
// i = 2, e1 = 4, e2 = 5
else {
const s1 = i // prev starting index
const s2 = i // next starting index
...
}
```

According to the example in the figure above ,s1 = 2, s2 = 2, Old nodes left C、D、E, The new node is left D、E、I、C It needs to continue diff

**5.1、 Generate map object , Through the key value pair to store the new node key => index**

```
// 5.1 build key:index map for newChildren
// Create an empty map object
const keyToNewIndexMap = new Map()
// There's nothing left patch The new node , That is to say D、E、I、H
for (i = s2; i <= e2; i++) {
const nextChild = (c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i]))
// If the remaining new nodes have key Words , Store it ,key Corresponding index
if (nextChild.key != null) {
keyToNewIndexMap.set(nextChild.key, i)
}
}
```

Finish the above method , obtain `keyToNewIndexMap = {D => 2, E => 3, I => 4, C => 5}`

,`keyToNewIndexMap`

It's mainly for what ~ Please read on

**5.2、 Traverse the remaining old nodes , Comparison of old and new data , Remove old nodes that are not used **

```
// 5.2 loop through old children left to be patched and try to patch
// matching nodes & remove nodes that are no longer present
let j
// The record is about to be patch Number of new nodes passed
let patched = 0
// Get the length of the remaining new nodes to traverse , As shown above toBePatched = 4
const toBePatched = e2 - s2 + 1
// Whether there has been movement
let moved = false
// Used to track whether any nodes are moving
let maxNewIndexSoFar = 0
// works as Map<newIndex, oldIndex>
// Be careful ： Old node oldIndex Offset + 1
// also oldIndex = 0 It's a special value , Represents that the new node has no corresponding old node
// newIndexToOldIndexMap It mainly acts on the longest enhancer sequence
// newIndexToOldIndexMap As you can see from the variable name , It represents the corresponding relationship between new and old nodes
const newIndexToOldIndexMap = new Array(toBePatched)
for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0
// here newIndexToOldIndexMap = [0, 0, 0, 0]
// Traverse the length of the remaining old nodes
for (i = s1; i <= e1; i++) {
const prevChild = c1[i]
if (patched >= toBePatched) {
// patched Larger than the length of the remaining new nodes , Represents that all current new nodes have patch 了 , So the remaining nodes can only be unloaded
unmount(prevChild, parentComponent, parentSuspense, true)
continue
}
let newIndex
if (prevChild.key != null) {
// Of the old nodes key exist , Then through the key Find the corresponding new node index Location subscript
newIndex = keyToNewIndexMap.get(prevChild.key)
} else {
// Old nodes don't have key Words , Then traverse all the new nodes
for (j = s2; j <= e2; j++) {
// newIndexToOldIndexMap[j - s2] If it is equal to 0 Words
// Represents that the current new node has not been modified patch, Because in the following operation
// If you find the location of the old node corresponding to the new node ,newIndexToOldIndexMap[j - s2] Will be equal to the subscript of the old node + 1
if (
newIndexToOldIndexMap[j - s2] === 0 &&
isSameVNodeType(prevChild, c2[j] as VNode)
) {
// The new node has not been found yet , And the old and new nodes are the same , The location of the new node is assigned to newIndex
newIndex = j
break
}
}
}
if (newIndex === undefined) {
// The current old node does not find the corresponding new node , Then unload
unmount(prevChild, parentComponent, parentSuspense, true)
} else {
// Found the corresponding new node , Then the location of the old node is stored in the corresponding new node subscript
newIndexToOldIndexMap[newIndex - s2] = i + 1
// maxNewIndexSoFar If it's not incremental , It means that the position of the new node has moved forward , So you need to move
if (newIndex >= maxNewIndexSoFar) {
maxNewIndexSoFar = newIndex
} else {
moved = true
}
// Update node differences
patch()
// Find a corresponding new node ,+1
patched++
}
}
```

This code is relatively long , But in general, the following things have been done ：

1、 Get the old node subscript corresponding to the new node `newIndexToOldIndexMap`

( Subscript +1, because 0 It means that the new node has no corresponding old node , Create a new node directly ), In our legend `newIndexToOldIndexMap = [4, 5, 0, 3]`

.

2、 In the process of traversal , If the old node finds the corresponding new node , Then patch it , Update node differences , If not, delete the old node

3️、 Judge by whether the subscript order of the new node is increasing , Whether any nodes have moved

**5.3、 Mount the remaining new nodes that are not found , Move the nodes that need to be moved **

```
// 5.3 move and mount
// The longest incremental subsequence is generated only when there are nodes that need to move
const increasingNewIndexSequence = moved
? getSequence(newIndexToOldIndexMap)
: EMPTY_ARR
j = increasingNewIndexSequence.length - 1
// In this case, the increasingNewIndexSequence = [4, 5]
// Start traversing from the back , Will be the last patch The nodes of are used as anchors
for (i = toBePatched - 1; i >= 0; i--) {
const nextIndex = s2 + i
const nextChild = c2[nextIndex] as VNode
const anchor =
nextIndex + 1 < l2 ? (c2[nextIndex + 1] as VNode).el : parentAnchor
// On behalf of the new
if (newIndexToOldIndexMap[i] === 0) {
// mount new
patch( )
} else if (moved) {
// Conditions for movement ： Of the current longest subsequence length Less than 0( There are no stable subsequences ), Or the current node is not in a stable sequence
if (j < 0 || i !== increasingNewIndexSequence[j]) {
move(nextChild, container, anchor, MoveType.REORDER)
} else {
j--
}
}
}
```

Finally, this source code uses an optimization method , Longest ascending subsequence , The general process is ：

1、 adopt `moved`

To determine whether a node has moved , If there is, through `getSequence(newIndexToOldIndexMap)`

Get the longest ascending subsequence , What we got in the picture is `increasingNewIndexSequence = [4, 5]`

2、 Traverse the length of the remaining new nodes , Start traversing from the back , Judge `newIndexToOldIndexMap[i] === 0`

, Whether the current new node has a corresponding old node , If it is equal to 0, No , Directly add .

3、 Otherwise, by `moved`

Judge if there is movement , If there's a movement , If the current longest subsequence length Less than 0, Or the current node is not in a stable sequence , It means that there are no stable subsequences , Each node needs to move , perhaps , The last new node , Not in the subsequence at the end , There's someone else at the end of the subsequence , Now we need to move as well . If you don't meet the conditions for moving , The new node is in the longest ascending subsequence , No need to move , Just wait for other nodes to move .

Come here ,diff The core process of the algorithm is almost understood ~ There is a chance to solve the longest subsequence .

Reference material ：

Source code ： https://github.com/vuejs/vue-...

diff Optimization strategy ： https://neil.fraser.name/writ...

inforno： https://github.com/infernojs/inferno

https://blog.csdn.net/u014125...

https://zhuanlan.zhihu.com/p/...

https://hustyichi.github.io/2...

https://www.cnblogs.com/Windr...