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/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/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/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)
     }

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}");
     }