Multilines: test that a run of coincident vertices at a corner takes the corner's miter

MLine::miters searched the direction array forwards and backwards from every
vertex for the nearest non-degenerate segment, so a long run of coincident
vertices made it quadratic. The nearest usable directions ahead and behind
are now computed once, in one backward and one forward pass (CWE-407).

crates/constraints/src/dof.rs

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

crates/constraints/src/lib.rs

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

crates/constraints/src/model.rs

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

crates/doc/src/entity/mline.rs

@@ -207,6 +207,41 @@ pub struct MLineGeometry {
     pub fill: Vec<Vec<Vec2>>,
 }
 
+/// For each segment direction in `dirs`, the first non-zero direction at or after it and the
+/// first at or before it, both wrapping around (`Vec2::X` when every direction is zero).
+///
+/// Two linear passes: searching from every segment separately is quadratic in a run of
+/// coincident vertices, which a hostile file can make as long as it likes (CWE-407).
+fn usable_directions(dirs: &[Vec2]) -> (Vec<Vec2>, Vec<Vec2>) {
+    let n = dirs.len();
+    let (Some(first), Some(last)) = (dirs.iter().position(|d| *d != Vec2::ZERO), dirs.iter().rposition(|d| *d != Vec2::ZERO)) else {
+        return (vec![Vec2::X; n], vec![Vec2::X; n]);
+    };
+    let (mut ahead, mut behind) = (vec![Vec2::X; n], vec![Vec2::X; n]);
+    // Walking backwards from the last usable direction, the latest one seen is the next ahead.
+    let mut cur = Vec2::X;
+    for k in 0..n {
+        let i = (last + n - k) % n;
+        if let Some(d) = dirs.get(i).filter(|d| **d != Vec2::ZERO) {
+            cur = *d;
+        }
+        if let Some(a) = ahead.get_mut(i) {
+            *a = cur;
+        }
+    }
+    // Walking forwards from the first usable direction, the latest one seen is the nearest behind.
+    for k in 0..n {
+        let i = (first + k) % n;
+        if let Some(d) = dirs.get(i).filter(|d| **d != Vec2::ZERO) {
+            cur = *d;
+        }
+        if let Some(b) = behind.get_mut(i) {
+            *b = cur;
+        }
+    }
+    (ahead, behind)
+}
+
 impl MLine {
     /// A multiline through `pts` in style `def`.
     pub fn new(def: &MLineStyle, pts: &[Vec2], closed: bool, just: MLineJust, scale: f64) -> MLine {
@@ -268,16 +303,11 @@ impl MLine {
         let dirs = self.directions();
         let n = self.vertices.len();
         let nseg = dirs.len();
-        // A degenerate segment takes its neighbour's direction.
-        let dir = |i: usize| -> Vec2 {
-            (0..nseg).map(|k| dirs.get((i + k) % nseg.max(1)).copied().unwrap_or_default()).find(|d| *d != Vec2::ZERO).unwrap_or(Vec2::X)
-        };
-        let dir_back = |i: usize| -> Vec2 {
-            (0..nseg)
-                .map(|k| dirs.get((i + nseg - k % nseg) % nseg.max(1)).copied().unwrap_or_default())
-                .find(|d| *d != Vec2::ZERO)
-                .unwrap_or(Vec2::X)
-        };
+        // A degenerate segment takes its neighbour's direction: the first usable one at or after
+        // it (`ahead`), or at or before it (`behind`), wrapping around.
+        let (ahead, behind) = usable_directions(&dirs);
+        let dir = |i: usize| -> Vec2 { ahead.get(i).copied().unwrap_or(Vec2::X) };
+        let dir_back = |i: usize| -> Vec2 { behind.get(i).copied().unwrap_or(Vec2::X) };
         let end = |d: Vec2, angle: f64| {
             let u = d.rotate(angle);
             let s = angle.sin();
@@ -426,3 +456,61 @@ impl crate::Drawing {
         self.mline_style(&name).or_else(|| self.mline_style(STANDARD_MLINE_STYLE)).cloned().unwrap_or_default()
     }
 }
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    /// The nearest usable directions found by searching from each segment, as miters did before.
+    fn searched(dirs: &[Vec2]) -> (Vec<Vec2>, Vec<Vec2>) {
+        let n = dirs.len();
+        let ahead = (0..n).map(|i| (0..n).filter_map(|k| dirs.get((i + k) % n).copied()).find(|d| *d != Vec2::ZERO).unwrap_or(Vec2::X));
+        let behind = (0..n).map(|i| (0..n).filter_map(|k| dirs.get((i + n - k) % n).copied()).find(|d| *d != Vec2::ZERO).unwrap_or(Vec2::X));
+        (ahead.collect(), behind.collect())
+    }
+
+    #[test]
+    fn usable_directions_match_a_search_from_each_segment() {
+        let (z, a, b, c) = (Vec2::ZERO, Vec2::Y, -Vec2::X, Vec2::new(0.6, 0.8));
+        for dirs in [
+            vec![],
+            vec![z],
+            vec![a],
+            vec![z, z, z],
+            vec![a, z, z, b],
+            vec![z, a, z, b, z],
+            vec![z, z, c],
+            vec![c, z, z],
+            vec![a, b, c],
+            vec![z, a, z, z, b, c, z],
+        ] {
+            assert_eq!(usable_directions(&dirs), searched(&dirs), "{dirs:?}");
+        }
+    }
+
+    #[test]
+    fn coincident_vertices_at_a_corner_take_the_corner_miter() {
+        // Every vertex of a run on one point mitres between the segment before the run and the one after.
+        let style = MLineStyle::default();
+        let corner = MLine::new(&style, &[Vec2::ZERO, Vec2::Y, Vec2::new(-1.0, 1.0)], false, MLineJust::Zero, 1.0);
+        let pts = [Vec2::ZERO, Vec2::Y, Vec2::Y, Vec2::Y, Vec2::new(-1.0, 1.0)];
+        let run = MLine::new(&style, &pts, false, MLineJust::Zero, 1.0);
+        let (expected, got) = (corner.miters(), run.miters());
+        assert_eq!(got.get(1..4), Some(&[expected[1]; 3][..]));
+        assert_eq!((got.first(), got.last()), (expected.first(), expected.last()));
+    }
+
+    #[test]
+    fn a_long_run_of_coincident_vertices_takes_linear_time() {
+        // 200 000 vertices on one point but the last: the miters must not search the run once per
+        // vertex (quadratic, minutes) to find the one usable direction.
+        let mut pts = vec![Vec2::ZERO; 200_000];
+        pts.push(Vec2::new(1.0, 0.0));
+        let m = MLine::new(&MLineStyle::default(), &pts, false, MLineJust::Zero, 1.0);
+        let t = std::time::Instant::now();
+        let miters = m.miters();
+        assert_eq!(miters.len(), pts.len());
+        assert!(miters.iter().all(|v| v.is_finite()));
+        assert!(t.elapsed() < std::time::Duration::from_secs(5), "{:?}", t.elapsed());
+    }
+}