src/librustc_data_structures/graph/test.rs

   1 // Copyright 2016 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use std::collections::HashMap;
  12 use std::cmp::max;
  13 use std::slice;
  14 use std::iter;
  15
  16 use super::{ControlFlowGraph, GraphPredecessors, GraphSuccessors};
  17
  18 pub struct TestGraph {
  19     num_nodes: usize,
  20     start_node: usize,
  21     successors: HashMap<usize, Vec<usize>>,
  22     predecessors: HashMap<usize, Vec<usize>>,
  23 }
  24
  25 impl TestGraph {
  26     pub fn new(start_node: usize, edges: &[(usize, usize)]) -> Self {
  27         let mut graph = TestGraph {
  28             num_nodes: start_node + 1,
  29             start_node,
  30             successors: HashMap::new(),
  31             predecessors: HashMap::new(),
  32         };
  33         for &(source, target) in edges {
  34             graph.num_nodes = max(graph.num_nodes, source + 1);
  35             graph.num_nodes = max(graph.num_nodes, target + 1);
  36             graph.successors.entry(source).or_insert(vec![]).push(target);
  37             graph.predecessors.entry(target).or_insert(vec![]).push(source);
  38         }
  39         for node in 0..graph.num_nodes {
  40             graph.successors.entry(node).or_insert(vec![]);
  41             graph.predecessors.entry(node).or_insert(vec![]);
  42         }
  43         graph
  44     }
  45 }
  46
  47 impl ControlFlowGraph for TestGraph {
  48     type Node = usize;
  49
  50     fn start_node(&self) -> usize {
  51         self.start_node
  52     }
  53
  54     fn num_nodes(&self) -> usize {
  55         self.num_nodes
  56     }
  57
  58     fn predecessors<'graph>(&'graph self,
  59                             node: usize)
  60                             -> <Self as GraphPredecessors<'graph>>::Iter {
  61         self.predecessors[&node].iter().cloned()
  62     }
  63
  64     fn successors<'graph>(&'graph self, node: usize) -> <Self as GraphSuccessors<'graph>>::Iter {
  65         self.successors[&node].iter().cloned()
  66     }
  67 }
  68
  69 impl<'graph> GraphPredecessors<'graph> for TestGraph {
  70     type Item = usize;
  71     type Iter = iter::Cloned<slice::Iter<'graph, usize>>;
  72 }
  73
  74 impl<'graph> GraphSuccessors<'graph> for TestGraph {
  75     type Item = usize;
  76     type Iter = iter::Cloned<slice::Iter<'graph, usize>>;
  77 }