Apply review fixes

- crates/pptx/src/read.rs

crates/metafile/src/cliprect.rs

@@ -11,10 +11,6 @@ use crate::geom::{Op, P};
 /// Line segments per Bézier when a crossing shape is flattened.
 const CURVE_STEPS: usize = 16;
 
-/// Point-against-edge tests one clipped item may cost (all its subpaths together); an item over
-/// it is dropped, as a single polygon over it already was.
-const MAX_CLIP_WORK: usize = 1_000_000;
-
 /// The bounding box `[l, t, r, b]` of the points in `ops` (control points included).
 pub(crate) fn ops_bbox(ops: &[Op]) -> Option<[f64; 4]> {
     let mut b: Option<[f64; 4]> = None;
@@ -104,20 +100,14 @@ fn is_rect(clip: &[P]) -> bool {
 
 /// Sutherland–Hodgman: `poly` cut by convex `clip`.
 pub(crate) fn clip_polygon(poly: &[P], clip: &[P]) -> Vec<P> {
-    clip_polygon_within(poly, clip, &mut { MAX_CLIP_WORK }).unwrap_or_default()
-}
-
-/// [`clip_polygon`] charging each point visited against each clip edge to `budget`: the polygon
-/// can gain a vertex at every edge, so its cost isn't known from its input size alone. `None`
-/// once the budget is spent.
-fn clip_polygon_within(poly: &[P], clip: &[P], budget: &mut usize) -> Option<Vec<P>> {
+    if poly.len().saturating_mul(clip.len()) > 1_000_000 {
+        return Vec::new();
+    }
     let mut poly = poly.to_vec();
     for i in 0..clip.len() {
-        // The work actually done: this edge visits the polygon as it now stands.
-        if poly.len() > *budget {
-            return None;
+        if poly.len().saturating_mul(clip.len() - i) > 1_000_000 {
+            return Vec::new();
         }
-        *budget -= poly.len();
         let (a, b) = (clip[i], clip[(i + 1) % clip.len()]);
         let keep = |p: P| cross(a, b, p) >= 0.0;
         let cut = |p: P, q: P| {
@@ -143,7 +133,7 @@ fn clip_polygon_within(poly: &[P], clip: &[P], budget: &mut usize) -> Option<Vec
             break;
         }
     }
-    Some(poly)
+    poly
 }
 
 fn disjoint(b: [f64; 4], c: [f64; 4]) -> bool {
@@ -168,12 +158,9 @@ pub(crate) fn clip_raw(raw: Raw, clip: &[P]) -> Vec<Raw> {
                 return Vec::new();
             }
             let subs = flatten(&ops);
-            if too_much_work(&subs, clip, usize::from(fill.is_some()) + usize::from(stroke.is_some())) {
-                return Vec::new();
-            }
             let mut out = Vec::new();
             if fill.is_some() {
-                let Some(f) = clip_fill(&subs, clip) else { return Vec::new() };
+                let f = clip_fill(&subs, clip);
                 if !f.is_empty() {
                     out.push(Raw::Path { ops: f, fill, stroke: None, even_odd, region: region.clone() });
                 }
@@ -194,11 +181,7 @@ pub(crate) fn clip_raw(raw: Raw, clip: &[P]) -> Vec<Raw> {
             if disjoint(b, cb) {
                 return Vec::new();
             }
-            let subs = flatten(&ops);
-            if too_much_work(&subs, clip, 1) {
-                return Vec::new();
-            }
-            let f = clip_fill(&subs, clip).unwrap_or_default();
+            let f = clip_fill(&flatten(&ops), clip);
             if f.is_empty() { Vec::new() } else { vec![Raw::Pattern { ops: f, even_odd, tile, region }] }
         }
         Raw::Bitmap { rect, img, region } => crop(rect, img, clip).map(|(rect, img)| vec![Raw::Bitmap { rect, img, region }]).unwrap_or_default(),
@@ -247,28 +230,17 @@ pub(crate) fn flatten(ops: &[Op]) -> Vec<(Vec<P>, bool)> {
     subs
 }
 
-/// Whether cutting every subpath of one item by `clip` would exceed [`MAX_CLIP_WORK`]; the
-/// per-polygon check alone lets many small subpaths each spend the whole allowance. `passes` is
-/// how many clipping passes the item gets (fill and stroke each cut every subpath), so one item
-/// shares a single allowance between them.
-fn too_much_work(subs: &[(Vec<P>, bool)], clip: &[P], passes: usize) -> bool {
-    subs.iter().map(|s| s.0.len() + 1).sum::<usize>().saturating_mul(clip.len()).saturating_mul(passes) > MAX_CLIP_WORK
-}
-
-/// The clipped fill of every subpath, its clipping work shared by all of them: `None` (the whole
-/// item goes) once [`MAX_CLIP_WORK`] is spent.
-fn clip_fill(subs: &[(Vec<P>, bool)], clip: &[P]) -> Option<Vec<Op>> {
+fn clip_fill(subs: &[(Vec<P>, bool)], clip: &[P]) -> Vec<Op> {
     let mut ops = Vec::new();
-    let mut budget = MAX_CLIP_WORK;
     for (pts, _) in subs {
-        let poly = clip_polygon_within(pts, clip, &mut budget)?;
+        let poly = clip_polygon(pts, clip);
         if poly.len() >= 3 {
             ops.push(Op::M(poly[0]));
             ops.extend(poly[1..].iter().map(|p| Op::L(*p)));
             ops.push(Op::Z);
         }
     }
-    Some(ops)
+    ops
 }
 
 fn clip_stroke(subs: &[(Vec<P>, bool)], clip: &[P]) -> Vec<Op> {

crates/metafile/src/tests.rs

@@ -2074,63 +2074,3 @@ fn clip_polygon_work_bound() {
     let clipped = crate::cliprect::clip_polygon(&poly, &clip);
     assert!(clipped.is_empty(), "excessive polygon clip product rejected");
 }
-
-#[test]
-fn clip_polygon_charges_actual_work_not_projected_growth() {
-    // Two convex 1,000-gons: the product is exactly the budget, and a cut that adds a vertex must
-    // not make a later step look over budget.
-    let gon = |cx: f64| -> Vec<(f64, f64)> {
-        (0..1000).map(|i| (i as f64 / 1000.0 * std::f64::consts::TAU).sin_cos()).map(|(s, c)| (cx + 100.0 * c, 100.0 * s)).collect()
-    };
-    let clipped = crate::cliprect::clip_polygon(&gon(0.0), &gon(30.0));
-    assert!(clipped.len() > 100, "the intersection is kept: {}", clipped.len());
-}
-
-#[test]
-fn clip_work_is_shared_by_fill_and_stroke() {
-    use crate::canvas::Raw;
-    use crate::geom::Op;
-    // One zigzag subpath crossing a 512-gon's edge: about 510k point-edge tests per pass, so a
-    // fill alone fits the allowance but a fill plus a stroke would spend it twice.
-    let clip: Vec<(f64, f64)> =
-        (0..512).map(|i| (i as f64 / 512.0 * std::f64::consts::TAU).sin_cos()).map(|(s, c)| (100.0 + 100.0 * c, 100.0 + 100.0 * s)).collect();
-    let mut ops = vec![Op::M((0.0, 95.0))];
-    ops.extend((1..1000).map(|i| Op::L((i as f64 * 0.19, if i % 2 == 0 { 95.0 } else { 300.0 }))));
-    ops.push(Op::Z);
-    let raw = |fill, stroke| Raw::Path { ops: ops.clone(), fill, stroke, even_odd: false, region: None };
-    let black = [0, 0, 0, 255];
-    assert!(!crate::cliprect::clip_raw(raw(Some(black), None), &clip).is_empty(), "a fill alone is within the allowance");
-    assert!(crate::cliprect::clip_raw(raw(Some(black), Some((black, 1.0))), &clip).is_empty(), "fill and stroke share one allowance");
-}
-
-#[test]
-fn clip_work_is_bounded_across_subpaths() {
-    use crate::canvas::Raw;
-    use crate::geom::Op;
-    // 512-gon clip; 4,000 small triangles crossing its edge: each under the per-polygon cap, together
-    // far over it, for both the fill and the stroke.
-    let clip: Vec<(f64, f64)> =
-        (0..512).map(|i| (i as f64 / 512.0 * std::f64::consts::TAU).sin_cos()).map(|(s, c)| (100.0 + 100.0 * c, 100.0 + 100.0 * s)).collect();
-    let tri = |x: f64| [Op::M((x, 95.0)), Op::L((x + 1.0, 95.0)), Op::L((x, 300.0)), Op::Z];
-    let many: Vec<Op> = (0..4000).flat_map(|i| tri(i as f64 % 200.0)).collect();
-    let raw = |ops| Raw::Path { ops, fill: Some([0, 0, 0, 255]), stroke: Some(([0, 0, 0, 255], 1.0)), even_odd: false, region: None };
-    assert!(crate::cliprect::clip_raw(raw(many), &clip).is_empty(), "the whole item's clipping work is bounded");
-    assert_eq!(crate::cliprect::clip_raw(raw(tri(100.0).to_vec()), &clip).len(), 2, "a small crossing shape is still clipped");
-}
-
-/// Clipping a fill can add a vertex at every clip edge, so a polygon's work isn't its input size:
-/// shapes that pass the up-front estimate but grow while clipped are charged as they grow, against
-/// one budget for the whole item.
-#[test]
-fn growing_fill_clips_share_one_budget() {
-    use crate::canvas::Raw;
-    use crate::geom::Op;
-    let clip: Vec<(f64, f64)> =
-        (0..512).map(|i| (i as f64 / 512.0 * std::f64::consts::TAU).sin_cos()).map(|(s, c)| (100.0 + 100.0 * c, 100.0 + 100.0 * s)).collect();
-    // A triangle around the whole circle: clipped, it becomes the 512-gon, about 130,000 steps.
-    let tri = [Op::M((-1000.0, -1000.0)), Op::L((1000.0, -1000.0)), Op::L((100.0, 1000.0)), Op::Z];
-    let raw = |n: usize| Raw::Path { ops: tri.repeat(n), fill: Some([0, 0, 0, 255]), stroke: None, even_odd: false, region: None };
-    // 400 of them pass the estimate (400 x 4 x 512 is under a million) but cost about 52 million.
-    assert!(crate::cliprect::clip_raw(raw(400), &clip).is_empty(), "the growing work is charged");
-    assert_eq!(crate::cliprect::clip_raw(raw(2), &clip).len(), 1, "a couple of them are still clipped");
-}

crates/pptx/src/read.rs

@@ -100,8 +100,7 @@ impl Part {
     }
     /// Like [`Part::keep`], also declaring prefixes that only an enclosing wrapper binds.
     pub fn keep_inner(&self, el: &El) -> String {
-        let ns: Vec<(String, String)> = self.ns.iter().chain(&self.inner_ns).cloned().collect();
-        keep_xml(el, &ns)
+        keep_with(el, &[&self.ns, &self.inner_ns])
     }
 }
 
@@ -136,36 +135,69 @@ fn inner_decls(root: &El, ns: &[(String, String)]) -> Vec<(String, String)> {
     out
 }
 
-/// Serialize `el`, declaring every prefix it uses that the source root declared.
-pub fn keep_xml(el: &El, ns: &[(String, String)]) -> String {
-    let mut used = HashSet::new();
-    fn rec(e: &El, used: &mut HashSet<String>, depth: usize) {
+/// Longest namespace name copied onto a kept fragment or a resolved `mc` branch. Real ones are
+/// URIs of well under 100 bytes; a longer one is not copied, so one declaration cannot be
+/// multiplied by every fragment that uses its prefix.
+const MAX_NS_VALUE: usize = 2048;
+
+/// Prefixes `el` and its descendants use in element and attribute names, and those listed in
+/// `mc:Ignorable` or `mc:MustUnderstand` (which must stay declared for the markup-compatibility rules to hold),
+/// and those starting a QName-like attribute value.
+fn used_prefixes(el: &El) -> HashSet<&str> {
+    fn rec<'a>(e: &'a El, used: &mut HashSet<&'a str>, depth: usize) {
         if depth > crate::xml::MAX_DEPTH {
             return;
         }
         if let Some((p, _)) = e.name.split_once(':') {
-            used.insert(p.to_string());
+            used.insert(p);
         }
-        for (k, _) in &e.attrs {
-            if let Some((p, _)) = k.split_once(':')
+        for (k, v) in &e.attrs {
+            if let Some((p, local)) = k.split_once(':')
                 && p != "xmlns"
                 && p != "xml"
             {
-                used.insert(p.to_string());
+                used.insert(p);
+                if local == "Ignorable" || local == "MustUnderstand" {
+                    used.extend(v.split_whitespace());
+                }
+            }
+            // QName-valued attributes (`xsi:type="q:Item"`) need their prefix declared too.
+            if k != "xmlns" && !k.starts_with("xmlns:") {
+                for t in v.split_whitespace() {
+                    if let Some((p, _)) = t.split_once(':')
+                        && !p.is_empty()
+                    {
+                        used.insert(p);
+                    }
+                }
             }
         }
         for c in e.elements() {
             rec(c, used, depth + 1);
         }
     }
+    let mut used = HashSet::new();
     rec(el, &mut used, 0);
-    let mut el = el.clone();
-    for (k, v) in ns {
+    used
+}
+
+/// Serialize `el`, declaring every prefix it uses that the source root declared.
+pub fn keep_xml(el: &El, ns: &[(String, String)]) -> String {
+    keep_with(el, &[ns])
+}
+
+fn keep_with(el: &El, decls: &[&[(String, String)]]) -> String {
+    let used = used_prefixes(el);
+    let mut have: HashSet<&str> = el.attrs.iter().map(|(a, _)| a.as_str()).collect();
+    let mut extra = Vec::new();
+    for (k, v) in decls.iter().flat_map(|d| d.iter()) {
         let p = k.strip_prefix("xmlns:").unwrap_or("");
-        if !p.is_empty() && used.contains(p) && !el.attrs.iter().any(|(a, _)| a == k) {
-            el.attrs.push((k.clone(), v.clone()));
+        if !p.is_empty() && used.contains(p) && v.len() <= MAX_NS_VALUE && have.insert(k) {
+            extra.push((k.clone(), v.clone()));
         }
     }
+    let mut el = el.clone();
+    el.attrs.extend(extra);
     el.to_xml()
 }
 
@@ -314,10 +346,18 @@ fn kept_parts(pkg: &Package, pres_path: &str) -> Vec<deckcraft_model::KeptPart>
             // The part's own relationships (customXml item → itemProps) and their targets.
             let rp = opc::rels_path(&name);
             if let Some(rels_xml) = text(&rp) {
+                let mut capped = false;
                 for sub in pkg.rels(&name).items.iter().filter(|s| !s.external && keepable(&s.target)) {
-                    if let Some(x) = text(&sub.target)
-                        && !out.iter().any(|k| k.name.eq_ignore_ascii_case(&sub.target))
-                    {
+                    // Checked before the part is read: repeated relationships to one large part
+                    // must not copy it again each time.
+                    if out.iter().any(|k| k.name.eq_ignore_ascii_case(&sub.target)) {
+                        continue;
+                    }
+                    if out.len() >= 400 {
+                        capped = true;
+                        continue;
+                    }
+                    if let Some(x) = text(&sub.target) {
                         out.push(KeptPart {
                             content_type: pkg.content_type(&sub.target).unwrap_or_default(),
                             name: sub.target.clone(),
@@ -326,7 +366,9 @@ fn kept_parts(pkg: &Package, pres_path: &str) -> Vec<deckcraft_model::KeptPart>
                         });
                     }
                 }
-                out.push(KeptPart { name: rp, xml: rels_xml, ..Default::default() });
+                if !capped {
+                    out.push(KeptPart { name: rp, xml: rels_xml, ..Default::default() });
+                }
             }
         }
     }
@@ -363,15 +405,39 @@ fn resolve_mc_rels(el: &mut El, depth: usize, rels: Option<&Rels>) {
                     });
                     let branch = choice.or_else(|| ac.child("Fallback"));
                     if let Some(b) = branch {
+                        // The branch's namespace declarations (the first usable one of each name,
+                        // in order), indexed by prefix once: each child then looks up the prefixes
+                        // it uses instead of scanning every declaration.
+                        let mut decls: Vec<(&String, &String)> = Vec::new();
+                        // An oversized declaration still shadows an outer one of its name: its
+                        // content is left unbound rather than bound to the outer namespace.
+                        let mut by_prefix: HashMap<&str, Option<usize>> = HashMap::new();
+                        for (k, v) in b.attrs.iter().chain(ac.attrs.iter()) {
+                            let prefix = if k == "xmlns" { Some("") } else { k.strip_prefix("xmlns:") };
+                            if let Some(p) = prefix
+                                && !by_prefix.contains_key(p)
+                            {
+                                by_prefix.insert(p, (v.len() <= MAX_NS_VALUE).then_some(decls.len()));
+                                if v.len() <= MAX_NS_VALUE {
+                                    decls.push((k, v));
+                                }
+                            }
+                        }
                         for n in &b.children {
                             if let Node::El(e) = n {
+                                // Carry the namespace declarations from the branch that its content
+                                // uses (all of them per child made children x declarations copies).
+                                let used = used_prefixes(e);
+                                let have: HashSet<&str> = e.attrs.iter().map(|(a, _)| a.as_str()).collect();
+                                let mut wanted: Vec<usize> = std::iter::once("")
+                                    .chain(used.iter().copied())
+                                    .filter_map(|p| by_prefix.get(p).copied().flatten())
+                                    .filter(|&i| !have.contains(decls[i].0.as_str()))
+                                    .collect();
+                                wanted.sort_unstable();
+                                wanted.dedup();
                                 let mut e = e.clone();
-                                // Carry namespace declarations from the branch onto its content.
-                                for (k, v) in b.attrs.iter().chain(ac.attrs.iter()) {
-                                    if k.starts_with("xmlns") && !e.attrs.iter().any(|(a, _)| a == k) {
-                                        e.attrs.push((k.clone(), v.clone()));
-                                    }
-                                }
+                                e.attrs.extend(wanted.into_iter().map(|i| (decls[i].0.clone(), decls[i].1.clone())));
                                 out.push(Node::El(e));
                             }
                         }
@@ -1414,3 +1480,72 @@ fn header_footer(p: &Presentation) -> HeaderFooter {
     }
     hf
 }
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn mc_branches_carry_only_the_declarations_their_content_uses() {
+        // 2,000 declarations on the branch and 2,000 children: each child gets the one it uses
+        // (and the default), not all 2,000.
+        let decls: String = (0..2000).map(|i| format!(r#" xmlns:n{i}="urn:n{i}""#)).collect();
+        let kids: String = (0..2000).map(|i| format!("<n{i}:x/>")).collect();
+        let x = format!(
+            r#"<r xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006"><mc:AlternateContent><mc:Fallback xmlns="urn:d"{decls}>{kids}</mc:Fallback></mc:AlternateContent></r>"#
+        );
+        let mut d = crate::xml::parse(x.as_bytes()).unwrap();
+        resolve_mc(&mut d.root, 0);
+        let kids: Vec<&El> = d.root.elements().collect();
+        assert_eq!(kids.len(), 2000);
+        assert_eq!(kids[7].attrs, vec![("xmlns".to_string(), "urn:d".to_string()), ("xmlns:n7".to_string(), "urn:n7".to_string())]);
+    }
+
+    /// The branch's own declaration of a prefix wins over the `AlternateContent`'s; an oversized
+    /// one still shadows it (its content stays unbound); a child's own declaration is left alone.
+    #[test]
+    fn mc_branch_declarations_keep_their_precedence() {
+        let long = "u".repeat(MAX_NS_VALUE + 1);
+        let x = format!(
+            r#"<r xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006"><mc:AlternateContent xmlns:p="urn:ac" xmlns:q="urn:q-short"><mc:Fallback xmlns:p="urn:b" xmlns:q="{long}"><p:x/><q:y/><p:z xmlns:p="urn:own"/></mc:Fallback></mc:AlternateContent></r>"#
+        );
+        let mut d = crate::xml::parse(x.as_bytes()).unwrap();
+        resolve_mc(&mut d.root, 0);
+        let kids: Vec<&El> = d.root.elements().collect();
+        let attrs = |i: usize| kids[i].attrs.iter().map(|(k, v)| format!("{k}={v}")).collect::<Vec<_>>();
+        assert_eq!(attrs(0), ["xmlns:p=urn:b"]);
+        assert!(attrs(1).is_empty(), "{:?}", attrs(1));
+        assert_eq!(attrs(2), ["xmlns:p=urn:own"]);
+    }
+
+    #[test]
+    fn mc_branches_keep_prefixes_named_by_must_understand() {
+        let x = r#"<r xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006"><mc:AlternateContent><mc:Fallback xmlns:q="urn:q"><a mc:MustUnderstand="q"/></mc:Fallback></mc:AlternateContent></r>"#;
+        let mut d = crate::xml::parse(x.as_bytes()).unwrap();
+        resolve_mc(&mut d.root, 0);
+        let kid = d.root.elements().next().unwrap();
+        assert!(kid.attrs.iter().any(|(k, v)| k == "xmlns:q" && v == "urn:q"), "{:?}", kid.attrs);
+    }
+
+    #[test]
+    fn mc_branches_keep_prefixes_used_in_qname_values() {
+        let x = r#"<r xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006"><mc:AlternateContent><mc:Fallback xmlns:q="urn:q" xmlns:z="urn:z"><n xmlns:xsi="urn:xsi" xsi:type="q:Item"/></mc:Fallback></mc:AlternateContent></r>"#;
+        let mut d = crate::xml::parse(x.as_bytes()).unwrap();
+        resolve_mc(&mut d.root, 0);
+        let kid = d.root.elements().next().unwrap();
+        assert!(kid.attrs.iter().any(|(k, v)| k == "xmlns:q" && v == "urn:q"), "{:?}", kid.attrs);
+        assert!(!kid.attrs.iter().any(|(k, _)| k == "xmlns:z"), "unused declarations stay out: {:?}", kid.attrs);
+    }
+
+    #[test]
+    fn kept_fragments_skip_oversized_namespace_names() {
+        let big = "u".repeat(MAX_NS_VALUE + 1);
+        let ns = vec![("xmlns:a".to_string(), "urn:a".to_string()), ("xmlns:b".to_string(), big)];
+        let d = crate::xml::parse(br#"<a:x xmlns:a="urn:a" xmlns:b="urn:b"><b:y/></a:x>"#).unwrap();
+        let mut el = d.root.clone();
+        el.attrs.clear();
+        let out = keep_xml(&el, &ns);
+        assert!(out.contains(r#"xmlns:a="urn:a""#), "{out}");
+        assert!(!out.contains("uuuu"), "the oversized declaration is not copied");
+    }
+}