Demystifying Snabbdom’s VNode and Diff Algorithm: A Deep Dive

Overview

Snabbdom is a lightweight virtual DOM library. It represents UI as a tree of virtual nodes (vnodes) and updates the real DOM by diffing old and new vnode trees.

Key Concepts

Virtual DOM

A vnode is a plain JavaScript object with fields sel, data, children, text, elm, and key. The children array can contain other vnodes, forming a hierarchical tree.

Diff algorithm

The diff algorithm compares two vnode trees, determines the minimal set of DOM operations (insert, move, remove, text update) and applies them via the patch function.

Creating VNodes

The helper h builds a vnode from a selector, optional data object, and optional children or text. It normalises primitive children into vnode objects and adds SVG namespace handling when the selector starts with svg.

export function h(sel, b?, c?): VNode {
  let data: VNodeData = {};
  let children;
  let text;
  if (c !== undefined) {
    if (b !== null) data = b;
    if (Array.isArray(c)) children = c;
    else if (typeof c === 'string' || typeof c === 'number') text = c.toString();
    else if (c && c.sel) children = [c];
  } else if (b !== undefined && b !== null) {
    if (Array.isArray(b)) children = b;
    else if (typeof b === 'string' || typeof b === 'number') text = b.toString();
    else if (b && b.sel) children = [b];
    else data = b;
  }
  if (children) {
    for (let i = 0; i < children.length; ++i) {
      if (typeof children[i] === 'string' || typeof children[i] === 'number') {
        children[i] = vnode(undefined, undefined, undefined, children[i].toString(), undefined);
      }
    }
  }
  if (sel.startsWith('svg') && (sel.length === 3 || sel[3] === '.' || sel[3] === '#')) {
    addNS(data, children, sel);
  }
  return vnode(sel, data, children, text, undefined);
}

The vnode factory simply returns the object:

export function vnode(sel, data, children, text, elm): VNode {
  const key = data === undefined ? undefined : data.key;
  return { sel, data, children, text, elm, key };
}

Patch Process

The init function receives an array of modules (e.g., classModule, propsModule, styleModule, eventListenersModule) and returns a patch function. The returned patch handles two cases:

If the first argument is a real DOM element, it is wrapped in an empty vnode and a new DOM tree is created from the second argument.

If both arguments are vnodes, the algorithm checks sameVnode and either calls patchVnode (when the roots match) or replaces the old subtree.

sameVnode

function sameVnode(v1, v2) {
  return v1.sel === v2.sel && v1.key === v2.key && v1.data?.is === v2.data?.is;
}

patchVnode

Updates the DOM node referenced by oldVnode.elm. If the new vnode has no text, it delegates to updateChildren to reconcile child lists; otherwise it updates the text content directly.

function patchVnode(oldVnode, vnode, insertedQueue) {
  const elm = (vnode.elm = oldVnode.elm)!;
  const oldCh = oldVnode.children as VNode[];
  const ch = vnode.children as VNode[];
  if (oldVnode === vnode) return;
  if (vnode.text === undefined) {
    if (oldCh && ch) {
      if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedQueue);
    } else if (ch) {
      if (oldVnode.text !== undefined) api.setTextContent(elm, '');
      addVnodes(elm, null, ch, 0, ch.length - 1, insertedQueue);
    } else if (oldCh) {
      removeVnodes(elm, oldCh, 0, oldCh.length - 1);
    } else if (oldVnode.text !== undefined) {
      api.setTextContent(elm, '');
    }
  } else if (oldVnode.text !== vnode.text) {
    if (oldCh) removeVnodes(elm, oldCh, 0, oldCh.length - 1);
    api.setTextContent(elm, vnode.text!);
  }
}

updateChildren (double‑ended diff)

The algorithm uses four pointers (oldStartIdx, oldEndIdx, newStartIdx, newEndIdx) to compare the start and end of both child lists. It handles the following cases in order:

Head‑to‑head match → patch and advance both starts.

Tail‑to‑tail match → patch and retreat both ends.

Head of old matches tail of new → patch, move the old node to the end, advance old start and retreat new end.

Tail of old matches head of new → patch, move the old node before the old start, retreat old end and advance new start.

Otherwise, look up the new start vnode’s key in a map of old keys; if not found, insert a new element; if found and selectors differ, insert a new element; if found and selectors match, patch the existing node and move it to the correct position.

When one list is exhausted, any remaining new nodes are appended, and any remaining old nodes are removed.

function updateChildren(parentElm, oldCh, newCh, insertedQueue) {
  let oldStartIdx = 0, newStartIdx = 0;
  let oldEndIdx = oldCh.length - 1, newEndIdx = newCh.length - 1;
  let oldStartVnode = oldCh[0], oldEndVnode = oldCh[oldEndIdx];
  let newStartVnode = newCh[0], newEndVnode = newCh[newEndIdx];
  let oldKeyToIdx;
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    if (oldStartVnode == null) { oldStartVnode = oldCh[++oldStartIdx]; continue; }
    if (oldEndVnode == null) { oldEndVnode = oldCh[--oldEndIdx]; continue; }
    if (newStartVnode == null) { newStartVnode = newCh[++newStartIdx]; continue; }
    if (newEndVnode == null) { newEndVnode = newCh[--newEndIdx]; continue; }

    if (sameVnode(oldStartVnode, newStartVnode)) {
      patchVnode(oldStartVnode, newStartVnode, insertedQueue);
      oldStartVnode = oldCh[++oldStartIdx];
      newStartVnode = newCh[++newStartIdx];
    } else if (sameVnode(oldEndVnode, newEndVnode)) {
      patchVnode(oldEndVnode, newEndVnode, insertedQueue);
      oldEndVnode = oldCh[--oldEndIdx];
      newEndVnode = newCh[--newEndIdx];
    } else if (sameVnode(oldStartVnode, newEndVnode)) {
      patchVnode(oldStartVnode, newEndVnode, insertedQueue);
      api.insertBefore(parentElm, oldStartVnode.elm!, api.nextSibling(oldEndVnode.elm!));
      oldStartVnode = oldCh[++oldStartIdx];
      newEndVnode = newCh[--newEndIdx];
    } else if (sameVnode(oldEndVnode, newStartVnode)) {
      patchVnode(oldEndVnode, newStartVnode, insertedQueue);
      api.insertBefore(parentElm, oldEndVnode.elm!, oldStartVnode.elm!);
      oldEndVnode = oldCh[--oldEndIdx];
      newStartVnode = newCh[++newStartIdx];
    } else {
      if (oldKeyToIdx === undefined) {
        oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
      }
      const idxInOld = oldKeyToIdx[newStartVnode.key as string];
      if (idxInOld === undefined) {
        api.insertBefore(parentElm, createElm(newStartVnode, insertedQueue), oldStartVnode.elm!);
      } else {
        const elmToMove = oldCh[idxInOld];
        if (elmToMove.sel !== newStartVnode.sel) {
          api.insertBefore(parentElm, createElm(newStartVnode, insertedQueue), oldStartVnode.elm!);
        } else {
          patchVnode(elmToMove, newStartVnode, insertedQueue);
          oldCh[idxInOld] = undefined as any;
          api.insertBefore(parentElm, elmToMove.elm!, oldStartVnode.elm!);
        }
      }
      newStartVnode = newCh[++newStartIdx];
    }
  }
  if (oldStartIdx > oldEndIdx) {
    const before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].elm;
    addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx, insertedQueue);
  } else if (newStartIdx > newEndIdx) {
    removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
  }
}

Typical Usage

import { init, classModule, propsModule, styleModule, eventListenersModule, h } from 'snabbdom';

const patch = init([classModule, propsModule, styleModule, eventListenersModule]);

const vnode = h('div#container.two.classes', { on: { click: someFn } }, [
  h('span', { style: { fontWeight: 'bold' } }, 'Bold text'),
  ' plain text',
  h('a', { props: { href: '/foo' } }, 'Link')
]);

const container = document.getElementById('container');
patch(container, vnode);

const newVnode = h('div#container.two.classes', { on: { click: anotherFn } }, [
  h('span', { style: { fontWeight: 'normal', fontStyle: 'italic' } }, 'Italic text'),
  ' plain text',
  h('a', { props: { href: '/bar' } }, 'Link')
]);

patch(vnode, newVnode);

Reference

Snabbdom source repository: https://github.com/snabbdom/snabbdom/tree/master