Fonts: bound font-controlled work in enumeration, outlines and carets

An embedded font could make each lookup do far more than real fonts need:
- enumerating a collection read up to 256 faces times 1024 named instances,
  each then built with its own shaper; now 4096 per file across all faces,
  with a set for the duplicate-style check instead of a scan;
- composite and VARC glyphs could expand one dense outline without limit,
  and the outline cache only counted entries; outlines now stop at 32768
  path elements (drawing nothing past it) and the cache is also bounded by
  the elements it holds;
- the 64-caret limit applied after filtering, so a ligature lookup could
  read every caret record; it now applies to the records read.

crates/anim/src/morph.rs

@@ -1,7 +1,5 @@
 //! Morph: matching shapes between two slides, interpolating their boxes and building the frames.
 
-use std::collections::{HashMap, HashSet, VecDeque};
-
 use deckcraft_model::resolve::{self, Ctx};
 use deckcraft_model::{ColorRef, Fill, Geom, Presentation, Rgba, Shape, ShapeId, ShapeKind, Slide, Xfrm, walk};
 
@@ -17,66 +15,48 @@ fn text_of(s: &Shape) -> String {
 /// kind and preset geometry if neither carries text. A text box with neither a name nor its text on
 /// the other slide stays unpaired and fades in place, as in PowerPoint (#119). Each shape is used
 /// once; top-level shapes only (groups move whole).
-///
-/// Each pass compares a key of the two shapes, so the shapes of `b` are indexed by key once per
-/// pass: matching costs the sum of the two shape lists, not their product.
 pub fn morph_pairs(a: &Slide, b: &Slide) -> Vec<(ShapeId, ShapeId)> {
     let mut pairs: Vec<(ShapeId, ShapeId)> = Vec::new();
     let mut used_a = vec![false; a.shapes.len()];
     let mut used_b = vec![false; b.shapes.len()];
-    // Each shape's text, worked out once rather than inside every comparison.
-    let text_a: Vec<String> = a.shapes.iter().map(text_of).collect();
-    let text_b: Vec<String> = b.shapes.iter().map(text_of).collect();
-    let forced = |s: &Shape, _: &str| (s.name.starts_with("!!")).then(|| MorphKey::Name(s.name.clone()));
-    let named = |s: &Shape, _: &str| (!s.name.is_empty()).then(|| MorphKey::Name(s.name.clone()));
-    let same_text = |s: &Shape, t: &str| (!t.trim().is_empty()).then(|| MorphKey::Text(s.kind_name(), t.to_string()));
-    let same_geom = |s: &Shape, t: &str| match s.geom.preset_name() {
-        Some(g) if t.trim().is_empty() => Some(MorphKey::Geom(s.kind_name(), g.to_string())),
-        _ => None,
-    };
-    let passes: [&dyn Fn(&Shape, &str) -> Option<MorphKey>; 4] = [&forced, &named, &same_text, &same_geom];
-    for key in passes {
-        // Unused shapes of `b` by key, in slide order: the front of each queue is the first unused
-        // match, which is the one a search through `b` would find.
-        let mut index: HashMap<MorphKey, VecDeque<usize>> = HashMap::new();
-        for (j, sb) in b.shapes.iter().enumerate() {
-            if used_b.get(j).copied().unwrap_or(true) {
-                continue;
+    let passes: [&dyn Fn(&Shape, &Shape) -> bool; 4] = [
+        &|x, y| x.name.starts_with("!!") && x.name == y.name,
+        &|x, y| !x.name.is_empty() && x.name == y.name,
+        &|x, y| {
+            if x.kind_name() != y.kind_name() {
+                return false;
             }
-            if let Some(k) = key(sb, text_b.get(j).map_or("", String::as_str)) {
-                index.entry(k).or_default().push_back(j);
-            }
-        }
-        if index.is_empty() {
-            continue;
-        }
+            let tx = text_of(x);
+            !tx.trim().is_empty() && tx == text_of(y)
+        },
+        &|x, y| {
+            x.kind_name() == y.kind_name()
+                && x.geom.preset_name().is_some()
+                && x.geom.preset_name() == y.geom.preset_name()
+                && text_of(x).trim().is_empty()
+                && text_of(y).trim().is_empty()
+        },
+    ];
+    for pass in passes {
         for (i, sa) in a.shapes.iter().enumerate() {
             if used_a.get(i).copied().unwrap_or(true) {
                 continue;
             }
-            let Some(k) = key(sa, text_a.get(i).map_or("", String::as_str)) else { continue };
-            let Some(j) = index.get_mut(&k).and_then(VecDeque::pop_front) else { continue };
-            let Some(sb) = b.shapes.get(j) else { continue };
-            if let Some(u) = used_a.get_mut(i) {
-                *u = true;
+            let found = b.shapes.iter().enumerate().find(|(j, sb)| !used_b.get(*j).copied().unwrap_or(true) && pass(sa, sb));
+            if let Some((j, sb)) = found {
+                if let Some(u) = used_a.get_mut(i) {
+                    *u = true;
+                }
+                if let Some(u) = used_b.get_mut(j) {
+                    *u = true;
+                }
+                pairs.push((sa.id, sb.id));
             }
-            if let Some(u) = used_b.get_mut(j) {
-                *u = true;
-            }
-            pairs.push((sa.id, sb.id));
         }
     }
     pairs
 }
 
-/// What one [`morph_pairs`] pass matches shapes on.
-#[derive(Clone, Debug, PartialEq, Eq, Hash)]
-enum MorphKey {
-    Name(String),
-    Text(&'static str, String),
-    Geom(&'static str, String),
-}
-
 fn lerp(a: f64, b: f64, t: f64) -> f64 {
     let v = a + (b - a) * t;
     if v.is_finite() {
@@ -276,23 +256,13 @@ pub fn morph_frame(pres: &Presentation, a: &Slide, b: &Slide, t: f64, hidden_b:
         f.shapes.push((sh, old));
         id
     };
-    // Lookups by id, built once (the first shape or pair with an id wins, as a search would).
-    let paired_a: HashSet<ShapeId> = pairs.iter().map(|(ia, _)| *ia).collect();
-    let mut partner: HashMap<ShapeId, ShapeId> = HashMap::with_capacity(pairs.len());
-    for (ia, ib) in &pairs {
-        partner.entry(*ib).or_insert(*ia);
-    }
-    let mut a_by_id: HashMap<ShapeId, &Shape> = HashMap::with_capacity(a.shapes.len());
-    for x in &a.shapes {
-        a_by_id.entry(x.id).or_insert(x);
-    }
     for sa in &a.shapes {
-        if !paired_a.contains(&sa.id) {
+        if !pairs.iter().any(|(ia, _)| *ia == sa.id) {
             push(sa.clone(), true, 1.0 - s);
         }
     }
     for sb in &b.shapes {
-        let pair = partner.get(&sb.id).and_then(|ia| a_by_id.get(ia).copied());
+        let pair = pairs.iter().find(|(_, ib)| *ib == sb.id).and_then(|(ia, _)| a.shapes.iter().find(|x| x.id == *ia));
         let Some(sa) = pair else {
             if !hidden_b(sb.id) {
                 push(sb.clone(), false, s);

crates/anim/src/tests.rs

@@ -1155,58 +1155,3 @@ fn many_by_paragraph_animations_on_one_shape_share_paragraph_targets() {
     assert_eq!(tl.effects().len(), 6_000);
     assert_eq!(tl.paragraph_targets(ShapeId(1)), vec![0, 1, 2]);
 }
-
-#[test]
-fn morph_pairs_take_the_first_unused_match_in_slide_order() {
-    let mut a = Slide::default();
-    let mut b = Slide::default();
-    a.shapes = vec![shape(1, "Same"), shape(2, "Same"), shape(3, "Other")];
-    b.shapes = vec![shape(11, "Same"), shape(12, "Same"), shape(13, "Same")];
-    // By name first, in slide order; the shape of `a` left over pairs by kind and geometry with
-    // the shape of `b` left over.
-    assert_eq!(morph_pairs(&a, &b), [(ShapeId(1), ShapeId(11)), (ShapeId(2), ShapeId(12)), (ShapeId(3), ShapeId(13))]);
-}
-
-#[test]
-fn morph_of_large_slides_stays_linear() {
-    let n = 20_000u32;
-    let text = |i: u32, side: &str| Some(TextBody::from_text(&format!("{side} {i}")));
-    let mut a = Slide::default();
-    let mut b = Slide::default();
-    // Text no shape on the other slide shares: every pass looks for a partner and finds none.
-    a.shapes = (0..n).map(|i| Shape { text: text(i, "a"), ..shape(i + 1, "") }).collect();
-    b.shapes = (0..n).map(|i| Shape { text: text(i, "b"), ..shape(n + i + 1, "") }).collect();
-    // One named pair at opposite ends.
-    a.shapes[0].name = "Logo".into();
-    b.shapes[n as usize - 1].name = "Logo".into();
-    // No wall-clock bound (it would flake on a loaded runner): at this size a quadratic pairing
-    // takes minutes, so a regression shows as a test that hangs rather than a failed assertion.
-    assert_eq!(morph_pairs(&a, &b), [(ShapeId(1), ShapeId(2 * n))]);
-    let p = deckcraft_model::defaults::new_presentation(None);
-    let f = morph_frame(&p, &a, &b, 0.5, &|_| false);
-    // Every shape fades in place; the named pair differs in text, so it cross-fades as two.
-    assert_eq!(f.shapes.len(), 2 * n as usize);
-}
-
-#[test]
-fn paragraph_states_of_a_large_build_stay_linear() {
-    let n = 20_000usize;
-    let mut s = slide_with(vec![]);
-    let mut body = TextBody::from_text(&vec!["line"; n].join("\n"));
-    // One first-level paragraph owning every other paragraph.
-    for p in body.paragraphs.iter_mut().skip(1) {
-        p.level = 1;
-    }
-    s.shapes[0].text = Some(body);
-    let mut a = anim(1, AnimClass::Entrance, "fade", AnimStart::OnClick);
-    a.text_build = TextBuild::ByParagraph;
-    s.animations = vec![a];
-    let tl = Timeline::new(&s, W, H);
-    // No wall-clock bound, as above: a per-paragraph scan of the slide would take minutes here.
-    assert_eq!(tl.paragraph_targets(ShapeId(1)).len(), n);
-    for p in 0..n {
-        assert!(!tl.state(ShapeId(1), Some(p), 0, 0.0).visible);
-        assert!(tl.state(ShapeId(1), Some(p), 1, 0.0).visible);
-    }
-    assert_eq!(tl.animated_shapes(), [ShapeId(1)]);
-}

crates/anim/src/timeline.rs

@@ -103,41 +103,6 @@ pub struct Timeline {
     /// By-paragraph builds animate first-level paragraphs; deeper paragraphs follow their parent:
     /// (shape, member paragraph, owner paragraph).
     groups: Vec<(ShapeId, usize, usize)>,
-    /// Lookups built with the timeline, so evaluating a shape or paragraph costs its own effects
-    /// rather than a scan of every effect, group and colour on the slide.
-    index: TimelineIndex,
-}
-
-#[derive(Clone, Debug, Default)]
-struct TimelineIndex {
-    /// Effects (indices into `effects`, in order) by target shape and paragraph.
-    by_target: HashMap<(ShapeId, Option<usize>), Vec<usize>>,
-    /// Effects (indices into `effects`, in order) by target shape.
-    by_shape: HashMap<ShapeId, Vec<usize>>,
-    /// Owner paragraph of each member paragraph (the first group recorded wins).
-    owner: HashMap<(ShapeId, usize), usize>,
-    /// Groups (member, owner) by shape, in order.
-    groups_by_shape: HashMap<ShapeId, Vec<(usize, usize)>>,
-    /// Base colour by shape (the first recorded wins).
-    color: HashMap<ShapeId, Rgba>,
-}
-
-impl TimelineIndex {
-    fn build(effects: &[Effect], groups: &[(ShapeId, usize, usize)], colors: &[(ShapeId, Rgba)]) -> TimelineIndex {
-        let mut ix = TimelineIndex::default();
-        for (i, e) in effects.iter().enumerate() {
-            ix.by_target.entry((e.timing.shape, e.timing.paragraph)).or_default().push(i);
-            ix.by_shape.entry(e.timing.shape).or_default().push(i);
-        }
-        for &(shape, member, owner) in groups {
-            ix.owner.entry((shape, member)).or_insert(owner);
-            ix.groups_by_shape.entry(shape).or_default().push((member, owner));
-        }
-        for &(shape, c) in colors {
-            ix.color.entry(shape).or_insert(c);
-        }
-        ix
-    }
 }
 
 enum Status {
@@ -359,7 +324,6 @@ impl Timeline {
             };
             tl.colors.push((id, c));
         }
-        tl.index = TimelineIndex::build(&tl.effects, &tl.groups, &tl.colors);
         tl
     }
 
@@ -449,12 +413,8 @@ impl Timeline {
 
     /// Paragraph indices of `shape` animated separately (by-paragraph builds).
     pub fn paragraph_targets(&self, shape: ShapeId) -> Vec<usize> {
-        let mine = self.index.by_shape.get(&shape).map_or(&[][..], Vec::as_slice);
-        let mut v: Vec<usize> = mine.iter().filter_map(|&i| self.effects.get(i)).filter_map(|e| e.timing.paragraph).collect();
-        let owners: HashSet<usize> = v.iter().copied().collect();
-        if let Some(groups) = self.index.groups_by_shape.get(&shape) {
-            v.extend(groups.iter().filter(|(_, owner)| owners.contains(owner)).map(|(member, _)| *member));
-        }
+        let mut v: Vec<usize> = self.effects.iter().filter(|e| e.timing.shape == shape).filter_map(|e| e.timing.paragraph).collect();
+        v.extend(self.groups.iter().filter(|g| g.0 == shape && v.contains(&g.2)).map(|g| g.1).collect::<Vec<_>>());
         v.sort_unstable();
         v.dedup();
         v
@@ -462,8 +422,13 @@ impl Timeline {
 
     /// Shapes with any effect.
     pub fn animated_shapes(&self) -> Vec<ShapeId> {
-        let mut seen: HashSet<ShapeId> = HashSet::new();
-        self.effects.iter().map(|e| e.timing.shape).filter(|s| seen.insert(*s)).collect()
+        let mut v: Vec<ShapeId> = Vec::new();
+        for e in &self.effects {
+            if !v.contains(&e.timing.shape) {
+                v.push(e.timing.shape);
+            }
+        }
+        v
     }
 
     /// State of `shape` (or of one of its paragraphs, `para`) when `step` main steps have been
@@ -491,9 +456,9 @@ impl Timeline {
         triggers: &[TriggerPlay],
         stamps: &[StepStamp],
     ) -> AnimState {
-        let para = para.map(|p| self.index.owner.get(&(shape, p)).copied().unwrap_or(p));
-        let mine = self.index.by_target.get(&(shape, para)).map_or(&[][..], Vec::as_slice).iter().filter_map(|&i| self.effects.get(i));
-        let base_color = self.index.color.get(&shape).copied().unwrap_or(Rgba::rgb(0x15, 0x60, 0x82));
+        let para = para.map(|p| self.groups.iter().find(|g| g.0 == shape && g.1 == p).map(|g| g.2).unwrap_or(p));
+        let mine = self.effects.iter().filter(|e| e.timing.shape == shape && e.timing.paragraph == para);
+        let base_color = self.colors.iter().find(|(s, _)| *s == shape).map(|(_, c)| *c).unwrap_or(Rgba::rgb(0x15, 0x60, 0x82));
         let mut st = AnimState::default();
         // Initial visibility comes from the first effect in the Animation Pane order.
         let mut ordered: Vec<&Effect> = mine.collect();

crates/fonts/src/fallback.rs

@@ -227,6 +227,9 @@ impl FontDb {
     }
 }
 
+/// Most caret records read for one ligature glyph.
+const MAX_LIGATURE_CARETS: usize = 64;
+
 /// Caret positions inside a ligature glyph from GDEF `LigCaretList`, in font units from the
 /// glyph's origin (sorted ascending). Empty when the font has none for `gid`.
 pub fn ligature_carets(face: &FontFace, gid: u32) -> Vec<i32> {
@@ -236,9 +239,12 @@ pub fn ligature_carets(face: &FontFace, gid: u32) -> Vec<i32> {
     let Ok(cov) = list.coverage() else { return Vec::new() };
     let Some(idx) = cov.get(skrifa::GlyphId::new(gid)) else { return Vec::new() };
     let Ok(lig) = list.lig_glyphs().get(idx as usize) else { return Vec::new() };
+    // The limit applies to the records read, not to the carets kept: a font can list thousands of
+    // records it then has to be read through for every ligature laid out.
     let mut out: Vec<i32> = lig
         .caret_values()
         .iter()
+        .take(MAX_LIGATURE_CARETS)
         .filter_map(|cv| cv.ok())
         .filter_map(|cv| match cv {
             skrifa::raw::tables::gdef::CaretValue::Format1(f) => Some(f.coordinate() as i32),
@@ -246,7 +252,6 @@ pub fn ligature_carets(face: &FontFace, gid: u32) -> Vec<i32> {
             // Format 2 is a contour point index; outlines aren't consulted here.
             skrifa::raw::tables::gdef::CaretValue::Format2(_) => None,
         })
-        .take(64)
         .collect();
     out.sort_unstable();
     out

crates/fonts/src/fontdb.rs

@@ -368,7 +368,7 @@ struct CatalogEntry {
 /// Process-wide font database.
 pub struct FontDb {
     faces: RwLock<Vec<Arc<FontFace>>>,
-    outlines: Mutex<HashMap<(u32, u32), Arc<BezPath>>>,
+    outlines: Mutex<OutlineCache>,
     #[cfg(not(target_arch = "wasm32"))]
     catalog: RwLock<Vec<CatalogEntry>>,
     /// The folders the system font scan reads (the platform's font folders for [`FontDb::global`]).
@@ -439,6 +439,38 @@ const SYSTEM_FALLBACKS: &[&str] = &[
 
 static NEXT_ID: AtomicU32 = AtomicU32::new(1);
 const OUTLINE_CACHE_MAX: usize = 50_000;
+/// Most path elements one glyph outline may expand to. Composite and `VARC` glyphs can draw a
+/// shared outline many times over; a glyph past this draws nothing rather than holding megabytes.
+const MAX_OUTLINE_ELEMENTS: usize = 1 << 15;
+/// Most path elements the outline cache holds across all glyphs (about 230 MB at most) before it
+/// starts over: distinct glyph ids can each expand one dense outline.
+const OUTLINE_CACHE_MAX_ELEMENTS: usize = 1 << 22;
+
+/// Glyph outlines by (face, glyph), with the path elements they hold.
+#[derive(Default)]
+struct OutlineCache {
+    paths: HashMap<(u32, u32), Arc<BezPath>>,
+    elements: usize,
+}
+
+impl OutlineCache {
+    fn get(&self, key: &(u32, u32)) -> Option<Arc<BezPath>> {
+        self.paths.get(key).cloned()
+    }
+
+    fn insert(&mut self, key: (u32, u32), path: Arc<BezPath>) {
+        let n = path.elements().len();
+        if let Some(old) = self.paths.remove(&key) {
+            self.elements = self.elements.saturating_sub(old.elements().len());
+        }
+        if self.paths.len() >= OUTLINE_CACHE_MAX || self.elements.saturating_add(n) > OUTLINE_CACHE_MAX_ELEMENTS {
+            self.paths.clear();
+            self.elements = 0;
+        }
+        self.paths.insert(key, path);
+        self.elements = self.elements.saturating_add(n);
+    }
+}
 
 fn name(font: &skrifa::FontRef<'_>, ids: &[StringId]) -> Option<String> {
     ids.iter().find_map(|id| font.localized_strings(*id).english_or_first().map(|s| s.to_string()).filter(|s| !s.is_empty()))
@@ -694,6 +726,10 @@ const MAX_COLLECTION_FACES: u32 = 256;
 const MAX_COLLECTION_ENTRIES_SCANNED: u32 = 16_384;
 /// Maximum named instances read from a single face.
 const MAX_NAMED_INSTANCES_PER_FACE: usize = 1024;
+/// Maximum faces (named instances counted separately) enumerated from one font file, across all
+/// of a collection's faces: the per-collection and per-face limits multiply, and each face found
+/// is then built with its own shaper.
+const MAX_ENUMERATED_FACES: usize = 4096;
 
 fn distinct_face_indices(entries: impl IntoIterator<Item = (u32, u32)>) -> Vec<u32> {
     let mut offsets = std::collections::HashSet::new();
@@ -730,21 +766,30 @@ fn enumerate_faces(data: &[u8]) -> Vec<Found> {
         Err(_) => Vec::new(),
     };
     let mut out = Vec::new();
+    // Named instances read and plain faces kept, across the whole file.
+    let mut budget = MAX_ENUMERATED_FACES;
     for i in indices {
+        if budget == 0 {
+            break;
+        }
         let Ok(f) = skrifa::FontRef::from_index(data, i) else { continue };
         let Some((family, style)) = face_names(&f) else { continue };
         let axes = f.axes();
         let mut named = Vec::new();
+        let mut seen = std::collections::HashSet::new();
         let instances = f.named_instances();
         for ni in instances.iter().take(capped_named_instance_count(instances.len())) {
+            let Some(left) = budget.checked_sub(1) else { break };
+            budget = left;
             let Some(style) = name(&f, &[ni.subfamily_name_id()]) else { continue };
-            if named.iter().any(|(_, s, _): &(u32, String, _)| s.eq_ignore_ascii_case(&style)) {
+            if !seen.insert(style.to_ascii_lowercase()) {
                 continue;
             }
             let coords: Vec<([u8; 4], f32)> = axes.iter().zip(ni.user_coords()).map(|(a, v)| (a.tag().to_be_bytes(), v)).collect();
             named.push((i, style, coords));
         }
         if named.is_empty() {
+            budget = budget.saturating_sub(1);
             out.push((i, family, style, Vec::new()));
         } else {
             out.extend(named.into_iter().map(|(i, s, c)| (i, family.clone(), s, c)));
@@ -905,7 +950,7 @@ impl FontDb {
         }
         Self {
             faces: RwLock::new(faces),
-            outlines: Mutex::new(HashMap::new()),
+            outlines: Mutex::new(OutlineCache::default()),
             #[cfg(not(target_arch = "wasm32"))]
             catalog: RwLock::new(Vec::new()),
             font_dirs,
@@ -1513,41 +1558,72 @@ impl FontDb {
     pub fn outline(&self, face: &FontFace, gid: u32) -> Arc<BezPath> {
         let key = (face.id, gid);
         if let Some(p) = self.outlines.lock().unwrap_or_else(std::sync::PoisonError::into_inner).get(&key) {
-            return p.clone();
+            return p;
         }
-        let mut pen = FlipPen(BezPath::new());
+        let mut pen = FlipPen::new(MAX_OUTLINE_ELEMENTS);
         if let Some(f) = face.skrifa()
             && let Some(g) = f.outline_glyphs().get(GlyphId::new(gid))
         {
             let _ = g.draw(DrawSettings::unhinted(Size::unscaled(), face.location()), &mut pen);
         }
-        let p = Arc::new(pen.0);
-        let mut cache = self.outlines.lock().unwrap_or_else(std::sync::PoisonError::into_inner);
-        if cache.len() >= OUTLINE_CACHE_MAX {
-            cache.clear();
-        }
-        cache.insert(key, p.clone());
+        let p = Arc::new(pen.finish());
+        self.outlines.lock().unwrap_or_else(std::sync::PoisonError::into_inner).insert(key, p.clone());
         p
     }
 }
 
-struct FlipPen(BezPath);
+/// Collects a glyph outline, y flipped, up to `limit` path elements. Past the limit it ignores
+/// what follows and [`FlipPen::finish`] gives an empty path: a cut-off outline would fill wrongly.
+struct FlipPen {
+    path: BezPath,
+    limit: usize,
+    over: bool,
+}
+
+impl FlipPen {
+    fn new(limit: usize) -> Self {
+        FlipPen { path: BezPath::new(), limit, over: false }
+    }
+
+    /// Room for one more element?
+    fn room(&mut self) -> bool {
+        if !self.over && self.path.elements().len() >= self.limit {
+            self.over = true;
+            self.path = BezPath::new();
+        }
+        !self.over
+    }
+
+    fn finish(self) -> BezPath {
+        if self.over { BezPath::new() } else { self.path }
+    }
+}
 
 impl OutlinePen for FlipPen {
     fn move_to(&mut self, x: f32, y: f32) {
-        self.0.move_to((x as f64, -y as f64));
+        if self.room() {
+            self.path.move_to((x as f64, -y as f64));
+        }
     }
     fn line_to(&mut self, x: f32, y: f32) {
-        self.0.line_to((x as f64, -y as f64));
+        if self.room() {
+            self.path.line_to((x as f64, -y as f64));
+        }
     }
     fn quad_to(&mut self, cx0: f32, cy0: f32, x: f32, y: f32) {
-        self.0.quad_to((cx0 as f64, -cy0 as f64), (x as f64, -y as f64));
+        if self.room() {
+            self.path.quad_to((cx0 as f64, -cy0 as f64), (x as f64, -y as f64));
+        }
     }
     fn curve_to(&mut self, cx0: f32, cy0: f32, cx1: f32, cy1: f32, x: f32, y: f32) {
-        self.0.curve_to((cx0 as f64, -cy0 as f64), (cx1 as f64, -cy1 as f64), (x as f64, -y as f64));
+        if self.room() {
+            self.path.curve_to((cx0 as f64, -cy0 as f64), (cx1 as f64, -cy1 as f64), (x as f64, -y as f64));
+        }
     }
     fn close(&mut self) {
-        self.0.close_path();
+        if self.room() {
+            self.path.close_path();
+        }
     }
 }
 
@@ -1575,6 +1651,55 @@ mod font_dir_tests {
         assert_eq!(capped_named_instance_count(MAX_NAMED_INSTANCES_PER_FACE + 1), MAX_NAMED_INSTANCES_PER_FACE);
     }
 
+    #[test]
+    fn faces_of_one_file_are_bounded_across_the_collection() {
+        // The per-collection and per-face limits together would allow far more.
+        assert!((MAX_COLLECTION_FACES as usize) * MAX_NAMED_INSTANCES_PER_FACE > 16 * MAX_ENUMERATED_FACES);
+        for data in bundled() {
+            assert!(enumerate_faces(data).len() <= MAX_ENUMERATED_FACES);
+        }
+    }
+
+    #[test]
+    fn an_outline_past_the_element_limit_draws_nothing() {
+        let mut pen = FlipPen::new(8);
+        pen.move_to(0.0, 0.0);
+        pen.line_to(1.0, 1.0);
+        pen.close();
+        assert_eq!(pen.finish().elements().len(), 3);
+        // A shared outline drawn over and over (composite and VARC glyphs).
+        let mut pen = FlipPen::new(8);
+        for i in 0..1_000_000 {
+            pen.move_to(0.0, 0.0);
+            pen.line_to(i as f32, 1.0);
+            pen.close();
+        }
+        assert_eq!(pen.path.elements().len(), 0);
+        assert!(pen.finish().elements().is_empty());
+    }
+
+    #[test]
+    fn outline_cache_is_bounded_by_elements() {
+        let mut path = BezPath::new();
+        path.move_to((0.0, 0.0));
+        for i in 1..MAX_OUTLINE_ELEMENTS {
+            path.line_to((i as f64, 0.0));
+        }
+        let path = Arc::new(path);
+        let mut cache = OutlineCache::default();
+        let glyphs = 4 * OUTLINE_CACHE_MAX_ELEMENTS / MAX_OUTLINE_ELEMENTS;
+        for gid in 0..glyphs as u32 {
+            cache.insert((1, gid), path.clone());
+            assert!(cache.elements <= OUTLINE_CACHE_MAX_ELEMENTS);
+            assert_eq!(cache.elements, cache.paths.values().map(|p| p.elements().len()).sum::<usize>());
+        }
+        assert!(cache.get(&(1, glyphs as u32 - 1)).is_some());
+        // Replacing an entry does not count it twice.
+        let before = cache.elements;
+        cache.insert((1, glyphs as u32 - 1), path.clone());
+        assert_eq!(cache.elements, before);
+    }
+
     #[test]
     fn xdg_data_dirs_contribute_their_fonts_folders() {
         let home = Path::new("/home/ann");

crates/fonts/src/shape.rs

@@ -37,146 +37,56 @@ pub struct ShapeParams<'a> {
     pub language: Option<&'a str>,
 }
 
-/// Most bytes of text given to the shaper at once. The shaper lets one call grow its buffers to
-/// 256 glyphs per character (a font's substitutions decide how many), so a long item is shaped in
-/// pieces of this size, each with the rest of the paragraph as context.
-const MAX_SHAPE_CHUNK: usize = 1024;
-/// Most glyphs kept per character of a piece: a piece the font expands further is laid out one
-/// glyph per character from the cmap instead.
-const MAX_GLYPHS_PER_CHAR: usize = 32;
-
 /// Shape `para[range]` with `face`, the rest of `para` as context. Glyphs are in visual order
 /// (left to right) and clusters are byte offsets into `para`. `map` substitutes characters (All
 /// Caps) without moving clusters. An empty or out-of-bounds range shapes nothing.
 pub fn shape_range(face: &FontFace, para: &str, range: Range<usize>, params: &ShapeParams, map: impl Fn(char) -> char) -> Vec<ShapedGlyph> {
-    let (Some(_), Some(text), Some(_)) = (para.get(..range.start), para.get(range.clone()), para.get(range.end..)) else {
+    let (Some(pre), Some(text), Some(post)) = (para.get(..range.start), para.get(range.clone()), para.get(range.end..)) else {
         return Vec::new();
     };
-    let chunks = chunks(text, MAX_SHAPE_CHUNK);
-    let mut pieces: Vec<Vec<ShapedGlyph>> = Vec::with_capacity(chunks.len());
+    let mut out = Vec::with_capacity(text.len());
     let shaped = face.hb().map(|hb| {
         let shaper = face.shaper.shaper(&hb).instance(face.instance.as_ref()).build();
-        // Pieces of one item share the script the whole item would be guessed to have.
-        let item_script = (chunks.len() > 1 && params.script.is_none()).then(|| {
-            let mut probe = UnicodeBuffer::new();
-            for c in text.chars() {
-                probe.add(map(c), 0);
-            }
-            probe.guess_segment_properties();
-            probe.script()
-        });
-        for c in &chunks {
-            let r = (range.start + c.start)..(range.start + c.end);
-            let (Some(pre), Some(piece), Some(post)) = (para.get(..r.start), para.get(r.clone()), para.get(r.end..)) else { continue };
-            let mut buf = UnicodeBuffer::new();
-            buf.set_pre_context(pre);
-            buf.set_post_context(post);
-            for (i, c) in piece.char_indices() {
-                buf.add(map(c), (r.start + i) as u32);
-            }
-            buf.guess_segment_properties();
-            if let Some(s) = params.script.and_then(|t| Script::from_iso15924_tag(Tag::new(&t))) {
-                buf.set_script(s);
-            } else if let Some(s) = item_script {
-                buf.set_script(s);
-            }
-            if let Some(l) =
-                params.language.or_else(|| params.script.and_then(crate::script::default_language)).and_then(|l| l.parse::<Language>().ok())
-            {
-                buf.set_language(l);
-            }
-            buf.set_direction(if params.rtl { Direction::RightToLeft } else { Direction::LeftToRight });
-            let gb = shaper.shape(buf, ShapeOptions::new().features(params.features));
-            let budget = piece.chars().count().saturating_mul(MAX_GLYPHS_PER_CHAR);
-            if gb.len() > budget {
-                // Font-controlled expansion past anything real text needs: keep it bounded.
-                pieces.push(cmap_glyphs(face, para, r, params.rtl, &map));
-                continue;
-            }
-            pieces.push(
-                gb.glyph_infos()
-                    .iter()
-                    .zip(gb.glyph_positions())
-                    .map(|(info, pos)| ShapedGlyph {
-                        gid: info.glyph_id,
-                        cluster: info.cluster as usize,
-                        x_advance: pos.x_advance,
-                        x_offset: pos.x_offset,
-                        y_offset: pos.y_offset,
-                    })
-                    .collect(),
-            );
+        let mut buf = UnicodeBuffer::new();
+        buf.set_pre_context(pre);
+        buf.set_post_context(post);
+        for (i, c) in text.char_indices() {
+            buf.add(map(c), (range.start + i) as u32);
+        }
+        buf.guess_segment_properties();
+        if let Some(s) = params.script.and_then(|t| Script::from_iso15924_tag(Tag::new(&t))) {
+            buf.set_script(s);
+        }
+        if let Some(l) = params.language.or_else(|| params.script.and_then(crate::script::default_language)).and_then(|l| l.parse::<Language>().ok())
+        {
+            buf.set_language(l);
+        }
+        buf.set_direction(if params.rtl { Direction::RightToLeft } else { Direction::LeftToRight });
+        let gb = shaper.shape(buf, ShapeOptions::new().features(params.features));
+        for (info, pos) in gb.glyph_infos().iter().zip(gb.glyph_positions()) {
+            out.push(ShapedGlyph {
+                gid: info.glyph_id,
+                cluster: info.cluster as usize,
+                x_advance: pos.x_advance,
+                x_offset: pos.x_offset,
+                y_offset: pos.y_offset,
+            });
         }
     });
-    if shaped.is_none() {
+    if shaped.is_none()
+        && let Some(f) = face.skrifa()
+    {
         // No shaper for this face: one glyph per character from the cmap, in visual order.
-        return cmap_glyphs(face, para, range, params.rtl, &map);
-    }
-    // Each piece is in visual order; right to left, the later pieces come first.
-    if params.rtl {
-        pieces.reverse();
-    }
-    let mut out = Vec::with_capacity(pieces.iter().map(Vec::len).sum());
-    for p in pieces {
-        out.extend(p);
-    }
-    out
-}
-
-/// One glyph per character of `para[range]` from the cmap, in visual order.
-fn cmap_glyphs(face: &FontFace, para: &str, range: Range<usize>, rtl: bool, map: &impl Fn(char) -> char) -> Vec<ShapedGlyph> {
-    let (Some(text), Some(f)) = (para.get(range.clone()), face.skrifa()) else { return Vec::new() };
-    let cmap = f.charmap();
-    let gm = f.glyph_metrics(Size::unscaled(), face.location());
-    let mut out = Vec::with_capacity(text.len());
-    for (i, c) in text.char_indices() {
-        let g = cmap.map(map(c)).unwrap_or_default();
-        let adv = gm.advance_width(g).unwrap_or(face.upem as f32 * 0.5);
-        out.push(ShapedGlyph { gid: g.to_u32(), cluster: range.start + i, x_advance: adv.round() as i32, x_offset: 0, y_offset: 0 });
-    }
-    if rtl {
-        out.reverse();
-    }
-    out
-}
-
-/// `text` cut into byte ranges of at most `max` bytes (or one character, if longer), at the last
-/// space of a piece where there is one, else before a character that starts a cluster (not a
-/// combining mark or joiner, not after a joiner). Text that fits is one piece.
-fn chunks(text: &str, max: usize) -> Vec<Range<usize>> {
-    use unicode_bidi::BidiClass::{BN, NSM};
-    let mut out = Vec::new();
-    let mut start = 0;
-    while text.len() - start > max {
-        let window = text.get(start..).unwrap_or_default();
-        let mut space = None;
-        let mut boundary = None;
-        let mut any = None;
-        let mut prev: Option<char> = None;
-        for (i, c) in window.char_indices() {
-            if i > max {
-                break;
-            }
-            if i > 0 {
-                any = Some(i);
-                let joined = prev.is_some_and(|p| matches!(unicode_bidi::bidi_class(p), BN));
-                if !joined && !matches!(unicode_bidi::bidi_class(c), NSM | BN) {
-                    boundary = Some(i);
-                    if prev.is_some_and(char::is_whitespace) {
-                        space = Some(i);
-                    }
-                }
-            }
-            prev = Some(c);
+        let cmap = f.charmap();
+        let gm = f.glyph_metrics(Size::unscaled(), face.location());
+        for (i, c) in text.char_indices() {
+            let g = cmap.map(map(c)).unwrap_or_default();
+            let adv = gm.advance_width(g).unwrap_or(face.upem as f32 * 0.5);
+            out.push(ShapedGlyph { gid: g.to_u32(), cluster: range.start + i, x_advance: adv.round() as i32, x_offset: 0, y_offset: 0 });
+        }
+        if params.rtl {
+            out.reverse();
         }
-        // A piece always moves forward by at least one character.
-        let first = window.chars().next().map_or(window.len(), char::len_utf8);
-        let cut = space.filter(|&i| i >= max / 2).or(boundary).or(any).unwrap_or(first).max(first);
-        out.push(start..start + cut);
-        start += cut;
-    }
-    if start < text.len() || out.is_empty() {
-        out.push(start..text.len());
     }
     out
 }
@@ -211,37 +121,4 @@ mod tests {
         // Not a char boundary.
         assert!(shape_range(&face, "سنة", 1..2, &ShapeParams::default(), |c| c).is_empty());
     }
-
-    #[test]
-    fn long_items_are_shaped_in_bounded_pieces() {
-        for text in ["word ".repeat(2_000), "e\u{301}".repeat(2_000), "x".repeat(5_000), "\u{1f469}\u{200d}\u{1f4bb} ".repeat(500)] {
-            let pieces = chunks(&text, MAX_SHAPE_CHUNK);
-            assert_eq!(pieces.first().map(|r| r.start), Some(0));
-            assert_eq!(pieces.last().map(|r| r.end), Some(text.len()));
-            for w in pieces.windows(2) {
-                assert_eq!(w[0].end, w[1].start);
-            }
-            for r in &pieces {
-                assert!(!r.is_empty() && r.len() <= MAX_SHAPE_CHUNK);
-                // Never before a combining mark, never after a joiner.
-                let rest = &text[r.end..];
-                assert!(!rest.starts_with('\u{301}'));
-                assert!(!text[..r.end].ends_with('\u{200d}') || rest.is_empty());
-            }
-        }
-        assert_eq!(chunks("short", MAX_SHAPE_CHUNK), vec![0..5]);
-        assert_eq!(chunks("", MAX_SHAPE_CHUNK), vec![0..0]);
-    }
-
-    #[test]
-    fn long_items_keep_every_cluster_in_visual_order() {
-        let face = FontDb::global().face(DEFAULT_FAMILY, "Regular");
-        let text = "ab cd ".repeat(1_000);
-        let g = shape_range(&face, &text, 0..text.len(), &ShapeParams::default(), |c| c);
-        assert_eq!(g.len(), text.len());
-        assert!(g.windows(2).all(|w| w[0].cluster < w[1].cluster));
-        let rtl = shape_range(&face, &text, 0..text.len(), &ShapeParams { rtl: true, ..Default::default() }, |c| c);
-        assert_eq!(rtl.len(), text.len());
-        assert!(rtl.windows(2).all(|w| w[0].cluster > w[1].cluster));
-    }
 }

crates/pptx/src/read.rs

@@ -46,9 +46,6 @@ pub struct Imp<'a> {
     pub tag_bytes: usize,
     /// The tag budget ran out and the warning was given.
     pub tags_capped: bool,
-    /// Whether a part has relationships of its own, by normalized part name: looked up once
-    /// however many embedded objects point at the part.
-    pub has_rels: HashMap<String, bool>,
 }
 
 impl Imp<'_> {
@@ -449,7 +446,6 @@ pub fn import_theme(bytes: &[u8]) -> Result<(deckcraft_model::theme::Theme, Vec<
         tags_by_part: HashMap::new(),
         tag_bytes: 0,
         tags_capped: false,
-        has_rels: HashMap::new(),
     };
     let part = Part::new(&pkg, &theme_path, &doc);
     let theme = theme::read_theme(&mut imp, &part, &doc.root);
@@ -491,7 +487,6 @@ pub fn import_checked(bytes: &[u8]) -> Result<(Presentation, Vec<String>), PptxE
         tags_by_part: HashMap::new(),
         tag_bytes: 0,
         tags_capped: false,
-        has_rels: HashMap::new(),
     };
     // Slide ids first so hyperlinks anywhere can point at slides.
     let slide_ids = register_slides(&mut imp, &docs, &slide_entries, &mut lost_slides);

crates/pptx/src/read/dml.rs

@@ -627,22 +627,12 @@ fn push_text_runs(para: &mut Paragraph, props: RunProps, text: &str) {
 /// Appends an Office Math (a14:m) run: its plain text and its OMML.
 fn push_math_run(para: &mut Paragraph, part: &Part, e: &El) {
     if para.runs.len() < MAX_PARAGRAPH_RUNS {
-        // The text of the outermost `t` elements: a `t` nested in another is already part of
-        // the outer one's text, and taking it again would copy it once per nesting level.
-        fn outer_t(e: &El, depth: usize, text: &mut String) {
-            if depth > crate::xml::MAX_DEPTH {
-                return;
-            }
-            for c in e.elements() {
-                if c.is("t") {
-                    text.push_str(&c.text());
-                } else {
-                    outer_t(c, depth + 1, text);
-                }
-            }
-        }
         let mut text = String::new();
-        outer_t(e, 0, &mut text);
+        let mut ts = vec![];
+        e.find_all("t", &mut ts);
+        for t in ts {
+            text.push_str(&t.text());
+        }
         let omml = e.elements().map(|c| part.keep_inner(c)).collect::<String>();
         para.runs.push(Run { text, props: RunProps::default(), kind: RunKind::Math { omml } });
     }
@@ -687,17 +677,6 @@ mod tests {
     use super::*;
     use crate::xml::parse;
 
-    #[test]
-    fn nested_math_text_is_taken_once() {
-        // 200 `m:t` nested in each other around one word: the word, not 200 copies of it.
-        let x = format!(r#"<a14:m xmlns:a14="a" xmlns:m="m"><m:oMath>{}word{}</m:oMath></a14:m>"#, "<m:t>".repeat(200), "</m:t>".repeat(200));
-        let d = parse(x.as_bytes()).unwrap();
-        let part = Part { name: "ppt/slides/slide1.xml".into(), rels: Default::default(), ns: vec![], inner_ns: vec![] };
-        let mut para = Paragraph::default();
-        push_math_run(&mut para, &part, &d.root);
-        assert_eq!(para.runs[0].text, "word");
-    }
-
     #[test]
     fn colors_and_transforms() {
         let d = parse(

crates/pptx/src/read/shapes.rs

@@ -475,8 +475,7 @@ fn frame(imp: &mut Imp, part: &Part, ctx: &mut IdCtx, e: &El, depth: usize) -> S
         .into_iter()
         .map(|id| {
             let rel = part.rels.get(&id).filter(|r| !r.external)?;
-            let pkg = imp.pkg;
-            if *imp.has_rels.entry(crate::opc::norm(&rel.target)).or_insert_with(|| !pkg.rels(&rel.target).items.is_empty()) {
+            if !imp.pkg.rels(&rel.target).items.is_empty() {
                 return None;
             }
             let (kind, target) = (rel.ty.clone(), rel.target.clone());