// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie // SPDX-License-Identifier: MIT //! Unicode Normalization Form C, which UTS #46 applies between mapping and //! validation. //! //! The character data comes from uucode; the algorithm (UAX #15 §3) is here: //! canonical decomposition, canonical ordering, then canonical composition. //! Hangul is handled arithmetically, as UAX #15 §10.2 specifies, so it needs //! no table at all. //! //! Composition needs the *inverse* of the decomposition mapping, which uucode //! does not expose directly. It is derived on first use by walking the code //! point space once and inverting every two-character canonical decomposition //! — about a thousand of them. Deriving it from uucode rather than generating //! a table into this repository means it can never disagree with the Unicode //! version uucode was built against. const std = @import("std"); const uucode = @import("uucode"); pub const Error = std.mem.Allocator.Error; // UAX #15 §10.2. const s_base = 0xAC00; const l_base = 0x1100; const v_base = 0x1161; const t_base = 0x11A7; const l_count = 19; const v_count = 21; const t_count = 28; const n_count = v_count * t_count; // 588 const s_count = l_count * n_count; // 11172 /// A primary composite: `starter` + `mark` composes to `composed`. const Composite = struct { starter: u21, mark: u21, composed: u21 }; // Unicode 17 has 1046 primary composites; the slack absorbs future additions // without a code change, and `buildComposites` asserts it was enough. var composite_buf: [2048]Composite = undefined; var composite_len: usize = 0; /// Guards the one-time build. A tiny compare-and-swap state machine rather /// than a mutex, because `std.Io.Mutex` would mean taking an `Io` parameter /// through an API that otherwise needs none. const BuildState = enum(u8) { uninit, building, ready }; var composites_state = std.atomic.Value(u8).init(@backingInt(BuildState.uninit)); fn ccc(cp: u21) u8 { return uucode.get(.canonical_combining_class, cp); } /// The canonical decomposition of `cp`, or null when it has none. fn canonicalDecomposition(cp: u21, buf: *[1]u21) ?[]const u21 { if (uucode.get(.decomposition_type, cp) != .canonical) return null; const m = uucode.get(.decomposition_mapping, cp).with(buf, cp); // A code point that decomposes to itself has no decomposition. if (m.len == 1 and m[0] == cp) return null; return m; } fn buildComposites() void { if (composites_state.load(.acquire) == @backingInt(BuildState.ready)) return; // Claim the build, or wait for whoever did. if (composites_state.cmpxchgStrong( @backingInt(BuildState.uninit), @backingInt(BuildState.building), .acquire, .acquire, )) |_| { while (composites_state.load(.acquire) != @backingInt(BuildState.ready)) { std.atomic.spinLoopHint(); } return; } var n: usize = 0; var buf: [1]u21 = undefined; var cp: u21 = 0; while (cp < 0x110000) : (cp += 1) { if (cp >= 0xD800 and cp <= 0xDFFF) continue; const d = canonicalDecomposition(cp, &buf) orelse continue; if (d.len != 2) continue; // Full_Composition_Exclusion: the listed script-specifics, plus // singletons (excluded by the length check above) and decompositions // that begin with a non-starter. if (uucode.get(.is_composition_exclusion, cp)) continue; if (ccc(d[0]) != 0) continue; std.debug.assert(n < composite_buf.len); composite_buf[n] = .{ .starter = d[0], .mark = d[1], .composed = cp }; n += 1; } std.mem.sort(Composite, composite_buf[0..n], {}, struct { fn lt(_: void, a: Composite, b: Composite) bool { return if (a.starter != b.starter) a.starter < b.starter else a.mark < b.mark; } }.lt); composite_len = n; composites_state.store(@backingInt(BuildState.ready), .release); } /// The primary composite of `starter` and `mark`, if one exists. fn composePair(starter: u21, mark: u21) ?u21 { // Hangul LV and LVT composition is arithmetic (UAX #15 §10.2). if (starter >= l_base and starter < l_base + l_count and mark >= v_base and mark < v_base + v_count) { const l = starter - l_base; const v = mark - v_base; return @intCast(s_base + (l * v_count + v) * t_count); } if (starter >= s_base and starter < s_base + s_count and (starter - s_base) % t_count == 0 and mark > t_base and mark < t_base + t_count) { return @intCast(starter + (mark - t_base)); } buildComposites(); const items = composite_buf[0..composite_len]; var lo: usize = 0; var hi: usize = items.len; while (lo < hi) { const mid = lo + (hi - lo) / 2; const it = items[mid]; if (it.starter < starter or (it.starter == starter and it.mark < mark)) { lo = mid + 1; } else if (it.starter == starter and it.mark == mark) { return it.composed; } else { hi = mid; } } return null; } /// Append the full canonical decomposition of `cp` to `out`. fn decomposeInto(alloc: std.mem.Allocator, out: *std.ArrayList(u21), cp: u21) Error!void { // Hangul syllables decompose arithmetically. if (cp >= s_base and cp < s_base + s_count) { const s = cp - s_base; const l = l_base + s / n_count; const v = v_base + (s % n_count) / t_count; const t = t_base + s % t_count; try out.append(alloc, @intCast(l)); try out.append(alloc, @intCast(v)); if (s % t_count != 0) try out.append(alloc, @intCast(t)); return; } var buf: [1]u21 = undefined; const d = canonicalDecomposition(cp, &buf) orelse { try out.append(alloc, cp); return; }; // Decomposition is recursive: a mapping may itself decompose further. for (d) |part| try decomposeInto(alloc, out, part); } /// Sort each run of combining marks by combining class, stably (UAX #15 §3). fn canonicalOrder(cps: []u21) void { if (cps.len < 2) return; // An insertion sort restricted to non-starters is both the textbook // formulation and inherently stable, which the algorithm requires. var i: usize = 1; while (i < cps.len) : (i += 1) { const c = ccc(cps[i]); if (c == 0) continue; var j = i; while (j > 0) : (j -= 1) { const prev = ccc(cps[j - 1]); if (prev <= c) break; std.mem.swap(u21, &cps[j], &cps[j - 1]); } } } /// Normalize `cps` to NFC. The result is owned by the caller. pub fn nfc(alloc: std.mem.Allocator, cps: []const u21) Error![]u21 { var decomposed: std.ArrayList(u21) = .empty; defer decomposed.deinit(alloc); try decomposed.ensureTotalCapacity(alloc, cps.len); for (cps) |cp| try decomposeInto(alloc, &decomposed, cp); canonicalOrder(decomposed.items); var out: std.ArrayList(u21) = .empty; errdefer out.deinit(alloc); try out.ensureTotalCapacity(alloc, decomposed.items.len); // UAX #15 §3 canonical composition: walk forward holding the most recent // starter, and try to compose each following character into it. var starter_idx: ?usize = null; var last_ccc: u8 = 0; for (decomposed.items) |cp| { const c = ccc(cp); if (starter_idx) |si| { // A character is blocked from the starter if the preceding // character has a combining class >= its own. const blocked = last_ccc != 0 and last_ccc >= c; if (!blocked) { if (composePair(out.items[si], cp)) |composed| { out.items[si] = composed; // last_ccc is unchanged: the composed character replaced // the starter, and this code point is gone. continue; } } } try out.append(alloc, cp); if (c == 0) starter_idx = out.items.len - 1; last_ccc = c; } return out.toOwnedSlice(alloc); } /// Whether `cps` is already in NFC. Cheaper than normalizing and comparing /// only in that it can stop early; it still normalizes. pub fn isNfc(alloc: std.mem.Allocator, cps: []const u21) Error!bool { const n = try nfc(alloc, cps); defer alloc.free(n); return std.mem.eql(u21, cps, n); }