New upstream version 1.31.0~beta.4+dfsg1

[rustc.git] / src / librustc_data_structures / transitive_relation.rs

diff --git a/src/librustc_data_structures/transitive_relation.rs b/src/librustc_data_structures/transitive_relation.rs
index 2acc29acb0caafd0325520d054fd1c18969d3127..e1318eb54d581df20643b9cd4d2d4bc486a738a6 100644 (file)
--- a/src/librustc_data_structures/transitive_relation.rs
+++ b/src/librustc_data_structures/transitive_relation.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use bitvec::BitMatrix;
+use bit_set::BitMatrix;
 use fx::FxHashMap;
 use sync::Lock;
 use rustc_serialize::{Encodable, Encoder, Decodable, Decoder};
@@ -51,16 +51,18 @@ struct Edge {
     target: Index,
 }
 
-impl<T: Clone + Debug + Eq + Hash> TransitiveRelation<T> {
-    pub fn new() -> TransitiveRelation<T> {
+impl<T: Clone + Debug + Eq + Hash> Default for TransitiveRelation<T> {
+    fn default() -> TransitiveRelation<T> {
         TransitiveRelation {
             elements: vec![],
-            map: FxHashMap(),
+            map: FxHashMap::default(),
             edges: vec![],
             closure: Lock::new(None),
         }
     }
+}
 
+impl<T: Clone + Debug + Eq + Hash> TransitiveRelation<T> {
     pub fn is_empty(&self) -> bool {
         self.edges.is_empty()
     }
@@ -95,7 +97,7 @@ impl<T: Clone + Debug + Eq + Hash> TransitiveRelation<T> {
         where F: FnMut(&T) -> Option<U>,
               U: Clone + Debug + Eq + Hash + Clone,
     {
-        let mut result = TransitiveRelation::new();
+        let mut result = TransitiveRelation::default();
         for edge in &self.edges {
             result.add(f(&self.elements[edge.source.0])?, f(&self.elements[edge.target.0])?);
         }
@@ -279,7 +281,7 @@ impl<T: Clone + Debug + Eq + Hash> TransitiveRelation<T> {
             //
             // This same algorithm is used in `parents` below.
 
-            let mut candidates = closure.intersection(a.0, b.0); // (1)
+            let mut candidates = closure.intersect_rows(a.0, b.0); // (1)
             pare_down(&mut candidates, closure); // (2)
             candidates.reverse(); // (3a)
             pare_down(&mut candidates, closure); // (3b)
@@ -321,7 +323,7 @@ impl<T: Clone + Debug + Eq + Hash> TransitiveRelation<T> {
         // with a slight tweak. In the case where `a R a`, we remove
         // that from the set of candidates.
         let ancestors = self.with_closure(|closure| {
-            let mut ancestors = closure.intersection(a.0, a.0);
+            let mut ancestors = closure.intersect_rows(a.0, a.0);
 
             // Remove anything that can reach `a`. If this is a
             // reflexive relation, this will include `a` itself.
@@ -366,10 +368,10 @@ impl<T: Clone + Debug + Eq + Hash> TransitiveRelation<T> {
             changed = false;
             for edge in &self.edges {
                 // add an edge from S -> T
-                changed |= matrix.add(edge.source.0, edge.target.0);
+                changed |= matrix.insert(edge.source.0, edge.target.0);
 
                 // add all outgoing edges from T into S
-                changed |= matrix.merge(edge.target.0, edge.source.0);
+                changed |= matrix.union_rows(edge.target.0, edge.source.0);
             }
         }
         matrix
@@ -487,7 +489,7 @@ impl<CTX> HashStable<CTX> for Index {
 
 #[test]
 fn test_one_step() {
-    let mut relation = TransitiveRelation::new();
+    let mut relation = TransitiveRelation::default();
     relation.add("a", "b");
     relation.add("a", "c");
     assert!(relation.contains(&"a", &"c"));
@@ -498,7 +500,7 @@ fn test_one_step() {
 
 #[test]
 fn test_many_steps() {
-    let mut relation = TransitiveRelation::new();
+    let mut relation = TransitiveRelation::default();
     relation.add("a", "b");
     relation.add("a", "c");
     relation.add("a", "f");
@@ -528,7 +530,7 @@ fn mubs_triangle() {
     //      ^
     //      |
     //      b
-    let mut relation = TransitiveRelation::new();
+    let mut relation = TransitiveRelation::default();
     relation.add("a", "tcx");
     relation.add("b", "tcx");
     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"tcx"]);
@@ -549,7 +551,7 @@ fn mubs_best_choice1() {
     // need the second pare down call to get the right result (after
     // intersection, we have [1, 2], but 2 -> 1).
 
-    let mut relation = TransitiveRelation::new();
+    let mut relation = TransitiveRelation::default();
     relation.add("0", "1");
     relation.add("0", "2");
 
@@ -576,7 +578,7 @@ fn mubs_best_choice2() {
     // 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::new();
+    let mut relation = TransitiveRelation::default();
     relation.add("0", "1");
     relation.add("0", "2");
 
@@ -595,7 +597,7 @@ fn mubs_best_choice2() {
 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::new();
+    let mut relation = TransitiveRelation::default();
     relation.add("0", "1");
     relation.add("0", "2");
 
@@ -612,7 +614,7 @@ fn mubs_best_choice_scc() {
     // in this case, 1 and 2 form a cycle; we pick arbitrarily (but
     // consistently).
 
-    let mut relation = TransitiveRelation::new();
+    let mut relation = TransitiveRelation::default();
     relation.add("0", "1");
     relation.add("0", "2");
 
@@ -634,7 +636,7 @@ fn pdub_crisscross() {
     //   /\       |
     // b -> b1 ---+
 
-    let mut relation = TransitiveRelation::new();
+    let mut relation = TransitiveRelation::default();
     relation.add("a", "a1");
     relation.add("a", "b1");
     relation.add("b", "a1");
@@ -657,7 +659,7 @@ fn pdub_crisscross_more() {
     //   /\    /\             |
     // b -> b1 -> b2 ---------+
 
-    let mut relation = TransitiveRelation::new();
+    let mut relation = TransitiveRelation::default();
     relation.add("a", "a1");
     relation.add("a", "b1");
     relation.add("b", "a1");
@@ -690,7 +692,7 @@ fn pdub_lub() {
     //            |
     // b -> b1 ---+
 
-    let mut relation = TransitiveRelation::new();
+    let mut relation = TransitiveRelation::default();
     relation.add("a", "a1");
     relation.add("b", "b1");
     relation.add("a1", "x");
@@ -713,7 +715,7 @@ fn mubs_intermediate_node_on_one_side_only() {
     //           b
 
     // "digraph { a -> c -> d; b -> d; }",
-    let mut relation = TransitiveRelation::new();
+    let mut relation = TransitiveRelation::default();
     relation.add("a", "c");
     relation.add("c", "d");
     relation.add("b", "d");
@@ -732,7 +734,7 @@ fn mubs_scc_1() {
     //           b
 
     // "digraph { a -> c -> d; d -> c; a -> d; b -> d; }",
-    let mut relation = TransitiveRelation::new();
+    let mut relation = TransitiveRelation::default();
     relation.add("a", "c");
     relation.add("c", "d");
     relation.add("d", "c");
@@ -752,7 +754,7 @@ fn mubs_scc_2() {
     //      +--- b
 
     // "digraph { a -> c -> d; d -> c; b -> d; b -> c; }",
-    let mut relation = TransitiveRelation::new();
+    let mut relation = TransitiveRelation::default();
     relation.add("a", "c");
     relation.add("c", "d");
     relation.add("d", "c");
@@ -772,7 +774,7 @@ fn mubs_scc_3() {
     //           b ---+
 
     // "digraph { a -> c -> d -> e -> c; b -> d; b -> e; }",
-    let mut relation = TransitiveRelation::new();
+    let mut relation = TransitiveRelation::default();
     relation.add("a", "c");
     relation.add("c", "d");
     relation.add("d", "e");
@@ -794,7 +796,7 @@ fn mubs_scc_4() {
     //           b ---+
 
     // "digraph { a -> c -> d -> e -> c; a -> d; b -> e; }"
-    let mut relation = TransitiveRelation::new();
+    let mut relation = TransitiveRelation::default();
     relation.add("a", "c");
     relation.add("c", "d");
     relation.add("d", "e");
@@ -832,7 +834,7 @@ fn parent() {
         (1, /*->*/ 3),
     ];
 
-    let mut relation = TransitiveRelation::new();
+    let mut relation = TransitiveRelation::default();
     for (a, b) in pairs {
         relation.add(a, b);
     }