// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie // SPDX-FileCopyrightText: © 2009,2010 Red Hat, Inc. // SPDX-FileCopyrightText: © 2010,2011,2013 Google, Inc. // SPDX-License-Identifier: MIT AND MIT-Modern-Variant //! Which lookups to apply, in what order, and to which glyphs. //! //! A shaper asks for features by tag, in stages; a `Builder` finds them in //! the font's script and language system, gives each the bits of the glyph //! mask it needs, and compiles the lot into the list of lookups `GSUB` and //! `GPOS` each run, stage by stage. Each lookup runs on the glyphs whose mask //! has one of its features' bits set. This is HarfBuzz's `hb_ot_map_t`. const std = @import("std"); const Allocator = std.mem.Allocator; const font = @import("font"); const Buffer = @import("Buffer.zig"); const Face = @import("Face.zig"); const script_mod = @import("script.zig"); const language_mod = @import("language.zig"); const Map = @This(); const Tag = font.Tag; const layout = font.tables.layout; /// GSUB is table 0 and GPOS table 1 throughout. pub const TableIndex = enum(u1) { gsub = 0, gpos = 1 }; pub const max_bits = 8; pub const max_value = (1 << max_bits) - 1; /// The feature index meaning "not in this table". pub const no_feature = 0xFFFF; pub const FeatureFlags = packed struct(u8) { /// The feature applies to all characters, and needs no bits of its own. global: bool = false, /// The shaper can do without the font, so the feature gets its bits even /// when the font lacks it. has_fallback: bool = false, /// Do not skip ZWNJ when matching context. manual_zwnj: bool = false, /// Do not skip ZWJ when matching input. manual_zwj: bool = false, /// If the language system lacks the feature, take it from wherever in /// the table it is. global_search: bool = false, /// Pick an alternate at random. random: bool = false, /// Keep matching within a syllable. per_syllable: bool = false, _: u1 = 0, pub const none: FeatureFlags = .{}; pub const global_only: FeatureFlags = .{ .global = true }; pub const manual_joiners: FeatureFlags = .{ .manual_zwnj = true, .manual_zwj = true }; pub const global_manual_joiners: FeatureFlags = .{ .global = true, .manual_zwnj = true, .manual_zwj = true }; pub const global_has_fallback: FeatureFlags = .{ .global = true, .has_fallback = true }; pub const global_search_only: FeatureFlags = .{ .global = true, .global_search = true }; }; pub const FeatureMap = struct { tag: u32, index: [2]u16, stage: [2]u32, shift: u5, mask: u32, /// The bits for value 1 alone, which is how most shapers set a feature. one_mask: u32, needs_fallback: bool, auto_zwnj: bool, auto_zwj: bool, random: bool, per_syllable: bool, }; pub const LookupMap = struct { index: u16, auto_zwnj: bool, auto_zwj: bool, random: bool, per_syllable: bool, mask: u32, feature_tag: u32, }; /// Something a shaper does between stages, between one feature's lookups /// and the next's. The context is the shape plan and the face, typed loosely /// so that the map does not depend on them. pub const PauseFunc = *const fn (ctx: *const anyopaque, buffer: *Buffer) Allocator.Error!void; pub const StageMap = struct { /// The end of this stage's lookups, counting from the start of the /// table's lookups. last_lookup: usize, pause: ?PauseFunc, }; global_mask: u32 = 0, /// Sorted by tag. features: std.ArrayList(FeatureMap) = .empty, lookups: [2]std.ArrayList(LookupMap) = .{ .empty, .empty }, stages: [2]std.ArrayList(StageMap) = .{ .empty, .empty }, /// The script tag found in each table, or the fallback chosen when none was. chosen_script: [2]u32 = .{ 0, 0 }, found_script: [2]bool = .{ false, false }, pub fn deinit(m: *Map, gpa: Allocator) void { m.features.deinit(gpa); for (&m.lookups) |*l| l.deinit(gpa); for (&m.stages) |*s| s.deinit(gpa); } fn findFeature(m: *const Map, tag: u32) ?*const FeatureMap { var lo: usize = 0; var hi: usize = m.features.items.len; while (lo < hi) { const mid = lo + (hi - lo) / 2; const t = m.features.items[mid].tag; if (tag < t) { hi = mid; } else if (tag > t) { lo = mid + 1; } else return &m.features.items[mid]; } return null; } /// The bits of the mask a feature's value is kept in, and where they start. pub fn getMask(m: *const Map, tag: u32) struct { mask: u32, shift: u5 } { const f = m.findFeature(tag) orelse return .{ .mask = 0, .shift = 0 }; return .{ .mask = f.mask, .shift = f.shift }; } /// The bits that set a feature to 1. pub fn get1Mask(m: *const Map, tag: u32) u32 { const f = m.findFeature(tag) orelse return 0; return f.one_mask; } pub fn needsFallback(m: *const Map, tag: u32) bool { const f = m.findFeature(tag) orelse return false; return f.needs_fallback; } pub fn getFeatureIndex(m: *const Map, table: TableIndex, tag: u32) u16 { const f = m.findFeature(tag) orelse return no_feature; return f.index[@backingInt(table)]; } pub fn getFeatureStage(m: *const Map, table: TableIndex, tag: u32) u32 { const f = m.findFeature(tag) orelse return std.math.maxInt(u32); return f.stage[@backingInt(table)]; } /// The lookups of one stage. pub fn stageLookups(m: *const Map, table: TableIndex, stage: usize) []const LookupMap { const t = @backingInt(table); const stages = m.stages[t].items; if (stage > stages.len) return &.{}; const start = if (stage > 0) stages[stage - 1].last_lookup else 0; const end = if (stage < stages.len) stages[stage].last_lookup else m.lookups[t].items.len; return m.lookups[t].items[start..end]; } pub fn tagInt(comptime s: *const [4]u8) u32 { return std.mem.readInt(u32, s, .big); } /// The script and language system lists of `GSUB` or `GPOS`, whichever the /// font has, or nothing. pub const LayoutView = struct { scripts: []const layout.Script = &.{}, features: []const layout.FeatureRecord = &.{}, lookup_count: usize = 0, feature_variations: ?layout.FeatureVariations = null, pub fn of(f: *const font.Font, table: TableIndex) LayoutView { switch (table) { .gsub => if (f.gsub) |t| return .{ .scripts = t.scripts, .features = t.features, .lookup_count = t.lookups.len, .feature_variations = t.feature_variations, }, .gpos => if (f.gpos) |t| return .{ .scripts = t.scripts, .features = t.features, .lookup_count = t.lookups.len, .feature_variations = t.feature_variations, }, } return .{}; } /// `find_script_index`: a binary search, as HarfBuzz does, which relies /// on the list being sorted by tag as the specification requires. fn findScript(v: LayoutView, tag: u32) ?usize { var lo: usize = 0; var hi: usize = v.scripts.len; while (lo < hi) { const mid = lo + (hi - lo) / 2; const t = v.scripts[mid].tag.toInt(); if (tag < t) { hi = mid; } else if (tag > t) { lo = mid + 1; } else return mid; } return null; } fn featureTag(v: LayoutView, index: u16) u32 { return if (index < v.features.len) v.features[index].tag.toInt() else 0; } /// The lookups of feature `index`, as the feature variation record at /// `variations_index` replaces them. fn featureLookups(v: LayoutView, index: u16, variations_index: ?usize) []const u16 { if (variations_index) |vi| if (v.feature_variations) |fv| { if (vi < fv.records.len) for (fv.records[vi].substitutions) |sub| { if (sub.feature_index == index) return sub.feature.lookup_indices; }; }; if (index >= v.features.len) return &.{}; return v.features[index].feature.lookup_indices; } }; /// The language system a script and language select: an index into the /// script list, and into that script's language systems, where null is the /// default one. const Selection = struct { script: ?usize = null, lang_sys: ?usize = null, fn langSys(s: Selection, v: LayoutView) ?layout.LangSys { const si = s.script orelse return null; const sc = v.scripts[si]; if (s.lang_sys) |li| return sc.lang_sys[li].lang_sys; return sc.default_lang_sys; } }; pub const Builder = struct { gpa: Allocator, face: *const Face, direction: Buffer.Direction, script: script_mod.Script, language: ?*const language_mod.Language, /// Whether features were added in an order that needs no sorting. is_simple: bool = false, chosen_script: [2]u32 = .{ 0, 0 }, found_script: [2]bool = .{ false, false }, selection: [2]Selection = .{ .{}, .{} }, views: [2]LayoutView, current_stage: [2]u32 = .{ 0, 0 }, feature_infos: std.ArrayList(FeatureInfo) = .empty, stage_infos: [2]std.ArrayList(StageInfo) = .{ .empty, .empty }, const FeatureInfo = struct { tag: u32, /// For a stable sort. seq: u32, max_value: u32, flags: FeatureFlags, /// What glyphs the feature was not set on take, for features that /// are not global. default_value: u32, stage: [2]u32, }; const StageInfo = struct { index: u32, pause: ?PauseFunc }; pub fn init( gpa: Allocator, face: *const Face, direction: Buffer.Direction, script: script_mod.Script, language: ?*const language_mod.Language, ) Builder { var b: Builder = .{ .gpa = gpa, .face = face, .direction = direction, .script = script, .language = language, .views = .{ LayoutView.of(face.font, .gsub), LayoutView.of(face.font, .gpos) }, }; var script_buf: [3]u32 = undefined; const lang_tags = language_mod.tagsFor(language); const script_tags: []const u32 = if (lang_tags.script_override) |t| blk: { script_buf[0] = t; break :blk script_buf[0..1]; } else script_mod.otTags(script, &script_buf); for (0..2) |t| { const v = b.views[t]; var sel: Selection = .{}; // hb_ot_layout_table_select_script var found = false; for (script_tags) |tag| if (v.findScript(tag)) |i| { sel.script = i; b.chosen_script[t] = tag; found = true; break; }; if (!found) { for ([_]u32{ tagInt("DFLT"), tagInt("dflt"), tagInt("latn") }) |tag| { if (v.findScript(tag)) |i| { sel.script = i; b.chosen_script[t] = tag; break; } } } b.found_script[t] = found; // hb_ot_layout_script_select_language if (sel.script) |si| { const sc = v.scripts[si]; var lang_found = false; for (lang_tags.languageTags()) |lt| { if (findLangSys(sc, lt)) |li| { sel.lang_sys = li; lang_found = true; break; } } if (!lang_found) sel.lang_sys = findLangSys(sc, language_mod.default_tag); } b.selection[t] = sel; } return b; } /// `find_lang_sys_index`, a binary search like `findScript`. fn findLangSys(sc: layout.Script, tag: u32) ?usize { var lo: usize = 0; var hi: usize = sc.lang_sys.len; while (lo < hi) { const mid = lo + (hi - lo) / 2; const t = sc.lang_sys[mid].tag.toInt(); if (tag < t) { hi = mid; } else if (tag > t) { lo = mid + 1; } else return mid; } return null; } pub fn deinit(b: *Builder) void { b.feature_infos.deinit(b.gpa); for (&b.stage_infos) |*s| s.deinit(b.gpa); } pub fn addFeature(b: *Builder, tag: u32, flags: FeatureFlags, value: u32) Allocator.Error!void { if (tag == 0) return; try b.feature_infos.append(b.gpa, .{ .tag = tag, .seq = @intCast(b.feature_infos.items.len + 1), .max_value = value, .flags = flags, .default_value = if (flags.global) value else 0, .stage = b.current_stage, }); } pub fn enableFeature(b: *Builder, tag: u32, flags: FeatureFlags, value: u32) Allocator.Error!void { var f = flags; f.global = true; return b.addFeature(tag, f, value); } pub fn disableFeature(b: *Builder, tag: u32) Allocator.Error!void { return b.addFeature(tag, .global_only, 0); } pub fn addGsubPause(b: *Builder, pause: ?PauseFunc) Allocator.Error!void { return b.addPause(.gsub, pause); } pub fn addGposPause(b: *Builder, pause: ?PauseFunc) Allocator.Error!void { return b.addPause(.gpos, pause); } fn addPause(b: *Builder, table: TableIndex, pause: ?PauseFunc) Allocator.Error!void { const t = @backingInt(table); try b.stage_infos[t].append(b.gpa, .{ .index = b.current_stage[t], .pause = pause }); b.current_stage[t] += 1; } /// Whether the selected language system of either table has `tag`. pub fn hasFeature(b: *const Builder, tag: u32) bool { for (0..2) |t| { const ls = b.selection[t].langSys(b.views[t]) orelse continue; for (ls.feature_indices) |fi| if (b.views[t].featureTag(fi) == tag) return true; } return false; } fn lessFeatureInfo(_: void, a: FeatureInfo, c: FeatureInfo) bool { if (a.tag != c.tag) return a.tag < c.tag; return a.seq < c.seq; } /// `compile`. `variations_index` is, for each table, the feature /// variation record that applies at the face's location. pub fn compile(b: *Builder, m: *Map, variations_index: [2]?usize) Allocator.Error!void { const global_bit_shift = 31; const global_bit_mask: u32 = 1 << global_bit_shift; m.global_mask = global_bit_mask; var required_index: [2]u16 = .{ no_feature, no_feature }; var required_tag: [2]u32 = .{ 0, 0 }; // The required feature is applied in stage 0, unless its tag is one // the shaper asked for, in which case it goes in that one's stage. var required_stage: [2]u32 = .{ 0, 0 }; for (0..2) |t| { m.chosen_script[t] = b.chosen_script[t]; m.found_script[t] = b.found_script[t]; if (b.selection[t].langSys(b.views[t])) |ls| { if (ls.required_feature_index) |ri| { required_index[t] = ri; required_tag[t] = b.views[t].featureTag(ri); } } } // Sort features and merge duplicates. const infos = b.feature_infos.items; var count: usize = 0; if (infos.len > 0) { if (!b.is_simple) std.mem.sort(FeatureInfo, infos, {}, lessFeatureInfo); var j: usize = 0; for (1..infos.len) |i| { if (infos[i].tag != infos[j].tag) { j += 1; infos[j] = infos[i]; } else { if (infos[i].flags.global) { infos[j].flags.global = true; infos[j].max_value = infos[i].max_value; infos[j].default_value = infos[i].default_value; } else { infos[j].flags.global = false; infos[j].max_value = @max(infos[j].max_value, infos[i].max_value); // Inherit default_value from j. } infos[j].flags.has_fallback = infos[j].flags.has_fallback or infos[i].flags.has_fallback; infos[j].stage[0] = @min(infos[j].stage[0], infos[i].stage[0]); infos[j].stage[1] = @min(infos[j].stage[1], infos[i].stage[1]); } } count = j + 1; } // Allocate bits now. The low bits are the glyph flags. var next_bit: u32 = @popCount(Buffer.GlyphFlags.defined) + 1; for (infos[0..count]) |info| { const bits_needed: u32 = if (info.flags.global and info.max_value == 1) 0 // Uses the global bit. else @min(max_bits, bitStorage(info.max_value)); if (info.max_value == 0 or next_bit + bits_needed >= global_bit_shift) continue; // Feature disabled, or not enough bits. var found = false; var feature_index: [2]u16 = .{ no_feature, no_feature }; for (0..2) |t| { if (required_tag[t] == info.tag) required_stage[t] = info.stage[t]; if (b.languageFeature(@fromBackingInt(@intCast(t)), info.tag)) |fi| { feature_index[t] = fi; found = true; } } if (!found and info.flags.global_search) { for (0..2) |t| { // hb_ot_layout_table_find_feature for (b.views[t].features, 0..) |fr, i| { if (fr.tag.toInt() == info.tag) { feature_index[t] = @intCast(i); found = true; break; } } } } if (!found and !info.flags.has_fallback) continue; var fm: FeatureMap = .{ .tag = info.tag, .index = feature_index, .stage = info.stage, .shift = undefined, .mask = undefined, .one_mask = undefined, .needs_fallback = !found, .auto_zwnj = !info.flags.manual_zwnj, .auto_zwj = !info.flags.manual_zwj, .random = info.flags.random, .per_syllable = info.flags.per_syllable, }; if (info.flags.global and info.max_value == 1) { fm.shift = global_bit_shift; fm.mask = global_bit_mask; } else { fm.shift = @intCast(next_bit); fm.mask = (@as(u32, 1) << @intCast(next_bit + bits_needed)) - (@as(u32, 1) << @intCast(next_bit)); next_bit += bits_needed; m.global_mask |= (info.default_value << fm.shift) & fm.mask; } fm.one_mask = (@as(u32, 1) << fm.shift) & fm.mask; try m.features.append(b.gpa, fm); } // Sorted for lookup by tag, stably, in case two share one. std.mem.sort(FeatureMap, m.features.items, {}, struct { fn lt(_: void, x: FeatureMap, y: FeatureMap) bool { return x.tag < y.tag; } }.lt); try b.addGsubPause(null); try b.addGposPause(null); for (0..2) |t| { const lookups = &m.lookups[t]; var stage_index: usize = 0; var last_num_lookups: usize = 0; var stage: u32 = 0; while (stage < b.current_stage[t]) : (stage += 1) { if (required_index[t] != no_feature and required_stage[t] == stage) { try b.addLookups(m, @fromBackingInt(@intCast(t)), required_index[t], variations_index[t], global_bit_mask, true, true, false, false, tagInt(" ")); } for (m.features.items) |f| { if (f.stage[t] == stage) { try b.addLookups(m, @fromBackingInt(@intCast(t)), f.index[t], variations_index[t], f.mask, f.auto_zwnj, f.auto_zwj, f.random, f.per_syllable, f.tag); } } // Sort lookups and merge duplicates. if (last_num_lookups + 1 < lookups.items.len) { const sub = lookups.items[last_num_lookups..]; std.mem.sort(LookupMap, sub, {}, struct { fn lt(_: void, x: LookupMap, y: LookupMap) bool { return x.index < y.index; } }.lt); var j = last_num_lookups; for (last_num_lookups + 1..lookups.items.len) |i| { if (lookups.items[i].index != lookups.items[j].index) { j += 1; lookups.items[j] = lookups.items[i]; } else { lookups.items[j].mask |= lookups.items[i].mask; lookups.items[j].auto_zwnj = lookups.items[j].auto_zwnj and lookups.items[i].auto_zwnj; lookups.items[j].auto_zwj = lookups.items[j].auto_zwj and lookups.items[i].auto_zwj; } } lookups.shrinkRetainingCapacity(j + 1); } last_num_lookups = lookups.items.len; if (stage_index < b.stage_infos[t].items.len and b.stage_infos[t].items[stage_index].index == stage) { try m.stages[t].append(b.gpa, .{ .last_lookup = last_num_lookups, .pause = b.stage_infos[t].items[stage_index].pause, }); stage_index += 1; } } } } /// The index of feature `tag` in the selected language system. When a /// language system names a tag twice, the first one wins. fn languageFeature(b: *const Builder, table: TableIndex, tag: u32) ?u16 { const t = @backingInt(table); const ls = b.selection[t].langSys(b.views[t]) orelse return null; for (ls.feature_indices) |fi| { if (b.views[t].featureTag(fi) == tag) return fi; } return null; } fn addLookups( b: *Builder, m: *Map, table: TableIndex, feature_index: u16, variations_index: ?usize, mask: u32, auto_zwnj: bool, auto_zwj: bool, random: bool, per_syllable: bool, feature_tag: u32, ) Allocator.Error!void { if (feature_index == no_feature) return; const t = @backingInt(table); const v = b.views[t]; for (v.featureLookups(feature_index, variations_index)) |li| { if (li >= v.lookup_count) continue; try m.lookups[t].append(b.gpa, .{ .index = li, .auto_zwnj = auto_zwnj, .auto_zwj = auto_zwj, .random = random, .per_syllable = per_syllable, .mask = mask, .feature_tag = feature_tag, }); } } }; /// `hb_bit_storage`: the number of bits needed to hold `v`. fn bitStorage(v: u32) u32 { return 32 - @clz(v); } /// The feature variation record that applies at the face's location, for /// each table: `hb_ot_layout_table_find_feature_variations`. pub fn variationsIndex(face: *const Face) [2]?usize { var out: [2]?usize = .{ null, null }; for (0..2) |t| { const v = LayoutView.of(face.font, @fromBackingInt(@intCast(t))); const fv = v.feature_variations orelse continue; for (fv.records, 0..) |rec, i| { if (rec.matches(face.coords)) { out[t] = i; break; } } } return out; }