constraints: find the next default parameter name in one pass

next_name tested up to 100,000 candidate names, each against every
parameter and constraint name, so a drawing with many occupied names
made adding one dimensional constraint quadratic. Collect the numeric
suffixes in use once and take the first free one.

crates/constraints/src/lib.rs

@@ -30,7 +30,7 @@ mod lm;
 mod model;
 mod residual;
 
-use std::collections::{BTreeMap, HashMap};
+use std::collections::{BTreeMap, HashMap, HashSet};
 
 use cadcraft_doc::{Constraint, ConstraintKind, Drawing, GeomRef, Handle};
 use cadcraft_geom::Vec2;
@@ -169,10 +169,26 @@ pub fn name_in_use(d: &Drawing, name: &str) -> bool {
     d.parametric.parameters.iter().any(|p| p.name == name) || d.constraints.iter().any(|c| c.name == name)
 }
 
+/// Highest numbered default name [`next_name`] tries.
+const MAX_NAME_SUFFIX: u32 = 100_000;
+
 /// Next free parameter name for a dimensional constraint kind (`d1`, `rad2`, `ang1`, …).
 pub fn next_name(d: &Drawing, kind: ConstraintKind) -> String {
     let prefix = kind.name_prefix();
-    (1..=100_000).map(|i| format!("{prefix}{i}")).find(|n| !name_in_use(d, n)).unwrap_or_else(|| format!("{prefix}_x"))
+    // Collect the suffixes in use in one pass, then take the first free one: checking every
+    // candidate against every name is quadratic in the number of names (CWE-407). Only a
+    // suffix spelled as `format!("{prefix}{i}")` spells it counts (`d07` does not take `d7`).
+    let taken: HashSet<u32> = d
+        .parametric
+        .parameters
+        .iter()
+        .map(|p| p.name.as_str())
+        .chain(d.constraints.iter().map(|c| c.name.as_str()))
+        .filter_map(|n| n.strip_prefix(prefix))
+        .filter(|s| !s.starts_with('0') && s.bytes().all(|b| b.is_ascii_digit()))
+        .filter_map(|s| s.parse::<u32>().ok())
+        .collect();
+    (1..=MAX_NAME_SUFFIX).find(|i| !taken.contains(i)).map_or_else(|| format!("{prefix}_x"), |i| format!("{prefix}{i}"))
 }
 
 /// Next free constraint id.

crates/constraints/src/tests.rs

@@ -489,3 +489,30 @@ fn arc_solved_with_a_negative_radius_keeps_its_points() {
         }
     }
 }
+
+/// The default name is the first free numbered one, found in one pass over many names in use.
+#[test]
+fn next_name_skips_names_in_use() {
+    let mut d = Drawing::default();
+    assert_eq!(next_name(&d, ConstraintKind::Radius), "rad1");
+    for i in (1..=20_000).filter(|i| *i != 15_000) {
+        d.parametric.parameters.push(cadcraft_doc::Parameter { name: format!("d{i}"), expr: "1".into(), description: String::new() });
+    }
+    assert_eq!(next_name(&d, ConstraintKind::Distance(DistAxis::Aligned)), "d15000");
+    d.parametric.parameters.push(cadcraft_doc::Parameter { name: "d15000".into(), expr: "1".into(), description: String::new() });
+    assert_eq!(next_name(&d, ConstraintKind::Distance(DistAxis::Aligned)), "d20001");
+    // A differently spelled suffix does not occupy the plain name.
+    let mut d = Drawing::default();
+    for name in ["d01", "d+1", "d1x", "D1"] {
+        d.parametric.parameters.push(cadcraft_doc::Parameter { name: name.into(), expr: "1".into(), description: String::new() });
+    }
+    assert_eq!(next_name(&d, ConstraintKind::Distance(DistAxis::Aligned)), "d1");
+    d.constraints.push(Constraint {
+        id: 1,
+        kind: ConstraintKind::Distance(DistAxis::Aligned),
+        refs: Vec::new(),
+        name: "d1".into(),
+        expr: "1".into(),
+    });
+    assert_eq!(next_name(&d, ConstraintKind::Distance(DistAxis::Aligned)), "d2");
+}

crates/doc/src/extents.rs

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

crates/doc/src/lib.rs

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

crates/engine/src/spatial.rs

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