X-Git-Url: https://git.lizzy.rs/?a=blobdiff_plain;f=src%2Flibrustc_data_structures%2Ftransitive_relation.rs;h=738e516f22ed07f066726eeb49f4c240c15339f9;hb=2a25876c585ede337fc4167147bbbfa53d30ca2b;hp=311ca054e8702864ee001bcef29f2798d3ae4a42;hpb=36809bf260dd3951fd9ffaa14556246abb17e5ea;p=rust.git

diff --git a/src/librustc_data_structures/transitive_relation.rs b/src/librustc_data_structures/transitive_relation.rs
index 311ca054e87..738e516f22e 100644
--- a/src/librustc_data_structures/transitive_relation.rs
+++ b/src/librustc_data_structures/transitive_relation.rs
@@ -464,3 +464,85 @@ fn bub_lub() {
     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"x"]);
     assert_eq!(relation.best_upper_bound(&"a", &"b"), 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::new();
+    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::new();
+    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::new();
+    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::new();
+    relation.add("a",  "c");
+    relation.add("c",  "d");
+    relation.add("e",  "e");
+    relation.add("e",  "c");
+    relation.add("b",  "d");
+    relation.add("b",  "e");
+
+    assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
+}
+
+/*
+    "digraph { a -> c -> d -> e -> c; a -> d; b -> e; }"
+*/