From ba5d9081b479e95ffa7f3baf751beedd370cec14 Mon Sep 17 00:00:00 2001
From: Sam Atman
Date: Wed, 4 Feb 2026 18:01:36 -0500
Subject: Normalization and case folding

Both of which deserve some further attention.
---
 src/CaseFolding.zig | 258 ++++++++++++++++++++--------------------------------
 1 file changed, 100 insertions(+), 158 deletions(-)

(limited to 'src/CaseFolding.zig')

diff --git a/src/CaseFolding.zig b/src/CaseFolding.zig
index df86b92..88f047c 100644
--- a/src/CaseFolding.zig
+++ b/src/CaseFolding.zig
@@ -1,113 +1,53 @@
-cutoff: u21 = undefined,
-cwcf_exceptions_min: u21 = undefined,
-cwcf_exceptions_max: u21 = undefined,
-cwcf_exceptions: []u21 = undefined,
-multiple_start: u21 = undefined,
-stage1: []u8 = undefined,
-stage2: []u8 = undefined,
-stage3: []i24 = undefined,
-normalize: Normalize,
-owns_normalize: bool,
-
 const CaseFolding = @This();
 
-pub fn init(allocator: Allocator) Allocator.Error!CaseFolding {
-    var case_fold: CaseFolding = undefined;
-    try case_fold.setup(allocator);
-    return case_fold;
-}
-
-pub fn initWithNormalize(allocator: Allocator, norm: Normalize) Allocator.Error!CaseFolding {
-    var casefold: CaseFolding = undefined;
-    try casefold.setupWithNormalize(allocator, norm);
-    return casefold;
-}
-
-pub fn setup(casefold: *CaseFolding, allocator: Allocator) Allocator.Error!void {
-    try casefold.setupImpl(allocator);
-    // Handle normalize memory separately during setup:
-    casefold.owns_normalize = false;
-    errdefer casefold.deinit(allocator);
-    try casefold.normalize.setup(allocator);
-    casefold.owns_normalize = true;
-}
-
-pub fn setupWithNormalize(casefold: *CaseFolding, allocator: Allocator, norm: Normalize) !void {
-    try casefold.setupImpl(allocator);
-    casefold.normalize = norm;
-    casefold.owns_normalize = false;
-}
-
-fn setupImpl(casefold: *CaseFolding, allocator: Allocator) Allocator.Error!void {
-    casefold.setupImplInner(allocator) catch |err| {
-        switch (err) {
-            error.OutOfMemory => |e| return e,
-            else => unreachable,
-        }
+const Data = struct {
+    cutoff: u21 = undefined,
+    cwcf_exceptions_min: u21 = undefined,
+    cwcf_exceptions_max: u21 = undefined,
+    cwcf_exceptions: []const u21 = undefined,
+    multiple_start: u21 = undefined,
+    stage1: []const u8 = undefined,
+    stage2: []const u8 = undefined,
+    stage3: []const i24 = undefined,
+};
+
+const casefold = casefold: {
+    const data = @import("fold");
+    break :casefold Data{
+        .cutoff = data.cutoff,
+        .multiple_start = data.multiple_start,
+        .stage1 = &data.stage1,
+        .stage2 = &data.stage2,
+        .stage3 = &data.stage3,
+        .cwcf_exceptions_min = data.cwcf_exceptions_min,
+        .cwcf_exceptions_max = data.cwcf_exceptions_max,
+        .cwcf_exceptions = &data.cwcf_exceptions,
     };
-}
-
-inline fn setupImplInner(casefold: *CaseFolding, allocator: Allocator) !void {
-    const in_bytes = @embedFile("fold");
-    var in_fbs = std.io.fixedBufferStream(in_bytes);
-    var reader = in_fbs.reader();
-
-    const endian = builtin.cpu.arch.endian();
-
-    casefold.cutoff = @intCast(try reader.readInt(u24, endian));
-    casefold.multiple_start = @intCast(try reader.readInt(u24, endian));
-
-    var len = try reader.readInt(u16, endian);
-    casefold.stage1 = try allocator.alloc(u8, len);
-    errdefer allocator.free(casefold.stage1);
-    for (0..len) |i| casefold.stage1[i] = try reader.readInt(u8, endian);
-
-    len = try reader.readInt(u16, endian);
-    casefold.stage2 = try allocator.alloc(u8, len);
-    errdefer allocator.free(casefold.stage2);
-    for (0..len) |i| casefold.stage2[i] = try reader.readInt(u8, endian);
-
-    len = try reader.readInt(u16, endian);
-    casefold.stage3 = try allocator.alloc(i24, len);
-    errdefer allocator.free(casefold.stage3);
-    for (0..len) |i| casefold.stage3[i] = try reader.readInt(i24, endian);
-
-    casefold.cwcf_exceptions_min = @intCast(try reader.readInt(u24, endian));
-    casefold.cwcf_exceptions_max = @intCast(try reader.readInt(u24, endian));
-    len = try reader.readInt(u16, endian);
-    casefold.cwcf_exceptions = try allocator.alloc(u21, len);
-    errdefer allocator.free(casefold.cwcf_exceptions);
-    for (0..len) |i| casefold.cwcf_exceptions[i] = @intCast(try reader.readInt(u24, endian));
-}
-
-pub fn deinit(fdata: *const CaseFolding, allocator: mem.Allocator) void {
-    allocator.free(fdata.stage1);
-    allocator.free(fdata.stage2);
-    allocator.free(fdata.stage3);
-    allocator.free(fdata.cwcf_exceptions);
-    if (fdata.owns_normalize) fdata.normalize.deinit(allocator);
-}
+};
 
 /// Returns the case fold for `cp`.
-pub fn caseFold(fdata: *const CaseFolding, cp: u21, buf: []u21) []const u21 {
-    if (cp >= fdata.cutoff) return &.{};
+pub fn caseFold(cp: u21, buf: []u21) []const u21 {
+    // Unmatched code points fold to themselves, so we default to this.
+    buf[0] = cp;
 
-    const stage1_val = fdata.stage1[cp >> 8];
-    if (stage1_val == 0) return &.{};
+    if (cp >= casefold.cutoff) return buf[0..1];
+
+    const stage1_val = casefold.stage1[cp >> 8];
+    if (stage1_val == 0) return buf[0..1];
 
     const stage2_index = @as(usize, stage1_val) * 256 + (cp & 0xFF);
-    const stage3_index = fdata.stage2[stage2_index];
+    const stage3_index = casefold.stage2[stage2_index];
 
     if (stage3_index & 0x80 != 0) {
-        const real_index = @as(usize, fdata.multiple_start) + (stage3_index ^ 0x80) * 3;
-        const mapping = mem.sliceTo(fdata.stage3[real_index..][0..3], 0);
+        const real_index = @as(usize, casefold.multiple_start) + (stage3_index ^ 0x80) * 3;
+        const mapping = mem.sliceTo(casefold.stage3[real_index..][0..3], 0);
         for (mapping, 0..) |c, i| buf[i] = @intCast(c);
 
         return buf[0..mapping.len];
     }
 
-    const offset = fdata.stage3[stage3_index];
-    if (offset == 0) return &.{};
+    const offset = casefold.stage3[stage3_index];
+    if (offset == 0) return buf[0..1];
 
     buf[0] = @intCast(@as(i32, cp) + offset);
 
@@ -117,7 +57,6 @@ pub fn caseFold(fdata: *const CaseFolding, cp: u21, buf: []u21) []const u21 {
 /// Produces the case folded code points for `cps`. Caller must free returned
 /// slice with `allocator`.
 pub fn caseFoldAlloc(
-    casefold: *const CaseFolding,
     allocator: Allocator,
     cps: []const u21,
 ) Allocator.Error![]const u21 {
@@ -126,7 +65,7 @@ pub fn caseFoldAlloc(
     var buf: [3]u21 = undefined;
 
     for (cps) |cp| {
-        const cf = casefold.caseFold(cp, &buf);
+        const cf = CaseFolding.caseFold(cp, &buf);
 
         if (cf.len == 0) {
             try cfcps.append(cp);
@@ -139,19 +78,19 @@ pub fn caseFoldAlloc(
 }
 
 /// Returns true when caseFold(NFD(`cp`)) != NFD(`cp`).
-pub fn cpChangesWhenCaseFolded(casefold: *const CaseFolding, cp: u21) bool {
+pub fn cpChangesWhenCaseFolded(cp: u21) bool {
     var buf: [3]u21 = undefined;
-    const has_mapping = casefold.caseFold(cp, &buf).len != 0;
-    return has_mapping and !casefold.isCwcfException(cp);
+    const has_mapping = CaseFolding.caseFold(cp, &buf).len != 0;
+    return has_mapping and !CaseFolding.isCwcfException(cp);
 }
 
-pub fn changesWhenCaseFolded(casefold: *const CaseFolding, cps: []const u21) bool {
+pub fn changesWhenCaseFolded(cps: []const u21) bool {
     return for (cps) |cp| {
-        if (casefold.cpChangesWhenCaseFolded(cp)) break true;
+        if (CaseFolding.cpChangesWhenCaseFolded(cp)) break true;
     } else false;
 }
 
-fn isCwcfException(casefold: *const CaseFolding, cp: u21) bool {
+fn isCwcfException(cp: u21) bool {
     return cp >= casefold.cwcf_exceptions_min and
         cp <= casefold.cwcf_exceptions_max and
         std.mem.indexOfScalar(u21, casefold.cwcf_exceptions, cp) != null;
@@ -160,88 +99,114 @@ fn isCwcfException(casefold: *const CaseFolding, cp: u21) bool {
 /// Caseless compare `a` and `b` by decomposing to NFKD. This is the most
 /// comprehensive comparison possible, but slower than `canonCaselessMatch`.
 pub fn compatCaselessMatch(
-    casefold: *const CaseFolding,
     allocator: Allocator,
+    normalize: Normalize,
     a: []const u8,
     b: []const u8,
 ) Allocator.Error!bool {
     if (ascii.isAsciiOnly(a) and ascii.isAsciiOnly(b)) return std.ascii.eqlIgnoreCase(a, b);
 
     // Process a
-    const nfd_a = try casefold.normalize.nfxdCodePoints(allocator, a, .nfd);
+    const nfd_a = try normalize.nfxdCodePoints(allocator, a, .nfd);
     defer allocator.free(nfd_a);
 
     var need_free_cf_nfd_a = false;
     var cf_nfd_a: []const u21 = nfd_a;
-    if (casefold.changesWhenCaseFolded(nfd_a)) {
-        cf_nfd_a = try casefold.caseFoldAlloc(allocator, nfd_a);
+    if (CaseFolding.changesWhenCaseFolded(nfd_a)) {
+        cf_nfd_a = try CaseFolding.caseFoldAlloc(allocator, nfd_a);
         need_free_cf_nfd_a = true;
     }
     defer if (need_free_cf_nfd_a) allocator.free(cf_nfd_a);
 
-    const nfkd_cf_nfd_a = try casefold.normalize.nfkdCodePoints(allocator, cf_nfd_a);
+    const nfkd_cf_nfd_a = try normalize.nfkdCodePoints(allocator, cf_nfd_a);
     defer allocator.free(nfkd_cf_nfd_a);
-    const cf_nfkd_cf_nfd_a = try casefold.caseFoldAlloc(allocator, nfkd_cf_nfd_a);
+    const cf_nfkd_cf_nfd_a = try CaseFolding.caseFoldAlloc(allocator, nfkd_cf_nfd_a);
     defer allocator.free(cf_nfkd_cf_nfd_a);
-    const nfkd_cf_nfkd_cf_nfd_a = try casefold.normalize.nfkdCodePoints(allocator, cf_nfkd_cf_nfd_a);
+    const nfkd_cf_nfkd_cf_nfd_a = try normalize.nfkdCodePoints(allocator, cf_nfkd_cf_nfd_a);
     defer allocator.free(nfkd_cf_nfkd_cf_nfd_a);
 
     // Process b
-    const nfd_b = try casefold.normalize.nfxdCodePoints(allocator, b, .nfd);
+    const nfd_b = try normalize.nfxdCodePoints(allocator, b, .nfd);
     defer allocator.free(nfd_b);
 
     var need_free_cf_nfd_b = false;
     var cf_nfd_b: []const u21 = nfd_b;
-    if (casefold.changesWhenCaseFolded(nfd_b)) {
-        cf_nfd_b = try casefold.caseFoldAlloc(allocator, nfd_b);
+    if (CaseFolding.changesWhenCaseFolded(nfd_b)) {
+        cf_nfd_b = try CaseFolding.caseFoldAlloc(allocator, nfd_b);
         need_free_cf_nfd_b = true;
     }
     defer if (need_free_cf_nfd_b) allocator.free(cf_nfd_b);
 
-    const nfkd_cf_nfd_b = try casefold.normalize.nfkdCodePoints(allocator, cf_nfd_b);
+    const nfkd_cf_nfd_b = try normalize.nfkdCodePoints(allocator, cf_nfd_b);
     defer allocator.free(nfkd_cf_nfd_b);
-    const cf_nfkd_cf_nfd_b = try casefold.caseFoldAlloc(allocator, nfkd_cf_nfd_b);
+    const cf_nfkd_cf_nfd_b = try CaseFolding.caseFoldAlloc(allocator, nfkd_cf_nfd_b);
     defer allocator.free(cf_nfkd_cf_nfd_b);
-    const nfkd_cf_nfkd_cf_nfd_b = try casefold.normalize.nfkdCodePoints(allocator, cf_nfkd_cf_nfd_b);
+    const nfkd_cf_nfkd_cf_nfd_b = try normalize.nfkdCodePoints(allocator, cf_nfkd_cf_nfd_b);
     defer allocator.free(nfkd_cf_nfkd_cf_nfd_b);
 
     return mem.eql(u21, nfkd_cf_nfkd_cf_nfd_a, nfkd_cf_nfkd_cf_nfd_b);
 }
 
+test "caseFold" {
+    var buf: [3]u21 = undefined;
+
+    // Folds '1' to '1'
+    try testing.expectEqual(1, caseFold('1', &buf).len);
+    try testing.expectEqual('1', caseFold('1', &buf)[0]);
+
+    // Folds '2' to '2'
+    try testing.expectEqual(1, caseFold('2', &buf).len);
+    try testing.expectEqual('2', caseFold('2', &buf)[0]);
+
+    // Folds Armenian capital letter 'Zhe' (U+053A)
+    try testing.expectEqual(1, caseFold('Ժ', &buf).len);
+    // Armenian small letter 'Zhe' (U+056A)
+    try testing.expectEqual('ժ', caseFold('Ժ', &buf)[0]);
+
+    // Folds Greek small letter Upsilon with Dialytika and Perispomeni (U+1FE7)
+    try testing.expectEqual(3, caseFold('ῧ', &buf).len);
+    // Greek small letter Upsilon (U+03C5)
+    try testing.expectEqual('υ', caseFold('ῧ', &buf)[0]);
+    // Combining Diaeresis
+    try testing.expectEqual('\u{0308}', caseFold('ῧ', &buf)[1]);
+    // Combining Greek Perispomeni
+    try testing.expectEqual('\u{0342}', caseFold('ῧ', &buf)[2]);
+}
+
 test "compatCaselessMatch" {
     const allocator = testing.allocator;
 
-    const caser = try CaseFolding.init(allocator);
-    defer caser.deinit(allocator);
+    var normalize = try Normalize.init(allocator);
+    defer normalize.deinit(allocator);
 
-    try testing.expect(try caser.compatCaselessMatch(allocator, "ascii only!", "ASCII Only!"));
+    try testing.expect(try compatCaselessMatch(allocator, normalize, "ascii only!", "ASCII Only!"));
 
     const a = "Héllo World! \u{3d3}";
     const b = "He\u{301}llo World! \u{3a5}\u{301}";
-    try testing.expect(try caser.compatCaselessMatch(allocator, a, b));
+    try testing.expect(try compatCaselessMatch(allocator, normalize, a, b));
 
     const c = "He\u{301}llo World! \u{3d2}\u{301}";
-    try testing.expect(try caser.compatCaselessMatch(allocator, a, c));
+    try testing.expect(try compatCaselessMatch(allocator, normalize, a, c));
 }
 
 /// Performs canonical caseless string matching by decomposing to NFD. This is
 /// faster than `compatCaselessMatch`, but less comprehensive.
 pub fn canonCaselessMatch(
-    casefold: *const CaseFolding,
     allocator: Allocator,
+    normalize: Normalize,
     a: []const u8,
     b: []const u8,
 ) Allocator.Error!bool {
     if (ascii.isAsciiOnly(a) and ascii.isAsciiOnly(b)) return std.ascii.eqlIgnoreCase(a, b);
 
     // Process a
-    const nfd_a = try casefold.normalize.nfxdCodePoints(allocator, a, .nfd);
+    const nfd_a = try normalize.nfxdCodePoints(allocator, a, .nfd);
     defer allocator.free(nfd_a);
 
     var need_free_cf_nfd_a = false;
     var cf_nfd_a: []const u21 = nfd_a;
-    if (casefold.changesWhenCaseFolded(nfd_a)) {
-        cf_nfd_a = try casefold.caseFoldAlloc(allocator, nfd_a);
+    if (CaseFolding.changesWhenCaseFolded(nfd_a)) {
+        cf_nfd_a = try CaseFolding.caseFoldAlloc(allocator, nfd_a);
         need_free_cf_nfd_a = true;
     }
     defer if (need_free_cf_nfd_a) allocator.free(cf_nfd_a);
@@ -249,19 +214,19 @@ pub fn canonCaselessMatch(
     var need_free_nfd_cf_nfd_a = false;
     var nfd_cf_nfd_a = cf_nfd_a;
     if (!need_free_cf_nfd_a) {
-        nfd_cf_nfd_a = try casefold.normalize.nfdCodePoints(allocator, cf_nfd_a);
+        nfd_cf_nfd_a = try normalize.nfdCodePoints(allocator, cf_nfd_a);
         need_free_nfd_cf_nfd_a = true;
     }
     defer if (need_free_nfd_cf_nfd_a) allocator.free(nfd_cf_nfd_a);
 
     // Process b
-    const nfd_b = try casefold.normalize.nfxdCodePoints(allocator, b, .nfd);
+    const nfd_b = try normalize.nfxdCodePoints(allocator, b, .nfd);
     defer allocator.free(nfd_b);
 
     var need_free_cf_nfd_b = false;
     var cf_nfd_b: []const u21 = nfd_b;
-    if (casefold.changesWhenCaseFolded(nfd_b)) {
-        cf_nfd_b = try casefold.caseFoldAlloc(allocator, nfd_b);
+    if (CaseFolding.changesWhenCaseFolded(nfd_b)) {
+        cf_nfd_b = try CaseFolding.caseFoldAlloc(allocator, nfd_b);
         need_free_cf_nfd_b = true;
     }
     defer if (need_free_cf_nfd_b) allocator.free(cf_nfd_b);
@@ -269,7 +234,7 @@ pub fn canonCaselessMatch(
     var need_free_nfd_cf_nfd_b = false;
     var nfd_cf_nfd_b = cf_nfd_b;
     if (!need_free_cf_nfd_b) {
-        nfd_cf_nfd_b = try casefold.normalize.nfdCodePoints(allocator, cf_nfd_b);
+        nfd_cf_nfd_b = try normalize.nfdCodePoints(allocator, cf_nfd_b);
         need_free_nfd_cf_nfd_b = true;
     }
     defer if (need_free_nfd_cf_nfd_b) allocator.free(nfd_cf_nfd_b);
@@ -280,40 +245,17 @@ pub fn canonCaselessMatch(
 test "canonCaselessMatch" {
     const allocator = testing.allocator;
 
-    const caser = try CaseFolding.init(allocator);
-    defer caser.deinit(allocator);
+    var normalize = try Normalize.init(allocator);
+    defer normalize.deinit(allocator);
 
-    try testing.expect(try caser.canonCaselessMatch(allocator, "ascii only!", "ASCII Only!"));
+    try testing.expect(try canonCaselessMatch(allocator, normalize, "ascii only!", "ASCII Only!"));
 
     const a = "Héllo World! \u{3d3}";
     const b = "He\u{301}llo World! \u{3a5}\u{301}";
-    try testing.expect(!try caser.canonCaselessMatch(allocator, a, b));
+    try testing.expect(!try canonCaselessMatch(allocator, normalize, a, b));
 
     const c = "He\u{301}llo World! \u{3d2}\u{301}";
-    try testing.expect(try caser.canonCaselessMatch(allocator, a, c));
-}
-
-fn testAllocations(allocator: Allocator) !void {
-    // With normalize provided
-    {
-        const normalize = try Normalize.init(allocator);
-        defer normalize.deinit(allocator);
-        const caser = try CaseFolding.initWithNormalize(allocator, normalize);
-        defer caser.deinit(allocator);
-    }
-    // With normalize owned
-    {
-        const caser = try CaseFolding.init(allocator);
-        defer caser.deinit(allocator);
-    }
-}
-
-test "Allocation Failures" {
-    try testing.checkAllAllocationFailures(
-        testing.allocator,
-        testAllocations,
-        .{},
-    );
+    try testing.expect(try canonCaselessMatch(allocator, normalize, a, c));
 }
 
 const std = @import("std");
-- 
cgit v1.2.3