src/librustc_data_structures/transitive_relation/tests.rs

use super::*;

#[test]
fn test_one_step() {
    let mut relation = TransitiveRelation::default();
    relation.add("a", "b");
    relation.add("a", "c");
    assert!(relation.contains(&"a", &"c"));
    assert!(relation.contains(&"a", &"b"));
    assert!(!relation.contains(&"b", &"a"));
    assert!(!relation.contains(&"a", &"d"));
}

#[test]
fn test_many_steps() {
    let mut relation = TransitiveRelation::default();
    relation.add("a", "b");
    relation.add("a", "c");
    relation.add("a", "f");

    relation.add("b", "c");
    relation.add("b", "d");
    relation.add("b", "e");

    relation.add("e", "g");

    assert!(relation.contains(&"a", &"b"));
    assert!(relation.contains(&"a", &"c"));
    assert!(relation.contains(&"a", &"d"));
    assert!(relation.contains(&"a", &"e"));
    assert!(relation.contains(&"a", &"f"));
    assert!(relation.contains(&"a", &"g"));

    assert!(relation.contains(&"b", &"g"));

    assert!(!relation.contains(&"a", &"x"));
    assert!(!relation.contains(&"b", &"f"));
}

#[test]
fn mubs_triangle() {
    // a -> tcx
    //      ^
    //      |
    //      b
    let mut relation = TransitiveRelation::default();
    relation.add("a", "tcx");
    relation.add("b", "tcx");
    assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"tcx"]);
    assert_eq!(relation.parents(&"a"), vec![&"tcx"]);
    assert_eq!(relation.parents(&"b"), vec![&"tcx"]);
}

#[test]
fn mubs_best_choice1() {
    // 0 -> 1 <- 3
    // |    ^    |
    // |    |    |
    // +--> 2 <--+
    //
    // mubs(0,3) = [1]

    // This tests a particular state in the algorithm, in which we
    // need the second pare down call to get the right result (after
    // intersection, we have [1, 2], but 2 -> 1).

    let mut relation = TransitiveRelation::default();
    relation.add("0", "1");
    relation.add("0", "2");

    relation.add("2", "1");

    relation.add("3", "1");
    relation.add("3", "2");

    assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"2"]);
    assert_eq!(relation.parents(&"0"), vec![&"2"]);
    assert_eq!(relation.parents(&"2"), vec![&"1"]);
    assert!(relation.parents(&"1").is_empty());
}

#[test]
fn mubs_best_choice2() {
    // 0 -> 1 <- 3
    // |    |    |
    // |    v    |
    // +--> 2 <--+
    //
    // mubs(0,3) = [2]

    // Like the precedecing test, but in this case intersection is [2,
    // 1], and hence we rely on the first pare down call.

    let mut relation = TransitiveRelation::default();
    relation.add("0", "1");
    relation.add("0", "2");

    relation.add("1", "2");

    relation.add("3", "1");
    relation.add("3", "2");

    assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1"]);
    assert_eq!(relation.parents(&"0"), vec![&"1"]);
    assert_eq!(relation.parents(&"1"), vec![&"2"]);
    assert!(relation.parents(&"2").is_empty());
}

#[test]
fn mubs_no_best_choice() {
    // in this case, the intersection yields [1, 2], and the "pare
    // down" calls find nothing to remove.
    let mut relation = TransitiveRelation::default();
    relation.add("0", "1");
    relation.add("0", "2");

    relation.add("3", "1");
    relation.add("3", "2");

    assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1", &"2"]);
    assert_eq!(relation.parents(&"0"), vec![&"1", &"2"]);
    assert_eq!(relation.parents(&"3"), vec![&"1", &"2"]);
}

#[test]
fn mubs_best_choice_scc() {
    // in this case, 1 and 2 form a cycle; we pick arbitrarily (but
    // consistently).

    let mut relation = TransitiveRelation::default();
    relation.add("0", "1");
    relation.add("0", "2");

    relation.add("1", "2");
    relation.add("2", "1");

    relation.add("3", "1");
    relation.add("3", "2");

    assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1"]);
    assert_eq!(relation.parents(&"0"), vec![&"1"]);
}

#[test]
fn pdub_crisscross() {
    // diagonal edges run left-to-right
    // a -> a1 -> x
    //   \/       ^
    //   /\       |
    // b -> b1 ---+

    let mut relation = TransitiveRelation::default();
    relation.add("a", "a1");
    relation.add("a", "b1");
    relation.add("b", "a1");
    relation.add("b", "b1");
    relation.add("a1", "x");
    relation.add("b1", "x");

    assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"a1", &"b1"]);
    assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x"));
    assert_eq!(relation.postdom_parent(&"a"), Some(&"x"));
    assert_eq!(relation.postdom_parent(&"b"), Some(&"x"));
}

#[test]
fn pdub_crisscross_more() {
    // diagonal edges run left-to-right
    // a -> a1 -> a2 -> a3 -> x
    //   \/    \/             ^
    //   /\    /\             |
    // b -> b1 -> b2 ---------+

    let mut relation = TransitiveRelation::default();
    relation.add("a", "a1");
    relation.add("a", "b1");
    relation.add("b", "a1");
    relation.add("b", "b1");

    relation.add("a1", "a2");
    relation.add("a1", "b2");
    relation.add("b1", "a2");
    relation.add("b1", "b2");

    relation.add("a2", "a3");

    relation.add("a3", "x");
    relation.add("b2", "x");

    assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"a1", &"b1"]);
    assert_eq!(relation.minimal_upper_bounds(&"a1", &"b1"), vec![&"a2", &"b2"]);
    assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x"));

    assert_eq!(relation.postdom_parent(&"a"), Some(&"x"));
    assert_eq!(relation.postdom_parent(&"b"), Some(&"x"));
}

#[test]
fn pdub_lub() {
    // a -> a1 -> x
    //            ^
    //            |
    // b -> b1 ---+

    let mut relation = TransitiveRelation::default();
    relation.add("a", "a1");
    relation.add("b", "b1");
    relation.add("a1", "x");
    relation.add("b1", "x");

    assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"x"]);
    assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x"));

    assert_eq!(relation.postdom_parent(&"a"), Some(&"a1"));
    assert_eq!(relation.postdom_parent(&"b"), Some(&"b1"));
    assert_eq!(relation.postdom_parent(&"a1"), Some(&"x"));
    assert_eq!(relation.postdom_parent(&"b1"), Some(&"x"));
}

#[test]
fn mubs_intermediate_node_on_one_side_only() {
    // a -> c -> d
    //           ^
    //           |
    //           b

    // "digraph { a -> c -> d; b -> d; }",
    let mut relation = TransitiveRelation::default();
    relation.add("a", "c");
    relation.add("c", "d");
    relation.add("b", "d");

    assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"d"]);
}

#[test]
fn mubs_scc_1() {
    // +-------------+
    // |    +----+   |
    // |    v    |   |
    // a -> c -> d <-+
    //           ^
    //           |
    //           b

    // "digraph { a -> c -> d; d -> c; a -> d; b -> d; }",
    let mut relation = TransitiveRelation::default();
    relation.add("a", "c");
    relation.add("c", "d");
    relation.add("d", "c");
    relation.add("a", "d");
    relation.add("b", "d");

    assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
}

#[test]
fn mubs_scc_2() {
    //      +----+
    //      v    |
    // a -> c -> d
    //      ^    ^
    //      |    |
    //      +--- b

    // "digraph { a -> c -> d; d -> c; b -> d; b -> c; }",
    let mut relation = TransitiveRelation::default();
    relation.add("a", "c");
    relation.add("c", "d");
    relation.add("d", "c");
    relation.add("b", "d");
    relation.add("b", "c");

    assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
}

#[test]
fn mubs_scc_3() {
    //      +---------+
    //      v         |
    // a -> c -> d -> e
    //           ^    ^
    //           |    |
    //           b ---+

    // "digraph { a -> c -> d -> e -> c; b -> d; b -> e; }",
    let mut relation = TransitiveRelation::default();
    relation.add("a", "c");
    relation.add("c", "d");
    relation.add("d", "e");
    relation.add("e", "c");
    relation.add("b", "d");
    relation.add("b", "e");

    assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
}

#[test]
fn mubs_scc_4() {
    //      +---------+
    //      v         |
    // a -> c -> d -> e
    // |         ^    ^
    // +---------+    |
    //                |
    //           b ---+

    // "digraph { a -> c -> d -> e -> c; a -> d; b -> e; }"
    let mut relation = TransitiveRelation::default();
    relation.add("a", "c");
    relation.add("c", "d");
    relation.add("d", "e");
    relation.add("e", "c");
    relation.add("a", "d");
    relation.add("b", "e");

    assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
}

#[test]
fn parent() {
    // An example that was misbehaving in the compiler.
    //
    // 4 -> 1 -> 3
    //   \  |   /
    //    \ v  /
    // 2 -> 0
    //
    // plus a bunch of self-loops
    //
    // Here `->` represents `<=` and `0` is `'static`.

    let pairs = vec![
        (2, /*->*/ 0),
        (2, /*->*/ 2),
        (0, /*->*/ 0),
        (0, /*->*/ 0),
        (1, /*->*/ 0),
        (1, /*->*/ 1),
        (3, /*->*/ 0),
        (3, /*->*/ 3),
        (4, /*->*/ 0),
        (4, /*->*/ 1),
        (1, /*->*/ 3),
    ];

    let mut relation = TransitiveRelation::default();
    for (a, b) in pairs {
        relation.add(a, b);
    }

    let p = relation.postdom_parent(&3);
    assert_eq!(p, Some(&0));
}