Reconciliation

The previous lesson built the matching rule at the list level: a key determines which record corresponds to which node. What happens after matching was left open — how attributes are compared, in what order children are visited, what happens when the type changes.

This lesson gathers all of these rules into a single algorithm. The algorithm is called reconciliation: its input is two view descriptions, its output is the list of operations to apply to the tree.

Reconciliation’s Input and Output

The framework keeps the last view description it produced in memory. This stored description is called the virtual tree: a copy of the document tree’s current state, made of plain data.

When state changes, a new description is produced and the two descriptions are compared. The result of the comparison is a patch list — create a node, remove it, move it, write an attribute, write text. Only this list is applied to the document tree.

This is the reason the virtual tree exists. If the comparison were done on the document tree, every step would read from the tree; reading from the tree can trigger a layout calculation and produces the layout thrashing from the Performance Recording lesson. Comparing over a copy made of plain data eliminates these reads.

Three Assumptions That Make Comparison Cheap

Finding the smallest sequence of transformations between two ordered trees is a job of cubic order in tree size. It is too expensive to do on every frame. Reconciliation reduces this problem to linear with three assumptions.

The subtree of a node whose type changes is not compared. If a section element appears in a position where a list item used to be, the old subtree is discarded entirely and the new one is built from scratch. The assumption’s rationale is that two elements of different types are expected to produce different structures. Its cost is that switching between two different wrappers carrying the same content rebuilds the entire subtree — and the state inside it.

Comparison is done level by level. Whether a node might have moved to a different level is never tried. A row leaving a table and entering a disclosure panel is seen as a removal and a creation, not a move.

Siblings match by key. The previous lesson’s rule is the algorithm’s child-visiting step. Siblings without a key match by position.

The Algorithm

The implementation below applies these three assumptions and produces the patch list.

// reconciliation.mjs — compares two view descriptions and produces a patch list
const element = (name, attrs = {}, children = [], key = null) =>
  ({ name, attrs, children, key });

function view(state) {
  return element("section", { class: "dashboard" }, [
    element("h2", {}, [`North Slope — ${state.measurements.length} measurements`]),
    element("ul", { class: "table" }, state.measurements.map((m) =>
      element("li", { class: m.value >= m.threshold ? "badge exceeded" : "badge" },
        [`${m.name}: ${m.value} ${m.unit}`], m.id))),
  ]);
}

// Longest increasing subsequence of the old ordering: nodes that can stay in place.
function longestIncreasingSubsequence(array) {
  const tails = [], prev = [];
  for (const [i, value] of array.entries()) {
    let lo = 0, hi = tails.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (array[tails[mid]] < value) lo = mid + 1; else hi = mid;
    }
    prev[i] = lo > 0 ? tails[lo - 1] : -1;
    tails[lo] = i;
  }
  const result = new Set();
  for (let i = tails.at(-1); i !== undefined && i !== -1; i = prev[i]) result.add(i);
  return result;
}

function reconcile(old, next, path, patches) {
  if (typeof old === "string" || typeof next === "string") {
    if (old !== next) patches.push(`TEXT     ${path}  ${JSON.stringify(next)}`);
    return;
  }
  // 1. If the type or key differs, the subtree is not compared; it is replaced with the new one.
  if (old.name !== next.name || old.key !== next.key) {
    patches.push(`REPLACE  ${path}  <${old.name}> → <${next.name}>`);
    return;
  }
  // 2. Attributes are compared in both directions.
  for (const [k, v] of Object.entries(next.attrs))
    if (old.attrs[k] !== v) patches.push(`ATTR     ${path}  ${k}=${JSON.stringify(v)}`);
  for (const k of Object.keys(old.attrs))
    if (!(k in next.attrs)) patches.push(`DEL-ATTR ${path}  ${k}`);
  // 3. Children: keyed ones match by key, unkeyed ones match by position.
  const oldIndex = new Map();
  old.children.forEach((c, i) =>
    oldIndex.set(typeof c === "string" || c.key === null ? `#${i}` : c.key, i));
  const matched = [];
  next.children.forEach((c, i) => {
    const key = typeof c === "string" || c.key === null ? `#${i}` : c.key;
    const oldIdx = oldIndex.get(key);
    if (oldIdx === undefined) patches.push(`CREATE   ${path}/${i}  ${key}`);
    else matched.push({ i, oldIdx, key });
  });
  for (const [key, i] of oldIndex)
    if (!matched.some((e) => e.key === key))
      patches.push(`REMOVE   ${path}/${i}  ${key}`);
  const keep = longestIncreasingSubsequence(matched.map((e) => e.oldIdx));
  matched.forEach((e, k) => {
    if (!keep.has(k)) patches.push(`MOVE     ${path}/${e.oldIdx} → ${path}/${e.i}  ${e.key}`);
    reconcile(old.children[e.oldIdx], next.children[e.i], `${path}/${e.i}`, patches);
  });
}

const M = (id, name, value, unit, threshold) => ({ id, name, value, unit, threshold });
const BEFORE = { measurements: [
  M("s1", "Temperature", -4.2, "°C", 30), M("n1", "Relative humidity", 72, "%", 90),
  M("r1", "Wind speed", 11.4, "m/s", 25), M("k1", "Snow depth", 38, "cm", 60),
] };
const AFTER = { measurements: [
  M("k1", "Snow depth", 38, "cm", 60), M("s1", "Temperature", -4.2, "°C", 30),
  M("n1", "Relative humidity", 94, "%", 90), M("b1", "Pressure", 964, "hPa", 1050),
] };

const patches = [];
reconcile(view(BEFORE), view(AFTER), "root", patches);
const countNodes = (description) => typeof description === "string"
  ? 1 : 1 + description.children.reduce((t, c) => t + countNodes(c), 0);
console.log(`nodes in the description: ${countNodes(view(AFTER))}`);
console.log(`patches produced        : ${patches.length}\n`);
console.log(patches.join("\n"));

nodes in the description: 12
patches produced        : 5

CREATE   root/1/3  b1
REMOVE   root/1/2  r1
MOVE     root/1/3 → root/1/0  k1
ATTR     root/1/2  class="badge exceeded"
TEXT     root/1/2/0  "Relative humidity: 94 %"

Four things changed at once: a measurement was added, one was removed, the list was reordered, and one measurement’s value crossed the threshold. Five patches were produced for a twelve-node description.

A single move is enough. Even though the order of all four rows changed, the rows found in the longest increasing subsequence of the old ordering were left in place, and only the snow depth row was moved.

Crossing the threshold produced two separate patches. The relative humidity’s class and text are separate fields; each field goes through its own comparison. This separation is kept because writing an attribute has a different cost than writing text.

The heading produced no patch at all. Because the measurement count stayed at four, the heading’s text did not change; the comparison saw this and wrote no operation. This is the difference between comparing a field and writing it: comparison is cheap, writing is expensive.

The changed measurement itself was never moved. Because removal, creation, and moving are resolved by key, the updated row stayed in its own node even though it changed position in the list. Without a key, this row would have been rewritten too.

Where the Cost Lies

Reconciliation is linear in the size of the produced description. A practical conclusion follows: the way to reduce cost is not to speed up the comparison but to produce a smaller description.

What determines the size of the description is the re-render area measured in the third lesson. When state at the root changes, the entire tree re-renders and the entire description is produced and compared. Keeping state as low as possible, skipping the production of subtrees whose input has not changed, and caching the result of expensive computations are the tools that narrow this area; the last two are covered in later topics of the course.

Approaches That Do Not Compare

Reconciliation resolves the question of “which value affects which node” all over again every time. Solving the same question once and storing the answer is also possible, and this is the fundamental design difference that separates framework families.

// approaches.mjs — the work three approaches do when a single measurement value changes
const N = 12;
const MEASUREMENTS = Array.from({ length: N }, (_, i) => ({
  id: `s${i}`, name: `Sensor ${String(i + 1).padStart(2, "0")}`, value: 10 + i,
}));
const CHANGED = 6, NEW_VALUE = 17.5;
const rowText = (m) => `${m.name}: ${m.value}`;

// --- A) Virtual tree: regenerate the description, compare against the old one ---
let produced = 0, compared = 0, writesA = 0;
const node = (name, children) => { produced++; return { name, children }; };
const text = (s) => { produced++; return s; };
const view = (measurements) =>
  node("ul", measurements.map((m) => node("li", [text(rowText(m))])));

function reconcile(old, next, tree) {
  compared++;
  if (typeof next === "string") {
    if (old !== next) { tree.texts[tree.k] = next; writesA++; }
    tree.k++;
    return;
  }
  old.children.forEach((c, i) => reconcile(c, next.children[i], tree));
}

const treeA = { texts: MEASUREMENTS.map(rowText), k: 0 };
const oldDescription = view(MEASUREMENTS);
produced = 0;                                    // the initial render is not counted
const nextMeasurements = MEASUREMENTS.map((m, i) =>
  i === CHANGED ? { ...m, value: NEW_VALUE } : m);
reconcile(oldDescription, view(nextMeasurements), treeA);

// --- B) Fine-grained reactivity: a binding subscribes to the cell it reads ---
let subscriptionsB = 0, writesB = 0;
const treeB = { texts: MEASUREMENTS.map(rowText) };
const cells = MEASUREMENTS.map((m, i) => {
  const cell = { value: m.value, subscribers: [] };
  cell.subscribers.push((v) => { treeB.texts[i] = `${m.name}: ${v}`; writesB++; });
  subscriptionsB++;                               // one subscription recorded at setup
  return cell;
});
const writeCell = (i, v) => {
  cells[i].value = v;
  for (const subscriber of cells[i].subscribers) subscriber(v);
};
writeCell(CHANGED, NEW_VALUE);

// --- C) Compile-time reactivity: the mapping comes from the compiler ---
// The compiler reads the template: row text depends only on the "value" field.
let writesC = 0;
const treeC = { texts: MEASUREMENTS.map(rowText) };
const COMPILED = {
  value: (i, v) => { treeC.texts[i] = `${MEASUREMENTS[i].name}: ${v}`; writesC++; },
};
COMPILED.value(CHANGED, NEW_VALUE);

// --- Result ------------------------------------------------------------------
const expected = nextMeasurements.map(rowText);
const same = (texts) => JSON.stringify(texts) === JSON.stringify(expected);
console.log(`one measurement value changed in a ${N}-row table\n`);
console.log("approach".padEnd(26) + "setup    produced  compared       writes  result");
console.log(`${"virtual tree".padEnd(26)}${String(0).padEnd(9)}${String(produced).padEnd(8)}` +
  `${String(compared).padEnd(15)}${String(writesA).padEnd(7)}${same(treeA.texts)}`);
console.log(`${"fine-grained reactivity".padEnd(26)}${String(subscriptionsB).padEnd(9)}${String(0).padEnd(8)}` +
  `${String(0).padEnd(15)}${String(writesB).padEnd(7)}${same(treeB.texts)}`);
console.log(`${"compile-time".padEnd(26)}${String(0).padEnd(9)}${String(0).padEnd(8)}` +
  `${String(0).padEnd(15)}${String(writesC).padEnd(7)}${same(treeC.texts)}`);

one measurement value changed in a 12-row table

approach                  setup    produced  compared       writes  result
virtual tree              0        25      25             1      true
fine-grained reactivity   12       0       0              1      true
compile-time              0        0       0              1      true

The three approaches produce the same result; the work they do differs.

The approach that keeps a virtual tree produces and walks the entire description on every update: twenty-five node productions, twenty-five comparisons, one write. In return, it records nothing and places no restriction on the view function — conditionals, loops, helper functions, all of it is ordinary code.

The approach that does fine-grained dependency tracking records at setup which binding reads which value. On update, it produces no description and does no comparison; it runs the relevant binding directly. Its cost is the record kept for every binding and the requirement that reads be trackable: values are accessed not directly, but through a tracked wrapper.

The approach that reactivates at compile time builds the same mapping not at runtime but in the compiler. Which part of the template reads which field is known at compile time; the output is code that writes that field directly. Neither a record is kept nor a comparison is done at runtime. Its cost is that a compilation step becomes mandatory and the template language has to stay restricted enough to remain analyzable: dynamic structures the compiler cannot see fall outside this mapping.

One more trade-off does not show up in the table. In the virtual-tree approach, update cost is proportional to the re-render area; in the other two, it is proportional to the number of changed values. In a small interface, the difference cannot be measured; it becomes clear in a dashboard where fifteen badges update several times a second. This number alone does not determine the choice — the course’s final topic covers the full set of criteria.

Summary

• Reconciliation compares the new view description against the stored previous one and produces a patch list; the stored description is called the virtual tree, and it prevents reads from the document tree.
• Finding the smallest transformation between two ordered trees is of cubic order; three assumptions — discarding the subtree on a type change, comparing level by level, matching siblings by key — reduce the problem to linear.
• The assumptions have a cost: changing a wrapper’s type rebuilds the subtree and its state; a node that changes level is not moved, it is removed and re-created.
• Comparison is cheap, writing is expensive; no patch is produced for fields that do not change.
• Reconciliation’s cost depends on the size of the produced description; the way to reduce it is to produce a smaller description, that is, to narrow the re-render area.
• Fine-grained dependency tracking solves the same problem with a record kept at setup, and the compile-time approach with a mapping built in the compiler; the first requires trackable access, the second a restricted template language and a compilation step.

Next Step

This topic built how the interface is produced from state and how what is produced is reflected onto the tree: the view is a function, the component is a contractual piece of that function, the template binds markup to data, the key preserves identity, reconciliation turns the difference into a patch. One thing remains unresolved: state itself. Reconciliation always runs after a re-render — so what triggers the re-render? When an event handler updates two values back to back, does it render twice, or are the updates batched together? Where exactly does a component’s local state live, and what does the call that updates it return when read on the very next line? The next topic, Component Lifecycle and State, begins with these questions in the Local State lesson.