// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie // SPDX-FileCopyrightText: © 2001 Keith Packard // SPDX-License-Identifier: MIT AND HPND-sell-variant //! A set of Unicode codepoints, laid out as fontconfig lays out an //! `FcCharSet`: a sorted list of 256-codepoint pages, each with a 256-bit //! map. //! //! A `CharSet` is immutable once built; `Builder` makes one. The slices are //! owned by whoever built it, usually an arena — the language tables are //! static, and a font's charset lives as long as the scanned font set. const std = @import("std"); const Allocator = std.mem.Allocator; const CharSet = @This(); /// The 256 codepoints of one page, as eight 32-bit words. pub const Leaf = [8]u32; /// The page numbers, `codepoint >> 8`, in increasing order. pages: []const u32 = &.{}, /// One bitmap per page. leaves: []const Leaf = &.{}, pub const empty: CharSet = .{}; /// Builds a `CharSet` one codepoint or range at a time. pub const Builder = struct { pages: std.ArrayList(u32) = .empty, leaves: std.ArrayList(Leaf) = .empty, /// Where `leafFor` last found or put a page. Characters are mostly added /// in order, so the next one is usually on the same page. last: usize = 0, pub fn deinit(b: *Builder, gpa: Allocator) void { b.pages.deinit(gpa); b.leaves.deinit(gpa); } /// Starts from a copy of `cs`. pub fn fromCharSet(gpa: Allocator, cs: CharSet) Allocator.Error!Builder { var b: Builder = .{}; errdefer b.deinit(gpa); try b.pages.appendSlice(gpa, cs.pages); try b.leaves.appendSlice(gpa, cs.leaves); return b; } fn leafFor(b: *Builder, gpa: Allocator, page: u32) Allocator.Error!*Leaf { if (b.last < b.pages.items.len and b.pages.items[b.last] == page) return &b.leaves.items[b.last]; const i = std.sort.lowerBound(u32, b.pages.items, page, orderU32); b.last = i; if (i < b.pages.items.len and b.pages.items[i] == page) return &b.leaves.items[i]; try b.pages.insert(gpa, i, page); try b.leaves.insert(gpa, i, @splat(0)); return &b.leaves.items[i]; } pub fn add(b: *Builder, gpa: Allocator, cp: u32) Allocator.Error!void { const leaf = try b.leafFor(gpa, cp >> 8); leaf[(cp & 0xff) >> 5] |= @as(u32, 1) << @intCast(cp & 31); } pub fn addRange(b: *Builder, gpa: Allocator, first: u32, last: u32) Allocator.Error!void { var cp = first; while (cp <= last) : (cp += 1) { try b.add(gpa, cp); if (cp == std.math.maxInt(u32)) break; } } pub fn hasChar(b: *const Builder, cp: u32) bool { const view: CharSet = .{ .pages = b.pages.items, .leaves = b.leaves.items }; return view.hasChar(cp); } /// `FcCharSetDelChar`. Like fontconfig, an emptied page stays. pub fn remove(b: *Builder, cp: u32) void { const page = cp >> 8; const i = std.sort.lowerBound(u32, b.pages.items, page, orderU32); if (i < b.pages.items.len and b.pages.items[i] == page) b.leaves.items[i][(cp & 0xff) >> 5] &= ~(@as(u32, 1) << @intCast(cp & 31)); } /// Hands the contents over as a `CharSet`, leaving the builder empty. pub fn finish(b: *Builder, gpa: Allocator) Allocator.Error!CharSet { const pages = try b.pages.toOwnedSlice(gpa); errdefer gpa.free(pages); const leaves = try b.leaves.toOwnedSlice(gpa); return .{ .pages = pages, .leaves = leaves }; } }; fn orderU32(a: u32, b: u32) std.math.Order { return std.math.order(a, b); } /// Frees a `CharSet` made by `Builder.finish` or one of the operations here /// with the same allocator. pub fn deinit(cs: CharSet, gpa: Allocator) void { gpa.free(cs.pages); gpa.free(cs.leaves); } pub fn dupe(cs: CharSet, gpa: Allocator) Allocator.Error!CharSet { const pages = try gpa.dupe(u32, cs.pages); errdefer gpa.free(pages); return .{ .pages = pages, .leaves = try gpa.dupe(Leaf, cs.leaves) }; } fn findPage(cs: CharSet, page: u32) ?usize { const i = std.sort.lowerBound(u32, cs.pages, page, orderU32); if (i < cs.pages.len and cs.pages[i] == page) return i; return null; } /// `FcCharSetHasChar`. pub fn hasChar(cs: CharSet, cp: u32) bool { const i = cs.findPage(cp >> 8) orelse return false; return (cs.leaves[i][(cp & 0xff) >> 5] >> @intCast(cp & 31)) & 1 != 0; } /// `FcCharSetCount`. pub fn count(cs: CharSet) u32 { var n: u32 = 0; for (cs.leaves) |leaf| { for (leaf) |word| n += @popCount(word); } return n; } /// `FcCharSetSubtractCount`: how many codepoints of `a` are missing from /// `b`. pub fn subtractCount(a: CharSet, b: CharSet) u32 { var n: u32 = 0; var bi: usize = 0; for (a.pages, a.leaves) |page, leaf| { while (bi < b.pages.len and b.pages[bi] < page) bi += 1; if (bi < b.pages.len and b.pages[bi] == page) { for (leaf, b.leaves[bi]) |aw, bw| n += @popCount(aw & ~bw); } else { for (leaf) |aw| n += @popCount(aw); } } return n; } /// `FcCharSetIntersectCount`. pub fn intersectCount(a: CharSet, b: CharSet) u32 { var n: u32 = 0; var bi: usize = 0; for (a.pages, a.leaves) |page, leaf| { while (bi < b.pages.len and b.pages[bi] < page) bi += 1; if (bi < b.pages.len and b.pages[bi] == page) { for (leaf, b.leaves[bi]) |aw, bw| n += @popCount(aw & bw); } } return n; } /// `FcCharSetIsSubset`: is every codepoint of `a` in `b`? pub fn isSubset(a: CharSet, b: CharSet) bool { if (a.pages.ptr == b.pages.ptr and a.pages.len == b.pages.len and a.leaves.ptr == b.leaves.ptr) return true; var bi: usize = 0; for (a.pages, a.leaves) |page, leaf| { while (bi < b.pages.len and b.pages[bi] < page) bi += 1; if (bi < b.pages.len and b.pages[bi] == page) { for (leaf, b.leaves[bi]) |aw, bw| if (aw & ~bw != 0) return false; } else { // fontconfig compares page numbers, not bits: a page of `a` // missing from `b` fails even when it is empty. return false; } } return true; } /// `FcCharSetEqual`. Pages are compared as they are stored, so an empty /// page in one and none in the other differ, as in fontconfig. pub fn eql(a: CharSet, b: CharSet) bool { if (a.pages.len != b.pages.len) return false; for (a.pages, b.pages, a.leaves, b.leaves) |ap, bp, al, bl| { if (ap != bp) return false; if (!std.mem.eql(u32, &al, &bl)) return false; } return true; } const Op = enum { @"union", subtract }; fn operate(gpa: Allocator, a: CharSet, b: CharSet, op: Op) Allocator.Error!CharSet { var pages: std.ArrayList(u32) = .empty; defer pages.deinit(gpa); var leaves: std.ArrayList(Leaf) = .empty; defer leaves.deinit(gpa); var ai: usize = 0; var bi: usize = 0; while (ai < a.pages.len or bi < b.pages.len) { const take_a = bi >= b.pages.len or (ai < a.pages.len and a.pages[ai] < b.pages[bi]); const take_b = ai >= a.pages.len or (bi < b.pages.len and b.pages[bi] < a.pages[ai]); if (take_a) { try pages.append(gpa, a.pages[ai]); try leaves.append(gpa, a.leaves[ai]); ai += 1; } else if (take_b) { if (op == .@"union") { try pages.append(gpa, b.pages[bi]); try leaves.append(gpa, b.leaves[bi]); } bi += 1; } else { var leaf: Leaf = undefined; for (&leaf, a.leaves[ai], b.leaves[bi]) |*l, aw, bw| l.* = switch (op) { .@"union" => aw | bw, .subtract => aw & ~bw, }; // fontconfig drops a page the operation leaves empty. if (!std.mem.allEqual(u32, &leaf, 0)) { try pages.append(gpa, a.pages[ai]); try leaves.append(gpa, leaf); } ai += 1; bi += 1; } } const out_pages = try pages.toOwnedSlice(gpa); errdefer gpa.free(out_pages); return .{ .pages = out_pages, .leaves = try leaves.toOwnedSlice(gpa) }; } /// `FcCharSetUnion`. pub fn unionWith(gpa: Allocator, a: CharSet, b: CharSet) Allocator.Error!CharSet { return operate(gpa, a, b, .@"union"); } /// `FcCharSetSubtract`. pub fn subtract(gpa: Allocator, a: CharSet, b: CharSet) Allocator.Error!CharSet { return operate(gpa, a, b, .subtract); } /// `FcNameParseCharSet`: whitespace-separated hexadecimal codepoints and /// `first-last` ranges. Returns null if the text does not parse. pub fn parse(gpa: Allocator, text: []const u8) Allocator.Error!?CharSet { var b: Builder = .{}; defer b.deinit(gpa); var s = text; while (s.len > 0) { s = std.mem.trimStart(u8, s, " \t\n\r\x0b\x0c"); // strtol accepts an optional 0x prefix and a sign; an empty number // is a failure to parse. const first = parseHexPrefix(s) orelse return null; s = std.mem.trimStart(u8, s[first.len..], " \t\n\r\x0b\x0c"); var last = first.value; if (s.len > 0 and s[0] == '-') { const l = parseHexPrefix(s[1..]) orelse return null; last = l.value; s = s[1 + l.len ..]; } if (first.value < 0 or last < 0 or last < first.value or last > 0x10ffff) return null; try b.addRange(gpa, @intCast(first.value), @intCast(last)); } return try b.finish(gpa); } fn parseHexPrefix(s: []const u8) ?struct { value: i64, len: usize } { var i: usize = 0; while (i < s.len and std.ascii.isWhitespace(s[i])) i += 1; var negative = false; if (i < s.len and (s[i] == '+' or s[i] == '-')) { negative = s[i] == '-'; i += 1; } if (i + 1 < s.len and s[i] == '0' and (s[i + 1] == 'x' or s[i + 1] == 'X') and i + 2 < s.len and std.ascii.isHex(s[i + 2])) i += 2; const start = i; var v: i64 = 0; while (i < s.len and std.ascii.isHex(s[i])) : (i += 1) { v = v * 16 + (std.fmt.charToDigit(s[i], 16) catch unreachable); if (v > 0x7fffffff) return null; } if (i == start) return null; return .{ .value = if (negative) -v else v, .len = i }; } /// `FcNameUnparseCharSet`: ranges of lowercase hexadecimal, separated by /// spaces. pub fn format(cs: CharSet, w: *std.Io.Writer) std.Io.Writer.Error!void { const none: u32 = 0x7fffffff; var first: u32 = none; var last: u32 = none; for (cs.pages, cs.leaves) |page, leaf| { for (leaf, 0..) |word, i| { var bits = word; var u: u32 = (page << 8) + @as(u32, @intCast(i)) * 32; while (bits != 0) : ({ bits >>= 1; u += 1; }) { if (bits & 1 == 0) continue; if (u != last +% 1) { if (last != first) try w.print("-{x}", .{last}); if (last != none) try w.writeByte(' '); first = u; try w.print("{x}", .{u}); } last = u; } } } if (last != first) try w.print("-{x}", .{last}); } /// Calls `f` with every codepoint in the set, in order. pub fn iterator(cs: CharSet) Iterator { return .{ .cs = cs }; } pub const Iterator = struct { cs: CharSet, page: usize = 0, bit: u32 = 0, pub fn next(it: *Iterator) ?u32 { while (it.page < it.cs.pages.len) { const leaf = it.cs.leaves[it.page]; while (it.bit < 256) { const b = it.bit; it.bit += 1; if ((leaf[b >> 5] >> @intCast(b & 31)) & 1 != 0) return (it.cs.pages[it.page] << 8) | b; } it.page += 1; it.bit = 0; } return null; } }; const testing = std.testing; test "build, query and count" { const gpa = testing.allocator; var b: Builder = .{}; defer b.deinit(gpa); try b.addRange(gpa, 0x20, 0x7e); try b.add(gpa, 0x4e00); const cs = try b.finish(gpa); defer cs.deinit(gpa); try testing.expect(cs.hasChar('A')); try testing.expect(cs.hasChar(0x4e00)); try testing.expect(!cs.hasChar(0x4e01)); try testing.expectEqual(@as(u32, 96), cs.count()); try testing.expectEqual(@as(usize, 2), cs.pages.len); } test "set operations" { const gpa = testing.allocator; const a = (try parse(gpa, "20-7e")).?; defer a.deinit(gpa); const b = (try parse(gpa, "41-5a 4e00")).?; defer b.deinit(gpa); try testing.expect(!b.isSubset(a)); try testing.expectEqual(@as(u32, 1), b.subtractCount(a)); try testing.expectEqual(@as(u32, 26), b.intersectCount(a)); const u = try unionWith(gpa, a, b); defer u.deinit(gpa); try testing.expect(b.isSubset(u)); try testing.expectEqual(@as(u32, 96), u.count()); const d = try subtract(gpa, u, a); defer d.deinit(gpa); try testing.expectEqual(@as(u32, 1), d.count()); try testing.expect(d.hasChar(0x4e00)); } test "parse and format round trip" { const gpa = testing.allocator; const cs = (try parse(gpa, " 20-7e a0 100-17f 4e00")).?; defer cs.deinit(gpa); var out: std.Io.Writer.Allocating = .init(gpa); defer out.deinit(); try cs.format(&out.writer); try testing.expectEqualStrings("20-7e a0 100-17f 4e00", out.written()); try testing.expectEqual(@as(?CharSet, null), try parse(gpa, "7e-20")); try testing.expectEqual(@as(?CharSet, null), try parse(gpa, "zz")); }