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

@@ -30,7 +30,7 @@ mod lm;
 mod model;
 mod residual;
 
-use std::collections::{BTreeMap, HashMap, HashSet};
+use std::collections::{BTreeMap, HashMap};
 
 use cadcraft_doc::{Constraint, ConstraintKind, Drawing, GeomRef, Handle};
 use cadcraft_geom::Vec2;
@@ -169,26 +169,10 @@ 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();
-    // 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}"))
+    (1..=100_000).map(|i| format!("{prefix}{i}")).find(|n| !name_in_use(d, n)).unwrap_or_else(|| format!("{prefix}_x"))
 }
 
 /// Next free constraint id.

crates/constraints/src/tests.rs

@@ -489,30 +489,3 @@ 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,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());
+    }
+}