The core of the vue diff algorithm is actually in the vue/SRC/core/vdom/patch. UpdateChildren method in js.

The main process of Diff algorithm:
  1. Reduce the size of two trees by comparing their boundary nodes.
  2. Find the same nodes by key or traversal (same here means reusable nodes, not identical nodes).
  3. Delete and add nodes by comparing the last index value.
The detailed code analysis 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
    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if (isUndef(oldStartVnode)) {
        oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
      } else if (isUndef(oldEndVnode)) {
        oldEndVnode = oldCh[--oldEndIdx]
        // Compare the start node of the new tree with the start node of the old tree.
      } else if (sameVnode(oldStartVnode, newStartVnode)) {
        // If it is the same node. Notice that the same node is not exactly the same node, it's just a comparison.
        // If it is a DOM element, the tag name is the same as the key
        // The index is changed and the boundary is narrowed.
        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
        oldStartVnode = oldCh[++oldStartIdx]
        newStartVnode = newCh[++newStartIdx]
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
        // Compare the end of the new tree with the end of the old tree (boundary node)
        // The change is the same as above
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
        oldEndVnode = oldCh[--oldEndIdx]
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldStartVnode, newEndVnode)) { 
        // Compare the end node of the new tree with the start node of the old tree.
        // This indicates that the order of the elements may have changed, moving the elements, and continuing to change the index to narrow the boundary.
        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)) { 
        // Compare the start node of the new tree with the end node of the old tree.
        // This indicates that the order of the elements may have changed, moving the elements, and continuing to change the index to narrow the boundary.
        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
        canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
        oldEndVnode = oldCh[--oldEndIdx]
        newStartVnode = newCh[++newStartIdx]
      } else {
         // If none of the boundary nodes has reusable nodes, then we need to traverse to find reusable nodes.
         // Find the same element as the key
         // If you can find a node that can be reused by key, perform the pathNode operation. Notice the key here
         // If no node with the same key can be found, findIdxInOld is executed. Walk through the nodes of the old tree to find nodes that can be reused
         // If there are no reusable nodes, perform the create operation.
         // Note that a lot of traversal is done by narrowing the tree boundaries. Reduces the number of nodes we need to traverse.
        if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
        idxInOld = isDef(newStartVnode.key)
          ? oldKeyToIdx[newStartVnode.key]
          : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
        if (isUndef(idxInOld)) { // New element
          createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
        } else {
          vnodeToMove = oldCh[idxInOld]
          if (sameVnode(vnodeToMove, newStartVnode)) {
            patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
            oldCh[idxInOld] = undefined
            canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
          } else {
            // same key but different element. treat as new element
            createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
          }
        }
        newStartVnode = newCh[++newStartIdx]
      }
    }


    // If oldStartIdx > oldEndIdx, there is a new element.
    if (oldStartIdx > oldEndIdx) {
      refElm = isUndef(newCh[newEndIdx + 1])?null : newCh[newEndIdx + 1].elm
      addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
    } else if (newStartIdx > newEndIdx) {
      // If newStartIdx > newEndIdx, there are deleted elements.
      removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
    }
  }
Copy the code

Note that there are two uses of key in the above diff procedure.

  1. insameVnodeMethod to determine if a key is reusable.
  2. The use of keys appears later in the finding reusable DOM. Use keys to quickly locate reusable elements.

Summary of key’s role:

  1. When looking for reusable nodes, the mapping between key and element index is establishedcreateKeyToOldIdx, reduces the traversal time. Otherwise you have to pass it every timefindIdxInOldMethod to traverse to find reusable nodes.
  2. Identifying elements with keys can be avoided to some extent in thefindIdxInOldThe reusability of the nodes sought is not high, resulting in redundant diff.