tinymux/docs/design-collation.md

Unicode Collation (Layer 4) Design

Overview

Implement the Unicode Collation Algorithm (UCA, UTS #10) using the existing DFA state machine infrastructure in utf/. This replaces strcmp-based sorting with linguistically correct ordering for all Unicode text.

Data Landscape (Unicode 16.0 DUCET)

Source: utf/allkeys.txt (allkeys-16.0.0.txt)

Metric	Count
Single-CP, single-CE entries	34,539
Single-CP, 2-CE entries	3,957
Single-CP, 3-CE entries	666
Single-CP, 4+-CE entries	245
Multi-CP contractions	964
Variable/shifted (punctuation)	8,467
Ignorable (all-zero CEs)	974
Unique primary weights	29,318
Unique secondary weights	264
Unique tertiary weights	29
Unique full CE tuples	32,458
Max CEs per entry	18
Primary weight range	0200..72B6
Secondary weight range	0020..0126
Tertiary weight range	0002..001F
Implicit weight ranges	4

Key insight: even NFC precomposed characters expand to multiple CEs. e-acute (U+00E9) produces two collation elements: [.23E7.0020.0002][.0000.0024.0002] -- the accent is a secondary-only CE (primary=0000).

Multi-Level Architecture

UCA comparison is NOT a simple per-code-point weight comparison. The algorithm collects collation elements across an entire string, then compares at each level in sequence:

String "cafe"  -> CEs: [2380.0020.0002] [2380.0020.0002] [2422.0020.0002] [23E7.0020.0002]
String "cafe'" -> CEs: [2380.0020.0002] [2380.0020.0002] [2422.0020.0002] [23E7.0020.0002] [0000.0024.0002]

Level 1 (primary):   2380 2380 2422 23E7   vs   2380 2380 2422 23E7     -> TIE (skip zero primaries)
Level 2 (secondary): 0020 0020 0020 0020   vs   0020 0020 0020 0020 0024 -> cafe' > cafe

Mappings Required

Mappings IN (code point -> collation structure):

1. Single code point -> CE sequence (34,539 single-CP entries)

   • Tool: integers.exe (cp -> CE table index)
   • Most entries (34,539) produce a single CE
   • 4,868 entries produce 2+ CEs (expansions)

2. Code point pair -> CE sequence (964 contractions)

   • Tool: pairs.exe ((cp1,cp2) -> CE table index)
   • Examples: Cyrillic short-I (0438 0306), Arabic hamza sequences

3. Implicit weights for unassigned/CJK (algorithmic)

   • Tangut: 17000..18AFF -> base FB00
   • Nushu: 1B170..1B2FF -> base FB01
   • Khitan: 18B00..18CFF -> base FB02
   • CJK Unified: algorithmic per UCA Section 10.1
   • All others: derived from code point value

The CE Table (the multi-level thing):

[length] [primary1, secondary1, tertiary1] [primary2, secondary2, tertiary2] ...

A flat C array of collation element sequences. Each entry:

Indexed by the DFA output. This is where the multi-level weights live.

Mappings OUT (collation structure -> comparison result):

The runtime comparison function walks two strings simultaneously, collecting CEs, then compares level by level per UCA algorithm:

1. Compare all primaries (skip zero primaries from secondary-only CEs)
2. If tied, compare all secondaries (skip zero secondaries)
3. If tied, compare all tertiaries
4. If tied, compare quaternary / code point order (tiebreaker)

DFA Tables

Table 1: cp -> CE index (integers.exe)

Input: tr_ducet.txt -- generated by gen_ducet.pl Format: CODEPOINT;CE_INDEX

Maps each code point with an explicit DUCET entry to an index into the CE table. Code points not in the DFA get implicit weights (computed algorithmically at runtime).

~39,400 entries, ~29,000+ unique CE sequences -> ~29,000+ accepting states. The integers.exe tool handles this (sot uses unsigned short, supporting up to 65,535 states).

Table 2: (cp1, cp2) -> CE index (pairs.exe)

Input: tr_ducet_contract.txt -- generated by gen_ducet.pl Format: CP1 CP2;CE_INDEX

Maps 964 two-character contractions to CE table indices. At runtime, check contractions first before falling back to single-CP lookup.

Table 3: CE table (generated C array)

A flat array of packed CE data. Generated directly by gen_ducet.pl as a C header/source fragment.

// Each CE sequence: 1 byte length + N * 5 bytes (primary:16, secondary:8, tertiary:8)
// Or: index into a structured array of CE_Entry.
typedef struct {
    unsigned short primary;
    unsigned char  secondary;
    unsigned char  tertiary;
} CE_Weight;

typedef struct {
    unsigned char nCEs;     // Number of CEs in this sequence (1-18)
    CE_Weight     ce[1];    // Variable-length array (actual size = nCEs)
} CE_Entry;

Structure (packed for space efficiency):

Estimated size: ~39,400 entries * avg ~1.2 CEs * 4 bytes = ~190 KB (compact — the DFA tables will be larger).

Phases

Phase 1: Data Pipeline (gen_ducet.pl + CE table generation)

Goal: Parse allkeys.txt, produce three output files, verify data integrity.

Deliverables:

• utf/gen_ducet.pl -- Perl script that reads allkeys.txt and emits:
  • utf/tr_ducet.txt -- single-CP entries: CODEPOINT;CE_INDEX
  • utf/tr_ducet_contract.txt -- contractions: CP1 CP2;CE_INDEX
  • utf/ducet_cetable.h -- C header with CE_Weight array and CE_Entry index table
• Verification: round-trip check that every DUCET entry can be reconstructed from the generated tables

Variable weighting: Entries marked with * (asterisk) in allkeys.txt are "variable"—punctuation, whitespace, symbols. In the default "non-ignorable" mode, their weights are kept as-is. We implement non-ignorable first (simplest, matches existing strcmp behavior for punctuation ordering). Shifted mode can be added later.

Implicit weights: The script also generates a comment documenting the implicit weight algorithm parameters, but the actual implicit weight computation is done at runtime (Phase 3).

Phase 2: DFA Table Generation

Goal: Run integers.exe and pairs.exe to build compressed DFA state machines from Phase 1 output.

Deliverables:

• Run integers.exe tr_ducet utf/tr_ducet.txt -> DFA tables in utf8tables.cpp/h (TR_DUCET_*)
• Run pairs.exe tr_ducet_contract utf/tr_ducet_contract.txt -> DFA tables (TR_DUCET_CONTRACT_*)
• Integrate ducet_cetable.h into the build
• Verify: tables compile, sizes are reasonable

Expected sizes:

• Single-CP DFA: ~39,400 entries across 29,000+ unique outputs -> large but within unsigned-short state range
• Contraction DFA: 964 pairs -> modest size (similar to NFC compose)
• CE table: ~190 KB

Phase 3: Runtime Comparison Function

Goal: Implement mux_collate_cmp() -- the core UCA comparison.

Deliverables:

• mux/src/utf8_collate.cpp -- new source file
• int mux_collate_cmp(const UTF8 *a, size_t nA, const UTF8 *b, size_t nB)
  • Walks both strings code-point by code-point
  • For each code point: check contraction DFA first (peek at next CP), then single-CP DFA, then implicit weight algorithm
  • Collects CE sequences for both strings
  • Compares level 1 (primary), then level 2 (secondary), then level 3 (tertiary), then tiebreaker (code point order)
  • Returns -1, 0, +1
• void mux_collate_sortkey(const UTF8 *src, size_t nSrc, UTF8 *key, size_t *nKey)
  • Generates a binary sort key that can be compared with memcmp
  • For use in qsort (pre-compute keys, then binary-compare)
  • Sort key format: all primaries (big-endian 16-bit) + 0x0000 + all secondaries (8-bit) + 0x00 + all tertiaries (8-bit)
• Implicit weight computation for CJK and unassigned code points per UCA Section 10.1

Phase 4: Sort Integration

Goal: Wire collation into sort(), setunion/inter/diff, comp().

Deliverables:

• New sort type UNICODE_LIST (value 32), triggered by 'u'/'U'
• New comparator u_comp() that uses pre-computed sort keys
• do_asort_start(): for UNICODE_LIST, pre-compute sort keys into q_rec, then qsort with memcmp-based comparator
• Update handle_sets() comparator dispatch
• Update fun_comp() to accept optional third argument for comparison type (or always use collation—TBD)
• Update AutoDetect -- when list is non-numeric, default to UNICODE_LIST instead of ASCII_LIST
• Add 'u'/'U' to sort type dispatch in fun_sort()

Phase 5: Case-Insensitive Collation ✓

Goal: Add a case-insensitive collation sort type.

UCA Level 1+2 comparison (ignoring tertiary/case) gives natural case-insensitive collation.

Delivered:

• mux_collate_cmp_ci() — Level 1+2 only, returns 0 for case-only differences
• mux_collate_sortkey_ci() — sort key omitting Level 3 weights
• New sort type CI_UNICODE_LIST (value 64), triggered by 'c'/'C'
• comp(a, b, c) for case-insensitive Unicode comparison

Phase 6: Polish and Documentation

Goal: Update help text, verify edge cases, optimize.

Deliverables:

• Help text for sort(), comp(), setunion(), setinter(), setdiff() documenting new sort types
• Edge case testing: empty strings, single characters, identical strings, maximum-length strings, CJK, emoji, mixed scripts
• Performance: benchmark sort key generation vs direct comparison for typical MUD string lengths
• Update docs/design-unicode-evolution.md Layer 4 section

Build Integration

• utf8_collate.cpp added to Makefile.am and netmux.vcxproj
• ducet_cetable.h included from utf8_collate.cpp
• DFA tables appended to existing utf8tables.cpp/h
• No new external dependencies

Risks and Mitigations

DFA size: The single-CP DUCET DFA has ~39,400 entries with ~29,000 unique outputs. This is much larger than any existing DFA (TR_NFC_COMPOSE is the current largest at 1,010 states). The integers.exe tool uses unsigned short for sot (65,535 max states) which should suffice. If the blob size is too large, we can split BMP vs supplementary planes.

Sort key memory: Sort keys for N-element lists require O(N * avg_key_len) temporary memory. For typical MUD lists (< 1000 elements, short strings), this is well within LBUF_SIZE constraints. For extreme cases, fall back to direct comparison (slower but no extra memory).

Contractions: The 964 two-CP contractions require peeking ahead one code point during string traversal. This is straightforward but adds a branch to the hot path. Most contractions are for combining-character sequences that are rare in MUD text.

Implicit weights: CJK unified ideographs (~97,000 code points) are not in allkeys.txt—their weights are derived algorithmically. This is well-specified in UCA Section 10.1 and is a few lines of code.

Future Extensions

• Variable weighting (shifted mode): Treat punctuation as ignorable at primary level. Useful for "natural" sorting where "don't" sorts near

"dont." Can be added as another sort type letter.

• Locale tailoring: CLDR locale data modifies DUCET for specific languages (e.g., Swedish a-ring sorts after z, not after a). Architecture

supports this via modified CE table entries, but no locale tailoring is planned for initial implementation.

• Incremental comparison: For comp() and setunion/inter/diff where we compare but don't sort, direct incremental comparison (without

building full sort keys) may be faster. Optimize after profiling.