omena_query/style/cross_file_hypergraph/
reachability.rs

1use std::collections::{BTreeMap, BTreeSet, VecDeque};
2
3use super::{HypergraphIFDSSummaryEdgeV0, UnifiedHypergraphHyperedgeV0};
4
5#[derive(Debug, Clone, PartialEq, Eq)]
6pub(in crate::style) struct HypergraphClosurePath<N> {
7    pub origin: N,
8    pub target: N,
9    pub depth: usize,
10    pub path_labels: Vec<String>,
11}
12
13#[derive(Debug, Clone, Copy, PartialEq, Eq)]
14pub(in crate::style) enum HypergraphClosureMode {
15    CanonicalFirstTarget,
16    RawAllPaths,
17}
18
19pub trait OmenaUnifiedHypergraphConnectivityOracle {
20    fn reachable_node_ids(
21        &self,
22        start_node_id: &str,
23        hyperedges: &[UnifiedHypergraphHyperedgeV0],
24    ) -> Vec<String>;
25}
26
27#[derive(Debug, Clone, Copy, Default)]
28pub struct BatchHypergraphConnectivityOracle;
29
30impl OmenaUnifiedHypergraphConnectivityOracle for BatchHypergraphConnectivityOracle {
31    fn reachable_node_ids(
32        &self,
33        start_node_id: &str,
34        hyperedges: &[UnifiedHypergraphHyperedgeV0],
35    ) -> Vec<String> {
36        let adjacency = build_adjacency(hyperedges);
37        let mut seen = BTreeSet::new();
38        let mut pending = VecDeque::from([start_node_id.to_string()]);
39        while let Some(current) = pending.pop_front() {
40            for target in adjacency.get(current.as_str()).into_iter().flatten() {
41                if seen.insert(target.clone()) {
42                    pending.push_back(target.clone());
43                }
44            }
45        }
46        seen.into_iter().collect()
47    }
48}
49
50pub fn tabulate_hypergraph_ifds_summary_edges(
51    hyperedges: &[UnifiedHypergraphHyperedgeV0],
52    projected_edges: Vec<HypergraphIFDSSummaryEdgeV0>,
53) -> Vec<HypergraphIFDSSummaryEdgeV0> {
54    let hyperedge_ids = hyperedges
55        .iter()
56        .map(|edge| edge.hyperedge_id.as_str())
57        .collect::<BTreeSet<_>>();
58    let mut edges = projected_edges
59        .into_iter()
60        .filter(|edge| hyperedge_ids.contains(edge.hyperedge_id.as_str()))
61        .collect::<Vec<_>>();
62    edges.sort_by(|left, right| {
63        left.projection_edge_id
64            .cmp(&right.projection_edge_id)
65            .then(left.hyperedge_id.cmp(&right.hyperedge_id))
66    });
67    edges
68}
69
70pub(in crate::style) fn collect_hypergraph_transitive_closure_paths<N, F>(
71    graph: &BTreeMap<N, BTreeSet<N>>,
72    mut label: F,
73) -> (Vec<HypergraphClosurePath<N>>, Vec<Vec<String>>)
74where
75    N: Clone + Ord,
76    F: FnMut(&N) -> String,
77{
78    collect_hypergraph_transitive_closure_paths_with_mode(
79        graph,
80        &mut label,
81        HypergraphClosureMode::CanonicalFirstTarget,
82    )
83}
84
85pub(in crate::style) fn collect_hypergraph_transitive_closure_paths_with_mode<N, F>(
86    graph: &BTreeMap<N, BTreeSet<N>>,
87    label: &mut F,
88    mode: HypergraphClosureMode,
89) -> (Vec<HypergraphClosurePath<N>>, Vec<Vec<String>>)
90where
91    N: Clone + Ord,
92    F: FnMut(&N) -> String,
93{
94    let mut closure_paths = Vec::new();
95    let mut cycle_paths = Vec::new();
96    let mut seen_cycles = BTreeSet::new();
97    let first_target = mode == HypergraphClosureMode::CanonicalFirstTarget;
98
99    for start in graph.keys() {
100        let mut visited = BTreeSet::new();
101        let mut pending = VecDeque::from([(start.clone(), vec![start.clone()])]);
102        while let Some((current, path)) = pending.pop_front() {
103            for target in graph.get(&current).into_iter().flatten() {
104                if let Some(cycle_start) = path.iter().position(|node| node == target) {
105                    let mut cycle = path[cycle_start..].to_vec();
106                    cycle.push(target.clone());
107                    let mut labels = cycle.iter().map(&mut *label).collect::<Vec<_>>();
108                    if first_target {
109                        labels = canonical_hypergraph_cycle_labels(labels);
110                    }
111                    if !labels.is_empty() && seen_cycles.insert(labels.clone()) {
112                        cycle_paths.push(labels);
113                    }
114                    continue;
115                }
116                if first_target && !visited.insert(target.clone()) {
117                    continue;
118                }
119                let mut edge_path = path.clone();
120                edge_path.push(target.clone());
121                closure_paths.push(HypergraphClosurePath {
122                    origin: start.clone(),
123                    target: target.clone(),
124                    depth: edge_path.len().saturating_sub(1),
125                    path_labels: edge_path.iter().map(&mut *label).collect(),
126                });
127                pending.push_back((target.clone(), edge_path));
128            }
129        }
130    }
131    (closure_paths, cycle_paths)
132}
133
134fn canonical_hypergraph_cycle_labels(mut labels: Vec<String>) -> Vec<String> {
135    if labels.len() > 1 && labels.first() == labels.last() {
136        labels.pop();
137    }
138    if labels.is_empty() {
139        return labels;
140    }
141    let mut best = labels.clone();
142    for offset in 1..labels.len() {
143        let mut rotated = labels[offset..].to_vec();
144        rotated.extend_from_slice(&labels[..offset]);
145        best = best.min(rotated);
146    }
147    best.push(best[0].clone());
148    best
149}
150
151fn build_adjacency(
152    hyperedges: &[UnifiedHypergraphHyperedgeV0],
153) -> BTreeMap<&str, BTreeSet<String>> {
154    let mut adjacency = BTreeMap::<&str, BTreeSet<String>>::new();
155    for edge in hyperedges {
156        for tail in &edge.tail_node_ids {
157            adjacency
158                .entry(tail.as_str())
159                .or_default()
160                .insert(edge.head_node_id.clone());
161        }
162    }
163    adjacency
164}
omena_query/style/cross_file_hypergraph/reachability.rs

omena_query/style/cross_file_hypergraph/
reachability.rs
