merge main into fix/sec-xlsx-sheet-rels

Co-authored-by: Brandon Thomas <echelon@gmail.com>

crates/doc/src/edit.rs

@@ -228,6 +228,11 @@ fn block_cost(b: &Block) -> (usize, bool) {
             .saturating_add(p.objects.len().saturating_mul(std::mem::size_of::<InlineObject>()));
         let objects = p.objects.iter().fold(0usize, |n, o| n.saturating_add(object_cost(o)));
         cost = cost.saturating_add(p.text.len()).saturating_add(items).saturating_add(objects);
+        // The formatting a clone copies too: style ids, font names and the like in the runs,
+        // the mark and the paragraph's properties.
+        let runs = p.runs.iter().filter(|r| !r.props.is_empty()).fold(0usize, |n, r| n.saturating_add(serialized_len(&r.props)));
+        let props = serialized_len(&p.props).saturating_add(serialized_len(&p.mark)).saturating_add(p.section.as_ref().map_or(0, serialized_len));
+        cost = cost.saturating_add(runs).saturating_add(props);
         boxes |= box_ids(p).next().is_some();
     });
     (cost, boxes)

crates/doc/src/edit/tests.rs

@@ -415,6 +415,24 @@ fn pasted_box_copies_are_capped_in_bytes() {
     assert_eq!(got.iter().flatten().count(), added);
 }
 
+#[test]
+fn pasted_box_copies_count_the_formatting_they_copy() {
+    // A story holding a text box and a run whose font name is 1 MiB: each copy clones the
+    // formatting too, so 64 copies used to copy 64 MiB of it past the 32 MiB cap.
+    let props = CharProps { font: Some("f".repeat(1 << 20)), ..CharProps::default() };
+    let mut p = Paragraph::with_text("x", props);
+    p.insert_object(0, box_shape(Some(999)), &CharProps::default()).unwrap();
+    let f = fan_out(vec![para_block(p)], 64);
+    let mut d = doc(&["x"]);
+    let before = d.parts.len();
+    d.insert_fragment(&Pos::body(0, 1), &f).unwrap();
+    let added = d.parts.len() - before;
+    let font = |p: &Paragraph| p.runs.iter().map(|r| r.props.font.as_ref().map_or(0, String::len)).sum::<usize>();
+    let copied: usize = d.parts.values().flat_map(|p| p.blocks.iter()).map(|b| if let Block::Para(p) = &**b { font(p) } else { 0 }).sum();
+    assert!((1..64).contains(&added), "{added}");
+    assert!(copied <= MAX_PASTED_BOX_BYTES, "{copied}");
+}
+
 #[test]
 fn pasted_box_copies_count_the_objects_they_copy() {
     // #3614 review: a story holding a text box and a 1 MiB kept-for-round-trip object costs

crates/docbin/src/lib.rs

@@ -364,6 +364,11 @@ pub fn read_with_password(bytes: &[u8], password: Option<&str>) -> Result<Docume
     // Sections: each section's properties attach to the paragraph that ends it (its story of
     // header/footer parts included); the section reaching the end of the text is the final one.
     let mut paras = walk(&ctx, 0, fib.ccp.text, &mut pics);
+    // The first paragraph ending at each CP, found once rather than by a scan per section.
+    let mut ending: std::collections::HashMap<u32, usize> = std::collections::HashMap::new();
+    for (i, p) in paras.iter().enumerate() {
+        ending.entry(p.end_cp).or_insert(i);
+    }
     let last = sects.last().map(|s| s.props.clone());
     for (si, sec) in sects.iter().enumerate() {
         let mut props = sec.props.clone();
@@ -374,11 +379,8 @@ pub fn read_with_password(bytes: &[u8], password: Option<&str>) -> Result<Docume
         if is_final {
             continue; // handled below through `last`
         }
-        for p in paras.iter_mut() {
-            if p.end_cp == sec.end_cp {
-                p.para.section = Some(Box::new(props));
-                break;
-            }
+        if let Some(p) = ending.get(&sec.end_cp).and_then(|&i| paras.get_mut(i)) {
+            p.para.section = Some(Box::new(props));
         }
     }
     if let Some(mut l) = last {

crates/docbin/src/table.rs

@@ -101,6 +101,12 @@ impl RowInfo {
         self.widths.iter().rfind(|(k, _)| *k == i).map(|(_, w)| *w)
     }
 
+    /// How many per-cell overrides the row keeps, for tests.
+    #[cfg(test)]
+    pub(crate) fn overrides(&self) -> usize {
+        self.vmerge.len() + self.shading.len() + self.widths.len() + self.width_pcts.len() + self.valign.len() + self.merges.len()
+    }
+
     /// The width percentage cell `i` ends up with, for tests.
     #[cfg(test)]
     pub(crate) fn width_pct_of(&self, i: u8) -> Option<f32> {
@@ -108,6 +114,15 @@ impl RowInfo {
     }
 }
 
+/// Set cell `c`'s override to `v`, replacing an earlier one: one slot per cell, however often
+/// a PAPX repeats the sprm, so a shared PAPX can't pile up copies on every paragraph mark.
+fn set<T>(slots: &mut Vec<(u8, T)>, c: u8, v: T) {
+    match slots.iter_mut().find(|(k, _)| *k == c) {
+        Some(slot) => slot.1 = v,
+        None => slots.push((c, v)),
+    }
+}
+
 pub(crate) fn decode(papx: &[u8]) -> RowInfo {
     let mut r = RowInfo::default();
     let mut gap_half: Option<i16> = None;
@@ -144,8 +159,10 @@ pub(crate) fn decode(papx: &[u8]) -> RowInfo {
             T_DXA_GAP_HALF => gap_half = s16(&prl),
             T_TABLE_BORDERS_80 => r.borders = table_borders(prl.operand),
             T_MERGE => {
+                // Rows apply only the first MAX_COLS merges.
                 if let [a, b, ..] = prl.operand
                     && b > a
+                    && r.merges.len() < MAX_COLS
                 {
                     r.merges.push((*a, *b));
                 }
@@ -158,7 +175,8 @@ pub(crate) fn decode(papx: &[u8]) -> RowInfo {
                         1 => VMerge::Continue,
                         _ => VMerge::None,
                     };
-                    if m != VMerge::None {
+                    // The first override for a cell wins.
+                    if m != VMerge::None && !r.vmerge.iter().any(|(k, _)| k == itc) {
                         r.vmerge.push((*itc, m));
                     }
                 }
@@ -168,7 +186,7 @@ pub(crate) fn decode(papx: &[u8]) -> RowInfo {
                     && let [a, b, ..] = prl.operand.get(1..3).unwrap_or(&[])
                 {
                     for c in *a..(*b).min(MAX_COLS as u8) {
-                        r.shading.push((c, Some(rgb)));
+                        set(&mut r.shading, c, Some(rgb));
                     }
                 }
             }
@@ -176,7 +194,7 @@ pub(crate) fn decode(papx: &[u8]) -> RowInfo {
                 let cells = prl.operand.get(1..).unwrap_or(&[]);
                 for (i, b) in cells.as_chunks::<2>().0.iter().take(MAX_COLS).enumerate() {
                     if let Some(rgb) = shd80_rgb(b) {
-                        r.shading.push((i as u8, Some(rgb)));
+                        set(&mut r.shading, i as u8, Some(rgb));
                     }
                 }
             }
@@ -196,7 +214,7 @@ pub(crate) fn decode(papx: &[u8]) -> RowInfo {
                     if raw && b.get(8..10) == Some(&[0xFF, 0xFF]) {
                         continue;
                     }
-                    r.shading.push(((first + i) as u8, shd_rgb(b)));
+                    set(&mut r.shading, (first + i) as u8, shd_rgb(b));
                 }
             }
             T_CELL_WIDTH => {
@@ -207,12 +225,12 @@ pub(crate) fn decode(papx: &[u8]) -> RowInfo {
                     if *fts == 3 {
                         let w = (i16::from_le_bytes([*w0, *w1]) as f32 / 20.0).clamp(0.0, 1584.0);
                         for c in *a..(*b).min(MAX_COLS as u8) {
-                            r.widths.push((c, w));
+                            set(&mut r.widths, c, w);
                         }
                     } else if *fts == 2 {
                         let pct = (u16::from_le_bytes([*w0, *w1]) as f32 / 50.0).clamp(0.0, 100.0);
                         for c in *a..(*b).min(MAX_COLS as u8) {
-                            r.width_pcts.push((c, pct));
+                            set(&mut r.width_pcts, c, pct);
                         }
                     }
                 }
@@ -224,8 +242,8 @@ pub(crate) fn decode(papx: &[u8]) -> RowInfo {
                         2 => VAlign::Bottom,
                         _ => VAlign::Top,
                     };
-                    for c in *a..*b {
-                        r.valign.push((c, v));
+                    for c in *a..(*b).min(MAX_COLS as u8) {
+                        set(&mut r.valign, c, v);
                     }
                 }
             }

crates/docbin/src/tests.rs

@@ -1018,6 +1018,32 @@ fn two_sections_box_the_first() {
     assert!(!doc.last_section.title_page);
 }
 
+#[test]
+fn sections_ending_off_a_paragraph_mark_attach_nowhere() {
+    // Hostile section ends that miss every paragraph mark are skipped; the one that ends a
+    // paragraph still boxes it. Paragraphs are found by their end, not scanned per section.
+    let mut sections: Vec<(u32, Vec<u8>)> = (1..6).map(|cp| (cp, Vec::new())).collect();
+    sections.push((6, grpprl(&[(0x300A, &[0x01])])));
+    sections.push((12, Vec::new()));
+    let spec = StructSpec {
+        text: "first\rsecond\r",
+        header_stories: vec![],
+        sections,
+        chpx_runs: vec![(0, Vec::new())],
+        papx_entries: vec![(0, 0, Vec::new()), (6, 0, Vec::new())],
+        plf_lst: Vec::new(),
+        plf_lfo: Vec::new(),
+        note_stories: vec![],
+        endnote_stories: vec![],
+        extra_pairs: Vec::new(),
+        data_stream: Vec::new(),
+    };
+    let doc = read(&struct_doc(&spec)).expect("opens");
+    let paras: Vec<_> = doc.body.iter().filter_map(|b| b.as_para()).collect();
+    assert!(paras.first().and_then(|p| p.section.as_ref()).expect("first paragraph boxed").title_page);
+    assert_eq!(paras.iter().filter(|p| p.section.is_some()).count(), 1, "the missing ends attach nowhere");
+}
+
 #[test]
 fn header_story_becomes_part() {
     let spec = StructSpec {
@@ -2375,6 +2401,23 @@ fn second_table_gets_its_own_grid() {
     assert_eq!(tables[1].props.indent, None, "indent reset");
 }
 
+#[test]
+fn repeated_cell_sprms_keep_one_override_per_cell() {
+    // A PAPX repeating cell-range sprms (shared by every paragraph mark that names it) keeps one
+    // slot per cell, the last value winning, instead of a copy per repetition.
+    let mut sprms = Vec::new();
+    for w in 0..200u16 {
+        let [w0, w1] = (w * 20).to_le_bytes();
+        sprms.push(sprm_cb(0xD635, &[0, 63, 3, w0, w1]));
+        sprms.push(sprm_cb(0xD62C, &[0, 255, 1]));
+        sprms.push([0x24, 0x56, 0, 2].to_vec());
+    }
+    let row = crate::table::decode(&sprms.concat());
+    assert_eq!(row.width_of(0), Some(199.0), "the last width wins");
+    assert_eq!(row.width_of(62), Some(199.0));
+    assert!(row.overrides() <= 63 + 255 + 63, "{}", row.overrides());
+}
+
 #[test]
 fn sprm_t_cell_width_twips_and_percentage() {
     // [MS-DOC] §2.9.290 sprmTCellWidth (0xD635):

crates/formats/src/sheet.rs

@@ -427,6 +427,27 @@ mod tests {
 
     const RELS: &str = r#"<Relationships xmlns="http://schemas.openxmlformats.org/package/2006/relationships"><Relationship Id="rId1" Type="http://schemas.openxmlformats.org/officeDocument/2006/relationships/officeDocument" Target="xl/workbook.xml"/></Relationships>"#;
 
+    #[test]
+    fn workbook_sheets_find_their_relationships_by_index() {
+        // Every sheet searched every relationship; 4,096 sheets over 20,000 relationships.
+        let sheets: String = (0..MAX_SHEETS).map(|i| format!(r#"<sheet name="S{i}" sheetId="{i}" r:id="rId{i}"/>"#)).collect();
+        let wb = format!(
+            r#"<workbook xmlns="http://schemas.openxmlformats.org/spreadsheetml/2006/main" xmlns:r="http://schemas.openxmlformats.org/officeDocument/2006/relationships"><sheets>{sheets}</sheets></workbook>"#
+        );
+        let mut rels = String::from(r#"<Relationships xmlns="http://schemas.openxmlformats.org/package/2006/relationships">"#);
+        // A chart sheet sharing a worksheet's id doesn't hide it.
+        rels.push_str(r#"<Relationship Id="rId0" Type="http://schemas.openxmlformats.org/officeDocument/2006/relationships/chartsheet" Target="chartsheets/c.xml"/>"#);
+        for i in 0..20_000 {
+            rels.push_str(&format!(
+                r#"<Relationship Id="rId{i}" Type="http://schemas.openxmlformats.org/officeDocument/2006/relationships/worksheet" Target="worksheets/sheet{i}.xml"/>"#
+            ));
+        }
+        rels.push_str("</Relationships>");
+        let names = sheet_names(&zip(&[("_rels/.rels", RELS), ("xl/workbook.xml", &wb), ("xl/_rels/workbook.xml.rels", &rels)])).unwrap();
+        assert_eq!(names.len(), MAX_SHEETS);
+        assert_eq!(names.first().map(String::as_str), Some("S0"));
+    }
+
     fn xlsx(sheet1: &str) -> Vec<u8> {
         let wb = r#"<workbook xmlns="http://schemas.openxmlformats.org/spreadsheetml/2006/main" xmlns:r="http://schemas.openxmlformats.org/officeDocument/2006/relationships"><workbookPr/><sheets><sheet name="People" sheetId="1" r:id="rId1"/><sheet name="Chart" sheetId="2" r:id="rId9"/><sheet name="Notes" sheetId="3" r:id="rId2"/></sheets></workbook>"#;
         let wb_rels = r#"<Relationships xmlns="http://schemas.openxmlformats.org/package/2006/relationships"><Relationship Id="rId1" Type="http://schemas.openxmlformats.org/officeDocument/2006/relationships/worksheet" Target="worksheets/sheet1.xml"/><Relationship Id="rId2" Type="http://schemas.openxmlformats.org/officeDocument/2006/relationships/worksheet" Target="/xl/worksheets/sheet2.xml"/><Relationship Id="rId9" Type="http://schemas.openxmlformats.org/officeDocument/2006/relationships/chartsheet" Target="chartsheets/sheet1.xml"/><Relationship Id="rId3" Type="http://schemas.openxmlformats.org/officeDocument/2006/relationships/sharedStrings" Target="sharedStrings.xml"/><Relationship Id="rId4" Type="http://schemas.openxmlformats.org/officeDocument/2006/relationships/styles" Target="styles.xml"/></Relationships>"#;

crates/formats/src/sheet/xlsx.rs

@@ -83,14 +83,13 @@ fn workbook(pkg: &mut Package<'_>) -> Result<Workbook, String> {
             }
         }
     });
-    let sheets = listed
-        .into_iter()
-        .filter_map(|(name, id)| {
-            // Worksheets only: chart and dialog sheets hold no cells.
-            let r = rels.iter().find(|r| r.id == id && r.kind.ends_with("/worksheet"))?;
-            Some(SheetRef { name, path: r.target.clone() })
-        })
-        .collect();
+    // Worksheets only: chart and dialog sheets hold no cells. Indexed by id once (the first
+    // relationship with an id wins), not searched for every sheet.
+    let mut worksheets: HashMap<&str, &str> = HashMap::new();
+    for r in rels.iter().filter(|r| r.kind.ends_with("/worksheet")) {
+        worksheets.entry(r.id.as_str()).or_insert(r.target.as_str());
+    }
+    let sheets = listed.into_iter().filter_map(|(name, id)| Some(SheetRef { name, path: worksheets.get(id.as_str())?.to_string() })).collect();
     let part = |suffix: &str| rels.iter().find(|r| r.kind.ends_with(suffix)).map(|r| r.target.clone());
     Ok(Workbook { sheets, date1904, shared: part("/sharedStrings"), styles: part("/styles") })
 }