Move std::{trie, hashmap} to libcollections

These two containers are indeed collections, so their place is in
libcollections, not in libstd. There will always be a hash map as part of the
standard distribution of Rust, but by moving it out of the standard library it
makes libstd that much more portable to more platforms and environments.

This conveniently also removes the stuttering of 'std::hashmap::HashMap',
although 'collections::HashMap' is only one character shorter.

109 files changed, 448 insertions, 436 deletions

diff --git a/mk/crates.mk b/mk/crates.mk
index af791c54edd..8e624cb313f 100644
--- a/mk/crates.mk
+++ b/mk/crates.mk
@@ -69,7 +69,7 @@ DEPS_flate := std native:miniz
 DEPS_arena := std collections
 DEPS_glob := std
 DEPS_serialize := std
-DEPS_term := std
+DEPS_term := std collections
 DEPS_semver := std
 DEPS_uuid := std serialize
 DEPS_sync := std
diff --git a/src/doc/rust.md b/src/doc/rust.md
index 9173156d91d..6d9cb8b5d7b 100644
--- a/src/doc/rust.md
+++ b/src/doc/rust.md
@@ -467,7 +467,7 @@ expression context, the final namespace qualifier is omitted.
 Two examples of paths with type arguments:
 
 ~~~~
-# use std::hashmap::HashMap;
+# struct HashMap<K, V>;
 # fn f() {
 # fn id<T>(t: T) -> T { t }
 type T = HashMap<int,~str>;  // Type arguments used in a type expression
diff --git a/src/doc/tutorial.md b/src/doc/tutorial.md
index 6454e22b896..304dc1fb5af 100644
--- a/src/doc/tutorial.md
+++ b/src/doc/tutorial.md
@@ -1977,8 +1977,8 @@ illegal to copy and pass by value.
 Generic `type`, `struct`, and `enum` declarations follow the same pattern:
 
 ~~~~
-use std::hashmap::HashMap;
-type Set<T> = HashMap<T, ()>;
+extern crate collections;
+type Set<T> = collections::HashMap<T, ()>;
 
 struct Stack<T> {
     elements: ~[T]
@@ -1988,6 +1988,7 @@ enum Option<T> {
     Some(T),
     None
 }
+# fn main() {}
 ~~~~
 
 These declarations can be instantiated to valid types like `Set<int>`,
diff --git a/src/etc/combine-tests.py b/src/etc/combine-tests.py
index c972392a4a0..2590db56d0a 100755
--- a/src/etc/combine-tests.py
+++ b/src/etc/combine-tests.py
@@ -55,6 +55,8 @@ c.write(
 #[crate_id=\"run_pass_stage2#0.1\"];
 #[feature(globs, macro_rules, struct_variant, managed_boxes)];
 #[allow(warnings)];
+extern crate collections;
+extern crate extra;
 """
 )
 for t in stage2_tests:
diff --git a/src/libstd/hashmap.rs b/src/libcollections/hashmap.rs
index f3783c27b54..5cdd5bf3812 100644
--- a/src/libstd/hashmap.rs
+++ b/src/libcollections/hashmap.rs
@@ -16,7 +16,7 @@
 //! # Example
 //!
 //! ```rust
-//! use std::hashmap::HashMap;
+//! use collections::HashMap;
 //!
 //! // type inference lets us omit an explicit type signature (which
 //! // would be `HashMap<&str, &str>` in this example).
@@ -52,24 +52,20 @@
 //! }
 //! ```
 
-use container::{Container, Mutable, Map, MutableMap, Set, MutableSet};
-use clone::Clone;
-use cmp::{Eq, Equiv, max};
-use default::Default;
-use fmt;
-use hash_old::Hash;
-use iter;
-use iter::{Iterator, FromIterator, Extendable};
-use iter::{FilterMap, Chain, Repeat, Zip};
-use mem::replace;
-use num;
-use option::{None, Option, Some};
-use rand::Rng;
-use rand;
-use result::{Ok, Err};
-use vec::{ImmutableVector, MutableVector, OwnedVector, Items, MutItems};
-use vec_ng;
-use vec_ng::Vec;
+use std::cmp::max;
+use std::fmt;
+use std::hash_old::Hash;
+use std::iter::{FilterMap, Chain, Repeat, Zip};
+use std::iter;
+use std::mem::replace;
+use std::num;
+use std::rand::Rng;
+use std::rand;
+use std::vec::{Items, MutItems};
+use std::vec_ng::Vec;
+use std::vec_ng;
+
+use serialize::{Encodable, Decodable, Encoder, Decoder};
 
 static INITIAL_CAPACITY: uint = 32u; // 2^5
 
@@ -404,7 +400,7 @@ impl<K: Hash + Eq, V> HashMap<K, V> {
     /// # Example
     ///
     /// ```rust
-    /// use std::hashmap::HashMap;
+    /// use collections::HashMap;
     ///
     /// // map some strings to vectors of strings
     /// let mut map = HashMap::<~str, ~[~str]>::new();
@@ -613,6 +609,10 @@ impl<A: fmt::Show + Hash + Eq, B: fmt::Show> fmt::Show for HashMap<A, B> {
     }
 }
 
+impl<K: fmt::Show + Hash + Eq, V: fmt::Show> ToStr for HashMap<K, V> {
+    fn to_str(&self) -> ~str { format!("{}", *self) }
+}
+
 /// HashMap iterator
 #[deriving(Clone)]
 pub struct Entries<'a, K, V> {
@@ -891,6 +891,10 @@ impl<A: fmt::Show + Hash + Eq> fmt::Show for HashSet<A> {
     }
 }
 
+impl<A: fmt::Show + Hash + Eq> ToStr for HashSet<A> {
+    fn to_str(&self) -> ~str { format!("{}", *self) }
+}
+
 impl<K: Eq + Hash> FromIterator<K> for HashSet<K> {
     fn from_iterator<T: Iterator<K>>(iter: &mut T) -> HashSet<K> {
         let (lower, _) = iter.size_hint();
@@ -919,12 +923,75 @@ pub type SetAlgebraItems<'a, T> =
     FilterMap<'static,(&'a HashSet<T>, &'a T), &'a T,
               Zip<Repeat<&'a HashSet<T>>,SetItems<'a,T>>>;
 
+impl<
+    E: Encoder,
+    K: Encodable<E> + Hash + IterBytes + Eq,
+    V: Encodable<E>
+> Encodable<E> for HashMap<K, V> {
+    fn encode(&self, e: &mut E) {
+        e.emit_map(self.len(), |e| {
+            let mut i = 0;
+            for (key, val) in self.iter() {
+                e.emit_map_elt_key(i, |e| key.encode(e));
+                e.emit_map_elt_val(i, |e| val.encode(e));
+                i += 1;
+            }
+        })
+    }
+}
+
+impl<
+    D: Decoder,
+    K: Decodable<D> + Hash + IterBytes + Eq,
+    V: Decodable<D>
+> Decodable<D> for HashMap<K, V> {
+    fn decode(d: &mut D) -> HashMap<K, V> {
+        d.read_map(|d, len| {
+            let mut map = HashMap::with_capacity(len);
+            for i in range(0u, len) {
+                let key = d.read_map_elt_key(i, |d| Decodable::decode(d));
+                let val = d.read_map_elt_val(i, |d| Decodable::decode(d));
+                map.insert(key, val);
+            }
+            map
+        })
+    }
+}
+
+impl<
+    S: Encoder,
+    T: Encodable<S> + Hash + IterBytes + Eq
+> Encodable<S> for HashSet<T> {
+    fn encode(&self, s: &mut S) {
+        s.emit_seq(self.len(), |s| {
+            let mut i = 0;
+            for e in self.iter() {
+                s.emit_seq_elt(i, |s| e.encode(s));
+                i += 1;
+            }
+        })
+    }
+}
+
+impl<
+    D: Decoder,
+    T: Decodable<D> + Hash + IterBytes + Eq
+> Decodable<D> for HashSet<T> {
+    fn decode(d: &mut D) -> HashSet<T> {
+        d.read_seq(|d, len| {
+            let mut set = HashSet::with_capacity(len);
+            for i in range(0u, len) {
+                set.insert(d.read_seq_elt(i, |d| Decodable::decode(d)));
+            }
+            set
+        })
+    }
+}
 
 #[cfg(test)]
 mod test_map {
-    use prelude::*;
-    use super::*;
-    use fmt;
+    use super::{HashMap, HashSet};
+    use std::fmt;
 
     #[test]
     fn test_create_capacity_zero() {
@@ -1180,14 +1247,49 @@ mod test_map {
         assert!(table_str == ~"{1: s2, 3: s4}" || table_str == ~"{3: s4, 1: s2}");
         assert_eq!(format!("{}", empty), ~"{}");
     }
+
+    struct StructWithToStrWithoutEqOrHash {
+        value: int
+    }
+
+    impl fmt::Show for StructWithToStrWithoutEqOrHash {
+        fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+            write!(f.buf, "s{}", self.value)
+        }
+    }
+
+    #[test]
+    fn test_hashset() {
+        let mut set: HashSet<int> = HashSet::new();
+        let empty_set: HashSet<int> = HashSet::new();
+
+        set.insert(1);
+        set.insert(2);
+
+        let set_str = set.to_str();
+
+        assert!(set_str == ~"{1, 2}" || set_str == ~"{2, 1}");
+        assert_eq!(empty_set.to_str(), ~"{}");
+    }
+
+    #[test]
+    fn test_hashmap() {
+        let mut table: HashMap<int, StructWithToStrWithoutEqOrHash> = HashMap::new();
+        let empty: HashMap<int, StructWithToStrWithoutEqOrHash> = HashMap::new();
+
+        table.insert(3, StructWithToStrWithoutEqOrHash { value: 4 });
+        table.insert(1, StructWithToStrWithoutEqOrHash { value: 2 });
+
+        let table_str = table.to_str();
+
+        assert!(table_str == ~"{1: s2, 3: s4}" || table_str == ~"{3: s4, 1: s2}");
+        assert_eq!(empty.to_str(), ~"{}");
+    }
 }
 
 #[cfg(test)]
 mod test_set {
-    use super::*;
-    use prelude::*;
-    use container::Container;
-    use vec::ImmutableEqVector;
+    use super::HashSet;
 
     #[test]
     fn test_disjoint() {
diff --git a/src/libcollections/lib.rs b/src/libcollections/lib.rs
index e3413adfe91..dd42c2a0dd0 100644
--- a/src/libcollections/lib.rs
+++ b/src/libcollections/lib.rs
@@ -27,21 +27,25 @@ pub use btree::BTree;
 pub use deque::Deque;
 pub use dlist::DList;
 pub use enum_set::EnumSet;
+pub use hashmap::{HashMap, HashSet};
 pub use list::List;
 pub use lru_cache::LruCache;
 pub use priority_queue::PriorityQueue;
 pub use ringbuf::RingBuf;
 pub use smallintmap::SmallIntMap;
 pub use treemap::{TreeMap, TreeSet};
+pub use trie::{TrieMap, TrieSet};
 
 pub mod bitv;
 pub mod btree;
 pub mod deque;
 pub mod dlist;
 pub mod enum_set;
+pub mod hashmap;
 pub mod list;
 pub mod lru_cache;
 pub mod priority_queue;
 pub mod ringbuf;
 pub mod smallintmap;
 pub mod treemap;
+pub mod trie;
diff --git a/src/libcollections/lru_cache.rs b/src/libcollections/lru_cache.rs
index de7b511fd41..d05d2f2d981 100644
--- a/src/libcollections/lru_cache.rs
+++ b/src/libcollections/lru_cache.rs
@@ -38,11 +38,12 @@
 //! ```
 
 use std::container::Container;
-use std::hashmap::HashMap;
 use std::to_bytes::Cb;
 use std::ptr;
 use std::cast;
 
+use HashMap;
+
 struct KeyRef<K> { k: *K }
 
 struct LruEntry<K, V> {
diff --git a/src/libstd/trie.rs b/src/libcollections/trie.rs
index d17d59f8665..022a64fbb7a 100644
--- a/src/libstd/trie.rs
+++ b/src/libcollections/trie.rs
@@ -10,15 +10,13 @@
 
 //! Ordered containers with integer keys, implemented as radix tries (`TrieSet` and `TrieMap` types)
 
-use option::{None, Option, Some};
-use container::{Container, Map, Mutable, MutableMap};
-use iter::{Extendable, FromIterator, Iterator};
-use mem;
-use uint;
-use mem::init;
-use vec;
-use ptr::RawPtr;
-use vec::{ImmutableVector, Items, MutableVector, MutItems, OwnedVector};
+use std::mem;
+use std::uint;
+use std::mem::init;
+use std::vec;
+use std::vec::{Items, MutItems};
+
+use serialize::{Encodable, Decodable, Encoder, Decoder};
 
 // FIXME: #5244: need to manually update the TrieNode constructor
 static SHIFT: uint = 4;
@@ -622,32 +620,83 @@ impl<'a> Iterator<uint> for SetItems<'a> {
     }
 }
 
-#[cfg(test)]
-pub fn check_integrity<T>(trie: &TrieNode<T>) {
-    assert!(trie.count != 0);
-
-    let mut sum = 0;
-
-    for x in trie.children.iter() {
-        match *x {
-          Nothing => (),
-          Internal(ref y) => {
-              check_integrity(&**y);
-              sum += 1
-          }
-          External(_, _) => { sum += 1 }
-        }
+impl<
+    E: Encoder,
+    V: Encodable<E>
+> Encodable<E> for TrieMap<V> {
+    fn encode(&self, e: &mut E) {
+        e.emit_map(self.len(), |e| {
+                for (i, (key, val)) in self.iter().enumerate() {
+                    e.emit_map_elt_key(i, |e| key.encode(e));
+                    e.emit_map_elt_val(i, |e| val.encode(e));
+                }
+            });
     }
+}
 
-    assert_eq!(sum, trie.count);
+impl<
+    D: Decoder,
+    V: Decodable<D>
+> Decodable<D> for TrieMap<V> {
+    fn decode(d: &mut D) -> TrieMap<V> {
+        d.read_map(|d, len| {
+            let mut map = TrieMap::new();
+            for i in range(0u, len) {
+                let key = d.read_map_elt_key(i, |d| Decodable::decode(d));
+                let val = d.read_map_elt_val(i, |d| Decodable::decode(d));
+                map.insert(key, val);
+            }
+            map
+        })
+    }
+}
+
+impl<S: Encoder> Encodable<S> for TrieSet {
+    fn encode(&self, s: &mut S) {
+        s.emit_seq(self.len(), |s| {
+                for (i, e) in self.iter().enumerate() {
+                    s.emit_seq_elt(i, |s| e.encode(s));
+                }
+            })
+    }
+}
+
+impl<D: Decoder> Decodable<D> for TrieSet {
+    fn decode(d: &mut D) -> TrieSet {
+        d.read_seq(|d, len| {
+            let mut set = TrieSet::new();
+            for i in range(0u, len) {
+                set.insert(d.read_seq_elt(i, |d| Decodable::decode(d)));
+            }
+            set
+        })
+    }
 }
 
 #[cfg(test)]
 mod test_map {
-    use super::*;
-    use prelude::*;
-    use iter::range_step;
-    use uint;
+    use super::{TrieMap, TrieNode, Internal, External};
+    use std::iter::range_step;
+    use std::uint;
+
+    fn check_integrity<T>(trie: &TrieNode<T>) {
+        assert!(trie.count != 0);
+
+        let mut sum = 0;
+
+        for x in trie.children.iter() {
+            match *x {
+              Nothing => (),
+              Internal(ref y) => {
+                  check_integrity(&**y);
+                  sum += 1
+              }
+              External(_, _) => { sum += 1 }
+            }
+        }
+
+        assert_eq!(sum, trie.count);
+    }
 
     #[test]
     fn test_find_mut() {
@@ -903,10 +952,9 @@ mod test_map {
 #[cfg(test)]
 mod bench_map {
     extern crate test;
+    use super::TrieMap;
+    use std::rand::{weak_rng, Rng};
     use self::test::BenchHarness;
-    use super::*;
-    use prelude::*;
-    use rand::{weak_rng, Rng};
 
     #[bench]
     fn bench_iter_small(bh: &mut BenchHarness) {
@@ -1011,9 +1059,8 @@ mod bench_map {
 
 #[cfg(test)]
 mod test_set {
-    use super::*;
-    use prelude::*;
-    use uint;
+    use super::TrieSet;
+    use std::uint;
 
     #[test]
     fn test_sane_chunk() {
diff --git a/src/libextra/json.rs b/src/libextra/json.rs
index 370d1026c41..4cc210aaa6c 100644
--- a/src/libextra/json.rs
+++ b/src/libextra/json.rs
@@ -235,7 +235,7 @@ fn main() {
 
 use std::char;
 use std::f64;
-use std::hashmap::HashMap;
+use collections::HashMap;
 use std::io;
 use std::io::MemWriter;
 use std::num;
diff --git a/src/libextra/stats.rs b/src/libextra/stats.rs
index 6738275c4c1..d791e1a2988 100644
--- a/src/libextra/stats.rs
+++ b/src/libextra/stats.rs
@@ -12,10 +12,10 @@
 
 use std::cmp;
 use std::hash_old::Hash;
-use std::hashmap;
 use std::io;
 use std::mem;
 use std::num;
+use collections::hashmap;
 
 // NB: this can probably be rewritten in terms of num::Num
 // to be less f64-specific.
diff --git a/src/libextra/url.rs b/src/libextra/url.rs
index 4580dd93098..6353e7e1159 100644
--- a/src/libextra/url.rs
+++ b/src/libextra/url.rs
@@ -14,7 +14,7 @@
 
 use std::io::BufReader;
 use std::cmp::Eq;
-use std::hashmap::HashMap;
+use collections::HashMap;
 use std::to_bytes;
 use std::uint;
 
@@ -957,7 +957,7 @@ mod tests {
 
     use super::*;
 
-    use std::hashmap::HashMap;
+    use collections::HashMap;
 
     #[test]
     fn test_url_parse() {
diff --git a/src/libnative/io/timer_other.rs b/src/libnative/io/timer_other.rs
index 3a060194a69..9f332adb27b 100644
--- a/src/libnative/io/timer_other.rs
+++ b/src/libnative/io/timer_other.rs
@@ -49,7 +49,6 @@
 #[allow(non_camel_case_types)];
 
 use std::comm::Data;
-use std::hashmap::HashMap;
 use std::libc;
 use std::mem;
 use std::os;
@@ -105,7 +104,7 @@ fn helper(input: libc::c_int, messages: Port<Req>) {
     // sorted list, and dead timers are those which have expired, but ownership
     // hasn't yet been transferred back to the timer itself.
     let mut active: ~[~Inner] = ~[];
-    let mut dead = HashMap::new();
+    let mut dead = ~[];
 
     // inserts a timer into an array of timers (sorted by firing time)
     fn insert(t: ~Inner, active: &mut ~[~Inner]) {
@@ -116,7 +115,7 @@ fn helper(input: libc::c_int, messages: Port<Req>) {
     }
 
     // signals the first requests in the queue, possible re-enqueueing it.
-    fn signal(active: &mut ~[~Inner], dead: &mut HashMap<uint, ~Inner>) {
+    fn signal(active: &mut ~[~Inner], dead: &mut ~[(uint, ~Inner)]) {
         let mut timer = match active.shift() {
             Some(timer) => timer, None => return
         };
@@ -127,7 +126,7 @@ fn helper(input: libc::c_int, messages: Port<Req>) {
             insert(timer, active);
         } else {
             drop(chan);
-            dead.insert(timer.id, timer);
+            dead.push((timer.id, timer));
         }
     }
 
@@ -172,8 +171,12 @@ fn helper(input: libc::c_int, messages: Port<Req>) {
                         Data(NewTimer(timer)) => insert(timer, &mut active),
 
                         Data(RemoveTimer(id, ack)) => {
-                            match dead.pop(&id) {
-                                Some(i) => { ack.send(i); continue }
+                            match dead.iter().position(|&(i, _)| id == i) {
+                                Some(i) => {
+                                    let (_, i) = dead.remove(i).unwrap();
+                                    ack.send(i);
+                                    continue
+                                }
                                 None => {}
                             }
                             let i = active.iter().position(|i| i.id == id);
diff --git a/src/libnative/io/timer_timerfd.rs b/src/libnative/io/timer_timerfd.rs
index b1ae5820888..baafe3f4850 100644
--- a/src/libnative/io/timer_timerfd.rs
+++ b/src/libnative/io/timer_timerfd.rs
@@ -35,7 +35,6 @@ use std::libc;
 use std::ptr;
 use std::os;
 use std::rt::rtio;
-use std::hashmap::HashMap;
 use std::mem;
 
 use io::file::FileDesc;
@@ -78,7 +77,7 @@ fn helper(input: libc::c_int, messages: Port<Req>) {
 
     add(efd, input);
     let events: [imp::epoll_event, ..16] = unsafe { mem::init() };
-    let mut map: HashMap<libc::c_int, (Chan<()>, bool)> = HashMap::new();
+    let mut list: ~[(libc::c_int, Chan<()>, bool)] = ~[];
     'outer: loop {
         let n = match unsafe {
             imp::epoll_wait(efd, events.as_ptr(),
@@ -107,13 +106,17 @@ fn helper(input: libc::c_int, messages: Port<Req>) {
                 // FIXME: should this perform a send() this number of
                 //      times?
                 let _ = FileDesc::new(fd, false).inner_read(bits).unwrap();
-                let remove = {
-                    match map.find(&fd).expect("fd unregistered") {
-                        &(ref c, oneshot) => !c.try_send(()) || oneshot
+                let (remove, i) = {
+                    match list.bsearch(|&(f, _, _)| f.cmp(&fd)) {
+                        Some(i) => {
+                            let (_, ref c, oneshot) = list[i];
+                            (!c.try_send(()) || oneshot, i)
+                        }
+                        None => fail!("fd not active: {}", fd),
                     }
                 };
                 if remove {
-                    map.remove(&fd);
+                    drop(list.remove(i));
                     del(efd, fd);
                 }
             }
@@ -128,8 +131,17 @@ fn helper(input: libc::c_int, messages: Port<Req>) {
 
                     // If we haven't previously seen the file descriptor, then
                     // we need to add it to the epoll set.
-                    if map.insert(fd, (chan, one)) {
-                        add(efd, fd);
+                    match list.bsearch(|&(f, _, _)| f.cmp(&fd)) {
+                        Some(i) => {
+                            drop(mem::replace(&mut list[i], (fd, chan, one)));
+                        }
+                        None => {
+                            match list.iter().position(|&(f, _, _)| f >= fd) {
+                                Some(i) => list.insert(i, (fd, chan, one)),
+                                None => list.push((fd, chan, one)),
+                            }
+                            add(efd, fd);
+                        }
                     }
 
                     // Update the timerfd's time value now that we have control
@@ -141,14 +153,18 @@ fn helper(input: libc::c_int, messages: Port<Req>) {
                 }
 
                 Data(RemoveTimer(fd, chan)) => {
-                    if map.remove(&fd) {
-                        del(efd, fd);
+                    match list.bsearch(|&(f, _, _)| f.cmp(&fd)) {
+                        Some(i) => {
+                            drop(list.remove(i));
+                            del(efd, fd);
+                        }
+                        None => {}
                     }
                     chan.send(());
                 }
 
                 Data(Shutdown) => {
-                    assert!(map.len() == 0);
+                    assert!(list.len() == 0);
                     break 'outer;
                 }
 
diff --git a/src/librustc/back/rpath.rs b/src/librustc/back/rpath.rs
index 43ecbccfd79..68deb0a9416 100644
--- a/src/librustc/back/rpath.rs
+++ b/src/librustc/back/rpath.rs
@@ -13,7 +13,7 @@ use driver::session;
 use metadata::cstore;
 use metadata::filesearch;
 
-use std::hashmap::HashSet;
+use collections::HashSet;
 use std::{os, vec};
 use syntax::abi;
 
diff --git a/src/librustc/driver/driver.rs b/src/librustc/driver/driver.rs
index f2d82bfdf3c..1f7a75da345 100644
--- a/src/librustc/driver/driver.rs
+++ b/src/librustc/driver/driver.rs
@@ -31,12 +31,12 @@ use extra::json;
 use serialize::Encodable;
 
 use std::cell::{Cell, RefCell};
-use std::hashmap::{HashMap,HashSet};
 use std::io;
 use std::io::fs;
 use std::io::MemReader;
 use std::os;
 use std::vec;
+use collections::{HashMap, HashSet};
 use getopts::{optopt, optmulti, optflag, optflagopt};
 use getopts;
 use syntax::ast;
diff --git a/src/librustc/driver/session.rs b/src/librustc/driver/session.rs
index d43a68e4f87..e023190e5f4 100644
--- a/src/librustc/driver/session.rs
+++ b/src/librustc/driver/session.rs
@@ -26,7 +26,7 @@ use syntax::{abi, ast, codemap};
 use syntax;
 
 use std::cell::{Cell, RefCell};
-use std::hashmap::{HashMap,HashSet};
+use collections::{HashMap,HashSet};
 
 pub struct Config {
     os: abi::Os,
diff --git a/src/librustc/lib/llvm.rs b/src/librustc/lib/llvm.rs
index d565e378af4..3bee339e3cc 100644
--- a/src/librustc/lib/llvm.rs
+++ b/src/librustc/lib/llvm.rs
@@ -13,7 +13,7 @@
 
 use std::c_str::ToCStr;
 use std::cell::RefCell;
-use std::hashmap::HashMap;
+use collections::HashMap;
 use std::libc::{c_uint, c_ushort, c_void, free};
 use std::str::raw::from_c_str;
 
diff --git a/src/librustc/metadata/creader.rs b/src/librustc/metadata/creader.rs
index d361ee56936..9f14b571d82 100644
--- a/src/librustc/metadata/creader.rs
+++ b/src/librustc/metadata/creader.rs
@@ -21,7 +21,7 @@ use metadata::loader;
 use metadata::loader::Os;
 
 use std::cell::RefCell;
-use std::hashmap::HashMap;
+use collections::HashMap;
 use syntax::ast;
 use syntax::abi;
 use syntax::attr;
diff --git a/src/librustc/metadata/cstore.rs b/src/librustc/metadata/cstore.rs
index 8c2c05b96cd..1a8b86b3510 100644
--- a/src/librustc/metadata/cstore.rs
+++ b/src/librustc/metadata/cstore.rs
@@ -17,7 +17,7 @@ use metadata::decoder;
 use metadata::loader;
 
 use std::cell::RefCell;
-use std::hashmap::HashMap;
+use collections::HashMap;
 use syntax::ast;
 use syntax::parse::token::IdentInterner;
 
diff --git a/src/librustc/metadata/encoder.rs b/src/librustc/metadata/encoder.rs
index 210c1f2a875..a32cdbe98a1 100644
--- a/src/librustc/metadata/encoder.rs
+++ b/src/librustc/metadata/encoder.rs
@@ -27,9 +27,9 @@ use serialize::Encodable;
 use std::cast;
 use std::cell::{Cell, RefCell};
 use std::hash_old::Hash;
-use std::hashmap::{HashMap, HashSet};
 use std::io::MemWriter;
 use std::str;
+use collections::{HashMap, HashSet};
 use syntax::abi::AbiSet;
 use syntax::ast::*;
 use syntax::ast;
diff --git a/src/librustc/metadata/filesearch.rs b/src/librustc/metadata/filesearch.rs
index 42231ce1b47..2ab3f8a147e 100644
--- a/src/librustc/metadata/filesearch.rs
+++ b/src/librustc/metadata/filesearch.rs
@@ -14,7 +14,7 @@ use std::cell::RefCell;
 use std::option;
 use std::os;
 use std::io::fs;
-use std::hashmap::HashSet;
+use collections::HashSet;
 
 pub enum FileMatch { FileMatches, FileDoesntMatch }
 
diff --git a/src/librustc/metadata/loader.rs b/src/librustc/metadata/loader.rs
index 3558166128b..e7d97f03913 100644
--- a/src/librustc/metadata/loader.rs
+++ b/src/librustc/metadata/loader.rs
@@ -26,13 +26,13 @@ use syntax::attr::AttrMetaMethods;
 
 use std::c_str::ToCStr;
 use std::cast;
-use std::hashmap::{HashMap, HashSet};
 use std::cmp;
 use std::io;
 use std::os::consts::{macos, freebsd, linux, android, win32};
 use std::str;
 use std::vec;
 
+use collections::{HashMap, HashSet};
 use flate;
 use time;
 
diff --git a/src/librustc/metadata/tyencode.rs b/src/librustc/metadata/tyencode.rs
index db0bcf7d029..c9b234743fa 100644
--- a/src/librustc/metadata/tyencode.rs
+++ b/src/librustc/metadata/tyencode.rs
@@ -14,7 +14,7 @@
 #[allow(non_camel_case_types)];
 
 use std::cell::RefCell;
-use std::hashmap::HashMap;
+use collections::HashMap;
 use std::io;
 use std::io::MemWriter;
 use std::str;
diff --git a/src/librustc/middle/borrowck/mod.rs b/src/librustc/middle/borrowck/mod.rs
index c7157ad1703..34008fb84df 100644
--- a/src/librustc/middle/borrowck/mod.rs
+++ b/src/librustc/middle/borrowck/mod.rs
@@ -21,7 +21,7 @@ use middle::dataflow::DataFlowOperator;
 use util::ppaux::{note_and_explain_region, Repr, UserString};
 
 use std::cell::{Cell, RefCell};
-use std::hashmap::HashMap;
+use collections::HashMap;
 use std::ops::{BitOr, BitAnd};
 use std::result::{Result};
 use syntax::ast;
diff --git a/src/librustc/middle/borrowck/move_data.rs b/src/librustc/middle/borrowck/move_data.rs
index 34efcacc44b..5034976c9f9 100644
--- a/src/librustc/middle/borrowck/move_data.rs
+++ b/src/librustc/middle/borrowck/move_data.rs
@@ -16,8 +16,8 @@ comments in the section "Moves and initialization" and in `doc.rs`.
 */
 
 use std::cell::RefCell;
-use std::hashmap::{HashMap, HashSet};
 use std::uint;
+use collections::{HashMap, HashSet};
 use middle::borrowck::*;
 use middle::dataflow::DataFlowContext;
 use middle::dataflow::DataFlowOperator;
diff --git a/src/librustc/middle/cfg/construct.rs b/src/librustc/middle/cfg/construct.rs
index 6ca779906e2..d4eb72ac577 100644
--- a/src/librustc/middle/cfg/construct.rs
+++ b/src/librustc/middle/cfg/construct.rs
@@ -12,7 +12,7 @@ use middle::cfg::*;
 use middle::graph;
 use middle::typeck;
 use middle::ty;
-use std::hashmap::HashMap;
+use collections::HashMap;
 use syntax::ast;
 use syntax::ast_util;
 use syntax::opt_vec;
diff --git a/src/librustc/middle/cfg/mod.rs b/src/librustc/middle/cfg/mod.rs
index cc00ab921b4..b0ee26f6f23 100644
--- a/src/librustc/middle/cfg/mod.rs
+++ b/src/librustc/middle/cfg/mod.rs
@@ -18,7 +18,7 @@ Uses `Graph` as the underlying representation.
 use middle::graph;
 use middle::ty;
 use middle::typeck;
-use std::hashmap::HashMap;
+use collections::HashMap;
 use syntax::ast;
 use syntax::opt_vec::OptVec;
 
diff --git a/src/librustc/middle/const_eval.rs b/src/librustc/middle/const_eval.rs
index 9cf055cad9d..5322aac8c23 100644
--- a/src/librustc/middle/const_eval.rs
+++ b/src/librustc/middle/const_eval.rs
@@ -24,7 +24,7 @@ use syntax::visit;
 use syntax::{ast, ast_map, ast_util};
 
 use std::cell::RefCell;
-use std::hashmap::HashMap;
+use collections::HashMap;
 use std::rc::Rc;
 
 //
diff --git a/src/librustc/middle/dataflow.rs b/src/librustc/middle/dataflow.rs
index 8a504f07b73..ba79d71bcb6 100644
--- a/src/librustc/middle/dataflow.rs
+++ b/src/librustc/middle/dataflow.rs
@@ -20,7 +20,7 @@
 use std::io;
 use std::uint;
 use std::vec;
-use std::hashmap::HashMap;
+use collections::HashMap;
 use syntax::ast;
 use syntax::ast_util;
 use syntax::ast_util::IdRange;
diff --git a/src/librustc/middle/dead.rs b/src/librustc/middle/dead.rs
index 39b232eed33..9cc5a49600f 100644
--- a/src/librustc/middle/dead.rs
+++ b/src/librustc/middle/dead.rs
@@ -17,7 +17,7 @@ use middle::privacy;
 use middle::ty;
 use middle::typeck;
 
-use std::hashmap::HashSet;
+use collections::HashSet;
 use syntax::ast;
 use syntax::ast_map;
 use syntax::ast_util::{local_def, def_id_of_def, is_local};
diff --git a/src/librustc/middle/freevars.rs b/src/librustc/middle/freevars.rs
index 4c488067ad3..9ff67377c59 100644
--- a/src/librustc/middle/freevars.rs
+++ b/src/librustc/middle/freevars.rs
@@ -16,7 +16,7 @@
 use middle::resolve;
 use middle::ty;
 
-use std::hashmap::HashMap;
+use collections::HashMap;
 use syntax::codemap::Span;
 use syntax::{ast, ast_util};
 use syntax::visit;
diff --git a/src/librustc/middle/lang_items.rs b/src/librustc/middle/lang_items.rs
index 290e901d1a3..0194d4a2510 100644
--- a/src/librustc/middle/lang_items.rs
+++ b/src/librustc/middle/lang_items.rs
@@ -30,7 +30,7 @@ use syntax::parse::token::InternedString;
 use syntax::visit::Visitor;
 use syntax::visit;
 
-use std::hashmap::HashMap;
+use collections::HashMap;
 use std::iter::Enumerate;
 use std::vec;
 
diff --git a/src/librustc/middle/lint.rs b/src/librustc/middle/lint.rs
index 911b6df10a6..36ed4913cdb 100644
--- a/src/librustc/middle/lint.rs
+++ b/src/librustc/middle/lint.rs
@@ -49,7 +49,7 @@ use std::to_str::ToStr;
 use util::ppaux::{ty_to_str};
 
 use std::cmp;
-use std::hashmap::HashMap;
+use collections::HashMap;
 use std::i16;
 use std::i32;
 use std::i64;
diff --git a/src/librustc/middle/liveness.rs b/src/librustc/middle/liveness.rs
index efe88b7847f..3b8eb682065 100644
--- a/src/librustc/middle/liveness.rs
+++ b/src/librustc/middle/liveness.rs
@@ -111,7 +111,7 @@ use middle::moves;
 
 use std::cast::transmute;
 use std::cell::{Cell, RefCell};
-use std::hashmap::HashMap;
+use collections::HashMap;
 use std::io;
 use std::str;
 use std::to_str;
diff --git a/src/librustc/middle/moves.rs b/src/librustc/middle/moves.rs
index 32cb7ca57da..1705e3a5160 100644
--- a/src/librustc/middle/moves.rs
+++ b/src/librustc/middle/moves.rs
@@ -137,8 +137,8 @@ use util::common::indenter;
 use util::ppaux::UserString;
 
 use std::cell::RefCell;
-use std::hashmap::{HashSet, HashMap};
 use std::rc::Rc;
+use collections::{HashSet, HashMap};
 use syntax::ast::*;
 use syntax::ast_util;
 use syntax::visit;
diff --git a/src/librustc/middle/pat_util.rs b/src/librustc/middle/pat_util.rs
index 50096c012be..d352771ef50 100644
--- a/src/librustc/middle/pat_util.rs
+++ b/src/librustc/middle/pat_util.rs
@@ -11,7 +11,7 @@
 
 use middle::resolve;
 
-use std::hashmap::HashMap;
+use collections::HashMap;
 use syntax::ast::*;
 use syntax::ast_util::{path_to_ident, walk_pat};
 use syntax::codemap::Span;
diff --git a/src/librustc/middle/privacy.rs b/src/librustc/middle/privacy.rs
index 7578636b2b6..1899b52cca8 100644
--- a/src/librustc/middle/privacy.rs
+++ b/src/librustc/middle/privacy.rs
@@ -12,8 +12,8 @@
 //! outside their scopes. This pass will also generate a set of exported items
 //! which are available for use externally when compiled as a library.
 
-use std::hashmap::{HashSet, HashMap};
 use std::mem::replace;
+use collections::{HashSet, HashMap};
 
 use metadata::csearch;
 use middle::resolve;
diff --git a/src/librustc/middle/reachable.rs b/src/librustc/middle/reachable.rs
index 547d78219a5..26104331a10 100644
--- a/src/librustc/middle/reachable.rs
+++ b/src/librustc/middle/reachable.rs
@@ -20,7 +20,7 @@ use middle::typeck;
 use middle::privacy;
 
 use std::cell::RefCell;
-use std::hashmap::HashSet;
+use collections::HashSet;
 use syntax::ast;
 use syntax::ast_map;
 use syntax::ast_util::{def_id_of_def, is_local};
diff --git a/src/librustc/middle/region.rs b/src/librustc/middle/region.rs
index 9b1473cbd8e..c06ad66f606 100644
--- a/src/librustc/middle/region.rs
+++ b/src/librustc/middle/region.rs
@@ -26,7 +26,7 @@ use middle::ty::{FreeRegion};
 use middle::ty;
 
 use std::cell::RefCell;
-use std::hashmap::{HashMap, HashSet};
+use collections::{HashMap, HashSet};
 use syntax::codemap::Span;
 use syntax::{ast, visit};
 use syntax::visit::{Visitor, FnKind};
diff --git a/src/librustc/middle/resolve.rs b/src/librustc/middle/resolve.rs
index 066e4d2b313..72967ff8195 100644
--- a/src/librustc/middle/resolve.rs
+++ b/src/librustc/middle/resolve.rs
@@ -31,8 +31,8 @@ use syntax::visit::Visitor;
 
 use std::cell::{Cell, RefCell};
 use std::uint;
-use std::hashmap::{HashMap, HashSet};
 use std::mem::replace;
+use collections::{HashMap, HashSet};
 
 // Definition mapping
 pub type DefMap = @RefCell<HashMap<NodeId,Def>>;
diff --git a/src/librustc/middle/resolve_lifetime.rs b/src/librustc/middle/resolve_lifetime.rs
index b3a975a13e4..4e780f45111 100644
--- a/src/librustc/middle/resolve_lifetime.rs
+++ b/src/librustc/middle/resolve_lifetime.rs
@@ -19,7 +19,7 @@
 
 use driver::session;
 use std::cell::RefCell;
-use std::hashmap::HashMap;
+use collections::HashMap;
 use syntax::ast;
 use syntax::codemap::Span;
 use syntax::opt_vec::OptVec;
diff --git a/src/librustc/middle/trans/_match.rs b/src/librustc/middle/trans/_match.rs
index 0aa8393e79d..5b2f9d87ca8 100644
--- a/src/librustc/middle/trans/_match.rs
+++ b/src/librustc/middle/trans/_match.rs
@@ -223,7 +223,7 @@ use util::common::indenter;
 use util::ppaux::{Repr, vec_map_to_str};
 
 use std::cell::Cell;
-use std::hashmap::HashMap;
+use collections::HashMap;
 use std::vec;
 use syntax::ast;
 use syntax::ast::Ident;
diff --git a/src/librustc/middle/trans/base.rs b/src/librustc/middle/trans/base.rs
index c7d09e31855..d920378f508 100644
--- a/src/librustc/middle/trans/base.rs
+++ b/src/librustc/middle/trans/base.rs
@@ -74,7 +74,7 @@ use util::sha2::Sha256;
 use arena::TypedArena;
 use std::c_str::ToCStr;
 use std::cell::{Cell, RefCell};
-use std::hashmap::HashMap;
+use collections::HashMap;
 use std::libc::c_uint;
 use std::local_data;
 use syntax::abi::{X86, X86_64, Arm, Mips, Rust, RustIntrinsic, OsWin32};
diff --git a/src/librustc/middle/trans/builder.rs b/src/librustc/middle/trans/builder.rs
index 9dd92fbc45c..4fa807ca608 100644
--- a/src/librustc/middle/trans/builder.rs
+++ b/src/librustc/middle/trans/builder.rs
@@ -17,8 +17,8 @@ use middle::trans::base;
 use middle::trans::common::*;
 use middle::trans::machine::llalign_of_pref;
 use middle::trans::type_::Type;
-use std::hashmap::HashMap;
 use std::libc::{c_uint, c_ulonglong, c_char};
+use collections::HashMap;
 use syntax::codemap::Span;
 
 pub struct Builder<'a> {
diff --git a/src/librustc/middle/trans/common.rs b/src/librustc/middle/trans/common.rs
index d9e929c2501..8ac885d183f 100644
--- a/src/librustc/middle/trans/common.rs
+++ b/src/librustc/middle/trans/common.rs
@@ -33,7 +33,7 @@ use util::ppaux::Repr;
 use arena::TypedArena;
 use std::c_str::ToCStr;
 use std::cell::{Cell, RefCell};
-use std::hashmap::HashMap;
+use collections::HashMap;
 use std::libc::{c_uint, c_longlong, c_ulonglong, c_char};
 use syntax::ast::Ident;
 use syntax::ast;
diff --git a/src/librustc/middle/trans/context.rs b/src/librustc/middle/trans/context.rs
index 2260ddea3c2..b90fc4f6bbf 100644
--- a/src/librustc/middle/trans/context.rs
+++ b/src/librustc/middle/trans/context.rs
@@ -29,9 +29,9 @@ use util::sha2::Sha256;
 
 use std::cell::{Cell, RefCell};
 use std::c_str::ToCStr;
-use std::hashmap::{HashMap, HashSet};
 use std::local_data;
 use std::libc::c_uint;
+use collections::{HashMap, HashSet};
 use syntax::ast;
 use syntax::parse::token::InternedString;
 
diff --git a/src/librustc/middle/trans/debuginfo.rs b/src/librustc/middle/trans/debuginfo.rs
index 6a9ee514f8f..564aab5d31d 100644
--- a/src/librustc/middle/trans/debuginfo.rs
+++ b/src/librustc/middle/trans/debuginfo.rs
@@ -142,8 +142,8 @@ use util::ppaux;
 
 use std::c_str::{CString, ToCStr};
 use std::cell::{Cell, RefCell};
-use std::hashmap::HashMap;
-use std::hashmap::HashSet;
+use collections::HashMap;
+use collections::HashSet;
 use std::libc::{c_uint, c_ulonglong, c_longlong};
 use std::ptr;
 use std::sync::atomics;
diff --git a/src/librustc/middle/trans/expr.rs b/src/librustc/middle/trans/expr.rs
index 99852e446cc..e3724ab4d11 100644
--- a/src/librustc/middle/trans/expr.rs
+++ b/src/librustc/middle/trans/expr.rs
@@ -70,7 +70,7 @@ use middle::trans::machine::llsize_of;
 
 use middle::trans::type_::Type;
 
-use std::hashmap::HashMap;
+use collections::HashMap;
 use std::vec;
 use syntax::ast;
 use syntax::ast_map;
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index 6f20de57fc7..c7aedec4b48 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -33,12 +33,12 @@ use util::common::{indenter};
 use std::cast;
 use std::cell::{Cell, RefCell};
 use std::cmp;
-use std::hashmap::{HashMap, HashSet};
 use std::ops;
 use std::rc::Rc;
 use std::to_bytes;
 use std::to_str::ToStr;
 use std::vec;
+use collections::{HashMap, HashSet};
 use syntax::ast::*;
 use syntax::ast_util::{is_local, lit_is_str};
 use syntax::ast_util;
@@ -460,7 +460,7 @@ pub struct param_ty {
 }
 
 /// Representation of regions:
-#[deriving(Clone, Eq, IterBytes, Encodable, Decodable, ToStr)]
+#[deriving(Clone, Eq, IterBytes, Encodable, Decodable, ToStr, Show)]
 pub enum Region {
     // Region bound in a type or fn declaration which will be
     // substituted 'early' -- that is, at the same time when type
@@ -620,13 +620,13 @@ impl Region {
     }
 }
 
-#[deriving(Clone, Eq, TotalOrd, TotalEq, IterBytes, Encodable, Decodable, ToStr)]
+#[deriving(Clone, Eq, TotalOrd, TotalEq, IterBytes, Encodable, Decodable, ToStr, Show)]
 pub struct FreeRegion {
     scope_id: NodeId,
     bound_region: BoundRegion
 }
 
-#[deriving(Clone, Eq, TotalEq, TotalOrd, IterBytes, Encodable, Decodable, ToStr)]
+#[deriving(Clone, Eq, TotalEq, TotalOrd, IterBytes, Encodable, Decodable, ToStr, Show)]
 pub enum BoundRegion {
     /// An anonymous region parameter for a given fn (&T)
     BrAnon(uint),
@@ -869,7 +869,7 @@ pub struct IntVid(uint);
 #[deriving(Clone, Eq, IterBytes)]
 pub struct FloatVid(uint);
 
-#[deriving(Clone, Eq, Encodable, Decodable, IterBytes)]
+#[deriving(Clone, Eq, Encodable, Decodable, IterBytes, Show)]
 pub struct RegionVid {
     id: uint
 }
@@ -881,7 +881,7 @@ pub enum InferTy {
     FloatVar(FloatVid)
 }
 
-#[deriving(Clone, Encodable, Decodable, IterBytes, ToStr)]
+#[deriving(Clone, Encodable, Decodable, IterBytes, ToStr, Show)]
 pub enum InferRegion {
     ReVar(RegionVid),
     ReSkolemized(uint, BoundRegion)
diff --git a/src/librustc/middle/typeck/check/_match.rs b/src/librustc/middle/typeck/check/_match.rs
index 160b6f5ec4e..6620f8502ed 100644
--- a/src/librustc/middle/typeck/check/_match.rs
+++ b/src/librustc/middle/typeck/check/_match.rs
@@ -19,7 +19,7 @@ use middle::typeck::check::{structure_of, valid_range_bounds};
 use middle::typeck::infer;
 use middle::typeck::require_same_types;
 
-use std::hashmap::{HashMap, HashSet};
+use collections::{HashMap, HashSet};
 use syntax::ast;
 use syntax::ast_util;
 use syntax::parse::token;
diff --git a/src/librustc/middle/typeck/check/method.rs b/src/librustc/middle/typeck/check/method.rs
index fca89f3f91c..3837c0b55d1 100644
--- a/src/librustc/middle/typeck/check/method.rs
+++ b/src/librustc/middle/typeck/check/method.rs
@@ -98,7 +98,7 @@ use util::common::indenter;
 use util::ppaux::Repr;
 
 use std::cell::RefCell;
-use std::hashmap::HashSet;
+use collections::HashSet;
 use std::result;
 use std::vec;
 use syntax::ast::{DefId, SelfValue, SelfRegion};
diff --git a/src/librustc/middle/typeck/check/mod.rs b/src/librustc/middle/typeck/check/mod.rs
index 761a8b81a46..ac17d327166 100644
--- a/src/librustc/middle/typeck/check/mod.rs
+++ b/src/librustc/middle/typeck/check/mod.rs
@@ -114,7 +114,7 @@ use util::ppaux;
 use util::ppaux::{UserString, Repr};
 
 use std::cell::{Cell, RefCell};
-use std::hashmap::HashMap;
+use collections::HashMap;
 use std::mem::replace;
 use std::result;
 use std::vec;
diff --git a/src/librustc/middle/typeck/check/regionmanip.rs b/src/librustc/middle/typeck/check/regionmanip.rs
index 0b04db88234..9192bdfda29 100644
--- a/src/librustc/middle/typeck/check/regionmanip.rs
+++ b/src/librustc/middle/typeck/check/regionmanip.rs
@@ -13,7 +13,7 @@
 use middle::ty;
 use middle::ty_fold;
 use middle::ty_fold::TypeFolder;
-use std::hashmap::HashMap;
+use collections::HashMap;
 use util::ppaux::Repr;
 use util::ppaux;
 
@@ -39,7 +39,7 @@ pub fn replace_bound_regions_in_fn_sig(
         });
         ty_fold::super_fold_sig(&mut f, fn_sig)
     };
-    debug!("resulting map: {}", map.to_str());
+    debug!("resulting map: {}", map);
     (map, fn_sig)
 }
 
diff --git a/src/librustc/middle/typeck/check/vtable.rs b/src/librustc/middle/typeck/check/vtable.rs
index ba4300b58a1..588dbec8a83 100644
--- a/src/librustc/middle/typeck/check/vtable.rs
+++ b/src/librustc/middle/typeck/check/vtable.rs
@@ -27,7 +27,7 @@ use util::ppaux;
 use util::ppaux::Repr;
 
 use std::cell::RefCell;
-use std::hashmap::HashSet;
+use collections::HashSet;
 use std::result;
 use syntax::ast;
 use syntax::ast_util;
diff --git a/src/librustc/middle/typeck/coherence.rs b/src/librustc/middle/typeck/coherence.rs
index a9dffeb670f..c22b3c81458 100644
--- a/src/librustc/middle/typeck/coherence.rs
+++ b/src/librustc/middle/typeck/coherence.rs
@@ -47,7 +47,7 @@ use syntax::parse::token;
 use syntax::visit;
 
 use std::cell::RefCell;
-use std::hashmap::HashSet;
+use collections::HashSet;
 use std::rc::Rc;
 use std::vec;
 
diff --git a/src/librustc/middle/typeck/infer/glb.rs b/src/librustc/middle/typeck/infer/glb.rs
index 4af6364642e..039ea995821 100644
--- a/src/librustc/middle/typeck/infer/glb.rs
+++ b/src/librustc/middle/typeck/infer/glb.rs
@@ -24,7 +24,7 @@ use middle::typeck::infer::fold_regions_in_sig;
 use syntax::ast::{Many, Once, MutImmutable, MutMutable};
 use syntax::ast::{ExternFn, ImpureFn, UnsafeFn, NodeId};
 use syntax::ast::{Onceness, Purity};
-use std::hashmap::HashMap;
+use collections::HashMap;
 use util::common::{indenter};
 use util::ppaux::mt_to_str;
 
diff --git a/src/librustc/middle/typeck/infer/lattice.rs b/src/librustc/middle/typeck/infer/lattice.rs
index fa40fa6a064..265ac7b0cf0 100644
--- a/src/librustc/middle/typeck/infer/lattice.rs
+++ b/src/librustc/middle/typeck/infer/lattice.rs
@@ -43,7 +43,7 @@ use middle::typeck::infer::lub::Lub;
 use middle::typeck::infer::unify::*;
 use middle::typeck::infer::sub::Sub;
 use middle::typeck::infer::to_str::InferStr;
-use std::hashmap::HashMap;
+use collections::HashMap;
 use util::common::indenter;
 
 pub trait LatticeValue {
diff --git a/src/librustc/middle/typeck/infer/lub.rs b/src/librustc/middle/typeck/infer/lub.rs
index dc6df333276..fd6950ee49e 100644
--- a/src/librustc/middle/typeck/infer/lub.rs
+++ b/src/librustc/middle/typeck/infer/lub.rs
@@ -21,7 +21,7 @@ use middle::typeck::infer::to_str::InferStr;
 use middle::typeck::infer::{cres, InferCtxt};
 use middle::typeck::infer::fold_regions_in_sig;
 use middle::typeck::infer::{TypeTrace, Subtype};
-use std::hashmap::HashMap;
+use collections::HashMap;
 use syntax::ast::{Many, Once, NodeId};
 use syntax::ast::{ExternFn, ImpureFn, UnsafeFn};
 use syntax::ast::{Onceness, Purity};
diff --git a/src/librustc/middle/typeck/infer/mod.rs b/src/librustc/middle/typeck/infer/mod.rs
index abff3b68395..dceef9e38d5 100644
--- a/src/librustc/middle/typeck/infer/mod.rs
+++ b/src/librustc/middle/typeck/infer/mod.rs
@@ -37,7 +37,7 @@ use middle::typeck::infer::to_str::InferStr;
 use middle::typeck::infer::unify::{ValsAndBindings, Root};
 use middle::typeck::infer::error_reporting::ErrorReporting;
 use std::cell::{Cell, RefCell};
-use std::hashmap::HashMap;
+use collections::HashMap;
 use std::result;
 use std::vec;
 use syntax::ast::{MutImmutable, MutMutable};
diff --git a/src/librustc/middle/typeck/infer/region_inference/mod.rs b/src/librustc/middle/typeck/infer/region_inference/mod.rs
index bbd9d8e1c4d..98391436aa3 100644
--- a/src/librustc/middle/typeck/infer/region_inference/mod.rs
+++ b/src/librustc/middle/typeck/infer/region_inference/mod.rs
@@ -25,9 +25,9 @@ use util::common::indenter;
 use util::ppaux::{Repr};
 
 use std::cell::{Cell, RefCell};
-use std::hashmap::{HashMap, HashSet};
 use std::uint;
 use std::vec;
+use collections::{HashMap, HashSet};
 use syntax::ast;
 use syntax::opt_vec;
 use syntax::opt_vec::OptVec;
diff --git a/src/librustc/middle/typeck/mod.rs b/src/librustc/middle/typeck/mod.rs
index 4f2c8966c50..d4e2660b4a0 100644
--- a/src/librustc/middle/typeck/mod.rs
+++ b/src/librustc/middle/typeck/mod.rs
@@ -70,7 +70,7 @@ use util::ppaux::Repr;
 use util::ppaux;
 
 use std::cell::RefCell;
-use std::hashmap::HashMap;
+use collections::HashMap;
 use std::rc::Rc;
 use collections::List;
 use collections::list;
diff --git a/src/librustc/middle/typeck/variance.rs b/src/librustc/middle/typeck/variance.rs
index 57c7f6752a8..47c40514e6c 100644
--- a/src/librustc/middle/typeck/variance.rs
+++ b/src/librustc/middle/typeck/variance.rs
@@ -192,7 +192,7 @@ represents the "variance transform" as defined in the paper:
 
 */
 
-use std::hashmap::HashMap;
+use collections::HashMap;
 use arena;
 use arena::Arena;
 use middle::ty;
diff --git a/src/librustdoc/core.rs b/src/librustdoc/core.rs
index 585b18a8821..f4062195978 100644
--- a/src/librustdoc/core.rs
+++ b/src/librustdoc/core.rs
@@ -21,7 +21,7 @@ use syntax;
 use std::cell::RefCell;
 use std::os;
 use std::local_data;
-use std::hashmap::{HashSet};
+use collections::HashSet;
 
 use visit_ast::RustdocVisitor;
 use clean;
diff --git a/src/librustdoc/html/render.rs b/src/librustdoc/html/render.rs
index 0f017a04da3..ab4bf5403ad 100644
--- a/src/librustdoc/html/render.rs
+++ b/src/librustdoc/html/render.rs
@@ -34,12 +34,12 @@
 //! both occur before the crate is rendered.
 
 use std::fmt;
-use std::hashmap::{HashMap, HashSet};
 use std::local_data;
 use std::io;
 use std::io::{fs, File, BufferedWriter};
 use std::str;
 use std::vec;
+use collections::{HashMap, HashSet};
 
 use sync::Arc;
 use extra::json::ToJson;
diff --git a/src/librustdoc/passes.rs b/src/librustdoc/passes.rs
index 4fc47d64e57..b8cc271ca9c 100644
--- a/src/librustdoc/passes.rs
+++ b/src/librustdoc/passes.rs
@@ -9,7 +9,7 @@
 // except according to those terms.
 
 use std::cmp;
-use std::hashmap::HashSet;
+use collections::HashSet;
 use std::local_data;
 use std::uint;
 use syntax::ast;
diff --git a/src/librustdoc/test.rs b/src/librustdoc/test.rs
index c0f8d2696ca..354b5cb0f14 100644
--- a/src/librustdoc/test.rs
+++ b/src/librustdoc/test.rs
@@ -9,7 +9,7 @@
 // except according to those terms.
 
 use std::cell::RefCell;
-use std::hashmap::HashSet;
+use collections::HashSet;
 use std::local_data;
 use std::os;
 use std::run;
diff --git a/src/libserialize/serialize.rs b/src/libserialize/serialize.rs
index f350bb0761f..a94df9975a4 100644
--- a/src/libserialize/serialize.rs
+++ b/src/libserialize/serialize.rs
@@ -14,10 +14,7 @@
 Core encoding and decoding interfaces.
 */
 
-use std::hash_old::Hash;
-use std::hashmap::{HashMap, HashSet};
 use std::rc::Rc;
-use std::trie::{TrieMap, TrieSet};
 use std::vec;
 use std::vec_ng::Vec;
 
@@ -628,124 +625,6 @@ impl<
     }
 }
 
-impl<
-    E: Encoder,
-    K: Encodable<E> + Hash + IterBytes + Eq,
-    V: Encodable<E>
-> Encodable<E> for HashMap<K, V> {
-    fn encode(&self, e: &mut E) {
-        e.emit_map(self.len(), |e| {
-            let mut i = 0;
-            for (key, val) in self.iter() {
-                e.emit_map_elt_key(i, |e| key.encode(e));
-                e.emit_map_elt_val(i, |e| val.encode(e));
-                i += 1;
-            }
-        })
-    }
-}
-
-impl<
-    D: Decoder,
-    K: Decodable<D> + Hash + IterBytes + Eq,
-    V: Decodable<D>
-> Decodable<D> for HashMap<K, V> {
-    fn decode(d: &mut D) -> HashMap<K, V> {
-        d.read_map(|d, len| {
-            let mut map = HashMap::with_capacity(len);
-            for i in range(0u, len) {
-                let key = d.read_map_elt_key(i, |d| Decodable::decode(d));
-                let val = d.read_map_elt_val(i, |d| Decodable::decode(d));
-                map.insert(key, val);
-            }
-            map
-        })
-    }
-}
-
-impl<
-    S: Encoder,
-    T: Encodable<S> + Hash + IterBytes + Eq
-> Encodable<S> for HashSet<T> {
-    fn encode(&self, s: &mut S) {
-        s.emit_seq(self.len(), |s| {
-            let mut i = 0;
-            for e in self.iter() {
-                s.emit_seq_elt(i, |s| e.encode(s));
-                i += 1;
-            }
-        })
-    }
-}
-
-impl<
-    D: Decoder,
-    T: Decodable<D> + Hash + IterBytes + Eq
-> Decodable<D> for HashSet<T> {
-    fn decode(d: &mut D) -> HashSet<T> {
-        d.read_seq(|d, len| {
-            let mut set = HashSet::with_capacity(len);
-            for i in range(0u, len) {
-                set.insert(d.read_seq_elt(i, |d| Decodable::decode(d)));
-            }
-            set
-        })
-    }
-}
-
-impl<
-    E: Encoder,
-    V: Encodable<E>
-> Encodable<E> for TrieMap<V> {
-    fn encode(&self, e: &mut E) {
-        e.emit_map(self.len(), |e| {
-                for (i, (key, val)) in self.iter().enumerate() {
-                    e.emit_map_elt_key(i, |e| key.encode(e));
-                    e.emit_map_elt_val(i, |e| val.encode(e));
-                }
-            });
-    }
-}
-
-impl<
-    D: Decoder,
-    V: Decodable<D>
-> Decodable<D> for TrieMap<V> {
-    fn decode(d: &mut D) -> TrieMap<V> {
-        d.read_map(|d, len| {
-            let mut map = TrieMap::new();
-            for i in range(0u, len) {
-                let key = d.read_map_elt_key(i, |d| Decodable::decode(d));
-                let val = d.read_map_elt_val(i, |d| Decodable::decode(d));
-                map.insert(key, val);
-            }
-            map
-        })
-    }
-}
-
-impl<S: Encoder> Encodable<S> for TrieSet {
-    fn encode(&self, s: &mut S) {
-        s.emit_seq(self.len(), |s| {
-                for (i, e) in self.iter().enumerate() {
-                    s.emit_seq_elt(i, |s| e.encode(s));
-                }
-            })
-    }
-}
-
-impl<D: Decoder> Decodable<D> for TrieSet {
-    fn decode(d: &mut D) -> TrieSet {
-        d.read_seq(|d, len| {
-            let mut set = TrieSet::new();
-            for i in range(0u, len) {
-                set.insert(d.read_seq_elt(i, |d| Decodable::decode(d)));
-            }
-            set
-        })
-    }
-}
-
 // ___________________________________________________________________________
 // Helper routines
 //
diff --git a/src/libstd/io/signal.rs b/src/libstd/io/signal.rs
index 46c106234db..19aff4f70fe 100644
--- a/src/libstd/io/signal.rs
+++ b/src/libstd/io/signal.rs
@@ -20,12 +20,14 @@ definitions for a number of signals.
 */
 
 use clone::Clone;
-use result::{Ok, Err};
 use comm::{Port, Chan};
-use container::{Map, MutableMap};
-use hashmap;
 use io;
+use iter::Iterator;
+use mem::drop;
+use option::{Some, None};
+use result::{Ok, Err};
 use rt::rtio::{IoFactory, LocalIo, RtioSignal};
+use vec::{ImmutableVector, OwnedVector};
 
 #[repr(int)]
 #[deriving(Eq, IterBytes)]
@@ -78,7 +80,7 @@ pub enum Signum {
 /// ```
 pub struct Listener {
     /// A map from signums to handles to keep the handles in memory
-    priv handles: hashmap::HashMap<Signum, ~RtioSignal>,
+    priv handles: ~[(Signum, ~RtioSignal)],
     /// chan is where all the handles send signums, which are received by
     /// the clients from port.
     priv chan: Chan<Signum>,
@@ -97,7 +99,7 @@ impl Listener {
         Listener {
             chan: chan,
             port: port,
-            handles: hashmap::HashMap::new(),
+            handles: ~[],
         }
     }
 
@@ -118,14 +120,14 @@ impl Listener {
     /// If this function fails to register a signal handler, then an error will
     /// be returned.
     pub fn register(&mut self, signum: Signum) -> io::IoResult<()> {
-        if self.handles.contains_key(&signum) {
+        if self.handles.iter().any(|&(sig, _)| sig == signum) {
             return Ok(()); // self is already listening to signum, so succeed
         }
         match LocalIo::maybe_raise(|io| {
             io.signal(signum, self.chan.clone())
         }) {
             Ok(handle) => {
-                self.handles.insert(signum, handle);
+                self.handles.push((signum, handle));
                 Ok(())
             }
             Err(e) => Err(e)
@@ -137,7 +139,10 @@ impl Listener {
     /// notification about the signal. If the signal has already been received,
     /// it may still be returned by `recv`.
     pub fn unregister(&mut self, signum: Signum) {
-        self.handles.pop(&signum);
+        match self.handles.iter().position(|&(i, _)| i == signum) {
+            Some(i) => drop(self.handles.remove(i)),
+            None => {}
+        }
     }
 }
 
diff --git a/src/libstd/lib.rs b/src/libstd/lib.rs
index 6996cba42b4..d855aebdf3f 100644
--- a/src/libstd/lib.rs
+++ b/src/libstd/lib.rs
@@ -11,7 +11,7 @@
 //! # The Rust standard library
 //!
 //! The Rust standard library is a group of interrelated modules defining
-//! the core language traits, operations on built-in data types, collections,
+//! the core language traits, operations on built-in data types,
 //! platform abstractions, the task scheduler, runtime support for language
 //! features and other common functionality.
 //!
@@ -68,9 +68,9 @@
 // When testing libstd, bring in libuv as the I/O backend so tests can print
 // things and all of the std::io tests have an I/O interface to run on top
 // of
-#[cfg(test)] extern crate rustuv = "rustuv";
-#[cfg(test)] extern crate native = "native";
-#[cfg(test)] extern crate green = "green";
+#[cfg(test)] extern crate rustuv;
+#[cfg(test)] extern crate native;
+#[cfg(test)] extern crate green;
 
 // Make extra accessible for benchmarking
 #[cfg(test)] extern crate extra = "extra";
@@ -156,9 +156,7 @@ pub mod any;
 
 pub mod option;
 pub mod result;
-pub mod hashmap;
 pub mod cell;
-pub mod trie;
 
 
 /* Tasks and communication */
diff --git a/src/libstd/logging.rs b/src/libstd/logging.rs
index 9aa63f15def..39a62a80cfc 100644
--- a/src/libstd/logging.rs
+++ b/src/libstd/logging.rs
@@ -70,7 +70,7 @@ hello                // turns on all logging for the 'hello' module
 info                 // turns on all info logging
 hello=debug          // turns on debug logging for 'hello'
 hello=3              // turns on info logging for 'hello'
-hello,std::hashmap   // turns on hello, and std's hashmap logging
+hello,std::option    // turns on hello, and std's option logging
 error,hello=warn     // turn on global error logging and also warn for hello
 ```
 
diff --git a/src/libstd/rt/crate_map.rs b/src/libstd/rt/crate_map.rs
index 8567f0e0251..847375121c8 100644
--- a/src/libstd/rt/crate_map.rs
+++ b/src/libstd/rt/crate_map.rs
@@ -8,13 +8,13 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+use cmp::TotalOrd;
 use container::MutableSet;
-use hashmap::HashSet;
 use iter::Iterator;
 use option::{Some, None, Option};
 use ptr::RawPtr;
-use vec::ImmutableVector;
 use rt::rtio::EventLoop;
+use vec::{ImmutableVector, OwnedVector};
 
 // Need to tell the linker on OS X to not barf on undefined symbols
 // and instead look them up at runtime, which we need to resolve
@@ -89,28 +89,33 @@ fn version(crate_map: &CrateMap) -> i32 {
 fn do_iter_crate_map<'a>(
                      crate_map: &'a CrateMap<'a>,
                      f: |&ModEntry|,
-                     visited: &mut HashSet<*CrateMap<'a>>) {
-    if visited.insert(crate_map as *CrateMap) {
-        match version(crate_map) {
-            2 => {
-                let (entries, children) = (crate_map.entries, crate_map.children);
-                for entry in entries.iter() {
-                    f(entry);
-                }
-                for child in children.iter() {
-                    do_iter_crate_map(*child, |x| f(x), visited);
-                }
-            },
-            _ => fail!("invalid crate map version")
-        }
+                     visited: &mut ~[*CrateMap<'a>]) {
+    let raw = crate_map as *CrateMap<'a>;
+    if visited.bsearch(|a| (*a as uint).cmp(&(raw as uint))).is_some() {
+        return
+    }
+    match visited.iter().position(|i| *i as uint > raw as uint) {
+        Some(i) => visited.insert(i, raw),
+        None => visited.push(raw),
+    }
+
+    match version(crate_map) {
+        2 => {
+            let (entries, children) = (crate_map.entries, crate_map.children);
+            for entry in entries.iter() {
+                f(entry);
+            }
+            for child in children.iter() {
+                do_iter_crate_map(*child, |x| f(x), visited);
+            }
+        },
+        _ => fail!("invalid crate map version")
     }
 }
 
 /// Iterates recursively over `crate_map` and all child crate maps
 pub fn iter_crate_map<'a>(crate_map: &'a CrateMap<'a>, f: |&ModEntry|) {
-    // FIXME: use random numbers as keys from the OS-level RNG when there is a nice
-    //        way to do this
-    let mut v: HashSet<*CrateMap<'a>> = HashSet::with_capacity_and_keys(0, 0, 32);
+    let mut v = ~[];
     do_iter_crate_map(crate_map, f, &mut v);
 }
 
diff --git a/src/libstd/to_str.rs b/src/libstd/to_str.rs
index 0e5627fa066..46a9e93f416 100644
--- a/src/libstd/to_str.rs
+++ b/src/libstd/to_str.rs
@@ -16,11 +16,7 @@ The `ToStr` trait for converting to strings
 
 use option::{Some, None};
 use str::OwnedStr;
-use hashmap::HashMap;
-use hashmap::HashSet;
-use hash_old::Hash;
 use iter::Iterator;
-use cmp::Eq;
 use vec::ImmutableVector;
 
 /// A generic trait for converting a value to a string
@@ -40,46 +36,6 @@ impl ToStr for () {
     fn to_str(&self) -> ~str { ~"()" }
 }
 
-impl<A:ToStr+Hash+Eq, B:ToStr> ToStr for HashMap<A, B> {
-    #[inline]
-    fn to_str(&self) -> ~str {
-        let mut acc = ~"{";
-        let mut first = true;
-        for (key, value) in self.iter() {
-            if first {
-                first = false;
-            }
-            else {
-                acc.push_str(", ");
-            }
-            acc.push_str(key.to_str());
-            acc.push_str(": ");
-            acc.push_str(value.to_str());
-        }
-        acc.push_char('}');
-        acc
-    }
-}
-
-impl<A:ToStr+Hash+Eq> ToStr for HashSet<A> {
-    #[inline]
-    fn to_str(&self) -> ~str {
-        let mut acc = ~"{";
-        let mut first = true;
-        for element in self.iter() {
-            if first {
-                first = false;
-            }
-            else {
-                acc.push_str(", ");
-            }
-            acc.push_str(element.to_str());
-        }
-        acc.push_char('}');
-        acc
-    }
-}
-
 impl<'a,A:ToStr> ToStr for &'a [A] {
     #[inline]
     fn to_str(&self) -> ~str {
@@ -120,9 +76,6 @@ impl<A:ToStr> ToStr for ~[A] {
 
 #[cfg(test)]
 mod tests {
-    use hashmap::HashMap;
-    use hashmap::HashSet;
-    use container::{MutableSet, MutableMap};
     use super::*;
 
     #[test]
@@ -146,42 +99,4 @@ mod tests {
         assert!((~[~[], ~[1], ~[1, 1]]).to_str() ==
                ~"[[], [1], [1, 1]]");
     }
-
-    struct StructWithToStrWithoutEqOrHash {
-        value: int
-    }
-
-    impl ToStr for StructWithToStrWithoutEqOrHash {
-        fn to_str(&self) -> ~str {
-            format!("s{}", self.value)
-        }
-    }
-
-    #[test]
-    fn test_hashmap() {
-        let mut table: HashMap<int, StructWithToStrWithoutEqOrHash> = HashMap::new();
-        let empty: HashMap<int, StructWithToStrWithoutEqOrHash> = HashMap::new();
-
-        table.insert(3, StructWithToStrWithoutEqOrHash { value: 4 });
-        table.insert(1, StructWithToStrWithoutEqOrHash { value: 2 });
-
-        let table_str = table.to_str();
-
-        assert!(table_str == ~"{1: s2, 3: s4}" || table_str == ~"{3: s4, 1: s2}");
-        assert_eq!(empty.to_str(), ~"{}");
-    }
-
-    #[test]
-    fn test_hashset() {
-        let mut set: HashSet<int> = HashSet::new();
-        let empty_set: HashSet<int> = HashSet::new();
-
-        set.insert(1);
-        set.insert(2);
-
-        let set_str = set.to_str();
-
-        assert!(set_str == ~"{1, 2}" || set_str == ~"{2, 1}");
-        assert_eq!(empty_set.to_str(), ~"{}");
-    }
 }
diff --git a/src/libstd/vec.rs b/src/libstd/vec.rs
index 0adc6083f6b..b4764f577cb 100644
--- a/src/libstd/vec.rs
+++ b/src/libstd/vec.rs
@@ -3395,7 +3395,6 @@ mod tests {
 
     #[test]
     fn test_permutations() {
-        use hashmap;
         {
             let v: [int, ..0] = [];
             let mut it = v.permutations();
@@ -3418,13 +3417,13 @@ mod tests {
             assert_eq!(it.next(), None);
         }
         {
-            // check that we have N! unique permutations
-            let mut set = hashmap::HashSet::new();
+            // check that we have N! permutations
             let v = ['A', 'B', 'C', 'D', 'E', 'F'];
-            for perm in v.permutations() {
-                set.insert(perm);
+            let mut amt = 0;
+            for _perm in v.permutations() {
+                amt += 1;
             }
-            assert_eq!(set.len(), 2 * 3 * 4 * 5 * 6);
+            assert_eq!(amt, 2 * 3 * 4 * 5 * 6);
         }
     }
 
diff --git a/src/libsyntax/ast.rs b/src/libsyntax/ast.rs
index 9ecc8e50935..db1243b18bc 100644
--- a/src/libsyntax/ast.rs
+++ b/src/libsyntax/ast.rs
@@ -18,7 +18,7 @@ use parse::token::{InternedString, special_idents, str_to_ident};
 use parse::token;
 
 use std::cell::RefCell;
-use std::hashmap::HashMap;
+use collections::HashMap;
 use std::option::Option;
 use std::rc::Rc;
 use std::to_str::ToStr;
@@ -39,7 +39,7 @@ pub fn P<T: 'static>(value: T) -> P<T> {
 // table) and a SyntaxContext to track renaming and
 // macro expansion per Flatt et al., "Macros
 // That Work Together"
-#[deriving(Clone, IterBytes, ToStr, TotalEq, TotalOrd)]
+#[deriving(Clone, IterBytes, ToStr, TotalEq, TotalOrd, Show)]
 pub struct Ident { name: Name, ctxt: SyntaxContext }
 
 impl Ident {
@@ -177,7 +177,7 @@ pub type CrateNum = u32;
 
 pub type NodeId = u32;
 
-#[deriving(Clone, TotalEq, TotalOrd, Eq, Encodable, Decodable, IterBytes, ToStr)]
+#[deriving(Clone, TotalEq, TotalOrd, Eq, Encodable, Decodable, IterBytes, ToStr, Show)]
 pub struct DefId {
     krate: CrateNum,
     node: NodeId,
diff --git a/src/libsyntax/ast_util.rs b/src/libsyntax/ast_util.rs
index 790f3927352..8ff66bc6629 100644
--- a/src/libsyntax/ast_util.rs
+++ b/src/libsyntax/ast_util.rs
@@ -20,7 +20,7 @@ use visit;
 
 use std::cell::{Cell, RefCell};
 use std::cmp;
-use std::hashmap::HashMap;
+use collections::HashMap;
 use std::u32;
 use std::local_data;
 
@@ -964,7 +964,7 @@ mod test {
     use ast::*;
     use super::*;
     use opt_vec;
-    use std::hashmap::HashMap;
+    use collections::HashMap;
 
     fn ident_to_segment(id : &Ident) -> PathSegment {
         PathSegment {identifier:id.clone(),
diff --git a/src/libsyntax/attr.rs b/src/libsyntax/attr.rs
index 78e9d3bd46f..93edb552bbe 100644
--- a/src/libsyntax/attr.rs
+++ b/src/libsyntax/attr.rs
@@ -20,7 +20,7 @@ use parse::token::InternedString;
 use parse::token;
 use crateid::CrateId;
 
-use std::hashmap::HashSet;
+use collections::HashSet;
 
 pub trait AttrMetaMethods {
     // This could be changed to `fn check_name(&self, name: InternedString) ->
diff --git a/src/libsyntax/ext/base.rs b/src/libsyntax/ext/base.rs
index e6fffe8b53f..0636d19163e 100644
--- a/src/libsyntax/ext/base.rs
+++ b/src/libsyntax/ext/base.rs
@@ -19,7 +19,7 @@ use parse::token;
 use parse::token::{InternedString, intern, str_to_ident};
 use util::small_vector::SmallVector;
 
-use std::hashmap::HashMap;
+use collections::HashMap;
 
 // new-style macro! tt code:
 //
diff --git a/src/libsyntax/ext/deriving/show.rs b/src/libsyntax/ext/deriving/show.rs
index 56493000a92..5286720b9fc 100644
--- a/src/libsyntax/ext/deriving/show.rs
+++ b/src/libsyntax/ext/deriving/show.rs
@@ -18,7 +18,7 @@ use ext::deriving::generic::*;
 
 use parse::token;
 
-use std::hashmap::HashMap;
+use collections::HashMap;
 
 pub fn expand_deriving_show(cx: &mut ExtCtxt,
                             span: Span,
diff --git a/src/libsyntax/ext/format.rs b/src/libsyntax/ext/format.rs
index 16a12661e9d..1b73d42c79a 100644
--- a/src/libsyntax/ext/format.rs
+++ b/src/libsyntax/ext/format.rs
@@ -18,8 +18,9 @@ use opt_vec;
 use parse::token::InternedString;
 use parse::token;
 use rsparse = parse;
+
 use std::fmt::parse;
-use std::hashmap::{HashMap, HashSet};
+use collections::{HashMap, HashSet};
 use std::vec;
 
 #[deriving(Eq)]
diff --git a/src/libsyntax/ext/tt/macro_parser.rs b/src/libsyntax/ext/tt/macro_parser.rs
index c2d005da74e..456533de5e9 100644
--- a/src/libsyntax/ext/tt/macro_parser.rs
+++ b/src/libsyntax/ext/tt/macro_parser.rs
@@ -21,7 +21,7 @@ use parse::parser::{LifetimeAndTypesWithoutColons, Parser};
 use parse::token::{Token, EOF, Nonterminal};
 use parse::token;
 
-use std::hashmap::HashMap;
+use collections::HashMap;
 use std::vec;
 
 /* This is an Earley-like parser, without support for in-grammar nonterminals,
diff --git a/src/libsyntax/ext/tt/transcribe.rs b/src/libsyntax/ext/tt/transcribe.rs
index fb2aae9b8c1..a8c9fe37226 100644
--- a/src/libsyntax/ext/tt/transcribe.rs
+++ b/src/libsyntax/ext/tt/transcribe.rs
@@ -18,7 +18,7 @@ use parse::token;
 use parse::lexer::TokenAndSpan;
 
 use std::cell::{Cell, RefCell};
-use std::hashmap::HashMap;
+use collections::HashMap;
 
 ///an unzipping of `TokenTree`s
 struct TtFrame {
diff --git a/src/libsyntax/parse/parser.rs b/src/libsyntax/parse/parser.rs
index 30e77c8c1cb..fed2034cd26 100644
--- a/src/libsyntax/parse/parser.rs
+++ b/src/libsyntax/parse/parser.rs
@@ -79,7 +79,7 @@ use opt_vec;
 use opt_vec::OptVec;
 
 use std::cell::Cell;
-use std::hashmap::HashSet;
+use collections::HashSet;
 use std::kinds::marker;
 use std::mem::replace;
 use std::vec;
diff --git a/src/libsyntax/util/interner.rs b/src/libsyntax/util/interner.rs
index 1c801f7d970..44b366c9890 100644
--- a/src/libsyntax/util/interner.rs
+++ b/src/libsyntax/util/interner.rs
@@ -14,11 +14,11 @@
 
 use ast::Name;
 
+use collections::HashMap;
 use std::cast;
 use std::cell::RefCell;
 use std::cmp::Equiv;
 use std::hash_old::Hash;
-use std::hashmap::HashMap;
 use std::rc::Rc;
 
 pub struct Interner<T> {
diff --git a/src/libterm/lib.rs b/src/libterm/lib.rs
index 1efbd461da8..db9f5d3da5c 100644
--- a/src/libterm/lib.rs
+++ b/src/libterm/lib.rs
@@ -23,6 +23,8 @@
 #[deny(non_camel_case_types)];
 #[allow(missing_doc)];
 
+extern crate collections;
+
 use std::os;
 use std::io;
 use terminfo::TermInfo;
diff --git a/src/libterm/terminfo/mod.rs b/src/libterm/terminfo/mod.rs
index 439297db84e..de8a1dcc363 100644
--- a/src/libterm/terminfo/mod.rs
+++ b/src/libterm/terminfo/mod.rs
@@ -10,7 +10,7 @@
 
 #[allow(missing_doc)];
 
-use std::hashmap::HashMap;
+use collections::HashMap;
 
 /// A parsed terminfo entry.
 pub struct TermInfo {
diff --git a/src/libterm/terminfo/parser/compiled.rs b/src/libterm/terminfo/parser/compiled.rs
index b2d06d3b7d8..e9d71d1c2f7 100644
--- a/src/libterm/terminfo/parser/compiled.rs
+++ b/src/libterm/terminfo/parser/compiled.rs
@@ -14,8 +14,8 @@
 
 
 use std::{vec, str};
-use std::hashmap::HashMap;
 use std::io;
+use collections::HashMap;
 use super::super::TermInfo;
 
 // These are the orders ncurses uses in its compiled format (as of 5.9). Not sure if portable.
diff --git a/src/libuuid/lib.rs b/src/libuuid/lib.rs
index 69780451935..e4053e3bc38 100644
--- a/src/libuuid/lib.rs
+++ b/src/libuuid/lib.rs
@@ -519,6 +519,8 @@ impl rand::Rand for Uuid {
 
 #[cfg(test)]
 mod test {
+    extern crate collections;
+
     use super::{Uuid, VariantMicrosoft, VariantNCS, VariantRFC4122,
                 Version1Mac, Version2Dce, Version3Md5, Version4Random,
                 Version5Sha1};
@@ -800,7 +802,7 @@ mod test {
 
     #[test]
     fn test_iterbytes_impl_for_uuid() {
-        use std::hashmap::HashSet;
+        use self::collections::HashSet;
         let mut set = HashSet::new();
         let id1 = Uuid::new_v4();
         let id2 = Uuid::new_v4();
diff --git a/src/test/auxiliary/issue-2631-a.rs b/src/test/auxiliary/issue-2631-a.rs
index 5c5a80e5d00..1a287b5e625 100644
--- a/src/test/auxiliary/issue-2631-a.rs
+++ b/src/test/auxiliary/issue-2631-a.rs
@@ -13,9 +13,10 @@
 #[crate_type = "lib"];
 
 extern crate extra;
+extern crate collections;
 
 use std::cell::RefCell;
-use std::hashmap::HashMap;
+use collections::HashMap;
 
 pub type header_map = HashMap<~str, @RefCell<~[@~str]>>;
 
diff --git a/src/test/auxiliary/issue-5521.rs b/src/test/auxiliary/issue-5521.rs
index 951e94e47c5..6f964d0824c 100644
--- a/src/test/auxiliary/issue-5521.rs
+++ b/src/test/auxiliary/issue-5521.rs
@@ -10,6 +10,8 @@
 
 #[feature(managed_boxes)];
 
-use std::hashmap::HashMap;
+extern crate collections;
+
+use collections::HashMap;
 
 pub type map = @HashMap<uint, uint>;
diff --git a/src/test/bench/core-map.rs b/src/test/bench/core-map.rs
index ac77e62f2c0..1830a888345 100644
--- a/src/test/bench/core-map.rs
+++ b/src/test/bench/core-map.rs
@@ -11,11 +11,9 @@
 extern crate collections;
 extern crate time;
 
-use collections::TreeMap;
-use std::hashmap::{HashMap, HashSet};
+use collections::{TrieMap, TreeMap, HashMap, HashSet};
 use std::os;
 use std::rand::{Rng, IsaacRng, SeedableRng};
-use std::trie::TrieMap;
 use std::uint;
 use std::vec;
 
diff --git a/src/test/bench/core-set.rs b/src/test/bench/core-set.rs
index 25ced5f35da..d1c311d2a7d 100644
--- a/src/test/bench/core-set.rs
+++ b/src/test/bench/core-set.rs
@@ -15,7 +15,7 @@ extern crate time;
 
 use collections::bitv::BitvSet;
 use collections::TreeSet;
-use std::hashmap::HashSet;
+use collections::HashSet;
 use std::os;
 use std::rand;
 use std::uint;
@@ -177,7 +177,7 @@ fn main() {
             let s: HashSet<~str> = HashSet::new();
             s
         });
-        write_results("std::hashmap::HashSet", &results);
+        write_results("collections::HashSet", &results);
     }
 
     {
diff --git a/src/test/bench/shootout-k-nucleotide-pipes.rs b/src/test/bench/shootout-k-nucleotide-pipes.rs
index 737e5c98214..7188e119a8d 100644
--- a/src/test/bench/shootout-k-nucleotide-pipes.rs
+++ b/src/test/bench/shootout-k-nucleotide-pipes.rs
@@ -14,10 +14,11 @@
 // multi tasking k-nucleotide
 
 extern crate extra;
+extern crate collections;
 
 use std::cmp::Ord;
 use std::comm;
-use std::hashmap::HashMap;
+use collections::HashMap;
 use std::mem::replace;
 use std::option;
 use std::os;
diff --git a/src/test/compile-fail/borrowck-borrowed-uniq-rvalue.rs b/src/test/compile-fail/borrowck-borrowed-uniq-rvalue.rs
index c004b3d0e54..20411723715 100644
--- a/src/test/compile-fail/borrowck-borrowed-uniq-rvalue.rs
+++ b/src/test/compile-fail/borrowck-borrowed-uniq-rvalue.rs
@@ -10,7 +10,8 @@
 
 //buggy.rs
 
-use std::hashmap::HashMap;
+extern crate collections;
+use collections::HashMap;
 
 fn main() {
     let mut buggy_map: HashMap<uint, &uint> = HashMap::new();
diff --git a/src/test/compile-fail/borrowck-insert-during-each.rs b/src/test/compile-fail/borrowck-insert-during-each.rs
index 38ff840ada4..b4781171487 100644
--- a/src/test/compile-fail/borrowck-insert-during-each.rs
+++ b/src/test/compile-fail/borrowck-insert-during-each.rs
@@ -8,7 +8,8 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use std::hashmap::HashSet;
+extern crate collections;
+use collections::HashSet;
 
 struct Foo {
   n: HashSet<int>,
diff --git a/src/test/compile-fail/map-types.rs b/src/test/compile-fail/map-types.rs
index a3b5a1264f7..bd10c6ad8c3 100644
--- a/src/test/compile-fail/map-types.rs
+++ b/src/test/compile-fail/map-types.rs
@@ -8,8 +8,9 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use std::container::Map;
-use std::hashmap::HashMap;
+extern crate collections;
+
+use collections::HashMap;
 
 // Test that trait types printed in error msgs include the type arguments.
 
diff --git a/src/test/run-fail/unwind-misc-1.rs b/src/test/run-fail/unwind-misc-1.rs
index 09e7d0bc28c..f9abb1566bb 100644
--- a/src/test/run-fail/unwind-misc-1.rs
+++ b/src/test/run-fail/unwind-misc-1.rs
@@ -13,9 +13,11 @@
 
 #[feature(managed_boxes)];
 
+extern crate collections;
+
 fn main() {
     let _count = @0u;
-    let mut map = std::hashmap::HashMap::new();
+    let mut map = collections::HashMap::new();
     let mut arr = ~[];
     for _i in range(0u, 10u) {
         arr.push(@~"key stuff");
diff --git a/src/test/run-pass/foreach-external-iterators-hashmap-break-restart.rs b/src/test/run-pass/foreach-external-iterators-hashmap-break-restart.rs
index 34ce8c47113..e2a06162bed 100644
--- a/src/test/run-pass/foreach-external-iterators-hashmap-break-restart.rs
+++ b/src/test/run-pass/foreach-external-iterators-hashmap-break-restart.rs
@@ -8,7 +8,9 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use std::hashmap::HashMap;
+extern crate collections;
+
+use collections::HashMap;
 
 // This is a fancy one: it uses an external iterator established
 // outside the loop, breaks, then _picks back up_ and continues
diff --git a/src/test/run-pass/foreach-external-iterators-hashmap.rs b/src/test/run-pass/foreach-external-iterators-hashmap.rs
index 365cde34dce..e6280b47b6e 100644
--- a/src/test/run-pass/foreach-external-iterators-hashmap.rs
+++ b/src/test/run-pass/foreach-external-iterators-hashmap.rs
@@ -8,7 +8,9 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use std::hashmap::HashMap;
+extern crate collections;
+
+use collections::HashMap;
 
 pub fn main() {
     let mut h = HashMap::new();
diff --git a/src/test/run-pass/hashmap-memory.rs b/src/test/run-pass/hashmap-memory.rs
index 9c05dae46bd..3f3687fd333 100644
--- a/src/test/run-pass/hashmap-memory.rs
+++ b/src/test/run-pass/hashmap-memory.rs
@@ -12,6 +12,8 @@
 
 #[feature(managed_boxes)];
 
+extern crate collections;
+
 /**
    A somewhat reduced test case to expose some Valgrind issues.
 
@@ -21,7 +23,7 @@
 pub fn map(filename: ~str, emit: map_reduce::putter) { emit(filename, ~"1"); }
 
 mod map_reduce {
-    use std::hashmap::HashMap;
+    use collections::HashMap;
     use std::str;
     use std::task;
 
diff --git a/src/test/run-pass/issue-1696.rs b/src/test/run-pass/issue-1696.rs
index 207e402732a..2dbed23677f 100644
--- a/src/test/run-pass/issue-1696.rs
+++ b/src/test/run-pass/issue-1696.rs
@@ -10,7 +10,9 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use std::hashmap::HashMap;
+extern crate collections;
+
+use collections::HashMap;
 
 pub fn main() {
     let mut m = HashMap::new();
diff --git a/src/test/run-pass/issue-2631-b.rs b/src/test/run-pass/issue-2631-b.rs
index 68f2fd95cde..592232ca21d 100644
--- a/src/test/run-pass/issue-2631-b.rs
+++ b/src/test/run-pass/issue-2631-b.rs
@@ -13,11 +13,12 @@
 // ignore-fast
 // aux-build:issue-2631-a.rs
 
+extern crate collections;
 extern crate req;
 
 use req::request;
 use std::cell::RefCell;
-use std::hashmap::HashMap;
+use collections::HashMap;
 
 pub fn main() {
   let v = ~[@~"hi"];
diff --git a/src/test/run-pass/issue-2804-2.rs b/src/test/run-pass/issue-2804-2.rs
index 9357d19d380..5e6ea5f6d44 100644
--- a/src/test/run-pass/issue-2804-2.rs
+++ b/src/test/run-pass/issue-2804-2.rs
@@ -13,7 +13,9 @@
 // Minimized version of issue-2804.rs. Both check that callee IDs don't
 // clobber the previous node ID in a macro expr
 
-use std::hashmap::HashMap;
+extern crate collections;
+
+use collections::HashMap;
 
 fn add_interfaces(managed_ip: ~str, device: HashMap<~str, int>)  {
      error!("{}, {:?}", managed_ip, device.get(&~"interfaces"));
diff --git a/src/test/run-pass/issue-2804.rs b/src/test/run-pass/issue-2804.rs
index a9ac81be0ba..a1bed266817 100644
--- a/src/test/run-pass/issue-2804.rs
+++ b/src/test/run-pass/issue-2804.rs
@@ -10,10 +10,11 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+extern crate collections;
 extern crate extra;
 
 use extra::json;
-use std::hashmap::HashMap;
+use collections::HashMap;
 use std::option;
 
 enum object {
diff --git a/src/test/run-pass/issue-3026.rs b/src/test/run-pass/issue-3026.rs
index c32b24c3847..ee7f3aab47a 100644
--- a/src/test/run-pass/issue-3026.rs
+++ b/src/test/run-pass/issue-3026.rs
@@ -10,7 +10,9 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use std::hashmap::HashMap;
+extern crate collections;
+
+use collections::HashMap;
 
 pub fn main() {
     let mut buggy_map: HashMap<uint, &uint> = HashMap::new();
diff --git a/src/test/run-pass/issue-3559.rs b/src/test/run-pass/issue-3559.rs
index 5cc098e591c..829df5060c3 100644
--- a/src/test/run-pass/issue-3559.rs
+++ b/src/test/run-pass/issue-3559.rs
@@ -8,7 +8,9 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use std::hashmap::HashMap;
+extern crate collections;
+
+use collections::HashMap;
 
 fn check_strs(actual: &str, expected: &str) -> bool {
     if actual != expected {
diff --git a/src/test/run-pass/issue-6128.rs b/src/test/run-pass/issue-6128.rs
index a01a04ebf82..3694421c691 100644
--- a/src/test/run-pass/issue-6128.rs
+++ b/src/test/run-pass/issue-6128.rs
@@ -8,7 +8,9 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use std::hashmap::HashMap;
+extern crate collections;
+
+use collections::HashMap;
 
 trait Graph<Node, Edge> {
     fn f(&self, Edge);
diff --git a/src/test/run-pass/issue-7660.rs b/src/test/run-pass/issue-7660.rs
index 7f1382cf890..eadcdb67f14 100644
--- a/src/test/run-pass/issue-7660.rs
+++ b/src/test/run-pass/issue-7660.rs
@@ -11,7 +11,9 @@
 // Regresion test for issue 7660
 // rvalue lifetime too short when equivalent `match` works
 
-use std::hashmap::HashMap;
+extern crate collections;
+
+use collections::HashMap;
 
 struct A(int, int);
 
diff --git a/src/test/run-pass/regions-mock-tcx.rs b/src/test/run-pass/regions-mock-tcx.rs
index 738a4899f27..6dafd81a018 100644
--- a/src/test/run-pass/regions-mock-tcx.rs
+++ b/src/test/run-pass/regions-mock-tcx.rs
@@ -17,9 +17,10 @@
 // - Arenas
 
 extern crate arena;
+extern crate collections;
 
 use arena::Arena;
-use std::hashmap::HashMap;
+use collections::HashMap;
 use std::cast;
 use std::libc;
 use std::mem;
diff --git a/src/test/run-pass/send_str_hashmap.rs b/src/test/run-pass/send_str_hashmap.rs
index 8599f9d3836..4fd7980e795 100644
--- a/src/test/run-pass/send_str_hashmap.rs
+++ b/src/test/run-pass/send_str_hashmap.rs
@@ -8,6 +8,8 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+extern crate collections;
+
 use std::clone::{Clone, DeepClone};
 use std::cmp::{TotalEq, Ord, TotalOrd, Equiv};
 use std::cmp::Equal;
@@ -15,7 +17,7 @@ use std::container::{Container, Map, MutableMap};
 use std::default::Default;
 use std::str::{Str, SendStr, Owned, Slice};
 use std::to_str::ToStr;
-use std::hashmap::HashMap;
+use collections::HashMap;
 use std::option::Some;
 
 pub fn main() {