compiler/rustc_data_structures/src/graph/tests.rs

   1 use crate::fx::FxHashMap;
   2 use std::cmp::max;
   3 use std::iter;
   4 use std::slice;
   5
   6 use super::*;
   7
   8 pub struct TestGraph {
   9     num_nodes: usize,
  10     start_node: usize,
  11     successors: FxHashMap<usize, Vec<usize>>,
  12     predecessors: FxHashMap<usize, Vec<usize>>,
  13 }
  14
  15 impl TestGraph {
  16     pub fn new(start_node: usize, edges: &[(usize, usize)]) -> Self {
  17         let mut graph = TestGraph {
  18             num_nodes: start_node + 1,
  19             start_node,
  20             successors: FxHashMap::default(),
  21             predecessors: FxHashMap::default(),
  22         };
  23         for &(source, target) in edges {
  24             graph.num_nodes = max(graph.num_nodes, source + 1);
  25             graph.num_nodes = max(graph.num_nodes, target + 1);
  26             graph.successors.entry(source).or_default().push(target);
  27             graph.predecessors.entry(target).or_default().push(source);
  28         }
  29         for node in 0..graph.num_nodes {
  30             graph.successors.entry(node).or_default();
  31             graph.predecessors.entry(node).or_default();
  32         }
  33         graph
  34     }
  35 }
  36
  37 impl DirectedGraph for TestGraph {
  38     type Node = usize;
  39 }
  40
  41 impl WithStartNode for TestGraph {
  42     fn start_node(&self) -> usize {
  43         self.start_node
  44     }
  45 }
  46
  47 impl WithNumNodes for TestGraph {
  48     fn num_nodes(&self) -> usize {
  49         self.num_nodes
  50     }
  51 }
  52
  53 impl WithPredecessors for TestGraph {
  54     fn predecessors(&self, node: usize) -> <Self as GraphPredecessors<'_>>::Iter {
  55         self.predecessors[&node].iter().cloned()
  56     }
  57 }
  58
  59 impl WithSuccessors for TestGraph {
  60     fn successors(&self, node: usize) -> <Self as GraphSuccessors<'_>>::Iter {
  61         self.successors[&node].iter().cloned()
  62     }
  63 }
  64
  65 impl<'graph> GraphPredecessors<'graph> for TestGraph {
  66     type Item = usize;
  67     type Iter = iter::Cloned<slice::Iter<'graph, usize>>;
  68 }
  69
  70 impl<'graph> GraphSuccessors<'graph> for TestGraph {
  71     type Item = usize;
  72     type Iter = iter::Cloned<slice::Iter<'graph, usize>>;
  73 }