The core process of the patch algorithm

Core Process of the Patch Algorithm

The patch algorithm is the core mechanism for virtual DOM updates in Vue 3, responsible for comparing differences between old and new virtual nodes and efficiently updating the real DOM. It recursively processes different types of nodes, performing creation, update, or unmount operations.

Virtual Node Type Determination

The patch process first checks whether the types of the old and new nodes are the same:

if (oldVnode === newVnode) {
  return
}

if (
  oldVnode.type !== newVnode.type ||
  oldVnode.key !== newVnode.key
) {
  unmount(oldVnode)
  mount(newVnode)
} else {
  patchElement(oldVnode, newVnode)
}

When the node types differ, the old node is directly unmounted and the new node is mounted. If the types are the same, the process proceeds to fine-grained comparison.

Element Node Patch Process

For element nodes, the patchElement function handles updates to attributes, child nodes, etc.:

function patchElement(oldVnode, newVnode) {
  const el = (newVnode.el = oldVnode.el)
  const oldProps = oldVnode.props || {}
  const newProps = newVnode.props || {}
  
  // Update props
  for (const key in newProps) {
    if (newProps[key] !== oldProps[key]) {
      hostPatchProp(el, key, oldProps[key], newProps[key])
    }
  }
  for (const key in oldProps) {
    if (!(key in newProps)) {
      hostPatchProp(el, key, oldProps[key], null)
    }
  }
  
  // Update child nodes
  patchChildren(
    oldVnode,
    newVnode,
    el,
    oldVnode.children,
    newVnode.children
  )
}

Child Node Diff Algorithm

patchChildren handles child node updates using an efficient double-ended diff algorithm:

function patchChildren(oldVnode, newVnode, container) {
  const c1 = oldVnode.children
  const c2 = newVnode.children
  
  if (typeof c2 === 'string') {
    if (c1 !== c2) {
      hostSetElementText(container, c2)
    }
  } else if (Array.isArray(c2)) {
    if (Array.isArray(c1)) {
      patchKeyedChildren(c1, c2, container)
    } else {
      hostSetElementText(container, '')
      mountChildren(c2, container)
    }
  } else {
    if (Array.isArray(c1)) {
      unmountChildren(c1)
    } else if (typeof c1 === 'string') {
      hostSetElementText(container, '')
    }
  }
}

Keyed Child Node Diff

For child node lists with keys, Vue 3 uses an optimized diff algorithm:

function patchKeyedChildren(c1, c2, container) {
  let i = 0
  let e1 = c1.length - 1
  let e2 = c2.length - 1
  
  // 1. Compare from the head
  while (i <= e1 && i <= e2 && isSameVNode(c1[i], c2[i])) {
    patch(c1[i], c2[i], container)
    i++
  }
  
  // 2. Compare from the tail
  while (i <= e1 && i <= e2 && isSameVNode(c1[e1], c2[e2])) {
    patch(c1[e1], c2[e2], container)
    e1--
    e2--
  }
  
  // 3. Handle new nodes
  if (i > e1 && i <= e2) {
    const nextPos = e2 + 1
    const anchor = nextPos < c2.length ? c2[nextPos].el : null
    while (i <= e2) {
      patch(null, c2[i], container, anchor)
      i++
    }
  } 
  // 4. Handle removed nodes
  else if (i > e2 && i <= e1) {
    while (i <= e1) {
      unmount(c1[i])
      i++
    }
  }
  // 5. Handle unknown sequence
  else {
    const s1 = i
    const s2 = i
    const keyToNewIndexMap = new Map()
    
    for (let i = s2; i <= e2; i++) {
      keyToNewIndexMap.set(c2[i].key, i)
    }
    
    // ... Remaining diff logic
  }
}

Component Node Handling

For component nodes, the patch process triggers the component update lifecycle:

function patchComponent(oldVnode, newVnode) {
  const instance = (newVnode.component = oldVnode.component)
  instance.props = newVnode.props
  instance.update() // Trigger component update
}

Text Node Handling

Text node handling is relatively straightforward, directly comparing text content:

function patchText(oldVnode, newVnode) {
  const el = (newVnode.el = oldVnode.el)
  if (oldVnode.children !== newVnode.children) {
    el.nodeValue = newVnode.children
  }
}

Fragment Node Handling

Fragment nodes require special handling of their child nodes:

function patchFragment(oldVnode, newVnode) {
  if (!oldVnode) {
    mountChildren(newVnode.children, container)
  } else {
    patchChildren(
      oldVnode,
      newVnode,
      container
    )
  }
}

Static Node Optimization

Vue 3 marks static nodes for optimization, skipping unnecessary diff:

function patchStaticNode(oldVnode, newVnode) {
  newVnode.el = oldVnode.el
}

Directive Handling

Directives are updated during the patch process:

function patchDirectives(oldVnode, newVnode) {
  const oldDirectives = oldVnode.dirs
  const newDirectives = newVnode.dirs
  
  if (!oldDirectives && !newDirectives) return
  
  // Directive comparison and update logic
  // ...
}

Lifecycle Hook Triggering

The patch process triggers relevant lifecycle hooks at appropriate times:

function invokeHooks(vnode, hookName) {
  const hooks = vnode[hookName]
  if (hooks) {
    hooks.forEach(hook => hook())
  }
}

Performance Optimization Strategies

Vue 3's patch algorithm includes multiple optimizations:

1. Static hoisting during compilation
2. Proxy-based reactivity system
3. More efficient diff algorithm
4. On-demand component update mechanism
5. Finer-grained dependency tracking

// Example of optimized code generated during compilation
function render() {
  return (_openBlock(), _createBlock("div", null, [
    _createVNode("span", null, "Static node"),
    _createVNode("div", null, _toDisplayString(_ctx.message), 1 /* TEXT */)
  ]))
}