fix(formats): skip full rows before walking them for HTML rowspans

crates/formats/src/model.rs

@@ -58,6 +58,23 @@ mod tests {
         assert!(t.rows.iter().all(|r| r.len() <= 64), "a row grew past the column cap");
     }
 
+    #[test]
+    fn insert_covered_skips_full_rows_without_walking_them() {
+        // 50,000 spanning cells over a 50,000-cell row: each walked the row below to its grid
+        // column before finding it full (billions of steps). A full row is now skipped at once.
+        let n = 50_000;
+        let mut t = FTable {
+            rows: vec![vec![Cell { rowspan: 2, ..Default::default() }; n], vec![Cell::default(); n]],
+            widths: Vec::new(),
+            borderless: false,
+        };
+        let start = std::time::Instant::now();
+        t.insert_covered();
+        assert!(start.elapsed() < std::time::Duration::from_secs(10), "{:?}", start.elapsed());
+        assert_eq!(t.rows[1].len(), n, "a full row takes no covered cell");
+        assert!(t.rows[1].iter().all(|c| !c.covered));
+    }
+
     #[test]
     fn base64_round_trip() {
         for data in [&b""[..], b"f", b"fo", b"foo", b"foob", b"fooba", b"foobar", &[0, 255, 128, 7]] {

crates/formats/src/model/types.rs

@@ -418,6 +418,11 @@ impl FTable {
                             return;
                         }
                         let Some(row) = self.rows.get_mut(r + k) else { break };
+                        // A full row takes no covered cell: checked before it is walked, so a
+                        // wide row isn't scanned for every span above it.
+                        if row.len() >= 64 {
+                            continue;
+                        }
                         // Find the index in that row at grid column `g`.
                         let mut x = 0usize;
                         let mut at = row.len();
@@ -428,9 +433,7 @@ impl FTable {
                             }
                             x += cc.colspan.clamp(1, 63) as usize;
                         }
-                        if row.len() < 64 {
-                            row.insert(at, Cell { colspan: span as u32, covered: true, ..Default::default() });
-                        }
+                        row.insert(at, Cell { colspan: span as u32, covered: true, ..Default::default() });
                     }
                 }
                 g += span;

crates/formats/src/sheet.rs

@@ -323,13 +323,11 @@ fn attr(e: &BytesStart<'_>, name: &[u8]) -> Option<String> {
     })
 }
 
-/// `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;
+/// `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));
     }
 }
 
@@ -446,22 +444,6 @@ 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,8 +11,6 @@ struct OCell {
     kind: String,
     value: Option<String>,
     text: String,
-    /// Characters in `text` (see [`push_capped`]).
-    text_chars: usize,
     paras: usize,
 }
 
@@ -79,7 +77,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, &mut c.text_chars, "\n");
+                            push_capped(&mut c.text, "\n");
                         }
                         c.paras += 1;
                     }
@@ -88,17 +86,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, &mut c.text_chars, &" ".repeat(k));
+                        push_capped(&mut c.text, &" ".repeat(k));
                     }
                 }
                 b"tab" if in_p > 0 && skip == 0 => {
                     if let Some(c) = cell.as_mut() {
-                        push_capped(&mut c.text, &mut c.text_chars, "\t");
+                        push_capped(&mut c.text, "\t");
                     }
                 }
                 b"line-break" if in_p > 0 && skip == 0 => {
                     if let Some(c) = cell.as_mut() {
-                        push_capped(&mut c.text, &mut c.text_chars, "\n");
+                        push_capped(&mut c.text, "\n");
                     }
                 }
                 _ => {}
@@ -109,7 +107,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, &mut c.text_chars, &t);
+                push_capped(&mut c.text, &t);
             }
         }
         Ev::End(n) => {
@@ -183,7 +181,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, &mut 0, v);
+            push_capped(&mut s, 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, usize)> = None;
+    let mut cur: Option<String> = 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(), 0)),
+            b"si" => cur = Some(String::new()),
             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, n)) = cur.as_mut()
+                && let Some(s) = cur.as_mut()
             {
-                push_capped(s, n, &t);
+                push_capped(s, &t);
             }
         }
     });
@@ -183,9 +183,6 @@ 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> {
@@ -231,9 +228,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, &mut c.value_chars, &t);
+                    push_capped(&mut c.value, &t);
                 } else if in_is_t && phonetic == 0 {
-                    push_capped(&mut c.inline, &mut c.inline_chars, &t);
+                    push_capped(&mut c.inline, &t);
                 }
             }
         }