Extents: share block-bounds memoization across all the entities measured

Each top-level bounds call started with an empty block cache, so measuring a
space's extents or building a spatial-index chunk measured a block definition
again for every reference to it: R references to a block of B entities cost
R x B. BlockBoundsCache keeps the per-depth block bounds (separately for drawn
bounds and extents, which differ on layers turned off) across one bulk
operation; Drawing::extents and the spatial index use it (CWE-407).

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

@@ -94,25 +94,48 @@ 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)
+    bounds_of(d, e, depth, false, &mut HashMap::new())
 }
 
 /// 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)
+    bounds_of(d, e, 0, true, &mut HashMap::new())
 }
 
-fn bounds_of(d: &Drawing, e: &Entity, depth: usize, off_counts: bool) -> Bounds2 {
+/// 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 {
     // 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, &mut HashMap::new(), off_counts),
+            crate::AnnoDraw::Scaled(f) => return bounds_in(d, &crate::anno_scaled(e, f), 0, blocks, off_counts),
         }
     }
-    bounds_in(d, e, depth, &mut HashMap::new(), off_counts)
+    bounds_in(d, e, depth, blocks, off_counts)
 }
 
 /// [`entity_bounds`] with the bounds of block contents (in block coordinates) already computed,
@@ -442,4 +465,53 @@ 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::{MAX_BLOCK_DEPTH, entity_bounds, extent_bounds};
+pub use extents::{BlockBoundsCache, MAX_BLOCK_DEPTH, entity_bounds, entity_bounds_cached, extent_bounds, extent_bounds_cached};
 pub use format::Format;
 pub use gdt::*;
 pub use header::{HVal, Header};
@@ -383,10 +383,13 @@ 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(self, e));
+                    b = b.union(&extent_bounds_cached(self, e, &mut cache));
                 }
             }
         }

crates/engine/src/spatial.rs

@@ -15,7 +15,7 @@
 use std::collections::BTreeMap;
 use std::sync::{Arc, Mutex};
 
-use cadcraft_doc::{Block, DimStyle, Drawing, Entity, EntityKind, EntityStore, Space, entity_bounds};
+use cadcraft_doc::{Block, BlockBoundsCache, DimStyle, Drawing, Entity, EntityKind, EntityStore, Space, entity_bounds_cached};
 use cadcraft_geom::Bounds2;
 use rstar::primitives::{GeomWithData, Rectangle};
 use rstar::{AABB, RTree};
@@ -44,6 +44,8 @@ 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()
@@ -51,7 +53,7 @@ impl ChunkIx {
                 if matches!(e.kind, EntityKind::XLine(_) | EntityKind::Ray(_)) {
                     infinite.push(u32::try_from(i).unwrap_or(u32::MAX));
                 }
-                entity_bounds(d, e, 0)
+                entity_bounds_cached(d, e, 0, &mut cache)
             })
             .collect();
         let serial = NEXT_SERIAL.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
@@ -200,7 +202,7 @@ impl SpatialIndex {
         let (c, l) = self.locate(i)?;
         c.ents.get(l)
     }
-    /// The bounds of the entity at draw index `i` (as [`entity_bounds`] computes them).
+    /// The bounds of the entity at draw index `i` (as [`cadcraft_doc::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)
     }