cgraph/state/
graph.rs

1//! Directed, globally deduplicated hierarchy state.
2//!
3//! This module deliberately contains no terminal geometry or LSP protocol
4//! types. `RelationGraph` owns semantic nodes, canonical edges, branch query
5//! state, anchors, and the cycle-safe projection of currently visible data.
6
7use std::collections::{HashMap, HashSet, VecDeque};
8
9use petgraph::stable_graph::{NodeIndex, StableDiGraph};
10use petgraph::visit::{EdgeRef, IntoEdgeReferences};
11
12use super::{HierarchyDirection, HierarchyKind, LoadState, NodeId, SourceLocation, SymbolIdentity};
13
14#[derive(Clone, Debug, Eq, Hash, PartialEq)]
15struct ResolvedSymbolKey {
16    kind: HierarchyKind,
17    location: SourceLocation,
18}
19
20impl ResolvedSymbolKey {
21    fn from_identity(identity: &SymbolIdentity) -> Option<Self> {
22        Some(Self {
23            kind: identity.kind,
24            location: identity.location.clone()?,
25        })
26    }
27}
28
29#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
30pub struct BranchKey {
31    pub node_id: NodeId,
32    pub direction: HierarchyDirection,
33}
34
35#[derive(Clone, Debug, Eq, PartialEq)]
36pub struct GraphBranch {
37    pub expanded: bool,
38    pub load_state: LoadState,
39    pub neighbors: Vec<NodeId>,
40    pub failure: Option<String>,
41    pub(crate) active_request_id: Option<u64>,
42}
43
44impl GraphBranch {
45    pub fn can_toggle(&self) -> bool {
46        !self.neighbors.is_empty()
47    }
48
49    pub fn toggle(&mut self) -> bool {
50        if !self.can_toggle() {
51            return false;
52        }
53        self.expanded = !self.expanded;
54        true
55    }
56
57    pub fn failure(&self) -> Option<&str> {
58        self.failure.as_deref()
59    }
60}
61
62impl Default for GraphBranch {
63    fn default() -> Self {
64        Self {
65            expanded: false,
66            load_state: LoadState::NotLoaded,
67            neighbors: Vec::new(),
68            failure: None,
69            active_request_id: None,
70        }
71    }
72}
73
74#[derive(Clone, Debug, Eq, PartialEq)]
75pub struct GraphNode {
76    pub id: NodeId,
77    pub symbol: String,
78    pub kind: HierarchyKind,
79    pub location: Option<SourceLocation>,
80    pub incoming: GraphBranch,
81    pub outgoing: GraphBranch,
82}
83
84impl GraphNode {
85    fn new(identity: SymbolIdentity) -> Self {
86        Self {
87            id: NodeId::next(),
88            symbol: identity.symbol,
89            kind: identity.kind,
90            location: identity.location,
91            incoming: GraphBranch::default(),
92            outgoing: GraphBranch::default(),
93        }
94    }
95
96    pub fn identity(&self) -> SymbolIdentity {
97        SymbolIdentity {
98            symbol: self.symbol.clone(),
99            kind: self.kind,
100            location: self.location.clone(),
101        }
102    }
103
104    pub fn branch(&self, direction: HierarchyDirection) -> &GraphBranch {
105        match direction {
106            HierarchyDirection::Incoming => &self.incoming,
107            HierarchyDirection::Outgoing => &self.outgoing,
108        }
109    }
110
111    pub fn branch_mut(&mut self, direction: HierarchyDirection) -> &mut GraphBranch {
112        match direction {
113            HierarchyDirection::Incoming => &mut self.incoming,
114            HierarchyDirection::Outgoing => &mut self.outgoing,
115        }
116    }
117}
118
119#[derive(Clone, Debug, Eq, PartialEq)]
120pub struct RelationEdge {
121    pub observed_by: Vec<BranchKey>,
122}
123
124#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
125pub struct VisibleEdge {
126    pub source: NodeId,
127    pub target: NodeId,
128}
129
130#[derive(Clone, Debug, Default, Eq, PartialEq)]
131pub struct VisibleGraph {
132    pub nodes: Vec<NodeId>,
133    pub edges: Vec<VisibleEdge>,
134}
135
136#[derive(Debug, Default)]
137pub struct RelationGraph {
138    graph: StableDiGraph<GraphNode, RelationEdge>,
139    by_id: HashMap<NodeId, NodeIndex>,
140    by_identity: HashMap<ResolvedSymbolKey, NodeId>,
141    redirects: HashMap<NodeId, NodeId>,
142    anchors: Vec<NodeId>,
143}
144
145impl RelationGraph {
146    pub fn insert_symbol(&mut self, identity: SymbolIdentity) -> NodeId {
147        if let Some(key) = ResolvedSymbolKey::from_identity(&identity)
148            && let Some(existing) = self.by_identity.get(&key)
149        {
150            return *existing;
151        }
152
153        let node = GraphNode::new(identity);
154        let node_id = node.id;
155        let key = ResolvedSymbolKey::from_identity(&node.identity());
156        let index = self.graph.add_node(node);
157        self.by_id.insert(node_id, index);
158        if let Some(key) = key {
159            self.by_identity.insert(key, node_id);
160        }
161        node_id
162    }
163
164    pub fn pin_symbol(&mut self, identity: SymbolIdentity) -> NodeId {
165        let node_id = self.insert_symbol(identity);
166        self.pin(node_id);
167        node_id
168    }
169
170    pub fn pin(&mut self, node_id: NodeId) -> bool {
171        let Some(node_id) = self.resolve_id(node_id) else {
172            return false;
173        };
174        if !self.anchors.contains(&node_id) {
175            self.anchors.push(node_id);
176        }
177        true
178    }
179
180    pub fn unpin(&mut self, node_id: NodeId) -> bool {
181        let Some(node_id) = self.resolve_id(node_id) else {
182            return false;
183        };
184        let Some(index) = self.anchors.iter().position(|anchor| *anchor == node_id) else {
185            return false;
186        };
187        self.anchors.remove(index);
188        true
189    }
190
191    pub fn anchors(&self) -> &[NodeId] {
192        &self.anchors
193    }
194
195    pub fn is_anchor(&self, node_id: NodeId) -> bool {
196        self.resolve_id(node_id)
197            .is_some_and(|node_id| self.anchors.contains(&node_id))
198    }
199
200    pub fn contains(&self, node_id: NodeId) -> bool {
201        self.resolve_id(node_id).is_some()
202    }
203
204    pub fn node(&self, node_id: NodeId) -> Option<&GraphNode> {
205        let node_id = self.resolve_id(node_id)?;
206        self.by_id
207            .get(&node_id)
208            .and_then(|index| self.graph.node_weight(*index))
209    }
210
211    pub fn node_mut(&mut self, node_id: NodeId) -> Option<&mut GraphNode> {
212        let node_id = self.resolve_id(node_id)?;
213        let index = *self.by_id.get(&node_id)?;
214        self.graph.node_weight_mut(index)
215    }
216
217    pub fn nodes_named(&self, symbol: &str, kind: HierarchyKind) -> Vec<NodeId> {
218        self.graph
219            .node_weights()
220            .filter(|node| node.symbol == symbol && node.kind == kind)
221            .map(|node| node.id)
222            .collect()
223    }
224
225    pub fn resolve_id(&self, mut node_id: NodeId) -> Option<NodeId> {
226        let mut visited = HashSet::new();
227        while let Some(next) = self.redirects.get(&node_id) {
228            if !visited.insert(node_id) {
229                return None;
230            }
231            node_id = *next;
232        }
233        self.by_id.contains_key(&node_id).then_some(node_id)
234    }
235
236    pub fn resolve_symbol(&mut self, node_id: NodeId, identity: SymbolIdentity) -> Option<NodeId> {
237        let node_id = self.resolve_id(node_id)?;
238        let new_key = ResolvedSymbolKey::from_identity(&identity);
239        if let Some(existing) = new_key
240            .as_ref()
241            .and_then(|key| self.by_identity.get(key))
242            .copied()
243            && existing != node_id
244        {
245            return Some(self.merge_nodes(node_id, existing, identity));
246        }
247
248        if let Some(old_key) = self
249            .node(node_id)
250            .and_then(|node| ResolvedSymbolKey::from_identity(&node.identity()))
251        {
252            self.by_identity.remove(&old_key);
253        }
254        let node = self.node_mut(node_id)?;
255        node.symbol = identity.symbol;
256        node.kind = identity.kind;
257        node.location = identity.location;
258        if let Some(key) = new_key {
259            self.by_identity.insert(key, node_id);
260        }
261        Some(node_id)
262    }
263
264    pub fn replace_branch_neighbors(
265        &mut self,
266        node_id: NodeId,
267        direction: HierarchyDirection,
268        children: Vec<SymbolIdentity>,
269    ) -> Option<Vec<NodeId>> {
270        let node_id = self.resolve_id(node_id)?;
271        let owner = BranchKey { node_id, direction };
272        let old_neighbors = self.node(node_id)?.branch(direction).neighbors.clone();
273        for neighbor in old_neighbors {
274            self.remove_observation(node_id, neighbor, owner);
275        }
276
277        let mut seen = HashSet::new();
278        let mut neighbors = Vec::new();
279        for child in children {
280            let child_id = self.insert_symbol(child);
281            if !seen.insert(child_id) {
282                continue;
283            }
284            self.observe_relation(node_id, child_id, owner);
285            neighbors.push(child_id);
286        }
287        self.node_mut(node_id)?.branch_mut(direction).neighbors = neighbors.clone();
288        Some(neighbors)
289    }
290
291    pub fn clear_branch(&mut self, node_id: NodeId, direction: HierarchyDirection) -> bool {
292        let Some(node_id) = self.resolve_id(node_id) else {
293            return false;
294        };
295        let owner = BranchKey { node_id, direction };
296        let neighbors = self
297            .node(node_id)
298            .map(|node| node.branch(direction).neighbors.clone())
299            .unwrap_or_default();
300        for neighbor in neighbors {
301            self.remove_observation(node_id, neighbor, owner);
302        }
303        let Some(node) = self.node_mut(node_id) else {
304            return false;
305        };
306        *node.branch_mut(direction) = GraphBranch::default();
307        true
308    }
309
310    pub fn visible_graph(&self) -> VisibleGraph {
311        self.project_graph(true)
312    }
313
314    /// Returns every relation currently known from an anchor, including cached
315    /// branches that are collapsed in the canvas. Orphaned storage left behind
316    /// after unpinning or clearing a branch is intentionally excluded.
317    pub fn known_graph(&self) -> VisibleGraph {
318        self.project_graph(false)
319    }
320
321    fn project_graph(&self, expanded_only: bool) -> VisibleGraph {
322        let mut visible = VisibleGraph::default();
323        let mut seen_nodes = HashSet::new();
324        let mut seen_edges = HashSet::new();
325        let mut queue = VecDeque::new();
326
327        for anchor in &self.anchors {
328            if self.contains(*anchor) && seen_nodes.insert(*anchor) {
329                visible.nodes.push(*anchor);
330                queue.push_back(*anchor);
331            }
332        }
333
334        while let Some(node_id) = queue.pop_front() {
335            let Some(node) = self.node(node_id) else {
336                continue;
337            };
338            for direction in [HierarchyDirection::Incoming, HierarchyDirection::Outgoing] {
339                let branch = node.branch(direction);
340                if expanded_only && !branch.expanded {
341                    continue;
342                }
343                for neighbor in &branch.neighbors {
344                    let Some(neighbor) = self.resolve_id(*neighbor) else {
345                        continue;
346                    };
347                    let edge = canonical_edge(node_id, neighbor, direction);
348                    if self.has_edge(edge.source, edge.target) && seen_edges.insert(edge) {
349                        visible.edges.push(edge);
350                    }
351                    if seen_nodes.insert(neighbor) {
352                        visible.nodes.push(neighbor);
353                        queue.push_back(neighbor);
354                    }
355                }
356            }
357        }
358        visible
359    }
360
361    pub fn node_count(&self) -> usize {
362        self.graph.node_count()
363    }
364
365    pub fn edge_count(&self) -> usize {
366        self.graph.edge_count()
367    }
368
369    fn observe_relation(&mut self, node_id: NodeId, neighbor: NodeId, owner: BranchKey) {
370        let edge = canonical_edge(node_id, neighbor, owner.direction);
371        let Some(source) = self.resolve_id(edge.source) else {
372            return;
373        };
374        let Some(target) = self.resolve_id(edge.target) else {
375            return;
376        };
377        let source_index = self.by_id[&source];
378        let target_index = self.by_id[&target];
379        if let Some(edge_index) = self.graph.find_edge(source_index, target_index) {
380            let relation = self
381                .graph
382                .edge_weight_mut(edge_index)
383                .expect("found edges have weights");
384            if !relation.observed_by.contains(&owner) {
385                relation.observed_by.push(owner);
386            }
387        } else {
388            self.graph.add_edge(
389                source_index,
390                target_index,
391                RelationEdge {
392                    observed_by: vec![owner],
393                },
394            );
395        }
396    }
397
398    fn remove_observation(&mut self, node_id: NodeId, neighbor: NodeId, owner: BranchKey) {
399        let edge = canonical_edge(node_id, neighbor, owner.direction);
400        let Some(source) = self.resolve_id(edge.source) else {
401            return;
402        };
403        let Some(target) = self.resolve_id(edge.target) else {
404            return;
405        };
406        let Some(edge_index) = self
407            .graph
408            .find_edge(self.by_id[&source], self.by_id[&target])
409        else {
410            return;
411        };
412        let relation = self
413            .graph
414            .edge_weight_mut(edge_index)
415            .expect("found edges have weights");
416        relation.observed_by.retain(|candidate| *candidate != owner);
417        if relation.observed_by.is_empty() {
418            self.graph.remove_edge(edge_index);
419        }
420    }
421
422    fn has_edge(&self, source: NodeId, target: NodeId) -> bool {
423        let (Some(source), Some(target)) = (self.resolve_id(source), self.resolve_id(target))
424        else {
425            return false;
426        };
427        self.graph
428            .find_edge(self.by_id[&source], self.by_id[&target])
429            .is_some()
430    }
431
432    fn merge_nodes(
433        &mut self,
434        source_id: NodeId,
435        target_id: NodeId,
436        identity: SymbolIdentity,
437    ) -> NodeId {
438        let identity_key = ResolvedSymbolKey::from_identity(&identity);
439        let source_index = self.by_id[&source_id];
440        let target_index = self.by_id[&target_id];
441        let incident = self
442            .graph
443            .edge_references()
444            .filter(|edge| edge.source() == source_index || edge.target() == source_index)
445            .map(|edge| {
446                let source = self.graph[edge.source()].id;
447                let target = self.graph[edge.target()].id;
448                (source, target, edge.weight().clone())
449            })
450            .collect::<Vec<_>>();
451        let mut source_node = self
452            .graph
453            .remove_node(source_index)
454            .expect("source node exists while merging");
455        replace_neighbor(&mut source_node.incoming.neighbors, source_id, target_id);
456        replace_neighbor(&mut source_node.outgoing.neighbors, source_id, target_id);
457        self.by_id.remove(&source_id);
458        self.redirects.insert(source_id, target_id);
459        self.by_identity.retain(|_, value| *value != source_id);
460
461        for node_index in self.graph.node_indices().collect::<Vec<_>>() {
462            let node = &mut self.graph[node_index];
463            replace_neighbor(&mut node.incoming.neighbors, source_id, target_id);
464            replace_neighbor(&mut node.outgoing.neighbors, source_id, target_id);
465        }
466        for relation in self.graph.edge_weights_mut() {
467            for owner in &mut relation.observed_by {
468                if owner.node_id == source_id {
469                    owner.node_id = target_id;
470                }
471            }
472            relation.observed_by.sort_by_key(|owner| {
473                (
474                    owner.node_id.0,
475                    match owner.direction {
476                        HierarchyDirection::Incoming => 0,
477                        HierarchyDirection::Outgoing => 1,
478                    },
479                )
480            });
481            relation.observed_by.dedup();
482        }
483
484        {
485            let target = self
486                .graph
487                .node_weight_mut(target_index)
488                .expect("target node remains while merging");
489            merge_branch(&mut target.incoming, source_node.incoming);
490            merge_branch(&mut target.outgoing, source_node.outgoing);
491            target.symbol = identity.symbol;
492            target.kind = identity.kind;
493            target.location = identity.location.clone();
494        }
495
496        for (source, target, mut relation) in incident {
497            let source = if source == source_id {
498                target_id
499            } else {
500                source
501            };
502            let target = if target == source_id {
503                target_id
504            } else {
505                target
506            };
507            for owner in &mut relation.observed_by {
508                if owner.node_id == source_id {
509                    owner.node_id = target_id;
510                }
511            }
512            let source_index = self.by_id[&source];
513            let target_index = self.by_id[&target];
514            if let Some(edge_index) = self.graph.find_edge(source_index, target_index) {
515                let existing = self
516                    .graph
517                    .edge_weight_mut(edge_index)
518                    .expect("found edges have weights");
519                for owner in relation.observed_by {
520                    if !existing.observed_by.contains(&owner) {
521                        existing.observed_by.push(owner);
522                    }
523                }
524            } else {
525                self.graph.add_edge(source_index, target_index, relation);
526            }
527        }
528
529        for anchor in &mut self.anchors {
530            if *anchor == source_id {
531                *anchor = target_id;
532            }
533        }
534        let mut seen = HashSet::new();
535        self.anchors.retain(|anchor| seen.insert(*anchor));
536        if let Some(key) = identity_key {
537            self.by_identity.insert(key, target_id);
538        }
539        target_id
540    }
541}
542
543fn canonical_edge(node_id: NodeId, neighbor: NodeId, direction: HierarchyDirection) -> VisibleEdge {
544    match direction {
545        HierarchyDirection::Incoming => VisibleEdge {
546            source: neighbor,
547            target: node_id,
548        },
549        HierarchyDirection::Outgoing => VisibleEdge {
550            source: node_id,
551            target: neighbor,
552        },
553    }
554}
555
556fn replace_neighbor(neighbors: &mut Vec<NodeId>, source: NodeId, target: NodeId) {
557    for neighbor in neighbors.iter_mut() {
558        if *neighbor == source {
559            *neighbor = target;
560        }
561    }
562    let mut seen = HashSet::new();
563    neighbors.retain(|neighbor| seen.insert(*neighbor));
564}
565
566fn merge_branch(target: &mut GraphBranch, source: GraphBranch) {
567    target.expanded |= source.expanded;
568    for neighbor in source.neighbors {
569        if !target.neighbors.contains(&neighbor) {
570            target.neighbors.push(neighbor);
571        }
572    }
573    if load_state_priority(source.load_state) > load_state_priority(target.load_state) {
574        target.load_state = source.load_state;
575        target.failure = source.failure;
576    } else if target.failure.is_none() {
577        target.failure = source.failure;
578    }
579    if target.active_request_id.is_none() {
580        target.active_request_id = source.active_request_id;
581    }
582}
583
584fn load_state_priority(state: LoadState) -> u8 {
585    match state {
586        LoadState::NotLoaded => 0,
587        LoadState::Failed => 1,
588        LoadState::Loading => 2,
589        LoadState::Loaded => 3,
590    }
591}
592
593#[cfg(test)]
594mod tests {
595    use super::{RelationGraph, VisibleEdge};
596    use crate::state::{
597        HierarchyDirection, HierarchyKind, LoadState, SourceLocation, SymbolIdentity,
598    };
599
600    fn symbol(name: &str, line: u32) -> SymbolIdentity {
601        SymbolIdentity {
602            symbol: name.to_owned(),
603            kind: HierarchyKind::Call,
604            location: Some(SourceLocation {
605                uri: "file:///workspace/src/lib.rs".to_owned(),
606                line: Some(line),
607                character: Some(0),
608            }),
609        }
610    }
611
612    #[test]
613    fn globally_deduplicates_diamond_nodes_without_losing_edges() {
614        let mut graph = RelationGraph::default();
615        let root = graph.pin_symbol(symbol("root", 0));
616        graph
617            .replace_branch_neighbors(
618                root,
619                HierarchyDirection::Outgoing,
620                vec![symbol("left", 1), symbol("right", 2)],
621            )
622            .unwrap();
623        graph.node_mut(root).unwrap().outgoing.expanded = true;
624        let left = graph.node(root).unwrap().outgoing.neighbors[0];
625        let right = graph.node(root).unwrap().outgoing.neighbors[1];
626        let shared_from_left = graph
627            .replace_branch_neighbors(
628                left,
629                HierarchyDirection::Outgoing,
630                vec![symbol("shared", 3)],
631            )
632            .unwrap()[0];
633        let shared_from_right = graph
634            .replace_branch_neighbors(
635                right,
636                HierarchyDirection::Outgoing,
637                vec![symbol("shared", 3)],
638            )
639            .unwrap()[0];
640        graph.node_mut(left).unwrap().outgoing.expanded = true;
641        graph.node_mut(right).unwrap().outgoing.expanded = true;
642
643        assert_eq!(shared_from_left, shared_from_right);
644        assert_eq!(graph.node_count(), 4);
645        assert_eq!(graph.edge_count(), 4);
646        let visible = graph.visible_graph();
647        assert_eq!(visible.nodes.len(), 4);
648        assert_eq!(visible.edges.len(), 4);
649    }
650
651    #[test]
652    fn merges_the_same_edge_observed_from_both_directions() {
653        let mut graph = RelationGraph::default();
654        let caller = graph.pin_symbol(symbol("caller", 0));
655        let callee = graph.insert_symbol(symbol("callee", 1));
656        graph
657            .replace_branch_neighbors(
658                caller,
659                HierarchyDirection::Outgoing,
660                vec![symbol("callee", 1)],
661            )
662            .unwrap();
663        graph
664            .replace_branch_neighbors(
665                callee,
666                HierarchyDirection::Incoming,
667                vec![symbol("caller", 0)],
668            )
669            .unwrap();
670
671        assert_eq!(graph.edge_count(), 1);
672    }
673
674    #[test]
675    fn traverses_cycles_once_and_preserves_the_closing_edge() {
676        let mut graph = RelationGraph::default();
677        let first = graph.pin_symbol(symbol("first", 0));
678        let second = graph
679            .replace_branch_neighbors(
680                first,
681                HierarchyDirection::Outgoing,
682                vec![symbol("second", 1)],
683            )
684            .unwrap()[0];
685        let third = graph
686            .replace_branch_neighbors(
687                second,
688                HierarchyDirection::Outgoing,
689                vec![symbol("third", 2)],
690            )
691            .unwrap()[0];
692        graph
693            .replace_branch_neighbors(
694                third,
695                HierarchyDirection::Outgoing,
696                vec![symbol("first", 0)],
697            )
698            .unwrap();
699        for node_id in [first, second, third] {
700            graph.node_mut(node_id).unwrap().outgoing.expanded = true;
701        }
702
703        let visible = graph.visible_graph();
704        assert_eq!(visible.nodes.len(), 3);
705        assert_eq!(visible.edges.len(), 3);
706        assert!(visible.edges.contains(&VisibleEdge {
707            source: third,
708            target: first,
709        }));
710    }
711
712    #[test]
713    fn represents_a_self_loop_without_creating_an_extra_node() {
714        let mut graph = RelationGraph::default();
715        let node = graph.pin_symbol(symbol("recursive", 0));
716        graph
717            .replace_branch_neighbors(
718                node,
719                HierarchyDirection::Outgoing,
720                vec![symbol("recursive", 0)],
721            )
722            .unwrap();
723        graph.node_mut(node).unwrap().outgoing.expanded = true;
724
725        assert_eq!(graph.node_count(), 1);
726        assert_eq!(graph.edge_count(), 1);
727        assert_eq!(
728            graph.visible_graph().edges,
729            [VisibleEdge {
730                source: node,
731                target: node,
732            }]
733        );
734    }
735
736    #[test]
737    fn keeps_same_named_symbols_at_different_locations_separate() {
738        let mut graph = RelationGraph::default();
739        let first = graph.insert_symbol(symbol("same", 1));
740        let second = graph.insert_symbol(symbol("same", 2));
741
742        assert_ne!(first, second);
743        assert_eq!(graph.node_count(), 2);
744    }
745
746    #[test]
747    fn resolves_a_provisional_anchor_into_an_existing_semantic_node() {
748        let mut graph = RelationGraph::default();
749        let provisional = graph.pin_symbol(SymbolIdentity {
750            symbol: "target".to_owned(),
751            kind: HierarchyKind::Call,
752            location: None,
753        });
754        let existing = graph.insert_symbol(symbol("Module::target", 4));
755
756        let resolved = graph
757            .resolve_symbol(provisional, symbol("Module::target", 4))
758            .unwrap();
759
760        assert_eq!(resolved, existing);
761        assert_eq!(graph.resolve_id(provisional), Some(existing));
762        assert_eq!(graph.anchors(), [existing]);
763        assert_eq!(graph.node_count(), 1);
764    }
765
766    #[test]
767    fn retargets_existing_edges_when_resolving_a_provisional_anchor() {
768        let mut graph = RelationGraph::default();
769        let provisional = graph.pin_symbol(SymbolIdentity {
770            symbol: "target".to_owned(),
771            kind: HierarchyKind::Call,
772            location: None,
773        });
774        let child = graph
775            .replace_branch_neighbors(
776                provisional,
777                HierarchyDirection::Outgoing,
778                vec![symbol("child", 5)],
779            )
780            .unwrap()[0];
781        graph.node_mut(provisional).unwrap().outgoing.expanded = true;
782        let existing = graph.insert_symbol(symbol("Module::target", 4));
783
784        let resolved = graph
785            .resolve_symbol(provisional, symbol("Module::target", 4))
786            .unwrap();
787        let visible = graph.visible_graph();
788
789        assert_eq!(resolved, existing);
790        assert_eq!(graph.edge_count(), 1);
791        assert_eq!(visible.nodes, [existing, child]);
792        assert_eq!(
793            visible.edges,
794            [VisibleEdge {
795                source: existing,
796                target: child,
797            }]
798        );
799    }
800
801    #[test]
802    fn clearing_one_branch_keeps_an_edge_observed_by_the_other_endpoint() {
803        let mut graph = RelationGraph::default();
804        let caller = graph.pin_symbol(symbol("caller", 0));
805        let callee = graph.insert_symbol(symbol("callee", 1));
806        graph
807            .replace_branch_neighbors(
808                caller,
809                HierarchyDirection::Outgoing,
810                vec![symbol("callee", 1)],
811            )
812            .unwrap();
813        graph
814            .replace_branch_neighbors(
815                callee,
816                HierarchyDirection::Incoming,
817                vec![symbol("caller", 0)],
818            )
819            .unwrap();
820
821        assert!(graph.clear_branch(caller, HierarchyDirection::Outgoing));
822        assert_eq!(graph.edge_count(), 1);
823        assert_eq!(
824            graph.node(caller).unwrap().outgoing.load_state,
825            LoadState::NotLoaded
826        );
827        assert!(graph.clear_branch(callee, HierarchyDirection::Incoming));
828        assert_eq!(graph.edge_count(), 0);
829    }
830
831    #[test]
832    fn known_graph_includes_collapsed_cache_and_excludes_cleared_orphans() {
833        let mut graph = RelationGraph::default();
834        let root = graph.pin_symbol(symbol("root", 0));
835        let child = graph
836            .replace_branch_neighbors(root, HierarchyDirection::Outgoing, vec![symbol("child", 1)])
837            .unwrap()[0];
838
839        assert_eq!(graph.visible_graph().nodes, [root]);
840        assert_eq!(graph.known_graph().nodes, [root, child]);
841        assert_eq!(
842            graph.known_graph().edges,
843            [VisibleEdge {
844                source: root,
845                target: child,
846            }]
847        );
848
849        assert!(graph.clear_branch(root, HierarchyDirection::Outgoing));
850        assert_eq!(graph.known_graph().nodes, [root]);
851        assert!(graph.known_graph().edges.is_empty());
852    }
853}
cgraph/state/graph.rs

cgraph/state/
graph.rs
