[TOC]

Learning goals

By looking at [Vue2. X](Vue_src_code/vue at Master · csDeng/Vue_src_code (github.com)) source code, learning Vnode and DIff algorithm, to solve the interview problem

The learning process

Environment to prepare

Modify thescriptsThe command

"dev": "rollup -w -c scripts/config.js --sourcemap --environment TARGET:web-full-dev".Copy the code

yarn devPackage (pay attention to installationrollup)

What does a Vnode look like

1. insrc\core\vdom\vnode.jsIn theVNodeOf the classconstructorIn printthisObserve what isVnode, the deleted code is as follows:

export default class VNode {
  constructor (tag? : string, data? : VNodeData, children? :?Array<VNode>, text? : string, elm? : Node, context? : Component, componentOptions? : VNodeComponentOptions, asyncFactory? :Function
  ) {
    console.log('Vnode class'.this)}Copy the code

1. repack

Write the testhtml

<! DOCTYPEhtml>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="Width = device - width, initial - scale = 1.0">
    <title>Document</title>
    <script src='.. /dist/vue.js'></script>
</head>
<body>
    <div id = 'demo'>
        <h1>Virtual dom</h1>
        <p id='p1'>{{foo}}</p>
    </div>

    <script>
        const app = new Vue({
            el:'#demo'.data: {foo:'foo'
            },
            mounted(){
                setTimeout(() = >{
                    this.foo = 'foooooooo'
                },3000)}})</script>
</body>
</html>
Copy the code

1. Open it in your browser and view the result

1. Open one of the nodes to see the concrete structure

1. And you can see thatVnodeIs to put ourhtmlThe tag is converted to ajsObject.
2. VdomJust one after anotherVnodeIn the composition of

Test Vue batch asynchronous update

Environment to prepare

Comment out the previous comments in vNode and repackage to avoid unnecessary interference

testhtml

<! DOCTYPEhtml>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="Width = device - width, initial - scale = 1.0">
    <title>Document</title>
    <script src='.. /dist/vue.js'></script>
</head>
<body>
    <div id = 'demo'>
        <h1>Asynchronous update</h1>
        <p id='p1'>{{foo}}</p>
    </div>

    <script>
        const app = new Vue({
            el:'#demo'.data: {foo:'ready'
            },
            mounted(){
                /* Indicates the code for batch asynchronous update */
                setInterval(() = >{
                    this.foo = Math.random()
                    console.log('1'.this.foo)
                    this.foo = Math.random()
                    console.log('2'.this.foo)
                    this.foo = Math.random()
                    console.log('3'.this.foo)

                    // Async behavior
                    console.log(p1.innerHTML)
                    this.$nextTick(() = >{
                         console.log('$nextTick', p1.innerHTML)
                    })
                },3000)}})</script>
</body>
</html>
Copy the code

Open the browser and observe the result

The Diff algorithm

Source location SRC \core\vdom\patch.js
Diff entry source code

function patchVnode (oldVnode, vnode, insertedVnodeQueue, ownerArray, index, removeOnly) {
    if (oldVnode === vnode) {
      // The new node is the same as the old one
      return
    }

    if (isDef(vnode.elm) && isDef(ownerArray)) {
      // clone reused vnode
      vnode = ownerArray[index] = cloneVNode(vnode)
    }

    const elm = vnode.elm = oldVnode.elm

    if (isTrue(oldVnode.isAsyncPlaceholder)) {
      if (isDef(vnode.asyncFactory.resolved)) {
        hydrate(oldVnode.elm, vnode, insertedVnodeQueue)
      } else {
        vnode.isAsyncPlaceholder = true
      }
      return
    }

    // reuse element for static trees.
    // note we only do this if the vnode is cloned -
    // if the new node is not cloned it means the render functions have been
    // reset by the hot-reload-api and we need to do a proper re-render.
    if (isTrue(vnode.isStatic) &&
      isTrue(oldVnode.isStatic) &&
      vnode.key === oldVnode.key &&
      (isTrue(vnode.isCloned) || isTrue(vnode.isOnce))
    ) {
      vnode.componentInstance = oldVnode.componentInstance
      return
    }

    /** * Performs some component hooks */
    let i
    const data = vnode.data
    if (isDef(data) && isDef(i = data.hook) && isDef(i = i.prepatch)) {
      i(oldVnode, vnode)
    }

    // See if the old and new nodes have child queues
    const oldCh = oldVnode.children
    const ch = vnode.children

    // Attribute update
    if (isDef(data) && isPatchable(vnode)) {
      for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode)
      if (isDef(i = data.hook) && isDef(i = i.update)) i(oldVnode, vnode)
    }

    // If there is no text, it is Element
    if (isUndef(vnode.text)) {

      // Both have children
      if (isDef(oldCh) && isDef(ch)) {
        if(oldCh ! == ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly) }else if (isDef(ch)) {
        // Only new nodes have children
        if(process.env.NODE_ENV ! = ='production') {
          checkDuplicateKeys(ch)
        }
        // Clear the text of the old node
        if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, ' ')

        // Add children
        addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
      } else if (isDef(oldCh)) {
        // Only old nodes have children
        removeVnodes(oldCh, 0, oldCh.length - 1)}else if (isDef(oldVnode.text)) {
        // The old node has text
        nodeOps.setTextContent(elm, ' ')}}else if(oldVnode.text ! == vnode.text) {// Both old and new are texts, and are not the same
      nodeOps.setTextContent(elm, vnode.text)
    }
    if (isDef(data)) {
      if (isDef(i = data.hook) && isDef(i = i.postpatch)) i(oldVnode, vnode)
    }
  }

Copy the code

To summarize

Comparing two VNodes involves three operations: attribute update, text update, and child node update

Specific rules:

If both the old and new nodes have children, perform the diff operation on the children and call updateChildren

If the old node has no children and the new node has children, clear the text content of the old node and add children to it

When a new node has no children and an old node has children, all children of the node are removed

When both old and new nodes have no children, it is just text substitution

updateChildren, the specific details of diff, the source code is as follows:

function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
    let oldStartIdx = 0
    let newStartIdx = 0

    let oldEndIdx = oldCh.length - 1
    let oldStartVnode = oldCh[0]
    let oldEndVnode = oldCh[oldEndIdx]

    let newEndIdx = newCh.length - 1
    let newStartVnode = newCh[0]
    let newEndVnode = newCh[newEndIdx]
    let oldKeyToIdx, idxInOld, vnodeToMove, refElm

    // removeOnly is a special flag used only by <transition-group>
    // to ensure removed elements stay in correct relative positions
    // during leaving transitions
    constcanMove = ! removeOnlyif(process.env.NODE_ENV ! = ='production') {
      checkDuplicateKeys(newCh)
    }

    /** * move the sides closer to the center, DFS */
    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if (isUndef(oldStartVnode)) {
        // The old start node is moved to the end of the queue
        oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left

      } else if (isUndef(oldEndVnode)) {
        // The old tail node is moved to the head of the queue
        oldEndVnode = oldCh[--oldEndIdx]

      } else if (sameVnode(oldStartVnode, newStartVnode)) {
        // The old and new start nodes are the same, with +1
        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
        oldStartVnode = oldCh[++oldStartIdx]
        newStartVnode = newCh[++newStartIdx]

      } else if (sameVnode(oldEndVnode, newEndVnode)) {
        // The old and new end nodes are the same, and -1
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
        oldEndVnode = oldCh[--oldEndIdx]
        newEndVnode = newCh[--newEndIdx]

      } else if (sameVnode(oldStartVnode, newEndVnode)) {
        // The old tail node is the same as the new head node, move the old head node to the old tail, increase the same degree
        // Vnode moved right
        patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
        canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
        oldStartVnode = oldCh[++oldStartIdx]
        newEndVnode = newCh[--newEndIdx]

      } else if (sameVnode(oldEndVnode, newStartVnode)) { 
        // The old tail is the same as the new head
        // Vnode moved left
        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
        canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
        oldEndVnode = oldCh[--oldEndIdx]
        newStartVnode = newCh[++newStartIdx]

      } else {
        // If you can't find the same for all four guesses, you are forced to loop

        if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
        
        // Find the index key in the old array
        idxInOld = isDef(newStartVnode.key)
          ? oldKeyToIdx[newStartVnode.key]
          : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)

        // If the element does not exist in the old child node array, create a new one
        if (isUndef(idxInOld)) { // New element
          createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
        } else {

          // If an element is found that can be reused, a further comparison is made
          vnodeToMove = oldCh[idxInOld]
          if (sameVnode(vnodeToMove, newStartVnode)) {
            // Is exactly the same element
            patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
            oldCh[idxInOld] = undefined
            canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
          } else {
            // Only the key is the same, but the content is different
            // same key but different element. treat as new element
            createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
          }
        }
        newStartVnode = newCh[++newStartIdx]
      }
    }

    // Wrap things up
    if (oldStartIdx > oldEndIdx) {
      refElm = isUndef(newCh[newEndIdx + 1])?null : newCh[newEndIdx + 1].elm

      // Batch create
      addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
    } else if (newStartIdx > newEndIdx) {

      // Batch delete
      removeVnodes(oldCh, oldStartIdx, oldEndIdx)
    }
  }

Copy the code

addVnodesAdd nodes in batches

  function addVnodes (parentElm, refElm, vnodes, startIdx, endIdx, insertedVnodeQueue) {
    for (; startIdx <= endIdx; ++startIdx) {
      // Batch create
      createElm(vnodes[startIdx], insertedVnodeQueue, parentElm, refElm, false, vnodes, startIdx)
    }
  }
Copy the code

removeVnodesDelete obsolete nodes in batches

  function removeVnodes (vnodes, startIdx, endIdx) {
    for (; startIdx <= endIdx; ++startIdx) {
      const ch = vnodes[startIdx]
      if (isDef(ch)) {
        if (isDef(ch.tag)) {
          removeAndInvokeRemoveHook(ch)
          invokeDestroyHook(ch)
        } else { // Text node
          removeNode(ch.elm)
        }
      }
    }
  }

Copy the code

Compare two nodes to see if they are exactly the same source

function sameVnode (a, b) {
  return (
    a.key === b.key &&
    a.asyncFactory === b.asyncFactory && (
      (
        a.tag === b.tag &&
        a.isComment === b.isComment &&
        isDef(a.data) === isDef(b.data) &&
        sameInputType(a, b)
      ) || (
        isTrue(a.isAsyncPlaceholder) &&
        isUndef(b.asyncFactory.error)
      )
    )
  )
}

Copy the code

Study summary (summarize from an interview question)

What do you think of the Diff algorithm in Vue

The necessity,lifecycle.jsThe inside of themountComponent

There are many keys used in data within the component

Implement waypatch.jsThe inside of thepatchVnode

Diff is implemented in updateChildren() in patch.js, which performs a comparison between two ends

Recursively search whether the same virtual node is the old and new head, tail, old head and new tail, and new head and old tail. If no search is found, traverse and compare, so as to realize the end to the middle, and finally batch update and delete VNodes, so as to achieve performance optimization.

The overall strategy

Depth first, same layer comparison

The answer

diffAlgorithms are mostly virtual through old and newdomThe comparison will change the place update in the realdomon
vue2In order to reduceWatcherGranularity, one per componentWatcherCorresponding to that, introducediffYou can pinpoint where the changes are happening
Vue2In thediffThe time of execution is when the component instance executes its update function, which compares the results of the previous renderingoldVnodeWith new render resultsnewVnodeThis process was described by You Da Chengpatch
diffImplementation details followDepth first, same layer comparisonAccording to whether they have text or children, the two old and new nodes conduct head, tail, old head and new tail, new head and old tail respectively, and compare the four guesses, trying to find the same node, and then recursive search to achieve the convergence of the two ends to the middle, and finally batch update the inconsistent parts in the middle. It also searches the oldVnode queue to see if there are any nodes that can be reused. If no identical nodes are found, a normal traversal is performed.
And finally, when diff did the comparison, he used itkey, inconsistent key results in inconsistent judgment, thus speeding up the efficiency of comparison.
Do not know what I say have unreasonable place, please give advice. (Guest star)

reference

How to understand the DIff algorithm in VUE _ If I am young and have no inferiority -CSDN blog

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Read the diff algorithm source code of Vue2

Learning goals

The learning process

Environment to prepare

What does a Vnode look like

Test Vue batch asynchronous update

The Diff algorithm

Study summary (summarize from an interview question)

What do you think of the Diff algorithm in Vue

The answer

reference

Read the diff algorithm source code of Vue2

Learning goals

The learning process

Environment to prepare

What does a Vnode look like

Test Vue batch asynchronous update

The Diff algorithm

Study summary (summarize from an interview question)

What do you think of the Diff algorithm in Vue

The answer

reference

Related Posts

Finger offer – Duplicate number in array

Using the Web to achieve a simple audio editor

Graph traversal of front-end data structures and algorithms