fix(render): charge boundary transforms and scanline sorts to the shared hatch budget

crates/constraints/src/auto.rs

@@ -232,10 +232,6 @@ pub fn infer_placed(d: &Drawing, placed: &[Handle], others: &[Handle], o: &Infer
     let mut extra = Vec::new();
     let mut on = Vec::new();
     for (rp, p) in g.points.iter().filter(|(r, _)| placed.contains(&r.handle)) {
-        // Nothing is added once the candidates are full, so the points left need no search.
-        if extra.len() + on.len() + out.len() >= MAX_CANDIDATES {
-            break;
-        }
         if out.iter().any(|c| c.kind == ConstraintKind::Coincident && c.refs.contains(rp)) {
             continue;
         }
@@ -271,22 +267,20 @@ pub fn infer_placed(d: &Drawing, placed: &[Handle], others: &[Handle], o: &Infer
     // Perpendicular lines meeting in a T (a perpendicular snap onto the middle of a line).
     let atol = if o.angle_tolerance.is_finite() { o.angle_tolerance.clamp(0.0, 45.0).to_radians() } else { 0.0 };
     let allow_per = o.types.is_empty() || o.types.iter().any(|t| t.eq_ignore_ascii_case(ConstraintKind::Perpendicular.name()));
-    'per: for (r1, a1, b1) in g.lines.iter().filter(|(r, _, _)| allow_per && placed.contains(&r.handle)) {
+    for (r1, a1, b1) in g.lines.iter().filter(|(r, _, _)| placed.contains(&r.handle)) {
         for (r2, a2, b2) in g.lines.iter().filter(|(r, _, _)| r.handle != r1.handle) {
-            // Full: nothing more can be added, so the pairs left need no geometry or duplicate search.
-            if out.len() >= MAX_CANDIDATES {
-                break 'per;
-            }
             let (l1, l2) = (Line::new(*a1, *b1), Line::new(*a2, *b2));
             let touches = |l: &Line, p: Vec2| l.dist(p) <= tol && (0.0..=1.0).contains(&l.param_of(p));
             let tee = [*a1, *b1].iter().any(|p| touches(&l2, *p)) || [*a2, *b2].iter().any(|p| touches(&l1, *p));
             let ang = ang_between(*b1 - *a1, *b2 - *a2);
-            // The duplicate search scans every candidate, so it comes after the cheap tests.
-            if tee
+            let dup = out.iter().any(|c| c.kind == ConstraintKind::Perpendicular && c.refs.contains(r1) && c.refs.contains(r2));
+            if allow_per
+                && tee
+                && !dup
                 && (std::f64::consts::FRAC_PI_2 - ang).abs() <= atol
                 && l1.len() > tol
                 && l2.len() > tol
-                && !out.iter().any(|c| c.kind == ConstraintKind::Perpendicular && c.refs.contains(r1) && c.refs.contains(r2))
+                && out.len() < MAX_CANDIDATES
             {
                 out.push(Constraint { id: 0, kind: ConstraintKind::Perpendicular, refs: vec![*r1, *r2], name: String::new(), expr: String::new() });
             }

crates/fonts/src/ttf.rs

@@ -89,11 +89,7 @@ impl Face {
         let Some(f) = self.font() else { return Vec::new() };
         [skrifa::string::StringId::FAMILY_NAME, skrifa::string::StringId::TYPOGRAPHIC_FAMILY_NAME, skrifa::string::StringId::FULL_NAME]
             .into_iter()
-            // A name table can hold many records that point at one big string: at most
-            // MAX_NAME_RECORDS per name id, each decoded only up to MAX_NAME_CHARS characters.
-            .flat_map(|id| {
-                f.localized_strings(id).take(MAX_NAME_RECORDS).map(|s| norm(&s.chars().take(MAX_NAME_CHARS).collect::<String>())).collect::<Vec<_>>()
-            })
+            .flat_map(|id| f.localized_strings(id).map(|s| norm(&s.to_string())).collect::<Vec<_>>())
             .collect()
     }
 }
@@ -108,10 +104,6 @@ pub fn faces(bytes: &Arc<Vec<u8>>) -> Vec<Face> {
 }
 
 const MAX_FACES_PER_FILE: u32 = 32;
-/// Name records read per name id of a face, and characters read of each: real fonts have a few
-/// dozen short ones.
-const MAX_NAME_RECORDS: usize = 64;
-const MAX_NAME_CHARS: usize = 256;
 /// Bounds of the missing-glyph search: files loaded, bytes loaded, faces checked per character.
 const MAX_FALLBACK_FILES: usize = 24;
 const MAX_FALLBACK_BYTES: usize = 160 << 20;

crates/geom/src/region.rs

@@ -110,10 +110,6 @@ fn build(polys: &[Vec<Vec2>], tol: f64) -> Option<Graph> {
     };
     let mut grid: HashMap<(usize, usize), Vec<usize>> = HashMap::new();
     let mut long: Vec<usize> = Vec::new();
-    // Every cell a segment is registered in is an index kept: past this many in all (each segment
-    // may take up to 4096 cells), the input is refused as it is for too much pair work.
-    const MAX_REGISTRATIONS: usize = 20_000_000;
-    let mut registered = 0usize;
     for (i, (a, b)) in segs.iter().enumerate() {
         let (x0, y0) = cell(a.min(*b));
         let (x1, y1) = cell(a.max(*b));
@@ -122,10 +118,6 @@ fn build(polys: &[Vec<Vec2>], tol: f64) -> Option<Graph> {
             long.push(i);
             continue;
         }
-        registered = registered.saturating_add((x1 - x0 + 1) * (y1 - y0 + 1));
-        if registered > MAX_REGISTRATIONS {
-            return None;
-        }
         for gx in x0..=x1 {
             for gy in y0..=y1 {
                 grid.entry((gx, gy)).or_default().push(i);
@@ -399,10 +391,10 @@ fn outside(core: &Graph, u: usize, steps: usize) -> Option<Vec<Vec2>> {
 }
 
 /// Outlines of the groups of curves inside the face `outer` (vertex indices into `g`).
-fn islands(g: &Graph, outer: &[usize], p: Vec2) -> Option<Vec<Island>> {
+fn islands(g: &Graph, outer: &[usize], p: Vec2) -> Vec<Island> {
     let comp = components(g);
     let outer_comp: std::collections::HashSet<usize> = outer.iter().filter_map(|&i| comp.get(i).copied()).collect();
-    let outer_pts = points(g, outer)?;
+    let Some(outer_pts) = points(g, outer) else { return Vec::new() };
     let ob = Bounds2::from_points(outer_pts.iter().copied());
     let core = prune(g);
     // Leftmost (then lowest) vertex still on a cycle, per component.
@@ -432,32 +424,19 @@ fn islands(g: &Graph, outer: &[usize], p: Vec2) -> Option<Vec<Island>> {
     let mut starts: Vec<(usize, usize)> = start.into_iter().collect();
     starts.sort_unstable();
     let mut out = Vec::new();
-    // Each containment test scans a whole polygon, accepted or not: they share one allowance of
-    // polygon edges, and the search ends when it is spent.
-    let mut edges_left: usize = 100_000_000;
     for (c, u) in starts {
         if out.len() >= MAX_ISLANDS {
             break;
         }
         let Some(&pu) = core.pts.get(u) else { continue };
-        if !ob.contains(pu) {
-            continue;
-        }
-        let left = edges_left.checked_sub(outer_pts.len())?;
-        edges_left = left;
-        if !point_in_polygon(&outer_pts, pu) {
+        if !ob.contains(pu) || !point_in_polygon(&outer_pts, pu) {
             continue;
         }
         let steps = edges.get(&c).copied().unwrap_or(0).saturating_add(4);
         let Some(lp) = outside(&core, u, steps) else { continue };
         let area = shoelace(&lp);
         let ib = Bounds2::from_points(lp.iter().copied());
-        if lp.len() < 3 || !area.is_finite() || area <= 0.0 || !ob.contains_box(&ib) {
-            continue;
-        }
-        let left = edges_left.checked_sub(lp.len())?;
-        edges_left = left;
-        if point_in_polygon(&lp, p) {
+        if lp.len() < 3 || !area.is_finite() || area <= 0.0 || !ob.contains_box(&ib) || point_in_polygon(&lp, p) {
             continue;
         }
         let mut src = sources.remove(&c).unwrap_or_default();
@@ -465,7 +444,7 @@ fn islands(g: &Graph, outer: &[usize], p: Vec2) -> Option<Vec<Island>> {
         src.dedup();
         out.push(Island { outline: lp, sources: src });
     }
-    Some(out)
+    out
 }
 
 /// The point of the nearest other curve within `snap` of the end `e` of curve `i`, as (curve,
@@ -478,10 +457,6 @@ fn nearest_curve(polys: &[Vec<Vec2>], i: usize, e: Vec2, snap: f64, tol: f64, bu
         if j == i {
             continue;
         }
-        // A curve with no segment costs a visit too, so many of them can't multiply the searches.
-        if other.len() < 2 {
-            *budget = budget.checked_sub(1).ok_or(())?;
-        }
         for (k, w) in other.windows(2).enumerate() {
             if *budget == 0 {
                 return Err(());
@@ -583,7 +558,7 @@ pub fn boundary_at_gap(polys: &[Vec<Vec2>], p: Vec2, tol: f64, gap: f64) -> Opti
     let g = build_gap(polys, tol, gap)?;
     let ids = outer_face(&g, p)?;
     let outer = points(&g, &ids)?;
-    let islands = islands(&g, &ids, p)?;
+    let islands = islands(&g, &ids, p);
     let mut outer_sources: Vec<usize> =
         ids.iter().zip(ids.iter().cycle().skip(1)).filter_map(|(&u, &v)| g.edge_src.get(&(u.min(v), u.max(v))).copied()).collect();
     outer_sources.sort_unstable();

crates/render/src/hatch.rs

@@ -367,6 +367,7 @@ pub fn reads_solid(d: &Drawing, h: &Hatch, px: f64) -> bool {
 /// `px`: a pixel in the hatch's units for the level of detail (a dash or dot repeat under two
 /// pixels is one continuous run); 0 = full detail, as plots, exports and picks use. `view`: only
 /// the part of the hatch inside it is generated; `None` = all of it.
+#[cfg(test)]
 pub fn pattern_lines(d: &Drawing, h: &Hatch, loops: &[Vec<Vec2>], px: f64, view: Option<&Bounds2>) -> Vec<Vec<Vec2>> {
     pattern_lines_until(d, h, loops, px, view, None)
 }
@@ -380,6 +381,21 @@ pub(crate) fn pattern_lines_until(
     px: f64,
     view: Option<&Bounds2>,
     cancel: Option<&AtomicBool>,
+) -> Vec<Vec<Vec2>> {
+    pattern_lines_within(d, h, loops, px, view, cancel, MAX_RUNS, MAX_HATCH_WORK)
+}
+
+/// [`pattern_lines_until`] with the most runs and the dash-work allowance given.
+#[allow(clippy::too_many_arguments)]
+fn pattern_lines_within(
+    d: &Drawing,
+    h: &Hatch,
+    loops: &[Vec<Vec2>],
+    px: f64,
+    view: Option<&Bounds2>,
+    cancel: Option<&AtomicBool>,
+    max_runs: usize,
+    work_limit: u64,
 ) -> Vec<Vec<Vec2>> {
     let lines = lines_of(d, h);
     let scale = scale_of(h);
@@ -388,7 +404,7 @@ pub(crate) fn pattern_lines_until(
     // Shared work budget across all families and spans, counting dash-processing steps even when
     // they emit no geometry: gap-only families produce no runs, so `out.len()` alone cannot bound
     // their cost (CWE-400).
-    let mut work: u64 = MAX_HATCH_WORK;
+    let mut work: u64 = work_limit;
     for fam in &lines {
         // A family with dashes but no positive (ink) element can never draw: skip it so its gaps
         // are not swept at all.
@@ -403,8 +419,8 @@ pub(crate) fn pattern_lines_until(
             continue;
         }
         let dashes: Vec<f64> = fam.dashes.iter().map(|d| d * scale).collect();
-        Family { origin, ang, delta, spacing, dashes: &dashes }.sweep(loops, px, view, cancel, &mut out, &mut work);
-        if out.len() >= MAX_RUNS || work == 0 || is_set(cancel) {
+        Family { max_runs, origin, ang, delta, spacing, dashes: &dashes }.sweep(loops, px, view, cancel, &mut out, &mut work);
+        if out.len() >= max_runs || work == 0 || is_set(cancel) {
             break;
         }
     }
@@ -415,6 +431,8 @@ pub(crate) fn pattern_lines_until(
 const SWATCH_REPEATS: f64 = 6.0;
 /// Most runs a swatch holds.
 const MAX_SWATCH_RUNS: usize = 4000;
+/// The dash-work allowance of a swatch (a hatch's is [`MAX_HATCH_WORK`]).
+const MAX_SWATCH_WORK: u64 = 2_000_000;
 
 /// A preview of a pattern for a pattern picker: the runs of its line families `lines` inside the
 /// `side` × `side` square with a corner at the origin, at a scale that shows a few repeats of the
@@ -441,14 +459,19 @@ pub fn pattern_swatch(lines: &[PatternLine], side: f64) -> Vec<Vec<Vec2>> {
         pattern_lines: lines.to_vec(),
     };
     let square = vec![Vec2::new(0.0, 0.0), Vec2::new(side, 0.0), Vec2::new(side, side), Vec2::new(0.0, side)];
-    let mut runs = pattern_lines(&Drawing::default(), &h, &[square], 0.0, None);
+    // The generator stops at the swatch's own limits, so a compact pattern is never made in full
+    // (about a million runs) to keep a few thousand.
+    let mut runs = pattern_lines_within(&Drawing::default(), &h, &[square], 0.0, None, None, MAX_SWATCH_RUNS, MAX_SWATCH_WORK);
     runs.truncate(MAX_SWATCH_RUNS);
+    runs.shrink_to_fit();
     runs
 }
 
 /// One pattern line family, scaled and placed: parallel lines `spacing` apart through `origin`
 /// at angle `ang`, each shifted along itself by `delta`'s along-line part from the last.
 struct Family<'a> {
+    /// Most runs the hatch may hold in all ([`MAX_RUNS`], less for a swatch).
+    max_runs: usize,
     origin: Vec2,
     ang: f64,
     delta: Vec2,
@@ -487,6 +510,13 @@ impl Family<'_> {
 
     /// Intersect a pattern family with boundary loops, respecting view, output, cancellation, and shared dash-work limits.
     fn sweep(&self, loops: &[Vec<Vec2>], px: f64, view: Option<&Bounds2>, cancel: Option<&AtomicBool>, out: &mut Vec<Vec<Vec2>>, work: &mut u64) {
+        // Transforming the boundary is charged before it is done, at the scanline rate (one unit per 8 vertices).
+        let verts: u64 = loops.iter().map(|l| l.len() as u64).sum();
+        let transform_charge = verts / 8 + 1;
+        if transform_charge > *work {
+            return;
+        }
+        *work -= transform_charge;
         let local: Vec<Vec<Vec2>> = loops.iter().map(|l| l.iter().map(|p| self.to_local(*p)).collect()).collect();
         let bb = Bounds2::from_points(local.iter().flatten().copied());
         if bb.is_empty() {
@@ -505,10 +535,17 @@ impl Family<'_> {
         // family draws anything at all).
         let draws = self.dashes.iter().any(|d| *d >= 0.0);
         let solid_line = self.dashes.is_empty() || pat_len < 1e-12 || (px > 0.0 && pat_len < 2.0 * px && draws);
+        // Each scanline visits every boundary edge and sorts the intersections. Charge both the
+        // traversal and an n*ceil(log2(n)) upper bound for sorting, scaled to one unit per eight
+        // operations, whether or not any dash is made.
+        let edges: u64 = local.iter().map(|l| l.len() as u64).sum();
+        let sort_levels = if edges > 1 { (u64::BITS - (edges - 1).leading_zeros()) as u64 } else { 0 };
+        let crossings_charge = edges.saturating_add(edges.saturating_mul(sort_levels)) / 8 + 1;
         for k in k0..=k1 {
-            if out.len() >= MAX_RUNS || *work == 0 || is_set(cancel) {
+            if out.len() >= self.max_runs || crossings_charge > *work || is_set(cancel) {
                 return;
             }
+            *work -= crossings_charge;
             let y = k as f64 * self.spacing;
             let xs = crossings(&local, y);
             let offset = shift_per_line * k as f64;
@@ -538,10 +575,10 @@ impl Family<'_> {
         'outer: while x < x1 {
             for d in self.dashes {
                 guard += 1;
-                *work = work.saturating_sub(1);
-                if guard > 100_000 || out.len() >= MAX_RUNS || *work == 0 {
+                if guard > 100_000 || out.len() >= self.max_runs || *work == 0 {
                     break 'outer;
                 }
+                *work -= 1;
                 let len = d.abs();
                 if *d > 0.0 {
                     let a = x.max(x0);

crates/render/src/linetype_text.rs

@@ -21,11 +21,17 @@ use cadcraft_geom::Vec2;
 /// Upper bound on the texts drawn along one run (hostile scales; `apply` caps the dashes).
 const MAX_TEXTS: usize = 10_000;
 
+/// Upper bound on the points of all the texts of one run: each placement keeps its own copy of the
+/// label's outline, so a long label times [`MAX_TEXTS`] would otherwise be too much to hold.
+const MAX_TEXT_POINTS: usize = 4_000_000;
+
 /// One text element of the pattern, shaped once at the origin.
 struct Element {
     /// Distance from the start of a pattern repeat to the anchor (where the element ends).
     at: f64,
     local: Shaped,
+    /// Points in `local`, each placement's cost against [`MAX_TEXT_POINTS`].
+    points: usize,
     rotation: f64,
     absolute: bool,
     offset: Vec2,
@@ -50,6 +56,7 @@ pub fn texts(d: &Drawing, pts: &[Vec2], lt: &Linetype, scale: f64, min_pattern:
         return out;
     }
     let mut walk = Walk { pts, i: 0, start: 0.0 };
+    let mut points_left = MAX_TEXT_POINTS;
     let mut base = 0.0;
     'repeats: while base <= len {
         for el in &elements {
@@ -57,6 +64,8 @@ pub fn texts(d: &Drawing, pts: &[Vec2], lt: &Linetype, scale: f64, min_pattern:
             if s > len + 1e-9 || out.len() >= MAX_TEXTS {
                 break 'repeats;
             }
+            let Some(left) = points_left.checked_sub(el.points) else { break 'repeats };
+            points_left = left;
             let Some((p, dir)) = walk.at(s) else { break 'repeats };
             let origin = p + dir * el.offset.x + dir.perp() * el.offset.y;
             let rot = if el.absolute { el.rotation } else { dir.angle() + el.rotation };
@@ -93,8 +102,16 @@ fn elements(d: &Drawing, lt: &Linetype, scale: f64) -> Vec<Element> {
         };
         let (local, _) = cadcraft_fonts::place(&font, text, &params);
         let finite = |v: f64| if v.is_finite() { v } else { 0.0 };
+        // Points plus one per stroke and glyph slot, and one for the label itself, so a label of empty
+        // glyphs still has a cost proportional to its size.
+        let points = local.strokes.iter().map(Vec::len).sum::<usize>()
+            + local.glyphs.iter().flatten().map(Vec::len).sum::<usize>()
+            + local.strokes.len()
+            + local.glyphs.len()
+            + 1;
         out.push(Element {
             at,
+            points,
             local,
             rotation: finite(el.rotation),
             absolute: el.absolute,
@@ -175,6 +192,20 @@ mod tests {
         assert!(texts(&d, &[Vec2::ZERO, Vec2::new(2.0, 0.0)], &plain, 1.0, 0.0).is_empty());
     }
 
+    /// A long label repeated along a long run stops at the point allowance, well before MAX_TEXTS.
+    #[test]
+    fn placed_labels_stop_at_the_point_allowance() {
+        let d = Drawing::new_imperial();
+        let mut lt = gas();
+        lt.pattern[1].text = Some("MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM".into());
+        // 0.95 per repeat over 9,000: about 9,500 repeats, under the 50,000 the run is drawn for.
+        let t = texts(&d, &[Vec2::ZERO, Vec2::new(9_000.0, 0.0)], &lt, 1.0, 0.0);
+        let points: usize =
+            t.iter().map(|s| s.strokes.iter().map(Vec::len).sum::<usize>() + s.glyphs.iter().flatten().map(Vec::len).sum::<usize>()).sum();
+        assert!(!t.is_empty() && t.len() < MAX_TEXTS, "{}", t.len());
+        assert!(points <= MAX_TEXT_POINTS, "{points}");
+    }
+
     #[test]
     fn hostile_values_never_panic() {
         let d = Drawing::new_imperial();

crates/render/tests/it/hatch_fill.rs

@@ -211,3 +211,14 @@ fn brick_joints_are_drawn_once_half_a_brick_apart_course_to_course() {
         assert!(next.iter().all(|nx| (nx - x[0]).rem_euclid(500) == 250), "courses {course}/{}: {x:?} {next:?}", course + 1);
     }
 }
+
+/// A pattern with a huge number of tiny dashes makes a swatch of a few thousand runs, stopping
+/// there; and many scanlines over a many-edged boundary are charged to the hatch's work allowance.
+#[test]
+fn compact_patterns_stop_at_the_swatch_limits() {
+    let lines = vec![PatternLine { angle: 0.0, origin: (0.0, 0.0), delta: (0.0, 1.0), dashes: vec![1e-6, -1e-6] }];
+    let started = std::time::Instant::now();
+    let runs = cadcraft_render::pattern_swatch(&lines, 1.0);
+    assert!(!runs.is_empty() && runs.len() <= 4000, "{}", runs.len());
+    assert!(started.elapsed() < std::time::Duration::from_secs(20));
+}