Skip to main content

harfrust/ot/lookup/
build.rs

1//! Reading a lookup and deriving the data its subtables apply with.
2
3use super::coverage::Coverage;
4use super::{context, gpos, gsub, CachedLookup, CachedSubtable, IntoKind, SubtableDigests};
5use crate::budget::{Budget, Exhausted};
6use crate::ot::apply::MappingCache;
7use crate::set_digest::SetDigest;
8use alloc::{boxed::Box, vec::Vec};
9use read_fonts::model::Tables;
10use read_fonts::tables::{
11    gpos::{CursivePos, MarkBasePos, MarkLigPos, MarkMarkPos, PairPos, SinglePos},
12    gsub::{
13        AlternateSubst, ExtensionSubstFormat1, LigatureSubst, MultipleSubst,
14        ReverseChainSingleSubst, SingleSubst,
15    },
16    layout::{
17        ChainedSequenceContext, CoverageTable, Lookup, LookupFlag, SelectedLookupList,
18        SequenceContext,
19    },
20};
21use read_fonts::{FontData, FontRead, ReadError, TableProvider};
22
23/// Subtables past this many in a lookup get no glyph lookup caches.
24const MAX_CACHED_SUBTABLES: usize = 8;
25
26/// Coverages of fewer than 8 glyphs or ranges get no cache: searching them
27/// costs about as much as a cache hit, and a cache takes 512 bytes.
28const MIN_CACHED_COVERAGE_COST: u32 = 4;
29
30/// A malformed subtable is skipped; exhausted preprocessing aborts its lookup.
31#[derive(Debug, PartialEq, Eq)]
32pub(super) enum BuildError {
33    Invalid,
34    Exhausted,
35}
36
37impl From<ReadError> for BuildError {
38    fn from(_: ReadError) -> Self {
39        Self::Invalid
40    }
41}
42
43impl From<Exhausted> for BuildError {
44    fn from(_: Exhausted) -> Self {
45        Self::Exhausted
46    }
47}
48
49/// The number of lookups in GSUB, or GPOS if `is_subst` is false.
50pub(super) fn lookup_count(tables: &Tables, is_subst: bool) -> u16 {
51    let count = if is_subst {
52        tables
53            .gsub()
54            .ok()
55            .and_then(|gsub| gsub.lookup_list().ok())
56            .map(|list| list.lookup_count())
57    } else {
58        tables
59            .gpos()
60            .ok()
61            .and_then(|gpos| gpos.lookup_list().ok())
62            .map(|list| list.lookup_count())
63    };
64    count.unwrap_or_default()
65}
66
67/// Reads lookup `index` of GSUB, or GPOS if `is_subst` is false.
68pub(super) fn build_lookup<'a>(
69    tables: &'a Tables,
70    is_subst: bool,
71    index: u16,
72    budget: &Budget,
73) -> Result<CachedLookup<'a>, BuildError> {
74    let (list_data, offset) = if is_subst {
75        lookup_location(&tables.gsub()?.lookup_list()?, index)
76    } else {
77        lookup_location(&tables.gpos()?.lookup_list()?, index)
78    }
79    .ok_or(BuildError::Invalid)?;
80    build_lookup_at(list_data, offset, is_subst, budget)
81}
82
83/// The data of a lookup list and the offset of lookup `index` in it.
84fn lookup_location<'a, T: FontRead<'a, Args = ()> + 'a>(
85    list: &SelectedLookupList<'a, T>,
86    index: u16,
87) -> Option<(FontData<'a>, usize)> {
88    let index = usize::from(index);
89    let offset = match list {
90        SelectedLookupList::Original(list) => list.lookup_offsets().get(index)?.get().to_u32(),
91        SelectedLookupList::Extended(list) => list.lookup_offsets().get(index)?.get().to_u32(),
92    };
93    Some((list.offset_data(), offset as usize))
94}
95
96/// Reads the lookup at `offset` in a GSUB (`is_subst`) or GPOS table.
97pub(super) fn build_lookup_at<'a>(
98    table_data: FontData<'a>,
99    offset: usize,
100    is_subst: bool,
101    budget: &Budget,
102) -> Result<CachedLookup<'a>, BuildError> {
103    budget.work(1)?;
104    let lookup: Lookup<()> =
105        Lookup::read(table_data.split_off(offset).ok_or(BuildError::Invalid)?)?;
106    let count = usize::from(lookup.sub_table_count());
107    budget.work(count)?;
108    budget.alloc::<CachedSubtable>(count)?;
109    let lookup_type = lookup.lookup_type();
110    let flag = lookup.lookup_flag();
111    let mut props = u32::from(flag.to_bits());
112    if flag.to_bits() & LookupFlag::USE_MARK_FILTERING_SET.to_bits() != 0 {
113        props |= u32::from(lookup.mark_filtering_set().unwrap_or_default()) << 16;
114    }
115    let mut cached = CachedLookup {
116        props,
117        is_subst,
118        is_reversed: is_subst && is_reversed(table_data, &lookup, offset).unwrap_or_default(),
119        digest: SetDigest::new(),
120        digest_second: SetDigest::new(),
121        hot_subtable: None,
122        uses_class_cache: false,
123        walk: super::walk_each,
124        subtables: Vec::with_capacity(count),
125    };
126    let mut hot_cost = 0;
127    let mut all_share_second_glyph = true;
128    for (index, subtable_offset) in lookup.subtable_offsets().iter().enumerate() {
129        let source = Source {
130            table_data,
131            offset: offset + subtable_offset.get().to_u32() as usize,
132            is_subst,
133            with_caches: index < MAX_CACHED_SUBTABLES,
134            budget,
135        };
136        let built = match source.build(lookup_type) {
137            Ok(built) => built,
138            Err(BuildError::Invalid) => continue,
139            Err(BuildError::Exhausted) => return Err(BuildError::Exhausted),
140        };
141        all_share_second_glyph &= built.shares_second_glyph;
142        cached.digest.union(&built.subtable.digest);
143        cached.digest_second.union(&built.digest_second);
144        if built.cache_cost > hot_cost {
145            hot_cost = built.cache_cost;
146            cached.hot_subtable = Some(cached.subtables.len());
147        }
148        cached.subtables.push(built.subtable);
149    }
150    // Only the class-based contexts report a cost, and they cache classes.
151    cached.uses_class_cache = cached.hot_subtable.is_some();
152    cached.walk = match cached.subtables.len() {
153        1 => super::walk_single,
154        _ if all_share_second_glyph => super::walk_sharing_second_glyph,
155        _ => super::walk_each,
156    };
157    Ok(cached)
158}
159
160fn is_extension(is_subst: bool, lookup_type: u16) -> bool {
161    lookup_type == if is_subst { 7 } else { 9 }
162}
163
164/// Whether a GSUB lookup is a reverse chain, looking through an extension.
165fn is_reversed(table_data: FontData, lookup: &Lookup<()>, lookup_offset: usize) -> Option<bool> {
166    match lookup.lookup_type() {
167        8 => Some(true),
168        7 => {
169            let offset = lookup_offset + lookup.subtable_offsets().first()?.get().to_u32() as usize;
170            let ext = ExtensionSubstFormat1::<()>::read(table_data.split_off(offset)?).ok()?;
171            let ext_type = ext.extension_lookup_type();
172            (!is_extension(true, ext_type)).then_some(ext_type == 8)
173        }
174        _ => Some(false),
175    }
176}
177
178/// A subtable together with what its lookup needs to know about it.
179struct BuiltSubtable<'a> {
180    subtable: CachedSubtable<'a>,
181    digest_second: SetDigest,
182    cache_cost: u32,
183    /// Whether the subtable adjusts pairs and shares the second glyph.
184    shares_second_glyph: bool,
185}
186
187/// Where a subtable is and how to cache it.
188#[derive(Clone, Copy)]
189struct Source<'a, 'b> {
190    table_data: FontData<'a>,
191    offset: usize,
192    is_subst: bool,
193    with_caches: bool,
194    budget: &'b Budget,
195}
196
197impl<'a> Source<'a, '_> {
198    fn build(self, lookup_type: u16) -> Result<BuiltSubtable<'a>, BuildError> {
199        let data = self
200            .table_data
201            .split_off(self.offset)
202            .ok_or(BuildError::Invalid)?;
203        self.budget.work(1)?;
204        let budget = self.budget;
205        let caches = self.with_caches;
206        match (self.is_subst, lookup_type) {
207            (true, 1) => match SingleSubst::read(data)? {
208                SingleSubst::Format1(t) => self.finish(t.coverage(), gsub::SingleSubst1::new(&t)),
209                SingleSubst::Format2(t) => self.finish(t.coverage(), gsub::SingleSubst2::new(&t)),
210                SingleSubst::Format3(t) => {
211                    self.finish(t.coverage(), gsub::SingleSubst1::new_wide(&t))
212                }
213                SingleSubst::Format4(t) => {
214                    self.finish(t.coverage(), gsub::SingleSubst2::new_wide(&t))
215                }
216            },
217            (true, 2) => match MultipleSubst::read(data)? {
218                MultipleSubst::Format1(t) => {
219                    self.finish(t.coverage(), gsub::MultipleSubst1::new(&t))
220                }
221                MultipleSubst::Format2(t) => {
222                    self.finish(t.coverage(), gsub::MultipleSubst1::new_wide(&t))
223                }
224            },
225            (true, 3) => match AlternateSubst::read(data)? {
226                AlternateSubst::Format1(t) => {
227                    self.finish(t.coverage(), gsub::AlternateSubst1::new(&t))
228                }
229                AlternateSubst::Format2(t) => {
230                    self.finish(t.coverage(), gsub::AlternateSubst1::new_wide(&t))
231                }
232            },
233            (true, 4) => match LigatureSubst::read(data)? {
234                LigatureSubst::Format1(t) => {
235                    self.finish(t.coverage(), Some(gsub::LigatureSubst1::new(&t, budget)?))
236                }
237                LigatureSubst::Format2(t) => self.finish(
238                    t.coverage(),
239                    Some(gsub::LigatureSubst1::new_wide(&t, budget)?),
240                ),
241            },
242            (true, 8) => match ReverseChainSingleSubst::read(data)? {
243                ReverseChainSingleSubst::Format1(t) => {
244                    self.finish(t.coverage(), gsub::ReverseChainSubst1::new(&t, budget)?)
245                }
246                ReverseChainSingleSubst::Format2(t) => self.finish(
247                    t.coverage(),
248                    gsub::ReverseChainSubst1::new_wide(&t, budget)?,
249                ),
250            },
251            (false, 1) => match SinglePos::read(data)? {
252                SinglePos::Format1(t) => self.finish(t.coverage(), gpos::SinglePos1::new(&t)),
253                SinglePos::Format2(t) => self.finish(t.coverage(), gpos::SinglePos2::new(&t)),
254                SinglePos::Format3(t) => self.finish(t.coverage(), gpos::SinglePos1::new_wide(&t)),
255                SinglePos::Format4(t) => self.finish(t.coverage(), gpos::SinglePos2::new_wide(&t)),
256            },
257            (false, 2) => match PairPos::read(data)? {
258                PairPos::Format1(t) => match gpos::PairKern1::new(&t, budget)? {
259                    Some(kern) => self.finish(t.coverage(), Some(kern)),
260                    None => self.finish(t.coverage(), Some(gpos::PairPos1::new(&t, budget)?)),
261                },
262                PairPos::Format2(t) => self.class_pairs(t.coverage(), gpos::ClassPairs::new(&t)),
263                PairPos::Format3(t) => {
264                    self.finish(t.coverage(), Some(gpos::PairPos1::new_wide(&t, budget)?))
265                }
266                PairPos::Format4(t) => {
267                    self.class_pairs(t.coverage(), gpos::ClassPairs::new_wide(&t))
268                }
269            },
270            (false, 3) => match CursivePos::read(data)? {
271                CursivePos::Format1(t) => self.finish(t.coverage(), gpos::CursivePos1::new(&t)),
272                CursivePos::Format2(t) => {
273                    self.finish(t.coverage(), gpos::CursivePos1::new_wide(&t))
274                }
275            },
276            (false, 4) => match MarkBasePos::read(data)? {
277                MarkBasePos::Format1(t) => {
278                    self.finish(t.mark_coverage(), gpos::MarkBasePos1::new(&t))
279                }
280                MarkBasePos::Format2(t) => {
281                    self.finish(t.mark_coverage(), gpos::MarkBasePos1::new_wide(&t))
282                }
283            },
284            (false, 5) => match MarkLigPos::read(data)? {
285                MarkLigPos::Format1(t) => {
286                    self.finish(t.mark_coverage(), gpos::MarkLigPos1::new(&t))
287                }
288                MarkLigPos::Format2(t) => {
289                    self.finish(t.mark_coverage(), gpos::MarkLigPos1::new_wide(&t))
290                }
291            },
292            (false, 6) => match MarkMarkPos::read(data)? {
293                MarkMarkPos::Format1(t) => {
294                    self.finish(t.mark1_coverage(), gpos::MarkMarkPos1::new(&t))
295                }
296                MarkMarkPos::Format2(t) => {
297                    self.finish(t.mark1_coverage(), gpos::MarkMarkPos1::new_wide(&t))
298                }
299            },
300            (true, 5) | (false, 7) => match SequenceContext::read(data)? {
301                SequenceContext::Format1(t) => {
302                    self.finish(t.coverage(), context::ChainContext1::from_plain(&t))
303                }
304                SequenceContext::Format2(t) => self.finish(
305                    t.coverage(),
306                    Some(context::ChainContext2::from_plain(&t, caches, budget)?),
307                ),
308                SequenceContext::Format3(t) => self.finish(
309                    t.coverages().get(0),
310                    Some(context::ChainContext3::from_plain(&t, budget)?),
311                ),
312                SequenceContext::Format4(t) => {
313                    self.finish(t.coverage(), context::ChainContext1::from_plain_wide(&t))
314                }
315                SequenceContext::Format5(t) => self.finish(
316                    t.coverage(),
317                    Some(context::ChainContext2::from_plain_wide(&t, caches, budget)?),
318                ),
319                SequenceContext::Format6(t) => self.finish(
320                    t.coverages().get(0),
321                    Some(context::ChainContext3::from_plain_wide(&t, budget)?),
322                ),
323            },
324            (true, 6) | (false, 8) => match ChainedSequenceContext::read(data)? {
325                ChainedSequenceContext::Format1(t) => {
326                    self.finish(t.coverage(), context::ChainContext1::new(&t))
327                }
328                ChainedSequenceContext::Format2(t) => self.finish(
329                    t.coverage(),
330                    Some(context::ChainContext2::new(&t, caches, budget)?),
331                ),
332                ChainedSequenceContext::Format3(t) => self.finish(
333                    t.input_coverages().get(0),
334                    Some(context::ChainContext3::new(&t, budget)?),
335                ),
336                ChainedSequenceContext::Format4(t) => {
337                    self.finish(t.coverage(), context::ChainContext1::new_wide(&t))
338                }
339                ChainedSequenceContext::Format5(t) => self.finish(
340                    t.coverage(),
341                    Some(context::ChainContext2::new_wide(&t, caches, budget)?),
342                ),
343            },
344            (true, 7) | (false, 9) => {
345                let ext = ExtensionSubstFormat1::<()>::read(data)?;
346                let ext_type = ext.extension_lookup_type();
347                if is_extension(self.is_subst, ext_type) {
348                    return Err(BuildError::Invalid);
349                }
350                let offset = self
351                    .offset
352                    .checked_add(ext.extension_offset().to_u32() as usize)
353                    .ok_or(BuildError::Invalid)?;
354                Source { offset, ..self }.build(ext_type)
355            }
356            _ => Err(BuildError::Invalid),
357        }
358    }
359
360    /// Completes a class pair subtable, as kerning if it holds only that.
361    fn class_pairs(
362        self,
363        coverage: Result<CoverageTable<'a>, ReadError>,
364        pairs: gpos::ClassPairs<'a>,
365    ) -> Result<BuiltSubtable<'a>, BuildError> {
366        let (caches, budget) = (self.with_caches, self.budget);
367        match gpos::PairKern2::new(&pairs, caches, budget)? {
368            Some(kern) => self.finish(coverage, Some(kern)),
369            None => self.finish(coverage, gpos::PairPos2::new(&pairs, caches, budget)?),
370        }
371    }
372
373    /// Completes a subtable from its first glyph's coverage and its data.
374    fn finish<T: IntoKind<'a> + SubtableDigests<'a>>(
375        self,
376        coverage: Result<CoverageTable<'a>, ReadError>,
377        data: Option<T>,
378    ) -> Result<BuiltSubtable<'a>, BuildError> {
379        let coverage = Coverage::required(coverage).ok_or(BuildError::Invalid)?;
380        let data = data.ok_or(BuildError::Invalid)?;
381        let digest_second = data.digest_second(self.budget)?;
382        let cache_cost = data.cache_cost();
383        let coverage_cache = if self.with_caches
384            && T::CACHES_COVERAGE
385            && coverage.cost() >= MIN_CACHED_COVERAGE_COST
386        {
387            self.budget.alloc::<MappingCache>(1)?;
388            Some(Box::new(MappingCache::new()))
389        } else {
390            None
391        };
392        Ok(BuiltSubtable {
393            subtable: CachedSubtable {
394                kind: data.into_kind(self.budget)?,
395                digest: coverage.digest(self.budget)?,
396                coverage,
397                coverage_cache,
398                fns: T::FNS,
399                apply_sharing: T::FNS.apply_sharing,
400            },
401            shares_second_glyph: T::FNS.shares_second_glyph,
402            digest_second,
403            cache_cost,
404        })
405    }
406}
407
408#[cfg(test)]
409mod tests {
410    use super::*;
411
412    fn repeated_single_subst(count: u16) -> Vec<u8> {
413        let offset = 6 + count * 2;
414        let mut words = alloc::vec![1, 0, count];
415        words.resize(3 + usize::from(count), offset);
416        // SingleSubst format 1, followed by coverage of glyph 42.
417        words.extend_from_slice(&[1, 6, 1, 1, 1, 42]);
418        words.into_iter().flat_map(u16::to_be_bytes).collect()
419    }
420
421    #[test]
422    fn exhaustion_discards_previously_built_subtables() {
423        let data = repeated_single_subst(2);
424        // Header, two offsets, and the first subtable and coverage fit.
425        // Reading the second subtable must abort the whole lookup.
426        let budget = Budget::new(5, 1 << 20);
427        assert!(matches!(
428            build_lookup_at(FontData::new(&data), 0, true, &budget),
429            Err(BuildError::Exhausted)
430        ));
431        let budget = Budget::new(7, 1 << 20);
432        let lookup = build_lookup_at(FontData::new(&data), 0, true, &budget).unwrap();
433        assert_eq!(lookup.subtables.len(), 2);
434    }
435
436    #[test]
437    fn subtable_storage_is_reserved_before_building() {
438        let data = repeated_single_subst(2);
439        let budget = Budget::new(100, size_of::<CachedSubtable>() * 2 - 1);
440        assert!(matches!(
441            build_lookup_at(FontData::new(&data), 0, true, &budget),
442            Err(BuildError::Exhausted)
443        ));
444        assert_eq!(budget.remaining().0, 97);
445    }
446
447    #[test]
448    fn thousands_of_subtables_are_allowed() {
449        // Gulzar has a lookup with 3625 subtables. Counts alone must not
450        // reject it; this synthetic lookup exercises an even larger count.
451        let data = repeated_single_subst(3800);
452        let budget = Budget::new(1 << 20, 16 << 20);
453        let lookup = build_lookup_at(FontData::new(&data), 0, true, &budget).unwrap();
454        assert_eq!(lookup.subtables.len(), 3800);
455    }
456
457    #[test]
458    fn malformed_subtables_do_not_abort_a_lookup() {
459        let mut data = repeated_single_subst(2);
460        // Only the first offset points outside the data.
461        data[6..8].copy_from_slice(&u16::MAX.to_be_bytes());
462        let budget = Budget::for_table_bytes(data.len());
463        let lookup = build_lookup_at(FontData::new(&data), 0, true, &budget).unwrap();
464        assert_eq!(lookup.subtables.len(), 1);
465    }
466
467    fn lookup_with_recursive_extension(lookup_type: u16) -> [u8; 16] {
468        let mut data = [0; 16];
469        // Lookup table.
470        data[0..2].copy_from_slice(&lookup_type.to_be_bytes());
471        data[4..6].copy_from_slice(&1u16.to_be_bytes());
472        data[6..8].copy_from_slice(&8u16.to_be_bytes());
473        // ExtensionSubstFormat1/ExtensionPosFormat1 subtable.
474        data[8..10].copy_from_slice(&1u16.to_be_bytes());
475        data[10..12].copy_from_slice(&lookup_type.to_be_bytes());
476        data
477    }
478
479    #[test]
480    fn gsub_extension_lookup_cannot_target_extension_lookup() {
481        let data = lookup_with_recursive_extension(7);
482        let lookup = build_lookup_at(
483            FontData::new(&data),
484            0,
485            true,
486            &Budget::for_table_bytes(data.len()),
487        )
488        .unwrap();
489        assert!(lookup.subtables.is_empty());
490    }
491
492    #[test]
493    fn gpos_extension_lookup_cannot_target_extension_lookup() {
494        let data = lookup_with_recursive_extension(9);
495        let lookup = build_lookup_at(
496            FontData::new(&data),
497            0,
498            false,
499            &Budget::for_table_bytes(data.len()),
500        )
501        .unwrap();
502        assert!(lookup.subtables.is_empty());
503    }
504}