// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>
// 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"));
}