fix(docx): look relationships up by id through an index

crates/docx/src/package.rs

@@ -350,6 +350,7 @@ impl Package {
                 let path = resolve(dir, target);
                 self.canonical(&path).map_or(path, str::to_string)
             };
+            rels.ids.entry(id.to_string()).or_insert(rels.list.len());
             rels.list.push(Rel { id: id.to_string(), kind: r.attr("Type").unwrap_or("").to_string(), target: resolved, external });
         }
         rels
@@ -405,11 +406,13 @@ pub struct Rel {
 #[derive(Clone, Debug, Default)]
 pub struct Rels {
     pub list: Vec<Rel>,
+    /// Each id's first relationship in `list`, so a lookup doesn't scan every relationship.
+    ids: HashMap<String, usize>,
 }
 
 impl Rels {
     pub fn by_id(&self, id: &str) -> Option<&Rel> {
-        self.list.iter().find(|r| r.id == id)
+        self.ids.get(id).and_then(|&i| self.list.get(i))
     }
     pub fn by_type(&self, full: &str) -> Option<&Rel> {
         self.list.iter().find(|r| rel_is(&r.kind, full))
@@ -547,6 +550,22 @@ mod tests {
         assert_eq!(crate::package_title(std::io::Cursor::new(z), 1 << 20).as_deref(), Some("Plan"));
     }
 
+    #[test]
+    fn relationships_are_looked_up_by_id_the_first_one_winning() {
+        let mut rels = String::from(r#"<Relationships xmlns="http://schemas.openxmlformats.org/package/2006/relationships">"#);
+        for i in 0..20_000 {
+            rels.push_str(&format!(r#"<Relationship Id="rId{i}" Type="hyperlink" Target="https://example.com/{i}" TargetMode="External"/>"#));
+        }
+        rels.push_str(r#"<Relationship Id="rId7" Type="hyperlink" Target="https://example.com/dup" TargetMode="External"/></Relationships>"#);
+        let z = zip_of(&[("word/_rels/document.xml.rels", rels.into_bytes())]);
+        let r = Package::open(&z).unwrap().rels("word/document.xml");
+        assert_eq!(r.by_id("rId7").map(|r| r.target.as_str()), Some("https://example.com/7"), "the first rId7 wins");
+        assert_eq!(r.by_id("rId19999").map(|r| r.target.as_str()), Some("https://example.com/19999"));
+        assert!(r.by_id("rId20000").is_none());
+        // Hyperlink-style lookups, one per relationship, are each a map lookup.
+        assert_eq!((0..20_000).filter(|i| r.by_id(&format!("rId{i}")).is_some()).count(), 20_000);
+    }
+
     #[test]
     fn decompression_bomb_is_rejected() {
         let z = zip_of(&[("word/document.xml", vec![b' '; 2_000_000])]);

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