compiler/rustc_data_structures/src/transitive_relation/tests.rs

   1 use super::*;
   2
   3 #[test]
   4 fn test_one_step() {
   5     let mut relation = TransitiveRelation::default();
   6     relation.add("a", "b");
   7     relation.add("a", "c");
   8     assert!(relation.contains(&"a", &"c"));
   9     assert!(relation.contains(&"a", &"b"));
  10     assert!(!relation.contains(&"b", &"a"));
  11     assert!(!relation.contains(&"a", &"d"));
  12 }
  13
  14 #[test]
  15 fn test_many_steps() {
  16     let mut relation = TransitiveRelation::default();
  17     relation.add("a", "b");
  18     relation.add("a", "c");
  19     relation.add("a", "f");
  20
  21     relation.add("b", "c");
  22     relation.add("b", "d");
  23     relation.add("b", "e");
  24
  25     relation.add("e", "g");
  26
  27     assert!(relation.contains(&"a", &"b"));
  28     assert!(relation.contains(&"a", &"c"));
  29     assert!(relation.contains(&"a", &"d"));
  30     assert!(relation.contains(&"a", &"e"));
  31     assert!(relation.contains(&"a", &"f"));
  32     assert!(relation.contains(&"a", &"g"));
  33
  34     assert!(relation.contains(&"b", &"g"));
  35
  36     assert!(!relation.contains(&"a", &"x"));
  37     assert!(!relation.contains(&"b", &"f"));
  38 }
  39
  40 #[test]
  41 fn mubs_triangle() {
  42     // a -> tcx
  43     //      ^
  44     //      |
  45     //      b
  46     let mut relation = TransitiveRelation::default();
  47     relation.add("a", "tcx");
  48     relation.add("b", "tcx");
  49     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"tcx"]);
  50     assert_eq!(relation.parents(&"a"), vec![&"tcx"]);
  51     assert_eq!(relation.parents(&"b"), vec![&"tcx"]);
  52 }
  53
  54 #[test]
  55 fn mubs_best_choice1() {
  56     // 0 -> 1 <- 3
  57     // |    ^    |
  58     // |    |    |
  59     // +--> 2 <--+
  60     //
  61     // mubs(0,3) = [1]
  62
  63     // This tests a particular state in the algorithm, in which we
  64     // need the second pare down call to get the right result (after
  65     // intersection, we have [1, 2], but 2 -> 1).
  66
  67     let mut relation = TransitiveRelation::default();
  68     relation.add("0", "1");
  69     relation.add("0", "2");
  70
  71     relation.add("2", "1");
  72
  73     relation.add("3", "1");
  74     relation.add("3", "2");
  75
  76     assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"2"]);
  77     assert_eq!(relation.parents(&"0"), vec![&"2"]);
  78     assert_eq!(relation.parents(&"2"), vec![&"1"]);
  79     assert!(relation.parents(&"1").is_empty());
  80 }
  81
  82 #[test]
  83 fn mubs_best_choice2() {
  84     // 0 -> 1 <- 3
  85     // |    |    |
  86     // |    v    |
  87     // +--> 2 <--+
  88     //
  89     // mubs(0,3) = [2]
  90
  91     // Like the precedecing test, but in this case intersection is [2,
  92     // 1], and hence we rely on the first pare down call.
  93
  94     let mut relation = TransitiveRelation::default();
  95     relation.add("0", "1");
  96     relation.add("0", "2");
  97
  98     relation.add("1", "2");
  99
 100     relation.add("3", "1");
 101     relation.add("3", "2");
 102
 103     assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1"]);
 104     assert_eq!(relation.parents(&"0"), vec![&"1"]);
 105     assert_eq!(relation.parents(&"1"), vec![&"2"]);
 106     assert!(relation.parents(&"2").is_empty());
 107 }
 108
 109 #[test]
 110 fn mubs_no_best_choice() {
 111     // in this case, the intersection yields [1, 2], and the "pare
 112     // down" calls find nothing to remove.
 113     let mut relation = TransitiveRelation::default();
 114     relation.add("0", "1");
 115     relation.add("0", "2");
 116
 117     relation.add("3", "1");
 118     relation.add("3", "2");
 119
 120     assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1", &"2"]);
 121     assert_eq!(relation.parents(&"0"), vec![&"1", &"2"]);
 122     assert_eq!(relation.parents(&"3"), vec![&"1", &"2"]);
 123 }
 124
 125 #[test]
 126 fn mubs_best_choice_scc() {
 127     // in this case, 1 and 2 form a cycle; we pick arbitrarily (but
 128     // consistently).
 129
 130     let mut relation = TransitiveRelation::default();
 131     relation.add("0", "1");
 132     relation.add("0", "2");
 133
 134     relation.add("1", "2");
 135     relation.add("2", "1");
 136
 137     relation.add("3", "1");
 138     relation.add("3", "2");
 139
 140     assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1"]);
 141     assert_eq!(relation.parents(&"0"), vec![&"1"]);
 142 }
 143
 144 #[test]
 145 fn pdub_crisscross() {
 146     // diagonal edges run left-to-right
 147     // a -> a1 -> x
 148     //   \/       ^
 149     //   /\       |
 150     // b -> b1 ---+
 151
 152     let mut relation = TransitiveRelation::default();
 153     relation.add("a", "a1");
 154     relation.add("a", "b1");
 155     relation.add("b", "a1");
 156     relation.add("b", "b1");
 157     relation.add("a1", "x");
 158     relation.add("b1", "x");
 159
 160     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"a1", &"b1"]);
 161     assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x"));
 162     assert_eq!(relation.postdom_parent(&"a"), Some(&"x"));
 163     assert_eq!(relation.postdom_parent(&"b"), Some(&"x"));
 164 }
 165
 166 #[test]
 167 fn pdub_crisscross_more() {
 168     // diagonal edges run left-to-right
 169     // a -> a1 -> a2 -> a3 -> x
 170     //   \/    \/             ^
 171     //   /\    /\             |
 172     // b -> b1 -> b2 ---------+
 173
 174     let mut relation = TransitiveRelation::default();
 175     relation.add("a", "a1");
 176     relation.add("a", "b1");
 177     relation.add("b", "a1");
 178     relation.add("b", "b1");
 179
 180     relation.add("a1", "a2");
 181     relation.add("a1", "b2");
 182     relation.add("b1", "a2");
 183     relation.add("b1", "b2");
 184
 185     relation.add("a2", "a3");
 186
 187     relation.add("a3", "x");
 188     relation.add("b2", "x");
 189
 190     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"a1", &"b1"]);
 191     assert_eq!(relation.minimal_upper_bounds(&"a1", &"b1"), vec![&"a2", &"b2"]);
 192     assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x"));
 193
 194     assert_eq!(relation.postdom_parent(&"a"), Some(&"x"));
 195     assert_eq!(relation.postdom_parent(&"b"), Some(&"x"));
 196 }
 197
 198 #[test]
 199 fn pdub_lub() {
 200     // a -> a1 -> x
 201     //            ^
 202     //            |
 203     // b -> b1 ---+
 204
 205     let mut relation = TransitiveRelation::default();
 206     relation.add("a", "a1");
 207     relation.add("b", "b1");
 208     relation.add("a1", "x");
 209     relation.add("b1", "x");
 210
 211     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"x"]);
 212     assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x"));
 213
 214     assert_eq!(relation.postdom_parent(&"a"), Some(&"a1"));
 215     assert_eq!(relation.postdom_parent(&"b"), Some(&"b1"));
 216     assert_eq!(relation.postdom_parent(&"a1"), Some(&"x"));
 217     assert_eq!(relation.postdom_parent(&"b1"), Some(&"x"));
 218 }
 219
 220 #[test]
 221 fn mubs_intermediate_node_on_one_side_only() {
 222     // a -> c -> d
 223     //           ^
 224     //           |
 225     //           b
 226
 227     // "digraph { a -> c -> d; b -> d; }",
 228     let mut relation = TransitiveRelation::default();
 229     relation.add("a", "c");
 230     relation.add("c", "d");
 231     relation.add("b", "d");
 232
 233     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"d"]);
 234 }
 235
 236 #[test]
 237 fn mubs_scc_1() {
 238     // +-------------+
 239     // |    +----+   |
 240     // |    v    |   |
 241     // a -> c -> d <-+
 242     //           ^
 243     //           |
 244     //           b
 245
 246     // "digraph { a -> c -> d; d -> c; a -> d; b -> d; }",
 247     let mut relation = TransitiveRelation::default();
 248     relation.add("a", "c");
 249     relation.add("c", "d");
 250     relation.add("d", "c");
 251     relation.add("a", "d");
 252     relation.add("b", "d");
 253
 254     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
 255 }
 256
 257 #[test]
 258 fn mubs_scc_2() {
 259     //      +----+
 260     //      v    |
 261     // a -> c -> d
 262     //      ^    ^
 263     //      |    |
 264     //      +--- b
 265
 266     // "digraph { a -> c -> d; d -> c; b -> d; b -> c; }",
 267     let mut relation = TransitiveRelation::default();
 268     relation.add("a", "c");
 269     relation.add("c", "d");
 270     relation.add("d", "c");
 271     relation.add("b", "d");
 272     relation.add("b", "c");
 273
 274     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
 275 }
 276
 277 #[test]
 278 fn mubs_scc_3() {
 279     //      +---------+
 280     //      v         |
 281     // a -> c -> d -> e
 282     //           ^    ^
 283     //           |    |
 284     //           b ---+
 285
 286     // "digraph { a -> c -> d -> e -> c; b -> d; b -> e; }",
 287     let mut relation = TransitiveRelation::default();
 288     relation.add("a", "c");
 289     relation.add("c", "d");
 290     relation.add("d", "e");
 291     relation.add("e", "c");
 292     relation.add("b", "d");
 293     relation.add("b", "e");
 294
 295     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
 296 }
 297
 298 #[test]
 299 fn mubs_scc_4() {
 300     //      +---------+
 301     //      v         |
 302     // a -> c -> d -> e
 303     // |         ^    ^
 304     // +---------+    |
 305     //                |
 306     //           b ---+
 307
 308     // "digraph { a -> c -> d -> e -> c; a -> d; b -> e; }"
 309     let mut relation = TransitiveRelation::default();
 310     relation.add("a", "c");
 311     relation.add("c", "d");
 312     relation.add("d", "e");
 313     relation.add("e", "c");
 314     relation.add("a", "d");
 315     relation.add("b", "e");
 316
 317     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
 318 }
 319
 320 #[test]
 321 fn parent() {
 322     // An example that was misbehaving in the compiler.
 323     //
 324     // 4 -> 1 -> 3
 325     //   \  |   /
 326     //    \ v  /
 327     // 2 -> 0
 328     //
 329     // plus a bunch of self-loops
 330     //
 331     // Here `->` represents `<=` and `0` is `'static`.
 332
 333     let pairs = vec![
 334         (2, /*->*/ 0),
 335         (2, /*->*/ 2),
 336         (0, /*->*/ 0),
 337         (0, /*->*/ 0),
 338         (1, /*->*/ 0),
 339         (1, /*->*/ 1),
 340         (3, /*->*/ 0),
 341         (3, /*->*/ 3),
 342         (4, /*->*/ 0),
 343         (4, /*->*/ 1),
 344         (1, /*->*/ 3),
 345     ];
 346
 347     let mut relation = TransitiveRelation::default();
 348     for (a, b) in pairs {
 349         relation.add(a, b);
 350     }
 351
 352     let p = relation.postdom_parent(&3);
 353     assert_eq!(p, Some(&0));
 354 }