1use crate::{
2 CanvasDocument, CanvasDocumentDiff, CanvasEdge, CanvasEndpoint, CanvasHandle, CanvasNode,
3 CanvasRecordId, EdgeId, NodeId,
4};
5use indexmap::{IndexMap, IndexSet};
6use serde::{Deserialize, Serialize};
7
8#[derive(Clone, Copy, Debug, Eq, PartialEq, Serialize, Deserialize)]
9pub enum CanvasEdgeDirection {
10 Incoming,
11 Outgoing,
12 Any,
13}
14
15#[derive(Clone, Copy, Debug)]
16pub struct CanvasGraph<'a> {
17 document: &'a CanvasDocument,
18}
19
20impl<'a> CanvasGraph<'a> {
21 pub fn new(document: &'a CanvasDocument) -> Self {
22 Self { document }
23 }
24
25 pub fn document(&self) -> &'a CanvasDocument {
26 self.document
27 }
28
29 pub fn node(&self, id: &NodeId) -> Option<&'a CanvasNode> {
30 self.document.node(id)
31 }
32
33 pub fn edge(&self, id: &EdgeId) -> Option<&'a CanvasEdge> {
34 self.document.edge(id)
35 }
36
37 pub fn endpoint_node(&self, endpoint: &CanvasEndpoint) -> Option<&'a CanvasNode> {
38 self.node(&endpoint.node_id)
39 }
40
41 pub fn endpoint_handle(&self, endpoint: &CanvasEndpoint) -> Option<&'a CanvasHandle> {
42 let handle_id = endpoint.handle_id.as_ref()?;
43 self.endpoint_node(endpoint)?.handle(Some(handle_id))
44 }
45
46 pub fn outgoing_edges<'q>(
47 &'q self,
48 node_id: &'q NodeId,
49 ) -> impl Iterator<Item = &'a CanvasEdge> + 'q
50 where
51 'a: 'q,
52 {
53 self.edges_for_node(node_id, CanvasEdgeDirection::Outgoing)
54 }
55
56 pub fn incoming_edges<'q>(
57 &'q self,
58 node_id: &'q NodeId,
59 ) -> impl Iterator<Item = &'a CanvasEdge> + 'q
60 where
61 'a: 'q,
62 {
63 self.edges_for_node(node_id, CanvasEdgeDirection::Incoming)
64 }
65
66 pub fn incident_edges<'q>(
67 &'q self,
68 node_id: &'q NodeId,
69 ) -> impl Iterator<Item = &'a CanvasEdge> + 'q
70 where
71 'a: 'q,
72 {
73 self.edges_for_node(node_id, CanvasEdgeDirection::Any)
74 }
75
76 pub fn edges_for_node<'q>(
77 &'q self,
78 node_id: &'q NodeId,
79 direction: CanvasEdgeDirection,
80 ) -> impl Iterator<Item = &'a CanvasEdge> + 'q
81 where
82 'a: 'q,
83 {
84 let document = self.document;
85 document
86 .edges()
87 .filter(move |edge| edge_matches_node(edge, node_id, direction))
88 }
89
90 pub fn edges_between<'q>(
91 &'q self,
92 source: &'q NodeId,
93 target: &'q NodeId,
94 ) -> impl Iterator<Item = &'a CanvasEdge> + 'q
95 where
96 'a: 'q,
97 {
98 let document = self.document;
99 document
100 .edges()
101 .filter(move |edge| edge.source.node_id == *source && edge.target.node_id == *target)
102 }
103
104 pub fn has_edge_between(&self, source: &NodeId, target: &NodeId) -> bool {
105 self.edges_between(source, target).next().is_some()
106 }
107
108 pub fn neighbor_node_ids<'q>(
109 &'q self,
110 node_id: &'q NodeId,
111 direction: CanvasEdgeDirection,
112 ) -> impl Iterator<Item = &'a NodeId> + 'q
113 where
114 'a: 'q,
115 {
116 let document = self.document;
117 document
118 .edges()
119 .filter_map(move |edge| neighbor_node_id(edge, node_id, direction))
120 }
121
122 pub fn incident_edge_count(&self, node_id: &NodeId) -> usize {
123 self.incident_edges(node_id).count()
124 }
125}
126
127impl CanvasDocument {
128 pub fn graph(&self) -> CanvasGraph<'_> {
129 CanvasGraph::new(self)
130 }
131
132 pub fn graph_index(&self) -> CanvasGraphIndex {
133 CanvasGraphIndex::rebuild(self)
134 }
135}
136
137#[derive(Clone, Debug, Eq, PartialEq, Serialize, Deserialize)]
138pub struct CanvasGraphEndpointIds {
139 pub source: NodeId,
140 pub target: NodeId,
141}
142
143impl CanvasGraphEndpointIds {
144 pub fn new(source: impl Into<NodeId>, target: impl Into<NodeId>) -> Self {
145 Self {
146 source: source.into(),
147 target: target.into(),
148 }
149 }
150
151 pub fn from_edge(edge: &CanvasEdge) -> Self {
152 Self {
153 source: edge.source.node_id.clone(),
154 target: edge.target.node_id.clone(),
155 }
156 }
157}
158
159#[derive(Clone, Debug, Default, Eq, PartialEq, Serialize, Deserialize)]
160pub struct CanvasGraphIndex {
161 outgoing: IndexMap<NodeId, IndexSet<EdgeId>>,
162 incoming: IndexMap<NodeId, IndexSet<EdgeId>>,
163 incident: IndexMap<NodeId, IndexSet<EdgeId>>,
164 edge_endpoints: IndexMap<EdgeId, CanvasGraphEndpointIds>,
165 #[serde(default, skip)]
166 edge_ordinals: IndexMap<EdgeId, usize>,
167}
168
169impl CanvasGraphIndex {
170 pub fn rebuild(document: &CanvasDocument) -> Self {
171 let mut index = Self::default();
172 for edge in document.edges() {
173 index.insert_edge(edge);
174 }
175 index.refresh_edge_ordinals(document);
176 index
177 }
178
179 pub fn apply_diff(&mut self, document: &CanvasDocument, diff: &CanvasDocumentDiff) {
180 if diff.is_empty() {
181 return;
182 }
183
184 let mut graph_changed = false;
185
186 for record_id in &diff.removed {
187 match record_id {
188 CanvasRecordId::Edge(edge_id) => {
189 graph_changed |= self.remove_edge_id(edge_id);
190 }
191 CanvasRecordId::Node(node_id) => {
192 let edge_ids = self.incident_edge_ids(node_id).cloned().collect::<Vec<_>>();
193 for edge_id in edge_ids {
194 graph_changed |= self.remove_edge_id(&edge_id);
195 }
196 }
197 CanvasRecordId::Shape(_) => {}
198 }
199 }
200
201 for record_id in &diff.updated {
202 if let CanvasRecordId::Edge(edge_id) = record_id
203 && let Some(endpoints) = self.edge_endpoints.get(edge_id).cloned()
204 && document.edge(edge_id).is_some_and(|edge| {
205 edge.source.node_id != endpoints.source
206 || edge.target.node_id != endpoints.target
207 })
208 {
209 graph_changed |= self.remove_edge_id(edge_id);
210 }
211 }
212
213 for record_id in diff.updated.iter().chain(&diff.inserted) {
214 if let CanvasRecordId::Edge(edge_id) = record_id
215 && let Some(edge) = document.edge(edge_id)
216 && !self.edge_endpoints.contains_key(edge_id)
217 {
218 self.insert_edge(edge);
219 graph_changed = true;
220 }
221 }
222
223 if graph_changed {
224 self.refresh_edge_ordinals(document);
225 self.sort_adjacency_by_edge_ordinals();
226 }
227 }
228
229 pub fn graph<'a>(&'a self, document: &'a CanvasDocument) -> CanvasIndexedGraph<'a> {
230 CanvasIndexedGraph::new(document, self)
231 }
232
233 pub fn edge_count(&self) -> usize {
234 self.edge_endpoints.len()
235 }
236
237 pub fn is_empty(&self) -> bool {
238 self.edge_endpoints.is_empty()
239 }
240
241 pub fn contains_edge(&self, edge_id: &EdgeId) -> bool {
242 self.edge_endpoints.contains_key(edge_id)
243 }
244
245 pub fn edge_endpoints(&self, edge_id: &EdgeId) -> Option<&CanvasGraphEndpointIds> {
246 self.edge_endpoints.get(edge_id)
247 }
248
249 pub fn outgoing_edge_ids<'a>(
250 &'a self,
251 node_id: &NodeId,
252 ) -> impl Iterator<Item = &'a EdgeId> + 'a {
253 self.outgoing
254 .get(node_id)
255 .into_iter()
256 .flat_map(|edge_ids| edge_ids.iter())
257 }
258
259 pub fn incoming_edge_ids<'a>(
260 &'a self,
261 node_id: &NodeId,
262 ) -> impl Iterator<Item = &'a EdgeId> + 'a {
263 self.incoming
264 .get(node_id)
265 .into_iter()
266 .flat_map(|edge_ids| edge_ids.iter())
267 }
268
269 pub fn incident_edge_ids<'a>(
270 &'a self,
271 node_id: &NodeId,
272 ) -> impl Iterator<Item = &'a EdgeId> + 'a {
273 self.incident
274 .get(node_id)
275 .into_iter()
276 .flat_map(|edge_ids| edge_ids.iter())
277 }
278
279 pub fn edge_ids_for_node<'a>(
280 &'a self,
281 node_id: &'a NodeId,
282 direction: CanvasEdgeDirection,
283 ) -> Box<dyn Iterator<Item = &'a EdgeId> + 'a> {
284 match direction {
285 CanvasEdgeDirection::Incoming => Box::new(self.incoming_edge_ids(node_id)),
286 CanvasEdgeDirection::Outgoing => Box::new(self.outgoing_edge_ids(node_id)),
287 CanvasEdgeDirection::Any => Box::new(self.incident_edge_ids(node_id)),
288 }
289 }
290
291 pub fn edge_ids_between<'a>(
292 &'a self,
293 source: &'a NodeId,
294 target: &'a NodeId,
295 ) -> impl Iterator<Item = &'a EdgeId> + 'a {
296 self.outgoing_edge_ids(source).filter(move |edge_id| {
297 self.edge_endpoints
298 .get(*edge_id)
299 .is_some_and(|endpoints| endpoints.source == *source && endpoints.target == *target)
300 })
301 }
302
303 pub fn has_edge_between(&self, source: &NodeId, target: &NodeId) -> bool {
304 self.edge_ids_between(source, target).next().is_some()
305 }
306
307 pub fn neighbor_node_ids<'a>(
308 &'a self,
309 node_id: &'a NodeId,
310 direction: CanvasEdgeDirection,
311 ) -> Box<dyn Iterator<Item = &'a NodeId> + 'a> {
312 match direction {
313 CanvasEdgeDirection::Incoming => {
314 Box::new(self.incoming_edge_ids(node_id).filter_map(move |edge_id| {
315 self.edge_endpoints
316 .get(edge_id)
317 .map(|endpoints| &endpoints.source)
318 }))
319 }
320 CanvasEdgeDirection::Outgoing => {
321 Box::new(self.outgoing_edge_ids(node_id).filter_map(move |edge_id| {
322 self.edge_endpoints
323 .get(edge_id)
324 .map(|endpoints| &endpoints.target)
325 }))
326 }
327 CanvasEdgeDirection::Any => {
328 Box::new(self.incident_edge_ids(node_id).filter_map(move |edge_id| {
329 let endpoints = self.edge_endpoints.get(edge_id)?;
330 if endpoints.source == *node_id {
331 Some(&endpoints.target)
332 } else {
333 Some(&endpoints.source)
334 }
335 }))
336 }
337 }
338 }
339
340 pub fn incident_edge_count(&self, node_id: &NodeId) -> usize {
341 self.incident_edge_ids(node_id).count()
342 }
343
344 fn insert_edge(&mut self, edge: &CanvasEdge) {
345 if self.edge_endpoints.contains_key(&edge.id) {
346 self.remove_edge_id(&edge.id);
347 }
348 let endpoints = CanvasGraphEndpointIds::from_edge(edge);
349 self.outgoing
350 .entry(endpoints.source.clone())
351 .or_default()
352 .insert(edge.id.clone());
353 self.incoming
354 .entry(endpoints.target.clone())
355 .or_default()
356 .insert(edge.id.clone());
357 self.incident
358 .entry(endpoints.source.clone())
359 .or_default()
360 .insert(edge.id.clone());
361 if endpoints.source != endpoints.target {
362 self.incident
363 .entry(endpoints.target.clone())
364 .or_default()
365 .insert(edge.id.clone());
366 }
367 self.edge_endpoints.insert(edge.id.clone(), endpoints);
368 }
369
370 fn remove_edge_id(&mut self, edge_id: &EdgeId) -> bool {
371 let Some(endpoints) = self.edge_endpoints.shift_remove(edge_id) else {
372 return false;
373 };
374 self.edge_ordinals.shift_remove(edge_id);
375 remove_edge_from_node(&mut self.outgoing, &endpoints.source, edge_id);
376 remove_edge_from_node(&mut self.incoming, &endpoints.target, edge_id);
377 remove_edge_from_node(&mut self.incident, &endpoints.source, edge_id);
378 if endpoints.source != endpoints.target {
379 remove_edge_from_node(&mut self.incident, &endpoints.target, edge_id);
380 }
381 true
382 }
383
384 fn refresh_edge_ordinals(&mut self, document: &CanvasDocument) {
385 self.edge_ordinals.clear();
386 for (ordinal, edge_id) in document.edge_ids().enumerate() {
387 self.edge_ordinals.insert(edge_id.clone(), ordinal);
388 }
389 }
390
391 fn sort_adjacency_by_edge_ordinals(&mut self) {
392 let ordinals = &self.edge_ordinals;
393 for edge_ids in self
394 .outgoing
395 .values_mut()
396 .chain(self.incoming.values_mut())
397 .chain(self.incident.values_mut())
398 {
399 edge_ids
400 .sort_by_cached_key(|edge_id| ordinals.get(edge_id).copied().unwrap_or(usize::MAX));
401 }
402 }
403}
404
405#[derive(Clone, Copy, Debug)]
406pub struct CanvasIndexedGraph<'a> {
407 document: &'a CanvasDocument,
408 index: &'a CanvasGraphIndex,
409}
410
411impl<'a> CanvasIndexedGraph<'a> {
412 pub fn new(document: &'a CanvasDocument, index: &'a CanvasGraphIndex) -> Self {
413 Self { document, index }
414 }
415
416 pub fn document(&self) -> &'a CanvasDocument {
417 self.document
418 }
419
420 pub fn index(&self) -> &'a CanvasGraphIndex {
421 self.index
422 }
423
424 pub fn node(&self, id: &NodeId) -> Option<&'a CanvasNode> {
425 self.document.node(id)
426 }
427
428 pub fn edge(&self, id: &EdgeId) -> Option<&'a CanvasEdge> {
429 self.document.edge(id)
430 }
431
432 pub fn endpoint_node(&self, endpoint: &CanvasEndpoint) -> Option<&'a CanvasNode> {
433 self.node(&endpoint.node_id)
434 }
435
436 pub fn endpoint_handle(&self, endpoint: &CanvasEndpoint) -> Option<&'a CanvasHandle> {
437 let handle_id = endpoint.handle_id.as_ref()?;
438 self.endpoint_node(endpoint)?.handle(Some(handle_id))
439 }
440
441 pub fn outgoing_edges<'q>(
442 &'q self,
443 node_id: &'q NodeId,
444 ) -> impl Iterator<Item = &'a CanvasEdge> + 'q
445 where
446 'a: 'q,
447 {
448 self.index
449 .outgoing_edge_ids(node_id)
450 .filter_map(|edge_id| self.document.edge(edge_id))
451 }
452
453 pub fn incoming_edges<'q>(
454 &'q self,
455 node_id: &'q NodeId,
456 ) -> impl Iterator<Item = &'a CanvasEdge> + 'q
457 where
458 'a: 'q,
459 {
460 self.index
461 .incoming_edge_ids(node_id)
462 .filter_map(|edge_id| self.document.edge(edge_id))
463 }
464
465 pub fn incident_edges<'q>(
466 &'q self,
467 node_id: &'q NodeId,
468 ) -> impl Iterator<Item = &'a CanvasEdge> + 'q
469 where
470 'a: 'q,
471 {
472 self.index
473 .incident_edge_ids(node_id)
474 .filter_map(|edge_id| self.document.edge(edge_id))
475 }
476
477 pub fn edges_for_node<'q>(
478 &'q self,
479 node_id: &'q NodeId,
480 direction: CanvasEdgeDirection,
481 ) -> Box<dyn Iterator<Item = &'a CanvasEdge> + 'q>
482 where
483 'a: 'q,
484 {
485 match direction {
486 CanvasEdgeDirection::Incoming => Box::new(self.incoming_edges(node_id)),
487 CanvasEdgeDirection::Outgoing => Box::new(self.outgoing_edges(node_id)),
488 CanvasEdgeDirection::Any => Box::new(self.incident_edges(node_id)),
489 }
490 }
491
492 pub fn edges_between<'q>(
493 &'q self,
494 source: &'q NodeId,
495 target: &'q NodeId,
496 ) -> impl Iterator<Item = &'a CanvasEdge> + 'q
497 where
498 'a: 'q,
499 {
500 self.index
501 .edge_ids_between(source, target)
502 .filter_map(|edge_id| self.document.edge(edge_id))
503 }
504
505 pub fn has_edge_between(&self, source: &NodeId, target: &NodeId) -> bool {
506 self.index.has_edge_between(source, target)
507 }
508
509 pub fn neighbor_node_ids<'q>(
510 &'q self,
511 node_id: &'q NodeId,
512 direction: CanvasEdgeDirection,
513 ) -> Box<dyn Iterator<Item = &'a NodeId> + 'q>
514 where
515 'a: 'q,
516 {
517 match direction {
518 CanvasEdgeDirection::Incoming => Box::new(
519 self.index
520 .incoming_edge_ids(node_id)
521 .filter_map(move |edge_id| {
522 let endpoints = self.index.edge_endpoints(edge_id)?;
523 self.document
524 .contains_node(&endpoints.source)
525 .then_some(&endpoints.source)
526 }),
527 ),
528 CanvasEdgeDirection::Outgoing => Box::new(
529 self.index
530 .outgoing_edge_ids(node_id)
531 .filter_map(move |edge_id| {
532 let endpoints = self.index.edge_endpoints(edge_id)?;
533 self.document
534 .contains_node(&endpoints.target)
535 .then_some(&endpoints.target)
536 }),
537 ),
538 CanvasEdgeDirection::Any => Box::new(self.index.incident_edge_ids(node_id).filter_map(
539 move |edge_id| {
540 let endpoints = self.index.edge_endpoints(edge_id)?;
541 let neighbor_id = if endpoints.source == *node_id {
542 &endpoints.target
543 } else {
544 &endpoints.source
545 };
546 self.document
547 .contains_node(neighbor_id)
548 .then_some(neighbor_id)
549 },
550 )),
551 }
552 }
553
554 pub fn incident_edge_count(&self, node_id: &NodeId) -> usize {
555 self.index.incident_edge_count(node_id)
556 }
557}
558
559fn remove_edge_from_node(
560 edges_by_node: &mut IndexMap<NodeId, IndexSet<EdgeId>>,
561 node_id: &NodeId,
562 edge_id: &EdgeId,
563) {
564 let Some(edge_ids) = edges_by_node.get_mut(node_id) else {
565 return;
566 };
567 edge_ids.shift_remove(edge_id);
568 if edge_ids.is_empty() {
569 edges_by_node.shift_remove(node_id);
570 }
571}
572
573fn edge_matches_node(edge: &CanvasEdge, node_id: &NodeId, direction: CanvasEdgeDirection) -> bool {
574 match direction {
575 CanvasEdgeDirection::Incoming => edge.target.node_id == *node_id,
576 CanvasEdgeDirection::Outgoing => edge.source.node_id == *node_id,
577 CanvasEdgeDirection::Any => {
578 edge.source.node_id == *node_id || edge.target.node_id == *node_id
579 }
580 }
581}
582
583fn neighbor_node_id<'a>(
584 edge: &'a CanvasEdge,
585 node_id: &NodeId,
586 direction: CanvasEdgeDirection,
587) -> Option<&'a NodeId> {
588 match direction {
589 CanvasEdgeDirection::Incoming if edge.target.node_id == *node_id => {
590 Some(&edge.source.node_id)
591 }
592 CanvasEdgeDirection::Outgoing if edge.source.node_id == *node_id => {
593 Some(&edge.target.node_id)
594 }
595 CanvasEdgeDirection::Any if edge.source.node_id == *node_id => Some(&edge.target.node_id),
596 CanvasEdgeDirection::Any if edge.target.node_id == *node_id => Some(&edge.source.node_id),
597 _ => None,
598 }
599}
600
601#[cfg(test)]
602mod tests {
603 use super::*;
604 use crate::{
605 CanvasHandle, CanvasTransaction, DocumentCommand, HandleRole,
606 test_support::document_fixture,
607 };
608 use open_gpui::{point, px, size};
609
610 #[test]
611 fn graph_queries_directed_edges() {
612 let document = sample_document();
613 let graph = document.graph();
614 let a = NodeId::from("a");
615 let b = NodeId::from("b");
616
617 assert_eq!(
618 edge_ids(graph.outgoing_edges(&a)),
619 vec!["a-b".to_string(), "a-a".to_string()]
620 );
621 assert_eq!(
622 edge_ids(graph.incoming_edges(&a)),
623 vec!["c-a".to_string(), "a-a".to_string()]
624 );
625 assert_eq!(
626 edge_ids(graph.incident_edges(&a)),
627 vec!["a-b".to_string(), "c-a".to_string(), "a-a".to_string()]
628 );
629 assert_eq!(
630 edge_ids(graph.edges_between(&a, &b)),
631 vec!["a-b".to_string()]
632 );
633 assert!(graph.has_edge_between(&a, &b));
634 assert!(!graph.has_edge_between(&b, &a));
635 assert_eq!(graph.incident_edge_count(&a), 3);
636 }
637
638 #[test]
639 fn graph_queries_neighbors_by_direction() {
640 let document = sample_document();
641 let graph = document.graph();
642 let a = NodeId::from("a");
643
644 assert_eq!(
645 node_ids(graph.neighbor_node_ids(&a, CanvasEdgeDirection::Outgoing)),
646 vec!["b".to_string(), "a".to_string()]
647 );
648 assert_eq!(
649 node_ids(graph.neighbor_node_ids(&a, CanvasEdgeDirection::Incoming)),
650 vec!["c".to_string(), "a".to_string()]
651 );
652 assert_eq!(
653 node_ids(graph.neighbor_node_ids(&a, CanvasEdgeDirection::Any)),
654 vec!["b".to_string(), "c".to_string(), "a".to_string()]
655 );
656 }
657
658 #[test]
659 fn graph_queries_endpoint_parts() {
660 let document = sample_document();
661 let graph = document.graph();
662 let endpoint = CanvasEndpoint::new("a", Some("out"));
663
664 assert_eq!(
665 graph.endpoint_node(&endpoint).unwrap().id,
666 NodeId::from("a")
667 );
668 assert_eq!(
669 graph.endpoint_handle(&endpoint).unwrap().id,
670 crate::HandleId::from("out")
671 );
672 assert!(
673 graph
674 .endpoint_handle(&CanvasEndpoint::new("a", None::<&str>))
675 .is_none()
676 );
677 assert!(
678 graph
679 .endpoint_node(&CanvasEndpoint::new("missing", None::<&str>))
680 .is_none()
681 );
682 }
683
684 #[test]
685 fn graph_index_queries_match_scan_graph() {
686 let document = sample_document();
687 let graph = document.graph();
688 let index = document.graph_index();
689 let indexed = index.graph(&document);
690 let a = NodeId::from("a");
691 let b = NodeId::from("b");
692
693 assert_eq!(index.edge_count(), 3);
694 assert!(!index.is_empty());
695 assert_eq!(
696 index.edge_endpoints(&EdgeId::from("a-b")).cloned(),
697 Some(CanvasGraphEndpointIds::new("a", "b"))
698 );
699 assert!(index.contains_edge(&EdgeId::from("a-b")));
700
701 assert_eq!(
702 edge_id_strings(index.outgoing_edge_ids(&a)),
703 edge_ids(graph.outgoing_edges(&a))
704 );
705 assert_eq!(
706 edge_id_strings(index.incoming_edge_ids(&a)),
707 edge_ids(graph.incoming_edges(&a))
708 );
709 assert_eq!(
710 edge_id_strings(index.incident_edge_ids(&a)),
711 edge_ids(graph.incident_edges(&a))
712 );
713 assert_eq!(
714 edge_id_strings(index.edge_ids_for_node(&a, CanvasEdgeDirection::Any)),
715 edge_ids(graph.edges_for_node(&a, CanvasEdgeDirection::Any))
716 );
717 assert_eq!(
718 edge_id_strings(index.edge_ids_between(&a, &b)),
719 edge_ids(graph.edges_between(&a, &b))
720 );
721 assert_eq!(
722 node_ids(index.neighbor_node_ids(&a, CanvasEdgeDirection::Any)),
723 node_ids(graph.neighbor_node_ids(&a, CanvasEdgeDirection::Any))
724 );
725 assert_eq!(index.incident_edge_count(&a), graph.incident_edge_count(&a));
726
727 assert_eq!(
728 edge_ids(indexed.outgoing_edges(&a)),
729 edge_ids(graph.outgoing_edges(&a))
730 );
731 assert_eq!(
732 edge_ids(indexed.incoming_edges(&a)),
733 edge_ids(graph.incoming_edges(&a))
734 );
735 assert_eq!(
736 edge_ids(indexed.incident_edges(&a)),
737 edge_ids(graph.incident_edges(&a))
738 );
739 assert_eq!(
740 edge_ids(indexed.edges_for_node(&a, CanvasEdgeDirection::Any)),
741 edge_ids(graph.edges_for_node(&a, CanvasEdgeDirection::Any))
742 );
743 assert_eq!(
744 edge_ids(indexed.edges_between(&a, &b)),
745 edge_ids(graph.edges_between(&a, &b))
746 );
747 assert_eq!(
748 node_ids(indexed.neighbor_node_ids(&a, CanvasEdgeDirection::Any)),
749 node_ids(graph.neighbor_node_ids(&a, CanvasEdgeDirection::Any))
750 );
751 assert!(indexed.has_edge_between(&a, &b));
752 assert_eq!(
753 indexed.incident_edge_count(&a),
754 graph.incident_edge_count(&a)
755 );
756 }
757
758 #[test]
759 fn graph_index_applies_document_diffs_incrementally() {
760 let mut document = sample_document();
761 let mut index = document.graph_index();
762
763 let diff = document
764 .apply_transaction_with_diff(CanvasTransaction::single(DocumentCommand::InsertEdge(
765 CanvasEdge::new(
766 "b-c",
767 CanvasEndpoint::new("b", None::<&str>),
768 CanvasEndpoint::new("c", None::<&str>),
769 ),
770 )))
771 .unwrap();
772 index.apply_diff(&document, &diff);
773 assert_eq!(
774 edge_id_strings(index.outgoing_edge_ids(&NodeId::from("b"))),
775 vec!["b-c".to_string()]
776 );
777 assert_eq!(index, document.graph_index());
778
779 let diff = document
780 .apply_transaction_with_diff(CanvasTransaction::single(DocumentCommand::UpdateEdge(
781 CanvasEdge::new(
782 "a-b",
783 CanvasEndpoint::new("b", None::<&str>),
784 CanvasEndpoint::new("c", None::<&str>),
785 ),
786 )))
787 .unwrap();
788 index.apply_diff(&document, &diff);
789 assert!(!index.has_edge_between(&NodeId::from("a"), &NodeId::from("b")));
790 assert_eq!(
791 edge_id_strings(index.edge_ids_between(&NodeId::from("b"), &NodeId::from("c"))),
792 vec!["a-b".to_string(), "b-c".to_string()]
793 );
794 assert_eq!(index, document.graph_index());
795
796 let diff = document
797 .apply_transaction_with_diff(CanvasTransaction::single(DocumentCommand::RemoveNode(
798 NodeId::from("b"),
799 )))
800 .unwrap();
801 index.apply_diff(&document, &diff);
802 assert!(!index.contains_edge(&EdgeId::from("a-b")));
803 assert!(!index.contains_edge(&EdgeId::from("b-c")));
804 assert_eq!(index, document.graph_index());
805 }
806
807 #[test]
808 fn graph_index_preserves_adjacency_when_edge_metadata_changes() {
809 let mut document = sample_document();
810 let mut index = document.graph_index();
811 let mut edge = document.edge(&EdgeId::from("a-b")).unwrap().clone();
812 edge.z_index = 42;
813
814 let diff = document
815 .apply_transaction_with_diff(CanvasTransaction::single(DocumentCommand::UpdateEdge(
816 edge,
817 )))
818 .unwrap();
819 index.apply_diff(&document, &diff);
820
821 assert_eq!(
822 edge_id_strings(index.outgoing_edge_ids(&NodeId::from("a"))),
823 vec!["a-b".to_string(), "a-a".to_string()]
824 );
825 assert_eq!(index, document.graph_index());
826 }
827
828 fn sample_document() -> CanvasDocument {
829 let mut a = CanvasNode::new("a", point(px(0.0), px(0.0)), size(px(100.0), px(60.0)));
830 let mut out = CanvasHandle::new("out", point(px(100.0), px(30.0)));
831 out.role = HandleRole::Source;
832 a.handles.push(out);
833 let mut input = CanvasHandle::new("in", point(px(0.0), px(30.0)));
834 input.role = HandleRole::Target;
835 a.handles.push(input);
836
837 let b = CanvasNode::new("b", point(px(160.0), px(0.0)), size(px(100.0), px(60.0)));
838 let c = CanvasNode::new("c", point(px(-160.0), px(0.0)), size(px(100.0), px(60.0)));
839
840 document_fixture()
841 .node(a)
842 .node(b)
843 .node(c)
844 .edge(CanvasEdge::new(
845 "a-b",
846 CanvasEndpoint::new("a", Some("out")),
847 CanvasEndpoint::new("b", None::<&str>),
848 ))
849 .edge(CanvasEdge::new(
850 "c-a",
851 CanvasEndpoint::new("c", None::<&str>),
852 CanvasEndpoint::new("a", Some("in")),
853 ))
854 .edge(CanvasEdge::new(
855 "a-a",
856 CanvasEndpoint::new("a", Some("out")),
857 CanvasEndpoint::new("a", Some("in")),
858 ))
859 .build()
860 }
861
862 fn edge_ids<'a>(edges: impl IntoIterator<Item = &'a CanvasEdge>) -> Vec<String> {
863 edges
864 .into_iter()
865 .map(|edge| edge.id.as_str().to_string())
866 .collect()
867 }
868
869 fn node_ids<'a>(ids: impl IntoIterator<Item = &'a NodeId>) -> Vec<String> {
870 ids.into_iter().map(|id| id.as_str().to_string()).collect()
871 }
872
873 fn edge_id_strings<'a>(ids: impl IntoIterator<Item = &'a EdgeId>) -> Vec<String> {
874 ids.into_iter().map(|id| id.as_str().to_string()).collect()
875 }
876}