Skip to main content

read_fonts/tables/gsub/
closure.rs

1//! Computing the closure over a set of glyphs
2//!
3//! This means taking a set of glyphs and updating it to include any other glyphs
4//! reachable from those glyphs via substitution, recursively.
5mod extended;
6
7#[cfg(test)]
8mod contextual_tests;
9
10use font_types::GlyphId;
11
12use crate::{
13    collections::{FastHashMap, IntSet},
14    tables::layout::{ExtensionLookup, Subtables},
15    FontRead, ReadError, Tag,
16};
17
18use super::{
19    AlternateSubstFormat1, ChainedSequenceContext, ClassDef, ExtensionSubstFormat1,
20    ExtensionSubtable, Gsub, Ligature, LigatureSet, LigatureSubstFormat1, MultipleSubstFormat1,
21    ReverseChainSingleSubstFormat1, SequenceContext, SingleSubst, SingleSubstFormat1,
22    SingleSubstFormat2, SubstitutionLookup, SubstitutionLookupList, SubstitutionSubtables,
23};
24
25#[cfg(feature = "std")]
26use crate::tables::layout::{
27    ContextFormat1, ContextFormat2, ContextFormat3, Intersect, LayoutLookupList, LookupClosure,
28    LookupClosureCtx, SeqCache,
29};
30
31// we put ClosureCtx in its own module to enforce visibility rules;
32// specifically we don't want cur_glyphs to be reachable directly
33mod ctx {
34    use std::collections::HashMap;
35    use types::GlyphId;
36
37    use crate::{
38        collections::IntSet,
39        tables::gsub::{SubstitutionLookup, SubstitutionLookupList},
40    };
41
42    use super::GlyphClosure as _;
43    use super::ReadError;
44
45    #[cfg(feature = "std")]
46    use crate::limits::{MAX_LOOKUP_VISIT_COUNT, MAX_RECURSION_DEPTH};
47
48    pub(super) struct ClosureCtx<'a> {
49        /// the current closure glyphs. This is updated as we go.
50        pub(super) glyphs: &'a mut IntSet<GlyphId>,
51        pub(super) active_glyphs_stack: Vec<IntSet<GlyphId>>,
52        pub(super) output: IntSet<GlyphId>,
53        /// If set, glyph ids at or past this are not in the font and are dropped
54        /// from the output when it is flushed.
55        num_glyphs: Option<u32>,
56        lookup_count: u16,
57        nesting_level_left: usize,
58        done_lookups_glyphs: HashMap<u16, (u64, IntSet<GlyphId>)>,
59    }
60
61    impl<'a> ClosureCtx<'a> {
62        pub(super) fn new(glyphs: &'a mut IntSet<GlyphId>, num_glyphs: Option<u32>) -> Self {
63            Self {
64                glyphs,
65                active_glyphs_stack: Vec::new(),
66                output: IntSet::empty(),
67                num_glyphs,
68                lookup_count: 0,
69                nesting_level_left: MAX_RECURSION_DEPTH,
70                done_lookups_glyphs: Default::default(),
71            }
72        }
73
74        pub(super) fn lookup_limit_exceed(&self) -> bool {
75            self.lookup_count > MAX_LOOKUP_VISIT_COUNT
76        }
77
78        pub(super) fn parent_active_glyphs(&self) -> &IntSet<GlyphId> {
79            if self.active_glyphs_stack.is_empty() {
80                return &*self.glyphs;
81            }
82
83            self.active_glyphs_stack.last().unwrap()
84        }
85
86        pub(super) fn push_cur_active_glyphs(&mut self, glyphs: IntSet<GlyphId>) {
87            self.active_glyphs_stack.push(glyphs)
88        }
89
90        pub(super) fn pop_cur_done_glyphs(&mut self) {
91            self.active_glyphs_stack.pop();
92        }
93
94        #[allow(clippy::too_many_arguments)]
95        pub(super) fn recurse(
96            &mut self,
97            lookup_list: &SubstitutionLookupList,
98            lookup: &SubstitutionLookup,
99            lookup_index: u16,
100            glyphs: IntSet<GlyphId>,
101            seen_seq_indices: &mut IntSet<u16>,
102            seq_idx: u16,
103            end_idx: u16,
104        ) -> Result<(), ReadError> {
105            if self.nesting_level_left == 0 {
106                return Ok(());
107            }
108
109            self.nesting_level_left -= 1;
110            self.push_cur_active_glyphs(glyphs);
111
112            if !self.should_visit_lookup(lookup_index) {
113                self.nesting_level_left += 1;
114                self.pop_cur_done_glyphs();
115                return Ok(());
116            }
117
118            if lookup.may_have_non_1to1()? {
119                seen_seq_indices.insert_range(seq_idx..=end_idx);
120            }
121            lookup
122                .subtables()?
123                .closure_glyphs(self, lookup_list, lookup_index)?;
124
125            self.nesting_level_left += 1;
126            self.pop_cur_done_glyphs();
127
128            Ok(())
129        }
130
131        pub(super) fn reset_lookup_visit_count(&mut self) {
132            self.lookup_count = 0;
133        }
134
135        pub(super) fn should_visit_lookup(&mut self, lookup_index: u16) -> bool {
136            if self.lookup_limit_exceed() {
137                return false;
138            }
139            self.lookup_count += 1;
140            !self.is_lookup_done(lookup_index)
141        }
142
143        // Return true if we have visited this lookup with current set of glyphs
144        pub(super) fn is_lookup_done(&mut self, lookup_index: u16) -> bool {
145            let cur_active_glyphs = self.active_glyphs_stack.last().unwrap_or(self.glyphs);
146
147            let (count, covered) = self
148                .done_lookups_glyphs
149                .entry(lookup_index)
150                .or_insert((0, IntSet::empty()));
151
152            if *count != self.glyphs.len() {
153                *count = self.glyphs.len();
154                covered.clear();
155            }
156
157            if cur_active_glyphs.is_subset(covered) {
158                return true;
159            }
160
161            covered.union(cur_active_glyphs);
162            false
163        }
164
165        pub(super) fn glyphs(&self) -> &IntSet<GlyphId> {
166            self.glyphs
167        }
168
169        pub(super) fn add(&mut self, gid: GlyphId) {
170            self.output.insert(gid);
171        }
172
173        pub(super) fn flush(&mut self) {
174            // Drop glyphs that are not in the font before they join the closure,
175            // so that they can't make other lookups reachable.
176            // ref: <https://github.com/harfbuzz/harfbuzz/blob/a69b43c1fd86f43d66f6d84e087d79a5b1e0cf04/src/hb-ot-layout-gsubgpos.hh#L190-L197>
177            if let Some(num_glyphs) = self.num_glyphs {
178                self.output
179                    .remove_range(GlyphId::new(num_glyphs)..=GlyphId::new(u32::MAX));
180            }
181            self.glyphs.union(&self.output);
182            self.output.clear();
183            self.active_glyphs_stack.clear();
184        }
185    }
186}
187
188use ctx::ClosureCtx;
189
190/// A trait for tables which participate in closure
191trait GlyphClosure {
192    /// Update the set of glyphs with any glyphs reachable via substitution.
193    fn closure_glyphs(
194        &self,
195        ctx: &mut ClosureCtx,
196        lookup_list: &SubstitutionLookupList,
197        lookup_index: u16,
198    ) -> Result<(), ReadError>;
199
200    fn may_have_non_1to1(&self) -> Result<bool, ReadError> {
201        Ok(false)
202    }
203}
204
205const CLOSURE_MAX_STAGES: u8 = 12;
206impl Gsub<'_> {
207    /// Return the set of glyphs reachable from the input set via any substitution.
208    /// ref: <https://github.com/harfbuzz/harfbuzz/blob/8d517f7e43f648cb804c46c47ae8009330fe4a47/src/hb-ot-layout.cc#L1616>
209    ///
210    /// Every glyph id produced by a substitution is added, even if it is not a
211    /// glyph in the font. Use [`Self::closure_glyphs_with_num_glyphs`] to drop
212    /// those, as harfbuzz does.
213    pub fn closure_glyphs(
214        &self,
215        lookups: &IntSet<u16>,
216        glyphs: &mut IntSet<GlyphId>,
217    ) -> Result<(), ReadError> {
218        self.closure_glyphs_impl(lookups, glyphs, None)
219    }
220
221    /// Like [`Self::closure_glyphs`], but for a font with `num_glyphs` glyphs.
222    ///
223    /// Glyph ids at or past `num_glyphs` produced by a substitution are dropped
224    /// before they join the closure, so they are never added to `glyphs` and
225    /// can't make other lookups reachable. This matches harfbuzz.
226    pub fn closure_glyphs_with_num_glyphs(
227        &self,
228        lookups: &IntSet<u16>,
229        glyphs: &mut IntSet<GlyphId>,
230        num_glyphs: u32,
231    ) -> Result<(), ReadError> {
232        self.closure_glyphs_impl(lookups, glyphs, Some(num_glyphs))
233    }
234
235    fn closure_glyphs_impl(
236        &self,
237        lookups: &IntSet<u16>,
238        glyphs: &mut IntSet<GlyphId>,
239        num_glyphs: Option<u32>,
240    ) -> Result<(), ReadError> {
241        if self.selected_lookup_list_offset()?.is_null() {
242            return Ok(());
243        }
244        let lookup_list = self.lookup_list()?;
245        let num_lookups = lookup_list.lookup_count();
246        let lookup_offsets = lookup_list.lookups();
247
248        let mut ctx = ClosureCtx::new(glyphs, num_glyphs);
249        let mut iteration_count = 0;
250        let mut glyphs_length;
251        loop {
252            ctx.reset_lookup_visit_count();
253            glyphs_length = ctx.glyphs().len();
254
255            if lookups.is_inverted() {
256                for i in 0..num_lookups {
257                    if !lookups.contains(i) {
258                        continue;
259                    }
260                    let lookup = match lookup_offsets.get(i as usize) {
261                        Err(ReadError::NullOffset) => continue,
262                        other => other,
263                    }?;
264                    lookup.closure_glyphs(&mut ctx, &lookup_list, i)?;
265                    ctx.flush();
266                }
267            } else {
268                for i in lookups.iter() {
269                    let lookup = match lookup_offsets.get(i as usize) {
270                        Err(ReadError::NullOffset) | Err(ReadError::InvalidCollectionIndex(_)) => {
271                            continue
272                        }
273                        other => other,
274                    }?;
275                    lookup.closure_glyphs(&mut ctx, &lookup_list, i)?;
276                    ctx.flush();
277                }
278            }
279            if iteration_count > CLOSURE_MAX_STAGES || glyphs_length == ctx.glyphs().len() {
280                break;
281            }
282            iteration_count += 1;
283        }
284        Ok(())
285    }
286
287    /// Return a set of lookups referenced by the specified features
288    ///
289    /// Pass `&IntSet::all()` to get the lookups referenced by all features.
290    pub fn collect_lookups(&self, feature_indices: &IntSet<u16>) -> Result<IntSet<u16>, ReadError> {
291        if self.selected_feature_list_offset()?.is_null() {
292            return Ok(IntSet::empty());
293        }
294        let feature_list = self.feature_list()?;
295        let mut lookup_indices = feature_list.collect_lookups(feature_indices)?;
296
297        if let Some(feature_variations) = self.feature_variations().transpose()? {
298            let subs_lookup_indices = feature_variations.collect_lookups(feature_indices)?;
299            lookup_indices.union(&subs_lookup_indices);
300        }
301        Ok(lookup_indices)
302    }
303
304    /// Return a set of all feature indices underneath the specified scripts, languages and features
305    pub fn collect_features(
306        &self,
307        scripts: &IntSet<Tag>,
308        languages: &IntSet<Tag>,
309        features: &IntSet<Tag>,
310    ) -> Result<IntSet<u16>, ReadError> {
311        if self.selected_script_list_offset()?.is_null()
312            || self.selected_feature_list_offset()?.is_null()
313        {
314            return Ok(IntSet::empty());
315        }
316        let feature_list = self.feature_list()?;
317        let script_list = self.script_list()?;
318        let head_ptr = self.offset_data().as_bytes().as_ptr() as usize;
319        script_list.collect_features(head_ptr, &feature_list, scripts, languages, features)
320    }
321
322    /// Update the set of lookup indices with all lookups reachable from specified glyph set and lookup_indices.
323    pub fn closure_lookups(
324        &self,
325        glyphs: &IntSet<GlyphId>,
326        lookup_indices: &mut IntSet<u16>,
327    ) -> Result<(), ReadError> {
328        if self.selected_lookup_list_offset()?.is_null() {
329            return Ok(());
330        }
331        let lookup_list = self.lookup_list()?;
332        lookup_list.closure_lookups(glyphs, lookup_indices)
333    }
334}
335
336//ref: <https://github.com/harfbuzz/harfbuzz/blob/8d517f7e43f648cb804c46c47ae8009330fe4a47/src/OT/Layout/GSUB/SubstLookup.hh#L50>
337impl GlyphClosure for SubstitutionLookup<'_> {
338    fn closure_glyphs(
339        &self,
340        ctx: &mut ClosureCtx,
341        lookup_list: &SubstitutionLookupList,
342        lookup_index: u16,
343    ) -> Result<(), ReadError> {
344        if !ctx.should_visit_lookup(lookup_index) {
345            return Ok(());
346        }
347        self.subtables()?
348            .closure_glyphs(ctx, lookup_list, lookup_index)
349    }
350
351    fn may_have_non_1to1(&self) -> Result<bool, ReadError> {
352        self.subtables()?.may_have_non_1to1()
353    }
354}
355
356impl GlyphClosure for SubstitutionSubtables<'_> {
357    fn closure_glyphs(
358        &self,
359        ctx: &mut ClosureCtx,
360        lookup_list: &SubstitutionLookupList,
361        lookup_index: u16,
362    ) -> Result<(), ReadError> {
363        match self {
364            SubstitutionSubtables::Single(tables) => {
365                tables.closure_glyphs(ctx, lookup_list, lookup_index)
366            }
367            SubstitutionSubtables::Multiple(tables) => {
368                tables.closure_glyphs(ctx, lookup_list, lookup_index)
369            }
370            SubstitutionSubtables::Alternate(tables) => {
371                tables.closure_glyphs(ctx, lookup_list, lookup_index)
372            }
373            SubstitutionSubtables::Ligature(tables) => {
374                tables.closure_glyphs(ctx, lookup_list, lookup_index)
375            }
376            SubstitutionSubtables::Reverse(tables) => {
377                tables.closure_glyphs(ctx, lookup_list, lookup_index)
378            }
379            SubstitutionSubtables::Contextual(tables) => {
380                tables.closure_glyphs(ctx, lookup_list, lookup_index)
381            }
382            SubstitutionSubtables::ChainContextual(tables) => {
383                tables.closure_glyphs(ctx, lookup_list, lookup_index)
384            }
385            SubstitutionSubtables::EmptyExtension => Ok(()),
386        }
387    }
388
389    fn may_have_non_1to1(&self) -> Result<bool, ReadError> {
390        match self {
391            SubstitutionSubtables::Single(_) => Ok(false),
392            SubstitutionSubtables::Multiple(_) => Ok(true),
393            SubstitutionSubtables::Alternate(_) => Ok(false),
394            SubstitutionSubtables::Ligature(_) => Ok(true),
395            SubstitutionSubtables::Reverse(_) => Ok(false),
396            SubstitutionSubtables::Contextual(_) => Ok(true),
397            SubstitutionSubtables::ChainContextual(_) => Ok(true),
398            SubstitutionSubtables::EmptyExtension => Ok(false),
399        }
400    }
401}
402
403impl<'a, T: FontRead<'a, Args = ()> + GlyphClosure + 'a, Ext: ExtensionLookup<'a, T> + 'a>
404    GlyphClosure for Subtables<'a, T, Ext>
405{
406    fn closure_glyphs(
407        &self,
408        ctx: &mut ClosureCtx,
409        lookup_list: &SubstitutionLookupList,
410        lookup_index: u16,
411    ) -> Result<(), ReadError> {
412        for t in self.iter().filter_map(|table| match table {
413            Err(ReadError::NullOffset) => None,
414            other => Some(other),
415        }) {
416            t?.closure_glyphs(ctx, lookup_list, lookup_index)?;
417        }
418        Ok(())
419    }
420}
421
422impl GlyphClosure for SingleSubst<'_> {
423    fn closure_glyphs(
424        &self,
425        ctx: &mut ClosureCtx,
426        lookup_list: &SubstitutionLookupList,
427        lookup_index: u16,
428    ) -> Result<(), ReadError> {
429        match self {
430            SingleSubst::Format1(t) => t.closure_glyphs(ctx, lookup_list, lookup_index),
431            SingleSubst::Format2(t) => t.closure_glyphs(ctx, lookup_list, lookup_index),
432            SingleSubst::Format3(t) => t.closure_glyphs(ctx, lookup_list, lookup_index),
433            SingleSubst::Format4(t) => t.closure_glyphs(ctx, lookup_list, lookup_index),
434        }
435    }
436}
437
438// ref: <https://github.com/harfbuzz/harfbuzz/blob/8d517f7e43f648cb804c46c47ae8009330fe4a47/src/OT/Layout/GSUB/SingleSubstFormat1.hh#L48>
439impl GlyphClosure for SingleSubstFormat1<'_> {
440    fn closure_glyphs(
441        &self,
442        ctx: &mut ClosureCtx,
443        _lookup_list: &SubstitutionLookupList,
444        _lookup_index: u16,
445    ) -> Result<(), ReadError> {
446        if self.coverage_offset().is_null() {
447            return Ok(());
448        }
449        let coverage = self.coverage()?;
450        let num_glyphs = coverage.population();
451        let mask = u16::MAX;
452        // ref: <https://github.com/harfbuzz/harfbuzz/blob/fbf5b2aa035d6cd9b796d74252045e2b7156ad02/src/OT/Layout/GSUB/SingleSubstFormat1.hh#L55>
453        if num_glyphs >= mask as usize {
454            return Ok(());
455        }
456
457        let intersection = coverage.intersect_set(ctx.parent_active_glyphs());
458        if intersection.is_empty() {
459            return Ok(());
460        }
461
462        // help fuzzer
463        // ref: <https://github.com/harfbuzz/harfbuzz/blob/fbf5b2aa035d6cd9b796d74252045e2b7156ad02/src/OT/Layout/GSUB/SingleSubstFormat1.hh#L61>
464        let d = self.delta_glyph_id() as i32;
465        let mask = mask as i32;
466        let min_before = intersection.first().unwrap().to_u32() as i32;
467        let max_before = intersection.last().unwrap().to_u32() as i32;
468        let min_after = (min_before + d) & mask;
469        let max_after = (max_before + d) & mask;
470
471        if intersection.len() == (max_before - min_before + 1) as u64
472            && ((min_before <= min_after && min_after <= max_before)
473                || (min_before <= max_after && max_after <= max_before))
474        {
475            return Ok(());
476        }
477
478        for g in intersection.iter() {
479            let new_g = (g.to_u32() as i32 + d) & mask;
480            ctx.add(GlyphId::from(new_g as u32));
481        }
482        Ok(())
483    }
484}
485
486impl GlyphClosure for SingleSubstFormat2<'_> {
487    fn closure_glyphs(
488        &self,
489        ctx: &mut ClosureCtx,
490        _lookup_list: &SubstitutionLookupList,
491        _lookup_index: u16,
492    ) -> Result<(), ReadError> {
493        if self.coverage_offset().is_null() || self.glyph_count() == 0 {
494            return Ok(());
495        }
496        let coverage = self.coverage()?;
497        let glyph_set = if let Some(glyph_set) = ctx.active_glyphs_stack.last() {
498            glyph_set
499        } else {
500            &*ctx.glyphs
501        };
502        let subs_glyphs = self.substitute_glyph_ids();
503
504        if self.glyph_count() as u64 > glyph_set.len() * coverage.cost() as u64 {
505            ctx.output.extend(
506                glyph_set
507                    .iter()
508                    .filter_map(|g| coverage.get(g))
509                    .filter_map(|idx| {
510                        subs_glyphs
511                            .get(idx as usize)
512                            .map(|new_g| GlyphId::from(new_g.get()))
513                    }),
514            );
515        } else {
516            ctx.output.extend(
517                coverage
518                    .iter()
519                    .zip(subs_glyphs)
520                    .filter(|&(g, _)| glyph_set.contains(g))
521                    .map(|(_, &new_g)| GlyphId::from(new_g.get())),
522            );
523        }
524        Ok(())
525    }
526}
527
528impl GlyphClosure for MultipleSubstFormat1<'_> {
529    fn closure_glyphs(
530        &self,
531        ctx: &mut ClosureCtx,
532        _lookup_list: &SubstitutionLookupList,
533        _lookup_index: u16,
534    ) -> Result<(), ReadError> {
535        if self.coverage_offset().is_null() || self.sequence_count() == 0 {
536            return Ok(());
537        }
538        let coverage = self.coverage()?;
539        let glyph_set = if let Some(glyph_set) = ctx.active_glyphs_stack.last() {
540            glyph_set
541        } else {
542            &*ctx.glyphs
543        };
544        let sequences = self.sequences();
545
546        if self.sequence_count() as u64 > glyph_set.len() * coverage.cost() as u64 {
547            ctx.output.extend(
548                glyph_set
549                    .iter()
550                    .filter_map(|g| coverage.get(g))
551                    .filter_map(|idx| sequences.get(idx as usize).ok())
552                    .flat_map(|seq| {
553                        seq.substitute_glyph_ids()
554                            .iter()
555                            .map(|new_g| GlyphId::from(new_g.get()))
556                    }),
557            );
558        } else {
559            ctx.output.extend(
560                coverage
561                    .iter()
562                    .zip(sequences.iter_as_nullable())
563                    .filter_map(|(g, seq)| {
564                        glyph_set
565                            .contains(g)
566                            .then(|| seq.transpose().ok().flatten())
567                            .flatten()
568                    })
569                    .flat_map(|seq| {
570                        seq.substitute_glyph_ids()
571                            .iter()
572                            .map(|new_g| GlyphId::from(new_g.get()))
573                    }),
574            );
575        }
576        Ok(())
577    }
578}
579
580impl GlyphClosure for AlternateSubstFormat1<'_> {
581    fn closure_glyphs(
582        &self,
583        ctx: &mut ClosureCtx,
584        _lookup_list: &SubstitutionLookupList,
585        _lookup_index: u16,
586    ) -> Result<(), ReadError> {
587        if self.coverage_offset().is_null() || self.alternate_set_count() == 0 {
588            return Ok(());
589        }
590        let coverage = self.coverage()?;
591        let glyph_set = if let Some(glyph_set) = ctx.active_glyphs_stack.last() {
592            glyph_set
593        } else {
594            &*ctx.glyphs
595        };
596        let alts = self.alternate_sets();
597        if self.alternate_set_count() as u64 > glyph_set.len() * coverage.cost() as u64 {
598            ctx.output.extend(
599                glyph_set
600                    .iter()
601                    .filter_map(|g| coverage.get(g))
602                    .filter_map(|idx| alts.get(idx as usize).ok())
603                    .flat_map(|alt_set| {
604                        alt_set
605                            .alternate_glyph_ids()
606                            .iter()
607                            .map(|new_g| GlyphId::from(new_g.get()))
608                    }),
609            );
610        } else {
611            ctx.output.extend(
612                coverage
613                    .iter()
614                    .zip(alts.iter_as_nullable())
615                    .filter_map(|(g, alt_set)| {
616                        glyph_set
617                            .contains(g)
618                            .then(|| alt_set.transpose().ok().flatten())
619                            .flatten()
620                    })
621                    .flat_map(|alt_set| {
622                        alt_set
623                            .alternate_glyph_ids()
624                            .iter()
625                            .map(|new_g| GlyphId::from(new_g.get()))
626                    }),
627            );
628        }
629        Ok(())
630    }
631}
632
633impl GlyphClosure for LigatureSubstFormat1<'_> {
634    fn closure_glyphs(
635        &self,
636        ctx: &mut ClosureCtx,
637        _lookup_list: &SubstitutionLookupList,
638        _lookup_index: u16,
639    ) -> Result<(), ReadError> {
640        if self.coverage_offset().is_null() || self.ligature_set_count() == 0 {
641            return Ok(());
642        }
643        let coverage = self.coverage()?;
644        let ligs = self.ligature_sets();
645        let glyph_set = if let Some(glyph_set) = ctx.active_glyphs_stack.last() {
646            glyph_set
647        } else {
648            &*ctx.glyphs
649        };
650
651        if self.ligature_set_count() as u64 > glyph_set.len() {
652            for idx in glyph_set
653                .iter()
654                .filter_map(|g| coverage.get(g))
655                .map(|idx| idx as usize)
656            {
657                let lig_set = match ligs.get(idx) {
658                    Err(ReadError::NullOffset) => continue,
659                    other => other,
660                }?;
661                for lig in lig_set.ligatures().iter_as_nullable() {
662                    let Some(lig) = lig.transpose()? else {
663                        continue;
664                    };
665                    if lig.intersects(ctx.glyphs())? {
666                        ctx.output.insert(GlyphId::from(lig.ligature_glyph()));
667                    }
668                }
669            }
670        } else {
671            for idx in coverage
672                .iter()
673                .enumerate()
674                .filter(|&(_idx, g)| glyph_set.contains(g))
675                .map(|(idx, _)| idx)
676            {
677                let lig_set = match ligs.get(idx) {
678                    Err(ReadError::NullOffset) => continue,
679                    other => other,
680                }?;
681                for lig in lig_set.ligatures().iter_as_nullable() {
682                    let Some(lig) = lig.transpose()? else {
683                        continue;
684                    };
685                    if lig.intersects(ctx.glyphs())? {
686                        ctx.output.insert(GlyphId::from(lig.ligature_glyph()));
687                    }
688                }
689            }
690        }
691        Ok(())
692    }
693}
694
695impl GlyphClosure for ReverseChainSingleSubstFormat1<'_> {
696    fn closure_glyphs(
697        &self,
698        ctx: &mut ClosureCtx,
699        _lookup_list: &SubstitutionLookupList,
700        _lookup_index: u16,
701    ) -> Result<(), ReadError> {
702        if !self.intersects(ctx.glyphs())? {
703            return Ok(());
704        }
705
706        let coverage = self.coverage()?;
707        let sub_glyphs = self.substitute_glyph_ids();
708        let glyph_set = if let Some(glyph_set) = ctx.active_glyphs_stack.last() {
709            glyph_set
710        } else {
711            &*ctx.glyphs
712        };
713
714        if self.glyph_count() as u64 > glyph_set.len() {
715            for i in glyph_set
716                .iter()
717                .filter_map(|g| coverage.get(g))
718                .map(|idx| idx as usize)
719            {
720                let Some(g) = sub_glyphs.get(i) else {
721                    continue;
722                };
723                ctx.output.insert(GlyphId::from(g.get()));
724            }
725        } else {
726            for i in coverage
727                .iter()
728                .enumerate()
729                .filter(|&(_idx, g)| glyph_set.contains(g))
730                .map(|(idx, _)| idx)
731            {
732                let Some(g) = sub_glyphs.get(i) else {
733                    continue;
734                };
735                ctx.output.insert(GlyphId::from(g.get()));
736            }
737        }
738
739        Ok(())
740    }
741}
742
743impl GlyphClosure for SequenceContext<'_> {
744    fn closure_glyphs(
745        &self,
746        ctx: &mut ClosureCtx,
747        lookup_list: &SubstitutionLookupList,
748        lookup_index: u16,
749    ) -> Result<(), ReadError> {
750        match self {
751            Self::Format1(table) => {
752                ContextFormat1::Plain(table.clone()).closure_glyphs(ctx, lookup_list, lookup_index)
753            }
754            Self::Format2(table) => {
755                ContextFormat2::Plain(table.clone()).closure_glyphs(ctx, lookup_list, lookup_index)
756            }
757            Self::Format5(table) => ContextFormat2::PlainWide(table.clone()).closure_glyphs(
758                ctx,
759                lookup_list,
760                lookup_index,
761            ),
762            Self::Format3(table) => {
763                ContextFormat3::Plain(table.clone()).closure_glyphs(ctx, lookup_list, lookup_index)
764            }
765            Self::Format4(table) => ContextFormat1::PlainWide(table.clone()).closure_glyphs(
766                ctx,
767                lookup_list,
768                lookup_index,
769            ),
770            Self::Format6(table) => ContextFormat3::PlainWide(table.clone()).closure_glyphs(
771                ctx,
772                lookup_list,
773                lookup_index,
774            ),
775        }
776    }
777}
778
779impl GlyphClosure for ChainedSequenceContext<'_> {
780    fn closure_glyphs(
781        &self,
782        ctx: &mut ClosureCtx,
783        lookup_list: &SubstitutionLookupList,
784        lookup_index: u16,
785    ) -> Result<(), ReadError> {
786        match self {
787            Self::Format1(table) => {
788                ContextFormat1::Chain(table.clone()).closure_glyphs(ctx, lookup_list, lookup_index)
789            }
790            Self::Format2(table) => {
791                ContextFormat2::Chain(table.clone()).closure_glyphs(ctx, lookup_list, lookup_index)
792            }
793            Self::Format5(table) => ContextFormat2::ChainWide(table.clone()).closure_glyphs(
794                ctx,
795                lookup_list,
796                lookup_index,
797            ),
798            Self::Format3(table) => {
799                ContextFormat3::Chain(table.clone()).closure_glyphs(ctx, lookup_list, lookup_index)
800            }
801            Self::Format4(table) => ContextFormat1::ChainWide(table.clone()).closure_glyphs(
802                ctx,
803                lookup_list,
804                lookup_index,
805            ),
806        }
807    }
808}
809
810//https://github.com/fonttools/fonttools/blob/a6f59a4f8/Lib/fontTools/subset/__init__.py#L1182
811impl GlyphClosure for ContextFormat1<'_> {
812    fn closure_glyphs(
813        &self,
814        ctx: &mut ClosureCtx,
815        lookup_list: &SubstitutionLookupList,
816        _lookup_index: u16,
817    ) -> Result<(), ReadError> {
818        let Some(coverage) = self.coverage().transpose()? else {
819            return Ok(());
820        };
821
822        let lookups = lookup_list.lookups();
823        let mut seen_sequence_indices = IntSet::new();
824        for (gid, rule_set) in coverage
825            .iter()
826            .zip(self.rule_sets())
827            .filter_map(|(g, rule_set)| rule_set.map(|rs| (g, rs)))
828        {
829            if !ctx.parent_active_glyphs().contains(gid) {
830                continue;
831            }
832            if ctx.lookup_limit_exceed() {
833                return Ok(());
834            }
835
836            for rule in rule_set?.rules() {
837                if ctx.lookup_limit_exceed() {
838                    return Ok(());
839                }
840                let Some(rule) = rule.transpose()? else {
841                    continue;
842                };
843                if !rule.intersects(ctx.glyphs())? {
844                    continue;
845                }
846
847                let input_count = rule.input_count();
848                // python calls this 'chaos'. Basically: if there are multiple
849                // lookups applied at a single position they can interact, and
850                // we can no longer trivially determine the state of the context
851                // at that point. In this case we give up, and assume that the
852                // second lookup is reachable by all glyphs.
853                seen_sequence_indices.clear();
854
855                for lookup_record in rule.lookup_records() {
856                    let lookup_index = lookup_record.lookup_list_index();
857                    let lookup = match lookups.get(lookup_index as usize) {
858                        Err(ReadError::NullOffset) | Err(ReadError::InvalidCollectionIndex(_)) => {
859                            continue
860                        }
861                        other => other,
862                    }?;
863
864                    let sequence_idx = lookup_record.sequence_index();
865                    if sequence_idx as usize >= input_count {
866                        continue;
867                    }
868
869                    let mut active_glyphs = IntSet::empty();
870                    if !seen_sequence_indices.insert(sequence_idx) {
871                        // During processing, when we see an empty set we will replace
872                        // it with the full current glyph set
873                        active_glyphs.extend(ctx.glyphs().iter());
874                    } else if sequence_idx == 0 {
875                        active_glyphs.insert(gid);
876                    } else {
877                        let Some(g) = rule.input_glyph(sequence_idx as usize - 1) else {
878                            continue;
879                        };
880                        active_glyphs.insert(g);
881                    };
882
883                    ctx.recurse(
884                        lookup_list,
885                        &lookup,
886                        lookup_index,
887                        active_glyphs,
888                        &mut seen_sequence_indices,
889                        sequence_idx,
890                        input_count as u16,
891                    )?;
892                }
893            }
894        }
895        Ok(())
896    }
897}
898
899fn intersected_class_glyphs(
900    class_def: &ClassDef,
901    glyphs: &IntSet<GlyphId>,
902    class: u32,
903    cache: &mut FastHashMap<u32, IntSet<GlyphId>>,
904) -> IntSet<GlyphId> {
905    if let Some(cached_set) = cache.get(&class) {
906        return cached_set.clone();
907    }
908
909    let out = class_def.intersected_class_glyphs(glyphs, class);
910    cache.insert(class, out.clone());
911    out
912}
913
914//https://github.com/fonttools/fonttools/blob/a6f59a4f87a0111/Lib/fontTools/subset/__init__.py#L1215
915impl GlyphClosure for ContextFormat2<'_> {
916    fn closure_glyphs(
917        &self,
918        ctx: &mut ClosureCtx,
919        lookup_list: &SubstitutionLookupList,
920        _lookup_index: u16,
921    ) -> Result<(), ReadError> {
922        let Some(coverage) = self.coverage().transpose()? else {
923            return Ok(());
924        };
925
926        let Some(input_class_def) = self.input_class_def().transpose()? else {
927            return Ok(());
928        };
929
930        if !coverage.intersects(ctx.parent_active_glyphs()) {
931            return Ok(());
932        }
933        let cov_active_glyphs = coverage.intersect_set(ctx.parent_active_glyphs());
934        let backtrack_class_def = self.backtrack_class_def().transpose()?;
935        let lookahead_class_def = self.lookahead_class_def().transpose()?;
936
937        let primary_classes = input_class_def.intersect_classes(&cov_active_glyphs);
938        let lookups = lookup_list.lookups();
939        let mut seen_sequence_indices = IntSet::new();
940
941        let mut intersected_class_cache = FastHashMap::default();
942        let mut seq_cache = SeqCache::default();
943        for (i, rule_set) in self
944            .rule_sets()
945            .enumerate()
946            .filter_map(|(class, rs)| rs.map(|rs| (class as u32, rs)))
947            .filter(|&(class, _)| primary_classes.contains(class))
948        {
949            if ctx.lookup_limit_exceed() {
950                return Ok(());
951            }
952
953            for rule in rule_set?.rules() {
954                if ctx.lookup_limit_exceed() {
955                    return Ok(());
956                }
957                let Some(rule) = rule.transpose()? else {
958                    continue;
959                };
960                if !rule.intersects(
961                    ctx.glyphs(),
962                    &input_class_def,
963                    backtrack_class_def.as_ref(),
964                    lookahead_class_def.as_ref(),
965                    &mut seq_cache,
966                ) {
967                    continue;
968                }
969
970                let input_seq = rule.input_sequence();
971                let input_count = input_seq.len() + 1;
972
973                seen_sequence_indices.clear();
974                for lookup_record in rule.lookup_records() {
975                    let lookup_index = lookup_record.lookup_list_index();
976                    let lookup = match lookups.get(lookup_index as usize) {
977                        Err(ReadError::NullOffset) | Err(ReadError::InvalidCollectionIndex(_)) => {
978                            continue
979                        }
980                        other => other,
981                    }?;
982                    let sequence_idx = lookup_record.sequence_index();
983                    if sequence_idx as usize >= input_count {
984                        continue;
985                    }
986
987                    let active_glyphs = if !seen_sequence_indices.insert(sequence_idx) {
988                        ctx.glyphs().clone()
989                    } else if sequence_idx == 0 {
990                        intersected_class_glyphs(
991                            &input_class_def,
992                            ctx.parent_active_glyphs(),
993                            i,
994                            &mut intersected_class_cache,
995                        )
996                    } else {
997                        let c = input_seq[sequence_idx as usize - 1].get();
998                        intersected_class_glyphs(
999                            &input_class_def,
1000                            ctx.glyphs(),
1001                            u32::from(c),
1002                            &mut intersected_class_cache,
1003                        )
1004                    };
1005
1006                    ctx.recurse(
1007                        lookup_list,
1008                        &lookup,
1009                        lookup_index,
1010                        active_glyphs,
1011                        &mut seen_sequence_indices,
1012                        sequence_idx,
1013                        input_count as u16,
1014                    )?;
1015                }
1016            }
1017        }
1018        Ok(())
1019    }
1020}
1021
1022impl GlyphClosure for ContextFormat3<'_> {
1023    fn closure_glyphs(
1024        &self,
1025        ctx: &mut ClosureCtx,
1026        lookup_list: &SubstitutionLookupList,
1027        _lookup_index: u16,
1028    ) -> Result<(), ReadError> {
1029        if !self.intersects(ctx.glyphs())? {
1030            return Ok(());
1031        }
1032
1033        let mut seen_sequence_indices = IntSet::new();
1034        let input_count = self.input_count();
1035        let lookups = lookup_list.lookups();
1036        for record in self.lookup_records() {
1037            let lookup_index = record.lookup_list_index();
1038            let lookup = match lookups.get(lookup_index as usize) {
1039                Err(ReadError::NullOffset) | Err(ReadError::InvalidCollectionIndex(_)) => continue,
1040                other => other,
1041            }?;
1042
1043            let seq_idx = record.sequence_index();
1044            if seq_idx as usize >= input_count {
1045                continue;
1046            }
1047
1048            let active_glyphs = if !seen_sequence_indices.insert(seq_idx) {
1049                ctx.glyphs().clone()
1050            } else if seq_idx == 0 {
1051                let cov = self.coverage(0)?;
1052                cov.intersect_set(ctx.parent_active_glyphs())
1053            } else {
1054                let cov = self.coverage(seq_idx as usize)?;
1055                cov.intersect_set(ctx.glyphs())
1056            };
1057
1058            ctx.recurse(
1059                lookup_list,
1060                &lookup,
1061                lookup_index,
1062                active_glyphs,
1063                &mut seen_sequence_indices,
1064                seq_idx,
1065                // Coverage arrays already include the first input glyph.
1066                input_count as u16,
1067            )?;
1068        }
1069        Ok(())
1070    }
1071}
1072
1073impl SubstitutionLookupList<'_> {
1074    pub fn closure_lookups(
1075        &self,
1076        glyph_set: &IntSet<GlyphId>,
1077        lookup_indices: &mut IntSet<u16>,
1078    ) -> Result<(), ReadError> {
1079        lookup_indices.remove_range(self.lookup_count()..=u16::MAX);
1080        if lookup_indices.is_empty() {
1081            return Ok(());
1082        }
1083        let lookup_list = LayoutLookupList::Gsub(self);
1084        let mut c = LookupClosureCtx::new(glyph_set, &lookup_list);
1085
1086        let lookups = self.lookups();
1087        for idx in lookup_indices.iter() {
1088            let lookup = match lookups.get(idx as usize) {
1089                Err(ReadError::NullOffset) => {
1090                    c.set_lookup_inactive(idx);
1091                    continue;
1092                }
1093                other => other,
1094            }?;
1095            lookup.closure_lookups(&mut c, idx)?;
1096        }
1097
1098        lookup_indices.union(c.visited_lookups());
1099        lookup_indices.subtract(c.inactive_lookups());
1100        Ok(())
1101    }
1102}
1103
1104impl LookupClosure for SubstitutionLookup<'_> {
1105    fn closure_lookups(
1106        &self,
1107        c: &mut LookupClosureCtx,
1108        lookup_index: u16,
1109    ) -> Result<(), ReadError> {
1110        if !c.should_visit_lookup(lookup_index) {
1111            return Ok(());
1112        }
1113
1114        if !self.intersects(c.glyphs())? {
1115            c.set_lookup_inactive(lookup_index);
1116            return Ok(());
1117        }
1118
1119        self.subtables()?.closure_lookups(c, lookup_index)
1120    }
1121}
1122
1123impl Intersect for SubstitutionLookup<'_> {
1124    fn intersects(&self, glyph_set: &IntSet<GlyphId>) -> Result<bool, ReadError> {
1125        match self {
1126            SubstitutionLookup::Single(inner) => inner.subtables().intersects(glyph_set),
1127            SubstitutionLookup::Multiple(inner) => inner.subtables().intersects(glyph_set),
1128            SubstitutionLookup::Alternate(inner) => inner.subtables().intersects(glyph_set),
1129            SubstitutionLookup::Ligature(inner) => inner.subtables().intersects(glyph_set),
1130            SubstitutionLookup::Contextual(inner) => inner.subtables().intersects(glyph_set),
1131            SubstitutionLookup::ChainContextual(inner) => inner.subtables().intersects(glyph_set),
1132            SubstitutionLookup::Extension(inner) => inner.subtables().intersects(glyph_set),
1133            SubstitutionLookup::Reverse(inner) => inner.subtables().intersects(glyph_set),
1134        }
1135    }
1136}
1137
1138impl Intersect for ExtensionSubtable<'_> {
1139    fn intersects(&self, glyph_set: &IntSet<GlyphId>) -> Result<bool, ReadError> {
1140        match self {
1141            ExtensionSubtable::Single(inner) => inner.intersects(glyph_set),
1142            ExtensionSubtable::Multiple(inner) => inner.intersects(glyph_set),
1143            ExtensionSubtable::Alternate(inner) => inner.intersects(glyph_set),
1144            ExtensionSubtable::Ligature(inner) => inner.intersects(glyph_set),
1145            ExtensionSubtable::Contextual(inner) => inner.intersects(glyph_set),
1146            ExtensionSubtable::ChainContextual(inner) => inner.intersects(glyph_set),
1147            ExtensionSubtable::Reverse(inner) => inner.intersects(glyph_set),
1148        }
1149    }
1150}
1151
1152impl<'a, T> Intersect for ExtensionSubstFormat1<'a, T>
1153where
1154    T: Intersect + FontRead<'a, Args = ()>,
1155{
1156    fn intersects(&self, glyph_set: &IntSet<GlyphId>) -> Result<bool, ReadError> {
1157        if self.extension_offset().is_null() {
1158            return Ok(false);
1159        }
1160        self.extension()?.intersects(glyph_set)
1161    }
1162}
1163
1164impl LookupClosure for SubstitutionSubtables<'_> {
1165    fn closure_lookups(&self, c: &mut LookupClosureCtx, arg: u16) -> Result<(), ReadError> {
1166        match self {
1167            SubstitutionSubtables::ChainContextual(subtables) => subtables.closure_lookups(c, arg),
1168            SubstitutionSubtables::Contextual(subtables) => subtables.closure_lookups(c, arg),
1169            _ => Ok(()),
1170        }
1171    }
1172}
1173
1174impl Intersect for SingleSubst<'_> {
1175    fn intersects(&self, glyph_set: &IntSet<GlyphId>) -> Result<bool, ReadError> {
1176        match self {
1177            Self::Format1(item) => item.intersects(glyph_set),
1178            Self::Format2(item) => item.intersects(glyph_set),
1179            Self::Format3(item) => item.intersects(glyph_set),
1180            Self::Format4(item) => item.intersects(glyph_set),
1181        }
1182    }
1183}
1184
1185impl Intersect for SingleSubstFormat1<'_> {
1186    fn intersects(&self, glyph_set: &IntSet<GlyphId>) -> Result<bool, ReadError> {
1187        if self.coverage_offset().is_null() {
1188            return Ok(false);
1189        }
1190        Ok(self.coverage()?.intersects(glyph_set))
1191    }
1192}
1193
1194impl Intersect for SingleSubstFormat2<'_> {
1195    fn intersects(&self, glyph_set: &IntSet<GlyphId>) -> Result<bool, ReadError> {
1196        if self.coverage_offset().is_null() {
1197            return Ok(false);
1198        }
1199        Ok(self.coverage()?.intersects(glyph_set))
1200    }
1201}
1202
1203impl Intersect for MultipleSubstFormat1<'_> {
1204    fn intersects(&self, glyph_set: &IntSet<GlyphId>) -> Result<bool, ReadError> {
1205        if self.coverage_offset().is_null() {
1206            return Ok(false);
1207        }
1208        Ok(self.coverage()?.intersects(glyph_set))
1209    }
1210}
1211
1212impl Intersect for AlternateSubstFormat1<'_> {
1213    fn intersects(&self, glyph_set: &IntSet<GlyphId>) -> Result<bool, ReadError> {
1214        if self.coverage_offset().is_null() {
1215            return Ok(false);
1216        }
1217        Ok(self.coverage()?.intersects(glyph_set))
1218    }
1219}
1220
1221impl Intersect for LigatureSubstFormat1<'_> {
1222    fn intersects(&self, glyph_set: &IntSet<GlyphId>) -> Result<bool, ReadError> {
1223        if self.coverage_offset().is_null() {
1224            return Ok(false);
1225        }
1226        let coverage = self.coverage()?;
1227        let lig_sets = self.ligature_sets();
1228        for lig_set in coverage
1229            .iter()
1230            .zip(lig_sets.iter_as_nullable())
1231            .filter_map(|(g, lig_set)| glyph_set.contains(g).then_some(lig_set))
1232        {
1233            let Some(lig_set) = lig_set.transpose()? else {
1234                continue;
1235            };
1236            if lig_set.intersects(glyph_set)? {
1237                return Ok(true);
1238            }
1239        }
1240        Ok(false)
1241    }
1242}
1243
1244impl Intersect for LigatureSet<'_> {
1245    fn intersects(&self, glyph_set: &IntSet<GlyphId>) -> Result<bool, ReadError> {
1246        let ligs = self.ligatures();
1247        for lig in ligs.iter_as_nullable().flatten() {
1248            if lig?.intersects(glyph_set)? {
1249                return Ok(true);
1250            }
1251        }
1252        Ok(false)
1253    }
1254}
1255
1256impl Intersect for Ligature<'_> {
1257    fn intersects(&self, glyph_set: &IntSet<GlyphId>) -> Result<bool, ReadError> {
1258        let ret = self
1259            .component_glyph_ids()
1260            .iter()
1261            .all(|g| glyph_set.contains(GlyphId::from(g.get())));
1262        Ok(ret)
1263    }
1264}
1265
1266impl Intersect for ReverseChainSingleSubstFormat1<'_> {
1267    fn intersects(&self, glyph_set: &IntSet<GlyphId>) -> Result<bool, ReadError> {
1268        if self.coverage_offset().is_null() {
1269            return Ok(false);
1270        }
1271        if !self.coverage()?.intersects(glyph_set) {
1272            return Ok(false);
1273        }
1274
1275        for coverage in self.backtrack_coverages().iter_as_nullable() {
1276            let Some(coverage) = coverage.transpose()? else {
1277                return Ok(false);
1278            };
1279            if !coverage.intersects(glyph_set) {
1280                return Ok(false);
1281            }
1282        }
1283
1284        for coverage in self.lookahead_coverages().iter_as_nullable() {
1285            let Some(coverage) = coverage.transpose()? else {
1286                return Ok(false);
1287            };
1288            if !coverage.intersects(glyph_set) {
1289                return Ok(false);
1290            }
1291        }
1292        Ok(true)
1293    }
1294}
1295
1296impl GlyphClosure for super::MultipleSubst<'_> {
1297    fn closure_glyphs(
1298        &self,
1299        ctx: &mut ClosureCtx,
1300        lookup_list: &SubstitutionLookupList,
1301        lookup_index: u16,
1302    ) -> Result<(), ReadError> {
1303        match self {
1304            Self::Format1(table) => table.closure_glyphs(ctx, lookup_list, lookup_index),
1305            Self::Format2(table) => table.closure_glyphs(ctx, lookup_list, lookup_index),
1306        }
1307    }
1308}
1309impl Intersect for super::MultipleSubst<'_> {
1310    fn intersects(&self, glyphs: &IntSet<GlyphId>) -> Result<bool, ReadError> {
1311        match self {
1312            Self::Format1(table) => table.intersects(glyphs),
1313            Self::Format2(table) => table.intersects(glyphs),
1314        }
1315    }
1316}
1317
1318impl GlyphClosure for super::AlternateSubst<'_> {
1319    fn closure_glyphs(
1320        &self,
1321        ctx: &mut ClosureCtx,
1322        lookup_list: &SubstitutionLookupList,
1323        lookup_index: u16,
1324    ) -> Result<(), ReadError> {
1325        match self {
1326            Self::Format1(table) => table.closure_glyphs(ctx, lookup_list, lookup_index),
1327            Self::Format2(table) => table.closure_glyphs(ctx, lookup_list, lookup_index),
1328        }
1329    }
1330}
1331impl Intersect for super::AlternateSubst<'_> {
1332    fn intersects(&self, glyphs: &IntSet<GlyphId>) -> Result<bool, ReadError> {
1333        match self {
1334            Self::Format1(table) => table.intersects(glyphs),
1335            Self::Format2(table) => table.intersects(glyphs),
1336        }
1337    }
1338}
1339
1340impl GlyphClosure for super::LigatureSubst<'_> {
1341    fn closure_glyphs(
1342        &self,
1343        ctx: &mut ClosureCtx,
1344        lookup_list: &SubstitutionLookupList,
1345        lookup_index: u16,
1346    ) -> Result<(), ReadError> {
1347        match self {
1348            Self::Format1(table) => table.closure_glyphs(ctx, lookup_list, lookup_index),
1349            Self::Format2(table) => table.closure_glyphs(ctx, lookup_list, lookup_index),
1350        }
1351    }
1352}
1353impl Intersect for super::LigatureSubst<'_> {
1354    fn intersects(&self, glyphs: &IntSet<GlyphId>) -> Result<bool, ReadError> {
1355        match self {
1356            Self::Format1(table) => table.intersects(glyphs),
1357            Self::Format2(table) => table.intersects(glyphs),
1358        }
1359    }
1360}
1361
1362impl GlyphClosure for super::ReverseChainSingleSubst<'_> {
1363    fn closure_glyphs(
1364        &self,
1365        ctx: &mut ClosureCtx,
1366        lookup_list: &SubstitutionLookupList,
1367        lookup_index: u16,
1368    ) -> Result<(), ReadError> {
1369        match self {
1370            Self::Format1(table) => table.closure_glyphs(ctx, lookup_list, lookup_index),
1371            Self::Format2(table) => table.closure_glyphs(ctx, lookup_list, lookup_index),
1372        }
1373    }
1374}
1375impl Intersect for super::ReverseChainSingleSubst<'_> {
1376    fn intersects(&self, glyphs: &IntSet<GlyphId>) -> Result<bool, ReadError> {
1377        match self {
1378            Self::Format1(table) => table.intersects(glyphs),
1379            Self::Format2(table) => table.intersects(glyphs),
1380        }
1381    }
1382}
1383
1384#[cfg(test)]
1385mod tests {
1386    use std::collections::{HashMap, HashSet};
1387
1388    use crate::{FontRef, TableProvider};
1389
1390    use super::*;
1391    use font_test_data::bebuffer::BeBuffer;
1392    use font_test_data::closure as test_data;
1393
1394    struct GlyphMap {
1395        to_gid: HashMap<&'static str, GlyphId>,
1396        from_gid: HashMap<GlyphId, &'static str>,
1397    }
1398
1399    impl GlyphMap {
1400        fn new(raw_order: &'static str) -> GlyphMap {
1401            let to_gid: HashMap<_, _> = raw_order
1402                .split('\n')
1403                .map(|line| line.trim())
1404                .filter(|line| !(line.starts_with('#') || line.is_empty()))
1405                .enumerate()
1406                .map(|(gid, name)| (name, GlyphId::new(gid.try_into().unwrap())))
1407                .collect();
1408            let from_gid = to_gid.iter().map(|(name, gid)| (*gid, *name)).collect();
1409            GlyphMap { from_gid, to_gid }
1410        }
1411
1412        fn get_gid(&self, name: &str) -> Option<GlyphId> {
1413            self.to_gid.get(name).copied()
1414        }
1415
1416        fn get_name(&self, gid: GlyphId) -> Option<&str> {
1417            self.from_gid.get(&gid).copied()
1418        }
1419    }
1420
1421    fn get_gsub(test_data: &'static [u8]) -> Gsub<'static> {
1422        let font = FontRef::new(test_data).unwrap();
1423        font.gsub().unwrap()
1424    }
1425
1426    fn compute_closure(gsub: &Gsub, glyph_map: &GlyphMap, input: &[&str]) -> IntSet<GlyphId> {
1427        let lookup_indices = gsub.collect_lookups(&IntSet::all()).unwrap();
1428        let mut input_glyphs = input
1429            .iter()
1430            .map(|name| glyph_map.get_gid(name).unwrap())
1431            .collect();
1432        gsub.closure_glyphs(&lookup_indices, &mut input_glyphs)
1433            .unwrap();
1434        input_glyphs
1435    }
1436
1437    /// assert a set of glyph ids matches a slice of names
1438    macro_rules! assert_closure_result {
1439        ($glyph_map:expr, $result:expr, $expected:expr) => {
1440            let result = $result
1441                .iter()
1442                .map(|gid| $glyph_map.get_name(gid).unwrap())
1443                .collect::<HashSet<_>>();
1444            let expected = $expected.iter().copied().collect::<HashSet<_>>();
1445            if expected != result {
1446                let in_output = result.difference(&expected).collect::<Vec<_>>();
1447                let in_expected = expected.difference(&result).collect::<Vec<_>>();
1448                let mut msg = format!("Closure output does not match\n");
1449                if !in_expected.is_empty() {
1450                    msg.push_str(format!("missing {in_expected:?}\n").as_str());
1451                }
1452                if !in_output.is_empty() {
1453                    msg.push_str(format!("unexpected {in_output:?}").as_str());
1454                }
1455                panic!("{msg}")
1456            }
1457        };
1458    }
1459
1460    #[test]
1461    fn smoke_test() {
1462        // tests various lookup types.
1463        // test input is font-test-data/test_data/fea/simple_closure.fea
1464        let gsub = get_gsub(test_data::SIMPLE);
1465        let glyph_map = GlyphMap::new(test_data::SIMPLE_GLYPHS);
1466        let result = compute_closure(&gsub, &glyph_map, &["a"]);
1467
1468        assert_closure_result!(
1469            glyph_map,
1470            result,
1471            &["a", "A", "b", "c", "d", "a_a", "a.1", "a.2", "a.3"]
1472        );
1473    }
1474
1475    #[test]
1476    fn recursive() {
1477        // a scenario in which one substitution adds glyphs that trigger additional
1478        // substitutions.
1479        //
1480        // test input is font-test-data/test_data/fea/recursive_closure.fea
1481        let gsub = get_gsub(test_data::RECURSIVE);
1482        let glyph_map = GlyphMap::new(test_data::RECURSIVE_GLYPHS);
1483        let result = compute_closure(&gsub, &glyph_map, &["a"]);
1484        assert_closure_result!(glyph_map, result, &["a", "b", "c", "d"]);
1485    }
1486
1487    #[test]
1488    fn closure_drops_glyphs_outside_the_font() {
1489        // Lookups map a -> b, b -> c and c -> d. With only 'a' and 'b' in the
1490        // font, 'c' must be dropped when the closure is flushed, so it can't
1491        // make c -> d reachable either.
1492        let gsub = get_gsub(test_data::RECURSIVE);
1493        let glyph_map = GlyphMap::new(test_data::RECURSIVE_GLYPHS);
1494        let lookups = gsub.collect_lookups(&IntSet::all()).unwrap();
1495        let mut glyphs: IntSet<GlyphId> = [glyph_map.get_gid("a").unwrap()].into_iter().collect();
1496        let num_glyphs = glyph_map.get_gid("c").unwrap().to_u32();
1497        gsub.closure_glyphs_with_num_glyphs(&lookups, &mut glyphs, num_glyphs)
1498            .unwrap();
1499        assert_closure_result!(glyph_map, glyphs, &["a", "b"]);
1500    }
1501
1502    #[test]
1503    fn contextual_lookups_nop() {
1504        let gsub = get_gsub(test_data::CONTEXTUAL);
1505        let glyph_map = GlyphMap::new(test_data::CONTEXTUAL_GLYPHS);
1506
1507        // these match the lookups but not the context
1508        let nop = compute_closure(&gsub, &glyph_map, &["three", "four", "e", "f"]);
1509        assert_closure_result!(glyph_map, nop, &["three", "four", "e", "f"]);
1510    }
1511
1512    #[test]
1513    fn contextual_lookups_chained_f1() {
1514        let gsub = get_gsub(test_data::CONTEXTUAL);
1515        let glyph_map = GlyphMap::new(test_data::CONTEXTUAL_GLYPHS);
1516        let gsub6f1 = compute_closure(
1517            &gsub,
1518            &glyph_map,
1519            &["one", "two", "three", "four", "five", "six", "seven"],
1520        );
1521        assert_closure_result!(
1522            glyph_map,
1523            gsub6f1,
1524            &["one", "two", "three", "four", "five", "six", "seven", "X", "Y"]
1525        );
1526    }
1527
1528    #[test]
1529    fn contextual_lookups_chained_f3() {
1530        let gsub = get_gsub(test_data::CONTEXTUAL);
1531        let glyph_map = GlyphMap::new(test_data::CONTEXTUAL_GLYPHS);
1532        let gsub6f3 = compute_closure(&gsub, &glyph_map, &["space", "e"]);
1533        assert_closure_result!(glyph_map, gsub6f3, &["space", "e", "e.2"]);
1534
1535        let gsub5f3 = compute_closure(&gsub, &glyph_map, &["f", "g"]);
1536        assert_closure_result!(glyph_map, gsub5f3, &["f", "g", "f.2"]);
1537    }
1538
1539    #[test]
1540    fn contextual_plain_f1() {
1541        let gsub = get_gsub(test_data::CONTEXTUAL);
1542        let glyph_map = GlyphMap::new(test_data::CONTEXTUAL_GLYPHS);
1543        let gsub5f1 = compute_closure(&gsub, &glyph_map, &["a", "b"]);
1544        assert_closure_result!(glyph_map, gsub5f1, &["a", "b", "a_b"]);
1545    }
1546
1547    #[test]
1548    fn contextual_plain_f3() {
1549        let gsub = get_gsub(test_data::CONTEXTUAL);
1550        let glyph_map = GlyphMap::new(test_data::CONTEXTUAL_GLYPHS);
1551        let gsub5f3 = compute_closure(&gsub, &glyph_map, &["f", "g"]);
1552        assert_closure_result!(glyph_map, gsub5f3, &["f", "g", "f.2"]);
1553    }
1554
1555    #[test]
1556    fn recursive_context() {
1557        let gsub = get_gsub(test_data::RECURSIVE_CONTEXTUAL);
1558        let glyph_map = GlyphMap::new(test_data::RECURSIVE_CONTEXTUAL_GLYPHS);
1559
1560        let nop = compute_closure(&gsub, &glyph_map, &["b", "B"]);
1561        assert_closure_result!(glyph_map, nop, &["b", "B"]);
1562
1563        let full = compute_closure(&gsub, &glyph_map, &["a", "b", "c"]);
1564        assert_closure_result!(glyph_map, full, &["a", "b", "c", "B", "B.2", "B.3"]);
1565
1566        let intermediate = compute_closure(&gsub, &glyph_map, &["a", "B.2"]);
1567        assert_closure_result!(glyph_map, intermediate, &["a", "B.2", "B.3"]);
1568    }
1569
1570    #[test]
1571    fn feature_variations() {
1572        let gsub = get_gsub(test_data::VARIATIONS_CLOSURE);
1573        let glyph_map = GlyphMap::new(test_data::VARIATIONS_GLYPHS);
1574
1575        let input = compute_closure(&gsub, &glyph_map, &["a"]);
1576        assert_closure_result!(glyph_map, input, &["a", "b", "c"]);
1577    }
1578
1579    #[test]
1580    fn chain_context_format3() {
1581        let gsub = get_gsub(test_data::CHAIN_CONTEXT_FORMAT3_BITS);
1582        let glyph_map = GlyphMap::new(test_data::CHAIN_CONTEXT_FORMAT3_BITS_GLYPHS);
1583
1584        let nop = compute_closure(&gsub, &glyph_map, &["c", "z"]);
1585        assert_closure_result!(glyph_map, nop, &["c", "z"]);
1586
1587        let full = compute_closure(&gsub, &glyph_map, &["a", "b", "c", "z"]);
1588        assert_closure_result!(glyph_map, full, &["a", "b", "c", "z", "A", "B"]);
1589    }
1590
1591    #[test]
1592    fn closure_ignore_unreachable_glyphs() {
1593        let font = FontRef::new(font_test_data::closure::CONTEXT_ONLY_REACHABLE).unwrap();
1594        let gsub = font.gsub().unwrap();
1595        let glyph_map = GlyphMap::new(test_data::CONTEXT_ONLY_REACHABLE_GLYPHS);
1596        let result = compute_closure(&gsub, &glyph_map, &["a", "b", "c", "d", "e", "f", "period"]);
1597        assert_closure_result!(
1598            glyph_map,
1599            result,
1600            &["a", "b", "c", "d", "e", "f", "period", "A", "B", "C"]
1601        );
1602    }
1603
1604    #[test]
1605    fn cyclical_context() {
1606        let gsub = get_gsub(test_data::CYCLIC_CONTEXTUAL);
1607        let glyph_map = GlyphMap::new(test_data::RECURSIVE_CONTEXTUAL_GLYPHS);
1608        // we mostly care that this terminates
1609        let nop = compute_closure(&gsub, &glyph_map, &["a", "b", "c"]);
1610        assert_closure_result!(glyph_map, nop, &["a", "b", "c"]);
1611    }
1612
1613    #[test]
1614    fn collect_all_features() {
1615        let font = FontRef::new(font_test_data::closure::CONTEXTUAL).unwrap();
1616        let gsub = font.gsub().unwrap();
1617        let ret = gsub
1618            .collect_features(&IntSet::all(), &IntSet::all(), &IntSet::all())
1619            .unwrap();
1620        assert_eq!(ret.len(), 2);
1621        assert!(ret.contains(0));
1622        assert!(ret.contains(1));
1623    }
1624
1625    #[test]
1626    fn collect_all_features_with_feature_filter() {
1627        let font = FontRef::new(font_test_data::closure::CONTEXTUAL).unwrap();
1628        let gsub = font.gsub().unwrap();
1629
1630        let mut feature_tags = IntSet::empty();
1631        feature_tags.insert(Tag::new(b"SUB5"));
1632
1633        let ret = gsub
1634            .collect_features(&IntSet::all(), &IntSet::all(), &feature_tags)
1635            .unwrap();
1636        assert_eq!(ret.len(), 1);
1637        assert!(ret.contains(0));
1638    }
1639
1640    #[test]
1641    fn collect_all_features_with_script_filter() {
1642        let font = FontRef::new(font_test_data::closure::CONTEXTUAL).unwrap();
1643        let gsub = font.gsub().unwrap();
1644
1645        let mut script_tags = IntSet::empty();
1646        script_tags.insert(Tag::new(b"LATN"));
1647
1648        let ret = gsub
1649            .collect_features(&script_tags, &IntSet::all(), &IntSet::all())
1650            .unwrap();
1651        assert!(ret.is_empty());
1652    }
1653
1654    /// GSUB with features 'aaaa', 'bbbb', 'cccc' and one 'latn' script with
1655    /// two LangSys: the first has `count` feature indices all pointing to
1656    /// feature 0, the second points to feature 1.
1657    fn gsub_with_many_feature_indices(count: u16) -> BeBuffer {
1658        let langsys1_len = 6 + 2 * count;
1659        let script_len = 4 + 2 * 6 + langsys1_len + 8;
1660        let script_list_len = 2 + 6 + script_len;
1661        let feature_list_off = 10 + script_list_len;
1662        let lookup_list_off = feature_list_off + 2 + 3 * 6 + 4;
1663
1664        BeBuffer::new()
1665            // header: version 1.0, scriptList, featureList, lookupList offsets
1666            .extend([1u16, 0, 10, feature_list_off, lookup_list_off])
1667            // ScriptList: 1 record
1668            .push(1u16)
1669            .push(Tag::new(b"latn"))
1670            .push(8u16)
1671            // Script: no default LangSys, 2 LangSys records
1672            .extend([0u16, 2])
1673            .push(Tag::new(b"AAAA"))
1674            .push(16u16)
1675            .push(Tag::new(b"BBBB"))
1676            .push(16u16 + langsys1_len)
1677            // LangSys 1: `count` feature indices, all 0
1678            .extend([0u16, 0xFFFF, count])
1679            .extend(std::iter::repeat_n(0u16, count as usize))
1680            // LangSys 2: feature index 1
1681            .extend([0u16, 0xFFFF, 1, 1])
1682            // FeatureList: 3 records sharing one empty Feature table
1683            .push(3u16)
1684            .push(Tag::new(b"aaaa"))
1685            .push(20u16)
1686            .push(Tag::new(b"bbbb"))
1687            .push(20u16)
1688            .push(Tag::new(b"cccc"))
1689            .push(20u16)
1690            .extend([0u16, 0])
1691            // LookupList: no lookups
1692            .push(0u16)
1693    }
1694
1695    /// LangSys past the feature index limit (8000, same as harfbuzz's
1696    /// HB_MAX_FEATURE_INDICES) are skipped.
1697    #[test]
1698    fn collect_all_features_feature_index_limit() {
1699        use crate::{FontData, FontRead};
1700
1701        let data = gsub_with_many_feature_indices(1600);
1702        let gsub = Gsub::read(FontData::new(&data)).unwrap();
1703        let ret = gsub
1704            .collect_features(&IntSet::all(), &IntSet::all(), &IntSet::all())
1705            .unwrap();
1706        assert_eq!(ret.iter().collect::<Vec<_>>(), [0, 1]);
1707
1708        let data = gsub_with_many_feature_indices(8001);
1709        let gsub = Gsub::read(FontData::new(&data)).unwrap();
1710        let ret = gsub
1711            .collect_features(&IntSet::all(), &IntSet::all(), &IntSet::all())
1712            .unwrap();
1713        assert!(ret.is_empty());
1714    }
1715}