Skip to main content

font_model/
cmap.rs

1//! Character maps: [`Cmap`], [`CmapSubtable`], and [`CodePointSet`].
2//!
3//! This module carries **format 4** (the BMP segment/delta form every TrueType
4//! font has) and **format 12** (segmented coverage above the BMP, plus
5//! everything below it). Both directions are modelled: decode a subtable into
6//! the owned model and encode it back to bytes. That symmetry is what lets an
7//! editor round-trip a font's `cmap` through a config format without losing
8//! the mapping.
9//!
10//! # Invariants
11//!
12//! A [`CmapSubtable`] is **sorted and non-overlapping**: codepoints ascend
13//! strictly across segments. [`Cmap::validate`] is where that is checked and
14//! [`ModelError::NonMonotonicCmap`] is what names the offending pair.
15//!
16//! ```
17//! use font_model::{Cmap, CodePointSet, GlyphId};
18//!
19//! // Build a format-12 subtable over an astral plane plus a BMP run, then
20//! // encode and decode it back.
21//! let sub = font_model::from_entries(
22//!     &[(0x41, GlyphId::new(1)), (0x1F600, GlyphId::new(2))],
23//!     12,
24//! );
25//! let bytes = sub.encode();
26//! let back = Cmap::decode_subtable(&bytes).expect("decodes");
27//! assert_eq!(back.lookup(0x41), Some(GlyphId::new(1)));
28//! assert_eq!(back.lookup(0x1F600), Some(GlyphId::new(2)));
29//! assert_eq!(back.lookup(0x42), None);
30//!
31//! // The codepoint view is the sorted, mergeable set of mapped codepoints.
32//! let set = sub.codepoints();
33//! assert_eq!(set.len(), 2);
34//! assert!(set.contains(0x1F600));
35//! ```
36
37use alloc::vec;
38use alloc::vec::Vec;
39
40use crate::error::ModelError;
41use crate::GlyphId;
42
43/// A sorted, mergeable set of codepoints.
44///
45/// The set is the currency of every subsetting operation: it is what
46/// [`Cmap::codepoints`] returns and what [`crate::Font::subset`] consumes.
47/// Insertion keeps it sorted and duplicate-free.
48#[derive(Debug, Clone, Default, PartialEq, Eq)]
49pub struct CodePointSet {
50    cps: Vec<u32>,
51}
52
53impl CodePointSet {
54    /// An empty set.
55    #[must_use]
56    pub fn new() -> Self {
57        CodePointSet { cps: Vec::new() }
58    }
59
60    /// A set from any iterator of codepoints: sorted and de-duplicated.
61    #[must_use]
62    pub fn from_iter_raw(iter: impl IntoIterator<Item = u32>) -> Self {
63        let mut cps: Vec<u32> = iter.into_iter().collect();
64        cps.sort_unstable();
65        cps.dedup();
66        CodePointSet { cps }
67    }
68
69    /// The codepoints, ascending.
70    #[must_use]
71    pub fn as_slice(&self) -> &[u32] {
72        &self.cps
73    }
74
75    /// Number of codepoints.
76    #[must_use]
77    pub fn len(&self) -> usize {
78        self.cps.len()
79    }
80
81    /// True when the set holds nothing.
82    #[must_use]
83    pub fn is_empty(&self) -> bool {
84        self.cps.is_empty()
85    }
86
87    /// Insert a codepoint, keeping the set sorted and unique.
88    pub fn insert(&mut self, cp: u32) {
89        match self.cps.binary_search(&cp) {
90            Ok(_) => {}
91            Err(at) => self.cps.insert(at, cp),
92        }
93    }
94
95    /// True when `cp` is in the set.
96    #[must_use]
97    pub fn contains(&self, cp: u32) -> bool {
98        self.cps.binary_search(&cp).is_ok()
99    }
100
101    /// Iterate the codepoints, ascending.
102    pub fn iter(&self) -> core::slice::Iter<'_, u32> {
103        self.cps.iter()
104    }
105
106    /// The union of two sets.
107    #[must_use]
108    pub fn union(&self, other: &CodePointSet) -> CodePointSet {
109        let mut cps = self.cps.clone();
110        cps.extend_from_slice(&other.cps);
111        cps.sort_unstable();
112        cps.dedup();
113        CodePointSet { cps }
114    }
115
116    /// The intersection of two sets.
117    #[must_use]
118    pub fn intersection(&self, other: &CodePointSet) -> CodePointSet {
119        let cps = self
120            .cps
121            .iter()
122            .copied()
123            .filter(|cp| other.contains(*cp))
124            .collect();
125        CodePointSet { cps }
126    }
127
128    /// `self` minus `other`.
129    #[must_use]
130    pub fn difference(&self, other: &CodePointSet) -> CodePointSet {
131        let cps = self
132            .cps
133            .iter()
134            .copied()
135            .filter(|cp| !other.contains(*cp))
136            .collect();
137        CodePointSet { cps }
138    }
139
140    /// True when every codepoint of `self` is also in `other`.
141    #[must_use]
142    pub fn is_subset_of(&self, other: &CodePointSet) -> bool {
143        self.cps.iter().all(|cp| other.contains(*cp))
144    }
145}
146
147/// One segment of a modelled subtable: an inclusive codepoint run.
148///
149/// Ascending and non-overlapping across the subtable. The glyph at
150/// `first_glyph` covers `start`, and — unless the owning subtable supplies an
151/// explicit glyph array for this segment — each subsequent codepoint takes the
152/// next glyph id.
153#[derive(Debug, Clone, Copy, PartialEq, Eq)]
154pub struct Segment {
155    /// First codepoint of the run, as a `u32` (format 12 goes above the BMP).
156    pub start: u32,
157    /// Last codepoint of the run, inclusive.
158    pub end: u32,
159    /// The glyph id at `start`. When the subtable carries an explicit glyph
160    /// array for this segment, that array is authoritative and this is only
161    /// its first entry.
162    pub first_glyph: u32,
163}
164
165/// The decoded, owned form of one `cmap` subtable.
166///
167/// Both modelled formats are *segmented coverage*: an ascending list of
168/// `[start, end]` ranges whose glyph ids either run consecutively
169/// (`first_glyph + (cp − start)`, format 12 and format 4's `idDelta` path) or
170/// come from an explicit array (format 4's `glyphIndexArray`).
171///
172/// Format 4's glyph-index array is normalised away on decode: a segment that
173/// used the array becomes a segment whose glyphs are consecutive only if they
174/// genuinely are; otherwise the array values are kept as a per-codepoint
175/// table. Both encode back to a spec-valid subtable.
176#[derive(Debug, Clone, PartialEq, Eq)]
177pub enum CmapSubtable {
178    /// Format 4: the BMP segment/delta form.
179    Format4 {
180        /// Segments, ascending and non-overlapping.
181        segments: Vec<Segment>,
182        /// Explicit glyph ids for format-4 segments that used the
183        /// `glyphIndexArray`; entry `k` belongs to segment `k` and has
184        /// `end − start + 1` entries (a `0` entry means "not mapped").
185        glyph_ids: Vec<Vec<u16>>,
186    },
187    /// Format 12: segmented coverage, `u32` codepoints.
188    Format12 {
189        /// Segments, ascending and non-overlapping.
190        segments: Vec<Segment>,
191    },
192}
193
194impl CmapSubtable {
195    /// An empty format-4 subtable.
196    #[must_use]
197    pub fn empty_format4() -> Self {
198        CmapSubtable::Format4 {
199            segments: Vec::new(),
200            glyph_ids: Vec::new(),
201        }
202    }
203
204    /// An empty format-12 subtable.
205    #[must_use]
206    pub fn empty_format12() -> Self {
207        CmapSubtable::Format12 {
208            segments: Vec::new(),
209        }
210    }
211
212    /// The format number this subtable encodes as (4 or 12).
213    #[must_use]
214    pub const fn format(&self) -> u16 {
215        match self {
216            CmapSubtable::Format4 { .. } => 4,
217            CmapSubtable::Format12 { .. } => 12,
218        }
219    }
220
221    /// Map a codepoint to a glyph. `None` for "not mapped": outside the
222    /// subtable's plane, in a hole of an explicit glyph array, mapped to
223    /// glyph 0, or resolving to a glyph id beyond the `u16` glyph space.
224    #[must_use]
225    pub fn lookup(&self, cp: u32) -> Option<GlyphId> {
226        let (segments, glyph_ids) = match self {
227            CmapSubtable::Format4 {
228                segments,
229                glyph_ids,
230            } => {
231                if cp > 0xFFFF {
232                    return None;
233                }
234                (segments, glyph_ids.as_slice())
235            }
236            CmapSubtable::Format12 { segments } => (segments, &[][..]),
237        };
238        let idx = find_segment(segments, cp)?;
239        let seg = segments.get(idx)?;
240        let explicit = glyph_ids.get(idx).filter(|arr| !arr.is_empty());
241        let gid: u32 = match explicit {
242            // Explicit array: entry `k` of segment `idx` covers
243            // `seg.start + k`, and a zero entry is a hole.
244            Some(arr) => u32::from(
245                arr.get(usize::try_from(cp - seg.start).unwrap_or(usize::MAX))
246                    .copied()
247                    .unwrap_or(0),
248            ),
249            // An absent *or empty* array means the run is a delta segment.
250            None => {
251                // Consecutive run: glyph = first_glyph + (cp - start). A run
252                // that would step past the glyph space clamps rather than
253                // wrapping — a wrapped id would alias an unrelated glyph.
254                seg.first_glyph
255                    .wrapping_add(cp.wrapping_sub(seg.start))
256                    .min(u32::from(u16::MAX))
257            }
258        };
259        let gid = u16::try_from(gid).ok().filter(|&g| g != 0)?;
260        Some(GlyphId::new(gid))
261    }
262
263    /// The mapped codepoints, ascending.
264    #[must_use]
265    pub fn codepoints(&self) -> CodePointSet {
266        let (segments, glyph_ids) = match self {
267            CmapSubtable::Format4 {
268                segments,
269                glyph_ids,
270            } => (segments, glyph_ids.as_slice()),
271            CmapSubtable::Format12 { segments } => (segments, &[][..]),
272        };
273        let mut set = CodePointSet::new();
274        for (idx, seg) in segments.iter().enumerate() {
275            for cp in seg.start..=seg.end {
276                // An explicit array may leave holes, so test each codepoint.
277                if self.lookup(cp).is_some() {
278                    set.insert(cp);
279                }
280                let _ = glyph_ids.get(idx);
281            }
282        }
283        set
284    }
285
286    /// Every `(codepoint, glyph)` pair, ascending by codepoint. The inverse of
287    /// the encode path and what a writer iterates.
288    pub fn entries(&self) -> Vec<(u32, GlyphId)> {
289        let mut out = Vec::new();
290        for cp in self.codepoints().iter() {
291            if let Some(gid) = self.lookup(*cp) {
292                out.push((*cp, gid));
293            }
294        }
295        out
296    }
297
298    /// The segments, ascending. Empty for a subtable that maps nothing.
299    #[must_use]
300    pub fn segments(&self) -> &[Segment] {
301        match self {
302            CmapSubtable::Format4 { segments, .. } | CmapSubtable::Format12 { segments } => {
303                segments
304            }
305        }
306    }
307
308    /// The explicit glyph-id arrays, one per format-4 segment; an empty inner
309    /// `Vec` means the segment is a delta (consecutive-glyph) segment.
310    #[must_use]
311    pub fn glyph_arrays(&self) -> &[Vec<u16>] {
312        match self {
313            CmapSubtable::Format4 { glyph_ids, .. } => glyph_ids,
314            CmapSubtable::Format12 { .. } => &[],
315        }
316    }
317
318    /// Number of codepoints that map to a glyph.
319    #[must_use]
320    pub fn len(&self) -> usize {
321        self.codepoints().len()
322    }
323
324    /// True when nothing maps.
325    #[must_use]
326    pub fn is_empty(&self) -> bool {
327        self.len() == 0
328    }
329
330    /// Encode to `cmap` subtable bytes (no table header, just the subtable).
331    ///
332    /// The output is spec-valid: format 4 ends with the mandatory
333    /// `0xFFFF` terminator segment, and every segment is ascending.
334    #[must_use]
335    pub fn encode(&self) -> Vec<u8> {
336        match self {
337            CmapSubtable::Format4 { .. } => self.encode_format4(),
338            CmapSubtable::Format12 { .. } => self.encode_format12(),
339        }
340    }
341
342    /// Encode as a format-4 subtable.
343    #[must_use]
344    pub fn encode_format4(&self) -> Vec<u8> {
345        // One encoded segment per modelled segment. The model already knows
346        // which segments carry explicit glyph ids, so this is a straight
347        // transcription rather than a re-derivation.
348        let (segments, glyph_ids) = match self {
349            CmapSubtable::Format4 {
350                segments,
351                glyph_ids,
352            } => (segments.as_slice(), glyph_ids.as_slice()),
353            CmapSubtable::Format12 { segments } => (segments.as_slice(), &[][..]),
354        };
355        struct Plan {
356            start: u32,
357            end: u32,
358            delta: i16,
359            /// Explicit glyph ids; empty means "use the delta".
360            array: Vec<u16>,
361        }
362        let mut plans: Vec<Plan> = Vec::new();
363        for (idx, seg) in segments.iter().enumerate() {
364            if seg.start > 0xFFFE {
365                continue;
366            }
367            let end = seg.end.min(0xFFFE);
368            if seg.start > end {
369                continue;
370            }
371            let array: Vec<u16> = glyph_ids
372                .get(idx)
373                .filter(|a| !a.is_empty())
374                .map(|a| {
375                    a.iter()
376                        .copied()
377                        .take(usize::try_from(end - seg.start + 1).unwrap_or(0))
378                        .collect()
379                })
380                .unwrap_or_default();
381            plans.push(Plan {
382                start: seg.start,
383                end,
384                // A delta segment stores `glyph = (cp + idDelta) mod 2^16`, and
385                // `first_glyph = start + idDelta`, so `idDelta` inverts exactly.
386                delta: (seg.first_glyph as i32 - seg.start as i32) as i16,
387                array,
388            });
389        }
390        // The mandatory terminator segment: start = end = 0xFFFF, with
391        // idDelta = 1 so that 0xFFFF + 1 == 0 (glyph 0, "not mapped").
392        plans.push(Plan {
393            start: 0xFFFF,
394            end: 0xFFFF,
395            delta: 1,
396            array: Vec::new(),
397        });
398        let final_plans = plans;
399        let seg_count = final_plans.len();
400        let seg_x2 = 2 * seg_count as u16;
401        let entry_selector = {
402            let mut e = 0u16;
403            while (1usize << (e + 1)) <= seg_count {
404                e += 1;
405            }
406            e
407        };
408        let search_range = 2u16.wrapping_mul(1u16 << entry_selector);
409        let range_shift = seg_x2.wrapping_sub(search_range);
410
411        // `glyphIndexArray` sits after `idRangeOffset`. An `idRangeOffset` is a
412        // u16 *element* offset measured from its own slot:
413        // (ro / 2) + (cp − start) + seg − segCount == the array index, so the
414        // needed value is (array index at cp == start) + segCount − seg.
415        let mut glyph_array: Vec<u16> = Vec::new();
416        let mut range_offsets: Vec<u16> = Vec::with_capacity(seg_count);
417        for (seg, plan) in final_plans.iter().enumerate() {
418            if plan.array.is_empty() {
419                range_offsets.push(0);
420            } else {
421                let ro = 2 * (glyph_array.len() + seg_count - seg);
422                range_offsets.push(u16::try_from(ro).unwrap_or(0));
423                glyph_array.extend_from_slice(&plan.array);
424            }
425        }
426        let length = 16 + 8 * seg_count + 2 * glyph_array.len();
427        let mut out = Vec::with_capacity(length);
428        out.extend_from_slice(&4u16.to_be_bytes());
429        out.extend_from_slice(&(length as u16).to_be_bytes());
430        out.extend_from_slice(&0u16.to_be_bytes()); // language
431        out.extend_from_slice(&seg_x2.to_be_bytes());
432        out.extend_from_slice(&search_range.to_be_bytes());
433        out.extend_from_slice(&entry_selector.to_be_bytes());
434        out.extend_from_slice(&range_shift.to_be_bytes());
435        for plan in &final_plans {
436            out.extend_from_slice(&u16::try_from(plan.end).unwrap_or(0xFFFF).to_be_bytes());
437        }
438        out.extend_from_slice(&0u16.to_be_bytes()); // reservedPad
439        for plan in &final_plans {
440            out.extend_from_slice(&u16::try_from(plan.start).unwrap_or(0xFFFF).to_be_bytes());
441        }
442        for plan in &final_plans {
443            out.extend_from_slice(&plan.delta.to_be_bytes());
444        }
445        for ro in &range_offsets {
446            out.extend_from_slice(&ro.to_be_bytes());
447        }
448        for g in &glyph_array {
449            out.extend_from_slice(&g.to_be_bytes());
450        }
451        out
452    }
453
454    /// Encode as a format-12 subtable.
455    #[must_use]
456    pub fn encode_format12(&self) -> Vec<u8> {
457        let groups = self.format12_groups();
458        let length = 16 + 12 * groups.len();
459        let mut out = Vec::with_capacity(length);
460        out.extend_from_slice(&12u16.to_be_bytes());
461        out.extend_from_slice(&0u16.to_be_bytes()); // reserved
462        out.extend_from_slice(&(length as u32).to_be_bytes());
463        out.extend_from_slice(&0u32.to_be_bytes()); // language
464        out.extend_from_slice(&(groups.len() as u32).to_be_bytes());
465        for (start, end, gid) in &groups {
466            out.extend_from_slice(&start.to_be_bytes());
467            out.extend_from_slice(&end.to_be_bytes());
468            out.extend_from_slice(&gid.to_be_bytes());
469        }
470        out
471    }
472
473    /// Decode a subtable from its bytes.
474    ///
475    /// # Errors
476    /// [`ModelError::UnsupportedCmapFormat`] for anything other than formats 4
477    /// and 12; [`ModelError::Parse`] when the byte layout is inconsistent.
478    #[allow(clippy::result_large_err)]
479    pub fn decode(data: &[u8]) -> Result<Self, ModelError> {
480        let format = read_u16(data, 0).ok_or_else(truncated)?;
481        match format {
482            4 => Self::decode_format4(data),
483            12 => Self::decode_format12(data),
484            other => Err(ModelError::UnsupportedCmapFormat { format: other }),
485        }
486    }
487
488    /// Decode a format-4 subtable.
489    ///
490    /// # Errors
491    /// [`ModelError::Parse`] when the segment arrays are inconsistent.
492    #[allow(clippy::result_large_err)]
493    pub fn decode_format4(data: &[u8]) -> Result<Self, ModelError> {
494        let seg_x2 = read_u16(data, 6).ok_or_else(truncated)?;
495        if seg_x2 == 0 || seg_x2 % 2 != 0 {
496            return Err(ModelError::Parse {
497                message: alloc::format!(
498                    "format 4 segCountX2 {seg_x2} is not a positive even count"
499                ),
500            });
501        }
502        let seg_count = usize::from(seg_x2 / 2);
503        let ends_at = 14usize;
504        let starts_at = ends_at + 2 * seg_count + 2; // + reservedPad
505        let deltas_at = starts_at + 2 * seg_count;
506        let ranges_at = deltas_at + 2 * seg_count;
507        // The glyphIndexArray begins after the four segment arrays.
508        let mut segments = Vec::with_capacity(seg_count);
509        let mut glyph_ids = Vec::with_capacity(seg_count);
510        for i in 0..seg_count {
511            let end = read_u16(data, ends_at + 2 * i).ok_or_else(truncated)?;
512            let start = read_u16(data, starts_at + 2 * i).ok_or_else(truncated)?;
513            let delta = read_i16(data, deltas_at + 2 * i).ok_or_else(truncated)?;
514            let range_offset = read_u16(data, ranges_at + 2 * i).ok_or_else(truncated)?;
515            // A segment whose start is past its end describes nothing; skip it
516            // rather than materialising a zero-width run.
517            if start > end {
518                segments.push(Segment {
519                    start: u32::from(start),
520                    end: u32::from(start),
521                    first_glyph: 0,
522                });
523                glyph_ids.push(vec![0]);
524                continue;
525            }
526            let width = usize::from(end - start) + 1;
527            if range_offset == 0 {
528                // idDelta path: glyph = (cp + delta) mod 65536, so the run's
529                // first glyph is `start + delta`.
530                segments.push(Segment {
531                    start: u32::from(start),
532                    end: u32::from(end),
533                    first_glyph: u32::from(u16::wrapping_add(start, delta as u16)),
534                });
535                glyph_ids.push(Vec::new());
536            } else {
537                // idRangeOffset is a u16 element offset from its own slot:
538                // (ro / 2) + (cp − start) + seg − segCount == array index.
539                // The spec: `idRangeOffset` is a *byte* offset from the address of its own
540                // slot (the `idRangeOffset` entry for this segment), and the
541                // value there is the glyph for `start`.
542                let base = ranges_at + 2 * i + usize::from(range_offset);
543                let mut arr = Vec::with_capacity(width);
544                for k in 0..width {
545                    arr.push(read_u16(data, base + 2 * k).unwrap_or(0));
546                }
547                // Normalise: an array that happens to be an arithmetic run
548                // collapses to a delta segment.
549                let linear = arr
550                    .first()
551                    .copied()
552                    .map(|first| {
553                        arr.iter().enumerate().all(|(k, &g)| {
554                            g == u16::wrapping_add(first, u16::try_from(k).unwrap_or(0))
555                        })
556                    })
557                    .unwrap_or(false);
558                let first_glyph = u32::from(arr.first().copied().unwrap_or(0));
559                segments.push(Segment {
560                    start: u32::from(start),
561                    end: u32::from(end),
562                    first_glyph,
563                });
564                glyph_ids.push(if linear { Vec::new() } else { arr });
565            }
566        }
567        Ok(CmapSubtable::Format4 {
568            segments,
569            glyph_ids,
570        })
571    }
572
573    /// Decode a format-12 subtable.
574    ///
575    /// # Errors
576    /// [`ModelError::Parse`] when the group array is inconsistent.
577    #[allow(clippy::result_large_err)]
578    pub fn decode_format12(data: &[u8]) -> Result<Self, ModelError> {
579        let n_groups = read_u32(data, 12).ok_or_else(truncated)?;
580        let n = usize::try_from(n_groups).map_err(|_| ModelError::Parse {
581            message: alloc::format!("format 12 declares {n_groups} groups"),
582        })?;
583        let mut segments = Vec::with_capacity(n);
584        for i in 0..n {
585            let at = 16 + 12 * i;
586            let start = read_u32(data, at).ok_or_else(truncated)?;
587            let end = read_u32(data, at + 4).ok_or_else(truncated)?;
588            let start_gid = read_u32(data, at + 8).ok_or_else(truncated)?;
589            if end < start {
590                return Err(ModelError::Parse {
591                    message: alloc::format!(
592                        "format 12 group {i} ends (U+{end:X}) before it starts (U+{start:X})"
593                    ),
594                });
595            }
596            segments.push(Segment {
597                start,
598                end,
599                first_glyph: start_gid,
600            });
601        }
602        Ok(CmapSubtable::Format12 { segments })
603    }
604
605    /// The BMP-only entries, ascending — the working set for a format-4
606    /// encode, and what a caller checks to decide whether a subtable needs a
607    /// format-12 companion.
608    ///
609    /// ```
610    /// use font_model::{from_entries, GlyphId};
611    ///
612    /// let sub = from_entries(&[(0x41, GlyphId::new(1)), (0x1F600, GlyphId::new(2))], 12);
613    /// assert_eq!(sub.bmp_entries(), vec![(0x41, 1)]);
614    /// ```
615    #[must_use]
616    pub fn bmp_entries(&self) -> Vec<(u32, u32)> {
617        self.entries()
618            .into_iter()
619            .filter(|(cp, _)| *cp <= 0xFFFF)
620            .map(|(cp, gid)| (cp, gid.to_u32()))
621            .collect()
622    }
623
624    /// Format-12 groups for the whole range, ascending.
625    fn format12_groups(&self) -> Vec<(u32, u32, u32)> {
626        let entries = self.entries();
627        let mut groups: Vec<(u32, u32, u32)> = Vec::new();
628        let mut i = 0usize;
629        while i < entries.len() {
630            let Some(&(start, gid)) = entries.get(i) else {
631                break;
632            };
633            let mut end = start;
634            let mut j = i + 1;
635            while let Some(&(cp, g)) = entries.get(j) {
636                if cp != end + 1 || g.to_u32() != gid.to_u32().wrapping_add(end + 1 - start) {
637                    break;
638                }
639                end = cp;
640                j += 1;
641            }
642            groups.push((start, end, gid.to_u32()));
643            i = j;
644        }
645        groups
646    }
647}
648
649/// A font's character map: one or more modelled subtables.
650///
651/// Lookup tries the subtables in order and returns the first hit, mirroring
652/// the parser's spec-preference scan while staying in the owned model.
653#[derive(Debug, Clone, Default, PartialEq, Eq)]
654pub struct Cmap {
655    subtables: Vec<CmapSubtable>,
656}
657
658impl Cmap {
659    /// An empty `cmap` (nothing maps).
660    #[must_use]
661    pub fn new() -> Self {
662        Cmap {
663            subtables: Vec::new(),
664        }
665    }
666
667    /// A `cmap` with one empty format-4 subtable — the minimum every font
668    /// carries.
669    #[must_use]
670    pub fn format4() -> Self {
671        Cmap {
672            subtables: vec![CmapSubtable::empty_format4()],
673        }
674    }
675
676    /// A `cmap` with one empty format-12 subtable.
677    #[must_use]
678    pub fn format12() -> Self {
679        Cmap {
680            subtables: vec![CmapSubtable::empty_format12()],
681        }
682    }
683
684    /// The subtables, in lookup order.
685    #[must_use]
686    pub fn subtables(&self) -> &[CmapSubtable] {
687        &self.subtables
688    }
689
690    /// The subtables, mutably.
691    pub fn subtables_mut(&mut self) -> &mut Vec<CmapSubtable> {
692        &mut self.subtables
693    }
694
695    /// The subtable a writer should emit first: format 12 when the font has
696    /// one (it covers every codepoint), otherwise the first format-4 subtable.
697    /// `None` for an empty `cmap`.
698    #[must_use]
699    pub fn preferred(&self) -> Option<&CmapSubtable> {
700        self.subtables
701            .iter()
702            .find(|s| s.format() == 12)
703            .or_else(|| self.subtables.first())
704    }
705
706    /// Map a codepoint to a glyph across every subtable.
707    #[must_use]
708    pub fn lookup(&self, cp: u32) -> Option<GlyphId> {
709        self.subtables.iter().find_map(|s| s.lookup(cp))
710    }
711
712    /// The union of every subtable's mapped codepoints.
713    #[must_use]
714    pub fn codepoints(&self) -> CodePointSet {
715        let mut set = CodePointSet::new();
716        for s in &self.subtables {
717            for cp in s.codepoints().iter() {
718                set.insert(*cp);
719            }
720        }
721        set
722    }
723
724    /// Number of subtables.
725    #[must_use]
726    pub fn len(&self) -> usize {
727        self.subtables.len()
728    }
729
730    /// True when the `cmap` carries no subtable.
731    #[must_use]
732    pub fn is_empty(&self) -> bool {
733        self.subtables.is_empty()
734    }
735
736    /// Encode the whole `cmap` table (header + encoding records + subtables),
737    /// writing one encoding record per subtable: `(3, 1)` for format 4 and
738    /// `(3, 10)` for format 12.
739    #[must_use]
740    pub fn encode(&self) -> Vec<u8> {
741        let n = self.subtables.len();
742        let header = 4 + 8 * n;
743        let mut offsets = Vec::with_capacity(n);
744        let mut bodies = Vec::with_capacity(n);
745        let mut at = header;
746        for sub in &self.subtables {
747            offsets.push(at);
748            let body = sub.encode();
749            // Subtables are 4-byte aligned within the table.
750            at += body.len();
751            at = (at + 3) & !3;
752            bodies.push(body);
753        }
754        let mut out = Vec::with_capacity(at);
755        out.extend_from_slice(&0u16.to_be_bytes()); // version
756        out.extend_from_slice(&(n as u16).to_be_bytes());
757        for (i, sub) in self.subtables.iter().enumerate() {
758            let (platform, encoding) = if sub.format() == 12 {
759                (3u16, 10u16)
760            } else {
761                (3, 1)
762            };
763            out.extend_from_slice(&platform.to_be_bytes());
764            out.extend_from_slice(&encoding.to_be_bytes());
765            out.extend_from_slice(
766                &u32::try_from(offsets.get(i).copied().unwrap_or(0))
767                    .unwrap_or(0)
768                    .to_be_bytes(),
769            );
770        }
771        for body in &bodies {
772            out.extend_from_slice(body);
773            while out.len() % 4 != 0 {
774                out.push(0);
775            }
776        }
777        out
778    }
779
780    /// Decode a whole `cmap` table: header, encoding records, and every
781    /// subtable they point at.
782    ///
783    /// # Errors
784    /// [`ModelError::Parse`] when the header or records are inconsistent, or
785    /// [`ModelError::UnsupportedCmapFormat`] for a subtable format outside the
786    /// modelled set.
787    #[allow(clippy::result_large_err)]
788    pub fn decode(data: &[u8]) -> Result<Self, ModelError> {
789        let num_tables = read_u16(data, 2).ok_or_else(truncated)?;
790        let mut out = Vec::new();
791        for i in 0..usize::from(num_tables) {
792            let at = 4 + 8 * i;
793            let offset = read_u32(data, at + 4).ok_or_else(truncated)?;
794            let start = usize::try_from(offset).map_err(|_| truncated())?;
795            let body = data.get(start..).ok_or_else(truncated)?;
796            out.push(CmapSubtable::decode(body)?);
797        }
798        Ok(Cmap { subtables: out })
799    }
800
801    /// Decode a standalone subtable (no `cmap` header) — what
802    /// [`CmapSubtable::encode`] produced.
803    ///
804    /// # Errors
805    /// See [`CmapSubtable::decode`].
806    #[allow(clippy::result_large_err)]
807    pub fn decode_subtable(data: &[u8]) -> Result<CmapSubtable, ModelError> {
808        CmapSubtable::decode(data)
809    }
810
811    /// An empty format-4 subtable, for building.
812    #[must_use]
813    pub fn subtable_format4() -> CmapSubtable {
814        CmapSubtable::empty_format4()
815    }
816
817    /// An empty format-12 subtable, for building.
818    #[must_use]
819    pub fn subtable_format12() -> CmapSubtable {
820        CmapSubtable::empty_format12()
821    }
822
823    /// Check the monotonicity invariant across every subtable.
824    ///
825    /// # Errors
826    /// [`ModelError::NonMonotonicCmap`] naming the subtable index and the two
827    /// codepoints that broke the ordering.
828    pub fn validate(&self) -> Result<(), ModelError> {
829        for (si, sub) in self.subtables.iter().enumerate() {
830            // Checked at the *segment* level rather than the entry level: two
831            // overlapping segments de-duplicate into a single entry, so an
832            // entry walk would not see the overlap at all. The segments must
833            // ascend, and each must start strictly after the previous one ends.
834            let mut previous_end: Option<u32> = None;
835            for seg in sub.segments() {
836                if let Some(end) = previous_end {
837                    if seg.start <= end {
838                        return Err(ModelError::NonMonotonicCmap {
839                            subtable: si,
840                            previous: end,
841                            current: seg.start,
842                        });
843                    }
844                }
845                previous_end = Some(seg.end);
846            }
847        }
848        Ok(())
849    }
850}
851
852/// Insert a `(codepoint, glyph)` pair into a subtable, extending the run it
853/// belongs to when the glyph ids stay consecutive.
854///
855/// Returns the rebuilt subtable; the caller owns it (the model stores owned
856/// subtables, and this keeps `CmapSubtable` a plain data type).
857#[must_use]
858pub fn insert_entry(sub: &CmapSubtable, cp: u32, gid: GlyphId) -> CmapSubtable {
859    // Rebuild from the full entry list: correctness over cleverness, and the
860    // entry counts involved are small.
861    let mut entries = sub.entries();
862    entries.retain(|(c, _)| *c != cp);
863    entries.push((cp, gid));
864    entries.sort_by_key(|(c, _)| *c);
865    from_entries(&entries, sub.format())
866}
867
868/// Build a subtable of the given format from a sorted `(codepoint, glyph)`
869/// entry list, collapsing consecutive runs.
870#[must_use]
871pub fn from_entries(entries: &[(u32, GlyphId)], format: u16) -> CmapSubtable {
872    // Sorting here rather than trusting the caller: the invariant every
873    // downstream consumer relies on (ascending, de-duplicated) is worth more
874    // than the O(n log n) on a list that is usually already sorted. A repeated
875    // codepoint keeps its *last* glyph, matching an overwrite.
876    let mut sorted: Vec<(u32, GlyphId)> = entries.to_vec();
877    sorted.sort_by_key(|(cp, _)| *cp);
878    sorted.dedup_by(|a, b| {
879        if a.0 == b.0 {
880            b.1 = a.1;
881            true
882        } else {
883            false
884        }
885    });
886    let entries = sorted.as_slice();
887    // Group the entries into maximal runs of *consecutive codepoints*,
888    // recording whether each run's glyph ids are also consecutive. Format 12
889    // can only express the latter, so it splits the runs further; format 4
890    // uses the explicit `glyphIndexArray` for a run that is not consecutive.
891    struct Run {
892        start: u32,
893        end: u32,
894        first_glyph: u32,
895        consecutive: bool,
896    }
897    let mut runs: Vec<Run> = Vec::new();
898    let mut i = 0usize;
899    while i < entries.len() {
900        let Some(&(start, gid)) = entries.get(i) else {
901            break;
902        };
903        let first_glyph = gid.to_u32();
904        let mut end = start;
905        let mut j = i + 1;
906        while let Some(&(cp, _)) = entries.get(j) {
907            if cp != end + 1 {
908                break;
909            }
910            end = cp;
911            j += 1;
912        }
913        let consecutive = entries
914            .get(i..j)
915            .unwrap_or(&[])
916            .iter()
917            .enumerate()
918            .all(|(k, (_, g))| g.to_u32() == first_glyph.wrapping_add(k as u32));
919        runs.push(Run {
920            start,
921            end,
922            first_glyph,
923            consecutive,
924        });
925        i = j;
926    }
927    if format == 12 {
928        // A format-12 group stores only its first glyph id, so a run whose
929        // glyph ids are *not* consecutive has to be split back into maximal
930        // sub-runs that are.
931        let mut segments: Vec<Segment> = Vec::new();
932        for run in runs {
933            if run.consecutive {
934                segments.push(Segment {
935                    start: run.start,
936                    end: run.end,
937                    first_glyph: run.first_glyph,
938                });
939                continue;
940            }
941            let width = usize::try_from(run.end - run.start + 1).unwrap_or(0);
942            let slice = match (i_of(entries, run.start), width) {
943                (Some(at), width) => entries.get(at..at.saturating_add(width)),
944                _ => None,
945            };
946            let Some(slice) = slice else { continue };
947            let mut k = 0usize;
948            while k < slice.len() {
949                let Some(&(s, g)) = slice.get(k) else {
950                    break;
951                };
952                let mut e = s;
953                let mut m = k + 1;
954                while let Some(&(ncp, ng)) = slice.get(m) {
955                    if ncp != e + 1 || ng.to_u32() != g.to_u32().wrapping_add(e + 1 - s) {
956                        break;
957                    }
958                    e = ncp;
959                    m += 1;
960                }
961                segments.push(Segment {
962                    start: s,
963                    end: e,
964                    first_glyph: g.to_u32(),
965                });
966                k = m;
967            }
968        }
969        return CmapSubtable::Format12 { segments };
970    }
971    // Format 4 is BMP-only, and U+FFFF is reserved for the terminator
972    // segment, so the highest mappable codepoint is U+FFFE.
973    let mut segments = Vec::new();
974    let mut glyph_ids: Vec<Vec<u16>> = Vec::new();
975    for run in runs {
976        if run.start > 0xFFFE {
977            continue;
978        }
979        let start = run.start;
980        let end = run.end.min(0xFFFE);
981        segments.push(Segment {
982            start,
983            end,
984            first_glyph: run.first_glyph,
985        });
986        if run.consecutive {
987            // Expressible as a delta (mod 2^16).
988            glyph_ids.push(Vec::new());
989        } else {
990            // Anything else needs the explicit array, holes included.
991            let arr = (start..=end)
992                .map(|cp| {
993                    entries
994                        .iter()
995                        .find(|(c, _)| *c == cp)
996                        .and_then(|(_, g)| u16::try_from(g.to_u32()).ok())
997                        .unwrap_or(0)
998                })
999                .collect();
1000            glyph_ids.push(arr);
1001        }
1002    }
1003    CmapSubtable::Format4 {
1004        segments,
1005        glyph_ids,
1006    }
1007}
1008
1009/// The index of `cp` in a sorted entry list, `None` when absent.
1010fn i_of(entries: &[(u32, GlyphId)], cp: u32) -> Option<usize> {
1011    entries
1012        .iter()
1013        .position(|(c, _)| *c == cp)
1014        .or_else(|| entries.iter().position(|(c, _)| *c >= cp))
1015}
1016
1017/// Find the segment covering `cp` in an ascending, non-overlapping list.
1018///
1019/// Binary search: the last segment whose `start` is `<= cp` wins, and the
1020/// result must also satisfy `cp <= end`.
1021fn find_segment(segments: &[Segment], cp: u32) -> Option<usize> {
1022    // The comparator never returns `Equal`, so `binary_search_by` always
1023    // returns `Err(insertion_point)` — the index of the first segment starting
1024    // after `cp`. Either arm of the match names that index.
1025    let idx = match segments.binary_search_by(|s| {
1026        if s.start > cp {
1027            core::cmp::Ordering::Greater
1028        } else {
1029            core::cmp::Ordering::Less
1030        }
1031    }) {
1032        Ok(i) | Err(i) => i,
1033    };
1034    let idx = idx.checked_sub(1)?;
1035    let seg = segments.get(idx)?;
1036    (cp <= seg.end).then_some(idx)
1037}
1038
1039/// A shared "truncated cmap" parse error.
1040fn truncated() -> ModelError {
1041    ModelError::Parse {
1042        message: alloc::string::String::from("truncated cmap subtable"),
1043    }
1044}
1045
1046/// Big-endian `u16` read, `None` when the buffer is short.
1047fn read_u16(data: &[u8], at: usize) -> Option<u16> {
1048    let bytes: [u8; 2] = data.get(at..at.checked_add(2)?)?.try_into().ok()?;
1049    Some(u16::from_be_bytes(bytes))
1050}
1051
1052/// Big-endian `i16` read.
1053fn read_i16(data: &[u8], at: usize) -> Option<i16> {
1054    read_u16(data, at).map(|v| v as i16)
1055}
1056
1057/// Big-endian `u32` read, `None` when the buffer is short.
1058fn read_u32(data: &[u8], at: usize) -> Option<u32> {
1059    let bytes: [u8; 4] = data.get(at..at.checked_add(4)?)?.try_into().ok()?;
1060    Some(u32::from_be_bytes(bytes))
1061}
1062
1063#[cfg(test)]
1064mod tests {
1065    #![allow(
1066        clippy::unwrap_used,
1067        clippy::expect_used,
1068        clippy::indexing_slicing,
1069        clippy::panic,
1070        clippy::float_cmp
1071    )]
1072    use super::{insert_entry, Cmap, CmapSubtable, CodePointSet};
1073    use crate::{GlyphId, ModelError};
1074    use alloc::vec;
1075    use alloc::vec::Vec;
1076
1077    // Test harness: assertions legitimately panic; the lib target stays
1078    // lint-clean.
1079
1080    /// The format-4 fixture from the OpenType spec's worked example:
1081    /// three segments plus the 0xFFFF terminator, exercising both the
1082    /// `idDelta` path and the `glyphIndexArray` path.
1083    fn spec_format4() -> Vec<u8> {
1084        let mut d = Vec::new();
1085        d.extend_from_slice(&4u16.to_be_bytes()); // format
1086        d.extend_from_slice(&40u16.to_be_bytes()); // length (patched below)
1087        d.extend_from_slice(&0u16.to_be_bytes()); // language
1088        d.extend_from_slice(&6u16.to_be_bytes()); // segCountX2 = 3 segments
1089        d.extend_from_slice(&4u16.to_be_bytes()); // searchRange
1090        d.extend_from_slice(&1u16.to_be_bytes()); // entrySelector
1091        d.extend_from_slice(&2u16.to_be_bytes()); // rangeShift
1092        d.extend_from_slice(&0x0020u16.to_be_bytes()); // end[0]
1093        d.extend_from_slice(&0x007Au16.to_be_bytes()); // end[1]
1094        d.extend_from_slice(&0xFFFFu16.to_be_bytes()); // end[2] terminator
1095        d.extend_from_slice(&0u16.to_be_bytes()); // reservedPad
1096        d.extend_from_slice(&0x0020u16.to_be_bytes()); // start[0]
1097        d.extend_from_slice(&0x0061u16.to_be_bytes()); // start[1]
1098        d.extend_from_slice(&0xFFFFu16.to_be_bytes()); // start[2]
1099        d.extend_from_slice(&0x0028u16.to_be_bytes()); // idDelta[0] 0x20+0x28=0x48
1100        d.extend_from_slice(&0x0000u16.to_be_bytes()); // idDelta[1] (array)
1101        d.extend_from_slice(&0x0001u16.to_be_bytes()); // idDelta[2] -> 0
1102        d.extend_from_slice(&0u16.to_be_bytes()); // idRangeOffset[0]
1103                                                  // idRangeOffset is a byte offset from the address of its own slot;
1104                                                  // the array sits at offset 40 and the slot at 36, so 4.
1105        d.extend_from_slice(&4u16.to_be_bytes()); // idRangeOffset[1]
1106        d.extend_from_slice(&0u16.to_be_bytes()); // idRangeOffset[2]
1107                                                  // glyphIndexArray for segment 1: 'a'..'z' -> glyphs 3, 0, 5, 0, 7 ...
1108        for g in [3u16, 0, 5, 0, 7] {
1109            d.extend_from_slice(&g.to_be_bytes());
1110        }
1111        let len = u16::try_from(d.len()).unwrap_or(0);
1112        d[2..4].copy_from_slice(&len.to_be_bytes());
1113        d
1114    }
1115
1116    #[test]
1117    fn format4_decodes_spec_example() {
1118        let bytes = spec_format4();
1119        let sub = CmapSubtable::decode(&bytes).expect("decodes");
1120        assert_eq!(sub.format(), 4);
1121        // idDelta path: 0x20 -> 0x48.
1122        assert_eq!(sub.lookup(0x20), Some(GlyphId::new(0x48)));
1123        // Array path with holes.
1124        assert_eq!(sub.lookup(0x61), Some(GlyphId::new(3)));
1125        assert_eq!(sub.lookup(0x62), None);
1126        assert_eq!(sub.lookup(0x63), Some(GlyphId::new(5)));
1127        assert_eq!(sub.lookup(0x65), Some(GlyphId::new(7)));
1128        // The terminator maps to glyph 0 == unmapped.
1129        assert_eq!(sub.lookup(0xFFFF), None);
1130        assert_eq!(sub.lookup(0x0000), None);
1131        // Above the BMP.
1132        assert_eq!(sub.lookup(0x1_0000), None);
1133    }
1134
1135    #[test]
1136    fn format4_round_trips_the_spec_example() {
1137        let sub = CmapSubtable::decode(&spec_format4()).expect("decodes");
1138        let bytes = sub.encode();
1139        let back = CmapSubtable::decode(&bytes).expect("re-decodes");
1140        for cp in 0u32..=0xFFFF {
1141            assert_eq!(sub.lookup(cp), back.lookup(cp), "mismatch at U+{cp:04X}");
1142        }
1143        assert_eq!(sub.entries(), back.entries());
1144    }
1145
1146    #[test]
1147    fn format4_round_trips_random_bmp_runs() {
1148        // Every interesting shape: single points, contiguous runs, gaps,
1149        // non-consecutive glyph ids inside a contiguous codepoint run, and the
1150        // U+FFFF sentinel.
1151        let cases: [Vec<(u32, u16)>; 6] = [
1152            vec![(0x41, 1)],
1153            vec![(0x41, 1), (0x42, 2), (0x43, 3)],
1154            vec![(0x41, 9), (0x50, 3)],
1155            vec![(0x41, 5), (0x42, 5), (0x43, 5)],
1156            vec![(0x00, 1), (0x7FFF, 2), (0xFFFE, 3)],
1157            vec![(0x30, 100), (0x39, 109), (0x3A, 200), (0x41, 300)],
1158        ];
1159        for case in cases {
1160            let entries: Vec<(u32, GlyphId)> =
1161                case.iter().map(|(c, g)| (*c, GlyphId::new(*g))).collect();
1162            let sub = super::from_entries(&entries, 4);
1163            let bytes = sub.encode();
1164            let back = CmapSubtable::decode(&bytes).expect("decodes");
1165            for (cp, gid) in &entries {
1166                assert_eq!(back.lookup(*cp), Some(*gid), "case {case:?} at U+{cp:X}");
1167            }
1168            // Unmapped neighbours stay unmapped.
1169            assert_eq!(back.lookup(0x10), None, "case {case:?}");
1170            assert_eq!(back.len(), entries.len(), "case {case:?}");
1171        }
1172    }
1173
1174    #[test]
1175    fn format4_always_appends_the_ffff_terminator() {
1176        let sub = super::from_entries(&[(0x41, GlyphId::new(1))], 4);
1177        let bytes = sub.encode();
1178        let seg_x2 = u16::from_be_bytes([bytes[6], bytes[7]]);
1179        let seg_count = usize::from(seg_x2 / 2);
1180        let ends_at = 14;
1181        let last_end = u16::from_be_bytes([
1182            bytes[ends_at + 2 * (seg_count - 1)],
1183            bytes[ends_at + 2 * (seg_count - 1) + 1],
1184        ]);
1185        assert_eq!(last_end, 0xFFFF, "terminator segment missing");
1186        // `startCode` follows `endCode` plus the reservedPad u16.
1187        let starts_at = ends_at + 2 * seg_count + 2;
1188        let last_start = u16::from_be_bytes([
1189            bytes[starts_at + 2 * (seg_count - 1)],
1190            bytes[starts_at + 2 * (seg_count - 1) + 1],
1191        ]);
1192        assert_eq!(last_start, 0xFFFF, "terminator start missing");
1193    }
1194
1195    #[test]
1196    fn format4_never_maps_the_terminator() {
1197        // Even when the caller tries to map U+FFFF, the terminator segment
1198        // resolves to glyph 0 == unmapped.
1199        let sub = super::from_entries(&[(0x41, GlyphId::new(1)), (0xFFFF, GlyphId::new(7))], 4);
1200        let back = CmapSubtable::decode(&sub.encode()).expect("decodes");
1201        assert_eq!(back.lookup(0xFFFF), None);
1202        assert_eq!(back.lookup(0x41), Some(GlyphId::new(1)));
1203    }
1204
1205    #[test]
1206    fn format12_round_trips_above_the_bmp() {
1207        let entries = vec![
1208            (0x1F600u32, GlyphId::new(10)),
1209            (0x1F601, GlyphId::new(11)),
1210            (0x1F602, GlyphId::new(12)),
1211            (0x20000, GlyphId::new(200)),
1212            (0x41, GlyphId::new(1)),
1213            (0x10FFFF, GlyphId::new(65535)),
1214        ];
1215        let sub = super::from_entries(&entries, 12);
1216        let bytes = sub.encode();
1217        assert_eq!(u16::from_be_bytes([bytes[0], bytes[1]]), 12);
1218        let back = CmapSubtable::decode(&bytes).expect("decodes");
1219        for (cp, gid) in &entries {
1220            assert_eq!(back.lookup(*cp), Some(*gid), "at U+{cp:X}");
1221        }
1222        assert_eq!(back.lookup(0x1F603), None, "past the first group");
1223        assert_eq!(back.lookup(0x1F5FF), None);
1224        // `from_entries` sorts and de-duplicates, so the round trip preserves
1225        // the *set* of entries rather than the input order.
1226        let mut expected = entries.clone();
1227        expected.sort_by_key(|(cp, _)| *cp);
1228        assert_eq!(back.entries(), expected);
1229    }
1230
1231    #[test]
1232    fn format12_handles_a_span_past_the_bmp() {
1233        // A single run crossing the BMP boundary (0xFFFE, 0xFFFF, 0x10000,
1234        // 0x10001) exercises the u32 codepoint path and the group encoder.
1235        let entries: Vec<(u32, GlyphId)> = (0xFFFEu32..=0x10001)
1236            .map(|cp| {
1237                (
1238                    cp,
1239                    GlyphId::new(100 + u16::try_from(cp - 0xFFFE).unwrap_or(0)),
1240                )
1241            })
1242            .collect();
1243        let sub = super::from_entries(&entries, 12);
1244        let back = CmapSubtable::decode(&sub.encode()).expect("decodes");
1245        for (cp, gid) in &entries {
1246            assert_eq!(back.lookup(*cp), Some(*gid));
1247        }
1248    }
1249
1250    #[test]
1251    fn lookup_of_mapped_unmapped_and_surrogate() {
1252        let sub = super::from_entries(
1253            &[
1254                (0x41, GlyphId::new(1)),
1255                (0xD800, GlyphId::new(2)), // a surrogate codepoint, kept raw
1256                (0x1F600, GlyphId::new(3)),
1257            ],
1258            12,
1259        );
1260        assert_eq!(sub.lookup(0x41), Some(GlyphId::new(1)));
1261        assert_eq!(sub.lookup(0x42), None);
1262        assert_eq!(sub.lookup(0xD800), Some(GlyphId::new(2)));
1263        assert_eq!(sub.lookup(0xDFFF), None);
1264        assert_eq!(sub.lookup(0x1F600), Some(GlyphId::new(3)));
1265        assert_eq!(sub.lookup(0x10FFFF), None);
1266    }
1267
1268    #[test]
1269    fn insert_entry_extends_runs() {
1270        let mut sub = Cmap::subtable_format12();
1271        sub = insert_entry(&sub, 0x41, GlyphId::new(1));
1272        sub = insert_entry(&sub, 0x42, GlyphId::new(2));
1273        sub = insert_entry(&sub, 0x44, GlyphId::new(4));
1274        assert_eq!(sub.lookup(0x41), Some(GlyphId::new(1)));
1275        assert_eq!(sub.lookup(0x42), Some(GlyphId::new(2)));
1276        assert_eq!(sub.lookup(0x43), None);
1277        assert_eq!(sub.lookup(0x44), Some(GlyphId::new(4)));
1278        // Overwriting an existing entry keeps the count stable.
1279        sub = insert_entry(&sub, 0x42, GlyphId::new(9));
1280        assert_eq!(sub.lookup(0x42), Some(GlyphId::new(9)));
1281        assert_eq!(sub.len(), 3);
1282        let back = CmapSubtable::decode(&sub.encode()).expect("decodes");
1283        assert_eq!(back.lookup(0x42), Some(GlyphId::new(9)));
1284    }
1285
1286    #[test]
1287    fn codepoint_set_operations() {
1288        let a = CodePointSet::from_iter_raw(vec![3, 1, 2, 2]);
1289        assert_eq!(a.as_slice(), &[1, 2, 3]);
1290        assert_eq!(a.len(), 3);
1291        let mut b = CodePointSet::new();
1292        assert!(b.is_empty());
1293        b.insert(5);
1294        b.insert(1);
1295        b.insert(5);
1296        assert_eq!(b.as_slice(), &[1, 5]);
1297        assert!(b.contains(5));
1298        assert!(!b.contains(4));
1299
1300        let u = a.union(&b);
1301        assert_eq!(u.as_slice(), &[1, 2, 3, 5]);
1302        let i = a.intersection(&b);
1303        assert_eq!(i.as_slice(), &[1]);
1304        let d = a.difference(&b);
1305        assert_eq!(d.as_slice(), &[2, 3]);
1306        assert!(CodePointSet::from_iter_raw(vec![1]).is_subset_of(&b));
1307        assert!(!a.is_subset_of(&b));
1308        assert_eq!(a.iter().copied().collect::<Vec<u32>>(), vec![1, 2, 3]);
1309        assert_eq!(CodePointSet::default(), CodePointSet::new());
1310    }
1311
1312    #[test]
1313    fn subtable_codepoints_and_entries() {
1314        let sub = super::from_entries(
1315            &[
1316                (0x41, GlyphId::new(1)),
1317                (0x42, GlyphId::new(2)),
1318                (0x43, GlyphId::new(5)),
1319            ],
1320            4,
1321        );
1322        let cps = sub.codepoints();
1323        assert_eq!(cps.len(), 3);
1324        assert!(cps.contains(0x43));
1325        assert_eq!(sub.entries().len(), 3);
1326        assert!(!sub.is_empty());
1327        assert!(CmapSubtable::empty_format4().is_empty());
1328        assert!(CmapSubtable::empty_format12().is_empty());
1329    }
1330
1331    #[test]
1332    fn cmap_table_round_trip() {
1333        let mut c = Cmap::new();
1334        c.subtables_mut()
1335            .push(super::from_entries(&[(0x41, GlyphId::new(1))], 4));
1336        c.subtables_mut()
1337            .push(super::from_entries(&[(0x1F600, GlyphId::new(2))], 12));
1338        let bytes = c.encode();
1339        let back = Cmap::decode(&bytes).expect("decodes");
1340        assert_eq!(back.len(), 2);
1341        assert_eq!(back.subtables()[0].format(), 4);
1342        assert_eq!(back.subtables()[1].format(), 12);
1343        assert_eq!(back.lookup(0x41), Some(GlyphId::new(1)));
1344        assert_eq!(back.lookup(0x1F600), Some(GlyphId::new(2)));
1345        let cps = back.codepoints();
1346        assert_eq!(cps.len(), 2);
1347    }
1348
1349    #[test]
1350    fn cmap_lookups_fall_through_subtables() {
1351        let mut c = Cmap::new();
1352        c.subtables_mut()
1353            .push(super::from_entries(&[(0x41, GlyphId::new(1))], 4));
1354        c.subtables_mut()
1355            .push(super::from_entries(&[(0x42, GlyphId::new(2))], 12));
1356        assert_eq!(c.lookup(0x41), Some(GlyphId::new(1)));
1357        assert_eq!(c.lookup(0x42), Some(GlyphId::new(2)));
1358        assert_eq!(c.lookup(0x43), None);
1359        assert_eq!(c.len(), 2);
1360        assert!(!c.is_empty());
1361        assert!(Cmap::new().is_empty());
1362        assert_eq!(Cmap::format4().subtables().len(), 1);
1363        assert_eq!(Cmap::format12().subtables()[0].format(), 12);
1364        assert!(c.preferred().is_some());
1365        assert!(Cmap::new().preferred().is_none());
1366    }
1367
1368    #[test]
1369    fn validate_rejects_non_monotonic() {
1370        // A format-12 subtable whose segments overlap: `validate` walks the
1371        // *entries*, so the second segment's first codepoint (0x41) is not
1372        // strictly greater than the first segment's last (0x5F).
1373        let bad = CmapSubtable::Format12 {
1374            segments: vec![
1375                super::Segment {
1376                    start: 0x41,
1377                    end: 0x5F,
1378                    first_glyph: 10,
1379                },
1380                super::Segment {
1381                    start: 0x50,
1382                    end: 0x5F,
1383                    first_glyph: 20,
1384                },
1385            ],
1386        };
1387        let c = Cmap {
1388            subtables: vec![bad],
1389        };
1390        match c.validate().unwrap_err() {
1391            ModelError::NonMonotonicCmap {
1392                subtable,
1393                previous,
1394                current,
1395            } => {
1396                assert_eq!(subtable, 0);
1397                assert_eq!(previous, 0x5F, "the first segment's end");
1398                assert_eq!(current, 0x50, "the overlapping start");
1399                let msg = alloc::format!(
1400                    "{}",
1401                    ModelError::NonMonotonicCmap {
1402                        subtable,
1403                        previous,
1404                        current
1405                    }
1406                );
1407                assert!(msg.contains("U+005F") && msg.contains("U+0050"), "{msg}");
1408            }
1409            other => panic!("expected NonMonotonicCmap, got {other:?}"),
1410        }
1411        // A repeated codepoint across two subtables is *legal* — a BMP table
1412        // inside a format-12 one is exactly that.
1413        let overlap_across = Cmap {
1414            subtables: vec![
1415                super::from_entries(&[(0x41, GlyphId::new(1))], 4),
1416                super::from_entries(&[(0x41, GlyphId::new(2))], 12),
1417            ],
1418        };
1419        assert!(overlap_across.validate().is_ok());
1420    }
1421
1422    #[test]
1423    fn validate_accepts_well_formed() {
1424        let mut c = Cmap::new();
1425        c.subtables_mut()
1426            .push(super::from_entries(&[(0x41, GlyphId::new(1))], 4));
1427        c.subtables_mut().push(super::from_entries(
1428            &[(0x1F600, GlyphId::new(2)), (0x1F601, GlyphId::new(3))],
1429            12,
1430        ));
1431        assert!(c.validate().is_ok());
1432        assert!(Cmap::new().validate().is_ok());
1433    }
1434
1435    #[test]
1436    fn decode_rejects_unsupported_and_truncated() {
1437        let mut f6 = vec![0u8; 16];
1438        f6[0..2].copy_from_slice(&6u16.to_be_bytes());
1439        match CmapSubtable::decode(&f6).unwrap_err() {
1440            ModelError::UnsupportedCmapFormat { format } => assert_eq!(format, 6),
1441            other => panic!("expected UnsupportedCmapFormat, got {other:?}"),
1442        }
1443        // A two-byte buffer naming format 4: the header is there, the segment
1444        // arrays are not.
1445        assert!(matches!(
1446            CmapSubtable::decode(&[0, 4]).unwrap_err(),
1447            ModelError::Parse { .. }
1448        ));
1449        assert!(matches!(
1450            Cmap::decode(&[0, 0, 1, 0]).unwrap_err(),
1451            ModelError::Parse { .. }
1452        ));
1453        // Format 12 with a group that ends before it starts.
1454        let mut bad = vec![0u8; 28];
1455        bad[0..2].copy_from_slice(&12u16.to_be_bytes());
1456        bad[12..16].copy_from_slice(&1u32.to_be_bytes());
1457        bad[16..20].copy_from_slice(&0x100u32.to_be_bytes());
1458        bad[20..24].copy_from_slice(&0x050u32.to_be_bytes());
1459        assert!(matches!(
1460            CmapSubtable::decode(&bad).unwrap_err(),
1461            ModelError::Parse { .. }
1462        ));
1463    }
1464
1465    #[test]
1466    fn from_entries_format4_clips_astral() {
1467        let entries = vec![(0x1F600u32, GlyphId::new(5)), (0x41, GlyphId::new(1))];
1468        let sub = super::from_entries(&entries, 4);
1469        assert_eq!(sub.len(), 1);
1470        assert_eq!(sub.lookup(0x41), Some(GlyphId::new(1)));
1471        assert_eq!(sub.lookup(0x1F600), None);
1472    }
1473
1474    #[test]
1475    fn format4_with_array_encodes_back_to_an_array() {
1476        // A contiguous codepoint run with non-consecutive glyphs needs the
1477        // glyphIndexArray; the decode must reproduce the holes.
1478        let entries: Vec<(u32, GlyphId)> = (0x41u32..0x46)
1479            .map(|cp| {
1480                (
1481                    cp,
1482                    GlyphId::new(10 + u16::try_from((cp - 0x41) * 2).unwrap_or(0)),
1483                )
1484            })
1485            .collect();
1486        let sub = super::from_entries(&entries, 4);
1487        let bytes = sub.encode();
1488        let back = CmapSubtable::decode(&bytes).expect("decodes");
1489        for (cp, gid) in &entries {
1490            assert_eq!(back.lookup(*cp), Some(*gid), "at U+{cp:X}");
1491        }
1492        assert_eq!(back.entries(), entries);
1493    }
1494
1495    #[test]
1496    fn tiny_and_degenerate_subtables() {
1497        // Empty encode/decode round trip.
1498        let sub = CmapSubtable::empty_format4();
1499        let back = CmapSubtable::decode(&sub.encode()).expect("decodes");
1500        assert!(back.is_empty());
1501        let sub12 = CmapSubtable::empty_format12();
1502        let back12 = CmapSubtable::decode(&sub12.encode()).expect("decodes");
1503        assert!(back12.is_empty());
1504        assert_eq!(back12.lookup(0x41), None);
1505        // Single-entry format 12.
1506        let one = super::from_entries(&[(0x41, GlyphId::new(1))], 12);
1507        let back = CmapSubtable::decode(&one.encode()).expect("decodes");
1508        assert_eq!(back.lookup(0x42), None);
1509        // Glyph id 0 means "not mapped".
1510        let zero = super::from_entries(&[(0x41, GlyphId::new(0))], 12);
1511        assert_eq!(zero.lookup(0x41), None);
1512        assert!(zero.codepoints().is_empty());
1513    }
1514
1515    #[test]
1516    fn insert_entry_on_empty_and_overwrite_glyph_zero() {
1517        let sub = Cmap::subtable_format4();
1518        let sub = insert_entry(&sub, 0x41, GlyphId::new(3));
1519        assert_eq!(sub.lookup(0x41), Some(GlyphId::new(3)));
1520        let sub = insert_entry(&sub, 0x41, GlyphId::new(0));
1521        assert_eq!(sub.lookup(0x41), None, "glyph 0 unmaps");
1522        let sub = insert_entry(&sub, 0x41, GlyphId::new(4));
1523        assert_eq!(sub.lookup(0x41), Some(GlyphId::new(4)));
1524    }
1525}