Imported Upstream version 1.9.0+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 7ea5cb8721d5932153df7dd852868b806499220e..c3a2f978e1a8a4945f39ed8c091edbe5857ef762 100644 (file)
--- a/src/librustc_data_structures/transitive_relation.rs
+++ b/src/librustc_data_structures/transitive_relation.rs
@@ -14,7 +14,7 @@ use std::fmt::Debug;
 use std::mem;
 
 #[derive(Clone)]
-pub struct TransitiveRelation<T:Debug+PartialEq> {
+pub struct TransitiveRelation<T: Debug + PartialEq> {
     // List of elements. This is used to map from a T to a usize.  We
     // expect domain to be small so just use a linear list versus a
     // hashmap or something.
@@ -33,7 +33,7 @@ pub struct TransitiveRelation<T:Debug+PartialEq> {
     // are added with new elements. Perhaps better would be to ask the
     // user for a batch of edges to minimize this effect, but I
     // already wrote the code this way. :P -nmatsakis
-    closure: RefCell<Option<BitMatrix>>
+    closure: RefCell<Option<BitMatrix>>,
 }
 
 #[derive(Clone, PartialEq, PartialOrd)]
@@ -45,11 +45,13 @@ struct Edge {
     target: Index,
 }
 
-impl<T:Debug+PartialEq> TransitiveRelation<T> {
+impl<T: Debug + PartialEq> TransitiveRelation<T> {
     pub fn new() -> TransitiveRelation<T> {
-        TransitiveRelation { elements: vec![],
-                             edges: vec![],
-                             closure: RefCell::new(None) }
+        TransitiveRelation {
+            elements: vec![],
+            edges: vec![],
+            closure: RefCell::new(None),
+        }
     }
 
     fn index(&self, a: &T) -> Option<Index> {
@@ -74,7 +76,10 @@ impl<T:Debug+PartialEq> TransitiveRelation<T> {
     pub fn add(&mut self, a: T, b: T) {
         let a = self.add_index(a);
         let b = self.add_index(b);
-        let edge = Edge { source: a, target: b };
+        let edge = Edge {
+            source: a,
+            target: b,
+        };
         if !self.edges.contains(&edge) {
             self.edges.push(edge);
 
@@ -86,10 +91,8 @@ impl<T:Debug+PartialEq> TransitiveRelation<T> {
     /// Check whether `a < target` (transitively)
     pub fn contains(&self, a: &T, b: &T) -> bool {
         match (self.index(a), self.index(b)) {
-            (Some(a), Some(b)) =>
-                self.with_closure(|closure| closure.contains(a.0, b.0)),
-            (None, _) | (_, None) =>
-                false,
+            (Some(a), Some(b)) => self.with_closure(|closure| closure.contains(a.0, b.0)),
+            (None, _) | (_, None) => false,
         }
     }
 
@@ -156,7 +159,9 @@ impl<T:Debug+PartialEq> TransitiveRelation<T> {
     pub fn minimal_upper_bounds(&self, a: &T, b: &T) -> Vec<&T> {
         let (mut a, mut b) = match (self.index(a), self.index(b)) {
             (Some(a), Some(b)) => (a, b),
-            (None, _) | (_, None) => { return vec![]; }
+            (None, _) | (_, None) => {
+                return vec![];
+            }
         };
 
         // in some cases, there are some arbitrary choices to be made;
@@ -233,7 +238,7 @@ impl<T:Debug+PartialEq> TransitiveRelation<T> {
                    .collect()
     }
 
-    fn with_closure<OP,R>(&self, op: OP) -> R
+    fn with_closure<OP, R>(&self, op: OP) -> R
         where OP: FnOnce(&BitMatrix) -> R
     {
         let mut closure_cell = self.closure.borrow_mut();
@@ -431,14 +436,15 @@ fn pdub_crisscross() {
     // b -> b1 ---+
 
     let mut relation = TransitiveRelation::new();
-    relation.add("a",  "a1");
-    relation.add("a",  "b1");
-    relation.add("b",  "a1");
-    relation.add("b",  "b1");
+    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.minimal_upper_bounds(&"a", &"b"),
+               vec![&"a1", &"b1"]);
     assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x"));
 }
 
@@ -451,23 +457,25 @@ fn pdub_crisscross_more() {
     // b -> b1 -> b2 ---------+
 
     let mut relation = TransitiveRelation::new();
-    relation.add("a",  "a1");
-    relation.add("a",  "b1");
-    relation.add("b",  "a1");
-    relation.add("b",  "b1");
+    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("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.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"));
 }
 
@@ -479,8 +487,8 @@ fn pdub_lub() {
     // b -> b1 ---+
 
     let mut relation = TransitiveRelation::new();
-    relation.add("a",  "a1");
-    relation.add("b",  "b1");
+    relation.add("a", "a1");
+    relation.add("b", "b1");
     relation.add("a1", "x");
     relation.add("b1", "x");
 
@@ -497,9 +505,9 @@ fn mubs_intermediate_node_on_one_side_only() {
 
     // "digraph { a -> c -> d; b -> d; }",
     let mut relation = TransitiveRelation::new();
-    relation.add("a",  "c");
-    relation.add("c",  "d");
-    relation.add("b",  "d");
+    relation.add("a", "c");
+    relation.add("c", "d");
+    relation.add("b", "d");
 
     assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"d"]);
 }
@@ -516,11 +524,11 @@ fn mubs_scc_1() {
 
     // "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");
+    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"]);
 }
@@ -536,11 +544,11 @@ fn mubs_scc_2() {
 
     // "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");
+    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"]);
 }
@@ -556,12 +564,12 @@ fn mubs_scc_3() {
 
     // "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("d",  "e");
-    relation.add("e",  "c");
-    relation.add("b",  "d");
-    relation.add("b",  "e");
+    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"]);
 }
@@ -578,12 +586,12 @@ fn mubs_scc_4() {
 
     // "digraph { a -> c -> d -> e -> c; a -> d; b -> e; }"
     let mut relation = TransitiveRelation::new();
-    relation.add("a",  "c");
-    relation.add("c",  "d");
-    relation.add("d",  "e");
-    relation.add("e",  "c");
-    relation.add("a",  "d");
-    relation.add("b",  "e");
+    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"]);
 }