xtask: match attribution globs with a table, not backtracking

crates/pptx/src/write/dml.rs

@@ -762,27 +762,17 @@ 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");
-            put_rpr(w);
+            rpr(w, x, o, "a:rPr", props);
             w.close("a:br");
         }
         if piece.is_empty() && i > 0 {
             continue;
         }
         w.open0("a:r");
-        put_rpr(w);
+        rpr(w, x, o, "a:rPr", props);
         w.elt("a:t", piece);
         w.close("a:r");
     }

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};
+use deckcraft_model::{Shape, ShapeId, ShapeKind, find_shape};
 
 use super::shapes::IdMap;
 use super::{Exp, Out};
@@ -577,21 +577,6 @@ 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();
@@ -600,31 +585,16 @@ 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) = by_id.get(&a.shape) else { continue };
+        let Some(shape) = find_shape(shapes, 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 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 roles = text.map(paragraph_build_roles).unwrap_or_default();
         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
@@ -662,19 +632,11 @@ 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));
         }

xtask/src/assets.rs

@@ -61,16 +61,23 @@ pub fn missing(files: &[String], assets_md: &str) -> Vec<String> {
     files.iter().filter(|f| is_asset(f) && !patterns.iter().any(|p| glob(p, f))).cloned().collect()
 }
 
-/// `*` matches any run of characters except `/`; everything else literally.
+/// `*` matches any run of characters except `/`; everything else literally. Matched with a
+/// table over the pattern, so a pattern with many `*` costs pattern length times name length
+/// rather than exploring every way to split the name.
 fn glob(pat: &str, s: &str) -> bool {
-    match pat.split_once('*') {
-        None => pat == s,
-        Some((head, tail)) => {
-            let Some(rest) = s.strip_prefix(head) else { return false };
-            let ends = rest.char_indices().map(|(i, _)| i).chain(std::iter::once(rest.len()));
-            ends.take_while(|&i| !rest[..i].contains('/')).any(|i| glob(tail, &rest[i..]))
+    let t: Vec<char> = s.chars().collect();
+    // `row[k]`: the pattern so far matches the first k characters of the name.
+    let mut row = vec![false; t.len() + 1];
+    row[0] = true;
+    for pc in pat.chars() {
+        let mut next = vec![false; t.len() + 1];
+        next[0] = pc == '*' && row[0];
+        for k in 1..=t.len() {
+            next[k] = if pc == '*' { row[k] || (next[k - 1] && t[k - 1] != '/') } else { row[k - 1] && t[k - 1] == pc };
         }
+        row = next;
     }
+    row[t.len()]
 }
 
 /// Splits `git ls-files -z` output into real file names (no display quoting of Unicode or special characters).
@@ -120,6 +127,15 @@ mod tests {
         assert_eq!(missing(&["assets/é.png".into()], "`assets/*.svg`"), vec!["assets/é.png".to_string()]);
     }
 
+    #[test]
+    fn many_wildcards_on_a_failing_name_finish_at_once() {
+        let pat = format!("{}b", "a*".repeat(40));
+        assert!(!glob(&pat, &"a".repeat(60)));
+        assert!(glob(&pat, &format!("{}b", "a".repeat(60))));
+        assert!(!glob("a*b", "a/b"));
+        assert!(glob("a*b", "ab"));
+    }
+
     #[test]
     fn ls_files_output_is_nul_separated_and_unquoted() {
         let names = parse_ls_files("assets/zażółć.png\0docs/images/a b\nc.png\0".as_bytes());