librustc_data_structures: Unconfigure tests during normal build

29 files changed, 1180 insertions, 1169 deletions

diff --git a/src/librustc_data_structures/base_n.rs b/src/librustc_data_structures/base_n.rs
index f1bd3f03aef..9b63a892b8c 100644
--- a/src/librustc_data_structures/base_n.rs
+++ b/src/librustc_data_structures/base_n.rs
@@ -3,6 +3,9 @@
 
 use std::str;
 
+#[cfg(test)]
+mod tests;
+
 pub const MAX_BASE: usize = 64;
 pub const ALPHANUMERIC_ONLY: usize = 62;
 pub const CASE_INSENSITIVE: usize = 36;
@@ -38,24 +41,3 @@ pub fn encode(n: u128, base: usize) -> String {
     push_str(n, base, &mut s);
     s
 }
-
-#[test]
-fn test_encode() {
-    fn test(n: u128, base: usize) {
-        assert_eq!(Ok(n), u128::from_str_radix(&encode(n, base), base as u32));
-    }
-
-    for base in 2..37 {
-        test(0, base);
-        test(1, base);
-        test(35, base);
-        test(36, base);
-        test(37, base);
-        test(u64::max_value() as u128, base);
-        test(u128::max_value(), base);
-
-        for i in 0 .. 1_000 {
-            test(i * 983, base);
-        }
-    }
-}
diff --git a/src/librustc_data_structures/base_n/tests.rs b/src/librustc_data_structures/base_n/tests.rs
new file mode 100644
index 00000000000..0b0a8c5e256
--- /dev/null
+++ b/src/librustc_data_structures/base_n/tests.rs
@@ -0,0 +1,22 @@
+use super::*;
+
+#[test]
+fn test_encode() {
+    fn test(n: u128, base: usize) {
+        assert_eq!(Ok(n), u128::from_str_radix(&encode(n, base), base as u32));
+    }
+
+    for base in 2..37 {
+        test(0, base);
+        test(1, base);
+        test(35, base);
+        test(36, base);
+        test(37, base);
+        test(u64::max_value() as u128, base);
+        test(u128::max_value(), base);
+
+        for i in 0 .. 1_000 {
+            test(i * 983, base);
+        }
+    }
+}
diff --git a/src/librustc_data_structures/binary_search_util/mod.rs b/src/librustc_data_structures/binary_search_util/mod.rs
index 32aa1cb6b1d..6d1e1abbcef 100644
--- a/src/librustc_data_structures/binary_search_util/mod.rs
+++ b/src/librustc_data_structures/binary_search_util/mod.rs
@@ -1,5 +1,5 @@
 #[cfg(test)]
-mod test;
+mod tests;
 
 /// Uses a sorted slice `data: &[E]` as a kind of "multi-map". The
 /// `key_fn` extracts a key of type `K` from the data, and this
diff --git a/src/librustc_data_structures/binary_search_util/test.rs b/src/librustc_data_structures/binary_search_util/tests.rs
index d74febb5c0f..d74febb5c0f 100644
--- a/src/librustc_data_structures/binary_search_util/test.rs
+++ b/src/librustc_data_structures/binary_search_util/tests.rs
diff --git a/src/librustc_data_structures/bit_set.rs b/src/librustc_data_structures/bit_set.rs
index 1eb28bccbe3..fe8ef642430 100644
--- a/src/librustc_data_structures/bit_set.rs
+++ b/src/librustc_data_structures/bit_set.rs
@@ -5,10 +5,9 @@ use std::iter;
 use std::marker::PhantomData;
 use std::mem;
 use std::slice;
+
 #[cfg(test)]
-extern crate test;
-#[cfg(test)]
-use test::Bencher;
+mod tests;
 
 pub type Word = u64;
 pub const WORD_BYTES: usize = mem::size_of::<Word>();
@@ -983,368 +982,3 @@ fn word_index_and_mask<T: Idx>(elem: T) -> (usize, Word) {
     let mask = 1 << (elem % WORD_BITS);
     (word_index, mask)
 }
-
-#[test]
-fn test_new_filled() {
-    for i in 0..128 {
-        let idx_buf = BitSet::new_filled(i);
-        let elems: Vec<usize> = idx_buf.iter().collect();
-        let expected: Vec<usize> = (0..i).collect();
-        assert_eq!(elems, expected);
-    }
-}
-
-#[test]
-fn bitset_iter_works() {
-    let mut bitset: BitSet<usize> = BitSet::new_empty(100);
-    bitset.insert(1);
-    bitset.insert(10);
-    bitset.insert(19);
-    bitset.insert(62);
-    bitset.insert(63);
-    bitset.insert(64);
-    bitset.insert(65);
-    bitset.insert(66);
-    bitset.insert(99);
-    assert_eq!(
-        bitset.iter().collect::<Vec<_>>(),
-        [1, 10, 19, 62, 63, 64, 65, 66, 99]
-    );
-}
-
-#[test]
-fn bitset_iter_works_2() {
-    let mut bitset: BitSet<usize> = BitSet::new_empty(320);
-    bitset.insert(0);
-    bitset.insert(127);
-    bitset.insert(191);
-    bitset.insert(255);
-    bitset.insert(319);
-    assert_eq!(bitset.iter().collect::<Vec<_>>(), [0, 127, 191, 255, 319]);
-}
-
-#[test]
-fn union_two_sets() {
-    let mut set1: BitSet<usize> = BitSet::new_empty(65);
-    let mut set2: BitSet<usize> = BitSet::new_empty(65);
-    assert!(set1.insert(3));
-    assert!(!set1.insert(3));
-    assert!(set2.insert(5));
-    assert!(set2.insert(64));
-    assert!(set1.union(&set2));
-    assert!(!set1.union(&set2));
-    assert!(set1.contains(3));
-    assert!(!set1.contains(4));
-    assert!(set1.contains(5));
-    assert!(!set1.contains(63));
-    assert!(set1.contains(64));
-}
-
-#[test]
-fn hybrid_bitset() {
-    let mut sparse038: HybridBitSet<usize> = HybridBitSet::new_empty(256);
-    assert!(sparse038.is_empty());
-    assert!(sparse038.insert(0));
-    assert!(sparse038.insert(1));
-    assert!(sparse038.insert(8));
-    assert!(sparse038.insert(3));
-    assert!(!sparse038.insert(3));
-    assert!(sparse038.remove(1));
-    assert!(!sparse038.is_empty());
-    assert_eq!(sparse038.iter().collect::<Vec<_>>(), [0, 3, 8]);
-
-    for i in 0..256 {
-        if i == 0 || i == 3 || i == 8 {
-            assert!(sparse038.contains(i));
-        } else {
-            assert!(!sparse038.contains(i));
-        }
-    }
-
-    let mut sparse01358 = sparse038.clone();
-    assert!(sparse01358.insert(1));
-    assert!(sparse01358.insert(5));
-    assert_eq!(sparse01358.iter().collect::<Vec<_>>(), [0, 1, 3, 5, 8]);
-
-    let mut dense10 = HybridBitSet::new_empty(256);
-    for i in 0..10 {
-        assert!(dense10.insert(i));
-    }
-    assert!(!dense10.is_empty());
-    assert_eq!(dense10.iter().collect::<Vec<_>>(), [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
-
-    let mut dense256 = HybridBitSet::new_empty(256);
-    assert!(dense256.is_empty());
-    dense256.insert_all();
-    assert!(!dense256.is_empty());
-    for i in 0..256 {
-        assert!(dense256.contains(i));
-    }
-
-    assert!(sparse038.superset(&sparse038));    // sparse + sparse (self)
-    assert!(sparse01358.superset(&sparse038));  // sparse + sparse
-    assert!(dense10.superset(&sparse038));      // dense + sparse
-    assert!(dense10.superset(&dense10));        // dense + dense (self)
-    assert!(dense256.superset(&dense10));       // dense + dense
-
-    let mut hybrid = sparse038;
-    assert!(!sparse01358.union(&hybrid));       // no change
-    assert!(hybrid.union(&sparse01358));
-    assert!(hybrid.superset(&sparse01358) && sparse01358.superset(&hybrid));
-    assert!(!dense10.union(&sparse01358));
-    assert!(!dense256.union(&dense10));
-    let mut dense = dense10;
-    assert!(dense.union(&dense256));
-    assert!(dense.superset(&dense256) && dense256.superset(&dense));
-    assert!(hybrid.union(&dense256));
-    assert!(hybrid.superset(&dense256) && dense256.superset(&hybrid));
-
-    assert_eq!(dense256.iter().count(), 256);
-    let mut dense0 = dense256;
-    for i in 0..256 {
-        assert!(dense0.remove(i));
-    }
-    assert!(!dense0.remove(0));
-    assert!(dense0.is_empty());
-}
-
-#[test]
-fn grow() {
-    let mut set: GrowableBitSet<usize> = GrowableBitSet::with_capacity(65);
-    for index in 0..65 {
-        assert!(set.insert(index));
-        assert!(!set.insert(index));
-    }
-    set.ensure(128);
-
-    // Check if the bits set before growing are still set
-    for index in 0..65 {
-        assert!(set.contains(index));
-    }
-
-    // Check if the new bits are all un-set
-    for index in 65..128 {
-        assert!(!set.contains(index));
-    }
-
-    // Check that we can set all new bits without running out of bounds
-    for index in 65..128 {
-        assert!(set.insert(index));
-        assert!(!set.insert(index));
-    }
-}
-
-#[test]
-fn matrix_intersection() {
-    let mut matrix: BitMatrix<usize, usize> = BitMatrix::new(200, 200);
-
-    // (*) Elements reachable from both 2 and 65.
-
-    matrix.insert(2, 3);
-    matrix.insert(2, 6);
-    matrix.insert(2, 10); // (*)
-    matrix.insert(2, 64); // (*)
-    matrix.insert(2, 65);
-    matrix.insert(2, 130);
-    matrix.insert(2, 160); // (*)
-
-    matrix.insert(64, 133);
-
-    matrix.insert(65, 2);
-    matrix.insert(65, 8);
-    matrix.insert(65, 10); // (*)
-    matrix.insert(65, 64); // (*)
-    matrix.insert(65, 68);
-    matrix.insert(65, 133);
-    matrix.insert(65, 160); // (*)
-
-    let intersection = matrix.intersect_rows(2, 64);
-    assert!(intersection.is_empty());
-
-    let intersection = matrix.intersect_rows(2, 65);
-    assert_eq!(intersection, &[10, 64, 160]);
-}
-
-#[test]
-fn matrix_iter() {
-    let mut matrix: BitMatrix<usize, usize> = BitMatrix::new(64, 100);
-    matrix.insert(3, 22);
-    matrix.insert(3, 75);
-    matrix.insert(2, 99);
-    matrix.insert(4, 0);
-    matrix.union_rows(3, 5);
-    matrix.insert_all_into_row(6);
-
-    let expected = [99];
-    let mut iter = expected.iter();
-    for i in matrix.iter(2) {
-        let j = *iter.next().unwrap();
-        assert_eq!(i, j);
-    }
-    assert!(iter.next().is_none());
-
-    let expected = [22, 75];
-    let mut iter = expected.iter();
-    assert_eq!(matrix.count(3), expected.len());
-    for i in matrix.iter(3) {
-        let j = *iter.next().unwrap();
-        assert_eq!(i, j);
-    }
-    assert!(iter.next().is_none());
-
-    let expected = [0];
-    let mut iter = expected.iter();
-    assert_eq!(matrix.count(4), expected.len());
-    for i in matrix.iter(4) {
-        let j = *iter.next().unwrap();
-        assert_eq!(i, j);
-    }
-    assert!(iter.next().is_none());
-
-    let expected = [22, 75];
-    let mut iter = expected.iter();
-    assert_eq!(matrix.count(5), expected.len());
-    for i in matrix.iter(5) {
-        let j = *iter.next().unwrap();
-        assert_eq!(i, j);
-    }
-    assert!(iter.next().is_none());
-
-    assert_eq!(matrix.count(6), 100);
-    let mut count = 0;
-    for (idx, i) in matrix.iter(6).enumerate() {
-        assert_eq!(idx, i);
-        count += 1;
-    }
-    assert_eq!(count, 100);
-
-    if let Some(i) = matrix.iter(7).next() {
-        panic!("expected no elements in row, but contains element {:?}", i);
-    }
-}
-
-#[test]
-fn sparse_matrix_iter() {
-    let mut matrix: SparseBitMatrix<usize, usize> = SparseBitMatrix::new(100);
-    matrix.insert(3, 22);
-    matrix.insert(3, 75);
-    matrix.insert(2, 99);
-    matrix.insert(4, 0);
-    matrix.union_rows(3, 5);
-
-    let expected = [99];
-    let mut iter = expected.iter();
-    for i in matrix.iter(2) {
-        let j = *iter.next().unwrap();
-        assert_eq!(i, j);
-    }
-    assert!(iter.next().is_none());
-
-    let expected = [22, 75];
-    let mut iter = expected.iter();
-    for i in matrix.iter(3) {
-        let j = *iter.next().unwrap();
-        assert_eq!(i, j);
-    }
-    assert!(iter.next().is_none());
-
-    let expected = [0];
-    let mut iter = expected.iter();
-    for i in matrix.iter(4) {
-        let j = *iter.next().unwrap();
-        assert_eq!(i, j);
-    }
-    assert!(iter.next().is_none());
-
-    let expected = [22, 75];
-    let mut iter = expected.iter();
-    for i in matrix.iter(5) {
-        let j = *iter.next().unwrap();
-        assert_eq!(i, j);
-    }
-    assert!(iter.next().is_none());
-}
-
-/// Merge dense hybrid set into empty sparse hybrid set.
-#[bench]
-fn union_hybrid_sparse_empty_to_dense(b: &mut Bencher) {
-    let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(256);
-    for i in 0..10 {
-        assert!(pre_dense.insert(i));
-    }
-    let pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(256);
-    b.iter(|| {
-        let dense = pre_dense.clone();
-        let mut sparse = pre_sparse.clone();
-        sparse.union(&dense);
-    })
-}
-
-/// Merge dense hybrid set into full hybrid set with same indices.
-#[bench]
-fn union_hybrid_sparse_full_to_dense(b: &mut Bencher) {
-    let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(256);
-    for i in 0..10 {
-        assert!(pre_dense.insert(i));
-    }
-    let mut pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(256);
-    for i in 0..SPARSE_MAX {
-        assert!(pre_sparse.insert(i));
-    }
-    b.iter(|| {
-        let dense = pre_dense.clone();
-        let mut sparse = pre_sparse.clone();
-        sparse.union(&dense);
-    })
-}
-
-/// Merge dense hybrid set into full hybrid set with indices over the whole domain.
-#[bench]
-fn union_hybrid_sparse_domain_to_dense(b: &mut Bencher) {
-    let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX*64);
-    for i in 0..10 {
-        assert!(pre_dense.insert(i));
-    }
-    let mut pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX*64);
-    for i in 0..SPARSE_MAX {
-        assert!(pre_sparse.insert(i*64));
-    }
-    b.iter(|| {
-        let dense = pre_dense.clone();
-        let mut sparse = pre_sparse.clone();
-        sparse.union(&dense);
-    })
-}
-
-/// Merge dense hybrid set into empty hybrid set where the domain is very small.
-#[bench]
-fn union_hybrid_sparse_empty_small_domain(b: &mut Bencher) {
-    let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
-    for i in 0..SPARSE_MAX {
-        assert!(pre_dense.insert(i));
-    }
-    let pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
-    b.iter(|| {
-        let dense = pre_dense.clone();
-        let mut sparse = pre_sparse.clone();
-        sparse.union(&dense);
-    })
-}
-
-/// Merge dense hybrid set into full hybrid set where the domain is very small.
-#[bench]
-fn union_hybrid_sparse_full_small_domain(b: &mut Bencher) {
-    let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
-    for i in 0..SPARSE_MAX {
-        assert!(pre_dense.insert(i));
-    }
-    let mut pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
-    for i in 0..SPARSE_MAX {
-        assert!(pre_sparse.insert(i));
-    }
-    b.iter(|| {
-        let dense = pre_dense.clone();
-        let mut sparse = pre_sparse.clone();
-        sparse.union(&dense);
-    })
-}
diff --git a/src/librustc_data_structures/bit_set/tests.rs b/src/librustc_data_structures/bit_set/tests.rs
new file mode 100644
index 00000000000..ac7913815ff
--- /dev/null
+++ b/src/librustc_data_structures/bit_set/tests.rs
@@ -0,0 +1,369 @@
+use super::*;
+
+extern crate test;
+use test::Bencher;
+
+#[test]
+fn test_new_filled() {
+    for i in 0..128 {
+        let idx_buf = BitSet::new_filled(i);
+        let elems: Vec<usize> = idx_buf.iter().collect();
+        let expected: Vec<usize> = (0..i).collect();
+        assert_eq!(elems, expected);
+    }
+}
+
+#[test]
+fn bitset_iter_works() {
+    let mut bitset: BitSet<usize> = BitSet::new_empty(100);
+    bitset.insert(1);
+    bitset.insert(10);
+    bitset.insert(19);
+    bitset.insert(62);
+    bitset.insert(63);
+    bitset.insert(64);
+    bitset.insert(65);
+    bitset.insert(66);
+    bitset.insert(99);
+    assert_eq!(
+        bitset.iter().collect::<Vec<_>>(),
+        [1, 10, 19, 62, 63, 64, 65, 66, 99]
+    );
+}
+
+#[test]
+fn bitset_iter_works_2() {
+    let mut bitset: BitSet<usize> = BitSet::new_empty(320);
+    bitset.insert(0);
+    bitset.insert(127);
+    bitset.insert(191);
+    bitset.insert(255);
+    bitset.insert(319);
+    assert_eq!(bitset.iter().collect::<Vec<_>>(), [0, 127, 191, 255, 319]);
+}
+
+#[test]
+fn union_two_sets() {
+    let mut set1: BitSet<usize> = BitSet::new_empty(65);
+    let mut set2: BitSet<usize> = BitSet::new_empty(65);
+    assert!(set1.insert(3));
+    assert!(!set1.insert(3));
+    assert!(set2.insert(5));
+    assert!(set2.insert(64));
+    assert!(set1.union(&set2));
+    assert!(!set1.union(&set2));
+    assert!(set1.contains(3));
+    assert!(!set1.contains(4));
+    assert!(set1.contains(5));
+    assert!(!set1.contains(63));
+    assert!(set1.contains(64));
+}
+
+#[test]
+fn hybrid_bitset() {
+    let mut sparse038: HybridBitSet<usize> = HybridBitSet::new_empty(256);
+    assert!(sparse038.is_empty());
+    assert!(sparse038.insert(0));
+    assert!(sparse038.insert(1));
+    assert!(sparse038.insert(8));
+    assert!(sparse038.insert(3));
+    assert!(!sparse038.insert(3));
+    assert!(sparse038.remove(1));
+    assert!(!sparse038.is_empty());
+    assert_eq!(sparse038.iter().collect::<Vec<_>>(), [0, 3, 8]);
+
+    for i in 0..256 {
+        if i == 0 || i == 3 || i == 8 {
+            assert!(sparse038.contains(i));
+        } else {
+            assert!(!sparse038.contains(i));
+        }
+    }
+
+    let mut sparse01358 = sparse038.clone();
+    assert!(sparse01358.insert(1));
+    assert!(sparse01358.insert(5));
+    assert_eq!(sparse01358.iter().collect::<Vec<_>>(), [0, 1, 3, 5, 8]);
+
+    let mut dense10 = HybridBitSet::new_empty(256);
+    for i in 0..10 {
+        assert!(dense10.insert(i));
+    }
+    assert!(!dense10.is_empty());
+    assert_eq!(dense10.iter().collect::<Vec<_>>(), [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
+
+    let mut dense256 = HybridBitSet::new_empty(256);
+    assert!(dense256.is_empty());
+    dense256.insert_all();
+    assert!(!dense256.is_empty());
+    for i in 0..256 {
+        assert!(dense256.contains(i));
+    }
+
+    assert!(sparse038.superset(&sparse038));    // sparse + sparse (self)
+    assert!(sparse01358.superset(&sparse038));  // sparse + sparse
+    assert!(dense10.superset(&sparse038));      // dense + sparse
+    assert!(dense10.superset(&dense10));        // dense + dense (self)
+    assert!(dense256.superset(&dense10));       // dense + dense
+
+    let mut hybrid = sparse038;
+    assert!(!sparse01358.union(&hybrid));       // no change
+    assert!(hybrid.union(&sparse01358));
+    assert!(hybrid.superset(&sparse01358) && sparse01358.superset(&hybrid));
+    assert!(!dense10.union(&sparse01358));
+    assert!(!dense256.union(&dense10));
+    let mut dense = dense10;
+    assert!(dense.union(&dense256));
+    assert!(dense.superset(&dense256) && dense256.superset(&dense));
+    assert!(hybrid.union(&dense256));
+    assert!(hybrid.superset(&dense256) && dense256.superset(&hybrid));
+
+    assert_eq!(dense256.iter().count(), 256);
+    let mut dense0 = dense256;
+    for i in 0..256 {
+        assert!(dense0.remove(i));
+    }
+    assert!(!dense0.remove(0));
+    assert!(dense0.is_empty());
+}
+
+#[test]
+fn grow() {
+    let mut set: GrowableBitSet<usize> = GrowableBitSet::with_capacity(65);
+    for index in 0..65 {
+        assert!(set.insert(index));
+        assert!(!set.insert(index));
+    }
+    set.ensure(128);
+
+    // Check if the bits set before growing are still set
+    for index in 0..65 {
+        assert!(set.contains(index));
+    }
+
+    // Check if the new bits are all un-set
+    for index in 65..128 {
+        assert!(!set.contains(index));
+    }
+
+    // Check that we can set all new bits without running out of bounds
+    for index in 65..128 {
+        assert!(set.insert(index));
+        assert!(!set.insert(index));
+    }
+}
+
+#[test]
+fn matrix_intersection() {
+    let mut matrix: BitMatrix<usize, usize> = BitMatrix::new(200, 200);
+
+    // (*) Elements reachable from both 2 and 65.
+
+    matrix.insert(2, 3);
+    matrix.insert(2, 6);
+    matrix.insert(2, 10); // (*)
+    matrix.insert(2, 64); // (*)
+    matrix.insert(2, 65);
+    matrix.insert(2, 130);
+    matrix.insert(2, 160); // (*)
+
+    matrix.insert(64, 133);
+
+    matrix.insert(65, 2);
+    matrix.insert(65, 8);
+    matrix.insert(65, 10); // (*)
+    matrix.insert(65, 64); // (*)
+    matrix.insert(65, 68);
+    matrix.insert(65, 133);
+    matrix.insert(65, 160); // (*)
+
+    let intersection = matrix.intersect_rows(2, 64);
+    assert!(intersection.is_empty());
+
+    let intersection = matrix.intersect_rows(2, 65);
+    assert_eq!(intersection, &[10, 64, 160]);
+}
+
+#[test]
+fn matrix_iter() {
+    let mut matrix: BitMatrix<usize, usize> = BitMatrix::new(64, 100);
+    matrix.insert(3, 22);
+    matrix.insert(3, 75);
+    matrix.insert(2, 99);
+    matrix.insert(4, 0);
+    matrix.union_rows(3, 5);
+    matrix.insert_all_into_row(6);
+
+    let expected = [99];
+    let mut iter = expected.iter();
+    for i in matrix.iter(2) {
+        let j = *iter.next().unwrap();
+        assert_eq!(i, j);
+    }
+    assert!(iter.next().is_none());
+
+    let expected = [22, 75];
+    let mut iter = expected.iter();
+    assert_eq!(matrix.count(3), expected.len());
+    for i in matrix.iter(3) {
+        let j = *iter.next().unwrap();
+        assert_eq!(i, j);
+    }
+    assert!(iter.next().is_none());
+
+    let expected = [0];
+    let mut iter = expected.iter();
+    assert_eq!(matrix.count(4), expected.len());
+    for i in matrix.iter(4) {
+        let j = *iter.next().unwrap();
+        assert_eq!(i, j);
+    }
+    assert!(iter.next().is_none());
+
+    let expected = [22, 75];
+    let mut iter = expected.iter();
+    assert_eq!(matrix.count(5), expected.len());
+    for i in matrix.iter(5) {
+        let j = *iter.next().unwrap();
+        assert_eq!(i, j);
+    }
+    assert!(iter.next().is_none());
+
+    assert_eq!(matrix.count(6), 100);
+    let mut count = 0;
+    for (idx, i) in matrix.iter(6).enumerate() {
+        assert_eq!(idx, i);
+        count += 1;
+    }
+    assert_eq!(count, 100);
+
+    if let Some(i) = matrix.iter(7).next() {
+        panic!("expected no elements in row, but contains element {:?}", i);
+    }
+}
+
+#[test]
+fn sparse_matrix_iter() {
+    let mut matrix: SparseBitMatrix<usize, usize> = SparseBitMatrix::new(100);
+    matrix.insert(3, 22);
+    matrix.insert(3, 75);
+    matrix.insert(2, 99);
+    matrix.insert(4, 0);
+    matrix.union_rows(3, 5);
+
+    let expected = [99];
+    let mut iter = expected.iter();
+    for i in matrix.iter(2) {
+        let j = *iter.next().unwrap();
+        assert_eq!(i, j);
+    }
+    assert!(iter.next().is_none());
+
+    let expected = [22, 75];
+    let mut iter = expected.iter();
+    for i in matrix.iter(3) {
+        let j = *iter.next().unwrap();
+        assert_eq!(i, j);
+    }
+    assert!(iter.next().is_none());
+
+    let expected = [0];
+    let mut iter = expected.iter();
+    for i in matrix.iter(4) {
+        let j = *iter.next().unwrap();
+        assert_eq!(i, j);
+    }
+    assert!(iter.next().is_none());
+
+    let expected = [22, 75];
+    let mut iter = expected.iter();
+    for i in matrix.iter(5) {
+        let j = *iter.next().unwrap();
+        assert_eq!(i, j);
+    }
+    assert!(iter.next().is_none());
+}
+
+/// Merge dense hybrid set into empty sparse hybrid set.
+#[bench]
+fn union_hybrid_sparse_empty_to_dense(b: &mut Bencher) {
+    let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(256);
+    for i in 0..10 {
+        assert!(pre_dense.insert(i));
+    }
+    let pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(256);
+    b.iter(|| {
+        let dense = pre_dense.clone();
+        let mut sparse = pre_sparse.clone();
+        sparse.union(&dense);
+    })
+}
+
+/// Merge dense hybrid set into full hybrid set with same indices.
+#[bench]
+fn union_hybrid_sparse_full_to_dense(b: &mut Bencher) {
+    let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(256);
+    for i in 0..10 {
+        assert!(pre_dense.insert(i));
+    }
+    let mut pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(256);
+    for i in 0..SPARSE_MAX {
+        assert!(pre_sparse.insert(i));
+    }
+    b.iter(|| {
+        let dense = pre_dense.clone();
+        let mut sparse = pre_sparse.clone();
+        sparse.union(&dense);
+    })
+}
+
+/// Merge dense hybrid set into full hybrid set with indices over the whole domain.
+#[bench]
+fn union_hybrid_sparse_domain_to_dense(b: &mut Bencher) {
+    let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX*64);
+    for i in 0..10 {
+        assert!(pre_dense.insert(i));
+    }
+    let mut pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX*64);
+    for i in 0..SPARSE_MAX {
+        assert!(pre_sparse.insert(i*64));
+    }
+    b.iter(|| {
+        let dense = pre_dense.clone();
+        let mut sparse = pre_sparse.clone();
+        sparse.union(&dense);
+    })
+}
+
+/// Merge dense hybrid set into empty hybrid set where the domain is very small.
+#[bench]
+fn union_hybrid_sparse_empty_small_domain(b: &mut Bencher) {
+    let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
+    for i in 0..SPARSE_MAX {
+        assert!(pre_dense.insert(i));
+    }
+    let pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
+    b.iter(|| {
+        let dense = pre_dense.clone();
+        let mut sparse = pre_sparse.clone();
+        sparse.union(&dense);
+    })
+}
+
+/// Merge dense hybrid set into full hybrid set where the domain is very small.
+#[bench]
+fn union_hybrid_sparse_full_small_domain(b: &mut Bencher) {
+    let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
+    for i in 0..SPARSE_MAX {
+        assert!(pre_dense.insert(i));
+    }
+    let mut pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
+    for i in 0..SPARSE_MAX {
+        assert!(pre_sparse.insert(i));
+    }
+    b.iter(|| {
+        let dense = pre_dense.clone();
+        let mut sparse = pre_sparse.clone();
+        sparse.union(&dense);
+    })
+}
diff --git a/src/librustc_data_structures/graph/dominators/mod.rs b/src/librustc_data_structures/graph/dominators/mod.rs
index 93a2a261c6f..04ddca7896a 100644
--- a/src/librustc_data_structures/graph/dominators/mod.rs
+++ b/src/librustc_data_structures/graph/dominators/mod.rs
@@ -9,7 +9,7 @@ use super::iterate::reverse_post_order;
 use super::ControlFlowGraph;
 
 #[cfg(test)]
-mod test;
+mod tests;
 
 pub fn dominators<G: ControlFlowGraph>(graph: &G) -> Dominators<G::Node> {
     let start_node = graph.start_node();
diff --git a/src/librustc_data_structures/graph/dominators/test.rs b/src/librustc_data_structures/graph/dominators/tests.rs
index 5d17ce9e909..70408fb6df1 100644
--- a/src/librustc_data_structures/graph/dominators/test.rs
+++ b/src/librustc_data_structures/graph/dominators/tests.rs
@@ -1,4 +1,4 @@
-use super::super::test::TestGraph;
+use super::super::tests::TestGraph;
 
 use super::*;
 
diff --git a/src/librustc_data_structures/graph/iterate/mod.rs b/src/librustc_data_structures/graph/iterate/mod.rs
index 5612778ce07..c4185fc7cd9 100644
--- a/src/librustc_data_structures/graph/iterate/mod.rs
+++ b/src/librustc_data_structures/graph/iterate/mod.rs
@@ -3,7 +3,7 @@ use super::{DirectedGraph, WithNumNodes, WithSuccessors};
 use crate::bit_set::BitSet;
 
 #[cfg(test)]
-mod test;
+mod tests;
 
 pub fn post_order_from<G: DirectedGraph + WithSuccessors + WithNumNodes>(
     graph: &G,
diff --git a/src/librustc_data_structures/graph/iterate/test.rs b/src/librustc_data_structures/graph/iterate/tests.rs
index 62e48aaec53..6c7cfd6d8a7 100644
--- a/src/librustc_data_structures/graph/iterate/test.rs
+++ b/src/librustc_data_structures/graph/iterate/tests.rs
@@ -1,4 +1,4 @@
-use super::super::test::TestGraph;
+use super::super::tests::TestGraph;
 
 use super::*;
 
diff --git a/src/librustc_data_structures/graph/mod.rs b/src/librustc_data_structures/graph/mod.rs
index 749709521e8..662581ca1e4 100644
--- a/src/librustc_data_structures/graph/mod.rs
+++ b/src/librustc_data_structures/graph/mod.rs
@@ -8,7 +8,7 @@ pub mod scc;
 pub mod vec_graph;
 
 #[cfg(test)]
-mod test;
+mod tests;
 
 pub trait DirectedGraph {
     type Node: Idx;
diff --git a/src/librustc_data_structures/graph/scc/mod.rs b/src/librustc_data_structures/graph/scc/mod.rs
index 78554cda77b..23a1a2a90a4 100644
--- a/src/librustc_data_structures/graph/scc/mod.rs
+++ b/src/librustc_data_structures/graph/scc/mod.rs
@@ -9,7 +9,8 @@ use crate::graph::vec_graph::VecGraph;
 use crate::indexed_vec::{Idx, IndexVec};
 use std::ops::Range;
 
-mod test;
+#[cfg(test)]
+mod tests;
 
 /// Strongly connected components (SCC) of a graph. The type `N` is
 /// the index type for the graph nodes and `S` is the index type for
diff --git a/src/librustc_data_structures/graph/scc/test.rs b/src/librustc_data_structures/graph/scc/tests.rs
index da3a1ceefe9..6da3ac0ecb8 100644
--- a/src/librustc_data_structures/graph/scc/test.rs
+++ b/src/librustc_data_structures/graph/scc/tests.rs
@@ -1,6 +1,4 @@
-#![cfg(test)]
-
-use crate::graph::test::TestGraph;
+use crate::graph::tests::TestGraph;
 use super::*;
 
 #[test]
diff --git a/src/librustc_data_structures/graph/test.rs b/src/librustc_data_structures/graph/tests.rs
index bc142144e93..bc142144e93 100644
--- a/src/librustc_data_structures/graph/test.rs
+++ b/src/librustc_data_structures/graph/tests.rs
diff --git a/src/librustc_data_structures/graph/vec_graph/mod.rs b/src/librustc_data_structures/graph/vec_graph/mod.rs
index 6fb1bb42d2c..19c61f2680d 100644
--- a/src/librustc_data_structures/graph/vec_graph/mod.rs
+++ b/src/librustc_data_structures/graph/vec_graph/mod.rs
@@ -2,7 +2,7 @@ use crate::indexed_vec::{Idx, IndexVec};
 use crate::graph::{DirectedGraph, WithNumNodes, WithNumEdges, WithSuccessors, GraphSuccessors};
 
 #[cfg(test)]
-mod test;
+mod tests;
 
 pub struct VecGraph<N: Idx> {
     /// Maps from a given node to an index where the set of successors
diff --git a/src/librustc_data_structures/graph/vec_graph/test.rs b/src/librustc_data_structures/graph/vec_graph/tests.rs
index 97a9bd2ad0b..97a9bd2ad0b 100644
--- a/src/librustc_data_structures/graph/vec_graph/test.rs
+++ b/src/librustc_data_structures/graph/vec_graph/tests.rs
diff --git a/src/librustc_data_structures/obligation_forest/mod.rs b/src/librustc_data_structures/obligation_forest/mod.rs
index 557e5e2186f..04d2b23ab1a 100644
--- a/src/librustc_data_structures/obligation_forest/mod.rs
+++ b/src/librustc_data_structures/obligation_forest/mod.rs
@@ -94,7 +94,7 @@ use self::node_index::NodeIndex;
 mod graphviz;
 
 #[cfg(test)]
-mod test;
+mod tests;
 
 pub trait ForestObligation : Clone + Debug {
     type Predicate : Clone + hash::Hash + Eq + Debug;
diff --git a/src/librustc_data_structures/obligation_forest/test.rs b/src/librustc_data_structures/obligation_forest/tests.rs
index 27d4bf4959e..27d4bf4959e 100644
--- a/src/librustc_data_structures/obligation_forest/test.rs
+++ b/src/librustc_data_structures/obligation_forest/tests.rs
diff --git a/src/librustc_data_structures/sip128.rs b/src/librustc_data_structures/sip128.rs
index e5de359e475..1c58eda24f4 100644
--- a/src/librustc_data_structures/sip128.rs
+++ b/src/librustc_data_structures/sip128.rs
@@ -6,6 +6,9 @@ use std::slice;
 use std::ptr;
 use std::mem;
 
+#[cfg(test)]
+mod tests;
+
 #[derive(Debug, Clone)]
 pub struct SipHasher128 {
     k0: u64,
@@ -291,233 +294,3 @@ impl Sip24Rounds {
         compress!(state);
     }
 }
-
-#[cfg(test)]
-mod test {
-    use std::hash::{Hash, Hasher};
-    use std::{slice, mem};
-    use super::SipHasher128;
-
-    // Hash just the bytes of the slice, without length prefix
-    struct Bytes<'a>(&'a [u8]);
-
-    impl<'a> Hash for Bytes<'a> {
-        #[allow(unused_must_use)]
-        fn hash<H: Hasher>(&self, state: &mut H) {
-            for byte in self.0 {
-                state.write_u8(*byte);
-            }
-        }
-    }
-
-    fn hash_with<T: Hash>(mut st: SipHasher128, x: &T) -> (u64, u64) {
-        x.hash(&mut st);
-        st.finish128()
-    }
-
-    fn hash<T: Hash>(x: &T) -> (u64, u64) {
-        hash_with(SipHasher128::new_with_keys(0, 0), x)
-    }
-
-    const TEST_VECTOR : [[u8; 16]; 64] = [
-        [0xa3,0x81,0x7f,0x04,0xba,0x25,0xa8,0xe6,0x6d,0xf6,0x72,0x14,0xc7,0x55,0x02,0x93],
-        [0xda,0x87,0xc1,0xd8,0x6b,0x99,0xaf,0x44,0x34,0x76,0x59,0x11,0x9b,0x22,0xfc,0x45],
-        [0x81,0x77,0x22,0x8d,0xa4,0xa4,0x5d,0xc7,0xfc,0xa3,0x8b,0xde,0xf6,0x0a,0xff,0xe4],
-        [0x9c,0x70,0xb6,0x0c,0x52,0x67,0xa9,0x4e,0x5f,0x33,0xb6,0xb0,0x29,0x85,0xed,0x51],
-        [0xf8,0x81,0x64,0xc1,0x2d,0x9c,0x8f,0xaf,0x7d,0x0f,0x6e,0x7c,0x7b,0xcd,0x55,0x79],
-        [0x13,0x68,0x87,0x59,0x80,0x77,0x6f,0x88,0x54,0x52,0x7a,0x07,0x69,0x0e,0x96,0x27],
-        [0x14,0xee,0xca,0x33,0x8b,0x20,0x86,0x13,0x48,0x5e,0xa0,0x30,0x8f,0xd7,0xa1,0x5e],
-        [0xa1,0xf1,0xeb,0xbe,0xd8,0xdb,0xc1,0x53,0xc0,0xb8,0x4a,0xa6,0x1f,0xf0,0x82,0x39],
-        [0x3b,0x62,0xa9,0xba,0x62,0x58,0xf5,0x61,0x0f,0x83,0xe2,0x64,0xf3,0x14,0x97,0xb4],
-        [0x26,0x44,0x99,0x06,0x0a,0xd9,0xba,0xab,0xc4,0x7f,0x8b,0x02,0xbb,0x6d,0x71,0xed],
-        [0x00,0x11,0x0d,0xc3,0x78,0x14,0x69,0x56,0xc9,0x54,0x47,0xd3,0xf3,0xd0,0xfb,0xba],
-        [0x01,0x51,0xc5,0x68,0x38,0x6b,0x66,0x77,0xa2,0xb4,0xdc,0x6f,0x81,0xe5,0xdc,0x18],
-        [0xd6,0x26,0xb2,0x66,0x90,0x5e,0xf3,0x58,0x82,0x63,0x4d,0xf6,0x85,0x32,0xc1,0x25],
-        [0x98,0x69,0xe2,0x47,0xe9,0xc0,0x8b,0x10,0xd0,0x29,0x93,0x4f,0xc4,0xb9,0x52,0xf7],
-        [0x31,0xfc,0xef,0xac,0x66,0xd7,0xde,0x9c,0x7e,0xc7,0x48,0x5f,0xe4,0x49,0x49,0x02],
-        [0x54,0x93,0xe9,0x99,0x33,0xb0,0xa8,0x11,0x7e,0x08,0xec,0x0f,0x97,0xcf,0xc3,0xd9],
-        [0x6e,0xe2,0xa4,0xca,0x67,0xb0,0x54,0xbb,0xfd,0x33,0x15,0xbf,0x85,0x23,0x05,0x77],
-        [0x47,0x3d,0x06,0xe8,0x73,0x8d,0xb8,0x98,0x54,0xc0,0x66,0xc4,0x7a,0xe4,0x77,0x40],
-        [0xa4,0x26,0xe5,0xe4,0x23,0xbf,0x48,0x85,0x29,0x4d,0xa4,0x81,0xfe,0xae,0xf7,0x23],
-        [0x78,0x01,0x77,0x31,0xcf,0x65,0xfa,0xb0,0x74,0xd5,0x20,0x89,0x52,0x51,0x2e,0xb1],
-        [0x9e,0x25,0xfc,0x83,0x3f,0x22,0x90,0x73,0x3e,0x93,0x44,0xa5,0xe8,0x38,0x39,0xeb],
-        [0x56,0x8e,0x49,0x5a,0xbe,0x52,0x5a,0x21,0x8a,0x22,0x14,0xcd,0x3e,0x07,0x1d,0x12],
-        [0x4a,0x29,0xb5,0x45,0x52,0xd1,0x6b,0x9a,0x46,0x9c,0x10,0x52,0x8e,0xff,0x0a,0xae],
-        [0xc9,0xd1,0x84,0xdd,0xd5,0xa9,0xf5,0xe0,0xcf,0x8c,0xe2,0x9a,0x9a,0xbf,0x69,0x1c],
-        [0x2d,0xb4,0x79,0xae,0x78,0xbd,0x50,0xd8,0x88,0x2a,0x8a,0x17,0x8a,0x61,0x32,0xad],
-        [0x8e,0xce,0x5f,0x04,0x2d,0x5e,0x44,0x7b,0x50,0x51,0xb9,0xea,0xcb,0x8d,0x8f,0x6f],
-        [0x9c,0x0b,0x53,0xb4,0xb3,0xc3,0x07,0xe8,0x7e,0xae,0xe0,0x86,0x78,0x14,0x1f,0x66],
-        [0xab,0xf2,0x48,0xaf,0x69,0xa6,0xea,0xe4,0xbf,0xd3,0xeb,0x2f,0x12,0x9e,0xeb,0x94],
-        [0x06,0x64,0xda,0x16,0x68,0x57,0x4b,0x88,0xb9,0x35,0xf3,0x02,0x73,0x58,0xae,0xf4],
-        [0xaa,0x4b,0x9d,0xc4,0xbf,0x33,0x7d,0xe9,0x0c,0xd4,0xfd,0x3c,0x46,0x7c,0x6a,0xb7],
-        [0xea,0x5c,0x7f,0x47,0x1f,0xaf,0x6b,0xde,0x2b,0x1a,0xd7,0xd4,0x68,0x6d,0x22,0x87],
-        [0x29,0x39,0xb0,0x18,0x32,0x23,0xfa,0xfc,0x17,0x23,0xde,0x4f,0x52,0xc4,0x3d,0x35],
-        [0x7c,0x39,0x56,0xca,0x5e,0xea,0xfc,0x3e,0x36,0x3e,0x9d,0x55,0x65,0x46,0xeb,0x68],
-        [0x77,0xc6,0x07,0x71,0x46,0xf0,0x1c,0x32,0xb6,0xb6,0x9d,0x5f,0x4e,0xa9,0xff,0xcf],
-        [0x37,0xa6,0x98,0x6c,0xb8,0x84,0x7e,0xdf,0x09,0x25,0xf0,0xf1,0x30,0x9b,0x54,0xde],
-        [0xa7,0x05,0xf0,0xe6,0x9d,0xa9,0xa8,0xf9,0x07,0x24,0x1a,0x2e,0x92,0x3c,0x8c,0xc8],
-        [0x3d,0xc4,0x7d,0x1f,0x29,0xc4,0x48,0x46,0x1e,0x9e,0x76,0xed,0x90,0x4f,0x67,0x11],
-        [0x0d,0x62,0xbf,0x01,0xe6,0xfc,0x0e,0x1a,0x0d,0x3c,0x47,0x51,0xc5,0xd3,0x69,0x2b],
-        [0x8c,0x03,0x46,0x8b,0xca,0x7c,0x66,0x9e,0xe4,0xfd,0x5e,0x08,0x4b,0xbe,0xe7,0xb5],
-        [0x52,0x8a,0x5b,0xb9,0x3b,0xaf,0x2c,0x9c,0x44,0x73,0xcc,0xe5,0xd0,0xd2,0x2b,0xd9],
-        [0xdf,0x6a,0x30,0x1e,0x95,0xc9,0x5d,0xad,0x97,0xae,0x0c,0xc8,0xc6,0x91,0x3b,0xd8],
-        [0x80,0x11,0x89,0x90,0x2c,0x85,0x7f,0x39,0xe7,0x35,0x91,0x28,0x5e,0x70,0xb6,0xdb],
-        [0xe6,0x17,0x34,0x6a,0xc9,0xc2,0x31,0xbb,0x36,0x50,0xae,0x34,0xcc,0xca,0x0c,0x5b],
-        [0x27,0xd9,0x34,0x37,0xef,0xb7,0x21,0xaa,0x40,0x18,0x21,0xdc,0xec,0x5a,0xdf,0x89],
-        [0x89,0x23,0x7d,0x9d,0xed,0x9c,0x5e,0x78,0xd8,0xb1,0xc9,0xb1,0x66,0xcc,0x73,0x42],
-        [0x4a,0x6d,0x80,0x91,0xbf,0x5e,0x7d,0x65,0x11,0x89,0xfa,0x94,0xa2,0x50,0xb1,0x4c],
-        [0x0e,0x33,0xf9,0x60,0x55,0xe7,0xae,0x89,0x3f,0xfc,0x0e,0x3d,0xcf,0x49,0x29,0x02],
-        [0xe6,0x1c,0x43,0x2b,0x72,0x0b,0x19,0xd1,0x8e,0xc8,0xd8,0x4b,0xdc,0x63,0x15,0x1b],
-        [0xf7,0xe5,0xae,0xf5,0x49,0xf7,0x82,0xcf,0x37,0x90,0x55,0xa6,0x08,0x26,0x9b,0x16],
-        [0x43,0x8d,0x03,0x0f,0xd0,0xb7,0xa5,0x4f,0xa8,0x37,0xf2,0xad,0x20,0x1a,0x64,0x03],
-        [0xa5,0x90,0xd3,0xee,0x4f,0xbf,0x04,0xe3,0x24,0x7e,0x0d,0x27,0xf2,0x86,0x42,0x3f],
-        [0x5f,0xe2,0xc1,0xa1,0x72,0xfe,0x93,0xc4,0xb1,0x5c,0xd3,0x7c,0xae,0xf9,0xf5,0x38],
-        [0x2c,0x97,0x32,0x5c,0xbd,0x06,0xb3,0x6e,0xb2,0x13,0x3d,0xd0,0x8b,0x3a,0x01,0x7c],
-        [0x92,0xc8,0x14,0x22,0x7a,0x6b,0xca,0x94,0x9f,0xf0,0x65,0x9f,0x00,0x2a,0xd3,0x9e],
-        [0xdc,0xe8,0x50,0x11,0x0b,0xd8,0x32,0x8c,0xfb,0xd5,0x08,0x41,0xd6,0x91,0x1d,0x87],
-        [0x67,0xf1,0x49,0x84,0xc7,0xda,0x79,0x12,0x48,0xe3,0x2b,0xb5,0x92,0x25,0x83,0xda],
-        [0x19,0x38,0xf2,0xcf,0x72,0xd5,0x4e,0xe9,0x7e,0x94,0x16,0x6f,0xa9,0x1d,0x2a,0x36],
-        [0x74,0x48,0x1e,0x96,0x46,0xed,0x49,0xfe,0x0f,0x62,0x24,0x30,0x16,0x04,0x69,0x8e],
-        [0x57,0xfc,0xa5,0xde,0x98,0xa9,0xd6,0xd8,0x00,0x64,0x38,0xd0,0x58,0x3d,0x8a,0x1d],
-        [0x9f,0xec,0xde,0x1c,0xef,0xdc,0x1c,0xbe,0xd4,0x76,0x36,0x74,0xd9,0x57,0x53,0x59],
-        [0xe3,0x04,0x0c,0x00,0xeb,0x28,0xf1,0x53,0x66,0xca,0x73,0xcb,0xd8,0x72,0xe7,0x40],
-        [0x76,0x97,0x00,0x9a,0x6a,0x83,0x1d,0xfe,0xcc,0xa9,0x1c,0x59,0x93,0x67,0x0f,0x7a],
-        [0x58,0x53,0x54,0x23,0x21,0xf5,0x67,0xa0,0x05,0xd5,0x47,0xa4,0xf0,0x47,0x59,0xbd],
-        [0x51,0x50,0xd1,0x77,0x2f,0x50,0x83,0x4a,0x50,0x3e,0x06,0x9a,0x97,0x3f,0xbd,0x7c],
-    ];
-
-    // Test vector from reference implementation
-    #[test]
-    fn test_siphash_2_4_test_vector() {
-        let k0 = 0x_07_06_05_04_03_02_01_00;
-        let k1 = 0x_0f_0e_0d_0c_0b_0a_09_08;
-
-        let mut input: Vec<u8> = Vec::new();
-
-        for i in 0 .. 64 {
-            let out = hash_with(SipHasher128::new_with_keys(k0, k1),
-                                &Bytes(&input[..]));
-            let expected = (
-                ((TEST_VECTOR[i][0] as u64) <<  0) |
-                ((TEST_VECTOR[i][1] as u64) <<  8) |
-                ((TEST_VECTOR[i][2] as u64) << 16) |
-                ((TEST_VECTOR[i][3] as u64) << 24) |
-                ((TEST_VECTOR[i][4] as u64) << 32) |
-                ((TEST_VECTOR[i][5] as u64) << 40) |
-                ((TEST_VECTOR[i][6] as u64) << 48) |
-                ((TEST_VECTOR[i][7] as u64) << 56),
-
-                ((TEST_VECTOR[i][8] as u64) <<  0) |
-                ((TEST_VECTOR[i][9] as u64) <<  8) |
-                ((TEST_VECTOR[i][10] as u64) << 16) |
-                ((TEST_VECTOR[i][11] as u64) << 24) |
-                ((TEST_VECTOR[i][12] as u64) << 32) |
-                ((TEST_VECTOR[i][13] as u64) << 40) |
-                ((TEST_VECTOR[i][14] as u64) << 48) |
-                ((TEST_VECTOR[i][15] as u64) << 56),
-            );
-
-            assert_eq!(out, expected);
-            input.push(i as u8);
-        }
-    }
-
-    #[test] #[cfg(target_arch = "arm")]
-    fn test_hash_usize() {
-        let val = 0xdeadbeef_deadbeef_u64;
-        assert!(hash(&(val as u64)) != hash(&(val as usize)));
-        assert_eq!(hash(&(val as u32)), hash(&(val as usize)));
-    }
-    #[test] #[cfg(target_arch = "x86_64")]
-    fn test_hash_usize() {
-        let val = 0xdeadbeef_deadbeef_u64;
-        assert_eq!(hash(&(val as u64)), hash(&(val as usize)));
-        assert!(hash(&(val as u32)) != hash(&(val as usize)));
-    }
-    #[test] #[cfg(target_arch = "x86")]
-    fn test_hash_usize() {
-        let val = 0xdeadbeef_deadbeef_u64;
-        assert!(hash(&(val as u64)) != hash(&(val as usize)));
-        assert_eq!(hash(&(val as u32)), hash(&(val as usize)));
-    }
-
-    #[test]
-    fn test_hash_idempotent() {
-        let val64 = 0xdeadbeef_deadbeef_u64;
-        assert_eq!(hash(&val64), hash(&val64));
-        let val32 = 0xdeadbeef_u32;
-        assert_eq!(hash(&val32), hash(&val32));
-    }
-
-    #[test]
-    fn test_hash_no_bytes_dropped_64() {
-        let val = 0xdeadbeef_deadbeef_u64;
-
-        assert!(hash(&val) != hash(&zero_byte(val, 0)));
-        assert!(hash(&val) != hash(&zero_byte(val, 1)));
-        assert!(hash(&val) != hash(&zero_byte(val, 2)));
-        assert!(hash(&val) != hash(&zero_byte(val, 3)));
-        assert!(hash(&val) != hash(&zero_byte(val, 4)));
-        assert!(hash(&val) != hash(&zero_byte(val, 5)));
-        assert!(hash(&val) != hash(&zero_byte(val, 6)));
-        assert!(hash(&val) != hash(&zero_byte(val, 7)));
-
-        fn zero_byte(val: u64, byte: usize) -> u64 {
-            assert!(byte < 8);
-            val & !(0xff << (byte * 8))
-        }
-    }
-
-    #[test]
-    fn test_hash_no_bytes_dropped_32() {
-        let val = 0xdeadbeef_u32;
-
-        assert!(hash(&val) != hash(&zero_byte(val, 0)));
-        assert!(hash(&val) != hash(&zero_byte(val, 1)));
-        assert!(hash(&val) != hash(&zero_byte(val, 2)));
-        assert!(hash(&val) != hash(&zero_byte(val, 3)));
-
-        fn zero_byte(val: u32, byte: usize) -> u32 {
-            assert!(byte < 4);
-            val & !(0xff << (byte * 8))
-        }
-    }
-
-    #[test]
-    fn test_hash_no_concat_alias() {
-        let s = ("aa", "bb");
-        let t = ("aabb", "");
-        let u = ("a", "abb");
-
-        assert!(s != t && t != u);
-        assert!(hash(&s) != hash(&t) && hash(&s) != hash(&u));
-
-        let u = [1, 0, 0, 0];
-        let v = (&u[..1], &u[1..3], &u[3..]);
-        let w = (&u[..], &u[4..4], &u[4..4]);
-
-        assert!(v != w);
-        assert!(hash(&v) != hash(&w));
-    }
-
-    #[test]
-    fn test_write_short_works() {
-        let test_usize = 0xd0c0b0a0usize;
-        let mut h1 = SipHasher128::new_with_keys(0, 0);
-        h1.write_usize(test_usize);
-        h1.write(b"bytes");
-        h1.write(b"string");
-        h1.write_u8(0xFFu8);
-        h1.write_u8(0x01u8);
-        let mut h2 = SipHasher128::new_with_keys(0, 0);
-        h2.write(unsafe {
-            slice::from_raw_parts(&test_usize as *const _ as *const u8,
-                                  mem::size_of::<usize>())
-        });
-        h2.write(b"bytes");
-        h2.write(b"string");
-        h2.write(&[0xFFu8, 0x01u8]);
-        assert_eq!(h1.finish128(), h2.finish128());
-    }
-
-}
diff --git a/src/librustc_data_structures/sip128/tests.rs b/src/librustc_data_structures/sip128/tests.rs
new file mode 100644
index 00000000000..90cc54448b4
--- /dev/null
+++ b/src/librustc_data_structures/sip128/tests.rs
@@ -0,0 +1,226 @@
+use super::*;
+
+use std::hash::{Hash, Hasher};
+use std::{slice, mem};
+
+// Hash just the bytes of the slice, without length prefix
+struct Bytes<'a>(&'a [u8]);
+
+impl<'a> Hash for Bytes<'a> {
+    #[allow(unused_must_use)]
+    fn hash<H: Hasher>(&self, state: &mut H) {
+        for byte in self.0 {
+            state.write_u8(*byte);
+        }
+    }
+}
+
+fn hash_with<T: Hash>(mut st: SipHasher128, x: &T) -> (u64, u64) {
+    x.hash(&mut st);
+    st.finish128()
+}
+
+fn hash<T: Hash>(x: &T) -> (u64, u64) {
+    hash_with(SipHasher128::new_with_keys(0, 0), x)
+}
+
+const TEST_VECTOR : [[u8; 16]; 64] = [
+    [0xa3,0x81,0x7f,0x04,0xba,0x25,0xa8,0xe6,0x6d,0xf6,0x72,0x14,0xc7,0x55,0x02,0x93],
+    [0xda,0x87,0xc1,0xd8,0x6b,0x99,0xaf,0x44,0x34,0x76,0x59,0x11,0x9b,0x22,0xfc,0x45],
+    [0x81,0x77,0x22,0x8d,0xa4,0xa4,0x5d,0xc7,0xfc,0xa3,0x8b,0xde,0xf6,0x0a,0xff,0xe4],
+    [0x9c,0x70,0xb6,0x0c,0x52,0x67,0xa9,0x4e,0x5f,0x33,0xb6,0xb0,0x29,0x85,0xed,0x51],
+    [0xf8,0x81,0x64,0xc1,0x2d,0x9c,0x8f,0xaf,0x7d,0x0f,0x6e,0x7c,0x7b,0xcd,0x55,0x79],
+    [0x13,0x68,0x87,0x59,0x80,0x77,0x6f,0x88,0x54,0x52,0x7a,0x07,0x69,0x0e,0x96,0x27],
+    [0x14,0xee,0xca,0x33,0x8b,0x20,0x86,0x13,0x48,0x5e,0xa0,0x30,0x8f,0xd7,0xa1,0x5e],
+    [0xa1,0xf1,0xeb,0xbe,0xd8,0xdb,0xc1,0x53,0xc0,0xb8,0x4a,0xa6,0x1f,0xf0,0x82,0x39],
+    [0x3b,0x62,0xa9,0xba,0x62,0x58,0xf5,0x61,0x0f,0x83,0xe2,0x64,0xf3,0x14,0x97,0xb4],
+    [0x26,0x44,0x99,0x06,0x0a,0xd9,0xba,0xab,0xc4,0x7f,0x8b,0x02,0xbb,0x6d,0x71,0xed],
+    [0x00,0x11,0x0d,0xc3,0x78,0x14,0x69,0x56,0xc9,0x54,0x47,0xd3,0xf3,0xd0,0xfb,0xba],
+    [0x01,0x51,0xc5,0x68,0x38,0x6b,0x66,0x77,0xa2,0xb4,0xdc,0x6f,0x81,0xe5,0xdc,0x18],
+    [0xd6,0x26,0xb2,0x66,0x90,0x5e,0xf3,0x58,0x82,0x63,0x4d,0xf6,0x85,0x32,0xc1,0x25],
+    [0x98,0x69,0xe2,0x47,0xe9,0xc0,0x8b,0x10,0xd0,0x29,0x93,0x4f,0xc4,0xb9,0x52,0xf7],
+    [0x31,0xfc,0xef,0xac,0x66,0xd7,0xde,0x9c,0x7e,0xc7,0x48,0x5f,0xe4,0x49,0x49,0x02],
+    [0x54,0x93,0xe9,0x99,0x33,0xb0,0xa8,0x11,0x7e,0x08,0xec,0x0f,0x97,0xcf,0xc3,0xd9],
+    [0x6e,0xe2,0xa4,0xca,0x67,0xb0,0x54,0xbb,0xfd,0x33,0x15,0xbf,0x85,0x23,0x05,0x77],
+    [0x47,0x3d,0x06,0xe8,0x73,0x8d,0xb8,0x98,0x54,0xc0,0x66,0xc4,0x7a,0xe4,0x77,0x40],
+    [0xa4,0x26,0xe5,0xe4,0x23,0xbf,0x48,0x85,0x29,0x4d,0xa4,0x81,0xfe,0xae,0xf7,0x23],
+    [0x78,0x01,0x77,0x31,0xcf,0x65,0xfa,0xb0,0x74,0xd5,0x20,0x89,0x52,0x51,0x2e,0xb1],
+    [0x9e,0x25,0xfc,0x83,0x3f,0x22,0x90,0x73,0x3e,0x93,0x44,0xa5,0xe8,0x38,0x39,0xeb],
+    [0x56,0x8e,0x49,0x5a,0xbe,0x52,0x5a,0x21,0x8a,0x22,0x14,0xcd,0x3e,0x07,0x1d,0x12],
+    [0x4a,0x29,0xb5,0x45,0x52,0xd1,0x6b,0x9a,0x46,0x9c,0x10,0x52,0x8e,0xff,0x0a,0xae],
+    [0xc9,0xd1,0x84,0xdd,0xd5,0xa9,0xf5,0xe0,0xcf,0x8c,0xe2,0x9a,0x9a,0xbf,0x69,0x1c],
+    [0x2d,0xb4,0x79,0xae,0x78,0xbd,0x50,0xd8,0x88,0x2a,0x8a,0x17,0x8a,0x61,0x32,0xad],
+    [0x8e,0xce,0x5f,0x04,0x2d,0x5e,0x44,0x7b,0x50,0x51,0xb9,0xea,0xcb,0x8d,0x8f,0x6f],
+    [0x9c,0x0b,0x53,0xb4,0xb3,0xc3,0x07,0xe8,0x7e,0xae,0xe0,0x86,0x78,0x14,0x1f,0x66],
+    [0xab,0xf2,0x48,0xaf,0x69,0xa6,0xea,0xe4,0xbf,0xd3,0xeb,0x2f,0x12,0x9e,0xeb,0x94],
+    [0x06,0x64,0xda,0x16,0x68,0x57,0x4b,0x88,0xb9,0x35,0xf3,0x02,0x73,0x58,0xae,0xf4],
+    [0xaa,0x4b,0x9d,0xc4,0xbf,0x33,0x7d,0xe9,0x0c,0xd4,0xfd,0x3c,0x46,0x7c,0x6a,0xb7],
+    [0xea,0x5c,0x7f,0x47,0x1f,0xaf,0x6b,0xde,0x2b,0x1a,0xd7,0xd4,0x68,0x6d,0x22,0x87],
+    [0x29,0x39,0xb0,0x18,0x32,0x23,0xfa,0xfc,0x17,0x23,0xde,0x4f,0x52,0xc4,0x3d,0x35],
+    [0x7c,0x39,0x56,0xca,0x5e,0xea,0xfc,0x3e,0x36,0x3e,0x9d,0x55,0x65,0x46,0xeb,0x68],
+    [0x77,0xc6,0x07,0x71,0x46,0xf0,0x1c,0x32,0xb6,0xb6,0x9d,0x5f,0x4e,0xa9,0xff,0xcf],
+    [0x37,0xa6,0x98,0x6c,0xb8,0x84,0x7e,0xdf,0x09,0x25,0xf0,0xf1,0x30,0x9b,0x54,0xde],
+    [0xa7,0x05,0xf0,0xe6,0x9d,0xa9,0xa8,0xf9,0x07,0x24,0x1a,0x2e,0x92,0x3c,0x8c,0xc8],
+    [0x3d,0xc4,0x7d,0x1f,0x29,0xc4,0x48,0x46,0x1e,0x9e,0x76,0xed,0x90,0x4f,0x67,0x11],
+    [0x0d,0x62,0xbf,0x01,0xe6,0xfc,0x0e,0x1a,0x0d,0x3c,0x47,0x51,0xc5,0xd3,0x69,0x2b],
+    [0x8c,0x03,0x46,0x8b,0xca,0x7c,0x66,0x9e,0xe4,0xfd,0x5e,0x08,0x4b,0xbe,0xe7,0xb5],
+    [0x52,0x8a,0x5b,0xb9,0x3b,0xaf,0x2c,0x9c,0x44,0x73,0xcc,0xe5,0xd0,0xd2,0x2b,0xd9],
+    [0xdf,0x6a,0x30,0x1e,0x95,0xc9,0x5d,0xad,0x97,0xae,0x0c,0xc8,0xc6,0x91,0x3b,0xd8],
+    [0x80,0x11,0x89,0x90,0x2c,0x85,0x7f,0x39,0xe7,0x35,0x91,0x28,0x5e,0x70,0xb6,0xdb],
+    [0xe6,0x17,0x34,0x6a,0xc9,0xc2,0x31,0xbb,0x36,0x50,0xae,0x34,0xcc,0xca,0x0c,0x5b],
+    [0x27,0xd9,0x34,0x37,0xef,0xb7,0x21,0xaa,0x40,0x18,0x21,0xdc,0xec,0x5a,0xdf,0x89],
+    [0x89,0x23,0x7d,0x9d,0xed,0x9c,0x5e,0x78,0xd8,0xb1,0xc9,0xb1,0x66,0xcc,0x73,0x42],
+    [0x4a,0x6d,0x80,0x91,0xbf,0x5e,0x7d,0x65,0x11,0x89,0xfa,0x94,0xa2,0x50,0xb1,0x4c],
+    [0x0e,0x33,0xf9,0x60,0x55,0xe7,0xae,0x89,0x3f,0xfc,0x0e,0x3d,0xcf,0x49,0x29,0x02],
+    [0xe6,0x1c,0x43,0x2b,0x72,0x0b,0x19,0xd1,0x8e,0xc8,0xd8,0x4b,0xdc,0x63,0x15,0x1b],
+    [0xf7,0xe5,0xae,0xf5,0x49,0xf7,0x82,0xcf,0x37,0x90,0x55,0xa6,0x08,0x26,0x9b,0x16],
+    [0x43,0x8d,0x03,0x0f,0xd0,0xb7,0xa5,0x4f,0xa8,0x37,0xf2,0xad,0x20,0x1a,0x64,0x03],
+    [0xa5,0x90,0xd3,0xee,0x4f,0xbf,0x04,0xe3,0x24,0x7e,0x0d,0x27,0xf2,0x86,0x42,0x3f],
+    [0x5f,0xe2,0xc1,0xa1,0x72,0xfe,0x93,0xc4,0xb1,0x5c,0xd3,0x7c,0xae,0xf9,0xf5,0x38],
+    [0x2c,0x97,0x32,0x5c,0xbd,0x06,0xb3,0x6e,0xb2,0x13,0x3d,0xd0,0x8b,0x3a,0x01,0x7c],
+    [0x92,0xc8,0x14,0x22,0x7a,0x6b,0xca,0x94,0x9f,0xf0,0x65,0x9f,0x00,0x2a,0xd3,0x9e],
+    [0xdc,0xe8,0x50,0x11,0x0b,0xd8,0x32,0x8c,0xfb,0xd5,0x08,0x41,0xd6,0x91,0x1d,0x87],
+    [0x67,0xf1,0x49,0x84,0xc7,0xda,0x79,0x12,0x48,0xe3,0x2b,0xb5,0x92,0x25,0x83,0xda],
+    [0x19,0x38,0xf2,0xcf,0x72,0xd5,0x4e,0xe9,0x7e,0x94,0x16,0x6f,0xa9,0x1d,0x2a,0x36],
+    [0x74,0x48,0x1e,0x96,0x46,0xed,0x49,0xfe,0x0f,0x62,0x24,0x30,0x16,0x04,0x69,0x8e],
+    [0x57,0xfc,0xa5,0xde,0x98,0xa9,0xd6,0xd8,0x00,0x64,0x38,0xd0,0x58,0x3d,0x8a,0x1d],
+    [0x9f,0xec,0xde,0x1c,0xef,0xdc,0x1c,0xbe,0xd4,0x76,0x36,0x74,0xd9,0x57,0x53,0x59],
+    [0xe3,0x04,0x0c,0x00,0xeb,0x28,0xf1,0x53,0x66,0xca,0x73,0xcb,0xd8,0x72,0xe7,0x40],
+    [0x76,0x97,0x00,0x9a,0x6a,0x83,0x1d,0xfe,0xcc,0xa9,0x1c,0x59,0x93,0x67,0x0f,0x7a],
+    [0x58,0x53,0x54,0x23,0x21,0xf5,0x67,0xa0,0x05,0xd5,0x47,0xa4,0xf0,0x47,0x59,0xbd],
+    [0x51,0x50,0xd1,0x77,0x2f,0x50,0x83,0x4a,0x50,0x3e,0x06,0x9a,0x97,0x3f,0xbd,0x7c],
+];
+
+// Test vector from reference implementation
+#[test]
+fn test_siphash_2_4_test_vector() {
+    let k0 = 0x_07_06_05_04_03_02_01_00;
+    let k1 = 0x_0f_0e_0d_0c_0b_0a_09_08;
+
+    let mut input: Vec<u8> = Vec::new();
+
+    for i in 0 .. 64 {
+        let out = hash_with(SipHasher128::new_with_keys(k0, k1),
+                            &Bytes(&input[..]));
+        let expected = (
+            ((TEST_VECTOR[i][0] as u64) <<  0) |
+            ((TEST_VECTOR[i][1] as u64) <<  8) |
+            ((TEST_VECTOR[i][2] as u64) << 16) |
+            ((TEST_VECTOR[i][3] as u64) << 24) |
+            ((TEST_VECTOR[i][4] as u64) << 32) |
+            ((TEST_VECTOR[i][5] as u64) << 40) |
+            ((TEST_VECTOR[i][6] as u64) << 48) |
+            ((TEST_VECTOR[i][7] as u64) << 56),
+
+            ((TEST_VECTOR[i][8] as u64) <<  0) |
+            ((TEST_VECTOR[i][9] as u64) <<  8) |
+            ((TEST_VECTOR[i][10] as u64) << 16) |
+            ((TEST_VECTOR[i][11] as u64) << 24) |
+            ((TEST_VECTOR[i][12] as u64) << 32) |
+            ((TEST_VECTOR[i][13] as u64) << 40) |
+            ((TEST_VECTOR[i][14] as u64) << 48) |
+            ((TEST_VECTOR[i][15] as u64) << 56),
+        );
+
+        assert_eq!(out, expected);
+        input.push(i as u8);
+    }
+}
+
+#[test] #[cfg(target_arch = "arm")]
+fn test_hash_usize() {
+    let val = 0xdeadbeef_deadbeef_u64;
+    assert!(hash(&(val as u64)) != hash(&(val as usize)));
+    assert_eq!(hash(&(val as u32)), hash(&(val as usize)));
+}
+#[test] #[cfg(target_arch = "x86_64")]
+fn test_hash_usize() {
+    let val = 0xdeadbeef_deadbeef_u64;
+    assert_eq!(hash(&(val as u64)), hash(&(val as usize)));
+    assert!(hash(&(val as u32)) != hash(&(val as usize)));
+}
+#[test] #[cfg(target_arch = "x86")]
+fn test_hash_usize() {
+    let val = 0xdeadbeef_deadbeef_u64;
+    assert!(hash(&(val as u64)) != hash(&(val as usize)));
+    assert_eq!(hash(&(val as u32)), hash(&(val as usize)));
+}
+
+#[test]
+fn test_hash_idempotent() {
+    let val64 = 0xdeadbeef_deadbeef_u64;
+    assert_eq!(hash(&val64), hash(&val64));
+    let val32 = 0xdeadbeef_u32;
+    assert_eq!(hash(&val32), hash(&val32));
+}
+
+#[test]
+fn test_hash_no_bytes_dropped_64() {
+    let val = 0xdeadbeef_deadbeef_u64;
+
+    assert!(hash(&val) != hash(&zero_byte(val, 0)));
+    assert!(hash(&val) != hash(&zero_byte(val, 1)));
+    assert!(hash(&val) != hash(&zero_byte(val, 2)));
+    assert!(hash(&val) != hash(&zero_byte(val, 3)));
+    assert!(hash(&val) != hash(&zero_byte(val, 4)));
+    assert!(hash(&val) != hash(&zero_byte(val, 5)));
+    assert!(hash(&val) != hash(&zero_byte(val, 6)));
+    assert!(hash(&val) != hash(&zero_byte(val, 7)));
+
+    fn zero_byte(val: u64, byte: usize) -> u64 {
+        assert!(byte < 8);
+        val & !(0xff << (byte * 8))
+    }
+}
+
+#[test]
+fn test_hash_no_bytes_dropped_32() {
+    let val = 0xdeadbeef_u32;
+
+    assert!(hash(&val) != hash(&zero_byte(val, 0)));
+    assert!(hash(&val) != hash(&zero_byte(val, 1)));
+    assert!(hash(&val) != hash(&zero_byte(val, 2)));
+    assert!(hash(&val) != hash(&zero_byte(val, 3)));
+
+    fn zero_byte(val: u32, byte: usize) -> u32 {
+        assert!(byte < 4);
+        val & !(0xff << (byte * 8))
+    }
+}
+
+#[test]
+fn test_hash_no_concat_alias() {
+    let s = ("aa", "bb");
+    let t = ("aabb", "");
+    let u = ("a", "abb");
+
+    assert!(s != t && t != u);
+    assert!(hash(&s) != hash(&t) && hash(&s) != hash(&u));
+
+    let u = [1, 0, 0, 0];
+    let v = (&u[..1], &u[1..3], &u[3..]);
+    let w = (&u[..], &u[4..4], &u[4..4]);
+
+    assert!(v != w);
+    assert!(hash(&v) != hash(&w));
+}
+
+#[test]
+fn test_write_short_works() {
+    let test_usize = 0xd0c0b0a0usize;
+    let mut h1 = SipHasher128::new_with_keys(0, 0);
+    h1.write_usize(test_usize);
+    h1.write(b"bytes");
+    h1.write(b"string");
+    h1.write_u8(0xFFu8);
+    h1.write_u8(0x01u8);
+    let mut h2 = SipHasher128::new_with_keys(0, 0);
+    h2.write(unsafe {
+        slice::from_raw_parts(&test_usize as *const _ as *const u8,
+                                mem::size_of::<usize>())
+    });
+    h2.write(b"bytes");
+    h2.write(b"string");
+    h2.write(&[0xFFu8, 0x01u8]);
+    assert_eq!(h1.finish128(), h2.finish128());
+}
diff --git a/src/librustc_data_structures/small_c_str.rs b/src/librustc_data_structures/small_c_str.rs
index bde7911267f..9d90b9052d1 100644
--- a/src/librustc_data_structures/small_c_str.rs
+++ b/src/librustc_data_structures/small_c_str.rs
@@ -3,6 +3,9 @@ use std::ops::Deref;
 
 use smallvec::SmallVec;
 
+#[cfg(test)]
+mod tests;
+
 const SIZE: usize = 36;
 
 /// Like SmallVec but for C strings.
@@ -66,47 +69,3 @@ impl Deref for SmallCStr {
         self.as_c_str()
     }
 }
-
-#[test]
-fn short() {
-    const TEXT: &str = "abcd";
-    let reference = ffi::CString::new(TEXT.to_string()).unwrap();
-
-    let scs = SmallCStr::new(TEXT);
-
-    assert_eq!(scs.len_with_nul(), TEXT.len() + 1);
-    assert_eq!(scs.as_c_str(), reference.as_c_str());
-    assert!(!scs.spilled());
-}
-
-#[test]
-fn empty() {
-    const TEXT: &str = "";
-    let reference = ffi::CString::new(TEXT.to_string()).unwrap();
-
-    let scs = SmallCStr::new(TEXT);
-
-    assert_eq!(scs.len_with_nul(), TEXT.len() + 1);
-    assert_eq!(scs.as_c_str(), reference.as_c_str());
-    assert!(!scs.spilled());
-}
-
-#[test]
-fn long() {
-    const TEXT: &str = "01234567890123456789012345678901234567890123456789\
-                        01234567890123456789012345678901234567890123456789\
-                        01234567890123456789012345678901234567890123456789";
-    let reference = ffi::CString::new(TEXT.to_string()).unwrap();
-
-    let scs = SmallCStr::new(TEXT);
-
-    assert_eq!(scs.len_with_nul(), TEXT.len() + 1);
-    assert_eq!(scs.as_c_str(), reference.as_c_str());
-    assert!(scs.spilled());
-}
-
-#[test]
-#[should_panic]
-fn internal_nul() {
-    let _ = SmallCStr::new("abcd\0def");
-}
diff --git a/src/librustc_data_structures/small_c_str/tests.rs b/src/librustc_data_structures/small_c_str/tests.rs
new file mode 100644
index 00000000000..47277604b2b
--- /dev/null
+++ b/src/librustc_data_structures/small_c_str/tests.rs
@@ -0,0 +1,45 @@
+use super::*;
+
+#[test]
+fn short() {
+    const TEXT: &str = "abcd";
+    let reference = ffi::CString::new(TEXT.to_string()).unwrap();
+
+    let scs = SmallCStr::new(TEXT);
+
+    assert_eq!(scs.len_with_nul(), TEXT.len() + 1);
+    assert_eq!(scs.as_c_str(), reference.as_c_str());
+    assert!(!scs.spilled());
+}
+
+#[test]
+fn empty() {
+    const TEXT: &str = "";
+    let reference = ffi::CString::new(TEXT.to_string()).unwrap();
+
+    let scs = SmallCStr::new(TEXT);
+
+    assert_eq!(scs.len_with_nul(), TEXT.len() + 1);
+    assert_eq!(scs.as_c_str(), reference.as_c_str());
+    assert!(!scs.spilled());
+}
+
+#[test]
+fn long() {
+    const TEXT: &str = "01234567890123456789012345678901234567890123456789\
+                        01234567890123456789012345678901234567890123456789\
+                        01234567890123456789012345678901234567890123456789";
+    let reference = ffi::CString::new(TEXT.to_string()).unwrap();
+
+    let scs = SmallCStr::new(TEXT);
+
+    assert_eq!(scs.len_with_nul(), TEXT.len() + 1);
+    assert_eq!(scs.as_c_str(), reference.as_c_str());
+    assert!(scs.spilled());
+}
+
+#[test]
+#[should_panic]
+fn internal_nul() {
+    let _ = SmallCStr::new("abcd\0def");
+}
diff --git a/src/librustc_data_structures/snapshot_map/mod.rs b/src/librustc_data_structures/snapshot_map/mod.rs
index 91d6e292370..ce0aa07cc28 100644
--- a/src/librustc_data_structures/snapshot_map/mod.rs
+++ b/src/librustc_data_structures/snapshot_map/mod.rs
@@ -4,7 +4,7 @@ use std::ops;
 use std::mem;
 
 #[cfg(test)]
-mod test;
+mod tests;
 
 pub struct SnapshotMap<K, V>
     where K: Hash + Clone + Eq
diff --git a/src/librustc_data_structures/snapshot_map/test.rs b/src/librustc_data_structures/snapshot_map/tests.rs
index 72ca53c2be9..72ca53c2be9 100644
--- a/src/librustc_data_structures/snapshot_map/test.rs
+++ b/src/librustc_data_structures/snapshot_map/tests.rs
diff --git a/src/librustc_data_structures/tiny_list.rs b/src/librustc_data_structures/tiny_list.rs
index 3d74516d9c3..1c0d9360f25 100644
--- a/src/librustc_data_structures/tiny_list.rs
+++ b/src/librustc_data_structures/tiny_list.rs
@@ -11,6 +11,9 @@
 //! If you expect to store more than 1 element in the common case, steer clear
 //! and use a `Vec<T>`, `Box<[T]>`, or a `SmallVec<T>`.
 
+#[cfg(test)]
+mod tests;
+
 #[derive(Clone, Hash, Debug, PartialEq)]
 pub struct TinyList<T: PartialEq> {
     head: Option<Element<T>>
@@ -118,139 +121,3 @@ impl<T: PartialEq> Element<T> {
         }
     }
 }
-
-#[cfg(test)]
-mod test {
-    use super::*;
-    extern crate test;
-    use test::Bencher;
-
-    #[test]
-    fn test_contains_and_insert() {
-        fn do_insert(i : u32) -> bool {
-            i % 2 == 0
-        }
-
-        let mut list = TinyList::new();
-
-        for i in 0 .. 10 {
-            for j in 0 .. i {
-                if do_insert(j) {
-                    assert!(list.contains(&j));
-                } else {
-                    assert!(!list.contains(&j));
-                }
-            }
-
-            assert!(!list.contains(&i));
-
-            if do_insert(i) {
-                list.insert(i);
-                assert!(list.contains(&i));
-            }
-        }
-    }
-
-    #[test]
-    fn test_remove_first() {
-        let mut list = TinyList::new();
-        list.insert(1);
-        list.insert(2);
-        list.insert(3);
-        list.insert(4);
-        assert_eq!(list.len(), 4);
-
-        assert!(list.remove(&4));
-        assert!(!list.contains(&4));
-
-        assert_eq!(list.len(), 3);
-        assert!(list.contains(&1));
-        assert!(list.contains(&2));
-        assert!(list.contains(&3));
-    }
-
-    #[test]
-    fn test_remove_last() {
-        let mut list = TinyList::new();
-        list.insert(1);
-        list.insert(2);
-        list.insert(3);
-        list.insert(4);
-        assert_eq!(list.len(), 4);
-
-        assert!(list.remove(&1));
-        assert!(!list.contains(&1));
-
-        assert_eq!(list.len(), 3);
-        assert!(list.contains(&2));
-        assert!(list.contains(&3));
-        assert!(list.contains(&4));
-    }
-
-    #[test]
-    fn test_remove_middle() {
-        let mut list = TinyList::new();
-        list.insert(1);
-        list.insert(2);
-        list.insert(3);
-        list.insert(4);
-        assert_eq!(list.len(), 4);
-
-        assert!(list.remove(&2));
-        assert!(!list.contains(&2));
-
-        assert_eq!(list.len(), 3);
-        assert!(list.contains(&1));
-        assert!(list.contains(&3));
-        assert!(list.contains(&4));
-    }
-
-    #[test]
-    fn test_remove_single() {
-        let mut list = TinyList::new();
-        list.insert(1);
-        assert_eq!(list.len(), 1);
-
-        assert!(list.remove(&1));
-        assert!(!list.contains(&1));
-
-        assert_eq!(list.len(), 0);
-    }
-
-    #[bench]
-    fn bench_insert_empty(b: &mut Bencher) {
-        b.iter(|| {
-            let mut list = TinyList::new();
-            list.insert(1);
-        })
-    }
-
-    #[bench]
-    fn bench_insert_one(b: &mut Bencher) {
-        b.iter(|| {
-            let mut list = TinyList::new_single(0);
-            list.insert(1);
-        })
-    }
-
-    #[bench]
-    fn bench_remove_empty(b: &mut Bencher) {
-        b.iter(|| {
-            TinyList::new().remove(&1)
-        });
-    }
-
-    #[bench]
-    fn bench_remove_unknown(b: &mut Bencher) {
-        b.iter(|| {
-            TinyList::new_single(0).remove(&1)
-        });
-    }
-
-    #[bench]
-    fn bench_remove_one(b: &mut Bencher) {
-        b.iter(|| {
-            TinyList::new_single(1).remove(&1)
-        });
-    }
-}
diff --git a/src/librustc_data_structures/tiny_list/tests.rs b/src/librustc_data_structures/tiny_list/tests.rs
new file mode 100644
index 00000000000..8374659e1e6
--- /dev/null
+++ b/src/librustc_data_structures/tiny_list/tests.rs
@@ -0,0 +1,133 @@
+use super::*;
+
+extern crate test;
+use test::Bencher;
+
+#[test]
+fn test_contains_and_insert() {
+    fn do_insert(i : u32) -> bool {
+        i % 2 == 0
+    }
+
+    let mut list = TinyList::new();
+
+    for i in 0 .. 10 {
+        for j in 0 .. i {
+            if do_insert(j) {
+                assert!(list.contains(&j));
+            } else {
+                assert!(!list.contains(&j));
+            }
+        }
+
+        assert!(!list.contains(&i));
+
+        if do_insert(i) {
+            list.insert(i);
+            assert!(list.contains(&i));
+        }
+    }
+}
+
+#[test]
+fn test_remove_first() {
+    let mut list = TinyList::new();
+    list.insert(1);
+    list.insert(2);
+    list.insert(3);
+    list.insert(4);
+    assert_eq!(list.len(), 4);
+
+    assert!(list.remove(&4));
+    assert!(!list.contains(&4));
+
+    assert_eq!(list.len(), 3);
+    assert!(list.contains(&1));
+    assert!(list.contains(&2));
+    assert!(list.contains(&3));
+}
+
+#[test]
+fn test_remove_last() {
+    let mut list = TinyList::new();
+    list.insert(1);
+    list.insert(2);
+    list.insert(3);
+    list.insert(4);
+    assert_eq!(list.len(), 4);
+
+    assert!(list.remove(&1));
+    assert!(!list.contains(&1));
+
+    assert_eq!(list.len(), 3);
+    assert!(list.contains(&2));
+    assert!(list.contains(&3));
+    assert!(list.contains(&4));
+}
+
+#[test]
+fn test_remove_middle() {
+    let mut list = TinyList::new();
+    list.insert(1);
+    list.insert(2);
+    list.insert(3);
+    list.insert(4);
+    assert_eq!(list.len(), 4);
+
+    assert!(list.remove(&2));
+    assert!(!list.contains(&2));
+
+    assert_eq!(list.len(), 3);
+    assert!(list.contains(&1));
+    assert!(list.contains(&3));
+    assert!(list.contains(&4));
+}
+
+#[test]
+fn test_remove_single() {
+    let mut list = TinyList::new();
+    list.insert(1);
+    assert_eq!(list.len(), 1);
+
+    assert!(list.remove(&1));
+    assert!(!list.contains(&1));
+
+    assert_eq!(list.len(), 0);
+}
+
+#[bench]
+fn bench_insert_empty(b: &mut Bencher) {
+    b.iter(|| {
+        let mut list = TinyList::new();
+        list.insert(1);
+    })
+}
+
+#[bench]
+fn bench_insert_one(b: &mut Bencher) {
+    b.iter(|| {
+        let mut list = TinyList::new_single(0);
+        list.insert(1);
+    })
+}
+
+#[bench]
+fn bench_remove_empty(b: &mut Bencher) {
+    b.iter(|| {
+        TinyList::new().remove(&1)
+    });
+}
+
+#[bench]
+fn bench_remove_unknown(b: &mut Bencher) {
+    b.iter(|| {
+        TinyList::new_single(0).remove(&1)
+    });
+}
+
+#[bench]
+fn bench_remove_one(b: &mut Bencher) {
+    b.iter(|| {
+        TinyList::new_single(1).remove(&1)
+    });
+}
diff --git a/src/librustc_data_structures/transitive_relation.rs b/src/librustc_data_structures/transitive_relation.rs
index d7cbd1e2e4b..ffc964ddb5a 100644
--- a/src/librustc_data_structures/transitive_relation.rs
+++ b/src/librustc_data_structures/transitive_relation.rs
@@ -7,6 +7,8 @@ use std::fmt::Debug;
 use std::hash::Hash;
 use std::mem;
 
+#[cfg(test)]
+mod tests;
 
 #[derive(Clone, Debug)]
 pub struct TransitiveRelation<T: Clone + Debug + Eq + Hash> {
@@ -481,359 +483,3 @@ impl<CTX> HashStable<CTX> for Index {
         idx.hash_stable(hcx, hasher);
     }
 }
-
-#[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));
-}
diff --git a/src/librustc_data_structures/transitive_relation/tests.rs b/src/librustc_data_structures/transitive_relation/tests.rs
new file mode 100644
index 00000000000..a462dbdb583
--- /dev/null
+++ b/src/librustc_data_structures/transitive_relation/tests.rs
@@ -0,0 +1,357 @@
+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));
+}
diff --git a/src/tools/tidy/src/unit_tests.rs b/src/tools/tidy/src/unit_tests.rs
index d7d47721170..f4de9bb07b5 100644
--- a/src/tools/tidy/src/unit_tests.rs
+++ b/src/tools/tidy/src/unit_tests.rs
@@ -27,7 +27,6 @@ pub fn check(root_path: &Path, bad: &mut bool) {
     };
     let fixme = [
         "liballoc",
-        "librustc_data_structures",
         "librustdoc",
         "libstd",
         "libsyntax",