The Diffing Algorithm

A state change produces a whole new tree. After this lesson your program compares two trees and prints the exact patch list that turns the first into the second, the list a renderer would then apply to the real DOM.

Why compare at all

Writing the new tree over the page would work, and it would destroy everything the browser keeps in the old nodes: a focused input, a text selection, a scroll offset, a half-finished transition. So the framework keeps the previous tree, compares, and touches only what differs. Finding the cheapest edit between two arbitrary trees costs O(n^3), far too slow to run sixty times a second. React gets to O(n) by betting on two heuristics. They are assumptions, not proofs.

Different type means different subtree. A div that became a span is replaced as a whole without looking inside; descending would almost never pay.

Same position means same thing. Child i of the old node is compared with child i of the new one.

What happens at one pair of nodes

For the same tag, each attribute that is new or has a different value (or switched between bare and valued) is a SET; each old attribute that is gone is an UNSET. Children are compared pairwise by index. A new child with no old partner is an INSERT of its HTML; an old child with no new partner is a REMOVE.

A node is addressed by the child indexes leading to it: / is the root, /0 its first child, /2/1 the second child of the third child. Patches are applied in the order printed, and that order matters. Removing child 1 of four makes the old child 2 become child 1, so removals must go last to first, or the second removal would hit the wrong node.

A worked trace

Old <nav><a>Home</a><a>Docs</a></nav>, new <nav><a>Home</a><span>Docs</span><a>Blog</a></nav>.

(root nav, same tag, no attributes)
child 0: a vs a, text Home vs Home      nothing
child 1: a vs span, different tags      REPLACE /1 <span>Docs</span>
child 2: only in new                    INSERT /2 <a>Blog</a>

The patch is REPLACE /1 <span>Docs</span> then INSERT /2 <a>Blog</a>. The inserted HTML is produced by the renderer from lesson 1, so it is escaped and uses the real attribute names.

Where position breaks

Prepend one row to a list of a thousand. Every child now sits one slot later, every pairwise comparison disagrees, and the diff patches a thousand rows and inserts one more. Along with the text, the DOM nodes keep their own state, so a focused field in row three now belongs to the data of row two. The fix is a key, a stable id that says which old child a new child is, so unchanged rows are matched by identity instead of position. That is lesson 8. Vue 3 adds a longest-increasing-subsequence pass to minimise moves; Solid and Svelte avoid the problem by not diffing at all, because their compilers know which expression feeds which node.

Common mistakes

• Descending after a replace. The whole new subtree is already in the patch.
• Removing in ascending order, which makes later removals hit the wrong child.
• Comparing only values. An attribute that went from bare to valued has changed, and a vanished attribute needs its own patch.
• Writing raw text in an insert instead of the escaped HTML, or className instead of class.
• Forgetting that text nodes have paths too.

Your exercise

The starter reads the two trees, provides the renderer from lesson 1, and prints your patch list (or NO CHANGES when it is empty). You write diff. The next stages of the course all start from patch lists like this one.