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