Trie Traversal Algorithm

Relevant source files

The following files were used as context for generating this wiki page:

• scripts/trie/decode-trie.ts
• scripts/trie/decode-trie.spec.ts
• src/decode.ts
• scripts/trie/encode-trie.ts
• scripts/trie/trie.ts
• scripts/trie/README.md

The Trie Traversal Algorithm is a high-performance mechanism used to decode named character references (entities) in HTML and XML documents. By mapping a radix tree structure into a single Uint16Array, the project achieves significant memory savings—reducing the in-memory size from ~8.5MB to ~250KB—while maintaining equivalent performance. The traversal logic involves navigating through nodes that may represent single characters, compact runs of characters, or branching paths using jump tables and dictionaries.

The algorithm supports different decoding modes, including Legacy (semicolon optional), Strict (semicolon required), and Attribute (specific termination rules). It uses bitwise flags within 16-bit words to identify node types and determine the next jump or value emission.

Sources: scripts/trie/README.md:1-12, src/decode.ts:80-87, src/decode.ts:689-693

Node Structure and Layout

Every node in the binary trie begins with a 16-bit header word. This word contains packed metadata that dictates how the traversal engine should interpret the subsequent elements in the Uint16Array.

Header Bit Layout

Bits	Field	Description
15..14	Value Length	Encoded length (0: No value, 1: Inlined, 2: 1 unit, 3: 2 units).
13	Dual-use Flag	Semicolon-required flag (if value) or Compact Run flag (if no value).
12..7	Branch/Span	Branch length, span length, or compact run length.
6..0	Offset/Char	Jump table offset, first character of a run, or single branch key.

Sources: scripts/trie/README.md:37-50, src/decode.ts:474-477

The diagram above illustrates the initial decision logic when the traversal engine encounters a new node header. Sources: src/decode.ts:474-565, scripts/trie/README.md:68-75

Traversal Modes

The traversal logic switches between three primary modes depending on how children are stored: Single Branch, Jump Table, and Dictionary.

1. Single Branch

If a node has exactly one child and that child is not encoded elsewhere, the branch length bits (12..7) are 0, and the child character code is stored in the lower 7 bits (6..0). The traversal simply compares the input character to this offset.
Sources: scripts/trie/README.md:92-96, src/decode.ts:696-699

2. Jump Table

Used when branch keys form a dense range. Bits 6..0 store the minimum key (offset), and bits 12..7 store the span length. The engine performs an unsigned subtraction and bounds check to locate the target slot.

• Slot value 0: No branch taken.
• Non-zero: Represents destinationIndex + 1.

Sources: scripts/trie/README.md:97-100, src/decode.ts:705-710

3. Dictionary (Sparse)

Used for sparse keys. Keys are packed two per uint16 word (low byte even, high byte odd). The engine uses binary search on these packed keys to find the destination index.
Sources: scripts/trie/README.md:101-106, src/decode.ts:713-739

Compact Runs

Compact runs optimize paths where multiple single-child nodes lead to a terminal. Instead of pointer chasing, the engine collapses these into a single header.

• The run length (bits 12..7) defines how many characters are in the path.
• The first character is in the header (bits 6..0).
• Subsequent characters are packed two per word immediately following the header.

Sources: scripts/trie/README.md:68-81, src/decode.ts:479-524

The sequence diagram shows how the EntityDecoder bypasses multiple node lookups by streaming through a packed character run. Sources: src/decode.ts:479-520, scripts/trie/README.md:76-81

Value Emission Logic

When the algorithm reaches a node with a value (valueLength > 0), it must decide whether to emit it based on the DecodingMode.

Implicit Semicolon Handling

HTML "strict" entities (where bit 13 is set) do not store an explicit ';' branch. During traversal, if the current node has a value and the input character is a semicolon, the value is emitted immediately.
Sources: scripts/trie/README.md:59-63, src/decode.ts:536-543

Legacy Matches

In Legacy mode, the algorithm records the "best" non-terminated match found so far. If a subsequent branch lookup fails (e.g., a mismatch occurs later in the string), the engine falls back and emits the last recorded legacy value.
Sources: src/decode.ts:553-562, src/decode.ts:634-644

Data Extraction

Values can be stored in three ways depending on valueLength:

1. Inlined: Codepoint is masked out of the header word's low 14 bits.
2. One unit: Stored in the next array element.
3. Two units: Stored in the next two array elements (for surrogate pairs).

Sources: scripts/trie/README.md:51-57, src/decode.ts:592-602

Summary of Traversal Logic

The determineBranch function is the core utility for moving between nodes. It encapsulates the jump table and dictionary lookup logic.

export function determineBranch(
    decodeTree: Uint16Array,
    current: number,
    nodeIndex: number,
    char: number,
): number {
    const branchCount = (current & BinTrieFlags.BRANCH_LENGTH) >> 7;
    const jumpOffset = current & BinTrieFlags.JUMP_TABLE;

    if (jumpOffset) {
        if (branchCount === 0) return char === jumpOffset ? nodeIndex : -1;
        const value = char - jumpOffset;
        if (value >>> 0 >= branchCount) return -1;
        const stored = decodeTree[nodeIndex + value];
        return stored === 0 ? -1 : (nodeIndex + value + stored - 1) & 0xff_ff;
    }
    // ... binary search for dictionary logic ...
}

Sources: src/decode.ts:689-710

The Trie Traversal Algorithm provides a memory-efficient, high-speed solution for entity decoding by utilizing a bit-packed array representation and optimized path-collapsing (compact runs). Its ability to handle legacy HTML entities via implicit semicolon checks and fallback mechanisms ensures full spec compliance with minimal overhead.