Decoding Trie Structure

Relevant source files

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

• scripts/trie/trie.ts
• scripts/trie/README.md
• src/decode.ts
• src/internal/decode-shared.ts
• scripts/write-decode-map.ts
• scripts/trie/decode-trie.ts

The decoding trie structure in the entities project is a highly optimized, array-mapped radix tree designed to facilitate rapid lookups of HTML and XML named character references. By mapping a logical trie into a Uint16Array, the system achieves significant memory reduction—decreasing the in-memory size of entity data from approximately 8.5MB to roughly 250KB while maintaining equivalent performance to object-based structures.

This system handles the complexities of the WHATWG HTML specification, including "legacy" entities (where the trailing semicolon is optional) and "strict" entities (which require a semicolon). It utilizes specialized node types, such as compact runs and jump tables, to minimize pointer chasing and optimize for various character distribution patterns found in entity names.
Sources: scripts/trie/README.md:3-12, src/decode.ts:400-420

Binary Node Layout

Nodes are stored contiguously in a Uint16Array. Each node starts with a 16-bit header that encodes the node's properties, including value presence, semicolon requirements, and branch metadata.

Header Bitmask Specification

Bits	Purpose	Description
15..14	Value Length	Encodes if the node has a value (0: none, 1: inline, 2: 1 unit, 3: 2 units).
13	Dual-use Flag	If Value > 0: Semicolon required. If Value == 0: Compact run flag.
12..7	Branch Span	Length of the run OR number of branches/span of the jump table.
6..0	Lookup Data	Jump table offset OR first character of a run/single branch.

Sources: scripts/trie/README.md:38-44, src/decode.ts:577-580

Value Encoding Strategies

The system supports three primary ways to store the result of a successful entity match:

1. Inlined Value (Length 1): The code point is stored directly in the lower 14 bits of the header. This is restricted to code points that do not collide with flag bits.
2. Single Code Unit (Length 2): One uint16 following the header.
3. Double Code Unit (Length 3): Two uint16 words following the header, typically used for surrogate pairs or multi-character entity results.
   Sources: scripts/trie/README.md:46-56, src/decode.ts:543-558

Navigation and Branching Logic

The determineBranch function is the core logic for traversing the trie. It selects a navigation strategy based on the branch count and offsets stored in the header.

The diagram shows the decision tree used to navigate from one trie node to the next based on the input character.
Sources: src/decode.ts:577-626, scripts/trie/decode-trie.ts:80-110

Branching Types

• Single Branch: Encoded directly in bits 6..0 of the header if there is exactly one child.
• Jump Table: Used for dense character ranges. It stores destinationIndex + 1 in slots following the header. A 0 value indicates no branch.
• Dictionary (Sparse): Used for sparse keys. Keys are packed two-per-word (low byte/high byte) and sorted to allow binary search during lookup.
  Sources: scripts/trie/README.md:83-100, src/decode.ts:600-625

Compact Runs

Compact runs optimize linear chains of single-child nodes. When a path of at least three nodes exists without branching or intermediate values, they are collapsed into a single run entry.

• Structure: The header sets bit 13 and stores the run length in bits 12..7. The first character is in bits 6..0.
• Packed Characters: Subsequent characters are packed two per uint16 word (low/high bytes).
• Validation: During decoding, if any character in the run mismatches the input, the decoder triggers a fallback to a recorded legacy match or rejects the entity.

This flow illustrates how the decoder validates a compact run before proceeding to the terminal node of that path.
Sources: scripts/trie/README.md:65-75, src/decode.ts:413-460

Data Persistence and Packing

The trie is stored as a string and unpacked into a Uint16Array at runtime using a delta-encoded dictionary format.

Delta and RLE Encoding

The scripts/write-decode-map.ts utility prepares the trie data using a custom base-91 encoding scheme.

• Dict1: Stores the 61 most frequent values.
• Dict2: Stores all remaining unique values.
• Delta-RLE: Values are stored as differences from the previous value. A specific marker (SAFE[89]) indicates a run of consecutive delta-1 values to further compress the data.
• Escaping: Large deltas use escape characters to signify 2-byte or 3-byte variable-length integers.
  Sources: scripts/write-decode-map.ts:25-60, src/internal/decode-shared.ts:38-75

Packing Format Table

Marker	Meaning	Logic
< 89	Direct Delta	previousValue += code
89	RLE Marker	Read next char N, emit N + 2 consecutive +1 increments.
90	Escape	Read next 1-2 chars to resolve large jumps.

Sources: src/internal/decode-shared.ts:45-70

Decoder State Management

The EntityDecoder class handles partial input and streaming. It maintains internal state to resume decoding across multiple write calls.

The state machine tracks the progress of decoding a single entity from the leading & to its termination.
Sources: src/decode.ts:60-70, src/decode.ts:133-160

Streaming Logic

The decoder tracks consumed characters and excess characters. If a write call ends while in the middle of a compact run or a deep trie branch, it returns -1 to signal that more data is required. The end() method is used to flush any pending legacy matches (entities without semicolons) when the input stream terminates.
Sources: src/decode.ts:178-200, src/decode.ts:515-535

Conclusion

The decoding trie structure is a sophisticated implementation of an array-mapped radix tree that balances extreme memory efficiency with high-speed lookup capabilities. By leveraging bit-packed headers, compact runs for linear paths, and multiple branching strategies (jump tables vs. binary-searched dictionaries), the system accurately implements the complex WHATWG HTML entity decoding rules while remaining performant in both synchronous and streaming environments.