preface

This article is a supplement to the previous one, with some omissions and other contents analyzed and supplemented.

Fargment Type comparison

The document fragment is a bunch of elements that have no parent node. Updates are executed as part of the processFragment function (run-time core/ SRC /renderer.ts).

Stable fragment does not need to compare the order of child nodes, but it may have dynmiacChildren, which needs to be compared. For the specific process of patchBlockChildren, please refer to my last article. After the comparison is done,

However, if there is a key on the stable fragment, it is a

Keyed/non-keyed fragments are generated after v-for compilation, so each of their subitems is a block, and they must not have dynamicChildren. The specific process of executing patchChildren was analyzed in the previous article.

Why notindexAs akey

To be clear, the VUE version here is VUE 3.2.

Node inversion case

Suppose we have the following code:

const {createApp, reactive, defineComponent} = Vue

const Comp = defineComponent({
    template: ` 
  • {{num}}
    •  `    .props: ['num']})const App = defineComponent({
    template: ` 
      
       
        
      
      `    .setup() {
        let list = reactive([1.2.3.4.5.6])

        function changeList() {
            list = list.reverse()
        }

        return {
            list,
            changeList
        }
    },
    components: {
        Item
    }
  })

  const app = createApp(App)
  app.mount('#app')
Copy the code

    This is a simple list rendering, using the Comp component to render each item in the list and pass num as props, so let’s look at using index as the key to track how it updates.

    We only need to care about the update of the Item list component. In the initial rendering, the vDOM list oldChildren is roughly represented as follows:

    [{type: {/ * * / components configuration}, key: 1, props: {key: 0, num: 1}}, {type: {/ * * / components configuration}, key: 1, props: {key: 1, num: 2}}, {type: {/ * * / components configuration}, key: 2, props: {key: 2, num: 3}},...]Copy the code

    When the button is clicked, the changeList function is triggered, which inverts the array. The new vDOM list newChildren will look something like this:

    [{type: {/ * * / components configuration}, key: 0, props: {key: 0, num: 5}}, {type: {/ * * / components configuration}, key: 1, props: {key: 1, num: 4}}, {type: {/ * * / components configuration}, key: 2, props: {key: 2, num: 3}},...Copy the code

    At this point, it can be found that although the value of key has not changed, the value of num passed is completely different. Under normal circumstances, the first new node can completely reuse the old last node.

    However, in the method of isSameeVNodeType in VUE to judge whether two nodes are the same or not, the most important thing is to judge the comparison of key values, while in patchKeyedChildren, it is the comparison of the old first node and the new first node. In the above example, the comparison of the old and new nodes. Because the key is the same, it is considered to be the same node, but it is actually the wrong node, which may or may not be updated at all

    However, if we use a unique value (instead of item), after the inversion, the new vDOM list newChildren will be expressed as follows:

    [{type: {/ * * / components configuration}, key: 5, props: {key: 5, num: 5}}, {type: {/ * * / components configuration}, key: 4, props: {key: 4, num: 4}}, {type: {/ * * / components configuration}, key: 3, props: {key: 3, num: 3}},...Copy the code

    In this case, patchKeyedChildren will go directly to process 5 and only copy the properties and move nodes.

    Longest increasing subsequence

    In process 5 of patchKeyedChildren, an algorithm is used: “Longest increasing subsequence”, which is the result of calculating the longest increasing subsequence rather than the length of the longest increasing subsequence. Renderer.ts (run-time core/ SRC /renderer.ts),

    Suppose we now have an array of [7, 8, 3, 4, 5, 9, 9, 9, 9, 9] and analyze the flow with this use case.

    The method name is getSequence, which takes an array, and finally evaluates the index of the value in the longest increasing subsequence in the original array. It starts with a copy of the original array and assigns a value to P, which is used for mapping. Result is used to store the result index. The variables I, j, u, etc., are not used in the first part, but will be used later.

    If arrI is larger than arr[j], arrI is larger than arr[j]. If arrI is larger than arr[j], arrI is larger than arr[j]. If arrI is larger than arr[j], arrI is larger than arr[j]. The index of the current item is pushed into result and the mapping is added to p. You can skip the layer loop and process the next item (PS: array P keeps track of the number of items that precede each item in the longest increasing subsequence).

    In the use case, the first two items pass, result becomes [0, 1], and the following limits fail, and the flow follows.

    If it is not greater than, then you need to continue down, using binary search, where u is the first position of result and v is the last position of result. The binary search here uses bitwise operation, that is, C = (u + V) >> 1, and obtains the middle position C of result. The binary search is to find the value in result that has the smallest difference between the value of arR corresponding to the value in the current increasing subsequence and the current comparison item (not necessarily in order). If arr[result[u]] is greater than this value, result[u] will be modified as the index of the current item, and the mapping of P will be modified if u is greater than 0. If u is 0, this item is the first sub-sequence, so the previous one is not needed to be mapped.

    In use, the third, fourth and fifth terms are all larger than the last term of result, so we can only find the smallest difference between them through binary search and replace them in result. The third term is the first term without mapping, and the fourth term is not the first term without mapping. Result becomes [2, 3, 4], and the fifth item is larger than the last one in the current subsequence, pushed directly into result and indexed in P.

    The remaining items are the same as the last item of result, but are not added to the subsequence if the desired location is not found after binary search.

    After the previous process, the prototype of the longest increasing subsequence is generated, but it may not be correct, we need to work backwards to get the correct longest increasing subsequence, combined with the mapping in P, can be obtained one by one.

    In this case, the value of p is [7, 0, 3, 2, 3, 4, 9, 9, 9, 9, 9, 9, 9, 9, 9]. Result is not needed here, and will be reassigned later. In the use case, v is the last item of result, which is the largest item in the longest increasing subsequence, and u is the length of result. V is 5, entering the loop u–, u becomes 3, v is assigned to result[3], and p[5] is assigned to v, and so on, [2, 3, 4, 5] is the longest increasing subsequence.

    conclusion

    This article complements the diff algorithm in the previous article. Added Fragment comparisons and updates. By the way, the reason why not to use index key is that the key is the basis for judging whether the node is the same or not in comparison. Using index key may lead to finding the wrong same node because the key is the same, which will lead to complete update or no update at all. The longest increasing subsequence algorithm in VUE is also analyzed.

    Well, to the end of the article, or I hope you brothers and sisters can guide guidance. Any mistakes or omissions are welcome in the comments section. Thank you.