address review: share one clip-work allowance between fill and stroke

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

@@ -11,6 +11,10 @@ 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;
@@ -100,14 +104,20 @@ 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()) > 1_000_000 {
-        return Vec::new();
-    }
+    clip_polygon_within(poly, clip, &mut { MAX_CLIP_WORK }).unwrap_or_default()
+}
+
+/// [`clip_polygon`] charging each point visited against each clip edge to `budget`: the polygon
+/// can gain a vertex at every edge, so its cost isn't known from its input size alone. `None`
+/// once the budget is spent.
+fn clip_polygon_within(poly: &[P], clip: &[P], budget: &mut usize) -> Option<Vec<P>> {
     let mut poly = poly.to_vec();
     for i in 0..clip.len() {
-        if poly.len().saturating_mul(clip.len() - i) > 1_000_000 {
-            return Vec::new();
+        // The work actually done: this edge visits the polygon as it now stands.
+        if poly.len() > *budget {
+            return None;
         }
+        *budget -= poly.len();
         let (a, b) = (clip[i], clip[(i + 1) % clip.len()]);
         let keep = |p: P| cross(a, b, p) >= 0.0;
         let cut = |p: P, q: P| {
@@ -133,7 +143,7 @@ pub(crate) fn clip_polygon(poly: &[P], clip: &[P]) -> Vec<P> {
             break;
         }
     }
-    poly
+    Some(poly)
 }
 
 fn disjoint(b: [f64; 4], c: [f64; 4]) -> bool {
@@ -158,9 +168,12 @@ pub(crate) fn clip_raw(raw: Raw, clip: &[P]) -> Vec<Raw> {
                 return Vec::new();
             }
             let subs = flatten(&ops);
+            if too_much_work(&subs, clip, usize::from(fill.is_some()) + usize::from(stroke.is_some())) {
+                return Vec::new();
+            }
             let mut out = Vec::new();
             if fill.is_some() {
-                let f = clip_fill(&subs, clip);
+                let Some(f) = clip_fill(&subs, clip) else { return Vec::new() };
                 if !f.is_empty() {
                     out.push(Raw::Path { ops: f, fill, stroke: None, even_odd, region: region.clone() });
                 }
@@ -181,7 +194,11 @@ pub(crate) fn clip_raw(raw: Raw, clip: &[P]) -> Vec<Raw> {
             if disjoint(b, cb) {
                 return Vec::new();
             }
-            let f = clip_fill(&flatten(&ops), clip);
+            let subs = flatten(&ops);
+            if too_much_work(&subs, clip, 1) {
+                return Vec::new();
+            }
+            let f = clip_fill(&subs, clip).unwrap_or_default();
             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(),
@@ -230,17 +247,28 @@ pub(crate) fn flatten(ops: &[Op]) -> Vec<(Vec<P>, bool)> {
     subs
 }
 
-fn clip_fill(subs: &[(Vec<P>, bool)], clip: &[P]) -> Vec<Op> {
+/// 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. `passes` is
+/// how many clipping passes the item gets (fill and stroke each cut every subpath), so one item
+/// shares a single allowance between them.
+fn too_much_work(subs: &[(Vec<P>, bool)], clip: &[P], passes: usize) -> bool {
+    subs.iter().map(|s| s.0.len() + 1).sum::<usize>().saturating_mul(clip.len()).saturating_mul(passes) > MAX_CLIP_WORK
+}
+
+/// The clipped fill of every subpath, its clipping work shared by all of them: `None` (the whole
+/// item goes) once [`MAX_CLIP_WORK`] is spent.
+fn clip_fill(subs: &[(Vec<P>, bool)], clip: &[P]) -> Option<Vec<Op>> {
     let mut ops = Vec::new();
+    let mut budget = MAX_CLIP_WORK;
     for (pts, _) in subs {
-        let poly = clip_polygon(pts, clip);
+        let poly = clip_polygon_within(pts, clip, &mut budget)?;
         if poly.len() >= 3 {
             ops.push(Op::M(poly[0]));
             ops.extend(poly[1..].iter().map(|p| Op::L(*p)));
             ops.push(Op::Z);
         }
     }
-    ops
+    Some(ops)
 }
 
 fn clip_stroke(subs: &[(Vec<P>, bool)], clip: &[P]) -> Vec<Op> {

crates/metafile/src/tests.rs

@@ -2074,3 +2074,63 @@ 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_polygon_charges_actual_work_not_projected_growth() {
+    // Two convex 1,000-gons: the product is exactly the budget, and a cut that adds a vertex must
+    // not make a later step look over budget.
+    let gon = |cx: f64| -> Vec<(f64, f64)> {
+        (0..1000).map(|i| (i as f64 / 1000.0 * std::f64::consts::TAU).sin_cos()).map(|(s, c)| (cx + 100.0 * c, 100.0 * s)).collect()
+    };
+    let clipped = crate::cliprect::clip_polygon(&gon(0.0), &gon(30.0));
+    assert!(clipped.len() > 100, "the intersection is kept: {}", clipped.len());
+}
+
+#[test]
+fn clip_work_is_shared_by_fill_and_stroke() {
+    use crate::canvas::Raw;
+    use crate::geom::Op;
+    // One zigzag subpath crossing a 512-gon's edge: about 510k point-edge tests per pass, so a
+    // fill alone fits the allowance but a fill plus a stroke would spend it twice.
+    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 mut ops = vec![Op::M((0.0, 95.0))];
+    ops.extend((1..1000).map(|i| Op::L((i as f64 * 0.19, if i % 2 == 0 { 95.0 } else { 300.0 }))));
+    ops.push(Op::Z);
+    let raw = |fill, stroke| Raw::Path { ops: ops.clone(), fill, stroke, even_odd: false, region: None };
+    let black = [0, 0, 0, 255];
+    assert!(!crate::cliprect::clip_raw(raw(Some(black), None), &clip).is_empty(), "a fill alone is within the allowance");
+    assert!(crate::cliprect::clip_raw(raw(Some(black), Some((black, 1.0))), &clip).is_empty(), "fill and stroke share one allowance");
+}
+
+#[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");
+}
+
+/// Clipping a fill can add a vertex at every clip edge, so a polygon's work isn't its input size:
+/// shapes that pass the up-front estimate but grow while clipped are charged as they grow, against
+/// one budget for the whole item.
+#[test]
+fn growing_fill_clips_share_one_budget() {
+    use crate::canvas::Raw;
+    use crate::geom::Op;
+    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();
+    // A triangle around the whole circle: clipped, it becomes the 512-gon, about 130,000 steps.
+    let tri = [Op::M((-1000.0, -1000.0)), Op::L((1000.0, -1000.0)), Op::L((100.0, 1000.0)), Op::Z];
+    let raw = |n: usize| Raw::Path { ops: tri.repeat(n), fill: Some([0, 0, 0, 255]), stroke: None, even_odd: false, region: None };
+    // 400 of them pass the estimate (400 x 4 x 512 is under a million) but cost about 52 million.
+    assert!(crate::cliprect::clip_raw(raw(400), &clip).is_empty(), "the growing work is charged");
+    assert_eq!(crate::cliprect::clip_raw(raw(2), &clip).len(), 1, "a couple of them are still clipped");
+}