address review: bound merge expansion work; measure a normalized copy of an unnormalized table

crates/engine/src/cmd.rs

@@ -433,6 +433,17 @@ pub(crate) fn shape_of(s: &Session, id: ShapeId) -> Result<deckcraft_model::Shap
 pub fn xfrm_of(doc: &deckcraft_model::Presentation, sel: &crate::Selection, shape: &deckcraft_model::Shape) -> Xfrm {
     let mut x = shape.xfrm.unwrap_or_else(|| ctx_xfrm(doc, sel, shape));
     if let deckcraft_model::ShapeKind::Table(t) = &shape.kind {
+        // A loaded table may not be normalized yet: measure the bounded grid an edit will
+        // leave, not every cell the file stored.
+        let normalized;
+        let t = if t.is_normalized() {
+            t
+        } else {
+            let mut n = t.clone();
+            n.normalize();
+            normalized = n;
+            &normalized
+        };
         let drawn: f64 = table_drawn_heights(doc, sel, t).iter().sum();
         if drawn.is_finite() && drawn > x.h {
             x.h = drawn;

crates/engine/src/cmd/table.rs

@@ -285,6 +285,8 @@ fn with_table(s: &mut Session, p: &Value, cmd: &str, f: impl Fn(&mut Table) -> R
     };
     let r = edit_shapes(s, &json!({"id": id}), cmd, |sh| match &mut sh.kind {
         ShapeKind::Table(t) => {
+            // Edits walk the grid: bound it first (a loaded table need not be normalized yet).
+            t.normalize();
             f(t)?;
             t.normalize();
             let (w, h) = (t.width(), t.height());

crates/model/src/table.rs

@@ -77,6 +77,12 @@ impl Default for Table {
     }
 }
 
+/// Cells a table may hold after [`Table::normalize`] (PowerPoint's own limit is 75 x 75).
+pub const MAX_CELLS: usize = 100_000;
+/// Cell visits [`Table::merge`] may spend growing its rectangle over existing merges: a few
+/// passes over the largest grid, where a real table needs one or two.
+const MAX_MERGE_WORK: usize = 16 * MAX_CELLS;
+
 impl Table {
     pub fn new(rows: usize, cols: usize, width: f64, row_height: f64) -> Self {
         let rows = rows.clamp(1, 1000);
@@ -164,8 +170,12 @@ impl Table {
         true
     }
     /// The merged areas: every uncovered cell spanning more than one cell, clipped to the grid.
+    /// Merges of a well-formed table do not overlap, so together they cover at most the grid; a
+    /// file's overlapping spans past that are dropped, so rebuilding them cannot revisit cells
+    /// without bound.
     fn merges(&self) -> Vec<Merge> {
         let (nr, nc) = (self.rows.len(), self.cols.len());
+        let mut area = nr.saturating_mul(nc);
         let mut out = vec![];
         for (r, row) in self.rows.iter().enumerate() {
             for (c, cell) in row.cells.iter().enumerate().take(nc) {
@@ -174,7 +184,10 @@ impl Table {
                 }
                 let rs = (cell.row_span.max(1) as usize).min(nr - r);
                 let gs = (cell.grid_span.max(1) as usize).min(nc - c);
-                if rs > 1 || gs > 1 {
+                if (rs > 1 || gs > 1)
+                    && let Some(left) = area.checked_sub(rs.saturating_mul(gs))
+                {
+                    area = left;
                     out.push(Merge { r, c, rs, gs });
                 }
             }
@@ -227,9 +240,17 @@ impl Table {
         if r1 >= self.rows.len() || c1 >= self.cols.len() || (r0 == r1 && c0 == c1) {
             return false;
         }
-        // Grow the rectangle until no existing merge sticks out of it.
+        // Grow the rectangle until no existing merge sticks out of it. Each pass reads the whole
+        // grid and may grow it by one row, so the passes are charged against
+        // [`MAX_MERGE_WORK`]: past it the merge is refused, before anything changed.
         let (mut r0, mut c0, mut r1, mut c1) = (r0, c0, r1, c1);
+        let pass = self.rows.len().saturating_mul(self.cols.len()).max(1);
+        let mut work = 0usize;
         loop {
+            work = work.saturating_add(pass);
+            if work > MAX_MERGE_WORK {
+                return false;
+            }
             let before = (r0, c0, r1, c1);
             for (r, row) in self.rows.iter().enumerate() {
                 for (c, cell) in row.cells.iter().enumerate().take(self.cols.len()) {
@@ -283,21 +304,31 @@ impl Table {
             return false;
         }
         // Spans come from the file and may reach past the table; only walk the cells that exist.
-        for rr in r..r.saturating_add(rs).min(self.rows.len()) {
-            for cc in c..c.saturating_add(gs).min(self.cols.len()) {
-                if let Some(x) = self.cell_mut(rr, cc) {
-                    x.h_merge = false;
-                    x.v_merge = false;
-                    x.grid_span = 1;
-                    x.row_span = 1;
-                }
+        let end = r.saturating_add(rs).min(self.rows.len());
+        let gs = gs.min(self.cols.len().saturating_sub(c));
+        for row in self.rows.get_mut(r..end).unwrap_or_default() {
+            for x in row.cells.iter_mut().skip(c).take(gs) {
+                x.h_merge = false;
+                x.v_merge = false;
+                x.grid_span = 1;
+                x.row_span = 1;
             }
         }
         true
     }
-    /// Make every row have exactly `cols.len()` cells (repair after loading).
-    pub fn normalize(&mut self) {
+    /// Whether the grid is as [`Table::normalize`] leaves it: within [`MAX_CELLS`], every row
+    /// exactly `cols.len()` cells wide.
+    pub fn is_normalized(&self) -> bool {
         let n = self.cols.len();
+        n <= MAX_CELLS && self.rows.len() <= (MAX_CELLS / n.max(1)).max(1) && self.rows.iter().all(|r| r.cells.len() == n)
+    }
+    /// Make every row have exactly `cols.len()` cells (repair after loading). A grid over
+    /// [`MAX_CELLS`] loses its last rows (and columns) first, so a file naming many rows and many
+    /// columns but few cells cannot make this allocate their product.
+    pub fn normalize(&mut self) {
+        self.cols.truncate(MAX_CELLS);
+        let n = self.cols.len();
+        self.rows.truncate((MAX_CELLS / n.max(1)).max(1));
         for r in &mut self.rows {
             r.cells.resize_with(n, || Cell::new(""));
             for c in &mut r.cells {
@@ -513,6 +544,61 @@ mod tests {
         }
     }
 
+    /// Each cell spans two rows, uncovered: merging the last two rows would grow the rectangle a
+    /// row per pass over the whole grid, 10,000 passes. The merge is refused at its work bound
+    /// instead, leaving the table as it was; a small merge still works.
+    #[test]
+    fn merge_expansion_stops_at_its_work_bound() {
+        let mut t = Table::new(10_000, 10, 400.0, 30.0);
+        for row in &mut t.rows {
+            for c in &mut row.cells {
+                c.row_span = 2;
+            }
+        }
+        let before = t.clone();
+        assert!(!t.merge(9_998, 0, 9_999, 9));
+        assert_eq!(t, before);
+        let mut small = Table::new(4, 4, 400.0, 30.0);
+        assert!(small.merge(0, 0, 1, 1));
+        assert!(small.is_normalized() && !Table { cols: vec![1.0; 3], rows: vec![Row::default(); 2], ..Default::default() }.is_normalized());
+    }
+
+    #[test]
+    fn normalize_caps_a_sparse_grid_at_max_cells() {
+        // 1,000 columns and 1,000 empty rows would be a million cells.
+        let mut t = Table { cols: vec![10.0; 1000], rows: vec![Row::default(); 1000], ..Default::default() };
+        t.normalize();
+        assert_eq!(t.cols.len(), 1000);
+        assert_eq!(t.rows.len(), MAX_CELLS / 1000);
+        assert!(t.rows.iter().all(|r| r.cells.len() == 1000));
+        // Columns alone past the cap keep one row of MAX_CELLS cells.
+        let mut t = Table { cols: vec![1.0; MAX_CELLS + 5], rows: vec![Row::default(); 3], ..Default::default() };
+        t.normalize();
+        assert_eq!((t.cols.len(), t.rows.len()), (MAX_CELLS, 1));
+        // A normal table is untouched.
+        let mut t = Table::new(4, 4, 400.0, 30.0);
+        t.normalize();
+        assert_eq!((t.n_rows(), t.n_cols()), (4, 4));
+    }
+
+    #[test]
+    fn overlapping_file_spans_rebuild_in_bounded_work() {
+        // Every cell an uncovered anchor spanning to the far corner: their areas add up to about
+        // n^4 / 4, but only what fits the grid is kept, so an edit's rebuild stays near n^2.
+        let n = 200;
+        let mut t = Table::new(n, n, 400.0, 30.0);
+        for row in &mut t.rows {
+            for c in &mut row.cells {
+                c.grid_span = u32::MAX;
+                c.row_span = u32::MAX;
+            }
+        }
+        assert_eq!(t.merges().len(), 1, "the first anchor already covers the whole grid");
+        t.insert_row(n);
+        assert_eq!(t.n_rows(), n + 1);
+        assert!(t.split(0, 0));
+    }
+
     fn merged() -> Table {
         // 4x4 with a 2x2 merge at (1,1) holding "M".
         let mut t = Table::new(4, 4, 400.0, 30.0);

crates/pptx/src/read.rs

@@ -663,55 +663,52 @@ fn read_slides(
     let pkg = imp.pkg;
     let fallback_layout = p.masters.first().and_then(|m| m.layouts.first()).map(|l| l.id).unwrap_or_default();
     let mut file_slide_ids: HashMap<u32, SlideId> = HashMap::new();
-    // A notes or comments part belongs to one slide; one shared by many must not be read (and
-    // copied) once per slide that names it.
-    let mut owned_parts: HashSet<String> = HashSet::new();
+    let mut notes_by_target: HashMap<String, TextBody> = HashMap::new();
     for (file_id, path, id) in slide_ids {
         let Some(doc) = docs.get(&opc::norm(path)) else { continue };
         let part = Part::new(pkg, path, doc);
         let layout = part.rels.first_of("slideLayout").and_then(|r| layout_by_part.get(&opc::norm(&r.target)).copied()).unwrap_or(fallback_layout);
         let mut slide = read_slide(imp, &part, doc, *id, layout);
-        if let Some(notes) = slide_notes(imp, &part, &mut owned_parts) {
+        if let Some(notes) = slide_notes(imp, &part, &mut notes_by_target) {
             slide.notes = notes;
         }
-        read_slide_comments(pkg, pres_part, &part, &mut slide, &mut owned_parts);
+        read_slide_comments(pkg, pres_part, &part, &mut slide);
         file_slide_ids.insert(*file_id, *id);
         p.slides.push(Arc::new(slide));
     }
     file_slide_ids
 }
 
-/// The slide's notes text. A notes part is the notes of the first slide that names it.
-fn slide_notes(imp: &mut Imp, part: &Part, owned: &mut HashSet<String>) -> Option<TextBody> {
+/// The slide's notes text, read once per notes part.
+fn slide_notes(imp: &mut Imp, part: &Part, cache: &mut HashMap<String, TextBody>) -> Option<TextBody> {
     let n = part.rels.first_of("notesSlide")?;
-    if !owned.insert(opc::norm(&n.target)) {
-        log::warn!("pptx: notes part {} is named by more than one slide; kept on the first", n.target);
-        return None;
+    let key = opc::norm(&n.target);
+    if let Some(cached) = cache.get(&key) {
+        return Some(cached.clone());
     }
     let pkg = imp.pkg;
     let nd = load(pkg, &n.target)?;
     let np = Part::new(pkg, &n.target, &nd);
-    Some(read_notes(imp, &np, &nd.root))
+    let notes = read_notes(imp, &np, &nd.root);
+    cache.insert(key, notes.clone());
+    Some(notes)
 }
 
 /// Comments. A modern part and the legacy part can describe the same threads (PowerPoint
 /// writes both): the modern one wins, its flattened legacy copy is skipped.
-/// Each comments part is read once, for the first slide that names it.
-fn read_slide_comments(pkg: &Package, pres_part: &Part, part: &Part, slide: &mut Slide, owned: &mut HashSet<String>) {
-    let mut parts: Vec<(Doc, bool, bool)> = vec![];
+fn read_slide_comments(pkg: &Package, pres_part: &Part, part: &Part, slide: &mut Slide) {
+    let mut parts: Vec<(Doc, bool)> = vec![];
     for c in part.rels.all_of("comments") {
-        // An already-owned part is not re-read, but its kind still decides modern precedence.
-        let fresh = owned.insert(opc::norm(&c.target));
         if let Some(cd) = pkg.xml(&c.target) {
             // The content type names the modern part; a package that types it only through a
             // Default entry instead of an Override is still modern when its root is p188.
             let modern = pkg.content_type(&c.target).as_deref() == Some(crate::write::CT_COMMENTS_MODERN) || cd.root.prefix() == "p188";
-            parts.push((cd, modern, fresh));
+            parts.push((cd, modern));
         }
     }
-    let has_modern = parts.iter().any(|(_, m, _)| *m);
-    for (cd, modern, fresh) in parts {
-        if !fresh || (has_modern && !modern) {
+    let has_modern = parts.iter().any(|(_, m)| *m);
+    for (cd, modern) in parts {
+        if has_modern && !modern {
             continue;
         }
         slide.comments.extend(read_comments(pkg, pres_part, &cd.root, modern));

crates/pptx/tests/it/comments.rs

@@ -146,33 +146,6 @@ fn comments_on_several_slides_round_trip() {
     assert_eq!(q.slides[2].comments[0].text, "Slide three");
 }
 
-/// A slide that names a modern part another slide already owns, plus its own legacy part, must
-/// not import the legacy copy: modern precedence holds even when the modern part is not re-read.
-#[test]
-fn owned_modern_part_still_suppresses_later_legacy() {
-    let mut p = deck();
-    let layout = p.slides[0].layout;
-    let s2 = defaults::new_slide(&mut p, layout).expect("slide");
-    p.slides.push(Arc::new(s2));
-    Arc::make_mut(&mut p.slides[1]).comments = vec![Comment { author: "Cara".into(), text: "Slide two".into(), ..Default::default() }];
-    let bytes = deckcraft_pptx::export(&p).expect("export");
-    let rels2 = part(&bytes, "ppt/slides/_rels/slide2.xml.rels").replace("modernComment2.xml", "modernComment1.xml");
-    let mut z = zip::ZipArchive::new(std::io::Cursor::new(&bytes)).expect("zip");
-    let mut out = zip::ZipWriter::new(std::io::Cursor::new(Vec::new()));
-    for i in 0..z.len() {
-        let mut f = z.by_index(i).expect("entry");
-        out.start_file(f.name(), zip::write::SimpleFileOptions::default()).expect("start");
-        if f.name() == "ppt/slides/_rels/slide2.xml.rels" {
-            std::io::Write::write_all(&mut out, rels2.as_bytes()).expect("write");
-        } else {
-            std::io::copy(&mut f, &mut out).expect("copy");
-        }
-    }
-    let q = deckcraft_pptx::import(&out.finish().expect("finish").into_inner()).expect("import");
-    assert_eq!(q.slides[0].comments.len(), 2);
-    assert!(q.slides[1].comments.is_empty(), "{:?}", q.slides[1].comments);
-}
-
 /// A legacy-only package (what older tools read and write) still imports: 1/8 pt positions,
 /// flattened replies.
 #[test]

crates/pptx/tests/it/malformed.rs

@@ -287,34 +287,3 @@ fn unreadable_slide_is_reported() {
     assert_eq!(lost, vec!["ppt/slides/slide2.xml".to_string()]);
     assert_eq!(deckcraft_pptx::import(&broken).expect("import").slides.len(), 1);
 }
-
-/// Many slides naming one notes part: it is read for the first slide only, not copied onto every
-/// slide that names it.
-#[test]
-fn a_shared_notes_part_is_read_once() {
-    use std::sync::Arc;
-    let mut p = defaults::new_presentation(None);
-    let layout = p.slides[0].layout;
-    for _ in 0..3 {
-        let s = defaults::new_slide(&mut p, layout).expect("slide");
-        p.slides.push(Arc::new(s));
-    }
-    for (i, s) in p.slides.iter_mut().enumerate() {
-        Arc::make_mut(s).notes = deckcraft_model::text::TextBody::from_text(&format!("notes {i}"));
-    }
-    let mut es = entries(&deckcraft_pptx::export(&p).expect("export"));
-    for (n, d) in es.iter_mut() {
-        if n.starts_with("ppt/slides/_rels/") {
-            let x = String::from_utf8(d.clone()).expect("utf8");
-            let x = x
-                .replace("notesSlide2.xml", "notesSlide1.xml")
-                .replace("notesSlide3.xml", "notesSlide1.xml")
-                .replace("notesSlide4.xml", "notesSlide1.xml");
-            *d = x.into_bytes();
-        }
-    }
-    let q = deckcraft_pptx::import(&rezip(&es)).expect("import");
-    assert_eq!(q.slides.len(), 4);
-    assert_eq!(q.slides[0].notes.text(), "notes 0");
-    assert!(q.slides[1..].iter().all(|s| s.notes.text().is_empty()), "a shared notes part is not copied");
-}