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

The shaper lets one call grow to 256 glyphs per input character, as an
embedded font's substitutions decide, and every glyph was then copied out.
Items longer than 1 KiB are now shaped in pieces (cut at a space where one
is near, never before a combining mark or after a joiner), each with the
rest of the paragraph as context and the item's script, and a piece that
expands past 32 glyphs per character falls back to one glyph per character
from the cmap.

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/fonts/src/shape.rs

@@ -37,56 +37,146 @@ pub struct ShapeParams<'a> {
     pub language: Option<&'a str>,
 }
 
+/// Most bytes of text given to the shaper at once. The shaper lets one call grow its buffers to
+/// 256 glyphs per character (a font's substitutions decide how many), so a long item is shaped in
+/// pieces of this size, each with the rest of the paragraph as context.
+const MAX_SHAPE_CHUNK: usize = 1024;
+/// Most glyphs kept per character of a piece: a piece the font expands further is laid out one
+/// glyph per character from the cmap instead.
+const MAX_GLYPHS_PER_CHAR: usize = 32;
+
 /// Shape `para[range]` with `face`, the rest of `para` as context. Glyphs are in visual order
 /// (left to right) and clusters are byte offsets into `para`. `map` substitutes characters (All
 /// Caps) without moving clusters. An empty or out-of-bounds range shapes nothing.
 pub fn shape_range(face: &FontFace, para: &str, range: Range<usize>, params: &ShapeParams, map: impl Fn(char) -> char) -> Vec<ShapedGlyph> {
-    let (Some(pre), Some(text), Some(post)) = (para.get(..range.start), para.get(range.clone()), para.get(range.end..)) else {
+    let (Some(_), Some(text), Some(_)) = (para.get(..range.start), para.get(range.clone()), para.get(range.end..)) else {
         return Vec::new();
     };
-    let mut out = Vec::with_capacity(text.len());
+    let chunks = chunks(text, MAX_SHAPE_CHUNK);
+    let mut pieces: Vec<Vec<ShapedGlyph>> = Vec::with_capacity(chunks.len());
     let shaped = face.hb().map(|hb| {
         let shaper = face.shaper.shaper(&hb).instance(face.instance.as_ref()).build();
-        let mut buf = UnicodeBuffer::new();
-        buf.set_pre_context(pre);
-        buf.set_post_context(post);
-        for (i, c) in text.char_indices() {
-            buf.add(map(c), (range.start + i) as u32);
-        }
-        buf.guess_segment_properties();
-        if let Some(s) = params.script.and_then(|t| Script::from_iso15924_tag(Tag::new(&t))) {
-            buf.set_script(s);
-        }
-        if let Some(l) = params.language.or_else(|| params.script.and_then(crate::script::default_language)).and_then(|l| l.parse::<Language>().ok())
-        {
-            buf.set_language(l);
-        }
-        buf.set_direction(if params.rtl { Direction::RightToLeft } else { Direction::LeftToRight });
-        let gb = shaper.shape(buf, ShapeOptions::new().features(params.features));
-        for (info, pos) in gb.glyph_infos().iter().zip(gb.glyph_positions()) {
-            out.push(ShapedGlyph {
-                gid: info.glyph_id,
-                cluster: info.cluster as usize,
-                x_advance: pos.x_advance,
-                x_offset: pos.x_offset,
-                y_offset: pos.y_offset,
-            });
+        // Pieces of one item share the script the whole item would be guessed to have.
+        let item_script = (chunks.len() > 1 && params.script.is_none()).then(|| {
+            let mut probe = UnicodeBuffer::new();
+            for c in text.chars() {
+                probe.add(map(c), 0);
+            }
+            probe.guess_segment_properties();
+            probe.script()
+        });
+        for c in &chunks {
+            let r = (range.start + c.start)..(range.start + c.end);
+            let (Some(pre), Some(piece), Some(post)) = (para.get(..r.start), para.get(r.clone()), para.get(r.end..)) else { continue };
+            let mut buf = UnicodeBuffer::new();
+            buf.set_pre_context(pre);
+            buf.set_post_context(post);
+            for (i, c) in piece.char_indices() {
+                buf.add(map(c), (r.start + i) as u32);
+            }
+            buf.guess_segment_properties();
+            if let Some(s) = params.script.and_then(|t| Script::from_iso15924_tag(Tag::new(&t))) {
+                buf.set_script(s);
+            } else if let Some(s) = item_script {
+                buf.set_script(s);
+            }
+            if let Some(l) =
+                params.language.or_else(|| params.script.and_then(crate::script::default_language)).and_then(|l| l.parse::<Language>().ok())
+            {
+                buf.set_language(l);
+            }
+            buf.set_direction(if params.rtl { Direction::RightToLeft } else { Direction::LeftToRight });
+            let gb = shaper.shape(buf, ShapeOptions::new().features(params.features));
+            let budget = piece.chars().count().saturating_mul(MAX_GLYPHS_PER_CHAR);
+            if gb.len() > budget {
+                // Font-controlled expansion past anything real text needs: keep it bounded.
+                pieces.push(cmap_glyphs(face, para, r, params.rtl, &map));
+                continue;
+            }
+            pieces.push(
+                gb.glyph_infos()
+                    .iter()
+                    .zip(gb.glyph_positions())
+                    .map(|(info, pos)| ShapedGlyph {
+                        gid: info.glyph_id,
+                        cluster: info.cluster as usize,
+                        x_advance: pos.x_advance,
+                        x_offset: pos.x_offset,
+                        y_offset: pos.y_offset,
+                    })
+                    .collect(),
+            );
         }
     });
-    if shaped.is_none()
-        && let Some(f) = face.skrifa()
-    {
+    if shaped.is_none() {
         // No shaper for this face: one glyph per character from the cmap, in visual order.
-        let cmap = f.charmap();
-        let gm = f.glyph_metrics(Size::unscaled(), face.location());
-        for (i, c) in text.char_indices() {
-            let g = cmap.map(map(c)).unwrap_or_default();
-            let adv = gm.advance_width(g).unwrap_or(face.upem as f32 * 0.5);
-            out.push(ShapedGlyph { gid: g.to_u32(), cluster: range.start + i, x_advance: adv.round() as i32, x_offset: 0, y_offset: 0 });
-        }
-        if params.rtl {
-            out.reverse();
+        return cmap_glyphs(face, para, range, params.rtl, &map);
+    }
+    // Each piece is in visual order; right to left, the later pieces come first.
+    if params.rtl {
+        pieces.reverse();
+    }
+    let mut out = Vec::with_capacity(pieces.iter().map(Vec::len).sum());
+    for p in pieces {
+        out.extend(p);
+    }
+    out
+}
+
+/// One glyph per character of `para[range]` from the cmap, in visual order.
+fn cmap_glyphs(face: &FontFace, para: &str, range: Range<usize>, rtl: bool, map: &impl Fn(char) -> char) -> Vec<ShapedGlyph> {
+    let (Some(text), Some(f)) = (para.get(range.clone()), face.skrifa()) else { return Vec::new() };
+    let cmap = f.charmap();
+    let gm = f.glyph_metrics(Size::unscaled(), face.location());
+    let mut out = Vec::with_capacity(text.len());
+    for (i, c) in text.char_indices() {
+        let g = cmap.map(map(c)).unwrap_or_default();
+        let adv = gm.advance_width(g).unwrap_or(face.upem as f32 * 0.5);
+        out.push(ShapedGlyph { gid: g.to_u32(), cluster: range.start + i, x_advance: adv.round() as i32, x_offset: 0, y_offset: 0 });
+    }
+    if rtl {
+        out.reverse();
+    }
+    out
+}
+
+/// `text` cut into byte ranges of at most `max` bytes (or one character, if longer), at the last
+/// space of a piece where there is one, else before a character that starts a cluster (not a
+/// combining mark or joiner, not after a joiner). Text that fits is one piece.
+fn chunks(text: &str, max: usize) -> Vec<Range<usize>> {
+    use unicode_bidi::BidiClass::{BN, NSM};
+    let mut out = Vec::new();
+    let mut start = 0;
+    while text.len() - start > max {
+        let window = text.get(start..).unwrap_or_default();
+        let mut space = None;
+        let mut boundary = None;
+        let mut any = None;
+        let mut prev: Option<char> = None;
+        for (i, c) in window.char_indices() {
+            if i > max {
+                break;
+            }
+            if i > 0 {
+                any = Some(i);
+                let joined = prev.is_some_and(|p| matches!(unicode_bidi::bidi_class(p), BN));
+                if !joined && !matches!(unicode_bidi::bidi_class(c), NSM | BN) {
+                    boundary = Some(i);
+                    if prev.is_some_and(char::is_whitespace) {
+                        space = Some(i);
+                    }
+                }
+            }
+            prev = Some(c);
         }
+        // A piece always moves forward by at least one character.
+        let first = window.chars().next().map_or(window.len(), char::len_utf8);
+        let cut = space.filter(|&i| i >= max / 2).or(boundary).or(any).unwrap_or(first).max(first);
+        out.push(start..start + cut);
+        start += cut;
+    }
+    if start < text.len() || out.is_empty() {
+        out.push(start..text.len());
     }
     out
 }
@@ -121,4 +211,37 @@ mod tests {
         // Not a char boundary.
         assert!(shape_range(&face, "سنة", 1..2, &ShapeParams::default(), |c| c).is_empty());
     }
+
+    #[test]
+    fn long_items_are_shaped_in_bounded_pieces() {
+        for text in ["word ".repeat(2_000), "e\u{301}".repeat(2_000), "x".repeat(5_000), "\u{1f469}\u{200d}\u{1f4bb} ".repeat(500)] {
+            let pieces = chunks(&text, MAX_SHAPE_CHUNK);
+            assert_eq!(pieces.first().map(|r| r.start), Some(0));
+            assert_eq!(pieces.last().map(|r| r.end), Some(text.len()));
+            for w in pieces.windows(2) {
+                assert_eq!(w[0].end, w[1].start);
+            }
+            for r in &pieces {
+                assert!(!r.is_empty() && r.len() <= MAX_SHAPE_CHUNK);
+                // Never before a combining mark, never after a joiner.
+                let rest = &text[r.end..];
+                assert!(!rest.starts_with('\u{301}'));
+                assert!(!text[..r.end].ends_with('\u{200d}') || rest.is_empty());
+            }
+        }
+        assert_eq!(chunks("short", MAX_SHAPE_CHUNK), vec![0..5]);
+        assert_eq!(chunks("", MAX_SHAPE_CHUNK), vec![0..0]);
+    }
+
+    #[test]
+    fn long_items_keep_every_cluster_in_visual_order() {
+        let face = FontDb::global().face(DEFAULT_FAMILY, "Regular");
+        let text = "ab cd ".repeat(1_000);
+        let g = shape_range(&face, &text, 0..text.len(), &ShapeParams::default(), |c| c);
+        assert_eq!(g.len(), text.len());
+        assert!(g.windows(2).all(|w| w[0].cluster < w[1].cluster));
+        let rtl = shape_range(&face, &text, 0..text.len(), &ShapeParams { rtl: true, ..Default::default() }, |c| c);
+        assert_eq!(rtl.len(), text.len());
+        assert!(rtl.windows(2).all(|w| w[0].cluster > w[1].cluster));
+    }
 }

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