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();