Animations: drop wall-clock bounds from the large morph and paragraph tests

On a loaded runner a ten-second bound can fail after every functional
assertion passed. The inputs stay large enough that a quadratic regression
hangs the test instead.

crates/anim/src/morph.rs

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

crates/anim/src/tests.rs

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

crates/anim/src/timeline.rs

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

crates/format/src/chart_parts_tests.rs

@@ -85,14 +85,14 @@ fn chart_parts_share_media_byte_and_item_budgets() {
     let mut p = fixture(vec![7; 600]);
     p.add_media("a.bin", "application/octet-stream", vec![8; 600]).unwrap();
     let bytes = save(&p).unwrap();
-    assert!(load_within(&bytes, Budget::media(1200, 2)).is_ok());
-    assert!(load_within(&bytes, Budget::media(1199, 2)).is_err(), "chart payloads share the cumulative media budget");
-    assert!(load_within(&bytes, Budget::media(1200, 1)).is_err(), "chart parts share the media item budget");
+    assert!(load_within(&bytes, Budget { total: 1200, items: 2 }).is_ok());
+    assert!(load_within(&bytes, Budget { total: 1199, items: 2 }).is_err(), "chart payloads share the cumulative media budget");
+    assert!(load_within(&bytes, Budget { total: 1200, items: 1 }).is_err(), "chart parts share the media item budget");
     let duplicated = rewrite_manifest(&bytes, |manifest| {
         let media = manifest["presentation"]["media"].as_array_mut().unwrap();
         media.push(media[0].clone());
     });
-    assert!(load_within(&duplicated, Budget::media(1200, 2)).is_err(), "duplicate media IDs still count as listed items");
+    assert!(load_within(&duplicated, Budget { total: 1200, items: 2 }).is_err(), "duplicate media IDs still count as listed items");
 }
 
 #[test]
@@ -104,9 +104,9 @@ fn legacy_inline_chart_bytes_are_budgeted_and_preserved() {
         part.remove("nativeEntry");
         part.insert("bytes".into(), json!(vec![9_u8; 600]));
     });
-    assert_eq!(load_within(&legacy, Budget::media(1200, 2)).unwrap().0, p);
-    assert!(load_within(&legacy, Budget::media(1199, 2)).is_err());
-    assert!(load_within(&legacy, Budget::media(1200, 1)).is_err());
+    assert_eq!(load_within(&legacy, Budget { total: 1200, items: 2 }).unwrap().0, p);
+    assert!(load_within(&legacy, Budget { total: 1199, items: 2 }).is_err());
+    assert!(load_within(&legacy, Budget { total: 1200, items: 1 }).is_err());
 }
 
 #[test]
@@ -207,7 +207,7 @@ fn corrupt_chart_members_stop_before_reusing_the_inflation_budget() {
     }
     // A failed CRC may already have inflated bytes. Continuing with the same remaining
     // budget would let each corrupt member consume that work budget again.
-    let result = load_within(&bytes, Budget::media(10, 2));
+    let result = load_within(&bytes, Budget { total: 10, items: 2 });
     assert!(result.is_err(), "two corrupt 10-byte members must not reuse a 10-byte budget");
     assert!(result.unwrap_err().to_string().contains("chart-parts/0"));
 }
@@ -228,7 +228,7 @@ fn duplicate_physical_zip_names_are_indexed_and_inflated_once() {
     assert_eq!(replaced, 2);
     let z = zip::ZipArchive::new(Cursor::new(bytes.as_slice())).unwrap();
     assert_eq!(z.file_names().filter(|n| n.starts_with("chart-parts/")).count(), 1);
-    let (q, damaged) = load_within(&bytes, Budget::media(10, 2)).unwrap();
+    let (q, damaged) = load_within(&bytes, Budget { total: 10, items: 2 }).unwrap();
     assert_eq!(damaged.len(), 1, "the second reference is missing, not inflated again");
     let ShapeKind::Group { children, .. } = &q.slides[0].shapes[0].kind else { panic!("group") };
     let ShapeKind::Chart(chart) = &children[0].kind else { panic!("chart") };

crates/format/src/lib.rs

@@ -29,24 +29,12 @@ const MAX_ENTRY: u64 = 2 << 30;
 const MAX_TOTAL_MEDIA: u64 = 4 << 30;
 /// Media items and chart sidecar parts one file may list.
 const MAX_MEDIA_ITEMS: usize = 100_000;
-/// Largest `presentation.json` we will inflate. The manifest holds no media bytes, so it is far
-/// smaller than a media entry may be; inflating and parsing one is what dominates memory.
-const MAX_MANIFEST: u64 = 256 << 20;
 
 /// What one load may inflate.
 #[derive(Clone, Copy)]
 struct Budget {
     total: u64,
     items: usize,
-    manifest: u64,
-}
-
-#[cfg(test)]
-impl Budget {
-    /// A media budget with the default manifest limit.
-    fn media(total: u64, items: usize) -> Self {
-        Budget { total, items, manifest: MAX_MANIFEST }
-    }
 }
 
 #[derive(Debug, thiserror::Error)]
@@ -119,7 +107,6 @@ pub fn sniff(bytes: &[u8]) -> bool {
     bytes.starts_with(b"PK") && [MIMETYPE, LEGACY_MIMETYPE].iter().any(|m| bytes.windows(m.len()).take(200).any(|w| w == m.as_bytes()))
 }
 
-#[cfg(test)]
 fn read_entry(z: &mut zip::ZipArchive<Cursor<&[u8]>>, name: &str) -> Result<Vec<u8>> {
     read_entry_max(z, name, MAX_ENTRY)
 }
@@ -127,30 +114,13 @@ fn read_entry(z: &mut zip::ZipArchive<Cursor<&[u8]>>, name: &str) -> Result<Vec<
 /// Read one member, refusing it before inflating if it declares more than `max` bytes, and
 /// stopping at `max` if it inflates further than it declared.
 fn read_entry_max(z: &mut zip::ZipArchive<Cursor<&[u8]>>, name: &str, max: u64) -> Result<Vec<u8>> {
-    read_entry_counted(z, name, max, &mut 0)
-}
-
-/// [`read_entry_max`] within `left` (and [`MAX_ENTRY`]), charging `left` for every byte inflated,
-/// including those inflated before a decode or CRC error, so a member that fails late still
-/// spends the shared budget it used.
-fn read_entry_charged(z: &mut zip::ZipArchive<Cursor<&[u8]>>, name: &str, left: &mut u64) -> Result<Vec<u8>> {
-    let mut spent = 0;
-    let out = read_entry_counted(z, name, (*left).min(MAX_ENTRY), &mut spent);
-    *left = left.saturating_sub(spent);
-    out
-}
-
-/// [`read_entry_max`], adding the bytes inflated to `spent` whether or not the read succeeds.
-fn read_entry_counted(z: &mut zip::ZipArchive<Cursor<&[u8]>>, name: &str, max: u64, spent: &mut u64) -> Result<Vec<u8>> {
     let f = z.by_name(name).map_err(|e| FormatError::Damaged(format!("{name}: {e}")))?;
     if f.size() > max {
         return Err(FormatError::Damaged(format!("{name} is too large")));
     }
     let mut out = Vec::with_capacity(f.size().min(64 << 20) as usize);
     let mut f = f.take(max.saturating_add(1));
-    let read = f.read_to_end(&mut out);
-    *spent = spent.saturating_add(out.len() as u64);
-    read.map_err(|e| FormatError::Damaged(format!("{name}: {e}")))?;
+    f.read_to_end(&mut out).map_err(|e| FormatError::Damaged(format!("{name}: {e}")))?;
     if out.len() as u64 > max {
         return Err(FormatError::Damaged(format!("{name} is too large")));
     }
@@ -167,15 +137,12 @@ pub fn load(bytes: &[u8]) -> Result<Presentation> {
 /// A chart member that is present but fails decoding, CRC or its entry limit refuses the file.
 /// Linked media saved without its bytes isn't damage.
 pub fn load_checked(bytes: &[u8]) -> Result<(Presentation, Vec<String>)> {
-    load_within(bytes, Budget { total: MAX_TOTAL_MEDIA, items: MAX_MEDIA_ITEMS, manifest: MAX_MANIFEST })
+    load_within(bytes, Budget { total: MAX_TOTAL_MEDIA, items: MAX_MEDIA_ITEMS })
 }
 
 fn load_within(bytes: &[u8], budget: Budget) -> Result<(Presentation, Vec<String>)> {
     let mut z = zip::ZipArchive::new(Cursor::new(bytes)).map_err(|e| FormatError::NotOurs(e.to_string()))?;
-    if z.index_for_name("presentation.json").is_none() {
-        return Err(FormatError::NotOurs("no presentation.json".into()));
-    }
-    let json = read_entry_max(&mut z, "presentation.json", budget.manifest)?;
+    let json = read_entry(&mut z, "presentation.json").map_err(|_| FormatError::NotOurs("no presentation.json".into()))?;
     let m = parse_manifest(&json)?;
     if m.format != "deckcraft" {
         return Err(FormatError::NotOurs(m.format));
@@ -197,9 +164,11 @@ fn load_within(bytes: &[u8], budget: Budget) -> Result<(Presentation, Vec<String
         if z.by_name(&name).is_ok_and(|f| f.size() > left) {
             return Err(FormatError::Damaged("embedded media is larger than DeckCraft can open".into()));
         }
-        // A failed read is charged for what it inflated, so later members can't reuse that budget.
-        match read_entry_charged(&mut z, &name, &mut left) {
-            Ok(data) => item.data = Arc::new(data),
+        match read_entry_max(&mut z, &name, left.min(MAX_ENTRY)) {
+            Ok(data) => {
+                left -= data.len() as u64;
+                item.data = Arc::new(data);
+            }
             Err(_) if linked_only => {}
             Err(e) => damaged.push(e.to_string()),
         }
@@ -219,11 +188,9 @@ pub fn repair(p: &mut Presentation) {
     }
     p.fix_next_id();
     let first_layout = p.masters.first().and_then(|m| m.layouts.first()).map(|l| l.id).unwrap_or_default();
-    // Indexed once: a per-slide scan of every layout is slides × layouts work.
-    let layouts: std::collections::HashSet<_> = p.masters.iter().flat_map(|m| m.layouts.iter().map(|l| l.id)).collect();
     let mut seen = std::collections::HashSet::new();
     for i in 0..p.slides.len() {
-        let needs_layout = p.slides.get(i).is_some_and(|s| !layouts.contains(&s.layout));
+        let needs_layout = p.slides.get(i).is_some_and(|s| p.layout(s.layout).is_none());
         let dup = p.slides.get(i).is_some_and(|s| !seen.insert(s.id));
         if needs_layout || dup {
             // An exhausted id space leaves a duplicate slide as it is: the engine refuses to
@@ -364,20 +331,16 @@ fn failure(src: &[u8]) -> std::result::Result<Manifest, (String, (usize, usize))
 /// nearest first, and a patch is kept only if the parse then gets further. (Files saved since
 /// [`finite::Finite`] never contain such `null`s; this reads older ones.)
 fn parse_manifest(json: &[u8]) -> Result<Manifest> {
-    // Parse the inflated text as it is: only a file that fails on a `null` number is copied for
-    // patching (the copy is bounded by `MAX_MANIFEST`).
-    let mut last = match failure(json) {
+    let mut src = json.to_vec();
+    let mut last = match failure(&src) {
         Ok(m) => return Ok(m),
         Err(f) => f,
     };
-    if !is_null_number(&last.0) {
-        return Err(FormatError::Damaged(last.0));
-    }
-    let mut src = json.to_vec();
     let mut budget = MAX_REPARSE_BYTES;
     'fixes: for _ in 0..MAX_NULL_FIXES {
         let (msg, pos) = &last;
-        if !is_null_number(msg) {
+        let number = msg.starts_with("invalid type: null, expected f") || msg.starts_with("invalid type: null, expected a number");
+        if !number {
             break;
         }
         let end = offset(&src, pos.0, pos.1).unwrap_or(src.len());
@@ -411,11 +374,6 @@ fn parse_manifest(json: &[u8]) -> Result<Manifest> {
     Err(FormatError::Damaged(last.0))
 }
 
-/// Is this parse error a `null` where a number belongs (a NaN or infinity serde_json wrote)?
-fn is_null_number(msg: &str) -> bool {
-    msg.starts_with("invalid type: null, expected f") || msg.starts_with("invalid type: null, expected a number")
-}
-
 /// Byte offset of a 1-based `line`:`column`.
 fn offset(src: &[u8], line: usize, column: usize) -> Option<usize> {
     let mut start = 0;

crates/format/src/tests.rs

@@ -93,60 +93,9 @@ fn media_budget_is_cumulative() {
     p.add_media("b.bin", "application/octet-stream", vec![2; 600]);
     let bytes = save(&p).unwrap();
     // Exactly at the limit opens; one byte under is refused, though each item fits.
-    assert!(load_within(&bytes, Budget::media(1200, 2)).is_ok());
-    assert!(load_within(&bytes, Budget::media(1199, 2)).is_err());
-    assert!(load_within(&bytes, Budget::media(1200, 1)).is_err());
-}
-
-#[test]
-fn corrupt_media_is_charged_for_what_it_inflated() {
-    let mut p = Presentation::default();
-    p.add_media("a.png", "image/png", b"PICTURE-AAAAAAAAAAAA".to_vec());
-    p.add_media("b.png", "image/png", b"PICTURE-BBBBBBBBBBBB".to_vec());
-    let mut bytes = save(&p).unwrap();
-    // Corrupt both stored members, so each fails its CRC only after inflating all its bytes.
-    for tag in [b"PICTURE-AAAA", b"PICTURE-BBBB"] {
-        let at = bytes.windows(tag.len()).position(|w| w == tag).unwrap();
-        bytes[at] ^= 0xff;
-    }
-    // Each member fits the budget on its own; the second must not reuse what the first spent.
-    let result = load_within(&bytes, Budget::media(20, 2));
-    assert!(result.is_err(), "two corrupt 20-byte members must not share a 20-byte budget");
-    // With room for both, the file opens and reports both.
-    let (_, damaged) = load_within(&bytes, Budget::media(40, 2)).unwrap();
-    assert_eq!(damaged.len(), 2, "{damaged:?}");
-}
-
-#[test]
-fn oversized_manifest_is_refused_before_inflating() {
-    let bytes = save(&Presentation::default()).unwrap();
-    let mut z = zip::ZipArchive::new(Cursor::new(bytes.as_slice())).unwrap();
-    let size = z.by_name("presentation.json").unwrap().size();
-    assert!(load_within(&bytes, Budget { total: 0, items: 0, manifest: size }).is_ok());
-    let err = load_within(&bytes, Budget { total: 0, items: 0, manifest: size - 1 }).unwrap_err();
-    assert!(err.to_string().contains("too large"), "{err}");
-}
-
-#[test]
-fn many_slides_on_missing_layouts_are_repaired() {
-    let mut p = Presentation::default();
-    let template = p.slides[0].clone();
-    let good = template.layout;
-    p.slides = (0..2000u32)
-        .map(|i| {
-            let mut s = (*template).clone();
-            s.id = deckcraft_model::SlideId(10_000 + i);
-            if i % 2 == 1 {
-                s.layout = deckcraft_model::LayoutId(900_000 + i);
-            }
-            Arc::new(s)
-        })
-        .collect();
-    p.next_id = 20_000;
-    repair(&mut p);
-    assert!(p.validate().is_empty(), "{:?}", p.validate().first());
-    assert!(p.slides.iter().all(|s| p.layout(s.layout).is_some()));
-    assert_eq!(p.slides[0].layout, good);
+    assert!(load_within(&bytes, Budget { total: 1200, items: 2 }).is_ok());
+    assert!(load_within(&bytes, Budget { total: 1199, items: 2 }).is_err());
+    assert!(load_within(&bytes, Budget { total: 1200, items: 1 }).is_err());
 }
 
 #[test]
@@ -175,7 +124,7 @@ fn repeated_media_ids_are_read_once() {
     }
     let bytes = out.finish().unwrap().into_inner();
     // 51 references to one 1000-byte member fit a 1000-byte budget: it's inflated once.
-    let q = load_within(&bytes, Budget::media(1000, 51)).unwrap().0;
+    let q = load_within(&bytes, Budget { total: 1000, items: 51 }).unwrap().0;
     assert_eq!(q.media.len(), 1);
     assert_eq!(q.media[0].data.len(), 1000);
     // And the deck saves again.

crates/model/src/lib.rs

@@ -1112,13 +1112,11 @@ impl Presentation {
     pub fn validate(&self) -> Vec<String> {
         let mut out = vec![];
         let mut seen = std::collections::HashSet::new();
-        // Indexed once: a per-slide scan of every layout is slides × layouts work.
-        let layouts: std::collections::HashSet<_> = self.masters.iter().flat_map(|m| m.layouts.iter().map(|l| l.id)).collect();
         for s in &self.slides {
             if !seen.insert(s.id) {
                 out.push(format!("duplicate slide id {}", s.id));
             }
-            if !layouts.contains(&s.layout) {
+            if self.layout(s.layout).is_none() {
                 out.push(format!("slide {} uses missing layout {}", s.id, s.layout));
             }
             let mut ids = std::collections::HashSet::new();