src/librustc_data_structures/graph/mod.rs

   1 use super::indexed_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 test;
  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(
  30         &self,
  31         node: Self::Node,
  32     ) -> <Self as GraphSuccessors<'_>>::Iter;
  33
  34     fn depth_first_search(&self, from: Self::Node) -> iterate::DepthFirstSearch<'_, Self>
  35     where
  36         Self: WithNumNodes,
  37     {
  38         iterate::DepthFirstSearch::new(self, from)
  39     }
  40 }
  41
  42 pub trait GraphSuccessors<'graph> {
  43     type Item;
  44     type Iter: Iterator<Item = Self::Item>;
  45 }
  46
  47 pub trait WithPredecessors: DirectedGraph
  48 where
  49     Self: for<'graph> GraphPredecessors<'graph, Item = <Self as DirectedGraph>::Node>,
  50 {
  51     fn predecessors(
  52         &self,
  53         node: Self::Node,
  54     ) -> <Self as GraphPredecessors<'_>>::Iter;
  55 }
  56
  57 pub trait GraphPredecessors<'graph> {
  58     type Item;
  59     type Iter: Iterator<Item = Self::Item>;
  60 }
  61
  62 pub trait WithStartNode: DirectedGraph {
  63     fn start_node(&self) -> Self::Node;
  64 }
  65
  66 pub trait ControlFlowGraph:
  67     DirectedGraph + WithStartNode + WithPredecessors + WithStartNode + WithSuccessors + WithNumNodes
  68 {
  69     // convenient trait
  70 }
  71
  72 impl<T> ControlFlowGraph for T
  73 where
  74     T: DirectedGraph
  75         + WithStartNode
  76         + WithPredecessors
  77         + WithStartNode
  78         + WithSuccessors
  79         + WithNumNodes,
  80 {
  81 }