// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie // SPDX-FileCopyrightText: © 2002 Keith Packard // SPDX-License-Identifier: MIT AND HPND-sell-variant //! A set of languages, as fontconfig's `FcLangSet`: one bit for each //! language fontconfig has an orthography for, plus a list of any other //! language tags. //! //! A font's `lang` property is one of these, computed when the font is //! scanned from which orthographies its charset covers; a query's `lang` //! is usually the user's locale. How the two compare is one of the larger //! terms in matching. const std = @import("std"); const Allocator = std.mem.Allocator; const tables = @import("tables"); const str = @import("str.zig"); const CharSet = @import("CharSet.zig"); const LangSet = @This(); pub const words = tables.lang_set_words; /// Bits indexed by `tables.Orth.bit`. map: [words]u32 = @splat(0), /// Languages with no orthography, in the order they were added. extra: []const []const u8 = &.{}, pub const empty: LangSet = .{}; /// How closely two languages agree. The order matters: lower is better. pub const Result = enum(u2) { equal = 0, different_territory = 1, different_lang = 2, }; pub fn deinit(ls: LangSet, gpa: Allocator) void { for (ls.extra) |e| gpa.free(e); gpa.free(ls.extra); } pub fn dupe(ls: LangSet, gpa: Allocator) Allocator.Error!LangSet { const extra = try gpa.alloc([]const u8, ls.extra.len); var n: usize = 0; errdefer { for (extra[0..n]) |e| gpa.free(e); gpa.free(extra); } for (ls.extra, extra) |src, *dst| { dst.* = try gpa.dupe(u8, src); n += 1; } return .{ .map = ls.map, .extra = extra }; } // --------------------------------------------------------------------------- // The orthography table pub const Orth = tables.Orth; pub const orths = &tables.orths; pub fn orthCharSet(o: *const Orth) CharSet { return .{ .pages = o.pages, .leaves = o.leaves }; } /// `FcLangSetIndex`: the position of `lang` in the orthography table, or /// where it would be inserted. pub fn index(lang: []const u8) union(enum) { found: usize, insert: usize } { var low: usize = 0; var high: usize = orths.len; while (low < high) { const mid = (low + high) / 2; switch (str.cmpIgnoreCase(orths[mid].lang, lang)) { .eq => return .{ .found = mid }, .lt => low = mid + 1, .gt => high = mid, } } return .{ .insert = low }; } fn isEnd(c: u8) bool { return c == '-' or c == 0; } fn at(s: []const u8, i: usize) u8 { return if (i < s.len) s[i] else 0; } /// `FcLangCompare`: do two language tags name the same language, the same /// language in a different territory, or a different language? The tag /// `und` matches nothing but itself followed by something. pub fn compare(s1: []const u8, s2: []const u8) Result { var result: Result = .different_lang; var is_und = str.toLower(at(s1, 0)) == 'u' and str.toLower(at(s1, 1)) == 'n' and str.toLower(at(s1, 2)) == 'd' and isEnd(at(s1, 3)); var i: usize = 0; while (true) { const c1 = str.toLower(at(s1, i)); const c2 = str.toLower(at(s2, i)); i += 1; if (c1 != c2) { if (!is_und and isEnd(c1) and isEnd(c2)) result = .different_territory; return result; } else if (c1 == 0) { return if (is_und) result else .equal; } else if (c1 == '-') { if (!is_und) result = .different_territory; } if (is_und and i == 4) is_und = false; } } /// `FcLangContains`: does `super` cover `sub`, where a language without a /// territory covers it with one and the other way round? fn langContains(super: []const u8, sub: []const u8) bool { var i: usize = 0; while (true) : (i += 1) { const c1 = str.toLower(at(super, i)); const c2 = str.toLower(at(sub, i)); if (c1 != c2) { if (c1 == '-' and c2 == 0) return true; if (c1 == 0 and c2 == '-') return true; return false; } else if (c1 == 0) return true; } } /// `FcLangGetCharSet`: the orthography for `lang`, or failing that the /// first one for the same language in another territory. pub fn charSetFor(lang: []const u8) ?CharSet { var country: ?usize = null; for (orths, 0..) |*o, i| { switch (compare(lang, o.lang)) { .equal => return orthCharSet(o), .different_territory => if (country == null) { country = i; }, .different_lang => {}, } } return if (country) |i| orthCharSet(&orths[i]) else null; } /// Every language in the orthography table. pub fn knownLangs() []const Orth { return orths; } const CodePageRange = struct { bit: u5, lang: []const u8 }; /// The Han languages, which are told apart by the code page bits a font /// declares rather than by coverage alone. const code_page_ranges = [_]CodePageRange{ .{ .bit = 17, .lang = "ja" }, .{ .bit = 18, .lang = "zh-cn" }, .{ .bit = 19, .lang = "ko" }, .{ .bit = 20, .lang = "zh-tw" }, }; /// `FcLangIsExclusive`. pub fn isExclusive(lang: []const u8) bool { for (code_page_ranges) |r| { if (compare(lang, r.lang) == .equal) return true; } return false; } /// `FcLangIsExclusiveFromOs2`: the one Han language an OS/2 code page /// range declares, if it declares exactly one. /// /// fontconfig passes the *code page* range here despite the parameter /// names, and so does this. pub fn exclusiveFromOs2(range1: u32, range2: u32) ?[]const u8 { _ = range2; var exclusive: ?[]const u8 = null; for (code_page_ranges) |r| { if (range1 & (@as(u32, 1) << r.bit) != 0) { if (exclusive != null) return null; exclusive = r.lang; } } return exclusive; } /// `FcLangNormalize`: turns a locale name such as `en_US.UTF-8@euro` into /// the language tag fontconfig would use for it, or null if it does not /// look like one. pub fn normalize(gpa: Allocator, lang: []const u8) Allocator.Error!?[]u8 { if (lang.len == 0) return null; if (str.eqlIgnoreCase(lang, "C") or str.eqlIgnoreCase(lang, "C.UTF-8") or str.eqlIgnoreCase(lang, "C.utf8") or str.eqlIgnoreCase(lang, "POSIX")) return try gpa.dupe(u8, "en"); var rest = lang; var modifier: ?[]const u8 = null; if (std.mem.findScalar(u8, rest, '@')) |i| { modifier = rest[i + 1 ..]; rest = rest[0..i]; } if (std.mem.findScalar(u8, rest, '.')) |i| rest = rest[0..i]; var territory: ?[]const u8 = null; const sep = std.mem.findScalar(u8, rest, '_') orelse std.mem.findScalar(u8, rest, '-'); if (sep) |i| { territory = rest[i + 1 ..]; rest = rest[0..i]; } const language = rest; if (language.len < 2 or language.len > 3) return null; if (territory) |t| { if ((t.len < 2 or t.len > 3) and !(t.len > 0 and t[0] == 'z' and t.len < 5)) return null; } // language[-territory][@modifier], then without the territory, then // without the modifier, keeping the first one there is an orthography // for. var buf: std.ArrayList(u8) = .empty; defer buf.deinit(gpa); try buf.appendSlice(gpa, language); if (territory) |t| { try buf.append(gpa, '-'); try buf.appendSlice(gpa, t); } if (modifier) |m| { try buf.append(gpa, '@'); try buf.appendSlice(gpa, m); } const orig = try str.downcase(gpa, buf.items); defer gpa.free(orig); if (territory) |t| { if (index(buf.items) == .found) return try buf.toOwnedSlice(gpa); // Drop the territory, keeping the modifier. const start = language.len; const len = 1 + t.len; std.mem.copyForwards(u8, buf.items[start..], buf.items[start + len ..]); buf.shrinkRetainingCapacity(buf.items.len - len); } if (modifier) |m| { if (index(buf.items) == .found) return try buf.toOwnedSlice(gpa); buf.shrinkRetainingCapacity(buf.items.len - 1 - m.len); } if (index(buf.items) == .found) return try buf.toOwnedSlice(gpa); // No orthography for any form of it: keep it whole, in lower case. return try gpa.dupe(u8, orig); } // --------------------------------------------------------------------------- // Sets fn bitGet(ls: *const LangSet, id: usize) bool { const bit = orths[id].bit; return (ls.map[bit >> 5] >> @intCast(bit & 31)) & 1 != 0; } fn bitSet(ls: *LangSet, id: usize) void { const bit = orths[id].bit; ls.map[bit >> 5] |= @as(u32, 1) << @intCast(bit & 31); } fn bitReset(ls: *LangSet, id: usize) void { const bit = orths[id].bit; ls.map[bit >> 5] &= ~(@as(u32, 1) << @intCast(bit & 31)); } /// The orthography table index for a language-set bit. fn idForBit(bit: usize) usize { const S = struct { const inverse = blk: { @setEvalBranchQuota(100_000); var inv: [words * 32]u16 = @splat(0); for (&tables.orths, 0..) |o, i| inv[o.bit] = i; break :blk inv; }; }; return S.inverse[bit]; } /// `FcLangSetAdd`. The new set shares nothing with `ls`; it is allocated /// with `gpa` and must be freed with `deinit`. pub fn add(ls: LangSet, gpa: Allocator, lang: []const u8) Allocator.Error!LangSet { var out = try ls.dupe(gpa); errdefer out.deinit(gpa); try out.addInPlace(gpa, lang); return out; } /// `FcLangSetAdd` on a set this code owns. pub fn addInPlace(ls: *LangSet, gpa: Allocator, lang: []const u8) Allocator.Error!void { switch (index(lang)) { .found => |id| ls.bitSet(id), .insert => { for (ls.extra) |e| if (std.mem.eql(u8, e, lang)) return; const copy = try gpa.dupe(u8, lang); errdefer gpa.free(copy); const extra = try gpa.alloc([]const u8, ls.extra.len + 1); @memcpy(extra[0..ls.extra.len], ls.extra); extra[ls.extra.len] = copy; gpa.free(ls.extra); ls.extra = extra; }, } } /// `FcLangSetDel` on a set this code owns. pub fn removeInPlace(ls: *LangSet, gpa: Allocator, lang: []const u8) void { switch (index(lang)) { .found => |id| ls.bitReset(id), .insert => { for (ls.extra, 0..) |e, i| { if (std.mem.eql(u8, e, lang)) { gpa.free(e); const extra: [][]const u8 = @constCast(ls.extra); std.mem.copyForwards([]const u8, extra[i..], extra[i + 1 ..]); ls.extra = extra[0 .. extra.len - 1]; return; } } }, } } /// A set holding just `lang`: fontconfig's promotion of a string to a /// language set when the two are compared. pub fn fromLang(gpa: Allocator, lang: []const u8) Allocator.Error!LangSet { var ls: LangSet = .{}; try ls.addInPlace(gpa, lang); return ls; } /// `FcLangSetHasLang`: how well the set covers `lang`. pub fn hasLang(ls: *const LangSet, lang: []const u8) Result { const id = switch (index(lang)) { .found => |id| if (ls.bitGet(id)) return .equal else id, .insert => |id| id, }; var best: Result = .different_lang; var i = id; while (i > 0) { i -= 1; const r = compare(lang, orths[i].lang); if (r == .different_lang) break; if (ls.bitGet(i) and @backingInt(r) < @backingInt(best)) best = r; } i = id; while (i < orths.len) : (i += 1) { const r = compare(lang, orths[i].lang); if (r == .different_lang) break; if (ls.bitGet(i) and @backingInt(r) < @backingInt(best)) best = r; } for (ls.extra) |e| { if (best == .equal) break; const r = compare(lang, e); if (@backingInt(r) < @backingInt(best)) best = r; } return best; } fn compareStrSet(ls: *const LangSet, set: []const []const u8) Result { var best: Result = .different_lang; for (set) |e| { if (best == .equal) break; const r = ls.hasLang(e); if (@backingInt(r) < @backingInt(best)) best = r; } return best; } /// `FcLangSetCompare`: the best agreement between any language of `a` and /// any of `b`. pub fn compareSets(a: *const LangSet, b: *const LangSet) Result { for (a.map, b.map) |aw, bw| if (aw & bw != 0) return .equal; var best: Result = .different_lang; for (tables.country_sets) |set| { var a_in: u32 = 0; var b_in: u32 = 0; for (a.map, b.map, set) |aw, bw, sw| { a_in |= aw & sw; b_in |= bw & sw; if (a_in != 0 and b_in != 0) { best = .different_territory; break; } } } if (a.extra.len > 0) { const r = b.compareStrSet(a.extra); if (@backingInt(r) < @backingInt(best)) best = r; } if (best != .equal and b.extra.len > 0) { const r = a.compareStrSet(b.extra); if (@backingInt(r) < @backingInt(best)) best = r; } return best; } /// `FcLangSetEqual`. The extra languages are compared as sets. pub fn eql(a: *const LangSet, b: *const LangSet) bool { if (!std.mem.eql(u32, &a.map, &b.map)) return false; if (a.extra.len != b.extra.len) return false; outer: for (a.extra) |x| { for (b.extra) |y| if (std.mem.eql(u8, x, y)) continue :outer; return false; } return true; } /// `FcLangSetContainsLang`. fn containsLang(ls: *const LangSet, lang: []const u8) bool { const id = switch (index(lang)) { .found => |id| if (ls.bitGet(id)) return true else id, .insert => |id| id, }; var i = id; while (i > 0) { i -= 1; if (compare(orths[i].lang, lang) == .different_lang) break; if (ls.bitGet(i) and langContains(orths[i].lang, lang)) return true; } i = id; while (i < orths.len) : (i += 1) { if (compare(orths[i].lang, lang) == .different_lang) break; if (ls.bitGet(i) and langContains(orths[i].lang, lang)) return true; } for (ls.extra) |e| if (langContains(e, lang)) return true; return false; } /// `FcLangSetContains`: does `a` cover every language of `b`? pub fn contains(a: *const LangSet, b: *const LangSet) bool { for (a.map, b.map, 0..) |aw, bw, i| { const missing = bw & ~aw; if (missing == 0) continue; for (0..32) |j| { if (missing & (@as(u32, 1) << @intCast(j)) != 0) { if (!a.containsLang(orths[idForBit(i * 32 + j)].lang)) return false; } } } for (b.extra) |e| if (!a.containsLang(e)) return false; return true; } /// `FcLangSetGetLangs`: every language in the set, those with an /// orthography in table order, then the others. pub fn langs(ls: *const LangSet, gpa: Allocator) Allocator.Error![][]const u8 { var out: std.ArrayList([]const u8) = .empty; errdefer out.deinit(gpa); for (orths, 0..) |*o, i| if (ls.bitGet(i)) try out.append(gpa, o.lang); for (ls.extra) |e| try out.append(gpa, e); return out.toOwnedSlice(gpa); } /// `FcLangSetUnion`. pub fn unionWith(gpa: Allocator, a: *const LangSet, b: *const LangSet) Allocator.Error!LangSet { var out = try a.dupe(gpa); errdefer out.deinit(gpa); const ls = try b.langs(gpa); defer gpa.free(ls); for (ls) |l| try out.addInPlace(gpa, l); return out; } /// `FcLangSetSubtract`. pub fn subtract(gpa: Allocator, a: *const LangSet, b: *const LangSet) Allocator.Error!LangSet { var out = try a.dupe(gpa); errdefer out.deinit(gpa); const ls = try b.langs(gpa); defer gpa.free(ls); for (ls) |l| out.removeInPlace(gpa, l); return out; } /// `FcLangSetFromCharSet`: the languages whose orthographies `charset` /// covers completely. `exclusive` is the one Han language the font's code /// pages declare, if any, and keeps the font from claiming the others. pub fn fromCharSet(charset: CharSet, exclusive: ?[]const u8) LangSet { var ls: LangSet = .{}; const exclusive_charset: ?CharSet = if (exclusive) |l| charSetFor(l) else null; for (orths, 0..) |*o, i| { if (exclusive_charset) |ex| { // fontconfig means to skip a Han orthography that is not the // declared one, but its test only ever compares the number of // pages, so that is all this compares. if (isExclusive(o.lang) and o.pages.len != ex.pages.len) continue; } if (orthCharSet(o).subtractCount(charset) == 0) ls.bitSet(i); } return ls; } /// `FcNameParseLangSet`: languages separated by `|`. Each is cut to 31 /// bytes, as fontconfig cuts it. pub fn parse(gpa: Allocator, text: []const u8) Allocator.Error!LangSet { var ls: LangSet = .{}; errdefer ls.deinit(gpa); var it = std.mem.splitScalar(u8, text, '|'); while (it.next()) |l| try ls.addInPlace(gpa, l[0..@min(l.len, 31)]); return ls; } /// `FcNameUnparseLangSet`: languages separated by `|`, those with an /// orthography in bit order, then the others. pub fn format(ls: *const LangSet, w: *std.Io.Writer) std.Io.Writer.Error!void { var first = true; for (ls.map, 0..) |word, i| { if (word == 0) continue; for (0..32) |bit| { if (word & (@as(u32, 1) << @intCast(bit)) == 0) continue; if (!first) try w.writeByte('|'); try w.writeAll(orths[idForBit(i * 32 + bit)].lang); first = false; } } for (ls.extra) |e| { if (!first) try w.writeByte('|'); try w.writeAll(e); first = false; } } const testing = std.testing; test "language tag comparison" { try testing.expectEqual(Result.equal, compare("en", "EN")); try testing.expectEqual(Result.different_territory, compare("en-us", "en-gb")); try testing.expectEqual(Result.different_territory, compare("en", "en-gb")); try testing.expectEqual(Result.different_lang, compare("en", "de")); try testing.expectEqual(Result.different_lang, compare("und", "und")); try testing.expectEqual(Result.different_lang, compare("und-zsye", "und-zmth")); try testing.expectEqual(Result.equal, compare("und-zsye", "und-zsye")); } test "table lookups" { try testing.expect(index("en") == .found); try testing.expect(index("EN") == .found); try testing.expect(index("xx-yy") == .insert); const en = charSetFor("en").?; try testing.expect(en.hasChar('a')); try testing.expect(charSetFor("en-us") != null); } test "normalize locale names" { const gpa = testing.allocator; const cases = [_][2][]const u8{ .{ "en_US.UTF-8", "en" }, .{ "C", "en" }, .{ "zh_TW.UTF-8", "zh-TW" }, .{ "pt_BR", "pt" }, .{ "sr_RS@latin", "sr" }, .{ "xx_YY", "xx-yy" }, }; for (cases) |c| { const got = (try normalize(gpa, c[0])).?; defer gpa.free(got); try testing.expectEqualStrings(c[1], got); } try testing.expectEqual(@as(?[]u8, null), try normalize(gpa, "toolong_XX")); } test "sets" { const gpa = testing.allocator; var a = try parse(gpa, "en|de|xx-yy"); defer a.deinit(gpa); var b = try parse(gpa, "en-gb"); defer b.deinit(gpa); try testing.expectEqual(Result.equal, a.hasLang("en")); try testing.expectEqual(Result.different_territory, a.hasLang("de-at")); try testing.expectEqual(Result.equal, a.hasLang("xx-yy")); try testing.expectEqual(Result.different_lang, a.hasLang("fr")); try testing.expect(a.contains(&b)); try testing.expect(!b.contains(&a)); var out: std.Io.Writer.Allocating = .init(gpa); defer out.deinit(); try a.format(&out.writer); try testing.expectEqualStrings("de|en|xx-yy", out.written()); } test "languages from a charset" { const gpa = testing.allocator; const latin = (try CharSet.parse(gpa, "20-7e a0-17f")).?; defer latin.deinit(gpa); const ls = fromCharSet(latin, null); try testing.expectEqual(Result.equal, ls.hasLang("en")); try testing.expectEqual(Result.equal, ls.hasLang("de")); try testing.expectEqual(Result.different_lang, ls.hasLang("ru")); }