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])]);