xtask: match attribution globs with a table, not backtracking

crates/pptx/src/read.rs

@@ -46,12 +46,6 @@ pub struct Imp<'a> {
     pub tag_bytes: usize,
     /// The tag budget ran out and the warning was given.
     pub tags_capped: bool,
-    /// Bytes of preserved theme XML kept by the masters read so far.
-    pub theme_extra_bytes: usize,
-    /// Shapes read from SmartArt drawings so far (see `shapes::MAX_SMARTART_SHAPES`).
-    pub smartart_shapes: usize,
-    /// Bytes of SmartArt layout, style and colour definitions copied into diagrams so far.
-    pub diagram_xml_bytes: usize,
 }
 
 impl Imp<'_> {
@@ -452,9 +446,6 @@ pub fn import_theme(bytes: &[u8]) -> Result<(deckcraft_model::theme::Theme, Vec<
         tags_by_part: HashMap::new(),
         tag_bytes: 0,
         tags_capped: false,
-        theme_extra_bytes: 0,
-        smartart_shapes: 0,
-        diagram_xml_bytes: 0,
     };
     let part = Part::new(&pkg, &theme_path, &doc);
     let theme = theme::read_theme(&mut imp, &part, &doc.root);
@@ -496,9 +487,6 @@ pub fn import_checked(bytes: &[u8]) -> Result<(Presentation, Vec<String>), PptxE
         tags_by_part: HashMap::new(),
         tag_bytes: 0,
         tags_capped: false,
-        theme_extra_bytes: 0,
-        smartart_shapes: 0,
-        diagram_xml_bytes: 0,
     };
     // Slide ids first so hyperlinks anywhere can point at slides.
     let slide_ids = register_slides(&mut imp, &docs, &slide_entries, &mut lost_slides);

crates/pptx/src/read/shapes.rs

@@ -558,20 +558,9 @@ fn diagram_data(imp: &mut Imp, target: &str) -> Option<deckcraft_model::MediaId>
     Some(id)
 }
 
-/// Shapes all SmartArt drawings of one presentation may add; a frame read after that is left as a
-/// placeholder. Each frame that references a drawing reads it again.
-const MAX_SMARTART_SHAPES: usize = 250_000;
-
-/// SmartArt definition XML (layout, style, colours) all diagrams of one presentation may copy.
-const MAX_DIAGRAM_XML_BYTES: usize = 32 << 20;
-
-fn count_shapes(shapes: &[Shape]) -> usize {
-    shapes.iter().map(|s| 1 + count_shapes(s.children())).sum()
-}
-
 /// SmartArt: read the pre-drawn shapes of its drawing part as a group.
 fn smartart(imp: &mut Imp, part: &Part, gd: &El, frame: &Shape, depth: usize) -> Option<Shape> {
-    if depth > 8 || imp.smartart_shapes >= MAX_SMARTART_SHAPES {
+    if depth > 8 {
         return None;
     }
     let rel_ids = gd.child("relIds")?;
@@ -587,8 +576,6 @@ fn smartart(imp: &mut Imp, part: &Part, gd: &El, frame: &Shape, depth: usize) ->
     if children.is_empty() {
         return None;
     }
-    // A drawing that frames reuse (or that nests another SmartArt) counts every time it is read.
-    imp.smartart_shapes = imp.smartart_shapes.saturating_add(count_shapes(&children));
     let children = smartart_text_rects(imp, &mut sub, tree, children, depth + 1);
     let mut g = frame.clone();
     let x = frame.xfrm.unwrap_or_default();
@@ -716,22 +703,15 @@ fn text_area(geom: &Geom, w: f64, h: f64) -> deckcraft_geom::Rect {
 
 /// The outline of a SmartArt graphic (for the Text Pane), with its layout, quick style and colour
 /// parts kept to be written back.
-fn diagram_outline(imp: &mut Imp, part: &Part, rel_ids: &El, data: &El) -> Option<deckcraft_model::Diagram> {
+fn diagram_outline(imp: &Imp, part: &Part, rel_ids: &El, data: &El) -> Option<deckcraft_model::Diagram> {
     let nodes = crate::dgm::outline(data);
     if nodes.is_empty() {
         return None;
     }
-    let (pkg, spent) = (imp.pkg, std::cell::Cell::new(imp.diagram_xml_bytes));
     let raw = |attr: &str| -> Option<String> {
         let rel = part.rels.get(rel_ids.attr(attr)?)?;
-        let bytes = pkg.get(&rel.target)?;
-        // Every diagram copies its definitions, so the copies share one presentation-wide budget.
-        if bytes.len() > 4 << 20 || spent.get().saturating_add(bytes.len()) > MAX_DIAGRAM_XML_BYTES {
-            return None;
-        }
-        let xml = String::from_utf8(bytes.to_vec()).ok()?;
-        spent.set(spent.get() + xml.len());
-        Some(xml)
+        let bytes = imp.pkg.get(&rel.target)?;
+        (bytes.len() <= 4 << 20).then(|| String::from_utf8(bytes.to_vec()).ok()).flatten()
     };
     let layout_xml = raw("r:lo");
     let (layout_id, cat) = layout_xml
@@ -752,8 +732,6 @@ fn diagram_outline(imp: &mut Imp, part: &Part, rel_ids: &El, data: &El) -> Optio
     let pr = data.path(&["ptLst"]).and_then(|l| l.children_named("pt").find(|p| p.attr("type") == Some("doc"))).and_then(|p| p.child("prSet"));
     let style = crate::dgm::style_for(pr.and_then(|p| p.attr("qsTypeId")).unwrap_or("")).to_string();
     let colors = crate::dgm::colors_for(pr.and_then(|p| p.attr("csTypeId")).unwrap_or(""));
-    let (style_xml, colors_xml) = (raw("r:qs"), raw("r:cs"));
-    imp.diagram_xml_bytes = spent.get();
     Some(deckcraft_model::Diagram {
         kind: crate::dgm::kind_for(&id, &cat).to_string(),
         nodes,
@@ -762,8 +740,8 @@ fn diagram_outline(imp: &mut Imp, part: &Part, rel_ids: &El, data: &El) -> Optio
         imported: true,
         layout_id: id,
         layout_xml,
-        style_xml,
-        colors_xml,
+        style_xml: raw("r:qs"),
+        colors_xml: raw("r:cs"),
     })
 }
 

crates/pptx/src/read/theme.rs

@@ -20,10 +20,6 @@ fn font_set(e: Option<&El>) -> FontSet {
     FontSet { latin: tf("latin"), ea: tf("ea"), cs: tf("cs"), scripts }
 }
 
-/// Bytes of preserved theme XML (object defaults and extra colour schemes) all masters of one
-/// presentation may keep.
-const MAX_THEME_EXTRA_BYTES: usize = 16 << 20;
-
 pub fn read_theme(imp: &mut Imp, part: &Part, root: &El) -> Theme {
     let mut t = Theme { name: root.attr("name").unwrap_or("Theme").to_string(), ..Default::default() };
     let Some(te) = root.child("themeElements") else { return t };
@@ -93,13 +89,8 @@ pub fn read_theme(imp: &mut Imp, part: &Part, root: &El) -> Theme {
         .filter(|e| !super::has_rel_refs(e))
         .map(|e| part.keep(e))
         .collect();
-    // Every master that references this theme keeps its own copy of the preserved XML, so the
-    // copies share one budget for the presentation.
-    if !extra.is_empty() && imp.theme_extra_bytes.saturating_add(extra.len()) <= MAX_THEME_EXTRA_BYTES {
-        imp.theme_extra_bytes += extra.len();
+    if !extra.is_empty() {
         t.raw_extra = Some(extra);
-    } else if !extra.is_empty() {
-        log::warn!("pptx: theme object defaults not kept; the preserved-XML budget is spent");
     }
     t
 }

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