style: rustfmt

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 = Vec::new();
+        let mut used = HashSet::new();
         rel_attr_values(&root, &mut used, 0);
         // Every relationship the markup uses must be writable, or the object would be broken.
-        let writable = |id: &String| src.refs.iter().any(|r| r.id == *id && (r.external || self.embeds.available(&r.target)));
-        if !used.iter().all(writable) {
+        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())) {
             log::warn!("docx: an embedded object's parts are missing; it is left out");
             return None;
         }
@@ -637,13 +637,15 @@ fn set_attr(e: &mut El, k: &str, v: &str) {
     }
 }
 
-fn rel_attr_values(e: &El, out: &mut Vec<String>, depth: usize) {
+/// 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) {
     if depth > MAX_DEPTH {
         return;
     }
     for (k, v) in &e.attrs {
         if xml::is_rel_attr(&e.name, k) && !out.contains(v) {
-            out.push(v.clone());
+            out.insert(v.clone());
         }
     }
     for c in e.els() {
@@ -851,6 +853,24 @@ 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/model.rs

@@ -58,23 +58,6 @@ 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,11 +418,6 @@ 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();
@@ -433,7 +428,9 @@ impl FTable {
                             }
                             x += cc.colspan.clamp(1, 63) as usize;
                         }
-                        row.insert(at, Cell { colspan: span as u32, covered: true, ..Default::default() });
+                        if row.len() < 64 {
+                            row.insert(at, Cell { colspan: span as u32, covered: true, ..Default::default() });
+                        }
                     }
                 }
                 g += span;