Vue source code parsing (3)- Diff algorithm optimization strategy

I. Implementation process

Diff algorithm node comparison criterion

The diff algorithm makes a fine comparison between the new virtual DOM and the old virtual DOM and finally re-renders the comparison result to reflect the real DOM

The DIff algorithm performs fine comparison only for the same virtual DOM, otherwise only violent inserts and inserts will be performed

The DIff algorithm will only compare between layers and not across layers

3. Optimization strategy of DIff algorithm

Four Pointers:

OldStartIdx (old front pointer)
NewStartIdx (new front pointer)
OldEndIdx (old after pointer)
NewEndIdx (new post-pointer)

The Map cache

4. Matching search rules for diff algorithm Pointers

4.1 Egress failed to match:

oldStartIdx>oldEndIdx && newStartIdx>newEndIdx
Copy the code

4.2 Matching Search rules

① The new front and the old front ② the new back and the old back ③ the new back and the old front ④ The new front and the old back in order to hit and hit only one if all four are not hit then re-execute the cycle

4.3 Match Details

4.3.1 New and old

Old front -> A A <- new front B B old back -> C M N C <- new backCopy the code

When the new front and the old front hit, the new front and the old front continue to move down

A A B B old before -> old after -> C M <- new before N C <- new afterCopy the code

When the new front pointer and the old back pointer do not match, judge whether the new back pointer and the old back pointer match if the two Pointers move up

A A old back -> B B old front -> C M <- new front N <- new back CCopy the code

The loop ends with oldStartIdx>oldEndIdx, and we find that the elements in the preceding and trailing Pointers are the ones we need to add

New rule: We want to insert the element (M,N) before the old pointer (C).

4.3.2 New and old

Old front -> A C <- new front B D <- new rear C old rear -> DCopy the code

When the old and new front Pointers do not match, judge whether the new and old rear Pointers match, then move the pointer up

Old front -> A C <- new front <- new rear B D old rear -> C DCopy the code

When the old and new front Pointers do not match, judge whether the new and old rear Pointers match, then move the pointer up

<- new - old -> A C <- new - old -> B D C DCopy the code

The newStartIdx>newEndIdx loop ends, and we find that the elements contained in the old before and after Pointers are the elements we need to delete, so we iterate over the pointer to delete those two elements

4.3.3 New and old

Old front -> A C <- new front B B old back -> C A <- new backCopy the code

When the old front doesn’t match the new front and the old back doesn’t match the new back, we try to match the old front and the new back, after the hit we insert the old front into the old back and move the pointer

C <- new old -> B B <- new old -> C A ACopy the code

C <- new <- new after B Old before -> old after -> C A B ACopy the code

Both sides of the old and new hit move pointer end the loop

4.4.4 New before and old after

Old before -> A C <- new before B A old after -> C B <- new afterCopy the code

The current three hits all fail, but with the new before and the old after fourth hit, we insert the old after node before the old before and move the pointer accordingly.

C Old front -> A C Old back -> B A <- new front B <- new backCopy the code

Then the subsequent hits end, and the loop ends on both sides.

4.5 None of the four modes are hit

When all four ways without hitting the need for the operation, in order to optimize the performance of our use of the Map of all the old node index, if the new node is new, we can't find it in the old node corresponding index need to insert the new node, if the new node can be found in the old node corresponding index is to move the node, and needs to be Moves the new front pointer backward to end the loop and remove the excess elements

The old front -> A D <- new front new rear B old rear -> CCopy the code

We can see that in this case none of the four are hit. We need to insert D in front of the old pointer and move the new pointer to end the loop and delete the old pointer to the ABC element covered by the old pointer

Old before -> A B <- new before new after B old after -> CCopy the code

In this case, we need to insert the element in the new node in front of the old node, move the pointer to end the loop, and delete the element ABC covered by the old pointer and the old pointer.

4.6 summarize

The above analysis has been very detailed, we only need to implement the diff algorithm according to the above six cases of code, from the above six cases, we can insert elements in three ways, and delete elements in one way.

5. Write diff according to the above analysis (may differ from the source)

function checkSameVnode(a,b){
  return a.sel == b.sel && a.key == b.key  // Check whether it is the same virtual node
}

export default function updateChildren(parentElm,oldCh,newCh){
  let oldStartIdx = 0 / / the old before
  let newStartIdx = 0 / / new front
  let oldEndIdx = oldCh.length-1 / / after the old
  let newEndIdx = newCh.length-1 / / new after
  let oldStartVnode = oldCh[0] // Old former node
  let oldEndVnode = oldCh[oldEndIdx] // Old back node
  let newStartVnode = newCh[0]  // New front node
  let newEndVnode = newCh[newEndIdx] // New post-node
  let keyMap = null;

  while(oldStartIdx<=oldEndIdx && newStartIdx <= newEndIdx){
    if(oldStartVnode == null || oldStartVnode === undefined){
      oldStartVnode = oldCh[++oldStartIdx]
    }else if(oldEndVnode == null oldEndVnode === undefined){
      oldEndVnode = oldCh[--oldEndIdx]
    }else if(newStartVnode == null newStartVnode === undefined){
      newStartVnode = newCh[++newStartIdx]
    }else if(newEndVnode == null || newEndVnode === undefined){
      newEndVnode = newCh[--newEndIdx]
    }else if(checkSameVnode(oldStartVnode,newStartVnode)){
      // Make a comparison between the old and the new to determine whether to update
      patchVnode(oldStartVnode,newStartVnode)
      oldStartVnode = oldCh[++oldStartIdx]
      newStartVnode = newCh[++newStartIdx]
    }else if(checkSameVnode(oldEndVnode,newEndVnode)){
      // New queen and old queen
      patchVnode(oldEndVnode,newEndVnode)
      oldEndVnode = oldCh[--oldEndIdx]
      newEndVnode = newCh[--newEndIdx]
    }else if(checkSameVnode(oldStartVnode,newEndVnode)){
      // The new and the old
      // Move the new node to the old node
      patchVnode(oldStartVnode,newEndVnode)
      parentElm.insertBefore(oldStartVnode.elm,oldEndVnode.elm.nextSibling)
      oldStartVnode = oldCh[++oldStartIdx]
      newEndVnode = newCh[--newEndIdx]
    }else if(checkSameVnode(newStartVnode,oldEndVnode)){
      // New before and old after
      // The new front node needs to be moved to the front of the old one
      patchVnode(oldEndVnode,newStartVnode)
      parentElm.insertBefore(oldEndVnode.elm,oldStartVnode.elm)
      oldEndVnode = oldCh[--oldEndIdx]
      newStartVnode = newCh[++newStartIdx]
    }else{
      Using the map cache is equivalent to moving the node in a loop
      / / cache
      if(! keyMap){ keyMap = {}for(leti=oldStartIdx; i<=oldEndIdx; i++){const key = oldCh[i].key;
          if(key! =undefined){ keyMap[key] = i; }}}// Find the position of the unmatched item in the old node
      const idxInOld = keyMap[newStartVnode.key]
      if(idxInOld == undefined) {// Is a brand new item that needs to add and delete elements between oldStartIdx and oldEndIdx
        parentElm.insertBefore(createElement(newStartVnode),oldStartVnode.elm)
      }else{
        // Not entirely new items need to be moved and the element matched in oldCh is set to undefined before moving to the old and then also removing elements between oldStartIdx and oldEndIdx
        const elmToMove = oldCh[idxInOld];
        patchVnode(elmToMove,newStartVnode);
        // Keep this setting undefined
        oldCh[idxInOld] = undefined
        // Move to the old before
        parentElm.insertBefore(elmToMove.elm,oldStartVnode.elm)
      }
      newStartVnode = newCh[++newStartIdx]
      
    }
  }
  // After the loop ends
  if(newStartIdx <= newEndIdx){
    / / to be inserted
    // Insert before the unprocessed node
      const before = newCh[newEndIdx+1] = =null ? null : newCh[newEndIdx+1].elm;
    for(leti=newStartIdx; i<=newEndIdx; i++){ parentElm.insertBefore(createElement(newCh[i]),before) } }else if(oldStartIdx<=oldEndIdx){
    / / to be deleted
    for(leti = oldStartIdx; i<=oldEndIdx; i++){if(oldCh[i]){
        parentElm.removeChild(oldCh[i].elm)
      }
    }
  }
}

Copy the code

Vue source code parsing (3)- Diff algorithm optimization strategy

I. Implementation process

Diff algorithm node comparison criterion

The diff algorithm makes a fine comparison between the new virtual DOM and the old virtual DOM and finally re-renders the comparison result to reflect the real DOM

The DIff algorithm performs fine comparison only for the same virtual DOM, otherwise only violent inserts and inserts will be performed

The DIff algorithm will only compare between layers and not across layers

3. Optimization strategy of DIff algorithm

Four Pointers:

OldStartIdx (old front pointer)

NewStartIdx (new front pointer)

OldEndIdx (old after pointer)

NewEndIdx (new post-pointer)