pptx: index relationships by id on read and by target on write

crates/pptx/src/opc.rs

@@ -171,6 +171,7 @@ fn rels_of(doc: &xml::Doc, part: &str) -> Rels {
         let external = r.attr("TargetMode").is_some_and(|m| m.eq_ignore_ascii_case("external"));
         let target_raw = target.to_string();
         let target = if external { target_raw.clone() } else { resolve(&base, target) };
+        out.by_id.entry(id.to_string()).or_insert(out.items.len());
         out.items.push(Rel {
             id: id.to_string(),
             kind: ty.rsplit('/').next().unwrap_or(ty).to_string(),
@@ -211,11 +212,13 @@ pub struct Rel {
 #[derive(Clone, Debug, Default)]
 pub struct Rels {
     pub items: Vec<Rel>,
+    /// Id → index of its first relationship in `items`.
+    by_id: HashMap<String, usize>,
 }
 
 impl Rels {
     pub fn get(&self, id: &str) -> Option<&Rel> {
-        self.items.iter().find(|r| r.id == id)
+        self.by_id.get(id).and_then(|&i| self.items.get(i))
     }
     pub fn target(&self, id: &str) -> Option<&str> {
         self.get(id).map(|r| r.target.as_str())
@@ -339,23 +342,29 @@ pub fn relative(from: &str, to: &str) -> String {
 #[derive(Default)]
 pub struct RelsOut {
     pub items: Vec<(String, String, String, bool)>,
+    /// (type, target, external) → id of the relationship [`RelsOut::add`] made for it.
+    added: HashMap<(String, String, bool), String>,
 }
 
 impl RelsOut {
     /// Add (or reuse) a relationship; `kind` is a full type URI or a suffix of the standard base.
     pub fn add(&mut self, kind: &str, target: &str, external: bool) -> String {
         let ty = if kind.starts_with("http") { kind.to_string() } else { format!("{RT_BASE}{kind}") };
-        if let Some((id, ..)) = self.items.iter().find(|(_, t, tg, e)| *t == ty && tg == target && *e == external) {
+        let key = (ty, target.to_string(), external);
+        if let Some(id) = self.added.get(&key) {
             return id.clone();
         }
         let id = format!("rId{}", self.items.len() + 1);
-        self.items.push((id.clone(), ty, target.to_string(), external));
+        self.items.push((id.clone(), key.0.clone(), key.1.clone(), external));
+        self.added.insert(key, id.clone());
         id
     }
     /// Always add a new relationship even if an identical one exists.
     pub fn add_new(&mut self, kind: &str, target: &str, external: bool) -> String {
         let ty = if kind.starts_with("http") { kind.to_string() } else { format!("{RT_BASE}{kind}") };
         let id = format!("rId{}", self.items.len() + 1);
+        // `add` reuses the first relationship for a target, whichever call made it.
+        self.added.entry((ty.clone(), target.to_string(), external)).or_insert_with(|| id.clone());
         self.items.push((id.clone(), ty, target.to_string(), external));
         id
     }
@@ -500,6 +509,27 @@ mod tests {
         assert!(p.get("e").is_some());
     }
 
+    #[test]
+    fn many_relationships_are_found_by_index_and_first_id_wins() {
+        let n = 50_000;
+        let mut x = String::from(r#"<Relationships xmlns="http://schemas.openxmlformats.org/package/2006/relationships">"#);
+        for i in 0..n {
+            x.push_str(&format!(r#"<Relationship Id="rId{i}" Type="{RT_BASE}image" Target="../media/image{i}.png"/>"#));
+        }
+        x.push_str(&format!(r#"<Relationship Id="rId0" Type="{RT_BASE}image" Target="../media/dup.png"/></Relationships>"#));
+        let rels = rels_from_bytes(x.as_bytes(), "ppt/slides/slide1.xml");
+        assert_eq!(rels.target("rId0"), Some("ppt/media/image0.png"), "the first of a repeated id wins");
+        assert!((0..n).all(|i| rels.target(&format!("rId{i}")) == Some(&*format!("ppt/media/image{i}.png"))));
+
+        let mut out = RelsOut::default();
+        let ids: Vec<String> = (0..n).map(|i| out.add("hyperlink", &format!("https://example.com/{i}"), true)).collect();
+        assert_eq!(out.add("hyperlink", "https://example.com/7", true), ids[7], "an identical target reuses its id");
+        assert_eq!(out.add("hyperlink", "https://example.com/7", false), format!("rId{}", n + 1), "internal is distinct");
+        let fresh = out.add_new("image", "../media/a.png", false);
+        assert_ne!(out.add_new("image", "../media/a.png", false), fresh);
+        assert_eq!(out.add("image", "../media/a.png", false), fresh, "add reuses the first add_new made");
+    }
+
     #[test]
     fn backslash_zip_entry_names_are_found() {
         let z = zip_of(&[("PPT\\Slides\\Slide1.xml", 3)]);

crates/text/src/breaking.rs

@@ -260,15 +260,12 @@ pub(crate) struct Tab {
     align: TabAlign,
 }
 
-/// The paragraph's tab stops in position order (a stop at no finite position is left out), so
-/// [`tab_advance`] finds the next one by binary search instead of a scan per tab.
 pub(crate) fn tabs_of(props: &ParaProps) -> Vec<Tab> {
-    let mut tabs: Vec<Tab> = props
+    props
         .tabs
         .as_ref()
         .map(|t| {
             t.iter()
-                .filter(|s| s.pos.is_finite())
                 .map(|s| Tab {
                     pos: s.pos,
                     align: match s.align.as_str() {
@@ -280,9 +277,7 @@ pub(crate) fn tabs_of(props: &ParaProps) -> Vec<Tab> {
                 })
                 .collect()
         })
-        .unwrap_or_default();
-    tabs.sort_by(|a, b| a.pos.total_cmp(&b.pos));
-    tabs
+        .unwrap_or_default()
 }
 
 /// Width of the text after the tab at cell `i` up to the next tab or line break, and the width of
@@ -306,15 +301,16 @@ pub(crate) fn tab_segment(cells: &[Cell], i: usize) -> (f64, f64) {
 /// (`seg`: its width, and its width before the decimal point) as the stop aligns it but never
 /// moving back, as PowerPoint does; past the last stop, to the next default stop.
 pub(crate) fn tab_advance(x: f64, stops: &[Tab], default_tab: f64, seg: (f64, f64)) -> f64 {
-    // `stops` is in position order (`tabs_of`): the next stop is the first past x.
-    if let Some(s) = stops.get(stops.partition_point(|s| s.pos <= x + 0.5)) {
-        let to = s.pos - x;
-        return match s.align {
-            TabAlign::Left => to,
-            TabAlign::Right => (to - seg.0).max(0.0),
-            TabAlign::Center => (to - seg.0 / 2.0).max(0.0),
-            TabAlign::Decimal => (to - seg.1).max(0.0),
-        };
+    for s in stops {
+        if s.pos > x + 0.5 {
+            let to = s.pos - x;
+            return match s.align {
+                TabAlign::Left => to,
+                TabAlign::Right => (to - seg.0).max(0.0),
+                TabAlign::Center => (to - seg.0 / 2.0).max(0.0),
+                TabAlign::Decimal => (to - seg.1).max(0.0),
+            };
+        }
     }
     let d = if default_tab > 1.0 { default_tab } else { 72.0 };
     let next = ((x / d).floor() + 1.0) * d;

crates/text/src/tests.rs

@@ -1416,16 +1416,6 @@ fn tab_stops_align_the_text_after_them() {
     assert!((l.lines[0].edges[4].0 - x0(&l) - 72.0).abs() < 0.01);
 }
 
-#[test]
-fn many_tabs_over_many_stops_lay_out_by_position() {
-    // 20,000 stops given out of order, and 2,000 tabs: each tab finds the next stop by position.
-    let mut stops: Vec<(f64, &str)> = (1..=20_000).rev().map(|k| (k as f64 * 0.05 + 30.0, "l")).collect();
-    stops.push((f64::NAN, "l"));
-    let text = "a\t".repeat(2_000);
-    let l = tabbed(&text, &stops, 1.0e6);
-    assert!((l.lines[0].edges[2].0 - l.inner.x0 - 30.05).abs() < 0.01, "{:?}", &l.lines[0].edges[..3]);
-}
-
 #[test]
 fn a_tab_past_the_end_moves_to_the_next_line() {
     // PowerPoint: "abcdefghij\tk\tl\tm…" in a narrow box puts the tab that doesn't fit on the next