Something went wrong. Try again.
A URI parser and formatter for Zig, modelled on Python's hyperlink package, with LDAP URLs, file: URIs and sdns:// DNS stamps beside it.
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>// 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; // 588const 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(@intFromEnum(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) == @intFromEnum(BuildState.ready)) return;
// Claim the build, or wait for whoever did. if (composites_state.cmpxchgStrong( @intFromEnum(BuildState.uninit), @intFromEnum(BuildState.building), .acquire, .acquire, )) |_| { while (composites_state.load(.acquire) != @intFromEnum(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(@intFromEnum(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);}