Skip to main content

harfrust/ot/lookup/
context.rs

1//! Contextual and chained contextual subtables, shared by GSUB and GPOS.
2//!
3//! A contextual subtable is a chained one without backtrack or lookahead,
4//! so both run through the same walks. Only the layout of their rules
5//! differs, which [`RuleLayout`] records: whether they are chained, and the
6//! width of the offsets to them, which the extended formats widen.
7//!
8//! Rule values are glyph IDs or classes. The rule walks take their width as
9//! a constant, since they read many values per rule: classes are always 16
10//! bits, and only the glyph rules of the extended formats are 24.
11
12use super::coverage::{ClassDef, Coverage, CoverageArray};
13use super::gsub::covered_at;
14use super::{glyph_class_cached, Offsets, SubtableDigests, Uints, Values};
15use crate::budget::{Budget, Exhausted};
16use crate::buffer::GlyphInfo;
17use crate::hint::Likely;
18use crate::ot::apply::{
19    apply_lookup, match_always, match_backtrack, match_glyph, match_input, match_lookahead,
20    ApplyContext, MappingCache, MaySkip, RuleSetDigest, SkippingIterator, WouldApplyContext,
21};
22use crate::set_digest::SetDigest;
23use alloc::{boxed::Box, vec::Vec};
24use read_fonts::tables::layout::{
25    ChainedSequenceContextFormat1, ChainedSequenceContextFormat2, ChainedSequenceContextFormat3,
26    ChainedSequenceContextFormat4, ChainedSequenceContextFormat5, ChainedSequenceRule,
27    SequenceContextFormat1, SequenceContextFormat2, SequenceContextFormat3, SequenceContextFormat4,
28    SequenceContextFormat5, SequenceContextFormat6, SequenceLookupRecord, SequenceRule,
29};
30use read_fonts::types::{FixedSize, GlyphId};
31use read_fonts::FontData;
32
33/// Matches a glyph against a rule value: a glyph ID or a class. The rule
34/// walks are generic over it so that matching inlines; `would_apply`, which
35/// is cold, takes it by reference.
36type MatchFn<'a> = &'a dyn Fn(&mut GlyphInfo, u32) -> bool;
37
38/// Offsets to rule sets, which are null for glyphs or classes without rules.
39type RuleSets<'a> = Offsets<'a>;
40
41/// The width of glyph IDs, classes and offsets in the original formats.
42const NARROW: u8 = 2;
43/// The width of glyph IDs and offsets in the extended formats.
44const WIDE: u8 = 3;
45
46/// The width of the class values of a rule, and of the glyph IDs of the
47/// original formats.
48const CLASS: usize = 2;
49/// The width of the glyph IDs of the extended formats.
50const GLYPH24: usize = 3;
51
52/// How the rules of a subtable are laid out.
53#[derive(Clone, Copy)]
54struct RuleLayout {
55    /// Whether the rules are chained rules rather than sequence rules.
56    chained: bool,
57    /// The width of the offsets from a rule set to its rules.
58    offset_width: u8,
59}
60
61impl RuleLayout {
62    const fn new(chained: bool, offset_width: u8) -> Self {
63        Self {
64            chained,
65            offset_width,
66        }
67    }
68}
69
70/// The class of `gid`, remembered in `cache` if there is one.
71fn cached_class(class_def: &ClassDef, gid: GlyphId, cache: Option<&MappingCache>) -> u32 {
72    match cache {
73        Some(cache) => glyph_class_cached(class_def, gid, cache),
74        None => class_def.get(gid),
75    }
76}
77
78/// Rule set `index` of `sets`, or `None` if it is null or can't be read.
79fn rule_set<'a>(sets: &RuleSets<'a>, index: usize, layout: RuleLayout) -> Option<Rules<'a>> {
80    Rules::read(sets.data(index)?, layout)
81}
82
83/// Calls `f` with each rule of each rule set present in `sets`, stopping
84/// with `None` at one that can't be read.
85fn for_each_rule<'a, const W: usize>(
86    sets: &RuleSets<'a>,
87    layout: RuleLayout,
88    budget: &Budget,
89    mut f: impl FnMut(ParsedRule<'a, W>) -> Result<Option<()>, Exhausted>,
90) -> Result<Option<()>, Exhausted> {
91    budget.work(sets.len())?;
92    for index in 0..sets.len() {
93        if sets.is_null(index) {
94            continue;
95        }
96        let Some(rules) = rule_set(sets, index, layout) else {
97            return Ok(None);
98        };
99        budget.work(rules.len())?;
100        for index in 0..rules.len() {
101            let Some(rule) = rules
102                .rule(index)
103                .and_then(|data| ParsedRule::try_parse(data, layout))
104            else {
105                return Ok(None);
106            };
107            if f(rule)?.is_none() {
108                return Ok(None);
109            }
110        }
111    }
112    Ok(Some(()))
113}
114
115/// The digest of the first input class of each rule set's rules.
116fn rule_set_digests(
117    sets: &RuleSets,
118    layout: RuleLayout,
119    budget: &Budget,
120) -> Result<Box<[RuleSetDigest]>, Exhausted> {
121    budget.work(sets.len())?;
122    budget.alloc::<RuleSetDigest>(sets.len())?;
123    let mut digests = Vec::with_capacity(sets.len());
124    for index in 0..sets.len() {
125        let mut digest = RuleSetDigest::default();
126        if !sets.is_null(index) {
127            if let Some(rules) = rule_set(sets, index, layout) {
128                budget.work(rules.len())?;
129                for index in 0..rules.len() {
130                    let Some(value) = rules
131                        .rule(index)
132                        .and_then(|data| rule_first_input::<CLASS>(&data, layout))
133                    else {
134                        digest = RuleSetDigest::full();
135                        break;
136                    };
137                    digest.add(value);
138                }
139            } else {
140                digest = RuleSetDigest::full();
141            }
142        }
143        digests.push(digest);
144    }
145    Ok(digests.into_boxed_slice())
146}
147
148/// Chained context by glyph sequences, or context by glyph sequences.
149pub(crate) struct ChainContext1<'a> {
150    rule_sets: RuleSets<'a>,
151    layout: RuleLayout,
152    /// Whether rule glyph IDs are 24 bits rather than 16.
153    wide_glyphs: bool,
154}
155
156impl<'a> ChainContext1<'a> {
157    pub fn new(table: &ChainedSequenceContextFormat1<'a>) -> Option<Self> {
158        let range = table.chained_seq_rule_set_offsets_byte_range();
159        Some(Self {
160            rule_sets: RuleSets::new(table.offset_data(), range, NARROW.into()),
161            layout: RuleLayout::new(true, NARROW),
162            wide_glyphs: false,
163        })
164    }
165
166    pub fn new_wide(table: &ChainedSequenceContextFormat4<'a>) -> Option<Self> {
167        let range = table.chained_seq_rule_set_offsets_byte_range();
168        Some(Self {
169            rule_sets: RuleSets::new(table.offset_data(), range, WIDE.into()),
170            layout: RuleLayout::new(true, WIDE),
171            wide_glyphs: true,
172        })
173    }
174
175    pub fn from_plain(table: &SequenceContextFormat1<'a>) -> Option<Self> {
176        let range = table.seq_rule_set_offsets_byte_range();
177        Some(Self {
178            rule_sets: RuleSets::new(table.offset_data(), range, NARROW.into()),
179            layout: RuleLayout::new(false, NARROW),
180            wide_glyphs: false,
181        })
182    }
183
184    pub fn from_plain_wide(table: &SequenceContextFormat4<'a>) -> Option<Self> {
185        let range = table.seq_rule_set_offsets_byte_range();
186        // Its rule sets keep 16-bit offsets to their rules.
187        Some(Self {
188            rule_sets: RuleSets::new(table.offset_data(), range, WIDE.into()),
189            layout: RuleLayout::new(false, NARROW),
190            wide_glyphs: true,
191        })
192    }
193
194    fn rule_set(&self, index: usize) -> Option<Rules<'a>> {
195        rule_set(&self.rule_sets, index, self.layout)
196    }
197
198    pub fn apply(&self, ctx: &mut ApplyContext, index: u32) -> Option<()> {
199        let rules = self.rule_set(index as usize)?;
200        let matchers = ChainMatchers {
201            backtrack: &match_glyph,
202            input: &match_glyph,
203            lookahead: &match_glyph,
204        };
205        if self.wide_glyphs {
206            apply_chain_rules::<GLYPH24>(ctx, rules, &matchers, None, &|_| 0)
207        } else {
208            apply_chain_rules::<CLASS>(ctx, rules, &matchers, None, &|_| 0)
209        }
210    }
211
212    pub fn would_apply(&self, ctx: &WouldApplyContext, coverage: &Coverage) -> bool {
213        coverage
214            .get(ctx.glyphs[0])
215            .and_then(|index| self.rule_set(index as usize))
216            .is_some_and(|rules| {
217                if self.wide_glyphs {
218                    would_apply_chain_rules::<GLYPH24>(ctx, rules, &match_glyph)
219                } else {
220                    would_apply_chain_rules::<CLASS>(ctx, rules, &match_glyph)
221                }
222            })
223    }
224}
225
226impl<'a> SubtableDigests<'a> for ChainContext1<'a> {
227    fn digest_second(&self, budget: &Budget) -> Result<SetDigest, Exhausted> {
228        if self.wide_glyphs {
229            glyph_seconds::<GLYPH24>(&self.rule_sets, self.layout, budget)
230        } else {
231            glyph_seconds::<CLASS>(&self.rule_sets, self.layout, budget)
232        }
233    }
234}
235
236/// The glyphs that may follow the first one in a match of a glyph rule.
237fn glyph_seconds<const W: usize>(
238    sets: &RuleSets,
239    layout: RuleLayout,
240    budget: &Budget,
241) -> Result<SetDigest, Exhausted> {
242    let mut digest = SetDigest::new();
243    let valid = for_each_rule::<W>(sets, layout, budget, |rule| {
244        let Some(second) = rule.input.first().or_else(|| rule.lookahead.first()) else {
245            return Ok(None);
246        };
247        digest.add(second);
248        Ok(Some(()))
249    })?;
250    Ok(valid.map_or_else(SetDigest::full, |()| digest))
251}
252
253/// Chained context by glyph class sequences, or context by glyph class
254/// sequences.
255pub(crate) struct ChainContext2<'a> {
256    backtrack: ClassDef<'a>,
257    input: ClassDef<'a>,
258    lookahead: ClassDef<'a>,
259    class_caches: Option<Box<ChainClassCaches>>,
260    rule_sets: RuleSets<'a>,
261    layout: RuleLayout,
262    /// The first input class of each rule set's rules.
263    rule_set_digests: Box<[RuleSetDigest]>,
264}
265
266/// Caches of the input and lookahead classes of a glyph.
267struct ChainClassCaches {
268    input: MappingCache,
269    lookahead: MappingCache,
270}
271
272impl<'a> ChainContext2<'a> {
273    pub fn new(
274        table: &ChainedSequenceContextFormat2<'a>,
275        with_caches: bool,
276        budget: &Budget,
277    ) -> Result<Self, Exhausted> {
278        let range = table.chained_class_seq_rule_set_offsets_byte_range();
279        Self::from_parts(
280            ClassDef::new(table.backtrack_class_def()),
281            ClassDef::new(table.input_class_def()),
282            ClassDef::new(table.lookahead_class_def()),
283            RuleSets::new(table.offset_data(), range, NARROW.into()),
284            RuleLayout::new(true, NARROW),
285            with_caches,
286            budget,
287        )
288    }
289
290    pub fn new_wide(
291        table: &ChainedSequenceContextFormat5<'a>,
292        with_caches: bool,
293        budget: &Budget,
294    ) -> Result<Self, Exhausted> {
295        let range = table.chained_class_seq_rule_set_offsets_byte_range();
296        Self::from_parts(
297            ClassDef::new(table.backtrack_class_def()),
298            ClassDef::new(table.input_class_def()),
299            ClassDef::new(table.lookahead_class_def()),
300            RuleSets::new(table.offset_data(), range, WIDE.into()),
301            RuleLayout::new(true, WIDE),
302            with_caches,
303            budget,
304        )
305    }
306
307    pub fn from_plain(
308        table: &SequenceContextFormat2<'a>,
309        with_caches: bool,
310        budget: &Budget,
311    ) -> Result<Self, Exhausted> {
312        let range = table.class_seq_rule_set_offsets_byte_range();
313        Self::from_parts(
314            ClassDef::None,
315            ClassDef::new(table.class_def()),
316            ClassDef::None,
317            RuleSets::new(table.offset_data(), range, NARROW.into()),
318            RuleLayout::new(false, NARROW),
319            with_caches,
320            budget,
321        )
322    }
323
324    pub fn from_plain_wide(
325        table: &SequenceContextFormat5<'a>,
326        with_caches: bool,
327        budget: &Budget,
328    ) -> Result<Self, Exhausted> {
329        let range = table.class_seq_rule_set_offsets_byte_range();
330        Self::from_parts(
331            ClassDef::None,
332            ClassDef::new(table.class_def()),
333            ClassDef::None,
334            RuleSets::new(table.offset_data(), range, WIDE.into()),
335            RuleLayout::new(false, WIDE),
336            with_caches,
337            budget,
338        )
339    }
340
341    fn from_parts(
342        backtrack: ClassDef<'a>,
343        input: ClassDef<'a>,
344        lookahead: ClassDef<'a>,
345        rule_sets: RuleSets<'a>,
346        layout: RuleLayout,
347        with_caches: bool,
348        budget: &Budget,
349    ) -> Result<Self, Exhausted> {
350        if with_caches {
351            budget.alloc::<ChainClassCaches>(1)?;
352        }
353        Ok(Self {
354            backtrack,
355            input,
356            lookahead,
357            class_caches: with_caches.then(|| {
358                Box::new(ChainClassCaches {
359                    input: MappingCache::new(),
360                    lookahead: MappingCache::new(),
361                })
362            }),
363            rule_set_digests: rule_set_digests(&rule_sets, layout, budget)?,
364            rule_sets,
365            layout,
366        })
367    }
368
369    fn rule_set(&self, index: usize) -> Option<Rules<'a>> {
370        rule_set(&self.rule_sets, index, self.layout)
371    }
372
373    /// The input class of a glyph, kept in its syllable byte if
374    /// `class_cache` is set.
375    #[inline(always)]
376    fn input_class(&self, info: &mut GlyphInfo, class_cache: bool) -> u32 {
377        let class_of = |gid| self.input.get(gid);
378        if !class_cache {
379            self.mapped_input_class(info.as_glyph())
380        } else if self.layout.chained {
381            // The lookahead class takes the low nibble.
382            SyllableSlot::HIGH.class(&class_of, info)
383        } else {
384            SyllableSlot::FULL.class(&class_of, info)
385        }
386    }
387
388    #[inline(always)]
389    fn lookahead_class(&self, info: &mut GlyphInfo, class_cache: bool) -> u32 {
390        if class_cache {
391            SyllableSlot::LOW.class(&|gid| self.lookahead.get(gid), info)
392        } else {
393            self.mapped_lookahead_class(info.as_glyph())
394        }
395    }
396
397    // The mapping-cache paths stay out of line so that the syllable-byte
398    // reads inline into the matchers.
399    #[inline(never)]
400    fn mapped_input_class(&self, gid: GlyphId) -> u32 {
401        let cache = self.class_caches.as_deref().map(|c| &c.input);
402        cached_class(&self.input, gid, cache)
403    }
404
405    #[inline(never)]
406    fn mapped_lookahead_class(&self, gid: GlyphId) -> u32 {
407        let cache = self.class_caches.as_deref().map(|c| &c.lookahead);
408        cached_class(&self.lookahead, gid, cache)
409    }
410
411    /// Applies, keeping glyph classes in the syllable byte if `class_cache`
412    /// is set, and in the subtable's mapping caches otherwise.
413    #[inline(never)]
414    pub fn apply(&self, ctx: &mut ApplyContext, _index: u32, class_cache: bool) -> Option<()> {
415        let info = ctx.buffer.info.get_mut(ctx.buffer.idx).likely()?;
416        let index = self.input_class(info, class_cache) as usize;
417        let matchers = ChainMatchers {
418            backtrack: &|info: &mut GlyphInfo, value| self.backtrack.get(info.as_glyph()) == value,
419            input: &|info: &mut GlyphInfo, value| self.input_class(info, class_cache) == value,
420            lookahead: &|info: &mut GlyphInfo, value| {
421                self.lookahead_class(info, class_cache) == value
422            },
423        };
424        apply_chain_rules::<CLASS>(
425            ctx,
426            self.rule_set(index)?,
427            &matchers,
428            self.rule_set_digests.get(index).copied(),
429            &|info| self.input_class(info, class_cache),
430        )
431    }
432
433    pub fn would_apply(&self, ctx: &WouldApplyContext, _coverage: &Coverage) -> bool {
434        let matches = |info: &mut GlyphInfo, value| self.input.get(info.as_glyph()) == value;
435        self.rule_set(self.input.get(ctx.glyphs[0]) as usize)
436            .is_some_and(|rules| would_apply_chain_rules::<CLASS>(ctx, rules, &matches))
437    }
438}
439
440impl<'a> SubtableDigests<'a> for ChainContext2<'a> {
441    const CACHES_COVERAGE: bool = true;
442
443    fn digest_second(&self, budget: &Budget) -> Result<SetDigest, Exhausted> {
444        let (input, lookahead) = (&self.input, &self.lookahead);
445        if input.is_none() {
446            return Ok(SetDigest::full());
447        }
448        let mut digest = SetDigest::new();
449        let valid = for_each_rule::<CLASS>(&self.rule_sets, self.layout, budget, |rule| {
450            if let Some(second) = rule.input.first() {
451                input.add_class_to(&mut digest, second, budget)?;
452            } else {
453                // A missing class definition puts every glyph in class 0.
454                let Some(second) = rule.lookahead.first().filter(|_| !lookahead.is_none()) else {
455                    return Ok(None);
456                };
457                lookahead.add_class_to(&mut digest, second, budget)?;
458            }
459            Ok(Some(()))
460        })?;
461        Ok(valid.map_or_else(SetDigest::full, |()| digest))
462    }
463
464    fn cache_cost(&self) -> u32 {
465        self.input.cost() + self.lookahead.cost()
466    }
467}
468
469/// Chained context by a coverage per glyph, or context by a coverage per
470/// glyph.
471pub(crate) struct ChainContext3<'a> {
472    /// The coverages of the input glyphs after the first.
473    inputs: CoverageArray<'a>,
474    backtrack: CoverageArray<'a>,
475    lookahead: CoverageArray<'a>,
476    records: &'a [SequenceLookupRecord],
477    chained: bool,
478}
479
480impl<'a> ChainContext3<'a> {
481    pub fn new(
482        table: &ChainedSequenceContextFormat3<'a>,
483        budget: &Budget,
484    ) -> Result<Self, Exhausted> {
485        let data = table.offset_data();
486        let narrow = NARROW.into();
487        Ok(Self {
488            inputs: CoverageArray::new(
489                Offsets::after_first(data, table.input_coverage_offsets_byte_range(), narrow),
490                budget,
491            )?,
492            backtrack: CoverageArray::new(
493                Offsets::new(data, table.backtrack_coverage_offsets_byte_range(), narrow),
494                budget,
495            )?,
496            lookahead: CoverageArray::new(
497                Offsets::new(data, table.lookahead_coverage_offsets_byte_range(), narrow),
498                budget,
499            )?,
500            records: table.seq_lookup_records(),
501            chained: true,
502        })
503    }
504
505    pub fn from_plain(
506        table: &SequenceContextFormat3<'a>,
507        budget: &Budget,
508    ) -> Result<Self, Exhausted> {
509        let range = table.coverage_offsets_byte_range();
510        let inputs = Offsets::after_first(table.offset_data(), range, NARROW.into());
511        Self::from_plain_parts(inputs, table.seq_lookup_records(), budget)
512    }
513
514    pub fn from_plain_wide(
515        table: &SequenceContextFormat6<'a>,
516        budget: &Budget,
517    ) -> Result<Self, Exhausted> {
518        let range = table.coverage_offsets_byte_range();
519        let inputs = Offsets::after_first(table.offset_data(), range, WIDE.into());
520        Self::from_plain_parts(inputs, table.seq_lookup_records(), budget)
521    }
522
523    fn from_plain_parts(
524        inputs: Offsets<'a>,
525        records: &'a [SequenceLookupRecord],
526        budget: &Budget,
527    ) -> Result<Self, Exhausted> {
528        Ok(Self {
529            inputs: CoverageArray::new(inputs, budget)?,
530            backtrack: CoverageArray::default(),
531            lookahead: CoverageArray::default(),
532            records,
533            chained: false,
534        })
535    }
536
537    pub fn apply(&self, ctx: &mut ApplyContext, _index: u32) -> Option<()> {
538        let mut end_index = ctx.buffer.idx;
539        let mut match_end = 0;
540        let input_matches = match_input(
541            ctx,
542            self.inputs.len() as u16,
543            |info, index| covered_at(&self.inputs, index, info),
544            &mut match_end,
545            None,
546        )?;
547        if !self.chained {
548            if !input_matches {
549                ctx.buffer
550                    .unsafe_to_concat(Some(ctx.buffer.idx), Some(match_end));
551                return None;
552            }
553            ctx.buffer
554                .unsafe_to_break(Some(ctx.buffer.idx), Some(match_end));
555            apply_lookup(ctx, self.inputs.len(), match_end, self.records);
556            return Some(());
557        }
558        if input_matches {
559            end_index = match_end;
560        }
561        if !(input_matches
562            && match_lookahead(
563                ctx,
564                self.lookahead.len() as u16,
565                |info, index| covered_at(&self.lookahead, index, info),
566                match_end,
567                &mut end_index,
568            ))
569        {
570            ctx.buffer
571                .unsafe_to_concat(Some(ctx.buffer.idx), Some(end_index));
572            return None;
573        }
574        let mut start_index = ctx.buffer.out_len;
575        if !match_backtrack(
576            ctx,
577            self.backtrack.len() as u16,
578            |info, index| covered_at(&self.backtrack, index, info),
579            &mut start_index,
580        ) {
581            ctx.buffer
582                .unsafe_to_concat_from_outbuffer(Some(start_index), Some(end_index));
583            return None;
584        }
585        ctx.buffer
586            .unsafe_to_break_from_outbuffer(Some(start_index), Some(end_index));
587        apply_lookup(ctx, self.inputs.len(), match_end, self.records);
588        Some(())
589    }
590
591    pub fn would_apply(&self, ctx: &WouldApplyContext, _coverage: &Coverage) -> bool {
592        (!ctx.zero_context || (self.backtrack.is_empty() && self.lookahead.is_empty()))
593            && ctx.glyphs.len() == self.inputs.len() + 1
594            && ctx.glyphs[1..]
595                .iter()
596                .enumerate()
597                .all(|(index, glyph)| self.inputs.get(index).covers(*glyph))
598    }
599}
600
601impl<'a> SubtableDigests<'a> for ChainContext3<'a> {
602    fn digest_second(&self, budget: &Budget) -> Result<SetDigest, Exhausted> {
603        if self.inputs.is_empty() {
604            self.lookahead.get(0).digest(budget)
605        } else {
606            self.inputs.get(0).digest(budget)
607        }
608    }
609}
610
611/// Where a glyph's class is kept in its syllable byte while a lookup
612/// applies: in the bits of `unknown` shifted left by `shift`, where the
613/// value `unknown` means the class isn't known yet.
614#[derive(Clone, Copy)]
615struct SyllableSlot {
616    shift: u8,
617    unknown: u8,
618}
619
620impl SyllableSlot {
621    /// The input class of a chained context.
622    const HIGH: Self = Self {
623        shift: 4,
624        unknown: 15,
625    };
626    /// The lookahead class of a chained context.
627    const LOW: Self = Self {
628        shift: 0,
629        unknown: 15,
630    };
631    /// The input class of a context, which has no lookahead.
632    const FULL: Self = Self {
633        shift: 0,
634        unknown: 255,
635    };
636
637    /// The class of the glyph, looked up with `class_def` the first time.
638    #[inline(always)]
639    fn class(self, class_def: &impl Fn(GlyphId) -> u32, info: &mut GlyphInfo) -> u32 {
640        let cached = (info.syllable() >> self.shift) & self.unknown;
641        if cached < self.unknown {
642            return u32::from(cached);
643        }
644        let class = class_def(info.as_glyph());
645        if class < u32::from(self.unknown) {
646            let mask = self.unknown << self.shift;
647            info.set_syllable((info.syllable() & !mask) | ((class as u8) << self.shift));
648        }
649        class
650    }
651}
652
653/// The rules of a rule set, read on demand from their offsets.
654#[derive(Clone, Copy)]
655struct Rules<'a> {
656    data: FontData<'a>,
657    offsets: Uints<'a>,
658    layout: RuleLayout,
659}
660
661impl<'a> Rules<'a> {
662    /// Reads a rule set: a 16-bit count and the offsets to its rules.
663    fn read(data: FontData<'a>, layout: RuleLayout) -> Option<Self> {
664        let count = usize::from(data.read_at::<u16>(0).ok()?);
665        let offsets = Uints::at(data, 2, count, layout.offset_width.into())?;
666        Some(Self {
667            data,
668            offsets,
669            layout,
670        })
671    }
672
673    fn len(&self) -> usize {
674        self.offsets.len()
675    }
676
677    /// The data of rule `index`, if it holds at least the fixed fields of
678    /// a rule, as reading the rule table would require.
679    fn rule(&self, index: usize) -> Option<FontData<'a>> {
680        // The extended rules have the same fixed fields.
681        let min_size = if self.layout.chained {
682            ChainedSequenceRule::MIN_SIZE
683        } else {
684            SequenceRule::MIN_SIZE
685        };
686        let data = self.data.split_off(self.offsets.get(index)? as usize)?;
687        (data.len() >= min_size).then_some(data)
688    }
689}
690
691/// A rule's fields, parsed in one pass. Glyph IDs and classes are both
692/// read as plain values of `W` bytes; a sequence rule has no backtrack or
693/// lookahead.
694#[derive(Clone, Copy, Default)]
695struct ParsedRule<'a, const W: usize> {
696    backtrack: Values<'a, W>,
697    input: Values<'a, W>,
698    lookahead: Values<'a, W>,
699    records: &'a [SequenceLookupRecord],
700    chained: bool,
701}
702
703impl<'a, const W: usize> ParsedRule<'a, W> {
704    /// Parses a rule; an unreadable one is empty.
705    fn parse(data: FontData<'a>, layout: RuleLayout) -> Self {
706        Self::try_parse(data, layout).unwrap_or_else(|| Self {
707            chained: layout.chained,
708            ..Self::default()
709        })
710    }
711
712    fn try_parse(data: FontData<'a>, layout: RuleLayout) -> Option<Self> {
713        if layout.chained {
714            Self::try_chain(data)
715        } else {
716            Self::try_plain(data)
717        }
718    }
719
720    /// Parses a sequence rule or class sequence rule.
721    fn try_plain(data: FontData<'a>) -> Option<Self> {
722        let glyph_count = usize::from(data.read_at::<u16>(0).ok()?);
723        let record_count = usize::from(data.read_at::<u16>(2).ok()?);
724        let input_end = 4 + glyph_count.saturating_sub(1) * W;
725        let records_end = input_end + record_count * SequenceLookupRecord::RAW_BYTE_LEN;
726        Some(Self {
727            input: Values::at(data, 4, glyph_count.saturating_sub(1))?,
728            records: data.read_array(input_end..records_end).ok()?,
729            ..Self::default()
730        })
731    }
732
733    /// Parses a chained sequence rule or chained class sequence rule.
734    fn try_chain(data: FontData<'a>) -> Option<Self> {
735        let backtrack_count = usize::from(data.read_at::<u16>(0).ok()?);
736        let backtrack_end = 2 + backtrack_count * W;
737        let input_count = usize::from(data.read_at::<u16>(backtrack_end).ok()?);
738        let input_end = backtrack_end + 2 + input_count.saturating_sub(1) * W;
739        let lookahead_count = usize::from(data.read_at::<u16>(input_end).ok()?);
740        let lookahead_end = input_end + 2 + lookahead_count * W;
741        let record_count = usize::from(data.read_at::<u16>(lookahead_end).ok()?);
742        let records_end = lookahead_end + 2 + record_count * SequenceLookupRecord::RAW_BYTE_LEN;
743        Some(Self {
744            backtrack: Values::at(data, 2, backtrack_count)?,
745            input: Values::at(data, backtrack_end + 2, input_count.saturating_sub(1))?,
746            lookahead: Values::at(data, input_end + 2, lookahead_count)?,
747            records: data.read_array(lookahead_end + 2..records_end).ok()?,
748            chained: true,
749        })
750    }
751
752    /// Matches the input, lookahead and backtrack sequences in that order
753    /// and applies the lookup records.
754    fn apply(
755        &self,
756        ctx: &mut ApplyContext,
757        matchers: &ChainMatchers<impl Matcher, impl Matcher, impl Matcher>,
758    ) -> Option<()> {
759        let mut end_index = ctx.buffer.idx;
760        let mut match_end = 0;
761        if !match_input(
762            ctx,
763            self.input.len() as u16,
764            |info, index| sequence_matches(&self.input, index, info, &matchers.input),
765            &mut match_end,
766            None,
767        )? {
768            if self.chained {
769                ctx.buffer
770                    .unsafe_to_concat(Some(ctx.buffer.idx), Some(end_index));
771            }
772            return None;
773        }
774        if !self.chained {
775            ctx.buffer
776                .unsafe_to_break(Some(ctx.buffer.idx), Some(match_end));
777            apply_lookup(ctx, self.input.len(), match_end, self.records);
778            return Some(());
779        }
780        end_index = match_end;
781        if !match_lookahead(
782            ctx,
783            self.lookahead.len() as u16,
784            |info, index| sequence_matches(&self.lookahead, index, info, &matchers.lookahead),
785            match_end,
786            &mut end_index,
787        ) {
788            ctx.buffer
789                .unsafe_to_concat(Some(ctx.buffer.idx), Some(end_index));
790            return None;
791        }
792        let mut start_index = ctx.buffer.out_len;
793        if !match_backtrack(
794            ctx,
795            self.backtrack.len() as u16,
796            |info, index| sequence_matches(&self.backtrack, index, info, &matchers.backtrack),
797            &mut start_index,
798        ) {
799            ctx.buffer
800                .unsafe_to_concat_from_outbuffer(Some(start_index), Some(end_index));
801            return None;
802        }
803        ctx.buffer
804            .unsafe_to_break_from_outbuffer(Some(start_index), Some(end_index));
805        apply_lookup(ctx, self.input.len(), match_end, self.records);
806        Some(())
807    }
808}
809
810/// Whether the glyph matches value `index` of `sequence`.
811fn sequence_matches<const W: usize>(
812    sequence: &Values<W>,
813    index: u32,
814    info: &mut GlyphInfo,
815    matches: &impl Fn(&mut GlyphInfo, u32) -> bool,
816) -> bool {
817    sequence
818        .get(index as usize)
819        .is_some_and(|value| matches(info, value))
820}
821
822/// How a chain rule matches each of its three sequences.
823struct ChainMatchers<B, I, L> {
824    backtrack: B,
825    input: I,
826    lookahead: L,
827}
828
829/// Matches a glyph against a rule value in a rule walk.
830trait Matcher: Fn(&mut GlyphInfo, u32) -> bool {}
831
832impl<F: Fn(&mut GlyphInfo, u32) -> bool> Matcher for F {}
833
834/// The first input value of a rule, after any backtrack: the second glyph
835/// of a match.
836fn rule_first_input<const W: usize>(data: &FontData, layout: RuleLayout) -> Option<u32> {
837    RuleProbe::<W>::new(*data, layout)
838        .filter(|probe| probe.input_count > 1)?
839        .input(0)
840}
841
842/// Reads the values of a rule that the pre-match needs, without parsing
843/// the rule.
844struct RuleProbe<'a, const W: usize> {
845    data: FontData<'a>,
846    input_start: usize,
847    input_end: usize,
848    input_count: u16,
849    chained: bool,
850}
851
852impl<'a, const W: usize> RuleProbe<'a, W> {
853    fn new(data: FontData<'a>, layout: RuleLayout) -> Option<Self> {
854        // A sequence rule's lookup count sits between its glyph count and
855        // its input.
856        let (count_pos, input_start) = if layout.chained {
857            let backtrack_count = usize::from(data.read_at::<u16>(0).ok()?);
858            let count_pos = 2 + backtrack_count * W;
859            (count_pos, count_pos + 2)
860        } else {
861            (0, 4)
862        };
863        let input_count: u16 = data.read_at(count_pos).ok()?;
864        let input_end = input_start + usize::from(input_count).saturating_sub(1) * W;
865        Some(Self {
866            data,
867            input_start,
868            input_end,
869            input_count,
870            chained: layout.chained,
871        })
872    }
873
874    /// The length of the input sequence, including the first glyph.
875    fn input_len(&self) -> usize {
876        usize::from(self.input_count).max(1)
877    }
878
879    fn input(&self, index: usize) -> Option<u32> {
880        super::read_be::<W>(self.data.as_bytes(), self.input_start + index * W)
881    }
882
883    fn lookahead_len(&self) -> usize {
884        if !self.chained {
885            return 0;
886        }
887        usize::from(self.data.read_at::<u16>(self.input_end).unwrap_or(0))
888    }
889
890    fn lookahead(&self, index: usize) -> Option<u32> {
891        super::read_be::<W>(self.data.as_bytes(), self.input_end + 2 + index * W)
892    }
893}
894
895/// Whether the glyph at `idx` matches `value`; a glyph outside the buffer
896/// never matches.
897fn matches_at(
898    info: &mut [GlyphInfo],
899    idx: usize,
900    value: u32,
901    matches: &impl Fn(&mut GlyphInfo, u32) -> bool,
902) -> bool {
903    info.get_mut(idx)
904        .likely()
905        .is_some_and(|info| matches(info, value))
906}
907
908/// The glyphs after the current one that rules are pre-matched against.
909struct Lookahead {
910    /// The glyph after the current one, and the end of the range a failed
911    /// match on it makes unsafe to concatenate.
912    first: usize,
913    unsafe_to1: usize,
914    /// The glyph after that, if there is one.
915    second: Option<usize>,
916    unsafe_to2: usize,
917}
918
919/// What the pre-match found after the current glyph.
920enum Prematch {
921    /// The rules are matched against these glyphs.
922    Glyphs(Lookahead),
923    /// A skippable glyph follows, so every rule must be tried in full.
924    TryAll,
925    /// Nothing follows; `unsafe_to` ends the range a match would depend on.
926    End { unsafe_to: usize },
927    /// The rule set digest rules out every rule.
928    Rejected,
929}
930
931/// Finds the glyphs that rules are pre-matched against. The context
932/// iterator, unlike the input one, doesn't skip default ignorables.
933/// https://github.com/harfbuzz/harfbuzz/issues/4813
934#[inline]
935fn prematch(
936    ctx: &mut ApplyContext,
937    has_rules: bool,
938    digest: Option<RuleSetDigest>,
939    first_value: &impl Fn(&mut GlyphInfo) -> u32,
940) -> Option<Prematch> {
941    let mut iter = SkippingIterator::with_match_fn(ctx, true, Some(match_always));
942    if iter.reset(iter.buffer.idx).is_none() {
943        iter.buffer.index_failed();
944    }
945    iter.set_glyph_data(0);
946    let mut unsafe_to1 = 0;
947    if !iter.next(Some(&mut unsafe_to1)) {
948        return Some(Prematch::End {
949            unsafe_to: unsafe_to1,
950        });
951    }
952    let first = iter.index();
953    if iter.may_skip(iter.buffer.info.get(first).likely()?) != MaySkip::No {
954        return Some(Prematch::TryAll);
955    }
956    let unsafe_to1 = first + 1;
957    if has_rules
958        && digest.is_some_and(|digest| {
959            !digest.is_full()
960                && iter
961                    .buffer
962                    .info
963                    .get_mut(first)
964                    .is_some_and(|info| !digest.may_have(first_value(info)))
965        })
966    {
967        iter.buffer
968            .unsafe_to_concat(Some(iter.buffer.idx), Some(unsafe_to1));
969        return Some(Prematch::Rejected);
970    }
971    let mut second = None;
972    let mut unsafe_to2 = 0;
973    if iter.next(None) {
974        let index = iter.index();
975        if iter.may_skip(iter.buffer.info.get(index).likely()?) != MaySkip::No {
976            return Some(Prematch::TryAll);
977        }
978        second = Some(index);
979        unsafe_to2 = index + 1;
980    }
981    Some(Prematch::Glyphs(Lookahead {
982        first,
983        unsafe_to1,
984        second,
985        unsafe_to2,
986    }))
987}
988
989/// Returns the index of the first rule after `index` whose first input
990/// isn't `first`. Rules are sorted by it, so the ones skipped would fail the
991/// same way; unreadable rules are skipped too.
992fn skip_rules<const W: usize>(rules: Rules, mut index: usize, first: u32) -> usize {
993    loop {
994        index += 1;
995        if index >= rules.len()
996            || rules
997                .rule(index)
998                .is_some_and(|data| rule_first_input::<W>(&data, rules.layout) != Some(first))
999        {
1000            return index;
1001        }
1002    }
1003}
1004
1005/// Marks the range a rule walk depended on, then returns its result.
1006fn finish_rules(
1007    ctx: &mut ApplyContext,
1008    unsafe_to: Option<usize>,
1009    result: Option<()>,
1010) -> Option<()> {
1011    if let Some(unsafe_to) = unsafe_to {
1012        ctx.buffer
1013            .unsafe_to_concat(Some(ctx.buffer.idx), Some(unsafe_to));
1014    }
1015    result
1016}
1017
1018/// Applies the first rule of a rule set that matches.
1019///
1020/// Rules are pre-matched on the first two values after the current glyph,
1021/// from the input and then the lookahead, which rejects most of them
1022/// without parsing. HarfBuzz skips the pre-match for small rule sets; here
1023/// it is faster at every size.
1024#[inline(never)]
1025fn apply_chain_rules<const W: usize>(
1026    ctx: &mut ApplyContext,
1027    rules: Rules,
1028    matchers: &ChainMatchers<impl Matcher, impl Matcher, impl Matcher>,
1029    digest: Option<RuleSetDigest>,
1030    first_value: &impl Fn(&mut GlyphInfo) -> u32,
1031) -> Option<()> {
1032    let lookahead = match prematch(ctx, rules.len() != 0, digest, first_value)? {
1033        Prematch::Glyphs(lookahead) => lookahead,
1034        Prematch::Rejected => return None,
1035        Prematch::TryAll => {
1036            return (0..rules.len())
1037                .filter_map(|index| rules.rule(index))
1038                .find_map(|data| ParsedRule::<W>::parse(data, rules.layout).apply(ctx, matchers));
1039        }
1040        Prematch::End { unsafe_to } => {
1041            // Only rules without further input or lookahead can match.
1042            let mut unsafe_to_concat = false;
1043            for data in (0..rules.len()).filter_map(|index| rules.rule(index)) {
1044                let rule = ParsedRule::<W>::parse(data, rules.layout);
1045                if !rule.input.is_empty() || !rule.lookahead.is_empty() {
1046                    unsafe_to_concat = true;
1047                } else if rule.apply(ctx, matchers).is_some() {
1048                    return finish_rules(ctx, unsafe_to_concat.then_some(unsafe_to), Some(()));
1049                }
1050            }
1051            return finish_rules(ctx, unsafe_to_concat.then_some(unsafe_to), None);
1052        }
1053    };
1054    let mut unsafe_to = None;
1055    let mut index = 0;
1056    while index < rules.len() {
1057        let Some(data) = rules.rule(index) else {
1058            index += 1;
1059            continue;
1060        };
1061        let Some(probe) = RuleProbe::<W>::new(data, rules.layout) else {
1062            // An unreadable header parses as an empty rule.
1063            if ParsedRule::<W>::parse(data, rules.layout)
1064                .apply(ctx, matchers)
1065                .is_some()
1066            {
1067                return finish_rules(ctx, unsafe_to, Some(()));
1068            }
1069            index += 1;
1070            continue;
1071        };
1072        // A rule with one input glyph is pre-matched on its lookahead.
1073        let input_len = probe.input_len();
1074        let info = &mut ctx.buffer.info;
1075        let first_matches = if input_len > 1 {
1076            probe
1077                .input(0)
1078                .is_some_and(|v| matches_at(info, lookahead.first, v, &matchers.input))
1079        } else {
1080            probe.lookahead_len() == 0
1081                || probe
1082                    .lookahead(0)
1083                    .is_some_and(|v| matches_at(info, lookahead.first, v, &matchers.lookahead))
1084        };
1085        if first_matches {
1086            let second_matches = lookahead.second.is_none_or(|second| {
1087                if input_len > 2 {
1088                    probe
1089                        .input(1)
1090                        .is_some_and(|v| matches_at(info, second, v, &matchers.input))
1091                } else {
1092                    probe.lookahead_len() <= 2 - input_len
1093                        || probe
1094                            .lookahead(2 - input_len)
1095                            .is_some_and(|v| matches_at(info, second, v, &matchers.lookahead))
1096                }
1097            });
1098            if !second_matches {
1099                unsafe_to = Some(lookahead.unsafe_to2);
1100            } else if ParsedRule::<W>::parse(data, rules.layout)
1101                .apply(ctx, matchers)
1102                .is_some()
1103            {
1104                return finish_rules(ctx, unsafe_to, Some(()));
1105            }
1106            index += 1;
1107        } else {
1108            unsafe_to.get_or_insert(lookahead.unsafe_to1);
1109            index = match (input_len > 1).then(|| probe.input(0)).flatten() {
1110                Some(first) => skip_rules::<W>(rules, index, first),
1111                None => index + 1,
1112            };
1113        }
1114    }
1115    finish_rules(ctx, unsafe_to, None)
1116}
1117
1118/// Whether a rule of `rules` matches the glyphs of `ctx`.
1119fn would_apply_chain_rules<const W: usize>(
1120    ctx: &WouldApplyContext,
1121    rules: Rules,
1122    matches: MatchFn,
1123) -> bool {
1124    (0..rules.len())
1125        .filter_map(|index| ParsedRule::<W>::try_parse(rules.rule(index)?, rules.layout))
1126        .any(|rule| {
1127            (!ctx.zero_context || (rule.backtrack.is_empty() && rule.lookahead.is_empty()))
1128                && sequence_would_apply(ctx, &rule.input, matches)
1129        })
1130}
1131
1132/// Whether `input` matches the glyphs of `ctx` after the first.
1133fn sequence_would_apply<const W: usize>(
1134    ctx: &WouldApplyContext,
1135    input: &Values<W>,
1136    matches: MatchFn,
1137) -> bool {
1138    ctx.glyphs.len() == input.len() + 1
1139        && input.iter().zip(&ctx.glyphs[1..]).all(|(value, glyph)| {
1140            let mut info = GlyphInfo {
1141                glyph_id: (*glyph).into(),
1142                ..GlyphInfo::default()
1143            };
1144            matches(&mut info, value)
1145        })
1146}