编程知识 cdmana.com

Vue 3 virtual DOM diff source code reading

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

diff (2).png
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 .
image.png

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 .
image.png

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 .
image.png


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 :
image.png
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 :
image.png

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 .
image.png

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++
    }

1.png

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--
    }

2.png

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...

版权声明
本文为[A kind of Vin]所创,转载请带上原文链接,感谢
https://cdmana.com/2020/12/20201225144248568m.html

Scroll to Top