Extents: share block-bounds memoization across all the entities measured

Each top-level bounds call started with an empty block cache, so measuring a
space's extents or building a spatial-index chunk measured a block definition
again for every reference to it: R references to a block of B entities cost
R x B. BlockBoundsCache keeps the per-depth block bounds (separately for drawn
bounds and extents, which differ on layers turned off) across one bulk
operation; Drawing::extents and the spatial index use it (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/extents.rs

@@ -94,25 +94,48 @@ fn mtext_box(t: &crate::MText) -> Bounds2 {
 
 /// The box of what `e` draws (block contents on layers turned off left out).
 pub fn entity_bounds(d: &Drawing, e: &Entity, depth: usize) -> Bounds2 {
-    bounds_of(d, e, depth, false)
+    bounds_of(d, e, depth, false, &mut HashMap::new())
 }
 
 /// The box `e` takes in the drawing's extents: as [`entity_bounds`], but block contents on a layer
 /// turned off count, as AutoCAD 2024's ZOOM Extents counts them (a frozen layer's do not).
 pub fn extent_bounds(d: &Drawing, e: &Entity) -> Bounds2 {
-    bounds_of(d, e, 0, true)
+    bounds_of(d, e, 0, true, &mut HashMap::new())
 }
 
-fn bounds_of(d: &Drawing, e: &Entity, depth: usize, off_counts: bool) -> Bounds2 {
+/// The bounds of block contents measured so far, kept across the entities of one unchanged
+/// drawing. Measuring many entities with [`entity_bounds_cached`] or [`extent_bounds_cached`]
+/// and one cache measures each block definition once per depth for all of them; a fresh cache per
+/// entity would measure a block again for every reference to it, R references to a block of B
+/// entities costing R x B (CWE-407). Use a cache only while the drawing it measured is unchanged.
+#[derive(Default)]
+pub struct BlockBoundsCache<'a> {
+    /// By block name and depth, block contents on layers turned off left out ([`entity_bounds`]).
+    drawn: HashMap<(&'a str, usize), Bounds2>,
+    /// The same with those contents counted ([`extent_bounds`]).
+    extents: HashMap<(&'a str, usize), Bounds2>,
+}
+
+/// [`entity_bounds`] reusing the block bounds `cache` holds from earlier calls on drawing `d`.
+pub fn entity_bounds_cached<'a>(d: &'a Drawing, e: &Entity, depth: usize, cache: &mut BlockBoundsCache<'a>) -> Bounds2 {
+    bounds_of(d, e, depth, false, &mut cache.drawn)
+}
+
+/// [`extent_bounds`] reusing the block bounds `cache` holds from earlier calls on drawing `d`.
+pub fn extent_bounds_cached<'a>(d: &'a Drawing, e: &Entity, cache: &mut BlockBoundsCache<'a>) -> Bounds2 {
+    bounds_of(d, e, 0, true, &mut cache.extents)
+}
+
+fn bounds_of<'a>(d: &'a Drawing, e: &Entity, depth: usize, off_counts: bool, blocks: &mut HashMap<(&'a str, usize), Bounds2>) -> Bounds2 {
     // A top-level annotative object measures as it draws at the current annotation scale.
     if depth == 0 {
         match d.anno_draw(e) {
             crate::AnnoDraw::Plain => {}
             crate::AnnoDraw::Hidden => return Bounds2::EMPTY,
-            crate::AnnoDraw::Scaled(f) => return bounds_in(d, &crate::anno_scaled(e, f), 0, &mut HashMap::new(), off_counts),
+            crate::AnnoDraw::Scaled(f) => return bounds_in(d, &crate::anno_scaled(e, f), 0, blocks, off_counts),
         }
     }
-    bounds_in(d, e, depth, &mut HashMap::new(), off_counts)
+    bounds_in(d, e, depth, blocks, off_counts)
 }
 
 /// [`entity_bounds`] with the bounds of block contents (in block coordinates) already computed,
@@ -442,4 +465,53 @@ mod tests {
         empty.text = Some(crate::MText { contents: " ".into(), ..mtext });
         assert!(bounds(EntityKind::MLeader(empty)).max.x < 26.0);
     }
+
+    #[test]
+    fn a_shared_block_cache_measures_as_a_fresh_one_for_each_entity() {
+        let line = |a: (f64, f64), b: (f64, f64), layer: &str| {
+            let mut e = Entity::new(crate::Handle(1), EntityKind::Line(crate::Line { a: Vec3::new(a.0, a.1, 0.0), b: Vec3::new(b.0, b.1, 0.0) }));
+            e.common.layer = layer.into();
+            e
+        };
+        let ins = |block: &str, at: f64| {
+            Entity::new(
+                crate::Handle(2),
+                EntityKind::Insert(crate::Insert {
+                    block: block.into(),
+                    insert: Vec3::new(at, at, 0.0),
+                    scale: Vec3::new(1.0, 1.0, 1.0),
+                    rotation: 0.0,
+                    attribs: Vec::new(),
+                    cols: 1,
+                    rows: 1,
+                    col_spacing: 0.0,
+                    row_spacing: 0.0,
+                }),
+            )
+        };
+        let mut d = Drawing::new_imperial();
+        d.ensure_layer("OFF");
+        if let Some(l) = d.layer_mut("OFF") {
+            l.on = false;
+        }
+        // A block with a part on a layer turned off (left out when drawn, counted in extents),
+        // and a block that nests it.
+        let mut b = crate::Block::new("B");
+        b.entities.push(line((0.0, 0.0), (1.0, 1.0), "0"));
+        b.entities.push(line((0.0, 0.0), (5.0, 5.0), "OFF"));
+        d.blocks.insert("B".into(), std::sync::Arc::new(b));
+        let mut n = crate::Block::new("N");
+        n.entities.push(ins("B", 10.0));
+        d.blocks.insert("N".into(), std::sync::Arc::new(n));
+        let ents: Vec<Entity> = (0..50).map(|i| ins(if i % 2 == 0 { "B" } else { "N" }, f64::from(i))).collect();
+        // One cache for both kinds of measure, interleaved: neither may answer for the other.
+        let mut cache = BlockBoundsCache::default();
+        for e in &ents {
+            let (drawn, extents) = (entity_bounds_cached(&d, e, 0, &mut cache), extent_bounds_cached(&d, e, &mut cache));
+            let (want_drawn, want_extents) = (entity_bounds(&d, e, 0), extent_bounds(&d, e));
+            assert_eq!((drawn.min, drawn.max), (want_drawn.min, want_drawn.max));
+            assert_eq!((extents.min, extents.max), (want_extents.min, want_extents.max));
+            assert!(extents.width() > drawn.width());
+        }
+    }
 }

crates/doc/src/lib.rs

@@ -27,7 +27,7 @@ pub use cadcraft_color as color;
 pub use cadcraft_geom as geom;
 pub use constraint::*;
 pub use entity::*;
-pub use extents::{MAX_BLOCK_DEPTH, entity_bounds, extent_bounds};
+pub use extents::{BlockBoundsCache, MAX_BLOCK_DEPTH, entity_bounds, entity_bounds_cached, extent_bounds, extent_bounds_cached};
 pub use format::Format;
 pub use gdt::*;
 pub use header::{HVal, Header};
@@ -383,10 +383,13 @@ impl Drawing {
     /// Bounds of the entities in a space that count in its extents ([`Drawing::in_extents`]).
     pub fn extents(&self, space: &Space) -> cadcraft_geom::Bounds2 {
         let mut b = cadcraft_geom::Bounds2::EMPTY;
+        // One block-bounds cache for the whole space: every reference to a block reuses its
+        // measured contents instead of measuring the definition again.
+        let mut cache = BlockBoundsCache::default();
         if let Some(store) = self.space(space) {
             for e in store.iter() {
                 if self.in_extents(e) {
-                    b = b.union(&extent_bounds(self, e));
+                    b = b.union(&extent_bounds_cached(self, e, &mut cache));
                 }
             }
         }

crates/engine/src/spatial.rs

@@ -15,7 +15,7 @@
 use std::collections::BTreeMap;
 use std::sync::{Arc, Mutex};
 
-use cadcraft_doc::{Block, DimStyle, Drawing, Entity, EntityKind, EntityStore, Space, entity_bounds};
+use cadcraft_doc::{Block, BlockBoundsCache, DimStyle, Drawing, Entity, EntityKind, EntityStore, Space, entity_bounds_cached};
 use cadcraft_geom::Bounds2;
 use rstar::primitives::{GeomWithData, Rectangle};
 use rstar::{AABB, RTree};
@@ -44,6 +44,8 @@ struct ChunkIx {
 impl ChunkIx {
     fn build(d: &Drawing, key: usize, items: &[Arc<Entity>]) -> ChunkIx {
         let mut infinite = Vec::new();
+        // One block-bounds cache for the chunk: references to the same block measure it once.
+        let mut cache = BlockBoundsCache::default();
         let bounds = items
             .iter()
             .enumerate()
@@ -51,7 +53,7 @@ impl ChunkIx {
                 if matches!(e.kind, EntityKind::XLine(_) | EntityKind::Ray(_)) {
                     infinite.push(u32::try_from(i).unwrap_or(u32::MAX));
                 }
-                entity_bounds(d, e, 0)
+                entity_bounds_cached(d, e, 0, &mut cache)
             })
             .collect();
         let serial = NEXT_SERIAL.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
@@ -200,7 +202,7 @@ impl SpatialIndex {
         let (c, l) = self.locate(i)?;
         c.ents.get(l)
     }
-    /// The bounds of the entity at draw index `i` (as [`entity_bounds`] computes them).
+    /// The bounds of the entity at draw index `i` (as [`cadcraft_doc::entity_bounds`] computes them).
     pub fn bounds(&self, i: u32) -> Bounds2 {
         self.locate(i).and_then(|(c, l)| c.bounds.get(l).copied()).unwrap_or(Bounds2::EMPTY)
     }