read_fonts/tables/gsub/
closure.rs

Help
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.
5
6use font_types::{GlyphId, GlyphId16};
7
8use crate::{
9    collections::IntSet,
10    tables::layout::{ExtensionLookup, Subtables},
11    FontRead, ReadError, Tag,
12};
13
14use super::{
15    AlternateSubstFormat1, ChainedSequenceContext, ClassDef, CoverageTable, Gsub, Ligature,
16    LigatureSet, LigatureSubstFormat1, MultipleSubstFormat1, ReverseChainSingleSubstFormat1,
17    SequenceContext, SingleSubst, SingleSubstFormat1, SingleSubstFormat2, SubstitutionLookup,
18    SubstitutionLookupList, SubstitutionSubtables,
19};
20
21#[cfg(feature = "std")]
22use crate::tables::layout::{
23    ContextFormat1, ContextFormat2, ContextFormat3, LookupClosure, LookupClosureCtx,
24};
25
26// we put ClosureCtx in its own module to enforce visibility rules;
27// specifically we don't want cur_glyphs to be reachable directly
28mod ctx {
29    use std::collections::HashMap;
30
31    use types::GlyphId16;
32
33    use crate::{collections::IntSet, tables::gsub::SubstitutionLookup};
34
35    use super::GlyphClosure as _;
36
37    pub(super) struct ClosureCtx<'a> {
38        /// the current closure glyphs. This is updated as we go.
39        glyphs: &'a mut IntSet<GlyphId16>,
40        // in certain situations (like when recursing into contextual lookups) we
41        // consider a smaller subset of glyphs to be 'active'.
42        cur_glyphs: Option<IntSet<GlyphId16>>,
43        finished_lookups: HashMap<u16, (u64, Option<IntSet<GlyphId16>>)>,
44        // when we encounter contextual lookups we want to visit the lookups
45        // they reference, but only with the glyphs that would trigger those
46        // subtable lookups.
47        //
48        // here we store tuples of (LookupId, relevant glyphs); these todos can
49        // be done at the end of each pass.
50        contextual_lookup_todos: Vec<super::ContextualLookupRef>,
51    }
52
53    impl<'a> ClosureCtx<'a> {
54        pub(super) fn new(glyphs: &'a mut IntSet<GlyphId16>) -> Self {
55            Self {
56                glyphs,
57                cur_glyphs: Default::default(),
58                contextual_lookup_todos: Default::default(),
59                finished_lookups: Default::default(),
60            }
61        }
62
63        pub(super) fn current_glyphs(&self) -> &IntSet<GlyphId16> {
64            self.cur_glyphs.as_ref().unwrap_or(self.glyphs)
65        }
66
67        pub(super) fn glyphs(&self) -> &IntSet<GlyphId16> {
68            self.glyphs
69        }
70
71        pub(super) fn add_glyph(&mut self, gid: GlyphId16) {
72            self.glyphs.insert(gid);
73        }
74
75        pub(super) fn extend_glyphs(&mut self, iter: impl IntoIterator<Item = GlyphId16>) {
76            self.glyphs.extend(iter)
77        }
78
79        pub(super) fn add_todo(
80            &mut self,
81            lookup_id: u16,
82            active_glyphs: Option<IntSet<GlyphId16>>,
83        ) {
84            self.contextual_lookup_todos
85                .push(super::ContextualLookupRef {
86                    lookup_id,
87                    active_glyphs,
88                })
89        }
90
91        pub(super) fn pop_a_todo(&mut self) -> Option<super::ContextualLookupRef> {
92            self.contextual_lookup_todos.pop()
93        }
94
95        pub(super) fn closure_glyphs(
96            &mut self,
97            lookup: SubstitutionLookup,
98            lookup_id: u16,
99            current_glyphs: Option<IntSet<GlyphId16>>,
100        ) -> Result<(), crate::ReadError> {
101            if self.needs_to_do_lookup(lookup_id, current_glyphs.as_ref()) {
102                self.cur_glyphs = current_glyphs;
103                lookup.add_reachable_glyphs(self)?;
104                self.cur_glyphs = None;
105            }
106            Ok(())
107        }
108
109        /// skip lookups if we've already seen them with our current state
110        /// <https://github.com/fonttools/fonttools/blob/a6f59a4f87a0111060/Lib/fontTools/subset/__init__.py#L1510>
111        fn needs_to_do_lookup(
112            &mut self,
113            id: u16,
114            current_glyphs: Option<&IntSet<GlyphId16>>,
115        ) -> bool {
116            let (count, covered) = self.finished_lookups.entry(id).or_insert((0, None));
117            if *count != self.glyphs.len() {
118                *count = self.glyphs.len();
119                *covered = Some(IntSet::new());
120            }
121            //TODO: would be nice to have IntSet::is_subset
122            if current_glyphs.unwrap_or(self.glyphs).iter().all(|gid| {
123                covered
124                    .as_ref()
125                    .map(|cov| cov.contains(gid))
126                    // only true if self.glyphs is empty, which means it's a noop anyway?
127                    .unwrap_or(false)
128            }) {
129                return false;
130            }
131            covered
132                .get_or_insert_with(Default::default)
133                .extend(current_glyphs.unwrap_or(self.glyphs).iter());
134            true
135        }
136    }
137}
138
139use ctx::ClosureCtx;
140
141/// a lookup referenced by a contextual lookup
142#[derive(Debug)]
143struct ContextualLookupRef {
144    lookup_id: u16,
145    // 'none' means the graph is too complex, assume all glyphs are active
146    active_glyphs: Option<IntSet<GlyphId16>>,
147}
148
149/// A trait for tables which participate in closure
150trait GlyphClosure {
151    /// Update the set of glyphs with any glyphs reachable via substitution.
152    fn add_reachable_glyphs(&self, ctx: &mut ClosureCtx) -> Result<(), ReadError>;
153}
154
155impl Gsub<'_> {
156    /// Return the set of glyphs reachable from the input set via any substitution.
157    pub fn closure_glyphs(
158        &self,
159        mut glyphs: IntSet<GlyphId16>,
160    ) -> Result<IntSet<GlyphId16>, ReadError> {
161        // we need to do this iteratively, since any glyph found in one pass
162        // over the lookups could also be the target of substitutions.
163
164        let mut ctx = ClosureCtx::new(&mut glyphs);
165
166        let reachable_lookups = self.find_reachable_lookups()?;
167        let mut prev_lookup_count = 0;
168        let mut prev_glyph_count = 0;
169        let mut new_glyph_count = ctx.glyphs().len();
170        let mut new_lookup_count = reachable_lookups.len();
171
172        while (prev_glyph_count, prev_lookup_count) != (new_glyph_count, new_lookup_count) {
173            (prev_glyph_count, prev_lookup_count) = (new_glyph_count, new_lookup_count);
174
175            // we always call this once, and then keep calling if it produces
176            // additional glyphs
177            self.closure_glyphs_once(&mut ctx, &reachable_lookups)?;
178
179            new_lookup_count = reachable_lookups.len();
180            new_glyph_count = ctx.glyphs().len();
181        }
182
183        Ok(glyphs)
184    }
185
186    fn closure_glyphs_once(
187        &self,
188        ctx: &mut ClosureCtx,
189        lookups_to_use: &IntSet<u16>,
190    ) -> Result<(), ReadError> {
191        let lookup_list = self.lookup_list()?;
192        for idx in lookups_to_use.iter() {
193            let lookup = lookup_list.lookups().get(idx as usize)?;
194            ctx.closure_glyphs(lookup, idx, None)?;
195        }
196        // then do any lookups referenced by contextual lookups
197        while let Some(todo) = ctx.pop_a_todo() {
198            let lookup = lookup_list.lookups().get(todo.lookup_id as _)?;
199            ctx.closure_glyphs(lookup, todo.lookup_id, todo.active_glyphs)?;
200        }
201        Ok(())
202    }
203
204    fn find_reachable_lookups(&self) -> Result<IntSet<u16>, ReadError> {
205        let feature_list = self.feature_list()?;
206        let mut lookup_ids = IntSet::new();
207
208        let feature_variations = self
209            .feature_variations()
210            .transpose()?
211            .map(|vars| {
212                let data = vars.offset_data();
213                vars.feature_variation_records()
214                    .iter()
215                    .filter_map(move |rec| {
216                        rec.feature_table_substitution(data)
217                            .transpose()
218                            .ok()
219                            .flatten()
220                    })
221                    .flat_map(|subs| {
222                        subs.substitutions()
223                            .iter()
224                            .map(move |sub| sub.alternate_feature(subs.offset_data()))
225                    })
226            })
227            .into_iter()
228            .flatten();
229        for feature in feature_list
230            .feature_records()
231            .iter()
232            .map(|rec| rec.feature(feature_list.offset_data()))
233            .chain(feature_variations)
234        {
235            lookup_ids.extend(feature?.lookup_list_indices().iter().map(|idx| idx.get()));
236        }
237        Ok(lookup_ids)
238    }
239
240    /// Return a set of all feature indices underneath the specified scripts, languages and features
241    pub fn collect_features(
242        &self,
243        scripts: &IntSet<Tag>,
244        languages: &IntSet<Tag>,
245        features: &IntSet<Tag>,
246    ) -> Result<IntSet<u16>, ReadError> {
247        let feature_list = self.feature_list()?;
248        let script_list = self.script_list()?;
249        let head_ptr = self.offset_data().as_bytes().as_ptr() as usize;
250        script_list.collect_features(head_ptr, &feature_list, scripts, languages, features)
251    }
252}
253
254impl GlyphClosure for SubstitutionLookup<'_> {
255    fn add_reachable_glyphs(&self, ctx: &mut ClosureCtx) -> Result<(), ReadError> {
256        self.subtables()?.add_reachable_glyphs(ctx)
257    }
258}
259
260impl GlyphClosure for SubstitutionSubtables<'_> {
261    fn add_reachable_glyphs(&self, glyphs: &mut ClosureCtx<'_>) -> Result<(), ReadError> {
262        match self {
263            SubstitutionSubtables::Single(tables) => tables.add_reachable_glyphs(glyphs),
264            SubstitutionSubtables::Multiple(tables) => tables.add_reachable_glyphs(glyphs),
265            SubstitutionSubtables::Alternate(tables) => tables.add_reachable_glyphs(glyphs),
266            SubstitutionSubtables::Ligature(tables) => tables.add_reachable_glyphs(glyphs),
267            SubstitutionSubtables::Reverse(tables) => tables.add_reachable_glyphs(glyphs),
268            SubstitutionSubtables::Contextual(tables) => tables.add_reachable_glyphs(glyphs),
269            SubstitutionSubtables::ChainContextual(tables) => tables.add_reachable_glyphs(glyphs),
270        }
271    }
272}
273
274impl<'a, T: FontRead<'a> + GlyphClosure + 'a, Ext: ExtensionLookup<'a, T> + 'a> GlyphClosure
275    for Subtables<'a, T, Ext>
276{
277    fn add_reachable_glyphs(&self, ctx: &mut ClosureCtx<'_>) -> Result<(), ReadError> {
278        self.iter().try_for_each(|t| t?.add_reachable_glyphs(ctx))
279    }
280}
281
282impl GlyphClosure for SingleSubst<'_> {
283    fn add_reachable_glyphs(&self, ctx: &mut ClosureCtx<'_>) -> Result<(), ReadError> {
284        for (target, replacement) in self.iter_subs()? {
285            if ctx.current_glyphs().contains(target) {
286                ctx.add_glyph(replacement);
287            }
288        }
289        Ok(())
290    }
291}
292
293impl SingleSubst<'_> {
294    fn iter_subs(&self) -> Result<impl Iterator<Item = (GlyphId16, GlyphId16)> + '_, ReadError> {
295        let (left, right) = match self {
296            SingleSubst::Format1(t) => (Some(t.iter_subs()?), None),
297            SingleSubst::Format2(t) => (None, Some(t.iter_subs()?)),
298        };
299        Ok(left
300            .into_iter()
301            .flatten()
302            .chain(right.into_iter().flatten()))
303    }
304}
305
306impl SingleSubstFormat1<'_> {
307    fn iter_subs(&self) -> Result<impl Iterator<Item = (GlyphId16, GlyphId16)> + '_, ReadError> {
308        let delta = self.delta_glyph_id();
309        let coverage = self.coverage()?;
310        Ok(coverage.iter().filter_map(move |gid| {
311            let raw = (gid.to_u16() as i32).checked_add(delta as i32);
312            let raw = raw.and_then(|raw| u16::try_from(raw).ok())?;
313            Some((gid, GlyphId16::new(raw)))
314        }))
315    }
316}
317
318impl SingleSubstFormat2<'_> {
319    fn iter_subs(&self) -> Result<impl Iterator<Item = (GlyphId16, GlyphId16)> + '_, ReadError> {
320        let coverage = self.coverage()?;
321        let subs = self.substitute_glyph_ids();
322        Ok(coverage.iter().zip(subs.iter().map(|id| id.get())))
323    }
324}
325
326impl GlyphClosure for MultipleSubstFormat1<'_> {
327    fn add_reachable_glyphs(&self, ctx: &mut ClosureCtx<'_>) -> Result<(), ReadError> {
328        let coverage = self.coverage()?;
329        let sequences = self.sequences();
330        for (gid, replacements) in coverage.iter().zip(sequences.iter()) {
331            let replacements = replacements?;
332            if ctx.current_glyphs().contains(gid) {
333                ctx.extend_glyphs(
334                    replacements
335                        .substitute_glyph_ids()
336                        .iter()
337                        .map(|gid| gid.get()),
338                );
339            }
340        }
341        Ok(())
342    }
343}
344
345impl GlyphClosure for AlternateSubstFormat1<'_> {
346    fn add_reachable_glyphs(&self, ctx: &mut ClosureCtx<'_>) -> Result<(), ReadError> {
347        let coverage = self.coverage()?;
348        let alts = self.alternate_sets();
349        for (gid, alts) in coverage.iter().zip(alts.iter()) {
350            let alts = alts?;
351            if ctx.current_glyphs().contains(gid) {
352                ctx.extend_glyphs(alts.alternate_glyph_ids().iter().map(|gid| gid.get()));
353            }
354        }
355        Ok(())
356    }
357}
358
359impl GlyphClosure for LigatureSubstFormat1<'_> {
360    fn add_reachable_glyphs(&self, ctx: &mut ClosureCtx<'_>) -> Result<(), ReadError> {
361        let coverage = self.coverage()?;
362        let ligs = self.ligature_sets();
363        for (gid, lig_set) in coverage.iter().zip(ligs.iter()) {
364            let lig_set = lig_set?;
365            if ctx.current_glyphs().contains(gid) {
366                for lig in lig_set.ligatures().iter() {
367                    let lig = lig?;
368                    if lig
369                        .component_glyph_ids()
370                        .iter()
371                        .all(|gid| ctx.glyphs().contains(gid.get()))
372                    {
373                        ctx.add_glyph(lig.ligature_glyph());
374                    }
375                }
376            }
377        }
378        Ok(())
379    }
380}
381
382impl GlyphClosure for ReverseChainSingleSubstFormat1<'_> {
383    fn add_reachable_glyphs(&self, ctx: &mut ClosureCtx<'_>) -> Result<(), ReadError> {
384        for coverage in self
385            .backtrack_coverages()
386            .iter()
387            .chain(self.lookahead_coverages().iter())
388        {
389            if !coverage?.iter().any(|gid| ctx.glyphs().contains(gid)) {
390                return Ok(());
391            }
392        }
393
394        for (gid, sub) in self.coverage()?.iter().zip(self.substitute_glyph_ids()) {
395            if ctx.current_glyphs().contains(gid) {
396                ctx.add_glyph(sub.get());
397            }
398        }
399
400        Ok(())
401    }
402}
403
404impl GlyphClosure for SequenceContext<'_> {
405    fn add_reachable_glyphs(&self, ctx: &mut ClosureCtx) -> Result<(), ReadError> {
406        match self {
407            Self::Format1(table) => ContextFormat1::Plain(table.clone()).add_reachable_glyphs(ctx),
408            Self::Format2(table) => ContextFormat2::Plain(table.clone()).add_reachable_glyphs(ctx),
409            Self::Format3(table) => ContextFormat3::Plain(table.clone()).add_reachable_glyphs(ctx),
410        }
411    }
412}
413
414impl GlyphClosure for ChainedSequenceContext<'_> {
415    fn add_reachable_glyphs(&self, ctx: &mut ClosureCtx) -> Result<(), ReadError> {
416        match self {
417            Self::Format1(table) => ContextFormat1::Chain(table.clone()).add_reachable_glyphs(ctx),
418            Self::Format2(table) => ContextFormat2::Chain(table.clone()).add_reachable_glyphs(ctx),
419            Self::Format3(table) => ContextFormat3::Chain(table.clone()).add_reachable_glyphs(ctx),
420        }
421    }
422}
423
424//https://github.com/fonttools/fonttools/blob/a6f59a4f8/Lib/fontTools/subset/__init__.py#L1182
425impl GlyphClosure for ContextFormat1<'_> {
426    fn add_reachable_glyphs(&self, ctx: &mut ClosureCtx<'_>) -> Result<(), ReadError> {
427        let coverage = self.coverage()?;
428        let Some(cur_glyphs) = intersect_coverage(&coverage, ctx.current_glyphs()) else {
429            return Ok(());
430        };
431
432        // now for each rule set that applies to a current glyph:
433        for (i, seq) in coverage
434            .iter()
435            .zip(self.rule_sets())
436            .enumerate()
437            .filter_map(|(i, (gid, seq))| {
438                seq.filter(|_| cur_glyphs.contains(gid)).map(|seq| (i, seq))
439            })
440        {
441            for rule in seq?.rules() {
442                let rule = rule?;
443                // skip rules if the whole input sequence isn't in our glyphset
444                if !rule.matches_glyphs(ctx.glyphs()) {
445                    continue;
446                }
447                // python calls this 'chaos'. Basically: if there are multiple
448                // lookups applied at a single position they can interact, and
449                // we can no longer trivially determine the state of the context
450                // at that point. In this case we give up, and assume that the
451                // second lookup is reachable by all glyphs.
452                let mut seen_sequence_indices = IntSet::new();
453                for lookup_record in rule.lookup_records() {
454                    let lookup_id = lookup_record.lookup_list_index();
455                    let sequence_idx = lookup_record.sequence_index();
456                    let active_glyphs = if !seen_sequence_indices.insert(sequence_idx) {
457                        // During processing, when we see an empty set we will replace
458                        // it with the full current glyph set
459                        None
460                    } else if sequence_idx == 0 {
461                        Some(IntSet::from([coverage.iter().nth(i).unwrap()]))
462                    } else {
463                        Some(IntSet::from([rule.input_sequence()
464                            [sequence_idx as usize - 1]
465                            .get()]))
466                    };
467                    ctx.add_todo(lookup_id, active_glyphs);
468                }
469            }
470        }
471        Ok(())
472    }
473}
474
475//https://github.com/fonttools/fonttools/blob/a6f59a4f87a0111/Lib/fontTools/subset/__init__.py#L1215
476impl GlyphClosure for ContextFormat2<'_> {
477    fn add_reachable_glyphs(&self, ctx: &mut ClosureCtx) -> Result<(), ReadError> {
478        let coverage = self.coverage()?;
479        let Some(cur_glyphs) = intersect_coverage(&coverage, ctx.current_glyphs()) else {
480            return Ok(());
481        };
482
483        let classdef = self.input_class_def()?;
484        let our_classes = make_class_set(ctx.glyphs(), &classdef);
485        for (class_i, seq) in self
486            .rule_sets()
487            .enumerate()
488            .filter_map(|(i, seq)| seq.map(|seq| (i as u16, seq)))
489            .filter(|x| our_classes.contains(x.0))
490        {
491            for rule in seq?.rules() {
492                let rule = rule?;
493                if !rule.matches_classes(&our_classes) {
494                    continue;
495                }
496
497                let mut seen_sequence_indices = IntSet::new();
498                for lookup_record in rule.lookup_records() {
499                    let lookup_id = lookup_record.lookup_list_index();
500                    let seq_idx = lookup_record.sequence_index();
501                    let active_glyphs = if !seen_sequence_indices.insert(seq_idx) {
502                        None
503                    } else if seq_idx == 0 {
504                        Some(intersect_class(&classdef, &cur_glyphs, class_i))
505                    } else {
506                        Some(intersect_class(
507                            &classdef,
508                            ctx.glyphs(),
509                            rule.input_sequence()[seq_idx as usize - 1].get(),
510                        ))
511                    };
512
513                    ctx.add_todo(lookup_id, active_glyphs);
514                }
515            }
516        }
517        Ok(())
518    }
519}
520
521impl GlyphClosure for ContextFormat3<'_> {
522    fn add_reachable_glyphs(&self, ctx: &mut ClosureCtx) -> Result<(), ReadError> {
523        let cov0 = self.coverages().get(0)?;
524        let Some(cur_glyphs) = intersect_coverage(&cov0, ctx.current_glyphs()) else {
525            return Ok(());
526        };
527
528        let glyphs = ctx.glyphs().iter().map(GlyphId::from).collect();
529        if !self.matches_glyphs(&glyphs)? {
530            return Ok(());
531        }
532        for record in self.lookup_records() {
533            let mut seen_sequence_indices = IntSet::new();
534            let seq_idx = record.sequence_index();
535            let lookup_id = record.lookup_list_index();
536            let active_glyphs = if !seen_sequence_indices.insert(seq_idx) {
537                None
538            } else if seq_idx == 0 {
539                Some(cur_glyphs.clone())
540            } else {
541                Some(
542                    self.coverages()
543                        .get(seq_idx as _)?
544                        .iter()
545                        .filter(|gid| ctx.glyphs().contains(*gid))
546                        .collect(),
547                )
548            };
549
550            ctx.add_todo(lookup_id, active_glyphs);
551        }
552        Ok(())
553    }
554}
555
556/// The set of classes for this set of glyphs
557fn make_class_set(glyphs: &IntSet<GlyphId16>, classdef: &ClassDef) -> IntSet<u16> {
558    glyphs.iter().map(|gid| classdef.get(gid)).collect()
559}
560
561/// Return the subset of `glyphs` that has the given class in this classdef
562// https://github.com/fonttools/fonttools/blob/a6f59a4f87a01110/Lib/fontTools/subset/__init__.py#L516
563fn intersect_class(
564    classdef: &ClassDef,
565    glyphs: &IntSet<GlyphId16>,
566    class: u16,
567) -> IntSet<GlyphId16> {
568    glyphs
569        .iter()
570        .filter(|gid| classdef.get(*gid) == class)
571        .collect()
572}
573
574fn intersect_coverage(
575    coverage: &CoverageTable,
576    glyphs: &IntSet<GlyphId16>,
577) -> Option<IntSet<GlyphId16>> {
578    let r = coverage
579        .iter()
580        .filter(|gid| glyphs.contains(*gid))
581        .collect::<IntSet<_>>();
582    Some(r).filter(|set| !set.is_empty())
583}
584
585impl SubstitutionLookupList<'_> {
586    pub fn closure_lookups(
587        &self,
588        glyph_set: &IntSet<GlyphId>,
589        lookup_indices: &mut IntSet<u16>,
590    ) -> Result<(), ReadError> {
591        let mut c = LookupClosureCtx::new(glyph_set);
592
593        let lookups = self.lookups();
594        for idx in lookup_indices.iter() {
595            let lookup = lookups.get(idx as usize)?;
596            lookup.closure_lookups(&mut c, idx)?;
597        }
598
599        lookup_indices.union(c.visited_lookups());
600        lookup_indices.subtract(c.inactive_lookups());
601        Ok(())
602    }
603}
604
605impl LookupClosure for SubstitutionLookup<'_> {
606    fn closure_lookups(
607        &self,
608        c: &mut LookupClosureCtx,
609        lookup_index: u16,
610    ) -> Result<(), ReadError> {
611        if !c.should_visit_lookup(lookup_index) {
612            return Ok(());
613        }
614
615        if !self.intersects(c.glyphs())? {
616            c.set_lookup_inactive(lookup_index);
617            return Ok(());
618        }
619
620        let lookup_type = self.lookup_type();
621        self.subtables()?.closure_lookups(c, lookup_type)
622    }
623
624    fn intersects(&self, glyph_set: &IntSet<GlyphId>) -> Result<bool, ReadError> {
625        self.subtables()?.intersects(glyph_set)
626    }
627}
628
629impl LookupClosure for SubstitutionSubtables<'_> {
630    fn closure_lookups(&self, _c: &mut LookupClosureCtx, _arg: u16) -> Result<(), ReadError> {
631        Ok(())
632    }
633
634    fn intersects(&self, glyph_set: &IntSet<GlyphId>) -> Result<bool, ReadError> {
635        match self {
636            SubstitutionSubtables::Single(subtables) => subtables.intersects(glyph_set),
637            SubstitutionSubtables::Multiple(subtables) => subtables.intersects(glyph_set),
638            SubstitutionSubtables::Alternate(subtables) => subtables.intersects(glyph_set),
639            SubstitutionSubtables::Ligature(subtables) => subtables.intersects(glyph_set),
640            SubstitutionSubtables::Contextual(subtables) => subtables.intersects(glyph_set),
641            SubstitutionSubtables::ChainContextual(subtables) => subtables.intersects(glyph_set),
642            SubstitutionSubtables::Reverse(subtables) => subtables.intersects(glyph_set),
643        }
644    }
645}
646
647impl LookupClosure for SingleSubst<'_> {
648    fn intersects(&self, glyph_set: &IntSet<GlyphId>) -> Result<bool, ReadError> {
649        match self {
650            Self::Format1(item) => item.intersects(glyph_set),
651            Self::Format2(item) => item.intersects(glyph_set),
652        }
653    }
654}
655
656impl LookupClosure for SingleSubstFormat1<'_> {
657    fn intersects(&self, glyph_set: &IntSet<GlyphId>) -> Result<bool, ReadError> {
658        Ok(self.coverage()?.intersects(glyph_set))
659    }
660}
661
662impl LookupClosure for SingleSubstFormat2<'_> {
663    fn intersects(&self, glyph_set: &IntSet<GlyphId>) -> Result<bool, ReadError> {
664        Ok(self.coverage()?.intersects(glyph_set))
665    }
666}
667
668impl LookupClosure for MultipleSubstFormat1<'_> {
669    fn intersects(&self, glyph_set: &IntSet<GlyphId>) -> Result<bool, ReadError> {
670        Ok(self.coverage()?.intersects(glyph_set))
671    }
672}
673
674impl LookupClosure for AlternateSubstFormat1<'_> {
675    fn intersects(&self, glyph_set: &IntSet<GlyphId>) -> Result<bool, ReadError> {
676        Ok(self.coverage()?.intersects(glyph_set))
677    }
678}
679
680impl LookupClosure for LigatureSubstFormat1<'_> {
681    fn intersects(&self, glyph_set: &IntSet<GlyphId>) -> Result<bool, ReadError> {
682        let coverage = self.coverage()?;
683        let lig_sets = self.ligature_sets();
684        for lig_set in coverage
685            .iter()
686            .zip(lig_sets.iter())
687            .filter_map(|(g, lig_set)| glyph_set.contains(GlyphId::from(g)).then_some(lig_set))
688        {
689            if lig_set?.intersects(glyph_set)? {
690                return Ok(true);
691            }
692        }
693        Ok(false)
694    }
695}
696
697impl LookupClosure for LigatureSet<'_> {
698    fn intersects(&self, glyph_set: &IntSet<GlyphId>) -> Result<bool, ReadError> {
699        let ligs = self.ligatures();
700        for lig in ligs.iter() {
701            if lig?.intersects(glyph_set)? {
702                return Ok(true);
703            }
704        }
705        Ok(false)
706    }
707}
708
709impl LookupClosure for Ligature<'_> {
710    fn intersects(&self, glyph_set: &IntSet<GlyphId>) -> Result<bool, ReadError> {
711        let ret = self
712            .component_glyph_ids()
713            .iter()
714            .all(|g| glyph_set.contains(GlyphId::from(g.get())));
715        Ok(ret)
716    }
717}
718
719impl LookupClosure for ReverseChainSingleSubstFormat1<'_> {
720    fn intersects(&self, glyph_set: &IntSet<GlyphId>) -> Result<bool, ReadError> {
721        if !self.coverage()?.intersects(glyph_set) {
722            return Ok(false);
723        }
724
725        for coverage in self.backtrack_coverages().iter() {
726            if !coverage?.intersects(glyph_set) {
727                return Ok(false);
728            }
729        }
730
731        for coverage in self.lookahead_coverages().iter() {
732            if !coverage?.intersects(glyph_set) {
733                return Ok(false);
734            }
735        }
736        Ok(true)
737    }
738}
739
740#[cfg(test)]
741mod tests {
742    use std::collections::{HashMap, HashSet};
743
744    use crate::{FontRef, TableProvider};
745
746    use super::*;
747    use font_test_data::closure as test_data;
748
749    struct GlyphMap {
750        to_gid: HashMap<&'static str, GlyphId16>,
751        from_gid: HashMap<GlyphId16, &'static str>,
752    }
753
754    impl GlyphMap {
755        fn new(raw_order: &'static str) -> GlyphMap {
756            let to_gid: HashMap<_, _> = raw_order
757                .split('\n')
758                .map(|line| line.trim())
759                .filter(|line| !(line.starts_with('#') || line.is_empty()))
760                .enumerate()
761                .map(|(gid, name)| (name, GlyphId16::new(gid.try_into().unwrap())))
762                .collect();
763            let from_gid = to_gid.iter().map(|(name, gid)| (*gid, *name)).collect();
764            GlyphMap { from_gid, to_gid }
765        }
766
767        fn get_gid(&self, name: &str) -> Option<GlyphId16> {
768            self.to_gid.get(name).copied()
769        }
770
771        fn get_name(&self, gid: GlyphId16) -> Option<&str> {
772            self.from_gid.get(&gid).copied()
773        }
774    }
775
776    fn get_gsub(test_data: &'static [u8]) -> Gsub<'static> {
777        let font = FontRef::new(test_data).unwrap();
778        font.gsub().unwrap()
779    }
780
781    fn compute_closure(gsub: &Gsub, glyph_map: &GlyphMap, input: &[&str]) -> IntSet<GlyphId16> {
782        let input_glyphs = input
783            .iter()
784            .map(|name| glyph_map.get_gid(name).unwrap())
785            .collect();
786        gsub.closure_glyphs(input_glyphs).unwrap()
787    }
788
789    /// assert a set of glyph ids matches a slice of names
790    macro_rules! assert_closure_result {
791        ($glyph_map:expr, $result:expr, $expected:expr) => {
792            let result = $result
793                .iter()
794                .map(|gid| $glyph_map.get_name(gid).unwrap())
795                .collect::<HashSet<_>>();
796            let expected = $expected.iter().copied().collect::<HashSet<_>>();
797            if expected != result {
798                let in_output = result.difference(&expected).collect::<Vec<_>>();
799                let in_expected = expected.difference(&result).collect::<Vec<_>>();
800                let mut msg = format!("Closure output does not match\n");
801                if !in_expected.is_empty() {
802                    msg.push_str(format!("missing {in_expected:?}\n").as_str());
803                }
804                if !in_output.is_empty() {
805                    msg.push_str(format!("unexpected {in_output:?}").as_str());
806                }
807                panic!("{msg}")
808            }
809        };
810    }
811
812    #[test]
813    fn smoke_test() {
814        // tests various lookup types.
815        // test input is font-test-data/test_data/fea/simple_closure.fea
816        let gsub = get_gsub(test_data::SIMPLE);
817        let glyph_map = GlyphMap::new(test_data::SIMPLE_GLYPHS);
818        let result = compute_closure(&gsub, &glyph_map, &["a"]);
819
820        assert_closure_result!(
821            glyph_map,
822            result,
823            &["a", "A", "b", "c", "d", "a_a", "a.1", "a.2", "a.3"]
824        );
825    }
826
827    #[test]
828    fn recursive() {
829        // a scenario in which one substitution adds glyphs that trigger additional
830        // substitutions.
831        //
832        // test input is font-test-data/test_data/fea/recursive_closure.fea
833        let gsub = get_gsub(test_data::RECURSIVE);
834        let glyph_map = GlyphMap::new(test_data::RECURSIVE_GLYPHS);
835        let result = compute_closure(&gsub, &glyph_map, &["a"]);
836        assert_closure_result!(glyph_map, result, &["a", "b", "c", "d"]);
837    }
838
839    #[test]
840    fn contextual_lookups_nop() {
841        let gsub = get_gsub(test_data::CONTEXTUAL);
842        let glyph_map = GlyphMap::new(test_data::CONTEXTUAL_GLYPHS);
843
844        // these match the lookups but not the context
845        let nop = compute_closure(&gsub, &glyph_map, &["three", "four", "e", "f"]);
846        assert_closure_result!(glyph_map, nop, &["three", "four", "e", "f"]);
847    }
848
849    #[test]
850    fn contextual_lookups_chained_f1() {
851        let gsub = get_gsub(test_data::CONTEXTUAL);
852        let glyph_map = GlyphMap::new(test_data::CONTEXTUAL_GLYPHS);
853        let gsub6f1 = compute_closure(
854            &gsub,
855            &glyph_map,
856            &["one", "two", "three", "four", "five", "six", "seven"],
857        );
858        assert_closure_result!(
859            glyph_map,
860            gsub6f1,
861            &["one", "two", "three", "four", "five", "six", "seven", "X", "Y"]
862        );
863    }
864
865    #[test]
866    fn contextual_lookups_chained_f3() {
867        let gsub = get_gsub(test_data::CONTEXTUAL);
868        let glyph_map = GlyphMap::new(test_data::CONTEXTUAL_GLYPHS);
869        let gsub6f3 = compute_closure(&gsub, &glyph_map, &["space", "e"]);
870        assert_closure_result!(glyph_map, gsub6f3, &["space", "e", "e.2"]);
871
872        let gsub5f3 = compute_closure(&gsub, &glyph_map, &["f", "g"]);
873        assert_closure_result!(glyph_map, gsub5f3, &["f", "g", "f.2"]);
874    }
875
876    #[test]
877    fn contextual_plain_f1() {
878        let gsub = get_gsub(test_data::CONTEXTUAL);
879        let glyph_map = GlyphMap::new(test_data::CONTEXTUAL_GLYPHS);
880        let gsub5f1 = compute_closure(&gsub, &glyph_map, &["a", "b"]);
881        assert_closure_result!(glyph_map, gsub5f1, &["a", "b", "a_b"]);
882    }
883
884    #[test]
885    fn contextual_plain_f3() {
886        let gsub = get_gsub(test_data::CONTEXTUAL);
887        let glyph_map = GlyphMap::new(test_data::CONTEXTUAL_GLYPHS);
888        let gsub5f3 = compute_closure(&gsub, &glyph_map, &["f", "g"]);
889        assert_closure_result!(glyph_map, gsub5f3, &["f", "g", "f.2"]);
890    }
891
892    #[test]
893    fn recursive_context() {
894        let gsub = get_gsub(test_data::RECURSIVE_CONTEXTUAL);
895        let glyph_map = GlyphMap::new(test_data::RECURSIVE_CONTEXTUAL_GLYPHS);
896
897        let nop = compute_closure(&gsub, &glyph_map, &["b", "B"]);
898        assert_closure_result!(glyph_map, nop, &["b", "B"]);
899
900        let full = compute_closure(&gsub, &glyph_map, &["a", "b", "c"]);
901        assert_closure_result!(glyph_map, full, &["a", "b", "c", "B", "B.2", "B.3"]);
902
903        let intermediate = compute_closure(&gsub, &glyph_map, &["a", "B.2"]);
904        assert_closure_result!(glyph_map, intermediate, &["a", "B.2", "B.3"]);
905    }
906
907    #[test]
908    fn feature_variations() {
909        let gsub = get_gsub(test_data::VARIATIONS_CLOSURE);
910        let glyph_map = GlyphMap::new(test_data::VARIATIONS_GLYPHS);
911
912        let input = compute_closure(&gsub, &glyph_map, &["a"]);
913        assert_closure_result!(glyph_map, input, &["a", "b", "c"]);
914    }
915
916    #[test]
917    fn context_with_unreachable_rules() {
918        let gsub = get_gsub(test_data::CONTEXT_WITH_UNREACHABLE_BITS);
919        let glyph_map = GlyphMap::new(test_data::CONTEXT_WITH_UNREACHABLE_BITS_GLYPHS);
920
921        let nop = compute_closure(&gsub, &glyph_map, &["c", "z"]);
922        assert_closure_result!(glyph_map, nop, &["c", "z"]);
923
924        let full = compute_closure(&gsub, &glyph_map, &["a", "b", "c", "z"]);
925        assert_closure_result!(glyph_map, full, &["a", "b", "c", "z", "A", "B"]);
926    }
927
928    #[test]
929    fn cyclical_context() {
930        let gsub = get_gsub(test_data::CYCLIC_CONTEXTUAL);
931        let glyph_map = GlyphMap::new(test_data::RECURSIVE_CONTEXTUAL_GLYPHS);
932        // we mostly care that this terminates
933        let nop = compute_closure(&gsub, &glyph_map, &["a", "b", "c"]);
934        assert_closure_result!(glyph_map, nop, &["a", "b", "c"]);
935    }
936
937    #[test]
938    fn collect_all_features() {
939        let font = FontRef::new(font_test_data::closure::CONTEXTUAL).unwrap();
940        let gsub = font.gsub().unwrap();
941        let ret = gsub
942            .collect_features(&IntSet::all(), &IntSet::all(), &IntSet::all())
943            .unwrap();
944        assert_eq!(ret.len(), 2);
945        assert!(ret.contains(0));
946        assert!(ret.contains(1));
947    }
948
949    #[test]
950    fn collect_all_features_with_feature_filter() {
951        let font = FontRef::new(font_test_data::closure::CONTEXTUAL).unwrap();
952        let gsub = font.gsub().unwrap();
953
954        let mut feature_tags = IntSet::empty();
955        feature_tags.insert(Tag::new(b"SUB5"));
956
957        let ret = gsub
958            .collect_features(&IntSet::all(), &IntSet::all(), &feature_tags)
959            .unwrap();
960        assert_eq!(ret.len(), 1);
961        assert!(ret.contains(0));
962    }
963
964    #[test]
965    fn collect_all_features_with_script_filter() {
966        let font = FontRef::new(font_test_data::closure::CONTEXTUAL).unwrap();
967        let gsub = font.gsub().unwrap();
968
969        let mut script_tags = IntSet::empty();
970        script_tags.insert(Tag::new(b"LATN"));
971
972        let ret = gsub
973            .collect_features(&script_tags, &IntSet::all(), &IntSet::all())
974            .unwrap();
975        assert!(ret.is_empty());
976    }
977}
read_fonts/tables/gsub/closure.rs

read_fonts/tables/gsub/
closure.rs
