Repair: bound the notes page size like a slide

* 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.

* address review: bound thread-local glyph cache by path elements

crates/av1/src/decoder.rs

@@ -425,6 +425,8 @@ impl Decoder {
 
     fn parse_obus(&mut self, data: &[u8], out: &mut Vec<(Output, usize, u32)>) -> Result<()> {
         let mut tu = 0usize;
+        // Repeated-frame outputs in `out`, counted as they are added rather than recounted per OBU.
+        let mut existing = out.iter().filter(|(o, _, _)| matches!(o, Output::Existing { .. })).count();
         let mut pos = 0;
         while pos < data.len() {
             let obu = parse_obu_unit(data, pos)?;
@@ -444,9 +446,10 @@ impl Decoder {
                 }
                 OBU_FRAME_HEADER_T | OBU_REDUNDANT_FRAME_HEADER_T | OBU_FRAME_T => {
                     if let Some(o) = self.frame_obu(&obu)? {
-                        if out.iter().filter(|(o, _, _)| matches!(o, Output::Existing { .. })).count() >= 32 {
+                        if existing >= 32 {
                             return Err(Error::Invalid("too many frame outputs in chunk"));
                         }
+                        existing += usize::from(matches!(o, Output::Existing { .. }));
                         out.push((o, tu, spatial_id));
                     }
                 }

crates/engine/src/cmd/file.rs

@@ -397,6 +397,7 @@ pub fn pdf_options(p: &Value, count: usize) -> Result<deckcraft_pdf::PdfOptions>
 pub fn parse_slide_range(text: &str, count: usize) -> Result<Vec<usize>> {
     let invalid = || bad("file.export", format!("“{text}” isn't a valid slide range: use numbers and ranges such as 1-3, 5"));
     let mut out: Vec<usize> = vec![];
+    let mut seen: std::collections::HashSet<usize> = std::collections::HashSet::new();
     for part in text.split([',', ';']).map(str::trim).filter(|p| !p.is_empty()) {
         let (a, b) = match part.split_once('-') {
             Some((a, b)) => (a.trim(), b.trim()),
@@ -412,7 +413,7 @@ pub fn parse_slide_range(text: &str, count: usize) -> Result<Vec<usize>> {
             return Err(bad("file.export", format!("the presentation has {count} slides; “{part}” is outside them")));
         }
         for i in lo - 1..hi {
-            if !out.contains(&i) {
+            if seen.insert(i) {
                 out.push(i);
             }
         }
@@ -776,6 +777,16 @@ mod tests {
 
     use super::{parse_slide_range, write_file};
 
+    #[test]
+    fn broad_and_repeated_slide_ranges_expand_once() {
+        // 200 copies of a 100,000-slide range: each index once, in order, without a scan per index.
+        let text = vec!["1-100000"; 200].join(",");
+        let v = parse_slide_range(&text, 100_000).unwrap();
+        assert_eq!(v.len(), 100_000);
+        assert!(v.windows(2).all(|w| w[0] < w[1]));
+        assert_eq!(parse_slide_range("3, 1-3, 2", 3).unwrap(), vec![2, 0, 1]);
+    }
+
     #[test]
     fn slide_range_rejects_plus_sign() {
         assert!(parse_slide_range("+2", 3).is_err());

crates/engine/src/cmd/review.rs

@@ -367,7 +367,7 @@ fn spelling(s: &mut Session, p: &Value) -> Result<Value> {
             }
             out.push(v);
         }
-        let rep: Vec<usize> = crate::spell::repeated(para, &default).iter().map(|w| w.start).collect();
+        let rep: std::collections::HashSet<usize> = crate::spell::repeated(para, &default).iter().map(|w| w.start).collect();
         for w in crate::spell::paragraph_words(para, &default) {
             if ignore.contains(&w.text.to_lowercase()) || rep.contains(&w.start) {
                 continue;
@@ -421,23 +421,30 @@ fn add_to_dictionary(_s: &mut Session, p: &Value) -> Result<Value> {
 /// Replace whole-word `from` with `to` in `text`; how many were replaced.
 fn replace_word(text: &mut String, from: &str, to: &str, all: bool) -> usize {
     let is_word = |c: char| c.is_alphanumeric() || c == '\'' || c == '’';
-    let mut n = 0;
-    let mut at = 0;
+    // The result is built in one pass; the text is not edited in place for every match.
+    let mut out = String::new();
+    let (mut n, mut at, mut copied) = (0, 0, 0);
     while let Some(i) = text.get(at..).and_then(|t| t.find(from)).map(|i| i + at) {
         let end = i + from.len();
-        let before = text.get(..i).and_then(|t| t.chars().next_back()).is_some_and(is_word);
+        // The character before the match as the edited text would have it.
+        let before = text.get(copied..i).and_then(|t| t.chars().next_back()).or_else(|| out.chars().next_back()).is_some_and(is_word);
         let after = text.get(end..).and_then(|t| t.chars().next()).is_some_and(is_word);
         if before || after {
             at = end;
             continue;
         }
-        text.replace_range(i..end, to);
+        out.push_str(text.get(copied..i).unwrap_or_default());
+        out.push_str(to);
         n += 1;
-        at = i + to.len();
+        (at, copied) = (end, end);
         if !all {
             break;
         }
     }
+    if n > 0 {
+        out.push_str(text.get(copied..).unwrap_or_default());
+        *text = out;
+    }
     n
 }
 
@@ -764,6 +771,49 @@ fn end_compare(s: &mut Session, _: &Value) -> Result<Value> {
 
 #[cfg(test)]
 mod tests {
+    /// The replacement as it ran before: edited in place for every match.
+    fn replace_word_in_place(text: &mut String, from: &str, to: &str, all: bool) -> usize {
+        let is_word = |c: char| c.is_alphanumeric() || c == '\'' || c == '’';
+        let mut n = 0;
+        let mut at = 0;
+        while let Some(i) = text.get(at..).and_then(|t| t.find(from)).map(|i| i + at) {
+            let end = i + from.len();
+            let before = text.get(..i).and_then(|t| t.chars().next_back()).is_some_and(is_word);
+            let after = text.get(end..).and_then(|t| t.chars().next()).is_some_and(is_word);
+            if before || after {
+                at = end;
+                continue;
+            }
+            text.replace_range(i..end, to);
+            n += 1;
+            at = i + to.len();
+            if !all {
+                break;
+            }
+        }
+        n
+    }
+
+    #[test]
+    fn replace_word_matches_the_in_place_version() {
+        let cases = [
+            ("a a b a", "a", "x", true),
+            ("aa a. a", "a", "bb", true),
+            ("a-a -a-", "-", "ab", true),
+            ("foo. foo.", "foo.", "", true),
+            ("it's it", "it", "so", true),
+            ("x.x. x.", "x.", "y", true),
+            ("a a a", "a", "b", false),
+            ("none", "z", "q", true),
+            ("é é", "é", "e", true),
+        ];
+        for (text, from, to, all) in cases {
+            let (mut a, mut b) = (text.to_string(), text.to_string());
+            let (na, nb) = (replace_word(&mut a, from, to, all), replace_word_in_place(&mut b, from, to, all));
+            assert_eq!((na, a), (nb, b), "{text:?} {from:?} -> {to:?}");
+        }
+    }
+
     use super::*;
     use serde_json::json;
 

crates/engine/src/cmd/slide.rs

@@ -408,8 +408,9 @@ fn select_slides(s: &mut Session, p: &Value) -> Result<Value> {
     };
     s.select(|doc, sel| {
         if add {
+            let mut have: std::collections::HashSet<_> = sel.slides.iter().copied().collect();
             for i in &ids {
-                if !sel.slides.contains(i) {
+                if have.insert(*i) {
                     sel.slides.push(*i);
                 }
             }

crates/engine/src/compare.rs

@@ -121,9 +121,10 @@ pub fn diff(cur: &Presentation, rev: &Presentation, by_position: bool) -> Vec<Ch
     let cur_matched: HashSet<usize> = pairs.iter().map(|p| p.0).collect();
     let rev_matched: HashSet<usize> = pairs.iter().map(|p| p.1).collect();
     let mut out = vec![];
+    let mut media = Media::new(cur, rev);
     for (i, j) in &pairs {
         let (Some(a), Some(b)) = (cur.slides.get(*i), rev.slides.get(*j)) else { continue };
-        let details = slide_details(cur, a, rev, b);
+        let details = slide_details(cur, a, rev, b, &mut media);
         if !details.is_empty() {
             out.push(Change { kind: ChangeKind::Changed, slide: *i, number: i.saturating_add(1), only_in: None, revised: Some(*j), details });
         }
@@ -140,10 +141,18 @@ pub fn diff(cur: &Presentation, rev: &Presentation, by_position: bool) -> Vec<Ch
             });
         }
     }
+    // Each revised slide's open match (the first pair naming it).
+    let mut rev_to_cur: HashMap<usize, usize> = HashMap::new();
+    for p in &pairs {
+        rev_to_cur.entry(p.1).or_insert(p.0);
+    }
+    // After the open slide that matches the nearest matched revised slide before it.
+    let mut at = 0;
     for (j, s) in rev.slides.iter().enumerate() {
+        if let Some(i) = rev_to_cur.get(&j) {
+            at = i + 1;
+        }
         if !rev_matched.contains(&j) {
-            // After the open slide that matches the revised slide before it.
-            let at = (0..j).rev().find_map(|k| pairs.iter().find(|p| p.1 == k).map(|p| p.0 + 1)).unwrap_or(0);
             out.push(Change {
                 kind: ChangeKind::Inserted,
                 slide: at,
@@ -174,8 +183,34 @@ fn shape_label(s: &Shape) -> String {
     if s.name.trim().is_empty() { format!("Shape {}", s.id.0) } else { s.name.clone() }
 }
 
-fn media_bytes(p: &Presentation, id: MediaId) -> Option<&[u8]> {
-    p.media(id).map(|m| m.data.as_slice())
+/// Both decks' media bytes by id, and which picture pairs were already compared: a deck can
+/// show one picture many times, and its bytes are compared once per pair.
+struct Media<'a> {
+    cur: HashMap<MediaId, &'a [u8]>,
+    rev: HashMap<MediaId, &'a [u8]>,
+    same: HashMap<(MediaId, MediaId), bool>,
+}
+
+impl<'a> Media<'a> {
+    fn new(cur: &'a Presentation, rev: &'a Presentation) -> Self {
+        // The first item with an id wins, as in `Presentation::media`.
+        let index = |p: &'a Presentation| {
+            let mut m = HashMap::new();
+            for x in &p.media {
+                m.entry(x.id).or_insert(x.data.as_slice());
+            }
+            m
+        };
+        Media { cur: index(cur), rev: index(rev), same: HashMap::new() }
+    }
+    /// Whether the pictures (by media id, `None` for a shape that is not a picture) differ.
+    fn differ(&mut self, a: Option<MediaId>, b: Option<MediaId>) -> bool {
+        let (ba, bb) = (a.and_then(|x| self.cur.get(&x)), b.and_then(|y| self.rev.get(&y)));
+        match (a, b) {
+            (Some(x), Some(y)) if ba.is_some() && bb.is_some() => !*self.same.entry((x, y)).or_insert_with(|| ba == bb),
+            _ => ba.is_some() || bb.is_some(),
+        }
+    }
 }
 
 /// A shape without its ids (shape and media), for comparing across decks.
@@ -204,7 +239,7 @@ fn turn(ctx: Option<&Ctx>, s: &Shape) -> (f64, bool, bool) {
     drawn_box(ctx, s).map_or((0.0, false, false), |x| (x.rot, x.flip_h, x.flip_v))
 }
 
-fn shape_details(cp: &Presentation, ca: Option<&Ctx>, a: &Shape, rp: &Presentation, cb: Option<&Ctx>, b: &Shape, out: &mut Vec<String>) {
+fn shape_details(ca: Option<&Ctx>, a: &Shape, cb: Option<&Ctx>, b: &Shape, media: &mut Media, out: &mut Vec<String>) {
     let label = shape_label(b);
     let text = |s: &Shape| s.text.as_ref().map(|t| t.text()).unwrap_or_default();
     let mut what = vec![];
@@ -234,11 +269,11 @@ fn shape_details(cp: &Presentation, ca: Option<&Ctx>, a: &Shape, rp: &Presentati
     if a.fill != b.fill || a.line != b.line || a.style != b.style || a.effects != b.effects {
         what.push("formatting");
     }
-    let pic = |p: &Presentation, s: &Shape| match &s.kind {
-        ShapeKind::Picture { fill } => media_bytes(p, fill.media).map(|b| b.to_vec()),
+    let pic = |s: &Shape| match &s.kind {
+        ShapeKind::Picture { fill } => Some(fill.media),
         _ => None,
     };
-    if pic(cp, a) != pic(rp, b) {
+    if media.differ(pic(a), pic(b)) {
         what.push("picture");
     }
     // Anything the checks above do not cover (alt text, hidden, a link…) is reported too, also
@@ -265,21 +300,32 @@ fn shape_details(cp: &Presentation, ca: Option<&Ctx>, a: &Shape, rp: &Presentati
     }
 }
 
-fn slide_details(cp: &Presentation, a: &Slide, rp: &Presentation, b: &Slide) -> Vec<String> {
+fn slide_details(cp: &Presentation, a: &Slide, rp: &Presentation, b: &Slide, media: &mut Media) -> Vec<String> {
     let mut out = vec![];
     let mut used: HashSet<usize> = HashSet::new();
     let (ca, cb) = (Ctx::for_slide(cp, a), Ctx::for_slide(rp, b));
+    // The revised shapes by id (first wins) and by name (in order, with a cursor past used ones).
+    let mut by_id: HashMap<ShapeId, usize> = HashMap::new();
+    let mut by_name: HashMap<&str, (Vec<usize>, usize)> = HashMap::new();
+    for (k, x) in b.shapes.iter().enumerate() {
+        by_id.entry(x.id).or_insert(k);
+        if !x.name.is_empty() {
+            by_name.entry(x.name.as_str()).or_default().0.push(k);
+        }
+    }
     for sa in &a.shapes {
-        let k = b
-            .shapes
-            .iter()
-            .position(|x| x.id == sa.id)
-            .or_else(|| b.shapes.iter().enumerate().position(|(k, x)| !used.contains(&k) && x.name == sa.name && !x.name.is_empty()));
+        let k = by_id.get(&sa.id).copied().or_else(|| {
+            let (ks, next) = by_name.get_mut(sa.name.as_str())?;
+            while ks.get(*next).is_some_and(|k| used.contains(k)) {
+                *next += 1;
+            }
+            ks.get(*next).copied()
+        });
         match k {
             Some(k) if !used.contains(&k) => {
                 used.insert(k);
                 if let Some(sb) = b.shapes.get(k) {
-                    shape_details(cp, ca.as_ref(), sa, rp, cb.as_ref(), sb, &mut out);
+                    shape_details(ca.as_ref(), sa, cb.as_ref(), sb, media, &mut out);
                 }
             }
             _ => out.push(format!("{} deleted (only in the deck)", shape_label(sa))),
@@ -334,19 +380,34 @@ pub fn adopt(doc: &mut Presentation, rev: &Presentation, slide: &Slide, replacin
     let mut sl = slide.clone();
     // Media.
     let mut media_map: HashMap<MediaId, MediaId> = HashMap::new();
+    // Both decks' media by id (the first item with an id wins, as in `Presentation::media`),
+    // looked up once per reference instead of searched.
+    let mut rev_at: HashMap<MediaId, usize> = HashMap::new();
+    for (i, m) in rev.media.iter().enumerate() {
+        rev_at.entry(m.id).or_insert(i);
+    }
+    let mut doc_at: HashMap<MediaId, usize> = HashMap::new();
+    for (i, m) in doc.media.iter().enumerate() {
+        doc_at.entry(m.id).or_insert(i);
+    }
     for id in crate::media_refs::slide_media(&sl) {
-        let Some(m) = rev.media(id) else { continue };
-        match doc.media(id) {
+        let Some(m) = rev_at.get(&id).and_then(|&i| rev.media.get(i)) else { continue };
+        match doc_at.get(&id).and_then(|&i| doc.media.get(i)) {
             Some(x) if x.data == m.data => {}
             None => {
                 // Keeps the revision's id, so later ids must start past it.
+                doc_at.insert(id, doc.media.len());
                 doc.media.push(m.clone());
                 doc.next_id = doc.next_id.max(id.0);
             }
             Some(_) => {
+                let before = doc.media.len();
                 let new = doc
                     .add_media(&m.name, &m.content_type, m.data.as_ref().clone())
                     .ok_or_else(|| crate::cmd::bad("review.accept", crate::cmd::NO_ID_SPACE))?;
+                if doc.media.len() > before {
+                    doc_at.entry(new).or_insert(before);
+                }
                 media_map.insert(id, new);
             }
         }
@@ -519,6 +580,39 @@ mod tests {
         assert_eq!(s.doc().unwrap().doc.slides.len(), n, "comparing alone changes nothing");
     }
 
+    #[test]
+    fn many_inserted_slides_and_same_named_pictures_compare_by_index() {
+        use std::sync::Arc;
+
+        use deckcraft_model::style::PictureFill;
+        use deckcraft_model::{Shape, ShapeId, ShapeKind, SlideId, defaults};
+
+        // One slide of 3,000 pictures of one image, all named "Box"; the revision has the same
+        // pictures under other ids (matched by name, in order) and 3,000 slides inserted after it.
+        let mut cur = defaults::new_presentation(None);
+        let img = cur.add_media("a.png", "image/png", vec![7; 4096]).unwrap();
+        let mut rev = cur.clone();
+        let pic = |id: u32| Shape {
+            id: ShapeId(id),
+            name: "Box".into(),
+            xfrm: Some(deckcraft_model::Xfrm::new(10.0, 10.0, 50.0, 50.0)),
+            kind: ShapeKind::Picture { fill: PictureFill { media: img, ..Default::default() } },
+            ..Default::default()
+        };
+        Arc::make_mut(&mut cur.slides[0]).shapes = (0..3000).map(|k| pic(100_000 + k)).collect();
+        Arc::make_mut(&mut rev.slides[0]).shapes = (0..3000).map(|k| pic(200_000 + k)).collect();
+        let mut base = (*rev.slides[0]).clone();
+        base.shapes.clear();
+        for k in 0..3000 {
+            let mut s = base.clone();
+            s.id = SlideId(300_000 + k);
+            rev.slides.push(Arc::new(s));
+        }
+        let changes = super::diff(&cur, &rev, false);
+        assert_eq!(changes.len(), 3000, "only the inserted slides differ");
+        assert!(changes.iter().all(|c| c.kind == super::ChangeKind::Inserted && c.slide == 1));
+    }
+
     /// A deck with one slide: a table whose cell has a picture fill, a picture background and a
     /// transition sound. `tag` starts the bytes of each.
     fn media_deck(tag: &str) -> deckcraft_model::Presentation {

crates/engine/src/io.rs

@@ -48,6 +48,8 @@ pub fn write_file(path: &str, bytes: &[u8]) -> Result<(), String> {
         // A short fixed-size name: appending to the target's name could exceed the file name limit.
         let tmp_name = format!(".deckcraft.{}.{}.saving", std::process::id(), COUNTER.fetch_add(1, Ordering::Relaxed));
         let tmp = target_path.with_file_name(tmp_name);
+        // The sibling must pass the same check: when `path` is the write root itself it lands outside.
+        crate::file_access::check_write(&tmp.to_string_lossy())?;
         match std::fs::OpenOptions::new().write(true).create_new(true).open(&tmp) {
             Ok(f) => break (tmp, f),
             Err(e) if e.kind() == std::io::ErrorKind::AlreadyExists && attempts < 16 => attempts += 1,
@@ -135,4 +137,16 @@ mod tests {
 
         let _ = std::fs::remove_file(&file);
     }
+
+    #[test]
+    fn write_file_to_the_write_root_itself_creates_no_sibling_outside_it() {
+        let base = std::env::temp_dir().join(format!("deckcraft_io_root_test_{}", std::process::id()));
+        let root = base.join("root");
+        std::fs::create_dir_all(&root).unwrap();
+        let roots = crate::file_access::AutomationRoots::new(&[], std::slice::from_ref(&root)).unwrap().unwrap();
+        let res = crate::file_access::confine(Some(&roots), || write_file(root.to_str().unwrap(), b"x"));
+        assert!(res.unwrap_err().contains("outside the write root"));
+        assert_eq!(std::fs::read_dir(&base).unwrap().count(), 1, "only the root is there");
+        let _ = std::fs::remove_dir_all(&base);
+    }
 }

crates/engine/src/spell.rs

@@ -700,15 +700,29 @@ pub struct Word {
     pub repeated: Option<usize>,
 }
 
+/// Longest language tag a word is checked in. BCP 47 tags in documents are a few bytes; a longer
+/// value from a file is no language we have a dictionary for, and copying it into every word of
+/// a paragraph would multiply it.
+const MAX_LANG_LEN: usize = 64;
+
 /// The words of `p`, each with its run's language (`lang` on the run, else `default`). Words
 /// with digits are skipped; apostrophes inside a word belong to it; hyphenated words are checked
-/// part by part.
+/// part by part. A language over [`MAX_LANG_LEN`] counts as none.
 pub fn paragraph_words(p: &deckcraft_model::Paragraph, default: &str) -> Vec<Word> {
     let mut chars: Vec<(char, usize)> = vec![];
     for (ri, r) in p.runs.iter().enumerate() {
         chars.extend(r.content().chars().map(|c| (c, ri)));
     }
-    let lang_of = |ri: usize| p.runs.get(ri).and_then(|r| r.props.lang.clone()).filter(|l| !l.is_empty()).unwrap_or_else(|| default.to_string());
+    let default = if default.len() > MAX_LANG_LEN { "" } else { default };
+    let lang_of = |ri: usize| {
+        p.runs
+            .get(ri)
+            .and_then(|r| r.props.lang.as_deref())
+            .filter(|l| !l.is_empty())
+            .map(|l| if l.len() > MAX_LANG_LEN { "" } else { l })
+            .unwrap_or(default)
+            .to_string()
+    };
     // Combining marks (decomposed accents) belong to the letter before them.
     let inside = |c: char| c.is_alphanumeric() || deckcraft_model::words::is_combining_mark(c) || c == '\'' || c == '’' || c == '-';
     let mut out = vec![];
@@ -791,15 +805,18 @@ pub fn misspelt(p: &deckcraft_model::Paragraph, default: &str, ignore: &[String]
         .chain(repeated(p, default))
         .collect::<Vec<_>>()
         .into_iter()
-        .fold(vec![], |mut v: Vec<Word>, w| {
+        .fold((vec![], HashMap::new()), |(mut v, mut at): (Vec<Word>, HashMap<usize, usize>), w| {
             // A repeated misspelt word is reported once, as repeated.
-            if let Some(i) = v.iter().position(|x| x.start == w.start) {
-                v[i] = w;
-            } else {
-                v.push(w);
+            match at.get(&w.start).and_then(|&i| v.get_mut(i)) {
+                Some(x) => *x = w,
+                None => {
+                    at.insert(w.start, v.len());
+                    v.push(w);
+                }
             }
-            v
+            (v, at)
         })
+        .0
 }
 
 /// Use `d` for `lang` from now on in this process (a dictionary the app loaded itself).
@@ -953,6 +970,23 @@ SFX D Y 1\nSFX D 0 ed/S .\n";
         assert_eq!(w, vec!["check", "done"]);
     }
 
+    #[test]
+    fn a_long_paragraph_with_a_huge_language_is_checked_in_linear_work() {
+        use deckcraft_model::{Paragraph, Run, RunProps};
+        // 100,000 copies of one word under a 1 MB language value: every word after the first is
+        // a repeat, and no word carries a copy of the value.
+        let lang = "x".repeat(1 << 20);
+        let p =
+            Paragraph { runs: vec![Run::with("the ".repeat(100_000), RunProps { lang: Some(lang), ..Default::default() })], ..Default::default() };
+        let words = paragraph_words(&p, "en-US");
+        assert_eq!(words.len(), 100_000);
+        assert!(words.iter().all(|w| w.lang.is_empty()));
+        let bad = misspelt(&p, "en-US", &[]);
+        assert_eq!(bad.len(), 99_999);
+        assert!(bad.iter().all(|w| w.repeated.is_some()));
+        assert!(paragraph_words(&Paragraph::new("word"), &"y".repeat(100)).iter().all(|w| w.lang.is_empty()));
+    }
+
     #[test]
     fn long_and_numeric_flags_and_latin1() {
         let d = Dictionary::parse(b"FLAG long\nSFX Aa Y 1\nSFX Aa 0 s .\n", b"1\ncat/Aa\n");

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/format/src/lib.rs

@@ -247,6 +247,11 @@ pub fn repair(p: &mut Presentation) {
     if !(p.notes_size.width.is_finite() && p.notes_size.width > 0.0 && p.notes_size.height.is_finite() && p.notes_size.height > 0.0) {
         p.notes_size = Presentation::default().notes_size;
     }
+    // A notes page is bounded like a slide: canvas and handout drawing scale with it.
+    p.notes_size = deckcraft_model::Size::new(
+        p.notes_size.width.clamp(*SLIDE_SIDE.start(), *SLIDE_SIDE.end()),
+        p.notes_size.height.clamp(*SLIDE_SIDE.start(), *SLIDE_SIDE.end()),
+    );
     sane_numbers(p);
 }
 

crates/format/src/tests.rs

@@ -451,6 +451,13 @@ fn degenerate_slide_sizes_are_repaired() {
     }
 }
 
+#[test]
+fn repair_bounds_the_notes_page_size() {
+    let mut p = Presentation { notes_size: deckcraft_model::Size::new(1e12, 0.01), ..Default::default() };
+    repair(&mut p);
+    assert_eq!((p.notes_size.width, p.notes_size.height), (4032.0, 72.0));
+}
+
 /// A file whose slide size is null, a string or missing a side (written by hand or by
 /// another tool; NaN is also saved as null) opens with the default size rather than failing
 /// as damaged.

crates/geom/src/morph.rs

@@ -126,6 +126,21 @@ fn split_curve(c: &[Point], n: usize, out: &mut Vec<Point>) {
     out.extend([p1, p2, p3]);
 }
 
+/// A piece length ordered totally, so it can sit in a heap.
+#[derive(PartialEq)]
+struct Share(f64);
+impl Eq for Share {}
+impl PartialOrd for Share {
+    fn partial_cmp(&self, o: &Self) -> Option<std::cmp::Ordering> {
+        Some(self.cmp(o))
+    }
+}
+impl Ord for Share {
+    fn cmp(&self, o: &Self) -> std::cmp::Ordering {
+        self.0.total_cmp(&o.0)
+    }
+}
+
 /// Brings a contour to `n` curves. Unlike manim (which splits every curve equally often), the extra
 /// splits go to the longest pieces, so a long side gets more points than a short one.
 fn refine(c: &Contour, n: usize) -> Contour {
@@ -136,11 +151,15 @@ fn refine(c: &Contour, n: usize) -> Contour {
     let curves: Vec<&[Point]> = (0..have).filter_map(|k| c.pts.get(3 * k..3 * k + 4)).collect();
     let len: Vec<f64> = curves.iter().map(|q| curve_length(q) + 1e-9).collect();
     let mut parts = vec![1usize; curves.len()];
+    // The curve with the longest piece gets the next split (the lowest index on a tie); a heap keeps
+    // this O(n log n) instead of rescanning every curve for each split.
+    let mut heap: std::collections::BinaryHeap<(Share, std::cmp::Reverse<usize>)> =
+        len.iter().enumerate().map(|(k, l)| (Share(*l), std::cmp::Reverse(k))).collect();
     for _ in 0..n - have {
-        let share = |k: usize| len.get(k).copied().unwrap_or(0.0) / parts.get(k).copied().unwrap_or(1) as f64;
-        let best = (1..curves.len()).fold(0, |b, k| if share(k) > share(b) { k } else { b });
+        let Some((_, std::cmp::Reverse(best))) = heap.pop() else { break };
         if let Some(p) = parts.get_mut(best) {
             *p += 1;
+            heap.push((Share(len.get(best).copied().unwrap_or(0.0) / *p as f64), std::cmp::Reverse(best)));
         }
     }
     let mut out = Vec::with_capacity(1 + 3 * n);
@@ -420,6 +439,16 @@ mod tests {
         assert_eq!(contours(&to_path(&cs)), cs);
     }
 
+    #[test]
+    fn refine_many_curves_finishes_at_the_asked_count() {
+        let mut c = Contour { closed: false, pts: vec![Point::ZERO] };
+        for i in 1..=20_000 {
+            line_to(&mut c.pts, Point::new(f64::from(i), f64::from(i % 7)));
+        }
+        let r = refine(&c, 40_000);
+        assert_eq!(r.curves(), 40_000);
+    }
+
     #[test]
     fn refine_splits_the_longest_curves_and_keeps_the_shape() {
         let c = Contour { closed: false, pts: vec![Point::ZERO, Point::new(1.0, 0.0), Point::new(2.0, 0.0), Point::new(3.0, 0.0)] };

crates/geom/src/warp.rs

@@ -928,11 +928,25 @@ impl Warp {
             k_fill = 1.0;
         }
         zoom = zoom.max(k_fill);
+        // Per band, measured once: its widest line and its first and last lines' baselines.
+        let mut stats: Vec<Option<(f64, f64, f64)>> = vec![None; nb];
+        for (l, &b) in lines.iter().zip(&band_of) {
+            let w = l.extent.1 - l.extent.0;
+            if let Some(slot) = stats.get_mut(b) {
+                match slot {
+                    Some((widest, _, last)) => {
+                        *widest = widest.max(w);
+                        *last = l.ref_y;
+                    }
+                    None => *slot = Some((0.0f64.max(w), l.ref_y, l.ref_y)),
+                }
+            }
+        }
         let mut maps = Vec::with_capacity(n);
         let mut offsets = Vec::new();
         for (i, l) in lines.iter().enumerate() {
             let b = band_of.get(i).copied().unwrap_or(0);
-            let in_band = |j: &usize| band_of.get(*j) == Some(&b);
+            let band = stats.get(b).copied().flatten();
             match self.bands.get(b) {
                 Some(Band::Fill { .. }) | None => {
                     let (y0, y1) = band_y.get(b).copied().flatten().unwrap_or((0.0, 1.0));
@@ -941,16 +955,12 @@ impl Warp {
                 }
                 Some(Band::Follow { path, anchor }) => {
                     let len = path.length();
-                    let widest = (0..n).filter(in_band).filter_map(|j| lines.get(j)).map(|l| l.extent.1 - l.extent.0).fold(0.0, f64::max);
+                    let widest = band.map_or(0.0, |s| s.0);
                     let k = if widest > len && widest > 1e-9 { len / widest } else { 1.0 };
-                    let members: Vec<&WarpLine> = (0..n).filter(in_band).filter_map(|j| lines.get(j)).collect();
                     let ref_y = match anchor {
-                        LineAnchor::Last => members.last().map(|l| l.ref_y),
-                        LineAnchor::First => members.first().map(|l| l.ref_y),
-                        LineAnchor::Middle => match (members.first(), members.last()) {
-                            (Some(a), Some(z)) => Some((a.ref_y + z.ref_y) / 2.0),
-                            _ => None,
-                        },
+                        LineAnchor::Last => band.map(|s| s.2),
+                        LineAnchor::First => band.map(|s| s.1),
+                        LineAnchor::Middle => band.map(|s| (s.1 + s.2) / 2.0),
                     }
                     .unwrap_or(l.ref_y);
                     // Lines off the guide run on a parallel curve at their natural length.

crates/geom/src/warp/tests.rs

@@ -319,3 +319,20 @@ fn arch_and_inflate_handles_follow_the_pointer() {
     assert!(more > adjust_defaults("textInflate")[0], "{more}");
     assert!((more - 20_000.0).abs() < 1.0, "{more}");
 }
+
+#[test]
+fn many_lines_on_a_follow_band_are_mapped_from_one_measurement() {
+    // 50,000 lines on an arch: each line's scale and anchor come from the band measured once.
+    let w = warp("textArchUp", &[], rect()).unwrap();
+    let inner = Rect::new(7.2, 3.6, W - 7.2, H - 3.6);
+    let lines: Vec<WarpLine> = (0..50_000)
+        .map(|i| {
+            let y = i as f64 * 0.01;
+            WarpLine { ink: Some(Rect::new(190.0, y, 230.0, y + 1.0)), extent: (190.0, 230.0), ref_y: y + 1.0 }
+        })
+        .collect();
+    let m = w.mapper(&lines, inner);
+    // The last line sits on the arc, as with two lines.
+    let last = lines.len() - 1;
+    assert!(m.map(last, Point::new(210.0, lines[last].ref_y)).y.abs() < 0.05);
+}

crates/hevc/src/slice.rs

@@ -326,7 +326,9 @@ impl SliceHeader {
 
     /// entry_point_offset list (tiles / wavefront substreams).
     fn parse_entry_points(&mut self, r: &mut BitReader, pps: &Pps, sps: &Sps) -> Result<()> {
-        self.entry_points.clear();
+        // A fresh list, not `clear()`: a dependent segment starts as a copy of its independent
+        // segment's header, and clearing would keep that copy's allocation for every segment.
+        self.entry_points = Vec::new();
         if pps.tiles_enabled || pps.entropy_coding_sync {
             let n = r.read_ue()?;
             ensure!(n <= sps.pic_width_in_ctbs() * sps.pic_height_in_ctbs(), "num_entry_point_offsets out of range");

crates/model/src/chart.rs

@@ -758,17 +758,20 @@ impl Chart {
     }
 
     fn stacked_value_range(&self, n: usize) -> (f64, f64) {
-        let mut lo: f64 = 0.0;
-        let mut hi: f64 = 0.0;
-        for i in 0..n {
-            let (mut p, mut m) = (0.0, 0.0);
-            for s in &self.series {
-                let v = s.values.get(i).copied().flatten().unwrap_or(0.0);
-                if v >= 0.0 { p += v } else { m += v }
+        // Sums per category, from the values the series hold (an absent one adds nothing).
+        let (mut pos, mut neg) = (vec![0.0f64; n], vec![0.0f64; n]);
+        for s in &self.series {
+            for (i, v) in s.values.iter().enumerate().take(n) {
+                let v = v.unwrap_or(0.0);
+                if v >= 0.0 {
+                    pos[i] += v;
+                } else {
+                    neg[i] += v;
+                }
             }
-            hi = hi.max(p);
-            lo = lo.min(m);
         }
+        let hi = pos.iter().fold(0.0f64, |a, &p| a.max(p));
+        let lo = neg.iter().fold(0.0f64, |a, &m| a.min(m));
         (lo, hi)
     }
 
@@ -1348,40 +1351,50 @@ impl Chart {
     /// The box chart's groups (distinct category labels in order of appearance; one unnamed
     /// group without categories) and, per series, each group's summary (None when it has no
     /// points).
+    ///
+    /// Each value is put in its group's bucket once (groups are found by name in a map), and the
+    /// series x groups result is held to [`MAX_BOX_CELLS`]: groups past it are left out.
     pub fn box_groups(&self) -> (Vec<String>, Vec<Vec<Option<BoxStats>>>) {
+        let max_groups = (MAX_BOX_CELLS / self.series.len().max(1)).max(1);
         let mut groups: Vec<String> = Vec::new();
+        let mut index: std::collections::HashMap<&str, usize> = std::collections::HashMap::new();
         for c in &self.categories {
-            if !groups.contains(c) {
+            if !index.contains_key(c.as_str()) && groups.len() < max_groups {
+                index.insert(c, groups.len());
                 groups.push(c.clone());
             }
         }
         if groups.is_empty() {
             groups.push(String::new());
+            index.insert("", 0);
         }
+        // A value past the categories belongs to the unnamed group, when there is one.
+        let past_end = index.get("").copied();
         let stats = self
             .series
             .iter()
             .map(|s| {
-                groups
-                    .iter()
-                    .map(|g| {
-                        let pts: Vec<f64> = s
-                            .values
-                            .iter()
-                            .enumerate()
-                            .filter(|(i, _)| self.categories.get(*i).map_or(g.is_empty() || self.categories.is_empty(), |c| c == g))
-                            .filter_map(|(_, v)| *v)
-                            .filter(|v| v.is_finite())
-                            .collect();
-                        box_stats_by(pts, self.inclusive_quartiles)
-                    })
-                    .collect()
+                let mut buckets: Vec<Vec<f64>> = vec![Vec::new(); groups.len()];
+                for (i, v) in s.values.iter().enumerate() {
+                    let Some(v) = v.filter(|v| v.is_finite()) else { continue };
+                    let g = match self.categories.get(i) {
+                        Some(c) => index.get(c.as_str()).copied(),
+                        None => past_end,
+                    };
+                    if let Some(b) = g.and_then(|g| buckets.get_mut(g)) {
+                        b.push(v);
+                    }
+                }
+                buckets.into_iter().map(|pts| box_stats_by(pts, self.inclusive_quartiles)).collect()
             })
             .collect();
         (groups, stats)
     }
 }
 
+/// Most series x group summaries [`Chart::box_groups`] makes.
+pub const MAX_BOX_CELLS: usize = 1_000_000;
+
 /// Widens the (min, max) extent `ext` to include `v`.
 fn widen(ext: &mut (f64, f64), v: f64) {
     ext.0 = ext.0.min(v);
@@ -1454,33 +1467,41 @@ impl Chart {
         let n = self.categories.len().max(s.values.len());
         let levels: Vec<&Vec<String>> = self.category_levels.iter().take(MAX_LEVELS).collect();
         // Each leaf's path from the top level down, blanks filled from the row above.
-        let mut last: Vec<String> = vec![String::new(); levels.len()];
-        let paths: Vec<Vec<String>> = (0..n)
+        // Labels are shared, not copied: an outer label given once stands for every leaf under it.
+        use std::rc::Rc;
+        let empty: Rc<str> = Rc::from("");
+        let mut last: Vec<Rc<str>> = vec![empty.clone(); levels.len()];
+        let paths: Vec<Vec<Rc<str>>> = (0..n)
             .map(|i| {
                 let mut path = Vec::with_capacity(levels.len() + 1);
                 for (d, lv) in levels.iter().enumerate().rev() {
                     let l = lv.get(i).map(|x| x.trim()).unwrap_or("");
                     if !l.is_empty() {
-                        last[d] = l.to_string();
+                        last[d] = Rc::from(l);
                         // A new outer label starts fresh inner groups.
                         for inner in last.iter_mut().take(d) {
-                            inner.clear();
+                            *inner = empty.clone();
                         }
                     }
                     path.push(last[d].clone());
                 }
-                path.push(self.categories.get(i).cloned().unwrap_or_default());
+                path.push(self.categories.get(i).map_or_else(|| empty.clone(), |c| Rc::from(c.as_str())));
                 path
             })
             .collect();
         let value = |i: usize| s.values.get(i).copied().flatten().filter(|v| v.is_finite()).unwrap_or(0.0).max(0.0);
-        fn build(rows: &[(usize, &[String])], value: &dyn Fn(usize) -> f64) -> Vec<TreeNode> {
+        fn build(rows: &[(usize, &[std::rc::Rc<str>])], value: &dyn Fn(usize) -> f64) -> Vec<TreeNode> {
             let mut out: Vec<TreeNode> = Vec::new();
             let mut i = 0;
             while i < rows.len() {
                 let (idx, path) = rows[i];
                 if path.len() <= 1 {
-                    out.push(TreeNode { name: path.first().cloned().unwrap_or_default(), value: value(idx), leaf: Some(idx), children: vec![] });
+                    out.push(TreeNode {
+                        name: path.first().map(|p| p.to_string()).unwrap_or_default(),
+                        value: value(idx),
+                        leaf: Some(idx),
+                        children: vec![],
+                    });
                     i += 1;
                     continue;
                 }
@@ -1489,14 +1510,14 @@ impl Chart {
                 while j < rows.len() && rows[j].1.len() > 1 && &rows[j].1[0] == head {
                     j += 1;
                 }
-                let sub: Vec<(usize, &[String])> = rows[i..j].iter().map(|(k, p)| (*k, &p[1..])).collect();
+                let sub: Vec<(usize, &[std::rc::Rc<str>])> = rows[i..j].iter().map(|(k, p)| (*k, &p[1..])).collect();
                 let children = build(&sub, value);
-                out.push(TreeNode { name: head.clone(), value: children.iter().map(|c| c.value).sum(), leaf: None, children });
+                out.push(TreeNode { name: head.to_string(), value: children.iter().map(|c| c.value).sum(), leaf: None, children });
                 i = j;
             }
             out
         }
-        let rows: Vec<(usize, &[String])> = paths.iter().enumerate().map(|(i, p)| (i, p.as_slice())).collect();
+        let rows: Vec<(usize, &[Rc<str>])> = paths.iter().enumerate().map(|(i, p)| (i, p.as_slice())).collect();
         build(&rows, &value)
     }
 }
@@ -1607,6 +1628,40 @@ mod chartex_tests {
         assert!(c.category_tree().iter().all(|n| n.leaf.is_some()));
     }
 
+    #[test]
+    fn large_box_hierarchy_and_stacked_charts_take_linear_work() {
+        // 50,000 distinct categories in one series: grouped through a map, one pass.
+        let n = 50_000;
+        let mut c = Chart::sample(ChartType::BoxWhisker);
+        c.series.truncate(1);
+        c.categories = (0..n).map(|i| format!("g{i}")).collect();
+        c.series[0].values = (0..n).map(|i| Some(i as f64)).collect();
+        let (groups, stats) = c.box_groups();
+        assert_eq!((groups.len(), stats[0].len()), (n, n));
+        assert!(stats[0].iter().all(Option::is_some));
+        // 2,000 series cap the groups so the result stays within MAX_BOX_CELLS.
+        c.series = vec![c.series[0].clone(); 2000];
+        let (groups, stats) = c.box_groups();
+        assert_eq!(groups.len(), MAX_BOX_CELLS / 2000);
+        assert!(stats.iter().all(|s| s.len() == groups.len()));
+        // One long outer label over 50,000 leaves is shared, not copied per leaf.
+        let mut t = Chart::sample(ChartType::Treemap);
+        t.series.truncate(1);
+        t.categories = (0..n).map(|i| format!("c{i}")).collect();
+        t.series[0].values = (0..n).map(|_| Some(1.0)).collect();
+        let mut outer = vec![String::new(); n];
+        outer[0] = "o".repeat(1 << 16);
+        t.category_levels = vec![outer];
+        let tree = t.category_tree();
+        assert_eq!(tree.len(), 1);
+        assert_eq!(tree[0].children.len(), n);
+        // Stacked sums over many sparse series.
+        let mut st = Chart::sample(ChartType::StackedBar);
+        st.categories = (0..n).map(|i| i.to_string()).collect();
+        st.series = (0..2000).map(|k| Series { values: vec![Some(1.0); if k == 0 { n } else { 1 }], ..Default::default() }).collect();
+        assert!(st.value_range().1 >= 2000.0, "{:?}", st.value_range());
+    }
+
     #[test]
     fn box_groups_follow_category_labels() {
         let c = Chart::sample(ChartType::BoxWhisker);

crates/model/src/edit.rs

@@ -78,45 +78,57 @@ pub fn insert(body: &mut TextBody, pos: Pos, text: &str, props: Option<RunProps>
     if body.paragraphs.is_empty() {
         body.paragraphs.push(Paragraph::default());
     }
-    let (mut pi, mut ch) = clamp(body, pos);
-    let props = props.unwrap_or_else(|| props_at(body, (pi, ch)));
+    let (pi0, mut ch) = clamp(body, pos);
+    let props = props.unwrap_or_else(|| props_at(body, (pi0, ch)));
     let text = text.replace("\r\n", "\n").replace('\r', "\n");
+    // Work on the paragraph being edited apart from the body, so each new paragraph is pushed to a
+    // list and the body's vector is spliced once instead of shifted for every `\n`.
+    let Some(slot) = body.paragraphs.get_mut(pi0) else { return (pi0, ch) };
+    let mut cur = std::mem::take(slot);
+    let mut done: Vec<Paragraph> = Vec::new();
     let mut first = true;
     for part in text.split('\n') {
         if !first {
-            // Split paragraph pi at ch.
-            let Some(p) = body.paragraphs.get_mut(pi) else { break };
-            let idx = split_at(p, ch);
-            let tail: Vec<Run> = p.runs.drain(idx..).collect();
-            let newp =
-                Paragraph { level: p.level, props: p.props.clone(), runs: tail, def_props: p.def_props.clone(), end_props: p.end_props.clone() };
-            p.end_props = props.clone();
-            body.paragraphs.insert(pi + 1, newp);
-            pi += 1;
+            // Split the current paragraph at ch.
+            let idx = split_at(&mut cur, ch);
+            let tail: Vec<Run> = cur.runs.drain(idx..).collect();
+            let newp = Paragraph {
+                level: cur.level,
+                props: cur.props.clone(),
+                runs: tail,
+                def_props: cur.def_props.clone(),
+                end_props: cur.end_props.clone(),
+            };
+            cur.end_props = props.clone();
+            done.push(std::mem::replace(&mut cur, newp));
             ch = 0;
         }
         first = false;
+        // The run index just after the last insertion: the next one lands there with no rescan.
+        let mut next: Option<usize> = None;
         for (k, seg) in part.split('\u{b}').enumerate() {
-            let Some(p) = body.paragraphs.get_mut(pi) else { break };
             if k > 0 {
-                let idx = split_at(p, ch);
-                p.runs.insert(idx, Run { text: String::new(), props: props.clone(), kind: RunKind::Break });
+                let idx = next.unwrap_or_else(|| split_at(&mut cur, ch));
+                cur.runs.insert(idx, Run { text: String::new(), props: props.clone(), kind: RunKind::Break });
                 ch += 1;
+                next = Some(idx + 1);
             }
             if seg.is_empty() {
                 continue;
             }
-            let idx = split_at(p, ch);
-            p.runs.insert(idx, Run::with(seg, props.clone()));
+            let idx = next.unwrap_or_else(|| split_at(&mut cur, ch));
+            cur.runs.insert(idx, Run::with(seg, props.clone()));
             ch += seg.chars().count();
+            next = Some(idx + 1);
         }
-        if let Some(p) = body.paragraphs.get_mut(pi) {
-            p.normalize();
-            if p.runs.is_empty() {
-                p.end_props = props.clone();
-            }
+        cur.normalize();
+        if cur.runs.is_empty() {
+            cur.end_props = props.clone();
         }
     }
+    let pi = pi0 + done.len();
+    done.push(cur);
+    body.paragraphs.splice(pi0..=pi0, done);
     (pi, ch)
 }
 
@@ -252,8 +264,16 @@ pub fn slice(body: &TextBody, a: Pos, b: Pos) -> TextBody {
 /// Insert a formatted body at `pos` (paste): first paragraph merges into the current one.
 pub fn insert_body(body: &mut TextBody, pos: Pos, src: &TextBody) -> Pos {
     let mut caret = clamp(body, pos);
+    // Plain text runs go straight in at the run index after the previous one and the paragraph is
+    // normalized once, not rescanned and merged for every source run.
+    let mut next: Option<usize> = None;
+    let mut dirty = false;
     for (k, sp) in src.paragraphs.iter().enumerate() {
         if k > 0 {
+            if let (true, Some(p)) = (dirty, body.paragraphs.get_mut(caret.0)) {
+                p.normalize();
+            }
+            (next, dirty) = (None, false);
             caret = insert(body, caret, "\n", None);
             if let Some(p) = body.paragraphs.get_mut(caret.0) {
                 p.level = sp.level;
@@ -261,6 +281,22 @@ pub fn insert_body(body: &mut TextBody, pos: Pos, src: &TextBody) -> Pos {
             }
         }
         for r in &sp.runs {
+            if r.kind == RunKind::Text
+                && !r.text.is_empty()
+                && !r.text.contains(['\n', '\r', '\u{b}'])
+                && let Some(p) = body.paragraphs.get_mut(caret.0)
+            {
+                let idx = next.unwrap_or_else(|| split_at(p, caret.1));
+                p.runs.insert(idx, Run::with(&r.text, r.props.clone()));
+                caret.1 += r.text.chars().count();
+                (next, dirty) = (Some(idx + 1), true);
+                continue;
+            }
+            // Anything else takes the general path, after the pending runs are merged.
+            if let (true, Some(p)) = (dirty, body.paragraphs.get_mut(caret.0)) {
+                p.normalize();
+            }
+            (next, dirty) = (None, false);
             match r.kind {
                 RunKind::Text => caret = insert(body, caret, &r.text, Some(r.props.clone())),
                 RunKind::Break => caret = insert(body, caret, "\u{b}", Some(r.props.clone())),
@@ -274,6 +310,9 @@ pub fn insert_body(body: &mut TextBody, pos: Pos, src: &TextBody) -> Pos {
             }
         }
     }
+    if let (true, Some(p)) = (dirty, body.paragraphs.get_mut(caret.0)) {
+        p.normalize();
+    }
     caret
 }
 
@@ -568,6 +607,74 @@ mod tests {
         assert_eq!(caret, (0, 5));
     }
 
+    /// The paste as it ran before the fast path: one `insert` (and normalize) per source run.
+    fn insert_body_by_runs(body: &mut TextBody, pos: Pos, src: &TextBody) -> Pos {
+        let mut caret = clamp(body, pos);
+        for (k, sp) in src.paragraphs.iter().enumerate() {
+            if k > 0 {
+                caret = insert(body, caret, "\n", None);
+                if let Some(p) = body.paragraphs.get_mut(caret.0) {
+                    p.level = sp.level;
+                    p.props = sp.props.clone();
+                }
+            }
+            for r in &sp.runs {
+                match r.kind {
+                    RunKind::Text => caret = insert(body, caret, &r.text, Some(r.props.clone())),
+                    RunKind::Break => caret = insert(body, caret, "\u{b}", Some(r.props.clone())),
+                    _ => {
+                        if let Some(p) = body.paragraphs.get_mut(caret.0) {
+                            let idx = split_at(p, caret.1);
+                            p.runs.insert(idx, r.clone());
+                            caret.1 += r.char_len();
+                        }
+                    }
+                }
+            }
+        }
+        caret
+    }
+
+    #[test]
+    fn paste_matches_inserting_run_by_run() {
+        let bold = |t: &str| Run::with(t, RunProps { bold: Some(true), ..Default::default() });
+        let mut src = body("");
+        src.paragraphs = vec![
+            Paragraph {
+                runs: vec![Run::with("ab", RunProps::default()), Run::with("cd", RunProps::default()), bold("ef"), bold("g")],
+                ..Default::default()
+            },
+            Paragraph {
+                runs: vec![
+                    bold("h"),
+                    Run { text: String::new(), props: RunProps::default(), kind: RunKind::Break },
+                    Run::with("i", RunProps::default()),
+                ],
+                level: 1,
+                ..Default::default()
+            },
+            Paragraph { runs: vec![Run::with("jk", RunProps::default())], ..Default::default() },
+        ];
+        for at in [0, 1, 3, 6] {
+            let mut dest = body("XYZabc");
+            format(&mut dest, (0, 2), (0, 4), &|p| p.italic = Some(true));
+            let mut want = dest.clone();
+            let want_caret = insert_body_by_runs(&mut want, (0, at), &src);
+            let caret = insert_body(&mut dest, (0, at), &src);
+            assert_eq!(caret, want_caret, "caret at {at}");
+            assert_eq!(format!("{:?}", dest.paragraphs), format!("{:?}", want.paragraphs), "paste at {at}");
+        }
+    }
+
+    #[test]
+    fn multiline_insert_splits_into_paragraphs() {
+        let mut b = body("abcd");
+        let c = insert(&mut b, (0, 2), "x\ny\u{b}z\n\nw", None);
+        assert_eq!(c, (3, 1));
+        let texts: Vec<String> = b.paragraphs.iter().map(Paragraph::text).collect();
+        assert_eq!(texts, ["abx", "y\u{b}z", "", "wcd"]);
+    }
+
     #[test]
     fn words_and_moves() {
         let b = body("Hello brave world");

crates/model/src/numfmt.rs

@@ -143,9 +143,14 @@ fn group(digits: &str, sep: char) -> String {
     out
 }
 
+/// Longest number format applied, as in Excel (255 characters); a longer one formats as
+/// General, so a chart cannot make every label expand a huge format.
+pub const MAX_CODE_LEN: usize = 255;
+
 /// `v` formatted with the Excel number format `code` in language `lang` (axis labels: the text
 /// section of a format doesn't apply).
 pub fn format(code: &str, v: f64, lang: Option<&str>) -> String {
+    let code = if code.len() > MAX_CODE_LEN * 4 || code.chars().count() > MAX_CODE_LEN { "General" } else { code };
     let (sep, dec) = marks(lang);
     if !v.is_finite() {
         return String::new();
@@ -299,6 +304,14 @@ mod tests {
 
     const RUB: &str = r#"_-* #\ ##0\ "₽"_-;\-* #\ ##0\ "₽"_-;_-* "-"??\ "₽"_-;_-@_-"#;
 
+    #[test]
+    fn an_overlong_format_is_general() {
+        let code = "0".repeat(100_000);
+        assert_eq!(format(&code, 12.5, None), format("General", 12.5, None));
+        let ok = "0".repeat(MAX_CODE_LEN);
+        assert_eq!(format(&ok, 7.0, None).len(), MAX_CODE_LEN);
+    }
+
     #[test]
     fn scientific_subnormal() {
         assert_eq!(format("0.00E+00", 5e-324, None), "4.94E-324");

crates/pptx/src/opc.rs

@@ -171,6 +171,7 @@ fn rels_of(doc: &xml::Doc, part: &str) -> Rels {
         let external = r.attr("TargetMode").is_some_and(|m| m.eq_ignore_ascii_case("external"));
         let target_raw = target.to_string();
         let target = if external { target_raw.clone() } else { resolve(&base, target) };
+        out.by_id.entry(id.to_string()).or_insert(out.items.len());
         out.items.push(Rel {
             id: id.to_string(),
             kind: ty.rsplit('/').next().unwrap_or(ty).to_string(),
@@ -211,11 +212,13 @@ pub struct Rel {
 #[derive(Clone, Debug, Default)]
 pub struct Rels {
     pub items: Vec<Rel>,
+    /// Id → index of its first relationship in `items`.
+    by_id: HashMap<String, usize>,
 }
 
 impl Rels {
     pub fn get(&self, id: &str) -> Option<&Rel> {
-        self.items.iter().find(|r| r.id == id)
+        self.by_id.get(id).and_then(|&i| self.items.get(i))
     }
     pub fn target(&self, id: &str) -> Option<&str> {
         self.get(id).map(|r| r.target.as_str())
@@ -339,23 +342,29 @@ pub fn relative(from: &str, to: &str) -> String {
 #[derive(Default)]
 pub struct RelsOut {
     pub items: Vec<(String, String, String, bool)>,
+    /// (type, target, external) → id of the relationship [`RelsOut::add`] made for it.
+    added: HashMap<(String, String, bool), String>,
 }
 
 impl RelsOut {
     /// Add (or reuse) a relationship; `kind` is a full type URI or a suffix of the standard base.
     pub fn add(&mut self, kind: &str, target: &str, external: bool) -> String {
         let ty = if kind.starts_with("http") { kind.to_string() } else { format!("{RT_BASE}{kind}") };
-        if let Some((id, ..)) = self.items.iter().find(|(_, t, tg, e)| *t == ty && tg == target && *e == external) {
+        let key = (ty, target.to_string(), external);
+        if let Some(id) = self.added.get(&key) {
             return id.clone();
         }
         let id = format!("rId{}", self.items.len() + 1);
-        self.items.push((id.clone(), ty, target.to_string(), external));
+        self.items.push((id.clone(), key.0.clone(), key.1.clone(), external));
+        self.added.insert(key, id.clone());
         id
     }
     /// Always add a new relationship even if an identical one exists.
     pub fn add_new(&mut self, kind: &str, target: &str, external: bool) -> String {
         let ty = if kind.starts_with("http") { kind.to_string() } else { format!("{RT_BASE}{kind}") };
         let id = format!("rId{}", self.items.len() + 1);
+        // `add` reuses the first relationship for a target, whichever call made it.
+        self.added.entry((ty.clone(), target.to_string(), external)).or_insert_with(|| id.clone());
         self.items.push((id.clone(), ty, target.to_string(), external));
         id
     }
@@ -500,6 +509,27 @@ mod tests {
         assert!(p.get("e").is_some());
     }
 
+    #[test]
+    fn many_relationships_are_found_by_index_and_first_id_wins() {
+        let n = 50_000;
+        let mut x = String::from(r#"<Relationships xmlns="http://schemas.openxmlformats.org/package/2006/relationships">"#);
+        for i in 0..n {
+            x.push_str(&format!(r#"<Relationship Id="rId{i}" Type="{RT_BASE}image" Target="../media/image{i}.png"/>"#));
+        }
+        x.push_str(&format!(r#"<Relationship Id="rId0" Type="{RT_BASE}image" Target="../media/dup.png"/></Relationships>"#));
+        let rels = rels_from_bytes(x.as_bytes(), "ppt/slides/slide1.xml");
+        assert_eq!(rels.target("rId0"), Some("ppt/media/image0.png"), "the first of a repeated id wins");
+        assert!((0..n).all(|i| rels.target(&format!("rId{i}")) == Some(&*format!("ppt/media/image{i}.png"))));
+
+        let mut out = RelsOut::default();
+        let ids: Vec<String> = (0..n).map(|i| out.add("hyperlink", &format!("https://example.com/{i}"), true)).collect();
+        assert_eq!(out.add("hyperlink", "https://example.com/7", true), ids[7], "an identical target reuses its id");
+        assert_eq!(out.add("hyperlink", "https://example.com/7", false), format!("rId{}", n + 1), "internal is distinct");
+        let fresh = out.add_new("image", "../media/a.png", false);
+        assert_ne!(out.add_new("image", "../media/a.png", false), fresh);
+        assert_eq!(out.add("image", "../media/a.png", false), fresh, "add reuses the first add_new made");
+    }
+
     #[test]
     fn backslash_zip_entry_names_are_found() {
         let z = zip_of(&[("PPT\\Slides\\Slide1.xml", 3)]);

crates/pptx/src/read.rs

@@ -46,6 +46,9 @@ 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<'_> {
@@ -446,6 +449,7 @@ 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);
@@ -487,6 +491,7 @@ 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);
@@ -663,52 +668,55 @@ fn read_slides(
     let pkg = imp.pkg;
     let fallback_layout = p.masters.first().and_then(|m| m.layouts.first()).map(|l| l.id).unwrap_or_default();
     let mut file_slide_ids: HashMap<u32, SlideId> = HashMap::new();
-    let mut notes_by_target: HashMap<String, TextBody> = HashMap::new();
+    // A notes or comments part belongs to one slide; one shared by many must not be read (and
+    // copied) once per slide that names it.
+    let mut owned_parts: HashSet<String> = HashSet::new();
     for (file_id, path, id) in slide_ids {
         let Some(doc) = docs.get(&opc::norm(path)) else { continue };
         let part = Part::new(pkg, path, doc);
         let layout = part.rels.first_of("slideLayout").and_then(|r| layout_by_part.get(&opc::norm(&r.target)).copied()).unwrap_or(fallback_layout);
         let mut slide = read_slide(imp, &part, doc, *id, layout);
-        if let Some(notes) = slide_notes(imp, &part, &mut notes_by_target) {
+        if let Some(notes) = slide_notes(imp, &part, &mut owned_parts) {
             slide.notes = notes;
         }
-        read_slide_comments(pkg, pres_part, &part, &mut slide);
+        read_slide_comments(pkg, pres_part, &part, &mut slide, &mut owned_parts);
         file_slide_ids.insert(*file_id, *id);
         p.slides.push(Arc::new(slide));
     }
     file_slide_ids
 }
 
-/// The slide's notes text, read once per notes part.
-fn slide_notes(imp: &mut Imp, part: &Part, cache: &mut HashMap<String, TextBody>) -> Option<TextBody> {
+/// The slide's notes text. A notes part is the notes of the first slide that names it.
+fn slide_notes(imp: &mut Imp, part: &Part, owned: &mut HashSet<String>) -> Option<TextBody> {
     let n = part.rels.first_of("notesSlide")?;
-    let key = opc::norm(&n.target);
-    if let Some(cached) = cache.get(&key) {
-        return Some(cached.clone());
+    if !owned.insert(opc::norm(&n.target)) {
+        log::warn!("pptx: notes part {} is named by more than one slide; kept on the first", n.target);
+        return None;
     }
     let pkg = imp.pkg;
     let nd = load(pkg, &n.target)?;
     let np = Part::new(pkg, &n.target, &nd);
-    let notes = read_notes(imp, &np, &nd.root);
-    cache.insert(key, notes.clone());
-    Some(notes)
+    Some(read_notes(imp, &np, &nd.root))
 }
 
 /// Comments. A modern part and the legacy part can describe the same threads (PowerPoint
 /// writes both): the modern one wins, its flattened legacy copy is skipped.
-fn read_slide_comments(pkg: &Package, pres_part: &Part, part: &Part, slide: &mut Slide) {
-    let mut parts: Vec<(Doc, bool)> = vec![];
+/// Each comments part is read once, for the first slide that names it.
+fn read_slide_comments(pkg: &Package, pres_part: &Part, part: &Part, slide: &mut Slide, owned: &mut HashSet<String>) {
+    let mut parts: Vec<(Doc, bool, bool)> = vec![];
     for c in part.rels.all_of("comments") {
+        // An already-owned part is not re-read, but its kind still decides modern precedence.
+        let fresh = owned.insert(opc::norm(&c.target));
         if let Some(cd) = pkg.xml(&c.target) {
             // The content type names the modern part; a package that types it only through a
             // Default entry instead of an Override is still modern when its root is p188.
             let modern = pkg.content_type(&c.target).as_deref() == Some(crate::write::CT_COMMENTS_MODERN) || cd.root.prefix() == "p188";
-            parts.push((cd, modern));
+            parts.push((cd, modern, fresh));
         }
     }
-    let has_modern = parts.iter().any(|(_, m)| *m);
-    for (cd, modern) in parts {
-        if has_modern && !modern {
+    let has_modern = parts.iter().any(|(_, m, _)| *m);
+    for (cd, modern, fresh) in parts {
+        if !fresh || (has_modern && !modern) {
             continue;
         }
         slide.comments.extend(read_comments(pkg, pres_part, &cd.root, modern));

crates/pptx/src/read/dml.rs

@@ -664,12 +664,22 @@ 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 {
-        let mut text = String::new();
-        let mut ts = vec![];
-        e.find_all("t", &mut ts);
-        for t in ts {
-            text.push_str(&t.text());
+        // 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 omml = e.elements().map(|c| part.keep_inner(c)).collect::<String>();
         para.runs.push(Run { text, props: RunProps::default(), kind: RunKind::Math { omml } });
     }
@@ -714,6 +724,17 @@ 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,7 +475,8 @@ 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)?;
-            if !imp.pkg.rels(&rel.target).items.is_empty() {
+            let pkg = imp.pkg;
+            if *imp.has_rels.entry(crate::opc::norm(&rel.target)).or_insert_with(|| !pkg.rels(&rel.target).items.is_empty()) {
                 return None;
             }
             let (kind, target) = (rel.ty.clone(), rel.target.clone());

crates/pptx/src/tables.rs

@@ -210,13 +210,20 @@ pub fn table_styles_xml(used: &[String], defs: &[deckcraft_model::table::TableSt
     let mut w = W::new();
     w.open("a:tblStyleLst", A::new().a("xmlns:a", NS_A).a("def", "{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}"));
     let names = deckcraft_model::table::table_styles();
-    let mut done: Vec<&str> = vec![];
+    // Indexes instead of scans: written ids (as given and ASCII lower-case), and the file's
+    // definitions by lower-case id (the first wins).
+    let mut done: std::collections::HashSet<&str> = std::collections::HashSet::new();
+    let mut done_lower: std::collections::HashSet<String> = std::collections::HashSet::new();
+    let mut def_of: std::collections::HashMap<String, &deckcraft_model::table::TableStyleDef> = std::collections::HashMap::new();
+    for d in defs {
+        def_of.entry(d.id.to_ascii_lowercase()).or_insert(d);
+    }
     for s in used {
-        if done.contains(&s.as_str()) {
+        if !done.insert(s.as_str()) {
             continue;
         }
-        done.push(s);
-        if let Some(d) = defs.iter().find(|d| d.id.eq_ignore_ascii_case(s))
+        done_lower.insert(s.to_ascii_lowercase());
+        if let Some(d) = def_of.get(&s.to_ascii_lowercase())
             && crate::xml::parse(d.raw.as_bytes()).is_ok_and(|x| x.root.is("tblStyle"))
         {
             w.raw(&d.raw);
@@ -231,11 +238,11 @@ pub fn table_styles_xml(used: &[String], defs: &[deckcraft_model::table::TableSt
     }
     // Styles the file defined but no table uses still belong to the deck.
     for d in defs {
-        if done.iter().any(|s| s.eq_ignore_ascii_case(&d.id)) {
+        if done_lower.contains(&d.id.to_ascii_lowercase()) {
             continue;
         }
         if crate::xml::parse(d.raw.as_bytes()).is_ok_and(|x| x.root.is("tblStyle")) {
-            done.push(&d.id);
+            done_lower.insert(d.id.to_ascii_lowercase());
             w.raw(&d.raw);
         }
     }

crates/pptx/src/write.rs

@@ -53,6 +53,8 @@ pub struct Exp<'a> {
     pub p: &'a Presentation,
     pub pkg: PackageOut,
     media_parts: HashMap<MediaId, String>,
+    /// Each media id's item in `p.media` (the first with the id, as `Presentation::media`).
+    media_at: HashMap<MediaId, usize>,
     n_image: u32,
     n_media: u32,
     n_chart: u32,
@@ -63,6 +65,8 @@ pub struct Exp<'a> {
     n_kept: u32,
     pub slide_parts: HashMap<SlideId, String>,
     pub table_styles: Vec<String>,
+    /// The ids in `table_styles`, for checking membership without a scan.
+    pub table_style_set: std::collections::HashSet<String>,
     placeholder: Option<String>,
 }
 
@@ -119,12 +123,17 @@ fn ext_for(content_type: &str, name: &str, data: &[u8]) -> String {
     if !e.is_empty() && e.len() <= 5 && e.chars().all(|c| c.is_ascii_alphanumeric()) { e } else { "bin".into() }
 }
 
-impl Exp<'_> {
+impl<'a> Exp<'a> {
+    /// The media item `id`, found through the index rather than a scan of every item.
+    pub fn media(&self, id: MediaId) -> Option<&'a deckcraft_model::MediaItem> {
+        let p: &'a Presentation = self.p;
+        self.media_at.get(&id).and_then(|&i| p.media.get(i))
+    }
     fn media_part(&mut self, id: MediaId) -> Option<String> {
         if let Some(p) = self.media_parts.get(&id) {
             return Some(p.clone());
         }
-        let m = self.p.media(id)?;
+        let m = self.media(id)?;
         if m.data.is_empty() {
             return None;
         }
@@ -147,7 +156,7 @@ impl Exp<'_> {
     }
     /// A relationship from `o` to a media item (embedded part, or external link).
     pub fn media_rel(&mut self, o: &mut Out, id: MediaId, kind: &str) -> Option<String> {
-        let m = self.p.media(id)?;
+        let m = self.media(id)?;
         if m.data.is_empty() {
             let link = m.link.clone()?;
             return Some(o.rels.add(kind, &link, true));
@@ -156,7 +165,7 @@ impl Exp<'_> {
         Some(o.rels.add(kind, &opc::relative(&o.name, &part), false))
     }
     pub fn media_rel_new(&mut self, o: &mut Out, id: MediaId, kind: &str) -> Option<String> {
-        let m = self.p.media(id)?;
+        let m = self.media(id)?;
         if m.data.is_empty() {
             return None;
         }
@@ -489,7 +498,8 @@ fn valid_date(s: &str) -> bool {
 /// A copy of the presentation with every slide pointing at a layout that exists.
 fn sanitized(p: &Presentation) -> std::borrow::Cow<'_, Presentation> {
     let mut need = p.masters.is_empty() || p.masters.iter().any(|m| m.layouts.is_empty());
-    need |= p.slides.iter().any(|s| p.layout(s.layout).is_none());
+    let layouts: std::collections::HashSet<_> = p.masters.iter().flat_map(|m| m.layouts.iter().map(|l| l.id)).collect();
+    need |= p.slides.iter().any(|s| !layouts.contains(&s.layout));
     if !need {
         return std::borrow::Cow::Borrowed(p);
     }
@@ -532,6 +542,13 @@ pub fn export(p: &Presentation, main_ct: &str) -> Result<Vec<u8>, PptxError> {
         p,
         pkg: PackageOut::default(),
         media_parts: HashMap::new(),
+        media_at: {
+            let mut m = HashMap::new();
+            for (i, item) in p.media.iter().enumerate() {
+                m.entry(item.id).or_insert(i);
+            }
+            m
+        },
         n_image: 0,
         n_media: 0,
         n_chart: 0,
@@ -541,6 +558,7 @@ pub fn export(p: &Presentation, main_ct: &str) -> Result<Vec<u8>, PptxError> {
         n_kept: 0,
         slide_parts: HashMap::new(),
         table_styles: vec![],
+        table_style_set: Default::default(),
         placeholder: None,
     };
     for (i, s) in p.slides.iter().enumerate() {
@@ -959,9 +977,16 @@ fn section_slides(p: &Presentation) -> Vec<(String, Vec<usize>)> {
     if out.is_empty() {
         return out;
     }
+    // Each slide's first section, found once: a section may name a slide many times.
+    let mut first: HashMap<SlideId, usize> = HashMap::new();
+    for (k, sec) in p.sections.iter().enumerate() {
+        for id in &sec.slides {
+            first.entry(*id).or_insert(k);
+        }
+    }
     let mut cur = 0usize;
     for (i, s) in p.slides.iter().enumerate() {
-        if let Some(k) = p.sections.iter().position(|sec| sec.slides.contains(&s.id))
+        if let Some(&k) = first.get(&s.id)
             && k >= cur
         {
             cur = k;
@@ -1027,7 +1052,7 @@ fn write_embedded_fonts(x: &mut Exp, o: &mut Out) -> Vec<WrittenFont> {
         if let Some(rid) = seen_part.get(&id) {
             return Some(rid.clone());
         }
-        let m = x.p.media(id)?;
+        let m = x.media(id)?;
         if m.data.is_empty() || m.data.len() > 32 * 1024 * 1024 {
             return None;
         }

crates/pptx/src/write/dml.rs

@@ -100,7 +100,7 @@ pub fn fill(w: &mut W, x: &mut Exp, o: &mut Out, f: &Fill) {
 pub fn blip_fill(w: &mut W, x: &mut Exp, o: &mut Out, tag: &str, pf: &PictureFill) {
     // An image that lives outside the package is a linked picture: `a:blip` names it through
     // `r:link`; `r:embed` may only reference a part inside the package.
-    let linked = x.p.media(pf.media).is_some_and(|m| m.data.is_empty() && m.link.is_some());
+    let linked = x.media(pf.media).is_some_and(|m| m.data.is_empty() && m.link.is_some());
     let rid = x.media_rel(o, pf.media, "image").unwrap_or_else(|| x.placeholder_rel(o));
     w.open(tag, A::new().a("rotWithShape", if pf.upright { "0" } else { "1" }));
     let adj = &pf.adjust;
@@ -449,7 +449,7 @@ pub fn hyperlink(w: &mut W, x: &mut Exp, o: &mut Out, tag: &str, h: &Hyperlink)
         return;
     };
     w.open(tag, attrs);
-    let name = x.p.media(sound_id).map(|m| sound_label(&m.name)).unwrap_or_else(|| "sound.wav".into());
+    let name = x.media(sound_id).map(|m| sound_label(&m.name)).unwrap_or_else(|| "sound.wav".into());
     w.empty("a:snd", A::new().a("r:embed", sound_rid).a("name", name));
     w.close(tag);
 }
@@ -601,7 +601,7 @@ pub fn ppr(w: &mut W, x: &mut Exp, o: &mut Out, tag: &str, level: Option<u8>, p:
         Some(Bullet::Picture { media }) => match x.media_rel(o, *media, "image") {
             Some(rid) => {
                 w.open0("a:buBlip");
-                let a = if x.p.media(*media).is_some_and(|m| m.data.is_empty() && m.link.is_some()) {
+                let a = if x.media(*media).is_some_and(|m| m.data.is_empty() && m.link.is_some()) {
                     A::new().a("r:link", &rid)
                 } else {
                     A::new().a("r:embed", &rid)
@@ -762,17 +762,27 @@ pub fn text_body(w: &mut W, x: &mut Exp, o: &mut Out, tag: &str, tb: &TextBody,
 }
 
 fn run_text(w: &mut W, x: &mut Exp, o: &mut Out, text: &str, props: &RunProps) {
+    // The run's properties are the same for every piece and line break: serialize them once.
+    let mut rpr_xml: Option<String> = None;
+    let mut put_rpr = |w: &mut W| match &rpr_xml {
+        Some(xml) => w.s.push_str(xml),
+        None => {
+            let start = w.s.len();
+            rpr(w, x, o, "a:rPr", props);
+            rpr_xml = Some(w.s[start..].to_string());
+        }
+    };
     for (i, piece) in text.split(['\n', '\u{b}']).enumerate() {
         if i > 0 {
             w.open0("a:br");
-            rpr(w, x, o, "a:rPr", props);
+            put_rpr(w);
             w.close("a:br");
         }
         if piece.is_empty() && i > 0 {
             continue;
         }
         w.open0("a:r");
-        rpr(w, x, o, "a:rPr", props);
+        put_rpr(w);
         w.elt("a:t", piece);
         w.close("a:r");
     }

crates/pptx/src/write/shapes.rs

@@ -446,7 +446,7 @@ pub fn shape(w: &mut W, x: &mut Exp, o: &mut Out, cx: &mut Ctx, s: &Shape, depth
 }
 
 fn model_rel(x: &mut Exp, o: &mut Out, media: deckcraft_model::MediaId) -> Option<String> {
-    if x.p.media(media).is_none_or(|m| m.data.is_empty()) {
+    if x.media(media).is_none_or(|m| m.data.is_empty()) {
         return None;
     }
     x.media_rel(o, media, crate::opc::RT_MODEL3D)
@@ -479,7 +479,7 @@ fn write_model(
         return;
     };
     let id = cx.id_for(s);
-    let poster = poster.filter(|p| x.p.media(*p).is_some_and(|m| !m.data.is_empty()));
+    let poster = poster.filter(|p| x.media(*p).is_some_and(|m| !m.data.is_empty()));
     let Some(poster) = poster else {
         write_model_part(w, x, o, id, s, &rid);
         return;
@@ -700,7 +700,7 @@ fn table(w: &mut W, x: &mut Exp, o: &mut Out, t: &Table) {
     t.normalize();
     w.open0("a:tbl");
     let (guid, _) = crate::tables::guid_for_style(&t.style);
-    if !x.table_styles.contains(&t.style) {
+    if x.table_style_set.insert(t.style.clone()) {
         x.table_styles.push(t.style.clone());
     }
     w.open(
@@ -884,7 +884,7 @@ fn opaque(
         p.name = label.to_string();
     }
     match preview {
-        Some(m) if x.p.media(m).is_some() => {
+        Some(m) if x.media(m).is_some() => {
             p.kind = ShapeKind::Picture { fill: deckcraft_model::style::PictureFill { media: m, ..Default::default() } };
             p.ph = None;
             shape_with_id(w, x, o, cx, &p, id);

crates/pptx/src/write/timing.rs

@@ -1,7 +1,7 @@
 //! Transitions and the animation timing tree.
 
 use deckcraft_model::anim::{AnimClass, AnimStart, Animation, BuildRole, TextBuild, Transition, build_filled, paragraph_build_roles};
-use deckcraft_model::{Shape, ShapeId, ShapeKind, find_shape};
+use deckcraft_model::{Shape, ShapeId, ShapeKind};
 
 use super::shapes::IdMap;
 use super::{Exp, Out};
@@ -16,7 +16,7 @@ pub fn transition(w: &mut W, x: &mut Exp, o: &mut Out, t: &Transition) {
         601..=900 => "med",
         _ => "slow",
     };
-    let sound = t.sound.and_then(|m| x.media_rel(o, m, "audio").map(|r| (r, x.p.media(m).map(|i| i.name.clone()).unwrap_or_default())));
+    let sound = t.sound.and_then(|m| x.media_rel(o, m, "audio").map(|r| (r, x.media(m).map(|i| i.name.clone()).unwrap_or_default())));
     let snd = |w: &mut W| {
         if let Some((r, name)) = &sound {
             w.open0("p:sndAc");
@@ -577,6 +577,21 @@ fn click_pars(w: &mut W, x: &mut Exp, ids: &mut Ids, clicks: &Groups, interactiv
     }
 }
 
+/// Most effects one slide's timing writes; animations past it are left out.
+const MAX_EFFECTS: usize = 100_000;
+
+/// The shapes of the tree by id, the first in document order for a repeated id (as `find_shape`
+/// finds it), so each animation resolves its shape without a tree walk.
+fn shape_index<'a>(shapes: &'a [Shape], depth: usize, out: &mut std::collections::HashMap<ShapeId, &'a Shape>) {
+    if depth > 64 {
+        return;
+    }
+    for s in shapes {
+        out.entry(s.id).or_insert(s);
+        shape_index(s.children(), depth + 1, out);
+    }
+}
+
 /// Write `p:timing` for a slide's animations.
 pub fn timing(w: &mut W, x: &mut Exp, anims: &[Animation], shapes: &[Shape], idmap: &IdMap) {
     let mut grp_count: std::collections::HashMap<u32, u32> = Default::default();
@@ -585,16 +600,31 @@ pub fn timing(w: &mut W, x: &mut Exp, anims: &[Animation], shapes: &[Shape], idm
     let mut bld: Vec<(u32, u32, bool)> = vec![];
     // The last paragraph effect written: (shape, class, trigger, grpId).
     let mut prev_para: Option<(ShapeId, AnimClass, Option<ShapeId>, u32)> = None;
+    let mut by_id = std::collections::HashMap::new();
+    shape_index(shapes, 0, &mut by_id);
+    let mut roles_of: std::collections::HashMap<ShapeId, Vec<BuildRole>> = Default::default();
+    let mut effect_count = 0usize;
+    let mut warned = false;
     for a in anims.iter().take(10_000) {
+        if effect_count >= MAX_EFFECTS {
+            if !warned {
+                log::warn!("pptx: more than {MAX_EFFECTS} animation effects; the rest are left out");
+            }
+            break;
+        }
         let Some(spid) = idmap.get(a.shape) else {
             log::warn!("pptx: animation on missing shape {} skipped", a.shape);
             continue;
         };
-        let Some(shape) = find_shape(shapes, a.shape) else { continue };
+        let Some(&shape) = by_id.get(&a.shape) else { continue };
         let text_sp = matches!(shape.kind, ShapeKind::Shape) && shape.text.is_some();
         let is_text_sp = matches!(shape.kind, ShapeKind::Shape) && shape.text.as_ref().is_some_and(|t| !t.is_empty());
         let text = shape.text.as_ref().filter(|_| a.text_build == TextBuild::ByParagraph && is_text_sp);
-        let roles = text.map(paragraph_build_roles).unwrap_or_default();
+        let no_roles = Vec::new();
+        let roles = match text {
+            Some(t) => roles_of.entry(a.shape).or_insert_with(|| paragraph_build_roles(t)),
+            None => &no_roles,
+        };
         let by_para = roles.contains(&BuildRole::Top);
         // PowerPoint keeps a shape's consecutive paragraph effects in one build (`grpId`) marked
         // `build="p"`; the reader turns them back into a by-paragraph build only if that plays them
@@ -632,11 +662,19 @@ pub fn timing(w: &mut W, x: &mut Exp, anims: &[Animation], shapes: &[Shape], idm
                     _ => continue,
                 };
                 let Ok(pi) = u32::try_from(i) else { break };
+                if effect_count + effs.len() >= MAX_EFFECTS {
+                    if !warned {
+                        log::warn!("pptx: more than {MAX_EFFECTS} animation effects; the rest are left out");
+                        warned = true;
+                    }
+                    break;
+                }
                 effs.push(Eff { a, spid, start, paragraph: Some(pi), grp });
             }
         } else {
             effs.push(Eff { a, spid, start: a.start, paragraph: a.paragraph, grp });
         }
+        effect_count += effs.len();
         if text_sp && !joins {
             bld.push((spid, grp, by_para || para_effect));
         }

crates/pptx/tests/it/comments.rs

@@ -146,6 +146,33 @@ fn comments_on_several_slides_round_trip() {
     assert_eq!(q.slides[2].comments[0].text, "Slide three");
 }
 
+/// A slide that names a modern part another slide already owns, plus its own legacy part, must
+/// not import the legacy copy: modern precedence holds even when the modern part is not re-read.
+#[test]
+fn owned_modern_part_still_suppresses_later_legacy() {
+    let mut p = deck();
+    let layout = p.slides[0].layout;
+    let s2 = defaults::new_slide(&mut p, layout).expect("slide");
+    p.slides.push(Arc::new(s2));
+    Arc::make_mut(&mut p.slides[1]).comments = vec![Comment { author: "Cara".into(), text: "Slide two".into(), ..Default::default() }];
+    let bytes = deckcraft_pptx::export(&p).expect("export");
+    let rels2 = part(&bytes, "ppt/slides/_rels/slide2.xml.rels").replace("modernComment2.xml", "modernComment1.xml");
+    let mut z = zip::ZipArchive::new(std::io::Cursor::new(&bytes)).expect("zip");
+    let mut out = zip::ZipWriter::new(std::io::Cursor::new(Vec::new()));
+    for i in 0..z.len() {
+        let mut f = z.by_index(i).expect("entry");
+        out.start_file(f.name(), zip::write::SimpleFileOptions::default()).expect("start");
+        if f.name() == "ppt/slides/_rels/slide2.xml.rels" {
+            std::io::Write::write_all(&mut out, rels2.as_bytes()).expect("write");
+        } else {
+            std::io::copy(&mut f, &mut out).expect("copy");
+        }
+    }
+    let q = deckcraft_pptx::import(&out.finish().expect("finish").into_inner()).expect("import");
+    assert_eq!(q.slides[0].comments.len(), 2);
+    assert!(q.slides[1].comments.is_empty(), "{:?}", q.slides[1].comments);
+}
+
 /// A legacy-only package (what older tools read and write) still imports: 1/8 pt positions,
 /// flattened replies.
 #[test]

crates/pptx/tests/it/export_scale.rs

@@ -0,0 +1,31 @@
+//! Export looks media, layouts, sections and table styles up by id: a deck with many of each and
+//! many references to the last ones exports in time linear in its size.
+
+use std::sync::Arc;
+
+use deckcraft_model::style::PictureFill;
+use deckcraft_model::{Section, Shape, ShapeId, ShapeKind, defaults};
+
+#[test]
+fn many_media_sections_and_table_styles_export() {
+    let mut p = defaults::new_presentation(None);
+    // 5,000 media items; 5,000 pictures of the last one.
+    let mut last = None;
+    for i in 0..5_000u32 {
+        last = p.add_media(&format!("m{i}.png"), "image/png", i.to_le_bytes().to_vec());
+    }
+    let last = last.unwrap();
+    let pic = |k: u32| Shape {
+        id: ShapeId(100_000 + k),
+        kind: ShapeKind::Picture { fill: PictureFill { media: last, ..Default::default() } },
+        ..Default::default()
+    };
+    Arc::make_mut(&mut p.slides[0]).shapes = (0..5_000).map(pic).collect();
+    // A section naming the slide 50,000 times, after 2,000 empty sections.
+    let id = p.slides[0].id;
+    p.sections = (0..2_000).map(|i| Section { name: format!("s{i}"), slides: vec![] }).collect();
+    p.sections.push(Section { name: "last".into(), slides: vec![id; 50_000] });
+    let bytes = deckcraft_pptx::export(&p).expect("export");
+    let q = deckcraft_pptx::import(&bytes).expect("import");
+    assert_eq!(q.slides[0].shapes.iter().filter(|s| matches!(s.kind, ShapeKind::Picture { .. })).count(), 5_000);
+}

crates/pptx/tests/it/main.rs

@@ -9,6 +9,7 @@ mod corpus_kinds;
 mod corpus_media;
 mod corpus_style;
 mod corpus_themes;
+mod export_scale;
 mod fills;
 mod kept_parts;
 mod locks;

crates/pptx/tests/it/malformed.rs

@@ -287,3 +287,34 @@ fn unreadable_slide_is_reported() {
     assert_eq!(lost, vec!["ppt/slides/slide2.xml".to_string()]);
     assert_eq!(deckcraft_pptx::import(&broken).expect("import").slides.len(), 1);
 }
+
+/// Many slides naming one notes part: it is read for the first slide only, not copied onto every
+/// slide that names it.
+#[test]
+fn a_shared_notes_part_is_read_once() {
+    use std::sync::Arc;
+    let mut p = defaults::new_presentation(None);
+    let layout = p.slides[0].layout;
+    for _ in 0..3 {
+        let s = defaults::new_slide(&mut p, layout).expect("slide");
+        p.slides.push(Arc::new(s));
+    }
+    for (i, s) in p.slides.iter_mut().enumerate() {
+        Arc::make_mut(s).notes = deckcraft_model::text::TextBody::from_text(&format!("notes {i}"));
+    }
+    let mut es = entries(&deckcraft_pptx::export(&p).expect("export"));
+    for (n, d) in es.iter_mut() {
+        if n.starts_with("ppt/slides/_rels/") {
+            let x = String::from_utf8(d.clone()).expect("utf8");
+            let x = x
+                .replace("notesSlide2.xml", "notesSlide1.xml")
+                .replace("notesSlide3.xml", "notesSlide1.xml")
+                .replace("notesSlide4.xml", "notesSlide1.xml");
+            *d = x.into_bytes();
+        }
+    }
+    let q = deckcraft_pptx::import(&rezip(&es)).expect("import");
+    assert_eq!(q.slides.len(), 4);
+    assert_eq!(q.slides[0].notes.text(), "notes 0");
+    assert!(q.slides[1..].iter().all(|s| s.notes.text().is_empty()), "a shared notes part is not copied");
+}

crates/render/src/chart.rs

@@ -1,5 +1,7 @@
 //! Charts: title, plot area with axes and gridlines, series marks, legend.
 
+use std::collections::HashMap;
+
 use deckcraft_color::{ColorTransform, Rgba, SchemeSlot};
 use deckcraft_model::Shape;
 use deckcraft_model::chart::{Chart, ChartType, TrendlineType, axis_scale};
@@ -85,9 +87,9 @@ fn bar_outline(ctx: &Ctx, s: &deckcraft_model::chart::Series) -> Option<(Rgba, f
 /// Paint of one bar: a `<c:dPt>` fill wins, and a single-series chart that varies colours by point uses one accent per point
 /// (not waterfalls, which are never read from a `<c:barChart>`). Pattern fills draw as patterns and
 /// `a:noFill` leaves the bar empty, as in PowerPoint.
-fn bar_paint(ctx: &Ctx, c: &Chart, si: usize, pi: usize, s: &deckcraft_model::chart::Series) -> Paint {
-    if let Some((_, f)) = s.point_fills.iter().find(|(k, _)| *k == pi) {
-        return paint_of(ctx, Some(f), series_fill(ctx, c, si, Some(s)));
+fn bar_paint(ctx: &Ctx, c: &Chart, si: usize, pi: usize, s: &deckcraft_model::chart::Series, fills: Option<&HashMap<usize, &Fill>>) -> Paint {
+    if let Some(f) = fills.and_then(|m| m.get(&pi)) {
+        return paint_of(ctx, Some(*f), series_fill(ctx, c, si, Some(s)));
     }
     if c.vary_colors && c.series.len() == 1 && s.fill.is_none() && c.kind != ChartType::Waterfall {
         return Paint::Color(series_color(ctx, c, pi));
@@ -883,6 +885,8 @@ fn draw_lines(ctx: &mut RenderContext, draw: &mut LineDrawing<'_, '_>) {
         let col = if area_kind { series_fill(rctx, c, si, Some(s)) } else { series_line(rctx, c, si, s) };
         let series_stats = s.error_bars.as_ref().map(|_| deckcraft_model::chart::SeriesStats::of(&s.values));
         let mut pts = vec![];
+        // Whether the series has any x value, found once rather than per point.
+        let any_x = s.x_values.iter().flatten().next().is_some();
         for i in 0..ncat {
             let Some(v) = s.values.get(i).copied().flatten() else { continue };
             let v = if stacked {
@@ -896,11 +900,11 @@ fn draw_lines(ctx: &mut RenderContext, draw: &mut LineDrawing<'_, '_>) {
             };
             let x = match kind {
                 ChartType::Scatter | ChartType::Bubble => {
-                    match (s.x_values.get(i).copied().flatten().and_then(to_x), s.x_values.iter().flatten().next()) {
+                    match (s.x_values.get(i).copied().flatten().and_then(to_x), any_x) {
                         (Some(x), _) => x,
                         // No x values at all: the points are numbered 1, 2, 3...
-                        (None, None) => to_x(i as f64 + 1.0).unwrap_or(plot.x0 + band * (slot(i) + 0.5)),
-                        (None, Some(_)) => continue,
+                        (None, false) => to_x(i as f64 + 1.0).unwrap_or(plot.x0 + band * (slot(i) + 0.5)),
+                        (None, true) => continue,
                     }
                 }
                 _ => plot.x0 + band * (slot(i) + 0.5),
@@ -970,6 +974,19 @@ fn draw_bars(ctx: &mut RenderContext, draw: &BarDrawing<'_, '_>) -> Vec<(f64, f6
         let group = bar + step * (n - 1.0);
         // Error bars need each series' mean and spread: worked out once, not per point.
         let stats: Vec<deckcraft_model::chart::SeriesStats> = bars.iter().map(|(_, s)| deckcraft_model::chart::SeriesStats::of(&s.values)).collect();
+        // Each series' per-point fills by point (the first for a point wins), not searched per bar.
+        let point_fills: Vec<HashMap<usize, &Fill>> = bars
+            .iter()
+            .map(|(_, s)| {
+                let mut m = HashMap::new();
+                for (k, f) in &s.point_fills {
+                    m.entry(*k).or_insert(f);
+                }
+                m
+            })
+            .collect();
+        // A waterfall's running bars, worked out once for all its categories.
+        let waterfall_bars = if waterfall { c.waterfall_bars() } else { Vec::new() };
         for i in 0..ncat {
             let mut pos_acc = 0.0;
             let mut neg_acc = 0.0;
@@ -983,7 +1000,7 @@ fn draw_bars(ctx: &mut RenderContext, draw: &BarDrawing<'_, '_>) -> Vec<(f64, f6
                 let v = s.values.get(i).copied().flatten().unwrap_or(0.0) / total;
                 let start = band * slot(i) + (band - group) / 2.0 + if stacked { 0.0 } else { step * bi as f64 };
                 let (a, b) = if waterfall {
-                    c.waterfall_bars().get(i).copied().unwrap_or_default()
+                    waterfall_bars.get(i).copied().unwrap_or_default()
                 } else if stacked {
                     if v >= 0.0 {
                         let r = (pos_acc, pos_acc + v);
@@ -1015,7 +1032,7 @@ fn draw_bars(ctx: &mut RenderContext, draw: &BarDrawing<'_, '_>) -> Vec<(f64, f6
                     };
                     Paint::Color(series_color(rctx, c, slot))
                 } else {
-                    bar_paint(rctx, c, *si, i, s)
+                    bar_paint(rctx, c, *si, i, s, point_fills.get(bi))
                 };
                 fill_with(ctx, &paint, r.abs(), m);
                 if !waterfall && let Some((oc, ow)) = bar_outline(rctx, s).filter(|o| o.1 > 0.0) {

crates/render/src/images.rs

@@ -37,7 +37,8 @@ struct Cache {
     bad_order: VecDeque<usize>,
     bad_bytes: usize,
     /// GIFs by bytes address and adjustments (`None`: not animated); the bytes stay alive with them.
-    anims: HashMap<(usize, u64), (Arc<Vec<u8>>, Option<Arc<Anim>>)>,
+    /// Decoded animations by (bytes, adjustments), each with the clock of its last use.
+    anims: HashMap<(usize, u64), (Arc<Vec<u8>>, Option<Arc<Anim>>, u64)>,
 }
 
 /// Longest side, total decoded size and frame count kept for one animated GIF; the largest canvas
@@ -432,16 +433,33 @@ fn anim(bytes: &Arc<Vec<u8>>, adj: &PictureAdjust) -> Option<Arc<Anim>> {
         return None;
     }
     let key = (Arc::as_ptr(bytes) as usize, adjust_key(adj));
-    if let Some(a) = with(|c| c.anims.get(&key).map(|e| e.1.clone())) {
+    let hit = with(|c| {
+        c.clock += 1;
+        let clock = c.clock;
+        c.anims.get_mut(&key).map(|e| {
+            e.2 = clock;
+            e.1.clone()
+        })
+    });
+    if let Some(a) = hit {
         return a;
     }
     let a = decode_anim(bytes, adj).map(Arc::new);
     with(|c| {
-        let held: usize = c.anims.values().filter_map(|e| e.1.as_ref()).map(|a| a.bytes()).sum();
-        if held + a.as_ref().map_or(0, |a| a.bytes()) > GIF_CACHE_BUDGET || c.anims.len() >= 64 {
-            c.anims.clear();
+        // Make room by dropping the least recently used animations, not every one of them, so a
+        // slide whose animations overflow the cache does not decode all of them again each frame.
+        let new = a.as_ref().map_or(0, |a| a.bytes());
+        loop {
+            let held: usize = c.anims.values().filter_map(|e| e.1.as_ref()).map(|a| a.bytes()).sum();
+            if held + new <= GIF_CACHE_BUDGET && c.anims.len() < 64 {
+                break;
+            }
+            let Some(oldest) = c.anims.iter().min_by_key(|(_, e)| e.2).map(|(k, _)| *k) else { break };
+            c.anims.remove(&oldest);
         }
-        c.anims.insert(key, (bytes.clone(), a.clone()));
+        c.clock += 1;
+        let clock = c.clock;
+        c.anims.insert(key, (bytes.clone(), a.clone(), clock));
     });
     a
 }
@@ -535,6 +553,26 @@ mod tests {
         out.into_inner()
     }
 
+    /// A two-frame GIF whose first pixel is `n`, so each one has its own bytes.
+    fn gif(n: u8) -> Arc<Vec<u8>> {
+        use image::codecs::gif::GifEncoder;
+        let frame = |c: u8| image::Frame::new(image::RgbaImage::from_pixel(2, 2, image::Rgba([n, c, 0, 255])));
+        let mut out = Vec::new();
+        GifEncoder::new(&mut out).encode_frames([frame(0), frame(255)]).expect("encode");
+        Arc::new(out)
+    }
+
+    #[test]
+    fn a_full_animation_cache_drops_the_oldest_entry_not_all_of_them() {
+        let adj = PictureAdjust::default();
+        let gifs: Vec<_> = (0..70).map(gif).collect();
+        for g in &gifs {
+            assert!(anim(g, &adj).is_some());
+        }
+        let (len, newest) = with(|c| (c.anims.len(), c.anims.contains_key(&(Arc::as_ptr(&gifs[69]) as usize, adjust_key(&adj)))));
+        assert!(newest && len >= 32, "{len} cached");
+    }
+
     #[test]
     fn rgba_conversion_is_refused_past_the_cap() {
         let png = grey_png(100, 50);

crates/render/src/morph_text.rs

@@ -76,16 +76,12 @@ fn tokens(l: &TextLayout, chars: bool) -> (Vec<Token>, Vec<(usize, usize)>) {
 
 /// For each token of `b`, the token of `a` with the same text, in reading order, each used once.
 fn matches(a: &[Token], b: &[Token]) -> Vec<Option<usize>> {
-    let mut used = vec![false; a.len()];
-    b.iter()
-        .map(|tb| {
-            let i = a.iter().enumerate().position(|(i, ta)| !used.get(i).copied().unwrap_or(true) && ta.key == tb.key)?;
-            if let Some(u) = used.get_mut(i) {
-                *u = true;
-            }
-            Some(i)
-        })
-        .collect()
+    // Unused tokens of `a` by text, in reading order, so each lookup is a pop rather than a scan.
+    let mut free: std::collections::HashMap<&str, std::collections::VecDeque<usize>> = std::collections::HashMap::new();
+    for (i, ta) in a.iter().enumerate() {
+        free.entry(ta.key.as_str()).or_default().push_back(i);
+    }
+    b.iter().map(|tb| free.get_mut(tb.key.as_str())?.pop_front()).collect()
 }
 
 fn layout(ctx: &Ctx, s: &Shape, x: Xfrm, fields: &dyn Fields) -> Option<TextLayout> {
@@ -228,3 +224,19 @@ pub(crate) fn draw(
 pub(crate) fn token_keys(l: &TextLayout, chars: bool) -> Vec<String> {
     tokens(l, chars).0.into_iter().map(|t| t.key).collect()
 }
+
+#[cfg(test)]
+mod match_tests {
+    use super::*;
+
+    fn tok(k: &str) -> Token {
+        Token { key: k.into(), glyphs: Vec::new(), origin: Point::ZERO, run: 0 }
+    }
+
+    #[test]
+    fn each_source_token_is_used_once_in_reading_order() {
+        let a: Vec<Token> = ["a", "b", "a"].map(tok).into();
+        let b: Vec<Token> = ["a", "a", "a", "b", "c"].map(tok).into();
+        assert_eq!(matches(&a, &b), vec![Some(0), Some(2), None, Some(1), None]);
+    }
+}

crates/render/src/placed.rs

@@ -131,9 +131,11 @@ fn place(out: &mut Placed, rctx: &Ctx, fields: &SlideFields, s: &Shape, parent:
         }
         ShapeKind::Table(t) => {
             // Cell text, laid out exactly as the table draws it.
+            // The table's style is looked up once, not once per cell.
+            let def = table::resolve_style(rctx, t);
             for (r, c, rect) in table::cell_rects(t, &table::row_heights(rctx, t, fields)) {
                 let Some(cell) = t.cell(r, c).filter(|cell| !cell.text.is_empty()) else { continue };
-                let body = table::cell_body(rctx, t, r, c, cell);
+                let body = table::cell_body_with_def(rctx, def, t, r, c, cell);
                 let tmp = Shape::table_cell(body.clone());
                 place_text(out, rctx, fields, s.id, &tmp, &body, rect, m);
             }

crates/render/src/renderer.rs

@@ -33,6 +33,10 @@ pub struct Renderer {
     /// Visits spent on outer-shadow silhouette passes, kept apart so they cannot use up the budget
     /// of the normal drawing that follows.
     shadow_work: usize,
+    /// `RenderOpts::skip` as a set, with the slice (address, length) it was built from: the
+    /// slice can be as long as the slide, and is tested for every shape drawn. Forgotten when a
+    /// frame starts, so another frame's slice at the same address is never mistaken for it.
+    skip: Option<(usize, usize, std::collections::HashSet<ShapeId>)>,
 }
 
 impl Default for Renderer {
@@ -48,6 +52,7 @@ impl Default for Renderer {
             in_shadow_pass: false,
             render_work: 0,
             shadow_work: 0,
+            skip: None,
         }
     }
 }
@@ -163,6 +168,7 @@ impl Renderer {
     pub(crate) fn slide(&mut self, pres: &Presentation, slide: &Slide, index: usize, opts: &RenderOpts) -> Image {
         self.render_work = 0;
         self.shadow_work = 0;
+        self.skip = None;
         self.in_shadow_pass = false;
         let (mut ctx, w, h, view) = Self::canvas(pres, opts, needs_filters(pres, slide));
         let f = Frame { pres, opts, fields: Self::fields(pres, index, opts) };
@@ -178,6 +184,7 @@ impl Renderer {
     pub(crate) fn slide_part(&mut self, pres: &Presentation, slide: &Slide, index: usize, part: SlidePart, opts: &RenderOpts) -> Image {
         self.render_work = 0;
         self.shadow_work = 0;
+        self.skip = None;
         self.in_shadow_pass = false;
         let (mut ctx, w, h, view) = Self::canvas(pres, opts, needs_filters(pres, slide));
         let f = Frame { pres, opts, fields: Self::fields(pres, index, opts) };
@@ -212,6 +219,7 @@ impl Renderer {
         let mix = if mix.is_finite() { mix.clamp(0.0, 1.0) } else { 1.0 };
         self.render_work = 0;
         self.shadow_work = 0;
+        self.skip = None;
         self.in_shadow_pass = false;
         let (mut ctx, w, h, view) = Self::canvas(pres, opts, needs_filters(pres, old.0) || needs_filters(pres, new.0));
         let (Some(co), Some(cn)) = (Ctx::for_slide(pres, old.0), Ctx::for_slide(pres, new.0)) else { return self.finish(ctx, w, h) };
@@ -260,6 +268,7 @@ impl Renderer {
     pub(crate) fn layout(&mut self, pres: &Presentation, mi: usize, li: Option<usize>, opts: &RenderOpts) -> Image {
         self.render_work = 0;
         self.shadow_work = 0;
+        self.skip = None;
         self.in_shadow_pass = false;
         let (w, h) = output_size(pres, opts);
         let mut ctx = RenderContext::new_with(w, h, vello_cpu::RenderSettings { num_threads: 0, ..Default::default() });
@@ -393,8 +402,25 @@ impl Renderer {
         geo
     }
 
+    /// Whether `id` is in `skip`, looked up in a set built once per frame and slice.
+    fn skipped(&mut self, skip: &[ShapeId], id: ShapeId) -> bool {
+        if skip.is_empty() {
+            return false;
+        }
+        let key = (skip.as_ptr() as usize, skip.len());
+        match &self.skip {
+            Some((p, n, set)) if (*p, *n) == key => set.contains(&id),
+            _ => {
+                let set: std::collections::HashSet<ShapeId> = skip.iter().copied().collect();
+                let hit = set.contains(&id);
+                self.skip = Some((key.0, key.1, set));
+                hit
+            }
+        }
+    }
+
     fn shape_at(&mut self, ctx: &mut RenderContext, f: &Frame, rctx: &Ctx, s: &Shape, parent: Affine, depth: usize) {
-        if depth > 32 || (s.hidden && !f.opts.show_hidden) || f.opts.skip.contains(&s.id) {
+        if depth > 32 || (s.hidden && !f.opts.show_hidden) || self.skipped(f.opts.skip, s.id) {
             return;
         }
         let work = if self.in_shadow_pass { &mut self.shadow_work } else { &mut self.render_work };

crates/render/src/stroke.rs

@@ -191,7 +191,8 @@ pub(crate) fn limit_dash_count(path: &BezPath, pat: Vec<f64>) -> Vec<f64> {
         return pat;
     }
     let len: f64 = path.segments().map(|s| s.arclen(1e-2)).sum();
-    let dashes = len / period;
+    // Every dash of the pattern counts, not each repeat of it: a custom pattern can hold many.
+    let dashes = len / period * pat.len().div_ceil(2) as f64;
     if !len.is_finite() {
         return vec![];
     }

crates/render/src/tests_wild.rs

@@ -990,4 +990,37 @@ fn a_tiny_dash_on_a_huge_shape_draws_without_running_out_of_memory() {
     p.line_to((4.0e6, 0.0));
     let pat = limit_dash_count(&p, vec![1.0, 1.0]);
     assert!((4.0e6 / (pat[0] + pat[1]) - MAX_DASHES).abs() < 1.0, "{pat:?}");
+    // A custom pattern of 1,000 dashes counts each of them: the limit is on dashes drawn.
+    let pat = limit_dash_count(&p, vec![1.0; 2000]);
+    let period: f64 = pat.iter().sum();
+    assert!((4.0e6 / period * 1000.0 - MAX_DASHES).abs() < 1.0, "{}", period);
+}
+
+/// A bar chart with 20,000 points, each with its own fill, and a sparse scatter of the same size:
+/// the per-point fills and the scatter's "has any x" are looked up, not searched per point.
+#[test]
+fn many_point_fills_and_sparse_scatter_x_render() {
+    use deckcraft_model::ShapeKind;
+    use deckcraft_model::chart::{Chart, ChartType};
+    use deckcraft_model::style::Fill;
+    let n = 20_000;
+    let chart = |kind: ChartType| {
+        let mut c = Chart::sample(kind);
+        c.series.truncate(1);
+        c.categories = (0..n).map(|i| i.to_string()).collect();
+        c.series[0].values = (0..n).map(|i| Some(i as f64)).collect();
+        c
+    };
+    let mut bars = chart(ChartType::Column);
+    bars.series[0].point_fills = (0..n).rev().map(|i| (i, Fill::solid(ColorRef::rgb(Rgba::rgb(200, 0, 0))))).collect();
+    let mut scatter = chart(ChartType::Scatter);
+    scatter.series[0].x_values = (0..n).map(|i| (i + 1 == n).then_some(1.0)).collect();
+    let shape = |id: u32, c: Chart| Shape {
+        id: ShapeId(id),
+        xfrm: Some(Xfrm::new(10.0, 10.0, 400.0, 300.0)),
+        kind: ShapeKind::Chart(Box::new(c)),
+        ..Default::default()
+    };
+    let img = render(vec![shape(2, bars), shape(3, scatter)]);
+    assert!(img.width > 0);
 }

crates/render/src/text_draw.rs

@@ -35,22 +35,30 @@ pub(crate) fn prompt_body(rctx: &Ctx, s: &Shape, kind: PhType) -> TextBody {
     t
 }
 
+/// Most path elements this thread's glyph cache retains. Its entries are shared with the font
+/// cache, but they stay alive here after that cache evicts them, so they are bounded by elements.
+const GLYPH_CACHE_MAX_ELEMENTS: usize = 1 << 22;
+
 thread_local! {
-    static GLYPH_CACHE: std::cell::RefCell<HashMap<(u32, u32), Arc<BezPath>>> = std::cell::RefCell::new(HashMap::new());
+    /// The cached outlines, and the path elements they hold.
+    static GLYPH_CACHE: std::cell::RefCell<(HashMap<(u32, u32), Arc<BezPath>>, usize)> = std::cell::RefCell::new((HashMap::new(), 0));
 }
 
 pub(crate) fn glyph(face: &deckcraft_fonts::FontFace, gid: u32) -> Arc<BezPath> {
     let key = (face.id(), gid);
-    if let Some(p) = GLYPH_CACHE.with(|c| c.borrow().get(&key).cloned()) {
+    if let Some(p) = GLYPH_CACHE.with(|c| c.borrow().0.get(&key).cloned()) {
         return p;
     }
     let p = FontDb::global().outline(face, gid);
     GLYPH_CACHE.with(|c| {
         let mut c = c.borrow_mut();
-        if c.len() > 200_000 {
-            c.clear();
+        let n = p.elements().len();
+        if c.0.len() > 200_000 || c.1.saturating_add(n) > GLYPH_CACHE_MAX_ELEMENTS {
+            c.0.clear();
+            c.1 = 0;
         }
-        c.insert(key, p.clone());
+        c.1 += n;
+        c.0.insert(key, p.clone());
     });
     p
 }
@@ -105,6 +113,7 @@ pub fn draw_layout(ctx: &mut RenderContext, l: &deckcraft_text::TextLayout, tr:
 pub fn draw_layout_with(ctx: &mut RenderContext, l: &deckcraft_text::TextLayout, tr: Rect, m: Affine, paras: &[(usize, ParaState)]) {
     let para = |i: usize| paras.iter().find(|(p, _)| *p == i).map(|(_, s)| *s).unwrap_or_default();
     let m = text_transform(m, tr, l.rotation);
+    let lines_of = LineIndex::new(l);
     let deco = |ctx: &mut RenderContext, d: &deckcraft_text::Deco| {
         let ps = para(d.para);
         if !ps.visible || ps.opacity <= 0.001 {
@@ -144,7 +153,7 @@ pub fn draw_layout_with(ctx: &mut RenderContext, l: &deckcraft_text::TextLayout,
                 draw_glyph(ctx, run, *gid, at, ps.opacity);
                 continue;
             };
-            let li = line_at(l, run.para, *y);
+            let li = lines_of.line_at(run.para, *y);
             if !grads.iter().any(|(i, _)| *i == li) {
                 let scheme = deckcraft_color::ColorScheme { name: String::new(), colors: [Rgba::BLACK; 12] };
                 let stops = g.stops.iter().map(|s| (s.pos, s.color.resolve(&scheme, None))).collect();
@@ -191,8 +200,78 @@ pub(crate) fn fill_deco(ctx: &mut RenderContext, d: &deckcraft_text::Deco) {
     }
 }
 
-/// The line of paragraph `para` holding a glyph on baseline `y` (the nearest baseline).
-fn line_at(l: &deckcraft_text::TextLayout, para: usize, y: f64) -> usize {
+/// Finds the line of a paragraph holding a glyph on baseline `y` without scanning the paragraph's
+/// lines for every glyph. A paragraph whose lines are ordered top to bottom (every layout the text
+/// crate produces) is searched by bisection; any other falls back to a scan with the same answer.
+pub(crate) struct LineIndex<'a> {
+    l: &'a deckcraft_text::TextLayout,
+    /// Per paragraph: its lines' tops, bottoms and baselines all rise with the line index.
+    ordered: Vec<bool>,
+}
+
+impl<'a> LineIndex<'a> {
+    pub(crate) fn new(l: &'a deckcraft_text::TextLayout) -> Self {
+        let ordered = l
+            .para_lines
+            .iter()
+            .map(|&(first, count)| {
+                let end = first.saturating_add(count).min(l.lines.len());
+                l.lines.get(first..end).is_some_and(|ls| {
+                    ls.iter().all(|a| a.top <= a.bottom)
+                        && ls.windows(2).all(|w| w[0].top <= w[1].top && w[0].bottom <= w[1].bottom && w[0].baseline <= w[1].baseline)
+                })
+            })
+            .collect();
+        LineIndex { l, ordered }
+    }
+
+    /// The nearest line baseline to `y` among `lines` (the first of equals), as an index into `lines`.
+    fn nearest(lines: &[deckcraft_text::LineInfo], y: f64) -> Option<usize> {
+        let i = lines.partition_point(|li| li.baseline < y);
+        let best = match (i.checked_sub(1), lines.get(i)) {
+            (Some(p), Some(n)) => {
+                if (lines[p].baseline - y).abs() <= (n.baseline - y).abs() {
+                    p
+                } else {
+                    i
+                }
+            }
+            (Some(p), None) => p,
+            (None, Some(_)) => i,
+            (None, None) => return None,
+        };
+        let b = lines[best].baseline;
+        Some(lines.partition_point(|li| li.baseline < b))
+    }
+
+    /// The paragraph's lines when they are ordered, with the index of the first.
+    fn ordered_lines(&self, para: usize) -> Option<(usize, &[deckcraft_text::LineInfo])> {
+        let &(first, count) = self.l.para_lines.get(para)?;
+        let end = first.saturating_add(count).min(self.l.lines.len());
+        (self.ordered[para] && first < end).then(|| (first, &self.l.lines[first..end]))
+    }
+
+    /// The line of paragraph `para` holding a glyph on baseline `y` (the nearest baseline).
+    pub(crate) fn line_at(&self, para: usize, y: f64) -> usize {
+        if let Some((first, ls)) = self.ordered_lines(para) {
+            return Self::nearest(ls, y).map_or(0, |i| first + i);
+        }
+        line_at_scan(self.l, para, y)
+    }
+
+    /// The first line of paragraph `para` whose box holds `y`, else the nearest baseline's line.
+    pub(crate) fn line_of(&self, para: usize, y: f64) -> Option<usize> {
+        let Some((first, ls)) = self.ordered_lines(para) else { return crate::warp::line_of_scan(self.l, para, y) };
+        let i = ls.partition_point(|li| li.bottom + 0.01 < y);
+        if ls.get(i).is_some_and(|li| y >= li.top - 0.01) {
+            return Some(first + i);
+        }
+        Self::nearest(ls, y).map(|i| first + i)
+    }
+}
+
+/// The line of paragraph `para` holding a glyph on baseline `y` (the nearest baseline), by scanning.
+fn line_at_scan(l: &deckcraft_text::TextLayout, para: usize, y: f64) -> usize {
     if let Some(&(first, count)) = l.para_lines.get(para) {
         if count == 0 {
             return 0;
@@ -318,3 +397,38 @@ fn draw_glyph_with(
         ctx.stroke_path(&path);
     }
 }
+
+#[cfg(test)]
+mod line_index_tests {
+    use super::*;
+    use deckcraft_text::{LineInfo, TextLayout};
+
+    fn layout(ordered: bool) -> TextLayout {
+        let line = |para, top: f64| LineInfo { para, top, baseline: top + 8.0, bottom: top + 10.0, ..Default::default() };
+        let mut lines: Vec<LineInfo> = (0..40).map(|i| line(usize::from(i >= 25), f64::from(i) * 10.0)).collect();
+        if !ordered {
+            lines.swap(3, 7);
+        }
+        TextLayout { lines, para_lines: vec![(0, 25), (25, 15)], ..Default::default() }
+    }
+
+    #[test]
+    fn bisection_matches_the_scan() {
+        for ordered in [true, false] {
+            let l = layout(ordered);
+            let idx = LineIndex::new(l_ref(&l));
+            assert_eq!(idx.ordered, vec![ordered, true]);
+            for para in 0..2 {
+                for k in -20..450 {
+                    let y = f64::from(k) * 0.9;
+                    assert_eq!(idx.line_at(para, y), line_at_scan(&l, para, y), "line_at {para} {y}");
+                    assert_eq!(idx.line_of(para, y), crate::warp::line_of_scan(&l, para, y), "line_of {para} {y}");
+                }
+            }
+        }
+    }
+
+    fn l_ref(l: &TextLayout) -> &TextLayout {
+        l
+    }
+}

crates/render/src/warp.rs

@@ -9,13 +9,14 @@ use deckcraft_text::{GlyphRun, TextLayout};
 use kurbo::{Affine, BezPath, PathEl, Point, Rect, Shape as _};
 use vello_cpu::{RenderContext, peniko};
 
+use crate::text_draw::LineIndex;
 use crate::{ParaState, color, glyph, scale_of, text_transform};
 
 /// Most points one warped glyph may have (a hostile size or zoom can't explode the work).
 const MAX_POINTS: usize = 40_000;
 
-/// The line of `l` a glyph of paragraph `para` on baseline `y` belongs to.
-fn line_of(l: &TextLayout, para: usize, y: f64) -> Option<usize> {
+/// The line of `l` a glyph of paragraph `para` on baseline `y` belongs to, by scanning.
+pub(crate) fn line_of_scan(l: &TextLayout, para: usize, y: f64) -> Option<usize> {
     if let Some(&(first, count)) = l.para_lines.get(para) {
         if count == 0 {
             return None;
@@ -110,6 +111,7 @@ pub(crate) fn draw(ctx: &mut RenderContext, l: &TextLayout, tr: Rect, m: Affine,
     let para = |i: usize| paras.iter().find(|(p, _)| *p == i).map(|(_, s)| *s).unwrap_or_default();
     let m = text_transform(m, tr, l.rotation);
     let n = l.lines.len();
+    let lines_of = LineIndex::new(l);
     let mut ink: Vec<Option<Rect>> = vec![None; n];
     let mut off: Vec<Option<f64>> = vec![None; n];
     let mut items: Vec<Item> = Vec::new();
@@ -117,7 +119,7 @@ pub(crate) fn draw(ctx: &mut RenderContext, l: &TextLayout, tr: Rect, m: Affine,
         let k = run.size / run.face.upem.max(1.0);
         let skew = if run.fake_italic { Affine::new([1.0, 0.0, -0.2, 1.0, 0.0, 0.0]) } else { Affine::IDENTITY };
         for (gid, x, y) in &run.glyphs {
-            let Some(li) = line_of(l, run.para, *y) else { continue };
+            let Some(li) = lines_of.line_of(run.para, *y) else { continue };
             if let Some(o) = off.get_mut(li) {
                 *o = Some(o.map_or(ref_offset(run), |v| v.max(ref_offset(run))));
             }
@@ -156,7 +158,7 @@ pub(crate) fn draw(ctx: &mut RenderContext, l: &TextLayout, tr: Rect, m: Affine,
             return;
         }
         let y = (d.rect.y0 + d.rect.y1) / 2.0;
-        let Some(li) = line_of(l, d.para, y) else { return };
+        let Some(li) = lines_of.line_of(d.para, y) else { return };
         ctx.set_transform(m * Affine::translate(ps.offset));
         ctx.set_paint(color(d.color, ps.opacity));
         for r in d.pieces() {

crates/text/src/breaking.rs

@@ -260,12 +260,15 @@ pub(crate) struct Tab {
     align: TabAlign,
 }
 
+/// The paragraph's tab stops in position order (a stop at no finite position is left out), so
+/// [`tab_advance`] finds the next one by binary search instead of a scan per tab.
 pub(crate) fn tabs_of(props: &ParaProps) -> Vec<Tab> {
-    props
+    let mut tabs: Vec<Tab> = props
         .tabs
         .as_ref()
         .map(|t| {
             t.iter()
+                .filter(|s| s.pos.is_finite())
                 .map(|s| Tab {
                     pos: s.pos,
                     align: match s.align.as_str() {
@@ -277,7 +280,9 @@ pub(crate) fn tabs_of(props: &ParaProps) -> Vec<Tab> {
                 })
                 .collect()
         })
-        .unwrap_or_default()
+        .unwrap_or_default();
+    tabs.sort_by(|a, b| a.pos.total_cmp(&b.pos));
+    tabs
 }
 
 /// Width of the text after the tab at cell `i` up to the next tab or line break, and the width of
@@ -301,18 +306,30 @@ pub(crate) fn tab_segment(cells: &[Cell], i: usize) -> (f64, f64) {
 /// (`seg`: its width, and its width before the decimal point) as the stop aligns it but never
 /// moving back, as PowerPoint does; past the last stop, to the next default stop.
 pub(crate) fn tab_advance(x: f64, stops: &[Tab], default_tab: f64, seg: (f64, f64)) -> f64 {
-    for s in stops {
-        if s.pos > x + 0.5 {
-            let to = s.pos - x;
-            return match s.align {
-                TabAlign::Left => to,
-                TabAlign::Right => (to - seg.0).max(0.0),
-                TabAlign::Center => (to - seg.0 / 2.0).max(0.0),
-                TabAlign::Decimal => (to - seg.1).max(0.0),
-            };
-        }
+    // `stops` is in position order (`tabs_of`): the next stop is the first past x.
+    // A NaN `x` (a NaN spacing upstream) skips the lookup and takes the finite default-stop path.
+    if let Some(s) = stops.get(stops.partition_point(|s| s.pos <= x + 0.5)).filter(|_| !x.is_nan()) {
+        let to = s.pos - x;
+        return match s.align {
+            TabAlign::Left => to,
+            TabAlign::Right => (to - seg.0).max(0.0),
+            TabAlign::Center => (to - seg.0 / 2.0).max(0.0),
+            TabAlign::Decimal => (to - seg.1).max(0.0),
+        };
     }
     let d = if default_tab > 1.0 { default_tab } else { 72.0 };
     let next = ((x / d).floor() + 1.0) * d;
     (next - x).max(1.0)
 }
+
+#[cfg(test)]
+mod tab_tests {
+    use super::*;
+
+    #[test]
+    fn a_nan_position_takes_the_finite_default_stop() {
+        let stops = [Tab { pos: 100.0, align: TabAlign::Left }];
+        assert!(tab_advance(f64::NAN, &stops, 72.0, (0.0, 0.0)).is_finite());
+        assert_eq!(tab_advance(10.0, &stops, 72.0, (0.0, 0.0)), 90.0);
+    }
+}

crates/text/src/run.rs

@@ -22,7 +22,7 @@ pub struct GlyphRun {
     pub link: bool,
     /// Opacity of the fill on top of `color`'s own alpha (0 for no fill).
     pub alpha: f64,
-    pub gradient: Option<deckcraft_model::style::Gradient>,
+    pub gradient: Option<std::sync::Arc<deckcraft_model::style::Gradient>>,
     /// Shadow and glow behind the glyphs (`a:rPr/a:effectLst`).
     pub effects: Option<RunEffects>,
     /// East Asian vertical text (`eaVert`): each glyph stands upright, turned a quarter turn

crates/text/src/style.rs

@@ -46,7 +46,7 @@ pub(crate) struct Style {
     pub(crate) highlight: Option<Rgba>,
     pub(crate) outline: Option<(Rgba, f64)>,
     pub(crate) link: bool,
-    pub(crate) gradient: Option<deckcraft_model::style::Gradient>,
+    pub(crate) gradient: Option<std::sync::Arc<deckcraft_model::style::Gradient>>,
     pub(crate) effects: Option<RunEffects>,
     /// "Regular", "Bold"… for the slot and fallback faces.
     pub(crate) style_name: &'static str,
@@ -136,7 +136,7 @@ pub(crate) fn make_style(ctx: &Ctx, r: &RunProps, scale: f64, prompt: Option<Rgb
             for s in &mut g.stops {
                 s.color = deckcraft_model::ColorRef::rgb(ctx.color(&s.color, None));
             }
-            (g.stops.first().map(|s| ctx.color(&s.color, None)).unwrap_or(Rgba::BLACK), 1.0, Some(g))
+            (g.stops.first().map(|s| ctx.color(&s.color, None)).unwrap_or(Rgba::BLACK), 1.0, Some(std::sync::Arc::new(g)))
         }
         Some(Fill::None) => (Rgba::TRANSPARENT, 0.0, None),
         _ => (resolve::text_color(ctx, r), 1.0, None),

crates/text/src/tests.rs

@@ -1416,6 +1416,16 @@ fn tab_stops_align_the_text_after_them() {
     assert!((l.lines[0].edges[4].0 - x0(&l) - 72.0).abs() < 0.01);
 }
 
+#[test]
+fn many_tabs_over_many_stops_lay_out_by_position() {
+    // 20,000 stops given out of order, and 2,000 tabs: each tab finds the next stop by position.
+    let mut stops: Vec<(f64, &str)> = (1..=20_000).rev().map(|k| (k as f64 * 0.05 + 30.0, "l")).collect();
+    stops.push((f64::NAN, "l"));
+    let text = "a\t".repeat(2_000);
+    let l = tabbed(&text, &stops, 1.0e6);
+    assert!((l.lines[0].edges[2].0 - l.inner.x0 - 30.05).abs() < 0.01, "{:?}", &l.lines[0].edges[..3]);
+}
+
 #[test]
 fn a_tab_past_the_end_moves_to_the_next_line() {
     // PowerPoint: "abcdefghij\tk\tl\tm…" in a narrow box puts the tab that doesn't fit on the next

crates/ui-egui/src/panels/thumbs.rs

@@ -112,6 +112,21 @@ pub fn show(app: &mut SlideApp, ui: &mut Ui) {
     }
 }
 
+/// Slide index -> the first section starting there, built once instead of searched per slide.
+fn section_starts(doc: &deckcraft_model::Presentation) -> std::collections::HashMap<usize, usize> {
+    let mut index_of = std::collections::HashMap::new();
+    for (i, s) in doc.slides.iter().enumerate() {
+        index_of.entry(s.id).or_insert(i);
+    }
+    let mut starts = std::collections::HashMap::new();
+    for (si, s) in doc.sections.iter().enumerate() {
+        if let Some(&i) = s.slides.first().and_then(|id| index_of.get(id)) {
+            starts.entry(i).or_insert(si);
+        }
+    }
+    starts
+}
+
 /// Render the scrollable thumbnail list, scrolling the current slide into view when it changes.
 fn list(app: &mut SlideApp, ui: &mut Ui) {
     let t = Tokens::get(ui.ctx());
@@ -135,11 +150,10 @@ fn list(app: &mut SlideApp, ui: &mut Ui) {
     let ppp = ui.ctx().pixels_per_point();
     let mut budget = 3u32;
     let mut rects = vec![];
-    let section_starts: Vec<(usize, usize)> =
-        doc.sections.iter().enumerate().filter_map(|(si, s)| s.slides.first().and_then(|id| doc.slide_index(*id)).map(|i| (i, si))).collect();
+    let section_starts = section_starts(&doc);
     let mut need_more = false;
     for i in 0..doc.slides.len() {
-        if let Some((_, si)) = section_starts.iter().find(|(start, _)| *start == i)
+        if let Some(si) = section_starts.get(&i)
             && let Some(sec) = doc.sections.get(*si)
         {
             ui.add_space(4.0);
@@ -434,6 +448,26 @@ mod tests {
         h
     }
 
+    #[test]
+    fn section_starts_map_each_first_slide_to_its_first_section() {
+        let mut s = Session::with_new();
+        for _ in 0..3 {
+            s.execute("slide.new", &json!({})).unwrap();
+        }
+        let mut doc = (*s.active().unwrap().doc).clone();
+        let ids: Vec<_> = doc.slides.iter().map(|sl| sl.id).collect();
+        doc.sections = vec![
+            deckcraft_model::Section { name: "a".into(), slides: vec![ids[0], ids[1]] },
+            deckcraft_model::Section { name: "dup".into(), slides: vec![ids[0]] },
+            deckcraft_model::Section { name: "c".into(), slides: vec![ids[2]] },
+            deckcraft_model::Section { name: "empty".into(), slides: vec![] },
+        ];
+        let starts = section_starts(&doc);
+        assert_eq!(starts.get(&0), Some(&0), "the first section starting at a slide wins");
+        assert_eq!(starts.get(&2), Some(&2));
+        assert_eq!(starts.len(), 2);
+    }
+
     /// Vertical scroll offset of the thumbnail pane, as recorded each frame by `show`.
     fn thumbs_scroll(h: &Harness<'_, SlideApp>) -> f32 {
         h.state().ui.thumbs_scroll