Merge crate `collections` into `alloc`

13 files changed, 7074 insertions, 0 deletions

diff --git a/src/liballoc/tests/binary_heap.rs b/src/liballoc/tests/binary_heap.rs
new file mode 100644
index 00000000000..06d585f8ea8
--- /dev/null
+++ b/src/liballoc/tests/binary_heap.rs
@@ -0,0 +1,302 @@
+// Copyright 2013-2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use std::panic;
+use std::collections::BinaryHeap;
+use std::collections::binary_heap::{Drain, PeekMut};
+
+#[test]
+fn test_iterator() {
+    let data = vec![5, 9, 3];
+    let iterout = [9, 5, 3];
+    let heap = BinaryHeap::from(data);
+    let mut i = 0;
+    for el in &heap {
+        assert_eq!(*el, iterout[i]);
+        i += 1;
+    }
+}
+
+#[test]
+fn test_iterator_reverse() {
+    let data = vec![5, 9, 3];
+    let iterout = vec![3, 5, 9];
+    let pq = BinaryHeap::from(data);
+
+    let v: Vec<_> = pq.iter().rev().cloned().collect();
+    assert_eq!(v, iterout);
+}
+
+#[test]
+fn test_move_iter() {
+    let data = vec![5, 9, 3];
+    let iterout = vec![9, 5, 3];
+    let pq = BinaryHeap::from(data);
+
+    let v: Vec<_> = pq.into_iter().collect();
+    assert_eq!(v, iterout);
+}
+
+#[test]
+fn test_move_iter_size_hint() {
+    let data = vec![5, 9];
+    let pq = BinaryHeap::from(data);
+
+    let mut it = pq.into_iter();
+
+    assert_eq!(it.size_hint(), (2, Some(2)));
+    assert_eq!(it.next(), Some(9));
+
+    assert_eq!(it.size_hint(), (1, Some(1)));
+    assert_eq!(it.next(), Some(5));
+
+    assert_eq!(it.size_hint(), (0, Some(0)));
+    assert_eq!(it.next(), None);
+}
+
+#[test]
+fn test_move_iter_reverse() {
+    let data = vec![5, 9, 3];
+    let iterout = vec![3, 5, 9];
+    let pq = BinaryHeap::from(data);
+
+    let v: Vec<_> = pq.into_iter().rev().collect();
+    assert_eq!(v, iterout);
+}
+
+#[test]
+fn test_peek_and_pop() {
+    let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1];
+    let mut sorted = data.clone();
+    sorted.sort();
+    let mut heap = BinaryHeap::from(data);
+    while !heap.is_empty() {
+        assert_eq!(heap.peek().unwrap(), sorted.last().unwrap());
+        assert_eq!(heap.pop().unwrap(), sorted.pop().unwrap());
+    }
+}
+
+#[test]
+fn test_peek_mut() {
+    let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1];
+    let mut heap = BinaryHeap::from(data);
+    assert_eq!(heap.peek(), Some(&10));
+    {
+        let mut top = heap.peek_mut().unwrap();
+        *top -= 2;
+    }
+    assert_eq!(heap.peek(), Some(&9));
+}
+
+#[test]
+fn test_peek_mut_pop() {
+    let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1];
+    let mut heap = BinaryHeap::from(data);
+    assert_eq!(heap.peek(), Some(&10));
+    {
+        let mut top = heap.peek_mut().unwrap();
+        *top -= 2;
+        assert_eq!(PeekMut::pop(top), 8);
+    }
+    assert_eq!(heap.peek(), Some(&9));
+}
+
+#[test]
+fn test_push() {
+    let mut heap = BinaryHeap::from(vec![2, 4, 9]);
+    assert_eq!(heap.len(), 3);
+    assert!(*heap.peek().unwrap() == 9);
+    heap.push(11);
+    assert_eq!(heap.len(), 4);
+    assert!(*heap.peek().unwrap() == 11);
+    heap.push(5);
+    assert_eq!(heap.len(), 5);
+    assert!(*heap.peek().unwrap() == 11);
+    heap.push(27);
+    assert_eq!(heap.len(), 6);
+    assert!(*heap.peek().unwrap() == 27);
+    heap.push(3);
+    assert_eq!(heap.len(), 7);
+    assert!(*heap.peek().unwrap() == 27);
+    heap.push(103);
+    assert_eq!(heap.len(), 8);
+    assert!(*heap.peek().unwrap() == 103);
+}
+
+#[test]
+fn test_push_unique() {
+    let mut heap = BinaryHeap::<Box<_>>::from(vec![box 2, box 4, box 9]);
+    assert_eq!(heap.len(), 3);
+    assert!(**heap.peek().unwrap() == 9);
+    heap.push(box 11);
+    assert_eq!(heap.len(), 4);
+    assert!(**heap.peek().unwrap() == 11);
+    heap.push(box 5);
+    assert_eq!(heap.len(), 5);
+    assert!(**heap.peek().unwrap() == 11);
+    heap.push(box 27);
+    assert_eq!(heap.len(), 6);
+    assert!(**heap.peek().unwrap() == 27);
+    heap.push(box 3);
+    assert_eq!(heap.len(), 7);
+    assert!(**heap.peek().unwrap() == 27);
+    heap.push(box 103);
+    assert_eq!(heap.len(), 8);
+    assert!(**heap.peek().unwrap() == 103);
+}
+
+fn check_to_vec(mut data: Vec<i32>) {
+    let heap = BinaryHeap::from(data.clone());
+    let mut v = heap.clone().into_vec();
+    v.sort();
+    data.sort();
+
+    assert_eq!(v, data);
+    assert_eq!(heap.into_sorted_vec(), data);
+}
+
+#[test]
+fn test_to_vec() {
+    check_to_vec(vec![]);
+    check_to_vec(vec![5]);
+    check_to_vec(vec![3, 2]);
+    check_to_vec(vec![2, 3]);
+    check_to_vec(vec![5, 1, 2]);
+    check_to_vec(vec![1, 100, 2, 3]);
+    check_to_vec(vec![1, 3, 5, 7, 9, 2, 4, 6, 8, 0]);
+    check_to_vec(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]);
+    check_to_vec(vec![9, 11, 9, 9, 9, 9, 11, 2, 3, 4, 11, 9, 0, 0, 0, 0]);
+    check_to_vec(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
+    check_to_vec(vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]);
+    check_to_vec(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 1, 2]);
+    check_to_vec(vec![5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1]);
+}
+
+#[test]
+fn test_empty_pop() {
+    let mut heap = BinaryHeap::<i32>::new();
+    assert!(heap.pop().is_none());
+}
+
+#[test]
+fn test_empty_peek() {
+    let empty = BinaryHeap::<i32>::new();
+    assert!(empty.peek().is_none());
+}
+
+#[test]
+fn test_empty_peek_mut() {
+    let mut empty = BinaryHeap::<i32>::new();
+    assert!(empty.peek_mut().is_none());
+}
+
+#[test]
+fn test_from_iter() {
+    let xs = vec![9, 8, 7, 6, 5, 4, 3, 2, 1];
+
+    let mut q: BinaryHeap<_> = xs.iter().rev().cloned().collect();
+
+    for &x in &xs {
+        assert_eq!(q.pop().unwrap(), x);
+    }
+}
+
+#[test]
+fn test_drain() {
+    let mut q: BinaryHeap<_> = [9, 8, 7, 6, 5, 4, 3, 2, 1].iter().cloned().collect();
+
+    assert_eq!(q.drain().take(5).count(), 5);
+
+    assert!(q.is_empty());
+}
+
+#[test]
+fn test_extend_ref() {
+    let mut a = BinaryHeap::new();
+    a.push(1);
+    a.push(2);
+
+    a.extend(&[3, 4, 5]);
+
+    assert_eq!(a.len(), 5);
+    assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]);
+
+    let mut a = BinaryHeap::new();
+    a.push(1);
+    a.push(2);
+    let mut b = BinaryHeap::new();
+    b.push(3);
+    b.push(4);
+    b.push(5);
+
+    a.extend(&b);
+
+    assert_eq!(a.len(), 5);
+    assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]);
+}
+
+#[test]
+fn test_append() {
+    let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]);
+    let mut b = BinaryHeap::from(vec![-20, 5, 43]);
+
+    a.append(&mut b);
+
+    assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
+    assert!(b.is_empty());
+}
+
+#[test]
+fn test_append_to_empty() {
+    let mut a = BinaryHeap::new();
+    let mut b = BinaryHeap::from(vec![-20, 5, 43]);
+
+    a.append(&mut b);
+
+    assert_eq!(a.into_sorted_vec(), [-20, 5, 43]);
+    assert!(b.is_empty());
+}
+
+#[test]
+fn test_extend_specialization() {
+    let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]);
+    let b = BinaryHeap::from(vec![-20, 5, 43]);
+
+    a.extend(b);
+
+    assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
+}
+
+#[test]
+fn test_placement() {
+    let mut a = BinaryHeap::new();
+    &mut a <- 2;
+    &mut a <- 4;
+    &mut a <- 3;
+    assert_eq!(a.peek(), Some(&4));
+    assert_eq!(a.len(), 3);
+    &mut a <- 1;
+    assert_eq!(a.into_sorted_vec(), vec![1, 2, 3, 4]);
+}
+
+#[test]
+fn test_placement_panic() {
+    let mut heap = BinaryHeap::from(vec![1, 2, 3]);
+    fn mkpanic() -> usize { panic!() }
+    let _ = panic::catch_unwind(panic::AssertUnwindSafe(|| { &mut heap <- mkpanic(); }));
+    assert_eq!(heap.len(), 3);
+}
+
+#[allow(dead_code)]
+fn assert_covariance() {
+    fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
+        d
+    }
+}
diff --git a/src/liballoc/tests/btree/map.rs b/src/liballoc/tests/btree/map.rs
new file mode 100644
index 00000000000..2c899d96940
--- /dev/null
+++ b/src/liballoc/tests/btree/map.rs
@@ -0,0 +1,687 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use std::collections::BTreeMap;
+use std::collections::Bound::{self, Excluded, Included, Unbounded};
+use std::collections::btree_map::Entry::{Occupied, Vacant};
+use std::rc::Rc;
+
+use std::iter::FromIterator;
+use super::DeterministicRng;
+
+#[test]
+fn test_basic_large() {
+    let mut map = BTreeMap::new();
+    let size = 10000;
+    assert_eq!(map.len(), 0);
+
+    for i in 0..size {
+        assert_eq!(map.insert(i, 10 * i), None);
+        assert_eq!(map.len(), i + 1);
+    }
+
+    for i in 0..size {
+        assert_eq!(map.get(&i).unwrap(), &(i * 10));
+    }
+
+    for i in size..size * 2 {
+        assert_eq!(map.get(&i), None);
+    }
+
+    for i in 0..size {
+        assert_eq!(map.insert(i, 100 * i), Some(10 * i));
+        assert_eq!(map.len(), size);
+    }
+
+    for i in 0..size {
+        assert_eq!(map.get(&i).unwrap(), &(i * 100));
+    }
+
+    for i in 0..size / 2 {
+        assert_eq!(map.remove(&(i * 2)), Some(i * 200));
+        assert_eq!(map.len(), size - i - 1);
+    }
+
+    for i in 0..size / 2 {
+        assert_eq!(map.get(&(2 * i)), None);
+        assert_eq!(map.get(&(2 * i + 1)).unwrap(), &(i * 200 + 100));
+    }
+
+    for i in 0..size / 2 {
+        assert_eq!(map.remove(&(2 * i)), None);
+        assert_eq!(map.remove(&(2 * i + 1)), Some(i * 200 + 100));
+        assert_eq!(map.len(), size / 2 - i - 1);
+    }
+}
+
+#[test]
+fn test_basic_small() {
+    let mut map = BTreeMap::new();
+    assert_eq!(map.remove(&1), None);
+    assert_eq!(map.get(&1), None);
+    assert_eq!(map.insert(1, 1), None);
+    assert_eq!(map.get(&1), Some(&1));
+    assert_eq!(map.insert(1, 2), Some(1));
+    assert_eq!(map.get(&1), Some(&2));
+    assert_eq!(map.insert(2, 4), None);
+    assert_eq!(map.get(&2), Some(&4));
+    assert_eq!(map.remove(&1), Some(2));
+    assert_eq!(map.remove(&2), Some(4));
+    assert_eq!(map.remove(&1), None);
+}
+
+#[test]
+fn test_iter() {
+    let size = 10000;
+
+    // Forwards
+    let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
+
+    fn test<T>(size: usize, mut iter: T)
+        where T: Iterator<Item = (usize, usize)>
+    {
+        for i in 0..size {
+            assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
+            assert_eq!(iter.next().unwrap(), (i, i));
+        }
+        assert_eq!(iter.size_hint(), (0, Some(0)));
+        assert_eq!(iter.next(), None);
+    }
+    test(size, map.iter().map(|(&k, &v)| (k, v)));
+    test(size, map.iter_mut().map(|(&k, &mut v)| (k, v)));
+    test(size, map.into_iter());
+}
+
+#[test]
+fn test_iter_rev() {
+    let size = 10000;
+
+    // Forwards
+    let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
+
+    fn test<T>(size: usize, mut iter: T)
+        where T: Iterator<Item = (usize, usize)>
+    {
+        for i in 0..size {
+            assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
+            assert_eq!(iter.next().unwrap(), (size - i - 1, size - i - 1));
+        }
+        assert_eq!(iter.size_hint(), (0, Some(0)));
+        assert_eq!(iter.next(), None);
+    }
+    test(size, map.iter().rev().map(|(&k, &v)| (k, v)));
+    test(size, map.iter_mut().rev().map(|(&k, &mut v)| (k, v)));
+    test(size, map.into_iter().rev());
+}
+
+#[test]
+fn test_values_mut() {
+    let mut a = BTreeMap::new();
+    a.insert(1, String::from("hello"));
+    a.insert(2, String::from("goodbye"));
+
+    for value in a.values_mut() {
+        value.push_str("!");
+    }
+
+    let values: Vec<String> = a.values().cloned().collect();
+    assert_eq!(values, [String::from("hello!"), String::from("goodbye!")]);
+}
+
+#[test]
+fn test_iter_mixed() {
+    let size = 10000;
+
+    // Forwards
+    let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
+
+    fn test<T>(size: usize, mut iter: T)
+        where T: Iterator<Item = (usize, usize)> + DoubleEndedIterator
+    {
+        for i in 0..size / 4 {
+            assert_eq!(iter.size_hint(), (size - i * 2, Some(size - i * 2)));
+            assert_eq!(iter.next().unwrap(), (i, i));
+            assert_eq!(iter.next_back().unwrap(), (size - i - 1, size - i - 1));
+        }
+        for i in size / 4..size * 3 / 4 {
+            assert_eq!(iter.size_hint(), (size * 3 / 4 - i, Some(size * 3 / 4 - i)));
+            assert_eq!(iter.next().unwrap(), (i, i));
+        }
+        assert_eq!(iter.size_hint(), (0, Some(0)));
+        assert_eq!(iter.next(), None);
+    }
+    test(size, map.iter().map(|(&k, &v)| (k, v)));
+    test(size, map.iter_mut().map(|(&k, &mut v)| (k, v)));
+    test(size, map.into_iter());
+}
+
+#[test]
+fn test_range_small() {
+    let size = 5;
+
+    // Forwards
+    let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
+
+    let mut j = 0;
+    for ((&k, &v), i) in map.range(2..).zip(2..size) {
+        assert_eq!(k, i);
+        assert_eq!(v, i);
+        j += 1;
+    }
+    assert_eq!(j, size - 2);
+}
+
+#[test]
+fn test_range_inclusive() {
+    let size = 500;
+
+    let map: BTreeMap<_, _> = (0...size).map(|i| (i, i)).collect();
+
+    fn check<'a, L, R>(lhs: L, rhs: R)
+        where L: IntoIterator<Item=(&'a i32, &'a i32)>,
+              R: IntoIterator<Item=(&'a i32, &'a i32)>,
+    {
+        let lhs: Vec<_> = lhs.into_iter().collect();
+        let rhs: Vec<_> = rhs.into_iter().collect();
+        assert_eq!(lhs, rhs);
+    }
+
+    check(map.range(size + 1...size + 1), vec![]);
+    check(map.range(size...size), vec![(&size, &size)]);
+    check(map.range(size...size + 1), vec![(&size, &size)]);
+    check(map.range(0...0), vec![(&0, &0)]);
+    check(map.range(0...size - 1), map.range(..size));
+    check(map.range(-1...-1), vec![]);
+    check(map.range(-1...size), map.range(..));
+    check(map.range(...size), map.range(..));
+    check(map.range(...200), map.range(..201));
+    check(map.range(5...8), vec![(&5, &5), (&6, &6), (&7, &7), (&8, &8)]);
+    check(map.range(-1...0), vec![(&0, &0)]);
+    check(map.range(-1...2), vec![(&0, &0), (&1, &1), (&2, &2)]);
+}
+
+#[test]
+fn test_range_inclusive_max_value() {
+    let max = ::std::usize::MAX;
+    let map: BTreeMap<_, _> = vec![(max, 0)].into_iter().collect();
+
+    assert_eq!(map.range(max...max).collect::<Vec<_>>(), &[(&max, &0)]);
+}
+
+#[test]
+fn test_range_equal_empty_cases() {
+    let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
+    assert_eq!(map.range((Included(2), Excluded(2))).next(), None);
+    assert_eq!(map.range((Excluded(2), Included(2))).next(), None);
+}
+
+#[test]
+#[should_panic]
+fn test_range_equal_excluded() {
+    let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
+    map.range((Excluded(2), Excluded(2)));
+}
+
+#[test]
+#[should_panic]
+fn test_range_backwards_1() {
+    let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
+    map.range((Included(3), Included(2)));
+}
+
+#[test]
+#[should_panic]
+fn test_range_backwards_2() {
+    let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
+    map.range((Included(3), Excluded(2)));
+}
+
+#[test]
+#[should_panic]
+fn test_range_backwards_3() {
+    let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
+    map.range((Excluded(3), Included(2)));
+}
+
+#[test]
+#[should_panic]
+fn test_range_backwards_4() {
+    let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
+    map.range((Excluded(3), Excluded(2)));
+}
+
+#[test]
+fn test_range_1000() {
+    let size = 1000;
+    let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
+
+    fn test(map: &BTreeMap<u32, u32>, size: u32, min: Bound<&u32>, max: Bound<&u32>) {
+        let mut kvs = map.range((min, max)).map(|(&k, &v)| (k, v));
+        let mut pairs = (0..size).map(|i| (i, i));
+
+        for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
+            assert_eq!(kv, pair);
+        }
+        assert_eq!(kvs.next(), None);
+        assert_eq!(pairs.next(), None);
+    }
+    test(&map, size, Included(&0), Excluded(&size));
+    test(&map, size, Unbounded, Excluded(&size));
+    test(&map, size, Included(&0), Included(&(size - 1)));
+    test(&map, size, Unbounded, Included(&(size - 1)));
+    test(&map, size, Included(&0), Unbounded);
+    test(&map, size, Unbounded, Unbounded);
+}
+
+#[test]
+fn test_range_borrowed_key() {
+    let mut map = BTreeMap::new();
+    map.insert("aardvark".to_string(), 1);
+    map.insert("baboon".to_string(), 2);
+    map.insert("coyote".to_string(), 3);
+    map.insert("dingo".to_string(), 4);
+    // NOTE: would like to use simply "b".."d" here...
+    let mut iter = map.range::<str, _>((Included("b"),Excluded("d")));
+    assert_eq!(iter.next(), Some((&"baboon".to_string(), &2)));
+    assert_eq!(iter.next(), Some((&"coyote".to_string(), &3)));
+    assert_eq!(iter.next(), None);
+}
+
+#[test]
+fn test_range() {
+    let size = 200;
+    let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
+
+    for i in 0..size {
+        for j in i..size {
+            let mut kvs = map.range((Included(&i), Included(&j))).map(|(&k, &v)| (k, v));
+            let mut pairs = (i..j + 1).map(|i| (i, i));
+
+            for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
+                assert_eq!(kv, pair);
+            }
+            assert_eq!(kvs.next(), None);
+            assert_eq!(pairs.next(), None);
+        }
+    }
+}
+
+#[test]
+fn test_range_mut() {
+    let size = 200;
+    let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
+
+    for i in 0..size {
+        for j in i..size {
+            let mut kvs = map.range_mut((Included(&i), Included(&j))).map(|(&k, &mut v)| (k, v));
+            let mut pairs = (i..j + 1).map(|i| (i, i));
+
+            for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
+                assert_eq!(kv, pair);
+            }
+            assert_eq!(kvs.next(), None);
+            assert_eq!(pairs.next(), None);
+        }
+    }
+}
+
+#[test]
+fn test_borrow() {
+    // make sure these compile -- using the Borrow trait
+    {
+        let mut map = BTreeMap::new();
+        map.insert("0".to_string(), 1);
+        assert_eq!(map["0"], 1);
+    }
+
+    {
+        let mut map = BTreeMap::new();
+        map.insert(Box::new(0), 1);
+        assert_eq!(map[&0], 1);
+    }
+
+    {
+        let mut map = BTreeMap::new();
+        map.insert(Box::new([0, 1]) as Box<[i32]>, 1);
+        assert_eq!(map[&[0, 1][..]], 1);
+    }
+
+    {
+        let mut map = BTreeMap::new();
+        map.insert(Rc::new(0), 1);
+        assert_eq!(map[&0], 1);
+    }
+}
+
+#[test]
+fn test_entry() {
+    let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
+
+    let mut map: BTreeMap<_, _> = xs.iter().cloned().collect();
+
+    // Existing key (insert)
+    match map.entry(1) {
+        Vacant(_) => unreachable!(),
+        Occupied(mut view) => {
+            assert_eq!(view.get(), &10);
+            assert_eq!(view.insert(100), 10);
+        }
+    }
+    assert_eq!(map.get(&1).unwrap(), &100);
+    assert_eq!(map.len(), 6);
+
+
+    // Existing key (update)
+    match map.entry(2) {
+        Vacant(_) => unreachable!(),
+        Occupied(mut view) => {
+            let v = view.get_mut();
+            *v *= 10;
+        }
+    }
+    assert_eq!(map.get(&2).unwrap(), &200);
+    assert_eq!(map.len(), 6);
+
+    // Existing key (take)
+    match map.entry(3) {
+        Vacant(_) => unreachable!(),
+        Occupied(view) => {
+            assert_eq!(view.remove(), 30);
+        }
+    }
+    assert_eq!(map.get(&3), None);
+    assert_eq!(map.len(), 5);
+
+
+    // Inexistent key (insert)
+    match map.entry(10) {
+        Occupied(_) => unreachable!(),
+        Vacant(view) => {
+            assert_eq!(*view.insert(1000), 1000);
+        }
+    }
+    assert_eq!(map.get(&10).unwrap(), &1000);
+    assert_eq!(map.len(), 6);
+}
+
+#[test]
+fn test_extend_ref() {
+    let mut a = BTreeMap::new();
+    a.insert(1, "one");
+    let mut b = BTreeMap::new();
+    b.insert(2, "two");
+    b.insert(3, "three");
+
+    a.extend(&b);
+
+    assert_eq!(a.len(), 3);
+    assert_eq!(a[&1], "one");
+    assert_eq!(a[&2], "two");
+    assert_eq!(a[&3], "three");
+}
+
+#[test]
+fn test_zst() {
+    let mut m = BTreeMap::new();
+    assert_eq!(m.len(), 0);
+
+    assert_eq!(m.insert((), ()), None);
+    assert_eq!(m.len(), 1);
+
+    assert_eq!(m.insert((), ()), Some(()));
+    assert_eq!(m.len(), 1);
+    assert_eq!(m.iter().count(), 1);
+
+    m.clear();
+    assert_eq!(m.len(), 0);
+
+    for _ in 0..100 {
+        m.insert((), ());
+    }
+
+    assert_eq!(m.len(), 1);
+    assert_eq!(m.iter().count(), 1);
+}
+
+// This test's only purpose is to ensure that zero-sized keys with nonsensical orderings
+// do not cause segfaults when used with zero-sized values. All other map behavior is
+// undefined.
+#[test]
+fn test_bad_zst() {
+    use std::cmp::Ordering;
+
+    struct Bad;
+
+    impl PartialEq for Bad {
+        fn eq(&self, _: &Self) -> bool {
+            false
+        }
+    }
+
+    impl Eq for Bad {}
+
+    impl PartialOrd for Bad {
+        fn partial_cmp(&self, _: &Self) -> Option<Ordering> {
+            Some(Ordering::Less)
+        }
+    }
+
+    impl Ord for Bad {
+        fn cmp(&self, _: &Self) -> Ordering {
+            Ordering::Less
+        }
+    }
+
+    let mut m = BTreeMap::new();
+
+    for _ in 0..100 {
+        m.insert(Bad, Bad);
+    }
+}
+
+#[test]
+fn test_clone() {
+    let mut map = BTreeMap::new();
+    let size = 100;
+    assert_eq!(map.len(), 0);
+
+    for i in 0..size {
+        assert_eq!(map.insert(i, 10 * i), None);
+        assert_eq!(map.len(), i + 1);
+        assert_eq!(map, map.clone());
+    }
+
+    for i in 0..size {
+        assert_eq!(map.insert(i, 100 * i), Some(10 * i));
+        assert_eq!(map.len(), size);
+        assert_eq!(map, map.clone());
+    }
+
+    for i in 0..size / 2 {
+        assert_eq!(map.remove(&(i * 2)), Some(i * 200));
+        assert_eq!(map.len(), size - i - 1);
+        assert_eq!(map, map.clone());
+    }
+
+    for i in 0..size / 2 {
+        assert_eq!(map.remove(&(2 * i)), None);
+        assert_eq!(map.remove(&(2 * i + 1)), Some(i * 200 + 100));
+        assert_eq!(map.len(), size / 2 - i - 1);
+        assert_eq!(map, map.clone());
+    }
+}
+
+#[test]
+#[allow(dead_code)]
+fn test_variance() {
+    use std::collections::btree_map::{Iter, IntoIter, Range, Keys, Values};
+
+    fn map_key<'new>(v: BTreeMap<&'static str, ()>) -> BTreeMap<&'new str, ()> {
+        v
+    }
+    fn map_val<'new>(v: BTreeMap<(), &'static str>) -> BTreeMap<(), &'new str> {
+        v
+    }
+    fn iter_key<'a, 'new>(v: Iter<'a, &'static str, ()>) -> Iter<'a, &'new str, ()> {
+        v
+    }
+    fn iter_val<'a, 'new>(v: Iter<'a, (), &'static str>) -> Iter<'a, (), &'new str> {
+        v
+    }
+    fn into_iter_key<'new>(v: IntoIter<&'static str, ()>) -> IntoIter<&'new str, ()> {
+        v
+    }
+    fn into_iter_val<'new>(v: IntoIter<(), &'static str>) -> IntoIter<(), &'new str> {
+        v
+    }
+    fn range_key<'a, 'new>(v: Range<'a, &'static str, ()>) -> Range<'a, &'new str, ()> {
+        v
+    }
+    fn range_val<'a, 'new>(v: Range<'a, (), &'static str>) -> Range<'a, (), &'new str> {
+        v
+    }
+    fn keys<'a, 'new>(v: Keys<'a, &'static str, ()>) -> Keys<'a, &'new str, ()> {
+        v
+    }
+    fn vals<'a, 'new>(v: Values<'a, (), &'static str>) -> Values<'a, (), &'new str> {
+        v
+    }
+}
+
+#[test]
+fn test_occupied_entry_key() {
+    let mut a = BTreeMap::new();
+    let key = "hello there";
+    let value = "value goes here";
+    assert!(a.is_empty());
+    a.insert(key.clone(), value.clone());
+    assert_eq!(a.len(), 1);
+    assert_eq!(a[key], value);
+
+    match a.entry(key.clone()) {
+        Vacant(_) => panic!(),
+        Occupied(e) => assert_eq!(key, *e.key()),
+    }
+    assert_eq!(a.len(), 1);
+    assert_eq!(a[key], value);
+}
+
+#[test]
+fn test_vacant_entry_key() {
+    let mut a = BTreeMap::new();
+    let key = "hello there";
+    let value = "value goes here";
+
+    assert!(a.is_empty());
+    match a.entry(key.clone()) {
+        Occupied(_) => panic!(),
+        Vacant(e) => {
+            assert_eq!(key, *e.key());
+            e.insert(value.clone());
+        }
+    }
+    assert_eq!(a.len(), 1);
+    assert_eq!(a[key], value);
+}
+
+macro_rules! create_append_test {
+    ($name:ident, $len:expr) => {
+        #[test]
+        fn $name() {
+            let mut a = BTreeMap::new();
+            for i in 0..8 {
+                a.insert(i, i);
+            }
+
+            let mut b = BTreeMap::new();
+            for i in 5..$len {
+                b.insert(i, 2*i);
+            }
+
+            a.append(&mut b);
+
+            assert_eq!(a.len(), $len);
+            assert_eq!(b.len(), 0);
+
+            for i in 0..$len {
+                if i < 5 {
+                    assert_eq!(a[&i], i);
+                } else {
+                    assert_eq!(a[&i], 2*i);
+                }
+            }
+
+            assert_eq!(a.remove(&($len-1)), Some(2*($len-1)));
+            assert_eq!(a.insert($len-1, 20), None);
+        }
+    };
+}
+
+// These are mostly for testing the algorithm that "fixes" the right edge after insertion.
+// Single node.
+create_append_test!(test_append_9, 9);
+// Two leafs that don't need fixing.
+create_append_test!(test_append_17, 17);
+// Two leafs where the second one ends up underfull and needs stealing at the end.
+create_append_test!(test_append_14, 14);
+// Two leafs where the second one ends up empty because the insertion finished at the root.
+create_append_test!(test_append_12, 12);
+// Three levels; insertion finished at the root.
+create_append_test!(test_append_144, 144);
+// Three levels; insertion finished at leaf while there is an empty node on the second level.
+create_append_test!(test_append_145, 145);
+// Tests for several randomly chosen sizes.
+create_append_test!(test_append_170, 170);
+create_append_test!(test_append_181, 181);
+create_append_test!(test_append_239, 239);
+create_append_test!(test_append_1700, 1700);
+
+fn rand_data(len: usize) -> Vec<(u32, u32)> {
+    let mut rng = DeterministicRng::new();
+    Vec::from_iter((0..len).map(|_| (rng.next(), rng.next())))
+}
+
+#[test]
+fn test_split_off_empty_right() {
+    let mut data = rand_data(173);
+
+    let mut map = BTreeMap::from_iter(data.clone());
+    let right = map.split_off(&(data.iter().max().unwrap().0 + 1));
+
+    data.sort();
+    assert!(map.into_iter().eq(data));
+    assert!(right.into_iter().eq(None));
+}
+
+#[test]
+fn test_split_off_empty_left() {
+    let mut data = rand_data(314);
+
+    let mut map = BTreeMap::from_iter(data.clone());
+    let right = map.split_off(&data.iter().min().unwrap().0);
+
+    data.sort();
+    assert!(map.into_iter().eq(None));
+    assert!(right.into_iter().eq(data));
+}
+
+#[test]
+fn test_split_off_large_random_sorted() {
+    let mut data = rand_data(1529);
+    // special case with maximum height.
+    data.sort();
+
+    let mut map = BTreeMap::from_iter(data.clone());
+    let key = data[data.len() / 2].0;
+    let right = map.split_off(&key);
+
+    assert!(map.into_iter().eq(data.clone().into_iter().filter(|x| x.0 < key)));
+    assert!(right.into_iter().eq(data.into_iter().filter(|x| x.0 >= key)));
+}
diff --git a/src/liballoc/tests/btree/mod.rs b/src/liballoc/tests/btree/mod.rs
new file mode 100644
index 00000000000..ae8b18d0c9f
--- /dev/null
+++ b/src/liballoc/tests/btree/mod.rs
@@ -0,0 +1,42 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+mod map;
+mod set;
+
+/// XorShiftRng
+struct DeterministicRng {
+    x: u32,
+    y: u32,
+    z: u32,
+    w: u32,
+}
+
+impl DeterministicRng {
+    fn new() -> Self {
+        DeterministicRng {
+            x: 0x193a6754,
+            y: 0xa8a7d469,
+            z: 0x97830e05,
+            w: 0x113ba7bb,
+        }
+    }
+
+    fn next(&mut self) -> u32 {
+        let x = self.x;
+        let t = x ^ (x << 11);
+        self.x = self.y;
+        self.y = self.z;
+        self.z = self.w;
+        let w_ = self.w;
+        self.w = w_ ^ (w_ >> 19) ^ (t ^ (t >> 8));
+        self.w
+    }
+}
diff --git a/src/liballoc/tests/btree/set.rs b/src/liballoc/tests/btree/set.rs
new file mode 100644
index 00000000000..6171b8ba624
--- /dev/null
+++ b/src/liballoc/tests/btree/set.rs
@@ -0,0 +1,331 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use std::collections::BTreeSet;
+
+use std::iter::FromIterator;
+use super::DeterministicRng;
+
+#[test]
+fn test_clone_eq() {
+    let mut m = BTreeSet::new();
+
+    m.insert(1);
+    m.insert(2);
+
+    assert!(m.clone() == m);
+}
+
+#[test]
+fn test_hash() {
+    let mut x = BTreeSet::new();
+    let mut y = BTreeSet::new();
+
+    x.insert(1);
+    x.insert(2);
+    x.insert(3);
+
+    y.insert(3);
+    y.insert(2);
+    y.insert(1);
+
+    assert!(::hash(&x) == ::hash(&y));
+}
+
+fn check<F>(a: &[i32], b: &[i32], expected: &[i32], f: F)
+    where F: FnOnce(&BTreeSet<i32>, &BTreeSet<i32>, &mut FnMut(&i32) -> bool) -> bool
+{
+    let mut set_a = BTreeSet::new();
+    let mut set_b = BTreeSet::new();
+
+    for x in a {
+        assert!(set_a.insert(*x))
+    }
+    for y in b {
+        assert!(set_b.insert(*y))
+    }
+
+    let mut i = 0;
+    f(&set_a,
+      &set_b,
+      &mut |&x| {
+          assert_eq!(x, expected[i]);
+          i += 1;
+          true
+      });
+    assert_eq!(i, expected.len());
+}
+
+#[test]
+fn test_intersection() {
+    fn check_intersection(a: &[i32], b: &[i32], expected: &[i32]) {
+        check(a, b, expected, |x, y, f| x.intersection(y).all(f))
+    }
+
+    check_intersection(&[], &[], &[]);
+    check_intersection(&[1, 2, 3], &[], &[]);
+    check_intersection(&[], &[1, 2, 3], &[]);
+    check_intersection(&[2], &[1, 2, 3], &[2]);
+    check_intersection(&[1, 2, 3], &[2], &[2]);
+    check_intersection(&[11, 1, 3, 77, 103, 5, -5],
+                       &[2, 11, 77, -9, -42, 5, 3],
+                       &[3, 5, 11, 77]);
+}
+
+#[test]
+fn test_difference() {
+    fn check_difference(a: &[i32], b: &[i32], expected: &[i32]) {
+        check(a, b, expected, |x, y, f| x.difference(y).all(f))
+    }
+
+    check_difference(&[], &[], &[]);
+    check_difference(&[1, 12], &[], &[1, 12]);
+    check_difference(&[], &[1, 2, 3, 9], &[]);
+    check_difference(&[1, 3, 5, 9, 11], &[3, 9], &[1, 5, 11]);
+    check_difference(&[-5, 11, 22, 33, 40, 42],
+                     &[-12, -5, 14, 23, 34, 38, 39, 50],
+                     &[11, 22, 33, 40, 42]);
+}
+
+#[test]
+fn test_symmetric_difference() {
+    fn check_symmetric_difference(a: &[i32], b: &[i32], expected: &[i32]) {
+        check(a, b, expected, |x, y, f| x.symmetric_difference(y).all(f))
+    }
+
+    check_symmetric_difference(&[], &[], &[]);
+    check_symmetric_difference(&[1, 2, 3], &[2], &[1, 3]);
+    check_symmetric_difference(&[2], &[1, 2, 3], &[1, 3]);
+    check_symmetric_difference(&[1, 3, 5, 9, 11],
+                               &[-2, 3, 9, 14, 22],
+                               &[-2, 1, 5, 11, 14, 22]);
+}
+
+#[test]
+fn test_union() {
+    fn check_union(a: &[i32], b: &[i32], expected: &[i32]) {
+        check(a, b, expected, |x, y, f| x.union(y).all(f))
+    }
+
+    check_union(&[], &[], &[]);
+    check_union(&[1, 2, 3], &[2], &[1, 2, 3]);
+    check_union(&[2], &[1, 2, 3], &[1, 2, 3]);
+    check_union(&[1, 3, 5, 9, 11, 16, 19, 24],
+                &[-2, 1, 5, 9, 13, 19],
+                &[-2, 1, 3, 5, 9, 11, 13, 16, 19, 24]);
+}
+
+#[test]
+fn test_zip() {
+    let mut x = BTreeSet::new();
+    x.insert(5);
+    x.insert(12);
+    x.insert(11);
+
+    let mut y = BTreeSet::new();
+    y.insert("foo");
+    y.insert("bar");
+
+    let x = x;
+    let y = y;
+    let mut z = x.iter().zip(&y);
+
+    assert_eq!(z.next().unwrap(), (&5, &("bar")));
+    assert_eq!(z.next().unwrap(), (&11, &("foo")));
+    assert!(z.next().is_none());
+}
+
+#[test]
+fn test_from_iter() {
+    let xs = [1, 2, 3, 4, 5, 6, 7, 8, 9];
+
+    let set: BTreeSet<_> = xs.iter().cloned().collect();
+
+    for x in &xs {
+        assert!(set.contains(x));
+    }
+}
+
+#[test]
+fn test_show() {
+    let mut set = BTreeSet::new();
+    let empty = BTreeSet::<i32>::new();
+
+    set.insert(1);
+    set.insert(2);
+
+    let set_str = format!("{:?}", set);
+
+    assert_eq!(set_str, "{1, 2}");
+    assert_eq!(format!("{:?}", empty), "{}");
+}
+
+#[test]
+fn test_extend_ref() {
+    let mut a = BTreeSet::new();
+    a.insert(1);
+
+    a.extend(&[2, 3, 4]);
+
+    assert_eq!(a.len(), 4);
+    assert!(a.contains(&1));
+    assert!(a.contains(&2));
+    assert!(a.contains(&3));
+    assert!(a.contains(&4));
+
+    let mut b = BTreeSet::new();
+    b.insert(5);
+    b.insert(6);
+
+    a.extend(&b);
+
+    assert_eq!(a.len(), 6);
+    assert!(a.contains(&1));
+    assert!(a.contains(&2));
+    assert!(a.contains(&3));
+    assert!(a.contains(&4));
+    assert!(a.contains(&5));
+    assert!(a.contains(&6));
+}
+
+#[test]
+fn test_recovery() {
+    use std::cmp::Ordering;
+
+    #[derive(Debug)]
+    struct Foo(&'static str, i32);
+
+    impl PartialEq for Foo {
+        fn eq(&self, other: &Self) -> bool {
+            self.0 == other.0
+        }
+    }
+
+    impl Eq for Foo {}
+
+    impl PartialOrd for Foo {
+        fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+            self.0.partial_cmp(&other.0)
+        }
+    }
+
+    impl Ord for Foo {
+        fn cmp(&self, other: &Self) -> Ordering {
+            self.0.cmp(&other.0)
+        }
+    }
+
+    let mut s = BTreeSet::new();
+    assert_eq!(s.replace(Foo("a", 1)), None);
+    assert_eq!(s.len(), 1);
+    assert_eq!(s.replace(Foo("a", 2)), Some(Foo("a", 1)));
+    assert_eq!(s.len(), 1);
+
+    {
+        let mut it = s.iter();
+        assert_eq!(it.next(), Some(&Foo("a", 2)));
+        assert_eq!(it.next(), None);
+    }
+
+    assert_eq!(s.get(&Foo("a", 1)), Some(&Foo("a", 2)));
+    assert_eq!(s.take(&Foo("a", 1)), Some(Foo("a", 2)));
+    assert_eq!(s.len(), 0);
+
+    assert_eq!(s.get(&Foo("a", 1)), None);
+    assert_eq!(s.take(&Foo("a", 1)), None);
+
+    assert_eq!(s.iter().next(), None);
+}
+
+#[test]
+#[allow(dead_code)]
+fn test_variance() {
+    use std::collections::btree_set::{IntoIter, Iter, Range};
+
+    fn set<'new>(v: BTreeSet<&'static str>) -> BTreeSet<&'new str> {
+        v
+    }
+    fn iter<'a, 'new>(v: Iter<'a, &'static str>) -> Iter<'a, &'new str> {
+        v
+    }
+    fn into_iter<'new>(v: IntoIter<&'static str>) -> IntoIter<&'new str> {
+        v
+    }
+    fn range<'a, 'new>(v: Range<'a, &'static str>) -> Range<'a, &'new str> {
+        v
+    }
+}
+
+#[test]
+fn test_append() {
+    let mut a = BTreeSet::new();
+    a.insert(1);
+    a.insert(2);
+    a.insert(3);
+
+    let mut b = BTreeSet::new();
+    b.insert(3);
+    b.insert(4);
+    b.insert(5);
+
+    a.append(&mut b);
+
+    assert_eq!(a.len(), 5);
+    assert_eq!(b.len(), 0);
+
+    assert_eq!(a.contains(&1), true);
+    assert_eq!(a.contains(&2), true);
+    assert_eq!(a.contains(&3), true);
+    assert_eq!(a.contains(&4), true);
+    assert_eq!(a.contains(&5), true);
+}
+
+fn rand_data(len: usize) -> Vec<u32> {
+    let mut rng = DeterministicRng::new();
+    Vec::from_iter((0..len).map(|_| rng.next()))
+}
+
+#[test]
+fn test_split_off_empty_right() {
+    let mut data = rand_data(173);
+
+    let mut set = BTreeSet::from_iter(data.clone());
+    let right = set.split_off(&(data.iter().max().unwrap() + 1));
+
+    data.sort();
+    assert!(set.into_iter().eq(data));
+    assert!(right.into_iter().eq(None));
+}
+
+#[test]
+fn test_split_off_empty_left() {
+    let mut data = rand_data(314);
+
+    let mut set = BTreeSet::from_iter(data.clone());
+    let right = set.split_off(data.iter().min().unwrap());
+
+    data.sort();
+    assert!(set.into_iter().eq(None));
+    assert!(right.into_iter().eq(data));
+}
+
+#[test]
+fn test_split_off_large_random_sorted() {
+    let mut data = rand_data(1529);
+    // special case with maximum height.
+    data.sort();
+
+    let mut set = BTreeSet::from_iter(data.clone());
+    let key = data[data.len() / 2];
+    let right = set.split_off(&key);
+
+    assert!(set.into_iter().eq(data.clone().into_iter().filter(|x| *x < key)));
+    assert!(right.into_iter().eq(data.into_iter().filter(|x| *x >= key)));
+}
diff --git a/src/liballoc/tests/cow_str.rs b/src/liballoc/tests/cow_str.rs
new file mode 100644
index 00000000000..aa87ee84b3e
--- /dev/null
+++ b/src/liballoc/tests/cow_str.rs
@@ -0,0 +1,151 @@
+// Copyright 2016 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use std::borrow::Cow;
+
+// check that Cow<'a, str> implements addition
+#[test]
+fn check_cow_add_cow() {
+    let borrowed1 = Cow::Borrowed("Hello, ");
+    let borrowed2 = Cow::Borrowed("World!");
+    let borrow_empty = Cow::Borrowed("");
+
+    let owned1: Cow<str> = Cow::Owned(String::from("Hi, "));
+    let owned2: Cow<str> = Cow::Owned(String::from("Rustaceans!"));
+    let owned_empty: Cow<str> = Cow::Owned(String::new());
+
+    assert_eq!("Hello, World!", borrowed1.clone() + borrowed2.clone());
+    assert_eq!("Hello, Rustaceans!", borrowed1.clone() + owned2.clone());
+
+    assert_eq!("Hi, World!", owned1.clone() + borrowed2.clone());
+    assert_eq!("Hi, Rustaceans!", owned1.clone() + owned2.clone());
+
+    if let Cow::Owned(_) = borrowed1.clone() + borrow_empty.clone() {
+        panic!("Adding empty strings to a borrow should note allocate");
+    }
+    if let Cow::Owned(_) = borrow_empty.clone() + borrowed1.clone() {
+        panic!("Adding empty strings to a borrow should note allocate");
+    }
+    if let Cow::Owned(_) = borrowed1.clone() + owned_empty.clone() {
+        panic!("Adding empty strings to a borrow should note allocate");
+    }
+    if let Cow::Owned(_) = owned_empty.clone() + borrowed1.clone() {
+        panic!("Adding empty strings to a borrow should note allocate");
+    }
+}
+
+#[test]
+fn check_cow_add_str() {
+    let borrowed = Cow::Borrowed("Hello, ");
+    let borrow_empty = Cow::Borrowed("");
+
+    let owned: Cow<str> = Cow::Owned(String::from("Hi, "));
+    let owned_empty: Cow<str> = Cow::Owned(String::new());
+
+    assert_eq!("Hello, World!", borrowed.clone() + "World!");
+
+    assert_eq!("Hi, World!", owned.clone() + "World!");
+
+    if let Cow::Owned(_) = borrowed.clone() + "" {
+        panic!("Adding empty strings to a borrow should note allocate");
+    }
+    if let Cow::Owned(_) = borrow_empty.clone() + "Hello, " {
+        panic!("Adding empty strings to a borrow should note allocate");
+    }
+    if let Cow::Owned(_) = owned_empty.clone() + "Hello, " {
+        panic!("Adding empty strings to a borrow should note allocate");
+    }
+}
+
+#[test]
+fn check_cow_add_assign_cow() {
+    let mut borrowed1 = Cow::Borrowed("Hello, ");
+    let borrowed2 = Cow::Borrowed("World!");
+    let borrow_empty = Cow::Borrowed("");
+
+    let mut owned1: Cow<str> = Cow::Owned(String::from("Hi, "));
+    let owned2: Cow<str> = Cow::Owned(String::from("Rustaceans!"));
+    let owned_empty: Cow<str> = Cow::Owned(String::new());
+
+    let mut s = borrowed1.clone();
+    s += borrow_empty.clone();
+    assert_eq!("Hello, ", s);
+    if let Cow::Owned(_) = s {
+        panic!("Adding empty strings to a borrow should note allocate");
+    }
+    let mut s = borrow_empty.clone();
+    s += borrowed1.clone();
+    assert_eq!("Hello, ", s);
+    if let Cow::Owned(_) = s {
+        panic!("Adding empty strings to a borrow should note allocate");
+    }
+    let mut s = borrowed1.clone();
+    s += owned_empty.clone();
+    assert_eq!("Hello, ", s);
+    if let Cow::Owned(_) = s {
+        panic!("Adding empty strings to a borrow should note allocate");
+    }
+    let mut s = owned_empty.clone();
+    s += borrowed1.clone();
+    assert_eq!("Hello, ", s);
+    if let Cow::Owned(_) = s {
+        panic!("Adding empty strings to a borrow should note allocate");
+    }
+
+    owned1 += borrowed2;
+    borrowed1 += owned2;
+
+    assert_eq!("Hi, World!", owned1);
+    assert_eq!("Hello, Rustaceans!", borrowed1);
+}
+
+#[test]
+fn check_cow_add_assign_str() {
+    let mut borrowed = Cow::Borrowed("Hello, ");
+    let borrow_empty = Cow::Borrowed("");
+
+    let mut owned: Cow<str> = Cow::Owned(String::from("Hi, "));
+    let owned_empty: Cow<str> = Cow::Owned(String::new());
+
+    let mut s = borrowed.clone();
+    s += "";
+    assert_eq!("Hello, ", s);
+    if let Cow::Owned(_) = s {
+        panic!("Adding empty strings to a borrow should note allocate");
+    }
+    let mut s = borrow_empty.clone();
+    s += "World!";
+    assert_eq!("World!", s);
+    if let Cow::Owned(_) = s {
+        panic!("Adding empty strings to a borrow should note allocate");
+    }
+    let mut s = owned_empty.clone();
+    s += "World!";
+    assert_eq!("World!", s);
+    if let Cow::Owned(_) = s {
+        panic!("Adding empty strings to a borrow should note allocate");
+    }
+
+    owned += "World!";
+    borrowed += "World!";
+
+    assert_eq!("Hi, World!", owned);
+    assert_eq!("Hello, World!", borrowed);
+}
+
+#[test]
+fn check_cow_clone_from() {
+    let mut c1: Cow<str> = Cow::Owned(String::with_capacity(25));
+    let s: String = "hi".to_string();
+    assert!(s.capacity() < 25);
+    let c2: Cow<str> = Cow::Owned(s);
+    c1.clone_from(&c2);
+    assert!(c1.into_owned().capacity() >= 25);
+}
\ No newline at end of file
diff --git a/src/liballoc/tests/fmt.rs b/src/liballoc/tests/fmt.rs
new file mode 100644
index 00000000000..70e21c65a18
--- /dev/null
+++ b/src/liballoc/tests/fmt.rs
@@ -0,0 +1,17 @@
+// Copyright 2013-2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use std::fmt;
+
+#[test]
+fn test_format() {
+    let s = fmt::format(format_args!("Hello, {}!", "world"));
+    assert_eq!(s, "Hello, world!");
+}
diff --git a/src/liballoc/tests/lib.rs b/src/liballoc/tests/lib.rs
new file mode 100644
index 00000000000..c6d70ee7575
--- /dev/null
+++ b/src/liballoc/tests/lib.rs
@@ -0,0 +1,57 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+#![deny(warnings)]
+
+#![feature(alloc)]
+#![feature(attr_literals)]
+#![feature(box_syntax)]
+#![feature(inclusive_range_syntax)]
+#![feature(collection_placement)]
+#![feature(const_fn)]
+#![feature(exact_size_is_empty)]
+#![feature(iterator_step_by)]
+#![feature(pattern)]
+#![feature(placement_in_syntax)]
+#![feature(rand)]
+#![feature(repr_align)]
+#![feature(slice_rotate)]
+#![feature(splice)]
+#![feature(str_checked_slicing)]
+#![feature(str_escape)]
+#![feature(test)]
+#![feature(unboxed_closures)]
+#![feature(unicode)]
+#![feature(utf8_error_error_len)]
+
+extern crate alloc;
+extern crate test;
+extern crate std_unicode;
+extern crate core;
+
+use std::hash::{Hash, Hasher};
+use std::collections::hash_map::DefaultHasher;
+
+mod binary_heap;
+mod btree;
+mod cow_str;
+mod fmt;
+mod linked_list;
+mod slice;
+mod str;
+mod string;
+mod vec_deque;
+mod vec;
+
+fn hash<T: Hash>(t: &T) -> u64 {
+    let mut s = DefaultHasher::new();
+    t.hash(&mut s);
+    s.finish()
+}
diff --git a/src/liballoc/tests/linked_list.rs b/src/liballoc/tests/linked_list.rs
new file mode 100644
index 00000000000..a59724a017b
--- /dev/null
+++ b/src/liballoc/tests/linked_list.rs
@@ -0,0 +1,368 @@
+// Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use std::collections::LinkedList;
+
+#[test]
+fn test_basic() {
+    let mut m = LinkedList::<Box<_>>::new();
+    assert_eq!(m.pop_front(), None);
+    assert_eq!(m.pop_back(), None);
+    assert_eq!(m.pop_front(), None);
+    m.push_front(box 1);
+    assert_eq!(m.pop_front(), Some(box 1));
+    m.push_back(box 2);
+    m.push_back(box 3);
+    assert_eq!(m.len(), 2);
+    assert_eq!(m.pop_front(), Some(box 2));
+    assert_eq!(m.pop_front(), Some(box 3));
+    assert_eq!(m.len(), 0);
+    assert_eq!(m.pop_front(), None);
+    m.push_back(box 1);
+    m.push_back(box 3);
+    m.push_back(box 5);
+    m.push_back(box 7);
+    assert_eq!(m.pop_front(), Some(box 1));
+
+    let mut n = LinkedList::new();
+    n.push_front(2);
+    n.push_front(3);
+    {
+        assert_eq!(n.front().unwrap(), &3);
+        let x = n.front_mut().unwrap();
+        assert_eq!(*x, 3);
+        *x = 0;
+    }
+    {
+        assert_eq!(n.back().unwrap(), &2);
+        let y = n.back_mut().unwrap();
+        assert_eq!(*y, 2);
+        *y = 1;
+    }
+    assert_eq!(n.pop_front(), Some(0));
+    assert_eq!(n.pop_front(), Some(1));
+}
+
+#[cfg(test)]
+fn generate_test() -> LinkedList<i32> {
+    list_from(&[0, 1, 2, 3, 4, 5, 6])
+}
+
+#[cfg(test)]
+fn list_from<T: Clone>(v: &[T]) -> LinkedList<T> {
+    v.iter().cloned().collect()
+}
+
+#[test]
+fn test_split_off() {
+    // singleton
+    {
+        let mut m = LinkedList::new();
+        m.push_back(1);
+
+        let p = m.split_off(0);
+        assert_eq!(m.len(), 0);
+        assert_eq!(p.len(), 1);
+        assert_eq!(p.back(), Some(&1));
+        assert_eq!(p.front(), Some(&1));
+    }
+
+    // not singleton, forwards
+    {
+        let u = vec![1, 2, 3, 4, 5];
+        let mut m = list_from(&u);
+        let mut n = m.split_off(2);
+        assert_eq!(m.len(), 2);
+        assert_eq!(n.len(), 3);
+        for elt in 1..3 {
+            assert_eq!(m.pop_front(), Some(elt));
+        }
+        for elt in 3..6 {
+            assert_eq!(n.pop_front(), Some(elt));
+        }
+    }
+    // not singleton, backwards
+    {
+        let u = vec![1, 2, 3, 4, 5];
+        let mut m = list_from(&u);
+        let mut n = m.split_off(4);
+        assert_eq!(m.len(), 4);
+        assert_eq!(n.len(), 1);
+        for elt in 1..5 {
+            assert_eq!(m.pop_front(), Some(elt));
+        }
+        for elt in 5..6 {
+            assert_eq!(n.pop_front(), Some(elt));
+        }
+    }
+
+    // no-op on the last index
+    {
+        let mut m = LinkedList::new();
+        m.push_back(1);
+
+        let p = m.split_off(1);
+        assert_eq!(m.len(), 1);
+        assert_eq!(p.len(), 0);
+        assert_eq!(m.back(), Some(&1));
+        assert_eq!(m.front(), Some(&1));
+    }
+
+}
+
+#[test]
+fn test_iterator() {
+    let m = generate_test();
+    for (i, elt) in m.iter().enumerate() {
+        assert_eq!(i as i32, *elt);
+    }
+    let mut n = LinkedList::new();
+    assert_eq!(n.iter().next(), None);
+    n.push_front(4);
+    let mut it = n.iter();
+    assert_eq!(it.size_hint(), (1, Some(1)));
+    assert_eq!(it.next().unwrap(), &4);
+    assert_eq!(it.size_hint(), (0, Some(0)));
+    assert_eq!(it.next(), None);
+}
+
+#[test]
+fn test_iterator_clone() {
+    let mut n = LinkedList::new();
+    n.push_back(2);
+    n.push_back(3);
+    n.push_back(4);
+    let mut it = n.iter();
+    it.next();
+    let mut jt = it.clone();
+    assert_eq!(it.next(), jt.next());
+    assert_eq!(it.next_back(), jt.next_back());
+    assert_eq!(it.next(), jt.next());
+}
+
+#[test]
+fn test_iterator_double_end() {
+    let mut n = LinkedList::new();
+    assert_eq!(n.iter().next(), None);
+    n.push_front(4);
+    n.push_front(5);
+    n.push_front(6);
+    let mut it = n.iter();
+    assert_eq!(it.size_hint(), (3, Some(3)));
+    assert_eq!(it.next().unwrap(), &6);
+    assert_eq!(it.size_hint(), (2, Some(2)));
+    assert_eq!(it.next_back().unwrap(), &4);
+    assert_eq!(it.size_hint(), (1, Some(1)));
+    assert_eq!(it.next_back().unwrap(), &5);
+    assert_eq!(it.next_back(), None);
+    assert_eq!(it.next(), None);
+}
+
+#[test]
+fn test_rev_iter() {
+    let m = generate_test();
+    for (i, elt) in m.iter().rev().enumerate() {
+        assert_eq!((6 - i) as i32, *elt);
+    }
+    let mut n = LinkedList::new();
+    assert_eq!(n.iter().rev().next(), None);
+    n.push_front(4);
+    let mut it = n.iter().rev();
+    assert_eq!(it.size_hint(), (1, Some(1)));
+    assert_eq!(it.next().unwrap(), &4);
+    assert_eq!(it.size_hint(), (0, Some(0)));
+    assert_eq!(it.next(), None);
+}
+
+#[test]
+fn test_mut_iter() {
+    let mut m = generate_test();
+    let mut len = m.len();
+    for (i, elt) in m.iter_mut().enumerate() {
+        assert_eq!(i as i32, *elt);
+        len -= 1;
+    }
+    assert_eq!(len, 0);
+    let mut n = LinkedList::new();
+    assert!(n.iter_mut().next().is_none());
+    n.push_front(4);
+    n.push_back(5);
+    let mut it = n.iter_mut();
+    assert_eq!(it.size_hint(), (2, Some(2)));
+    assert!(it.next().is_some());
+    assert!(it.next().is_some());
+    assert_eq!(it.size_hint(), (0, Some(0)));
+    assert!(it.next().is_none());
+}
+
+#[test]
+fn test_iterator_mut_double_end() {
+    let mut n = LinkedList::new();
+    assert!(n.iter_mut().next_back().is_none());
+    n.push_front(4);
+    n.push_front(5);
+    n.push_front(6);
+    let mut it = n.iter_mut();
+    assert_eq!(it.size_hint(), (3, Some(3)));
+    assert_eq!(*it.next().unwrap(), 6);
+    assert_eq!(it.size_hint(), (2, Some(2)));
+    assert_eq!(*it.next_back().unwrap(), 4);
+    assert_eq!(it.size_hint(), (1, Some(1)));
+    assert_eq!(*it.next_back().unwrap(), 5);
+    assert!(it.next_back().is_none());
+    assert!(it.next().is_none());
+}
+
+#[test]
+fn test_mut_rev_iter() {
+    let mut m = generate_test();
+    for (i, elt) in m.iter_mut().rev().enumerate() {
+        assert_eq!((6 - i) as i32, *elt);
+    }
+    let mut n = LinkedList::new();
+    assert!(n.iter_mut().rev().next().is_none());
+    n.push_front(4);
+    let mut it = n.iter_mut().rev();
+    assert!(it.next().is_some());
+    assert!(it.next().is_none());
+}
+
+#[test]
+fn test_eq() {
+    let mut n = list_from(&[]);
+    let mut m = list_from(&[]);
+    assert!(n == m);
+    n.push_front(1);
+    assert!(n != m);
+    m.push_back(1);
+    assert!(n == m);
+
+    let n = list_from(&[2, 3, 4]);
+    let m = list_from(&[1, 2, 3]);
+    assert!(n != m);
+}
+
+#[test]
+fn test_hash() {
+    let mut x = LinkedList::new();
+    let mut y = LinkedList::new();
+
+    assert!(::hash(&x) == ::hash(&y));
+
+    x.push_back(1);
+    x.push_back(2);
+    x.push_back(3);
+
+    y.push_front(3);
+    y.push_front(2);
+    y.push_front(1);
+
+    assert!(::hash(&x) == ::hash(&y));
+}
+
+#[test]
+fn test_ord() {
+    let n = list_from(&[]);
+    let m = list_from(&[1, 2, 3]);
+    assert!(n < m);
+    assert!(m > n);
+    assert!(n <= n);
+    assert!(n >= n);
+}
+
+#[test]
+fn test_ord_nan() {
+    let nan = 0.0f64 / 0.0;
+    let n = list_from(&[nan]);
+    let m = list_from(&[nan]);
+    assert!(!(n < m));
+    assert!(!(n > m));
+    assert!(!(n <= m));
+    assert!(!(n >= m));
+
+    let n = list_from(&[nan]);
+    let one = list_from(&[1.0f64]);
+    assert!(!(n < one));
+    assert!(!(n > one));
+    assert!(!(n <= one));
+    assert!(!(n >= one));
+
+    let u = list_from(&[1.0f64, 2.0, nan]);
+    let v = list_from(&[1.0f64, 2.0, 3.0]);
+    assert!(!(u < v));
+    assert!(!(u > v));
+    assert!(!(u <= v));
+    assert!(!(u >= v));
+
+    let s = list_from(&[1.0f64, 2.0, 4.0, 2.0]);
+    let t = list_from(&[1.0f64, 2.0, 3.0, 2.0]);
+    assert!(!(s < t));
+    assert!(s > one);
+    assert!(!(s <= one));
+    assert!(s >= one);
+}
+
+#[test]
+fn test_show() {
+    let list: LinkedList<_> = (0..10).collect();
+    assert_eq!(format!("{:?}", list), "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
+
+    let list: LinkedList<_> = vec!["just", "one", "test", "more"].iter().cloned().collect();
+    assert_eq!(format!("{:?}", list),
+               "[\"just\", \"one\", \"test\", \"more\"]");
+}
+
+#[test]
+fn test_extend_ref() {
+    let mut a = LinkedList::new();
+    a.push_back(1);
+
+    a.extend(&[2, 3, 4]);
+
+    assert_eq!(a.len(), 4);
+    assert_eq!(a, list_from(&[1, 2, 3, 4]));
+
+    let mut b = LinkedList::new();
+    b.push_back(5);
+    b.push_back(6);
+    a.extend(&b);
+
+    assert_eq!(a.len(), 6);
+    assert_eq!(a, list_from(&[1, 2, 3, 4, 5, 6]));
+}
+
+#[test]
+fn test_extend() {
+    let mut a = LinkedList::new();
+    a.push_back(1);
+    a.extend(vec![2, 3, 4]); // uses iterator
+
+    assert_eq!(a.len(), 4);
+    assert!(a.iter().eq(&[1, 2, 3, 4]));
+
+    let b: LinkedList<_> = vec![5, 6, 7].into_iter().collect();
+    a.extend(b); // specializes to `append`
+
+    assert_eq!(a.len(), 7);
+    assert!(a.iter().eq(&[1, 2, 3, 4, 5, 6, 7]));
+}
+
+#[test]
+fn test_contains() {
+    let mut l = LinkedList::new();
+    l.extend(&[2, 3, 4]);
+
+    assert!(l.contains(&3));
+    assert!(!l.contains(&1));
+
+    l.clear();
+
+    assert!(!l.contains(&3));
+}
diff --git a/src/liballoc/tests/slice.rs b/src/liballoc/tests/slice.rs
new file mode 100644
index 00000000000..7fa65a2144e
--- /dev/null
+++ b/src/liballoc/tests/slice.rs
@@ -0,0 +1,1225 @@
+// Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use std::cmp::Ordering::{Equal, Greater, Less};
+use std::mem;
+use std::__rand::{Rng, thread_rng};
+use std::rc::Rc;
+
+fn square(n: usize) -> usize {
+    n * n
+}
+
+fn is_odd(n: &usize) -> bool {
+    *n % 2 == 1
+}
+
+#[test]
+fn test_from_fn() {
+    // Test on-stack from_fn.
+    let mut v: Vec<_> = (0..3).map(square).collect();
+    {
+        let v = v;
+        assert_eq!(v.len(), 3);
+        assert_eq!(v[0], 0);
+        assert_eq!(v[1], 1);
+        assert_eq!(v[2], 4);
+    }
+
+    // Test on-heap from_fn.
+    v = (0..5).map(square).collect();
+    {
+        let v = v;
+        assert_eq!(v.len(), 5);
+        assert_eq!(v[0], 0);
+        assert_eq!(v[1], 1);
+        assert_eq!(v[2], 4);
+        assert_eq!(v[3], 9);
+        assert_eq!(v[4], 16);
+    }
+}
+
+#[test]
+fn test_from_elem() {
+    // Test on-stack from_elem.
+    let mut v = vec![10, 10];
+    {
+        let v = v;
+        assert_eq!(v.len(), 2);
+        assert_eq!(v[0], 10);
+        assert_eq!(v[1], 10);
+    }
+
+    // Test on-heap from_elem.
+    v = vec![20; 6];
+    {
+        let v = &v[..];
+        assert_eq!(v[0], 20);
+        assert_eq!(v[1], 20);
+        assert_eq!(v[2], 20);
+        assert_eq!(v[3], 20);
+        assert_eq!(v[4], 20);
+        assert_eq!(v[5], 20);
+    }
+}
+
+#[test]
+fn test_is_empty() {
+    let xs: [i32; 0] = [];
+    assert!(xs.is_empty());
+    assert!(![0].is_empty());
+}
+
+#[test]
+fn test_len_divzero() {
+    type Z = [i8; 0];
+    let v0: &[Z] = &[];
+    let v1: &[Z] = &[[]];
+    let v2: &[Z] = &[[], []];
+    assert_eq!(mem::size_of::<Z>(), 0);
+    assert_eq!(v0.len(), 0);
+    assert_eq!(v1.len(), 1);
+    assert_eq!(v2.len(), 2);
+}
+
+#[test]
+fn test_get() {
+    let mut a = vec![11];
+    assert_eq!(a.get(1), None);
+    a = vec![11, 12];
+    assert_eq!(a.get(1).unwrap(), &12);
+    a = vec![11, 12, 13];
+    assert_eq!(a.get(1).unwrap(), &12);
+}
+
+#[test]
+fn test_first() {
+    let mut a = vec![];
+    assert_eq!(a.first(), None);
+    a = vec![11];
+    assert_eq!(a.first().unwrap(), &11);
+    a = vec![11, 12];
+    assert_eq!(a.first().unwrap(), &11);
+}
+
+#[test]
+fn test_first_mut() {
+    let mut a = vec![];
+    assert_eq!(a.first_mut(), None);
+    a = vec![11];
+    assert_eq!(*a.first_mut().unwrap(), 11);
+    a = vec![11, 12];
+    assert_eq!(*a.first_mut().unwrap(), 11);
+}
+
+#[test]
+fn test_split_first() {
+    let mut a = vec![11];
+    let b: &[i32] = &[];
+    assert!(b.split_first().is_none());
+    assert_eq!(a.split_first(), Some((&11, b)));
+    a = vec![11, 12];
+    let b: &[i32] = &[12];
+    assert_eq!(a.split_first(), Some((&11, b)));
+}
+
+#[test]
+fn test_split_first_mut() {
+    let mut a = vec![11];
+    let b: &mut [i32] = &mut [];
+    assert!(b.split_first_mut().is_none());
+    assert!(a.split_first_mut() == Some((&mut 11, b)));
+    a = vec![11, 12];
+    let b: &mut [_] = &mut [12];
+    assert!(a.split_first_mut() == Some((&mut 11, b)));
+}
+
+#[test]
+fn test_split_last() {
+    let mut a = vec![11];
+    let b: &[i32] = &[];
+    assert!(b.split_last().is_none());
+    assert_eq!(a.split_last(), Some((&11, b)));
+    a = vec![11, 12];
+    let b: &[_] = &[11];
+    assert_eq!(a.split_last(), Some((&12, b)));
+}
+
+#[test]
+fn test_split_last_mut() {
+    let mut a = vec![11];
+    let b: &mut [i32] = &mut [];
+    assert!(b.split_last_mut().is_none());
+    assert!(a.split_last_mut() == Some((&mut 11, b)));
+
+    a = vec![11, 12];
+    let b: &mut [_] = &mut [11];
+    assert!(a.split_last_mut() == Some((&mut 12, b)));
+}
+
+#[test]
+fn test_last() {
+    let mut a = vec![];
+    assert_eq!(a.last(), None);
+    a = vec![11];
+    assert_eq!(a.last().unwrap(), &11);
+    a = vec![11, 12];
+    assert_eq!(a.last().unwrap(), &12);
+}
+
+#[test]
+fn test_last_mut() {
+    let mut a = vec![];
+    assert_eq!(a.last_mut(), None);
+    a = vec![11];
+    assert_eq!(*a.last_mut().unwrap(), 11);
+    a = vec![11, 12];
+    assert_eq!(*a.last_mut().unwrap(), 12);
+}
+
+#[test]
+fn test_slice() {
+    // Test fixed length vector.
+    let vec_fixed = [1, 2, 3, 4];
+    let v_a = vec_fixed[1..vec_fixed.len()].to_vec();
+    assert_eq!(v_a.len(), 3);
+
+    assert_eq!(v_a[0], 2);
+    assert_eq!(v_a[1], 3);
+    assert_eq!(v_a[2], 4);
+
+    // Test on stack.
+    let vec_stack: &[_] = &[1, 2, 3];
+    let v_b = vec_stack[1..3].to_vec();
+    assert_eq!(v_b.len(), 2);
+
+    assert_eq!(v_b[0], 2);
+    assert_eq!(v_b[1], 3);
+
+    // Test `Box<[T]>`
+    let vec_unique = vec![1, 2, 3, 4, 5, 6];
+    let v_d = vec_unique[1..6].to_vec();
+    assert_eq!(v_d.len(), 5);
+
+    assert_eq!(v_d[0], 2);
+    assert_eq!(v_d[1], 3);
+    assert_eq!(v_d[2], 4);
+    assert_eq!(v_d[3], 5);
+    assert_eq!(v_d[4], 6);
+}
+
+#[test]
+fn test_slice_from() {
+    let vec: &[_] = &[1, 2, 3, 4];
+    assert_eq!(&vec[..], vec);
+    let b: &[_] = &[3, 4];
+    assert_eq!(&vec[2..], b);
+    let b: &[_] = &[];
+    assert_eq!(&vec[4..], b);
+}
+
+#[test]
+fn test_slice_to() {
+    let vec: &[_] = &[1, 2, 3, 4];
+    assert_eq!(&vec[..4], vec);
+    let b: &[_] = &[1, 2];
+    assert_eq!(&vec[..2], b);
+    let b: &[_] = &[];
+    assert_eq!(&vec[..0], b);
+}
+
+
+#[test]
+fn test_pop() {
+    let mut v = vec![5];
+    let e = v.pop();
+    assert_eq!(v.len(), 0);
+    assert_eq!(e, Some(5));
+    let f = v.pop();
+    assert_eq!(f, None);
+    let g = v.pop();
+    assert_eq!(g, None);
+}
+
+#[test]
+fn test_swap_remove() {
+    let mut v = vec![1, 2, 3, 4, 5];
+    let mut e = v.swap_remove(0);
+    assert_eq!(e, 1);
+    assert_eq!(v, [5, 2, 3, 4]);
+    e = v.swap_remove(3);
+    assert_eq!(e, 4);
+    assert_eq!(v, [5, 2, 3]);
+}
+
+#[test]
+#[should_panic]
+fn test_swap_remove_fail() {
+    let mut v = vec![1];
+    let _ = v.swap_remove(0);
+    let _ = v.swap_remove(0);
+}
+
+#[test]
+fn test_swap_remove_noncopyable() {
+    // Tests that we don't accidentally run destructors twice.
+    let mut v: Vec<Box<_>> = Vec::new();
+    v.push(box 0);
+    v.push(box 0);
+    v.push(box 0);
+    let mut _e = v.swap_remove(0);
+    assert_eq!(v.len(), 2);
+    _e = v.swap_remove(1);
+    assert_eq!(v.len(), 1);
+    _e = v.swap_remove(0);
+    assert_eq!(v.len(), 0);
+}
+
+#[test]
+fn test_push() {
+    // Test on-stack push().
+    let mut v = vec![];
+    v.push(1);
+    assert_eq!(v.len(), 1);
+    assert_eq!(v[0], 1);
+
+    // Test on-heap push().
+    v.push(2);
+    assert_eq!(v.len(), 2);
+    assert_eq!(v[0], 1);
+    assert_eq!(v[1], 2);
+}
+
+#[test]
+fn test_truncate() {
+    let mut v: Vec<Box<_>> = vec![box 6, box 5, box 4];
+    v.truncate(1);
+    let v = v;
+    assert_eq!(v.len(), 1);
+    assert_eq!(*(v[0]), 6);
+    // If the unsafe block didn't drop things properly, we blow up here.
+}
+
+#[test]
+fn test_clear() {
+    let mut v: Vec<Box<_>> = vec![box 6, box 5, box 4];
+    v.clear();
+    assert_eq!(v.len(), 0);
+    // If the unsafe block didn't drop things properly, we blow up here.
+}
+
+#[test]
+fn test_retain() {
+    let mut v = vec![1, 2, 3, 4, 5];
+    v.retain(is_odd);
+    assert_eq!(v, [1, 3, 5]);
+}
+
+#[test]
+fn test_binary_search() {
+    assert_eq!([1, 2, 3, 4, 5].binary_search(&5).ok(), Some(4));
+    assert_eq!([1, 2, 3, 4, 5].binary_search(&4).ok(), Some(3));
+    assert_eq!([1, 2, 3, 4, 5].binary_search(&3).ok(), Some(2));
+    assert_eq!([1, 2, 3, 4, 5].binary_search(&2).ok(), Some(1));
+    assert_eq!([1, 2, 3, 4, 5].binary_search(&1).ok(), Some(0));
+
+    assert_eq!([2, 4, 6, 8, 10].binary_search(&1).ok(), None);
+    assert_eq!([2, 4, 6, 8, 10].binary_search(&5).ok(), None);
+    assert_eq!([2, 4, 6, 8, 10].binary_search(&4).ok(), Some(1));
+    assert_eq!([2, 4, 6, 8, 10].binary_search(&10).ok(), Some(4));
+
+    assert_eq!([2, 4, 6, 8].binary_search(&1).ok(), None);
+    assert_eq!([2, 4, 6, 8].binary_search(&5).ok(), None);
+    assert_eq!([2, 4, 6, 8].binary_search(&4).ok(), Some(1));
+    assert_eq!([2, 4, 6, 8].binary_search(&8).ok(), Some(3));
+
+    assert_eq!([2, 4, 6].binary_search(&1).ok(), None);
+    assert_eq!([2, 4, 6].binary_search(&5).ok(), None);
+    assert_eq!([2, 4, 6].binary_search(&4).ok(), Some(1));
+    assert_eq!([2, 4, 6].binary_search(&6).ok(), Some(2));
+
+    assert_eq!([2, 4].binary_search(&1).ok(), None);
+    assert_eq!([2, 4].binary_search(&5).ok(), None);
+    assert_eq!([2, 4].binary_search(&2).ok(), Some(0));
+    assert_eq!([2, 4].binary_search(&4).ok(), Some(1));
+
+    assert_eq!([2].binary_search(&1).ok(), None);
+    assert_eq!([2].binary_search(&5).ok(), None);
+    assert_eq!([2].binary_search(&2).ok(), Some(0));
+
+    assert_eq!([].binary_search(&1).ok(), None);
+    assert_eq!([].binary_search(&5).ok(), None);
+
+    assert!([1, 1, 1, 1, 1].binary_search(&1).ok() != None);
+    assert!([1, 1, 1, 1, 2].binary_search(&1).ok() != None);
+    assert!([1, 1, 1, 2, 2].binary_search(&1).ok() != None);
+    assert!([1, 1, 2, 2, 2].binary_search(&1).ok() != None);
+    assert_eq!([1, 2, 2, 2, 2].binary_search(&1).ok(), Some(0));
+
+    assert_eq!([1, 2, 3, 4, 5].binary_search(&6).ok(), None);
+    assert_eq!([1, 2, 3, 4, 5].binary_search(&0).ok(), None);
+}
+
+#[test]
+fn test_reverse() {
+    let mut v = vec![10, 20];
+    assert_eq!(v[0], 10);
+    assert_eq!(v[1], 20);
+    v.reverse();
+    assert_eq!(v[0], 20);
+    assert_eq!(v[1], 10);
+
+    let mut v3 = Vec::<i32>::new();
+    v3.reverse();
+    assert!(v3.is_empty());
+
+    // check the 1-byte-types path
+    let mut v = (-50..51i8).collect::<Vec<_>>();
+    v.reverse();
+    assert_eq!(v, (-50..51i8).rev().collect::<Vec<_>>());
+
+    // check the 2-byte-types path
+    let mut v = (-50..51i16).collect::<Vec<_>>();
+    v.reverse();
+    assert_eq!(v, (-50..51i16).rev().collect::<Vec<_>>());
+}
+
+#[test]
+fn test_sort() {
+    let mut rng = thread_rng();
+
+    for len in (2..25).chain(500..510) {
+        for _ in 0..100 {
+            let mut v: Vec<_> = rng.gen_iter::<i32>().take(len).collect();
+            let mut v1 = v.clone();
+
+            v.sort();
+            assert!(v.windows(2).all(|w| w[0] <= w[1]));
+
+            v1.sort_by(|a, b| a.cmp(b));
+            assert!(v1.windows(2).all(|w| w[0] <= w[1]));
+
+            v1.sort_by(|a, b| b.cmp(a));
+            assert!(v1.windows(2).all(|w| w[0] >= w[1]));
+        }
+    }
+
+    // Sort using a completely random comparison function.
+    // This will reorder the elements *somehow*, but won't panic.
+    let mut v = [0; 500];
+    for i in 0..v.len() {
+        v[i] = i as i32;
+    }
+    v.sort_by(|_, _| *rng.choose(&[Less, Equal, Greater]).unwrap());
+    v.sort();
+    for i in 0..v.len() {
+        assert_eq!(v[i], i as i32);
+    }
+
+    // Should not panic.
+    [0i32; 0].sort();
+    [(); 10].sort();
+    [(); 100].sort();
+
+    let mut v = [0xDEADBEEFu64];
+    v.sort();
+    assert!(v == [0xDEADBEEF]);
+}
+
+#[test]
+fn test_sort_stability() {
+    for len in (2..25).chain(500..510) {
+        for _ in 0..10 {
+            let mut counts = [0; 10];
+
+            // create a vector like [(6, 1), (5, 1), (6, 2), ...],
+            // where the first item of each tuple is random, but
+            // the second item represents which occurrence of that
+            // number this element is, i.e. the second elements
+            // will occur in sorted order.
+            let mut v: Vec<_> = (0..len)
+                .map(|_| {
+                    let n = thread_rng().gen::<usize>() % 10;
+                    counts[n] += 1;
+                    (n, counts[n])
+                })
+                .collect();
+
+            // only sort on the first element, so an unstable sort
+            // may mix up the counts.
+            v.sort_by(|&(a, _), &(b, _)| a.cmp(&b));
+
+            // this comparison includes the count (the second item
+            // of the tuple), so elements with equal first items
+            // will need to be ordered with increasing
+            // counts... i.e. exactly asserting that this sort is
+            // stable.
+            assert!(v.windows(2).all(|w| w[0] <= w[1]));
+        }
+    }
+}
+
+#[test]
+fn test_rotate() {
+    let expected: Vec<_> = (0..13).collect();
+    let mut v = Vec::new();
+
+    // no-ops
+    v.clone_from(&expected);
+    v.rotate(0);
+    assert_eq!(v, expected);
+    v.rotate(expected.len());
+    assert_eq!(v, expected);
+    let mut zst_array = [(), (), ()];
+    zst_array.rotate(2);
+
+    // happy path
+    v = (5..13).chain(0..5).collect();
+    v.rotate(8);
+    assert_eq!(v, expected);
+
+    let expected: Vec<_> = (0..1000).collect();
+
+    // small rotations in large slice, uses ptr::copy
+    v = (2..1000).chain(0..2).collect();
+    v.rotate(998);
+    assert_eq!(v, expected);
+    v = (998..1000).chain(0..998).collect();
+    v.rotate(2);
+    assert_eq!(v, expected);
+
+    // non-small prime rotation, has a few rounds of swapping
+    v = (389..1000).chain(0..389).collect();
+    v.rotate(1000-389);
+    assert_eq!(v, expected);
+}
+
+#[test]
+fn test_concat() {
+    let v: [Vec<i32>; 0] = [];
+    let c = v.concat();
+    assert_eq!(c, []);
+    let d = [vec![1], vec![2, 3]].concat();
+    assert_eq!(d, [1, 2, 3]);
+
+    let v: &[&[_]] = &[&[1], &[2, 3]];
+    assert_eq!(v.join(&0), [1, 0, 2, 3]);
+    let v: &[&[_]] = &[&[1], &[2], &[3]];
+    assert_eq!(v.join(&0), [1, 0, 2, 0, 3]);
+}
+
+#[test]
+fn test_join() {
+    let v: [Vec<i32>; 0] = [];
+    assert_eq!(v.join(&0), []);
+    assert_eq!([vec![1], vec![2, 3]].join(&0), [1, 0, 2, 3]);
+    assert_eq!([vec![1], vec![2], vec![3]].join(&0), [1, 0, 2, 0, 3]);
+
+    let v: [&[_]; 2] = [&[1], &[2, 3]];
+    assert_eq!(v.join(&0), [1, 0, 2, 3]);
+    let v: [&[_]; 3] = [&[1], &[2], &[3]];
+    assert_eq!(v.join(&0), [1, 0, 2, 0, 3]);
+}
+
+#[test]
+fn test_insert() {
+    let mut a = vec![1, 2, 4];
+    a.insert(2, 3);
+    assert_eq!(a, [1, 2, 3, 4]);
+
+    let mut a = vec![1, 2, 3];
+    a.insert(0, 0);
+    assert_eq!(a, [0, 1, 2, 3]);
+
+    let mut a = vec![1, 2, 3];
+    a.insert(3, 4);
+    assert_eq!(a, [1, 2, 3, 4]);
+
+    let mut a = vec![];
+    a.insert(0, 1);
+    assert_eq!(a, [1]);
+}
+
+#[test]
+#[should_panic]
+fn test_insert_oob() {
+    let mut a = vec![1, 2, 3];
+    a.insert(4, 5);
+}
+
+#[test]
+fn test_remove() {
+    let mut a = vec![1, 2, 3, 4];
+
+    assert_eq!(a.remove(2), 3);
+    assert_eq!(a, [1, 2, 4]);
+
+    assert_eq!(a.remove(2), 4);
+    assert_eq!(a, [1, 2]);
+
+    assert_eq!(a.remove(0), 1);
+    assert_eq!(a, [2]);
+
+    assert_eq!(a.remove(0), 2);
+    assert_eq!(a, []);
+}
+
+#[test]
+#[should_panic]
+fn test_remove_fail() {
+    let mut a = vec![1];
+    let _ = a.remove(0);
+    let _ = a.remove(0);
+}
+
+#[test]
+fn test_capacity() {
+    let mut v = vec![0];
+    v.reserve_exact(10);
+    assert!(v.capacity() >= 11);
+}
+
+#[test]
+fn test_slice_2() {
+    let v = vec![1, 2, 3, 4, 5];
+    let v = &v[1..3];
+    assert_eq!(v.len(), 2);
+    assert_eq!(v[0], 2);
+    assert_eq!(v[1], 3);
+}
+
+macro_rules! assert_order {
+    (Greater, $a:expr, $b:expr) => {
+        assert_eq!($a.cmp($b), Greater);
+        assert!($a > $b);
+    };
+    (Less, $a:expr, $b:expr) => {
+        assert_eq!($a.cmp($b), Less);
+        assert!($a < $b);
+    };
+    (Equal, $a:expr, $b:expr) => {
+        assert_eq!($a.cmp($b), Equal);
+        assert_eq!($a, $b);
+    }
+}
+
+#[test]
+fn test_total_ord_u8() {
+    let c = &[1u8, 2, 3];
+    assert_order!(Greater, &[1u8, 2, 3, 4][..], &c[..]);
+    let c = &[1u8, 2, 3, 4];
+    assert_order!(Less, &[1u8, 2, 3][..], &c[..]);
+    let c = &[1u8, 2, 3, 6];
+    assert_order!(Equal, &[1u8, 2, 3, 6][..], &c[..]);
+    let c = &[1u8, 2, 3, 4, 5, 6];
+    assert_order!(Less, &[1u8, 2, 3, 4, 5, 5, 5, 5][..], &c[..]);
+    let c = &[1u8, 2, 3, 4];
+    assert_order!(Greater, &[2u8, 2][..], &c[..]);
+}
+
+
+#[test]
+fn test_total_ord_i32() {
+    let c = &[1, 2, 3];
+    assert_order!(Greater, &[1, 2, 3, 4][..], &c[..]);
+    let c = &[1, 2, 3, 4];
+    assert_order!(Less, &[1, 2, 3][..], &c[..]);
+    let c = &[1, 2, 3, 6];
+    assert_order!(Equal, &[1, 2, 3, 6][..], &c[..]);
+    let c = &[1, 2, 3, 4, 5, 6];
+    assert_order!(Less, &[1, 2, 3, 4, 5, 5, 5, 5][..], &c[..]);
+    let c = &[1, 2, 3, 4];
+    assert_order!(Greater, &[2, 2][..], &c[..]);
+}
+
+#[test]
+fn test_iterator() {
+    let xs = [1, 2, 5, 10, 11];
+    let mut it = xs.iter();
+    assert_eq!(it.size_hint(), (5, Some(5)));
+    assert_eq!(it.next().unwrap(), &1);
+    assert_eq!(it.size_hint(), (4, Some(4)));
+    assert_eq!(it.next().unwrap(), &2);
+    assert_eq!(it.size_hint(), (3, Some(3)));
+    assert_eq!(it.next().unwrap(), &5);
+    assert_eq!(it.size_hint(), (2, Some(2)));
+    assert_eq!(it.next().unwrap(), &10);
+    assert_eq!(it.size_hint(), (1, Some(1)));
+    assert_eq!(it.next().unwrap(), &11);
+    assert_eq!(it.size_hint(), (0, Some(0)));
+    assert!(it.next().is_none());
+}
+
+#[test]
+fn test_iter_size_hints() {
+    let mut xs = [1, 2, 5, 10, 11];
+    assert_eq!(xs.iter().size_hint(), (5, Some(5)));
+    assert_eq!(xs.iter_mut().size_hint(), (5, Some(5)));
+}
+
+#[test]
+fn test_iter_as_slice() {
+    let xs = [1, 2, 5, 10, 11];
+    let mut iter = xs.iter();
+    assert_eq!(iter.as_slice(), &[1, 2, 5, 10, 11]);
+    iter.next();
+    assert_eq!(iter.as_slice(), &[2, 5, 10, 11]);
+}
+
+#[test]
+fn test_iter_as_ref() {
+    let xs = [1, 2, 5, 10, 11];
+    let mut iter = xs.iter();
+    assert_eq!(iter.as_ref(), &[1, 2, 5, 10, 11]);
+    iter.next();
+    assert_eq!(iter.as_ref(), &[2, 5, 10, 11]);
+}
+
+#[test]
+fn test_iter_clone() {
+    let xs = [1, 2, 5];
+    let mut it = xs.iter();
+    it.next();
+    let mut jt = it.clone();
+    assert_eq!(it.next(), jt.next());
+    assert_eq!(it.next(), jt.next());
+    assert_eq!(it.next(), jt.next());
+}
+
+#[test]
+fn test_iter_is_empty() {
+    let xs = [1, 2, 5, 10, 11];
+    for i in 0..xs.len() {
+        for j in i..xs.len() {
+            assert_eq!(xs[i..j].iter().is_empty(), xs[i..j].is_empty());
+        }
+    }
+}
+
+#[test]
+fn test_mut_iterator() {
+    let mut xs = [1, 2, 3, 4, 5];
+    for x in &mut xs {
+        *x += 1;
+    }
+    assert!(xs == [2, 3, 4, 5, 6])
+}
+
+#[test]
+fn test_rev_iterator() {
+
+    let xs = [1, 2, 5, 10, 11];
+    let ys = [11, 10, 5, 2, 1];
+    let mut i = 0;
+    for &x in xs.iter().rev() {
+        assert_eq!(x, ys[i]);
+        i += 1;
+    }
+    assert_eq!(i, 5);
+}
+
+#[test]
+fn test_mut_rev_iterator() {
+    let mut xs = [1, 2, 3, 4, 5];
+    for (i, x) in xs.iter_mut().rev().enumerate() {
+        *x += i;
+    }
+    assert!(xs == [5, 5, 5, 5, 5])
+}
+
+#[test]
+fn test_move_iterator() {
+    let xs = vec![1, 2, 3, 4, 5];
+    assert_eq!(xs.into_iter().fold(0, |a: usize, b: usize| 10 * a + b),
+               12345);
+}
+
+#[test]
+fn test_move_rev_iterator() {
+    let xs = vec![1, 2, 3, 4, 5];
+    assert_eq!(xs.into_iter().rev().fold(0, |a: usize, b: usize| 10 * a + b),
+               54321);
+}
+
+#[test]
+fn test_splitator() {
+    let xs = &[1, 2, 3, 4, 5];
+
+    let splits: &[&[_]] = &[&[1], &[3], &[5]];
+    assert_eq!(xs.split(|x| *x % 2 == 0).collect::<Vec<_>>(), splits);
+    let splits: &[&[_]] = &[&[], &[2, 3, 4, 5]];
+    assert_eq!(xs.split(|x| *x == 1).collect::<Vec<_>>(), splits);
+    let splits: &[&[_]] = &[&[1, 2, 3, 4], &[]];
+    assert_eq!(xs.split(|x| *x == 5).collect::<Vec<_>>(), splits);
+    let splits: &[&[_]] = &[&[1, 2, 3, 4, 5]];
+    assert_eq!(xs.split(|x| *x == 10).collect::<Vec<_>>(), splits);
+    let splits: &[&[_]] = &[&[], &[], &[], &[], &[], &[]];
+    assert_eq!(xs.split(|_| true).collect::<Vec<&[i32]>>(), splits);
+
+    let xs: &[i32] = &[];
+    let splits: &[&[i32]] = &[&[]];
+    assert_eq!(xs.split(|x| *x == 5).collect::<Vec<&[i32]>>(), splits);
+}
+
+#[test]
+fn test_splitnator() {
+    let xs = &[1, 2, 3, 4, 5];
+
+    let splits: &[&[_]] = &[&[1, 2, 3, 4, 5]];
+    assert_eq!(xs.splitn(1, |x| *x % 2 == 0).collect::<Vec<_>>(), splits);
+    let splits: &[&[_]] = &[&[1], &[3, 4, 5]];
+    assert_eq!(xs.splitn(2, |x| *x % 2 == 0).collect::<Vec<_>>(), splits);
+    let splits: &[&[_]] = &[&[], &[], &[], &[4, 5]];
+    assert_eq!(xs.splitn(4, |_| true).collect::<Vec<_>>(), splits);
+
+    let xs: &[i32] = &[];
+    let splits: &[&[i32]] = &[&[]];
+    assert_eq!(xs.splitn(2, |x| *x == 5).collect::<Vec<_>>(), splits);
+}
+
+#[test]
+fn test_splitnator_mut() {
+    let xs = &mut [1, 2, 3, 4, 5];
+
+    let splits: &[&mut [_]] = &[&mut [1, 2, 3, 4, 5]];
+    assert_eq!(xs.splitn_mut(1, |x| *x % 2 == 0).collect::<Vec<_>>(),
+               splits);
+    let splits: &[&mut [_]] = &[&mut [1], &mut [3, 4, 5]];
+    assert_eq!(xs.splitn_mut(2, |x| *x % 2 == 0).collect::<Vec<_>>(),
+               splits);
+    let splits: &[&mut [_]] = &[&mut [], &mut [], &mut [], &mut [4, 5]];
+    assert_eq!(xs.splitn_mut(4, |_| true).collect::<Vec<_>>(), splits);
+
+    let xs: &mut [i32] = &mut [];
+    let splits: &[&mut [i32]] = &[&mut []];
+    assert_eq!(xs.splitn_mut(2, |x| *x == 5).collect::<Vec<_>>(), splits);
+}
+
+#[test]
+fn test_rsplitator() {
+    let xs = &[1, 2, 3, 4, 5];
+
+    let splits: &[&[_]] = &[&[5], &[3], &[1]];
+    assert_eq!(xs.split(|x| *x % 2 == 0).rev().collect::<Vec<_>>(), splits);
+    let splits: &[&[_]] = &[&[2, 3, 4, 5], &[]];
+    assert_eq!(xs.split(|x| *x == 1).rev().collect::<Vec<_>>(), splits);
+    let splits: &[&[_]] = &[&[], &[1, 2, 3, 4]];
+    assert_eq!(xs.split(|x| *x == 5).rev().collect::<Vec<_>>(), splits);
+    let splits: &[&[_]] = &[&[1, 2, 3, 4, 5]];
+    assert_eq!(xs.split(|x| *x == 10).rev().collect::<Vec<_>>(), splits);
+
+    let xs: &[i32] = &[];
+    let splits: &[&[i32]] = &[&[]];
+    assert_eq!(xs.split(|x| *x == 5).rev().collect::<Vec<&[i32]>>(), splits);
+}
+
+#[test]
+fn test_rsplitnator() {
+    let xs = &[1, 2, 3, 4, 5];
+
+    let splits: &[&[_]] = &[&[1, 2, 3, 4, 5]];
+    assert_eq!(xs.rsplitn(1, |x| *x % 2 == 0).collect::<Vec<_>>(), splits);
+    let splits: &[&[_]] = &[&[5], &[1, 2, 3]];
+    assert_eq!(xs.rsplitn(2, |x| *x % 2 == 0).collect::<Vec<_>>(), splits);
+    let splits: &[&[_]] = &[&[], &[], &[], &[1, 2]];
+    assert_eq!(xs.rsplitn(4, |_| true).collect::<Vec<_>>(), splits);
+
+    let xs: &[i32] = &[];
+    let splits: &[&[i32]] = &[&[]];
+    assert_eq!(xs.rsplitn(2, |x| *x == 5).collect::<Vec<&[i32]>>(), splits);
+    assert!(xs.rsplitn(0, |x| *x % 2 == 0).next().is_none());
+}
+
+#[test]
+fn test_windowsator() {
+    let v = &[1, 2, 3, 4];
+
+    let wins: &[&[_]] = &[&[1, 2], &[2, 3], &[3, 4]];
+    assert_eq!(v.windows(2).collect::<Vec<_>>(), wins);
+
+    let wins: &[&[_]] = &[&[1, 2, 3], &[2, 3, 4]];
+    assert_eq!(v.windows(3).collect::<Vec<_>>(), wins);
+    assert!(v.windows(6).next().is_none());
+
+    let wins: &[&[_]] = &[&[3, 4], &[2, 3], &[1, 2]];
+    assert_eq!(v.windows(2).rev().collect::<Vec<&[_]>>(), wins);
+}
+
+#[test]
+#[should_panic]
+fn test_windowsator_0() {
+    let v = &[1, 2, 3, 4];
+    let _it = v.windows(0);
+}
+
+#[test]
+fn test_chunksator() {
+    let v = &[1, 2, 3, 4, 5];
+
+    assert_eq!(v.chunks(2).len(), 3);
+
+    let chunks: &[&[_]] = &[&[1, 2], &[3, 4], &[5]];
+    assert_eq!(v.chunks(2).collect::<Vec<_>>(), chunks);
+    let chunks: &[&[_]] = &[&[1, 2, 3], &[4, 5]];
+    assert_eq!(v.chunks(3).collect::<Vec<_>>(), chunks);
+    let chunks: &[&[_]] = &[&[1, 2, 3, 4, 5]];
+    assert_eq!(v.chunks(6).collect::<Vec<_>>(), chunks);
+
+    let chunks: &[&[_]] = &[&[5], &[3, 4], &[1, 2]];
+    assert_eq!(v.chunks(2).rev().collect::<Vec<_>>(), chunks);
+}
+
+#[test]
+#[should_panic]
+fn test_chunksator_0() {
+    let v = &[1, 2, 3, 4];
+    let _it = v.chunks(0);
+}
+
+#[test]
+fn test_reverse_part() {
+    let mut values = [1, 2, 3, 4, 5];
+    values[1..4].reverse();
+    assert!(values == [1, 4, 3, 2, 5]);
+}
+
+#[test]
+fn test_show() {
+    macro_rules! test_show_vec {
+        ($x:expr, $x_str:expr) => ({
+            let (x, x_str) = ($x, $x_str);
+            assert_eq!(format!("{:?}", x), x_str);
+            assert_eq!(format!("{:?}", x), x_str);
+        })
+    }
+    let empty = Vec::<i32>::new();
+    test_show_vec!(empty, "[]");
+    test_show_vec!(vec![1], "[1]");
+    test_show_vec!(vec![1, 2, 3], "[1, 2, 3]");
+    test_show_vec!(vec![vec![], vec![1], vec![1, 1]], "[[], [1], [1, 1]]");
+
+    let empty_mut: &mut [i32] = &mut [];
+    test_show_vec!(empty_mut, "[]");
+    let v = &mut [1];
+    test_show_vec!(v, "[1]");
+    let v = &mut [1, 2, 3];
+    test_show_vec!(v, "[1, 2, 3]");
+    let v: &mut [&mut [_]] = &mut [&mut [], &mut [1], &mut [1, 1]];
+    test_show_vec!(v, "[[], [1], [1, 1]]");
+}
+
+#[test]
+fn test_vec_default() {
+    macro_rules! t {
+        ($ty:ty) => {{
+            let v: $ty = Default::default();
+            assert!(v.is_empty());
+        }}
+    }
+
+    t!(&[i32]);
+    t!(Vec<i32>);
+}
+
+#[test]
+#[should_panic]
+fn test_overflow_does_not_cause_segfault() {
+    let mut v = vec![];
+    v.reserve_exact(!0);
+    v.push(1);
+    v.push(2);
+}
+
+#[test]
+#[should_panic]
+fn test_overflow_does_not_cause_segfault_managed() {
+    let mut v = vec![Rc::new(1)];
+    v.reserve_exact(!0);
+    v.push(Rc::new(2));
+}
+
+#[test]
+fn test_mut_split_at() {
+    let mut values = [1, 2, 3, 4, 5];
+    {
+        let (left, right) = values.split_at_mut(2);
+        {
+            let left: &[_] = left;
+            assert!(left[..left.len()] == [1, 2]);
+        }
+        for p in left {
+            *p += 1;
+        }
+
+        {
+            let right: &[_] = right;
+            assert!(right[..right.len()] == [3, 4, 5]);
+        }
+        for p in right {
+            *p += 2;
+        }
+    }
+
+    assert!(values == [2, 3, 5, 6, 7]);
+}
+
+#[derive(Clone, PartialEq)]
+struct Foo;
+
+#[test]
+fn test_iter_zero_sized() {
+    let mut v = vec![Foo, Foo, Foo];
+    assert_eq!(v.len(), 3);
+    let mut cnt = 0;
+
+    for f in &v {
+        assert!(*f == Foo);
+        cnt += 1;
+    }
+    assert_eq!(cnt, 3);
+
+    for f in &v[1..3] {
+        assert!(*f == Foo);
+        cnt += 1;
+    }
+    assert_eq!(cnt, 5);
+
+    for f in &mut v {
+        assert!(*f == Foo);
+        cnt += 1;
+    }
+    assert_eq!(cnt, 8);
+
+    for f in v {
+        assert!(f == Foo);
+        cnt += 1;
+    }
+    assert_eq!(cnt, 11);
+
+    let xs: [Foo; 3] = [Foo, Foo, Foo];
+    cnt = 0;
+    for f in &xs {
+        assert!(*f == Foo);
+        cnt += 1;
+    }
+    assert!(cnt == 3);
+}
+
+#[test]
+fn test_shrink_to_fit() {
+    let mut xs = vec![0, 1, 2, 3];
+    for i in 4..100 {
+        xs.push(i)
+    }
+    assert_eq!(xs.capacity(), 128);
+    xs.shrink_to_fit();
+    assert_eq!(xs.capacity(), 100);
+    assert_eq!(xs, (0..100).collect::<Vec<_>>());
+}
+
+#[test]
+fn test_starts_with() {
+    assert!(b"foobar".starts_with(b"foo"));
+    assert!(!b"foobar".starts_with(b"oob"));
+    assert!(!b"foobar".starts_with(b"bar"));
+    assert!(!b"foo".starts_with(b"foobar"));
+    assert!(!b"bar".starts_with(b"foobar"));
+    assert!(b"foobar".starts_with(b"foobar"));
+    let empty: &[u8] = &[];
+    assert!(empty.starts_with(empty));
+    assert!(!empty.starts_with(b"foo"));
+    assert!(b"foobar".starts_with(empty));
+}
+
+#[test]
+fn test_ends_with() {
+    assert!(b"foobar".ends_with(b"bar"));
+    assert!(!b"foobar".ends_with(b"oba"));
+    assert!(!b"foobar".ends_with(b"foo"));
+    assert!(!b"foo".ends_with(b"foobar"));
+    assert!(!b"bar".ends_with(b"foobar"));
+    assert!(b"foobar".ends_with(b"foobar"));
+    let empty: &[u8] = &[];
+    assert!(empty.ends_with(empty));
+    assert!(!empty.ends_with(b"foo"));
+    assert!(b"foobar".ends_with(empty));
+}
+
+#[test]
+fn test_mut_splitator() {
+    let mut xs = [0, 1, 0, 2, 3, 0, 0, 4, 5, 0];
+    assert_eq!(xs.split_mut(|x| *x == 0).count(), 6);
+    for slice in xs.split_mut(|x| *x == 0) {
+        slice.reverse();
+    }
+    assert!(xs == [0, 1, 0, 3, 2, 0, 0, 5, 4, 0]);
+
+    let mut xs = [0, 1, 0, 2, 3, 0, 0, 4, 5, 0, 6, 7];
+    for slice in xs.split_mut(|x| *x == 0).take(5) {
+        slice.reverse();
+    }
+    assert!(xs == [0, 1, 0, 3, 2, 0, 0, 5, 4, 0, 6, 7]);
+}
+
+#[test]
+fn test_mut_splitator_rev() {
+    let mut xs = [1, 2, 0, 3, 4, 0, 0, 5, 6, 0];
+    for slice in xs.split_mut(|x| *x == 0).rev().take(4) {
+        slice.reverse();
+    }
+    assert!(xs == [1, 2, 0, 4, 3, 0, 0, 6, 5, 0]);
+}
+
+#[test]
+fn test_get_mut() {
+    let mut v = [0, 1, 2];
+    assert_eq!(v.get_mut(3), None);
+    v.get_mut(1).map(|e| *e = 7);
+    assert_eq!(v[1], 7);
+    let mut x = 2;
+    assert_eq!(v.get_mut(2), Some(&mut x));
+}
+
+#[test]
+fn test_mut_chunks() {
+    let mut v = [0, 1, 2, 3, 4, 5, 6];
+    assert_eq!(v.chunks_mut(2).len(), 4);
+    for (i, chunk) in v.chunks_mut(3).enumerate() {
+        for x in chunk {
+            *x = i as u8;
+        }
+    }
+    let result = [0, 0, 0, 1, 1, 1, 2];
+    assert!(v == result);
+}
+
+#[test]
+fn test_mut_chunks_rev() {
+    let mut v = [0, 1, 2, 3, 4, 5, 6];
+    for (i, chunk) in v.chunks_mut(3).rev().enumerate() {
+        for x in chunk {
+            *x = i as u8;
+        }
+    }
+    let result = [2, 2, 2, 1, 1, 1, 0];
+    assert!(v == result);
+}
+
+#[test]
+#[should_panic]
+fn test_mut_chunks_0() {
+    let mut v = [1, 2, 3, 4];
+    let _it = v.chunks_mut(0);
+}
+
+#[test]
+fn test_mut_last() {
+    let mut x = [1, 2, 3, 4, 5];
+    let h = x.last_mut();
+    assert_eq!(*h.unwrap(), 5);
+
+    let y: &mut [i32] = &mut [];
+    assert!(y.last_mut().is_none());
+}
+
+#[test]
+fn test_to_vec() {
+    let xs: Box<_> = box [1, 2, 3];
+    let ys = xs.to_vec();
+    assert_eq!(ys, [1, 2, 3]);
+}
+
+#[test]
+fn test_box_slice_clone() {
+    let data = vec![vec![0, 1], vec![0], vec![1]];
+    let data2 = data.clone().into_boxed_slice().clone().to_vec();
+
+    assert_eq!(data, data2);
+}
+
+#[test]
+#[cfg_attr(target_os = "emscripten", ignore)]
+fn test_box_slice_clone_panics() {
+    use std::sync::Arc;
+    use std::sync::atomic::{AtomicUsize, Ordering};
+    use std::thread::spawn;
+
+    struct Canary {
+        count: Arc<AtomicUsize>,
+        panics: bool,
+    }
+
+    impl Drop for Canary {
+        fn drop(&mut self) {
+            self.count.fetch_add(1, Ordering::SeqCst);
+        }
+    }
+
+    impl Clone for Canary {
+        fn clone(&self) -> Self {
+            if self.panics {
+                panic!()
+            }
+
+            Canary {
+                count: self.count.clone(),
+                panics: self.panics,
+            }
+        }
+    }
+
+    let drop_count = Arc::new(AtomicUsize::new(0));
+    let canary = Canary {
+        count: drop_count.clone(),
+        panics: false,
+    };
+    let panic = Canary {
+        count: drop_count.clone(),
+        panics: true,
+    };
+
+    spawn(move || {
+            // When xs is dropped, +5.
+            let xs = vec![canary.clone(), canary.clone(), canary.clone(), panic, canary]
+                .into_boxed_slice();
+
+            // When panic is cloned, +3.
+            xs.clone();
+        })
+        .join()
+        .unwrap_err();
+
+    // Total = 8
+    assert_eq!(drop_count.load(Ordering::SeqCst), 8);
+}
+
+#[test]
+fn test_copy_from_slice() {
+    let src = [0, 1, 2, 3, 4, 5];
+    let mut dst = [0; 6];
+    dst.copy_from_slice(&src);
+    assert_eq!(src, dst)
+}
+
+#[test]
+#[should_panic(expected = "destination and source slices have different lengths")]
+fn test_copy_from_slice_dst_longer() {
+    let src = [0, 1, 2, 3];
+    let mut dst = [0; 5];
+    dst.copy_from_slice(&src);
+}
+
+#[test]
+#[should_panic(expected = "destination and source slices have different lengths")]
+fn test_copy_from_slice_dst_shorter() {
+    let src = [0, 1, 2, 3];
+    let mut dst = [0; 3];
+    dst.copy_from_slice(&src);
+}
diff --git a/src/liballoc/tests/str.rs b/src/liballoc/tests/str.rs
new file mode 100644
index 00000000000..9d8ca38b20e
--- /dev/null
+++ b/src/liballoc/tests/str.rs
@@ -0,0 +1,1573 @@
+// Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use std::borrow::Cow;
+use std::cmp::Ordering::{Equal, Greater, Less};
+use std::str::from_utf8;
+
+#[test]
+fn test_le() {
+    assert!("" <= "");
+    assert!("" <= "foo");
+    assert!("foo" <= "foo");
+    assert!("foo" != "bar");
+}
+
+#[test]
+fn test_find() {
+    assert_eq!("hello".find('l'), Some(2));
+    assert_eq!("hello".find(|c:char| c == 'o'), Some(4));
+    assert!("hello".find('x').is_none());
+    assert!("hello".find(|c:char| c == 'x').is_none());
+    assert_eq!("ประเทศไทย中华Việt Nam".find('华'), Some(30));
+    assert_eq!("ประเทศไทย中华Việt Nam".find(|c: char| c == '华'), Some(30));
+}
+
+#[test]
+fn test_rfind() {
+    assert_eq!("hello".rfind('l'), Some(3));
+    assert_eq!("hello".rfind(|c:char| c == 'o'), Some(4));
+    assert!("hello".rfind('x').is_none());
+    assert!("hello".rfind(|c:char| c == 'x').is_none());
+    assert_eq!("ประเทศไทย中华Việt Nam".rfind('华'), Some(30));
+    assert_eq!("ประเทศไทย中华Việt Nam".rfind(|c: char| c == '华'), Some(30));
+}
+
+#[test]
+fn test_collect() {
+    let empty = "";
+    let s: String = empty.chars().collect();
+    assert_eq!(empty, s);
+    let data = "ประเทศไทย中";
+    let s: String = data.chars().collect();
+    assert_eq!(data, s);
+}
+
+#[test]
+fn test_into_bytes() {
+    let data = String::from("asdf");
+    let buf = data.into_bytes();
+    assert_eq!(buf, b"asdf");
+}
+
+#[test]
+fn test_find_str() {
+    // byte positions
+    assert_eq!("".find(""), Some(0));
+    assert!("banana".find("apple pie").is_none());
+
+    let data = "abcabc";
+    assert_eq!(data[0..6].find("ab"), Some(0));
+    assert_eq!(data[2..6].find("ab"), Some(3 - 2));
+    assert!(data[2..4].find("ab").is_none());
+
+    let string = "ประเทศไทย中华Việt Nam";
+    let mut data = String::from(string);
+    data.push_str(string);
+    assert!(data.find("ไท华").is_none());
+    assert_eq!(data[0..43].find(""), Some(0));
+    assert_eq!(data[6..43].find(""), Some(6 - 6));
+
+    assert_eq!(data[0..43].find("ประ"), Some( 0));
+    assert_eq!(data[0..43].find("ทศไ"), Some(12));
+    assert_eq!(data[0..43].find("ย中"), Some(24));
+    assert_eq!(data[0..43].find("iệt"), Some(34));
+    assert_eq!(data[0..43].find("Nam"), Some(40));
+
+    assert_eq!(data[43..86].find("ประ"), Some(43 - 43));
+    assert_eq!(data[43..86].find("ทศไ"), Some(55 - 43));
+    assert_eq!(data[43..86].find("ย中"), Some(67 - 43));
+    assert_eq!(data[43..86].find("iệt"), Some(77 - 43));
+    assert_eq!(data[43..86].find("Nam"), Some(83 - 43));
+
+    // find every substring -- assert that it finds it, or an earlier occurrence.
+    let string = "Việt Namacbaabcaabaaba";
+    for (i, ci) in string.char_indices() {
+        let ip = i + ci.len_utf8();
+        for j in string[ip..].char_indices()
+                             .map(|(i, _)| i)
+                             .chain(Some(string.len() - ip))
+        {
+            let pat = &string[i..ip + j];
+            assert!(match string.find(pat) {
+                None => false,
+                Some(x) => x <= i,
+            });
+            assert!(match string.rfind(pat) {
+                None => false,
+                Some(x) => x >= i,
+            });
+        }
+    }
+}
+
+fn s(x: &str) -> String { x.to_string() }
+
+macro_rules! test_concat {
+    ($expected: expr, $string: expr) => {
+        {
+            let s: String = $string.concat();
+            assert_eq!($expected, s);
+        }
+    }
+}
+
+#[test]
+fn test_concat_for_different_types() {
+    test_concat!("ab", vec![s("a"), s("b")]);
+    test_concat!("ab", vec!["a", "b"]);
+}
+
+#[test]
+fn test_concat_for_different_lengths() {
+    let empty: &[&str] = &[];
+    test_concat!("", empty);
+    test_concat!("a", ["a"]);
+    test_concat!("ab", ["a", "b"]);
+    test_concat!("abc", ["", "a", "bc"]);
+}
+
+macro_rules! test_join {
+    ($expected: expr, $string: expr, $delim: expr) => {
+        {
+            let s = $string.join($delim);
+            assert_eq!($expected, s);
+        }
+    }
+}
+
+#[test]
+fn test_join_for_different_types() {
+    test_join!("a-b", ["a", "b"], "-");
+    let hyphen = "-".to_string();
+    test_join!("a-b", [s("a"), s("b")], &*hyphen);
+    test_join!("a-b", vec!["a", "b"], &*hyphen);
+    test_join!("a-b", &*vec!["a", "b"], "-");
+    test_join!("a-b", vec![s("a"), s("b")], "-");
+}
+
+#[test]
+fn test_join_for_different_lengths() {
+    let empty: &[&str] = &[];
+    test_join!("", empty, "-");
+    test_join!("a", ["a"], "-");
+    test_join!("a-b", ["a", "b"], "-");
+    test_join!("-a-bc", ["", "a", "bc"], "-");
+}
+
+#[test]
+fn test_unsafe_slice() {
+    assert_eq!("ab", unsafe {"abc".slice_unchecked(0, 2)});
+    assert_eq!("bc", unsafe {"abc".slice_unchecked(1, 3)});
+    assert_eq!("", unsafe {"abc".slice_unchecked(1, 1)});
+    fn a_million_letter_a() -> String {
+        let mut i = 0;
+        let mut rs = String::new();
+        while i < 100000 {
+            rs.push_str("aaaaaaaaaa");
+            i += 1;
+        }
+        rs
+    }
+    fn half_a_million_letter_a() -> String {
+        let mut i = 0;
+        let mut rs = String::new();
+        while i < 100000 {
+            rs.push_str("aaaaa");
+            i += 1;
+        }
+        rs
+    }
+    let letters = a_million_letter_a();
+    assert_eq!(half_a_million_letter_a(),
+        unsafe { letters.slice_unchecked(0, 500000)});
+}
+
+#[test]
+fn test_starts_with() {
+    assert!("".starts_with(""));
+    assert!("abc".starts_with(""));
+    assert!("abc".starts_with("a"));
+    assert!(!"a".starts_with("abc"));
+    assert!(!"".starts_with("abc"));
+    assert!(!"ödd".starts_with("-"));
+    assert!("ödd".starts_with("öd"));
+}
+
+#[test]
+fn test_ends_with() {
+    assert!("".ends_with(""));
+    assert!("abc".ends_with(""));
+    assert!("abc".ends_with("c"));
+    assert!(!"a".ends_with("abc"));
+    assert!(!"".ends_with("abc"));
+    assert!(!"ddö".ends_with("-"));
+    assert!("ddö".ends_with("dö"));
+}
+
+#[test]
+fn test_is_empty() {
+    assert!("".is_empty());
+    assert!(!"a".is_empty());
+}
+
+#[test]
+fn test_replacen() {
+    assert_eq!("".replacen('a', "b", 5), "");
+    assert_eq!("acaaa".replacen("a", "b", 3), "bcbba");
+    assert_eq!("aaaa".replacen("a", "b", 0), "aaaa");
+
+    let test = "test";
+    assert_eq!(" test test ".replacen(test, "toast", 3), " toast toast ");
+    assert_eq!(" test test ".replacen(test, "toast", 0), " test test ");
+    assert_eq!(" test test ".replacen(test, "", 5), "   ");
+
+    assert_eq!("qwer123zxc789".replacen(char::is_numeric, "", 3), "qwerzxc789");
+}
+
+#[test]
+fn test_replace() {
+    let a = "a";
+    assert_eq!("".replace(a, "b"), "");
+    assert_eq!("a".replace(a, "b"), "b");
+    assert_eq!("ab".replace(a, "b"), "bb");
+    let test = "test";
+    assert_eq!(" test test ".replace(test, "toast"), " toast toast ");
+    assert_eq!(" test test ".replace(test, ""), "   ");
+}
+
+#[test]
+fn test_replace_2a() {
+    let data = "ประเทศไทย中华";
+    let repl = "دولة الكويت";
+
+    let a = "ประเ";
+    let a2 = "دولة الكويتทศไทย中华";
+    assert_eq!(data.replace(a, repl), a2);
+}
+
+#[test]
+fn test_replace_2b() {
+    let data = "ประเทศไทย中华";
+    let repl = "دولة الكويت";
+
+    let b = "ะเ";
+    let b2 = "ปรدولة الكويتทศไทย中华";
+    assert_eq!(data.replace(b, repl), b2);
+}
+
+#[test]
+fn test_replace_2c() {
+    let data = "ประเทศไทย中华";
+    let repl = "دولة الكويت";
+
+    let c = "中华";
+    let c2 = "ประเทศไทยدولة الكويت";
+    assert_eq!(data.replace(c, repl), c2);
+}
+
+#[test]
+fn test_replace_2d() {
+    let data = "ประเทศไทย中华";
+    let repl = "دولة الكويت";
+
+    let d = "ไท华";
+    assert_eq!(data.replace(d, repl), data);
+}
+
+#[test]
+fn test_replace_pattern() {
+    let data = "abcdαβγδabcdαβγδ";
+    assert_eq!(data.replace("dαβ", "😺😺😺"), "abc😺😺😺γδabc😺😺😺γδ");
+    assert_eq!(data.replace('γ', "😺😺😺"), "abcdαβ😺😺😺δabcdαβ😺😺😺δ");
+    assert_eq!(data.replace(&['a', 'γ'] as &[_], "😺😺😺"), "😺😺😺bcdαβ😺😺😺δ😺😺😺bcdαβ😺😺😺δ");
+    assert_eq!(data.replace(|c| c == 'γ', "😺😺😺"), "abcdαβ😺😺😺δabcdαβ😺😺😺δ");
+}
+
+#[test]
+fn test_slice() {
+    assert_eq!("ab", &"abc"[0..2]);
+    assert_eq!("bc", &"abc"[1..3]);
+    assert_eq!("", &"abc"[1..1]);
+    assert_eq!("\u{65e5}", &"\u{65e5}\u{672c}"[0..3]);
+
+    let data = "ประเทศไทย中华";
+    assert_eq!("ป", &data[0..3]);
+    assert_eq!("ร", &data[3..6]);
+    assert_eq!("", &data[3..3]);
+    assert_eq!("华", &data[30..33]);
+
+    fn a_million_letter_x() -> String {
+        let mut i = 0;
+        let mut rs = String::new();
+        while i < 100000 {
+            rs.push_str("华华华华华华华华华华");
+            i += 1;
+        }
+        rs
+    }
+    fn half_a_million_letter_x() -> String {
+        let mut i = 0;
+        let mut rs = String::new();
+        while i < 100000 {
+            rs.push_str("华华华华华");
+            i += 1;
+        }
+        rs
+    }
+    let letters = a_million_letter_x();
+    assert_eq!(half_a_million_letter_x(), &letters[0..3 * 500000]);
+}
+
+#[test]
+fn test_slice_2() {
+    let ss = "中华Việt Nam";
+
+    assert_eq!("华", &ss[3..6]);
+    assert_eq!("Việt Nam", &ss[6..16]);
+
+    assert_eq!("ab", &"abc"[0..2]);
+    assert_eq!("bc", &"abc"[1..3]);
+    assert_eq!("", &"abc"[1..1]);
+
+    assert_eq!("中", &ss[0..3]);
+    assert_eq!("华V", &ss[3..7]);
+    assert_eq!("", &ss[3..3]);
+    /*0: 中
+      3: 华
+      6: V
+      7: i
+      8: ệ
+     11: t
+     12:
+     13: N
+     14: a
+     15: m */
+}
+
+#[test]
+#[should_panic]
+fn test_slice_fail() {
+    &"中华Việt Nam"[0..2];
+}
+
+#[test]
+#[should_panic]
+fn test_str_slice_rangetoinclusive_max_panics() {
+    &"hello"[...usize::max_value()];
+}
+
+#[test]
+#[should_panic]
+fn test_str_slice_rangeinclusive_max_panics() {
+    &"hello"[1...usize::max_value()];
+}
+
+#[test]
+#[should_panic]
+fn test_str_slicemut_rangetoinclusive_max_panics() {
+    let mut s = "hello".to_owned();
+    let s: &mut str = &mut s;
+    &mut s[...usize::max_value()];
+}
+
+#[test]
+#[should_panic]
+fn test_str_slicemut_rangeinclusive_max_panics() {
+    let mut s = "hello".to_owned();
+    let s: &mut str = &mut s;
+    &mut s[1...usize::max_value()];
+}
+
+#[test]
+fn test_str_get_maxinclusive() {
+    let mut s = "hello".to_owned();
+    {
+        let s: &str = &s;
+        assert_eq!(s.get(...usize::max_value()), None);
+        assert_eq!(s.get(1...usize::max_value()), None);
+    }
+    {
+        let s: &mut str = &mut s;
+        assert_eq!(s.get(...usize::max_value()), None);
+        assert_eq!(s.get(1...usize::max_value()), None);
+    }
+}
+
+#[test]
+fn test_is_char_boundary() {
+    let s = "ศไทย中华Việt Nam β-release 🐱123";
+    assert!(s.is_char_boundary(0));
+    assert!(s.is_char_boundary(s.len()));
+    assert!(!s.is_char_boundary(s.len() + 1));
+    for (i, ch) in s.char_indices() {
+        // ensure character locations are boundaries and continuation bytes are not
+        assert!(s.is_char_boundary(i), "{} is a char boundary in {:?}", i, s);
+        for j in 1..ch.len_utf8() {
+            assert!(!s.is_char_boundary(i + j),
+                    "{} should not be a char boundary in {:?}", i + j, s);
+        }
+    }
+}
+const LOREM_PARAGRAPH: &'static str = "\
+Lorem ipsum dolor sit amet, consectetur adipiscing elit. Suspendisse quis lorem sit amet dolor \
+ultricies condimentum. Praesent iaculis purus elit, ac malesuada quam malesuada in. Duis sed orci \
+eros. Suspendisse sit amet magna mollis, mollis nunc luctus, imperdiet mi. Integer fringilla non \
+sem ut lacinia. Fusce varius tortor a risus porttitor hendrerit. Morbi mauris dui, ultricies nec \
+tempus vel, gravida nec quam.";
+
+// check the panic includes the prefix of the sliced string
+#[test]
+#[should_panic(expected="byte index 1024 is out of bounds of `Lorem ipsum dolor sit amet")]
+fn test_slice_fail_truncated_1() {
+    &LOREM_PARAGRAPH[..1024];
+}
+// check the truncation in the panic message
+#[test]
+#[should_panic(expected="luctus, im`[...]")]
+fn test_slice_fail_truncated_2() {
+    &LOREM_PARAGRAPH[..1024];
+}
+
+#[test]
+#[should_panic(expected="byte index 4 is not a char boundary; it is inside 'α' (bytes 3..5) of")]
+fn test_slice_fail_boundary_1() {
+    &"abcαβγ"[4..];
+}
+
+#[test]
+#[should_panic(expected="byte index 6 is not a char boundary; it is inside 'β' (bytes 5..7) of")]
+fn test_slice_fail_boundary_2() {
+    &"abcαβγ"[2..6];
+}
+
+#[test]
+fn test_slice_from() {
+    assert_eq!(&"abcd"[0..], "abcd");
+    assert_eq!(&"abcd"[2..], "cd");
+    assert_eq!(&"abcd"[4..], "");
+}
+#[test]
+fn test_slice_to() {
+    assert_eq!(&"abcd"[..0], "");
+    assert_eq!(&"abcd"[..2], "ab");
+    assert_eq!(&"abcd"[..4], "abcd");
+}
+
+#[test]
+fn test_trim_left_matches() {
+    let v: &[char] = &[];
+    assert_eq!(" *** foo *** ".trim_left_matches(v), " *** foo *** ");
+    let chars: &[char] = &['*', ' '];
+    assert_eq!(" *** foo *** ".trim_left_matches(chars), "foo *** ");
+    assert_eq!(" ***  *** ".trim_left_matches(chars), "");
+    assert_eq!("foo *** ".trim_left_matches(chars), "foo *** ");
+
+    assert_eq!("11foo1bar11".trim_left_matches('1'), "foo1bar11");
+    let chars: &[char] = &['1', '2'];
+    assert_eq!("12foo1bar12".trim_left_matches(chars), "foo1bar12");
+    assert_eq!("123foo1bar123".trim_left_matches(|c: char| c.is_numeric()), "foo1bar123");
+}
+
+#[test]
+fn test_trim_right_matches() {
+    let v: &[char] = &[];
+    assert_eq!(" *** foo *** ".trim_right_matches(v), " *** foo *** ");
+    let chars: &[char] = &['*', ' '];
+    assert_eq!(" *** foo *** ".trim_right_matches(chars), " *** foo");
+    assert_eq!(" ***  *** ".trim_right_matches(chars), "");
+    assert_eq!(" *** foo".trim_right_matches(chars), " *** foo");
+
+    assert_eq!("11foo1bar11".trim_right_matches('1'), "11foo1bar");
+    let chars: &[char] = &['1', '2'];
+    assert_eq!("12foo1bar12".trim_right_matches(chars), "12foo1bar");
+    assert_eq!("123foo1bar123".trim_right_matches(|c: char| c.is_numeric()), "123foo1bar");
+}
+
+#[test]
+fn test_trim_matches() {
+    let v: &[char] = &[];
+    assert_eq!(" *** foo *** ".trim_matches(v), " *** foo *** ");
+    let chars: &[char] = &['*', ' '];
+    assert_eq!(" *** foo *** ".trim_matches(chars), "foo");
+    assert_eq!(" ***  *** ".trim_matches(chars), "");
+    assert_eq!("foo".trim_matches(chars), "foo");
+
+    assert_eq!("11foo1bar11".trim_matches('1'), "foo1bar");
+    let chars: &[char] = &['1', '2'];
+    assert_eq!("12foo1bar12".trim_matches(chars), "foo1bar");
+    assert_eq!("123foo1bar123".trim_matches(|c: char| c.is_numeric()), "foo1bar");
+}
+
+#[test]
+fn test_trim_left() {
+    assert_eq!("".trim_left(), "");
+    assert_eq!("a".trim_left(), "a");
+    assert_eq!("    ".trim_left(), "");
+    assert_eq!("     blah".trim_left(), "blah");
+    assert_eq!("   \u{3000}  wut".trim_left(), "wut");
+    assert_eq!("hey ".trim_left(), "hey ");
+}
+
+#[test]
+fn test_trim_right() {
+    assert_eq!("".trim_right(), "");
+    assert_eq!("a".trim_right(), "a");
+    assert_eq!("    ".trim_right(), "");
+    assert_eq!("blah     ".trim_right(), "blah");
+    assert_eq!("wut   \u{3000}  ".trim_right(), "wut");
+    assert_eq!(" hey".trim_right(), " hey");
+}
+
+#[test]
+fn test_trim() {
+    assert_eq!("".trim(), "");
+    assert_eq!("a".trim(), "a");
+    assert_eq!("    ".trim(), "");
+    assert_eq!("    blah     ".trim(), "blah");
+    assert_eq!("\nwut   \u{3000}  ".trim(), "wut");
+    assert_eq!(" hey dude ".trim(), "hey dude");
+}
+
+#[test]
+fn test_is_whitespace() {
+    assert!("".chars().all(|c| c.is_whitespace()));
+    assert!(" ".chars().all(|c| c.is_whitespace()));
+    assert!("\u{2009}".chars().all(|c| c.is_whitespace())); // Thin space
+    assert!("  \n\t   ".chars().all(|c| c.is_whitespace()));
+    assert!(!"   _   ".chars().all(|c| c.is_whitespace()));
+}
+
+#[test]
+fn test_is_utf8() {
+    // deny overlong encodings
+    assert!(from_utf8(&[0xc0, 0x80]).is_err());
+    assert!(from_utf8(&[0xc0, 0xae]).is_err());
+    assert!(from_utf8(&[0xe0, 0x80, 0x80]).is_err());
+    assert!(from_utf8(&[0xe0, 0x80, 0xaf]).is_err());
+    assert!(from_utf8(&[0xe0, 0x81, 0x81]).is_err());
+    assert!(from_utf8(&[0xf0, 0x82, 0x82, 0xac]).is_err());
+    assert!(from_utf8(&[0xf4, 0x90, 0x80, 0x80]).is_err());
+
+    // deny surrogates
+    assert!(from_utf8(&[0xED, 0xA0, 0x80]).is_err());
+    assert!(from_utf8(&[0xED, 0xBF, 0xBF]).is_err());
+
+    assert!(from_utf8(&[0xC2, 0x80]).is_ok());
+    assert!(from_utf8(&[0xDF, 0xBF]).is_ok());
+    assert!(from_utf8(&[0xE0, 0xA0, 0x80]).is_ok());
+    assert!(from_utf8(&[0xED, 0x9F, 0xBF]).is_ok());
+    assert!(from_utf8(&[0xEE, 0x80, 0x80]).is_ok());
+    assert!(from_utf8(&[0xEF, 0xBF, 0xBF]).is_ok());
+    assert!(from_utf8(&[0xF0, 0x90, 0x80, 0x80]).is_ok());
+    assert!(from_utf8(&[0xF4, 0x8F, 0xBF, 0xBF]).is_ok());
+}
+
+#[test]
+fn from_utf8_mostly_ascii() {
+    // deny invalid bytes embedded in long stretches of ascii
+    for i in 32..64 {
+        let mut data = [0; 128];
+        data[i] = 0xC0;
+        assert!(from_utf8(&data).is_err());
+        data[i] = 0xC2;
+        assert!(from_utf8(&data).is_err());
+    }
+}
+
+#[test]
+fn from_utf8_error() {
+    macro_rules! test {
+        ($input: expr, $expected_valid_up_to: expr, $expected_error_len: expr) => {
+            let error = from_utf8($input).unwrap_err();
+            assert_eq!(error.valid_up_to(), $expected_valid_up_to);
+            assert_eq!(error.error_len(), $expected_error_len);
+        }
+    }
+    test!(b"A\xC3\xA9 \xFF ", 4, Some(1));
+    test!(b"A\xC3\xA9 \x80 ", 4, Some(1));
+    test!(b"A\xC3\xA9 \xC1 ", 4, Some(1));
+    test!(b"A\xC3\xA9 \xC1", 4, Some(1));
+    test!(b"A\xC3\xA9 \xC2", 4, None);
+    test!(b"A\xC3\xA9 \xC2 ", 4, Some(1));
+    test!(b"A\xC3\xA9 \xC2\xC0", 4, Some(1));
+    test!(b"A\xC3\xA9 \xE0", 4, None);
+    test!(b"A\xC3\xA9 \xE0\x9F", 4, Some(1));
+    test!(b"A\xC3\xA9 \xE0\xA0", 4, None);
+    test!(b"A\xC3\xA9 \xE0\xA0\xC0", 4, Some(2));
+    test!(b"A\xC3\xA9 \xE0\xA0 ", 4, Some(2));
+    test!(b"A\xC3\xA9 \xED\xA0\x80 ", 4, Some(1));
+    test!(b"A\xC3\xA9 \xF1", 4, None);
+    test!(b"A\xC3\xA9 \xF1\x80", 4, None);
+    test!(b"A\xC3\xA9 \xF1\x80\x80", 4, None);
+    test!(b"A\xC3\xA9 \xF1 ", 4, Some(1));
+    test!(b"A\xC3\xA9 \xF1\x80 ", 4, Some(2));
+    test!(b"A\xC3\xA9 \xF1\x80\x80 ", 4, Some(3));
+}
+
+#[test]
+fn test_as_bytes() {
+    // no null
+    let v = [
+        224, 184, 168, 224, 185, 132, 224, 184, 151, 224, 184, 162, 228,
+        184, 173, 229, 141, 142, 86, 105, 225, 187, 135, 116, 32, 78, 97,
+        109
+    ];
+    let b: &[u8] = &[];
+    assert_eq!("".as_bytes(), b);
+    assert_eq!("abc".as_bytes(), b"abc");
+    assert_eq!("ศไทย中华Việt Nam".as_bytes(), v);
+}
+
+#[test]
+#[should_panic]
+fn test_as_bytes_fail() {
+    // Don't double free. (I'm not sure if this exercises the
+    // original problem code path anymore.)
+    let s = String::from("");
+    let _bytes = s.as_bytes();
+    panic!();
+}
+
+#[test]
+fn test_as_ptr() {
+    let buf = "hello".as_ptr();
+    unsafe {
+        assert_eq!(*buf.offset(0), b'h');
+        assert_eq!(*buf.offset(1), b'e');
+        assert_eq!(*buf.offset(2), b'l');
+        assert_eq!(*buf.offset(3), b'l');
+        assert_eq!(*buf.offset(4), b'o');
+    }
+}
+
+#[test]
+fn vec_str_conversions() {
+    let s1: String = String::from("All mimsy were the borogoves");
+
+    let v: Vec<u8> = s1.as_bytes().to_vec();
+    let s2: String = String::from(from_utf8(&v).unwrap());
+    let mut i = 0;
+    let n1 = s1.len();
+    let n2 = v.len();
+    assert_eq!(n1, n2);
+    while i < n1 {
+        let a: u8 = s1.as_bytes()[i];
+        let b: u8 = s2.as_bytes()[i];
+        assert_eq!(a, b);
+        i += 1;
+    }
+}
+
+#[test]
+fn test_contains() {
+    assert!("abcde".contains("bcd"));
+    assert!("abcde".contains("abcd"));
+    assert!("abcde".contains("bcde"));
+    assert!("abcde".contains(""));
+    assert!("".contains(""));
+    assert!(!"abcde".contains("def"));
+    assert!(!"".contains("a"));
+
+    let data = "ประเทศไทย中华Việt Nam";
+    assert!(data.contains("ประเ"));
+    assert!(data.contains("ะเ"));
+    assert!(data.contains("中华"));
+    assert!(!data.contains("ไท华"));
+}
+
+#[test]
+fn test_contains_char() {
+    assert!("abc".contains('b'));
+    assert!("a".contains('a'));
+    assert!(!"abc".contains('d'));
+    assert!(!"".contains('a'));
+}
+
+#[test]
+fn test_split_at() {
+    let s = "ศไทย中华Việt Nam";
+    for (index, _) in s.char_indices() {
+        let (a, b) = s.split_at(index);
+        assert_eq!(&s[..a.len()], a);
+        assert_eq!(&s[a.len()..], b);
+    }
+    let (a, b) = s.split_at(s.len());
+    assert_eq!(a, s);
+    assert_eq!(b, "");
+}
+
+#[test]
+fn test_split_at_mut() {
+    use std::ascii::AsciiExt;
+    let mut s = "Hello World".to_string();
+    {
+        let (a, b) = s.split_at_mut(5);
+        a.make_ascii_uppercase();
+        b.make_ascii_lowercase();
+    }
+    assert_eq!(s, "HELLO world");
+}
+
+#[test]
+#[should_panic]
+fn test_split_at_boundscheck() {
+    let s = "ศไทย中华Việt Nam";
+    s.split_at(1);
+}
+
+#[test]
+fn test_escape_unicode() {
+    assert_eq!("abc".escape_unicode(), "\\u{61}\\u{62}\\u{63}");
+    assert_eq!("a c".escape_unicode(), "\\u{61}\\u{20}\\u{63}");
+    assert_eq!("\r\n\t".escape_unicode(), "\\u{d}\\u{a}\\u{9}");
+    assert_eq!("'\"\\".escape_unicode(), "\\u{27}\\u{22}\\u{5c}");
+    assert_eq!("\x00\x01\u{fe}\u{ff}".escape_unicode(), "\\u{0}\\u{1}\\u{fe}\\u{ff}");
+    assert_eq!("\u{100}\u{ffff}".escape_unicode(), "\\u{100}\\u{ffff}");
+    assert_eq!("\u{10000}\u{10ffff}".escape_unicode(), "\\u{10000}\\u{10ffff}");
+    assert_eq!("ab\u{fb00}".escape_unicode(), "\\u{61}\\u{62}\\u{fb00}");
+    assert_eq!("\u{1d4ea}\r".escape_unicode(), "\\u{1d4ea}\\u{d}");
+}
+
+#[test]
+fn test_escape_debug() {
+    assert_eq!("abc".escape_debug(), "abc");
+    assert_eq!("a c".escape_debug(), "a c");
+    assert_eq!("éèê".escape_debug(), "éèê");
+    assert_eq!("\r\n\t".escape_debug(), "\\r\\n\\t");
+    assert_eq!("'\"\\".escape_debug(), "\\'\\\"\\\\");
+    assert_eq!("\u{7f}\u{ff}".escape_debug(), "\\u{7f}\u{ff}");
+    assert_eq!("\u{100}\u{ffff}".escape_debug(), "\u{100}\\u{ffff}");
+    assert_eq!("\u{10000}\u{10ffff}".escape_debug(), "\u{10000}\\u{10ffff}");
+    assert_eq!("ab\u{200b}".escape_debug(), "ab\\u{200b}");
+    assert_eq!("\u{10d4ea}\r".escape_debug(), "\\u{10d4ea}\\r");
+}
+
+#[test]
+fn test_escape_default() {
+    assert_eq!("abc".escape_default(), "abc");
+    assert_eq!("a c".escape_default(), "a c");
+    assert_eq!("éèê".escape_default(), "\\u{e9}\\u{e8}\\u{ea}");
+    assert_eq!("\r\n\t".escape_default(), "\\r\\n\\t");
+    assert_eq!("'\"\\".escape_default(), "\\'\\\"\\\\");
+    assert_eq!("\u{7f}\u{ff}".escape_default(), "\\u{7f}\\u{ff}");
+    assert_eq!("\u{100}\u{ffff}".escape_default(), "\\u{100}\\u{ffff}");
+    assert_eq!("\u{10000}\u{10ffff}".escape_default(), "\\u{10000}\\u{10ffff}");
+    assert_eq!("ab\u{200b}".escape_default(), "ab\\u{200b}");
+    assert_eq!("\u{10d4ea}\r".escape_default(), "\\u{10d4ea}\\r");
+}
+
+#[test]
+fn test_total_ord() {
+    assert_eq!("1234".cmp("123"), Greater);
+    assert_eq!("123".cmp("1234"), Less);
+    assert_eq!("1234".cmp("1234"), Equal);
+    assert_eq!("12345555".cmp("123456"), Less);
+    assert_eq!("22".cmp("1234"), Greater);
+}
+
+#[test]
+fn test_iterator() {
+    let s = "ศไทย中华Việt Nam";
+    let v = ['ศ','ไ','ท','ย','中','华','V','i','ệ','t',' ','N','a','m'];
+
+    let mut pos = 0;
+    let it = s.chars();
+
+    for c in it {
+        assert_eq!(c, v[pos]);
+        pos += 1;
+    }
+    assert_eq!(pos, v.len());
+    assert_eq!(s.chars().count(), v.len());
+}
+
+#[test]
+fn test_rev_iterator() {
+    let s = "ศไทย中华Việt Nam";
+    let v = ['m', 'a', 'N', ' ', 't', 'ệ','i','V','华','中','ย','ท','ไ','ศ'];
+
+    let mut pos = 0;
+    let it = s.chars().rev();
+
+    for c in it {
+        assert_eq!(c, v[pos]);
+        pos += 1;
+    }
+    assert_eq!(pos, v.len());
+}
+
+#[test]
+fn test_chars_decoding() {
+    let mut bytes = [0; 4];
+    for c in (0..0x110000).filter_map(::std::char::from_u32) {
+        let s = c.encode_utf8(&mut bytes);
+        if Some(c) != s.chars().next() {
+            panic!("character {:x}={} does not decode correctly", c as u32, c);
+        }
+    }
+}
+
+#[test]
+fn test_chars_rev_decoding() {
+    let mut bytes = [0; 4];
+    for c in (0..0x110000).filter_map(::std::char::from_u32) {
+        let s = c.encode_utf8(&mut bytes);
+        if Some(c) != s.chars().rev().next() {
+            panic!("character {:x}={} does not decode correctly", c as u32, c);
+        }
+    }
+}
+
+#[test]
+fn test_iterator_clone() {
+    let s = "ศไทย中华Việt Nam";
+    let mut it = s.chars();
+    it.next();
+    assert!(it.clone().zip(it).all(|(x,y)| x == y));
+}
+
+#[test]
+fn test_iterator_last() {
+    let s = "ศไทย中华Việt Nam";
+    let mut it = s.chars();
+    it.next();
+    assert_eq!(it.last(), Some('m'));
+}
+
+#[test]
+fn test_bytesator() {
+    let s = "ศไทย中华Việt Nam";
+    let v = [
+        224, 184, 168, 224, 185, 132, 224, 184, 151, 224, 184, 162, 228,
+        184, 173, 229, 141, 142, 86, 105, 225, 187, 135, 116, 32, 78, 97,
+        109
+    ];
+    let mut pos = 0;
+
+    for b in s.bytes() {
+        assert_eq!(b, v[pos]);
+        pos += 1;
+    }
+}
+
+#[test]
+fn test_bytes_revator() {
+    let s = "ศไทย中华Việt Nam";
+    let v = [
+        224, 184, 168, 224, 185, 132, 224, 184, 151, 224, 184, 162, 228,
+        184, 173, 229, 141, 142, 86, 105, 225, 187, 135, 116, 32, 78, 97,
+        109
+    ];
+    let mut pos = v.len();
+
+    for b in s.bytes().rev() {
+        pos -= 1;
+        assert_eq!(b, v[pos]);
+    }
+}
+
+#[test]
+fn test_bytesator_nth() {
+    let s = "ศไทย中华Việt Nam";
+    let v = [
+        224, 184, 168, 224, 185, 132, 224, 184, 151, 224, 184, 162, 228,
+        184, 173, 229, 141, 142, 86, 105, 225, 187, 135, 116, 32, 78, 97,
+        109
+    ];
+
+    let mut b = s.bytes();
+    assert_eq!(b.nth(2).unwrap(), v[2]);
+    assert_eq!(b.nth(10).unwrap(), v[10]);
+    assert_eq!(b.nth(200), None);
+}
+
+#[test]
+fn test_bytesator_count() {
+    let s = "ศไทย中华Việt Nam";
+
+    let b = s.bytes();
+    assert_eq!(b.count(), 28)
+}
+
+#[test]
+fn test_bytesator_last() {
+    let s = "ศไทย中华Việt Nam";
+
+    let b = s.bytes();
+    assert_eq!(b.last().unwrap(), 109)
+}
+
+#[test]
+fn test_char_indicesator() {
+    let s = "ศไทย中华Việt Nam";
+    let p = [0, 3, 6, 9, 12, 15, 18, 19, 20, 23, 24, 25, 26, 27];
+    let v = ['ศ','ไ','ท','ย','中','华','V','i','ệ','t',' ','N','a','m'];
+
+    let mut pos = 0;
+    let it = s.char_indices();
+
+    for c in it {
+        assert_eq!(c, (p[pos], v[pos]));
+        pos += 1;
+    }
+    assert_eq!(pos, v.len());
+    assert_eq!(pos, p.len());
+}
+
+#[test]
+fn test_char_indices_revator() {
+    let s = "ศไทย中华Việt Nam";
+    let p = [27, 26, 25, 24, 23, 20, 19, 18, 15, 12, 9, 6, 3, 0];
+    let v = ['m', 'a', 'N', ' ', 't', 'ệ','i','V','华','中','ย','ท','ไ','ศ'];
+
+    let mut pos = 0;
+    let it = s.char_indices().rev();
+
+    for c in it {
+        assert_eq!(c, (p[pos], v[pos]));
+        pos += 1;
+    }
+    assert_eq!(pos, v.len());
+    assert_eq!(pos, p.len());
+}
+
+#[test]
+fn test_char_indices_last() {
+    let s = "ศไทย中华Việt Nam";
+    let mut it = s.char_indices();
+    it.next();
+    assert_eq!(it.last(), Some((27, 'm')));
+}
+
+#[test]
+fn test_splitn_char_iterator() {
+    let data = "\nMäry häd ä little lämb\nLittle lämb\n";
+
+    let split: Vec<&str> = data.splitn(4, ' ').collect();
+    assert_eq!(split, ["\nMäry", "häd", "ä", "little lämb\nLittle lämb\n"]);
+
+    let split: Vec<&str> = data.splitn(4, |c: char| c == ' ').collect();
+    assert_eq!(split, ["\nMäry", "häd", "ä", "little lämb\nLittle lämb\n"]);
+
+    // Unicode
+    let split: Vec<&str> = data.splitn(4, 'ä').collect();
+    assert_eq!(split, ["\nM", "ry h", "d ", " little lämb\nLittle lämb\n"]);
+
+    let split: Vec<&str> = data.splitn(4, |c: char| c == 'ä').collect();
+    assert_eq!(split, ["\nM", "ry h", "d ", " little lämb\nLittle lämb\n"]);
+}
+
+#[test]
+fn test_split_char_iterator_no_trailing() {
+    let data = "\nMäry häd ä little lämb\nLittle lämb\n";
+
+    let split: Vec<&str> = data.split('\n').collect();
+    assert_eq!(split, ["", "Märy häd ä little lämb", "Little lämb", ""]);
+
+    let split: Vec<&str> = data.split_terminator('\n').collect();
+    assert_eq!(split, ["", "Märy häd ä little lämb", "Little lämb"]);
+}
+
+#[test]
+fn test_rsplit() {
+    let data = "\nMäry häd ä little lämb\nLittle lämb\n";
+
+    let split: Vec<&str> = data.rsplit(' ').collect();
+    assert_eq!(split, ["lämb\n", "lämb\nLittle", "little", "ä", "häd", "\nMäry"]);
+
+    let split: Vec<&str> = data.rsplit("lämb").collect();
+    assert_eq!(split, ["\n", "\nLittle ", "\nMäry häd ä little "]);
+
+    let split: Vec<&str> = data.rsplit(|c: char| c == 'ä').collect();
+    assert_eq!(split, ["mb\n", "mb\nLittle l", " little l", "d ", "ry h", "\nM"]);
+}
+
+#[test]
+fn test_rsplitn() {
+    let data = "\nMäry häd ä little lämb\nLittle lämb\n";
+
+    let split: Vec<&str> = data.rsplitn(2, ' ').collect();
+    assert_eq!(split, ["lämb\n", "\nMäry häd ä little lämb\nLittle"]);
+
+    let split: Vec<&str> = data.rsplitn(2, "lämb").collect();
+    assert_eq!(split, ["\n", "\nMäry häd ä little lämb\nLittle "]);
+
+    let split: Vec<&str> = data.rsplitn(2, |c: char| c == 'ä').collect();
+    assert_eq!(split, ["mb\n", "\nMäry häd ä little lämb\nLittle l"]);
+}
+
+#[test]
+fn test_split_whitespace() {
+    let data = "\n \tMäry   häd\tä  little lämb\nLittle lämb\n";
+    let words: Vec<&str> = data.split_whitespace().collect();
+    assert_eq!(words, ["Märy", "häd", "ä", "little", "lämb", "Little", "lämb"])
+}
+
+#[test]
+fn test_lines() {
+    let data = "\nMäry häd ä little lämb\n\r\nLittle lämb\n";
+    let lines: Vec<&str> = data.lines().collect();
+    assert_eq!(lines, ["", "Märy häd ä little lämb", "", "Little lämb"]);
+
+    let data = "\r\nMäry häd ä little lämb\n\nLittle lämb"; // no trailing \n
+    let lines: Vec<&str> = data.lines().collect();
+    assert_eq!(lines, ["", "Märy häd ä little lämb", "", "Little lämb"]);
+}
+
+#[test]
+fn test_splitator() {
+    fn t(s: &str, sep: &str, u: &[&str]) {
+        let v: Vec<&str> = s.split(sep).collect();
+        assert_eq!(v, u);
+    }
+    t("--1233345--", "12345", &["--1233345--"]);
+    t("abc::hello::there", "::", &["abc", "hello", "there"]);
+    t("::hello::there", "::", &["", "hello", "there"]);
+    t("hello::there::", "::", &["hello", "there", ""]);
+    t("::hello::there::", "::", &["", "hello", "there", ""]);
+    t("ประเทศไทย中华Việt Nam", "中华", &["ประเทศไทย", "Việt Nam"]);
+    t("zzXXXzzYYYzz", "zz", &["", "XXX", "YYY", ""]);
+    t("zzXXXzYYYz", "XXX", &["zz", "zYYYz"]);
+    t(".XXX.YYY.", ".", &["", "XXX", "YYY", ""]);
+    t("", ".", &[""]);
+    t("zz", "zz", &["",""]);
+    t("ok", "z", &["ok"]);
+    t("zzz", "zz", &["","z"]);
+    t("zzzzz", "zz", &["","","z"]);
+}
+
+#[test]
+fn test_str_default() {
+    use std::default::Default;
+
+    fn t<S: Default + AsRef<str>>() {
+        let s: S = Default::default();
+        assert_eq!(s.as_ref(), "");
+    }
+
+    t::<&str>();
+    t::<String>();
+}
+
+#[test]
+fn test_str_container() {
+    fn sum_len(v: &[&str]) -> usize {
+        v.iter().map(|x| x.len()).sum()
+    }
+
+    let s = "01234";
+    assert_eq!(5, sum_len(&["012", "", "34"]));
+    assert_eq!(5, sum_len(&["01", "2", "34", ""]));
+    assert_eq!(5, sum_len(&[s]));
+}
+
+#[test]
+fn test_str_from_utf8() {
+    let xs = b"hello";
+    assert_eq!(from_utf8(xs), Ok("hello"));
+
+    let xs = "ศไทย中华Việt Nam".as_bytes();
+    assert_eq!(from_utf8(xs), Ok("ศไทย中华Việt Nam"));
+
+    let xs = b"hello\xFF";
+    assert!(from_utf8(xs).is_err());
+}
+
+#[test]
+fn test_pattern_deref_forward() {
+    let data = "aabcdaa";
+    assert!(data.contains("bcd"));
+    assert!(data.contains(&"bcd"));
+    assert!(data.contains(&"bcd".to_string()));
+}
+
+#[test]
+fn test_empty_match_indices() {
+    let data = "aä中!";
+    let vec: Vec<_> = data.match_indices("").collect();
+    assert_eq!(vec, [(0, ""), (1, ""), (3, ""), (6, ""), (7, "")]);
+}
+
+#[test]
+fn test_bool_from_str() {
+    assert_eq!("true".parse().ok(), Some(true));
+    assert_eq!("false".parse().ok(), Some(false));
+    assert_eq!("not even a boolean".parse::<bool>().ok(), None);
+}
+
+fn check_contains_all_substrings(s: &str) {
+    assert!(s.contains(""));
+    for i in 0..s.len() {
+        for j in i+1..s.len() + 1 {
+            assert!(s.contains(&s[i..j]));
+        }
+    }
+}
+
+#[test]
+fn strslice_issue_16589() {
+    assert!("bananas".contains("nana"));
+
+    // prior to the fix for #16589, x.contains("abcdabcd") returned false
+    // test all substrings for good measure
+    check_contains_all_substrings("012345678901234567890123456789bcdabcdabcd");
+}
+
+#[test]
+fn strslice_issue_16878() {
+    assert!(!"1234567ah012345678901ah".contains("hah"));
+    assert!(!"00abc01234567890123456789abc".contains("bcabc"));
+}
+
+
+#[test]
+fn test_strslice_contains() {
+    let x = "There are moments, Jeeves, when one asks oneself, 'Do trousers matter?'";
+    check_contains_all_substrings(x);
+}
+
+#[test]
+fn test_rsplitn_char_iterator() {
+    let data = "\nMäry häd ä little lämb\nLittle lämb\n";
+
+    let mut split: Vec<&str> = data.rsplitn(4, ' ').collect();
+    split.reverse();
+    assert_eq!(split, ["\nMäry häd ä", "little", "lämb\nLittle", "lämb\n"]);
+
+    let mut split: Vec<&str> = data.rsplitn(4, |c: char| c == ' ').collect();
+    split.reverse();
+    assert_eq!(split, ["\nMäry häd ä", "little", "lämb\nLittle", "lämb\n"]);
+
+    // Unicode
+    let mut split: Vec<&str> = data.rsplitn(4, 'ä').collect();
+    split.reverse();
+    assert_eq!(split, ["\nMäry häd ", " little l", "mb\nLittle l", "mb\n"]);
+
+    let mut split: Vec<&str> = data.rsplitn(4, |c: char| c == 'ä').collect();
+    split.reverse();
+    assert_eq!(split, ["\nMäry häd ", " little l", "mb\nLittle l", "mb\n"]);
+}
+
+#[test]
+fn test_split_char_iterator() {
+    let data = "\nMäry häd ä little lämb\nLittle lämb\n";
+
+    let split: Vec<&str> = data.split(' ').collect();
+    assert_eq!( split, ["\nMäry", "häd", "ä", "little", "lämb\nLittle", "lämb\n"]);
+
+    let mut rsplit: Vec<&str> = data.split(' ').rev().collect();
+    rsplit.reverse();
+    assert_eq!(rsplit, ["\nMäry", "häd", "ä", "little", "lämb\nLittle", "lämb\n"]);
+
+    let split: Vec<&str> = data.split(|c: char| c == ' ').collect();
+    assert_eq!( split, ["\nMäry", "häd", "ä", "little", "lämb\nLittle", "lämb\n"]);
+
+    let mut rsplit: Vec<&str> = data.split(|c: char| c == ' ').rev().collect();
+    rsplit.reverse();
+    assert_eq!(rsplit, ["\nMäry", "häd", "ä", "little", "lämb\nLittle", "lämb\n"]);
+
+    // Unicode
+    let split: Vec<&str> = data.split('ä').collect();
+    assert_eq!( split, ["\nM", "ry h", "d ", " little l", "mb\nLittle l", "mb\n"]);
+
+    let mut rsplit: Vec<&str> = data.split('ä').rev().collect();
+    rsplit.reverse();
+    assert_eq!(rsplit, ["\nM", "ry h", "d ", " little l", "mb\nLittle l", "mb\n"]);
+
+    let split: Vec<&str> = data.split(|c: char| c == 'ä').collect();
+    assert_eq!( split, ["\nM", "ry h", "d ", " little l", "mb\nLittle l", "mb\n"]);
+
+    let mut rsplit: Vec<&str> = data.split(|c: char| c == 'ä').rev().collect();
+    rsplit.reverse();
+    assert_eq!(rsplit, ["\nM", "ry h", "d ", " little l", "mb\nLittle l", "mb\n"]);
+}
+
+#[test]
+fn test_rev_split_char_iterator_no_trailing() {
+    let data = "\nMäry häd ä little lämb\nLittle lämb\n";
+
+    let mut split: Vec<&str> = data.split('\n').rev().collect();
+    split.reverse();
+    assert_eq!(split, ["", "Märy häd ä little lämb", "Little lämb", ""]);
+
+    let mut split: Vec<&str> = data.split_terminator('\n').rev().collect();
+    split.reverse();
+    assert_eq!(split, ["", "Märy häd ä little lämb", "Little lämb"]);
+}
+
+#[test]
+fn test_utf16_code_units() {
+    use std_unicode::str::Utf16Encoder;
+    assert_eq!(Utf16Encoder::new(vec!['é', '\u{1F4A9}'].into_iter()).collect::<Vec<u16>>(),
+               [0xE9, 0xD83D, 0xDCA9])
+}
+
+#[test]
+fn starts_with_in_unicode() {
+    assert!(!"├── Cargo.toml".starts_with("# "));
+}
+
+#[test]
+fn starts_short_long() {
+    assert!(!"".starts_with("##"));
+    assert!(!"##".starts_with("####"));
+    assert!("####".starts_with("##"));
+    assert!(!"##ä".starts_with("####"));
+    assert!("####ä".starts_with("##"));
+    assert!(!"##".starts_with("####ä"));
+    assert!("##ä##".starts_with("##ä"));
+
+    assert!("".starts_with(""));
+    assert!("ä".starts_with(""));
+    assert!("#ä".starts_with(""));
+    assert!("##ä".starts_with(""));
+    assert!("ä###".starts_with(""));
+    assert!("#ä##".starts_with(""));
+    assert!("##ä#".starts_with(""));
+}
+
+#[test]
+fn contains_weird_cases() {
+    assert!("* \t".contains(' '));
+    assert!(!"* \t".contains('?'));
+    assert!(!"* \t".contains('\u{1F4A9}'));
+}
+
+#[test]
+fn trim_ws() {
+    assert_eq!(" \t  a \t  ".trim_left_matches(|c: char| c.is_whitespace()),
+                    "a \t  ");
+    assert_eq!(" \t  a \t  ".trim_right_matches(|c: char| c.is_whitespace()),
+               " \t  a");
+    assert_eq!(" \t  a \t  ".trim_matches(|c: char| c.is_whitespace()),
+                    "a");
+    assert_eq!(" \t   \t  ".trim_left_matches(|c: char| c.is_whitespace()),
+                         "");
+    assert_eq!(" \t   \t  ".trim_right_matches(|c: char| c.is_whitespace()),
+               "");
+    assert_eq!(" \t   \t  ".trim_matches(|c: char| c.is_whitespace()),
+               "");
+}
+
+#[test]
+fn to_lowercase() {
+    assert_eq!("".to_lowercase(), "");
+    assert_eq!("AÉDžaé ".to_lowercase(), "aédžaé ");
+
+    // https://github.com/rust-lang/rust/issues/26035
+    assert_eq!("ΑΣ".to_lowercase(), "ας");
+    assert_eq!("Α'Σ".to_lowercase(), "α'ς");
+    assert_eq!("Α''Σ".to_lowercase(), "α''ς");
+
+    assert_eq!("ΑΣ Α".to_lowercase(), "ας α");
+    assert_eq!("Α'Σ Α".to_lowercase(), "α'ς α");
+    assert_eq!("Α''Σ Α".to_lowercase(), "α''ς α");
+
+    assert_eq!("ΑΣ' Α".to_lowercase(), "ας' α");
+    assert_eq!("ΑΣ'' Α".to_lowercase(), "ας'' α");
+
+    assert_eq!("Α'Σ' Α".to_lowercase(), "α'ς' α");
+    assert_eq!("Α''Σ'' Α".to_lowercase(), "α''ς'' α");
+
+    assert_eq!("Α Σ".to_lowercase(), "α σ");
+    assert_eq!("Α 'Σ".to_lowercase(), "α 'σ");
+    assert_eq!("Α ''Σ".to_lowercase(), "α ''σ");
+
+    assert_eq!("Σ".to_lowercase(), "σ");
+    assert_eq!("'Σ".to_lowercase(), "'σ");
+    assert_eq!("''Σ".to_lowercase(), "''σ");
+
+    assert_eq!("ΑΣΑ".to_lowercase(), "ασα");
+    assert_eq!("ΑΣ'Α".to_lowercase(), "ασ'α");
+    assert_eq!("ΑΣ''Α".to_lowercase(), "ασ''α");
+}
+
+#[test]
+fn to_uppercase() {
+    assert_eq!("".to_uppercase(), "");
+    assert_eq!("aéDžßfiᾀ".to_uppercase(), "AÉDŽSSFIἈΙ");
+}
+
+#[test]
+fn test_into_string() {
+    // The only way to acquire a Box<str> in the first place is through a String, so just
+    // test that we can round-trip between Box<str> and String.
+    let string = String::from("Some text goes here");
+    assert_eq!(string.clone().into_boxed_str().into_string(), string);
+}
+
+#[test]
+fn test_box_slice_clone() {
+    let data = String::from("hello HELLO hello HELLO yes YES 5 中ä华!!!");
+    let data2 = data.clone().into_boxed_str().clone().into_string();
+
+    assert_eq!(data, data2);
+}
+
+#[test]
+fn test_cow_from() {
+    let borrowed = "borrowed";
+    let owned = String::from("owned");
+    match (Cow::from(owned.clone()), Cow::from(borrowed)) {
+        (Cow::Owned(o), Cow::Borrowed(b)) => assert!(o == owned && b == borrowed),
+        _ => panic!("invalid `Cow::from`"),
+    }
+}
+
+#[test]
+fn test_repeat() {
+    assert_eq!("".repeat(3), "");
+    assert_eq!("abc".repeat(0), "");
+    assert_eq!("α".repeat(3), "ααα");
+}
+
+mod pattern {
+    use std::str::pattern::Pattern;
+    use std::str::pattern::{Searcher, ReverseSearcher};
+    use std::str::pattern::SearchStep::{self, Match, Reject, Done};
+
+    macro_rules! make_test {
+        ($name:ident, $p:expr, $h:expr, [$($e:expr,)*]) => {
+            #[allow(unused_imports)]
+            mod $name {
+                use std::str::pattern::SearchStep::{Match, Reject};
+                use super::{cmp_search_to_vec};
+                #[test]
+                fn fwd() {
+                    cmp_search_to_vec(false, $p, $h, vec![$($e),*]);
+                }
+                #[test]
+                fn bwd() {
+                    cmp_search_to_vec(true, $p, $h, vec![$($e),*]);
+                }
+            }
+        }
+    }
+
+    fn cmp_search_to_vec<'a, P: Pattern<'a>>(rev: bool, pat: P, haystack: &'a str,
+                                             right: Vec<SearchStep>)
+    where P::Searcher: ReverseSearcher<'a>
+    {
+        let mut searcher = pat.into_searcher(haystack);
+        let mut v = vec![];
+        loop {
+            match if !rev {searcher.next()} else {searcher.next_back()} {
+                Match(a, b) => v.push(Match(a, b)),
+                Reject(a, b) => v.push(Reject(a, b)),
+                Done => break,
+            }
+        }
+        if rev {
+            v.reverse();
+        }
+
+        let mut first_index = 0;
+        let mut err = None;
+
+        for (i, e) in right.iter().enumerate() {
+            match *e {
+                Match(a, b) | Reject(a, b)
+                if a <= b && a == first_index => {
+                    first_index = b;
+                }
+                _ => {
+                    err = Some(i);
+                    break;
+                }
+            }
+        }
+
+        if let Some(err) = err {
+            panic!("Input skipped range at {}", err);
+        }
+
+        if first_index != haystack.len() {
+            panic!("Did not cover whole input");
+        }
+
+        assert_eq!(v, right);
+    }
+
+    make_test!(str_searcher_ascii_haystack, "bb", "abbcbbd", [
+        Reject(0, 1),
+        Match (1, 3),
+        Reject(3, 4),
+        Match (4, 6),
+        Reject(6, 7),
+    ]);
+    make_test!(str_searcher_ascii_haystack_seq, "bb", "abbcbbbbd", [
+        Reject(0, 1),
+        Match (1, 3),
+        Reject(3, 4),
+        Match (4, 6),
+        Match (6, 8),
+        Reject(8, 9),
+    ]);
+    make_test!(str_searcher_empty_needle_ascii_haystack, "", "abbcbbd", [
+        Match (0, 0),
+        Reject(0, 1),
+        Match (1, 1),
+        Reject(1, 2),
+        Match (2, 2),
+        Reject(2, 3),
+        Match (3, 3),
+        Reject(3, 4),
+        Match (4, 4),
+        Reject(4, 5),
+        Match (5, 5),
+        Reject(5, 6),
+        Match (6, 6),
+        Reject(6, 7),
+        Match (7, 7),
+    ]);
+    make_test!(str_searcher_mulibyte_haystack, " ", "├──", [
+        Reject(0, 3),
+        Reject(3, 6),
+        Reject(6, 9),
+    ]);
+    make_test!(str_searcher_empty_needle_mulibyte_haystack, "", "├──", [
+        Match (0, 0),
+        Reject(0, 3),
+        Match (3, 3),
+        Reject(3, 6),
+        Match (6, 6),
+        Reject(6, 9),
+        Match (9, 9),
+    ]);
+    make_test!(str_searcher_empty_needle_empty_haystack, "", "", [
+        Match(0, 0),
+    ]);
+    make_test!(str_searcher_nonempty_needle_empty_haystack, "├", "", [
+    ]);
+    make_test!(char_searcher_ascii_haystack, 'b', "abbcbbd", [
+        Reject(0, 1),
+        Match (1, 2),
+        Match (2, 3),
+        Reject(3, 4),
+        Match (4, 5),
+        Match (5, 6),
+        Reject(6, 7),
+    ]);
+    make_test!(char_searcher_mulibyte_haystack, ' ', "├──", [
+        Reject(0, 3),
+        Reject(3, 6),
+        Reject(6, 9),
+    ]);
+    make_test!(char_searcher_short_haystack, '\u{1F4A9}', "* \t", [
+        Reject(0, 1),
+        Reject(1, 2),
+        Reject(2, 3),
+    ]);
+
+}
+
+macro_rules! generate_iterator_test {
+    {
+        $name:ident {
+            $(
+                ($($arg:expr),*) -> [$($t:tt)*];
+            )*
+        }
+        with $fwd:expr, $bwd:expr;
+    } => {
+        #[test]
+        fn $name() {
+            $(
+                {
+                    let res = vec![$($t)*];
+
+                    let fwd_vec: Vec<_> = ($fwd)($($arg),*).collect();
+                    assert_eq!(fwd_vec, res);
+
+                    let mut bwd_vec: Vec<_> = ($bwd)($($arg),*).collect();
+                    bwd_vec.reverse();
+                    assert_eq!(bwd_vec, res);
+                }
+            )*
+        }
+    };
+    {
+        $name:ident {
+            $(
+                ($($arg:expr),*) -> [$($t:tt)*];
+            )*
+        }
+        with $fwd:expr;
+    } => {
+        #[test]
+        fn $name() {
+            $(
+                {
+                    let res = vec![$($t)*];
+
+                    let fwd_vec: Vec<_> = ($fwd)($($arg),*).collect();
+                    assert_eq!(fwd_vec, res);
+                }
+            )*
+        }
+    }
+}
+
+generate_iterator_test! {
+    double_ended_split {
+        ("foo.bar.baz", '.') -> ["foo", "bar", "baz"];
+        ("foo::bar::baz", "::") -> ["foo", "bar", "baz"];
+    }
+    with str::split, str::rsplit;
+}
+
+generate_iterator_test! {
+    double_ended_split_terminator {
+        ("foo;bar;baz;", ';') -> ["foo", "bar", "baz"];
+    }
+    with str::split_terminator, str::rsplit_terminator;
+}
+
+generate_iterator_test! {
+    double_ended_matches {
+        ("a1b2c3", char::is_numeric) -> ["1", "2", "3"];
+    }
+    with str::matches, str::rmatches;
+}
+
+generate_iterator_test! {
+    double_ended_match_indices {
+        ("a1b2c3", char::is_numeric) -> [(1, "1"), (3, "2"), (5, "3")];
+    }
+    with str::match_indices, str::rmatch_indices;
+}
+
+generate_iterator_test! {
+    not_double_ended_splitn {
+        ("foo::bar::baz", 2, "::") -> ["foo", "bar::baz"];
+    }
+    with str::splitn;
+}
+
+generate_iterator_test! {
+    not_double_ended_rsplitn {
+        ("foo::bar::baz", 2, "::") -> ["baz", "foo::bar"];
+    }
+    with str::rsplitn;
+}
+
+#[test]
+fn different_str_pattern_forwarding_lifetimes() {
+    use std::str::pattern::Pattern;
+
+    fn foo<'a, P>(p: P) where for<'b> &'b P: Pattern<'a> {
+        for _ in 0..3 {
+            "asdf".find(&p);
+        }
+    }
+
+    foo::<&str>("x");
+}
diff --git a/src/liballoc/tests/string.rs b/src/liballoc/tests/string.rs
new file mode 100644
index 00000000000..b1731b2a5dc
--- /dev/null
+++ b/src/liballoc/tests/string.rs
@@ -0,0 +1,498 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use std::borrow::Cow;
+
+pub trait IntoCow<'a, B: ?Sized> where B: ToOwned {
+    fn into_cow(self) -> Cow<'a, B>;
+}
+
+impl<'a> IntoCow<'a, str> for String {
+    fn into_cow(self) -> Cow<'a, str> {
+        Cow::Owned(self)
+    }
+}
+
+impl<'a> IntoCow<'a, str> for &'a str {
+    fn into_cow(self) -> Cow<'a, str> {
+        Cow::Borrowed(self)
+    }
+}
+
+#[test]
+fn test_from_str() {
+    let owned: Option<::std::string::String> = "string".parse().ok();
+    assert_eq!(owned.as_ref().map(|s| &**s), Some("string"));
+}
+
+#[test]
+fn test_from_cow_str() {
+    assert_eq!(String::from(Cow::Borrowed("string")), "string");
+    assert_eq!(String::from(Cow::Owned(String::from("string"))), "string");
+}
+
+#[test]
+fn test_unsized_to_string() {
+    let s: &str = "abc";
+    let _: String = (*s).to_string();
+}
+
+#[test]
+fn test_from_utf8() {
+    let xs = b"hello".to_vec();
+    assert_eq!(String::from_utf8(xs).unwrap(), String::from("hello"));
+
+    let xs = "ศไทย中华Việt Nam".as_bytes().to_vec();
+    assert_eq!(String::from_utf8(xs).unwrap(),
+               String::from("ศไทย中华Việt Nam"));
+
+    let xs = b"hello\xFF".to_vec();
+    let err = String::from_utf8(xs).unwrap_err();
+    assert_eq!(err.into_bytes(), b"hello\xff".to_vec());
+}
+
+#[test]
+fn test_from_utf8_lossy() {
+    let xs = b"hello";
+    let ys: Cow<str> = "hello".into_cow();
+    assert_eq!(String::from_utf8_lossy(xs), ys);
+
+    let xs = "ศไทย中华Việt Nam".as_bytes();
+    let ys: Cow<str> = "ศไทย中华Việt Nam".into_cow();
+    assert_eq!(String::from_utf8_lossy(xs), ys);
+
+    let xs = b"Hello\xC2 There\xFF Goodbye";
+    assert_eq!(String::from_utf8_lossy(xs),
+               String::from("Hello\u{FFFD} There\u{FFFD} Goodbye").into_cow());
+
+    let xs = b"Hello\xC0\x80 There\xE6\x83 Goodbye";
+    assert_eq!(String::from_utf8_lossy(xs),
+               String::from("Hello\u{FFFD}\u{FFFD} There\u{FFFD} Goodbye").into_cow());
+
+    let xs = b"\xF5foo\xF5\x80bar";
+    assert_eq!(String::from_utf8_lossy(xs),
+               String::from("\u{FFFD}foo\u{FFFD}\u{FFFD}bar").into_cow());
+
+    let xs = b"\xF1foo\xF1\x80bar\xF1\x80\x80baz";
+    assert_eq!(String::from_utf8_lossy(xs),
+               String::from("\u{FFFD}foo\u{FFFD}bar\u{FFFD}baz").into_cow());
+
+    let xs = b"\xF4foo\xF4\x80bar\xF4\xBFbaz";
+    assert_eq!(String::from_utf8_lossy(xs),
+               String::from("\u{FFFD}foo\u{FFFD}bar\u{FFFD}\u{FFFD}baz").into_cow());
+
+    let xs = b"\xF0\x80\x80\x80foo\xF0\x90\x80\x80bar";
+    assert_eq!(String::from_utf8_lossy(xs),
+               String::from("\u{FFFD}\u{FFFD}\u{FFFD}\u{FFFD}foo\u{10000}bar").into_cow());
+
+    // surrogates
+    let xs = b"\xED\xA0\x80foo\xED\xBF\xBFbar";
+    assert_eq!(String::from_utf8_lossy(xs),
+               String::from("\u{FFFD}\u{FFFD}\u{FFFD}foo\u{FFFD}\u{FFFD}\u{FFFD}bar").into_cow());
+}
+
+#[test]
+fn test_from_utf16() {
+    let pairs = [(String::from("𐍅𐌿𐌻𐍆𐌹𐌻𐌰\n"),
+                  vec![0xd800, 0xdf45, 0xd800, 0xdf3f, 0xd800, 0xdf3b, 0xd800, 0xdf46, 0xd800,
+                       0xdf39, 0xd800, 0xdf3b, 0xd800, 0xdf30, 0x000a]),
+
+                 (String::from("𐐒𐑉𐐮𐑀𐐲𐑋 𐐏𐐲𐑍\n"),
+                  vec![0xd801, 0xdc12, 0xd801, 0xdc49, 0xd801, 0xdc2e, 0xd801, 0xdc40, 0xd801,
+                       0xdc32, 0xd801, 0xdc4b, 0x0020, 0xd801, 0xdc0f, 0xd801, 0xdc32, 0xd801,
+                       0xdc4d, 0x000a]),
+
+                 (String::from("𐌀𐌖𐌋𐌄𐌑𐌉·𐌌𐌄𐌕𐌄𐌋𐌉𐌑\n"),
+                  vec![0xd800, 0xdf00, 0xd800, 0xdf16, 0xd800, 0xdf0b, 0xd800, 0xdf04, 0xd800,
+                       0xdf11, 0xd800, 0xdf09, 0x00b7, 0xd800, 0xdf0c, 0xd800, 0xdf04, 0xd800,
+                       0xdf15, 0xd800, 0xdf04, 0xd800, 0xdf0b, 0xd800, 0xdf09, 0xd800, 0xdf11,
+                       0x000a]),
+
+                 (String::from("𐒋𐒘𐒈𐒑𐒛𐒒 𐒕𐒓 𐒈𐒚𐒍 𐒏𐒜𐒒𐒖𐒆 𐒕𐒆\n"),
+                  vec![0xd801, 0xdc8b, 0xd801, 0xdc98, 0xd801, 0xdc88, 0xd801, 0xdc91, 0xd801,
+                       0xdc9b, 0xd801, 0xdc92, 0x0020, 0xd801, 0xdc95, 0xd801, 0xdc93, 0x0020,
+                       0xd801, 0xdc88, 0xd801, 0xdc9a, 0xd801, 0xdc8d, 0x0020, 0xd801, 0xdc8f,
+                       0xd801, 0xdc9c, 0xd801, 0xdc92, 0xd801, 0xdc96, 0xd801, 0xdc86, 0x0020,
+                       0xd801, 0xdc95, 0xd801, 0xdc86, 0x000a]),
+                 // Issue #12318, even-numbered non-BMP planes
+                 (String::from("\u{20000}"), vec![0xD840, 0xDC00])];
+
+    for p in &pairs {
+        let (s, u) = (*p).clone();
+        let s_as_utf16 = s.encode_utf16().collect::<Vec<u16>>();
+        let u_as_string = String::from_utf16(&u).unwrap();
+
+        assert!(::std_unicode::char::decode_utf16(u.iter().cloned()).all(|r| r.is_ok()));
+        assert_eq!(s_as_utf16, u);
+
+        assert_eq!(u_as_string, s);
+        assert_eq!(String::from_utf16_lossy(&u), s);
+
+        assert_eq!(String::from_utf16(&s_as_utf16).unwrap(), s);
+        assert_eq!(u_as_string.encode_utf16().collect::<Vec<u16>>(), u);
+    }
+}
+
+#[test]
+fn test_utf16_invalid() {
+    // completely positive cases tested above.
+    // lead + eof
+    assert!(String::from_utf16(&[0xD800]).is_err());
+    // lead + lead
+    assert!(String::from_utf16(&[0xD800, 0xD800]).is_err());
+
+    // isolated trail
+    assert!(String::from_utf16(&[0x0061, 0xDC00]).is_err());
+
+    // general
+    assert!(String::from_utf16(&[0xD800, 0xd801, 0xdc8b, 0xD800]).is_err());
+}
+
+#[test]
+fn test_from_utf16_lossy() {
+    // completely positive cases tested above.
+    // lead + eof
+    assert_eq!(String::from_utf16_lossy(&[0xD800]),
+               String::from("\u{FFFD}"));
+    // lead + lead
+    assert_eq!(String::from_utf16_lossy(&[0xD800, 0xD800]),
+               String::from("\u{FFFD}\u{FFFD}"));
+
+    // isolated trail
+    assert_eq!(String::from_utf16_lossy(&[0x0061, 0xDC00]),
+               String::from("a\u{FFFD}"));
+
+    // general
+    assert_eq!(String::from_utf16_lossy(&[0xD800, 0xd801, 0xdc8b, 0xD800]),
+               String::from("\u{FFFD}𐒋\u{FFFD}"));
+}
+
+#[test]
+fn test_push_bytes() {
+    let mut s = String::from("ABC");
+    unsafe {
+        let mv = s.as_mut_vec();
+        mv.extend_from_slice(&[b'D']);
+    }
+    assert_eq!(s, "ABCD");
+}
+
+#[test]
+fn test_push_str() {
+    let mut s = String::new();
+    s.push_str("");
+    assert_eq!(&s[0..], "");
+    s.push_str("abc");
+    assert_eq!(&s[0..], "abc");
+    s.push_str("ประเทศไทย中华Việt Nam");
+    assert_eq!(&s[0..], "abcประเทศไทย中华Việt Nam");
+}
+
+#[test]
+fn test_add_assign() {
+    let mut s = String::new();
+    s += "";
+    assert_eq!(s.as_str(), "");
+    s += "abc";
+    assert_eq!(s.as_str(), "abc");
+    s += "ประเทศไทย中华Việt Nam";
+    assert_eq!(s.as_str(), "abcประเทศไทย中华Việt Nam");
+}
+
+#[test]
+fn test_push() {
+    let mut data = String::from("ประเทศไทย中");
+    data.push('华');
+    data.push('b'); // 1 byte
+    data.push('¢'); // 2 byte
+    data.push('€'); // 3 byte
+    data.push('𤭢'); // 4 byte
+    assert_eq!(data, "ประเทศไทย中华b¢€𤭢");
+}
+
+#[test]
+fn test_pop() {
+    let mut data = String::from("ประเทศไทย中华b¢€𤭢");
+    assert_eq!(data.pop().unwrap(), '𤭢'); // 4 bytes
+    assert_eq!(data.pop().unwrap(), '€'); // 3 bytes
+    assert_eq!(data.pop().unwrap(), '¢'); // 2 bytes
+    assert_eq!(data.pop().unwrap(), 'b'); // 1 bytes
+    assert_eq!(data.pop().unwrap(), '华');
+    assert_eq!(data, "ประเทศไทย中");
+}
+
+#[test]
+fn test_split_off_empty() {
+    let orig = "Hello, world!";
+    let mut split = String::from(orig);
+    let empty: String = split.split_off(orig.len());
+    assert!(empty.is_empty());
+}
+
+#[test]
+#[should_panic]
+fn test_split_off_past_end() {
+    let orig = "Hello, world!";
+    let mut split = String::from(orig);
+    split.split_off(orig.len() + 1);
+}
+
+#[test]
+#[should_panic]
+fn test_split_off_mid_char() {
+    let mut orig = String::from("山");
+    orig.split_off(1);
+}
+
+#[test]
+fn test_split_off_ascii() {
+    let mut ab = String::from("ABCD");
+    let cd = ab.split_off(2);
+    assert_eq!(ab, "AB");
+    assert_eq!(cd, "CD");
+}
+
+#[test]
+fn test_split_off_unicode() {
+    let mut nihon = String::from("日本語");
+    let go = nihon.split_off("日本".len());
+    assert_eq!(nihon, "日本");
+    assert_eq!(go, "語");
+}
+
+#[test]
+fn test_str_truncate() {
+    let mut s = String::from("12345");
+    s.truncate(5);
+    assert_eq!(s, "12345");
+    s.truncate(3);
+    assert_eq!(s, "123");
+    s.truncate(0);
+    assert_eq!(s, "");
+
+    let mut s = String::from("12345");
+    let p = s.as_ptr();
+    s.truncate(3);
+    s.push_str("6");
+    let p_ = s.as_ptr();
+    assert_eq!(p_, p);
+}
+
+#[test]
+fn test_str_truncate_invalid_len() {
+    let mut s = String::from("12345");
+    s.truncate(6);
+    assert_eq!(s, "12345");
+}
+
+#[test]
+#[should_panic]
+fn test_str_truncate_split_codepoint() {
+    let mut s = String::from("\u{FC}"); // ü
+    s.truncate(1);
+}
+
+#[test]
+fn test_str_clear() {
+    let mut s = String::from("12345");
+    s.clear();
+    assert_eq!(s.len(), 0);
+    assert_eq!(s, "");
+}
+
+#[test]
+fn test_str_add() {
+    let a = String::from("12345");
+    let b = a + "2";
+    let b = b + "2";
+    assert_eq!(b.len(), 7);
+    assert_eq!(b, "1234522");
+}
+
+#[test]
+fn remove() {
+    let mut s = "ศไทย中华Việt Nam; foobar".to_string();
+    assert_eq!(s.remove(0), 'ศ');
+    assert_eq!(s.len(), 33);
+    assert_eq!(s, "ไทย中华Việt Nam; foobar");
+    assert_eq!(s.remove(17), 'ệ');
+    assert_eq!(s, "ไทย中华Vit Nam; foobar");
+}
+
+#[test]
+#[should_panic]
+fn remove_bad() {
+    "ศ".to_string().remove(1);
+}
+
+#[test]
+fn insert() {
+    let mut s = "foobar".to_string();
+    s.insert(0, 'ệ');
+    assert_eq!(s, "ệfoobar");
+    s.insert(6, 'ย');
+    assert_eq!(s, "ệfooยbar");
+}
+
+#[test]
+#[should_panic]
+fn insert_bad1() {
+    "".to_string().insert(1, 't');
+}
+#[test]
+#[should_panic]
+fn insert_bad2() {
+    "ệ".to_string().insert(1, 't');
+}
+
+#[test]
+fn test_slicing() {
+    let s = "foobar".to_string();
+    assert_eq!("foobar", &s[..]);
+    assert_eq!("foo", &s[..3]);
+    assert_eq!("bar", &s[3..]);
+    assert_eq!("oob", &s[1..4]);
+}
+
+#[test]
+fn test_simple_types() {
+    assert_eq!(1.to_string(), "1");
+    assert_eq!((-1).to_string(), "-1");
+    assert_eq!(200.to_string(), "200");
+    assert_eq!(2.to_string(), "2");
+    assert_eq!(true.to_string(), "true");
+    assert_eq!(false.to_string(), "false");
+    assert_eq!(("hi".to_string()).to_string(), "hi");
+}
+
+#[test]
+fn test_vectors() {
+    let x: Vec<i32> = vec![];
+    assert_eq!(format!("{:?}", x), "[]");
+    assert_eq!(format!("{:?}", vec![1]), "[1]");
+    assert_eq!(format!("{:?}", vec![1, 2, 3]), "[1, 2, 3]");
+    assert!(format!("{:?}", vec![vec![], vec![1], vec![1, 1]]) == "[[], [1], [1, 1]]");
+}
+
+#[test]
+fn test_from_iterator() {
+    let s = "ศไทย中华Việt Nam".to_string();
+    let t = "ศไทย中华";
+    let u = "Việt Nam";
+
+    let a: String = s.chars().collect();
+    assert_eq!(s, a);
+
+    let mut b = t.to_string();
+    b.extend(u.chars());
+    assert_eq!(s, b);
+
+    let c: String = vec![t, u].into_iter().collect();
+    assert_eq!(s, c);
+
+    let mut d = t.to_string();
+    d.extend(vec![u]);
+    assert_eq!(s, d);
+}
+
+#[test]
+fn test_drain() {
+    let mut s = String::from("αβγ");
+    assert_eq!(s.drain(2..4).collect::<String>(), "β");
+    assert_eq!(s, "αγ");
+
+    let mut t = String::from("abcd");
+    t.drain(..0);
+    assert_eq!(t, "abcd");
+    t.drain(..1);
+    assert_eq!(t, "bcd");
+    t.drain(3..);
+    assert_eq!(t, "bcd");
+    t.drain(..);
+    assert_eq!(t, "");
+}
+
+#[test]
+fn test_splice() {
+    let mut s = "Hello, world!".to_owned();
+    let t: String = s.splice(7..12, "世界").collect();
+    assert_eq!(s, "Hello, 世界!");
+    assert_eq!(t, "world");
+}
+
+#[test]
+#[should_panic]
+fn test_splice_char_boundary() {
+    let mut s = "Hello, 世界!".to_owned();
+    s.splice(..8, "");
+}
+
+#[test]
+fn test_splice_inclusive_range() {
+    let mut v = String::from("12345");
+    let t: String = v.splice(2...3, "789").collect();
+    assert_eq!(v, "127895");
+    assert_eq!(t, "34");
+    let t2: String = v.splice(1...2, "A").collect();
+    assert_eq!(v, "1A895");
+    assert_eq!(t2, "27");
+}
+
+#[test]
+#[should_panic]
+fn test_splice_out_of_bounds() {
+    let mut s = String::from("12345");
+    s.splice(5..6, "789");
+}
+
+#[test]
+#[should_panic]
+fn test_splice_inclusive_out_of_bounds() {
+    let mut s = String::from("12345");
+    s.splice(5...5, "789");
+}
+
+#[test]
+fn test_splice_empty() {
+    let mut s = String::from("12345");
+    let t: String = s.splice(1..2, "").collect();
+    assert_eq!(s, "1345");
+    assert_eq!(t, "2");
+}
+
+#[test]
+fn test_splice_unbounded() {
+    let mut s = String::from("12345");
+    let t: String = s.splice(.., "").collect();
+    assert_eq!(s, "");
+    assert_eq!(t, "12345");
+}
+
+#[test]
+fn test_splice_forget() {
+    let mut s = String::from("12345");
+    ::std::mem::forget(s.splice(2..4, "789"));
+    assert_eq!(s, "12345");
+}
+
+#[test]
+fn test_extend_ref() {
+    let mut a = "foo".to_string();
+    a.extend(&['b', 'a', 'r']);
+
+    assert_eq!(&a, "foobar");
+}
+
+#[test]
+fn test_into_boxed_str() {
+    let xs = String::from("hello my name is bob");
+    let ys = xs.into_boxed_str();
+    assert_eq!(&*ys, "hello my name is bob");
+}
diff --git a/src/liballoc/tests/vec.rs b/src/liballoc/tests/vec.rs
new file mode 100644
index 00000000000..fdf453b39cf
--- /dev/null
+++ b/src/liballoc/tests/vec.rs
@@ -0,0 +1,798 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use std::ascii::AsciiExt;
+use std::borrow::Cow;
+use std::mem::size_of;
+use std::panic;
+use std::vec::{Drain, IntoIter};
+
+struct DropCounter<'a> {
+    count: &'a mut u32,
+}
+
+impl<'a> Drop for DropCounter<'a> {
+    fn drop(&mut self) {
+        *self.count += 1;
+    }
+}
+
+#[test]
+fn test_small_vec_struct() {
+    assert!(size_of::<Vec<u8>>() == size_of::<usize>() * 3);
+}
+
+#[test]
+fn test_double_drop() {
+    struct TwoVec<T> {
+        x: Vec<T>,
+        y: Vec<T>,
+    }
+
+    let (mut count_x, mut count_y) = (0, 0);
+    {
+        let mut tv = TwoVec {
+            x: Vec::new(),
+            y: Vec::new(),
+        };
+        tv.x.push(DropCounter { count: &mut count_x });
+        tv.y.push(DropCounter { count: &mut count_y });
+
+        // If Vec had a drop flag, here is where it would be zeroed.
+        // Instead, it should rely on its internal state to prevent
+        // doing anything significant when dropped multiple times.
+        drop(tv.x);
+
+        // Here tv goes out of scope, tv.y should be dropped, but not tv.x.
+    }
+
+    assert_eq!(count_x, 1);
+    assert_eq!(count_y, 1);
+}
+
+#[test]
+fn test_reserve() {
+    let mut v = Vec::new();
+    assert_eq!(v.capacity(), 0);
+
+    v.reserve(2);
+    assert!(v.capacity() >= 2);
+
+    for i in 0..16 {
+        v.push(i);
+    }
+
+    assert!(v.capacity() >= 16);
+    v.reserve(16);
+    assert!(v.capacity() >= 32);
+
+    v.push(16);
+
+    v.reserve(16);
+    assert!(v.capacity() >= 33)
+}
+
+#[test]
+fn test_extend() {
+    let mut v = Vec::new();
+    let mut w = Vec::new();
+
+    v.extend(w.clone());
+    assert_eq!(v, &[]);
+
+    v.extend(0..3);
+    for i in 0..3 {
+        w.push(i)
+    }
+
+    assert_eq!(v, w);
+
+    v.extend(3..10);
+    for i in 3..10 {
+        w.push(i)
+    }
+
+    assert_eq!(v, w);
+
+    v.extend(w.clone()); // specializes to `append`
+    assert!(v.iter().eq(w.iter().chain(w.iter())));
+
+    // Zero sized types
+    #[derive(PartialEq, Debug)]
+    struct Foo;
+
+    let mut a = Vec::new();
+    let b = vec![Foo, Foo];
+
+    a.extend(b);
+    assert_eq!(a, &[Foo, Foo]);
+
+    // Double drop
+    let mut count_x = 0;
+    {
+        let mut x = Vec::new();
+        let y = vec![DropCounter { count: &mut count_x }];
+        x.extend(y);
+    }
+    assert_eq!(count_x, 1);
+}
+
+#[test]
+fn test_extend_ref() {
+    let mut v = vec![1, 2];
+    v.extend(&[3, 4, 5]);
+
+    assert_eq!(v.len(), 5);
+    assert_eq!(v, [1, 2, 3, 4, 5]);
+
+    let w = vec![6, 7];
+    v.extend(&w);
+
+    assert_eq!(v.len(), 7);
+    assert_eq!(v, [1, 2, 3, 4, 5, 6, 7]);
+}
+
+#[test]
+fn test_slice_from_mut() {
+    let mut values = vec![1, 2, 3, 4, 5];
+    {
+        let slice = &mut values[2..];
+        assert!(slice == [3, 4, 5]);
+        for p in slice {
+            *p += 2;
+        }
+    }
+
+    assert!(values == [1, 2, 5, 6, 7]);
+}
+
+#[test]
+fn test_slice_to_mut() {
+    let mut values = vec![1, 2, 3, 4, 5];
+    {
+        let slice = &mut values[..2];
+        assert!(slice == [1, 2]);
+        for p in slice {
+            *p += 1;
+        }
+    }
+
+    assert!(values == [2, 3, 3, 4, 5]);
+}
+
+#[test]
+fn test_split_at_mut() {
+    let mut values = vec![1, 2, 3, 4, 5];
+    {
+        let (left, right) = values.split_at_mut(2);
+        {
+            let left: &[_] = left;
+            assert!(&left[..left.len()] == &[1, 2]);
+        }
+        for p in left {
+            *p += 1;
+        }
+
+        {
+            let right: &[_] = right;
+            assert!(&right[..right.len()] == &[3, 4, 5]);
+        }
+        for p in right {
+            *p += 2;
+        }
+    }
+
+    assert_eq!(values, [2, 3, 5, 6, 7]);
+}
+
+#[test]
+fn test_clone() {
+    let v: Vec<i32> = vec![];
+    let w = vec![1, 2, 3];
+
+    assert_eq!(v, v.clone());
+
+    let z = w.clone();
+    assert_eq!(w, z);
+    // they should be disjoint in memory.
+    assert!(w.as_ptr() != z.as_ptr())
+}
+
+#[test]
+fn test_clone_from() {
+    let mut v = vec![];
+    let three: Vec<Box<_>> = vec![box 1, box 2, box 3];
+    let two: Vec<Box<_>> = vec![box 4, box 5];
+    // zero, long
+    v.clone_from(&three);
+    assert_eq!(v, three);
+
+    // equal
+    v.clone_from(&three);
+    assert_eq!(v, three);
+
+    // long, short
+    v.clone_from(&two);
+    assert_eq!(v, two);
+
+    // short, long
+    v.clone_from(&three);
+    assert_eq!(v, three)
+}
+
+#[test]
+fn test_retain() {
+    let mut vec = vec![1, 2, 3, 4];
+    vec.retain(|&x| x % 2 == 0);
+    assert_eq!(vec, [2, 4]);
+}
+
+#[test]
+fn test_dedup() {
+    fn case(a: Vec<i32>, b: Vec<i32>) {
+        let mut v = a;
+        v.dedup();
+        assert_eq!(v, b);
+    }
+    case(vec![], vec![]);
+    case(vec![1], vec![1]);
+    case(vec![1, 1], vec![1]);
+    case(vec![1, 2, 3], vec![1, 2, 3]);
+    case(vec![1, 1, 2, 3], vec![1, 2, 3]);
+    case(vec![1, 2, 2, 3], vec![1, 2, 3]);
+    case(vec![1, 2, 3, 3], vec![1, 2, 3]);
+    case(vec![1, 1, 2, 2, 2, 3, 3], vec![1, 2, 3]);
+}
+
+#[test]
+fn test_dedup_by_key() {
+    fn case(a: Vec<i32>, b: Vec<i32>) {
+        let mut v = a;
+        v.dedup_by_key(|i| *i / 10);
+        assert_eq!(v, b);
+    }
+    case(vec![], vec![]);
+    case(vec![10], vec![10]);
+    case(vec![10, 11], vec![10]);
+    case(vec![10, 20, 30], vec![10, 20, 30]);
+    case(vec![10, 11, 20, 30], vec![10, 20, 30]);
+    case(vec![10, 20, 21, 30], vec![10, 20, 30]);
+    case(vec![10, 20, 30, 31], vec![10, 20, 30]);
+    case(vec![10, 11, 20, 21, 22, 30, 31], vec![10, 20, 30]);
+}
+
+#[test]
+fn test_dedup_by() {
+    let mut vec = vec!["foo", "bar", "Bar", "baz", "bar"];
+    vec.dedup_by(|a, b| a.eq_ignore_ascii_case(b));
+
+    assert_eq!(vec, ["foo", "bar", "baz", "bar"]);
+}
+
+#[test]
+fn test_dedup_unique() {
+    let mut v0: Vec<Box<_>> = vec![box 1, box 1, box 2, box 3];
+    v0.dedup();
+    let mut v1: Vec<Box<_>> = vec![box 1, box 2, box 2, box 3];
+    v1.dedup();
+    let mut v2: Vec<Box<_>> = vec![box 1, box 2, box 3, box 3];
+    v2.dedup();
+    // If the boxed pointers were leaked or otherwise misused, valgrind
+    // and/or rt should raise errors.
+}
+
+#[test]
+fn zero_sized_values() {
+    let mut v = Vec::new();
+    assert_eq!(v.len(), 0);
+    v.push(());
+    assert_eq!(v.len(), 1);
+    v.push(());
+    assert_eq!(v.len(), 2);
+    assert_eq!(v.pop(), Some(()));
+    assert_eq!(v.pop(), Some(()));
+    assert_eq!(v.pop(), None);
+
+    assert_eq!(v.iter().count(), 0);
+    v.push(());
+    assert_eq!(v.iter().count(), 1);
+    v.push(());
+    assert_eq!(v.iter().count(), 2);
+
+    for &() in &v {}
+
+    assert_eq!(v.iter_mut().count(), 2);
+    v.push(());
+    assert_eq!(v.iter_mut().count(), 3);
+    v.push(());
+    assert_eq!(v.iter_mut().count(), 4);
+
+    for &mut () in &mut v {}
+    unsafe {
+        v.set_len(0);
+    }
+    assert_eq!(v.iter_mut().count(), 0);
+}
+
+#[test]
+fn test_partition() {
+    assert_eq!(vec![].into_iter().partition(|x: &i32| *x < 3),
+               (vec![], vec![]));
+    assert_eq!(vec![1, 2, 3].into_iter().partition(|x| *x < 4),
+               (vec![1, 2, 3], vec![]));
+    assert_eq!(vec![1, 2, 3].into_iter().partition(|x| *x < 2),
+               (vec![1], vec![2, 3]));
+    assert_eq!(vec![1, 2, 3].into_iter().partition(|x| *x < 0),
+               (vec![], vec![1, 2, 3]));
+}
+
+#[test]
+fn test_zip_unzip() {
+    let z1 = vec![(1, 4), (2, 5), (3, 6)];
+
+    let (left, right): (Vec<_>, Vec<_>) = z1.iter().cloned().unzip();
+
+    assert_eq!((1, 4), (left[0], right[0]));
+    assert_eq!((2, 5), (left[1], right[1]));
+    assert_eq!((3, 6), (left[2], right[2]));
+}
+
+#[test]
+fn test_vec_truncate_drop() {
+    static mut DROPS: u32 = 0;
+    struct Elem(i32);
+    impl Drop for Elem {
+        fn drop(&mut self) {
+            unsafe {
+                DROPS += 1;
+            }
+        }
+    }
+
+    let mut v = vec![Elem(1), Elem(2), Elem(3), Elem(4), Elem(5)];
+    assert_eq!(unsafe { DROPS }, 0);
+    v.truncate(3);
+    assert_eq!(unsafe { DROPS }, 2);
+    v.truncate(0);
+    assert_eq!(unsafe { DROPS }, 5);
+}
+
+#[test]
+#[should_panic]
+fn test_vec_truncate_fail() {
+    struct BadElem(i32);
+    impl Drop for BadElem {
+        fn drop(&mut self) {
+            let BadElem(ref mut x) = *self;
+            if *x == 0xbadbeef {
+                panic!("BadElem panic: 0xbadbeef")
+            }
+        }
+    }
+
+    let mut v = vec![BadElem(1), BadElem(2), BadElem(0xbadbeef), BadElem(4)];
+    v.truncate(0);
+}
+
+#[test]
+fn test_index() {
+    let vec = vec![1, 2, 3];
+    assert!(vec[1] == 2);
+}
+
+#[test]
+#[should_panic]
+fn test_index_out_of_bounds() {
+    let vec = vec![1, 2, 3];
+    let _ = vec[3];
+}
+
+#[test]
+#[should_panic]
+fn test_slice_out_of_bounds_1() {
+    let x = vec![1, 2, 3, 4, 5];
+    &x[!0..];
+}
+
+#[test]
+#[should_panic]
+fn test_slice_out_of_bounds_2() {
+    let x = vec![1, 2, 3, 4, 5];
+    &x[..6];
+}
+
+#[test]
+#[should_panic]
+fn test_slice_out_of_bounds_3() {
+    let x = vec![1, 2, 3, 4, 5];
+    &x[!0..4];
+}
+
+#[test]
+#[should_panic]
+fn test_slice_out_of_bounds_4() {
+    let x = vec![1, 2, 3, 4, 5];
+    &x[1..6];
+}
+
+#[test]
+#[should_panic]
+fn test_slice_out_of_bounds_5() {
+    let x = vec![1, 2, 3, 4, 5];
+    &x[3..2];
+}
+
+#[test]
+#[should_panic]
+fn test_swap_remove_empty() {
+    let mut vec = Vec::<i32>::new();
+    vec.swap_remove(0);
+}
+
+#[test]
+fn test_move_items() {
+    let vec = vec![1, 2, 3];
+    let mut vec2 = vec![];
+    for i in vec {
+        vec2.push(i);
+    }
+    assert_eq!(vec2, [1, 2, 3]);
+}
+
+#[test]
+fn test_move_items_reverse() {
+    let vec = vec![1, 2, 3];
+    let mut vec2 = vec![];
+    for i in vec.into_iter().rev() {
+        vec2.push(i);
+    }
+    assert_eq!(vec2, [3, 2, 1]);
+}
+
+#[test]
+fn test_move_items_zero_sized() {
+    let vec = vec![(), (), ()];
+    let mut vec2 = vec![];
+    for i in vec {
+        vec2.push(i);
+    }
+    assert_eq!(vec2, [(), (), ()]);
+}
+
+#[test]
+fn test_drain_items() {
+    let mut vec = vec![1, 2, 3];
+    let mut vec2 = vec![];
+    for i in vec.drain(..) {
+        vec2.push(i);
+    }
+    assert_eq!(vec, []);
+    assert_eq!(vec2, [1, 2, 3]);
+}
+
+#[test]
+fn test_drain_items_reverse() {
+    let mut vec = vec![1, 2, 3];
+    let mut vec2 = vec![];
+    for i in vec.drain(..).rev() {
+        vec2.push(i);
+    }
+    assert_eq!(vec, []);
+    assert_eq!(vec2, [3, 2, 1]);
+}
+
+#[test]
+fn test_drain_items_zero_sized() {
+    let mut vec = vec![(), (), ()];
+    let mut vec2 = vec![];
+    for i in vec.drain(..) {
+        vec2.push(i);
+    }
+    assert_eq!(vec, []);
+    assert_eq!(vec2, [(), (), ()]);
+}
+
+#[test]
+#[should_panic]
+fn test_drain_out_of_bounds() {
+    let mut v = vec![1, 2, 3, 4, 5];
+    v.drain(5..6);
+}
+
+#[test]
+fn test_drain_range() {
+    let mut v = vec![1, 2, 3, 4, 5];
+    for _ in v.drain(4..) {
+    }
+    assert_eq!(v, &[1, 2, 3, 4]);
+
+    let mut v: Vec<_> = (1..6).map(|x| x.to_string()).collect();
+    for _ in v.drain(1..4) {
+    }
+    assert_eq!(v, &[1.to_string(), 5.to_string()]);
+
+    let mut v: Vec<_> = (1..6).map(|x| x.to_string()).collect();
+    for _ in v.drain(1..4).rev() {
+    }
+    assert_eq!(v, &[1.to_string(), 5.to_string()]);
+
+    let mut v: Vec<_> = vec![(); 5];
+    for _ in v.drain(1..4).rev() {
+    }
+    assert_eq!(v, &[(), ()]);
+}
+
+#[test]
+fn test_drain_inclusive_range() {
+    let mut v = vec!['a', 'b', 'c', 'd', 'e'];
+    for _ in v.drain(1...3) {
+    }
+    assert_eq!(v, &['a', 'e']);
+
+    let mut v: Vec<_> = (0...5).map(|x| x.to_string()).collect();
+    for _ in v.drain(1...5) {
+    }
+    assert_eq!(v, &["0".to_string()]);
+
+    let mut v: Vec<String> = (0...5).map(|x| x.to_string()).collect();
+    for _ in v.drain(0...5) {
+    }
+    assert_eq!(v, Vec::<String>::new());
+
+    let mut v: Vec<_> = (0...5).map(|x| x.to_string()).collect();
+    for _ in v.drain(0...3) {
+    }
+    assert_eq!(v, &["4".to_string(), "5".to_string()]);
+
+    let mut v: Vec<_> = (0...1).map(|x| x.to_string()).collect();
+    for _ in v.drain(...0) {
+    }
+    assert_eq!(v, &["1".to_string()]);
+}
+
+#[test]
+fn test_drain_max_vec_size() {
+    let mut v = Vec::<()>::with_capacity(usize::max_value());
+    unsafe { v.set_len(usize::max_value()); }
+    for _ in v.drain(usize::max_value() - 1..) {
+    }
+    assert_eq!(v.len(), usize::max_value() - 1);
+
+    let mut v = Vec::<()>::with_capacity(usize::max_value());
+    unsafe { v.set_len(usize::max_value()); }
+    for _ in v.drain(usize::max_value() - 1...usize::max_value() - 1) {
+    }
+    assert_eq!(v.len(), usize::max_value() - 1);
+}
+
+#[test]
+#[should_panic]
+fn test_drain_inclusive_out_of_bounds() {
+    let mut v = vec![1, 2, 3, 4, 5];
+    v.drain(5...5);
+}
+
+#[test]
+fn test_splice() {
+    let mut v = vec![1, 2, 3, 4, 5];
+    let a = [10, 11, 12];
+    v.splice(2..4, a.iter().cloned());
+    assert_eq!(v, &[1, 2, 10, 11, 12, 5]);
+    v.splice(1..3, Some(20));
+    assert_eq!(v, &[1, 20, 11, 12, 5]);
+}
+
+#[test]
+fn test_splice_inclusive_range() {
+    let mut v = vec![1, 2, 3, 4, 5];
+    let a = [10, 11, 12];
+    let t1: Vec<_> = v.splice(2...3, a.iter().cloned()).collect();
+    assert_eq!(v, &[1, 2, 10, 11, 12, 5]);
+    assert_eq!(t1, &[3, 4]);
+    let t2: Vec<_> = v.splice(1...2, Some(20)).collect();
+    assert_eq!(v, &[1, 20, 11, 12, 5]);
+    assert_eq!(t2, &[2, 10]);
+}
+
+#[test]
+#[should_panic]
+fn test_splice_out_of_bounds() {
+    let mut v = vec![1, 2, 3, 4, 5];
+    let a = [10, 11, 12];
+    v.splice(5..6, a.iter().cloned());
+}
+
+#[test]
+#[should_panic]
+fn test_splice_inclusive_out_of_bounds() {
+    let mut v = vec![1, 2, 3, 4, 5];
+    let a = [10, 11, 12];
+    v.splice(5...5, a.iter().cloned());
+}
+
+#[test]
+fn test_splice_items_zero_sized() {
+    let mut vec = vec![(), (), ()];
+    let vec2 = vec![];
+    let t: Vec<_> = vec.splice(1..2, vec2.iter().cloned()).collect();
+    assert_eq!(vec, &[(), ()]);
+    assert_eq!(t, &[()]);
+}
+
+#[test]
+fn test_splice_unbounded() {
+    let mut vec = vec![1, 2, 3, 4, 5];
+    let t: Vec<_> = vec.splice(.., None).collect();
+    assert_eq!(vec, &[]);
+    assert_eq!(t, &[1, 2, 3, 4, 5]);
+}
+
+#[test]
+fn test_splice_forget() {
+    let mut v = vec![1, 2, 3, 4, 5];
+    let a = [10, 11, 12];
+    ::std::mem::forget(v.splice(2..4, a.iter().cloned()));
+    assert_eq!(v, &[1, 2]);
+}
+
+#[test]
+fn test_into_boxed_slice() {
+    let xs = vec![1, 2, 3];
+    let ys = xs.into_boxed_slice();
+    assert_eq!(&*ys, [1, 2, 3]);
+}
+
+#[test]
+fn test_append() {
+    let mut vec = vec![1, 2, 3];
+    let mut vec2 = vec![4, 5, 6];
+    vec.append(&mut vec2);
+    assert_eq!(vec, [1, 2, 3, 4, 5, 6]);
+    assert_eq!(vec2, []);
+}
+
+#[test]
+fn test_split_off() {
+    let mut vec = vec![1, 2, 3, 4, 5, 6];
+    let vec2 = vec.split_off(4);
+    assert_eq!(vec, [1, 2, 3, 4]);
+    assert_eq!(vec2, [5, 6]);
+}
+
+#[test]
+fn test_into_iter_as_slice() {
+    let vec = vec!['a', 'b', 'c'];
+    let mut into_iter = vec.into_iter();
+    assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
+    let _ = into_iter.next().unwrap();
+    assert_eq!(into_iter.as_slice(), &['b', 'c']);
+    let _ = into_iter.next().unwrap();
+    let _ = into_iter.next().unwrap();
+    assert_eq!(into_iter.as_slice(), &[]);
+}
+
+#[test]
+fn test_into_iter_as_mut_slice() {
+    let vec = vec!['a', 'b', 'c'];
+    let mut into_iter = vec.into_iter();
+    assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
+    into_iter.as_mut_slice()[0] = 'x';
+    into_iter.as_mut_slice()[1] = 'y';
+    assert_eq!(into_iter.next().unwrap(), 'x');
+    assert_eq!(into_iter.as_slice(), &['y', 'c']);
+}
+
+#[test]
+fn test_into_iter_debug() {
+    let vec = vec!['a', 'b', 'c'];
+    let into_iter = vec.into_iter();
+    let debug = format!("{:?}", into_iter);
+    assert_eq!(debug, "IntoIter(['a', 'b', 'c'])");
+}
+
+#[test]
+fn test_into_iter_count() {
+    assert_eq!(vec![1, 2, 3].into_iter().count(), 3);
+}
+
+#[test]
+fn test_into_iter_clone() {
+    fn iter_equal<I: Iterator<Item = i32>>(it: I, slice: &[i32]) {
+        let v: Vec<i32> = it.collect();
+        assert_eq!(&v[..], slice);
+    }
+    let mut it = vec![1, 2, 3].into_iter();
+    iter_equal(it.clone(), &[1, 2, 3]);
+    assert_eq!(it.next(), Some(1));
+    let mut it = it.rev();
+    iter_equal(it.clone(), &[3, 2]);
+    assert_eq!(it.next(), Some(3));
+    iter_equal(it.clone(), &[2]);
+    assert_eq!(it.next(), Some(2));
+    iter_equal(it.clone(), &[]);
+    assert_eq!(it.next(), None);
+}
+
+#[test]
+fn test_cow_from() {
+    let borrowed: &[_] = &["borrowed", "(slice)"];
+    let owned = vec!["owned", "(vec)"];
+    match (Cow::from(owned.clone()), Cow::from(borrowed)) {
+        (Cow::Owned(o), Cow::Borrowed(b)) => assert!(o == owned && b == borrowed),
+        _ => panic!("invalid `Cow::from`"),
+    }
+}
+
+#[test]
+fn test_from_cow() {
+    let borrowed: &[_] = &["borrowed", "(slice)"];
+    let owned = vec!["owned", "(vec)"];
+    assert_eq!(Vec::from(Cow::Borrowed(borrowed)), vec!["borrowed", "(slice)"]);
+    assert_eq!(Vec::from(Cow::Owned(owned)), vec!["owned", "(vec)"]);
+}
+
+#[allow(dead_code)]
+fn assert_covariance() {
+    fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
+        d
+    }
+    fn into_iter<'new>(i: IntoIter<&'static str>) -> IntoIter<&'new str> {
+        i
+    }
+}
+
+#[test]
+fn test_placement() {
+    let mut vec = vec![1];
+    assert_eq!(vec.place_back() <- 2, &2);
+    assert_eq!(vec.len(), 2);
+    assert_eq!(vec.place_back() <- 3, &3);
+    assert_eq!(vec.len(), 3);
+    assert_eq!(&vec, &[1, 2, 3]);
+}
+
+#[test]
+fn test_placement_panic() {
+    let mut vec = vec![1, 2, 3];
+    fn mkpanic() -> usize { panic!() }
+    let _ = panic::catch_unwind(panic::AssertUnwindSafe(|| { vec.place_back() <- mkpanic(); }));
+    assert_eq!(vec.len(), 3);
+}
+
+#[test]
+fn from_into_inner() {
+    let vec = vec![1, 2, 3];
+    let ptr = vec.as_ptr();
+    let vec = vec.into_iter().collect::<Vec<_>>();
+    assert_eq!(vec, [1, 2, 3]);
+    assert_eq!(vec.as_ptr(), ptr);
+
+    let ptr = &vec[1] as *const _;
+    let mut it = vec.into_iter();
+    it.next().unwrap();
+    let vec = it.collect::<Vec<_>>();
+    assert_eq!(vec, [2, 3]);
+    assert!(ptr != vec.as_ptr());
+}
+
+#[test]
+fn overaligned_allocations() {
+    #[repr(align(256))]
+    struct Foo(usize);
+    let mut v = vec![Foo(273)];
+    for i in 0..0x1000 {
+        v.reserve_exact(i);
+        assert!(v[0].0 == 273);
+        assert!(v.as_ptr() as usize & 0xff == 0);
+        v.shrink_to_fit();
+        assert!(v[0].0 == 273);
+        assert!(v.as_ptr() as usize & 0xff == 0);
+    }
+}
diff --git a/src/liballoc/tests/vec_deque.rs b/src/liballoc/tests/vec_deque.rs
new file mode 100644
index 00000000000..a992351653d
--- /dev/null
+++ b/src/liballoc/tests/vec_deque.rs
@@ -0,0 +1,1025 @@
+// Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use std::collections::VecDeque;
+use std::fmt::Debug;
+use std::collections::vec_deque::{Drain};
+
+use self::Taggy::*;
+use self::Taggypar::*;
+
+#[test]
+fn test_simple() {
+    let mut d = VecDeque::new();
+    assert_eq!(d.len(), 0);
+    d.push_front(17);
+    d.push_front(42);
+    d.push_back(137);
+    assert_eq!(d.len(), 3);
+    d.push_back(137);
+    assert_eq!(d.len(), 4);
+    assert_eq!(*d.front().unwrap(), 42);
+    assert_eq!(*d.back().unwrap(), 137);
+    let mut i = d.pop_front();
+    assert_eq!(i, Some(42));
+    i = d.pop_back();
+    assert_eq!(i, Some(137));
+    i = d.pop_back();
+    assert_eq!(i, Some(137));
+    i = d.pop_back();
+    assert_eq!(i, Some(17));
+    assert_eq!(d.len(), 0);
+    d.push_back(3);
+    assert_eq!(d.len(), 1);
+    d.push_front(2);
+    assert_eq!(d.len(), 2);
+    d.push_back(4);
+    assert_eq!(d.len(), 3);
+    d.push_front(1);
+    assert_eq!(d.len(), 4);
+    assert_eq!(d[0], 1);
+    assert_eq!(d[1], 2);
+    assert_eq!(d[2], 3);
+    assert_eq!(d[3], 4);
+}
+
+#[cfg(test)]
+fn test_parameterized<T: Clone + PartialEq + Debug>(a: T, b: T, c: T, d: T) {
+    let mut deq = VecDeque::new();
+    assert_eq!(deq.len(), 0);
+    deq.push_front(a.clone());
+    deq.push_front(b.clone());
+    deq.push_back(c.clone());
+    assert_eq!(deq.len(), 3);
+    deq.push_back(d.clone());
+    assert_eq!(deq.len(), 4);
+    assert_eq!((*deq.front().unwrap()).clone(), b.clone());
+    assert_eq!((*deq.back().unwrap()).clone(), d.clone());
+    assert_eq!(deq.pop_front().unwrap(), b.clone());
+    assert_eq!(deq.pop_back().unwrap(), d.clone());
+    assert_eq!(deq.pop_back().unwrap(), c.clone());
+    assert_eq!(deq.pop_back().unwrap(), a.clone());
+    assert_eq!(deq.len(), 0);
+    deq.push_back(c.clone());
+    assert_eq!(deq.len(), 1);
+    deq.push_front(b.clone());
+    assert_eq!(deq.len(), 2);
+    deq.push_back(d.clone());
+    assert_eq!(deq.len(), 3);
+    deq.push_front(a.clone());
+    assert_eq!(deq.len(), 4);
+    assert_eq!(deq[0].clone(), a.clone());
+    assert_eq!(deq[1].clone(), b.clone());
+    assert_eq!(deq[2].clone(), c.clone());
+    assert_eq!(deq[3].clone(), d.clone());
+}
+
+#[test]
+fn test_push_front_grow() {
+    let mut deq = VecDeque::new();
+    for i in 0..66 {
+        deq.push_front(i);
+    }
+    assert_eq!(deq.len(), 66);
+
+    for i in 0..66 {
+        assert_eq!(deq[i], 65 - i);
+    }
+
+    let mut deq = VecDeque::new();
+    for i in 0..66 {
+        deq.push_back(i);
+    }
+
+    for i in 0..66 {
+        assert_eq!(deq[i], i);
+    }
+}
+
+#[test]
+fn test_index() {
+    let mut deq = VecDeque::new();
+    for i in 1..4 {
+        deq.push_front(i);
+    }
+    assert_eq!(deq[1], 2);
+}
+
+#[test]
+#[should_panic]
+fn test_index_out_of_bounds() {
+    let mut deq = VecDeque::new();
+    for i in 1..4 {
+        deq.push_front(i);
+    }
+    deq[3];
+}
+
+#[derive(Clone, PartialEq, Debug)]
+enum Taggy {
+    One(i32),
+    Two(i32, i32),
+    Three(i32, i32, i32),
+}
+
+#[derive(Clone, PartialEq, Debug)]
+enum Taggypar<T> {
+    Onepar(T),
+    Twopar(T, T),
+    Threepar(T, T, T),
+}
+
+#[derive(Clone, PartialEq, Debug)]
+struct RecCy {
+    x: i32,
+    y: i32,
+    t: Taggy,
+}
+
+#[test]
+fn test_param_int() {
+    test_parameterized::<i32>(5, 72, 64, 175);
+}
+
+#[test]
+fn test_param_taggy() {
+    test_parameterized::<Taggy>(One(1), Two(1, 2), Three(1, 2, 3), Two(17, 42));
+}
+
+#[test]
+fn test_param_taggypar() {
+    test_parameterized::<Taggypar<i32>>(Onepar::<i32>(1),
+                                        Twopar::<i32>(1, 2),
+                                        Threepar::<i32>(1, 2, 3),
+                                        Twopar::<i32>(17, 42));
+}
+
+#[test]
+fn test_param_reccy() {
+    let reccy1 = RecCy {
+        x: 1,
+        y: 2,
+        t: One(1),
+    };
+    let reccy2 = RecCy {
+        x: 345,
+        y: 2,
+        t: Two(1, 2),
+    };
+    let reccy3 = RecCy {
+        x: 1,
+        y: 777,
+        t: Three(1, 2, 3),
+    };
+    let reccy4 = RecCy {
+        x: 19,
+        y: 252,
+        t: Two(17, 42),
+    };
+    test_parameterized::<RecCy>(reccy1, reccy2, reccy3, reccy4);
+}
+
+#[test]
+fn test_with_capacity() {
+    let mut d = VecDeque::with_capacity(0);
+    d.push_back(1);
+    assert_eq!(d.len(), 1);
+    let mut d = VecDeque::with_capacity(50);
+    d.push_back(1);
+    assert_eq!(d.len(), 1);
+}
+
+#[test]
+fn test_with_capacity_non_power_two() {
+    let mut d3 = VecDeque::with_capacity(3);
+    d3.push_back(1);
+
+    // X = None, | = lo
+    // [|1, X, X]
+    assert_eq!(d3.pop_front(), Some(1));
+    // [X, |X, X]
+    assert_eq!(d3.front(), None);
+
+    // [X, |3, X]
+    d3.push_back(3);
+    // [X, |3, 6]
+    d3.push_back(6);
+    // [X, X, |6]
+    assert_eq!(d3.pop_front(), Some(3));
+
+    // Pushing the lo past half way point to trigger
+    // the 'B' scenario for growth
+    // [9, X, |6]
+    d3.push_back(9);
+    // [9, 12, |6]
+    d3.push_back(12);
+
+    d3.push_back(15);
+    // There used to be a bug here about how the
+    // VecDeque made growth assumptions about the
+    // underlying Vec which didn't hold and lead
+    // to corruption.
+    // (Vec grows to next power of two)
+    // good- [9, 12, 15, X, X, X, X, |6]
+    // bug-  [15, 12, X, X, X, |6, X, X]
+    assert_eq!(d3.pop_front(), Some(6));
+
+    // Which leads us to the following state which
+    // would be a failure case.
+    // bug-  [15, 12, X, X, X, X, |X, X]
+    assert_eq!(d3.front(), Some(&9));
+}
+
+#[test]
+fn test_reserve_exact() {
+    let mut d = VecDeque::new();
+    d.push_back(0);
+    d.reserve_exact(50);
+    assert!(d.capacity() >= 51);
+}
+
+#[test]
+fn test_reserve() {
+    let mut d = VecDeque::new();
+    d.push_back(0);
+    d.reserve(50);
+    assert!(d.capacity() >= 51);
+}
+
+#[test]
+fn test_swap() {
+    let mut d: VecDeque<_> = (0..5).collect();
+    d.pop_front();
+    d.swap(0, 3);
+    assert_eq!(d.iter().cloned().collect::<Vec<_>>(), [4, 2, 3, 1]);
+}
+
+#[test]
+fn test_iter() {
+    let mut d = VecDeque::new();
+    assert_eq!(d.iter().next(), None);
+    assert_eq!(d.iter().size_hint(), (0, Some(0)));
+
+    for i in 0..5 {
+        d.push_back(i);
+    }
+    {
+        let b: &[_] = &[&0, &1, &2, &3, &4];
+        assert_eq!(d.iter().collect::<Vec<_>>(), b);
+    }
+
+    for i in 6..9 {
+        d.push_front(i);
+    }
+    {
+        let b: &[_] = &[&8, &7, &6, &0, &1, &2, &3, &4];
+        assert_eq!(d.iter().collect::<Vec<_>>(), b);
+    }
+
+    let mut it = d.iter();
+    let mut len = d.len();
+    loop {
+        match it.next() {
+            None => break,
+            _ => {
+                len -= 1;
+                assert_eq!(it.size_hint(), (len, Some(len)))
+            }
+        }
+    }
+}
+
+#[test]
+fn test_rev_iter() {
+    let mut d = VecDeque::new();
+    assert_eq!(d.iter().rev().next(), None);
+
+    for i in 0..5 {
+        d.push_back(i);
+    }
+    {
+        let b: &[_] = &[&4, &3, &2, &1, &0];
+        assert_eq!(d.iter().rev().collect::<Vec<_>>(), b);
+    }
+
+    for i in 6..9 {
+        d.push_front(i);
+    }
+    let b: &[_] = &[&4, &3, &2, &1, &0, &6, &7, &8];
+    assert_eq!(d.iter().rev().collect::<Vec<_>>(), b);
+}
+
+#[test]
+fn test_mut_rev_iter_wrap() {
+    let mut d = VecDeque::with_capacity(3);
+    assert!(d.iter_mut().rev().next().is_none());
+
+    d.push_back(1);
+    d.push_back(2);
+    d.push_back(3);
+    assert_eq!(d.pop_front(), Some(1));
+    d.push_back(4);
+
+    assert_eq!(d.iter_mut().rev().map(|x| *x).collect::<Vec<_>>(),
+               vec![4, 3, 2]);
+}
+
+#[test]
+fn test_mut_iter() {
+    let mut d = VecDeque::new();
+    assert!(d.iter_mut().next().is_none());
+
+    for i in 0..3 {
+        d.push_front(i);
+    }
+
+    for (i, elt) in d.iter_mut().enumerate() {
+        assert_eq!(*elt, 2 - i);
+        *elt = i;
+    }
+
+    {
+        let mut it = d.iter_mut();
+        assert_eq!(*it.next().unwrap(), 0);
+        assert_eq!(*it.next().unwrap(), 1);
+        assert_eq!(*it.next().unwrap(), 2);
+        assert!(it.next().is_none());
+    }
+}
+
+#[test]
+fn test_mut_rev_iter() {
+    let mut d = VecDeque::new();
+    assert!(d.iter_mut().rev().next().is_none());
+
+    for i in 0..3 {
+        d.push_front(i);
+    }
+
+    for (i, elt) in d.iter_mut().rev().enumerate() {
+        assert_eq!(*elt, i);
+        *elt = i;
+    }
+
+    {
+        let mut it = d.iter_mut().rev();
+        assert_eq!(*it.next().unwrap(), 0);
+        assert_eq!(*it.next().unwrap(), 1);
+        assert_eq!(*it.next().unwrap(), 2);
+        assert!(it.next().is_none());
+    }
+}
+
+#[test]
+fn test_into_iter() {
+
+    // Empty iter
+    {
+        let d: VecDeque<i32> = VecDeque::new();
+        let mut iter = d.into_iter();
+
+        assert_eq!(iter.size_hint(), (0, Some(0)));
+        assert_eq!(iter.next(), None);
+        assert_eq!(iter.size_hint(), (0, Some(0)));
+    }
+
+    // simple iter
+    {
+        let mut d = VecDeque::new();
+        for i in 0..5 {
+            d.push_back(i);
+        }
+
+        let b = vec![0, 1, 2, 3, 4];
+        assert_eq!(d.into_iter().collect::<Vec<_>>(), b);
+    }
+
+    // wrapped iter
+    {
+        let mut d = VecDeque::new();
+        for i in 0..5 {
+            d.push_back(i);
+        }
+        for i in 6..9 {
+            d.push_front(i);
+        }
+
+        let b = vec![8, 7, 6, 0, 1, 2, 3, 4];
+        assert_eq!(d.into_iter().collect::<Vec<_>>(), b);
+    }
+
+    // partially used
+    {
+        let mut d = VecDeque::new();
+        for i in 0..5 {
+            d.push_back(i);
+        }
+        for i in 6..9 {
+            d.push_front(i);
+        }
+
+        let mut it = d.into_iter();
+        assert_eq!(it.size_hint(), (8, Some(8)));
+        assert_eq!(it.next(), Some(8));
+        assert_eq!(it.size_hint(), (7, Some(7)));
+        assert_eq!(it.next_back(), Some(4));
+        assert_eq!(it.size_hint(), (6, Some(6)));
+        assert_eq!(it.next(), Some(7));
+        assert_eq!(it.size_hint(), (5, Some(5)));
+    }
+}
+
+#[test]
+fn test_drain() {
+
+    // Empty iter
+    {
+        let mut d: VecDeque<i32> = VecDeque::new();
+
+        {
+            let mut iter = d.drain(..);
+
+            assert_eq!(iter.size_hint(), (0, Some(0)));
+            assert_eq!(iter.next(), None);
+            assert_eq!(iter.size_hint(), (0, Some(0)));
+        }
+
+        assert!(d.is_empty());
+    }
+
+    // simple iter
+    {
+        let mut d = VecDeque::new();
+        for i in 0..5 {
+            d.push_back(i);
+        }
+
+        assert_eq!(d.drain(..).collect::<Vec<_>>(), [0, 1, 2, 3, 4]);
+        assert!(d.is_empty());
+    }
+
+    // wrapped iter
+    {
+        let mut d = VecDeque::new();
+        for i in 0..5 {
+            d.push_back(i);
+        }
+        for i in 6..9 {
+            d.push_front(i);
+        }
+
+        assert_eq!(d.drain(..).collect::<Vec<_>>(), [8, 7, 6, 0, 1, 2, 3, 4]);
+        assert!(d.is_empty());
+    }
+
+    // partially used
+    {
+        let mut d: VecDeque<_> = VecDeque::new();
+        for i in 0..5 {
+            d.push_back(i);
+        }
+        for i in 6..9 {
+            d.push_front(i);
+        }
+
+        {
+            let mut it = d.drain(..);
+            assert_eq!(it.size_hint(), (8, Some(8)));
+            assert_eq!(it.next(), Some(8));
+            assert_eq!(it.size_hint(), (7, Some(7)));
+            assert_eq!(it.next_back(), Some(4));
+            assert_eq!(it.size_hint(), (6, Some(6)));
+            assert_eq!(it.next(), Some(7));
+            assert_eq!(it.size_hint(), (5, Some(5)));
+        }
+        assert!(d.is_empty());
+    }
+}
+
+#[test]
+fn test_from_iter() {
+    let v = vec![1, 2, 3, 4, 5, 6, 7];
+    let deq: VecDeque<_> = v.iter().cloned().collect();
+    let u: Vec<_> = deq.iter().cloned().collect();
+    assert_eq!(u, v);
+
+    // FIXME #27741: Remove `.skip(0)` when Range::step_by is fully removed
+    let seq = (0..).skip(0).step_by(2).take(256);
+    let deq: VecDeque<_> = seq.collect();
+    for (i, &x) in deq.iter().enumerate() {
+        assert_eq!(2 * i, x);
+    }
+    assert_eq!(deq.len(), 256);
+}
+
+#[test]
+fn test_clone() {
+    let mut d = VecDeque::new();
+    d.push_front(17);
+    d.push_front(42);
+    d.push_back(137);
+    d.push_back(137);
+    assert_eq!(d.len(), 4);
+    let mut e = d.clone();
+    assert_eq!(e.len(), 4);
+    while !d.is_empty() {
+        assert_eq!(d.pop_back(), e.pop_back());
+    }
+    assert_eq!(d.len(), 0);
+    assert_eq!(e.len(), 0);
+}
+
+#[test]
+fn test_eq() {
+    let mut d = VecDeque::new();
+    assert!(d == VecDeque::with_capacity(0));
+    d.push_front(137);
+    d.push_front(17);
+    d.push_front(42);
+    d.push_back(137);
+    let mut e = VecDeque::with_capacity(0);
+    e.push_back(42);
+    e.push_back(17);
+    e.push_back(137);
+    e.push_back(137);
+    assert!(&e == &d);
+    e.pop_back();
+    e.push_back(0);
+    assert!(e != d);
+    e.clear();
+    assert!(e == VecDeque::new());
+}
+
+#[test]
+fn test_partial_eq_array() {
+    let d = VecDeque::<char>::new();
+    assert!(d == []);
+
+    let mut d = VecDeque::new();
+    d.push_front('a');
+    assert!(d == ['a']);
+
+    let mut d = VecDeque::new();
+    d.push_back('a');
+    assert!(d == ['a']);
+
+    let mut d = VecDeque::new();
+    d.push_back('a');
+    d.push_back('b');
+    assert!(d == ['a', 'b']);
+}
+
+#[test]
+fn test_hash() {
+    let mut x = VecDeque::new();
+    let mut y = VecDeque::new();
+
+    x.push_back(1);
+    x.push_back(2);
+    x.push_back(3);
+
+    y.push_back(0);
+    y.push_back(1);
+    y.pop_front();
+    y.push_back(2);
+    y.push_back(3);
+
+    assert!(::hash(&x) == ::hash(&y));
+}
+
+#[test]
+fn test_hash_after_rotation() {
+    // test that two deques hash equal even if elements are laid out differently
+    let len = 28;
+    let mut ring: VecDeque<i32> = (0..len as i32).collect();
+    let orig = ring.clone();
+    for _ in 0..ring.capacity() {
+        // shift values 1 step to the right by pop, sub one, push
+        ring.pop_front();
+        for elt in &mut ring {
+            *elt -= 1;
+        }
+        ring.push_back(len - 1);
+        assert_eq!(::hash(&orig), ::hash(&ring));
+        assert_eq!(orig, ring);
+        assert_eq!(ring, orig);
+    }
+}
+
+#[test]
+fn test_eq_after_rotation() {
+    // test that two deques are equal even if elements are laid out differently
+    let len = 28;
+    let mut ring: VecDeque<i32> = (0..len as i32).collect();
+    let mut shifted = ring.clone();
+    for _ in 0..10 {
+        // shift values 1 step to the right by pop, sub one, push
+        ring.pop_front();
+        for elt in &mut ring {
+            *elt -= 1;
+        }
+        ring.push_back(len - 1);
+    }
+
+    // try every shift
+    for _ in 0..shifted.capacity() {
+        shifted.pop_front();
+        for elt in &mut shifted {
+            *elt -= 1;
+        }
+        shifted.push_back(len - 1);
+        assert_eq!(shifted, ring);
+        assert_eq!(ring, shifted);
+    }
+}
+
+#[test]
+fn test_ord() {
+    let x = VecDeque::new();
+    let mut y = VecDeque::new();
+    y.push_back(1);
+    y.push_back(2);
+    y.push_back(3);
+    assert!(x < y);
+    assert!(y > x);
+    assert!(x <= x);
+    assert!(x >= x);
+}
+
+#[test]
+fn test_show() {
+    let ringbuf: VecDeque<_> = (0..10).collect();
+    assert_eq!(format!("{:?}", ringbuf), "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
+
+    let ringbuf: VecDeque<_> = vec!["just", "one", "test", "more"]
+        .iter()
+        .cloned()
+        .collect();
+    assert_eq!(format!("{:?}", ringbuf),
+               "[\"just\", \"one\", \"test\", \"more\"]");
+}
+
+#[test]
+fn test_drop() {
+    static mut DROPS: i32 = 0;
+    struct Elem;
+    impl Drop for Elem {
+        fn drop(&mut self) {
+            unsafe {
+                DROPS += 1;
+            }
+        }
+    }
+
+    let mut ring = VecDeque::new();
+    ring.push_back(Elem);
+    ring.push_front(Elem);
+    ring.push_back(Elem);
+    ring.push_front(Elem);
+    drop(ring);
+
+    assert_eq!(unsafe { DROPS }, 4);
+}
+
+#[test]
+fn test_drop_with_pop() {
+    static mut DROPS: i32 = 0;
+    struct Elem;
+    impl Drop for Elem {
+        fn drop(&mut self) {
+            unsafe {
+                DROPS += 1;
+            }
+        }
+    }
+
+    let mut ring = VecDeque::new();
+    ring.push_back(Elem);
+    ring.push_front(Elem);
+    ring.push_back(Elem);
+    ring.push_front(Elem);
+
+    drop(ring.pop_back());
+    drop(ring.pop_front());
+    assert_eq!(unsafe { DROPS }, 2);
+
+    drop(ring);
+    assert_eq!(unsafe { DROPS }, 4);
+}
+
+#[test]
+fn test_drop_clear() {
+    static mut DROPS: i32 = 0;
+    struct Elem;
+    impl Drop for Elem {
+        fn drop(&mut self) {
+            unsafe {
+                DROPS += 1;
+            }
+        }
+    }
+
+    let mut ring = VecDeque::new();
+    ring.push_back(Elem);
+    ring.push_front(Elem);
+    ring.push_back(Elem);
+    ring.push_front(Elem);
+    ring.clear();
+    assert_eq!(unsafe { DROPS }, 4);
+
+    drop(ring);
+    assert_eq!(unsafe { DROPS }, 4);
+}
+
+#[test]
+fn test_reserve_grow() {
+    // test growth path A
+    // [T o o H] -> [T o o H . . . . ]
+    let mut ring = VecDeque::with_capacity(4);
+    for i in 0..3 {
+        ring.push_back(i);
+    }
+    ring.reserve(7);
+    for i in 0..3 {
+        assert_eq!(ring.pop_front(), Some(i));
+    }
+
+    // test growth path B
+    // [H T o o] -> [. T o o H . . . ]
+    let mut ring = VecDeque::with_capacity(4);
+    for i in 0..1 {
+        ring.push_back(i);
+        assert_eq!(ring.pop_front(), Some(i));
+    }
+    for i in 0..3 {
+        ring.push_back(i);
+    }
+    ring.reserve(7);
+    for i in 0..3 {
+        assert_eq!(ring.pop_front(), Some(i));
+    }
+
+    // test growth path C
+    // [o o H T] -> [o o H . . . . T ]
+    let mut ring = VecDeque::with_capacity(4);
+    for i in 0..3 {
+        ring.push_back(i);
+        assert_eq!(ring.pop_front(), Some(i));
+    }
+    for i in 0..3 {
+        ring.push_back(i);
+    }
+    ring.reserve(7);
+    for i in 0..3 {
+        assert_eq!(ring.pop_front(), Some(i));
+    }
+}
+
+#[test]
+fn test_get() {
+    let mut ring = VecDeque::new();
+    ring.push_back(0);
+    assert_eq!(ring.get(0), Some(&0));
+    assert_eq!(ring.get(1), None);
+
+    ring.push_back(1);
+    assert_eq!(ring.get(0), Some(&0));
+    assert_eq!(ring.get(1), Some(&1));
+    assert_eq!(ring.get(2), None);
+
+    ring.push_back(2);
+    assert_eq!(ring.get(0), Some(&0));
+    assert_eq!(ring.get(1), Some(&1));
+    assert_eq!(ring.get(2), Some(&2));
+    assert_eq!(ring.get(3), None);
+
+    assert_eq!(ring.pop_front(), Some(0));
+    assert_eq!(ring.get(0), Some(&1));
+    assert_eq!(ring.get(1), Some(&2));
+    assert_eq!(ring.get(2), None);
+
+    assert_eq!(ring.pop_front(), Some(1));
+    assert_eq!(ring.get(0), Some(&2));
+    assert_eq!(ring.get(1), None);
+
+    assert_eq!(ring.pop_front(), Some(2));
+    assert_eq!(ring.get(0), None);
+    assert_eq!(ring.get(1), None);
+}
+
+#[test]
+fn test_get_mut() {
+    let mut ring = VecDeque::new();
+    for i in 0..3 {
+        ring.push_back(i);
+    }
+
+    match ring.get_mut(1) {
+        Some(x) => *x = -1,
+        None => (),
+    };
+
+    assert_eq!(ring.get_mut(0), Some(&mut 0));
+    assert_eq!(ring.get_mut(1), Some(&mut -1));
+    assert_eq!(ring.get_mut(2), Some(&mut 2));
+    assert_eq!(ring.get_mut(3), None);
+
+    assert_eq!(ring.pop_front(), Some(0));
+    assert_eq!(ring.get_mut(0), Some(&mut -1));
+    assert_eq!(ring.get_mut(1), Some(&mut 2));
+    assert_eq!(ring.get_mut(2), None);
+}
+
+#[test]
+fn test_front() {
+    let mut ring = VecDeque::new();
+    ring.push_back(10);
+    ring.push_back(20);
+    assert_eq!(ring.front(), Some(&10));
+    ring.pop_front();
+    assert_eq!(ring.front(), Some(&20));
+    ring.pop_front();
+    assert_eq!(ring.front(), None);
+}
+
+#[test]
+fn test_as_slices() {
+    let mut ring: VecDeque<i32> = VecDeque::with_capacity(127);
+    let cap = ring.capacity() as i32;
+    let first = cap / 2;
+    let last = cap - first;
+    for i in 0..first {
+        ring.push_back(i);
+
+        let (left, right) = ring.as_slices();
+        let expected: Vec<_> = (0..i + 1).collect();
+        assert_eq!(left, &expected[..]);
+        assert_eq!(right, []);
+    }
+
+    for j in -last..0 {
+        ring.push_front(j);
+        let (left, right) = ring.as_slices();
+        let expected_left: Vec<_> = (-last..j + 1).rev().collect();
+        let expected_right: Vec<_> = (0..first).collect();
+        assert_eq!(left, &expected_left[..]);
+        assert_eq!(right, &expected_right[..]);
+    }
+
+    assert_eq!(ring.len() as i32, cap);
+    assert_eq!(ring.capacity() as i32, cap);
+}
+
+#[test]
+fn test_as_mut_slices() {
+    let mut ring: VecDeque<i32> = VecDeque::with_capacity(127);
+    let cap = ring.capacity() as i32;
+    let first = cap / 2;
+    let last = cap - first;
+    for i in 0..first {
+        ring.push_back(i);
+
+        let (left, right) = ring.as_mut_slices();
+        let expected: Vec<_> = (0..i + 1).collect();
+        assert_eq!(left, &expected[..]);
+        assert_eq!(right, []);
+    }
+
+    for j in -last..0 {
+        ring.push_front(j);
+        let (left, right) = ring.as_mut_slices();
+        let expected_left: Vec<_> = (-last..j + 1).rev().collect();
+        let expected_right: Vec<_> = (0..first).collect();
+        assert_eq!(left, &expected_left[..]);
+        assert_eq!(right, &expected_right[..]);
+    }
+
+    assert_eq!(ring.len() as i32, cap);
+    assert_eq!(ring.capacity() as i32, cap);
+}
+
+#[test]
+fn test_append() {
+    let mut a: VecDeque<_> = vec![1, 2, 3].into_iter().collect();
+    let mut b: VecDeque<_> = vec![4, 5, 6].into_iter().collect();
+
+    // normal append
+    a.append(&mut b);
+    assert_eq!(a.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]);
+    assert_eq!(b.iter().cloned().collect::<Vec<_>>(), []);
+
+    // append nothing to something
+    a.append(&mut b);
+    assert_eq!(a.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]);
+    assert_eq!(b.iter().cloned().collect::<Vec<_>>(), []);
+
+    // append something to nothing
+    b.append(&mut a);
+    assert_eq!(b.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]);
+    assert_eq!(a.iter().cloned().collect::<Vec<_>>(), []);
+}
+
+#[test]
+fn test_retain() {
+    let mut buf = VecDeque::new();
+    buf.extend(1..5);
+    buf.retain(|&x| x % 2 == 0);
+    let v: Vec<_> = buf.into_iter().collect();
+    assert_eq!(&v[..], &[2, 4]);
+}
+
+#[test]
+fn test_extend_ref() {
+    let mut v = VecDeque::new();
+    v.push_back(1);
+    v.extend(&[2, 3, 4]);
+
+    assert_eq!(v.len(), 4);
+    assert_eq!(v[0], 1);
+    assert_eq!(v[1], 2);
+    assert_eq!(v[2], 3);
+    assert_eq!(v[3], 4);
+
+    let mut w = VecDeque::new();
+    w.push_back(5);
+    w.push_back(6);
+    v.extend(&w);
+
+    assert_eq!(v.len(), 6);
+    assert_eq!(v[0], 1);
+    assert_eq!(v[1], 2);
+    assert_eq!(v[2], 3);
+    assert_eq!(v[3], 4);
+    assert_eq!(v[4], 5);
+    assert_eq!(v[5], 6);
+}
+
+#[test]
+fn test_contains() {
+    let mut v = VecDeque::new();
+    v.extend(&[2, 3, 4]);
+
+    assert!(v.contains(&3));
+    assert!(!v.contains(&1));
+
+    v.clear();
+
+    assert!(!v.contains(&3));
+}
+
+#[allow(dead_code)]
+fn assert_covariance() {
+    fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
+        d
+    }
+}
+
+#[test]
+fn test_is_empty() {
+    let mut v = VecDeque::<i32>::new();
+    assert!(v.is_empty());
+    assert!(v.iter().is_empty());
+    assert!(v.iter_mut().is_empty());
+    v.extend(&[2, 3, 4]);
+    assert!(!v.is_empty());
+    assert!(!v.iter().is_empty());
+    assert!(!v.iter_mut().is_empty());
+    while let Some(_) = v.pop_front() {
+        assert_eq!(v.is_empty(), v.len() == 0);
+        assert_eq!(v.iter().is_empty(), v.iter().len() == 0);
+        assert_eq!(v.iter_mut().is_empty(), v.iter_mut().len() == 0);
+    }
+    assert!(v.is_empty());
+    assert!(v.iter().is_empty());
+    assert!(v.iter_mut().is_empty());
+    assert!(v.into_iter().is_empty());
+}
+
+#[test]
+fn test_placement_in() {
+    let mut buf: VecDeque<isize> = VecDeque::new();
+    buf.place_back() <- 1;
+    buf.place_back() <- 2;
+    assert_eq!(buf, [1,2]);
+
+    buf.place_front() <- 3;
+    buf.place_front() <- 4;
+    assert_eq!(buf, [4,3,1,2]);
+
+    {
+        let ptr_head = buf.place_front() <- 5;
+        assert_eq!(*ptr_head, 5);
+    }
+    {
+        let ptr_tail = buf.place_back() <- 6;
+        assert_eq!(*ptr_tail, 6);
+    }
+    assert_eq!(buf, [5,4,3,1,2,6]);
+}