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 #[allow(unused_lifetimes)]
  43 pub trait GraphSuccessors<'graph> {
  44     type Item;
  45     type Iter: Iterator<Item = Self::Item>;
  46 }
  47
  48 pub trait WithPredecessors: DirectedGraph
  49 where
  50     Self: for<'graph> GraphPredecessors<'graph, Item = <Self as DirectedGraph>::Node>,
  51 {
  52     fn predecessors(
  53         &self,
  54         node: Self::Node,
  55     ) -> <Self as GraphPredecessors<'_>>::Iter;
  56 }
  57
  58 #[allow(unused_lifetimes)]
  59 pub trait GraphPredecessors<'graph> {
  60     type Item;
  61     type Iter: Iterator<Item = Self::Item>;
  62 }
  63
  64 pub trait WithStartNode: DirectedGraph {
  65     fn start_node(&self) -> Self::Node;
  66 }
  67
  68 pub trait ControlFlowGraph:
  69     DirectedGraph + WithStartNode + WithPredecessors + WithStartNode + WithSuccessors + WithNumNodes
  70 {
  71     // convenient trait
  72 }
  73
  74 impl<T> ControlFlowGraph for T
  75 where
  76     T: DirectedGraph
  77         + WithStartNode
  78         + WithPredecessors
  79         + WithStartNode
  80         + WithSuccessors
  81         + WithNumNodes,
  82 {
  83 }