core: Move the collections traits to libcollections

This commit moves Mutable, Map, MutableMap, Set, and MutableSet from
`core::collections` to the `collections` crate at the top-level. Additionally,
this removes the `deque` module and moves the `Deque` trait to only being
available at the top-level of the collections crate.

All functionality continues to be reexported through `std::collections`.

[breaking-change]

25 files changed, 171 insertions, 154 deletions

diff --git a/src/libcollections/bitv.rs b/src/libcollections/bitv.rs
index ac31fbbf9e4..42c81779770 100644
--- a/src/libcollections/bitv.rs
+++ b/src/libcollections/bitv.rs
@@ -20,6 +20,7 @@ use core::slice;
 use core::uint;
 use std::hash;
 
+use {Collection, Mutable, Set, MutableSet};
 use vec::Vec;
 
 #[deriving(Clone)]
@@ -1008,6 +1009,7 @@ mod tests {
     use std::rand::Rng;
     use test::Bencher;
 
+    use {Set, Mutable, MutableSet};
     use bitv::{Bitv, SmallBitv, BigBitv, BitvSet, from_bools, from_fn,
                from_bytes};
     use bitv;
diff --git a/src/libcollections/btree.rs b/src/libcollections/btree.rs
index ebca0157da4..82abe69a639 100644
--- a/src/libcollections/btree.rs
+++ b/src/libcollections/btree.rs
@@ -24,6 +24,7 @@ use alloc::owned::Box;
 use core::fmt;
 use core::fmt::Show;
 
+use Collection;
 use vec::Vec;
 
 #[allow(missing_doc)]
diff --git a/src/libcollections/deque.rs b/src/libcollections/deque.rs
index 5624c67f108..1faa9be99e3 100644
--- a/src/libcollections/deque.rs
+++ b/src/libcollections/deque.rs
@@ -10,41 +10,13 @@
 
 //! Container traits for collections
 
-use core::prelude::*;
-
-/// A double-ended sequence that allows querying, insertion and deletion at both ends.
-pub trait Deque<T> : Mutable {
-    /// Provide a reference to the front element, or None if the sequence is empty
-    fn front<'a>(&'a self) -> Option<&'a T>;
-
-    /// Provide a mutable reference to the front element, or None if the sequence is empty
-    fn front_mut<'a>(&'a mut self) -> Option<&'a mut T>;
-
-    /// Provide a reference to the back element, or None if the sequence is empty
-    fn back<'a>(&'a self) -> Option<&'a T>;
-
-    /// Provide a mutable reference to the back element, or None if the sequence is empty
-    fn back_mut<'a>(&'a mut self) -> Option<&'a mut T>;
-
-    /// Insert an element first in the sequence
-    fn push_front(&mut self, elt: T);
-
-    /// Insert an element last in the sequence
-    fn push_back(&mut self, elt: T);
-
-    /// Remove the last element and return it, or None if the sequence is empty
-    fn pop_back(&mut self) -> Option<T>;
-
-    /// Remove the first element and return it, or None if the sequence is empty
-    fn pop_front(&mut self) -> Option<T>;
-}
-
 #[cfg(test)]
 pub mod bench {
     use std::prelude::*;
     use std::rand;
     use std::rand::Rng;
     use test::Bencher;
+    use MutableMap;
 
     pub fn insert_rand_n<M:MutableMap<uint,uint>>(n: uint,
                                                   map: &mut M,
@@ -121,3 +93,4 @@ pub mod bench {
         })
      }
 }
+
diff --git a/src/libcollections/dlist.rs b/src/libcollections/dlist.rs
index f71cc7401c5..5a231245691 100644
--- a/src/libcollections/dlist.rs
+++ b/src/libcollections/dlist.rs
@@ -13,7 +13,7 @@
 //! The DList allows pushing and popping elements at either end.
 //!
 //! DList implements the trait Deque. It should be imported with `use
-//! collections::deque::Deque`.
+//! collections::Deque`.
 
 // DList is constructed like a singly-linked list over the field `next`.
 // including the last link being None; each Node owns its `next` field.
@@ -29,7 +29,7 @@ use core::iter;
 use core::mem;
 use core::ptr;
 
-use deque::Deque;
+use {Collection, Mutable, Deque};
 
 /// A doubly-linked list.
 pub struct DList<T> {
@@ -629,7 +629,7 @@ mod tests {
     use test::Bencher;
     use test;
 
-    use deque::Deque;
+    use Deque;
     use super::{DList, Node, ListInsertion};
     use vec::Vec;
 
diff --git a/src/libcollections/lib.rs b/src/libcollections/lib.rs
index c46ea84a765..602ecf39a83 100644
--- a/src/libcollections/lib.rs
+++ b/src/libcollections/lib.rs
@@ -32,9 +32,11 @@ extern crate alloc;
 #[cfg(test)] #[phase(syntax, link)] extern crate std;
 #[cfg(test)] #[phase(syntax, link)] extern crate log;
 
+use core::prelude::*;
+
+pub use core::collections::Collection;
 pub use bitv::{Bitv, BitvSet};
 pub use btree::BTree;
-pub use deque::Deque;
 pub use dlist::DList;
 pub use enum_set::EnumSet;
 pub use priority_queue::PriorityQueue;
@@ -47,7 +49,6 @@ mod macros;
 
 pub mod bitv;
 pub mod btree;
-pub mod deque;
 pub mod dlist;
 pub mod enum_set;
 pub mod priority_queue;
@@ -64,12 +65,120 @@ pub mod hash;
 // Internal unicode fiddly bits for the str module
 mod unicode;
 
-// FIXME(#14008) should this actually exist, or should a method be added?
-fn expect<T>(a: core::option::Option<T>, b: &str) -> T {
-    match a {
-        core::option::Some(a) => a,
-        core::option::None => fail!("{}", b),
+mod deque;
+
+/// A trait to represent mutable containers
+pub trait Mutable: Collection {
+    /// Clear the container, removing all values.
+    fn clear(&mut self);
+}
+
+/// A map is a key-value store where values may be looked up by their keys. This
+/// trait provides basic operations to operate on these stores.
+pub trait Map<K, V>: Collection {
+    /// Return a reference to the value corresponding to the key
+    fn find<'a>(&'a self, key: &K) -> Option<&'a V>;
+
+    /// Return true if the map contains a value for the specified key
+    #[inline]
+    fn contains_key(&self, key: &K) -> bool {
+        self.find(key).is_some()
+    }
+}
+
+/// This trait provides basic operations to modify the contents of a map.
+pub trait MutableMap<K, V>: Map<K, V> + Mutable {
+    /// Insert a key-value pair into the map. An existing value for a
+    /// key is replaced by the new value. Return true if the key did
+    /// not already exist in the map.
+    #[inline]
+    fn insert(&mut self, key: K, value: V) -> bool {
+        self.swap(key, value).is_none()
+    }
+
+    /// Remove a key-value pair from the map. Return true if the key
+    /// was present in the map, otherwise false.
+    #[inline]
+    fn remove(&mut self, key: &K) -> bool {
+        self.pop(key).is_some()
+    }
+
+    /// Insert a key-value pair from the map. If the key already had a value
+    /// present in the map, that value is returned. Otherwise None is returned.
+    fn swap(&mut self, k: K, v: V) -> Option<V>;
+
+    /// Removes a key from the map, returning the value at the key if the key
+    /// was previously in the map.
+    fn pop(&mut self, k: &K) -> Option<V>;
+
+    /// Return a mutable reference to the value corresponding to the key
+    fn find_mut<'a>(&'a mut self, key: &K) -> Option<&'a mut V>;
+}
+
+/// A set is a group of objects which are each distinct from one another. This
+/// trait represents actions which can be performed on sets to iterate over
+/// them.
+pub trait Set<T>: Collection {
+    /// Return true if the set contains a value
+    fn contains(&self, value: &T) -> bool;
+
+    /// Return true if the set has no elements in common with `other`.
+    /// This is equivalent to checking for an empty intersection.
+    fn is_disjoint(&self, other: &Self) -> bool;
+
+    /// Return true if the set is a subset of another
+    fn is_subset(&self, other: &Self) -> bool;
+
+    /// Return true if the set is a superset of another
+    fn is_superset(&self, other: &Self) -> bool {
+        other.is_subset(self)
     }
+
+    // FIXME #8154: Add difference, sym. difference, intersection and union iterators
+}
+
+/// This trait represents actions which can be performed on sets to mutate
+/// them.
+pub trait MutableSet<T>: Set<T> + Mutable {
+    /// Add a value to the set. Return true if the value was not already
+    /// present in the set.
+    fn insert(&mut self, value: T) -> bool;
+
+    /// Remove a value from the set. Return true if the value was
+    /// present in the set.
+    fn remove(&mut self, value: &T) -> bool;
+}
+
+/// A double-ended sequence that allows querying, insertion and deletion at both
+/// ends.
+pub trait Deque<T> : Mutable {
+    /// Provide a reference to the front element, or None if the sequence is
+    /// empty
+    fn front<'a>(&'a self) -> Option<&'a T>;
+
+    /// Provide a mutable reference to the front element, or None if the
+    /// sequence is empty
+    fn front_mut<'a>(&'a mut self) -> Option<&'a mut T>;
+
+    /// Provide a reference to the back element, or None if the sequence is
+    /// empty
+    fn back<'a>(&'a self) -> Option<&'a T>;
+
+    /// Provide a mutable reference to the back element, or None if the sequence
+    /// is empty
+    fn back_mut<'a>(&'a mut self) -> Option<&'a mut T>;
+
+    /// Insert an element first in the sequence
+    fn push_front(&mut self, elt: T);
+
+    /// Insert an element last in the sequence
+    fn push_back(&mut self, elt: T);
+
+    /// Remove the last element and return it, or None if the sequence is empty
+    fn pop_back(&mut self) -> Option<T>;
+
+    /// Remove the first element and return it, or None if the sequence is empty
+    fn pop_front(&mut self) -> Option<T>;
 }
 
 // FIXME(#14344) this shouldn't be necessary
diff --git a/src/libcollections/priority_queue.rs b/src/libcollections/priority_queue.rs
index f10c6f230ae..ea3e7d17471 100644
--- a/src/libcollections/priority_queue.rs
+++ b/src/libcollections/priority_queue.rs
@@ -17,6 +17,7 @@ use core::prelude::*;
 use core::mem::{zeroed, replace, swap};
 use core::ptr;
 
+use {Collection, Mutable};
 use slice;
 use vec::Vec;
 
diff --git a/src/libcollections/ringbuf.rs b/src/libcollections/ringbuf.rs
index 5708dfaf915..addf73d67a8 100644
--- a/src/libcollections/ringbuf.rs
+++ b/src/libcollections/ringbuf.rs
@@ -11,7 +11,7 @@
 //! A double-ended queue implemented as a circular buffer
 //!
 //! RingBuf implements the trait Deque. It should be imported with `use
-//! collections::deque::Deque`.
+//! collections::Deque`.
 
 use core::prelude::*;
 
@@ -19,7 +19,7 @@ use core::cmp;
 use core::fmt;
 use core::iter::RandomAccessIterator;
 
-use deque::Deque;
+use {Deque, Collection, Mutable};
 use vec::Vec;
 
 static INITIAL_CAPACITY: uint = 8u; // 2^3
@@ -415,7 +415,7 @@ mod tests {
     use test::Bencher;
     use test;
 
-    use deque::Deque;
+    use {Deque, Mutable};
     use super::RingBuf;
     use vec::Vec;
 
diff --git a/src/libcollections/slice.rs b/src/libcollections/slice.rs
index 4798218e3ff..1bc56368693 100644
--- a/src/libcollections/slice.rs
+++ b/src/libcollections/slice.rs
@@ -109,6 +109,8 @@ use core::mem::transmute;
 use core::mem;
 use core::ptr;
 use core::iter::{range_step, MultiplicativeIterator};
+
+use Collection;
 use vec::Vec;
 
 pub use core::slice::{ref_slice, mut_ref_slice, Splits, Windows};
@@ -296,9 +298,9 @@ impl<'a, T: Clone> CloneableVector<T> for &'a [T] {
 
         let len = self.len();
         let data_size = len.checked_mul(&mem::size_of::<T>());
-        let data_size = ::expect(data_size, "overflow in to_owned()");
+        let data_size = data_size.expect("overflow in to_owned()");
         let size = mem::size_of::<RawVec<()>>().checked_add(&data_size);
-        let size = ::expect(size, "overflow in to_owned()");
+        let size = size.expect("overflow in to_owned()");
 
         unsafe {
             // this should pass the real required alignment
@@ -865,6 +867,7 @@ mod tests {
     use std::rt;
     use slice::*;
 
+    use Mutable;
     use vec::Vec;
 
     fn square(n: uint) -> uint { n * n }
diff --git a/src/libcollections/smallintmap.rs b/src/libcollections/smallintmap.rs
index c61f518caa4..cc901864ab5 100644
--- a/src/libcollections/smallintmap.rs
+++ b/src/libcollections/smallintmap.rs
@@ -21,6 +21,7 @@ use core::fmt;
 use core::iter::{Enumerate, FilterMap};
 use core::mem::replace;
 
+use {Collection, Mutable, Map, MutableMap};
 use {vec, slice};
 use vec::Vec;
 
@@ -123,7 +124,7 @@ impl<V> SmallIntMap<V> {
     }
 
     pub fn get<'a>(&'a self, key: &uint) -> &'a V {
-        ::expect(self.find(key), "key not present")
+        self.find(key).expect("key not present")
     }
 
     /// An iterator visiting all key-value pairs in ascending order by the keys.
@@ -264,6 +265,7 @@ double_ended_iterator!(impl MutEntries -> (uint, &'a mut T), get_mut_ref)
 mod test_map {
     use std::prelude::*;
 
+    use {Map, MutableMap, Mutable};
     use super::SmallIntMap;
 
     #[test]
diff --git a/src/libcollections/str.rs b/src/libcollections/str.rs
index 102d9c3abde..49d8775dd9c 100644
--- a/src/libcollections/str.rs
+++ b/src/libcollections/str.rs
@@ -76,6 +76,7 @@ use core::cmp;
 use core::iter::AdditiveIterator;
 use core::mem;
 
+use Collection;
 use hash;
 use string::String;
 use vec::Vec;
diff --git a/src/libcollections/string.rs b/src/libcollections/string.rs
index 1c1d4b98592..76f53c9b257 100644
--- a/src/libcollections/string.rs
+++ b/src/libcollections/string.rs
@@ -18,6 +18,7 @@ use core::mem;
 use core::ptr;
 use core::raw::Slice;
 
+use {Collection, Mutable};
 use hash;
 use str;
 use str::{CharRange, StrAllocating};
@@ -356,6 +357,7 @@ mod tests {
     use std::prelude::*;
     use test::Bencher;
 
+    use Mutable;
     use str::{Str, StrSlice};
     use super::String;
 
diff --git a/src/libcollections/treemap.rs b/src/libcollections/treemap.rs
index 8d472282a68..489fe60cebf 100644
--- a/src/libcollections/treemap.rs
+++ b/src/libcollections/treemap.rs
@@ -22,6 +22,7 @@ use core::iter;
 use core::mem::{replace, swap};
 use core::ptr;
 
+use {Collection, Mutable, Set, MutableSet, MutableMap, Map};
 use vec::Vec;
 
 // This is implemented as an AA tree, which is a simplified variation of
@@ -1006,6 +1007,7 @@ mod test_treemap {
     use std::rand::Rng;
     use std::rand;
 
+    use {Map, MutableMap, Mutable};
     use super::{TreeMap, TreeNode};
 
     #[test]
@@ -1437,7 +1439,6 @@ mod test_treemap {
 
 #[cfg(test)]
 mod bench {
-    use std::prelude::*;
     use test::Bencher;
 
     use super::TreeMap;
@@ -1500,6 +1501,7 @@ mod bench {
 mod test_set {
     use std::prelude::*;
 
+    use {Set, MutableSet, Mutable, MutableMap};
     use super::{TreeMap, TreeSet};
 
     #[test]
diff --git a/src/libcollections/trie.rs b/src/libcollections/trie.rs
index 1c6b7ed9333..6e99d6054a5 100644
--- a/src/libcollections/trie.rs
+++ b/src/libcollections/trie.rs
@@ -17,6 +17,7 @@ use core::mem::zeroed;
 use core::mem;
 use core::uint;
 
+use {Collection, Mutable, Map, MutableMap, Set, MutableSet};
 use slice::{Items, MutItems};
 use slice;
 
@@ -645,6 +646,7 @@ mod test_map {
     use std::iter::range_step;
     use std::uint;
 
+    use {MutableMap, Map};
     use super::{TrieMap, TrieNode, Internal, External, Nothing};
 
     fn check_integrity<T>(trie: &TrieNode<T>) {
@@ -923,6 +925,7 @@ mod bench_map {
     use std::rand::{weak_rng, Rng};
     use test::Bencher;
 
+    use MutableMap;
     use super::TrieMap;
 
     #[bench]
@@ -1031,6 +1034,7 @@ mod test_set {
     use std::prelude::*;
     use std::uint;
 
+    use {MutableSet, Set};
     use super::TrieSet;
 
     #[test]
diff --git a/src/libcollections/vec.rs b/src/libcollections/vec.rs
index 3d0182acc7e..dbef73efc47 100644
--- a/src/libcollections/vec.rs
+++ b/src/libcollections/vec.rs
@@ -24,6 +24,7 @@ use core::num;
 use core::ptr;
 use core::uint;
 
+use {Collection, Mutable};
 use slice::{MutableOrdVector, OwnedVector, MutableVectorAllocating};
 use slice::{Items, MutItems};
 
@@ -91,8 +92,8 @@ impl<T> Vec<T> {
         } else if capacity == 0 {
             Vec::new()
         } else {
-            let size = ::expect(capacity.checked_mul(&mem::size_of::<T>()),
-                                "capacity overflow");
+            let size = capacity.checked_mul(&mem::size_of::<T>())
+                               .expect("capacity overflow");
             let ptr = unsafe { allocate(size, mem::min_align_of::<T>()) };
             Vec { len: 0, cap: capacity, ptr: ptr as *mut T }
         }
@@ -499,8 +500,8 @@ impl<T> Vec<T> {
         if mem::size_of::<T>() == 0 { return }
 
         if capacity > self.cap {
-            let size = ::expect(capacity.checked_mul(&mem::size_of::<T>()),
-                                "capacity overflow");
+            let size = capacity.checked_mul(&mem::size_of::<T>())
+                               .expect("capacity overflow");
             unsafe {
                 self.ptr = alloc_or_realloc(self.ptr, size,
                                             self.cap * mem::size_of::<T>());
@@ -579,7 +580,7 @@ impl<T> Vec<T> {
     pub fn push(&mut self, value: T) {
         if mem::size_of::<T>() == 0 {
             // zero-size types consume no memory, so we can't rely on the address space running out
-            self.len = ::expect(self.len.checked_add(&1), "length overflow");
+            self.len = self.len.checked_add(&1).expect("length overflow");
             unsafe { mem::forget(value); }
             return
         }
@@ -1526,9 +1527,9 @@ impl<T> FromVec<T> for ~[T] {
     fn from_vec(mut v: Vec<T>) -> ~[T] {
         let len = v.len();
         let data_size = len.checked_mul(&mem::size_of::<T>());
-        let data_size = ::expect(data_size, "overflow in from_vec()");
+        let data_size = data_size.expect("overflow in from_vec()");
         let size = mem::size_of::<RawVec<()>>().checked_add(&data_size);
-        let size = ::expect(size, "overflow in from_vec()");
+        let size = size.expect("overflow in from_vec()");
 
         // In a post-DST world, we can attempt to reuse the Vec allocation by calling
         // shrink_to_fit() on it. That may involve a reallocation+memcpy, but that's no
diff --git a/src/libcore/collections.rs b/src/libcore/collections.rs
index 8ebc7c2f7fe..0bb9289397a 100644
--- a/src/libcore/collections.rs
+++ b/src/libcore/collections.rs
@@ -8,9 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-//! Traits for generic collections (including `Map` and `Set`)
-
-use option::Option;
+//! Traits for generic collections
 
 /// A trait to represent the abstract idea of a container. The only concrete
 /// knowledge known is the number of elements contained within.
@@ -24,85 +22,3 @@ pub trait Collection {
         self.len() == 0
     }
 }
-
-/// A trait to represent mutable containers
-pub trait Mutable: Collection {
-    /// Clear the container, removing all values.
-    fn clear(&mut self);
-}
-
-/// A map is a key-value store where values may be looked up by their keys. This
-/// trait provides basic operations to operate on these stores.
-pub trait Map<K, V>: Collection {
-    /// Return a reference to the value corresponding to the key
-    fn find<'a>(&'a self, key: &K) -> Option<&'a V>;
-
-    /// Return true if the map contains a value for the specified key
-    #[inline]
-    fn contains_key(&self, key: &K) -> bool {
-        self.find(key).is_some()
-    }
-}
-
-/// This trait provides basic operations to modify the contents of a map.
-pub trait MutableMap<K, V>: Map<K, V> + Mutable {
-    /// Insert a key-value pair into the map. An existing value for a
-    /// key is replaced by the new value. Return true if the key did
-    /// not already exist in the map.
-    #[inline]
-    fn insert(&mut self, key: K, value: V) -> bool {
-        self.swap(key, value).is_none()
-    }
-
-    /// Remove a key-value pair from the map. Return true if the key
-    /// was present in the map, otherwise false.
-    #[inline]
-    fn remove(&mut self, key: &K) -> bool {
-        self.pop(key).is_some()
-    }
-
-    /// Insert a key-value pair from the map. If the key already had a value
-    /// present in the map, that value is returned. Otherwise None is returned.
-    fn swap(&mut self, k: K, v: V) -> Option<V>;
-
-    /// Removes a key from the map, returning the value at the key if the key
-    /// was previously in the map.
-    fn pop(&mut self, k: &K) -> Option<V>;
-
-    /// Return a mutable reference to the value corresponding to the key
-    fn find_mut<'a>(&'a mut self, key: &K) -> Option<&'a mut V>;
-}
-
-/// A set is a group of objects which are each distinct from one another. This
-/// trait represents actions which can be performed on sets to iterate over
-/// them.
-pub trait Set<T>: Collection {
-    /// Return true if the set contains a value
-    fn contains(&self, value: &T) -> bool;
-
-    /// Return true if the set has no elements in common with `other`.
-    /// This is equivalent to checking for an empty intersection.
-    fn is_disjoint(&self, other: &Self) -> bool;
-
-    /// Return true if the set is a subset of another
-    fn is_subset(&self, other: &Self) -> bool;
-
-    /// Return true if the set is a superset of another
-    fn is_superset(&self, other: &Self) -> bool {
-        other.is_subset(self)
-    }
-
-    // FIXME #8154: Add difference, sym. difference, intersection and union iterators
-}
-
-/// This trait represents actions which can be performed on sets to mutate
-/// them.
-pub trait MutableSet<T>: Set<T> + Mutable {
-    /// Add a value to the set. Return true if the value was not already
-    /// present in the set.
-    fn insert(&mut self, value: T) -> bool;
-
-    /// Remove a value from the set. Return true if the value was
-    /// present in the set.
-    fn remove(&mut self, value: &T) -> bool;
-}
diff --git a/src/libstd/collections/hashmap.rs b/src/libstd/collections/hashmap.rs
index 1f3c34600bd..a780b63bfd0 100644
--- a/src/libstd/collections/hashmap.rs
+++ b/src/libstd/collections/hashmap.rs
@@ -12,7 +12,7 @@
 
 use clone::Clone;
 use cmp::{max, Eq, Equiv, PartialEq};
-use container::{Container, Mutable, Set, MutableSet, Map, MutableMap};
+use collections::{Collection, Mutable, Set, MutableSet, Map, MutableMap};
 use default::Default;
 use fmt::Show;
 use fmt;
@@ -930,7 +930,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     }
 }
 
-impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> Container for HashMap<K, V, H> {
+impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> Collection for HashMap<K, V, H> {
     /// Return the number of elements in the map
     fn len(&self) -> uint { self.table.size() }
 }
@@ -2160,7 +2160,7 @@ mod test_set {
 
     use super::HashSet;
     use slice::ImmutableEqVector;
-    use std::collections::Collection;
+    use collections::Collection;
 
     #[test]
     fn test_disjoint() {
diff --git a/src/libstd/collections/lru_cache.rs b/src/libstd/collections/lru_cache.rs
index 5f32abfe653..72d96804d6d 100644
--- a/src/libstd/collections/lru_cache.rs
+++ b/src/libstd/collections/lru_cache.rs
@@ -38,8 +38,7 @@
 //! ```
 
 use cmp::{PartialEq, Eq};
-use collections::HashMap;
-use container::{Container, Mutable, MutableMap};
+use collections::{HashMap, Collection, Mutable, MutableMap};
 use fmt;
 use hash::Hash;
 use iter::{range, Iterator};
diff --git a/src/libstd/collections/mod.rs b/src/libstd/collections/mod.rs
index 16a6a35d9d5..9e5288f9541 100644
--- a/src/libstd/collections/mod.rs
+++ b/src/libstd/collections/mod.rs
@@ -12,10 +12,12 @@
  * Collection types.
  */
 
-pub use core_collections::{Bitv, BitvSet, BTree, Deque, DList, EnumSet};
+pub use core_collections::{Collection, Mutable, Map, MutableMap};
+pub use core_collections::{Set, MutableSet, Deque};
+pub use core_collections::{Bitv, BitvSet, BTree, DList, EnumSet};
 pub use core_collections::{PriorityQueue, RingBuf, SmallIntMap};
 pub use core_collections::{TreeMap, TreeSet, TrieMap, TrieSet};
-pub use core_collections::{bitv, btree, deque, dlist, enum_set};
+pub use core_collections::{bitv, btree, dlist, enum_set};
 pub use core_collections::{priority_queue, ringbuf, smallintmap, treemap, trie};
 
 pub use self::hashmap::{HashMap, HashSet};
diff --git a/src/libstd/lib.rs b/src/libstd/lib.rs
index d319d6bd03d..fbdbc13e1b4 100644
--- a/src/libstd/lib.rs
+++ b/src/libstd/lib.rs
@@ -144,7 +144,6 @@ pub use core::cell;
 pub use core::char;
 pub use core::clone;
 #[cfg(not(test))] pub use core::cmp;
-pub use core::collections;
 pub use core::default;
 pub use core::finally;
 pub use core::intrinsics;
diff --git a/src/libstd/path/posix.rs b/src/libstd/path/posix.rs
index 8dfb64194e7..171535edbeb 100644
--- a/src/libstd/path/posix.rs
+++ b/src/libstd/path/posix.rs
@@ -13,7 +13,7 @@
 use c_str::{CString, ToCStr};
 use clone::Clone;
 use cmp::{PartialEq, Eq};
-use container::Container;
+use collections::Collection;
 use from_str::FromStr;
 use hash;
 use io::Writer;
diff --git a/src/libstd/prelude.rs b/src/libstd/prelude.rs
index 54dcbd1812f..485c2140a8d 100644
--- a/src/libstd/prelude.rs
+++ b/src/libstd/prelude.rs
@@ -60,8 +60,8 @@
 #[doc(no_inline)] pub use clone::Clone;
 #[doc(no_inline)] pub use cmp::{PartialEq, PartialOrd, Eq, Ord};
 #[doc(no_inline)] pub use cmp::{Ordering, Less, Equal, Greater, Equiv};
-#[doc(no_inline)] pub use container::{Container, Mutable, Map, MutableMap};
-#[doc(no_inline)] pub use container::{Set, MutableSet};
+#[doc(no_inline)] pub use collections::{Collection, Mutable, Map, MutableMap};
+#[doc(no_inline)] pub use collections::{Set, MutableSet};
 #[doc(no_inline)] pub use iter::{FromIterator, Extendable, ExactSize};
 #[doc(no_inline)] pub use iter::{Iterator, DoubleEndedIterator};
 #[doc(no_inline)] pub use iter::{RandomAccessIterator, CloneableIterator};
diff --git a/src/libstd/rand/os.rs b/src/libstd/rand/os.rs
index 284d41d3208..2654b7a1acc 100644
--- a/src/libstd/rand/os.rs
+++ b/src/libstd/rand/os.rs
@@ -62,7 +62,7 @@ mod imp {
 mod imp {
     extern crate libc;
 
-    use container::Container;
+    use core_collections::Collection;
     use io::{IoResult, IoError};
     use mem;
     use ops::Drop;
diff --git a/src/libstd/rand/reader.rs b/src/libstd/rand/reader.rs
index 170884073f3..8655d1e47d5 100644
--- a/src/libstd/rand/reader.rs
+++ b/src/libstd/rand/reader.rs
@@ -10,7 +10,7 @@
 
 //! A wrapper around any Reader to treat it as an RNG.
 
-use container::Container;
+use collections::Collection;
 use io::Reader;
 use rand::Rng;
 use result::{Ok, Err};
diff --git a/src/libstd/rt/backtrace.rs b/src/libstd/rt/backtrace.rs
index d52c63abe1b..83fc95267af 100644
--- a/src/libstd/rt/backtrace.rs
+++ b/src/libstd/rt/backtrace.rs
@@ -602,7 +602,7 @@ mod imp {
 #[allow(dead_code, uppercase_variables)]
 mod imp {
     use c_str::CString;
-    use container::Container;
+    use core_collections::Collection;
     use intrinsics;
     use io::{IoResult, Writer};
     use libc;
diff --git a/src/test/compile-fail/map-types.rs b/src/test/compile-fail/map-types.rs
index 61c26d4d8fd..bb5f020e78c 100644
--- a/src/test/compile-fail/map-types.rs
+++ b/src/test/compile-fail/map-types.rs
@@ -18,6 +18,6 @@ fn main() {
     let x: Box<HashMap<int, int>> = box HashMap::new();
     let x: Box<Map<int, int>> = x;
     let y: Box<Map<uint, int>> = box x;
-    //~^ ERROR failed to find an implementation of trait core::collections::Map<uint,int>
-    //         for ~core::collections::Map<int,int>:Send
+    //~^ ERROR failed to find an implementation of trait collections::Map<uint,int>
+    //         for ~collections::Map<int,int>:Send
 }