Dynamic blocks: list a block as dynamic from its graph object without walking the graph's members

Listing blocks rebuilt a handle index of every kept foreign object for each
block with an extension dictionary, multiplying the block count by the object
count. The listing now builds one ObjectIndex and asks is_dynamic_block_in per
block; dynamic_block answers None before indexing when the block has no
extension dictionary.

templates() copied a value record's tags once per dictionary key, so a record
listed under many keys was copied many times, and it looked up each
dictionary entry by scanning every object. It now resolves entries through
its handle index and copies each record at most once (CWE-400, 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/dynblock.rs

@@ -323,8 +323,9 @@ impl<'a> Cursor<'a> {
     }
 }
 
-/// 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>> {
+/// `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> {
     let dict = objects.get(&xdict)?;
     let mut graph = None;
     let mut tags = dict.tags.iter();
@@ -334,7 +335,12 @@ fn graph_members<'a>(objects: &HashMap<Handle, &'a ForeignObject>, xdict: Handle
             break;
         }
     }
-    let graph = objects.get(&graph?).filter(|o| o.kind.eq_ignore_ascii_case("ACAD_EVALUATION_GRAPH"))?;
+    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 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
@@ -343,13 +349,42 @@ 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> {
-    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();
+    // 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 mut out = DynamicBlock::default();
-    for o in graph_members(&objects, xdict)? {
+    for o in graph_members(&objects.0, 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,7 +54,11 @@ 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> {
-    let o = d.foreign.objects.iter().find(|o| o.handle == dict)?;
+    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 mut tags = o.tags.iter();
     while let Some(t) = tags.next() {
         if t.code == 3 && t.value.eq_ignore_ascii_case(key) {
@@ -66,7 +70,11 @@ fn entry(d: &Drawing, dict: Handle, key: &str) -> Option<Handle> {
 
 /// Every entry of dictionary `dict`: (key, object).
 fn entries(d: &Drawing, dict: Handle) -> Vec<(String, Handle)> {
-    let Some(o) = d.foreign.objects.iter().find(|o| o.handle == dict) else { return Vec::new() };
+    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 mut out = Vec::new();
     let mut key: Option<&str> = None;
     for t in &o.tags {
@@ -692,19 +700,33 @@ 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) = entry(d, rep.handle, "AcDbRepData").and_then(|h| objects.get(&h)) else { continue };
+        let Some(rd) = dictionary_entry(rep, "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) = entry(d, rep.handle, "AppDataCache").and_then(|c| entry(d, c, "ACAD_ENHANCEDBLOCKDATA")) else { continue };
-        for (k, h) in entries(d, values) {
+        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;
+            }
             if let Some(x) = objects.get(&h).filter(|x| x.kind.eq_ignore_ascii_case("XRECORD")) {
-                out.entry(k).or_insert_with(|| x.tags.clone());
+                taken.insert(h);
+                out.insert(k, x.tags.clone());
             }
         }
     }
@@ -1044,4 +1066,23 @@ 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,8 +379,11 @@ 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::dynamic_block(d, &b.name).is_some();
+        let dynamic = cadcraft_doc::dynblock::is_dynamic_block_in(d, &objects, &b.name);
         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,6 +83,10 @@ 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}");
     }