fix(formats): count spreadsheet cell characters as they are added

crates/docx/src/write/embed.rs

@@ -353,11 +353,11 @@ impl super::Writer<'_> {
         };
         self.embeds.markup_bytes = left;
         let mut root = xml::parse(src.xml.as_bytes()).ok()?;
-        let mut used = HashSet::new();
+        let mut used = Vec::new();
         rel_attr_values(&root, &mut used, 0);
         // Every relationship the markup uses must be writable, or the object would be broken.
-        let writable: HashSet<&str> = src.refs.iter().filter(|r| r.external || self.embeds.available(&r.target)).map(|r| r.id.as_str()).collect();
-        if !used.iter().all(|id| writable.contains(id.as_str())) {
+        let writable = |id: &String| src.refs.iter().any(|r| r.id == *id && (r.external || self.embeds.available(&r.target)));
+        if !used.iter().all(writable) {
             log::warn!("docx: an embedded object's parts are missing; it is left out");
             return None;
         }
@@ -637,15 +637,13 @@ fn set_attr(e: &mut El, k: &str, v: &str) {
     }
 }
 
-/// The distinct relationship ids `e` uses: a set, so a large tree (a native document's markup
-/// never went through the reader's id limit) costs no scan per attribute.
-fn rel_attr_values(e: &El, out: &mut HashSet<String>, depth: usize) {
+fn rel_attr_values(e: &El, out: &mut Vec<String>, depth: usize) {
     if depth > MAX_DEPTH {
         return;
     }
     for (k, v) in &e.attrs {
         if xml::is_rel_attr(&e.name, k) && !out.contains(v) {
-            out.insert(v.clone());
+            out.push(v.clone());
         }
     }
     for c in e.els() {
@@ -853,24 +851,6 @@ fn valid_part_name(name: &str) -> String {
 mod tests {
     use super::*;
 
-    #[test]
-    fn relationship_ids_are_collected_once_each() {
-        // A native document's embedded markup skips the reader's id limit: 40,000 distinct ids
-        // (each named twice) were a scan of every id collected so far, per attribute.
-        let mut xml = String::from(
-            r#"<w:p xmlns:w="http://schemas.openxmlformats.org/wordprocessingml/2006/main" xmlns:r="http://schemas.openxmlformats.org/officeDocument/2006/relationships">"#,
-        );
-        for i in 0..40_000 {
-            xml.push_str(&format!(r#"<w:r r:id="rId{i}"/><w:r r:id="rId{i}"/>"#));
-        }
-        xml.push_str("</w:p>");
-        let root = xml::parse(xml.as_bytes()).unwrap();
-        let mut used = HashSet::new();
-        rel_attr_values(&root, &mut used, 0);
-        assert_eq!(used.len(), 40_000);
-        assert!(used.contains("rId39999"));
-    }
-
     #[test]
     fn charts_cut_to_the_limits_on_save_say_so_once() {
         // A model deserialised as is can hold more than a chart part keeps; the save left the rest

crates/formats/src/sheet.rs

@@ -323,11 +323,13 @@ fn attr(e: &BytesStart<'_>, name: &[u8]) -> Option<String> {
     })
 }
 
-/// `s` + `t`, keeping `s` at most [`MAX_CELL_CHARS`] characters.
-fn push_capped(s: &mut String, t: &str) {
-    let have = s.chars().count();
-    if have < MAX_CELL_CHARS {
-        s.extend(t.chars().take(MAX_CELL_CHARS - have));
+/// `s` + `t`, keeping `s` at most [`MAX_CELL_CHARS`] characters. `have` is `s`'s character
+/// count, kept up to date here: counting `s` again for every piece of text made a full cell
+/// cost its length per further text event.
+fn push_capped(s: &mut String, have: &mut usize, t: &str) {
+    for c in t.chars().take(MAX_CELL_CHARS.saturating_sub(*have)) {
+        s.push(c);
+        *have += 1;
     }
 }
 
@@ -444,6 +446,22 @@ mod tests {
         ])
     }
 
+    #[test]
+    fn a_full_cell_takes_further_text_without_recounting() {
+        let (mut s, mut n) = (String::new(), 0usize);
+        push_capped(&mut s, &mut n, "é");
+        push_capped(&mut s, &mut n, &"x".repeat(MAX_CELL_CHARS));
+        assert_eq!((s.chars().count(), n), (MAX_CELL_CHARS, MAX_CELL_CHARS));
+        // A million more text events on the full cell each cost nothing (they used to count it).
+        let t = std::time::Instant::now();
+        for _ in 0..1_000_000 {
+            push_capped(&mut s, &mut n, "y");
+        }
+        assert!(t.elapsed() < std::time::Duration::from_secs(10), "{:?}", t.elapsed());
+        assert_eq!(s.chars().count(), MAX_CELL_CHARS);
+        assert!(!s.contains('y'));
+    }
+
     /// #1287: one long shared string in thousands of cells stays under the text budget.
     #[test]
     fn xlsx_shared_strings_cannot_blow_up_memory() {

crates/formats/src/sheet/ods.rs

@@ -11,6 +11,8 @@ struct OCell {
     kind: String,
     value: Option<String>,
     text: String,
+    /// Characters in `text` (see [`push_capped`]).
+    text_chars: usize,
     paras: usize,
 }
 
@@ -77,7 +79,7 @@ pub(super) fn ods_read(xml: &[u8], want: Option<usize>) -> Result<(Vec<String>,
                         && skip == 0
                     {
                         if c.paras > 0 {
-                            push_capped(&mut c.text, "\n");
+                            push_capped(&mut c.text, &mut c.text_chars, "\n");
                         }
                         c.paras += 1;
                     }
@@ -86,17 +88,17 @@ pub(super) fn ods_read(xml: &[u8], want: Option<usize>) -> Result<(Vec<String>,
                 b"s" if in_p > 0 && skip == 0 => {
                     let k = attr(e, b"c").and_then(|v| v.trim().parse::<usize>().ok()).unwrap_or(1).clamp(1, 1_000);
                     if let Some(c) = cell.as_mut() {
-                        push_capped(&mut c.text, &" ".repeat(k));
+                        push_capped(&mut c.text, &mut c.text_chars, &" ".repeat(k));
                     }
                 }
                 b"tab" if in_p > 0 && skip == 0 => {
                     if let Some(c) = cell.as_mut() {
-                        push_capped(&mut c.text, "\t");
+                        push_capped(&mut c.text, &mut c.text_chars, "\t");
                     }
                 }
                 b"line-break" if in_p > 0 && skip == 0 => {
                     if let Some(c) = cell.as_mut() {
-                        push_capped(&mut c.text, "\n");
+                        push_capped(&mut c.text, &mut c.text_chars, "\n");
                     }
                 }
                 _ => {}
@@ -107,7 +109,7 @@ pub(super) fn ods_read(xml: &[u8], want: Option<usize>) -> Result<(Vec<String>,
                 && skip == 0
                 && let Some(c) = cell.as_mut()
             {
-                push_capped(&mut c.text, &t);
+                push_capped(&mut c.text, &mut c.text_chars, &t);
             }
         }
         Ev::End(n) => {
@@ -181,7 +183,7 @@ fn ods_value(c: &OCell) -> String {
         ("string", Some(v)) if c.text.trim().is_empty() => {
             // Attribute text obeys the same per-cell cap as `<text:p>` text.
             let mut s = String::new();
-            push_capped(&mut s, v);
+            push_capped(&mut s, &mut 0, v);
             s
         }
         _ => c.text.clone(),

crates/formats/src/sheet/xlsx.rs

@@ -103,18 +103,18 @@ pub(super) fn xlsx_sheets(pkg: &mut Package<'_>) -> Result<Vec<SheetRef>, String
 /// (`rPh`) left out.
 fn shared_strings(xml: &[u8]) -> Vec<String> {
     let mut out = Vec::new();
-    let mut cur: Option<String> = None;
+    let mut cur: Option<(String, usize)> = None;
     let (mut in_t, mut phonetic) = (false, 0usize);
     walk(xml, |ev| match ev {
         Ev::Start(e) => match e.local_name().as_ref() {
-            b"si" => cur = Some(String::new()),
+            b"si" => cur = Some((String::new(), 0)),
             b"t" => in_t = true,
             b"rPh" => phonetic += 1,
             _ => {}
         },
         Ev::End(n) => match n.as_slice() {
             b"si" => {
-                if let Some(s) = cur.take()
+                if let Some((s, _)) = cur.take()
                     && out.len() < MAX_SHARED
                 {
                     out.push(s);
@@ -127,9 +127,9 @@ fn shared_strings(xml: &[u8]) -> Vec<String> {
         Ev::Text(t) => {
             if in_t
                 && phonetic == 0
-                && let Some(s) = cur.as_mut()
+                && let Some((s, n)) = cur.as_mut()
             {
-                push_capped(s, &t);
+                push_capped(s, n, &t);
             }
         }
     });
@@ -183,6 +183,9 @@ struct XCell {
     style: usize,
     value: String,
     inline: String,
+    /// Characters in `value` and `inline` (see [`push_capped`]).
+    value_chars: usize,
+    inline_chars: usize,
 }
 
 pub(super) fn xlsx_rows(pkg: &mut Package<'_>, path: &str) -> Result<Vec<Vec<String>>, String> {
@@ -228,9 +231,9 @@ pub(super) fn xlsx_rows(pkg: &mut Package<'_>, path: &str) -> Result<Vec<Vec<Str
         Ev::Text(t) => {
             if let Some(c) = cell.as_mut() {
                 if in_v {
-                    push_capped(&mut c.value, &t);
+                    push_capped(&mut c.value, &mut c.value_chars, &t);
                 } else if in_is_t && phonetic == 0 {
-                    push_capped(&mut c.inline, &t);
+                    push_capped(&mut c.inline, &mut c.inline_chars, &t);
                 }
             }
         }