This is the second day of my participation in Gwen Challenge

This paper is a study note about virtual DOM and diff algorithm, aiming to better understand the underlying principle of Vue. It is long, so it is divided into several parts, and this is the end part. Previous content portal: virtual DOM and DiFF Algorithm-01 virtual DOM and DiFF Algorithm-02 Virtual DOM and DiFF Algorithm-03

Continue from the previous chapter, when the new and old nodes have values of children attribute, continue to analyze the last two of the four matching searches:

3. The new and the old



Judge the new front and the old front, not hit; Then judge the new and old, do not hit; Then judge the new and the old before, and find the match, conduct patchVnode processing first, and then move the node, move the node pointing to the old before to the node pointing to the old after, then the old before pointer moves down one bit to change the node pointing to, and the new after pointer moves up one bit to change the node pointing to



At this time, the new queen and the old front hit, so the new queen continues to move up, the old front continues to move down



And so on, eventually breaking out of the while loop

// 3. The new and the old
if (sameVnode(oldStartVnode, newEndVnode)) {
  patchVnode(oldStartVnode, newEndVnode)
  if(newEndVnode) newEndVnode.elm = oldStartVnode? .elm// Move the old forward-pointing node behind the old forward-pointing node
  parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling)
  oldStartVnode = oldCh[++oldStartIdx]
  newEndVnode = newCh[--newEndIdx]
}
Copy the code

Note that insertBefore is used instead of appendChild, because the node that the old post-pointer points to is not necessarily the last parentElm (for example, the node that was moved to the end of the previous operation).

4. New before and old after



The judgment of the new before and the old before, the new after and the old after, the new after and the old before are all lost. Before the new before and the old after are matched, the patchVnode is processed first and then the node is moved to move the node pointing to the old before, and then the pointer pointing to the old before is moved up one bit and the pointer pointing to the new before is moved down one bit



Then the old and the new hit each other

// New before and old after
if (sameVnode(oldEndVnode, newStartVnode)) {
  patchVnode(oldEndVnode, newStartVnode)
  if(newStartVnode) newStartVnode.elm = oldEndVnode? .elm// Move the old node to the front of the old node
  parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm)
  oldEndVnode = oldCh[--oldEndIdx]
  newStartVnode = newCh[++newStartIdx]
}
Copy the code

Four off-hit scenarios

We need to loop through the node in oldvNode. children from the previous pointer to the previous pointer to see if the key is the same as the previous key (not considering sel differences).

// Create a mapping object for the key so that the new node can look for the same key in the old node
const keyMap = {}
for (let i = oldStartIdx; i <= oldEndIdx; i++) {
  const key = oldCh[i].key
  if (key) keyMap[key] = i
}
const idxInOld = keyMap[newStartVnode.key] // Find the new node in the old node
Copy the code

If idxInOld has a value

In this case, the new node has a node with the same key value in the old node. You only need to move the old node. For example, if the initial new h(‘li’, {key: ‘B’}, ‘BBB’) does not satisfy any of the four hits, but there is a node with SEL as Li and key as B in the old node.



After it is found in the old node, save it with the elmToMove variable, and then patchVnode of the old and new node, and then assign the value of undefined (because a node cannot be located at two points in the document at the same time). Finally, we move elmToMove with insertBefore

const elmToMove = oldCh[idxInOld]
patchVnode(elmToMove, newStartVnode)
// The processed node is assigned the value undefined
oldCh[idxInOld] = undefined
parentElm.insertBefore(elmToMove.elm, oldStartVnode.elm)
Copy the code

NewStartVnode = newCh[++newStartIdx] h(‘li’, {key: ‘A’}, ‘AAA’), then the new front and the old front hit, then move down at the same time



When the old front moves to undefined, it skips and moves down one bit, so the while loop starts with a judgment and then matches the four hits

if (oldStartVnode === undefined) { // It may have already been handled
  oldStartVnode = oldCh[++oldStartIdx]
} else if (oldEndVnode === undefined) {
  oldEndVnode = oldCh[--oldEndIdx]
}
Copy the code

The following situation is shown below, and the diagram of the remaining operations is omitted

If idxInOld has no value

Parentelm.insertbefore (creatElement(newStartVnode), oldStartvNode.elm)

Analyze after the while loop

There are only two conditions for a while loop to end:

1. oldStartIdx > oldEndIdx

The old node is processed first, indicating that there are still nodes that the pointer does not point to and process, and new nodes are added, such as the situation in the following figure

2. newStartIdx > newEndIdx

If the new node is processed first, it indicates that the new node is deleted

if (oldStartIdx > oldEndIdx) { // New nodes are added
  // We cannot use the real DOM attribute nextSibling here
  const before = newCh[newEndIdx + 1]? newCh[newEndIdx +1].elm : null
  for (let i = newStartIdx; i <= newEndIdx; i++) {
    parentElm.insertBefore(creatElement(newCh[i]), before)
  }
} else { // The new node was deleted
  for (let i = oldStartIdx; i <= oldEndIdx; i++) {
    parentElm.removeChild(oldCh[i].elm)
  }
}
Copy the code

NewCh [newEndIdx + 1]. Elm, so the first four hits should assign corresponding values to elm of the new node



Extract it into the updateChildren function, as shown below

// updateChildren.js
import patchVnode from './patchVnode.js'
import creatElement from './creatElement.js'

// Check whether the two virtual nodes are the same node
function sameVnode(vnode1, vnode2) {
  return vnode1.sel === vnode2.sel && vnode1.key === vnode2.key
}

export default (parentElm, oldCh, newCh) => {
  let oldStartIdx = 0 // Old pointer
  let oldEndIdx = oldCh.length - 1 // Old after pointer
  let newStartIdx = 0 // new pointer
  let newEndIdx = newCh.length - 1 // new after pointer
  
  let oldStartVnode = oldCh[0] // The virtual node to which the previous pointer points initially
  let oldEndVnode = oldCh[oldEndIdx] // The virtual node to which the old back pointer points initially
  let newStartVnode = newCh[0] // Initialize the virtual node to which the previous pointer points
  let newEndVnode = newCh[newEndIdx] // The virtual node to which the back pointer points at the beginning
  
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx){
    if (oldStartVnode === undefined) { // It may have already been handled
      oldStartVnode = oldCh[++oldStartIdx]
    } else if (oldEndVnode === undefined) {
      oldEndVnode = oldCh[--oldEndIdx]
    } else if (sameVnode(oldStartVnode, newStartVnode)) {
      // 1. New and old
      patchVnode(oldStartVnode, newStartVnode)
      if(newStartVnode) newStartVnode.elm = oldStartVnode? .elm oldStartVnode = oldCh[++oldStartIdx] newStartVnode = newCh[++newStartIdx] }else if (sameVnode(oldEndVnode, newEndVnode)) {
      // 2. New queen and old queen
      patchVnode(oldEndVnode, newEndVnode)
      if(newEndVnode) newEndVnode.elm = oldEndVnode? .elmconsole.log(oldEndVnode.elm, newEndVnode.elm)
      oldEndVnode = oldCh[--oldEndIdx]
      newEndVnode = newCh[--newEndIdx]
    } else if (sameVnode(oldStartVnode, newEndVnode)) {
      // 3. The new and the old
      patchVnode(oldStartVnode, newEndVnode)
      if(newEndVnode) newEndVnode.elm = oldStartVnode? .elm// Move the old forward-pointing node behind the old forward-pointing node
      parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling)
      oldStartVnode = oldCh[++oldStartIdx]
      newEndVnode = newCh[--newEndIdx]
    } else if (sameVnode(oldEndVnode, newStartVnode)) {
      // New before and old after
      patchVnode(oldEndVnode, newStartVnode)
      if(newStartVnode) newStartVnode.elm = oldEndVnode? .elm// Move the old node to the front of the old node
      parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm)
      oldEndVnode = oldCh[--oldEndIdx]
      newStartVnode = newCh[++newStartIdx]
    } else {
      // All four hits failed
      // Create a mapping object for the key so that the new node can look for the same key in the old node
      const keyMap = {}
      for (let i = oldStartIdx; i <= oldEndIdx; i++) {
        constkey = oldCh[i]? .keyif (key) keyMap[key] = i
      }
      const idxInOld = keyMap[newStartVnode.key] // Find the new node in the old node
      if (idxInOld) {
        // If yes, the node exists in the old node. You only need to move the node
        const elmToMove = oldCh[idxInOld]
        patchVnode(elmToMove, newStartVnode)
        // The processed node is assigned the value undefined
        oldCh[idxInOld] = undefined
        parentElm.insertBefore(elmToMove.elm, oldStartVnode.elm)
      } else {
        // If not, it is a new node
        parentElm.insertBefore(creatElement(newStartVnode), oldStartVnode.elm)
      }
      newStartVnode = newCh[++newStartIdx]
    }
  }
  OldStartIdx > oldEndIdx; oldStartIdx > oldEndIdx; NewStartIdx > newEndIdx * The new node is deleted */
  if (oldStartIdx > oldEndIdx) { // New nodes are added
    // We cannot use the real DOM attribute nextSibling here
    const before = newCh[newEndIdx + 1]? newCh[newEndIdx +1].elm : null
    console.log(newCh[newEndIdx + 1],newCh[newEndIdx + 1].elm)
    for (let i = newStartIdx; i <= newEndIdx; i++) {
      parentElm.insertBefore(creatElement(newCh[i]), before)
    }
  } else { // The new node was deleted
    for (let i = oldStartIdx; i <= oldEndIdx; i++) {
      parentElm.removeChild(oldCh[i].elm)
    }
  }
}
Copy the code