fix(formats): hand imported lists their numbering ids without a scan per list

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/model/to_doc.rs

@@ -118,6 +118,10 @@ struct Builder<'a> {
     revs: std::collections::HashMap<(u8, RevMark), u32>,
     /// Link and font bytes given to runs so far ([`MAX_RUN_STRINGS`]).
     run_strings: usize,
+    /// The ids the next list's abstract and concrete numbering take: past every id in `doc`,
+    /// found once rather than by a scan of every numbering per list.
+    next_abstract: u32,
+    next_num: u32,
 }
 
 fn rev_key(kind: RevisionKind) -> u8 {
@@ -137,7 +141,9 @@ impl<'a> Builder<'a> {
                 revs.entry((rev_key(r.kind), mark)).or_insert(i as u32);
             }
         }
-        Builder { doc, revs, run_strings: 0 }
+        let next_abstract = doc.numbering.abstracts.iter().map(|a| a.id.saturating_add(1)).max().unwrap_or(0);
+        let next_num = doc.numbering.nums.iter().map(|n| n.id.saturating_add(1)).max().unwrap_or(1).max(1);
+        Builder { doc, revs, run_strings: 0, next_abstract, next_num }
     }
 
     /// The document revision for a tracked change, added the first time it is seen.
@@ -291,9 +297,10 @@ impl<'a> Builder<'a> {
             })
             .collect();
         let numbering = &mut self.doc.numbering;
-        let aid = numbering.abstracts.iter().map(|a| a.id + 1).max().unwrap_or(0);
+        let (aid, nid) = (self.next_abstract, self.next_num);
+        self.next_abstract = aid.saturating_add(1);
+        self.next_num = nid.saturating_add(1);
         numbering.abstracts.push(AbstractNum { id: aid, name: None, levels, ..Default::default() });
-        let nid = numbering.nums.iter().map(|n| n.id + 1).max().unwrap_or(1).max(1);
         numbering.nums.push(Num { id: nid, abstract_id: aid, ..Default::default() });
         nid
     }

crates/formats/src/tests.rs

@@ -1019,3 +1019,14 @@ fn latex_export_keeps_repeated_spaces() {
     let d = crate::import("tex", tex.as_bytes()).unwrap().unwrap();
     assert_eq!(para_texts(&d), vec!["a  b   c".to_string()]);
 }
+
+#[test]
+fn many_imported_lists_take_fresh_numbering_ids_in_turn() {
+    // Each list found its ids by scanning every numbering made before it (quadratic in lists).
+    let md: String = (0..4000).map(|i| if i % 2 == 0 { "- a\n\n" } else { "1. b\n\n" }).collect();
+    let d = import("md", md.as_bytes()).expect("handled").expect("import");
+    let ids: Vec<u32> = d.numbering.nums.iter().map(|n| n.id).collect();
+    assert_eq!(ids, (1..=4000).collect::<Vec<u32>>());
+    let abstracts: Vec<u32> = d.numbering.abstracts.iter().map(|a| a.id).collect();
+    assert_eq!(abstracts, (0..4000).collect::<Vec<u32>>());
+}