Regions: test a loop's probe only against loops whose box holds it, within a budget

Region::renest tested every loop's probe point against every other
tessellated loop, scanning all of its edges each time, so the work was the
loop count times the total vertex count. It now skips loops whose bounding
box does not hold the probe, and stops once MAX_RENEST_EDGE_VISITS edge tests
have been spent, leaving the flags unchanged and returning false; UNION,
SUBTRACT and INTERSECT then report the regions as too complex to combine, as
they already do for too many boundary pairs (CWE-407).

crates/constraints/src/dof.rs

@@ -11,13 +11,16 @@ use std::collections::HashSet;
 use cadcraft_doc::{Constraint, Drawing, Handle};
 use serde::Serialize;
 
-use crate::model::{Model, Prep};
-use crate::{Comp, MAX_CONSTRAINTS, MAX_EVAL_WORK, SolveError, SolveOptions, build_with, lm};
+use crate::model::Model;
+use crate::{Comp, MAX_CONSTRAINTS, SolveError, SolveOptions, build_budgeted, lm};
 
 /// Most free parameters for which per-object freedom is analysed (null-space basis size).
 const MAX_NULL_COLS: usize = 600;
 /// Largest Jacobian (rows × columns × min) whose rank is computed.
 const MAX_RANK_WORK: f64 = 4e8;
+/// Largest residual-evaluation work (rows × free × per-residual cost, including spline
+/// reconstruction) allowed before building the Jacobian during numerical differentiation.
+const MAX_EVAL_WORK: f64 = 2e9;
 /// Most objects listed in one report.
 const MAX_OBJECTS: usize = 10_000;
 
@@ -136,8 +139,8 @@ fn plural(n: usize, one: &str, many: &str) -> String {
 /// (constrained or not) and the constraint components they belong to.
 pub fn dof(d: &Drawing, handles: &[Handle]) -> Result<DofReport, SolveError> {
     let cons: Vec<&Constraint> = d.constraints.iter().take(MAX_CONSTRAINTS).collect();
-    let mut prep = Prep::new(crate::model::MAX_RIGID_WORK);
-    let (comps, _) = build_with(d, &cons, &SolveOptions::default(), &mut prep)?;
+    let mut members_left = crate::model::MAX_RIGID_WORK;
+    let (comps, _) = build_budgeted(d, &cons, &SolveOptions::default(), &mut members_left)?;
     let want = |h: Handle| handles.is_empty() || handles.contains(&h);
     let mut objects = Vec::new();
     let mut seen = HashSet::new();
@@ -176,7 +179,7 @@ pub fn dof(d: &Drawing, handles: &[Handle]) -> Result<DofReport, SolveError> {
         if seen.contains(&h) {
             continue;
         }
-        let m = Model::build_with(d, &[h], &mut prep);
+        let m = Model::build_budgeted(d, &[h], &mut members_left);
         let Some(s) = m.slots.first() else { continue };
         seen.insert(h);
         free_objects = true;
@@ -234,36 +237,5 @@ mod budget_tests {
         };
         let comp = Comp { model, built: vec![endpoint], weights: vec![1.0; 2], held: Vec::new(), tol: 1e-9 };
         assert!(analyse(&comp).dof.is_none());
-        // Solving it is refused for the same reason, before any Jacobian is built.
-        assert!(matches!(comp.run(None), Err(SolveError::TooLarge)));
-    }
-
-    /// Many Tangent constraints on one large fit spline rebuild it once while being interpreted,
-    /// and the solve is refused by its rebuild budget instead of running.
-    #[test]
-    fn repeated_spline_tangents_rebuild_once_and_solve_is_bounded() {
-        use cadcraft_doc::{Constraint, Line};
-        use cadcraft_geom::Vec3;
-        let mut d = Drawing::default();
-        let pts: Vec<_> = (0..400).map(|i| Vec2::new(i as f64, (i % 3) as f64)).collect();
-        let h = d.add(&Space::Model, Common::default(), EntityKind::Spline(Spline::fit_with(&pts, false, Default::default()))).unwrap();
-        let l =
-            d.add(&Space::Model, Common::default(), EntityKind::Line(Line { a: Vec3::new(-1.0, 0.0, 0.0), b: Vec3::new(-1.0, 5.0, 0.0) })).unwrap();
-        for id in 1..=200 {
-            d.constraints.push(Constraint {
-                id,
-                kind: ConstraintKind::Tangent,
-                refs: vec![GeomRef::whole(h), GeomRef::whole(l)],
-                name: String::new(),
-                expr: String::new(),
-            });
-        }
-        let cons: Vec<&Constraint> = d.constraints.iter().collect();
-        let (comps, skipped) = crate::build(&d, &cons, &SolveOptions::default()).unwrap();
-        assert!(skipped.is_empty());
-        let comp = comps.first().unwrap();
-        assert_eq!(comp.built.len(), 200);
-        assert!(matches!(comp.run(None), Err(SolveError::TooLarge)));
-        assert!(crate::purge_invalid(&mut d).is_empty());
     }
 }

crates/constraints/src/lib.rs

@@ -41,7 +41,7 @@ pub use dof::{DofReport, DofStatus, ObjectDof, dof};
 pub use expr::{Env, ExprError};
 pub use model::{ref_points, rigid_points, supported};
 
-use model::{Model, Prep};
+use model::Model;
 use residual::{Built, Form};
 
 /// Most constraints one drawing may hold.
@@ -50,11 +50,6 @@ pub const MAX_CONSTRAINTS: usize = 5000;
 const MAX_CONFLICT_PROBES: usize = 48;
 /// Solver iterations.
 const MAX_ITER: usize = 200;
-/// Largest residual-evaluation work (including spline rebuilds) one numerical Jacobian may take,
-/// shared by solving, redundancy checks and DOF analysis.
-pub(crate) const MAX_EVAL_WORK: f64 = 2e9;
-/// Residual evaluations a solver iteration makes besides its Jacobian (damped trial steps).
-const TRIAL_EVALS: f64 = 14.0;
 
 #[derive(Clone, Debug, PartialEq, thiserror::Error)]
 pub enum SolveError {
@@ -256,41 +251,12 @@ impl Comp {
     pub(crate) fn rows(&self, skip: Option<usize>) -> usize {
         self.built.iter().enumerate().filter(|(i, _)| Some(*i) != skip).map(|(_, b)| b.rows).sum()
     }
-    /// Work of one solver iteration's residual evaluations over `free`: every residual twice per
-    /// free parameter, plus a spline rebuild each time a spline's own defining points move (rebuilds
-    /// are shared by residuals at the same points, see [`Model`]).
-    pub(crate) fn eval_work(&self, free: &[usize], skip: Option<usize>) -> f64 {
-        let rows = self.rows(skip) as f64;
-        let evals = 2.0 * free.len() as f64 + TRIAL_EVALS;
-        let mut splines: Vec<Handle> = Vec::new();
-        for (i, b) in self.built.iter().enumerate() {
-            if Some(i) != skip && b.spline_reconstruct_cost(&self.model) > 0.0 {
-                splines.extend(b.refs.iter().map(|r| r.handle).filter(|h| self.model.spline_reconstruct_cost(*h) > 0.0));
-            }
-        }
-        splines.sort_unstable();
-        splines.dedup();
-        let rebuilds: f64 = splines
-            .iter()
-            .filter_map(|h| self.model.slot(*h))
-            .map(|s| {
-                let own = free.iter().filter(|j| (s.off..s.off + s.len).contains(*j)).count() as f64;
-                (2.0 * own + TRIAL_EVALS + 1.0) * self.model.spline_reconstruct_cost(s.handle)
-            })
-            .sum();
-        evals * rows + rebuilds
-    }
     fn run(&self, skip: Option<usize>) -> Result<lm::Outcome, SolveError> {
         let free = self.free(skip);
         let rows = self.rows(skip);
         if rows > lm::MAX_ROWS || (rows as f64) * (rows as f64) * (free.len() as f64) > 4e8 {
             return Err(SolveError::TooLarge);
         }
-        // Numerical differentiation rebuilds a fit spline through a dense solve for every move of
-        // its own fit points: refuse before iterating when that alone is too much (CWE-407).
-        if self.eval_work(&free, skip) > MAX_EVAL_WORK {
-            return Err(SolveError::TooLarge);
-        }
         let f = |x: &[f64], out: &mut Vec<f64>| self.eval(x, out, skip);
         let mut o = lm::solve(&f, &self.model.x0, &free, &self.weights, self.tol, MAX_ITER);
         // A solution the ellipses would be stored differently from (axes swapped, minor axis
@@ -444,24 +410,24 @@ fn slot_scales(model: &Model, s: &model::Slot) -> Vec<(usize, f64)> {
 
 /// Build the component systems. Constraints that cannot be interpreted are returned as skipped.
 pub(crate) fn build(d: &Drawing, cons: &[&Constraint], opts: &SolveOptions) -> Result<(Vec<Comp>, Vec<(u32, String)>), SolveError> {
-    build_with(d, cons, opts, &mut Prep::new(model::MAX_RIGID_WORK))
+    let mut members_left = model::MAX_RIGID_WORK;
+    build_budgeted(d, cons, opts, &mut members_left)
 }
 
-/// Build constraint components sharing one caller-owned geometry preparation (block sampling and
-/// its member budget, spline rebuilds) between every model.
+/// Build constraint components with one caller-owned rigid-member sampling budget shared by every model.
 /// Return constraints that cannot be interpreted as skipped entries.
-pub(crate) fn build_with(
+pub(crate) fn build_budgeted(
     d: &Drawing,
     cons: &[&Constraint],
     opts: &SolveOptions,
-    prep: &mut Prep,
+    members_left: &mut usize,
 ) -> Result<(Vec<Comp>, Vec<(u32, String)>), SolveError> {
     let mut e = env(d);
     let mut skipped = Vec::new();
     let mut comps = Vec::new();
     for group in components(cons) {
         let handles: Vec<Handle> = group.iter().flat_map(|c| c.refs.iter().map(|r| r.handle)).collect();
-        let mut model = Model::build_with(d, &handles, prep);
+        let mut model = Model::build_budgeted(d, &handles, members_left);
         let mut built = Vec::new();
         for c in group {
             let target = if c.kind.is_dimensional() { constraint_value(&mut e, c)? } else { 0.0 };
@@ -674,11 +640,6 @@ pub fn all_satisfied(d: &Drawing) -> bool {
 
 /// Check that a constraint's references make sense for its type.
 pub fn validate(d: &Drawing, c: &Constraint) -> Result<(), String> {
-    validate_with(d, c, &mut Prep::new(model::MAX_RIGID_WORK))
-}
-
-/// [`validate`] sharing block samples and spline rebuilds with other checks of the same drawing.
-fn validate_with(d: &Drawing, c: &Constraint, prep: &mut Prep) -> Result<(), String> {
     let handles: Vec<Handle> = c.refs.iter().map(|r| r.handle).collect();
     for h in &handles {
         match d.entity(*h) {
@@ -687,7 +648,7 @@ fn validate_with(d: &Drawing, c: &Constraint, prep: &mut Prep) -> Result<(), Str
             _ => {}
         }
     }
-    let mut model = Model::build_with(d, &handles, prep);
+    let mut model = Model::build(d, &handles);
     interpret(c, &mut model, 1.0).map(|_| ())
 }
 
@@ -704,12 +665,7 @@ pub fn measure(d: &Drawing, kind: ConstraintKind, refs: &[GeomRef]) -> Result<f6
 /// Returns the removed ids.
 pub fn purge_invalid(d: &mut Drawing) -> Vec<u32> {
     let mut gone = Vec::new();
-    // One preparation for every check: each block is sampled and each spline rebuilt once,
-    // however many constraints refer to them (CWE-407). Its member budget is not shared, so
-    // a constraint is never dropped because earlier ones spent it: every block is still
-    // examined at most once, up to its own member limit.
-    let mut prep = Prep::new(usize::MAX);
-    let keep: Vec<bool> = d.constraints.iter().map(|c| validate_with(d, c, &mut prep).is_ok()).collect();
+    let keep: Vec<bool> = d.constraints.iter().map(|c| validate(d, c).is_ok()).collect();
     let mut i = 0;
     d.constraints.retain(|c| {
         let k = keep.get(i).copied().unwrap_or(true);
@@ -796,9 +752,6 @@ pub fn add(d: &mut Drawing, mut c: Constraint, opts: &SolveOptions) -> Result<u3
         && comp.built.get(pos).is_some_and(|b| b.form == Form::Lock)
     {
         let before = comp.free(Some(pos));
-        if comp.eval_work(&before, Some(pos)) > MAX_EVAL_WORK {
-            return Err(SolveError::TooLarge);
-        }
         let after = comp.free(None);
         let locked: Vec<usize> = before.iter().enumerate().filter(|(_, j)| !after.contains(j)).map(|(k, _)| k).collect();
         let rows_old = comp.rows(Some(pos));

crates/constraints/src/model.rs

@@ -14,11 +14,9 @@
 //! Constraints may append auxiliary unknowns after the entity parameters (contact parameters of
 //! a tangency between curves); they are never written back.
 
-use std::cell::RefCell;
 use std::collections::HashMap;
-use std::rc::Rc;
 
-use cadcraft_doc::{Block, Drawing, EntityKind, GeomRef, Handle, Insert, Sub};
+use cadcraft_doc::{Drawing, EntityKind, GeomRef, Handle, Insert, Sub};
 use cadcraft_geom::{Spline as GSpline, Vec2, ccw_sweep};
 
 use crate::curves::{Ell, Frame, clamped, spline_end};
@@ -72,9 +70,6 @@ pub(crate) struct Slot {
     pub len: usize,
 }
 
-/// The spline last rebuilt for each handle, with the defining points it was rebuilt from.
-type SplineCache = HashMap<Handle, (Vec<Vec2>, Rc<GSpline>)>;
-
 #[derive(Clone, Debug, Default)]
 pub(crate) struct Model {
     pub slots: Vec<Slot>,
@@ -84,75 +79,20 @@ pub(crate) struct Model {
     splines: HashMap<Handle, GSpline>,
     /// Block reference rigid points relative to the insertion point at rotation 0.
     rigid: HashMap<Handle, Vec<Vec2>>,
-    /// Rebuilt splines, shared with every model of the same [`Prep`]: residuals that ask for the
-    /// same spline at the same defining points (several constraints on one spline, or derivatives
-    /// taken along other objects' parameters) reuse one rebuild instead of a dense solve each.
-    rebuilt: Rc<RefCell<SplineCache>>,
-}
-
-/// Geometry preparation shared by every model built for one operation (a solve, a DOF report, a
-/// purge): rigid samples per block, a case-insensitive block-name index and rebuilt splines. A
-/// block referenced by many Inserts is sampled once, an unknown block name costs one hashed
-/// lookup, and a spline referenced by many constraints is rebuilt once (CWE-407).
-#[derive(Debug)]
-pub(crate) struct Prep {
-    /// Block members that may still be examined across the operation.
-    members_left: usize,
-    /// Block-local rigid samples by the name an Insert gives (`None`: no such block).
-    blocks: HashMap<String, Option<Rc<[Vec2]>>>,
-    /// Lower-cased block name to the stored name it resolves to, built on the first exact miss.
-    folded: Option<HashMap<String, String>>,
-    rebuilt: Rc<RefCell<SplineCache>>,
-}
-
-impl Prep {
-    /// Preparation that may examine at most `members` block members in all.
-    pub(crate) fn new(members: usize) -> Prep {
-        Prep { members_left: members, blocks: HashMap::new(), folded: None, rebuilt: Rc::default() }
-    }
-
-    /// The block an Insert names, as [`Drawing::block`] resolves it (exact name, else the first
-    /// stored name equal ignoring ASCII case), without scanning every block on each miss.
-    fn resolve<'d>(&mut self, d: &'d Drawing, name: &str) -> Option<&'d Block> {
-        if let Some(b) = d.blocks.get(name) {
-            return Some(b);
-        }
-        let folded = self.folded.get_or_insert_with(|| {
-            let mut m = HashMap::with_capacity(d.blocks.len());
-            for k in d.blocks.keys() {
-                m.entry(k.to_ascii_lowercase()).or_insert_with(|| k.clone());
-            }
-            m
-        });
-        d.blocks.get(folded.get(&name.to_ascii_lowercase())?).map(|b| &**b)
-    }
-
-    /// Finite characteristic points of a block in its own coordinates, sampled once per name.
-    fn block_points(&mut self, d: &Drawing, name: &str) -> Option<Rc<[Vec2]>> {
-        if let Some(s) = self.blocks.get(name) {
-            return s.clone();
-        }
-        let sampled = self.resolve(d, name).map(|b| sample_block(b, &mut self.members_left));
-        self.blocks.insert(name.to_string(), sampled.clone());
-        sampled
-    }
-
-    /// World positions of an Insert's rigid points, at most [`MAX_RIGID_POINTS`].
-    fn rigid_points(&mut self, d: &Drawing, ins: &Insert) -> Vec<Vec2> {
-        let Some(local) = self.block_points(d, &ins.block) else { return Vec::new() };
-        let Some(block) = self.resolve(d, &ins.block) else { return Vec::new() };
-        let m = ins.transform(block.base.xy());
-        local.iter().map(|p| m.apply(*p)).filter(|p| p.is_finite()).take(MAX_RIGID_POINTS).collect()
-    }
 }
 
 impl Model {
     /// Work for a spline that an endpoint residual actually reconstructs. Fit interpolation
     /// uses dense Gaussian elimination (cubic); control splines clone and evaluate their template.
     pub(crate) fn spline_reconstruct_cost(&self, handle: Handle) -> f64 {
-        let Some(Shape::Spline { n, fit, .. }) = self.slot(handle).map(|s| s.shape) else { return 0.0 };
-        let n = n as f64;
-        if fit { n * n * n } else { n * n }
+        let Some(s) = self.splines.get(&handle) else { return 0.0 };
+        let n = s.fit.len() as f64;
+        if fit_mode(s) {
+            n * n * n
+        } else {
+            let n = s.control.len() as f64;
+            n * n
+        }
     }
 }
 
@@ -175,18 +115,23 @@ pub fn supported(kind: &EntityKind) -> bool {
 /// centres, vertices, nested insertion points) of the block's own objects, at most
 /// [`MAX_RIGID_POINTS`]. Nested blocks are not entered.
 pub fn rigid_points(d: &Drawing, ins: &Insert) -> Vec<Vec2> {
-    Prep::new(MAX_RIGID_MEMBERS).rigid_points(d, ins)
+    let mut members_left = MAX_RIGID_MEMBERS;
+    rigid_points_budgeted(d, ins, &mut members_left)
 }
 
-/// Sample a block's finite characteristic points in block coordinates, within the per-block
-/// member limit and the caller-shared `members_left`. Members that contribute no points still
-/// consume traversal work; nested blocks are not entered.
-fn sample_block(block: &Block, members_left: &mut usize) -> Rc<[Vec2]> {
+/// Sample finite block points within per-insert and caller-shared member limits.
+/// Members that contribute no points still consume traversal work; nested blocks are not entered.
+fn rigid_points_budgeted(d: &Drawing, ins: &Insert, members_left: &mut usize) -> Vec<Vec2> {
+    let Some(block) = d.block(&ins.block) else { return Vec::new() };
+    let m = ins.transform(block.base.xy());
     let mut out = Vec::new();
     // Bound the members examined, not only the points collected: entities that contribute no
-    // points (Text, Ray, …) still cost traversal (CWE-407).
-    for (examined, e) in block.entities.iter().enumerate() {
-        if out.len() >= MAX_RIGID_POINTS || examined >= MAX_RIGID_MEMBERS || *members_left == 0 {
+    // points (Text, Ray, …) still cost traversal, so a block full of them — scanned again for
+    // every Insert — would otherwise be unbounded (CWE-407).
+    let mut examined = 0usize;
+    for e in block.entities.iter() {
+        examined += 1;
+        if out.len() >= MAX_RIGID_POINTS || examined > MAX_RIGID_MEMBERS || *members_left == 0 {
             break;
         }
         *members_left -= 1;
@@ -203,10 +148,10 @@ fn sample_block(block: &Block, members_left: &mut usize) -> Rc<[Vec2]> {
             EntityKind::LwPolyline(p) => p.vertices.iter().take(MAX_RIGID_POINTS).map(|v| v.p).collect(),
             _ => Vec::new(),
         };
-        out.extend(pts.into_iter().filter(|p| p.is_finite()));
+        out.extend(pts.into_iter().map(|p| m.apply(p)).filter(|p| p.is_finite()));
     }
     out.truncate(MAX_RIGID_POINTS);
-    out.into()
+    out
 }
 
 /// Constraint points of an object as the solver sees them (`Sub`, position): end points,
@@ -242,12 +187,13 @@ fn fit_mode(s: &GSpline) -> bool {
 impl Model {
     /// Build a model for the given entities. Unsupported or missing entities are skipped.
     pub fn build(d: &Drawing, handles: &[Handle]) -> Model {
-        Self::build_with(d, handles, &mut Prep::new(MAX_RIGID_WORK))
+        let mut members_left = MAX_RIGID_WORK;
+        Self::build_budgeted(d, handles, &mut members_left)
     }
 
     /// Add the parameters of one supported entity to `m`, and return its shape; `None` when it is
     /// left out (too large, degenerate or unsupported).
-    fn add_params(m: &mut Model, d: &Drawing, h: Handle, kind: &EntityKind, off: usize, prep: &mut Prep) -> Option<Shape> {
+    fn add_params(m: &mut Model, d: &Drawing, h: Handle, kind: &EntityKind, off: usize, members_left: &mut usize) -> Option<Shape> {
         let shape = match kind {
             EntityKind::Line(l) => {
                 m.x0.extend([l.a.x, l.a.y, l.b.x, l.b.y]);
@@ -297,22 +243,15 @@ impl Model {
                 // fit point; a control polygon's ends are its first and last points when the
                 // knots are clamped.
                 let ends = !sp.closed && (fit || (clamped(sp, false) && clamped(sp, true)));
-                // Keep only what rebuilding reads, so each rebuild copies no unused data: missing
-                // weights default to 1 in eval and only excess weights are unused; a control
-                // spline's fit points are dropped when its control points move (write_back), and
-                // a fit spline is rebuilt from its parameters, not from its old control net.
-                let mut kept = if fit {
-                    GSpline { fit_opts: sp.fit_opts, closed: sp.closed, ..GSpline::default() }
-                } else {
-                    GSpline { fit: Vec::new(), ..sp.clone() }
-                };
+                // Missing weights default to 1 in eval; only excess weights are unused.
+                let mut kept = sp.clone();
                 kept.weights.truncate(kept.control.len());
                 m.splines.insert(h, kept);
                 Shape::Spline { n, fit, ends }
             }
             EntityKind::Insert(ins) => {
                 let base = Vec2::new(ins.insert.x, ins.insert.y);
-                let pts: Vec<Vec2> = prep.rigid_points(d, ins).into_iter().map(|p| (p - base).rotate(-ins.rotation)).collect();
+                let pts: Vec<Vec2> = rigid_points_budgeted(d, ins, members_left).into_iter().map(|p| (p - base).rotate(-ins.rotation)).collect();
                 m.x0.extend([ins.insert.x, ins.insert.y, ins.rotation]);
                 let n = pts.len();
                 m.rigid.insert(h, pts);
@@ -323,17 +262,16 @@ impl Model {
         Some(shape)
     }
 
-    /// Build solver parameters for supported entities, sharing block sampling, its member budget
-    /// and spline rebuilds with every other model built from `prep`.
-    pub(crate) fn build_with(d: &Drawing, handles: &[Handle], prep: &mut Prep) -> Model {
-        let mut m = Model { rebuilt: Rc::clone(&prep.rebuilt), ..Model::default() };
+    /// Build solver parameters for supported entities while sharing rigid-member sampling work with other models.
+    pub(crate) fn build_budgeted(d: &Drawing, handles: &[Handle], members_left: &mut usize) -> Model {
+        let mut m = Model::default();
         for &h in handles {
             if m.index.contains_key(&h) {
                 continue;
             }
             let Some(e) = d.entity(h) else { continue };
             let off = m.x0.len();
-            let Some(shape) = Self::add_params(&mut m, d, h, &e.kind, off, prep) else { continue };
+            let Some(shape) = Self::add_params(&mut m, d, h, &e.kind, off, members_left) else { continue };
             if m.x0.len() > MAX_PARAMS || m.x0.get(off..).unwrap_or(&[]).iter().any(|v| !v.is_finite()) {
                 m.x0.truncate(off);
                 continue;
@@ -435,20 +373,18 @@ impl Model {
         self.slot(r.handle).is_some_and(|s| matches!(s.shape, Shape::Spline { .. }))
     }
 
-    /// The spline of a reference with the defining points taken from `x`. The last rebuild of
-    /// each spline is kept, so asking again at the same points costs a comparison, not a rebuild.
-    fn spline(&self, x: &[f64], s: &Slot) -> Option<Rc<GSpline>> {
+    /// The spline of a reference with the defining points taken from `x`.
+    fn spline(&self, x: &[f64], s: &Slot) -> Option<GSpline> {
         let Shape::Spline { n, fit, .. } = s.shape else { return None };
         let t = self.splines.get(&s.handle)?;
         let pts = (0..n).map(|i| p2(x, s.off + 2 * i)).collect::<Option<Vec<_>>>()?;
-        if let Some((at, sp)) = self.rebuilt.borrow().get(&s.handle)
-            && *at == pts
-        {
-            return Some(Rc::clone(sp));
-        }
-        let sp = Rc::new(if fit { t.refit(&pts, t.closed) } else { GSpline { control: pts.clone(), ..t.clone() } });
-        self.rebuilt.borrow_mut().insert(s.handle, (pts, Rc::clone(&sp)));
-        Some(sp)
+        Some(if fit {
+            t.refit(&pts, t.closed)
+        } else {
+            let mut sp = t.clone();
+            sp.control = pts;
+            sp
+        })
     }
 
     /// The start (`at_end` false) or end of a curve reference, in the curve's own direction:
@@ -485,7 +421,7 @@ impl Model {
                 let e = self.ell_at(x, o, true)?;
                 e.frame(if at_end { e.t1 } else { e.t0 })
             }
-            (Shape::Spline { ends: true, .. }, Sub::Whole | Sub::Start | Sub::End) => spline_end(&*self.spline(x, s)?, at_end),
+            (Shape::Spline { ends: true, .. }, Sub::Whole | Sub::Start | Sub::End) => spline_end(&self.spline(x, s)?, at_end),
             _ => None,
         }
     }
@@ -654,8 +590,7 @@ impl Model {
             }
             let shape = s.shape;
             // A control-point spline loses its fit data once its control points move.
-            let spline = self.spline(x, s).map(|sp| {
-                let mut sp = GSpline::clone(&sp);
+            let spline = self.spline(x, s).map(|mut sp| {
                 if matches!(shape, Shape::Spline { fit: false, .. }) {
                     sp.fit.clear();
                 }
@@ -777,21 +712,21 @@ mod budget_tests {
         }
     }
 
-    fn add_block(d: &mut Drawing, name: &str, lines: usize) {
-        let mut block = Block::new(name);
-        for _ in 0..lines {
+    /// A second model receives no sampled block points after the first model spends the shared member budget.
+    #[test]
+    fn rigid_sampling_budget_is_shared_between_models() {
+        let mut d = Drawing::default();
+        let mut block = Block::new("BAR");
+        for _ in 0..3 {
             block.entities.push(Entity {
                 handle: d.new_handle(),
                 common: Common::default(),
                 kind: EntityKind::Line(Line { a: Vec3::ZERO, b: Vec3::new(1.0, 0.0, 0.0) }),
             });
         }
-        d.blocks.insert(name.into(), Arc::new(block));
-    }
-
-    fn insert(block: &str) -> Insert {
-        Insert {
-            block: block.into(),
+        d.blocks.insert("BAR".into(), Arc::new(block));
+        let ins = Insert {
+            block: "BAR".into(),
             insert: Vec3::ZERO,
             scale: Vec3::new(1.0, 1.0, 1.0),
             rotation: 0.0,
@@ -800,79 +735,13 @@ mod budget_tests {
             rows: 1,
             col_spacing: 0.0,
             row_spacing: 0.0,
-        }
-    }
-
-    fn add_insert(d: &mut Drawing, block: &str) -> Handle {
-        d.add(&Space::Model, Common::default(), EntityKind::Insert(insert(block))).unwrap()
-    }
-
-    /// The member budget is shared by every model of one preparation, and a block it already
-    /// sampled is reused by later Inserts without examining its members again.
-    #[test]
-    fn rigid_sampling_budget_is_shared_and_blocks_sampled_once() {
-        let mut d = Drawing::default();
-        add_block(&mut d, "BAR", 3);
-        add_block(&mut d, "BAZ", 3);
-        let (bar, baz, bar2) = (add_insert(&mut d, "BAR"), add_insert(&mut d, "BAZ"), add_insert(&mut d, "BAR"));
-        let mut prep = Prep::new(2);
-        let first = Model::build_with(&d, &[bar], &mut prep);
-        assert_eq!(first.rigid[&bar].len(), 4);
-        assert_eq!(prep.members_left, 0);
-        let other = Model::build_with(&d, &[baz], &mut prep);
-        assert!(other.rigid[&baz].is_empty());
-        let again = Model::build_with(&d, &[bar2], &mut prep);
-        assert_eq!(again.rigid[&bar2].len(), 4);
-    }
-
-    /// Block names resolve ignoring ASCII case, as `Drawing::block` does, through one index.
-    #[test]
-    fn block_names_resolve_ignoring_case() {
-        let mut d = Drawing::default();
-        add_block(&mut d, "Bar", 2);
-        let (lower, missing) = (add_insert(&mut d, "bAR"), add_insert(&mut d, "nope"));
-        let mut prep = Prep::new(MAX_RIGID_WORK);
-        let m = Model::build_with(&d, &[lower, missing], &mut prep);
-        assert_eq!(m.rigid[&lower].len(), 4);
-        assert!(m.rigid[&missing].is_empty());
-        assert!(prep.folded.as_ref().is_some_and(|f| f.len() == 1));
-        assert_eq!(rigid_points(&d, &insert("BAR")).len(), 4);
-    }
-
-    /// A spline asked for again at the same defining points is not rebuilt, also from another
-    /// model of the same preparation; moved points rebuild it.
-    #[test]
-    fn spline_rebuilds_are_reused_at_the_same_points() {
-        let mut d = Drawing::default();
-        let pts: Vec<Vec2> = (0..6).map(|i| Vec2::new(i as f64, (i % 2) as f64)).collect();
-        let h = d.add(&Space::Model, Common::default(), EntityKind::Spline(GSpline::fit_with(&pts, false, Default::default()))).unwrap();
-        let mut prep = Prep::new(MAX_RIGID_WORK);
-        let a = Model::build_with(&d, &[h], &mut prep);
-        let b = Model::build_with(&d, &[h], &mut prep);
-        let (sa, sb) = (a.slot(h).unwrap(), b.slot(h).unwrap());
-        assert!(matches!(sa.shape, Shape::Spline { fit: true, .. }));
-        let first = a.spline(&a.x0, sa).unwrap();
-        assert!(Rc::ptr_eq(&first, &a.spline(&a.x0, sa).unwrap()));
-        assert!(Rc::ptr_eq(&first, &b.spline(&b.x0, sb).unwrap()));
-        let mut moved = a.x0.clone();
-        moved[1] += 0.5;
-        let other = a.spline(&moved, sa).unwrap();
-        assert!(!Rc::ptr_eq(&first, &other));
-        assert_eq!(other.fit[0], Vec2::new(0.0, 0.5));
-    }
-
-    /// A control spline's template keeps no fit points and no excess weights.
-    #[test]
-    fn control_template_drops_unused_data() {
-        let mut d = Drawing::default();
-        let mut sp = GSpline::from_control(vec![Vec2::ZERO, Vec2::new(1.0, 2.0), Vec2::new(3.0, 0.0), Vec2::new(4.0, 1.0)], 3);
-        sp.fit = vec![Vec2::ZERO; 10_000];
-        sp.fit_opts.tolerance = 0.5;
-        sp.weights = vec![1.0; 10_000];
-        let h = d.add(&Space::Model, Common::default(), EntityKind::Spline(sp)).unwrap();
-        let m = Model::build(&d, &[h]);
-        let t = &m.splines[&h];
-        assert!(t.fit.is_empty());
-        assert_eq!(t.weights.len(), 4);
+        };
+        let h = d.add(&Space::Model, Common::default(), EntityKind::Insert(ins)).unwrap();
+        let mut budget = 2;
+        let first = Model::build_budgeted(&d, &[h], &mut budget);
+        assert_eq!(first.rigid[&h].len(), 4);
+        assert_eq!(budget, 0);
+        let next = Model::build_budgeted(&d, &[h], &mut budget);
+        assert!(next.rigid[&h].is_empty());
     }
 }

crates/doc/src/entity/region.rs

@@ -9,6 +9,9 @@ use super::HatchLoop;
 /// Most loops one region has (hostile files and edits).
 pub const MAX_REGION_LOOPS: usize = 10_000;
 
+/// Most polygon edges [`Region::renest`] tests, over all its point-in-loop tests.
+pub const MAX_RENEST_EDGE_VISITS: usize = 50_000_000;
+
 #[derive(Clone, Debug, Default, PartialEq, Serialize, Deserialize)]
 pub struct Region {
     /// Closed loops with bulges; `outer` false for islands.
@@ -76,20 +79,49 @@ impl Region {
     }
 
     /// Set each loop's `outer` flag from how deeply other loops enclose it: an even depth is
-    /// an outer loop, odd an island.
-    pub fn renest(&mut self) {
+    /// an outer loop, odd an island. `false`, with the flags left as they were, when that takes
+    /// more than [`MAX_RENEST_EDGE_VISITS`] polygon edge tests.
+    #[must_use]
+    pub fn renest(&mut self) -> bool {
         let polys = self.tessellate(self.fine_tol());
-        let depth: Vec<usize> = polys
+        // A loop's probe can only be inside loops whose box holds it: test only those. A box with
+        // a non-finite corner says nothing (an edge through a non-finite point never counts, so
+        // such a polygon need not be closed), so its loop is always tested.
+        let boxes: Vec<Option<Bounds2>> = polys
             .iter()
-            .enumerate()
-            .map(|(i, l)| {
-                let Some(p) = probe(l) else { return 0 };
-                polys.iter().enumerate().filter(|(j, o)| *j != i && point_in_polygon(o, p)).count()
+            .map(|l| {
+                let b = Bounds2::from_points(l.iter().copied());
+                (l.iter().all(|p| p.is_finite()) && b.min.is_finite() && b.max.is_finite()).then_some(b)
             })
             .collect();
+        let mut visits = 0usize;
+        let mut depth = Vec::with_capacity(polys.len());
+        for (i, l) in polys.iter().enumerate() {
+            let Some(p) = probe(l) else {
+                depth.push(0);
+                continue;
+            };
+            let mut d = 0;
+            for (j, (o, b)) in polys.iter().zip(&boxes).enumerate() {
+                if j == i || b.is_some_and(|b| !b.contains(p)) {
+                    continue;
+                }
+                // Each loop against every other is loops x vertices: bounded so a region of many
+                // large nested loops cannot hold the thread (CWE-407).
+                visits = visits.saturating_add(o.len());
+                if visits > MAX_RENEST_EDGE_VISITS {
+                    return false;
+                }
+                if point_in_polygon(o, p) {
+                    d += 1;
+                }
+            }
+            depth.push(d);
+        }
         for (l, d) in self.loops.iter_mut().zip(depth) {
             l.outer = d % 2 == 0;
         }
+        true
     }
 
     /// Area, perimeter, bounding box, centroid and second moments (outer loops counted
@@ -128,3 +160,37 @@ fn probe(l: &[Vec2]) -> Option<Vec2> {
         (a.dist(b) > 1e-12).then(|| (a + b) * 0.5).filter(|m| m.is_finite())
     })
 }
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    fn square(c: f64, half: f64, n: usize, outer: bool) -> HatchLoop {
+        // `n` vertices along the bottom edge, then the other three corners.
+        let mut vertices: Vec<PolyVertex> =
+            (0..n).map(|k| PolyVertex::new(Vec2::new(c - half + 2.0 * half * k as f64 / n as f64, c - half))).collect();
+        vertices.extend([Vec2::new(c + half, c - half), Vec2::new(c + half, c + half), Vec2::new(c - half, c + half)].map(PolyVertex::new));
+        HatchLoop { vertices, outer, sources: Vec::new() }
+    }
+
+    #[test]
+    fn renest_sets_depth_parity_and_skips_loops_far_away() {
+        // Three nested squares, and one beside them.
+        let mut r =
+            Region { loops: vec![square(0.0, 3.0, 1, false), square(0.0, 2.0, 1, false), square(0.0, 1.0, 1, false), square(10.0, 1.0, 1, false)] };
+        assert!(r.renest());
+        assert_eq!(r.loops.iter().map(|l| l.outer).collect::<Vec<_>>(), [true, false, true, true]);
+    }
+
+    #[test]
+    fn renest_of_many_large_nested_loops_stops_at_its_budget() {
+        // Concentric loops of many vertices each: each probe is inside the box of every larger
+        // loop (about loops² / 2 pairs), so each of those tests is a full polygon scan.
+        let loops = 300;
+        let n = 3 * MAX_RENEST_EDGE_VISITS / (loops * loops);
+        let mut r = Region { loops: (0..loops).map(|i| square(0.0, 1.0 + i as f64, n, false)).collect() };
+        let before = r.clone();
+        assert!(!r.renest());
+        assert_eq!(r, before, "flags left as they were");
+    }
+}

crates/engine/src/cmd/inquiry/regions.rs

@@ -128,7 +128,9 @@ fn combine(a: &Region, b: &Region, op: Op) -> Result<Option<Region>> {
     }
     loops.retain(|l| l.vertices.len() >= 2);
     let mut r = Region { loops };
-    r.renest();
+    if !r.renest() {
+        return Err(other("These regions are too complex to combine."));
+    }
     Ok(Some(r))
 }