constraints: share geometry preparation across an operation and budget spline rebuilds

Endpoint residuals rebuilt a fit spline through a dense interpolation
solve on every evaluation, so many Tangent/Smooth constraints on one
spline, or numerical differentiation along other objects' parameters,
repeated identical O(n^3) rebuilds; solving had no budget for them.
purge_invalid built a fresh model per constraint, re-sampling the same
block for every reference, and an Insert naming no block scanned every
block definition case-insensitively.

- Models built for one operation share a Prep: block samples are taken
  once per block (in block coordinates, transformed per Insert), block
  names resolve through a lazily built case-insensitive index, and the
  last rebuild of each spline is reused at the same defining points.
- Comp::run and the Fix redundancy check refuse a system whose
  per-iteration residual work, including spline rebuilds, exceeds the
  limit DOF analysis already applied (MAX_EVAL_WORK).
- Spline templates keep only what a rebuild reads: no fit points for a
  control spline, no control net for a fit spline.
- purge_invalid validates every constraint with one Prep.

crates/constraints/src/dof.rs

@@ -11,16 +11,13 @@ use std::collections::HashSet;
 use cadcraft_doc::{Constraint, Drawing, Handle};
 use serde::Serialize;
 
-use crate::model::Model;
-use crate::{Comp, MAX_CONSTRAINTS, SolveError, SolveOptions, build_budgeted, lm};
+use crate::model::{Model, Prep};
+use crate::{Comp, MAX_CONSTRAINTS, MAX_EVAL_WORK, SolveError, SolveOptions, build_with, 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;
 
@@ -139,8 +136,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 members_left = crate::model::MAX_RIGID_WORK;
-    let (comps, _) = build_budgeted(d, &cons, &SolveOptions::default(), &mut members_left)?;
+    let mut prep = Prep::new(crate::model::MAX_RIGID_WORK);
+    let (comps, _) = build_with(d, &cons, &SolveOptions::default(), &mut prep)?;
     let want = |h: Handle| handles.is_empty() || handles.contains(&h);
     let mut objects = Vec::new();
     let mut seen = HashSet::new();
@@ -179,7 +176,7 @@ pub fn dof(d: &Drawing, handles: &[Handle]) -> Result<DofReport, SolveError> {
         if seen.contains(&h) {
             continue;
         }
-        let m = Model::build_budgeted(d, &[h], &mut members_left);
+        let m = Model::build_with(d, &[h], &mut prep);
         let Some(s) = m.slots.first() else { continue };
         seen.insert(h);
         free_objects = true;
@@ -237,5 +234,36 @@ 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;
+use model::{Model, Prep};
 use residual::{Built, Form};
 
 /// Most constraints one drawing may hold.
@@ -50,6 +50,11 @@ 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 {
@@ -251,12 +256,41 @@ 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
@@ -410,24 +444,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> {
-    let mut members_left = model::MAX_RIGID_WORK;
-    build_budgeted(d, cons, opts, &mut members_left)
+    build_with(d, cons, opts, &mut Prep::new(model::MAX_RIGID_WORK))
 }
 
-/// Build constraint components with one caller-owned rigid-member sampling budget shared by every model.
+/// Build constraint components sharing one caller-owned geometry preparation (block sampling and
+/// its member budget, spline rebuilds) between every model.
 /// Return constraints that cannot be interpreted as skipped entries.
-pub(crate) fn build_budgeted(
+pub(crate) fn build_with(
     d: &Drawing,
     cons: &[&Constraint],
     opts: &SolveOptions,
-    members_left: &mut usize,
+    prep: &mut Prep,
 ) -> 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_budgeted(d, &handles, members_left);
+        let mut model = Model::build_with(d, &handles, prep);
         let mut built = Vec::new();
         for c in group {
             let target = if c.kind.is_dimensional() { constraint_value(&mut e, c)? } else { 0.0 };
@@ -640,6 +674,11 @@ 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) {
@@ -648,7 +687,7 @@ pub fn validate(d: &Drawing, c: &Constraint) -> Result<(), String> {
             _ => {}
         }
     }
-    let mut model = Model::build(d, &handles);
+    let mut model = Model::build_with(d, &handles, prep);
     interpret(c, &mut model, 1.0).map(|_| ())
 }
 
@@ -665,7 +704,12 @@ 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();
-    let keep: Vec<bool> = d.constraints.iter().map(|c| validate(d, c).is_ok()).collect();
+    // 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 mut i = 0;
     d.constraints.retain(|c| {
         let k = keep.get(i).copied().unwrap_or(true);
@@ -752,6 +796,9 @@ 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,9 +14,11 @@
 //! 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::{Drawing, EntityKind, GeomRef, Handle, Insert, Sub};
+use cadcraft_doc::{Block, Drawing, EntityKind, GeomRef, Handle, Insert, Sub};
 use cadcraft_geom::{Spline as GSpline, Vec2, ccw_sweep};
 
 use crate::curves::{Ell, Frame, clamped, spline_end};
@@ -70,6 +72,9 @@ 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>,
@@ -79,20 +84,75 @@ 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(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
-        }
+        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 }
     }
 }
 
@@ -115,23 +175,18 @@ 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> {
-    let mut members_left = MAX_RIGID_MEMBERS;
-    rigid_points_budgeted(d, ins, &mut members_left)
+    Prep::new(MAX_RIGID_MEMBERS).rigid_points(d, ins)
 }
 
-/// 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());
+/// 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]> {
     let mut out = Vec::new();
     // Bound the members examined, not only the points collected: entities that contribute no
-    // 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 {
+    // 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 {
             break;
         }
         *members_left -= 1;
@@ -148,10 +203,10 @@ fn rigid_points_budgeted(d: &Drawing, ins: &Insert, members_left: &mut usize) ->
             EntityKind::LwPolyline(p) => p.vertices.iter().take(MAX_RIGID_POINTS).map(|v| v.p).collect(),
             _ => Vec::new(),
         };
-        out.extend(pts.into_iter().map(|p| m.apply(p)).filter(|p| p.is_finite()));
+        out.extend(pts.into_iter().filter(|p| p.is_finite()));
     }
     out.truncate(MAX_RIGID_POINTS);
-    out
+    out.into()
 }
 
 /// Constraint points of an object as the solver sees them (`Sub`, position): end points,
@@ -187,13 +242,12 @@ 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 {
-        let mut members_left = MAX_RIGID_WORK;
-        Self::build_budgeted(d, handles, &mut members_left)
+        Self::build_with(d, handles, &mut Prep::new(MAX_RIGID_WORK))
     }
 
     /// 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, members_left: &mut usize) -> Option<Shape> {
+    fn add_params(m: &mut Model, d: &Drawing, h: Handle, kind: &EntityKind, off: usize, prep: &mut Prep) -> Option<Shape> {
         let shape = match kind {
             EntityKind::Line(l) => {
                 m.x0.extend([l.a.x, l.a.y, l.b.x, l.b.y]);
@@ -243,15 +297,22 @@ 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)));
-                // Missing weights default to 1 in eval; only excess weights are unused.
-                let mut kept = sp.clone();
+                // 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() }
+                };
                 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> = rigid_points_budgeted(d, ins, members_left).into_iter().map(|p| (p - base).rotate(-ins.rotation)).collect();
+                let pts: Vec<Vec2> = prep.rigid_points(d, ins).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);
@@ -262,16 +323,17 @@ impl Model {
         Some(shape)
     }
 
-    /// 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();
+    /// 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() };
         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, members_left) else { continue };
+            let Some(shape) = Self::add_params(&mut m, d, h, &e.kind, off, prep) 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;
@@ -373,18 +435,20 @@ 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`.
-    fn spline(&self, x: &[f64], s: &Slot) -> Option<GSpline> {
+    /// 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>> {
         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<_>>>()?;
-        Some(if fit {
-            t.refit(&pts, t.closed)
-        } else {
-            let mut sp = t.clone();
-            sp.control = pts;
-            sp
-        })
+        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)
     }
 
     /// The start (`at_end` false) or end of a curve reference, in the curve's own direction:
@@ -421,7 +485,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,
         }
     }
@@ -590,7 +654,8 @@ 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(|mut sp| {
+            let spline = self.spline(x, s).map(|sp| {
+                let mut sp = GSpline::clone(&sp);
                 if matches!(shape, Shape::Spline { fit: false, .. }) {
                     sp.fit.clear();
                 }
@@ -712,21 +777,21 @@ mod budget_tests {
         }
     }
 
-    /// 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 {
+    fn add_block(d: &mut Drawing, name: &str, lines: usize) {
+        let mut block = Block::new(name);
+        for _ in 0..lines {
             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("BAR".into(), Arc::new(block));
-        let ins = Insert {
-            block: "BAR".into(),
+        d.blocks.insert(name.into(), Arc::new(block));
+    }
+
+    fn insert(block: &str) -> Insert {
+        Insert {
+            block: block.into(),
             insert: Vec3::ZERO,
             scale: Vec3::new(1.0, 1.0, 1.0),
             rotation: 0.0,
@@ -735,13 +800,79 @@ mod budget_tests {
             rows: 1,
             col_spacing: 0.0,
             row_spacing: 0.0,
-        };
-        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());
+        }
+    }
+
+    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);
     }
 }

crates/doc/src/entity/region.rs

@@ -9,9 +9,6 @@ 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.
@@ -79,49 +76,20 @@ 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. `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 {
+    /// an outer loop, odd an island.
+    pub fn renest(&mut self) {
         let polys = self.tessellate(self.fine_tol());
-        // 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
+        let depth: Vec<usize> = polys
             .iter()
-            .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)
+            .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()
             })
             .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
@@ -160,37 +128,3 @@ 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,9 +128,7 @@ fn combine(a: &Region, b: &Region, op: Op) -> Result<Option<Region>> {
     }
     loops.retain(|l| l.vertices.len() >= 2);
     let mut r = Region { loops };
-    if !r.renest() {
-        return Err(other("These regions are too complex to combine."));
-    }
+    r.renest();
     Ok(Some(r))
 }