From 312ca415bb01212a320acacda743896ed59a7b82 Mon Sep 17 00:00:00 2001 From: Sam Atman Date: Wed, 30 Apr 2025 15:23:14 -0400 Subject: Remove FoldData, make CaseFolding CaseFolding now has the FoldData, and can be initialized with a copy of Normalize if wanted. --- src/CanonData.zig | 14 +-- src/CaseFold.zig | 256 +++++++++++++++++++++++++++++++++++++++++------------- src/FoldData.zig | 99 --------------------- src/Normalize.zig | 16 +++- 4 files changed, 218 insertions(+), 167 deletions(-) delete mode 100644 src/FoldData.zig (limited to 'src') diff --git a/src/CanonData.zig b/src/CanonData.zig index c67d1d6..d95a5be 100644 --- a/src/CanonData.zig +++ b/src/CanonData.zig @@ -17,11 +17,11 @@ pub fn init(allocator: mem.Allocator) !CanonData { .nfc = .empty, .nfd = try allocator.alloc([]u21, 0x110000), }; + var _cp: u24 = undefined; - var slices: usize = 0; errdefer { cdata.nfc.deinit(allocator); - for (cdata.nfd[0..slices]) |slice| allocator.free(slice); + for (cdata.nfd[0.._cp]) |slice| allocator.free(slice); allocator.free(cdata.nfd); } @@ -31,14 +31,16 @@ pub fn init(allocator: mem.Allocator) !CanonData { const len: u8 = try reader.readInt(u8, endian); if (len == 0) break; const cp = try reader.readInt(u24, endian); - cdata.nfd[cp] = try allocator.alloc(u21, len - 1); - slices += 1; + _cp = cp; + const nfd_cp = try allocator.alloc(u21, len - 1); + errdefer allocator.free(nfd_cp); for (0..len - 1) |i| { - cdata.nfd[cp][i] = @intCast(try reader.readInt(u24, endian)); + nfd_cp[i] = @intCast(try reader.readInt(u24, endian)); } if (len == 3) { - try cdata.nfc.put(allocator, cdata.nfd[cp][0..2].*, @intCast(cp)); + try cdata.nfc.put(allocator, nfd_cp[0..2].*, @intCast(cp)); } + cdata.nfd[cp] = nfd_cp; } return cdata; diff --git a/src/CaseFold.zig b/src/CaseFold.zig index 6490aea..162e82f 100644 --- a/src/CaseFold.zig +++ b/src/CaseFold.zig @@ -1,28 +1,124 @@ -const std = @import("std"); -const mem = std.mem; -const testing = std.testing; +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) !CaseFolding { + var case_fold: CaseFolding = undefined; + try case_fold.setup(allocator); + return case_fold; +} -const ascii = @import("ascii"); -pub const FoldData = @import("FoldData"); -const Normalize = @import("Normalize"); +pub fn initWithNormalize(allocator: Allocator, norm: Normalize) !CaseFolding { + var casefold: CaseFolding = undefined; + try casefold.setupWithNormalize(allocator, norm); + return casefold; +} + +pub fn setup(casefold: *CaseFolding, allocator: Allocator) !void { + try casefold.setupImpl(allocator); + 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; +} -fold_data: *const FoldData, +fn setupImpl(casefold: *CaseFolding, allocator: Allocator) !void { + const decompressor = compress.flate.inflate.decompressor; + const in_bytes = @embedFile("fold"); + var in_fbs = std.io.fixedBufferStream(in_bytes); + var in_decomp = decompressor(.raw, in_fbs.reader()); + var reader = in_decomp.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 &.{}; + + const stage1_val = fdata.stage1[cp >> 8]; + if (stage1_val == 0) return &.{}; + + const stage2_index = @as(usize, stage1_val) * 256 + (cp & 0xFF); + const stage3_index = fdata.stage2[stage2_index]; -const Self = @This(); + 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); + for (mapping, 0..) |c, i| buf[i] = @intCast(c); + + return buf[0..mapping.len]; + } + + const offset = fdata.stage3[stage3_index]; + if (offset == 0) return &.{}; + + buf[0] = @intCast(@as(i32, cp) + offset); + + return buf[0..1]; +} /// Produces the case folded code points for `cps`. Caller must free returned /// slice with `allocator`. -pub fn caseFold( - self: Self, - allocator: mem.Allocator, +pub fn caseFoldAlloc( + casefold: *const CaseFolding, + allocator: Allocator, cps: []const u21, -) ![]const u21 { +) Allocator.Error![]const u21 { var cfcps = std.ArrayList(u21).init(allocator); defer cfcps.deinit(); var buf: [3]u21 = undefined; for (cps) |cp| { - const cf = self.fold_data.caseFold(cp, &buf); + const cf = casefold.caseFold(cp, &buf); if (cf.len == 0) { try cfcps.append(cp); @@ -34,59 +130,71 @@ pub fn caseFold( return try cfcps.toOwnedSlice(); } -fn changesWhenCaseFolded(self: Self, cps: []const u21) bool { +/// Returns true when caseFold(NFD(`cp`)) != NFD(`cp`). +pub fn cpChangesWhenCaseFolded(casefold: *const CaseFolding, cp: u21) bool { + var buf: [3]u21 = undefined; + const has_mapping = casefold.caseFold(cp, &buf).len != 0; + return has_mapping and !casefold.isCwcfException(cp); +} + +pub fn changesWhenCaseFolded(casefold: *const CaseFolding, cps: []const u21) bool { return for (cps) |cp| { - if (self.fold_data.changesWhenCaseFolded(cp)) break true; + if (casefold.cpChangesWhenCaseFolded(cp)) break true; } else false; } +fn isCwcfException(casefold: *const CaseFolding, 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; +} + /// Caseless compare `a` and `b` by decomposing to NFKD. This is the most /// comprehensive comparison possible, but slower than `canonCaselessMatch`. pub fn compatCaselessMatch( - self: Self, - allocator: mem.Allocator, - normalizer: *const Normalize, + casefold: *const CaseFolding, + allocator: Allocator, a: []const u8, b: []const u8, -) !bool { +) Allocator.Error!bool { if (ascii.isAsciiOnly(a) and ascii.isAsciiOnly(b)) return std.ascii.eqlIgnoreCase(a, b); // Process a - const nfd_a = try normalizer.nfxdCodePoints(allocator, a, .nfd); + const nfd_a = try casefold.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 (self.changesWhenCaseFolded(nfd_a)) { - cf_nfd_a = try self.caseFold(allocator, nfd_a); + if (casefold.changesWhenCaseFolded(nfd_a)) { + cf_nfd_a = try casefold.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 normalizer.nfkdCodePoints(allocator, cf_nfd_a); + const nfkd_cf_nfd_a = try casefold.normalize.nfkdCodePoints(allocator, cf_nfd_a); defer allocator.free(nfkd_cf_nfd_a); - const cf_nfkd_cf_nfd_a = try self.caseFold(allocator, nfkd_cf_nfd_a); + const cf_nfkd_cf_nfd_a = try casefold.caseFoldAlloc(allocator, nfkd_cf_nfd_a); defer allocator.free(cf_nfkd_cf_nfd_a); - const nfkd_cf_nfkd_cf_nfd_a = try normalizer.nfkdCodePoints(allocator, cf_nfkd_cf_nfd_a); + const nfkd_cf_nfkd_cf_nfd_a = try casefold.normalize.nfkdCodePoints(allocator, cf_nfkd_cf_nfd_a); defer allocator.free(nfkd_cf_nfkd_cf_nfd_a); // Process b - const nfd_b = try normalizer.nfxdCodePoints(allocator, b, .nfd); + const nfd_b = try casefold.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 (self.changesWhenCaseFolded(nfd_b)) { - cf_nfd_b = try self.caseFold(allocator, nfd_b); + if (casefold.changesWhenCaseFolded(nfd_b)) { + cf_nfd_b = try casefold.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 normalizer.nfkdCodePoints(allocator, cf_nfd_b); + const nfkd_cf_nfd_b = try casefold.normalize.nfkdCodePoints(allocator, cf_nfd_b); defer allocator.free(nfkd_cf_nfd_b); - const cf_nfkd_cf_nfd_b = try self.caseFold(allocator, nfkd_cf_nfd_b); + const cf_nfkd_cf_nfd_b = try casefold.caseFoldAlloc(allocator, nfkd_cf_nfd_b); defer allocator.free(cf_nfkd_cf_nfd_b); - const nfkd_cf_nfkd_cf_nfd_b = try normalizer.nfkdCodePoints(allocator, cf_nfkd_cf_nfd_b); + const nfkd_cf_nfkd_cf_nfd_b = try casefold.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); @@ -95,42 +203,37 @@ pub fn compatCaselessMatch( test "compatCaselessMatch" { const allocator = testing.allocator; - const n = try Normalize.init(allocator); - defer n.deinit(allocator); + const caser = try CaseFolding.init(allocator); + defer caser.deinit(allocator); - const fold_data = try FoldData.init(allocator); - defer fold_data.deinit(allocator); - const caser = Self{ .fold_data = &fold_data }; - - try testing.expect(try caser.compatCaselessMatch(allocator, &n, "ascii only!", "ASCII Only!")); + try testing.expect(try caser.compatCaselessMatch(allocator, "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, &n, a, b)); + try testing.expect(try caser.compatCaselessMatch(allocator, a, b)); const c = "He\u{301}llo World! \u{3d2}\u{301}"; - try testing.expect(try caser.compatCaselessMatch(allocator, &n, a, c)); + try testing.expect(try caser.compatCaselessMatch(allocator, a, c)); } /// Performs canonical caseless string matching by decomposing to NFD. This is /// faster than `compatCaselessMatch`, but less comprehensive. pub fn canonCaselessMatch( - self: Self, - allocator: mem.Allocator, - normalizer: *const Normalize, + casefold: *const CaseFolding, + allocator: Allocator, a: []const u8, b: []const u8, -) !bool { +) Allocator.Error!bool { if (ascii.isAsciiOnly(a) and ascii.isAsciiOnly(b)) return std.ascii.eqlIgnoreCase(a, b); // Process a - const nfd_a = try normalizer.nfxdCodePoints(allocator, a, .nfd); + const nfd_a = try casefold.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 (self.changesWhenCaseFolded(nfd_a)) { - cf_nfd_a = try self.caseFold(allocator, nfd_a); + if (casefold.changesWhenCaseFolded(nfd_a)) { + cf_nfd_a = try casefold.caseFoldAlloc(allocator, nfd_a); need_free_cf_nfd_a = true; } defer if (need_free_cf_nfd_a) allocator.free(cf_nfd_a); @@ -138,19 +241,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 normalizer.nfdCodePoints(allocator, cf_nfd_a); + nfd_cf_nfd_a = try casefold.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 normalizer.nfxdCodePoints(allocator, b, .nfd); + const nfd_b = try casefold.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 (self.changesWhenCaseFolded(nfd_b)) { - cf_nfd_b = try self.caseFold(allocator, nfd_b); + if (casefold.changesWhenCaseFolded(nfd_b)) { + cf_nfd_b = try casefold.caseFoldAlloc(allocator, nfd_b); need_free_cf_nfd_b = true; } defer if (need_free_cf_nfd_b) allocator.free(cf_nfd_b); @@ -158,7 +261,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 normalizer.nfdCodePoints(allocator, cf_nfd_b); + nfd_cf_nfd_b = try casefold.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); @@ -169,19 +272,50 @@ pub fn canonCaselessMatch( test "canonCaselessMatch" { const allocator = testing.allocator; - const n = try Normalize.init(allocator); - defer n.deinit(allocator); - - const fold_data = try FoldData.init(allocator); - defer fold_data.deinit(allocator); - const caser = Self{ .fold_data = &fold_data }; + const caser = try CaseFolding.init(allocator); + defer caser.deinit(allocator); - try testing.expect(try caser.canonCaselessMatch(allocator, &n, "ascii only!", "ASCII Only!")); + try testing.expect(try caser.canonCaselessMatch(allocator, "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, &n, a, b)); + try testing.expect(!try caser.canonCaselessMatch(allocator, a, b)); const c = "He\u{301}llo World! \u{3d2}\u{301}"; - try testing.expect(try caser.canonCaselessMatch(allocator, &n, a, c)); + 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 caser1 = try CaseFolding.initWithNormalize(allocator, normalize); + defer caser1.deinit(allocator); + } + // With normalize owned + { + const caser2 = try CaseFolding.init(allocator); + defer caser2.deinit(allocator); + } +} + +// test "Allocation Failures" { +// if (true) return error.SkipZigTest; // XXX: remove +// try testing.checkAllAllocationFailures( +// testing.allocator, +// testAllocations, +// .{}, +// ); +// } + +const std = @import("std"); +const builtin = @import("builtin"); +const mem = std.mem; +const testing = std.testing; +const Allocator = mem.Allocator; + +const ascii = @import("ascii"); +const Normalize = @import("Normalize"); + +const compress = std.compress; diff --git a/src/FoldData.zig b/src/FoldData.zig deleted file mode 100644 index b7fdceb..0000000 --- a/src/FoldData.zig +++ /dev/null @@ -1,99 +0,0 @@ -const std = @import("std"); -const builtin = @import("builtin"); -const compress = std.compress; -const mem = std.mem; - -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, - -const FoldData = @This(); - -pub fn init(allocator: mem.Allocator) !FoldData { - const decompressor = compress.flate.inflate.decompressor; - const in_bytes = @embedFile("fold"); - var in_fbs = std.io.fixedBufferStream(in_bytes); - var in_decomp = decompressor(.raw, in_fbs.reader()); - var reader = in_decomp.reader(); - - const endian = builtin.cpu.arch.endian(); - - var fdata = FoldData{}; - fdata.cutoff = @intCast(try reader.readInt(u24, endian)); - fdata.multiple_start = @intCast(try reader.readInt(u24, endian)); - - var len = try reader.readInt(u16, endian); - fdata.stage1 = try allocator.alloc(u8, len); - errdefer allocator.free(fdata.stage1); - for (0..len) |i| fdata.stage1[i] = try reader.readInt(u8, endian); - - len = try reader.readInt(u16, endian); - fdata.stage2 = try allocator.alloc(u8, len); - errdefer allocator.free(fdata.stage2); - for (0..len) |i| fdata.stage2[i] = try reader.readInt(u8, endian); - - len = try reader.readInt(u16, endian); - fdata.stage3 = try allocator.alloc(i24, len); - errdefer allocator.free(fdata.stage3); - for (0..len) |i| fdata.stage3[i] = try reader.readInt(i24, endian); - - fdata.cwcf_exceptions_min = @intCast(try reader.readInt(u24, endian)); - fdata.cwcf_exceptions_max = @intCast(try reader.readInt(u24, endian)); - len = try reader.readInt(u16, endian); - fdata.cwcf_exceptions = try allocator.alloc(u21, len); - errdefer allocator.free(fdata.cwcf_exceptions); - for (0..len) |i| fdata.cwcf_exceptions[i] = @intCast(try reader.readInt(u24, endian)); - - return fdata; -} - -pub fn deinit(fdata: *const FoldData, allocator: mem.Allocator) void { - allocator.free(fdata.stage1); - allocator.free(fdata.stage2); - allocator.free(fdata.stage3); - allocator.free(fdata.cwcf_exceptions); -} - -/// Returns the case fold for `cp`. -pub fn caseFold(fdata: *const FoldData, cp: u21, buf: []u21) []const u21 { - if (cp >= fdata.cutoff) return &.{}; - - const stage1_val = fdata.stage1[cp >> 8]; - if (stage1_val == 0) return &.{}; - - const stage2_index = @as(usize, stage1_val) * 256 + (cp & 0xFF); - const stage3_index = fdata.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); - for (mapping, 0..) |c, i| buf[i] = @intCast(c); - - return buf[0..mapping.len]; - } - - const offset = fdata.stage3[stage3_index]; - if (offset == 0) return &.{}; - - buf[0] = @intCast(@as(i32, cp) + offset); - - return buf[0..1]; -} - -/// Returns true when caseFold(NFD(`cp`)) != NFD(`cp`). -pub fn changesWhenCaseFolded(fdata: *const FoldData, cp: u21) bool { - var buf: [3]u21 = undefined; - const has_mapping = fdata.caseFold(cp, &buf).len != 0; - return has_mapping and !fdata.isCwcfException(cp); -} - -fn isCwcfException(fdata: *const FoldData, cp: u21) bool { - return cp >= fdata.cwcf_exceptions_min and - cp <= fdata.cwcf_exceptions_max and - std.mem.indexOfScalar(u21, fdata.cwcf_exceptions, cp) != null; -} diff --git a/src/Normalize.zig b/src/Normalize.zig index 4f014cf..d8c867d 100644 --- a/src/Normalize.zig +++ b/src/Normalize.zig @@ -632,6 +632,21 @@ test "isLatin1Only" { try testing.expect(!isLatin1Only(not_latin1_only)); } +// NOTE: These tests take way waaaaay too long to run, because +// the amount of allocations in a couple of the inflators is +// completely excessive and is also costing memory for metadata. +// I'm leaving this here for when I fix that. +// +// fn testAllocations(allocator: Allocator) !void { +// const norm = try Normalize.init(allocator); +// norm.deinit(allocator); +// } +// +// test "allocation failures" { +// if (true) return error.SkipZigTest; +// try testing.checkAllAllocationFailures(testing.allocator, testAllocations, .{}); +// } + const std = @import("std"); const debug = std.debug; const assert = debug.assert; @@ -649,6 +664,5 @@ const CodePointIterator = @import("code_point").Iterator; const CanonData = @import("CanonData"); const CccData = @import("CombiningData"); const CompatData = @import("CompatData"); -const FoldData = @import("FoldData"); const HangulData = @import("HangulData"); const NormPropsData = @import("NormPropsData"); -- cgit v1.2.3