Map Generation Scripts

Relevant source files

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

• scripts/write-decode-map.ts
• scripts/write-encode-map.ts
• scripts/trie/encode-trie.ts
• scripts/trie/trie.ts
• scripts/trie/README.md
• package.json

The map generation scripts are a set of build-time utilities responsible for transforming raw JSON entity maps into highly optimized, binary-encoded data structures. These scripts ensure that the library can perform fast lookups for both encoding and decoding HTML/XML entities while maintaining a small memory footprint.

The primary purpose of these scripts is to generate Uint16Array trie structures and serialized strings that are consumed by the runtime decode and encode modules. This pre-compilation step allows the library to avoid expensive object allocations and large memory consumption at runtime.

Sources: scripts/trie/README.md:1-12, package.json:44-45

Architecture Overview

The generation process follows a pipeline where raw entity mappings are first converted into logical trie structures, then optimized (e.g., into radix trees or via compact runs), and finally serialized into TypeScript files.

Decode Map Generation

The write-decode-map.ts script handles the creation of the decoding tries. It uses a custom encoding scheme to pack trie data into a string that is smaller than Base64 and optimized for Gzip compression.

Encoding Logic and Dictionary

For large tries (like HTML), the script uses a dictionary-based approach combined with delta-encoding and Run-Length Encoding (RLE).

Component	Description
SAFE Chars	91 printable ASCII characters safe for JS literals (0x21–0x7E minus ", $, \).
Dict1	The 61 most frequent trie values, assigned to 1-char codes.
Dict2	Remaining unique values, assigned to 2-char codes.
RLE Marker	A specific character (SAFE[89]) used to denote consecutive delta-1 values.
Escaping	Escape characters (SAFE[90]) used for large deltas between values.

Sources: scripts/write-decode-map.ts:10-20, scripts/write-decode-map.ts:25-36, scripts/write-decode-map.ts:105-115

Binary Trie Packing

The script leverages encodeTrie to map the logical trie into a Uint16Array. The layout includes:

• Header Word: 16-bit word containing value length, dual-use flags (semicolon requirement or compact run), and branch/jump data.
• Value Storage: Inlined 14-bit values or out-of-line 16-bit values.
• Branching: Jump tables for dense keys and dictionaries for sparse keys.

Sources: scripts/trie/README.md:47-97

Encode Map Generation

The write-encode-map.ts script generates the trie used to convert characters back into entities. Unlike the decoder trie, the encoder trie is keyed by full Unicode code points rather than UTF-16 char codes to eliminate large surrogate blocks.

Serialization Format

The encoder trie is serialized into a compact string using a delta-encoded format:
[gap][name];[{children}]

• Gap: A base-10 integer representing currentKey - previousKey - 1.
• Name: The entity name (e.g., amp).
• Children: Nested blocks {} representing the second code unit of multi-character entities (e.g., < + U+20D2 → <⃒).

Sources: scripts/write-encode-map.ts:32-75, src/encode.ts:47-65

Key Functions

Trie Construction

• getTrie(map, legacy): Constructs a logical trie from JSON maps. In the encode script, it treats astral characters as flat entries at their code point.
• encodeTrie(trie, redundancy): Transforms the logical trie into a Uint16Array with optimized branch lookups.

Sources: scripts/write-encode-map.ts:38-66, scripts/write-decode-map.ts:219-223

Data Serialization

• encodeTrieData(data): Implements the dictionary + delta + RLE encoding for the decoder map.
• serializeTrie(trie): Recursively stringifies the encoder trie into the custom gap-based format.

Sources: scripts/write-decode-map.ts:40-184, scripts/write-encode-map.ts:68-87

Build Integration

The scripts are integrated into the project's lifecycle via NPM scripts defined in package.json.

"scripts": {
    "build:encode-trie": "node --import=tsx scripts/write-encode-map.ts",
    "build:trie": "node --import=tsx scripts/write-decode-map.ts"
}

Sources: package.json:44-45

Summary

Map Generation Scripts are critical to the performance of the entities library. By moving the complexity of trie construction and optimization to a build-time step, the library achieves high-speed decoding and encoding with minimal runtime overhead. The use of specialized binary layouts and custom string serializations allows the project to provide comprehensive HTML5 entity support within a few hundred kilobytes of data.

Sources: scripts/trie/README.md:6-12, scripts/write-decode-map.ts:34-36