How Fre's diff() Algorithm Handles Keyed Reconciliation in the Virtual DOM

Fre's diff() function in src/reconcile.ts implements an O(N) keyed reconciliation strategy that uses double-ended pointers and a key-index map to generate minimal DOM mutation actions—insert, move, update, and remove—between two fiber child lists.

Fre is a lightweight React-like library that achieves high performance through an optimized virtual DOM reconciliation engine. At the heart of this system lies the diff() algorithm, which efficiently computes the difference between previous and new component trees while preserving component state through stable keys. This deep dive examines the implementation from lines 40-108 of src/reconcile.ts to reveal how Fre minimizes expensive DOM operations.

Algorithm Structure and Initialization

The diff() function accepts two arrays of fiber nodes: aCh (previous children) and bCh (new children). It returns an ordered list of Action objects that instruct the commit phase how to transform the DOM.

Double-Ended Pointer Strategy

Fre employs a classic optimization using four index pointers to narrow down the differential region before performing heavy key comparisons:

• aHead and aTail track the unconsumed boundaries of the old list
• bHead and bTail track the unconsumed boundaries of the new list

// From src/reconcile.ts#L40-L44
let aHead = 0, bHead = 0, aTail = aCh.length - 1, bTail = bCh.length - 1;

The algorithm first synchronizes from the right (tail) using a while loop that checks if the tail nodes of both lists are identical via the same() function. When matched, it clones the old fiber onto the new one (reusing the DOM node) and records an UPDATE action. Both aTail and bTail decrement inward until a mismatch occurs【L49-L55】.

Next, it performs the same optimization from the left (head), incrementing aHead and bHead while nodes match【L57-L63】. These fast-path checks handle common patterns like appending to the end of a list or prepending to the beginning without requiring key map construction.

Key Index Map Construction

After the fast-path synchronization, Fre builds a lookup table for the remaining new children that possess keys:

// From src/reconcile.ts#L65-L67
for (let i = bHead; i <= bTail; i++) {
  if (bCh[i].key) bMap[bCh[i].key] = i;
}

This bMap object enables O(1) retrieval of a new child's index by its key, transforming the reconciliation from an O(N²) search into an O(N) operation for keyed lists. Elements without keys fall back to positional comparison during the core loop.

Core Reconciliation Loop and Operations

The main reconciliation logic resides in a while loop that processes the unmatched middle region between aHead…aTail and bHead…bTail【L69-L101】. During each iteration, the algorithm determines whether to remove, insert, move, or update a fiber based on key presence and position.

REMOVE Operations

When the current old element aElm has no corresponding key in bMap (foundB == null), the algorithm immediately schedules a removal:

// From src/reconcile.ts#L87-L90
removeElement(aElm);
aHead++;

This occurs when a keyed element is deleted from the list or when an unkeyed element no longer aligns positionally with any new child.

INSERT and MOVE Handling

The algorithm distinguishes between insertion (creating a new DOM node) and moving (repositioning an existing node) using the key map:

• INSERT: Triggered when the old list is exhausted (aTail + 1 <= aHead) or when foundB exists ahead of the current bHead. The action includes a reference node for proper insertion placement【L76-L79】【L91-L94】.

• MOVE: Occurs when foundB exists behind the current bHead (foundB < bHead). The element is already rendered elsewhere in the tree, so Fre clones the old fiber to preserve its DOM node and records a MOVE action to reposition it before the current aHead reference【L95-L99】.

UPDATE Actions

When the same() function confirms that old and new elements are identical (either by key match or by reference), Fre clones the old fiber onto the new one to preserve the underlying DOM node and component state. An UPDATE action is pushed to the queue, and both aHead and bHead advance【L78-L84】.

Action Pipeline and Commit Integration

After the core loop completes, Fre appends any updates collected from the initial right-side synchronization. These are stored temporarily in a temp array and reversed before concatenation to ensure proper execution order【L104-L106】:

for (let i = temp.length - 1; i >= 0; i--) {
  actions.push(temp[i]);
}
return actions; // L107-L108

The returned actions array contains objects with an op property referencing the TAG enum defined in src/type.ts (lines 16-24). The reconcileChildren caller attaches these actions to each child fiber (child.action = actions[i]), which the commit phase (src/commit.ts) consumes to perform actual DOM mutations.

Practical Example: Keyed List Reordering

Consider a component rendering a dynamic list where each item has a stable identifier:

import { h } from 'fre'

function List({ items }: { items: { id: string; text: string }[] }) {
  return (
    <ul>
      {items.map(item => (
        <li key={item.id}>{item.text}</li>
      ))}
    </ul>
  )
}

When the items array reorders, Fre's diff() algorithm:

1. Detects that each <li> retains the same key (item.id) via the bMap lookup
2. Issues MOVE actions to reposition existing DOM nodes rather than destroying and recreating them
3. Preserves component state and input focus across the reorder operation

Without keys, the algorithm would fall back to positional comparison, likely resulting in unnecessary removals and insertions.

Summary

• Fre's diff() implements an O(N) keyed reconciliation algorithm in src/reconcile.ts using double-ended pointers (aHead, aTail, bHead, bTail) to optimize list diffing.

• The algorithm builds a bMap key index for the new children to achieve constant-time lookups, enabling efficient detection of moved elements versus new insertions.

• Four operation types drive the commit phase: UPDATE (reuse DOM node), MOVE (reposition existing node), INSERT (create new node), and REMOVE (destroy node).

• Actions are batched and ordered to ensure DOM mutations execute correctly, with tail-side updates reversed and appended after the core reconciliation loop.

• The TAG enum in src/type.ts defines operation codes consumed by src/commit.ts to apply the computed differences to the actual DOM.

Frequently Asked Questions

What makes Fre's diff algorithm "keyed"?

Keyed reconciliation relies on the optional key property assigned to elements in arrays. When children possess stable keys, Fre builds an index map (bMap) of the new children's positions, allowing the algorithm to identify which existing DOM nodes can be reused and moved versus which need creation. This prevents unnecessary destruction of component state when lists reorder.

How does Fre handle unkeyed children during reconciliation?

For elements without keys, Fre falls back to positional comparison using the double-ended pointer strategy. If the fast-path head/tail synchronization fails to match nodes, the algorithm treats mismatches as removals and insertions rather than moves, which is less efficient but maintains correctness for dynamic content.

What is the time complexity of Fre's diff() function?

The algorithm operates in O(N) time complexity where N is the total number of children in both lists. The initial pointer sweeps run in linear time, the key map construction is linear, and the core reconciliation loop processes each node exactly once thanks to the bMap providing O(1) key lookups.

How does the diff algorithm interact with Fre's commit phase?

After diff() returns the actions array, the reconcileChildren function attaches each action to its corresponding fiber. During the commit phase (src/commit.ts), the system iterates these fibers and executes the DOM mutations encoded in action.op (INSERT, MOVE, UPDATE, or REMOVE), ensuring the browser reflects the new virtual DOM state.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}