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/engine/src/compare.rs

@@ -121,10 +121,9 @@ 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, &mut media);
+        let details = slide_details(cur, a, rev, b);
         if !details.is_empty() {
             out.push(Change { kind: ChangeKind::Changed, slide: *i, number: i.saturating_add(1), only_in: None, revised: Some(*j), details });
         }
@@ -141,18 +140,10 @@ 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,
@@ -183,34 +174,8 @@ fn shape_label(s: &Shape) -> String {
     if s.name.trim().is_empty() { format!("Shape {}", s.id.0) } else { s.name.clone() }
 }
 
-/// 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(),
-        }
-    }
+fn media_bytes(p: &Presentation, id: MediaId) -> Option<&[u8]> {
+    p.media(id).map(|m| m.data.as_slice())
 }
 
 /// A shape without its ids (shape and media), for comparing across decks.
@@ -239,7 +204,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(ca: Option<&Ctx>, a: &Shape, cb: Option<&Ctx>, b: &Shape, media: &mut Media, out: &mut Vec<String>) {
+fn shape_details(cp: &Presentation, ca: Option<&Ctx>, a: &Shape, rp: &Presentation, cb: Option<&Ctx>, b: &Shape, 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![];
@@ -269,11 +234,11 @@ fn shape_details(ca: Option<&Ctx>, a: &Shape, cb: Option<&Ctx>, b: &Shape, media
     if a.fill != b.fill || a.line != b.line || a.style != b.style || a.effects != b.effects {
         what.push("formatting");
     }
-    let pic = |s: &Shape| match &s.kind {
-        ShapeKind::Picture { fill } => Some(fill.media),
+    let pic = |p: &Presentation, s: &Shape| match &s.kind {
+        ShapeKind::Picture { fill } => media_bytes(p, fill.media).map(|b| b.to_vec()),
         _ => None,
     };
-    if media.differ(pic(a), pic(b)) {
+    if pic(cp, a) != pic(rp, b) {
         what.push("picture");
     }
     // Anything the checks above do not cover (alt text, hidden, a link…) is reported too, also
@@ -300,32 +265,21 @@ fn shape_details(ca: Option<&Ctx>, a: &Shape, cb: Option<&Ctx>, b: &Shape, media
     }
 }
 
-fn slide_details(cp: &Presentation, a: &Slide, rp: &Presentation, b: &Slide, media: &mut Media) -> Vec<String> {
+fn slide_details(cp: &Presentation, a: &Slide, rp: &Presentation, b: &Slide) -> 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 = 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()
-        });
+        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()));
         match k {
             Some(k) if !used.contains(&k) => {
                 used.insert(k);
                 if let Some(sb) = b.shapes.get(k) {
-                    shape_details(ca.as_ref(), sa, cb.as_ref(), sb, media, &mut out);
+                    shape_details(cp, ca.as_ref(), sa, rp, cb.as_ref(), sb, &mut out);
                 }
             }
             _ => out.push(format!("{} deleted (only in the deck)", shape_label(sa))),
@@ -380,34 +334,19 @@ 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_at.get(&id).and_then(|&i| rev.media.get(i)) else { continue };
-        match doc_at.get(&id).and_then(|&i| doc.media.get(i)) {
+        let Some(m) = rev.media(id) else { continue };
+        match doc.media(id) {
             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);
             }
         }
@@ -580,39 +519,6 @@ 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/fonts/src/shape.rs

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