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/engine/src/tests.rs

@@ -5023,38 +5023,6 @@ fn pen_pressure_is_kept_and_a_mouse_draws_at_full_width() {
     assert_eq!(got, vec![vec![0.2, 1.0, 0.4], vec![1.0, 1.0]]);
 }
 
-#[test]
-fn a_long_ink_stroke_is_extended_in_place_and_capped() {
-    let mut s = session();
-    s.set_tool(tools::ToolKind::Ink { mode: "pen".into(), color: deckcraft_model::Rgba::rgb(20, 20, 20), width: 4.0 });
-    let ev = |kind, x: f64| tools::PointerEvent { kind, x, y: 80.0, mods: Mods::default(), tol: 3.0, pressure: Some(0.5) };
-    s.pointer(ev(PointerKind::Down, 0.0)).unwrap();
-    let n = tools::MAX_GESTURE_POINTS + 5_000;
-    for i in 1..n {
-        s.pointer(ev(PointerKind::Drag, (i % 500) as f64)).unwrap();
-    }
-    assert_eq!(s.tool.ink_preview.len(), tools::MAX_GESTURE_POINTS);
-    s.pointer(ev(PointerKind::Up, 0.0)).unwrap();
-    let kept: usize = ink_pressures(&s).iter().map(Vec::len).sum();
-    assert!((2..=tools::MAX_GESTURE_POINTS).contains(&kept), "{kept}");
-}
-
-#[test]
-fn double_clicking_a_capped_freeform_keeps_its_vertices() {
-    let mut s = session();
-    let ev = |kind, x: f64, y: f64| tools::PointerEvent { kind, x, y, mods: Default::default(), tol: 3.0, pressure: None };
-    s.set_tool(tools::ToolKind::Shape { preset: "freeform".into() });
-    s.pointer(ev(tools::PointerKind::Down, 100.0, 100.0)).unwrap();
-    // Densely clicked vertices, each within the double-click tolerance of the last.
-    for i in 0..tools::MAX_GESTURE_POINTS + 10 {
-        s.pointer(ev(tools::PointerKind::Down, 300.0 + i as f64 * 0.001, 100.0)).unwrap();
-    }
-    s.pointer(ev(tools::PointerKind::DoubleClick, 300.0, 100.0)).unwrap();
-    let st = s.doc().unwrap();
-    let deckcraft_model::Geom::Custom { paths } = &st.shapes().last().unwrap().geom else { panic!("no freeform") };
-    assert_eq!(paths[0].d.matches(" L ").count(), tools::MAX_GESTURE_POINTS - 1);
-}
-
 fn ink_pressures(s: &Session) -> Vec<Vec<f32>> {
     let st = s.doc().unwrap();
     let Some(sh) = st.shapes().iter().rev().find(|sh| matches!(sh.kind, deckcraft_model::ShapeKind::Ink { .. })) else {

crates/engine/src/tools.rs

@@ -17,7 +17,6 @@ mod geometry;
 mod hit;
 mod pointer;
 
-pub(crate) use drag::MAX_GESTURE_POINTS;
 pub use hit::{line_xfrm, resize_box, table_rows, text_pos};
 
 #[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Serialize, Deserialize)]
@@ -276,8 +275,6 @@ pub struct ToolState {
     pub path_preview: Vec<Point>,
     pub path_smooth: bool,
     pub path_closing: bool,
-    /// Whether the last freeform press added a vertex (it adds none at the point cap).
-    pub press_added_vertex: bool,
     /// The shape in Edit Points: its vertices are handles instead of the box's.
     pub edit_points: Option<ShapeId>,
     /// The vertex (path, index) whose control handles show in Edit Points.

crates/engine/src/tools/click.rs

@@ -4,12 +4,8 @@ use super::{Drag, Hit, Point, Result, Session, ShapeId, ShapeKind, TextSel, Tool
 impl Session {
     pub(super) fn double_click(&mut self, p: Point, tol: f64) -> Result<Value> {
         if let Some(Drag::Freeform { mode, mut points, .. }) = self.tool.drag.clone() {
-            // The double-click's own click added a duplicate vertex (none at the point cap, where
-            // the existing vertices are all kept).
-            while self.tool.press_added_vertex
-                && points.len() > 2
-                && points.last().zip(points.get(points.len() - 2)).is_some_and(|(a, b)| (*a - *b).hypot() <= tol)
-            {
+            // The double-click's own click added a duplicate vertex.
+            while points.len() > 2 && points.last().zip(points.get(points.len() - 2)).is_some_and(|(a, b)| (*a - *b).hypot() <= tol) {
                 points.pop();
             }
             self.tool.drag = Some(Drag::Freeform { mode, points, pressed: false });

crates/engine/src/tools/drag.rs

@@ -12,16 +12,9 @@ struct MoveDrag {
     enter_text: Option<(ShapeId, Point)>,
 }
 
-/// Samples one ink or freeform gesture keeps; later pointer moves extend it no further.
-pub(crate) const MAX_GESTURE_POINTS: usize = 20_000;
-
 impl Session {
     /// Update the active drag interaction using the pointer position and modifiers.
     pub(super) fn drag(&mut self, p: Point, mods: Mods, tol: f64) -> Result<Value> {
-        if matches!(self.tool.drag, Some(Drag::Ink { .. })) {
-            self.extend_ink(p);
-            return Ok(Value::Null);
-        }
         let Some(drag) = self.tool.drag.clone() else { return Ok(Value::Null) };
         match drag {
             Drag::Guide { index } => {
@@ -188,7 +181,7 @@ impl Session {
             }
             Drag::Freeform { mode, mut points, pressed } => {
                 // Dragging scribbles (except for curves, which only take clicked points).
-                if pressed && mode != "curve" && points.len() < MAX_GESTURE_POINTS && points.last().is_none_or(|l| (*l - p).hypot() >= 1.5) {
+                if pressed && mode != "curve" && points.last().is_none_or(|l| (*l - p).hypot() >= 1.5) {
                     points.push(p);
                 }
                 let mut v = points.clone();
@@ -198,24 +191,15 @@ impl Session {
                 self.tool.path_preview = v;
                 self.tool.drag = Some(Drag::Freeform { mode, points, pressed });
             }
-            // Handled above.
-            Drag::Ink { .. } => {}
+            Drag::Ink { mut points } => {
+                points.push(self.ink_sample(p));
+                self.tool.ink_preview = points.clone();
+                self.tool.drag = Some(Drag::Ink { points });
+            }
         }
         Ok(Value::Null)
     }
 
-    /// Ink grows by one sample per move: extend it (and its preview) in place rather than
-    /// copying the whole stroke twice per event, up to [`MAX_GESTURE_POINTS`].
-    fn extend_ink(&mut self, p: Point) {
-        let sample = self.ink_sample(p);
-        if let Some(Drag::Ink { points }) = self.tool.drag.as_mut()
-            && points.len() < MAX_GESTURE_POINTS
-        {
-            points.push(sample);
-            self.tool.ink_preview.push(sample);
-        }
-    }
-
     fn drag_move(&mut self, drag: MoveDrag, p: Point, mods: Mods, tol: f64) -> Result<Value> {
         let MoveDrag { ids, start, origs, moved, duplicate, enter_text } = drag;
         let mut d = p - start;

crates/engine/src/tools/pointer.rs

@@ -228,10 +228,7 @@ impl Session {
                 self.tool.drag = Some(Drag::Freeform { mode, points, pressed: false });
                 return self.finish_freeform(true);
             }
-            self.tool.press_added_vertex = points.len() < super::MAX_GESTURE_POINTS;
-            if self.tool.press_added_vertex {
-                points.push(p);
-            }
+            points.push(p);
             self.tool.path_preview = points.clone();
             self.tool.drag = Some(Drag::Freeform { mode, points, pressed: true });
             return Ok(Value::Null);
@@ -552,7 +549,7 @@ impl Session {
             Some(Drag::Freeform { mode, points, .. }) => {
                 if mode == "scribble" {
                     // A scribble ending back at its start closes into a filled shape.
-                    let closed = points.len() > 3 && points.first().is_some_and(|a| (*a - p).hypot() <= 6.0);
+                    let closed = points.len() > 3 && points.first().zip(points.last()).is_some_and(|(a, b)| (*a - *b).hypot() <= 6.0);
                     self.tool.drag = Some(Drag::Freeform { mode, points, pressed: false });
                     return self.finish_freeform(closed);
                 }

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);