pptx: copy only used, bounded namespace declarations onto imported fragments

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,58 @@ 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` (which must stay declared for the markup-compatibility rules to hold).
+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" {
+                    used.extend(v.split_whitespace());
+                }
             }
         }
         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()
 }
 
@@ -315,9 +336,12 @@ fn kept_parts(pkg: &Package, pres_path: &str) -> Vec<deckcraft_model::KeptPart>
             let rp = opc::rels_path(&name);
             if let Some(rels_xml) = text(&rp) {
                 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.len() >= 400 || out.iter().any(|k| k.name.eq_ignore_ascii_case(&sub.target)) {
+                        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(),
@@ -365,13 +389,19 @@ fn resolve_mc_rels(el: &mut El, depth: usize, rels: Option<&Rels>) {
                     if let Some(b) = branch {
                         for n in &b.children {
                             if let Node::El(e) = n {
-                                let mut e = e.clone();
-                                // Carry namespace declarations from the branch onto its content.
+                                // 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 mut have: HashSet<&str> = e.attrs.iter().map(|(a, _)| a.as_str()).collect();
+                                let mut extra = Vec::new();
                                 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()));
+                                    let needed = k == "xmlns" || k.strip_prefix("xmlns:").is_some_and(|p| used.contains(p));
+                                    if needed && v.len() <= MAX_NS_VALUE && have.insert(k) {
+                                        extra.push((k.clone(), v.clone()));
                                     }
                                 }
+                                let mut e = e.clone();
+                                e.attrs.extend(extra);
                                 out.push(Node::El(e));
                             }
                         }
@@ -1414,3 +1444,36 @@ 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())]);
+    }
+
+    #[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");
+    }
+}

crates/text/src/breaking.rs

@@ -260,15 +260,12 @@ pub(crate) struct Tab {
     align: TabAlign,
 }
 
-/// The paragraph's tab stops in position order (a stop at no finite position is left out), so
-/// [`tab_advance`] finds the next one by binary search instead of a scan per tab.
 pub(crate) fn tabs_of(props: &ParaProps) -> Vec<Tab> {
-    let mut tabs: Vec<Tab> = props
+    props
         .tabs
         .as_ref()
         .map(|t| {
             t.iter()
-                .filter(|s| s.pos.is_finite())
                 .map(|s| Tab {
                     pos: s.pos,
                     align: match s.align.as_str() {
@@ -280,9 +277,7 @@ pub(crate) fn tabs_of(props: &ParaProps) -> Vec<Tab> {
                 })
                 .collect()
         })
-        .unwrap_or_default();
-    tabs.sort_by(|a, b| a.pos.total_cmp(&b.pos));
-    tabs
+        .unwrap_or_default()
 }
 
 /// Width of the text after the tab at cell `i` up to the next tab or line break, and the width of
@@ -306,15 +301,16 @@ pub(crate) fn tab_segment(cells: &[Cell], i: usize) -> (f64, f64) {
 /// (`seg`: its width, and its width before the decimal point) as the stop aligns it but never
 /// moving back, as PowerPoint does; past the last stop, to the next default stop.
 pub(crate) fn tab_advance(x: f64, stops: &[Tab], default_tab: f64, seg: (f64, f64)) -> f64 {
-    // `stops` is in position order (`tabs_of`): the next stop is the first past x.
-    if let Some(s) = stops.get(stops.partition_point(|s| s.pos <= x + 0.5)) {
-        let to = s.pos - x;
-        return match s.align {
-            TabAlign::Left => to,
-            TabAlign::Right => (to - seg.0).max(0.0),
-            TabAlign::Center => (to - seg.0 / 2.0).max(0.0),
-            TabAlign::Decimal => (to - seg.1).max(0.0),
-        };
+    for s in stops {
+        if s.pos > x + 0.5 {
+            let to = s.pos - x;
+            return match s.align {
+                TabAlign::Left => to,
+                TabAlign::Right => (to - seg.0).max(0.0),
+                TabAlign::Center => (to - seg.0 / 2.0).max(0.0),
+                TabAlign::Decimal => (to - seg.1).max(0.0),
+            };
+        }
     }
     let d = if default_tab > 1.0 { default_tab } else { 72.0 };
     let next = ((x / d).floor() + 1.0) * d;

crates/text/src/tests.rs

@@ -1416,16 +1416,6 @@ fn tab_stops_align_the_text_after_them() {
     assert!((l.lines[0].edges[4].0 - x0(&l) - 72.0).abs() < 0.01);
 }
 
-#[test]
-fn many_tabs_over_many_stops_lay_out_by_position() {
-    // 20,000 stops given out of order, and 2,000 tabs: each tab finds the next stop by position.
-    let mut stops: Vec<(f64, &str)> = (1..=20_000).rev().map(|k| (k as f64 * 0.05 + 30.0, "l")).collect();
-    stops.push((f64::NAN, "l"));
-    let text = "a\t".repeat(2_000);
-    let l = tabbed(&text, &stops, 1.0e6);
-    assert!((l.lines[0].edges[2].0 - l.inner.x0 - 30.05).abs() < 0.01, "{:?}", &l.lines[0].edges[..3]);
-}
-
 #[test]
 fn a_tab_past_the_end_moves_to_the_next_line() {
     // PowerPoint: "abcdefghij\tk\tl\tm…" in a narrow box puts the tab that doesn't fit on the next