]>
Commit | Line | Data |
---|---|---|
49aad941 | 1 | use rustc_index::Idx; |
1a4d82fc | 2 | |
8faf50e0 XL |
3 | pub mod dominators; |
4 | pub mod implementation; | |
5 | pub mod iterate; | |
6 | mod reference; | |
7 | pub mod scc; | |
dc9dc135 | 8 | pub mod vec_graph; |
d9579d0f AL |
9 | |
10 | #[cfg(test)] | |
416331ca | 11 | mod tests; |
1a4d82fc | 12 | |
8faf50e0 XL |
13 | pub trait DirectedGraph { |
14 | type Node: Idx; | |
1a4d82fc JJ |
15 | } |
16 | ||
8faf50e0 XL |
17 | pub trait WithNumNodes: DirectedGraph { |
18 | fn num_nodes(&self) -> usize; | |
1a4d82fc JJ |
19 | } |
20 | ||
dc9dc135 XL |
21 | pub trait WithNumEdges: DirectedGraph { |
22 | fn num_edges(&self) -> usize; | |
23 | } | |
24 | ||
8faf50e0 | 25 | pub trait WithSuccessors: DirectedGraph |
0531ce1d | 26 | where |
8faf50e0 | 27 | Self: for<'graph> GraphSuccessors<'graph, Item = <Self as DirectedGraph>::Node>, |
d9579d0f | 28 | { |
dfeec247 | 29 | fn successors(&self, node: Self::Node) -> <Self as GraphSuccessors<'_>>::Iter; |
dc9dc135 XL |
30 | |
31 | fn depth_first_search(&self, from: Self::Node) -> iterate::DepthFirstSearch<'_, Self> | |
32 | where | |
33 | Self: WithNumNodes, | |
34 | { | |
c295e0f8 | 35 | iterate::DepthFirstSearch::new(self).with_start_node(from) |
dc9dc135 | 36 | } |
d9579d0f AL |
37 | } |
38 | ||
416331ca | 39 | #[allow(unused_lifetimes)] |
8faf50e0 XL |
40 | pub trait GraphSuccessors<'graph> { |
41 | type Item; | |
42 | type Iter: Iterator<Item = Self::Item>; | |
d9579d0f AL |
43 | } |
44 | ||
8faf50e0 | 45 | pub trait WithPredecessors: DirectedGraph |
0531ce1d | 46 | where |
8faf50e0 | 47 | Self: for<'graph> GraphPredecessors<'graph, Item = <Self as DirectedGraph>::Node>, |
476ff2be | 48 | { |
dfeec247 | 49 | fn predecessors(&self, node: Self::Node) -> <Self as GraphPredecessors<'_>>::Iter; |
1a4d82fc JJ |
50 | } |
51 | ||
416331ca | 52 | #[allow(unused_lifetimes)] |
8faf50e0 XL |
53 | pub trait GraphPredecessors<'graph> { |
54 | type Item; | |
55 | type Iter: Iterator<Item = Self::Item>; | |
5bcae85e SL |
56 | } |
57 | ||
8faf50e0 XL |
58 | pub trait WithStartNode: DirectedGraph { |
59 | fn start_node(&self) -> Self::Node; | |
1a4d82fc JJ |
60 | } |
61 | ||
8faf50e0 | 62 | pub trait ControlFlowGraph: |
94222f64 | 63 | DirectedGraph + WithStartNode + WithPredecessors + WithSuccessors + WithNumNodes |
8faf50e0 XL |
64 | { |
65 | // convenient trait | |
66 | } | |
9cc50fc6 | 67 | |
dfeec247 | 68 | impl<T> ControlFlowGraph for T where |
94222f64 | 69 | T: DirectedGraph + WithStartNode + WithPredecessors + WithSuccessors + WithNumNodes |
8faf50e0 | 70 | { |
1a4d82fc | 71 | } |
e74abb32 XL |
72 | |
73 | /// Returns `true` if the graph has a cycle that is reachable from the start node. | |
74 | pub fn is_cyclic<G>(graph: &G) -> bool | |
75 | where | |
76 | G: ?Sized + DirectedGraph + WithStartNode + WithSuccessors + WithNumNodes, | |
77 | { | |
78 | iterate::TriColorDepthFirstSearch::new(graph) | |
79 | .run_from_start(&mut iterate::CycleDetector) | |
80 | .is_some() | |
81 | } |