Skip to main content

harfrust/ot/lookup/
gpos.rs

1//! Positioning subtables.
2//!
3//! Each kind serves the original format and its extended counterpart, which
4//! differ only in the widths of glyph IDs, counts and offsets.
5
6use super::coverage::{ClassDef, Coverage};
7use super::{glyph_class_cached, read_uint, Offsets, SubtableDigests, Uints};
8use crate::budget::{Budget, Exhausted};
9use crate::buffer::{Buffer, GlyphPosition, HB_BUFFER_SCRATCH_FLAG_HAS_GPOS_ATTACHMENT};
10use crate::hint::{Likely, LikelyOk};
11use crate::ot::apply::{ApplyContext, MappingCache, MatchResult, SkippingIterator};
12use crate::ot::gpos::attach_type;
13use crate::ot::lookup_flags;
14use crate::set_digest::SetDigest;
15use crate::Direction;
16use alloc::{boxed::Box, vec::Vec};
17use core::ops::Range;
18use read_fonts::tables::gpos::{
19    AnchorTable, ClassValueRecords, CursivePosFormat1, CursivePosFormat2, MarkBasePosFormat1,
20    MarkBasePosFormat2, MarkLigPosFormat1, MarkLigPosFormat2, MarkMarkPosFormat1,
21    MarkMarkPosFormat2, PairPosFormat1, PairPosFormat2, PairPosFormat3, PairPosFormat4,
22    SinglePosFormat1, SinglePosFormat2, SinglePosFormat3, SinglePosFormat4, ValueFormat,
23    ValueRecord,
24};
25use read_fonts::tables::variations::DeltaSetIndex;
26use read_fonts::types::{BigEndian, GlyphId};
27use read_fonts::{FontData, FontRead};
28
29/// The width of glyph IDs, counts and child offsets in the original formats.
30const NARROW: usize = 2;
31/// Their width in the extended formats.
32const WIDE: usize = 3;
33
34/// Adds `record` to the position of glyph `idx`, returning whether it
35/// changed anything. A truncated record changes nothing.
36#[inline]
37fn apply_value(ctx: &mut ApplyContext, idx: usize, record: &ValueRecord) -> bool {
38    let Some(bytes) = record.bytes() else {
39        return false;
40    };
41    // Most kerning adjusts only the advance.
42    if record.format() == ValueFormat::X_ADVANCE {
43        let &[hi, lo] = bytes else {
44            return false;
45        };
46        let value = i16::from_be_bytes([hi, lo]);
47        if !ctx.buffer.direction.is_horizontal() {
48            return false;
49        }
50        let x_advance = ctx.scale.scale_x(i32::from(value));
51        let Some(pos) = ctx.buffer.pos.get_mut(idx).likely() else {
52            return false;
53        };
54        pos.x_advance = pos.x_advance.saturating_add(x_advance);
55        return value != 0;
56    }
57    apply_value_fields(ctx, idx, bytes, record.format(), record.offset_data())
58}
59
60/// Applies a value record of any format. Device offsets in it are relative
61/// to `base`.
62// The cursor is advanced past the last field too, for uniformity.
63#[allow(unused_assignments)]
64#[inline(never)]
65fn apply_value_fields(
66    ctx: &mut ApplyContext,
67    idx: usize,
68    bytes: &[u8],
69    format: ValueFormat,
70    base: FontData,
71) -> bool {
72    let scale = ctx.scale;
73    let is_horizontal = ctx.buffer.direction.is_horizontal();
74    let Some(pos) = ctx.buffer.pos.get_mut(idx).likely() else {
75        return false;
76    };
77    let mut fields = bytes
78        .chunks_exact(2)
79        .map(|field| i16::from_be_bytes([field[0], field[1]]));
80    let mut worked = false;
81    // Reads the next value, which counts only if it applies in this
82    // direction.
83    macro_rules! value {
84        ($applies:expr) => {{
85            let value = fields.next().unwrap_or(0);
86            let applies = $applies;
87            worked |= applies && value != 0;
88            applies.then_some(i32::from(value))
89        }};
90    }
91    if format.contains(ValueFormat::X_PLACEMENT) {
92        if let Some(value) = value!(true) {
93            pos.x_offset = pos.x_offset.saturating_add(scale.scale_x(value));
94        }
95    }
96    if format.contains(ValueFormat::Y_PLACEMENT) {
97        if let Some(value) = value!(true) {
98            pos.y_offset = pos.y_offset.saturating_add(scale.scale_y(value));
99        }
100    }
101    if format.contains(ValueFormat::X_ADVANCE) {
102        if let Some(value) = value!(is_horizontal) {
103            pos.x_advance = pos.x_advance.saturating_add(scale.scale_x(value));
104        }
105    }
106    if format.contains(ValueFormat::Y_ADVANCE) {
107        if let Some(value) = value!(!is_horizontal) {
108            pos.y_advance = pos.y_advance.saturating_sub(scale.scale_y(value));
109        }
110    }
111    if !format.intersects(ValueFormat::ANY_DEVICE_OR_VARIDX) {
112        return worked;
113    }
114    let Some(store) = ctx.layout.ot.var_store() else {
115        return worked;
116    };
117    let coords = ctx.layout.ot.coords;
118    // Reads the next device offset and resolves its delta, if it applies in
119    // this direction. Only variation indices contribute; device tables are
120    // for hinting, which shaping doesn't do.
121    let mut delta = |applies: bool, worked: &mut bool| -> Option<f32> {
122        let device = fields.next().unwrap_or(0) as u16 as usize;
123        if !applies {
124            return None;
125        }
126        const VARIATION_INDEX_FORMAT: u16 = 0x8000;
127        if device == 0 || base.read_at::<u16>(device + 4).ok() != Some(VARIATION_INDEX_FORMAT) {
128            return Some(0.0);
129        }
130        let outer = base.read_at::<u16>(device).ok()?;
131        let inner = base.read_at::<u16>(device + 2).ok()?;
132        // Keep the delta fractional so it is rounded once, when scaled.
133        let value = store
134            .compute_delta(DeltaSetIndex { outer, inner }, coords)
135            .unwrap_or_default()
136            .to_f64() as f32;
137        *worked |= value != 0.0;
138        Some(value)
139    };
140    if format.contains(ValueFormat::X_PLACEMENT_DEVICE) {
141        if let Some(value) = delta(true, &mut worked) {
142            pos.x_offset = pos.x_offset.saturating_add(scale.scale_x_f(value));
143        }
144    }
145    if format.contains(ValueFormat::Y_PLACEMENT_DEVICE) {
146        if let Some(value) = delta(true, &mut worked) {
147            pos.y_offset = pos.y_offset.saturating_add(scale.scale_y_f(value));
148        }
149    }
150    if format.contains(ValueFormat::X_ADVANCE_DEVICE) {
151        if let Some(value) = delta(is_horizontal, &mut worked) {
152            pos.x_advance = pos.x_advance.saturating_add(scale.scale_x_f(value));
153        }
154    }
155    if format.contains(ValueFormat::Y_ADVANCE_DEVICE) {
156        if let Some(value) = delta(!is_horizontal, &mut worked) {
157            pos.y_advance = pos.y_advance.saturating_sub(scale.scale_y_f(value));
158        }
159    }
160    worked
161}
162
163/// Single adjustment by one value record.
164pub(crate) struct SinglePos1<'a> {
165    value: ValueRecord<'a>,
166}
167
168impl<'a> SinglePos1<'a> {
169    pub fn new(table: &SinglePosFormat1<'a>) -> Option<Self> {
170        Some(Self {
171            value: ValueRecord::new(
172                table.offset_data(),
173                table.value_record_byte_range().start,
174                table.value_format(),
175            ),
176        })
177    }
178
179    pub fn new_wide(table: &SinglePosFormat3<'a>) -> Option<Self> {
180        Some(Self {
181            value: ValueRecord::new(
182                table.offset_data(),
183                table.value_record_byte_range().start,
184                table.value_format(),
185            ),
186        })
187    }
188
189    pub fn apply(&self, ctx: &mut ApplyContext, _index: u32) -> Option<()> {
190        message!(ctx, "positioning glyph at {}", ctx.buffer.idx);
191        apply_value(ctx, ctx.buffer.idx, &self.value);
192        message!(ctx, "positioned glyph at {}", ctx.buffer.idx);
193        ctx.buffer.idx += 1;
194        Some(())
195    }
196}
197
198impl<'a> SubtableDigests<'a> for SinglePos1<'a> {}
199
200/// Single adjustment by a value record per covered glyph.
201pub(crate) struct SinglePos2<'a> {
202    /// The first value record.
203    values: ValueRecord<'a>,
204    count: u32,
205}
206
207impl<'a> SinglePos2<'a> {
208    pub fn new(table: &SinglePosFormat2<'a>) -> Option<Self> {
209        Some(Self {
210            values: ValueRecord::new(
211                table.offset_data(),
212                table.value_records_byte_range().start,
213                table.value_format(),
214            ),
215            count: table.value_count().into(),
216        })
217    }
218
219    pub fn new_wide(table: &SinglePosFormat4<'a>) -> Option<Self> {
220        Some(Self {
221            values: ValueRecord::new(
222                table.offset_data(),
223                table.value_records_byte_range().start,
224                table.value_format(),
225            ),
226            count: table.value_count().to_u32(),
227        })
228    }
229
230    pub fn apply(&self, ctx: &mut ApplyContext, index: u32) -> Option<()> {
231        // A glyph covered past the end of the values has none.
232        if index >= self.count {
233            return None;
234        }
235        let values = &self.values;
236        let value = ValueRecord::new(
237            values.offset_data(),
238            values.offset() + values.byte_len() * index as usize,
239            values.format(),
240        );
241        message!(ctx, "positioning glyph at {}", ctx.buffer.idx);
242        apply_value(ctx, ctx.buffer.idx, &value);
243        message!(ctx, "positioned glyph at {}", ctx.buffer.idx);
244        ctx.buffer.idx += 1;
245        Some(())
246    }
247}
248
249impl<'a> SubtableDigests<'a> for SinglePos2<'a> {}
250
251/// The glyph that a pair starting at the current glyph would pair with.
252///
253/// It depends only on the buffer and the lookup, so the subtables of a pair
254/// lookup share one search per position.
255#[derive(Clone, Copy)]
256pub(crate) enum SecondGlyph {
257    Unknown,
258    /// No glyph follows; a match would depend on the glyphs up to
259    /// `unsafe_to`.
260    Missing {
261        unsafe_to: usize,
262    },
263    Found {
264        index: usize,
265        buf_idx: usize,
266        glyph: GlyphId,
267    },
268    Failed,
269}
270
271impl SecondGlyph {
272    /// Returns the second glyph's index in the buffer, the index to resume
273    /// from after the pair, and the glyph, searching the first time. Without
274    /// one, marks the buffer unsafe to concatenate as far as the search went.
275    #[inline(always)]
276    fn get(&mut self, ctx: &mut ApplyContext) -> Option<(usize, usize, GlyphId)> {
277        if let Self::Unknown = self {
278            *self = Self::search(ctx);
279        }
280        self.resolve(ctx)
281    }
282
283    /// The second glyph, if the search found one.
284    #[inline(always)]
285    fn resolve(self, ctx: &mut ApplyContext) -> Option<(usize, usize, GlyphId)> {
286        match self {
287            Self::Found {
288                index,
289                buf_idx,
290                glyph,
291            } => Some((index, buf_idx, glyph)),
292            Self::Missing { unsafe_to } => {
293                ctx.buffer
294                    .unsafe_to_concat(Some(ctx.buffer.idx), Some(unsafe_to));
295                None
296            }
297            Self::Unknown | Self::Failed => None,
298        }
299    }
300
301    #[inline(always)]
302    fn search(ctx: &mut ApplyContext) -> Self {
303        let mut iter = SkippingIterator::new(ctx, false);
304        if iter.reset(iter.buffer.idx).is_none() {
305            iter.buffer.index_failed();
306        }
307        let mut unsafe_to = 0;
308        if !iter.next(Some(&mut unsafe_to)) {
309            return Self::Missing { unsafe_to };
310        }
311        let index = iter.index();
312        let buf_idx = iter.buf_idx;
313        match iter.buffer.info.get(index).likely() {
314            Some(info) => Self::Found {
315                index,
316                buf_idx,
317                glyph: info.as_glyph(),
318            },
319            None => Self::Failed,
320        }
321    }
322}
323
324/// Applies the two value records of a pair at `second_index`, then moves
325/// past the pair.
326#[inline(always)]
327fn apply_pair(
328    ctx: &mut ApplyContext,
329    second_index: usize,
330    mut buf_idx: usize,
331    value1: &ValueRecord,
332    value2: &ValueRecord,
333) -> Option<()> {
334    message!(
335        ctx,
336        "try kerning glyphs at {},{second_index}",
337        ctx.buffer.idx
338    );
339    let has_value2 = !value2.is_empty();
340    let worked1 = !value1.is_empty() && apply_value(ctx, ctx.buffer.idx, value1);
341    let worked2 = has_value2 && apply_value(ctx, second_index, value2);
342    if worked1 || worked2 {
343        message!(ctx, "kerned glyphs at {},{second_index}", ctx.buffer.idx);
344        ctx.buffer
345            .unsafe_to_break(Some(ctx.buffer.idx), Some(second_index + 1));
346    } else {
347        // Even a zero-valued record is a hazard: a different second glyph
348        // could select a non-zero one.
349        ctx.buffer
350            .unsafe_to_concat(Some(ctx.buffer.idx), Some(second_index + 1));
351    }
352    message!(
353        ctx,
354        "tried kerning glyphs at {},{second_index}",
355        ctx.buffer.idx
356    );
357    if has_value2 {
358        buf_idx += 1;
359        // https://github.com/harfbuzz/harfbuzz/issues/3824
360        // https://github.com/harfbuzz/harfbuzz/issues/3888#issuecomment-1326781116
361        ctx.buffer
362            .unsafe_to_break(Some(ctx.buffer.idx), Some(buf_idx + 1));
363    }
364    ctx.buffer.idx = buf_idx;
365    Some(())
366}
367
368/// Pair adjustment by glyph pairs.
369pub(crate) struct PairPos1<'a> {
370    pair_sets: Offsets<'a>,
371    /// The second glyphs of each pair set.
372    pair_set_digests: Box<[SetDigest]>,
373    format1: ValueFormat,
374    format2: ValueFormat,
375    /// The width of a pair set's count and second glyphs.
376    width: u8,
377}
378
379impl<'a> PairPos1<'a> {
380    pub fn new(table: &PairPosFormat1<'a>, budget: &Budget) -> Result<Self, Exhausted> {
381        let range = table.pair_set_offsets_byte_range();
382        Self::from_parts(
383            Offsets::new(table.offset_data(), range, NARROW),
384            table.value_format1(),
385            table.value_format2(),
386            NARROW,
387            budget,
388        )
389    }
390
391    pub fn new_wide(table: &PairPosFormat3<'a>, budget: &Budget) -> Result<Self, Exhausted> {
392        let range = table.pair_set_offsets_byte_range();
393        Self::from_parts(
394            Offsets::new(table.offset_data(), range, WIDE),
395            table.value_format1(),
396            table.value_format2(),
397            WIDE,
398            budget,
399        )
400    }
401
402    fn from_parts(
403        pair_sets: Offsets<'a>,
404        format1: ValueFormat,
405        format2: ValueFormat,
406        width: usize,
407        budget: &Budget,
408    ) -> Result<Self, Exhausted> {
409        let record_len = width + format1.record_byte_len() + format2.record_byte_len();
410        budget.work(pair_sets.len())?;
411        budget.alloc::<SetDigest>(pair_sets.len())?;
412        let mut digests = Vec::with_capacity(pair_sets.len());
413        for index in 0..pair_sets.len() {
414            digests.push(match pair_sets.data(index) {
415                Some(data) => pair_set_digest(data, width, record_len, budget)?,
416                None => SetDigest::full(),
417            });
418        }
419        Ok(Self {
420            pair_sets,
421            pair_set_digests: digests.into_boxed_slice(),
422            format1,
423            format2,
424            width: width as u8,
425        })
426    }
427
428    /// Applies, sharing the search for the second glyph with the lookup's
429    /// other subtables.
430    #[inline]
431    pub fn apply(
432        &self,
433        ctx: &mut ApplyContext,
434        index: u32,
435        second: &mut SecondGlyph,
436    ) -> Option<()> {
437        let index = index as usize;
438        let (second_index, buf_idx, second) = second.get(ctx)?;
439        if self
440            .pair_set_digests
441            .get(index)
442            .is_some_and(|digest| !digest.may_have(second.to_u32()))
443        {
444            ctx.buffer
445                .unsafe_to_concat(Some(ctx.buffer.idx), Some(second_index + 1));
446            return None;
447        }
448
449        // Binary search the pair set's records, which start with the second
450        // glyph, directly in the bytes.
451        let data = self.pair_sets.data(index)?;
452        let bytes = data.as_bytes();
453        let width = usize::from(self.width);
454        let format1_len = self.format1.record_byte_len();
455        let record_len = width + format1_len + self.format2.record_byte_len();
456        if bytes.len() < width {
457            return None;
458        }
459        let second = second.to_u32();
460        let (mut lo, mut hi) = (0, read_uint(bytes, 0, width) as usize);
461        while lo < hi {
462            // The bounds are at most 24-bit, so the plain midpoint can't
463            // overflow.
464            #[allow(clippy::manual_midpoint)]
465            let mid = (lo + hi) / 2;
466            let offset = width + mid * record_len;
467            if offset + width > bytes.len() {
468                return None;
469            }
470            let glyph = read_uint(bytes, offset, width);
471            if glyph < second {
472                lo = mid + 1;
473            } else if glyph > second {
474                hi = mid;
475            } else {
476                let value1 = ValueRecord::new(data, offset + width, self.format1);
477                let value2 = ValueRecord::new(data, offset + width + format1_len, self.format2);
478                return apply_pair(ctx, second_index, buf_idx, &value1, &value2);
479            }
480        }
481        // The same hazard the digest reports, found the long way.
482        ctx.buffer
483            .unsafe_to_concat(Some(ctx.buffer.idx), Some(second_index + 1));
484        None
485    }
486
487    /// The second glyphs of all pairs.
488    pub fn seconds(&self, budget: &Budget) -> Result<SetDigest, Exhausted> {
489        budget.work(self.pair_set_digests.len())?;
490        let mut seconds = SetDigest::new();
491        for digest in &self.pair_set_digests {
492            seconds.union(digest);
493        }
494        Ok(seconds)
495    }
496}
497
498impl<'a> SubtableDigests<'a> for PairPos1<'a> {
499    const CACHES_COVERAGE: bool = true;
500
501    fn digest_second(&self, budget: &Budget) -> Result<SetDigest, Exhausted> {
502        self.seconds(budget)
503    }
504}
505
506/// The second glyphs of a pair set whose count and glyphs are `width` bytes,
507/// or a full digest if it is truncated.
508fn pair_set_digest(
509    data: FontData,
510    width: usize,
511    record_len: usize,
512    budget: &Budget,
513) -> Result<SetDigest, Exhausted> {
514    let bytes = data.as_bytes();
515    if bytes.len() < width {
516        return Ok(SetDigest::full());
517    }
518    let count = read_uint(bytes, 0, width) as usize;
519    let fits = count
520        .checked_mul(record_len)
521        .and_then(|len| len.checked_add(width))
522        .is_some_and(|end| end <= bytes.len());
523    if !fits {
524        return Ok(SetDigest::full());
525    }
526    budget.work(count)?;
527    let mut digest = SetDigest::new();
528    for index in 0..count {
529        digest.add(read_uint(bytes, width + index * record_len, width));
530    }
531    Ok(digest)
532}
533
534/// What the class pair subtables of both widths share: their class
535/// definitions and value matrix.
536pub(crate) struct ClassPairs<'a> {
537    class_def1: ClassDef<'a>,
538    class_def2: ClassDef<'a>,
539    records: ClassValueRecords<'a>,
540    /// The matrix, or `None` if it does not fit in the subtable.
541    matrix: Option<Range<usize>>,
542    data: FontData<'a>,
543    format1: ValueFormat,
544    format2: ValueFormat,
545    class1_count: u16,
546    class2_count: u16,
547}
548
549impl<'a> ClassPairs<'a> {
550    pub fn new(table: &PairPosFormat2<'a>) -> Self {
551        Self::from_parts(
552            ClassDef::new(table.class_def1()),
553            ClassDef::new(table.class_def2()),
554            table.class_value_records(),
555            table.offset_data(),
556            table.class2_count_byte_range().end,
557            [table.value_format1(), table.value_format2()],
558            [table.class1_count(), table.class2_count()],
559        )
560    }
561
562    pub fn new_wide(table: &PairPosFormat4<'a>) -> Self {
563        Self::from_parts(
564            ClassDef::new(table.class_def1()),
565            ClassDef::new(table.class_def2()),
566            table.class_value_records(),
567            table.offset_data(),
568            table.class2_count_byte_range().end,
569            [table.value_format1(), table.value_format2()],
570            [table.class1_count(), table.class2_count()],
571        )
572    }
573
574    fn from_parts(
575        class_def1: ClassDef<'a>,
576        class_def2: ClassDef<'a>,
577        records: ClassValueRecords<'a>,
578        data: FontData<'a>,
579        matrix_start: usize,
580        [format1, format2]: [ValueFormat; 2],
581        [class1_count, class2_count]: [u16; 2],
582    ) -> Self {
583        Self {
584            class_def1,
585            class_def2,
586            records,
587            matrix: class_matrix_range(
588                data.len(),
589                matrix_start,
590                format1.record_byte_len() + format2.record_byte_len(),
591                class1_count,
592                class2_count,
593            ),
594            data,
595            format1,
596            format2,
597            class1_count,
598            class2_count,
599        }
600    }
601}
602
603/// Caches of both classes of a glyph.
604struct PairPos2Caches {
605    class1: MappingCache,
606    class2: MappingCache,
607}
608
609fn pair_caches(
610    with_caches: bool,
611    budget: &Budget,
612) -> Result<Option<Box<PairPos2Caches>>, Exhausted> {
613    if !with_caches {
614        return Ok(None);
615    }
616    budget.alloc::<PairPos2Caches>(1)?;
617    Ok(Some(Box::new(PairPos2Caches {
618        class1: MappingCache::new(),
619        class2: MappingCache::new(),
620    })))
621}
622
623/// The classes of the first and second glyph of a pair.
624#[inline(always)]
625fn pair_classes(
626    class_def1: &ClassDef,
627    class_def2: &ClassDef,
628    caches: Option<&PairPos2Caches>,
629    first: GlyphId,
630    second: GlyphId,
631) -> (u32, u32) {
632    match caches {
633        Some(caches) => (
634            glyph_class_cached(class_def1, first, &caches.class1),
635            glyph_class_cached(class_def2, second, &caches.class2),
636        ),
637        None => (class_def1.get(first), class_def2.get(second)),
638    }
639}
640
641/// Pair adjustment by glyph classes.
642pub(crate) struct PairPos2<'a> {
643    class_def1: ClassDef<'a>,
644    class_def2: ClassDef<'a>,
645    caches: Option<Box<PairPos2Caches>>,
646    /// The matrix of value records, by first and second class.
647    records: ClassValueRecords<'a>,
648}
649
650impl<'a> PairPos2<'a> {
651    pub fn new(
652        pairs: &ClassPairs<'a>,
653        with_caches: bool,
654        budget: &Budget,
655    ) -> Result<Option<Self>, Exhausted> {
656        if pairs.matrix.is_none() {
657            return Ok(None);
658        }
659        Ok(Some(Self {
660            class_def1: pairs.class_def1,
661            class_def2: pairs.class_def2,
662            caches: pair_caches(with_caches, budget)?,
663            records: pairs.records,
664        }))
665    }
666
667    /// Applies, sharing the search for the second glyph with the lookup's
668    /// other subtables.
669    #[inline]
670    pub fn apply(
671        &self,
672        ctx: &mut ApplyContext,
673        _index: u32,
674        second: &mut SecondGlyph,
675    ) -> Option<()> {
676        let first = ctx.buffer.cur(0)?.as_glyph();
677        let (second_index, buf_idx, second) = second.get(ctx)?;
678        let (class1, class2) = pair_classes(
679            &self.class_def1,
680            &self.class_def2,
681            self.caches.as_deref(),
682            first,
683            second,
684        );
685        // Classes past 16 bits are outside any matrix.
686        let values = if (class1 | class2) >> 16 == 0 {
687            self.records.get(class1 as u16, class2 as u16)
688        } else {
689            None
690        };
691        let Some([value1, value2]) = values else {
692            // A class outside the matrix matches nothing, as in HarfBuzz.
693            ctx.buffer
694                .unsafe_to_concat(Some(ctx.buffer.idx), Some(second_index + 1));
695            return None;
696        };
697        apply_pair(ctx, second_index, buf_idx, &value1, &value2)
698    }
699}
700
701impl<'a> SubtableDigests<'a> for PairPos2<'a> {
702    const CACHES_COVERAGE: bool = true;
703}
704
705/// The byte range of a class pair subtable's value matrix, or `None` if it
706/// does not fit in the subtable's `len` bytes.
707///
708/// The extent is checked here because the generated range helpers add the
709/// matrix size to its start unchecked, which overflows on 32-bit targets.
710fn class_matrix_range(
711    len: usize,
712    start: usize,
713    record_len: usize,
714    class1_count: u16,
715    class2_count: u16,
716) -> Option<Range<usize>> {
717    let size = usize::from(class1_count)
718        .checked_mul(usize::from(class2_count))?
719        .checked_mul(record_len)?;
720    let end = start.checked_add(size)?;
721    (end <= len).then_some(start..end)
722}
723
724/// Whether a pair subtable only adjusts the advance of its first glyph,
725/// which is how kerning is stored.
726fn is_kerning(format1: ValueFormat, format2: ValueFormat) -> bool {
727    format1 == ValueFormat::X_ADVANCE && format2.is_empty()
728}
729
730/// Adds a kerning `value` to the current glyph's advance, then moves on to
731/// the second glyph of the pair.
732#[inline(always)]
733fn apply_kerning(
734    ctx: &mut ApplyContext,
735    second_index: usize,
736    buf_idx: usize,
737    value: i16,
738) -> Option<()> {
739    message!(
740        ctx,
741        "try kerning glyphs at {},{second_index}",
742        ctx.buffer.idx
743    );
744    let x_advance = ctx.scale.scale_x(i32::from(value));
745    let worked = value != 0
746        && ctx.buffer.direction.is_horizontal()
747        && ctx
748            .buffer
749            .pos
750            .get_mut(ctx.buffer.idx)
751            .likely()
752            .map(|pos| pos.x_advance = pos.x_advance.saturating_add(x_advance))
753            .is_some();
754    if worked {
755        message!(ctx, "kerned glyphs at {},{second_index}", ctx.buffer.idx);
756        ctx.buffer
757            .unsafe_to_break(Some(ctx.buffer.idx), Some(second_index + 1));
758    } else {
759        // Even a zero kern is a hazard: a different second glyph could
760        // select a non-zero one.
761        ctx.buffer
762            .unsafe_to_concat(Some(ctx.buffer.idx), Some(second_index + 1));
763    }
764    message!(
765        ctx,
766        "tried kerning glyphs at {},{second_index}",
767        ctx.buffer.idx
768    );
769    ctx.buffer.idx = buf_idx;
770    Some(())
771}
772
773/// Kerning by glyph pairs: pair adjustment format 1 whose records hold only
774/// an advance for the first glyph.
775pub(crate) struct PairKern1<'a> {
776    pair_sets: Offsets<'a>,
777    /// The second glyphs of each pair set.
778    pair_set_digests: Box<[SetDigest]>,
779}
780
781impl<'a> PairKern1<'a> {
782    /// Returns `None` unless the subtable holds only kerning.
783    pub fn new(table: &PairPosFormat1<'a>, budget: &Budget) -> Result<Option<Self>, Exhausted> {
784        if !is_kerning(table.value_format1(), table.value_format2()) {
785            return Ok(None);
786        }
787        let pairs = PairPos1::new(table, budget)?;
788        Ok(Some(Self {
789            pair_sets: pairs.pair_sets,
790            pair_set_digests: pairs.pair_set_digests,
791        }))
792    }
793
794    #[inline]
795    pub fn apply(
796        &self,
797        ctx: &mut ApplyContext,
798        index: u32,
799        second: &mut SecondGlyph,
800    ) -> Option<()> {
801        let index = index as usize;
802        let (second_index, buf_idx, second) = second.get(ctx)?;
803        if self
804            .pair_set_digests
805            .get(index)
806            .is_some_and(|digest| !digest.may_have(second.to_u32()))
807        {
808            ctx.buffer
809                .unsafe_to_concat(Some(ctx.buffer.idx), Some(second_index + 1));
810            return None;
811        }
812        // Each record is a second glyph in the high half and its kern in
813        // the low half.
814        let data = self.pair_sets.data(index)?;
815        let count = data.read_at::<u16>(0).likely_ok()? as usize;
816        let records: &[BigEndian<u32>] = data.read_array(2..2 + count * 4).ok()?;
817        let second = second.to_u32();
818        if let Ok(found) = records.binary_search_by_key(&second, |record| record.get() >> 16) {
819            let value = records[found].get() as u16 as i16;
820            return apply_kerning(ctx, second_index, buf_idx, value);
821        }
822        // The same hazard the digest reports, found the long way.
823        ctx.buffer
824            .unsafe_to_concat(Some(ctx.buffer.idx), Some(second_index + 1));
825        None
826    }
827}
828
829impl<'a> SubtableDigests<'a> for PairKern1<'a> {
830    const CACHES_COVERAGE: bool = true;
831
832    fn digest_second(&self, budget: &Budget) -> Result<SetDigest, Exhausted> {
833        budget.work(self.pair_set_digests.len())?;
834        let mut seconds = SetDigest::new();
835        for digest in &self.pair_set_digests {
836            seconds.union(digest);
837        }
838        Ok(seconds)
839    }
840}
841
842/// Kerning by glyph classes: class pair adjustment whose matrix holds only
843/// an advance for the first glyph.
844pub(crate) struct PairKern2<'a> {
845    class_def1: ClassDef<'a>,
846    class_def2: ClassDef<'a>,
847    caches: Option<Box<PairPos2Caches>>,
848    /// The kern of each first class and second class.
849    matrix: &'a [BigEndian<i16>],
850    class1_count: u16,
851    class2_count: u16,
852}
853
854impl<'a> PairKern2<'a> {
855    /// Returns `None` unless the subtable holds only kerning, in a matrix
856    /// that can be read.
857    pub fn new(
858        pairs: &ClassPairs<'a>,
859        with_caches: bool,
860        budget: &Budget,
861    ) -> Result<Option<Self>, Exhausted> {
862        if !is_kerning(pairs.format1, pairs.format2) {
863            return Ok(None);
864        }
865        let Some(Ok(matrix)) = pairs
866            .matrix
867            .clone()
868            .map(|range| pairs.data.read_array(range))
869        else {
870            return Ok(None);
871        };
872        Ok(Some(Self {
873            matrix,
874            class_def1: pairs.class_def1,
875            class_def2: pairs.class_def2,
876            caches: pair_caches(with_caches, budget)?,
877            class1_count: pairs.class1_count,
878            class2_count: pairs.class2_count,
879        }))
880    }
881
882    #[inline]
883    pub fn apply(
884        &self,
885        ctx: &mut ApplyContext,
886        _index: u32,
887        second: &mut SecondGlyph,
888    ) -> Option<()> {
889        let first = ctx.buffer.cur(0)?.as_glyph();
890        let (second_index, buf_idx, second) = second.get(ctx)?;
891        let (class1, class2) = pair_classes(
892            &self.class_def1,
893            &self.class_def2,
894            self.caches.as_deref(),
895            first,
896            second,
897        );
898        if class1 >= u32::from(self.class1_count) || class2 >= u32::from(self.class2_count) {
899            // A class outside the matrix matches nothing, as in HarfBuzz.
900            ctx.buffer
901                .unsafe_to_concat(Some(ctx.buffer.idx), Some(second_index + 1));
902            return None;
903        }
904        let index = class1 as usize * usize::from(self.class2_count) + class2 as usize;
905        let value = self.matrix.get(index)?.get();
906        apply_kerning(ctx, second_index, buf_idx, value)
907    }
908}
909
910impl<'a> SubtableDigests<'a> for PairKern2<'a> {
911    const CACHES_COVERAGE: bool = true;
912}
913
914/// Cursive attachment.
915pub(crate) struct CursivePos1<'a> {
916    coverage: Coverage<'a>,
917    /// The entry and exit anchor offsets of each covered glyph, in turn.
918    anchors: Offsets<'a>,
919}
920
921impl<'a> CursivePos1<'a> {
922    pub fn new(table: &CursivePosFormat1<'a>) -> Option<Self> {
923        let range = table.entry_exit_record_byte_range();
924        Some(Self {
925            coverage: Coverage::required(table.coverage())?,
926            anchors: Offsets::new(table.offset_data(), range, NARROW),
927        })
928    }
929
930    pub fn new_wide(table: &CursivePosFormat2<'a>) -> Option<Self> {
931        let range = table.entry_exit_record_byte_range();
932        Some(Self {
933            coverage: Coverage::required(table.coverage())?,
934            anchors: Offsets::new(table.offset_data(), range, WIDE),
935        })
936    }
937
938    pub fn apply(&self, ctx: &mut ApplyContext, index: u32) -> Option<()> {
939        let index_this = index as usize;
940        let entry_this: AnchorTable = self.anchors.get(index_this * 2)?;
941
942        let mut iter = SkippingIterator::new(ctx, false);
943        iter.reset_fast(iter.buffer.idx);
944        let mut unsafe_from = 0;
945        if !iter.prev(Some(&mut unsafe_from)) {
946            ctx.buffer
947                .unsafe_to_concat_from_outbuffer(Some(unsafe_from), Some(ctx.buffer.idx + 1));
948            return None;
949        }
950        let i = iter.index();
951        let prev = iter.buffer.info.get(i).likely()?.as_glyph();
952        let index_prev = self.coverage.get(prev)? as usize;
953        let Some(exit_prev) = self.anchors.get::<AnchorTable>(index_prev * 2 + 1) else {
954            iter.buffer
955                .unsafe_to_concat_from_outbuffer(Some(i), Some(iter.buffer.idx + 1));
956            return None;
957        };
958
959        let (exit_x, exit_y) = ctx.layout.ot.resolve_anchor(&exit_prev);
960        let (entry_x, entry_y) = ctx.layout.ot.resolve_anchor(&entry_this);
961        let (exit_x, exit_y) = (ctx.scale_x(exit_x), ctx.scale_y(exit_y));
962        let (entry_x, entry_y) = (ctx.scale_x(entry_x), ctx.scale_y(entry_y));
963
964        let direction = ctx.buffer.direction;
965        let j = ctx.buffer.idx;
966        ctx.buffer.unsafe_to_break(Some(i), Some(j + 1));
967
968        message!(ctx, "cursive attaching glyph at {} to glyph at {}", i, j);
969        let pos = &mut ctx.buffer.pos;
970        // Both glyphs change together, so adjust copies and store them back.
971        let mut prev_pos = *pos.get(i).likely()?;
972        let mut this_pos = *pos.get(j).likely()?;
973        match direction {
974            Direction::LeftToRight => {
975                prev_pos.x_advance = exit_x.saturating_add(prev_pos.x_offset);
976                let d = entry_x.saturating_add(this_pos.x_offset);
977                this_pos.x_advance = this_pos.x_advance.saturating_sub(d);
978                this_pos.x_offset = this_pos.x_offset.saturating_sub(d);
979            }
980            Direction::RightToLeft => {
981                let d = exit_x.saturating_add(prev_pos.x_offset);
982                prev_pos.x_advance = prev_pos.x_advance.saturating_sub(d);
983                prev_pos.x_offset = prev_pos.x_offset.saturating_sub(d);
984                this_pos.x_advance = entry_x.saturating_add(this_pos.x_offset);
985            }
986            Direction::TopToBottom => {
987                prev_pos.y_advance = exit_y.saturating_add(prev_pos.y_offset);
988                let d = entry_y.saturating_add(this_pos.y_offset);
989                this_pos.y_advance = this_pos.y_advance.saturating_sub(d);
990                this_pos.y_offset = this_pos.y_offset.saturating_sub(d);
991            }
992            Direction::BottomToTop => {
993                let d = exit_y.saturating_add(prev_pos.y_offset);
994                prev_pos.y_advance = prev_pos.y_advance.saturating_sub(d);
995                prev_pos.y_offset = prev_pos.y_offset.saturating_sub(d);
996                this_pos.y_advance = entry_y;
997            }
998            Direction::Invalid => {}
999        }
1000        *pos.get_mut(i).likely()? = prev_pos;
1001        *pos.get_mut(j).likely()? = this_pos;
1002
1003        // Attach the child to its parent in the cross direction. The parent
1004        // stays on the baseline; right to left, the common Arabic case, the
1005        // later glyph is the parent.
1006        let (mut child, mut parent) = (i, j);
1007        let mut x_offset = entry_x.saturating_sub(exit_x);
1008        let mut y_offset = entry_y.saturating_sub(exit_y);
1009        // The low 16 bits of the props are the lookup flags.
1010        if ctx.lookup_props as u16 & lookup_flags::RIGHT_TO_LEFT == 0 {
1011            core::mem::swap(&mut child, &mut parent);
1012            x_offset = x_offset.saturating_neg();
1013            y_offset = y_offset.saturating_neg();
1014        }
1015
1016        // If the child was attached elsewhere, reverse that chain so it
1017        // now hangs off the new parent.
1018        reverse_cursive_minor_offset(pos, child, direction, parent)?;
1019
1020        let child_pos = pos.get_mut(child).likely()?;
1021        child_pos.set_attach_type(attach_type::CURSIVE);
1022        let chain = parent as isize - child as isize;
1023        child_pos.set_attach_chain(chain as i16);
1024        // A distance that doesn't fit the chain field leaves the glyph
1025        // unattached, as in HarfBuzz.
1026        if isize::from(child_pos.attach_chain()) != chain {
1027            child_pos.set_attach_chain(0);
1028        }
1029        if direction.is_horizontal() {
1030            child_pos.y_offset = y_offset;
1031        } else {
1032            child_pos.x_offset = x_offset;
1033        }
1034        let child_chain = child_pos.attach_chain();
1035        ctx.buffer.scratch_flags |= HB_BUFFER_SCRATCH_FLAG_HAS_GPOS_ATTACHMENT;
1036
1037        // If the parent was attached to the child, separate them.
1038        // https://github.com/harfbuzz/harfbuzz/issues/2469
1039        let parent_pos = ctx.buffer.pos.get_mut(parent).likely()?;
1040        if parent_pos.attach_chain() == -child_chain {
1041            parent_pos.set_attach_chain(0);
1042            if direction.is_horizontal() {
1043                parent_pos.y_offset = 0;
1044            } else {
1045                parent_pos.x_offset = 0;
1046            }
1047        }
1048        message!(ctx, "cursive attached glyph at {} to glyph at {}", i, j);
1049        ctx.buffer.idx += 1;
1050        Some(())
1051    }
1052}
1053
1054impl<'a> SubtableDigests<'a> for CursivePos1<'a> {
1055    fn digest_second(&self, budget: &Budget) -> Result<SetDigest, Exhausted> {
1056        self.coverage.digest(budget)
1057    }
1058}
1059
1060/// Reverses the cursive chain from glyph `i` so that it ends at
1061/// `new_parent`. Returns `None` only if `i` is outside `pos`.
1062fn reverse_cursive_minor_offset(
1063    pos: &mut [GlyphPosition],
1064    i: usize,
1065    direction: Direction,
1066    new_parent: usize,
1067) -> Option<()> {
1068    let this = pos.get_mut(i).likely()?;
1069    let chain = this.attach_chain();
1070    let attach_type = this.attach_type();
1071    if chain == 0 || attach_type & attach_type::CURSIVE == 0 {
1072        return Some(());
1073    }
1074    this.set_attach_chain(0);
1075    let j = (i as isize + isize::from(chain)) as usize;
1076    // A truncated chain can point outside the buffer, and the chain stops
1077    // at the new parent.
1078    if j >= pos.len() || j == new_parent {
1079        return Some(());
1080    }
1081    reverse_cursive_minor_offset(pos, j, direction, new_parent)?;
1082    // Read this glyph after the recursion, which a looping chain can
1083    // rewrite.
1084    let this = pos.get(i).likely()?;
1085    let offset = if direction.is_horizontal() {
1086        this.y_offset
1087    } else {
1088        this.x_offset
1089    };
1090    let next = pos.get_mut(j).likely()?;
1091    if direction.is_horizontal() {
1092        next.y_offset = offset.saturating_neg();
1093    } else {
1094        next.x_offset = offset.saturating_neg();
1095    }
1096    next.set_attach_chain(-chain);
1097    next.set_attach_type(attach_type);
1098    Some(())
1099}
1100
1101/// Attaches the current glyph, a mark, to the glyph at `base_pos`.
1102fn attach_mark(
1103    ctx: &mut ApplyContext,
1104    base_anchor: &AnchorTable,
1105    mark_anchor: &AnchorTable,
1106    base_pos: usize,
1107) -> Option<()> {
1108    let (base_x, base_y) = ctx.layout.ot.resolve_anchor(base_anchor);
1109    let (mark_x, mark_y) = ctx.layout.ot.resolve_anchor(mark_anchor);
1110    let x_offset = ctx.scale_x(base_x - mark_x);
1111    let y_offset = ctx.scale_y(base_y - mark_y);
1112    // Resolve the base first so a bad index leaves the buffer untouched.
1113    let base_offset = cross_offset(&ctx.buffer.pos, base_pos, ctx.buffer.direction)?;
1114    ctx.buffer
1115        .unsafe_to_break(Some(base_pos), Some(ctx.buffer.idx + 1));
1116    let horizontal = ctx.buffer.direction.is_horizontal();
1117    let idx = ctx.buffer.idx;
1118    message!(
1119        ctx,
1120        "attaching mark glyph at {} to glyph at {}",
1121        idx,
1122        base_pos
1123    );
1124    // A distance that doesn't fit the chain field leaves the mark
1125    // unattached, as in HarfBuzz.
1126    let Ok(chain) = i16::try_from(base_pos as isize - idx as isize) else {
1127        ctx.buffer.cur_pos_mut()?.set_attach_chain(0);
1128        ctx.buffer.idx += 1;
1129        return Some(());
1130    };
1131    let pos = ctx.buffer.cur_pos_mut()?;
1132    pos.x_offset = x_offset;
1133    pos.y_offset = y_offset;
1134    if horizontal {
1135        pos.y_offset = pos.y_offset.saturating_add(base_offset);
1136    } else {
1137        pos.x_offset = pos.x_offset.saturating_add(base_offset);
1138    }
1139    pos.set_attach_type(attach_type::MARK);
1140    pos.set_attach_chain(chain);
1141    message!(
1142        ctx,
1143        "attached mark glyph at {} to glyph at {}",
1144        idx,
1145        base_pos
1146    );
1147    ctx.buffer.scratch_flags |= HB_BUFFER_SCRATCH_FLAG_HAS_GPOS_ATTACHMENT;
1148    ctx.buffer.idx += 1;
1149    Some(())
1150}
1151
1152/// The cross-direction offset of the glyph at `index`, summed along its
1153/// cursive chain.
1154fn cross_offset(pos: &[GlyphPosition], mut index: usize, direction: Direction) -> Option<i32> {
1155    let cross = |p: &GlyphPosition| {
1156        if direction.is_horizontal() {
1157            p.y_offset
1158        } else {
1159            p.x_offset
1160        }
1161    };
1162    let mut this = pos.get(index).likely()?;
1163    let mut offset = cross(this);
1164    while this.attach_type() & attach_type::CURSIVE != 0 && this.attach_chain() != 0 {
1165        // Stop at a parent outside the buffer.
1166        let Some(parent) = index
1167            .checked_add_signed(isize::from(this.attach_chain()))
1168            .and_then(|parent| Some((parent, pos.get(parent)?)))
1169        else {
1170            break;
1171        };
1172        (index, this) = parent;
1173        offset = offset.saturating_add(cross(this));
1174    }
1175    Some(offset)
1176}
1177
1178/// Searches back from the current glyph for the base a mark attaches to,
1179/// remembering the result for the marks that follow.
1180fn find_mark_base(
1181    ctx: &mut ApplyContext,
1182    accept: fn(&Buffer, usize) -> Option<bool>,
1183    coverage: &Coverage,
1184) -> Option<usize> {
1185    if ctx.last_base_until > ctx.buffer.idx as u32 {
1186        ctx.last_base_until = 0;
1187        ctx.last_base = -1;
1188    }
1189    let last_base_until = ctx.last_base_until;
1190    let mut last_base = ctx.last_base;
1191    // Search without skippy_iter.prev() to avoid O(n^2) behavior.
1192    let mut iter = SkippingIterator::new(ctx, false);
1193    iter.set_lookup_props(u32::from(lookup_flags::IGNORE_MARKS));
1194    let mut j = iter.buffer.idx;
1195    while j > last_base_until as usize {
1196        let mut matched = iter.match_at(j - 1);
1197        // https://github.com/harfbuzz/harfbuzz/issues/4124
1198        if matched == MatchResult::Match
1199            && accept(iter.buffer, j - 1) != Some(true)
1200            && iter
1201                .buffer
1202                .info
1203                .get(j - 1)
1204                .is_none_or(|info| coverage.get(info.as_glyph()).is_none())
1205        {
1206            matched = MatchResult::Skip;
1207        }
1208        if matched == MatchResult::Match {
1209            last_base = j as i32 - 1;
1210            break;
1211        }
1212        j -= 1;
1213    }
1214    ctx.last_base_until = ctx.buffer.idx as u32;
1215    ctx.last_base = last_base;
1216    if last_base == -1 {
1217        ctx.buffer
1218            .unsafe_to_concat_from_outbuffer(Some(0), Some(ctx.buffer.idx + 1));
1219        return None;
1220    }
1221    Some(last_base as usize)
1222}
1223
1224/// Whether a mark may attach to the base at `idx`: only the first glyph of
1225/// a multiple substitution is a base, unless a mark breaks the sequence.
1226/// https://github.com/harfbuzz/harfbuzz/issues/740
1227/// https://github.com/harfbuzz/harfbuzz/issues/1020
1228fn accept_base(buffer: &Buffer, idx: usize) -> Option<bool> {
1229    let info = buffer.info.get(idx).likely()?;
1230    if !info.multiplied() || info.lig_comp() == 0 || idx == 0 {
1231        return Some(true);
1232    }
1233    let prev = buffer.info.get(idx - 1).likely()?;
1234    Some(
1235        prev.is_mark()
1236            || !prev.multiplied()
1237            || info.lig_id() != prev.lig_id()
1238            || info.lig_comp() != prev.lig_comp() + 1,
1239    )
1240}
1241
1242/// Whether a mark may attach to the ligature at `idx`: the first glyph of
1243/// a multiple substitution may have been ligated with what precedes it.
1244/// https://github.com/harfbuzz/harfbuzz/issues/4969
1245fn accept_ligature(buffer: &Buffer, idx: usize) -> Option<bool> {
1246    let info = buffer.info.get(idx).likely()?;
1247    Some(!info.multiplied() || info.lig_comp() == 0)
1248}
1249
1250/// The records of a mark array: a class and an anchor offset each.
1251#[derive(Clone, Copy)]
1252struct Marks<'a> {
1253    data: FontData<'a>,
1254    count: u32,
1255    /// The width of the count, and of each anchor offset.
1256    width: u8,
1257}
1258
1259impl<'a> Marks<'a> {
1260    fn new(data: FontData<'a>, count: u32, width: usize) -> Self {
1261        Self {
1262            data,
1263            count,
1264            width: width as u8,
1265        }
1266    }
1267
1268    /// The anchor of the mark at `index` and its class.
1269    fn get(&self, index: usize) -> Option<(AnchorTable<'a>, usize)> {
1270        if index >= self.count as usize {
1271            return None;
1272        }
1273        let width = usize::from(self.width);
1274        let pos = width + index * (2 + width);
1275        let class = self.data.read_at::<u16>(pos).ok()?;
1276        let bytes = self.data.as_bytes();
1277        if pos + 2 + width > bytes.len() {
1278            return None;
1279        }
1280        // The offset isn't nullable, so a zero offset is read as given.
1281        let offset = read_uint(bytes, pos + 2, width) as usize;
1282        let anchor = AnchorTable::read(self.data.split_off(offset)?).ok()?;
1283        Some((anchor, usize::from(class)))
1284    }
1285}
1286
1287/// Rows of anchor offsets with one column per mark class, as in a base
1288/// array or a ligature component array.
1289#[derive(Clone, Copy)]
1290struct AnchorRows<'a> {
1291    offsets: Offsets<'a>,
1292    rows: u32,
1293    columns: u16,
1294}
1295
1296impl<'a> AnchorRows<'a> {
1297    /// The rows after a count of `count_width` bytes at the start of `data`,
1298    /// with offsets of `width` bytes; `None` if they are truncated.
1299    fn read(data: FontData<'a>, count_width: usize, columns: u16, width: usize) -> Option<Self> {
1300        let bytes = data.as_bytes();
1301        if bytes.len() < count_width {
1302            return None;
1303        }
1304        let rows = read_uint(bytes, 0, count_width);
1305        let count = (rows as usize).checked_mul(usize::from(columns))?;
1306        Some(Self {
1307            offsets: Offsets {
1308                data,
1309                offsets: Uints::at(data, count_width, count, width)?,
1310            },
1311            rows,
1312            columns,
1313        })
1314    }
1315
1316    fn rows(&self) -> u32 {
1317        self.rows
1318    }
1319
1320    /// The anchor in `row` for mark class `column`, or `None` if its offset
1321    /// is null.
1322    fn get(&self, row: usize, column: usize) -> Option<AnchorTable<'a>> {
1323        if row >= self.rows as usize || column >= usize::from(self.columns) {
1324            return None;
1325        }
1326        self.offsets.get(row * usize::from(self.columns) + column)
1327    }
1328}
1329
1330/// Mark-to-base attachment.
1331pub(crate) struct MarkBasePos1<'a> {
1332    base_coverage: Coverage<'a>,
1333    marks: Option<Marks<'a>>,
1334    bases: Option<AnchorRows<'a>>,
1335}
1336
1337impl<'a> MarkBasePos1<'a> {
1338    pub fn new(table: &MarkBasePosFormat1<'a>) -> Option<Self> {
1339        let classes = table.mark_class_count();
1340        Some(Self {
1341            base_coverage: Coverage::new(table.base_coverage()),
1342            marks: table
1343                .mark_array()
1344                .ok()
1345                .map(|marks| Marks::new(marks.offset_data(), marks.mark_count().into(), NARROW)),
1346            bases: table
1347                .base_array()
1348                .ok()
1349                .and_then(|bases| AnchorRows::read(bases.offset_data(), NARROW, classes, NARROW)),
1350        })
1351    }
1352
1353    pub fn new_wide(table: &MarkBasePosFormat2<'a>) -> Option<Self> {
1354        let classes = table.mark_class_count();
1355        Some(Self {
1356            base_coverage: Coverage::new(table.base_coverage()),
1357            marks: table
1358                .mark_array()
1359                .ok()
1360                .map(|marks| Marks::new(marks.offset_data(), marks.mark_count().to_u32(), WIDE)),
1361            bases: table
1362                .base_array()
1363                .ok()
1364                .and_then(|bases| AnchorRows::read(bases.offset_data(), WIDE, classes, WIDE)),
1365        })
1366    }
1367
1368    pub fn apply(&self, ctx: &mut ApplyContext, index: u32) -> Option<()> {
1369        let mark_index = index as usize;
1370        let base_coverage = self.base_coverage.present()?;
1371        let base_pos = find_mark_base(ctx, accept_base, base_coverage)?;
1372        // Checking the base's GDEF class is too strict, so it isn't done.
1373        let base = ctx.buffer.info.get(base_pos).likely()?.as_glyph();
1374        let Some(base_index) = base_coverage.get(base) else {
1375            ctx.buffer
1376                .unsafe_to_concat_from_outbuffer(Some(base_pos), Some(ctx.buffer.idx + 1));
1377            return None;
1378        };
1379        let (mark_anchor, class) = self.marks.as_ref()?.get(mark_index)?;
1380        let base_anchor = self.bases.as_ref()?.get(base_index as usize, class)?;
1381        attach_mark(ctx, &base_anchor, &mark_anchor, base_pos)
1382    }
1383}
1384
1385impl<'a> SubtableDigests<'a> for MarkBasePos1<'a> {
1386    fn digest_second(&self, budget: &Budget) -> Result<SetDigest, Exhausted> {
1387        self.base_coverage.digest(budget)
1388    }
1389}
1390
1391/// Mark-to-ligature attachment.
1392pub(crate) struct MarkLigPos1<'a> {
1393    ligature_coverage: Coverage<'a>,
1394    marks: Option<Marks<'a>>,
1395    /// The offsets to the component arrays of the ligatures.
1396    ligatures: Option<Offsets<'a>>,
1397    mark_class_count: u16,
1398    width: u8,
1399}
1400
1401impl<'a> MarkLigPos1<'a> {
1402    pub fn new(table: &MarkLigPosFormat1<'a>) -> Option<Self> {
1403        Some(Self {
1404            ligature_coverage: Coverage::new(table.ligature_coverage()),
1405            marks: table
1406                .mark_array()
1407                .ok()
1408                .map(|marks| Marks::new(marks.offset_data(), marks.mark_count().into(), NARROW)),
1409            ligatures: table.ligature_array().ok().map(|ligatures| {
1410                Offsets::new(
1411                    ligatures.offset_data(),
1412                    ligatures.ligature_attach_offsets_byte_range(),
1413                    NARROW,
1414                )
1415            }),
1416            mark_class_count: table.mark_class_count(),
1417            width: NARROW as u8,
1418        })
1419    }
1420
1421    pub fn new_wide(table: &MarkLigPosFormat2<'a>) -> Option<Self> {
1422        Some(Self {
1423            ligature_coverage: Coverage::new(table.ligature_coverage()),
1424            marks: table
1425                .mark_array()
1426                .ok()
1427                .map(|marks| Marks::new(marks.offset_data(), marks.mark_count().to_u32(), WIDE)),
1428            ligatures: table.ligature_array().ok().map(|ligatures| {
1429                Offsets::new(
1430                    ligatures.offset_data(),
1431                    ligatures.ligature_attach_offsets_byte_range(),
1432                    WIDE,
1433                )
1434            }),
1435            mark_class_count: table.mark_class_count(),
1436            width: WIDE as u8,
1437        })
1438    }
1439
1440    pub fn apply(&self, ctx: &mut ApplyContext, index: u32) -> Option<()> {
1441        let mark_index = index as usize;
1442        let ligature_coverage = self.ligature_coverage.present()?;
1443        let lig_pos = find_mark_base(ctx, accept_ligature, ligature_coverage)?;
1444        // Checking the ligature's GDEF class is too strict, so it isn't done.
1445        let lig_info = ctx.buffer.info.get(lig_pos).likely()?;
1446        let lig_id = lig_info.lig_id();
1447        let Some(lig_index) = ligature_coverage.get(lig_info.as_glyph()) else {
1448            ctx.buffer
1449                .unsafe_to_concat_from_outbuffer(Some(lig_pos), Some(ctx.buffer.idx + 1));
1450            return None;
1451        };
1452        // Each component of a ligature has a row of anchors.
1453        let components = AnchorRows::read(
1454            self.ligatures.as_ref()?.data(lig_index as usize)?,
1455            NARROW,
1456            self.mark_class_count,
1457            usize::from(self.width),
1458        )?;
1459        let comp_count = components.rows();
1460        if comp_count == 0 {
1461            ctx.buffer
1462                .unsafe_to_concat_from_outbuffer(Some(lig_pos), Some(ctx.buffer.idx + 1));
1463            return None;
1464        }
1465        // A mark from the same ligature attaches to its own component;
1466        // otherwise it attaches to the last one.
1467        let mark_id = ctx.buffer.cur(0)?.lig_id();
1468        let mark_comp = u32::from(ctx.buffer.cur(0)?.lig_comp());
1469        let comp_index = if lig_id != 0 && lig_id == mark_id && mark_comp > 0 {
1470            mark_comp.min(comp_count)
1471        } else {
1472            comp_count
1473        } - 1;
1474        let (mark_anchor, class) = self.marks.as_ref()?.get(mark_index)?;
1475        let base_anchor = components.get(comp_index as usize, class)?;
1476        attach_mark(ctx, &base_anchor, &mark_anchor, lig_pos)
1477    }
1478}
1479
1480impl<'a> SubtableDigests<'a> for MarkLigPos1<'a> {
1481    fn digest_second(&self, budget: &Budget) -> Result<SetDigest, Exhausted> {
1482        self.ligature_coverage.digest(budget)
1483    }
1484}
1485
1486/// Mark-to-mark attachment.
1487pub(crate) struct MarkMarkPos1<'a> {
1488    mark2_coverage: Coverage<'a>,
1489    marks1: Option<Marks<'a>>,
1490    marks2: Option<AnchorRows<'a>>,
1491}
1492
1493impl<'a> MarkMarkPos1<'a> {
1494    pub fn new(table: &MarkMarkPosFormat1<'a>) -> Option<Self> {
1495        let classes = table.mark_class_count();
1496        Some(Self {
1497            mark2_coverage: Coverage::new(table.mark2_coverage()),
1498            marks1: table
1499                .mark1_array()
1500                .ok()
1501                .map(|marks| Marks::new(marks.offset_data(), marks.mark_count().into(), NARROW)),
1502            marks2: table
1503                .mark2_array()
1504                .ok()
1505                .and_then(|marks| AnchorRows::read(marks.offset_data(), NARROW, classes, NARROW)),
1506        })
1507    }
1508
1509    pub fn new_wide(table: &MarkMarkPosFormat2<'a>) -> Option<Self> {
1510        let classes = table.mark_class_count();
1511        Some(Self {
1512            mark2_coverage: Coverage::new(table.mark2_coverage()),
1513            marks1: table
1514                .mark1_array()
1515                .ok()
1516                .map(|marks| Marks::new(marks.offset_data(), marks.mark_count().to_u32(), WIDE)),
1517            // The mark2 count is 16 bits in both formats.
1518            marks2: table
1519                .mark2_array()
1520                .ok()
1521                .and_then(|marks| AnchorRows::read(marks.offset_data(), NARROW, classes, WIDE)),
1522        })
1523    }
1524
1525    pub fn apply(&self, ctx: &mut ApplyContext, index: u32) -> Option<()> {
1526        let mark1_index = index as usize;
1527        // Search back for a mark, stopping at the first glyph that isn't one.
1528        let lookup_props = ctx.lookup_props;
1529        let mut iter = SkippingIterator::new(ctx, false);
1530        iter.reset_fast(iter.buffer.idx);
1531        iter.set_lookup_props(lookup_props & !u32::from(lookup_flags::IGNORE_FLAGS));
1532        let mut unsafe_from = 0;
1533        if !iter.prev(Some(&mut unsafe_from)) {
1534            iter.buffer
1535                .unsafe_to_concat_from_outbuffer(Some(unsafe_from), Some(iter.buffer.idx + 1));
1536            return None;
1537        }
1538        let mark2_pos = iter.index();
1539        let mark2 = *ctx.buffer.info.get(mark2_pos).likely()?;
1540        if !mark2.is_mark() {
1541            ctx.buffer
1542                .unsafe_to_concat_from_outbuffer(Some(mark2_pos), Some(ctx.buffer.idx + 1));
1543            return None;
1544        }
1545        let cur = ctx.buffer.cur(0)?;
1546        let (id1, comp1) = (cur.lig_id(), cur.lig_comp());
1547        let (id2, comp2) = (mark2.lig_id(), mark2.lig_comp());
1548        let matches = if id1 == id2 {
1549            // Marks of the same base, or of the same ligature component.
1550            id1 == 0 || comp1 == comp2
1551        } else {
1552            // One of the marks may itself be a ligature.
1553            (id1 > 0 && comp1 == 0) || (id2 > 0 && comp2 == 0)
1554        };
1555        if !matches {
1556            ctx.buffer
1557                .unsafe_to_concat_from_outbuffer(Some(mark2_pos), Some(ctx.buffer.idx + 1));
1558            return None;
1559        }
1560        let mark2_index = self.mark2_coverage.get(mark2.as_glyph())? as usize;
1561        let (mark1_anchor, class) = self.marks1.as_ref()?.get(mark1_index)?;
1562        let mark2_anchor = self.marks2.as_ref()?.get(mark2_index, class)?;
1563        attach_mark(ctx, &mark2_anchor, &mark1_anchor, mark2_pos)
1564    }
1565}
1566
1567impl<'a> SubtableDigests<'a> for MarkMarkPos1<'a> {
1568    fn digest_second(&self, budget: &Budget) -> Result<SetDigest, Exhausted> {
1569        self.mark2_coverage.digest(budget)
1570    }
1571}
1572
1573#[cfg(test)]
1574mod tests {
1575    use super::*;
1576    use alloc::vec;
1577    use alloc::vec::Vec;
1578
1579    /// A kerning class pair subtable claiming a 65535 by 65535 matrix while
1580    /// holding one value, which overflows the matrix size on 32-bit targets.
1581    #[test]
1582    fn repeated_pair_sets_charge_every_record_visit() {
1583        // Three offsets alias one pair set of four records. Value records
1584        // are empty, so each pair record consists only of its second glyph.
1585        let words: [u16; 13] = [1, 0, 0, 0, 3, 16, 16, 16, 4, 10, 20, 30, 40];
1586        let data: Vec<_> = words.into_iter().flat_map(u16::to_be_bytes).collect();
1587        let table = PairPosFormat1::read(FontData::new(&data)).unwrap();
1588        assert!(matches!(
1589            PairPos1::new(&table, &Budget::new(14, 1024)),
1590            Err(Exhausted)
1591        ));
1592        assert!(PairPos1::new(&table, &Budget::new(15, 1024)).is_ok());
1593    }
1594
1595    #[test]
1596    fn oversized_class_matrix_is_rejected() {
1597        let words: [u16; 14] = [
1598            2, 18, 4, 0, 24, 24, 65535, 65535,  // header
1599            0xffce, // the only value
1600            1, 1, 36, // coverage of glyph 36
1601            2, 0, // an empty class definition
1602        ];
1603        let bytes: Vec<u8> = words.iter().flat_map(|word| word.to_be_bytes()).collect();
1604        let table = PairPosFormat2::read(FontData::new(&bytes)).unwrap();
1605        let pairs = ClassPairs::new(&table);
1606        assert!(pairs.matrix.is_none());
1607        assert!(PairKern2::new(&pairs, false, &Budget::new(0, 0))
1608            .unwrap()
1609            .is_none());
1610        assert!(PairPos2::new(&pairs, false, &Budget::new(0, 0))
1611            .unwrap()
1612            .is_none());
1613    }
1614
1615    #[test]
1616    fn reverse_cursive_minor_offset_ignores_out_of_range_chain() {
1617        // A truncated attach_chain can make `i + chain` point past the end of
1618        // the buffer; reverse_cursive_minor_offset must not index out of
1619        // bounds. See https://github.com/harfbuzz/harfrust/issues/410.
1620        let mut pos = vec![GlyphPosition::default(); 4];
1621        pos[0].set_attach_type(attach_type::CURSIVE);
1622        pos[0].set_attach_chain(30000); // 0 + 30000 is far past the buffer end
1623
1624        reverse_cursive_minor_offset(&mut pos, 0, Direction::LeftToRight, 3);
1625
1626        // The out-of-range link is cleared and no other glyph is touched.
1627        assert_eq!(pos[0].attach_chain(), 0);
1628    }
1629
1630    #[test]
1631    fn reverse_cursive_minor_offset_saturates_negation() {
1632        let mut pos = vec![GlyphPosition::default(); 2];
1633        pos[0].set_attach_type(attach_type::CURSIVE);
1634        pos[0].set_attach_chain(1);
1635        pos[0].y_offset = i32::MIN;
1636
1637        reverse_cursive_minor_offset(&mut pos, 0, Direction::LeftToRight, usize::MAX);
1638
1639        assert_eq!(pos[1].y_offset, i32::MAX);
1640    }
1641}