Skip to main content

read_fonts/tables/
cmap.rs

1//! The [cmap](https://docs.microsoft.com/en-us/typography/opentype/spec/cmap) table
2
3include!("../../generated/generated_cmap.rs");
4
5#[cfg(feature = "std")]
6use crate::collections::IntSet;
7use crate::{FontRef, TableProvider};
8use std::ops::{Range, RangeInclusive};
9
10// See <https://docs.microsoft.com/en-us/typography/opentype/spec/cmap#windows-platform-platform-id--3>
11const WINDOWS_SYMBOL_ENCODING: u16 = 0;
12const WINDOWS_UNICODE_BMP_ENCODING: u16 = 1;
13const WINDOWS_UNICODE_FULL_ENCODING: u16 = 10;
14
15// See <https://docs.microsoft.com/en-us/typography/opentype/spec/name#platform-specific-encoding-and-language-ids-unicode-platform-platform-id--0>
16const UNICODE_1_0_ENCODING: u16 = 0;
17const UNICODE_1_1_ENCODING: u16 = 1;
18const UNICODE_ISO_ENCODING: u16 = 2;
19const UNICODE_2_0_BMP_ENCODING: u16 = 3;
20const UNICODE_2_0_FULL_ENCODING: u16 = 4;
21const UNICODE_VARIATION_SEQUENCES_ENCODING: u16 = 5;
22const UNICODE_FULL_ENCODING: u16 = 6;
23
24/// Result of mapping a codepoint with a variation selector.
25#[derive(Copy, Clone, PartialEq, Eq, Debug)]
26pub enum MapVariant {
27    /// The variation selector should be ignored and the default mapping
28    /// of the character should be used.
29    UseDefault,
30    /// The variant glyph mapped by a codepoint and associated variation
31    /// selector.
32    Variant(GlyphId),
33}
34
35impl<'a> Dmap<'a> {
36    /// Returns a cmap view of this table, whose structure and subtables are identical.
37    pub fn as_cmap(&self) -> Cmap<'a> {
38        // The two tables share a layout, so data that parsed as one parses
39        // as the other.
40        Cmap::read(self.offset_data()).unwrap_or_default()
41    }
42}
43
44impl<'a> Cmap<'a> {
45    /// Map a codepoint to a nominal glyph identifier
46    ///
47    /// This uses the first available subtable that provides a valid mapping.
48    ///
49    /// # Note:
50    ///
51    /// Mapping logic is currently only implemented for the most common subtable
52    /// formats.
53    pub fn map_codepoint(&self, codepoint: impl Into<u32>) -> Option<GlyphId> {
54        let codepoint = codepoint.into();
55        for record in self.encoding_records() {
56            if let Ok(subtable) = record.subtable(self.offset_data()) {
57                if let Some(gid) = subtable.map_codepoint(codepoint) {
58                    return Some(gid);
59                }
60            }
61        }
62        None
63    }
64
65    /// Returns the index, encoding record and subtable for the most
66    /// comprehensive mapping available.
67    ///
68    /// Comprehensive means that tables capable of mapping the Unicode full
69    /// repertoire are chosen over those that only support the basic
70    /// multilingual plane. The exception is that symbol mappings are
71    /// preferred above all others
72    /// (see <https://github.com/harfbuzz/harfbuzz/issues/1918>).
73    pub fn best_subtable(&self) -> Option<(u16, EncodingRecord, CmapSubtable<'a>)> {
74        // Follows the HarfBuzz approach
75        // See <https://github.com/harfbuzz/harfbuzz/blob/a9a78e1bff9d4a62429d22277fea4e0e76e9ac7e/src/hb-ot-cmap-table.hh#L1962>
76        let offset_data = self.offset_data();
77        let records = self.encoding_records();
78        let find = |platform_id, encoding_id| {
79            for (index, record) in records.iter().enumerate() {
80                if record.platform_id() != platform_id || record.encoding_id() != encoding_id {
81                    continue;
82                }
83                if let Ok(subtable) = record.subtable(offset_data) {
84                    match subtable {
85                        CmapSubtable::Format0(_)
86                        | CmapSubtable::Format4(_)
87                        | CmapSubtable::Format6(_)
88                        | CmapSubtable::Format10(_)
89                        | CmapSubtable::Format12(_)
90                        | CmapSubtable::Format13(_) => {
91                            return Some((index as u16, *record, subtable))
92                        }
93                        _ => {}
94                    }
95                }
96            }
97            None
98        };
99        // Symbol subtable.
100        // Prefer symbol if available.
101        // https://github.com/harfbuzz/harfbuzz/issues/1918
102        find(PlatformId::Windows, WINDOWS_SYMBOL_ENCODING)
103            // 32-bit subtables:
104            .or_else(|| find(PlatformId::Windows, WINDOWS_UNICODE_FULL_ENCODING))
105            .or_else(|| find(PlatformId::Unicode, UNICODE_FULL_ENCODING))
106            .or_else(|| find(PlatformId::Unicode, UNICODE_2_0_FULL_ENCODING))
107            // 16-bit subtables:
108            .or_else(|| find(PlatformId::Windows, WINDOWS_UNICODE_BMP_ENCODING))
109            .or_else(|| find(PlatformId::Unicode, UNICODE_2_0_BMP_ENCODING))
110            .or_else(|| find(PlatformId::Unicode, UNICODE_ISO_ENCODING))
111            .or_else(|| find(PlatformId::Unicode, UNICODE_1_1_ENCODING))
112            .or_else(|| find(PlatformId::Unicode, UNICODE_1_0_ENCODING))
113            // MacRoman subtable:
114            .or_else(|| find(PlatformId::Macintosh, 0))
115    }
116
117    /// Returns the index and subtable for Unicode variation sequences.
118    ///
119    /// Only Unicode records with encoding 5 hold them. A format 15 subtable
120    /// is preferred over format 14, and among records of the same format the
121    /// last one wins, following FreeType's reverse search of the records.
122    pub fn uvs_subtable(&self) -> Option<(u16, UvsSubtable<'a>)> {
123        let mut format14 = None;
124        for (index, record) in self.encoding_records().iter().enumerate().rev() {
125            if record.platform_id() != PlatformId::Unicode
126                || record.encoding_id() != UNICODE_VARIATION_SEQUENCES_ENCODING
127            {
128                continue;
129            }
130            match record.subtable(self.offset_data()) {
131                Ok(CmapSubtable::Format15(subtable)) => {
132                    return Some((index as u16, subtable.into()))
133                }
134                Ok(CmapSubtable::Format14(subtable)) if format14.is_none() => {
135                    format14 = Some((index as u16, subtable.into()));
136                }
137                _ => {}
138            }
139        }
140        format14
141    }
142
143    /// Returns the subtable at the given index.
144    pub fn subtable(&self, index: u16) -> Result<CmapSubtable<'a>, ReadError> {
145        self.encoding_records()
146            .get(index as usize)
147            .ok_or(ReadError::OutOfBounds)
148            .and_then(|encoding| encoding.subtable(self.offset_data()))
149    }
150
151    #[cfg(feature = "std")]
152    pub fn closure_glyphs(&self, unicodes: &IntSet<u32>, glyph_set: &mut IntSet<GlyphId>) {
153        if let Some((_, subtable)) = self.uvs_subtable() {
154            subtable.closure_glyphs(unicodes, glyph_set);
155        }
156    }
157}
158
159impl EncodingRecord {
160    pub fn is_symbol(&self) -> bool {
161        self.platform_id() == PlatformId::Windows && self.encoding_id() == WINDOWS_SYMBOL_ENCODING
162    }
163
164    pub fn is_mac_roman(&self) -> bool {
165        self.platform_id() == PlatformId::Macintosh && self.encoding_id() == 0
166    }
167}
168
169impl<'a> CmapSubtable<'a> {
170    pub fn language(&self) -> u32 {
171        match self {
172            Self::Format0(item) => item.language() as u32,
173            Self::Format2(item) => item.language() as u32,
174            Self::Format4(item) => item.language() as u32,
175            Self::Format6(item) => item.language() as u32,
176            Self::Format10(item) => item.language(),
177            Self::Format12(item) => item.language(),
178            Self::Format13(item) => item.language(),
179            _ => 0,
180        }
181    }
182
183    /// Attempts to map the given codepoint to a nominal glyph identifier using
184    /// the underlying subtable.
185    #[inline]
186    pub fn map_codepoint(&self, codepoint: impl Into<u32>) -> Option<GlyphId> {
187        match self {
188            Self::Format0(item) => item.map_codepoint(codepoint),
189            Self::Format4(item) => item.map_codepoint(codepoint),
190            Self::Format6(item) => item.map_codepoint(codepoint),
191            Self::Format10(item) => item.map_codepoint(codepoint),
192            Self::Format12(item) => item.map_codepoint(codepoint),
193            Self::Format13(item) => item.map_codepoint(codepoint),
194            _ => None,
195        }
196    }
197
198    /// Returns an iterator over all (codepoint, glyph identifier) pairs
199    /// in the subtable.
200    ///
201    /// Malicious and malformed fonts can produce a large number of invalid
202    /// pairs. Use [`Self::iter_with_limits`] to generate a pruned sequence
203    /// that is limited to reasonable values.
204    pub fn iter(&self) -> CmapSubtableIter<'a> {
205        let limits = CmapIterLimits {
206            max_char: u32::MAX,
207            glyph_count: u32::MAX,
208        };
209        self.iter_with_limits(limits)
210    }
211
212    /// Returns an iterator over all (codepoint, glyph identifier) pairs
213    /// in the subtable within the given limits.    
214    pub fn iter_with_limits(&self, limits: CmapIterLimits) -> CmapSubtableIter<'a> {
215        match self {
216            Self::Format0(item) => CmapSubtableIter::Format0(item.iter()),
217            Self::Format4(item) => CmapSubtableIter::Format4(item.iter()),
218            Self::Format6(item) => CmapSubtableIter::Format6(item.iter()),
219            Self::Format10(item) => CmapSubtableIter::Format10(item.iter()),
220            Self::Format12(item) => CmapSubtableIter::Format12(item.iter_with_limits(limits)),
221            Self::Format13(item) => CmapSubtableIter::Format13(item.iter_with_limits(limits)),
222            _ => CmapSubtableIter::None,
223        }
224    }
225}
226
227/// Iterator over all (codepoint, glyph identifier) pairs in
228/// the subtable.
229#[derive(Clone)]
230#[non_exhaustive]
231pub enum CmapSubtableIter<'a> {
232    None,
233    Format0(Cmap0Iter<'a>),
234    Format4(Cmap4Iter<'a>),
235    Format6(Cmap6Iter<'a>),
236    Format10(Cmap10Iter<'a>),
237    Format12(Cmap12Iter<'a>),
238    Format13(Cmap13Iter<'a>),
239}
240
241impl Iterator for CmapSubtableIter<'_> {
242    type Item = (u32, GlyphId);
243
244    #[inline]
245    fn next(&mut self) -> Option<Self::Item> {
246        match self {
247            Self::None => None,
248            Self::Format0(iter) => iter.next(),
249            Self::Format4(iter) => iter.next(),
250            Self::Format6(iter) => iter.next(),
251            Self::Format10(iter) => iter.next(),
252            Self::Format12(iter) => iter.next(),
253            Self::Format13(iter) => iter.next(),
254        }
255    }
256}
257
258impl<'a> Cmap0<'a> {
259    pub fn map_codepoint(&self, codepoint: impl Into<u32>) -> Option<GlyphId> {
260        let codepoint = codepoint.into();
261
262        self.glyph_id_array()
263            .get(codepoint as usize)
264            .map(|g| GlyphId::new(*g as u32))
265    }
266
267    /// Returns an iterator over all (codepoint, glyph identifier) pairs
268    /// in the subtable, including mappings to glyph zero.
269    pub fn iter(&self) -> Cmap0Iter<'a> {
270        Cmap0Iter {
271            glyph_ids: self.glyph_id_array(),
272            pos: 0,
273        }
274    }
275}
276
277/// Iterator over all (codepoint, glyph identifier) pairs in
278/// a format 0 subtable.
279#[derive(Clone)]
280pub struct Cmap0Iter<'a> {
281    glyph_ids: &'a [u8],
282    pos: u32,
283}
284
285impl Iterator for Cmap0Iter<'_> {
286    type Item = (u32, GlyphId);
287
288    fn next(&mut self) -> Option<Self::Item> {
289        let glyph_id = GlyphId::new(*self.glyph_ids.get(self.pos as usize)? as u32);
290        let codepoint = self.pos;
291        self.pos += 1;
292        Some((codepoint, glyph_id))
293    }
294}
295
296/// A format 4 segment a search found, for a batch to reuse.
297#[derive(Clone)]
298pub(crate) struct Cmap4Segment {
299    index: usize,
300    start_code: u16,
301    /// The codepoints of the segment the search reaches it for. Only these
302    /// may reuse it, so that a batch maps each codepoint as one lookup does.
303    reached: RangeInclusive<u16>,
304}
305
306impl<'a> Cmap4<'a> {
307    /// Maps a codepoint to a nominal glyph identifier.
308    pub fn map_codepoint(&self, codepoint: impl Into<u32>) -> Option<GlyphId> {
309        let codepoint = codepoint.into();
310        if codepoint > 0xFFFF {
311            return None;
312        }
313        let codepoint = codepoint as u16;
314        let segment = self.find_segment(codepoint)?;
315        self.lookup_glyph_id(codepoint, segment.index, segment.start_code)
316    }
317
318    /// Reuses the segment of the preceding lookup when the search would
319    /// find it for `codepoint` too.
320    pub(crate) fn map_codepoint_cached(
321        &self,
322        codepoint: u32,
323        cached: &mut Option<Cmap4Segment>,
324    ) -> Option<GlyphId> {
325        let codepoint = u16::try_from(codepoint).ok()?;
326        let segment = match cached.as_ref() {
327            Some(segment) if segment.reached.contains(&codepoint) => segment.clone(),
328            _ => self.find_segment(codepoint)?,
329        };
330        let glyph = self.lookup_glyph_id(codepoint, segment.index, segment.start_code);
331        *cached = Some(segment);
332        glyph
333    }
334
335    /// Finds the segment that maps `codepoint`, by binary search.
336    fn find_segment(&self, codepoint: u16) -> Option<Cmap4Segment> {
337        let mut lo = 0;
338        let mut hi = self.seg_count_x2() as usize / 2;
339        let start_codes = self.start_code();
340        let end_codes = self.end_code();
341        // The codepoints that take the same path down as `codepoint`. A
342        // valid table never narrows this inside the segment found; one with
343        // overlapping segments can.
344        let (mut first, mut last) = (u16::MIN, u16::MAX);
345        while lo < hi {
346            let i = (lo + hi) / 2;
347            let start_code = start_codes.get(i)?.get();
348            let end_code = end_codes.get(i)?.get();
349            if codepoint < start_code {
350                hi = i;
351                last = last.min(start_code.saturating_sub(1));
352            } else if codepoint > end_code {
353                lo = i + 1;
354                first = first.max(end_code.saturating_add(1));
355            } else {
356                return Some(Cmap4Segment {
357                    index: i,
358                    start_code,
359                    reached: start_code.max(first)..=end_code.min(last),
360                });
361            }
362        }
363        None
364    }
365
366    /// Returns an iterator over all (codepoint, glyph identifier) pairs
367    /// in the subtable.
368    pub fn iter(&self) -> Cmap4Iter<'a> {
369        Cmap4Iter::new(self.clone())
370    }
371
372    /// Does the final phase of glyph id lookup.
373    ///
374    /// Shared between Self::map and Cmap4Iter.
375    fn lookup_glyph_id(&self, codepoint: u16, index: usize, start_code: u16) -> Option<GlyphId> {
376        let deltas = self.id_delta();
377        let range_offsets = self.id_range_offsets();
378        let delta = deltas.get(index)?.get() as i32;
379        let range_offset = range_offsets.get(index)?.get() as usize;
380        if range_offset == 0 {
381            return Some(GlyphId::from((codepoint as i32 + delta) as u16));
382        }
383        // An offset that lands before the glyph id array maps nothing
384        let offset = (range_offset / 2 + (codepoint - start_code) as usize)
385            .checked_sub(range_offsets.len() - index)?;
386        let gid = self.glyph_id_array().get(offset)?.get();
387        (gid != 0).then_some(GlyphId::from((gid as i32 + delta) as u16))
388    }
389
390    /// Returns the [start_code, end_code] range at the given index.
391    fn code_range(&self, index: usize) -> Option<Range<u32>> {
392        // Extend to u32 to ensure we don't overflow on the end + 1 bound
393        // below.
394        let start = self.start_code().get(index)?.get() as u32;
395        let end = self.end_code().get(index)?.get() as u32;
396        // Use end + 1 here because the range in the table is inclusive
397        Some(start..end + 1)
398    }
399}
400
401/// Iterator over all (codepoint, glyph identifier) pairs in
402/// the subtable.
403#[derive(Clone)]
404pub struct Cmap4Iter<'a> {
405    subtable: Cmap4<'a>,
406    cur_range: Range<u32>,
407    cur_start_code: u16,
408    cur_range_ix: usize,
409}
410
411impl<'a> Cmap4Iter<'a> {
412    fn new(subtable: Cmap4<'a>) -> Self {
413        let cur_range = subtable.code_range(0).unwrap_or_default();
414        let cur_start_code = cur_range.start as u16;
415        Self {
416            subtable,
417            cur_range,
418            cur_start_code,
419            cur_range_ix: 0,
420        }
421    }
422}
423
424impl Iterator for Cmap4Iter<'_> {
425    type Item = (u32, GlyphId);
426
427    fn next(&mut self) -> Option<Self::Item> {
428        loop {
429            if let Some(codepoint) = self.cur_range.next() {
430                let Some(glyph_id) = self.subtable.lookup_glyph_id(
431                    codepoint as u16,
432                    self.cur_range_ix,
433                    self.cur_start_code,
434                ) else {
435                    continue;
436                };
437                return Some((codepoint, glyph_id));
438            } else {
439                self.cur_range_ix += 1;
440                let next_range = self.subtable.code_range(self.cur_range_ix)?;
441                // Groups should be in order and non-overlapping so make sure
442                // that the start code of next group is at least current_end + 1.
443                // Also avoid start sliding backwards if we see data where end < start by taking the max
444                // of next.end and curr.end as the new end.
445                // This prevents timeout and bizarre results in the face of numerous overlapping ranges
446                // https://github.com/googlefonts/fontations/issues/1100
447                // cmap4 ranges are u16 so no need to stress about values past char::MAX
448                // Clamp only the iteration range; the segment's real start code
449                // is still needed by lookup_glyph_id to index the glyph id array.
450                let start_code = next_range.start as u16;
451                self.cur_range = next_range.start.max(self.cur_range.end)
452                    ..next_range.end.max(self.cur_range.end);
453                self.cur_start_code = start_code;
454            }
455        }
456    }
457}
458
459impl<'a> Cmap6<'a> {
460    pub fn map_codepoint(&self, codepoint: impl Into<u32>) -> Option<GlyphId> {
461        let codepoint = codepoint.into();
462
463        let first = self.first_code() as u32;
464        let idx = codepoint.checked_sub(first)?;
465        self.glyph_id_array()
466            .get(idx as usize)
467            .map(|g| GlyphId::new(g.get() as u32))
468    }
469
470    /// Returns an iterator over all (codepoint, glyph identifier) pairs
471    /// in the subtable.    
472    pub fn iter(&self) -> Cmap6Iter<'a> {
473        Cmap6Iter {
474            first: self.first_code() as u32,
475            glyph_ids: self.glyph_id_array(),
476            pos: 0,
477        }
478    }
479}
480
481/// Iterator over all (codepoint, glyph identifier) pairs in
482/// the subtable.
483#[derive(Clone)]
484pub struct Cmap6Iter<'a> {
485    first: u32,
486    glyph_ids: &'a [BigEndian<u16>],
487    pos: u32,
488}
489
490impl Iterator for Cmap6Iter<'_> {
491    type Item = (u32, GlyphId);
492
493    fn next(&mut self) -> Option<Self::Item> {
494        let gid = self.glyph_ids.get(self.pos as usize)?.get().into();
495        let codepoint = self.first + self.pos;
496        self.pos += 1;
497        Some((codepoint, gid))
498    }
499}
500
501impl<'a> Cmap10<'a> {
502    pub fn map_codepoint(&self, codepoint: impl Into<u32>) -> Option<GlyphId> {
503        let codepoint = codepoint.into();
504        let idx = codepoint.checked_sub(self.start_char_code())?;
505        self.glyph_id_array()
506            .get(idx as usize)
507            .map(|g| GlyphId::new(g.get() as u32))
508    }
509
510    /// Returns an iterator over all (codepoint, glyph identifier) pairs
511    /// in the subtable.    
512    pub fn iter(&self) -> Cmap10Iter<'a> {
513        Cmap10Iter {
514            first: self.start_char_code(),
515            glyph_ids: self.glyph_id_array(),
516            pos: 0,
517        }
518    }
519}
520
521/// Iterator over all (codepoint, glyph identifier) pairs in
522/// the subtable.
523#[derive(Clone)]
524pub struct Cmap10Iter<'a> {
525    first: u32,
526    glyph_ids: &'a [BigEndian<u16>],
527    pos: u32,
528}
529
530impl Iterator for Cmap10Iter<'_> {
531    type Item = (u32, GlyphId);
532
533    fn next(&mut self) -> Option<Self::Item> {
534        let gid = self.glyph_ids.get(self.pos as usize)?.get().into();
535        let codepoint = self.first + self.pos;
536        self.pos += 1;
537        Some((codepoint, gid))
538    }
539}
540
541/// Trait to unify constant and sequential map groups.
542trait AnyMapGroup {
543    const IS_CONSTANT: bool;
544
545    fn start_char_code(&self) -> u32;
546    fn end_char_code(&self) -> u32;
547    /// Either start glyph id for a sequential group or just glyph id
548    /// for a constant group.
549    fn ref_glyph_id(&self) -> u32;
550
551    fn compute_glyph_id(codepoint: u32, start_char_code: u32, ref_glyph_id: u32) -> GlyphId {
552        if Self::IS_CONSTANT {
553            GlyphId::new(ref_glyph_id)
554        } else {
555            GlyphId::new(ref_glyph_id.wrapping_add(codepoint.wrapping_sub(start_char_code)))
556        }
557    }
558}
559
560impl AnyMapGroup for ConstantMapGroup {
561    const IS_CONSTANT: bool = true;
562
563    fn start_char_code(&self) -> u32 {
564        self.start_char_code()
565    }
566
567    fn end_char_code(&self) -> u32 {
568        self.end_char_code()
569    }
570
571    fn ref_glyph_id(&self) -> u32 {
572        self.glyph_id()
573    }
574}
575
576impl AnyMapGroup for SequentialMapGroup {
577    const IS_CONSTANT: bool = false;
578
579    fn start_char_code(&self) -> u32 {
580        self.start_char_code()
581    }
582
583    fn end_char_code(&self) -> u32 {
584        self.end_char_code()
585    }
586
587    fn ref_glyph_id(&self) -> u32 {
588        self.start_glyph_id()
589    }
590}
591
592/// Shared codepoint mapping code for cmap 12/13.
593fn cmap1213_map_codepoint<T: AnyMapGroup>(
594    groups: &[T],
595    codepoint: impl Into<u32>,
596) -> Option<GlyphId> {
597    let codepoint = codepoint.into();
598    let (group, _) = cmap1213_find_group(groups, codepoint)?;
599    Some(T::compute_glyph_id(
600        codepoint,
601        group.start_char_code(),
602        group.ref_glyph_id(),
603    ))
604}
605
606/// Finds the group that maps `codepoint`, by binary search, with the
607/// codepoints of that group the search reaches it for.
608fn cmap1213_find_group<T: AnyMapGroup>(
609    groups: &[T],
610    codepoint: u32,
611) -> Option<(&T, RangeInclusive<u32>)> {
612    let mut lo = 0;
613    let mut hi = groups.len();
614    // The codepoints that take the same path down as `codepoint`. Valid
615    // groups never narrow this inside the group found; overlapping ones can.
616    let (mut first, mut last) = (u32::MIN, u32::MAX);
617    while lo < hi {
618        let i = (lo + hi) / 2;
619        let group = groups.get(i)?;
620        let (start, end) = (group.start_char_code(), group.end_char_code());
621        if codepoint < start {
622            hi = i;
623            last = last.min(start.saturating_sub(1));
624        } else if codepoint > end {
625            lo = i + 1;
626            first = first.max(end.saturating_add(1));
627        } else {
628            return Some((group, start.max(first)..=end.min(last)));
629        }
630    }
631    None
632}
633
634/// Character and glyph limits for iterating format 12 and 13 subtables.
635#[derive(Copy, Clone, Debug)]
636pub struct CmapIterLimits {
637    /// The maximum valid character.
638    pub max_char: u32,
639    /// The number of glyphs in the font.
640    pub glyph_count: u32,
641}
642
643impl CmapIterLimits {
644    /// Returns the default limits for the given font.
645    ///
646    /// This will limit pairs to `char::MAX` and the number of glyphs contained
647    /// in the font. If the font is missing a `maxp` table, the number of
648    /// glyphs will be limited to `u16::MAX`.
649    pub fn default_for_font(font: &FontRef) -> Self {
650        let glyph_count = font
651            .selected_maxp()
652            .map(|maxp| maxp.num_glyphs())
653            .unwrap_or(u16::MAX as u32);
654        Self {
655            // Limit to the valid range of Unicode characters
656            // per https://github.com/googlefonts/fontations/issues/952#issuecomment-2161510184
657            max_char: char::MAX as u32,
658            glyph_count,
659        }
660    }
661}
662
663impl Default for CmapIterLimits {
664    fn default() -> Self {
665        Self {
666            max_char: char::MAX as u32,
667            // Revisit this when we actually support big glyph ids
668            glyph_count: u16::MAX as u32,
669        }
670    }
671}
672
673/// Remapped groups for iterating cmap12/13.
674#[derive(Clone, Debug)]
675struct Cmap1213IterGroup {
676    range: Range<u64>,
677    start_code: u32,
678    ref_glyph_id: u32,
679}
680
681/// Shared group resolution code for cmap 12/13.
682fn cmap1213_iter_group<T: AnyMapGroup>(
683    groups: &[T],
684    index: usize,
685    limits: &Option<CmapIterLimits>,
686) -> Option<Cmap1213IterGroup> {
687    let group = groups.get(index)?;
688    let start_code = group.start_char_code();
689    // Change to exclusive range. This can never overflow since the source
690    // is a 32-bit value
691    let end_code = group.end_char_code() as u64 + 1;
692    let start_glyph_id = group.ref_glyph_id();
693    let end_code = if let Some(limits) = limits {
694        // Set our end code to the minimum of our character and glyph
695        // count limit
696        let char_limit = limits.max_char as u64 + 1;
697        if T::IS_CONSTANT {
698            end_code.min(char_limit)
699        } else {
700            (limits.glyph_count as u64)
701                .saturating_sub(start_glyph_id as u64)
702                .saturating_add(start_code as u64)
703                .min(end_code.min(char_limit))
704        }
705    } else {
706        end_code
707    };
708    Some(Cmap1213IterGroup {
709        range: start_code as u64..end_code,
710        start_code,
711        ref_glyph_id: start_glyph_id,
712    })
713}
714
715/// Shared iterator for cmap 12/13.
716#[derive(Clone)]
717struct Cmap1213Iter<'a, T> {
718    groups: &'a [T],
719    cur_group: Option<Cmap1213IterGroup>,
720    cur_group_ix: usize,
721    limits: Option<CmapIterLimits>,
722}
723
724impl<'a, T> Cmap1213Iter<'a, T>
725where
726    T: AnyMapGroup,
727{
728    fn new(groups: &'a [T], limits: Option<CmapIterLimits>) -> Self {
729        let cur_group = cmap1213_iter_group(groups, 0, &limits);
730        Self {
731            groups,
732            cur_group,
733            cur_group_ix: 0,
734            limits,
735        }
736    }
737}
738
739impl<T> Iterator for Cmap1213Iter<'_, T>
740where
741    T: AnyMapGroup,
742{
743    type Item = (u32, GlyphId);
744
745    fn next(&mut self) -> Option<Self::Item> {
746        loop {
747            let group = self.cur_group.as_mut()?;
748            if let Some(codepoint) = group.range.next() {
749                let codepoint = codepoint as u32;
750                let glyph_id = T::compute_glyph_id(codepoint, group.start_code, group.ref_glyph_id);
751                return Some((codepoint, glyph_id));
752            } else {
753                self.cur_group_ix += 1;
754                let mut next_group =
755                    cmap1213_iter_group(self.groups, self.cur_group_ix, &self.limits)?;
756                // Groups should be in order and non-overlapping so make sure
757                // that the start code of next group is at least
758                // current_end.
759                if next_group.range.start < group.range.end {
760                    next_group.range.start = group.range.end;
761                }
762                next_group.range.end = next_group.range.end.max(group.range.end);
763                self.cur_group = Some(next_group);
764            }
765        }
766    }
767}
768
769/// A format 12 group a search found, for a batch to reuse.
770#[derive(Clone)]
771pub(crate) struct Cmap12Group {
772    start_code: u32,
773    start_glyph: u32,
774    /// The codepoints of the group the search reaches it for. Only these
775    /// may reuse it, so that a batch maps each codepoint as one lookup does.
776    reached: RangeInclusive<u32>,
777}
778
779impl<'a> Cmap12<'a> {
780    /// Maps a codepoint to a nominal glyph identifier.
781    pub fn map_codepoint(&self, codepoint: impl Into<u32>) -> Option<GlyphId> {
782        cmap1213_map_codepoint(self.groups(), codepoint)
783    }
784
785    /// Reuses the group of the preceding lookup when the search would find
786    /// it for `codepoint` too.
787    pub(crate) fn map_codepoint_cached(
788        &self,
789        codepoint: u32,
790        cached: &mut Option<Cmap12Group>,
791    ) -> Option<GlyphId> {
792        let group = match cached.as_ref() {
793            Some(group) if group.reached.contains(&codepoint) => group.clone(),
794            _ => {
795                let (group, reached) = cmap1213_find_group(self.groups(), codepoint)?;
796                Cmap12Group {
797                    start_code: group.start_char_code(),
798                    start_glyph: group.start_glyph_id(),
799                    reached,
800                }
801            }
802        };
803        let glyph = group
804            .start_glyph
805            .wrapping_add(codepoint.wrapping_sub(group.start_code));
806        *cached = Some(group);
807        Some(GlyphId::new(glyph))
808    }
809
810    /// Returns an iterator over all (codepoint, glyph identifier) pairs
811    /// in the subtable.
812    ///
813    /// Malicious and malformed fonts can produce a large number of invalid
814    /// pairs. Use [`Self::iter_with_limits`] to generate a pruned sequence
815    /// that is limited to reasonable values.
816    pub fn iter(&self) -> Cmap12Iter<'a> {
817        Cmap12Iter::new(self.clone(), None)
818    }
819
820    /// Returns an iterator over all (codepoint, glyph identifier) pairs
821    /// in the subtable within the given limits.
822    pub fn iter_with_limits(&self, limits: CmapIterLimits) -> Cmap12Iter<'a> {
823        Cmap12Iter::new(self.clone(), Some(limits))
824    }
825}
826
827/// Iterator over all (codepoint, glyph identifier) pairs in
828/// the subtable.
829#[derive(Clone)]
830pub struct Cmap12Iter<'a>(Cmap1213Iter<'a, SequentialMapGroup>);
831
832impl<'a> Cmap12Iter<'a> {
833    fn new(subtable: Cmap12<'a>, limits: Option<CmapIterLimits>) -> Self {
834        Self(Cmap1213Iter::new(subtable.groups(), limits))
835    }
836}
837
838impl Iterator for Cmap12Iter<'_> {
839    type Item = (u32, GlyphId);
840
841    fn next(&mut self) -> Option<Self::Item> {
842        self.0.next()
843    }
844}
845
846impl<'a> Cmap13<'a> {
847    /// Maps a codepoint to a nominal glyph identifier.
848    pub fn map_codepoint(&self, codepoint: impl Into<u32>) -> Option<GlyphId> {
849        cmap1213_map_codepoint(self.groups(), codepoint)
850    }
851
852    /// Returns an iterator over all (codepoint, glyph identifier) pairs
853    /// in the subtable.
854    ///
855    /// Malicious and malformed fonts can produce a large number of invalid
856    /// pairs. Use [`Self::iter_with_limits`] to generate a pruned sequence
857    /// that is limited to reasonable values.
858    pub fn iter(&self) -> Cmap13Iter<'a> {
859        Cmap13Iter::new(self.clone(), None)
860    }
861
862    /// Returns an iterator over all (codepoint, glyph identifier) pairs
863    /// in the subtable within the given limits.
864    ///
865    /// Malicious and malformed fonts can produce a large number of invalid
866    /// pairs. Use [`Self::iter_with_limits`] to generate a pruned sequence
867    /// that is limited to reasonable values.
868    pub fn iter_with_limits(&self, limits: CmapIterLimits) -> Cmap13Iter<'a> {
869        Cmap13Iter::new(self.clone(), Some(limits))
870    }
871}
872
873/// Iterator over all (codepoint, glyph identifier) pairs in
874/// the subtable.
875#[derive(Clone)]
876pub struct Cmap13Iter<'a>(Cmap1213Iter<'a, ConstantMapGroup>);
877
878impl<'a> Cmap13Iter<'a> {
879    fn new(subtable: Cmap13<'a>, limits: Option<CmapIterLimits>) -> Self {
880        Self(Cmap1213Iter::new(subtable.groups(), limits))
881    }
882}
883
884impl Iterator for Cmap13Iter<'_> {
885    type Item = (u32, GlyphId);
886
887    fn next(&mut self) -> Option<Self::Item> {
888        self.0.next()
889    }
890}
891
892impl<'a> Cmap14<'a> {
893    /// Maps a codepoint and variation selector to a nominal glyph identifier.
894    pub fn map_variant(
895        &self,
896        codepoint: impl Into<u32>,
897        selector: impl Into<u32>,
898    ) -> Option<MapVariant> {
899        UvsSubtable::from(self.clone()).map_variant(codepoint, selector)
900    }
901
902    /// Returns an iterator over all (codepoint, selector, mapping variant)
903    /// triples in the subtable.
904    ///
905    /// Malicious and malformed fonts can produce a large number of invalid
906    /// triples. Use [`Self::iter_with_limits`] to generate a pruned sequence
907    /// that is limited to reasonable values.
908    pub fn iter(&self) -> Cmap14Iter<'a> {
909        UvsSubtable::from(self.clone()).iter()
910    }
911
912    /// Returns an iterator over all (codepoint, selector, mapping variant)
913    /// triples in the subtable within the given limits.
914    pub fn iter_with_limits(&self, limits: CmapIterLimits) -> Cmap14Iter<'a> {
915        UvsSubtable::from(self.clone()).iter_with_limits(limits)
916    }
917
918    /// Adds the glyphs that variation sequences of `unicodes` map to.
919    #[cfg(feature = "std")]
920    pub fn closure_glyphs(&self, unicodes: &IntSet<u32>, glyph_set: &mut IntSet<GlyphId>) {
921        UvsSubtable::from(self.clone()).closure_glyphs(unicodes, glyph_set);
922    }
923}
924
925impl<'a> Cmap15<'a> {
926    /// Maps a codepoint and variation selector to a nominal glyph identifier.
927    pub fn map_variant(
928        &self,
929        codepoint: impl Into<u32>,
930        selector: impl Into<u32>,
931    ) -> Option<MapVariant> {
932        UvsSubtable::from(self.clone()).map_variant(codepoint, selector)
933    }
934
935    /// Returns an iterator over all (codepoint, selector, mapping variant)
936    /// triples in the subtable.
937    ///
938    /// Malicious and malformed fonts can produce a large number of invalid
939    /// triples. Use [`Self::iter_with_limits`] to generate a pruned sequence
940    /// that is limited to reasonable values.
941    pub fn iter(&self) -> Cmap15Iter<'a> {
942        UvsSubtable::from(self.clone()).iter()
943    }
944
945    /// Returns an iterator over all (codepoint, selector, mapping variant)
946    /// triples in the subtable within the given limits.
947    pub fn iter_with_limits(&self, limits: CmapIterLimits) -> Cmap15Iter<'a> {
948        UvsSubtable::from(self.clone()).iter_with_limits(limits)
949    }
950
951    /// Adds the glyphs that variation sequences of `unicodes` map to.
952    #[cfg(feature = "std")]
953    pub fn closure_glyphs(&self, unicodes: &IntSet<u32>, glyph_set: &mut IntSet<GlyphId>) {
954        UvsSubtable::from(self.clone()).closure_glyphs(unicodes, glyph_set);
955    }
956}
957
958/// A Unicode variation sequences subtable: format 14, or format 15, whose
959/// non-default mappings carry 24-bit glyph IDs.
960#[derive(Clone)]
961pub struct UvsSubtable<'a> {
962    data: FontData<'a>,
963    selectors: &'a [VariationSelector],
964    format: u16,
965}
966
967impl<'a> From<Cmap14<'a>> for UvsSubtable<'a> {
968    fn from(table: Cmap14<'a>) -> Self {
969        Self {
970            data: table.offset_data(),
971            selectors: table.var_selector(),
972            format: 14,
973        }
974    }
975}
976
977impl<'a> From<Cmap15<'a>> for UvsSubtable<'a> {
978    fn from(table: Cmap15<'a>) -> Self {
979        // The selector records of both formats have the same layout; only
980        // the non-default tables they point to differ.
981        let data = table.offset_data();
982        Self {
983            selectors: data
984                .read_array(table.var_selector_byte_range())
985                .unwrap_or_default(),
986            data,
987            format: 15,
988        }
989    }
990}
991
992impl<'a> UvsSubtable<'a> {
993    /// The subtable format: 14, or 15 for 24-bit glyph IDs.
994    pub fn format(&self) -> u16 {
995        self.format
996    }
997
998    /// The variation selector records, sorted by selector.
999    pub fn var_selector(&self) -> &'a [VariationSelector] {
1000        self.selectors
1001    }
1002
1003    /// Maps a codepoint and variation selector to a nominal glyph identifier.
1004    pub fn map_variant(
1005        &self,
1006        codepoint: impl Into<u32>,
1007        selector: impl Into<u32>,
1008    ) -> Option<MapVariant> {
1009        let codepoint = codepoint.into();
1010        let selector = selector.into();
1011        // Variation selector records are sorted in order of var_selector. Binary search to find
1012        // the appropriate record.
1013        let selector_record = self
1014            .selectors
1015            .binary_search_by(|rec| rec.var_selector().to_u32().cmp(&selector))
1016            .ok()
1017            .and_then(|idx| self.selectors.get(idx))?;
1018        // If a default UVS table is present in this selector record, binary search on the ranges
1019        // (start_unicode_value, start_unicode_value + additional_count) to find the requested codepoint.
1020        // If found, ignore the selector and return a value indicating that the default cmap mapping
1021        // should be used.
1022        if let Some(Ok(default_uvs)) = selector_record.default_uvs(self.data) {
1023            use core::cmp::Ordering;
1024            let found_default_uvs = default_uvs
1025                .ranges()
1026                .binary_search_by(|range| {
1027                    let start = range.start_unicode_value().into();
1028                    if codepoint < start {
1029                        Ordering::Greater
1030                    } else if codepoint > (start + range.additional_count() as u32) {
1031                        Ordering::Less
1032                    } else {
1033                        Ordering::Equal
1034                    }
1035                })
1036                .is_ok();
1037            if found_default_uvs {
1038                return Some(MapVariant::UseDefault);
1039            }
1040        }
1041        // Binary search the non-default UVS table if present. This maps codepoint+selector to a variant glyph.
1042        self.non_default_uvs(selector_record)?
1043            .find(codepoint)
1044            .map(MapVariant::Variant)
1045    }
1046
1047    /// Returns an iterator over all (codepoint, selector, mapping variant)
1048    /// triples in the subtable.
1049    ///
1050    /// Malicious and malformed fonts can produce a large number of invalid
1051    /// triples. Use [`Self::iter_with_limits`] to generate a pruned sequence
1052    /// that is limited to reasonable values.
1053    pub fn iter(&self) -> UvsSubtableIter<'a> {
1054        UvsSubtableIter::new(self.clone(), None)
1055    }
1056
1057    /// Returns an iterator over all (codepoint, selector, mapping variant)
1058    /// triples in the subtable within the given limits.
1059    pub fn iter_with_limits(&self, limits: CmapIterLimits) -> UvsSubtableIter<'a> {
1060        UvsSubtableIter::new(self.clone(), Some(limits))
1061    }
1062
1063    #[cfg(feature = "std")]
1064    pub fn closure_glyphs(&self, unicodes: &IntSet<u32>, glyph_set: &mut IntSet<GlyphId>) {
1065        for selector in self.selectors {
1066            if !unicodes.contains(selector.var_selector().to_u32()) {
1067                continue;
1068            }
1069            if let Some(mappings) = self.non_default_uvs(selector) {
1070                glyph_set.extend(
1071                    mappings
1072                        .filter(|(codepoint, _)| unicodes.contains(*codepoint))
1073                        .map(|(_, glyph)| glyph),
1074                );
1075            }
1076        }
1077    }
1078
1079    /// The non-default mappings of a selector record, if present and readable.
1080    fn non_default_uvs(&self, record: &VariationSelector) -> Option<NonDefaultUvsIter<'a>> {
1081        let offset = record.non_default_uvs_offset().offset().to_u32() as usize;
1082        if offset == 0 {
1083            return None;
1084        }
1085        NonDefaultUvsIter::new(self.data.split_off(offset)?, self.format == 15)
1086    }
1087}
1088
1089/// Iterator over all (codepoint, selector, mapping variant) triples in a
1090/// format 14 subtable.
1091pub type Cmap14Iter<'a> = UvsSubtableIter<'a>;
1092
1093/// Iterator over all (codepoint, selector, mapping variant) triples in a
1094/// format 15 subtable.
1095pub type Cmap15Iter<'a> = UvsSubtableIter<'a>;
1096
1097/// Iterator over all (codepoint, selector, mapping variant) triples in a
1098/// Unicode variation sequences subtable.
1099#[derive(Clone)]
1100pub struct UvsSubtableIter<'a> {
1101    subtable: UvsSubtable<'a>,
1102    records: core::slice::Iter<'a, VariationSelector>,
1103    cur_selector: Option<u32>,
1104    default_uvs: Option<DefaultUvsIter<'a>>,
1105    non_default_uvs: Option<NonDefaultUvsIter<'a>>,
1106    default_uv_left: u32,
1107    non_default_uv_left: u32,
1108}
1109
1110impl<'a> UvsSubtableIter<'a> {
1111    fn new(subtable: UvsSubtable<'a>, limits: Option<CmapIterLimits>) -> Self {
1112        let (default_uv_left, non_default_uv_left) = if let Some(limits) = limits {
1113            (limits.max_char.saturating_add(1), limits.glyph_count)
1114        } else {
1115            (u32::MAX, u32::MAX)
1116        };
1117        Self {
1118            records: subtable.selectors.iter(),
1119            subtable,
1120            cur_selector: None,
1121            default_uvs: None,
1122            non_default_uvs: None,
1123            default_uv_left,
1124            non_default_uv_left,
1125        }
1126    }
1127
1128    fn advance_selector(&mut self) -> Option<u32> {
1129        loop {
1130            let record = self.records.next()?;
1131            let selector = record.var_selector().to_u32();
1132            // The spec says:
1133            // "The VariationSelector records are sorted in increasing order of
1134            // varSelector. No two records may have the same varSelector value."
1135            //
1136            // So skip any selectors that are less than or equal to the current
1137            // selector.
1138            if let Some(cur_selector) = self.cur_selector {
1139                if selector <= cur_selector {
1140                    continue;
1141                }
1142            }
1143            self.cur_selector = Some(selector);
1144            self.default_uvs = record
1145                .default_uvs(self.subtable.data)
1146                .transpose()
1147                .ok()
1148                .flatten()
1149                .map(DefaultUvsIter::new);
1150            self.non_default_uvs = self.subtable.non_default_uvs(record);
1151            return Some(selector);
1152        }
1153    }
1154}
1155
1156impl Iterator for UvsSubtableIter<'_> {
1157    type Item = (u32, u32, MapVariant);
1158
1159    fn next(&mut self) -> Option<Self::Item> {
1160        loop {
1161            let selector = if let Some(selector) = self.cur_selector {
1162                selector
1163            } else {
1164                self.advance_selector()?
1165            };
1166            if let Some(default_uvs) = self.default_uvs.as_mut() {
1167                if let Some(codepoint) = default_uvs.next() {
1168                    self.default_uv_left = self.default_uv_left.checked_sub(1)?;
1169                    return Some((codepoint, selector, MapVariant::UseDefault));
1170                }
1171            }
1172            if let Some(non_default_uvs) = self.non_default_uvs.as_mut() {
1173                if let Some((codepoint, variant)) = non_default_uvs.next() {
1174                    self.non_default_uv_left = self.non_default_uv_left.checked_sub(1)?;
1175                    return Some((codepoint, selector, MapVariant::Variant(variant)));
1176                }
1177            }
1178            self.advance_selector()?;
1179        }
1180    }
1181}
1182
1183/// The (codepoint, glyph) mappings of a non-default UVS table, whose glyph
1184/// IDs are 16-bit in format 14 and 24-bit in format 15.
1185#[derive(Clone)]
1186struct NonDefaultUvsIter<'a> {
1187    mappings: FontData<'a>,
1188    record_len: usize,
1189    wide: bool,
1190    range: Range<usize>,
1191}
1192
1193impl<'a> NonDefaultUvsIter<'a> {
1194    fn new(data: FontData<'a>, wide: bool) -> Option<Self> {
1195        let count = usize::try_from(data.read_at::<u32>(0).ok()?).ok()?;
1196        let record_len = if wide {
1197            UvsMapping24::RAW_BYTE_LEN
1198        } else {
1199            UvsMapping::RAW_BYTE_LEN
1200        };
1201        let end = count.checked_mul(record_len)?.checked_add(4)?;
1202        Some(Self {
1203            mappings: data.slice(4..end)?,
1204            record_len,
1205            wide,
1206            range: 0..count,
1207        })
1208    }
1209
1210    fn get(&self, index: usize) -> Option<(u32, GlyphId)> {
1211        let pos = index * self.record_len;
1212        let codepoint = self.mappings.read_at::<Uint24>(pos).ok()?.to_u32();
1213        let glyph = if self.wide {
1214            self.mappings.read_at::<Uint24>(pos + 3).ok()?.to_u32()
1215        } else {
1216            self.mappings.read_at::<u16>(pos + 3).ok()?.into()
1217        };
1218        Some((codepoint, GlyphId::new(glyph)))
1219    }
1220
1221    /// Returns the glyph that `codepoint` maps to. Mappings are sorted by
1222    /// codepoint.
1223    fn find(&self, codepoint: u32) -> Option<GlyphId> {
1224        let (mut lo, mut hi) = (self.range.start, self.range.end);
1225        while lo < hi {
1226            let mid = lo + (hi - lo) / 2;
1227            let (mid_codepoint, glyph) = self.get(mid)?;
1228            match mid_codepoint.cmp(&codepoint) {
1229                core::cmp::Ordering::Less => lo = mid + 1,
1230                core::cmp::Ordering::Greater => hi = mid,
1231                core::cmp::Ordering::Equal => return Some(glyph),
1232            }
1233        }
1234        None
1235    }
1236}
1237
1238impl Iterator for NonDefaultUvsIter<'_> {
1239    type Item = (u32, GlyphId);
1240
1241    fn next(&mut self) -> Option<Self::Item> {
1242        let index = self.range.next()?;
1243        self.get(index)
1244    }
1245}
1246
1247#[derive(Clone)]
1248struct DefaultUvsIter<'a> {
1249    ranges: std::slice::Iter<'a, UnicodeRange>,
1250    cur_range: Range<u32>,
1251}
1252
1253impl<'a> DefaultUvsIter<'a> {
1254    fn new(ranges: DefaultUvs<'a>) -> Self {
1255        let mut ranges = ranges.ranges().iter();
1256        let cur_range = if let Some(range) = ranges.next() {
1257            let start: u32 = range.start_unicode_value().into();
1258            let end = start + range.additional_count() as u32 + 1;
1259            start..end
1260        } else {
1261            0..0
1262        };
1263        Self { ranges, cur_range }
1264    }
1265}
1266
1267impl Iterator for DefaultUvsIter<'_> {
1268    type Item = u32;
1269
1270    fn next(&mut self) -> Option<Self::Item> {
1271        loop {
1272            if let Some(codepoint) = self.cur_range.next() {
1273                return Some(codepoint);
1274            }
1275            let range = self.ranges.next()?;
1276            let start: u32 = range.start_unicode_value().into();
1277            let end = start + range.additional_count() as u32 + 1;
1278            self.cur_range = start..end;
1279        }
1280    }
1281}
1282
1283#[cfg(test)]
1284mod tests {
1285    use super::*;
1286    use crate::{types::Uint24, FontRef, GlyphId, TableProvider};
1287    use font_test_data::{be_buffer, bebuffer::BeBuffer};
1288
1289    // A malformed subtable with overlapping ranges must map the same glyphs
1290    // in a batch as one lookup at a time.
1291    // <https://github.com/googlefonts/fontations/pull/2261#discussion_r4305236270>
1292    const OVERLAPPING_ORDERS: [&[u32]; 4] = [
1293        &[65, 70],
1294        &[70, 65, 71, 74],
1295        &[65, 69, 70, 75, 76, 80, 81],
1296        &[80, 75, 70, 65, 66, 74],
1297    ];
1298
1299    #[test]
1300    fn cached_format12_agrees_with_lookup_on_overlapping_groups() {
1301        // Groups (65..=75 from glyph 1) and (70..=80 from glyph 100).
1302        let mut data = alloc::vec![0, 12, 0, 0];
1303        data.extend_from_slice(&(16u32 + 2 * 12).to_be_bytes());
1304        data.extend_from_slice(&0u32.to_be_bytes());
1305        data.extend_from_slice(&2u32.to_be_bytes());
1306        for (start, end, glyph) in [(65u32, 75u32, 1u32), (70, 80, 100)] {
1307            data.extend_from_slice(&start.to_be_bytes());
1308            data.extend_from_slice(&end.to_be_bytes());
1309            data.extend_from_slice(&glyph.to_be_bytes());
1310        }
1311        let cmap = Cmap12::read(FontData::new(&data)).unwrap();
1312        // The search reaches the first group for 65 and the second for 70.
1313        assert_eq!(cmap.map_codepoint(65u32), Some(GlyphId::new(1)));
1314        assert_eq!(cmap.map_codepoint(70u32), Some(GlyphId::new(100)));
1315        for order in OVERLAPPING_ORDERS {
1316            let mut cached = None;
1317            for &codepoint in order {
1318                assert_eq!(
1319                    cmap.map_codepoint_cached(codepoint, &mut cached),
1320                    cmap.map_codepoint(codepoint),
1321                    "{codepoint} in {order:?}"
1322                );
1323            }
1324        }
1325    }
1326
1327    #[test]
1328    fn cached_format4_agrees_with_lookup_on_overlapping_segments() {
1329        // Segments 65..=75 to glyphs from 1 and 70..=80 to glyphs from 100,
1330        // and the 0xFFFF segment every format 4 subtable ends with.
1331        let segments: [(u16, u16, i16); 3] = [(65, 75, -64), (70, 80, 30), (0xFFFF, 0xFFFF, 1)];
1332        let seg_count = segments.len() as u16;
1333        let mut data = alloc::vec![0, 4];
1334        data.extend_from_slice(&(16 + 8 * seg_count).to_be_bytes());
1335        data.extend_from_slice(&0u16.to_be_bytes());
1336        data.extend_from_slice(&(2 * seg_count).to_be_bytes());
1337        // Search range, entry selector and range shift, which lookups ignore.
1338        data.extend_from_slice(&[0, 4, 0, 1, 0, 2]);
1339        for (_, end, _) in segments {
1340            data.extend_from_slice(&end.to_be_bytes());
1341        }
1342        data.extend_from_slice(&0u16.to_be_bytes());
1343        for (start, _, _) in segments {
1344            data.extend_from_slice(&start.to_be_bytes());
1345        }
1346        for (_, _, delta) in segments {
1347            data.extend_from_slice(&delta.to_be_bytes());
1348        }
1349        for _ in segments {
1350            data.extend_from_slice(&0u16.to_be_bytes());
1351        }
1352        let cmap = Cmap4::read(FontData::new(&data)).unwrap();
1353        assert_eq!(cmap.map_codepoint(65u32), Some(GlyphId::new(1)));
1354        assert_eq!(cmap.map_codepoint(70u32), Some(GlyphId::new(100)));
1355        for order in OVERLAPPING_ORDERS {
1356            let mut cached = None;
1357            for &codepoint in order {
1358                assert_eq!(
1359                    cmap.map_codepoint_cached(codepoint, &mut cached),
1360                    cmap.map_codepoint(codepoint),
1361                    "{codepoint} in {order:?}"
1362                );
1363            }
1364        }
1365    }
1366
1367    #[test]
1368    fn cmap15_variants_and_iteration() {
1369        use font_test_data::cmap::format15;
1370        let data = format15(0xe0100, &[65], &[(66, 65536), (67, 70000), (68, 0xffffff)]);
1371        let table = Cmap15::read(FontData::new(&data)).unwrap();
1372        assert_eq!(table.length() as usize, data.len());
1373        let subtable = UvsSubtable::from(table.clone());
1374        assert_eq!(subtable.format(), 15);
1375        let expected = [
1376            (65, 0xe0100, MapVariant::UseDefault),
1377            (66, 0xe0100, MapVariant::Variant(GlyphId::new(65536))),
1378            (67, 0xe0100, MapVariant::Variant(GlyphId::new(70000))),
1379            (68, 0xe0100, MapVariant::Variant(GlyphId::new(0xffffff))),
1380        ];
1381        assert_eq!(subtable.iter().collect::<Vec<_>>(), expected);
1382        for (codepoint, selector, mapping) in expected {
1383            assert_eq!(subtable.map_variant(codepoint, selector), Some(mapping));
1384        }
1385        assert_eq!(subtable.map_variant(69u32, 0xe0100u32), None);
1386        assert_eq!(subtable.map_variant(66u32, 0xe0101u32), None);
1387        let mappings = table.var_selector()[0]
1388            .non_default_uvs(table.offset_data())
1389            .unwrap()
1390            .unwrap();
1391        assert_eq!(mappings.uvs_mapping().len(), 3);
1392        assert_eq!(UvsMapping24::RAW_BYTE_LEN, 6);
1393        let limits = CmapIterLimits {
1394            max_char: 0,
1395            glyph_count: 1,
1396        };
1397        assert_eq!(
1398            subtable.iter_with_limits(limits).collect::<Vec<_>>(),
1399            expected[..2]
1400        );
1401        let empty = format15(0xe0100, &[], &[]);
1402        let empty = UvsSubtable::from(Cmap15::read(FontData::new(&empty)).unwrap());
1403        assert_eq!(empty.iter().count(), 0);
1404        assert_eq!(empty.map_variant(65u32, 0xe0100u32), None);
1405    }
1406
1407    #[test]
1408    fn cmap15_malformed_arrays_and_offsets() {
1409        use font_test_data::cmap::format15;
1410        let mut data = format15(0xe0100, &[65], &[(66, 70000)]);
1411        assert!(Cmap15::read(FontData::new(&data[..9])).is_err());
1412        // An incomplete non-default mapping must not hide a valid default UVS.
1413        data.pop();
1414        let subtable = UvsSubtable::from(Cmap15::read(FontData::new(&data)).unwrap());
1415        assert_eq!(
1416            subtable.map_variant(65u32, 0xe0100u32),
1417            Some(MapVariant::UseDefault)
1418        );
1419        assert_eq!(subtable.map_variant(66u32, 0xe0100u32), None);
1420        assert_eq!(subtable.iter().count(), 1);
1421        data[17..21].copy_from_slice(&u32::MAX.to_be_bytes());
1422        let subtable = UvsSubtable::from(Cmap15::read(FontData::new(&data)).unwrap());
1423        assert_eq!(subtable.map_variant(66u32, 0xe0100u32), None);
1424        assert_eq!(subtable.iter().count(), 1);
1425        data[6..10].copy_from_slice(&u32::MAX.to_be_bytes());
1426        let subtable = UvsSubtable::from(Cmap15::read(FontData::new(&data)).unwrap());
1427        assert_eq!(subtable.iter().count(), 0);
1428        assert_eq!(subtable.map_variant(65u32, 0xe0100u32), None);
1429    }
1430
1431    #[test]
1432    fn prefer_cmap15_over_cmap14() {
1433        use font_test_data::cmap::{format14, format15, table};
1434        let old = format14(0xe0100, &[], &[(65, 1)]);
1435        let new = format15(0xe0100, &[], &[(65, 70000)]);
1436        for records in [
1437            vec![(0, 5, old.as_slice()), (0, 5, new.as_slice())],
1438            vec![(0, 5, new.as_slice()), (0, 5, old.as_slice())],
1439        ] {
1440            let data = table(&records);
1441            let cmap = Cmap::read(FontData::new(&data)).unwrap();
1442            let (_, selected) = cmap.uvs_subtable().unwrap();
1443            assert_eq!(selected.format(), 15);
1444            assert_eq!(
1445                selected.map_variant(65u32, 0xe0100u32),
1446                Some(MapVariant::Variant(GlyphId::new(70000)))
1447            );
1448            #[cfg(feature = "std")]
1449            {
1450                let unicodes = [65, 0xe0100].into_iter().collect();
1451                let mut glyphs = IntSet::empty();
1452                cmap.closure_glyphs(&unicodes, &mut glyphs);
1453                assert_eq!(glyphs.iter().collect::<Vec<_>>(), vec![GlyphId::new(70000)]);
1454            }
1455        }
1456    }
1457
1458    #[test]
1459    fn map_codepoints() {
1460        let font = FontRef::new(font_test_data::VAZIRMATN_VAR).unwrap();
1461        let cmap = font.cmap().unwrap();
1462        assert_eq!(cmap.map_codepoint('A'), Some(GlyphId::new(1)));
1463        assert_eq!(cmap.map_codepoint('À'), Some(GlyphId::new(2)));
1464        assert_eq!(cmap.map_codepoint('`'), Some(GlyphId::new(3)));
1465        assert_eq!(cmap.map_codepoint('B'), None);
1466
1467        let font = FontRef::new(font_test_data::SIMPLE_GLYF).unwrap();
1468        let cmap = font.cmap().unwrap();
1469        assert_eq!(cmap.map_codepoint(' '), Some(GlyphId::new(1)));
1470        assert_eq!(cmap.map_codepoint(0xE_u32), Some(GlyphId::new(2)));
1471        assert_eq!(cmap.map_codepoint('B'), None);
1472
1473        let cmap0_data = cmap0_data();
1474        let cmap = Cmap::read(FontData::new(cmap0_data.data())).unwrap();
1475
1476        assert_eq!(cmap.map_codepoint(0u8), Some(GlyphId::new(0)));
1477        assert_eq!(cmap.map_codepoint(b' '), Some(GlyphId::new(178)));
1478        assert_eq!(cmap.map_codepoint(b'r'), Some(GlyphId::new(193)));
1479        assert_eq!(cmap.map_codepoint(b'X'), Some(GlyphId::new(13)));
1480        assert_eq!(cmap.map_codepoint(255u8), Some(GlyphId::new(3)));
1481
1482        let cmap6_data = be_buffer! {
1483            // version
1484            0u16,
1485            // numTables
1486            1u16,
1487            // platformID
1488            1u16,
1489            // encodingID
1490            0u16,
1491            // subtableOffset
1492            12u32,
1493            // format
1494            6u16,
1495            // length
1496            32u16,
1497            // language
1498            0u16,
1499            // firstCode
1500            32u16,
1501            // entryCount
1502            5u16,
1503            // glyphIDArray
1504            [10u16, 15, 7, 20, 4]
1505        };
1506
1507        let cmap = Cmap::read(FontData::new(cmap6_data.data())).unwrap();
1508
1509        assert_eq!(cmap.map_codepoint(0u8), None);
1510        assert_eq!(cmap.map_codepoint(31u8), None);
1511        assert_eq!(cmap.map_codepoint(33u8), Some(GlyphId::new(15)));
1512        assert_eq!(cmap.map_codepoint(35u8), Some(GlyphId::new(20)));
1513        assert_eq!(cmap.map_codepoint(36u8), Some(GlyphId::new(4)));
1514        assert_eq!(cmap.map_codepoint(50u8), None);
1515    }
1516
1517    #[test]
1518    fn map_variants() {
1519        use super::MapVariant::*;
1520        let font = FontRef::new(font_test_data::CMAP14_FONT1).unwrap();
1521        let cmap = font.cmap().unwrap();
1522        let cmap14 = find_cmap14(&cmap).unwrap();
1523        let selector = '\u{e0100}';
1524        assert_eq!(cmap14.map_variant('a', selector), None);
1525        assert_eq!(cmap14.map_variant('\u{4e00}', selector), Some(UseDefault));
1526        assert_eq!(cmap14.map_variant('\u{4e06}', selector), Some(UseDefault));
1527        assert_eq!(
1528            cmap14.map_variant('\u{4e08}', selector),
1529            Some(Variant(GlyphId::new(25)))
1530        );
1531        assert_eq!(
1532            cmap14.map_variant('\u{4e09}', selector),
1533            Some(Variant(GlyphId::new(26)))
1534        );
1535    }
1536
1537    #[test]
1538    #[cfg(feature = "std")]
1539    fn cmap14_closure_glyphs() {
1540        let font = FontRef::new(font_test_data::CMAP14_FONT1).unwrap();
1541        let cmap = font.cmap().unwrap();
1542        let mut unicodes = IntSet::empty();
1543        unicodes.insert(0x4e08_u32);
1544        unicodes.insert(0xe0100_u32);
1545
1546        let mut glyph_set = IntSet::empty();
1547        glyph_set.insert(GlyphId::new(18));
1548        cmap.closure_glyphs(&unicodes, &mut glyph_set);
1549
1550        assert_eq!(glyph_set.len(), 2);
1551        assert!(glyph_set.contains(GlyphId::new(18)));
1552        assert!(glyph_set.contains(GlyphId::new(25)));
1553    }
1554
1555    #[test]
1556    fn cmap0_iter() {
1557        let data = cmap0_data();
1558        let cmap = Cmap::read(FontData::new(data.data())).unwrap();
1559        let subtable = cmap.subtable(0).unwrap();
1560        let CmapSubtable::Format0(cmap0) = &subtable else {
1561            panic!("expected format 0");
1562        };
1563
1564        let mappings = cmap0.iter().collect::<Vec<_>>();
1565        assert_eq!(mappings.len(), 256);
1566        assert_eq!(mappings[0], (0, GlyphId::NOTDEF));
1567        assert_eq!(mappings[32], (32, GlyphId::new(178)));
1568        assert_eq!(mappings[255], (255, GlyphId::new(3)));
1569        for (index, &(codepoint, glyph_id)) in mappings.iter().enumerate() {
1570            assert_eq!(codepoint, index as u32);
1571            assert_eq!(cmap0.map_codepoint(codepoint), Some(glyph_id));
1572        }
1573
1574        assert_eq!(subtable.iter().collect::<Vec<_>>(), mappings);
1575        assert_eq!(
1576            subtable
1577                .iter_with_limits(CmapIterLimits::default())
1578                .collect::<Vec<_>>(),
1579            mappings
1580        );
1581
1582        let mut iter = cmap0.iter();
1583        assert_eq!(iter.nth(255), Some((255, GlyphId::new(3))));
1584        assert_eq!(iter.next(), None);
1585        assert_eq!(iter.next(), None);
1586    }
1587
1588    #[test]
1589    fn cmap4_iter() {
1590        let font = FontRef::new(font_test_data::VAZIRMATN_VAR).unwrap();
1591        let cmap4 = find_cmap4(&font.cmap().unwrap()).unwrap();
1592        let mut count = 0;
1593        for (codepoint, glyph_id) in cmap4.iter() {
1594            assert_eq!(cmap4.map_codepoint(codepoint), Some(glyph_id));
1595            count += 1;
1596        }
1597        assert_eq!(count, 4);
1598        let font = FontRef::new(font_test_data::SIMPLE_GLYF).unwrap();
1599        let cmap4 = find_cmap4(&font.cmap().unwrap()).unwrap();
1600        let mut count = 0;
1601        for (codepoint, glyph_id) in cmap4.iter() {
1602            assert_eq!(cmap4.map_codepoint(codepoint), Some(glyph_id));
1603            count += 1;
1604        }
1605        assert_eq!(count, 3);
1606    }
1607
1608    #[test]
1609    fn cmap4_iter_explicit_notdef() {
1610        let font = FontRef::new(font_test_data::VAZIRMATN_VAR).unwrap();
1611        let cmap4 = find_cmap4(&font.cmap().unwrap()).unwrap();
1612        let mut notdef_count = 0;
1613        for (_, glyph_id) in cmap4.iter() {
1614            notdef_count += (glyph_id == GlyphId::NOTDEF) as i32;
1615        }
1616        assert!(notdef_count > 0);
1617        assert_eq!(cmap4.map_codepoint(0xFFFF_u32), Some(GlyphId::NOTDEF));
1618    }
1619
1620    // Make sure we don't bail early when iterating ranges with holes.
1621    // Encountered with Gentium Basic and Gentium Basic Book.
1622    // See <https://github.com/googlefonts/fontations/issues/897>
1623    #[test]
1624    fn cmap4_iter_sparse_range() {
1625        #[rustfmt::skip]
1626        let cmap4_data: &[u16] = &[
1627            // format, length, lang
1628            4, 0, 0,
1629            // segCountX2
1630            4,
1631            // bin search data
1632            0, 0, 0,
1633            // end code
1634            262, 0xFFFF, 
1635            // reserved pad
1636            0,
1637            // start code
1638            259, 0xFFFF,
1639            // id delta
1640            0, 1, 
1641            // id range offset
1642            4, 0,
1643            // glyph ids
1644            236, 0, 0, 326,
1645        ];
1646        let mut buf = BeBuffer::new();
1647        for &word in cmap4_data {
1648            buf = buf.push(word);
1649        }
1650        let cmap4 = Cmap4::read(FontData::new(&buf)).unwrap();
1651        let mappings = cmap4
1652            .iter()
1653            .map(|(ch, gid)| (ch, gid.to_u32()))
1654            .collect::<Vec<_>>();
1655        assert_eq!(mappings, &[(259, 236), (262, 326), (65535, 0)]);
1656    }
1657
1658    // When two segments overlap, the iterator clamps the *iteration* range of
1659    // the later segment to avoid emitting duplicate codepoints, but it must
1660    // still use that segment's real start code when indexing the glyph id
1661    // array. Otherwise codepoints in the clamped tail resolve to the wrong
1662    // glyph. See the overlap handling in the format 12/13 iterator for the
1663    // correct shape.
1664    #[test]
1665    fn cmap4_iter_overlapping_range_offset_segment() {
1666        #[rustfmt::skip]
1667        let cmap4_data: &[u16] = &[
1668            // format, length, lang
1669            4, 0, 0,
1670            // segCountX2
1671            6,
1672            // bin search data (searchRange, entrySelector, rangeShift)
1673            0, 0, 0,
1674            // end code
1675            20, 25, 0xFFFF,
1676            // reserved pad
1677            0,
1678            // start code (segment 1 overlaps segment 0: 15 <= 20)
1679            10, 15, 0xFFFF,
1680            // id delta
1681            0, 0, 1,
1682            // id range offset (segment 1 maps via the glyph id array)
1683            0, 8, 0,
1684            // glyph id array
1685            100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112,
1686        ];
1687        let mut buf = BeBuffer::new();
1688        for &word in cmap4_data {
1689            buf = buf.push(word);
1690        }
1691        let cmap4 = Cmap4::read(FontData::new(&buf)).unwrap();
1692        let mappings = cmap4
1693            .iter()
1694            .map(|(ch, gid)| (ch, gid.to_u32()))
1695            .collect::<Vec<_>>();
1696
1697        // Codepoints 21..=25 live only in segment 1, so they are resolved
1698        // through its glyph id array using start code 15. With start code 15
1699        // the indices land on glyph ids 108..=112; using the clamped value 21
1700        // instead would (incorrectly) yield 102..=106.
1701        assert_eq!(
1702            mappings,
1703            &[
1704                (10, 10),
1705                (11, 11),
1706                (12, 12),
1707                (13, 13),
1708                (14, 14),
1709                (15, 15),
1710                (16, 16),
1711                (17, 17),
1712                (18, 18),
1713                (19, 19),
1714                (20, 20),
1715                (21, 108),
1716                (22, 109),
1717                (23, 110),
1718                (24, 111),
1719                (25, 112),
1720                (65535, 0),
1721            ]
1722        );
1723    }
1724
1725    // An idRangeOffset that points before the glyph id array must leave the
1726    // codepoint unmapped rather than fall back to the first entry of the
1727    // array, as in HarfBuzz and FreeType.
1728    #[test]
1729    fn cmap4_range_offset_before_glyph_id_array() {
1730        #[rustfmt::skip]
1731        let cmap4_data: &[u16] = &[
1732            // format, length, lang
1733            4, 0, 0,
1734            // segCountX2
1735            4,
1736            // bin search data
1737            0, 0, 0,
1738            // end code
1739            0x41, 0xFFFF,
1740            // reserved pad
1741            0,
1742            // start code
1743            0x41, 0xFFFF,
1744            // id delta
1745            0, 1,
1746            // id range offset (2 / 2 + 0 - 2 is before the glyph id array)
1747            2, 0,
1748            // glyph ids
1749            5,
1750        ];
1751        let mut buf = BeBuffer::new();
1752        for &word in cmap4_data {
1753            buf = buf.push(word);
1754        }
1755        let cmap4 = Cmap4::read(FontData::new(&buf)).unwrap();
1756        assert_eq!(cmap4.map_codepoint(0x41u32), None);
1757        assert!(cmap4.iter().all(|(ch, _)| ch != 0x41));
1758    }
1759
1760    const CMAP6_PAIRS: &[(u32, u32)] = &[
1761        (0x1723, 1),
1762        (0x1724, 2),
1763        (0x1725, 3),
1764        (0x1726, 4),
1765        (0x1727, 5),
1766    ];
1767
1768    #[test]
1769    fn cmap6_map() {
1770        let font = FontRef::new(font_test_data::CMAP6).unwrap();
1771        let cmap = font.cmap().unwrap();
1772        let CmapSubtable::Format6(cmap6) = cmap.subtable(0).unwrap() else {
1773            panic!("should be a format 6 subtable");
1774        };
1775        for (ch, gid) in CMAP6_PAIRS {
1776            assert_eq!(cmap6.map_codepoint(*ch).unwrap().to_u32(), *gid);
1777        }
1778        // Check out of bounds codepoints
1779        assert!(cmap6.map_codepoint(CMAP6_PAIRS[0].0 - 1).is_none());
1780        assert!(cmap6
1781            .map_codepoint(CMAP6_PAIRS.last().copied().unwrap().0 + 1)
1782            .is_none());
1783    }
1784
1785    #[test]
1786    fn cmap6_iter() {
1787        let font = FontRef::new(font_test_data::CMAP6).unwrap();
1788        let cmap = font.cmap().unwrap();
1789        let CmapSubtable::Format6(cmap6) = cmap.subtable(0).unwrap() else {
1790            panic!("should be a format 6 subtable");
1791        };
1792        let pairs = cmap6
1793            .iter()
1794            .map(|(ch, gid)| (ch, gid.to_u32()))
1795            .collect::<Vec<_>>();
1796        assert_eq!(pairs, CMAP6_PAIRS);
1797    }
1798
1799    const CMAP10_PAIRS: &[(u32, u32)] = &[(0x109423, 26), (0x109424, 27), (0x109425, 32)];
1800
1801    #[test]
1802    fn cmap10_map() {
1803        let font = FontRef::new(font_test_data::CMAP10).unwrap();
1804        let cmap = font.cmap().unwrap();
1805        let CmapSubtable::Format10(cmap10) = cmap.subtable(0).unwrap() else {
1806            panic!("should be a format 10 subtable");
1807        };
1808        for (ch, gid) in CMAP10_PAIRS {
1809            assert_eq!(cmap10.map_codepoint(*ch).unwrap().to_u32(), *gid);
1810        }
1811        // Check out of bounds codepoints
1812        assert!(cmap10.map_codepoint(CMAP10_PAIRS[0].0 - 1).is_none());
1813        assert!(cmap10
1814            .map_codepoint(CMAP10_PAIRS.last().copied().unwrap().0 + 1)
1815            .is_none());
1816    }
1817
1818    #[test]
1819    fn cmap10_iter() {
1820        let font = FontRef::new(font_test_data::CMAP10).unwrap();
1821        let cmap = font.cmap().unwrap();
1822        let CmapSubtable::Format10(cmap10) = cmap.subtable(0).unwrap() else {
1823            panic!("should be a format 10 subtable");
1824        };
1825        let pairs = cmap10
1826            .iter()
1827            .map(|(ch, gid)| (ch, gid.to_u32()))
1828            .collect::<Vec<_>>();
1829        assert_eq!(pairs, CMAP10_PAIRS);
1830    }
1831
1832    #[test]
1833    fn cmap12_iter() {
1834        let font = FontRef::new(font_test_data::CMAP12_FONT1).unwrap();
1835        let cmap12 = find_cmap12(&font.cmap().unwrap()).unwrap();
1836        let mut count = 0;
1837        for (codepoint, glyph_id) in cmap12.iter() {
1838            assert_eq!(cmap12.map_codepoint(codepoint), Some(glyph_id));
1839            count += 1;
1840        }
1841        assert_eq!(count, 10);
1842    }
1843
1844    // oss-fuzz: detected integer addition overflow in Cmap12::group()
1845    // ref: https://oss-fuzz.com/testcase-detail/5141969742397440
1846    // and https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=69547
1847    #[test]
1848    fn cmap12_iter_avoid_overflow() {
1849        // reconstructed cmap from <https://oss-fuzz.com/testcase-detail/5141969742397440>
1850        let data = be_buffer! {
1851            12u16,      // format
1852            0u16,       // reserved, set to 0
1853            0u32,       // length, ignored
1854            0u32,       // language, ignored
1855            2u32,       // numGroups
1856            // groups: [startCode, endCode, startGlyphID]
1857            [0xFFFFFFFA_u32, 0xFFFFFFFC, 0], // group 0
1858            [0xFFFFFFFB_u32, 0xFFFFFFFF, 0] // group 1
1859        };
1860        let cmap12 = Cmap12::read(data.data().into()).unwrap();
1861        let _ = cmap12.iter().count();
1862    }
1863
1864    // oss-fuzz: timeout in Cmap12Iter
1865    // ref: https://oss-fuzz.com/testcase-detail/4628971063934976
1866    // and https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=69540
1867    #[test]
1868    fn cmap12_iter_avoid_timeout() {
1869        // ranges: [SequentialMapGroup { start_char_code: 170, end_char_code: 1330926671, start_glyph_id: 328960 }]
1870        let cmap12_data = be_buffer! {
1871            12u16,      // format
1872            0u16,       // reserved, set to 0
1873            0u32,       // length, ignored
1874            0u32,       // language, ignored
1875            1u32,       // numGroups
1876            // groups: [startCode, endCode, startGlyphID]
1877            [170u32, 1330926671, 328960] // group 0
1878        };
1879        let cmap12 = Cmap12::read(cmap12_data.data().into()).unwrap();
1880        assert!(
1881            cmap12.iter_with_limits(CmapIterLimits::default()).count() <= char::MAX as usize + 1
1882        );
1883    }
1884
1885    // oss-fuzz: timeout in outlines, caused by cmap 12 iter
1886    // ref: <https://issues.oss-fuzz.com/issues/394638728>
1887    #[test]
1888    fn cmap12_iter_avoid_timeout2() {
1889        let cmap12_data = be_buffer! {
1890            12u16,      // format
1891            0u16,       // reserved, set to 0
1892            0u32,       // length, ignored
1893            0u32,       // language, ignored
1894            3u32,       // numGroups
1895            // groups: [startCode, endCode, startGlyphID]
1896            [199u32, 16777271, 2],
1897            [262u32, 262, 3],
1898            [268u32, 268, 4]
1899        };
1900        let cmap12 = Cmap12::read(cmap12_data.data().into()).unwrap();
1901        // In the test case, maxp.numGlyphs = 8
1902        const MAX_GLYPHS: u32 = 8;
1903        let limits = CmapIterLimits {
1904            glyph_count: MAX_GLYPHS,
1905            ..Default::default()
1906        };
1907        assert_eq!(cmap12.iter_with_limits(limits).count(), MAX_GLYPHS as usize);
1908    }
1909
1910    #[test]
1911    fn cmap12_iter_glyph_limit() {
1912        let font = FontRef::new(font_test_data::CMAP12_FONT1).unwrap();
1913        let cmap12 = find_cmap12(&font.cmap().unwrap()).unwrap();
1914        let mut limits = CmapIterLimits::default_for_font(&font);
1915        // Ensure we obey the glyph count limit.
1916        // This font has 11 glyphs
1917        for glyph_count in 0..=11 {
1918            limits.glyph_count = glyph_count;
1919            assert_eq!(
1920                cmap12.iter_with_limits(limits).count(),
1921                // We always return one less than glyph count limit because
1922                // notdef is not mapped
1923                (glyph_count as usize).saturating_sub(1)
1924            );
1925        }
1926    }
1927
1928    #[test]
1929    fn cmap12_and_13_iter_include_the_maximum_character() {
1930        for max_char in [0, 1, char::MAX as u32, u32::MAX] {
1931            let mut bytes = font_test_data::cmap::format12(&[(max_char, 1)]);
1932            let limits = CmapIterLimits {
1933                max_char,
1934                glyph_count: 2,
1935            };
1936            let table = Cmap12::read(FontData::new(&bytes)).unwrap();
1937            assert_eq!(table.map_codepoint(max_char), Some(GlyphId::new(1)));
1938            assert_eq!(
1939                table.iter_with_limits(limits).collect::<Vec<_>>(),
1940                [(max_char, GlyphId::new(1))]
1941            );
1942            bytes[..2].copy_from_slice(&13u16.to_be_bytes());
1943            let table = Cmap13::read(FontData::new(&bytes)).unwrap();
1944            assert_eq!(table.map_codepoint(max_char), Some(GlyphId::new(1)));
1945            assert_eq!(
1946                table.iter_with_limits(limits).collect::<Vec<_>>(),
1947                [(max_char, GlyphId::new(1))]
1948            );
1949        }
1950    }
1951
1952    #[test]
1953    fn cmap12_iter_range_clamping() {
1954        let data = be_buffer! {
1955            12u16,      // format
1956            0u16,       // reserved, set to 0
1957            0u32,       // length, ignored
1958            0u32,       // language, ignored
1959            2u32,       // numGroups
1960            // groups: [startCode, endCode, startGlyphID]
1961            [0u32, 16777215, 0], // group 0
1962            [255u32, 0xFFFFFFFF, 0] // group 1
1963        };
1964        let cmap12 = Cmap12::read(data.data().into()).unwrap();
1965        let ranges = cmap12
1966            .groups()
1967            .iter()
1968            .map(|group| (group.start_char_code(), group.end_char_code()))
1969            .collect::<Vec<_>>();
1970        // These groups overlap and extend to the whole u32 range
1971        assert_eq!(ranges, &[(0, 16777215), (255, u32::MAX)]);
1972        // But we produce at most char::MAX + 1 results
1973        let limits = CmapIterLimits {
1974            glyph_count: u32::MAX,
1975            ..Default::default()
1976        };
1977        assert!(cmap12.iter_with_limits(limits).count() <= char::MAX as usize + 1);
1978    }
1979
1980    // Ensure range bounds stay monotonic across groups even when a middle
1981    // group's end is saturated by glyph limits. Without this, a later group
1982    // can reset iteration backwards.
1983    #[test]
1984    fn cmap12_iter_saturated_group_does_not_reset_range() {
1985        let data = be_buffer! {
1986            12u16,      // format
1987            0u16,       // reserved, set to 0
1988            0u32,       // length, ignored
1989            0u32,       // language, ignored
1990            3u32,       // numGroups
1991            // groups: [startCode, endCode, startGlyphID]
1992            [10u32, 20, 0],
1993            [15u32, 40, 100],
1994            [18u32, 22, 0]
1995        };
1996        let cmap12 = Cmap12::read(data.data().into()).unwrap();
1997        let limits = CmapIterLimits {
1998            glyph_count: 50,
1999            ..Default::default()
2000        };
2001        let codepoints = cmap12
2002            .iter_with_limits(limits)
2003            .map(|(cp, _)| cp)
2004            .collect::<Vec<_>>();
2005        assert_eq!(codepoints, (10..=22).collect::<Vec<_>>());
2006    }
2007
2008    #[test]
2009    fn cmap12_iter_explicit_notdef() {
2010        let data = be_buffer! {
2011            12u16,      // format
2012            0u16,       // reserved, set to 0
2013            0u32,       // length, ignored
2014            0u32,       // language, ignored
2015            1u32,       // numGroups
2016            // groups: [startCode, endCode, startGlyphID]
2017            [0_u32, 1_u32, 0] // group 0
2018        };
2019        let cmap12 = Cmap12::read(data.data().into()).unwrap();
2020        for (i, (codepoint, glyph_id)) in cmap12.iter().enumerate() {
2021            assert_eq!(codepoint as usize, i);
2022            assert_eq!(glyph_id.to_u32() as usize, i);
2023        }
2024        assert_eq!(cmap12.iter().next().unwrap().1, GlyphId::NOTDEF);
2025    }
2026
2027    fn cmap13_data() -> Vec<u8> {
2028        let data = be_buffer! {
2029            13u16,      // format
2030            0u16,       // reserved, set to 0
2031            0u32,       // length, ignored
2032            0u32,       // language, ignored
2033            2u32,       // numGroups
2034            // groups: [startCode, endCode, startGlyphID]
2035            [0u32, 8, 20], // group 0
2036            [42u32, 46u32, 30] // group 1
2037        };
2038        data.to_vec()
2039    }
2040
2041    #[test]
2042    fn cmap13_map() {
2043        let data = cmap13_data();
2044        let cmap13 = Cmap13::read(FontData::new(&data)).unwrap();
2045        for ch in 0u32..=8 {
2046            assert_eq!(cmap13.map_codepoint(ch), Some(GlyphId::new(20)));
2047        }
2048        for ch in 9u32..42 {
2049            assert_eq!(cmap13.map_codepoint(ch), None);
2050        }
2051        for ch in 42u32..=46 {
2052            assert_eq!(cmap13.map_codepoint(ch), Some(GlyphId::new(30)));
2053        }
2054        for ch in 47u32..1024 {
2055            assert_eq!(cmap13.map_codepoint(ch), None);
2056        }
2057    }
2058
2059    #[test]
2060    fn cmap13_iter() {
2061        let data = cmap13_data();
2062        let cmap13 = Cmap13::read(FontData::new(&data)).unwrap();
2063        for (ch, gid) in cmap13.iter() {
2064            assert_eq!(cmap13.map_codepoint(ch), Some(gid));
2065        }
2066    }
2067
2068    #[test]
2069    fn cmap14_iter() {
2070        let font = FontRef::new(font_test_data::CMAP14_FONT1).unwrap();
2071        let cmap14 = find_cmap14(&font.cmap().unwrap()).unwrap();
2072        let mut count = 0;
2073        for (codepoint, selector, mapping) in cmap14.iter() {
2074            assert_eq!(cmap14.map_variant(codepoint, selector), Some(mapping));
2075            count += 1;
2076        }
2077        assert_eq!(count, 7);
2078    }
2079
2080    /// Slice of default UVS ranges, each of which is (start_unicode_value, additional_count).
2081    type DefaultUvs<'a> = &'a [(u32, u8)];
2082
2083    /// Slice of non-default UVS ranges, each of which is (unicode_value, glyph_id).
2084    type NonDefaultUvs<'a> = &'a [(u32, u16)];
2085
2086    /// Build a minimal synthetic format-14 subtable.
2087    ///
2088    /// Each record is (selector, default_ranges, non_default_mappings), where
2089    /// default_ranges is a slice of (start, additional_count) and
2090    /// non_default_mappings is a slice of (codepoint, glyph_id).
2091    fn build_cmap14(records: &[(u32, Option<DefaultUvs>, Option<NonDefaultUvs>)]) -> BeBuffer {
2092        fn default_uvs_data(ranges: &[(u32, u8)]) -> BeBuffer {
2093            let mut bytes = BeBuffer::new();
2094            bytes = bytes.push(ranges.len() as u32);
2095            for &(start, additional_count) in ranges {
2096                bytes = bytes.push(Uint24::new(start));
2097                bytes = bytes.push(additional_count);
2098            }
2099            bytes
2100        }
2101        fn non_default_uvs_data(mappings: &[(u32, u16)]) -> BeBuffer {
2102            let mut bytes = BeBuffer::new();
2103            bytes = bytes.push(mappings.len() as u32);
2104            for &(codepoint, glyph_id) in mappings {
2105                bytes = bytes.push(Uint24::new(codepoint));
2106                bytes = bytes.push(glyph_id);
2107            }
2108            bytes
2109        }
2110        let mut data = BeBuffer::new();
2111        // format
2112        data = data.push(14u16);
2113        // length (patched after writing all data)
2114        data = data.push_with_tag(0u32, "cmap14_length");
2115        // num_var_selector_records
2116        data = data.push(records.len() as u32);
2117        let mut default_offset_tags = Vec::with_capacity(records.len());
2118        let mut non_default_offset_tags = Vec::with_capacity(records.len());
2119        for (i, (selector, default_ranges, non_default_mappings)) in records.iter().enumerate() {
2120            // var_selector (24-bit packed value)
2121            data = data.push(Uint24::new(*selector));
2122            // default_uvs_offset
2123            if default_ranges.is_some() {
2124                let tag = format!("default_uvs_offset_{i}");
2125                data = data.push_with_tag(0u32, tag.as_str());
2126                default_offset_tags.push(Some(tag));
2127            } else {
2128                data = data.push(0u32);
2129                default_offset_tags.push(None);
2130            }
2131            // non_default_uvs_offset
2132            if non_default_mappings.is_some() {
2133                let tag = format!("non_default_uvs_offset_{i}");
2134                data = data.push_with_tag(0u32, tag.as_str());
2135                non_default_offset_tags.push(Some(tag));
2136            } else {
2137                data = data.push(0u32);
2138                non_default_offset_tags.push(None);
2139            }
2140        }
2141        for (i, (_, default_ranges, _)) in records.iter().enumerate() {
2142            if let Some(ranges) = default_ranges {
2143                let table_offset = data.len() as u32;
2144                data.write_at(default_offset_tags[i].as_ref().unwrap(), table_offset);
2145                // DefaultUvs: num_unicode_value_ranges + UnicodeRange[]
2146                let bytes = default_uvs_data(ranges);
2147                data = data.extend(bytes.as_slice().iter().copied());
2148            }
2149        }
2150        for (i, (_, _, non_default_mappings)) in records.iter().enumerate() {
2151            if let Some(mappings) = non_default_mappings {
2152                let table_offset = data.len() as u32;
2153                data.write_at(non_default_offset_tags[i].as_ref().unwrap(), table_offset);
2154                // NonDefaultUvs: num_uvs_mappings + UvsMapping[]
2155                let bytes = non_default_uvs_data(mappings);
2156                data = data.extend(bytes.as_slice().iter().copied());
2157            }
2158        }
2159        data.write_at("cmap14_length", data.len() as u32);
2160        data
2161    }
2162
2163    #[test]
2164    fn cmap14_iter_only_handles_monotone_selectors() {
2165        use super::MapVariant::*;
2166        let data = build_cmap14(&[
2167            (0xE100, Some(&[(0x4E00, 0)]), Some(&[(0x4E01, 7)])),
2168            // This one is ignored, same as previous
2169            (0xE100, None, Some(&[(0x4E02, 8)])),
2170            (0xE200, None, Some(&[(0x4E03, 9)])),
2171            // This one is ignored too, less than previous
2172            (0xE100, None, Some(&[(0x4E03, 10)])),
2173        ]);
2174        let cmap14 = Cmap14::read(FontData::new(data.data())).unwrap();
2175        assert_eq!(
2176            cmap14.iter().collect::<Vec<_>>(),
2177            vec![
2178                (0x4E00, 0xE100, UseDefault),
2179                (0x4E01, 0xE100, Variant(GlyphId::new(7))),
2180                (0x4E03, 0xE200, Variant(GlyphId::new(9))),
2181            ]
2182        );
2183    }
2184
2185    #[test]
2186    fn cmap14_iter_limits_default_uvs_to_max_char() {
2187        use super::MapVariant::*;
2188        let data = build_cmap14(&[(0xE100, Some(&[(0x41, 2), (0x50, 0)]), None)]);
2189        let cmap14 = Cmap14::read(FontData::new(data.data())).unwrap();
2190        assert_eq!(
2191            cmap14
2192                .iter_with_limits(CmapIterLimits {
2193                    max_char: 1,
2194                    glyph_count: u32::MAX,
2195                })
2196                .collect::<Vec<_>>(),
2197            vec![(0x41, 0xE100, UseDefault), (0x42, 0xE100, UseDefault),]
2198        );
2199    }
2200
2201    #[test]
2202    fn cmap14_iter_limits_non_default_uvs_to_glyph_count() {
2203        use super::MapVariant::*;
2204        let data = build_cmap14(&[(
2205            0xE100,
2206            None,
2207            Some(&[(0x4E00, 10), (0x4E01, 11), (0x4E02, 12)]),
2208        )]);
2209        let cmap14 = Cmap14::read(FontData::new(data.data())).unwrap();
2210        assert_eq!(
2211            cmap14
2212                .iter_with_limits(CmapIterLimits {
2213                    max_char: u32::MAX,
2214                    glyph_count: 2,
2215                })
2216                .collect::<Vec<_>>(),
2217            vec![
2218                (0x4E00, 0xE100, Variant(GlyphId::new(10))),
2219                (0x4E01, 0xE100, Variant(GlyphId::new(11))),
2220            ]
2221        );
2222    }
2223
2224    fn find_cmap4<'a>(cmap: &Cmap<'a>) -> Option<Cmap4<'a>> {
2225        cmap.encoding_records()
2226            .iter()
2227            .filter_map(|record| record.subtable(cmap.offset_data()).ok())
2228            .find_map(|subtable| match subtable {
2229                CmapSubtable::Format4(cmap4) => Some(cmap4),
2230                _ => None,
2231            })
2232    }
2233
2234    fn find_cmap12<'a>(cmap: &Cmap<'a>) -> Option<Cmap12<'a>> {
2235        cmap.encoding_records()
2236            .iter()
2237            .filter_map(|record| record.subtable(cmap.offset_data()).ok())
2238            .find_map(|subtable| match subtable {
2239                CmapSubtable::Format12(cmap12) => Some(cmap12),
2240                _ => None,
2241            })
2242    }
2243
2244    fn find_cmap14<'a>(cmap: &Cmap<'a>) -> Option<Cmap14<'a>> {
2245        cmap.encoding_records()
2246            .iter()
2247            .filter_map(|record| record.subtable(cmap.offset_data()).ok())
2248            .find_map(|subtable| match subtable {
2249                CmapSubtable::Format14(cmap14) => Some(cmap14),
2250                _ => None,
2251            })
2252    }
2253
2254    /// <https://github.com/googlefonts/fontations/issues/1100>
2255    ///
2256    /// Note that this doesn't demonstrate the timeout, merely that we've eliminated the underlying
2257    /// enthusiasm for non-ascending ranges that enabled it
2258    #[test]
2259    fn cmap4_bad_data() {
2260        let buf = font_test_data::cmap::repetitive_cmap4();
2261        let cmap4 = Cmap4::read(FontData::new(buf.as_slice())).unwrap();
2262
2263        // we should have unique, ascending codepoints, not duplicates and overlaps
2264        assert_eq!(
2265            (6..=64).collect::<Vec<_>>(),
2266            cmap4.iter().map(|(cp, _)| cp).collect::<Vec<_>>()
2267        );
2268    }
2269
2270    fn cmap0_data() -> BeBuffer {
2271        be_buffer! {
2272            // version
2273            0u16,
2274            // numTables
2275            1u16,
2276            // platformID
2277            1u16,
2278            // encodingID
2279            0u16,
2280            // subtableOffset
2281            12u32,
2282            // format
2283            0u16,
2284            // length
2285            274u16,
2286            // language
2287            0u16,
2288            // glyphIDArray
2289            [0u8, 249, 32, 2, 198, 23, 1, 4, 26, 36,
2290            171, 168, 69, 151, 208, 238, 226, 153, 161, 138,
2291            160, 130, 169, 223, 162, 207, 146, 227, 111, 248,
2292            163, 79, 178, 27, 50, 234, 213, 57, 45, 63,
2293            103, 186, 30, 105, 131, 118, 35, 140, 51, 211,
2294            75, 172, 56, 71, 137, 99, 22, 76, 61, 125,
2295            39, 8, 177, 117, 108, 97, 202, 92, 49, 134,
2296            93, 43, 80, 66, 84, 54, 180, 113, 11, 176,
2297            229, 48, 47, 17, 124, 40, 119, 21, 13, 133,
2298            181, 224, 33, 128, 44, 46, 38, 24, 65, 152,
2299            197, 225, 102, 251, 157, 126, 182, 242, 28, 184,
2300            90, 170, 201, 144, 193, 189, 250, 142, 77, 221,
2301            81, 164, 154, 60, 37, 200, 12, 53, 219, 89,
2302            31, 209, 188, 179, 253, 220, 127, 18, 19, 64,
2303            20, 141, 98, 173, 55, 194, 70, 107, 228, 104,
2304            10, 9, 15, 217, 255, 222, 196, 236, 67, 165,
2305            5, 143, 149, 100, 91, 95, 135, 235, 145, 204,
2306            72, 114, 246, 82, 245, 233, 106, 158, 185, 212,
2307            86, 243, 16, 195, 123, 190, 120, 187, 132, 139,
2308            192, 239, 110, 183, 240, 214, 166, 41, 59, 231,
2309            42, 94, 244, 83, 121, 25, 215, 96, 73, 87,
2310            174, 136, 62, 206, 156, 175, 230, 150, 116, 147,
2311            68, 122, 78, 112, 6, 167, 232, 254, 52, 34,
2312            191, 85, 241, 14, 216, 155, 29, 101, 115, 210,
2313            252, 218, 129, 247, 203, 159, 109, 74, 7, 58,
2314            237, 199, 88, 205, 148, 3]
2315        }
2316    }
2317
2318    #[test]
2319    fn best_subtable_full() {
2320        let font = FontRef::new(font_test_data::VORG).unwrap();
2321        let cmap = font.cmap().unwrap();
2322        let (index, record, _) = cmap.best_subtable().unwrap();
2323        assert_eq!(
2324            (index, record.platform_id(), record.encoding_id()),
2325            (3, PlatformId::Windows, WINDOWS_UNICODE_FULL_ENCODING)
2326        );
2327    }
2328
2329    #[test]
2330    fn best_subtable_bmp() {
2331        let font = FontRef::new(font_test_data::CMAP12_FONT1).unwrap();
2332        let cmap = font.cmap().unwrap();
2333        let (index, record, _) = cmap.best_subtable().unwrap();
2334        assert_eq!(
2335            (index, record.platform_id(), record.encoding_id()),
2336            (0, PlatformId::Windows, WINDOWS_UNICODE_BMP_ENCODING)
2337        );
2338    }
2339
2340    #[test]
2341    fn best_subtable_symbol() {
2342        let font = FontRef::new(font_test_data::CMAP4_SYMBOL_PUA).unwrap();
2343        let cmap = font.cmap().unwrap();
2344        let (index, record, _) = cmap.best_subtable().unwrap();
2345        assert!(record.is_symbol());
2346        assert_eq!(
2347            (index, record.platform_id(), record.encoding_id()),
2348            (0, PlatformId::Windows, WINDOWS_SYMBOL_ENCODING)
2349        );
2350    }
2351
2352    #[test]
2353    fn uvs_subtable() {
2354        let font = FontRef::new(font_test_data::CMAP14_FONT1).unwrap();
2355        let cmap = font.cmap().unwrap();
2356        let (index, _) = cmap.uvs_subtable().unwrap();
2357        assert_eq!(index, 0);
2358    }
2359}