compiler/rustc_data_structures/src/graph/mod.rs

   1 use rustc_index::vec::Idx;
   2
   3 pub mod dominators;
   4 pub mod implementation;
   5 pub mod iterate;
   6 mod reference;
   7 pub mod scc;
   8 pub mod vec_graph;
   9
  10 #[cfg(test)]
  11 mod tests;
  12
  13 pub trait DirectedGraph {
  14     type Node: Idx;
  15 }
  16
  17 pub trait WithNumNodes: DirectedGraph {
  18     fn num_nodes(&self) -> usize;
  19 }
  20
  21 pub trait WithNumEdges: DirectedGraph {
  22     fn num_edges(&self) -> usize;
  23 }
  24
  25 pub trait WithSuccessors: DirectedGraph
  26 where
  27     Self: for<'graph> GraphSuccessors<'graph, Item = <Self as DirectedGraph>::Node>,
  28 {
  29     fn successors(&self, node: Self::Node) -> <Self as GraphSuccessors<'_>>::Iter;
  30
  31     fn depth_first_search(&self, from: Self::Node) -> iterate::DepthFirstSearch<'_, Self>
  32     where
  33         Self: WithNumNodes,
  34     {
  35         iterate::DepthFirstSearch::new(self).with_start_node(from)
  36     }
  37 }
  38
  39 #[allow(unused_lifetimes)]
  40 pub trait GraphSuccessors<'graph> {
  41     type Item;
  42     type Iter: Iterator<Item = Self::Item>;
  43 }
  44
  45 pub trait WithPredecessors: DirectedGraph
  46 where
  47     Self: for<'graph> GraphPredecessors<'graph, Item = <Self as DirectedGraph>::Node>,
  48 {
  49     fn predecessors(&self, node: Self::Node) -> <Self as GraphPredecessors<'_>>::Iter;
  50 }
  51
  52 #[allow(unused_lifetimes)]
  53 pub trait GraphPredecessors<'graph> {
  54     type Item;
  55     type Iter: Iterator<Item = Self::Item>;
  56 }
  57
  58 pub trait WithStartNode: DirectedGraph {
  59     fn start_node(&self) -> Self::Node;
  60 }
  61
  62 pub trait ControlFlowGraph:
  63     DirectedGraph + WithStartNode + WithPredecessors + WithSuccessors + WithNumNodes
  64 {
  65     // convenient trait
  66 }
  67
  68 impl<T> ControlFlowGraph for T where
  69     T: DirectedGraph + WithStartNode + WithPredecessors + WithSuccessors + WithNumNodes
  70 {
  71 }
  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 }