auto merge of #14538 : alexcrichton/rust/libcollections, r=brson

As with the previous commit with `librand`, this commit shuffles around some
`collections` code. The new state of the world is similar to that of librand:

* The libcollections crate now only depends on libcore and liballoc.
* The standard library has a new module, `std::collections`. All functionality
  of libcollections is reexported through this module.

I would like to stress that this change is purely cosmetic. There are very few
alterations to these primitives.

There are a number of notable points about the new organization:

* std::{str, slice, string, vec} all moved to libcollections. There is no reason
  that these primitives shouldn't be necessarily usable in a freestanding
  context that has allocation. These are all reexported in their usual places in
  the standard library.

* The `hashmap`, and transitively the `lru_cache`, modules no longer reside in
  `libcollections`, but rather in libstd. The reason for this is because the
  `HashMap::new` contructor requires access to the OSRng for initially seeding
  the hash map. Beyond this requirement, there is no reason that the hashmap
  could not move to libcollections.

  I do, however, have a plan to move the hash map to the collections module. The
  `HashMap::new` function could be altered to require that the `H` hasher
  parameter ascribe to the `Default` trait, allowing the entire `hashmap` module
  to live in libcollections. The key idea would be that the default hasher would
  be different in libstd. Something along the lines of:

      // src/libstd/collections/mod.rs

      pub type HashMap<K, V, H = RandomizedSipHasher> =
            core_collections::HashMap<K, V, H>;

  This is not possible today because you cannot invoke static methods through
  type aliases. If we modified the compiler, however, to allow invocation of
  static methods through type aliases, then this type definition would
  essentially be switching the default hasher from `SipHasher` in libcollections
  to a libstd-defined `RandomizedSipHasher` type. This type's `Default`
  implementation would randomly seed the `SipHasher` instance, and otherwise
  perform the same as `SipHasher`.

  This future state doesn't seem incredibly far off, but until that time comes,
  the hashmap module will live in libstd to not compromise on functionality.

* In preparation for the hashmap moving to libcollections, the `hash` module has
  moved from libstd to libcollections. A previously snapshotted commit enables a
  distinct `Writer` trait to live in the `hash` module which `Hash`
  implementations are now parameterized over.

  Due to using a custom trait, the `SipHasher` implementation has lost its
  specialized methods for writing integers. These can be re-added
  backwards-compatibly in the future via default methods if necessary, but the
  FNV hashing should satisfy much of the need for speedier hashing.

A list of breaking changes:

* HashMap::{get, get_mut} no longer fails with the key formatted into the error
  message with `{:?}`, instead, a generic message is printed. With backtraces,
  it should still be not-too-hard to track down errors.

* The HashMap, HashSet, and LruCache types are now available through
  std::collections instead of the collections crate.

* Manual implementations of hash should be parameterized over `hash::Writer`
  instead of just `Writer`.

[breaking-change]

11 files changed, 13 insertions, 15 deletions

diff --git a/src/libsyntax/attr.rs b/src/libsyntax/attr.rs
index a514ef65e72..a8f30c0514b 100644
--- a/src/libsyntax/attr.rs
+++ b/src/libsyntax/attr.rs
@@ -20,8 +20,8 @@ use parse::token::InternedString;
 use parse::token;
 use crateid::CrateId;
 
-use collections::HashSet;
-use collections::bitv::BitvSet;
+use std::collections::HashSet;
+use std::collections::BitvSet;
 
 local_data_key!(used_attrs: BitvSet)
 
diff --git a/src/libsyntax/ext/base.rs b/src/libsyntax/ext/base.rs
index e4c7fbb1deb..521b7ee0063 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 collections::HashMap;
+use std::collections::HashMap;
 
 // new-style macro! tt code:
 //
diff --git a/src/libsyntax/ext/deriving/show.rs b/src/libsyntax/ext/deriving/show.rs
index b352a702eec..1124cf6d7cb 100644
--- a/src/libsyntax/ext/deriving/show.rs
+++ b/src/libsyntax/ext/deriving/show.rs
@@ -18,7 +18,7 @@ use ext::deriving::generic::*;
 use ext::deriving::generic::ty::*;
 use parse::token;
 
-use collections::HashMap;
+use std::collections::HashMap;
 use std::string::String;
 
 pub fn expand_deriving_show(cx: &mut ExtCtxt,
diff --git a/src/libsyntax/ext/format.rs b/src/libsyntax/ext/format.rs
index 0d228a1146d..2db0d047942 100644
--- a/src/libsyntax/ext/format.rs
+++ b/src/libsyntax/ext/format.rs
@@ -19,7 +19,7 @@ use parse::token;
 use rsparse = parse;
 
 use parse = fmt_macros;
-use collections::{HashMap, HashSet};
+use std::collections::{HashMap, HashSet};
 
 #[deriving(PartialEq)]
 enum ArgumentType {
diff --git a/src/libsyntax/ext/mtwt.rs b/src/libsyntax/ext/mtwt.rs
index 12e314781ae..6c97a8aed1f 100644
--- a/src/libsyntax/ext/mtwt.rs
+++ b/src/libsyntax/ext/mtwt.rs
@@ -19,8 +19,7 @@ use ast::{Ident, Mrk, Name, SyntaxContext};
 
 use std::cell::RefCell;
 use std::rc::Rc;
-
-use collections::HashMap;
+use std::collections::HashMap;
 
 // the SCTable contains a table of SyntaxContext_'s. It
 // represents a flattened tree structure, to avoid having
@@ -267,7 +266,7 @@ mod tests {
     use super::{resolve, xor_push, new_mark_internal, new_sctable_internal};
     use super::{new_rename_internal, marksof_internal, resolve_internal};
     use super::{SCTable, EmptyCtxt, Mark, Rename, IllegalCtxt};
-    use collections::HashMap;
+    use std::collections::HashMap;
 
     #[test]
     fn xorpush_test () {
diff --git a/src/libsyntax/ext/tt/macro_parser.rs b/src/libsyntax/ext/tt/macro_parser.rs
index 65733793d6c..e74861f6efe 100644
--- a/src/libsyntax/ext/tt/macro_parser.rs
+++ b/src/libsyntax/ext/tt/macro_parser.rs
@@ -22,7 +22,7 @@ use parse::token::{Token, EOF, Nonterminal};
 use parse::token;
 
 use std::rc::Rc;
-use collections::HashMap;
+use std::collections::HashMap;
 
 /* This is an Earley-like parser, without support for in-grammar nonterminals,
 only by calling out to the main rust parser for named nonterminals (which it
diff --git a/src/libsyntax/ext/tt/transcribe.rs b/src/libsyntax/ext/tt/transcribe.rs
index 4b0e2171062..748ba6b19da 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::rc::Rc;
-use collections::HashMap;
+use std::collections::HashMap;
 
 ///an unzipping of `TokenTree`s
 #[deriving(Clone)]
diff --git a/src/libsyntax/lib.rs b/src/libsyntax/lib.rs
index b1033c419b1..1ab420eb69b 100644
--- a/src/libsyntax/lib.rs
+++ b/src/libsyntax/lib.rs
@@ -32,7 +32,6 @@ This API is completely unstable and subject to change.
 
 extern crate serialize;
 extern crate term;
-extern crate collections;
 #[phase(syntax, link)]
 extern crate log;
 extern crate fmt_macros;
diff --git a/src/libsyntax/owned_slice.rs b/src/libsyntax/owned_slice.rs
index a514c1e9c5d..28d63ea071a 100644
--- a/src/libsyntax/owned_slice.rs
+++ b/src/libsyntax/owned_slice.rs
@@ -9,7 +9,7 @@
 // except according to those terms.
 
 use std::default::Default;
-use std::hash::Hash;
+use std::hash;
 use std::{mem, raw, ptr, slice};
 use serialize::{Encodable, Decodable, Encoder, Decoder};
 
@@ -107,7 +107,7 @@ impl<T: Clone> Clone for OwnedSlice<T> {
     }
 }
 
-impl<S: Writer, T: Hash<S>> Hash<S> for OwnedSlice<T> {
+impl<S: hash::Writer, T: hash::Hash<S>> hash::Hash<S> for OwnedSlice<T> {
     fn hash(&self, state: &mut S) {
         self.as_slice().hash(state)
     }
diff --git a/src/libsyntax/parse/parser.rs b/src/libsyntax/parse/parser.rs
index 6c09fa20510..4af4385e3c1 100644
--- a/src/libsyntax/parse/parser.rs
+++ b/src/libsyntax/parse/parser.rs
@@ -76,7 +76,7 @@ use parse::token;
 use parse::{new_sub_parser_from_file, ParseSess};
 use owned_slice::OwnedSlice;
 
-use collections::HashSet;
+use std::collections::HashSet;
 use std::mem::replace;
 use std::rc::Rc;
 use std::string::String;
diff --git a/src/libsyntax/util/interner.rs b/src/libsyntax/util/interner.rs
index 66acd576aa1..4d88aaca748 100644
--- a/src/libsyntax/util/interner.rs
+++ b/src/libsyntax/util/interner.rs
@@ -14,7 +14,7 @@
 
 use ast::Name;
 
-use collections::HashMap;
+use std::collections::HashMap;
 use std::cell::RefCell;
 use std::cmp::Equiv;
 use std::fmt;