xlsx: analyse each kept chart sheet's graph once per save

chart_sheet_usable walked a chart sheet's relationship graph and parsed
its charts for every workbook entry, so many entries naming one shared
graph multiplied the work. The referenced sheet names are now cached by
relationship id.

crates/xlsx/src/passthrough/write.rs

@@ -254,27 +254,37 @@ pub(crate) fn sheet_names_in(formula: &str) -> Vec<String> {
 /// Whether a kept chart sheet can be written back: its chart's series must still refer to sheets
 /// that exist under the same names (the chart is kept as it was, so a series on a deleted or
 /// renamed sheet would be left pointing at nothing), and no worksheet may have taken its name.
-fn chart_sheet_usable(wb: &Workbook, p: &Preserved, s: &PreservedSheet) -> bool {
+///
+/// `refs` caches, by relationship id, the sheet names a chart sheet's graph refers to (`None`
+/// when the relationship is missing): entries sharing one graph are analysed once.
+fn chart_sheet_usable<'p>(wb: &Workbook, p: &'p Preserved, s: &'p PreservedSheet, refs: &mut HashMap<&'p str, Option<Vec<String>>>) -> bool {
     let same = |a: &str, b: &str| a.chars().take(31).collect::<String>().eq_ignore_ascii_case(&b.chars().take(31).collect::<String>());
     if wb.sheets.iter().any(|w| same(&w.name, &s.name)) {
         return false;
     }
-    let Some(root) = p.rels.iter().find(|r| r.id == s.rel_id) else { return false };
-    let parts = reachable(p, root);
-    let mut formulas = vec![];
-    for q in p.parts.iter().filter(|q| parts.contains(&normalize(&q.name)) && q.content_type.contains("chart")) {
-        if let Ok(x) = xml::parse(&q.data) {
-            chart_formulas(&x, &mut formulas);
+    let names = refs.entry(s.rel_id.as_str()).or_insert_with(|| {
+        let root = p.rels.iter().find(|r| r.id == s.rel_id)?;
+        let parts = reachable(p, root);
+        let mut formulas = vec![];
+        for q in p.parts.iter().filter(|q| parts.contains(&normalize(&q.name)) && q.content_type.contains("chart")) {
+            if let Ok(x) = xml::parse(&q.data) {
+                chart_formulas(&x, &mut formulas);
+            }
         }
-    }
-    formulas.iter().flat_map(|f| sheet_names_in(f)).all(|n| wb.sheets.iter().any(|w| same(&w.name, &n)))
+        Some(formulas.iter().flat_map(|f| sheet_names_in(f)).collect())
+    });
+    let Some(names) = names else { return false };
+    names.iter().all(|n| wb.sheets.iter().any(|w| same(&w.name, n)))
 }
 
 /// Writes the workbook's kept parts and relationships. Chart sheets that can't be written back
 /// (see [`chart_sheet_usable`]) are left out with the parts only they reach.
 pub fn write_workbook(wb: &Workbook, wb_rels: &mut Rels, out: &mut Out) -> WorkbookKept {
     let Some(p) = wb.preserved.as_deref() else { return WorkbookKept::default() };
-    let (live, dropped): (Vec<&PreservedSheet>, Vec<&PreservedSheet>) = p.sheets.iter().partition(|s| chart_sheet_usable(wb, p, s));
+    let (live, dropped): (Vec<&PreservedSheet>, Vec<&PreservedSheet>) = {
+        let mut refs = HashMap::new();
+        p.sheets.iter().partition(|s| chart_sheet_usable(wb, p, s, &mut refs))
+    };
     let root_of = |s: &PreservedSheet| p.rels.iter().find(|r| r.id == s.rel_id);
     let dropped_ids: HashSet<&str> = dropped.iter().map(|s| s.rel_id.as_str()).collect();
     // Parts reached only by dropped chart sheets go with them.

crates/xlsx/src/richdata.rs

@@ -142,22 +142,13 @@ pub fn read(cx: &mut Ctx<'_>, workbook_rels: &[Rel]) -> Result<Vec<Option<Arc<Ce
     let Some(image_rel_list) = read_xml(cx, &image_rels_path, "richValueRels")? else { return Ok(vec![]) };
     let image_rels = cx.pkg.rels(&image_rels_path)?;
     let structures = entries(cx, &structures, "s")?;
-    // Each structure's key layout, worked out once: every value would otherwise walk its
-    // structure's keys again. Only local-image structures matter here.
-    let layouts: Vec<Option<Layout>> = structures.iter().map(|s| Layout::of(s)).collect();
     let image_rel_list = entries(cx, &image_rel_list, "rel")?;
-    // Relationships by id, a repeated id recorded as invalid (`None`), so a value's lookup is
-    // one probe rather than a scan of the whole table for duplicates.
-    let mut rels_by_id: HashMap<&str, Option<&Rel>> = HashMap::new();
-    for rel in &image_rels {
-        rels_by_id.entry(rel.id.as_str()).and_modify(|r| *r = None).or_insert(Some(rel));
-    }
     let values = entries(cx, &data, "rv")?;
     let mut pictures = Vec::with_capacity(values.len());
     let mut cache = HashMap::new();
     let mut total = 0usize;
     for value in values {
-        let picture = read_value(cx, value, &layouts, &image_rel_list, &rels_by_id, &mut cache, &mut total)?;
+        let picture = read_value(cx, value, &structures, &image_rel_list, &image_rels, &mut cache, &mut total)?;
         if picture.is_none() {
             cx.warn("some rich values are unsupported or malformed; their scalar fallbacks were retained (cell pictures may be missing)");
         }
@@ -197,56 +188,43 @@ pub fn read(cx: &mut Ctx<'_>, workbook_rels: &[Rel]) -> Result<Vec<Option<Arc<Ce
         .collect())
 }
 
-/// Where a `_localImage` structure keeps the values a picture needs.
-struct Layout {
-    keys: usize,
-    /// Index of the one `_rvRel:LocalImageIdentifier` key of type `i`, if exactly one.
-    image: Option<usize>,
-    /// Index of the one `Text` key of type `s`, if exactly one.
-    text: Option<usize>,
-}
-
-impl Layout {
-    fn of(structure: &El) -> Option<Layout> {
-        if structure.attr("t") != Some("_localImage") {
-            return None;
-        }
-        let keys: Vec<&El> = structure.kids("k").collect();
-        let one = |name: &str, ty: &str| {
-            let mut matches = keys.iter().enumerate().filter(|(_, k)| k.attr("n") == Some(name));
-            let (i, key) = matches.next()?;
-            (matches.next().is_none() && key.attr("t") == Some(ty)).then_some(i)
-        };
-        Some(Layout { keys: keys.len(), image: one("_rvRel:LocalImageIdentifier", "i"), text: one("Text", "s") })
-    }
-}
-
 fn read_value(
     cx: &mut Ctx<'_>,
     value: &El,
-    layouts: &[Option<Layout>],
+    structures: &[&El],
     image_rel_list: &[&El],
-    rels_by_id: &HashMap<&str, Option<&Rel>>,
+    image_rels: &[Rel],
     cache: &mut HashMap<(String, String), Arc<CellPicture>>,
     total: &mut usize,
 ) -> Result<Option<Arc<CellPicture>>, IoError> {
-    let Some(Some(layout)) = value.attr_u32("s").and_then(|n| layouts.get(n as usize)) else { return Ok(None) };
-    let values: Vec<_> = value.kids("v").collect();
-    if layout.keys != values.len() {
+    let Some(structure) = value.attr_u32("s").and_then(|n| structures.get(n as usize)) else { return Ok(None) };
+    if structure.attr("t") != Some("_localImage") {
         return Ok(None);
     }
-    let lookup = |slot: Option<usize>| slot.and_then(|i| values.get(i)).map(|v| v.text.as_str());
-    let Some(rel_id) =
-        lookup(layout.image).and_then(|v| v.trim().parse::<usize>().ok()).and_then(|n| image_rel_list.get(n)).and_then(|rel| rel.attr("id"))
+    let keys: Vec<_> = structure.kids("k").collect();
+    let values: Vec<_> = value.kids("v").collect();
+    if keys.len() != values.len() {
+        return Ok(None);
+    }
+    let lookup = |name: &str, ty: &str| {
+        let mut matches = keys.iter().zip(&values).filter(|(k, _)| k.attr("n") == Some(name));
+        let (key, value) = matches.next()?;
+        (matches.next().is_none() && key.attr("t") == Some(ty)).then_some(value.text.as_str())
+    };
+    let Some(rel_id) = lookup("_rvRel:LocalImageIdentifier", "i")
+        .and_then(|v| v.trim().parse::<usize>().ok())
+        .and_then(|n| image_rel_list.get(n))
+        .and_then(|rel| rel.attr("id"))
     else {
         return Ok(None);
     };
-    let Some(found) = rels_by_id.get(rel_id) else { return Ok(None) };
-    let Some(rel) = found.filter(|rel| rel.kind == "image" && !rel.external) else {
+    let mut matches = image_rels.iter().filter(|rel| rel.id == rel_id);
+    let Some(rel) = matches.next() else { return Ok(None) };
+    if matches.next().is_some() || rel.kind != "image" || rel.external {
         cx.warn("a cell picture has an external or invalid image relationship; kept its scalar fallback");
         return Ok(None);
-    };
-    let alt = lookup(layout.text).unwrap_or("").to_string();
+    }
+    let alt = lookup("Text", "s").unwrap_or("").to_string();
     let key = (normalize(&rel.target), alt.clone());
     if let Some(picture) = cache.get(&key) {
         return Ok(Some(picture.clone()));

crates/xlsx/src/tests/passthrough_tests.rs

@@ -696,6 +696,32 @@ fn chartsheet_package() -> Vec<u8> {
     ])
 }
 
+/// Thousands of chart-sheet entries naming one chart sheet's relationship: its graph is walked
+/// and its charts parsed once when saving, not once per entry.
+#[test]
+fn chart_sheet_entries_sharing_a_graph_are_checked_once() {
+    let bytes = chartsheet_package();
+    let mut z = zip::ZipArchive::new(std::io::Cursor::new(bytes)).unwrap();
+    let mut parts: Vec<(String, Vec<u8>)> = Vec::new();
+    for i in 0..z.len() {
+        let mut f = z.by_index(i).unwrap();
+        let mut data = Vec::new();
+        f.read_to_end(&mut data).unwrap();
+        parts.push((f.name().to_string(), data));
+    }
+    let extra: String = (0..3_000).map(|i| format!(r#"<sheet name="Copy{i}" sheetId="{}" r:id="rId2"/>"#, 100 + i)).collect();
+    for (name, data) in &mut parts {
+        if name == "xl/workbook.xml" {
+            *data = String::from_utf8(data.clone()).unwrap().replace("</sheets>", &format!("{extra}</sheets>")).into_bytes();
+        }
+    }
+    let refs: Vec<(&str, &[u8])> = parts.iter().map(|(n, d)| (n.as_str(), d.as_slice())).collect();
+    let (wb, _) = read_xlsx(&make_zip(&refs)).unwrap();
+    let u = Unpacked::new(&write_xlsx(&wb).unwrap());
+    u.assert_valid();
+    assert!(written_sheets(&u).iter().any(|(n, _)| n == "Chart1"));
+}
+
 /// The sheets of a written workbook: (name, state) in file order.
 fn written_sheets(u: &Unpacked) -> Vec<(String, String)> {
     let wb = xml::parse(u.parts.get("xl/workbook.xml").unwrap()).unwrap();

crates/xlsx/src/tests/richdata_tests.rs

@@ -270,27 +270,3 @@ fn picture_metadata_limits_and_relationship_read_errors_do_not_block_workbooks()
         assert!(report.warnings.iter().any(|w| w.contains("cell-picture data could not be read")), "{:?}", report.warnings);
     }
 }
-
-/// Many values over one wide structure, and a repeated relationship id: the structure's layout
-/// is worked out once and relationships are indexed, so the import is linear in the records;
-/// the repeated id is invalid and keeps the scalar fallback.
-#[test]
-fn wide_structures_and_repeated_relationship_ids_are_resolved_through_indexes() {
-    let mut parts = independent_parts(false);
-    // 200,000 keys in one structure and 50,000 short values that name it: rebuilding the key
-    // list per value would be ten billion steps.
-    let padding = r#"<k n="pad" t="s"/>"#.repeat(200_000);
-    replace(&mut parts, "rich/structures.xml", r#"<k n="CalcOrigin" t="i"/>"#, &format!(r#"<k n="CalcOrigin" t="i"/>{padding}"#));
-    let values = r#"<rv s="1"><v/></rv>"#.repeat(50_000);
-    replace(&mut parts, "rich/values.xml", r#"<rv s="1"><v>green &amp; &lt;image&gt;</v><v>1</v><v>5</v></rv>"#, &values);
-    let (wb, report) = read_xlsx(&zip(&parts)).unwrap();
-    assert!(!wb.sheet(0).unwrap().cell_pictures.contains_key(&at("A1")));
-    assert!(report.warnings.iter().any(|w| w.contains("picture")), "{:?}", report.warnings);
-    // The same id twice makes every reference to it invalid.
-    let mut parts = independent_parts(false);
-    let dup = r#"<Relationship Id="opaqueImageId" Type="http://schemas.openxmlformats.org/officeDocument/2006/relationships/image" Target="../media/original.bin"/>"#;
-    replace(&mut parts, "rich/_rels/images.xml.rels", dup, &dup.repeat(2));
-    let (wb, report) = read_xlsx(&zip(&parts)).unwrap();
-    assert!(!wb.sheet(0).unwrap().cell_pictures.contains_key(&at("A1")));
-    assert!(report.warnings.iter().any(|w| w.contains("invalid image relationship")), "{:?}", report.warnings);
-}