Skip to main content

harfrust/ot/lookup/
mod.rs

1//! The lookups of GSUB and GPOS, parsed once and kept with the font tables.
2//!
3//! When a lookup is first used, each of its subtables is read into a
4//! [`CachedSubtableKind`] that holds the parsed table together with
5//! everything derived from it: coverage and class tables, digests and glyph
6//! lookup caches. Applying a subtable is then one indirect call through
7//! [`CachedSubtable`] that checks the kind it expects and runs.
8//!
9//! The parsed tables borrow the font data, so a lookup is kept in a
10//! [`yoke::Yoke`] with a reference to the font's shared tables; see
11//! [`CachedLookupRef`].
12
13mod build;
14mod context;
15mod coverage;
16mod gpos;
17mod gsub;
18
19#[cfg(test)]
20mod extended_tests;
21
22use super::apply::{ApplyContext, MappingCache, WouldApplyContext};
23use crate::budget::{Budget, Exhausted};
24use crate::once::Once;
25use crate::set_digest::SetDigest;
26use crate::GlyphInfo;
27use alloc::{boxed::Box, sync::Arc, vec::Vec};
28use core::ops::Range;
29pub(crate) use coverage::{ClassDef, Coverage};
30use gpos::SecondGlyph;
31use read_fonts::model::Tables;
32use read_fonts::types::GlyphId;
33use read_fonts::{FontData, FontRead};
34use yoke::erased::ErasedArcCart;
35use yoke::{Yoke, Yokeable};
36
37/// The lookups of GSUB or GPOS, each parsed on first use.
38pub(crate) struct LookupCache {
39    lookups: Vec<Once<Option<Box<CachedLookupRef>>>>,
40    /// The font's shared tables, which lookups are cached against.
41    tables: Option<Arc<Tables>>,
42    is_subst: bool,
43    budget: Option<Arc<Budget>>,
44}
45
46impl LookupCache {
47    pub const EMPTY: Self = Self {
48        lookups: Vec::new(),
49        tables: None,
50        is_subst: false,
51        budget: None,
52    };
53
54    pub fn new(tables: Option<Arc<Tables>>, is_subst: bool, budget: Arc<Budget>) -> Self {
55        let count = tables
56            .as_deref()
57            .map_or(0, |tables| build::lookup_count(tables, is_subst));
58        let count = usize::from(count);
59        if budget.work(count).is_err()
60            || budget
61                .alloc::<Once<Option<Box<CachedLookupRef>>>>(count)
62                .is_err()
63        {
64            return Self::EMPTY;
65        }
66        let mut lookups = Vec::with_capacity(count);
67        lookups.resize_with(count, Once::new);
68        Self {
69            lookups,
70            tables,
71            is_subst,
72            budget: Some(budget),
73        }
74    }
75
76    pub fn get(&self, index: u16) -> Option<&CachedLookup<'_>> {
77        let cell = self.lookups.get(usize::from(index))?;
78        // Checked before `get_or_init`, whose initializer would otherwise
79        // weigh down the path taken every time.
80        let lookup = match cell.get() {
81            Some(lookup) => lookup,
82            None => cell.get_or_init(|| {
83                let budget = self.budget.as_deref()?;
84                budget.alloc::<CachedLookupRef>(1).ok()?;
85                cache_lookup(self.tables.clone()?, self.is_subst, index, budget).map(Box::new)
86            }),
87        };
88        lookup.as_deref().map(Yoke::get)
89    }
90}
91
92/// A cached lookup kept with the data it borrows: the font's tables, or
93/// the bytes of a lookup made up for a font that lacks one.
94pub(crate) type CachedLookupRef = Yoke<CachedLookup<'static>, ErasedArcCart>;
95
96/// Parses lookup `index` of GSUB, or GPOS if `is_subst` is false.
97pub(crate) fn cache_lookup(
98    tables: Arc<Tables>,
99    is_subst: bool,
100    index: u16,
101    budget: &Budget,
102) -> Option<CachedLookupRef> {
103    Yoke::try_attach_to_cart(tables, |tables| {
104        build::build_lookup(tables, is_subst, index, budget)
105    })
106    .ok()
107    .map(Yoke::erase_arc_cart)
108}
109
110/// Parses a substitution lookup serialized on its own, as the Arabic
111/// fallback makes them.
112pub(crate) fn cache_synthesized_subst(data: Vec<u8>) -> Option<CachedLookupRef> {
113    Yoke::try_attach_to_cart(Arc::new(data), |data: &Vec<u8>| {
114        build::build_lookup_at(
115            FontData::new(data),
116            0,
117            true,
118            &Budget::for_table_bytes(data.len()),
119        )
120    })
121    .ok()
122    .map(Yoke::erase_arc_cart)
123}
124
125/// A lookup with its subtables parsed.
126#[derive(Yokeable)]
127pub struct CachedLookup<'a> {
128    pub props: u32,
129    pub is_subst: bool,
130    pub is_reversed: bool,
131    pub digest: SetDigest,
132    pub digest_second: SetDigest,
133    /// The subtable that uses the buffer's glyph-info cache, if any.
134    hot_subtable: Option<usize>,
135    /// Whether the hot subtable keeps glyph classes in the glyph-info cache.
136    uses_class_cache: bool,
137    /// Applies the subtables in turn, chosen for their number and kinds.
138    walk: WalkFn,
139    subtables: Vec<CachedSubtable<'a>>,
140}
141
142/// Applies the subtables of a lookup until one applies.
143type WalkFn = fn(&CachedLookup, &mut ApplyContext, bool) -> Option<()>;
144
145impl CachedLookup<'_> {
146    pub fn props(&self) -> u32 {
147        self.props
148    }
149
150    pub fn is_reverse(&self) -> bool {
151        self.is_reversed
152    }
153
154    pub fn digest(&self) -> &SetDigest {
155        &self.digest
156    }
157
158    pub fn digest_second(&self) -> &SetDigest {
159        &self.digest_second
160    }
161
162    #[inline]
163    pub(crate) fn apply(&self, ctx: &mut ApplyContext, use_hot_subtable_cache: bool) -> Option<()> {
164        (self.walk)(self, ctx, use_hot_subtable_cache)
165    }
166
167    /// Prepares the glyph-info class cache for the hot subtable, returning
168    /// true if it is in use.
169    pub(crate) fn cache_enter(&self, ctx: &mut ApplyContext) -> bool {
170        if !self.uses_class_cache || !ctx.buffer.try_allocate_var(GlyphInfo::SYLLABLE_VAR) {
171            return false;
172        }
173        for info in &mut ctx.buffer.info {
174            info.set_syllable(255);
175        }
176        ctx.new_syllables = Some(255);
177        true
178    }
179
180    pub(crate) fn cache_leave(&self, ctx: &mut ApplyContext) {
181        if self.uses_class_cache {
182            ctx.new_syllables = None;
183            ctx.buffer.deallocate_var(GlyphInfo::SYLLABLE_VAR);
184        }
185    }
186
187    pub fn would_apply(&self, ctx: &WouldApplyContext) -> Option<bool> {
188        let glyph = ctx.glyphs[0].into();
189        if !self.digest.may_have(glyph) {
190            return Some(false);
191        }
192        for subtable in &self.subtables {
193            if subtable.digest.may_have(glyph)
194                && subtable.kind.would_apply(ctx, &subtable.coverage) == Some(true)
195            {
196                return Some(true);
197            }
198        }
199        None
200    }
201}
202
203/// Applies a lookup's only subtable. Its digest equals the lookup's,
204/// which the caller has already tested.
205fn walk_single(
206    lookup: &CachedLookup,
207    ctx: &mut ApplyContext,
208    use_hot_subtable_cache: bool,
209) -> Option<()> {
210    let glyph = ctx.buffer.cur(0)?.glyph_id;
211    let subtable = lookup.subtables.first()?;
212    let index = subtable.coverage_index(glyph)?;
213    let is_cached = use_hot_subtable_cache && lookup.hot_subtable == Some(0);
214    subtable.fns.apply[is_cached as usize](subtable, ctx, index)
215}
216
217/// Applies subtables in turn.
218fn walk_each(
219    lookup: &CachedLookup,
220    ctx: &mut ApplyContext,
221    use_hot_subtable_cache: bool,
222) -> Option<()> {
223    let glyph = ctx.buffer.cur(0)?.glyph_id;
224    for (position, subtable) in lookup.subtables.iter().enumerate() {
225        if !subtable.digest.may_have(glyph) {
226            continue;
227        }
228        let Some(index) = subtable.coverage_index(glyph) else {
229            continue;
230        };
231        let is_cached = use_hot_subtable_cache && lookup.hot_subtable == Some(position);
232        if subtable.fns.apply[is_cached as usize](subtable, ctx, index).is_some() {
233            return Some(());
234        }
235    }
236    None
237}
238
239/// Applies subtables that adjust pairs, searching for the second glyph
240/// of the pair at most once for all of them.
241fn walk_sharing_second_glyph(lookup: &CachedLookup, ctx: &mut ApplyContext, _: bool) -> Option<()> {
242    let glyph = ctx.buffer.cur(0)?.glyph_id;
243    let mut second = SecondGlyph::Unknown;
244    for subtable in &lookup.subtables {
245        if !subtable.digest.may_have(glyph) {
246            continue;
247        }
248        let Some(index) = subtable.coverage_index(glyph) else {
249            continue;
250        };
251        if (subtable.apply_sharing)(subtable, ctx, index, &mut second).is_some() {
252            return Some(());
253        }
254    }
255    None
256}
257
258/// A parsed subtable and the functions that apply it.
259pub(crate) struct CachedSubtable<'a> {
260    kind: CachedSubtableKind<'a>,
261    /// The glyphs the subtable may apply to.
262    digest: SetDigest,
263    /// The coverage of the glyph that a match starts at.
264    coverage: Coverage<'a>,
265    coverage_cache: Option<Box<MappingCache>>,
266    /// How `kind` applies.
267    fns: &'static KindFns,
268    /// `fns.apply_sharing`, kept here for the pair walk.
269    apply_sharing: ApplySharingFn,
270}
271
272impl CachedSubtable<'_> {
273    /// The coverage index of the glyph a match would start at.
274    #[inline(always)]
275    fn coverage_index(&self, glyph: u32) -> Option<u32> {
276        let Some(cache) = &self.coverage_cache else {
277            return self.coverage.get(glyph);
278        };
279        match cache.get(glyph) {
280            Some(MappingCache::MAX_VALUE) => None,
281            Some(index) => Some(index),
282            None => self.coverage_index_uncached(glyph, cache),
283        }
284    }
285
286    /// Looks up a glyph the cache doesn't hold, and remembers it. Kept out
287    /// of line so the walks inline only the cache hit.
288    #[inline(never)]
289    fn coverage_index_uncached(&self, glyph: u32, cache: &MappingCache) -> Option<u32> {
290        coverage_index_cached(|gid| self.coverage.get(gid), glyph.into(), cache)
291    }
292}
293
294/// Applies a subtable of one kind at the given coverage index, returning
295/// `None` for any other kind.
296type ApplyFn = fn(&CachedSubtable, &mut ApplyContext, u32) -> Option<()>;
297
298/// Applies a subtable of one kind, sharing the search for a pair's second
299/// glyph with the other subtables of its lookup.
300type ApplySharingFn = fn(&CachedSubtable, &mut ApplyContext, u32, &mut SecondGlyph) -> Option<()>;
301
302/// How a kind of subtable applies.
303struct KindFns {
304    /// Applies without and with the glyph-info class cache.
305    apply: [ApplyFn; 2],
306    apply_sharing: ApplySharingFn,
307    /// Whether the kind adjusts pairs and uses the shared second glyph.
308    shares_second_glyph: bool,
309}
310
311/// The derived data of one kind of subtable.
312trait IntoKind<'a>: Sized {
313    const FNS: &'static KindFns;
314
315    fn into_kind(self, budget: &Budget) -> Result<CachedSubtableKind<'a>, Exhausted>;
316}
317
318/// The functions of a kind that applies plainly, adjusts pairs, or keeps
319/// classes in the glyph-info cache.
320macro_rules! kind_fns {
321    ($kind:ident) => {{
322        const APPLY: ApplyFn = |subtable, ctx, index| match &subtable.kind {
323            CachedSubtableKind::$kind(data) => data.apply(ctx, index),
324            _ => None,
325        };
326        &KindFns {
327            apply: [APPLY, APPLY],
328            apply_sharing: never_shares,
329            shares_second_glyph: false,
330        }
331    }};
332    ($kind:ident adjusts_pairs) => {{
333        const APPLY_SHARING: ApplySharingFn = |subtable, ctx, index, second| match &subtable.kind {
334            CachedSubtableKind::$kind(data) => data.apply(ctx, index, second),
335            _ => None,
336        };
337        const APPLY: ApplyFn =
338            |subtable, ctx, index| APPLY_SHARING(subtable, ctx, index, &mut SecondGlyph::Unknown);
339        &KindFns {
340            apply: [APPLY, APPLY],
341            apply_sharing: APPLY_SHARING,
342            shares_second_glyph: true,
343        }
344    }};
345    ($kind:ident uses_class_cache) => {
346        &KindFns {
347            apply: [
348                |subtable, ctx, index| match &subtable.kind {
349                    CachedSubtableKind::$kind(data) => data.apply(ctx, index, false),
350                    _ => None,
351                },
352                |subtable, ctx, index| match &subtable.kind {
353                    CachedSubtableKind::$kind(data) => data.apply(ctx, index, true),
354                    _ => None,
355                },
356            ],
357            apply_sharing: never_shares,
358            shares_second_glyph: false,
359        }
360    };
361}
362
363/// The `apply_sharing` of kinds that don't adjust pairs, which no walk calls.
364fn never_shares(
365    _: &CachedSubtable,
366    _: &mut ApplyContext,
367    _: u32,
368    _: &mut SecondGlyph,
369) -> Option<()> {
370    None
371}
372
373/// The payload of a kind, boxed if the kind is marked so.
374macro_rules! kind_payload {
375    ($data:ty) => { $data };
376    ($data:ty, boxed) => { Box<$data> };
377}
378
379macro_rules! wrap_payload {
380    ($value:expr, $budget:expr) => {{
381        let _ = $budget;
382        $value
383    }};
384    ($value:expr, $budget:expr, boxed) => {{
385        $budget.alloc::<Self>(1)?;
386        Box::new($value)
387    }};
388}
389
390/// Declares the subtable kinds, the data each holds, and how it applies.
391///
392/// Kinds whose data is much larger than the rest are boxed, so that they
393/// don't set the size of every subtable.
394macro_rules! subtable_kinds {
395    ($($kind:ident($data:ty) $($how:ident)? $(, $boxed:ident)?;)*) => {
396        /// A parsed subtable with the data derived from it.
397        pub(crate) enum CachedSubtableKind<'a> {
398            $($kind(kind_payload!($data $(, $boxed)?)),)*
399        }
400
401        $(
402            impl<'a> IntoKind<'a> for $data {
403                const FNS: &'static KindFns = kind_fns!($kind $($how)?);
404
405                fn into_kind(self, budget: &Budget) -> Result<CachedSubtableKind<'a>, Exhausted> {
406                    Ok(CachedSubtableKind::$kind(wrap_payload!(self, budget $(, $boxed)?)))
407                }
408            }
409        )*
410    };
411}
412
413subtable_kinds! {
414    SingleSubst1(gsub::SingleSubst1);
415    SingleSubst2(gsub::SingleSubst2<'a>);
416    MultipleSubst1(gsub::MultipleSubst1<'a>);
417    AlternateSubst1(gsub::AlternateSubst1<'a>);
418    LigatureSubst1(gsub::LigatureSubst1<'a>);
419    ReverseChainSubst1(gsub::ReverseChainSubst1<'a>);
420    SinglePos1(gpos::SinglePos1<'a>);
421    SinglePos2(gpos::SinglePos2<'a>);
422    PairPos1(gpos::PairPos1<'a>) adjusts_pairs;
423    PairPos2(gpos::PairPos2<'a>) adjusts_pairs, boxed;
424    PairKern1(gpos::PairKern1<'a>) adjusts_pairs;
425    PairKern2(gpos::PairKern2<'a>) adjusts_pairs, boxed;
426    CursivePos1(gpos::CursivePos1<'a>);
427    MarkBasePos1(gpos::MarkBasePos1<'a>), boxed;
428    MarkLigPos1(gpos::MarkLigPos1<'a>), boxed;
429    MarkMarkPos1(gpos::MarkMarkPos1<'a>), boxed;
430    ChainContext1(context::ChainContext1<'a>);
431    ChainContext2(context::ChainContext2<'a>) uses_class_cache, boxed;
432    ChainContext3(context::ChainContext3<'a>);
433}
434
435impl CachedSubtableKind<'_> {
436    /// Returns whether a substitution subtable would apply, or `None` for a
437    /// positioning subtable.
438    fn would_apply(&self, ctx: &WouldApplyContext, coverage: &Coverage) -> Option<bool> {
439        Some(match self {
440            // These substitute a single glyph.
441            Self::SingleSubst1(_)
442            | Self::SingleSubst2(_)
443            | Self::MultipleSubst1(_)
444            | Self::AlternateSubst1(_)
445            | Self::ReverseChainSubst1(_) => {
446                ctx.glyphs.len() == 1 && coverage.covers(ctx.glyphs[0])
447            }
448            Self::LigatureSubst1(t) => t.would_apply(ctx, coverage),
449            Self::ChainContext1(t) => t.would_apply(ctx, coverage),
450            Self::ChainContext2(t) => t.would_apply(ctx, coverage),
451            Self::ChainContext3(t) => t.would_apply(ctx, coverage),
452            _ => return None,
453        })
454    }
455}
456
457/// What a lookup needs to know about one of its subtables.
458trait SubtableDigests<'a> {
459    /// Whether looking up the first glyph's coverage gains from a cache.
460    const CACHES_COVERAGE: bool = false;
461
462    /// The glyphs that may follow the first one in a match.
463    fn digest_second(&self, _budget: &Budget) -> Result<SetDigest, Exhausted> {
464        Ok(SetDigest::full())
465    }
466
467    /// How much the subtable gains from the glyph-info class cache.
468    fn cache_cost(&self) -> u32 {
469        0
470    }
471}
472
473/// Big-endian unsigned integers of one width, two or three bytes, read from
474/// an array in place. Glyph IDs, offsets and rule values of the original and
475/// extended formats share code through it.
476#[derive(Clone, Copy, Default)]
477pub(crate) struct Uints<'a> {
478    bytes: &'a [u8],
479    len: u32,
480    width: u8,
481}
482
483impl<'a> Uints<'a> {
484    /// The integers of `width` bytes in `range` of `data`, or `None` if the
485    /// range is out of bounds.
486    pub fn new(data: FontData<'a>, range: Range<usize>, width: usize) -> Option<Self> {
487        let bytes = data.as_bytes().get(range)?;
488        let len = bytes.len() / width;
489        Some(Self {
490            bytes: &bytes[..len * width],
491            len: len as u32,
492            width: width as u8,
493        })
494    }
495
496    /// `count` integers of `width` bytes at `start` of `data`.
497    #[inline(always)]
498    pub fn at(data: FontData<'a>, start: usize, count: usize, width: usize) -> Option<Self> {
499        let end = start.checked_add(count.checked_mul(width)?)?;
500        let bytes = data.as_bytes().get(start..end)?;
501        Some(Self {
502            bytes,
503            len: count as u32,
504            width: width as u8,
505        })
506    }
507
508    #[inline(always)]
509    pub fn len(&self) -> usize {
510        self.len as usize
511    }
512
513    #[inline(always)]
514    pub fn is_empty(&self) -> bool {
515        self.len == 0
516    }
517
518    #[inline(always)]
519    pub fn get(&self, index: usize) -> Option<u32> {
520        // Branching between two fixed widths reads faster than reading any
521        // width. Indices are at most 24 bits, so the products can't
522        // overflow.
523        if self.width == 3 {
524            read_be::<3>(self.bytes, index * 3)
525        } else {
526            read_be::<2>(self.bytes, index * 2)
527        }
528    }
529
530    #[inline(always)]
531    pub fn first(&self) -> Option<u32> {
532        self.get(0)
533    }
534
535    pub fn iter(&self) -> impl Iterator<Item = u32> + '_ {
536        (0..self.len()).filter_map(|index| self.get(index))
537    }
538}
539
540/// The unsigned integer of `width` bytes at `pos`, which the caller has
541/// checked is in bounds.
542#[inline(always)]
543pub(crate) fn read_uint(bytes: &[u8], pos: usize, width: usize) -> u32 {
544    be_uint(&bytes[pos..pos + width])
545}
546
547/// The big-endian unsigned integer of `W` bytes at `pos`, or `None` if it
548/// is out of bounds.
549#[inline(always)]
550pub(crate) fn read_be<const W: usize>(bytes: &[u8], pos: usize) -> Option<u32> {
551    let b = bytes.get(pos..pos.checked_add(W)?)?;
552    Some(match W {
553        2 => u32::from(u16::from_be_bytes([b[0], b[1]])),
554        3 => u32::from_be_bytes([0, b[0], b[1], b[2]]),
555        _ => u32::from_be_bytes([b[0], b[1], b[2], b[3]]),
556    })
557}
558
559/// The big-endian unsigned integer of two to four bytes.
560#[inline(always)]
561pub(crate) fn be_uint(bytes: &[u8]) -> u32 {
562    match *bytes {
563        [a, b] => u32::from(u16::from_be_bytes([a, b])),
564        [a, b, c] => u32::from_be_bytes([0, a, b, c]),
565        [a, b, c, d] => u32::from_be_bytes([a, b, c, d]),
566        _ => 0,
567    }
568}
569
570/// Unsigned integers of `W` bytes, read in place: glyph IDs, classes or
571/// offsets whose width a hot path fixes at compile time.
572#[derive(Clone, Copy)]
573pub(crate) struct Values<'a, const W: usize> {
574    values: &'a [[u8; W]],
575}
576
577impl<const W: usize> Default for Values<'_, W> {
578    fn default() -> Self {
579        Self { values: &[] }
580    }
581}
582
583impl<'a, const W: usize> Values<'a, W> {
584    #[inline(always)]
585    pub fn at(data: FontData<'a>, start: usize, count: usize) -> Option<Self> {
586        let bytes = data.as_bytes().get(start..start + count * W)?;
587        Some(Self {
588            values: bytemuck::cast_slice(bytes),
589        })
590    }
591
592    #[inline(always)]
593    pub fn len(&self) -> usize {
594        self.values.len()
595    }
596
597    #[inline(always)]
598    pub fn is_empty(&self) -> bool {
599        self.values.is_empty()
600    }
601
602    #[inline(always)]
603    pub fn get(&self, index: usize) -> Option<u32> {
604        self.values.get(index).map(be_value)
605    }
606
607    pub fn first(&self) -> Option<u32> {
608        self.get(0)
609    }
610
611    pub fn iter(&self) -> impl Iterator<Item = u32> + '_ {
612        self.values.iter().map(be_value)
613    }
614}
615
616/// The big-endian value of `W` bytes, two or three.
617#[inline(always)]
618fn be_value<const W: usize>(value: &[u8; W]) -> u32 {
619    if W == 2 {
620        u32::from(u16::from_be_bytes([value[0], value[1]]))
621    } else {
622        u32::from_be_bytes([0, value[0], value[1], value[2]])
623    }
624}
625
626/// An array of offsets to child tables, with the data they are relative to.
627#[derive(Clone, Copy, Default)]
628struct Offsets<'a> {
629    data: FontData<'a>,
630    offsets: Uints<'a>,
631}
632
633impl<'a> Offsets<'a> {
634    /// The offsets of `width` bytes in `range` of `data`, relative to it.
635    fn new(data: FontData<'a>, range: Range<usize>, width: usize) -> Self {
636        Self {
637            data,
638            offsets: Uints::new(data, range, width).unwrap_or_default(),
639        }
640    }
641
642    /// The offsets of `width` bytes in `range` of `data` after the first.
643    fn after_first(data: FontData<'a>, range: Range<usize>, width: usize) -> Self {
644        let start = range.start.saturating_add(width).min(range.end);
645        Self::new(data, start..range.end, width)
646    }
647
648    fn is_null(&self, index: usize) -> bool {
649        self.offsets.get(index) == Some(0)
650    }
651
652    fn len(&self) -> usize {
653        self.offsets.len()
654    }
655
656    /// The data of the child table at `index`, or `None` if its offset is
657    /// null or out of bounds.
658    #[inline(always)]
659    fn data(&self, index: usize) -> Option<FontData<'a>> {
660        let offset = self.offsets.get(index)? as usize;
661        if offset == 0 {
662            return None;
663        }
664        self.data.split_off(offset)
665    }
666
667    /// Reads the child table at `index`, or `None` if its offset is null
668    /// or it can't be read.
669    fn get<T: FontRead<'a, Args = ()>>(&self, index: usize) -> Option<T> {
670        T::read(self.data(index)?).ok()
671    }
672}
673
674/// Returns the coverage index of `gid`, remembering it in `cache`.
675#[inline(always)]
676fn coverage_index_cached(
677    coverage: impl Fn(GlyphId) -> Option<u32>,
678    gid: GlyphId,
679    cache: &MappingCache,
680) -> Option<u32> {
681    if let Some(index) = cache.get(gid.into()) {
682        if index == MappingCache::MAX_VALUE {
683            None
684        } else {
685            Some(index)
686        }
687    } else {
688        let index = coverage(gid);
689        if let Some(index) = index {
690            if index < MappingCache::MAX_VALUE {
691                cache.set(gid.into(), index);
692            }
693            Some(index)
694        } else {
695            cache.set(gid.into(), MappingCache::MAX_VALUE);
696            None
697        }
698    }
699}
700
701/// Returns the class of `gid`, remembering it in `cache`.
702#[inline(always)]
703fn glyph_class_cached(class_def: &ClassDef, gid: GlyphId, cache: &MappingCache) -> u32 {
704    match cache.get(gid.into()) {
705        Some(class) => class,
706        None => glyph_class_uncached(class_def, gid, cache),
707    }
708}
709
710/// Looks up a class the cache doesn't hold, and remembers it. Kept out of
711/// line so callers inline only the cache hit.
712#[inline(never)]
713fn glyph_class_uncached(class_def: &ClassDef, gid: GlyphId, cache: &MappingCache) -> u32 {
714    let class = class_def.get(gid);
715    cache.set(gid.into(), class);
716    class
717}
718
719#[cfg(all(test, feature = "std"))]
720mod tests {
721    use super::*;
722    use crate::ot::OtCache;
723
724    #[test]
725    fn exhausted_lookups_are_memoized() {
726        let tables = Arc::new(
727            Tables::new(
728                include_bytes!("../../../tests/fonts/rb_custom/PT_Sans-Caption-Web-Regular.ttf")
729                    .to_vec(),
730                0,
731            )
732            .unwrap(),
733        );
734        let budget = Arc::new(Budget::new(1 << 20, 1 << 20));
735        let cache = LookupCache::new(Some(tables), true, budget.clone());
736        assert!(!cache.lookups.is_empty());
737        budget.work(budget.remaining().0).unwrap();
738        assert!(cache.get(0).is_none());
739        assert!(matches!(cache.lookups[0].get(), Some(None)));
740        let remaining = budget.remaining();
741        assert!(cache.get(0).is_none());
742        assert_eq!(budget.remaining(), remaining);
743    }
744
745    #[test]
746    fn overlapping_pair_sets_exhaust_the_shared_budget() {
747        let data = include_bytes!("../../../../fuzz/corpus/fuzz_shape/clusterfuzz-5665051575648256-overlapping-pair-sets.otf");
748        let tables = Arc::new(Tables::new(data.to_vec(), 0).unwrap());
749        let cache = OtCache::new(Some(tables));
750        // Many lookup indices point at the same expensive lookup.
751        for index in [53, 87, 118] {
752            assert!(cache.gpos.get(index).is_none());
753            assert!(matches!(
754                cache.gpos.lookups[index as usize].get(),
755                Some(None)
756            ));
757        }
758        assert!(Arc::ptr_eq(
759            cache.gsub.budget.as_ref().unwrap(),
760            cache.gpos.budget.as_ref().unwrap()
761        ));
762    }
763
764    /// Allows checking every lookup, including ones sample text won't select.
765    #[test]
766    #[ignore = "set HARFRUST_BUDGET_FONTS to font files or directories for calibration"]
767    fn real_font_budget_headroom() {
768        fn collect(path: &std::path::Path, files: &mut Vec<std::path::PathBuf>) {
769            if path.is_dir() {
770                for entry in std::fs::read_dir(path).unwrap() {
771                    collect(&entry.unwrap().path(), files);
772                }
773            } else if path
774                .extension()
775                .is_some_and(|ext| ext == "ttf" || ext == "otf")
776            {
777                files.push(path.to_owned());
778            }
779        }
780        let paths = std::env::var_os("HARFRUST_BUDGET_FONTS").expect("set HARFRUST_BUDGET_FONTS");
781        let mut files = Vec::new();
782        for path in std::env::split_paths(&paths) {
783            collect(&path, &mut files);
784        }
785        files.sort();
786        assert!(
787            !files.is_empty(),
788            "no font files found in HARFRUST_BUDGET_FONTS"
789        );
790        for path in files {
791            let tables = Arc::new(Tables::new(std::fs::read(&path).unwrap(), 0).unwrap());
792            let bytes = [tables.gsub_data(), tables.gpos_data(), tables.gdef_data()]
793                .into_iter()
794                .flatten()
795                .map(<[u8]>::len)
796                .sum::<usize>();
797            let cache = OtCache::new(Some(tables));
798            for lookups in [&cache.gsub, &cache.gpos] {
799                for index in 0..lookups.lookups.len() {
800                    assert!(
801                        lookups.get(index as u16).is_some(),
802                        "lookup {index}: {}",
803                        path.display()
804                    );
805                }
806            }
807            let budget = cache.gsub.budget.as_ref().unwrap();
808            let (work, memory) = budget.remaining();
809            let (work_limit, memory_limit) = Budget::for_table_bytes(bytes).remaining();
810            std::println!(
811                "{}: work {}/{work_limit}, bytes {}/{memory_limit}",
812                path.display(),
813                work_limit - work,
814                memory_limit - memory
815            );
816        }
817    }
818}