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/dynblock.rs

@@ -323,9 +323,8 @@ impl<'a> Cursor<'a> {
     }
 }
 
-/// `xdict`'s `ACAD_ENHANCEDBLOCK` evaluation graph object, when the dictionary has one. Only the
-/// dictionary's own tags are read, so asking whether a block is dynamic never walks the graph.
-fn evaluation_graph<'a>(objects: &HashMap<Handle, &'a ForeignObject>, xdict: Handle) -> Option<&'a ForeignObject> {
+/// The objects `xdict`'s `ACAD_ENHANCEDBLOCK` evaluation graph lists, when the dictionary has one.
+fn graph_members<'a>(objects: &HashMap<Handle, &'a ForeignObject>, xdict: Handle) -> Option<Vec<&'a ForeignObject>> {
     let dict = objects.get(&xdict)?;
     let mut graph = None;
     let mut tags = dict.tags.iter();
@@ -335,12 +334,7 @@ fn evaluation_graph<'a>(objects: &HashMap<Handle, &'a ForeignObject>, xdict: Han
             break;
         }
     }
-    objects.get(&graph?).copied().filter(|o| o.kind.eq_ignore_ascii_case("ACAD_EVALUATION_GRAPH"))
-}
-
-/// The objects `xdict`'s `ACAD_ENHANCEDBLOCK` evaluation graph lists, when the dictionary has one.
-fn graph_members<'a>(objects: &HashMap<Handle, &'a ForeignObject>, xdict: Handle) -> Option<Vec<&'a ForeignObject>> {
-    let graph = evaluation_graph(objects, xdict)?;
+    let graph = objects.get(&graph?).filter(|o| o.kind.eq_ignore_ascii_case("ACAD_EVALUATION_GRAPH"))?;
     let members = section(&sections(&graph.tags), "AcDbEvalGraph").iter().filter(|t| t.code == 360).filter_map(|t| Handle::parse_hex(&t.value));
     // Deduplicate member handles before resolving them: a graph can list the same member many
     // times, and parsing each occurrence into its own owned parameter multiplies a single large
@@ -349,42 +343,13 @@ fn graph_members<'a>(objects: &HashMap<Handle, &'a ForeignObject>, xdict: Handle
     Some(members.take(MAX_NODES).filter(|h| seen.insert(*h)).filter_map(|h| objects.get(&h).copied()).collect())
 }
 
-/// The kept foreign objects of a drawing by handle. Building it walks every object, so a caller
-/// that asks about many blocks (listing them) builds it once and passes it to
-/// [`dynamic_block_in`] and [`is_dynamic_block_in`] instead of rebuilding it per block, which
-/// multiplies the block count by the object count (CWE-407).
-pub struct ObjectIndex<'a>(HashMap<Handle, &'a ForeignObject>);
-
-impl<'a> ObjectIndex<'a> {
-    pub fn new(d: &'a Drawing) -> Self {
-        ObjectIndex(d.foreign.objects.iter().map(|o| (o.handle, o)).collect())
-    }
-}
-
-/// The extension dictionary of block `name`'s record, if it has one.
-fn block_xdict(d: &Drawing, name: &str) -> Option<Handle> {
-    d.foreign.records.get(&("BLOCK_RECORD".to_string(), name.trim().to_ascii_uppercase()))?.xdict
-}
-
 /// The dynamic block data of block `name` (any case; `*Model_Space` for a drawing that is a
 /// block's own drawing), or `None` when it has none.
 pub fn dynamic_block(d: &Drawing, name: &str) -> Option<DynamicBlock> {
-    // A block without an extension dictionary is never dynamic: answer before indexing objects.
-    block_xdict(d, name)?;
-    dynamic_block_in(d, &ObjectIndex::new(d), name)
-}
-
-/// Whether block `name` is a dynamic block (has an evaluation graph), without reading its
-/// parameters and actions; `objects` is the drawing's [`ObjectIndex`].
-pub fn is_dynamic_block_in(d: &Drawing, objects: &ObjectIndex<'_>, name: &str) -> bool {
-    block_xdict(d, name).and_then(|x| evaluation_graph(&objects.0, x)).is_some()
-}
-
-/// [`dynamic_block`] with the drawing's [`ObjectIndex`] already built.
-pub fn dynamic_block_in(d: &Drawing, objects: &ObjectIndex<'_>, name: &str) -> Option<DynamicBlock> {
-    let xdict = block_xdict(d, name)?;
+    let xdict = d.foreign.records.get(&("BLOCK_RECORD".to_string(), name.trim().to_ascii_uppercase()))?.xdict?;
+    let objects: HashMap<Handle, &ForeignObject> = d.foreign.objects.iter().map(|o| (o.handle, o)).collect();
     let mut out = DynamicBlock::default();
-    for o in graph_members(&objects.0, xdict)? {
+    for o in graph_members(&objects, xdict)? {
         let secs = sections(&o.tags);
         let node = Cursor::new(section(&secs, "AcDbEvalExpr")).int(90);
         let element = Cursor::new(section(&secs, "AcDbBlockElement")).string(300);

crates/doc/src/dynblock/apply.rs

@@ -54,11 +54,7 @@ fn record_handle(d: &Drawing, name: &str) -> Option<Handle> {
 
 /// The object entry `key` of dictionary `dict` refers to.
 fn entry(d: &Drawing, dict: Handle, key: &str) -> Option<Handle> {
-    dictionary_entry(d.foreign.objects.iter().find(|o| o.handle == dict)?, key)
-}
-
-/// The object entry `key` (any case) of dictionary object `o` names.
-fn dictionary_entry(o: &ForeignObject, key: &str) -> Option<Handle> {
+    let o = d.foreign.objects.iter().find(|o| o.handle == dict)?;
     let mut tags = o.tags.iter();
     while let Some(t) = tags.next() {
         if t.code == 3 && t.value.eq_ignore_ascii_case(key) {
@@ -70,11 +66,7 @@ fn dictionary_entry(o: &ForeignObject, key: &str) -> Option<Handle> {
 
 /// Every entry of dictionary `dict`: (key, object).
 fn entries(d: &Drawing, dict: Handle) -> Vec<(String, Handle)> {
-    d.foreign.objects.iter().find(|o| o.handle == dict).map(dictionary_entries).unwrap_or_default()
-}
-
-/// Every entry of dictionary object `o`: (key, object).
-fn dictionary_entries(o: &ForeignObject) -> Vec<(String, Handle)> {
+    let Some(o) = d.foreign.objects.iter().find(|o| o.handle == dict) else { return Vec::new() };
     let mut out = Vec::new();
     let mut key: Option<&str> = None;
     for t in &o.tags {
@@ -700,33 +692,19 @@ fn refill_hatches(b: &mut Block) {
 
 /// The value records of the references to the dynamic block whose record is `def_record` (from
 /// any one of them, by graph id): AutoCAD's layout of each record, class ids included.
-///
-/// Each record is copied once at most: a key naming a record an earlier key already took is
-/// skipped. Records are copied per key (and copied again per key when a new reference's data is
-/// made), so a file listing one large record under many keys would otherwise multiply its size by
-/// the key count (CWE-400); AutoCAD gives every key its own record.
 fn templates(d: &Drawing, def_record: Handle) -> HashMap<String, Vec<RawTag>> {
     let objects: HashMap<Handle, &ForeignObject> = d.foreign.objects.iter().map(|o| (o.handle, o)).collect();
-    // Dictionary entries looked up through the index, not by scanning every object per
-    // dictionary (which is quadratic in the object count).
-    let entry = |dict: Handle, key: &str| objects.get(&dict).and_then(|o| dictionary_entry(o, key));
     let mut out: HashMap<String, Vec<RawTag>> = HashMap::new();
-    let mut taken: HashSet<Handle> = HashSet::new();
     for rep in d.foreign.objects.iter().filter(|o| o.kind.eq_ignore_ascii_case("DICTIONARY")) {
         // A representation dictionary whose data names this dynamic block.
-        let Some(rd) = dictionary_entry(rep, "AcDbRepData").and_then(|h| objects.get(&h)) else { continue };
+        let Some(rd) = entry(d, rep.handle, "AcDbRepData").and_then(|h| objects.get(&h)) else { continue };
         if !rd.tags.iter().any(|t| t.code == 340 && Handle::parse_hex(&t.value) == Some(def_record)) {
             continue;
         }
-        let Some(values) = dictionary_entry(rep, "AppDataCache").and_then(|c| entry(c, "ACAD_ENHANCEDBLOCKDATA")) else { continue };
-        let Some(values) = objects.get(&values) else { continue };
-        for (k, h) in dictionary_entries(values) {
-            if out.contains_key(&k) || taken.contains(&h) {
-                continue;
-            }
+        let Some(values) = entry(d, rep.handle, "AppDataCache").and_then(|c| entry(d, c, "ACAD_ENHANCEDBLOCKDATA")) else { continue };
+        for (k, h) in entries(d, values) {
             if let Some(x) = objects.get(&h).filter(|x| x.kind.eq_ignore_ascii_case("XRECORD")) {
-                taken.insert(h);
-                out.insert(k, x.tags.clone());
+                out.entry(k).or_insert_with(|| x.tags.clone());
             }
         }
     }
@@ -1066,23 +1044,4 @@ mod tests {
         assert_eq!(by_tag(&d, &def), vec![(10, Handle(1)), (20, Handle(2))]);
         assert_eq!(by_tag(&d, &anon), vec![(20, Handle(5)), (1_000_001, Handle(6))]);
     }
-
-    #[test]
-    fn a_value_record_listed_under_many_keys_is_copied_once() {
-        // One large XRECORD named by many keys of a reference's value dictionary: the templates
-        // keep one copy, not one per key.
-        let mut d = Drawing::new_imperial();
-        let (def_record, rep, rd, cache, values, record) = (Handle(0x10), Handle(0x20), Handle(0x21), Handle(0x22), Handle(0x23), Handle(0x24));
-        let keys: Vec<String> = (0..1000).map(|i| i.to_string()).collect();
-        let entries: Vec<(&str, Handle)> = keys.iter().map(|k| (k.as_str(), record)).collect();
-        let f = std::sync::Arc::make_mut(&mut d.foreign);
-        f.objects.push(dictionary(rep, Handle(1), &[("AcDbRepData", rd), ("AppDataCache", cache)]));
-        f.objects.push(ForeignObject { handle: rd, kind: "ACDB_BLOCKREPRESENTATION_DATA".into(), tags: vec![tag(340, def_record.hex())] });
-        f.objects.push(dictionary(cache, rep, &[("ACAD_ENHANCEDBLOCKDATA", values)]));
-        f.objects.push(dictionary(values, cache, &entries));
-        f.objects.push(ForeignObject { handle: record, kind: "XRECORD".into(), tags: (0..1000).map(|_| tag(1, "x")).collect() });
-        let t = templates(&d, def_record);
-        assert_eq!(t.len(), 1, "one record, one template");
-        assert_eq!(t.get("0").map(Vec::len), Some(1000));
-    }
 }

crates/engine/src/cmd/blocks.rs

@@ -379,11 +379,8 @@ fn run_base(s: &mut Session, p: &Value) -> Result<Value> {
 
 fn run_list(s: &mut Session, _p: &Value) -> Result<Value> {
     let d = s.doc()?;
-    // One object index for the whole listing: rebuilding it per block multiplies the block count
-    // by the drawing's kept object count (CWE-407).
-    let objects = cadcraft_doc::dynblock::ObjectIndex::new(d);
     let block = |b: &Block| {
-        let dynamic = cadcraft_doc::dynblock::is_dynamic_block_in(d, &objects, &b.name);
+        let dynamic = cadcraft_doc::dynblock::dynamic_block(d, &b.name).is_some();
         json!({"name": b.name, "entities": b.entities.len(), "base": [b.base.x, b.base.y], "description": b.description, "dynamic": dynamic})
     };
     Ok(json!({ "blocks": d.blocks.values().filter(|b| !b.anonymous).map(|b| block(b)).collect::<Vec<_>>() }))

crates/engine/tests/it/dynamic_block_data.rs

@@ -83,10 +83,6 @@ fn blocks_without_dynamic_data_and_bad_names() {
     s.execute("block", &json!({ "name": "Window", "base": [0, 0], "handles": [l] })).unwrap();
     assert_eq!(s.execute("blocks.dynamic", &json!({ "name": "Window" })).unwrap(), json!(null));
     assert_eq!(s.execute("blocks.dynamic", &json!({ "name": "*Model_Space" })).unwrap(), json!(null));
-    let list = s.execute("blocks.list", &json!({})).unwrap();
-    let flags: Vec<_> = list["blocks"].as_array().unwrap().iter().map(|b| (b["name"].as_str().unwrap().to_string(), b["dynamic"].clone())).collect();
-    assert!(flags.contains(&("Window".into(), json!(false))), "{flags:?}");
-    assert!(flags.contains(&("Door".into(), json!(true))), "{flags:?}");
     for p in [json!({}), json!({ "name": 3 }), json!({ "name": "Nope" }), json!(null)] {
         assert!(s.execute("blocks.dynamic", &p).is_err(), "{p}");
     }