address review: count shared tiles once, include text advances, check clip region before keeping an item

crates/metafile/src/canvas.rs

@@ -369,6 +369,11 @@ impl Canvas {
     }
 
     /// True once the item cap is hit; the readers stop there and keep what they have.
+    /// Bytes the canvas has retained so far.
+    pub fn used(&self) -> usize {
+        self.used
+    }
+
     pub fn full(&self) -> bool {
         self.full
     }
@@ -551,6 +556,10 @@ impl Canvas {
     /// of at most [`SHADE_RES`] cells on the longer side, laid out so that its one repeat covers
     /// the shape.
     pub fn shade_shape(&mut self, ops: &[Op], shade: &dyn Fn(P) -> [u8; 4]) {
+        // A full canvas keeps nothing more, so do not sample a tile for it.
+        if self.full {
+            return;
+        }
         let dev: Vec<Op> = ops.iter().map(|o| self.map_op(*o)).collect();
         let Some([l, t, r, b]) = crate::cliprect::ops_bbox(&dev) else { return };
         let side = (r - l).max(b - t);

crates/metafile/src/emfplus.rs

@@ -289,7 +289,7 @@ impl Plus {
             return None;
         }
         match typ {
-            0x4008 => self.object(flags, r),
+            0x4008 => self.object(flags, r, cv.used()),
             0x4009 | 0x4013 | 0x401A..=0x401C | 0x4036 => self.record_image_text_region(cv, typ, flags, r),
             0x4025..=0x4035 => self.record_state(cv, typ, flags, r),
             0x4010..=0x4012 | 0x4016..=0x4019 => self.record_curve(cv, typ, flags, r),
@@ -559,7 +559,7 @@ impl Plus {
         Some(())
     }
 
-    fn object(&mut self, flags: u16, r: Bytes) -> Option<()> {
+    fn object(&mut self, flags: u16, r: Bytes, canvas_used: usize) -> Option<()> {
         let id = usize::from(flags & 0xFF);
         let kind = (flags >> 8) & 0x7F;
         if flags & 0x8000 != 0 {
@@ -575,7 +575,7 @@ impl Plus {
             p.data.extend_from_slice(&chunk[..chunk.len().min(room)]);
             if p.data.len() >= p.total {
                 let obj = parse_object(p.kind, Bytes(&p.data));
-                self.store(p.id, obj);
+                self.store(p.id, obj, canvas_used);
             } else {
                 self.partial = Some(p);
             }
@@ -589,22 +589,23 @@ impl Plus {
             let room = p.total.saturating_sub(p.data.len());
             p.data.extend_from_slice(&r.0[..r.0.len().min(room)]);
             let obj = parse_object(kind, Bytes(&p.data));
-            self.store(id, obj);
+            self.store(id, obj, canvas_used);
             return Some(());
         }
         let obj = parse_object(kind, r);
-        self.store(id, obj);
+        self.store(id, obj, canvas_used);
         Some(())
     }
 
-    fn store(&mut self, id: usize, obj: Option<Obj>) {
+    /// `canvas_used` is what the canvas already retains: objects and items share one budget.
+    fn store(&mut self, id: usize, obj: Option<Obj>, canvas_used: usize) {
         let Some(slot) = self.objects.get_mut(id) else { return };
         if let Some(old) = slot.take() {
             self.object_bytes = self.object_bytes.saturating_sub(Self::obj_cost(&old));
         }
         if let Some(new_obj) = obj {
             let cost = Self::obj_cost(&new_obj);
-            if self.object_bytes.saturating_add(cost) <= crate::MAX_BYTES {
+            if self.object_bytes.saturating_add(cost).saturating_add(canvas_used) <= crate::MAX_BYTES {
                 self.object_bytes += cost;
                 *slot = Some(new_obj);
             }
@@ -615,7 +616,7 @@ impl Plus {
         match obj {
             Obj::Image(img) => match img.as_ref() {
                 ImageData::Bitmap(rgba) => rgba.px.len(),
-                ImageData::Meta(pic) => pic.items.len().saturating_mul(128),
+                ImageData::Meta(pic) => picture_cost(&pic.items),
             },
             Obj::Brush(Fill::Texture { img, .. }) => img.px.len(),
             Obj::Path(ops) => ops.len().saturating_mul(std::mem::size_of::<Op>()),
@@ -1276,6 +1277,33 @@ fn metafile(r: Bytes) -> Option<Picture> {
     pic.filter(|p| p.width > 0.0 && p.height > 0.0)
 }
 
+/// Bytes the items of a nested picture own: path segments, clip rectangles, pixels and text, with
+/// each shared pattern tile counted once.
+fn picture_cost(items: &[crate::Item]) -> usize {
+    use crate::Item;
+    let region = |r: &Option<Vec<[f32; 4]>>| r.as_ref().map_or(0, |v| v.len().saturating_mul(16));
+    let mut tiles = std::collections::HashSet::new();
+    let mut total = 0usize;
+    for item in items {
+        let own = match item {
+            Item::Path { segs, region: r, .. } => segs.len().saturating_mul(std::mem::size_of::<crate::Seg>()).saturating_add(region(r)),
+            Item::Bitmap { rgba, region: r, .. } => rgba.len().saturating_add(region(r)),
+            Item::Pattern { segs, tile, region: r, .. } => {
+                let tile_bytes = if tiles.insert(Arc::as_ptr(tile)) { tile.rgba.len() } else { 0 };
+                segs.len().saturating_mul(std::mem::size_of::<crate::Seg>()).saturating_add(tile_bytes).saturating_add(region(r))
+            }
+            Item::Text(t) => t
+                .text
+                .len()
+                .saturating_add(t.dx.len().saturating_mul(std::mem::size_of::<f32>()))
+                .saturating_add(t.font.family.len())
+                .saturating_add(region(&t.region)),
+        };
+        total = total.saturating_add(128).saturating_add(own);
+    }
+    total
+}
+
 fn bitmap(r: Bytes) -> Option<Rgba> {
     let (w, h, stride) = (r.u32(8)? as i32, r.u32(12)? as i32, r.u32(16)? as i32);
     let format = r.u32(20)?;
@@ -1553,3 +1581,17 @@ fn wrap_line(line: &[u16], width: f64, em: f64) -> Vec<Vec<u16>> {
     out.push(cur);
     out
 }
+
+#[cfg(test)]
+mod cost_tests {
+    use super::*;
+    use crate::{Item, Seg, Tile};
+
+    #[test]
+    fn a_shared_pattern_tile_is_charged_once() {
+        let tile = Arc::new(Tile { width: 512, height: 512, rgba: vec![0; 1 << 20], cell: [1.0, 1.0], origin: [0.0, 0.0] });
+        let item = || Item::Pattern { segs: vec![Seg::Move(0.0, 0.0), Seg::Line(1.0, 1.0)], even_odd: false, tile: tile.clone(), region: None };
+        let items: Vec<Item> = (0..257).map(|_| item()).collect();
+        assert!(picture_cost(&items) < 2 << 20, "{}", picture_cost(&items));
+    }
+}

crates/metafile/src/place.rs

@@ -58,6 +58,7 @@ impl Picture {
         let k = (c[0].abs() + c[3].abs()) / 2.0;
         let mut out = Vec::with_capacity(self.items.len());
         let mut total_elements = 0usize;
+        let region_elements = std::cell::Cell::new(0usize);
         let mut cached_region: Option<(*const [f32; 4], usize, Option<Option<Arc<BezPath>>>)> = None;
         let mut get_region = |reg: &Option<Vec<[f32; 4]>>| -> Option<Option<Arc<BezPath>>> {
             let (ptr, len) = match reg {
@@ -71,12 +72,15 @@ impl Picture {
                 return res.clone();
             }
             let res = placed_region(&tf, reg);
+            // Each distinct clip region is expanded once; its elements count against the placement budget.
+            let n = res.as_ref().and_then(Option::as_ref).map_or(0, |p| p.elements().len());
+            region_elements.set(region_elements.get().saturating_add(n));
             cached_region = Some((ptr, len, res.clone()));
             res
         };
 
         for (index, item) in self.items.iter().enumerate() {
-            if total_elements >= MAX_PLACED_ELEMENTS {
+            if total_elements.saturating_add(region_elements.get()) >= MAX_PLACED_ELEMENTS {
                 break;
             }
             match item {
@@ -84,6 +88,10 @@ impl Picture {
                     let path = tf * bez(segs);
                     let Some(region) = get_region(region) else { continue };
                     if in_range(path.bounding_box()) {
+                        // This item's own region is expanded by now: it counts before it is kept.
+                        if total_elements.saturating_add(path.elements().len()).saturating_add(region_elements.get()) > MAX_PLACED_ELEMENTS {
+                            break;
+                        }
                         total_elements = total_elements.saturating_add(path.elements().len());
                         let stroke = stroke.map(|(c, w)| (c, f64::from(w) * k));
                         out.push(PlacedItem::Path { path, fill: *fill, stroke, even_odd: *even_odd, region });
@@ -97,6 +105,9 @@ impl Picture {
                         * Affine::scale_non_uniform(f64::from(t.cell[0]), f64::from(t.cell[1]));
                     let det = tile.determinant();
                     if in_range(path.bounding_box()) && det.is_finite() && det.abs() > 1e-12 {
+                        if total_elements.saturating_add(path.elements().len()).saturating_add(region_elements.get()) > MAX_PLACED_ELEMENTS {
+                            break;
+                        }
                         total_elements = total_elements.saturating_add(path.elements().len());
                         out.push(PlacedItem::Pattern { index, path, even_odd: *even_odd, tile, region });
                     }

crates/metafile/src/tests.rs

@@ -897,6 +897,24 @@ fn place_fits_the_frame_scales_strokes_and_drops_far_paths() {
     assert_eq!(stroke.map(|s| s.1), Some(8.0));
 }
 
+#[test]
+fn place_counts_the_items_own_clip_region_before_keeping_it() {
+    // A path of 499,999 elements nearly fills the 500,000 budget; a second one whose new clip
+    // region adds elements goes past it and is left out.
+    let mut segs = vec![Seg::Move(0.0, 0.0)];
+    segs.extend((0..499_998).map(|i| Seg::Line(1.0 + (i % 50) as f32, 1.0)));
+    let big = Item::Path { segs, fill: None, stroke: None, even_odd: false, region: None };
+    let small = Item::Path {
+        segs: vec![Seg::Move(0.0, 0.0), Seg::Line(1.0, 1.0)],
+        fill: None,
+        stroke: None,
+        even_odd: false,
+        region: Some(vec![[0.0, 0.0, 50.0, 25.0], [10.0, 10.0, 20.0, 20.0]]),
+    };
+    let pic = crate::Picture { width: 100.0, height: 50.0, items: vec![big, small] };
+    assert_eq!(pic.place(kurbo::Rect::new(0.0, 0.0, 100.0, 50.0), [0.0; 4]).len(), 1);
+}
+
 #[test]
 fn place_keeps_only_finite_bounded_bitmaps_with_area() {
     let bitmap = |rect: [f32; 4]| Item::Bitmap { rect, width: 1, height: 1, rgba: vec![0; 4], region: None };
@@ -2074,3 +2092,15 @@ fn clip_polygon_work_bound() {
     let clipped = crate::cliprect::clip_polygon(&poly, &clip);
     assert!(clipped.is_empty(), "excessive polygon clip product rejected");
 }
+
+#[test]
+fn full_canvas_does_not_sample_gradient_tiles() {
+    let mut cv = Canvas::new();
+    let big = || Rgba { w: 1, h: 1, bottom_up: false, px: vec![0u8; MAX_BYTES / 2] };
+    for _ in 0..3 {
+        cv.bitmap([0.0, 0.0, 1.0, 1.0], big());
+    }
+    assert!(cv.full());
+    cv.shade_shape(&crate::geom::rect(0.0, 0.0, 10.0, 10.0), &|_| panic!("sampled a full canvas"));
+    assert_eq!(cv.items.len(), 2);
+}

crates/render/src/bevel.rs

@@ -125,9 +125,7 @@ pub fn draw(ctx: &mut RenderContext, bevel: &Bevel, fill: Option<Rgba>, path: &B
     let longest = bounds.width().max(bounds.height()) * k;
     let s = (MAX_SIDE / longest).min(1.0) * k;
     let (pw, ph) = (((bounds.width() * s).ceil() as u32).clamp(1, 2048), ((bounds.height() * s).ceil() as u32).clamp(1, 2048));
-    // Each pixel tests every edge, so a dense outline is simplified to the raster's edge budget.
-    let pixel = (bounds.width() / f64::from(pw)).min(bounds.height() / f64::from(ph));
-    let polys = crate::pathgrad::simplify(crate::pathgrad::polygons(path), pixel, crate::pathgrad::edge_budget(pw, ph));
+    let polys = crate::pathgrad::polygons(path);
     if polys.is_empty() {
         return;
     }

crates/render/src/colr.rs

@@ -11,8 +11,6 @@ use vello_cpu::{RenderContext, peniko};
 
 /// Nesting depth of clips and layers past which a glyph opens no more (hostile fonts).
 const MAX_DEPTH: usize = 64;
-/// Fills and gradient stops one colour glyph may paint; the rest of a hostile glyph is skipped.
-const MAX_WORK: usize = 100_000;
 
 /// Paint `gid` of `face` as a colour glyph, its origin mapped by `at` (y down, points) at `scale`
 /// points per font unit. `fg` is the text colour (palette index 0xFFFF) and `alpha` fades it all.
@@ -28,7 +26,7 @@ pub fn paint(ctx: &mut RenderContext, face: &FontFace, gid: u32, at: Affine, sca
         .unwrap_or_default();
     // Font units are y up; the slide is y down.
     let base = at * Affine::scale(scale) * Affine::scale_non_uniform(1.0, -1.0);
-    let mut p = Painter { ctx, face, base, stack: vec![Affine::IDENTITY], palette, fg, opened: Vec::new(), work: 0 };
+    let mut p = Painter { ctx, face, base, stack: vec![Affine::IDENTITY], palette, fg, opened: Vec::new() };
     p.ctx.push_layer(None, None, Some(alpha.clamp(0.0, 1.0) as f32), None, None);
     let ok = glyph.paint(face.location(), &mut p).is_ok();
     // A malformed glyph may leave layers open: close them all.
@@ -52,8 +50,6 @@ struct Painter<'a> {
     /// Clips and composite groups pushed by the glyph, innermost last: true when a layer was
     /// opened on the context for it (false past `MAX_DEPTH`, so its pop is skipped too).
     opened: Vec<bool>,
-    /// Fills plus gradient stops painted so far, against [`MAX_WORK`].
-    work: usize,
 }
 
 fn affine(t: &Transform) -> Affine {
@@ -178,16 +174,6 @@ impl ColorPainter for Painter<'_> {
     }
 
     fn fill(&mut self, brush: Brush<'_>) {
-        let stops = match &brush {
-            Brush::Solid { .. } => 0,
-            Brush::LinearGradient { color_stops, .. } | Brush::RadialGradient { color_stops, .. } | Brush::SweepGradient { color_stops, .. } => {
-                color_stops.len()
-            }
-        };
-        self.work = self.work.saturating_add(1 + stops);
-        if self.work > MAX_WORK {
-            return;
-        }
         match brush {
             Brush::Solid { palette_index, alpha } => {
                 let c = self.color(palette_index, alpha);

crates/render/src/pathgrad.rs

@@ -25,16 +25,6 @@ const MAX_EDGE_WORK: u64 = 64_000_000;
 /// Fewest edges a simplified polygon keeps, so a coarse outline still has a shape.
 const MIN_POLY_EDGES: usize = 8;
 
-/// Most points `polygons` keeps from one path; a path flattening past this (a huge finite curve) is
-/// not drawn rather than held in memory first.
-const MAX_POINTS: usize = 2_000_000;
-
-/// The edge budget for a `pw` x `ph` raster where each pixel tests every edge.
-pub(crate) fn edge_budget(pw: u32, ph: u32) -> usize {
-    let pixels = u64::from(pw).saturating_mul(u64::from(ph)).max(1);
-    usize::try_from(MAX_EDGE_WORK / pixels).unwrap_or(usize::MAX).max(MIN_POLY_EDGES)
-}
-
 /// Colour position (0 at the focus, 1 at the edge) of `p` for path `kind` in `bounds` with the
 /// focus rect `focus` (fractions inset from left, top, right, bottom), `outline` being the
 /// shape's flattened polygon(s) for `shape`.
@@ -124,31 +114,21 @@ fn shape_position(outline: &[Vec<Point>], c: Point, p: Point) -> f64 {
 pub fn polygons(path: &BezPath) -> Vec<Vec<Point>> {
     let mut out: Vec<Vec<Point>> = Vec::new();
     let mut cur: Vec<Point> = Vec::new();
-    let mut total = 0usize;
-    kurbo::flatten(path.iter(), 0.25, |el| {
-        total += 1;
-        if total > MAX_POINTS {
-            return;
-        }
-        match el {
-            PathEl::MoveTo(p) => {
-                if cur.len() > 1 {
-                    out.push(std::mem::take(&mut cur));
-                }
-                cur = vec![p];
+    kurbo::flatten(path.iter(), 0.25, |el| match el {
+        PathEl::MoveTo(p) => {
+            if cur.len() > 1 {
+                out.push(std::mem::take(&mut cur));
             }
-            PathEl::LineTo(p) => cur.push(p),
-            PathEl::ClosePath => {
-                if let Some(f) = cur.first().copied() {
-                    cur.push(f);
-                }
-            }
-            _ => {}
+            cur = vec![p];
         }
+        PathEl::LineTo(p) => cur.push(p),
+        PathEl::ClosePath => {
+            if let Some(f) = cur.first().copied() {
+                cur.push(f);
+            }
+        }
+        _ => {}
     });
-    if total > MAX_POINTS {
-        return Vec::new();
-    }
     if cur.len() > 1 {
         out.push(cur);
     }
@@ -166,7 +146,7 @@ pub fn polygons(path: &BezPath) -> Vec<Vec<Point>> {
 /// `outline` cut down to at most about `max_edges` edges in total: first by dropping points
 /// closer than `tol` to the last kept one (detail finer than a raster pixel), then, if still too
 /// many, by keeping every k-th point. Each polygon stays closed. Returns it unchanged when it fits.
-pub(crate) fn simplify(outline: Vec<Vec<Point>>, tol: f64, max_edges: usize) -> Vec<Vec<Point>> {
+fn simplify(outline: Vec<Vec<Point>>, tol: f64, max_edges: usize) -> Vec<Vec<Point>> {
     let edges = |o: &[Vec<Point>]| o.iter().map(|p| p.len().saturating_sub(1)).sum::<usize>();
     if edges(&outline) <= max_edges {
         return outline;
@@ -253,17 +233,13 @@ pub fn fill(ctx: &mut RenderContext, kind: &str, focus: [f64; 4], stops: &[(f64,
     let s = (MAX_SIDE / longest).min(1.0) * k;
     let (pw, ph) = (((bounds.width() * s).ceil() as u32).clamp(1, 4096), ((bounds.height() * s).ceil() as u32).clamp(1, 4096));
     let outline = if kind == "shape" {
-        let max_edges = edge_budget(pw, ph);
+        let pixels = u64::from(pw).saturating_mul(u64::from(ph)).max(1);
+        let max_edges = usize::try_from(MAX_EDGE_WORK / pixels).unwrap_or(usize::MAX).max(MIN_POLY_EDGES);
         let pixel = (bounds.width() / f64::from(pw)).min(bounds.height() / f64::from(ph));
         simplify(polygons(path), pixel, max_edges)
     } else {
         Vec::new()
     };
-    // An outline `polygons` refused (too many points) has no contours: skip the shape rather than
-    // paint it with the rectangle fallback's different gradient.
-    if kind == "shape" && outline.is_empty() {
-        return;
-    }
     let lut = ramp(stops);
     let a = alpha.clamp(0.0, 1.0);
     let mut data = Vec::with_capacity((pw * ph) as usize);
@@ -396,20 +372,6 @@ mod tests {
         assert!(t.elapsed() < std::time::Duration::from_secs(20), "{:?}", t.elapsed());
     }
 
-    #[test]
-    fn a_shape_gradient_with_no_usable_outline_paints_nothing() {
-        // One polygon over the per-polygon cap is dropped by `polygons`.
-        let path = many_segment_square(26_000);
-        assert!(polygons(&path).is_empty());
-        let mut ctx = RenderContext::new(64, 64);
-        let stops = [(0.0, Rgba::rgb(0, 0, 0)), (1.0, Rgba::rgb(255, 255, 255))];
-        fill(&mut ctx, "shape", CENTRE, &stops, Rect::new(0.0, 0.0, 64.0, 64.0), &path, Affine::IDENTITY, 1.0);
-        ctx.flush();
-        let mut px = vec![0u8; 64 * 64 * 4];
-        ctx.render(vello_cpu::PixmapMut::new(64, 64, &mut px).unwrap(), &mut vello_cpu::Resources::new());
-        assert!(px.chunks(4).all(|p| p[3] == 0), "nothing was painted");
-    }
-
     #[test]
     fn the_ramp_runs_through_the_stops() {
         let stops = [(0.0, Rgba::rgb(0, 0, 0)), (0.5, Rgba::rgb(128, 128, 128)), (1.0, Rgba::rgb(255, 255, 255))];