liquid_fixpoint/
graph.rs

1use std::hash::Hash;
2
3use rustc_data_structures::fx::{FxIndexMap, FxIndexSet};
4
5fn dfs_finish_order<'a, T: Hash + Eq + Clone>(
6    node: &'a T,
7    graph: &'a FxIndexMap<T, Vec<T>>,
8    visited: &mut FxIndexSet<T>,
9    order: &mut Vec<T>,
10) {
11    if visited.contains(node) {
12        return;
13    }
14
15    visited.insert(node.clone());
16
17    if let Some(neighbors) = graph.get(node) {
18        for neighbor in neighbors {
19            dfs_finish_order::<T>(neighbor, graph, visited, order);
20        }
21    }
22
23    order.push(node.clone());
24}
25
26fn reverse_graph<T: Hash + Eq + Clone>(graph: &FxIndexMap<T, Vec<T>>) -> FxIndexMap<T, Vec<T>> {
27    let mut reversed = FxIndexMap::default();
28
29    for (node, neighbors) in graph {
30        for neighbor in neighbors {
31            reversed
32                .entry(neighbor.clone())
33                .or_insert_with(Vec::new)
34                .push(node.clone());
35        }
36    }
37
38    for node in graph.keys() {
39        reversed.entry(node.clone()).or_insert_with(Vec::new);
40    }
41
42    reversed
43}
44
45fn dfs_collect_scc<'a, T: Hash + Eq + Clone>(
46    node: &'a T,
47    graph: &'a FxIndexMap<T, Vec<T>>,
48    visited: &mut FxIndexSet<T>,
49    scc: &mut Vec<T>,
50) {
51    if visited.contains(node) {
52        return;
53    }
54
55    visited.insert(node.clone());
56    scc.push(node.clone());
57
58    if let Some(neighbors) = graph.get(node) {
59        for neighbor in neighbors {
60            dfs_collect_scc::<T>(neighbor, graph, visited, scc);
61        }
62    }
63}
64
65fn find_sccs<T: Hash + Eq + Clone>(graph: &FxIndexMap<T, Vec<T>>) -> Vec<Vec<T>> {
66    let mut visited = FxIndexSet::default();
67    let mut order = Vec::new();
68
69    // First pass: original graph
70    for node in graph.keys() {
71        if !visited.contains(node) {
72            dfs_finish_order::<T>(node, graph, &mut visited, &mut order);
73        }
74    }
75
76    let reversed = reverse_graph::<T>(graph);
77    visited.clear();
78    let mut sccs = Vec::new();
79
80    // Second pass: reversed graph in reverse finishing order
81    while let Some(node) = order.pop() {
82        if !visited.contains(&node) {
83            let mut scc = Vec::new();
84            dfs_collect_scc::<T>(&node, &reversed, &mut visited, &mut scc);
85            sccs.push(scc);
86        }
87    }
88
89    sccs
90}
91
92pub fn topological_sort_sccs<T: Hash + Eq + Clone>(graph: &FxIndexMap<T, Vec<T>>) -> Vec<Vec<T>> {
93    let sccs = find_sccs::<T>(graph);
94
95    // Map each node to its SCC index
96    let mut node_to_scc = FxIndexMap::default();
97    for (i, scc) in sccs.iter().enumerate() {
98        for node in scc {
99            node_to_scc.insert(node.clone(), i);
100        }
101    }
102
103    // Build condensed graph (DAG of SCCs)
104    let mut condensed_graph: FxIndexMap<usize, FxIndexSet<usize>> = FxIndexMap::default();
105    for (node, neighbors) in graph {
106        let &from = node_to_scc.get(node).unwrap();
107        for neighbor in neighbors {
108            let &to = node_to_scc.get(neighbor).unwrap();
109            if from != to {
110                condensed_graph.entry(from).or_default().insert(to);
111            }
112        }
113    }
114
115    // Perform topological sort on SCC graph using DFS
116    fn dfs_topo(
117        node: usize,
118        graph: &FxIndexMap<usize, FxIndexSet<usize>>,
119        visited: &mut FxIndexSet<usize>,
120        result: &mut Vec<usize>,
121    ) {
122        if visited.contains(&node) {
123            return;
124        }
125
126        visited.insert(node);
127
128        if let Some(neighbors) = graph.get(&node) {
129            for &neighbor in neighbors {
130                dfs_topo(neighbor, graph, visited, result);
131            }
132        }
133
134        result.push(node);
135    }
136
137    let mut visited = FxIndexSet::default();
138    let mut result = Vec::new();
139
140    for i in 0..sccs.len() {
141        if !visited.contains(&i) {
142            dfs_topo(i, &condensed_graph, &mut visited, &mut result);
143        }
144    }
145
146    result.reverse(); // topological order
147    result.into_iter().map(|i| sccs[i].clone()).collect()
148}
liquid_fixpoint/graph.rs

liquid_fixpoint/
graph.rs
