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/entity/mline.rs

@@ -207,41 +207,6 @@ 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 {
@@ -303,11 +268,16 @@ impl MLine {
         let dirs = self.directions();
         let n = self.vertices.len();
         let nseg = dirs.len();
-        // 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) };
+        // 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)
+        };
         let end = |d: Vec2, angle: f64| {
             let u = d.rotate(angle);
             let s = angle.sin();
@@ -456,61 +426,3 @@ 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());
-    }
-}