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/doc/src/dynblock.rs

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

crates/engine/src/cmd/blocks.rs

@@ -379,11 +379,8 @@ 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::is_dynamic_block_in(d, &objects, &b.name);
+        let dynamic = cadcraft_doc::dynblock::dynamic_block(d, &b.name).is_some();
         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,10 +83,6 @@ 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}");
     }