engine: pass the test run's text by value

crates/engine/src/spell.rs

@@ -700,15 +700,29 @@ pub struct Word {
     pub repeated: Option<usize>,
 }
 
+/// Longest language tag a word is checked in. BCP 47 tags in documents are a few bytes; a longer
+/// value from a file is no language we have a dictionary for, and copying it into every word of
+/// a paragraph would multiply it.
+const MAX_LANG_LEN: usize = 64;
+
 /// The words of `p`, each with its run's language (`lang` on the run, else `default`). Words
 /// with digits are skipped; apostrophes inside a word belong to it; hyphenated words are checked
-/// part by part.
+/// part by part. A language over [`MAX_LANG_LEN`] counts as none.
 pub fn paragraph_words(p: &deckcraft_model::Paragraph, default: &str) -> Vec<Word> {
     let mut chars: Vec<(char, usize)> = vec![];
     for (ri, r) in p.runs.iter().enumerate() {
         chars.extend(r.content().chars().map(|c| (c, ri)));
     }
-    let lang_of = |ri: usize| p.runs.get(ri).and_then(|r| r.props.lang.clone()).filter(|l| !l.is_empty()).unwrap_or_else(|| default.to_string());
+    let default = if default.len() > MAX_LANG_LEN { "" } else { default };
+    let lang_of = |ri: usize| {
+        p.runs
+            .get(ri)
+            .and_then(|r| r.props.lang.as_deref())
+            .filter(|l| !l.is_empty())
+            .map(|l| if l.len() > MAX_LANG_LEN { "" } else { l })
+            .unwrap_or(default)
+            .to_string()
+    };
     // Combining marks (decomposed accents) belong to the letter before them.
     let inside = |c: char| c.is_alphanumeric() || deckcraft_model::words::is_combining_mark(c) || c == '\'' || c == '’' || c == '-';
     let mut out = vec![];
@@ -791,15 +805,18 @@ pub fn misspelt(p: &deckcraft_model::Paragraph, default: &str, ignore: &[String]
         .chain(repeated(p, default))
         .collect::<Vec<_>>()
         .into_iter()
-        .fold(vec![], |mut v: Vec<Word>, w| {
+        .fold((vec![], HashMap::new()), |(mut v, mut at): (Vec<Word>, HashMap<usize, usize>), w| {
             // A repeated misspelt word is reported once, as repeated.
-            if let Some(i) = v.iter().position(|x| x.start == w.start) {
-                v[i] = w;
-            } else {
-                v.push(w);
+            match at.get(&w.start).and_then(|&i| v.get_mut(i)) {
+                Some(x) => *x = w,
+                None => {
+                    at.insert(w.start, v.len());
+                    v.push(w);
+                }
             }
-            v
+            (v, at)
         })
+        .0
 }
 
 /// Use `d` for `lang` from now on in this process (a dictionary the app loaded itself).
@@ -953,6 +970,23 @@ SFX D Y 1\nSFX D 0 ed/S .\n";
         assert_eq!(w, vec!["check", "done"]);
     }
 
+    #[test]
+    fn a_long_paragraph_with_a_huge_language_is_checked_in_linear_work() {
+        use deckcraft_model::{Paragraph, Run, RunProps};
+        // 100,000 copies of one word under a 1 MB language value: every word after the first is
+        // a repeat, and no word carries a copy of the value.
+        let lang = "x".repeat(1 << 20);
+        let p =
+            Paragraph { runs: vec![Run::with("the ".repeat(100_000), RunProps { lang: Some(lang), ..Default::default() })], ..Default::default() };
+        let words = paragraph_words(&p, "en-US");
+        assert_eq!(words.len(), 100_000);
+        assert!(words.iter().all(|w| w.lang.is_empty()));
+        let bad = misspelt(&p, "en-US", &[]);
+        assert_eq!(bad.len(), 99_999);
+        assert!(bad.iter().all(|w| w.repeated.is_some()));
+        assert!(paragraph_words(&Paragraph::new("word"), &"y".repeat(100)).iter().all(|w| w.lang.is_empty()));
+    }
+
     #[test]
     fn long_and_numeric_flags_and_latin1() {
         let d = Dictionary::parse(b"FLAG long\nSFX Aa Y 1\nSFX Aa 0 s .\n", b"1\ncat/Aa\n");

crates/pptx/src/read.rs

@@ -100,7 +100,8 @@ impl Part {
     }
     /// Like [`Part::keep`], also declaring prefixes that only an enclosing wrapper binds.
     pub fn keep_inner(&self, el: &El) -> String {
-        keep_with(el, &[&self.ns, &self.inner_ns])
+        let ns: Vec<(String, String)> = self.ns.iter().chain(&self.inner_ns).cloned().collect();
+        keep_xml(el, &ns)
     }
 }
 
@@ -135,58 +136,36 @@ fn inner_decls(root: &El, ns: &[(String, String)]) -> Vec<(String, String)> {
     out
 }
 
-/// 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).
-fn used_prefixes(el: &El) -> HashSet<&str> {
-    fn rec<'a>(e: &'a El, used: &mut HashSet<&'a str>, depth: usize) {
+/// 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) {
         if depth > crate::xml::MAX_DEPTH {
             return;
         }
         if let Some((p, _)) = e.name.split_once(':') {
-            used.insert(p);
+            used.insert(p.to_string());
         }
-        for (k, v) in &e.attrs {
-            if let Some((p, local)) = k.split_once(':')
+        for (k, _) in &e.attrs {
+            if let Some((p, _)) = k.split_once(':')
                 && p != "xmlns"
                 && p != "xml"
             {
-                used.insert(p);
-                if local == "Ignorable" || local == "MustUnderstand" {
-                    used.extend(v.split_whitespace());
-                }
+                used.insert(p.to_string());
             }
         }
         for c in e.elements() {
             rec(c, used, depth + 1);
         }
     }
-    let mut used = HashSet::new();
     rec(el, &mut used, 0);
-    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 mut el = el.clone();
+    for (k, v) in ns {
         let p = k.strip_prefix("xmlns:").unwrap_or("");
-        if !p.is_empty() && used.contains(p) && v.len() <= MAX_NS_VALUE && have.insert(k) {
-            extra.push((k.clone(), v.clone()));
+        if !p.is_empty() && used.contains(p) && !el.attrs.iter().any(|(a, _)| a == k) {
+            el.attrs.push((k.clone(), v.clone()));
         }
     }
-    let mut el = el.clone();
-    el.attrs.extend(extra);
     el.to_xml()
 }
 
@@ -336,12 +315,9 @@ 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)) {
-                    // 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) {
+                    if let Some(x) = text(&sub.target)
+                        && !out.iter().any(|k| k.name.eq_ignore_ascii_case(&sub.target))
+                    {
                         out.push(KeptPart {
                             content_type: pkg.content_type(&sub.target).unwrap_or_default(),
                             name: sub.target.clone(),
@@ -387,39 +363,15 @@ 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();
-                                e.attrs.extend(wanted.into_iter().map(|i| (decls[i].0.clone(), decls[i].1.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()));
+                                    }
+                                }
                                 out.push(Node::El(e));
                             }
                         }
@@ -1462,62 +1414,3 @@ 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 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");
-    }
-}