1use crate::{
2 CanvasDocument, CanvasDocumentDiff, CanvasEdgeRouter, CanvasGeometryFacts, CanvasKindRegistry,
3 CanvasRecordId, EdgeId, HandleId, NodeId, ShapeId,
4 runtime_query::{hit_matches, query_matches},
5 spatial_cache::{dirty_record_ids, remove_record},
6};
7use open_gpui::{Bounds, Pixels, Point};
8use serde::{Deserialize, Serialize};
9
10#[derive(Clone, Debug, Eq, Hash, PartialEq, Serialize, Deserialize)]
11pub enum HitTarget {
12 Node(NodeId),
13 Handle {
14 node_id: NodeId,
15 handle_id: HandleId,
16 },
17 Shape(ShapeId),
18 Edge(EdgeId),
19}
20
21#[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
22pub struct HitRecord {
23 pub target: HitTarget,
24 pub bounds: Bounds<Pixels>,
25 pub z_index: i32,
26 pub hidden: bool,
27 pub locked: bool,
28}
29
30#[derive(Clone, Copy, Debug, PartialEq, Serialize, Deserialize)]
31pub struct HitOptions {
32 pub include_hidden: bool,
33 pub include_locked: bool,
34 pub include_handles: bool,
35 pub margin: Pixels,
36}
37
38impl Default for HitOptions {
39 fn default() -> Self {
40 Self {
41 include_hidden: false,
42 include_locked: false,
43 include_handles: false,
44 margin: Pixels::ZERO,
45 }
46 }
47}
48
49#[derive(Clone, Debug, Default, PartialEq)]
50pub struct SpatialIndex {
51 records: Vec<HitRecord>,
52}
53
54impl SpatialIndex {
55 pub fn rebuild(document: &CanvasDocument) -> Self {
56 Self::rebuild_with_facts(CanvasGeometryFacts::new(document))
57 }
58
59 pub fn rebuild_with_kind_registry(
60 document: &CanvasDocument,
61 kind_registry: &CanvasKindRegistry,
62 ) -> Self {
63 Self::rebuild_with_facts(CanvasGeometryFacts::with_kind_registry(
64 document,
65 kind_registry,
66 ))
67 }
68
69 pub fn rebuild_with_router<R>(document: &CanvasDocument, router: &R) -> Self
70 where
71 R: CanvasEdgeRouter + ?Sized,
72 {
73 Self::rebuild_with_facts(CanvasGeometryFacts::with_router(document, router))
74 }
75
76 pub fn rebuild_with_router_and_kind_registry<R>(
77 document: &CanvasDocument,
78 router: &R,
79 kind_registry: &CanvasKindRegistry,
80 ) -> Self
81 where
82 R: CanvasEdgeRouter + ?Sized,
83 {
84 Self::rebuild_with_facts(CanvasGeometryFacts::with_router_and_kind_registry(
85 document,
86 router,
87 Some(kind_registry),
88 ))
89 }
90
91 fn rebuild_with_facts<R>(facts: CanvasGeometryFacts<'_, R>) -> Self
92 where
93 R: CanvasEdgeRouter + Copy,
94 {
95 let mut records = facts.hit_records();
96 records.sort_by(|a, b| a.z_index.cmp(&b.z_index));
97 Self { records }
98 }
99
100 pub fn apply_diff(&mut self, document: &CanvasDocument, diff: &CanvasDocumentDiff) {
101 self.apply_diff_with_facts(CanvasGeometryFacts::new(document), diff);
102 }
103
104 pub fn apply_diff_with_kind_registry(
105 &mut self,
106 document: &CanvasDocument,
107 diff: &CanvasDocumentDiff,
108 kind_registry: &CanvasKindRegistry,
109 ) {
110 self.apply_diff_with_facts(
111 CanvasGeometryFacts::with_kind_registry(document, kind_registry),
112 diff,
113 );
114 }
115
116 pub fn apply_diff_with_router<R>(
117 &mut self,
118 document: &CanvasDocument,
119 diff: &CanvasDocumentDiff,
120 router: &R,
121 ) where
122 R: CanvasEdgeRouter + ?Sized,
123 {
124 self.apply_diff_with_facts(CanvasGeometryFacts::with_router(document, router), diff);
125 }
126
127 pub fn apply_diff_with_router_and_kind_registry<R>(
128 &mut self,
129 document: &CanvasDocument,
130 diff: &CanvasDocumentDiff,
131 router: &R,
132 kind_registry: &CanvasKindRegistry,
133 ) where
134 R: CanvasEdgeRouter + ?Sized,
135 {
136 self.apply_diff_with_facts(
137 CanvasGeometryFacts::with_router_and_kind_registry(
138 document,
139 router,
140 Some(kind_registry),
141 ),
142 diff,
143 );
144 }
145
146 fn apply_diff_with_facts<R>(
147 &mut self,
148 facts: CanvasGeometryFacts<'_, R>,
149 diff: &CanvasDocumentDiff,
150 ) where
151 R: CanvasEdgeRouter + Copy,
152 {
153 if diff.is_empty() {
154 return;
155 }
156
157 let dirty = dirty_record_ids(facts.document(), diff);
158
159 for record_id in &dirty {
160 remove_record(&mut self.records, record_id);
161 }
162
163 for record_id in &dirty {
164 self.refresh_record_with_facts(facts, record_id);
165 }
166
167 self.records.sort_by(|a, b| a.z_index.cmp(&b.z_index));
168 }
169
170 pub fn query(&self, viewport: Bounds<Pixels>) -> impl Iterator<Item = &HitRecord> {
171 self.query_with_options(
172 viewport,
173 HitOptions {
174 include_locked: true,
175 ..HitOptions::default()
176 },
177 )
178 }
179
180 pub fn query_with_options(
181 &self,
182 viewport: Bounds<Pixels>,
183 options: HitOptions,
184 ) -> impl Iterator<Item = &HitRecord> {
185 self.records
186 .iter()
187 .filter(move |record| query_matches(record, viewport, options))
188 }
189
190 pub fn hit_test(
191 &self,
192 point: Point<Pixels>,
193 options: HitOptions,
194 ) -> impl Iterator<Item = &HitRecord> {
195 self.records
196 .iter()
197 .rev()
198 .filter(move |record| hit_matches(record, point, options))
199 }
200
201 pub fn records(&self) -> &[HitRecord] {
202 &self.records
203 }
204
205 fn refresh_record_with_facts<R>(
206 &mut self,
207 facts: CanvasGeometryFacts<'_, R>,
208 record_id: &CanvasRecordId,
209 ) where
210 R: CanvasEdgeRouter + Copy,
211 {
212 remove_record(&mut self.records, record_id);
213 self.records.extend(facts.hit_records_for_record(record_id));
214 }
215}
216
217#[cfg(test)]
218mod tests {
219 use super::*;
220 use crate::{
221 CanvasDocument, CanvasEdge, CanvasEdgeRouter, CanvasEndpoint, CanvasNode, CanvasRoutePath,
222 CanvasRouteRequest, CanvasShape, CanvasTransaction, DocumentCommand,
223 test_support::{CanvasCommandGenerator, TestRng, document_fixture},
224 };
225 use open_gpui::{Bounds, point, px, size};
226 use std::cmp::Ordering;
227
228 #[test]
229 fn hit_test_returns_topmost_first() {
230 let mut back = CanvasNode::new("back", point(px(0.0), px(0.0)), size(px(100.0), px(100.0)));
231 back.z_index = 1;
232 let mut front = CanvasShape::new(
233 "front",
234 Bounds::new(point(px(0.0), px(0.0)), size(px(100.0), px(100.0))),
235 );
236 front.z_index = 2;
237 let document = document_fixture().node(back).shape(front).build();
238
239 let index = SpatialIndex::rebuild(&document);
240 let hits = index
241 .hit_test(point(px(50.0), px(50.0)), HitOptions::default())
242 .map(|record| record.target.clone())
243 .collect::<Vec<_>>();
244
245 assert_eq!(
246 hits,
247 vec![
248 HitTarget::Shape(ShapeId::from("front")),
249 HitTarget::Node(NodeId::from("back"))
250 ]
251 );
252 }
253
254 #[test]
255 fn query_culls_outside_records() {
256 let document = document_fixture()
257 .node(CanvasNode::new(
258 "inside",
259 point(px(0.0), px(0.0)),
260 size(px(10.0), px(10.0)),
261 ))
262 .node(CanvasNode::new(
263 "outside",
264 point(px(100.0), px(100.0)),
265 size(px(10.0), px(10.0)),
266 ))
267 .build();
268
269 let index = SpatialIndex::rebuild(&document);
270 let visible = index
271 .query(Bounds::new(
272 point(px(0.0), px(0.0)),
273 size(px(50.0), px(50.0)),
274 ))
275 .map(|record| record.target.clone())
276 .collect::<Vec<_>>();
277
278 assert_eq!(visible, vec![HitTarget::Node(NodeId::from("inside"))]);
279 }
280
281 #[test]
282 fn hidden_records_are_only_returned_when_requested() {
283 let mut node = CanvasNode::new("hidden", point(px(0.0), px(0.0)), size(px(10.0), px(10.0)));
284 node.hidden = true;
285 let document = document_fixture().node(node).build();
286
287 let index = SpatialIndex::rebuild(&document);
288 assert!(
289 index
290 .hit_test(point(px(5.0), px(5.0)), HitOptions::default())
291 .next()
292 .is_none()
293 );
294
295 let options = HitOptions {
296 include_hidden: true,
297 ..HitOptions::default()
298 };
299 assert_eq!(
300 index
301 .hit_test(point(px(5.0), px(5.0)), options)
302 .map(|record| record.target.clone())
303 .collect::<Vec<_>>(),
304 vec![HitTarget::Node(NodeId::from("hidden"))]
305 );
306 }
307
308 #[test]
309 fn locked_records_are_skipped_by_hit_test_unless_requested() {
310 let mut node = CanvasNode::new("locked", point(px(0.0), px(0.0)), size(px(10.0), px(10.0)));
311 node.locked = true;
312 let document = document_fixture().node(node).build();
313
314 let index = SpatialIndex::rebuild(&document);
315 assert!(
316 index
317 .hit_test(point(px(5.0), px(5.0)), HitOptions::default())
318 .next()
319 .is_none()
320 );
321
322 let options = HitOptions {
323 include_locked: true,
324 ..HitOptions::default()
325 };
326 assert_eq!(
327 index
328 .hit_test(point(px(5.0), px(5.0)), options)
329 .map(|record| (record.target.clone(), record.locked))
330 .collect::<Vec<_>>(),
331 vec![(HitTarget::Node(NodeId::from("locked")), true)]
332 );
333 }
334
335 #[test]
336 fn query_returns_locked_records_for_culling() {
337 let mut node = CanvasNode::new("locked", point(px(0.0), px(0.0)), size(px(10.0), px(10.0)));
338 node.locked = true;
339 let document = document_fixture().node(node).build();
340
341 let index = SpatialIndex::rebuild(&document);
342 let records = index
343 .query(Bounds::new(
344 point(px(0.0), px(0.0)),
345 size(px(20.0), px(20.0)),
346 ))
347 .map(|record| (record.target.clone(), record.locked))
348 .collect::<Vec<_>>();
349
350 assert_eq!(
351 records,
352 vec![(HitTarget::Node(NodeId::from("locked")), true)]
353 );
354 }
355
356 #[test]
357 fn edge_bounds_are_indexed_from_route_hit_area() {
358 use crate::{CanvasEdge, CanvasEndpoint};
359
360 let document = document_fixture()
361 .node(CanvasNode::new(
362 "a",
363 point(px(0.0), px(0.0)),
364 size(px(20.0), px(20.0)),
365 ))
366 .node(CanvasNode::new(
367 "b",
368 point(px(100.0), px(0.0)),
369 size(px(20.0), px(20.0)),
370 ))
371 .edge(CanvasEdge::new(
372 "a-b",
373 CanvasEndpoint::new("a", None::<&str>),
374 CanvasEndpoint::new("b", None::<&str>),
375 ))
376 .build();
377
378 let index = SpatialIndex::rebuild(&document);
379 assert!(index.records().iter().any(|record| {
380 record.target == HitTarget::Edge(EdgeId::from("a-b"))
381 && record.bounds.origin == point(px(4.0), px(4.0))
382 && record.bounds.size.width == px(112.0)
383 && record.bounds.size.height == px(12.0)
384 }));
385 }
386
387 #[test]
388 fn custom_router_flows_through_edge_culling_and_hit_testing() {
389 let document = connected_document_for_router();
390 let index = SpatialIndex::rebuild_with_router(&document, &VerticalDetourRouter);
391
392 let visible = index
393 .query(Bounds::new(
394 point(px(0.0), px(76.0)),
395 size(px(12.0), px(12.0)),
396 ))
397 .map(|record| record.target.clone())
398 .collect::<Vec<_>>();
399 assert_eq!(visible, vec![HitTarget::Edge(EdgeId::from("a-b"))]);
400
401 let hits = index
402 .hit_test(point(px(5.0), px(80.0)), HitOptions::default())
403 .map(|record| record.target.clone())
404 .collect::<Vec<_>>();
405 assert_eq!(hits, vec![HitTarget::Edge(EdgeId::from("a-b"))]);
406 }
407
408 #[test]
409 fn custom_router_flows_through_incremental_edge_refresh() {
410 let mut document = connected_document_for_router();
411 let mut index = SpatialIndex::rebuild_with_router(&document, &VerticalDetourRouter);
412 let mut target = document.node(&NodeId::from("b")).unwrap().clone();
413 target.position = point(px(40.0), px(0.0));
414
415 let diff = document
416 .apply_transaction_with_diff(CanvasTransaction::single(DocumentCommand::UpdateNode(
417 target,
418 )))
419 .unwrap();
420 index.apply_diff_with_router(&document, &diff, &VerticalDetourRouter);
421
422 assert!(index.records().iter().any(|record| {
423 record.target == HitTarget::Edge(EdgeId::from("a-b"))
424 && record.bounds.origin == point(px(-1.0), px(-1.0))
425 && record.bounds.size == size(px(52.0), px(87.0))
426 }));
427 }
428
429 #[test]
430 fn handles_are_hit_only_when_requested() {
431 use crate::CanvasHandle;
432
433 let mut node = CanvasNode::new("a", point(px(0.0), px(0.0)), size(px(100.0), px(100.0)));
434 node.handles
435 .push(CanvasHandle::new("out", point(px(95.0), px(50.0))));
436 let document = document_fixture().node(node).build();
437
438 let index = SpatialIndex::rebuild(&document);
439 let point = point(px(95.0), px(50.0));
440 assert_eq!(
441 index
442 .hit_test(point, HitOptions::default())
443 .map(|record| record.target.clone())
444 .collect::<Vec<_>>(),
445 vec![HitTarget::Node(NodeId::from("a"))]
446 );
447
448 let options = HitOptions {
449 include_handles: true,
450 ..HitOptions::default()
451 };
452 assert_eq!(
453 index
454 .hit_test(point, options)
455 .map(|record| record.target.clone())
456 .collect::<Vec<_>>(),
457 vec![
458 HitTarget::Handle {
459 node_id: NodeId::from("a"),
460 handle_id: HandleId::from("out"),
461 },
462 HitTarget::Node(NodeId::from("a")),
463 ]
464 );
465 }
466
467 #[test]
468 fn hidden_handles_are_only_hit_when_hidden_records_are_requested() {
469 use crate::CanvasHandle;
470
471 let mut node = CanvasNode::new("a", point(px(0.0), px(0.0)), size(px(100.0), px(100.0)));
472 let mut handle = CanvasHandle::new("hidden", point(px(95.0), px(50.0)));
473 handle.hidden = true;
474 node.handles.push(handle);
475 let document = document_fixture().node(node).build();
476
477 let index = SpatialIndex::rebuild(&document);
478 let point = point(px(95.0), px(50.0));
479 let visible_options = HitOptions {
480 include_handles: true,
481 ..HitOptions::default()
482 };
483
484 assert_eq!(
485 index
486 .hit_test(point, visible_options)
487 .map(|record| record.target.clone())
488 .collect::<Vec<_>>(),
489 vec![HitTarget::Node(NodeId::from("a"))]
490 );
491
492 let hidden_options = HitOptions {
493 include_hidden: true,
494 include_handles: true,
495 ..HitOptions::default()
496 };
497 assert_eq!(
498 index
499 .hit_test(point, hidden_options)
500 .map(|record| record.target.clone())
501 .collect::<Vec<_>>(),
502 vec![
503 HitTarget::Handle {
504 node_id: NodeId::from("a"),
505 handle_id: HandleId::from("hidden"),
506 },
507 HitTarget::Node(NodeId::from("a")),
508 ]
509 );
510 }
511
512 #[test]
513 fn applies_diff_for_inserted_records() {
514 let previous = document_fixture().build();
515 let mut document = previous.clone();
516 let diff = document
517 .apply_transaction_with_diff(CanvasTransaction::single(DocumentCommand::InsertNode(
518 CanvasNode::new("a", point(px(0.0), px(0.0)), size(px(10.0), px(10.0))),
519 )))
520 .unwrap();
521
522 let mut index = SpatialIndex::rebuild(&previous);
523 index.apply_diff(&document, &diff);
524
525 assert_eq!(
526 index
527 .hit_test(point(px(5.0), px(5.0)), HitOptions::default())
528 .map(|record| record.target.clone())
529 .collect::<Vec<_>>(),
530 vec![HitTarget::Node(NodeId::from("a"))]
531 );
532 }
533
534 #[test]
535 fn applies_diff_for_moved_node_and_incident_edge() {
536 use crate::{CanvasEdge, CanvasEndpoint};
537
538 let previous = document_fixture()
539 .node(CanvasNode::new(
540 "a",
541 point(px(0.0), px(0.0)),
542 size(px(20.0), px(20.0)),
543 ))
544 .node(CanvasNode::new(
545 "b",
546 point(px(100.0), px(0.0)),
547 size(px(20.0), px(20.0)),
548 ))
549 .edge(CanvasEdge::new(
550 "a-b",
551 CanvasEndpoint::new("a", None::<&str>),
552 CanvasEndpoint::new("b", None::<&str>),
553 ))
554 .build();
555
556 let mut document = previous.clone();
557 let mut node = document.node(&NodeId::from("a")).unwrap().clone();
558 node.position = point(px(40.0), px(0.0));
559 let diff = document
560 .apply_transaction_with_diff(CanvasTransaction::single(DocumentCommand::UpdateNode(
561 node,
562 )))
563 .unwrap();
564
565 let mut index = SpatialIndex::rebuild(&previous);
566 index.apply_diff(&document, &diff);
567
568 assert!(index.records().iter().any(|record| {
569 record.target == HitTarget::Edge(EdgeId::from("a-b"))
570 && record.bounds.origin == point(px(44.0), px(4.0))
571 && record.bounds.size.width == px(72.0)
572 && record.bounds.size.height == px(12.0)
573 }));
574 }
575
576 #[test]
577 fn applies_diff_for_updated_edge_route() {
578 use crate::{CanvasEdge, CanvasEdgeRoute, CanvasEndpoint};
579
580 let previous = document_fixture()
581 .node(CanvasNode::new(
582 "a",
583 point(px(0.0), px(0.0)),
584 size(px(20.0), px(20.0)),
585 ))
586 .node(CanvasNode::new(
587 "b",
588 point(px(100.0), px(0.0)),
589 size(px(20.0), px(20.0)),
590 ))
591 .edge(CanvasEdge::new(
592 "a-b",
593 CanvasEndpoint::new("a", None::<&str>),
594 CanvasEndpoint::new("b", None::<&str>),
595 ))
596 .build();
597
598 let mut document = previous.clone();
599 let mut edge = document.edge(&EdgeId::from("a-b")).unwrap().clone();
600 edge.route = CanvasEdgeRoute::polyline([point(px(60.0), px(80.0))]);
601 edge.route.interaction_width = px(20.0);
602 let diff = document
603 .apply_transaction_with_diff(CanvasTransaction::single(DocumentCommand::UpdateEdge(
604 edge,
605 )))
606 .unwrap();
607
608 let mut index = SpatialIndex::rebuild(&previous);
609 index.apply_diff(&document, &diff);
610
611 assert!(index.records().iter().any(|record| {
612 record.target == HitTarget::Edge(EdgeId::from("a-b"))
613 && record.bounds.origin == point(px(0.0), px(0.0))
614 && record.bounds.size == size(px(120.0), px(90.0))
615 }));
616 }
617
618 #[test]
619 fn incremental_index_matches_rebuild_after_random_diffs() {
620 let mut rng = TestRng::new(0x4b65_9072_e9c1_fab3);
621 let mut generator = CanvasCommandGenerator::default();
622 let mut document = document_fixture().build();
623 let mut index = SpatialIndex::rebuild(&document);
624
625 for _ in 0..192 {
626 let command = generator.next_command(&document, &mut rng);
627 let diff = document
628 .apply_transaction_with_diff(CanvasTransaction::single(command))
629 .unwrap();
630 index.apply_diff(&document, &diff);
631
632 let rebuilt = SpatialIndex::rebuild(&document);
633 assert_eq!(sorted_records(&index), sorted_records(&rebuilt));
634 }
635 }
636
637 fn sorted_records(index: &SpatialIndex) -> Vec<HitRecord> {
638 let mut records = index.records().to_vec();
639 records.sort_by(compare_hit_records);
640 records
641 }
642
643 fn compare_hit_records(left: &HitRecord, right: &HitRecord) -> Ordering {
644 target_key(&left.target)
645 .cmp(&target_key(&right.target))
646 .then_with(|| left.z_index.cmp(&right.z_index))
647 .then_with(|| left.hidden.cmp(&right.hidden))
648 .then_with(|| left.locked.cmp(&right.locked))
649 }
650
651 fn target_key(target: &HitTarget) -> (u8, String, String) {
652 match target {
653 HitTarget::Node(id) => (0, id.to_string(), String::new()),
654 HitTarget::Handle { node_id, handle_id } => {
655 (1, node_id.to_string(), handle_id.to_string())
656 }
657 HitTarget::Shape(id) => (2, id.to_string(), String::new()),
658 HitTarget::Edge(id) => (3, id.to_string(), String::new()),
659 }
660 }
661
662 fn connected_document_for_router() -> CanvasDocument {
663 document_fixture()
664 .node(CanvasNode::new(
665 "a",
666 point(px(0.0), px(0.0)),
667 size(px(10.0), px(10.0)),
668 ))
669 .node(CanvasNode::new(
670 "b",
671 point(px(20.0), px(0.0)),
672 size(px(10.0), px(10.0)),
673 ))
674 .edge(CanvasEdge::new(
675 "a-b",
676 CanvasEndpoint::new("a", None::<&str>),
677 CanvasEndpoint::new("b", None::<&str>),
678 ))
679 .build()
680 }
681
682 struct VerticalDetourRouter;
683
684 impl CanvasEdgeRouter for VerticalDetourRouter {
685 fn route_edge(&self, request: CanvasRouteRequest<'_>) -> CanvasRoutePath {
686 CanvasRoutePath::polyline([
687 request.source,
688 point(request.source.x, px(80.0)),
689 request.target,
690 ])
691 }
692 }
693}