Dynamic blocks: list a block as dynamic from its graph object without walking the graph's members

Listing blocks rebuilt a handle index of every kept foreign object for each
block with an extension dictionary, multiplying the block count by the object
count. The listing now builds one ObjectIndex and asks is_dynamic_block_in per
block; dynamic_block answers None before indexing when the block has no
extension dictionary.

templates() copied a value record's tags once per dictionary key, so a record
listed under many keys was copied many times, and it looked up each
dictionary entry by scanning every object. It now resolves entries through
its handle index and copies each record at most once (CWE-400, CWE-407).

crates/doc/src/dynblock.rs

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

crates/engine/src/cmd/blocks.rs

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