// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>
// SPDX-FileCopyrightText: © 2000 Keith Packard
// SPDX-License-Identifier: MIT AND HPND-sell-variant

//! A pattern, fontconfig's `FcPattern`: a set of objects, each with an
//! ordered list of values, and each value bound weakly or strongly.
//!
//! Patterns are both the questions and the answers. A query is a pattern
//! saying what is wanted; every font is a pattern saying what it is; a
//! match is the font's pattern with the query's other wishes merged in.
//!
//! Everything a pattern holds is allocated in its own arena, so editing one
//! never frees anything and a value read out of it stays valid as long as
//! the pattern does. A value may also *borrow* memory that outlives the
//! pattern — the configuration's expressions, or a scanned font's charset —
//! which is how a match result avoids copying a font's charset; such a
//! result is valid only as long as the `Config` it came from.

const std = @import("std");
const Allocator = std.mem.Allocator;
const object = @import("object.zig");
const value = @import("value.zig");
const Object = object.Object;
const Builtin = object.Builtin;
const Value = value.Value;

const Pattern = @This();

arena: std.heap.ArenaAllocator,
/// Sorted by object, as `Object.order` orders them.
elts: std.ArrayList(*Elt) = .empty,

/// How strongly a value holds: a strong value of a query outranks
/// differences that a weak one does not. `same` takes the binding of the
/// value it is placed next to, and is only seen while editing.
pub const Binding = enum { weak, strong, same };

pub const ValueList = struct {
    next: ?*ValueList = null,
    value: Value,
    binding: Binding,

    pub fn iterator(l: ?*ValueList) Iterator {
        return .{ .cur = l };
    }
};

pub const Iterator = struct {
    cur: ?*ValueList,

    pub fn next(it: *Iterator) ?*ValueList {
        const c = it.cur orelse return null;
        it.cur = c.next;
        return c;
    }
};

pub const Elt = struct {
    object: Object,
    values: ?*ValueList = null,

    pub fn iterator(e: *const Elt) Iterator {
        return .{ .cur = e.values };
    }

    pub fn count(e: *const Elt) usize {
        var n: usize = 0;
        var it = e.iterator();
        while (it.next()) |_| n += 1;
        return n;
    }
};

pub fn init(gpa: Allocator) Pattern {
    return .{ .arena = .init(gpa) };
}

pub fn deinit(p: *Pattern) void {
    p.arena.deinit();
    p.* = undefined;
}

/// The allocator everything in the pattern is allocated with.
/// Makes room for about `bytes` in the pattern's arena with one allocation,
/// rather than the many it would grow by one value at a time. A pattern
/// built in one go whose size is known roughly — one read from the cache —
/// is worth this, most of all in a Debug build, where the backing allocator
/// records a stack trace for every allocation it makes.
pub fn preheat(p: *Pattern, bytes: usize) Allocator.Error!void {
    if (bytes == 0) return;
    const a = p.allocator();
    // Freeing an arena's last allocation gives the room back to the arena
    // and keeps it, which is the whole point.
    a.free(try a.alloc(u8, bytes));
}

pub fn allocator(p: *Pattern) Allocator {
    return p.arena.allocator();
}

fn position(p: *const Pattern, o: Object) union(enum) { found: usize, insert: usize } {
    var low: usize = 0;
    var high: usize = p.elts.items.len;
    while (low < high) {
        const mid = (low + high) / 2;
        switch (p.elts.items[mid].object.order(o)) {
            .eq => return .{ .found = mid },
            .lt => low = mid + 1,
            .gt => high = mid,
        }
    }
    return .{ .insert = low };
}

/// `FcPatternObjectFindElt`.
pub fn find(p: *const Pattern, o: Object) ?*Elt {
    return switch (p.position(o)) {
        .found => |i| p.elts.items[i],
        .insert => null,
    };
}

pub fn findBuiltin(p: *const Pattern, b: Builtin) ?*Elt {
    return p.find(.{ .builtin = b });
}

/// `FcPatternObjectInsertElt`: the element for `o`, made empty if there
/// was none.
pub fn insertElt(p: *Pattern, o: Object) Allocator.Error!*Elt {
    switch (p.position(o)) {
        .found => |i| return p.elts.items[i],
        .insert => |i| {
            const a = p.allocator();
            const e = try a.create(Elt);
            e.* = .{ .object = switch (o) {
                .builtin => o,
                .custom => |n| .{ .custom = try a.dupe(u8, n) },
            } };
            try p.elts.insert(a, i, e);
            return e;
        },
    }
}

/// `FcPatternObjectDel`: removes every value of `o`. Returns whether there
/// were any.
pub fn del(p: *Pattern, o: Object) bool {
    switch (p.position(o)) {
        .found => |i| {
            _ = p.elts.orderedRemove(i);
            return true;
        },
        .insert => return false,
    }
}

/// `FcPatternObjectAddWithBinding`: adds a copy of `v` to the front or the
/// back of `o`'s values. A void value, or one of the wrong type for a
/// builtin object, is refused and `false` returned, as fontconfig refuses
/// it.
pub fn addWithBinding(p: *Pattern, o: Object, v: Value, binding: Binding, append: bool) Allocator.Error!bool {
    return p.addInternal(o, try v.dupe(p.allocator()), binding, append);
}

/// Like `addWithBinding`, without copying: `v` must outlive the pattern.
pub fn addBorrowed(p: *Pattern, o: Object, v: Value, binding: Binding, append: bool) Allocator.Error!bool {
    return p.addInternal(o, v, binding, append);
}

fn addInternal(p: *Pattern, o: Object, v: Value, binding: Binding, append: bool) Allocator.Error!bool {
    if (v == .void) return false;
    if (!o.acceptsType(v.typ())) return false;
    const e = try p.insertElt(o);
    const node = try p.allocator().create(ValueList);
    node.* = .{ .value = v, .binding = binding };
    if (append) {
        var prev = &e.values;
        while (prev.*) |n| prev = &n.next;
        prev.* = node;
    } else {
        node.next = e.values;
        e.values = node;
    }
    return true;
}

/// `FcPatternAdd`: a strongly bound copy of `v`, at the back.
pub fn add(p: *Pattern, o: Object, v: Value) Allocator.Error!bool {
    return p.addWithBinding(o, v, .strong, true);
}

pub fn addBuiltin(p: *Pattern, b: Builtin, v: Value) Allocator.Error!bool {
    return p.add(.{ .builtin = b }, v);
}

pub fn addInteger(p: *Pattern, b: Builtin, i: i32) Allocator.Error!void {
    _ = try p.add(.{ .builtin = b }, .{ .integer = i });
}

pub fn addDouble(p: *Pattern, b: Builtin, d: f64) Allocator.Error!void {
    _ = try p.add(.{ .builtin = b }, .{ .double = d });
}

pub fn addString(p: *Pattern, b: Builtin, s: []const u8) Allocator.Error!void {
    _ = try p.add(.{ .builtin = b }, .{ .string = s });
}

pub fn addBool(p: *Pattern, b: Builtin, v: bool) Allocator.Error!void {
    _ = try p.add(.{ .builtin = b }, .{ .bool = .from(v) });
}

pub fn addRange(p: *Pattern, b: Builtin, begin: f64, end: f64) Allocator.Error!void {
    _ = try p.add(.{ .builtin = b }, .{ .range = .{ .begin = begin, .end = end } });
}

/// `FcPatternObjectListAdd`: links a list of values in, refusing all of
/// them if any has the wrong type.
pub fn addList(p: *Pattern, o: Object, list: ?*ValueList, append: bool) Allocator.Error!bool {
    var it = ValueList.iterator(list);
    while (it.next()) |l| if (!o.acceptsType(l.value.typ())) return false;
    const head = list orelse return true;
    const e = try p.insertElt(o);
    if (append) {
        var prev = &e.values;
        while (prev.*) |n| prev = &n.next;
        prev.* = head;
    } else {
        var last = head;
        while (last.next) |n| last = n;
        last.next = e.values;
        e.values = head;
    }
    return true;
}

/// `FcPatternObjectGet`: the `n`th value of `o`.
pub fn get(p: *const Pattern, o: Object, n: usize) ?Value {
    const l = p.getList(o, n) orelse return null;
    return l.value;
}

pub fn getList(p: *const Pattern, o: Object, n: usize) ?*ValueList {
    const e = p.find(o) orelse return null;
    var it = e.iterator();
    var i: usize = 0;
    while (it.next()) |l| : (i += 1) {
        if (i == n) return l;
    }
    return null;
}

pub fn getBuiltin(p: *const Pattern, b: Builtin, n: usize) ?Value {
    return p.get(.{ .builtin = b }, n);
}

/// `FcPatternObjectGetString`: the `n`th value of `b` if it is a string.
pub fn getString(p: *const Pattern, b: Builtin, n: usize) ?[]const u8 {
    const v = p.getBuiltin(b, n) orelse return null;
    return switch (v) {
        .string => |s| s,
        else => null,
    };
}

/// `FcPatternObjectGetInteger`: an integer, or a double truncated to one.
pub fn getInteger(p: *const Pattern, b: Builtin, n: usize) ?i32 {
    const v = p.getBuiltin(b, n) orelse return null;
    return switch (v) {
        .integer => |i| i,
        .double => |d| if (std.math.isFinite(d)) std.math.lossyCast(i32, d) else null,
        else => null,
    };
}

/// `FcPatternObjectGetDouble`: a double, or an integer as one.
pub fn getDouble(p: *const Pattern, b: Builtin, n: usize) ?f64 {
    const v = p.getBuiltin(b, n) orelse return null;
    return switch (v) {
        .double => |d| d,
        .integer => |i| @floatFromInt(i),
        else => null,
    };
}

/// `FcPatternObjectGetBool`.
pub fn getBool(p: *const Pattern, b: Builtin, n: usize) ?value.Bool {
    const v = p.getBuiltin(b, n) orelse return null;
    return switch (v) {
        .bool => |x| x,
        else => null,
    };
}

/// `FcPatternDuplicate`: a deep copy, sharing nothing with `p` except what
/// `p` itself borrowed.
pub fn duplicate(p: *const Pattern, gpa: Allocator) Allocator.Error!Pattern {
    var out: Pattern = .init(gpa);
    errdefer out.deinit();
    for (p.elts.items) |e| {
        var it = e.iterator();
        while (it.next()) |l| _ = try out.addBorrowed(e.object, l.value, l.binding, true);
    }
    // The values were borrowed from `p`; give the copy its own.
    for (out.elts.items) |e| {
        var it = e.iterator();
        while (it.next()) |l| l.value = try l.value.dupe(out.allocator());
    }
    return out;
}

/// `FcPatternEqual`: the same objects, with equal values in the same order.
pub fn eql(a: *const Pattern, b: *const Pattern) bool {
    if (a.elts.items.len != b.elts.items.len) return false;
    for (a.elts.items, b.elts.items) |ea, eb| {
        if (!ea.object.eql(eb.object)) return false;
        var ia = ea.iterator();
        var ib = eb.iterator();
        while (true) {
            const la = ia.next();
            const lb = ib.next();
            if (la == null and lb == null) break;
            if (la == null or lb == null) return false;
            if (!la.?.value.eql(lb.?.value)) return false;
        }
    }
    return true;
}

pub fn count(p: *const Pattern) usize {
    return p.elts.items.len;
}

const escape_fixed = "\\-:,";
const escape_variable = "\\=_:,";

/// `FcNameUnparse`: the pattern as a font name, `Family-size:object=value`.
pub fn format(p: *const Pattern, w: *std.Io.Writer) std.Io.Writer.Error!void {
    return p.unparse(w, true);
}

/// `FcNameUnparseEscaped`.
pub fn unparse(p: *const Pattern, w: *std.Io.Writer, escape: bool) std.Io.Writer.Error!void {
    if (p.findBuiltin(.family)) |e| try unparseList(w, e, if (escape) escape_fixed else null);
    if (p.findBuiltin(.size)) |e| {
        // fontconfig writes the size only when its list came out
        // non-empty.
        var buf: [256]u8 = undefined;
        var sw: std.Io.Writer = .fixed(&buf);
        unparseList(&sw, e, if (escape) escape_fixed else null) catch {};
        if (sw.buffered().len > 0) {
            try w.writeByte('-');
            try w.writeAll(sw.buffered());
        }
    }
    for (p.elts.items) |e| {
        const b = switch (e.object) {
            .builtin => |b| b,
            // fontconfig writes only its own objects.
            .custom => continue,
        };
        if (b == .family or b == .size) continue;
        try w.writeByte(':');
        try value.writeEscaped(w, @tagName(b), if (escape) escape_variable else null);
        try w.writeByte('=');
        try unparseList(w, e, if (escape) escape_variable else null);
    }
}

fn unparseList(w: *std.Io.Writer, e: *const Elt, escape: ?[]const u8) std.Io.Writer.Error!void {
    var it = e.iterator();
    var first = true;
    while (it.next()) |l| {
        if (!first) try w.writeByte(',');
        first = false;
        try l.value.unparse(w, escape);
    }
}

const testing = std.testing;

test "add, get and order" {
    var p: Pattern = .init(testing.allocator);
    defer p.deinit();
    try p.addString(.style, "Bold");
    try p.addString(.family, "DejaVu Sans");
    try p.addString(.family, "Verdana");
    _ = try p.addWithBinding(.{ .builtin = .family }, .{ .string = "Sans" }, .weak, false);
    try p.addInteger(.weight, 200);
    try testing.expect(!try p.addBuiltin(.family, .{ .integer = 3 }));
    try testing.expect(!try p.addBuiltin(.family, .void));

    try testing.expectEqualStrings("Sans", p.getString(.family, 0).?);
    try testing.expectEqualStrings("DejaVu Sans", p.getString(.family, 1).?);
    try testing.expectEqual(@as(?i32, 200), p.getInteger(.weight, 0));
    try testing.expectEqual(Builtin.family, p.elts.items[0].object.builtin);

    var out: std.Io.Writer.Allocating = .init(testing.allocator);
    defer out.deinit();
    try p.format(&out.writer);
    try testing.expectEqualStrings("Sans,DejaVu Sans,Verdana:style=Bold:weight=200", out.written());

    var copy = try p.duplicate(testing.allocator);
    defer copy.deinit();
    try testing.expect(copy.eql(&p));
    try testing.expect(p.del(.{ .builtin = .style }));
    try testing.expect(!copy.eql(&p));
}