zig-collate

The Unicode Collation Algorithm, UTS #10, in Zig.

Sorting text by code point is not merely unlocalized, it is wrong in a way people notice: Mueller sorts before Märtens, because u is U+0075 and ä is U+00E4. This library exists so that a program which needs to put names in order does not have to reimplement a collation to get that right — and so that it does not get it wrong in the same way every such reimplementation does.

The API documentation is generated from the doc comments in the source and published at https://jeff.jcollie.page/zig-collate/. Those comments carry most of the explanation, including which paragraph of the specification each piece implements, and every public function has a worked example beside it — a doctest, which zig build test runs, so an example that stops being true fails the build rather than misleading a reader.

It passes the UCA conformance suite of UTS #10 section 12.2 in full: 212,066 cases with non_ignorable variable weighting and 212,066 with shifted, all at identical strength, nothing filtered. Built with -Dembed-cldr it also passes CLDR's own suite for the CLDR root collation, 210,186 cases in each. Those are the acceptance criteria rather than smoke tests — see Testing.

Using it

const collate = @import("collate");

const c: collate.Collator = .{};
const order = try c.order(gpa, "Märtens", "Mueller"); // .lt

order allocates nothing for strings of ordinary length — both keys and the scratch come off the stack — so it is safe to hand to a sort comparator, and it does not write a whole key to answer: it compares a level at a time and stops at the first level that decides, which is section 9.7's incremental comparison. It still weighs both strings on every call, though, and sorting a list means building one sort key per string and then comparing the keys, which is what makes the whole thing affordable: n key constructions and n log n byte comparisons, rather than n log n collations. Hoist a Builder so the scratch is reused rather than re-made per string:

var builder: collate.Builder = .empty;
defer builder.deinit(gpa);

const key = try builder.sortKeyAlloc(gpa, c, name);
// ... and later, wherever the comparison happens
if (collate.orderKeys(key_a, key_b) == .lt) { ... }

Settings are the parametric ones of section 8.1:

const c: collate.Collator = .{ .options = .{
    .strength = .primary,            // base letters only: a == A == á
    .alternate = .non_ignorable,     // punctuation sorts at its own weight
    .backwards_secondary = true,     // French dictionary accent ordering
    .case_first = .upper_first,       // uppercase before lowercase
    .case_level = false,             // compare case on a level of its own
} };

One default is worth knowing about. alternate defaults to shifted and strength to tertiary, which is what the UCA specifies — and shifted puts what it takes from punctuation on the fourth level, which tertiary strength does not look at. So at the defaults punctuation is ignored outright, and "abc" and "abc!" collate equal. LDML defaults alternate to non_ignorable for exactly that reason. Both readings are conformant; pass .non_ignorable if punctuation should count, or .quaternary strength if it should count last.

case_first orders by a case weight in front of the tertiary weight, which is what ICU does and is not the same as swapping Table 17's two cased bands over. Every collation element carries its own case, in three values rather than two: section 3.3 of LDML part 5 is explicit that a rule target of more than one letter can be mixed case, and CLDR relies on it — Danish orders aa, then Aa, then AA, and Maltese does the same with four spellings of għ. Which case an element has is section 5.1's algorithm rather than a reading of its tertiary weight: the root's uppercase weights are a named set, and a tailored mapping takes its bits from the root elements of the string the rule is about.

case_level is the setting for a question no strength can answer: compare case but not accents. strength = .secondary ignores the tertiary level entirely, so a and A come out equal; turning the case level on inserts a level of case weights between the secondary and the tertiary, which is section 5.1's caseLevel. The tertiary level is left exactly as it was — the case goes on its own level rather than coming out of the one below it. Church Slavonic's rules ask for it, and it is the only CLDR locale that does.

A locale's rules can ask for these settings themselves, and Options.applying is how they are taken up:

const c: collate.Collator = .{
    .table = collate.cldr_root.tailored(&collate.locales.da),
    // Danish's rules open with `[caseFirst upper]`.
    .options = (collate.Options{ .alternate = .non_ignorable })
        .applying(collate.locales.da.settings),
};

It is applied on request rather than automatically, because the locale's opinion and the caller's are different things: xsl:sort case-order= has its own, and it has to be able to win.

Two root collations

collate.ducet is the Default Unicode Collation Element Table, straight out of UTS #10. collate.cldr_root is CLDR's, which is a tailoring of DUCET applied before anyone's language is considered: scripts regrouped, the set of characters treated as variable narrowed sharply — DUCET's variable band runs 0x0201..0x221F and CLDR's 0x0201..0x04E4, so symbols are variable in one and not the other — and the sentinels that section 1.6's sort key merging needs added at each end. It is what ICU orders by, so it is what most other software agrees with.

The bottom sentinel is U+FFFE, which both roots give the lowest primary weight there is, 0x0200, and which is never variable. The sort key follows UCA 18.0's two further rules for it: with backwards_secondary the accents are reversed within each field between separators rather than across the whole string, and at identical strength U+FFFE sorts below every code point. So last ++ "\u{FFFE}" ++ first sorts by the last name and then the first at every strength, French accent order included.

const c: collate.Collator = .{ .table = collate.cldr_root };

Both are generated from allkeys-format files by the same generator, because CLDR publishes its root as one — with one thing left out of that file, which is Han. CLDR orders the Unified Repertoire by radical and stroke count, and allkeys_CLDR.txt carries no Han mappings at all, so a table built from it alone falls back on section 10.1.3's code-point order and disagrees with ICU about most pairs of ideographs. The order lives in FractionalUCA.txt instead, as 214 lines of the form [radical 87=⽖爫:爫-爯…], and data/FractionalUCA_radicals-49-beta4.txt is those lines; cldr_root ranks 101,997 ideographs from them and computes an implicit weight from the rank. ducet keeps the code-point order, because that is what the DUCET is.

cldr_root needs -Dembed-cldr, which is off by default for the reason under The Unicode data.

Searching

Searcher finds a pattern in a target by what the collation cannot tell apart, which is UTS #10 section 11: resume in Your Résumé at primary strength, strasse in STRASSE at secondary, and, under a Danish tailoring, aa in Gård.

const c: collate.Collator = .{ .options = .{ .strength = .primary } };
var s = try collate.Searcher.init(gpa, c, "resume", .{});
defer s.deinit();

const m = (try s.find("Your Résumé", 0)).?; // m.start == 5, m.end == 13
const yes = try s.contains("RÉSUMÉ");
var it = try s.iterator("resume, Résumé, RESUME");
while (try it.next()) |hit| { ... }

Offsets are in the caller's units: bytes into a []const u8, or indices into a []const u21 for the …CodePoints variants. A Searcher holds the pattern's weights, so one query against many targets weighs the pattern once. It also holds scratch for the target, so it is one per thread, like a Builder.

What counts as a match is section 11's: a range of the target whose collation elements write the same sort key as the pattern's. The target's elements are weighed in place, so a contraction is weighed as the whole target has it, and a match never begins or ends inside one — и does not match the first half of й written as и and a breve, at any strength, because the two code points are one letter. Nor inside a run of marks that normalization reordered.

Five options:

• span: .minimal (the default) leaves out characters that weigh nothing at either end, and .maximal takes them in. Looking for abc in def*!Abc%*ghi with punctuation ignored finds Abc minimally and *!Abc%* maximally.
• boundary: .whole_character (the default) lets a match begin and end only between grapheme clusters, so abc does not match the start of abç; .none allows any boundary between collation elements.
• asymmetric: section 11.2's asymmetric search. A pattern character that is unmarked at a level — unaccented at the secondary, lowercase at the tertiary — matches the target's character marked or not, and a marked one only a character marked the same way. At tertiary strength resume finds RÉSUMÉ, Résumé finds RÉSUMÉ but not resume, é does not find ệ́, and けんこ finds げんご but not ケンコ: for kana the normal form is unmarked only among its own syllabary's forms, which is what section 11.2's own table shows. "Unmarked" means the lowest weight, and where a tailoring orders a variant before its letter, as Arabic's &[before 2]ت<<ة does, the variant's weight is below the letter's rather than the letter moving up, so ت finds ة and not the other way round.
• sharp_s_tertiary: section 11's suggestion for German. The DUCET keeps ß a secondary difference from ss, as DIN sorting has it, so a search that ignores case still misses Straße for strasse. With this on, ß and ẞ differ from ss and SS only at the tertiary level, in the pattern and the target alike, and sorting is unaffected.
• max_edits: fuzzy matching. A match may differ from the pattern by this many characters inserted, deleted or substituted, so with one edit colour finds color in the colors. A character is a grapheme cluster — or with boundary = .none whatever lies between two places a match may begin or end — and a contraction such as Danish aa is one. Characters that weigh nothing cost nothing to pass over, and a run of the pattern's characters that matches a run of the target's costs nothing however many each side has, so æb finds aeb at primary strength with no edits: a fuzzy match with no edits is exactly an exact one. A match keeps at least one of the pattern's characters, so for a pattern of n characters this is taken as at most n - 1. Of overlapping candidates the one reported has the fewest edits, then the fewest secondary and tertiary differences, then the leftmost start, then the shortest span, so abc with one edit finds ab in abd, a deletion, rather than abd, a substitution of the same cost.

Every match also says how far it is from the pattern at the levels the search did not compare: secondary_differences counts accents added, removed or changed, and tertiary_differences case and variant forms. resume found in Résumé at primary strength has two of the first and one of the second. Match.closeness orders matches the way section 11.2.1 ranks them, fewest edits first, then fewest secondary differences and then fewest tertiary ones, and Match.closer is the same as a lessThan for std.mem.sort. The library reports the counts and leaves sorting to the caller.

A pattern that weighs nothing at the strength searched at — the empty string, or a lone accent at primary strength — matches everywhere, as an empty range, which is what contains(x, "") conventionally answers.

Match keys are for finding text that is stored rather than at hand. A match key is a string's collation elements as fixed-width records: two strings with equal match keys are equal under the collation, and a string the Searcher finds inside another has its match key inside the other's. So keys can be stored and indexed as bytes, and only the candidates they turn up need a Searcher:

const c: collate.Collator = .{ .options = .{ .strength = .secondary } };
const stored = try c.matchKeyAlloc(gpa, "Your Résumé"); // kept with the text
const query = try c.matchKeyAlloc(gpa, "résumé");
if (c.findMatchKey(stored, query)) |byte_offset| { ... } // a candidate

findMatchKey only finds a query's key at a whole number of records (matchKeyWidth bytes each), because a plain byte search can find it straddling two. A match key holds only the levels its collator's strength compares, and its binary order means nothing.

What a key cannot do:

• It has no grapheme boundaries and cannot tell where one character's elements end and the next one's begin, so it can be found where the Searcher finds no match: a's key is inside æ's at primary strength, because æ expands to an a and an e.
• Asymmetric search and sharp_s_tertiary are the Searcher's alone.
• Under a tailoring, strings the collation calls equal can have different keys, and then a key search misses a match. A collation compares each level's weights as a sequence of their own, so the same weights split differently between elements are equal. The root tables never allow that, but Arabic's do: it weighs its tashkil at the tertiary level only, so a high hamza and a dammatan read the same weights level by level in either order, and ٴٌ equals ٌٴ.

Section 11.1 describes a readable folded string instead, such as gaard for Gård; ADR 0001 says why it is keys here.

Not here yet: whole-word boundaries, which would need UAX #29's word segmentation, or searching backwards. Canonical matches (DS3) are left out by design; section 11 calls them "not commonly necessary".

Checked against ICU's StringSearch, by zig build oracle-search: over the same 53 locales as the collation oracle, 810,886 searches agree on the match exactly — 536,953 exact searches at four comparisons, and 273,933 asymmetric ones at secondary and tertiary strength, which ICU calls USEARCH_PATTERN_BASE_WEIGHT_IS_WILDCARD. Where the two differ by convention the oracle counts the case apart rather than ignoring it, and each count is decided mechanically, from ICU's own answers, boundaries and collation elements. Across all six comparisons:

• ICU matches a pattern that weighs nothing nowhere rather than everywhere (16,591 searches).
• It will end a match inside a grapheme cluster, such as the L and V of a Hangul syllable written in jamo (6,725), or inside a contraction, such as L in the CLDR root's L· (428).
• ICU's search and ICU's own collator disagree about whether the match equals the pattern (642), mostly under shifted handling, where the search treats every accent-like element as ignorable and UCA does not.

And for asymmetric search alone:

• ICU's match takes in accents before or after it that the minimal match leaves out (345).
• ICU takes in characters with no primary weight after a pattern that ends in an accent, or in the variant marker the DUCET spells a compatibility form with, where here the marks after it make the character a different one; and it lets a repeated accent line up with the pattern's last one again (1,518).
• ICU refuses a match followed by a character with no primary weight, even when that character is a grapheme cluster of its own (554).
• The two take different weights of the pattern to be unmarked (126): Korean hanja, whose secondary weights run into a second collation element that ICU's search reads as COMMON; and kana, whose normal forms ICU does not treat as unmarked.
• They agree once tertiary weights are set aside and differ about which of those are unmarked (7), from how ICU encodes some of the CLDR root's compatibility variants.

Searches holding a character added in Unicode 18.0.0 are set aside while ICU is on 17.0.0, as the collation oracle does.

The first run of it found a bug in sorting rather than in search: Hungarian's &cs<<<ccs/cs read the /cs from the root, which has no cs, so ccs weighed as cs, c, s instead of cs twice over and sorted before cscz where ICU puts it after. Nothing in the collation oracle's corpus told those apart.

What is here and what is not

The root collation: the untailored Default Unicode Collation Element Table, all four steps of section 7, the variable weighting options of section 4, strengths from primary to identical, and the derived weights of section 10.1 for everything the table does not mention — Han, Tangut, Nushu, Khitan Small Script, unassigned code points and surrogates.

Also here, for the locales listed below: the CLDR per-locale tailorings, compiled from CLDR's own rule files.

Here: the half of section 9.5's advice about avoiding normalization that turns out not to need FCD at all. Step 1 asks the property tables nothing it can work out for itself — nothing below U+00C0 decomposes or reorders, one table row answers both questions it has about the rest, canonical ordering happens as the string is appended rather than in a pass of its own, and a run of ASCII is copied in one go. That is 33% off a sort key for a string of ASCII, 23% off Latin text in NFC, and 10% off Han. zig build bench is what says so, and DESIGN.md has the table and the two things that were measured and rejected.

Here too, the cheaper half of section 9.7's incremental comparison: order weighs both strings in full, then writes and compares one level at a time, stopping at the first level that decides. Writing the key is 28% to 39% of building one, and almost every comparison of two different strings is settled by the primary level, so most of that is never done — which makes order faster than writing two whole keys and comparing them, by 15% on ASCII and 24% on Vietnamese. Weighing incrementally as well is not done: a contraction or a discontiguous match can reach across the point a partial weighing stopped.

And section 9.1.4's run-length compression, which halves a sort key. Below the first level a key repeats itself — 0x0020 is 94.6% of the root tables' non-zero secondary weights and 0x0002 is 80.0% of their tertiaries, and a string of unaccented lowercase letters has nothing else at either level — so each run of the commonest weight is written as one synthetic weight standing for the run's length. An ASCII key goes from 40.3 bytes to 22.1, Hangul from 50.8 to 23.6, and building one costs no more than it did. The fourth level is compressed as well, where the technique has to be turned upside down — the commonest weight there is the largest the level can hold, so the gap for the synthetic weights is taken from below it rather than above — which takes a quaternary-strength key down by another 21% to 33%. The other techniques in section 9.1 are not applied and DESIGN.md says why; for two of them the answer is in the data, which uses 264 distinct secondary weights where a byte holds 255.

FCD proper — the part that would let composed text skip normalization too — was costed and declined: the ceiling is 2.5% on composed Latin text, measured as the gap between the same words composed and decomposed, and the price is a canonical closure in the root table and in every tailoring. DESIGN.md has the numbers and the reason the closure cannot simply be read out of allkeys_CLDR.txt.

Not here, and measured rather than merely postponed: the four tailored Hangul methods of section 10.1.6. Syllables are decomposed to jamo as S1.1 requires, so the trailing weights problem is reachable — a syllable followed by a Han ideograph outranks the same syllable with a trailing consonant, where Korean dictionary order would have it the other way round. ICU gives the same order, because CLDR's root does not put the trailing consonants above every other script and CLDR's Korean rules tailor no Hangul at all — their 2,212 chains order Hanja by Korean reading. Those shapes are in the oracle's root corpus now, so the agreement is checked rather than assumed; applying any of the four methods would mean disagreeing with both ICU and CLDR.

DESIGN.md has the reasoning, the measurements the representation is built on, and what was decided against.

Per-locale tailorings

A tailoring is what a language wants on top of the root collation: Swedish's å, ä and ö are letters after z rather than variants of a and o, Turkish's ı and i are separate letters. CLDR carries the rules; -Dlocales compiles them in.

const swedish: collate.Collator = .{
    .table = collate.ducet.tailored(&collate.locales.sv),
};

$ zig build -Dlocales=sv,tr,pl

Naming a locale the build was not asked for is a compile error, not a run-time surprise, which is the point of generating declarations. For a caller that has a language string rather than a name it can write down — an xsl:sort lang=, an HTTP header — there is a lookup beside them:

const tailoring = collate.locales.match("sv-FI");   // finds sv

match matches a language tag the way one is meant to be matched: the whole tag, then with its last subtag dropped, and so on. Either separator, case insensitively. Null means no tailoring, which is not a failure — match("de") is null because German needs none — and the root collation is the answer either way. Each tailoring is a delta over the root table — overridden code points, added contractions and the settings the rules asked for, nothing else — because a generated root table is 1.4 MB of Zig source and there are 112 locales with rules. Most deltas are tens of kilobytes; Burmese is 230 KB, Japanese 1.5 MB, and Korean, which tailors 7,476 code points, 2.4 MB.

How much of CLDR this covers

All 135 of the locale files CLDR 49 ships compile: 112 with rules, plus 23 that need no tailoring at all — the root collation is already their answer, and those 23 include de, fr, en, it, nl, pt, id, ms, nb, nn and sw. Nothing is refused.

Compiling is not the same as being right, so every one of the 112 that carries rules is checked against ICU wherever ICU can check it. All 101 that ICU can answer for agree with it on every pair, over 58,169,711 comparisons. The other eleven are locales ICU has nothing to say about, Church Slavonic among them.

Japanese was the last to compile and took three things the others do not ask for: a quaternary relation, a contextual mapping, and a chain of 6,355 kanji at &[last regular]. All three are described below.

What the rules ask for, and where each piece of it lives:

Rule syntax	How it is implemented
&anchor, <, <<, <<<, =	Section 3.3's resets and relations. A relation maps its target to the anchor's elements with the last one of sufficient strength incremented; a primary insertion between two root weights takes a sub-weight, since DUCET's primaries are consecutive and leave nothing between.
<<<<	The quaternary relation: a fourth weight in the element, four bits of it. Only ja writes one, 116 times.
<*, <<*, <<<*, =* with - ranges	Section 3.3's abbreviated relations, one relation per character. Korean writes 436 of them and ja one of 6,355 characters.
prefix|target	A contextual mapping: a contraction with a condition on the code points before it. Only ja, 627 of them.
target/extension	Section 8's expansion: the target weighs as the new elements followed by the extension's.
[before 1], [before 2], [before 3]	The anchor's own weight at that level, with the anchor and everything above it moved up to make room.
&[last tertiary ignorable], &[first secondary ignorable], &[last secondary ignorable]	The three logical positions in the ignorable space, each answered from the definitions rather than from a table of boundary weights.
&[last regular]	The top of the regular primary space. A chain there takes fresh weights from the bottom of the Han group — see below.
[import …]	The imported locale's rules, processed where the [import] stands. Six locales' standard rules use it.
[reorder …]	A permutation of whole reordering groups, as the primary ranges that moved and how far. 47 locales.
[suppressContractions […]]	A list of root contractions to ignore, which step 2 consults. mk, sr and bs_Cyrl.
[caseFirst], [caseLevel], [backwards 2], [strength N], [alternate]	Recorded on the tailoring rather than applied to a weight, because they change how a sort key is built; Options.applying is how the locale's opinion and the caller's meet.
[normalization on], [optimize […]]	Accepted and ignored. The first asks for what step 1 does unconditionally; the second is a hint about which characters to make fast.

Two things in the rule text are punctuation rather than content, and reading them as content is how each was found. CLDR wraps its Arabic operands in U+200E and U+200F so that they read left to right in an editor — ar.xml writes &[before 2]ت<<<LRM>ة, spelling the invisible mark out here — so both marks are skipped the way whitespace is. And three of the script codes [reorder …] uses are not groups of their own: LDML part 5 says "Hrkt=Hira=Kana & Hans=Hant=Hani", so Kana and Hrkt resolve to Hira and Hans and Hant to Hani.

Checked against ICU

There is no conformance suite for a tailoring — UTS #10 ships one for DUCET and CLDR ships one for its root, both of which are run above, and for the per-locale rules there is nothing. So zig build oracle asks ICU, which is the reference implementation of the CLDR collation algorithm:

$ zig build oracle -Dembed-cldr -Dlocales=sv,tr,fi

It builds a corpus out of each tailoring's own material — the code points it overrides, the sequences it contracts, the base letters those hang off — and compares every pair against icu::Collator with the strength, alternate handling and normalization set the same on both sides.

It asks nine questions, one run each. -Doracle-mode=tertiary is the default and the one CI runs: tertiary strength with non-ignorable alternate handling, which is what a tailoring is about. The others are different paths through the sort key builder — primary and secondary truncate the key, which is what a caller asking to ignore accents or case gets; identical appends the NFD of the input behind the weights, and is the only mode that compares anything but weights; quaternary compares the fourth level with nothing shifted on to it, which is where a <<<< relation shows; shifted is quaternary strength with shifted handling, which moves a variable element's primary weight down to that same level; and case_level, upper_first and lower_first force a case setting on both sides, which is how a setting that only three of CLDR's locales ask for — one of them a locale ICU has no data for — gets asked about across a hundred. One mode per run rather than all of them at once, because any of them writes a 615 MB file of comparisons and asks ICU thirty million times — and they accumulate in .zig-cache until it is cleaned.

The eight modes added after the tailorings had stopped disagreeing found seven defects, all below. There is no mode for blanked: ICU's alternate handling attribute takes only the two values, so there is nothing to ask.

Over all 135 locales, against ICU 78.3:

compared against an ICU tailoring, and agreeing on every pair	101, over 58,169,711 comparisons — 28,452,196 of them Korean's and 24,468,510 Japanese's
compared, and disagreeing	none
CLDR gives the locale no tailoring, so there was nothing to compare	23 — de, fr, en and the rest of the root-ordered ones
ICU knows the locale but carries no tailoring for it	4 — ca, dz, sa, wae
ICU has no collation data at all	7 — aa, bal, bal_Latn, cu, sgs, ssy, vo

cu is the one of those worth naming. Church Slavonic asks for five settings at once — [caseLevel on], [caseFirst upper], [backwards 2], [reorder Cyrl] and [suppressContractions] — and 46 combining marks after &[first secondary ignorable], and it was the last locale but one that this library learned to compile. ICU has no Church Slavonic data at all, so nothing has compared it against another implementation: what covers it is unit tests and the other locales that use each of those settings.

[before 1] stays inside the anchor's primary weight

The last locale to disagree was bo, by 5,436 comparisons, and it is worth saying what it took. Tibetan's rules do two things at once: &[before 1]ཀ puts the marks before the first Tibetan letter, and [reorder Tibt] moves Tibetan ahead of Latin. [before 1] used to take the primary weight below the anchor's, which belongs to whatever group precedes Tibetan — so the reordering moved Tibetan and left the marks behind among the Latin letters.

It takes the anchor's own primary weight now, with sub-weight zero, which makeRoomSub frees by moving the root's mappings at that primary up one sub-weight. Both attempts at that broke something else first, and both were the same mistake twice over — a weight moved twice:

• The replacement a root contraction gets must not then be shifted again by the same call, which means doing the root's mappings after the tailoring's own.
• A code point the tailoring already overrides must be skipped when the root's mappings are walked, because the pass over the tailoring's own has already moved it. Maltese found that one: the squared IC at U+1F18B has an element at C's primary and one at I's, so by the time the rule about i runs it is already an override from the rule about c, and its I went to sub-weight two where every other I went to one. 24 comparisons.

The fourth level

<<<< is a relation at a level that UTS #10 says exists in the algorithm and never in a table — for the DUCET that is true, because Alternate.shifted computes the fourth level from the primary weight of a variable element. A tailoring can put one there, and one does: Japanese separates katakana from hiragana with 116 quaternary relations, because it does not want that difference at tertiary strength.

So Element carries a four-bit quaternary, zero for everything in a root table and for 523 elements of Japanese's. Four bits are enough because every one of those chains is one step deep, and the weight came out of primary_sub, which is eleven bits now against a measured maximum of 265.

The two uses share the level, and the sort key keeps them apart the way level one keeps a primary and its sub-weight apart — by writing a pair. The high half is the element's shifted primary weight if shifting moved one down, and otherwise a marker above every weight shifting can produce; the low half is the quaternary weight. ICU is where that ordering comes from rather than a reading of the specification: for Japanese it puts a hyphen followed by katakana before hiragana followed by a hyphen, which places every shifted primary below the marker.

One consequence is worth stating. The level is written under non_ignorable handling too, not only under shifted, because a <<<< difference is not conditional on how punctuation is handled — and ICU agrees, answering identically in both modes. For an untailored collation that makes the fourth level one repeated weight, which cannot change an ordering: two strings equal at the first three levels have the same number of elements contributing to each of them, so they have the same number here. It costs two bytes an element in a key built at quaternary strength or above, and nothing at the default strength, where the level is not written at all.

Contextual mappings

prefix|target is section 3.3's contextual mapping: the rule applies to the target only when the prefix comes before it. Japanese writes 633 of them in the private kana collation it imports — 627 distinct pairs — and every one gives an iteration mark or the prolonged sound mark the weights of the kana it follows, so that あー sorts where ああ does.

A contextual mapping is a contraction with a condition on it, and that is how it is stored: Contraction carries a prefix, empty for every mapping that is not conditional, which is every one in a root table. Everything S2.1 already does for a contraction then serves it unchanged — the longest-match search, the discontiguous growth of section 7.2, and the Entry.starts_contraction flag that keeps the whole mechanism off the path of the code points that have none. The prefix is a condition rather than part of the match: it has been weighed as itself already, it is not consumed, and matching it costs a comparison against the code points the walk has just passed.

Both halves are one or two code points in NFD — が is か followed by U+3099 — which is why both are pooled sequences rather than single values. Sorting puts the longest prefix first within a target, so the most specific condition is tried first and an unconditional mapping last.

The condition has to be checked in both places a contraction can be chosen. S2.1 matches contiguously; S2.1.1 grows a match across skipped non-starters through a second search, and a mapping whose target ends in a non-starter is reached that way rather than by the first. ゞ is ゝ followed by U+3099, U+3099 is a non-starter, so every pair of them took the second route — which was taking the first contextual mapping in the list whatever stood before it, and a bare ゞ weighed as some rule's prefix kana. 864,568 of Japanese's 24,468,510 comparisons, and the oracle is what said so.

6,355 kanji at the top of the regular space

&[last regular]<* and then the JIS-ordered kanji is Japanese's own rule rather than the private collation's, and it asks for two things this library had no answer for.

The first is where the chain's weights come from. A primary insertion ordinarily subdivides the weight it is inserted under, because DUCET's primaries are consecutive; at the top of the regular space there is nothing to insert between, so the chain takes fresh weights. It takes them in pairs — rolling the primary when the 2,047 sub-weights under it run out — because a sort key compares a primary and its sub-weight lexicographically, and 6,355 does not fit in 2,047.

The second is which reordering group they belong to, and that one ICU had to answer. Japanese also asks for [reorder Latn Kana Hani], and ICU sorts those kanji where Han sorts: after the kana and before the untailored ideographs, with Hangul after all of them. This library lays the derived weights of section 10.1.3 out at fixed primaries, which leaves sixty unused between the siniform leads and the Han ranks; CLDR's fractional space has no such gap, so "after the last regular weight" and "before the first Han weight" are the same place there. The band is allocated from the bottom of the Han group accordingly, and the group's declared range starts there. Left in the group below, the kanji sorted after Hangul — 864,280 comparisons of 24,468,510.

What the other modes found

Seven defects: two in key.write that need a tailoring and shifted handling together, one in the generator that only a truncated key shows, and four in the case handling, which had been written from a reading of the algorithm where LDML part 5 section 5.1 gives one outright.

A shifted element must write nothing at the tertiary level, and "nothing" is not the same as "zero". Shifted handling makes a variable element completely ignorable and moves its primary weight to the fourth level; step S3.5 then skips its zero weights. But caseFirst folds the case weight into the tertiary weight, and a case weight of 2 or 3 times the size of the tertiary field is a perfectly good non-zero number — so Danish wrote a phantom tertiary weight for each parenthesis it had just shifted away. The skip now reads the weight in the element rather than what caseFirst made of it. 21 of Danish's 8,778 comparisons, every one a parenthesized H against some other compatibility H.

The fourth level carries the sub-weight too. What shifted handling moves down is a primary weight, and in a tailored collation a primary weight is a primary and a sub-weight together — the pair is one weight in two halves, which is exactly how level one writes it. The fourth level was writing the primary alone, so Thai's &[before 1]๚<ฯ — which gives paiyannoi the angkhankhu's primary with a sub-weight of its own, both of them variable — came out equal where ICU orders them. One comparison of 102,378, and it would have been silent forever without the mode that asked.

Both have unit tests of their own now, because the shifted question is not one CI asks: the tests are what keeps the answers.

Section 5.1's case parameters are an algorithm, not a principle. Four of the seven were here, and every one of them is a line of that section that had been reasoned around rather than read:

• A case level leaves the tertiary level alone. The table of modified collation elements writes p.s.t → p.s.c.t: the case weight goes on a level of its own and the tertiary weight is unmodified. Folding the cased band onto the uncased one as well is not wrong for a root element, whose tertiary weight does mean a case — but a tailoring's tertiary weights are chain positions, and nine of Arabic's forty-three tashkil land in 0x08..0x0C and were being moved down by six. 396 of Arabic's 396,495 comparisons.
• The case level ignores the elements the table says to ignore, which are every secondary ignorable at any strength and every primary ignorable at primary strength. Writing a case weight for each of Arabic's tashkil made a string of two marks differ from a string of one at a level above the one the rule is about.
• A tertiary element's case weight is the constant 3, whatever its case bits and whatever caseFirst asks for — the specification says so, because UCA well-formedness condition 2 wants such an element above every primary and secondary one. And the root's uppercase tertiary weights are {08-0C, 0E, 11, 12, 1D}, three more than Table 17 reads at a glance: the halfwidth voiced sound marks at U+FF9E and U+FF9F weigh 0x11, so under [caseFirst upper] they belong before the combining marks they are forms of. Ewe and Vietnamese are 616,605 and 602,253 comparisons each, and two apiece went the wrong way.
• The case bits of a tailored mapping are read off the root's elements, not off the Unicode case properties. Section 5.1 gives the algorithm: N root primary elements against M tailored ones, copied one for one where they match and combined into the last one where the root has more. Croatian maps U+01C4 and U+01C5 onto DŽ and Dž; both are general category Lt, so the properties call both uppercase, where the root elements say one is uppercase and the other mixed. Breton's c'h spellings are all mixed, C'H included, because the apostrophe between the letters is an uncased primary element, so "all of them uppercase" is false. And Hausa's 'Y is mixed for the same reason. Nine comparisons each in Croatian, Bosnian and Latin Serbian, eight in Breton, two in Hausa.

Croatian and Breton have unit tests of their own, and both are in the tailorings CI compiles.

The ignorable-anchor fallback is for << only. When the element a relation lands on has no primary weight of its own, this library uses the element with one before it instead — which is Finnish's &D̵<<đ, and the reason is that making room in the secondary space between two adjacent combining marks would move every mark in the root. A tertiary relation needs no such thing: the root's tertiary weights stop at 0x1E and the field holds 63, so there is room inside the mark's own bucket. Yiddish's &פֿ<<<ף, which makes final pe a tertiary variant of pe with a rafe, was having the mark dropped — so final pe came out equal to bare pe at secondary strength, where ICU orders them, because ICU keeps the mark and bumps its tertiary weight. At tertiary strength both orderings agree, which is why one comparison of 4,095 sat there until -Doracle-mode=secondary asked.

How long a contraction may be

DUCET's longest is three code points and CLDR's rules go further, so the code points live in a pool and Contraction holds an index into it. That began as a [2]u21, which is exactly what the root needs and nothing more; raising the cap would have been wrong again at the next release, and widening the array would have paid for the longest contraction on all 964 of the root's, most of which are two code points. data.max_contraction is now only the bound on the buffer step 2 keeps a partial match in.

That unblocked five locales. None of the five was right at first — ta by one comparison, ff_Adlm by 136, my by 101,098 — and each was a rule shape the generator had not had to handle before. Removing a limit is not the same as being right past it, and the oracle is what says which.

Script reordering

[reorder Cyrl] moves Cyrillic ahead of Latin without changing a single character's rules. That is 47 of CLDR's locales, and it is a permutation of whole reordering groups — where a group is a contiguous range of primary weights, because FractionalUCA.txt declares where each one starts and each runs to the next one's start. Russian's entire tailoring is four {first, last, offset} ranges: Cyrillic down 1,034 to land where Latin began, and Latin, Greek and Coptic each up 452 to make room.

This is the one place a fixed-width primary weight pays off unexpectedly. The specification's notes for implementations that write sort keys are all about fractional weights — primaries must move by whole lead bytes, a group that does not begin and end on a boundary needs a reserved byte so one can be split, primary compression has to be terminable by comparing adjacent weights. None of it applies to a u16.

Where the weights come from

This is the part that makes a build-time generator worth having. Inserting after an anchor at primary strength needs no search at all: the new element takes the anchor's primary weight with the next free Element.primary_sub, so it lands after the anchor and before whatever primary followed, and everything below it is free because no root element shares that pair.

Secondary and tertiary insertions against a root anchor are the hard case, and &i<<<İ is the example. İ must sort immediately after i at tertiary strength; i has tertiary 0x02; U+FF49 FULLWIDTH LATIN SMALL LETTER I already holds 0x03 under the same primary and secondary. There is no integer between them. A run-time rule applier is stuck, which is why ICU's weights are variable-length byte strings — but a generator can shift U+FF49 up to 0x04 and put İ at 0x03, because a shifted root element is just another entry in the delta. Turkish moves 73 root elements that way; Swedish, 102.

A root contraction is the same trick one level up. The root's own copy cannot be rewritten in place, because a tailoring is a delta over it, so the contraction is replaced: a copy with the same code points and shifted weights goes in the tailoring's own list, and step 2 tries that list before the root's, so the copy shadows the original. Catalan's L· and its relatives are what needed it.

Building

It builds with Zig 0.17.0. The zig-0.16 branch, tagged v0.1.0, is the last that builds with Zig 0.16, and gets only critical fixes.

$ nix develop
$ zig build test               # the unit tests
$ zig build test-conformance   # the UCA conformance suite (downloads 5MB)
$ zig build bench -Dembed-cldr # what the four steps cost, per corpus
$ zig build docs-serve         # read the API documentation locally

Options

-Dembed-ducet=false	Leave the table out. Every code point then takes the derived weights of section 10.1, which is only useful to a caller supplying a Table of its own.
-Dembed-cldr	Compile the CLDR root collation in as collate.cldr_root, and enable zig build test-conformance-cldr.
-Dlocales=sv,tr	Compile these CLDR tailorings in, reachable as collate.locales.sv.
-Drepertoire='Basic Latin,General Punctuation'	Section 9.3.3: generate tables covering only these Unicode blocks — or ranges written as 0000..024F. See below.
-Ddocs-port=N	Port for zig build docs-serve.

A smaller table, for a smaller repertoire

Section 9.3.3 says that characters an implementation does not support "can be treated as if they were unassigned", which means weighing them from their code point by section 10.1 instead of storing them. -Drepertoire= does that, naming the Unicode blocks to keep:

$ zig build -Drepertoire='Basic Latin,Latin-1 Supplement,Latin Extended-A,General Punctuation,Combining Diacritical Marks'

repertoire	table
the whole of Unicode	501.8 KiB
Basic Latin	2.0 KiB
Cyrillic	4.1 KiB
Greek and Coptic	6.1 KiB
the five Latin blocks above	9.9 KiB
those plus Greek and Cyrillic	14.1 KiB

-Dlocales= composes with it: a tailoring carries its own weights, so a locale's characters are supported whether or not the repertoire names their blocks, and the rules are resolved against the full root either way.

Two things to know. A restricted table is a different collation, not a smaller one: everything outside the repertoire sorts after everything inside it, in code point order, so it is conformant over the repertoire it names and not beyond it. And the repertoire is closed under canonical decomposition for you — ask for Greek and you get U+02B9 as well, because U+0374 decomposes to it and would otherwise sort after the whole table. DESIGN.md has the measurement, the bug that taught us the closure, and what checks it; zig build test-conformance -Drepertoire=… runs the conformance files over the repertoire and says how many cases it was entitled to answer.

The Unicode data

data/ holds five files, byte for byte as published. Three are from unicode.org: allkeys-18.0.0.txt (the DUCET itself), PropList-18.0.0.txt (for Unified_Ideograph, which Table 16 needs and no other file carries) and Blocks-18.0.0.txt (for the two CJK block boundaries that split Table 16's "core" Han from the rest). tools/gen_table.zig turns them into the table at build time; tools/update-ducet.sh is what refreshes them.

The fourth is allkeys_CLDR-49-beta4.txt, CLDR's root collation, from common/uca/allkeys_CLDR.txt in the CLDR repository. It is the same format, so the same generator reads it — the one thing it lacks is the @implicitweights lines, and those are UTS #10's parameterization of Table 16 rather than anything table-specific, so the generator takes them from the DUCET file. It is versioned by CLDR release rather than by Unicode release, which is why it is named differently and why tools/update-ducet.sh does not touch it. It is from CLDR 49 beta 4, the first CLDR built on UCA 18.0.0, which is the Unicode version the rest of data/ has to match; it moves to CLDR 49 itself when that is released.

The fifth is FractionalUCA_radicals-49-beta4.txt, which is the [radical …] lines of common/uca/FractionalUCA.txt from the same CLDR release and nothing else from that file. They are CLDR's Han order, which allkeys_CLDR.txt does not carry; the whole of FractionalUCA.txt is 4.2 MB for the 135 KB that matters, so the extraction — one grep, recorded in the file's own header — is committed instead.

-Dembed-cldr is off by default because of the tests rather than the table: CLDR's conformance files are only distributed inside the CLDR repository, whose release tarball is 66 MB and unpacks to 409 MB. That is a lazy dependency, so an ordinary build neither fetches nor unpacks it, but a default that did would be a rude surprise.

They are committed rather than fetched, which is not the shape the rest of these projects use, and the reason is narrow: Zig's package manager refuses a dependency served as text/plain, and Unicode publishes the DUCET only as a plain text file. zig fetch https://www.unicode.org/Public/18.0.0/uca/allkeys.txt answers error: unrecognized 'Content-Type' header: 'text/plain; charset=utf-8'. There is no archive of it anywhere on unicode.org — UCD.zip does not contain it and CollationTest.zip holds only the tests — and the one git repository that carries a versioned copy is unicode-org/unicodetools, whose tarball is 618 MB.

Two things about the version. A release's UCA data is published twice, and only one of the two places is immutable: Public/UCA/latest/ is whatever is current, while Public/<version>/uca/ is that version for good. The numbered directories under Public/UCA/ are the trap — they stop at 16.0.0, which reads as "17.0.0 has no pinned URL" and is wrong. latest/ moves with every release, which changes CollationTest.zip under a URL whose hash is pinned, so the dependency names Public/18.0.0/uca/CollationTest.zip instead. And the DUCET version must match the Unicode version of uucode's own Unicode Character Database, because step 1 and step 2 reading different releases is the kind of mismatch that surfaces as a handful of failures a hundred thousand lines into the conformance suite. uucode exposes no version constant to assert against, so the two are updated together by hand. The pin is 1fb7343 on uucode's main, which is Zig 0.17.0 and Unicode 18.0.0. What the generator does check is that the three files in data/ agree with each other, and it fails the build if they do not.

Testing

zig build test covers each step against worked examples out of the specification — figure 1's collation element array, figure 3's four levels, section 4.1's Table 12 for variable weighting, section 10.1.3's [.FB40.0020.0002][.CE00.0000.0000] for U+4E00, section 7.2's own discontiguous matching example — plus the case from the issue this started as: Märtens < Möller < Mueller, which the root collation gets right with no tailoring at all.

It also runs a doctest for every public function, the example the API documentation shows beside it. A doctest is written inside the type it documents, so src/root.zig and src/data.zig refer to every declaration from their test blocks; without that, a type's doctests are compiled only if a test happens to use the type.

zig build test-conformance-cldr does the same for the CLDR root collation against CLDR's own four files, which exist because a tailored root orders things differently and so needs its own expectations. It passing is what confirms two things that are easy to get wrong: that the variable-weight test is a band rather than a threshold, since U+FFFE sits below every variable element at primary weight 0x0200 and is not variable; and that reusing DUCET's @implicitweights parameters for CLDR's table is right.

zig build test-conformance is the one that matters. Section 12.2's files are built so that each line sorts at or after the line before it; the runner reads both _SHORT variants, which between them pin both Alternate values, and compares at identical strength. The suite deliberately includes ill-formed strings holding surrogate code points, and section 12.2 permits filtering those lines out — this implementation weights a surrogate as a reserved code point, which is section 10.1.1's second approach, so nothing is filtered.

zig build fuzz runs a loop of this project's own over the properties a collation owes whatever its table says: that comparison is reflexive, antisymmetric and transitive; that a reused Builder agrees with a fresh one, even warmed up on a different string under a different collation; that each strength refines the one below it; that NFD is idempotent; that a string and its NFD produce byte-identical keys; that the code point and UTF-8 entry points, which decode independently, agree; and that order, which compares a level at a time, gives what comparing two whole keys gives — the only check there is on that path, since both conformance suites and the ICU oracle compare keys.

The fourteenth, search-agrees, checks Searcher against a brute-force reading of section 11's definitions: every range between two permitted match edges whose sort key, as the target weighs it, equals the pattern's is a match; the first match that contains no other must be what find returns; and startsWith, endsWith and a maximal match must agree with the same table. For an asymmetric search the table comes instead from section 11.2 read as a search over every way of lining the pattern's elements up with the range's, rather than the searcher's single left-to-right walk; sharp_s_tertiary must give what spelling ß and ẞ as ss and SS gives; and a match the search compared exactly must report no differences at the levels it compared. Its strings come from a short alphabet built to provoke the hard cases — accents, case, punctuation that shifted handling makes ignorable, a contraction and the marks that can sit inside it, Hangul jamo, both sharp s and kana with the voicing mark — since a pattern drawn uniformly almost never occurs in a target at all.

The fifteenth, match-keys-agree, checks match keys over the same alphabet: that two strings have equal match keys exactly when they have equal sort keys, that every key is a whole number of records, and that a match the Searcher finds without boundaries is a hit for findMatchKey. Most of its second strings are made from the first — a copy with characters swapped, alone or with text around it — because two strings drawn apart are seldom equal.

The sixteenth, fuzzy-agrees, checks fuzzy search against the textbook edit-distance table, worked out afresh over the edges the searcher allows: every range within the limit is a candidate, and the match must be one of those overlapping the candidate that ends first, with the fewest edits of them. The reference weighs each string once, whole, and cuts it at the edges, because a character's weight can depend on what is before it — a mark after shifted punctuation weighs nothing there — and the search weighs it in place.

Five of the thirteen collation targets build their strings out of the table's own material rather than out of uniform code points, because uniform code points do not reach the interesting code at all. Only 19 of DUCET's 964 contractions have a non-starter as their second code point, which is what a discontiguous match needs in order to be possible, and reaching one also needs an intruding mark of strictly lower combining class between the halves — three particular values in that order, which independent draws from a million code points never produce. The sharpest of those targets is reordered-marks-agree: two non-starters of different combining class are canonically equivalent either way round, since NFD sorts them the same however they were written, so swapping them must not change the key by a byte. Swapping a mark is exactly what turns a contiguous contraction match into a discontiguous one, so the two strings reach the same answer down two different paths through S2.1.

The driver prints how many inputs reached an assertion beside each total. A target that cannot make sense of its input has to give up, and a target that gives up on nearly everything looks identical to one that is working — both report millions of iterations and no findings. That count is worth reading: it is what showed the generator picking the first entry of every table on half its draws, because std.testing.Smith answers a value outside the range a target asked for with that range's minimum rather than reducing it into range. tools/fuzz.zig spells out that encoding and the rest of the traps in it.

This is a driver of its own rather than zig build test --fuzz. It was written when Zig 0.16.0 could not build a test executable in fuzz mode; Zig 0.17 can, with coverage feedback when LLVM compiles the test binary, but the targets have not been moved onto it.

References cited

• Whistler, K., & Scherer, M. (2026, August 31). Unicode Technical Standard #10: Unicode Collation Algorithm (Version 18.0.0, Revision 55). Unicode Consortium. https://www.unicode.org/reports/tr10/tr10-55.html
• Scherer, M., and other CLDR committee members. Unicode Technical Standard #35: Unicode Locale Data Markup Language (LDML) Part 5: Collation (Version 48.2). Unicode Consortium. https://www.unicode.org/reports/tr35/tr35-collation.html
• Unicode Consortium. (2026, August 25). allkeys.txt: the Default Unicode Collation Element Table (DUCET) (Version 18.0.0). https://www.unicode.org/Public/18.0.0/uca/allkeys.txt
• Unicode Consortium. (2026, August 26). Unicode Common Locale Data Repository (CLDR) (Release 49 beta 4). https://github.com/unicode-org/cldr/releases/tag/release-49-beta4
• Unicode Consortium. ICU: International Components for Unicode (Version 78.3). https://icu.unicode.org/
• Andreev, A., Shardt, Y., & Simmons, N. (2015, November 4). Unicode Technical Note #41: Church Slavonic Typography in Unicode (Version 1). Unicode Consortium. https://www.unicode.org/notes/tn41/

The first is the algorithm this implements, and its section numbers are the ones the source quotes — steps S1.1 through S4.3, the well-formedness conditions, and section 12's conformance tests, which zig build test-conformance runs. The second is the rule syntax the per-locale tailorings are written in, and the authority for how a reset and a relation behave; three attempts to derive the reordering model from the data files failed before reading section 4.7 settled it.

The third and fourth are the data. data/allkeys-18.0.0.txt is a copy of the DUCET, committed because zig fetch will not take a text/plain response; CLDR supplies both its own root collation, which differs from the DUCET and is what ICU orders by, and the 135 locale rule files. The fifth is the oracle: ICU is the reference implementation of CLDR's collation, and since CLDR ships no conformance data for the tailorings it is the only thing that can say whether one of them is right.

The sixth is where one locale's rules come from. Church Slavonic is the awkward one — five settings at once, and ICU has no data for it, so the oracle cannot check it — and its section 5 is the argument behind cu.xml: the diacritical marks sorted at the secondary level starting from &[first secondary ignorable], which is the rule that made this library implement a logical reset position.

All six are in the zig-collate Zotero collection, the technical note with its PDF attached.

Where this lives

$ git clone https://git.jcollie.dev/jeff/zig-collate.git

Mirrored on Tangled at https://tangled.org/jcollie.dev/zig-collate, which is where to report issues and send pull requests. CONTRIBUTING.md says what a change needs to pass.

It is also on Radicle, where a repository is findable only by its ID:

$ rad clone rad:z2CUn5MxFzb4KUWKPuXRj9A62SxuH

The Repository ID is rad:z2CUn5MxFzb4KUWKPuXRj9A62SxuH.

Licence

MIT, and the project follows the REUSE standard — reuse lint passes. The Unicode data files in data/ are Unicode's, under the Unicode licence; see REUSE.toml.