The cause of

Why I want to write this article in Vue3.0 has been out for so long, because I am still reading the source code of vue2.x, and I feel it. As a fresh graduate, I suddenly had a little understanding of the overall design and architecture of Vue framework, so I suddenly wrote down the DIff algorithm without any head or tail. In my opinion, the core content of Vue is divided into the following sections:

  1. Generate the render function (runtime version does not have this function)
  2. Generate VNode
  3. Render the VNode as a real DOM
  4. Monitor data changes
  5. Generate a new VNode
  6. Compare the new VNode with the new VNode and update the page

Generally divided into the above points (may be I haven’t read the complete code, there are omissions in the hope that the big guy is generous). In fact, you can pick the point of interest to view the source code and learn. At present, I have also read most of the source code and made a record of the sixth point, namely the patch process.

The preparatory work

Let’s use vue-cli to pull down the 2.x template and simply write the following code:

// main.js
new Vue({
  el: '#app',
  data() {
    return {
      list: [1.2.3.4]
    }
  },
  render(h) {
    return h(
      'ul',
      {
        class: 'c-ul'
      },
      this.list.map(_= > h('li', { key: _ }, _))
    )
  },
  mounted() {
    this.list = [2.5.3.6.7.1]}})Copy the code

The reason for writing render functions manually is that you don’t want to design them into the compiler. Render gives developers the ability to write VNode directly. The demo above starts with a list of pages rendered in the order [1, 2, 3, 4] and records oldVNode. When the list changes during the Mounted lifecycle, newVNode is regenerated and the new and old Vnodes are patched. This article will focus on this operation.

VNode

You can run the demo project and put a breakpoint in the console to see what the VNode data structure looks like, and I’m just going to show you that.

// oldVNode
let oldVNode = {
  tag: 'ul'.data: {
    class: 'c-ul'
  },
  children: [{tag: 'li'.data: {
        key: 1
      },
      children: [{tag: undefined.text: 1}]}, {tag: 'li'.data: {
        key: 2
      },
      children: [{tag: undefined.text: 2}},// VNodes with tag li are children]}Copy the code

In the mounted lifecycle, the same operation will generate a VNode, with the same structure, but newvNode.children.

let oldVNode = {
  tag: 'ul'.data: {
    class: 'c-ul'
  },
  children: [{tag: 'li'.data: {
        key: 2
      },
      children: [{tag: undefined.text: 2}]}, {tag: 'li'.data: {
        key: 5
      },
      children: [{tag: undefined.text: 5}},// VNodes with tag li are children]}Copy the code

So with these two VNode objects, we can compare them. Note that each VNode object in oldVNode has a reference to the real DOM node, such as oldvnode.elm

patchVNode

In fact, before entering patchVNode, Vue will call sameVNode method on two Vnodes to judge whether it is necessary to patch. The logic of sameVNode is simply the same key, the same tag, whether (not) the same annotation node, whether (not) the data object is defined at the same time, and the judgment of the input. The example we refer to here obviously returns true, the specific sameVNode logic reader can see for himself.

// patchVNode()
function patchVnode (oldVNode, newVNode, insertedVnodeQueue, ownerArray, index, removeOnly)  {
    const elm = newVNode.elm = oldVNode.elm
    / / to omit
    if (isUndef(newVNode.text)) {
        if (isDef(newVNode.children) && isDef(oldVNode.children)) { // If both new and old Vnodes have children
            updateChildren(elm, oldVNode.children, newVNode.children) / / the children
        } else if (isDef(newVNode.children)) { // If newVnode has children and oldVNode does not
            // Add a node
            if (isDef(oldVNode.text)) { // If oldVNode has text, the child node is originally text, and the text needs to be cleared
                setTextContent(elm, ' ')
            }
            addVNodes() // Add newVNode Children to the DOM element
        } else if (isDef(oldVNode.children)) { // If oldVNode has children and newVNode does not
            removeVNodes()// Delete the original Children}}else if(oldVNode.text ! == newVNode.text) { setTextContent(elm, newVNode.text) } }Copy the code

Elm = oldvNode. elm = newvNode. elm = oldvNode. elm = newvnode. elm = oldvNode. elm = sameVNode = sameVNode = sameVNode = sameVNode = sameVNode = sameVNode = sameVNode = sameVNode They are vNodes with the same tag (ul), so we can reuse oldvNode.elm directly from newvNode.elm.

Then judge whether newvNode.text exists, if it exists, it indicates that the child node only has text content, and if the text content of oldVNode (which may be empty or non-empty) is not oldvNode.text, then directly replace textContent to complete the patch process.

The other branch is to judge the children of newVNode and oldVNode, where if one side has children (that is, one has children and the other does not), then either delete the node or add the node. And if you have both children, you need updateChildren.

updateChildren

This part is diff’s real process. Because this involves comparing two VNode arrays. Let’s consider the following question before looking at diff’s algorithm:

The purpose of updateChildren is to render the VNode in the newChildren array as dom elements, and then replace the ORIGINAL DOM elements that have been rendered according to the VNode in the oldChildren array. What is the easiest way to do this?

No doubt the simplest method would be to delete it and then add:

function updateChildren(parentElm, oldCh, newCh) {
    // Delete all the original elements
    for (let i = 0, l = oldCh.length; i < l; i++) {
        parentElm.removeChild(oldCh[i].elm)
    }
    // Render the new VNode as a DOM and add it to the document flow
    for (let i = 0, l = newCh.length; i < l; i++) {
        parentElm.append(createElm(newCh[i]))
    }
}
Copy the code

The reason why you need to use VDOM is that it is a performance cost to operate on DOM nodes frequently. If you just delete and replace them, you don’t need to use VNode at all. Instead, you can use any other data structure that records tags and children. So we can’t update hildren using the above method, because there will be reusable elements.

What is a reusable element: two VNodes that can be determined by sameVNode are reusable. For the record, sameVNode only looks at the VNode itself and not its children. If the two Vnodes pass sameVNode, the tag and key of the two vnodes are the same, so there is a large probability that they can be reused directly or simply patch vnodes. How to compare two arrays and find reusable elements is the purpose of the Diff algorithm.

So how do you implement the Diff algorithm? Vue uses a double-ended DIFF.

The above dom represents the actual rendered DOM node, oldCh represents the original vNode array, and newCh represents the core VNode array.

Double-ended means that oldCh and newCh are compared from both ends of the array

function updateChildren(parentElm, oldCh, newCh) {
    let oldStartIdx = 0
    let oldEndIdx = oldCh.length - 1
    let newStartIdx = 0
    let newEndIdx = newCh.length - 1
    let oldStartEl = oldCh[oldStartIdx]
    let oldEndEl = oldCh[oldEndIdx]
    let newStartEl = newCh[newStartIdx]
    let newStartEl = newCh[newEndIdx]
    
    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdex) {
        if (isUndef(oldStartEl)) {
            oldStartIdx++  
        } else if (isUndef(oldEndEl)) {
            oldEndIdx--
        } else if (sameVNode(oldStartEl, newStartEl)) {
            // If the two start elements are the same, then only patchNode is required
            patchVNode(oldStartEl, newStartEl)
            oldStartIdx++
            newStartIdx++
        } else if (sameVNode(oldEndEl, newEndEl)) {
            // If the tail elements are the same, the same as above
            patchVNode(oldEndEl, newEndEl)
            oldEndIdx--
            startEndIdx--
        } else if (sameVNode(newStartEl, oldEndEl)) {
            // If the old tail element is the same as the new head element, move the node before performing patchNode
            // We need to move the real DOM element oldEndEl points to before the element oldStartEl currently points to
            parentElm.insertBefore(oldEndEl.elm, oldStartEl.elm)
            patchVNode(oldEndEl, newStartEl)
            newStartIdx++
            oldEndIdx--
        } else if (sameVNode(newEndEl, oldStartEl)) {
            // If the old head element is the same as the new tail element, it is the same as above, but the direction of moving the element is changed to move back the element oldStartEl points to
            parentElm.insertBefore(oldStartEl.elm, oldEndEl.elm.nextSibling)
        } else {
            // If the end of the comparison of the two ends of the four elements does not match, it does not mean that the new start node is not found at all. For example, if el-2's key is 2, it should be found in oldCh, and then sameVNode will determine
            let vnodeToMove = oldCh.findIndex(vnode= > vnode.key === newStartEl.key)
            if (vnodeToMove >= 0) {
                // If a node with the same key is found
                if (sameVNode(vnodeToMove, newStartEl)) {
                    // Can reuse, move elements
                    patchVNode(vnodeToMove, newStartEl)
                    parentElm.insertBefore(oldCh[vnodeToMove].elm, oldStartEl.elm)
                    oldCh[vnodeToMove] = undefined
                } else {
                    // Create a new DOM element
                    createElm(newStartEl, parentElm, oldStartEL.elm, newCh, vnodeToMove) // render VNode with vnodeToMove as a real DOM and insert it before parentElm's oldstartel.elm}}else {
                // If no identical key is found, create a new key as if sameVNode had found a key but failed to detect it
                createElm(newStartEl, parentElm, oldStartEL.elm, newCh, vnodeToMove)
            }
        }
    }
    // If oldCh does not complete the traversal
    if (newStartIdx > newEndIdx) {
        // Delete the old node
        removeVNodes(oldCh, oldStartIdx, oldEndIdx)
    }
    // If newCh has not finished traversing
    if (oldStartIdx > oldEndIdx) {
        // Add a new node
        addVNodes(newCh, newStartIdx, newEndIdx)
    }
}
Copy the code

Afterword.

The above code is mainly for my own purposes, most of which are the same as the source code, but the operations such as insertBefore and so on. Since Vue is made up of WEEX platform and Web platform, the design mode adopted by Vue is to inject these operations, and I changed them to the operations of web platform by myself.