model: cap a table's grid and merge area before edits allocate or walk it

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/metafile/src/cliprect.rs

@@ -11,10 +11,6 @@ use crate::geom::{Op, P};
 /// Line segments per Bézier when a crossing shape is flattened.
 const CURVE_STEPS: usize = 16;
 
-/// Point-against-edge tests one clipped item may cost (all its subpaths together); an item over
-/// it is dropped, as a single polygon over it already was.
-const MAX_CLIP_WORK: usize = 1_000_000;
-
 /// The bounding box `[l, t, r, b]` of the points in `ops` (control points included).
 pub(crate) fn ops_bbox(ops: &[Op]) -> Option<[f64; 4]> {
     let mut b: Option<[f64; 4]> = None;
@@ -104,12 +100,12 @@ fn is_rect(clip: &[P]) -> bool {
 
 /// Sutherland–Hodgman: `poly` cut by convex `clip`.
 pub(crate) fn clip_polygon(poly: &[P], clip: &[P]) -> Vec<P> {
-    if poly.len().saturating_mul(clip.len()) > MAX_CLIP_WORK {
+    if poly.len().saturating_mul(clip.len()) > 1_000_000 {
         return Vec::new();
     }
     let mut poly = poly.to_vec();
     for i in 0..clip.len() {
-        if poly.len().saturating_mul(clip.len() - i) > MAX_CLIP_WORK {
+        if poly.len().saturating_mul(clip.len() - i) > 1_000_000 {
             return Vec::new();
         }
         let (a, b) = (clip[i], clip[(i + 1) % clip.len()]);
@@ -162,9 +158,6 @@ pub(crate) fn clip_raw(raw: Raw, clip: &[P]) -> Vec<Raw> {
                 return Vec::new();
             }
             let subs = flatten(&ops);
-            if too_much_work(&subs, clip) {
-                return Vec::new();
-            }
             let mut out = Vec::new();
             if fill.is_some() {
                 let f = clip_fill(&subs, clip);
@@ -188,11 +181,7 @@ pub(crate) fn clip_raw(raw: Raw, clip: &[P]) -> Vec<Raw> {
             if disjoint(b, cb) {
                 return Vec::new();
             }
-            let subs = flatten(&ops);
-            if too_much_work(&subs, clip) {
-                return Vec::new();
-            }
-            let f = clip_fill(&subs, clip);
+            let f = clip_fill(&flatten(&ops), clip);
             if f.is_empty() { Vec::new() } else { vec![Raw::Pattern { ops: f, even_odd, tile, region }] }
         }
         Raw::Bitmap { rect, img, region } => crop(rect, img, clip).map(|(rect, img)| vec![Raw::Bitmap { rect, img, region }]).unwrap_or_default(),
@@ -241,12 +230,6 @@ pub(crate) fn flatten(ops: &[Op]) -> Vec<(Vec<P>, bool)> {
     subs
 }
 
-/// Whether cutting every subpath of one item by `clip` would exceed [`MAX_CLIP_WORK`]; the
-/// per-polygon check alone lets many small subpaths each spend the whole allowance.
-fn too_much_work(subs: &[(Vec<P>, bool)], clip: &[P]) -> bool {
-    subs.iter().map(|s| s.0.len() + 1).sum::<usize>().saturating_mul(clip.len()) > MAX_CLIP_WORK
-}
-
 fn clip_fill(subs: &[(Vec<P>, bool)], clip: &[P]) -> Vec<Op> {
     let mut ops = Vec::new();
     for (pts, _) in subs {

crates/metafile/src/tests.rs

@@ -2074,18 +2074,3 @@ fn clip_polygon_work_bound() {
     let clipped = crate::cliprect::clip_polygon(&poly, &clip);
     assert!(clipped.is_empty(), "excessive polygon clip product rejected");
 }
-
-#[test]
-fn clip_work_is_bounded_across_subpaths() {
-    use crate::canvas::Raw;
-    use crate::geom::Op;
-    // 512-gon clip; 4,000 small triangles crossing its edge: each under the per-polygon cap, together
-    // far over it, for both the fill and the stroke.
-    let clip: Vec<(f64, f64)> =
-        (0..512).map(|i| (i as f64 / 512.0 * std::f64::consts::TAU).sin_cos()).map(|(s, c)| (100.0 + 100.0 * c, 100.0 + 100.0 * s)).collect();
-    let tri = |x: f64| [Op::M((x, 95.0)), Op::L((x + 1.0, 95.0)), Op::L((x, 300.0)), Op::Z];
-    let many: Vec<Op> = (0..4000).flat_map(|i| tri(i as f64 % 200.0)).collect();
-    let raw = |ops| Raw::Path { ops, fill: Some([0, 0, 0, 255]), stroke: Some(([0, 0, 0, 255], 1.0)), even_odd: false, region: None };
-    assert!(crate::cliprect::clip_raw(raw(many), &clip).is_empty(), "the whole item's clipping work is bounded");
-    assert_eq!(crate::cliprect::clip_raw(raw(tri(100.0).to_vec()), &clip).len(), 2, "a small crossing shape is still clipped");
-}

crates/model/src/table.rs

@@ -77,6 +77,9 @@ 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;
+
 impl Table {
     pub fn new(rows: usize, cols: usize, width: f64, row_height: f64) -> Self {
         let rows = rows.clamp(1, 1000);
@@ -164,8 +167,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 +181,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 });
                 }
             }
@@ -283,21 +293,25 @@ 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).
+    /// 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 +527,42 @@ mod tests {
         }
     }
 
+    #[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);