Regions: test a loop's probe only against loops whose box holds it, within a budget

Region::renest tested every loop's probe point against every other
tessellated loop, scanning all of its edges each time, so the work was the
loop count times the total vertex count. It now skips loops whose bounding
box does not hold the probe, and stops once MAX_RENEST_EDGE_VISITS edge tests
have been spent, leaving the flags unchanged and returning false; UNION,
SUBTRACT and INTERSECT then report the regions as too complex to combine, as
they already do for too many boundary pairs (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/region.rs

@@ -9,6 +9,9 @@ use super::HatchLoop;
 /// Most loops one region has (hostile files and edits).
 pub const MAX_REGION_LOOPS: usize = 10_000;
 
+/// Most polygon edges [`Region::renest`] tests, over all its point-in-loop tests.
+pub const MAX_RENEST_EDGE_VISITS: usize = 50_000_000;
+
 #[derive(Clone, Debug, Default, PartialEq, Serialize, Deserialize)]
 pub struct Region {
     /// Closed loops with bulges; `outer` false for islands.
@@ -76,20 +79,49 @@ impl Region {
     }
 
     /// Set each loop's `outer` flag from how deeply other loops enclose it: an even depth is
-    /// an outer loop, odd an island.
-    pub fn renest(&mut self) {
+    /// an outer loop, odd an island. `false`, with the flags left as they were, when that takes
+    /// more than [`MAX_RENEST_EDGE_VISITS`] polygon edge tests.
+    #[must_use]
+    pub fn renest(&mut self) -> bool {
         let polys = self.tessellate(self.fine_tol());
-        let depth: Vec<usize> = polys
+        // A loop's probe can only be inside loops whose box holds it: test only those. A box with
+        // a non-finite corner says nothing (an edge through a non-finite point never counts, so
+        // such a polygon need not be closed), so its loop is always tested.
+        let boxes: Vec<Option<Bounds2>> = polys
             .iter()
-            .enumerate()
-            .map(|(i, l)| {
-                let Some(p) = probe(l) else { return 0 };
-                polys.iter().enumerate().filter(|(j, o)| *j != i && point_in_polygon(o, p)).count()
+            .map(|l| {
+                let b = Bounds2::from_points(l.iter().copied());
+                (l.iter().all(|p| p.is_finite()) && b.min.is_finite() && b.max.is_finite()).then_some(b)
             })
             .collect();
+        let mut visits = 0usize;
+        let mut depth = Vec::with_capacity(polys.len());
+        for (i, l) in polys.iter().enumerate() {
+            let Some(p) = probe(l) else {
+                depth.push(0);
+                continue;
+            };
+            let mut d = 0;
+            for (j, (o, b)) in polys.iter().zip(&boxes).enumerate() {
+                if j == i || b.is_some_and(|b| !b.contains(p)) {
+                    continue;
+                }
+                // Each loop against every other is loops x vertices: bounded so a region of many
+                // large nested loops cannot hold the thread (CWE-407).
+                visits = visits.saturating_add(o.len());
+                if visits > MAX_RENEST_EDGE_VISITS {
+                    return false;
+                }
+                if point_in_polygon(o, p) {
+                    d += 1;
+                }
+            }
+            depth.push(d);
+        }
         for (l, d) in self.loops.iter_mut().zip(depth) {
             l.outer = d % 2 == 0;
         }
+        true
     }
 
     /// Area, perimeter, bounding box, centroid and second moments (outer loops counted
@@ -128,3 +160,37 @@ fn probe(l: &[Vec2]) -> Option<Vec2> {
         (a.dist(b) > 1e-12).then(|| (a + b) * 0.5).filter(|m| m.is_finite())
     })
 }
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    fn square(c: f64, half: f64, n: usize, outer: bool) -> HatchLoop {
+        // `n` vertices along the bottom edge, then the other three corners.
+        let mut vertices: Vec<PolyVertex> =
+            (0..n).map(|k| PolyVertex::new(Vec2::new(c - half + 2.0 * half * k as f64 / n as f64, c - half))).collect();
+        vertices.extend([Vec2::new(c + half, c - half), Vec2::new(c + half, c + half), Vec2::new(c - half, c + half)].map(PolyVertex::new));
+        HatchLoop { vertices, outer, sources: Vec::new() }
+    }
+
+    #[test]
+    fn renest_sets_depth_parity_and_skips_loops_far_away() {
+        // Three nested squares, and one beside them.
+        let mut r =
+            Region { loops: vec![square(0.0, 3.0, 1, false), square(0.0, 2.0, 1, false), square(0.0, 1.0, 1, false), square(10.0, 1.0, 1, false)] };
+        assert!(r.renest());
+        assert_eq!(r.loops.iter().map(|l| l.outer).collect::<Vec<_>>(), [true, false, true, true]);
+    }
+
+    #[test]
+    fn renest_of_many_large_nested_loops_stops_at_its_budget() {
+        // Concentric loops of many vertices each: each probe is inside the box of every larger
+        // loop (about loops² / 2 pairs), so each of those tests is a full polygon scan.
+        let loops = 300;
+        let n = 3 * MAX_RENEST_EDGE_VISITS / (loops * loops);
+        let mut r = Region { loops: (0..loops).map(|i| square(0.0, 1.0 + i as f64, n, false)).collect() };
+        let before = r.clone();
+        assert!(!r.renest());
+        assert_eq!(r, before, "flags left as they were");
+    }
+}

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/src/cmd/inquiry/regions.rs

@@ -128,7 +128,9 @@ fn combine(a: &Region, b: &Region, op: Op) -> Result<Option<Region>> {
     }
     loops.retain(|l| l.vertices.len() >= 2);
     let mut r = Region { loops };
-    r.renest();
+    if !r.renest() {
+        return Err(other("These regions are too complex to combine."));
+    }
     Ok(Some(r))
 }
 

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