compiler/rustc_data_structures/src/transitive_relation/tests.rs

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