compiler/rustc_data_structures/src/graph/scc/tests.rs

   1 extern crate test;
   2
   3 use super::*;
   4 use crate::graph::tests::TestGraph;
   5
   6 #[test]
   7 fn diamond() {
   8     let graph = TestGraph::new(0, &[(0, 1), (0, 2), (1, 3), (2, 3)]);
   9     let sccs: Sccs<_, usize> = Sccs::new(&graph);
  10     assert_eq!(sccs.num_sccs(), 4);
  11     assert_eq!(sccs.num_sccs(), 4);
  12 }
  13
  14 #[test]
  15 fn test_big_scc() {
  16     // The order in which things will be visited is important to this
  17     // test.
  18     //
  19     // We will visit:
  20     //
  21     // 0 -> 1 -> 2 -> 0
  22     //
  23     // and at this point detect a cycle. 2 will return back to 1 which
  24     // will visit 3. 3 will visit 2 before the cycle is complete, and
  25     // hence it too will return a cycle.
  26
  27     /*
  28     +-> 0
  29     |   |
  30     |   v
  31     |   1 -> 3
  32     |   |    |
  33     |   v    |
  34     +-- 2 <--+
  35          */
  36     let graph = TestGraph::new(0, &[(0, 1), (1, 2), (1, 3), (2, 0), (3, 2)]);
  37     let sccs: Sccs<_, usize> = Sccs::new(&graph);
  38     assert_eq!(sccs.num_sccs(), 1);
  39 }
  40
  41 #[test]
  42 fn test_three_sccs() {
  43     /*
  44         0
  45         |
  46         v
  47     +-> 1    3
  48     |   |    |
  49     |   v    |
  50     +-- 2 <--+
  51          */
  52     let graph = TestGraph::new(0, &[(0, 1), (1, 2), (2, 1), (3, 2)]);
  53     let sccs: Sccs<_, usize> = Sccs::new(&graph);
  54     assert_eq!(sccs.num_sccs(), 3);
  55     assert_eq!(sccs.scc(0), 1);
  56     assert_eq!(sccs.scc(1), 0);
  57     assert_eq!(sccs.scc(2), 0);
  58     assert_eq!(sccs.scc(3), 2);
  59     assert_eq!(sccs.successors(0), &[]);
  60     assert_eq!(sccs.successors(1), &[0]);
  61     assert_eq!(sccs.successors(2), &[0]);
  62 }
  63
  64 #[test]
  65 fn test_find_state_2() {
  66     // The order in which things will be visited is important to this
  67     // test. It tests part of the `find_state` behavior. Here is the
  68     // graph:
  69     //
  70     //
  71     //       /----+
  72     //     0 <--+ |
  73     //     |    | |
  74     //     v    | |
  75     // +-> 1 -> 3 4
  76     // |   |      |
  77     // |   v      |
  78     // +-- 2 <----+
  79
  80     let graph = TestGraph::new(0, &[(0, 1), (0, 4), (1, 2), (1, 3), (2, 1), (3, 0), (4, 2)]);
  81
  82     // For this graph, we will start in our DFS by visiting:
  83     //
  84     // 0 -> 1 -> 2 -> 1
  85     //
  86     // and at this point detect a cycle. The state of 2 will thus be
  87     // `InCycleWith { 1 }`.  We will then visit the 1 -> 3 edge, which
  88     // will attempt to visit 0 as well, thus going to the state
  89     // `InCycleWith { 0 }`. Finally, node 1 will complete; the lowest
  90     // depth of any successor was 3 which had depth 0, and thus it
  91     // will be in the state `InCycleWith { 3 }`.
  92     //
  93     // When we finally traverse the `0 -> 4` edge and then visit node 2,
  94     // the states of the nodes are:
  95     //
  96     // 0 BeingVisited { 0 }
  97     // 1 InCycleWith { 3 }
  98     // 2 InCycleWith { 1 }
  99     // 3 InCycleWith { 0 }
 100     //
 101     // and hence 4 will traverse the links, finding an ultimate depth of 0.
 102     // If will also collapse the states to the following:
 103     //
 104     // 0 BeingVisited { 0 }
 105     // 1 InCycleWith { 3 }
 106     // 2 InCycleWith { 1 }
 107     // 3 InCycleWith { 0 }
 108
 109     let sccs: Sccs<_, usize> = Sccs::new(&graph);
 110     assert_eq!(sccs.num_sccs(), 1);
 111     assert_eq!(sccs.scc(0), 0);
 112     assert_eq!(sccs.scc(1), 0);
 113     assert_eq!(sccs.scc(2), 0);
 114     assert_eq!(sccs.scc(3), 0);
 115     assert_eq!(sccs.scc(4), 0);
 116     assert_eq!(sccs.successors(0), &[]);
 117 }
 118
 119 #[test]
 120 fn test_find_state_3() {
 121     /*
 122           /----+
 123         0 <--+ |
 124         |    | |
 125         v    | |
 126     +-> 1 -> 3 4 5
 127     |   |      | |
 128     |   v      | |
 129     +-- 2 <----+-+
 130          */
 131     let graph =
 132         TestGraph::new(0, &[(0, 1), (0, 4), (1, 2), (1, 3), (2, 1), (3, 0), (4, 2), (5, 2)]);
 133     let sccs: Sccs<_, usize> = Sccs::new(&graph);
 134     assert_eq!(sccs.num_sccs(), 2);
 135     assert_eq!(sccs.scc(0), 0);
 136     assert_eq!(sccs.scc(1), 0);
 137     assert_eq!(sccs.scc(2), 0);
 138     assert_eq!(sccs.scc(3), 0);
 139     assert_eq!(sccs.scc(4), 0);
 140     assert_eq!(sccs.scc(5), 1);
 141     assert_eq!(sccs.successors(0), &[]);
 142     assert_eq!(sccs.successors(1), &[0]);
 143 }
 144
 145 #[test]
 146 fn test_deep_linear() {
 147     /*
 148     0
 149     |
 150     v
 151     1
 152     |
 153     v
 154     2
 155     |
 156     v
 157     …
 158      */
 159     #[cfg(not(miri))]
 160     const NR_NODES: usize = 1 << 14;
 161     #[cfg(miri)]
 162     const NR_NODES: usize = 1 << 3;
 163     let mut nodes = vec![];
 164     for i in 1..NR_NODES {
 165         nodes.push((i - 1, i));
 166     }
 167     let graph = TestGraph::new(0, nodes.as_slice());
 168     let sccs: Sccs<_, usize> = Sccs::new(&graph);
 169     assert_eq!(sccs.num_sccs(), NR_NODES);
 170     assert_eq!(sccs.scc(0), NR_NODES - 1);
 171     assert_eq!(sccs.scc(NR_NODES - 1), 0);
 172 }
 173
 174 #[bench]
 175 fn bench_sccc(b: &mut test::Bencher) {
 176     // Like `test_three_sccs` but each state is replaced by a group of
 177     // three or four to have some amount of test data.
 178     /*
 179        0-3
 180         |
 181         v
 182     +->4-6 11-14
 183     |   |    |
 184     |   v    |
 185     +--7-10<-+
 186          */
 187     fn make_3_clique(slice: &mut [(usize, usize)], base: usize) {
 188         slice[0] = (base + 0, base + 1);
 189         slice[1] = (base + 1, base + 2);
 190         slice[2] = (base + 2, base + 0);
 191     }
 192     // Not actually a clique but strongly connected.
 193     fn make_4_clique(slice: &mut [(usize, usize)], base: usize) {
 194         slice[0] = (base + 0, base + 1);
 195         slice[1] = (base + 1, base + 2);
 196         slice[2] = (base + 2, base + 3);
 197         slice[3] = (base + 3, base + 0);
 198         slice[4] = (base + 1, base + 3);
 199         slice[5] = (base + 2, base + 1);
 200     }
 201
 202     let mut graph = [(0, 0); 6 + 3 + 6 + 3 + 4];
 203     make_4_clique(&mut graph[0..6], 0);
 204     make_3_clique(&mut graph[6..9], 4);
 205     make_4_clique(&mut graph[9..15], 7);
 206     make_3_clique(&mut graph[15..18], 11);
 207     graph[18] = (0, 4);
 208     graph[19] = (5, 7);
 209     graph[20] = (11, 10);
 210     graph[21] = (7, 4);
 211     let graph = TestGraph::new(0, &graph[..]);
 212     b.iter(|| {
 213         let sccs: Sccs<_, usize> = Sccs::new(&graph);
 214         assert_eq!(sccs.num_sccs(), 3);
 215     });
 216 }