moved collections from libextra into libcollections

35 files changed, 109 insertions, 66 deletions

diff --git a/src/doc/index.md b/src/doc/index.md
index 39dc196b6a0..a552a48714b 100644
--- a/src/doc/index.md
+++ b/src/doc/index.md
@@ -38,6 +38,7 @@ li {list-style-type: none; }
 * [The Rust compiler, `librustc`](rustc/index.html)
 
 * [The `arena` allocation library](arena/index.html)
+* [The `collections` library](collections/index.html)
 * [The `flate` compression library](flate/index.html)
 * [The `getopts` argument parsing library](getopts/index.html)
 * [The `glob` file path matching library](glob/index.html)
diff --git a/src/doc/rust.md b/src/doc/rust.md
index ff2e2b52369..4a611fe7d53 100644
--- a/src/doc/rust.md
+++ b/src/doc/rust.md
@@ -881,7 +881,7 @@ use foo::baz::foobaz;    // good: foo is at the root of the crate
 mod foo {
     extern mod extra;
 
-    use foo::extra::list;  // good: foo is at crate root
+    use foo::extra::time;  // good: foo is at crate root
 //  use extra::*;          // bad:  extra is not at the crate root
     use self::baz::foobaz; // good: self refers to module 'foo'
     use foo::bar::foobar;  // good: foo is at crate root
diff --git a/src/libarena/lib.rs b/src/libarena/lib.rs
index 9bd4c1d58fc..cd9b638a5c2 100644
--- a/src/libarena/lib.rs
+++ b/src/libarena/lib.rs
@@ -22,10 +22,12 @@
 #[allow(missing_doc)];
 #[feature(managed_boxes)];
 
-extern mod extra;
+extern mod collections;
 
-use extra::list::{List, Cons, Nil};
-use extra::list;
+#[cfg(test)] extern mod extra;
+
+use collections::list::{List, Cons, Nil};
+use collections::list;
 
 use std::cast::{transmute, transmute_mut, transmute_mut_region};
 use std::cast;
diff --git a/src/libextra/bitv.rs b/src/libcollections/bitv.rs
index 7211907f483..7211907f483 100644
--- a/src/libextra/bitv.rs
+++ b/src/libcollections/bitv.rs
diff --git a/src/libextra/btree.rs b/src/libcollections/btree.rs
index 791673d75bb..791673d75bb 100644
--- a/src/libextra/btree.rs
+++ b/src/libcollections/btree.rs
diff --git a/src/libextra/container.rs b/src/libcollections/deque.rs
index 0ba00510ed8..325f0ee4edb 100644
--- a/src/libextra/container.rs
+++ b/src/libcollections/deque.rs
@@ -44,7 +44,7 @@ pub mod bench {
     use std::container::MutableMap;
     use std::{vec, rand};
     use std::rand::Rng;
-    use test::BenchHarness;
+    use extra::test::BenchHarness;
 
     pub fn insert_rand_n<M:MutableMap<uint,uint>>(n: uint,
                                                   map: &mut M,
diff --git a/src/libextra/dlist.rs b/src/libcollections/dlist.rs
index 88df73845d0..2b7c5d37336 100644
--- a/src/libextra/dlist.rs
+++ b/src/libcollections/dlist.rs
@@ -28,7 +28,7 @@ use std::util;
 use std::iter::Rev;
 use std::iter;
 
-use container::Deque;
+use deque::Deque;
 
 use serialize::{Encodable, Decodable, Encoder, Decoder};
 
@@ -657,7 +657,7 @@ impl<D:Decoder,T:Decodable<D>> Decodable<D> for DList<T> {
 
 #[cfg(test)]
 mod tests {
-    use container::Deque;
+    use deque::Deque;
     use extra::test;
     use std::rand;
     use super::{DList, Node, ListInsertion};
diff --git a/src/libcollections/lib.rs b/src/libcollections/lib.rs
new file mode 100644
index 00000000000..417bf47803e
--- /dev/null
+++ b/src/libcollections/lib.rs
@@ -0,0 +1,46 @@
+// Copyright 2013-2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+/*!
+ * Collection types.
+ */
+
+#[crate_id = "collections#0.10-pre"];
+#[crate_type = "rlib"];
+#[crate_type = "dylib"];
+#[license = "MIT/ASL2"];
+
+#[feature(macro_rules, managed_boxes)];
+
+#[cfg(test)] extern mod extra;
+
+extern mod serialize;
+
+pub use bitv::Bitv;
+pub use btree::BTree;
+pub use deque::Deque;
+pub use dlist::DList;
+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 mod bitv;
+pub mod btree;
+pub mod deque;
+pub mod dlist;
+pub mod list;
+pub mod lru_cache;
+pub mod priority_queue;
+pub mod ringbuf;
+pub mod smallintmap;
+pub mod treemap;
\ No newline at end of file
diff --git a/src/libextra/list.rs b/src/libcollections/list.rs
index b530d9c9bc1..79d0f3f49a7 100644
--- a/src/libextra/list.rs
+++ b/src/libcollections/list.rs
@@ -153,7 +153,7 @@ pub fn each<T>(l: @List<T>, f: |&T| -> bool) -> bool {
 
 #[cfg(test)]
 mod tests {
-    use list::*;
+    use list::{List, Nil, from_vec, head, is_empty, tail};
     use list;
 
     use std::option;
diff --git a/src/libextra/lru_cache.rs b/src/libcollections/lru_cache.rs
index f602db2e54d..de7b511fd41 100644
--- a/src/libextra/lru_cache.rs
+++ b/src/libcollections/lru_cache.rs
@@ -17,7 +17,7 @@
 //! # Example
 //!
 //! ```rust
-//! use extra::lru_cache::LruCache;
+//! use collections::LruCache;
 //!
 //! let mut cache: LruCache<int, int> = LruCache::new(2);
 //! cache.put(1, 10);
diff --git a/src/libextra/priority_queue.rs b/src/libcollections/priority_queue.rs
index 3ae3dae9ea3..3ae3dae9ea3 100644
--- a/src/libextra/priority_queue.rs
+++ b/src/libcollections/priority_queue.rs
diff --git a/src/libextra/ringbuf.rs b/src/libcollections/ringbuf.rs
index 17631f5bdff..933fe2048e4 100644
--- a/src/libextra/ringbuf.rs
+++ b/src/libcollections/ringbuf.rs
@@ -17,7 +17,7 @@ use std::num;
 use std::vec;
 use std::iter::{Rev, RandomAccessIterator};
 
-use container::Deque;
+use deque::Deque;
 
 use serialize::{Encodable, Decodable, Encoder, Decoder};
 
@@ -431,7 +431,7 @@ impl<D:Decoder,T:Decodable<D>> Decodable<D> for RingBuf<T> {
 
 #[cfg(test)]
 mod tests {
-    use container::Deque;
+    use deque::Deque;
     use extra::test;
     use std::clone::Clone;
     use std::cmp::Eq;
diff --git a/src/libextra/smallintmap.rs b/src/libcollections/smallintmap.rs
index abbd987a9c4..b996f0dea32 100644
--- a/src/libextra/smallintmap.rs
+++ b/src/libcollections/smallintmap.rs
@@ -471,9 +471,9 @@ mod test_map {
 #[cfg(test)]
 mod bench {
 
-    use super::*;
-    use test::BenchHarness;
-    use container::bench::*;
+    use super::SmallIntMap;
+    use extra::test::BenchHarness;
+    use deque::bench::{insert_rand_n, insert_seq_n, find_rand_n, find_seq_n};
 
     // Find seq
     #[bench]
diff --git a/src/libextra/treemap.rs b/src/libcollections/treemap.rs
index 449e72dd0ec..0fccc57b29e 100644
--- a/src/libextra/treemap.rs
+++ b/src/libcollections/treemap.rs
@@ -1495,9 +1495,9 @@ mod test_treemap {
 #[cfg(test)]
 mod bench {
 
-    use super::*;
-    use test::BenchHarness;
-    use container::bench::*;
+    use super::TreeMap;
+    use extra::test::BenchHarness;
+    use deque::bench::{insert_rand_n, insert_seq_n, find_rand_n, find_seq_n};
 
     // Find seq
     #[bench]
@@ -1555,7 +1555,7 @@ mod bench {
 #[cfg(test)]
 mod test_set {
 
-    use super::*;
+    use super::{TreeMap, TreeSet};
 
     #[test]
     fn test_clear() {
diff --git a/src/libextra/json.rs b/src/libextra/json.rs
index 8b082bf3056..75bbd3d8a01 100644
--- a/src/libextra/json.rs
+++ b/src/libextra/json.rs
@@ -98,9 +98,11 @@ A basic `ToJson` example using a TreeMap of attribute name / attribute value:
 
 
 ```rust
+extern mod collections;
+
 use extra::json;
 use extra::json::ToJson;
-use extra::treemap::TreeMap;
+use collections::TreeMap;
 
 pub struct MyStruct  {
     attr1: u8,
@@ -185,10 +187,12 @@ Example of `ToJson` trait implementation for TestStruct1.
 
 ```rust
 extern mod serialize;
+extern mod collections;
+
 use extra::json;
 use extra::json::ToJson;
 use serialize::{Encodable, Decodable};
-use extra::treemap::TreeMap;
+use collections::TreeMap;
 
 #[deriving(Decodable, Encodable)] // generate Decodable, Encodable impl.
 pub struct TestStruct1  {
@@ -236,7 +240,7 @@ use std::to_str;
 
 use serialize::Encodable;
 use serialize;
-use treemap::TreeMap;
+use collections::TreeMap;
 
 macro_rules! if_ok( ($e:expr) => (
     match $e { Ok(e) => e, Err(e) => { self.error = Err(e); return } }
@@ -1588,7 +1592,7 @@ mod tests {
 
     use std::io;
     use serialize::{Encodable, Decodable};
-    use treemap::TreeMap;
+    use collections::TreeMap;
 
     #[deriving(Eq, Encodable, Decodable)]
     enum Animal {
diff --git a/src/libextra/lib.rs b/src/libextra/lib.rs
index 97c38a59af8..519192fd177 100644
--- a/src/libextra/lib.rs
+++ b/src/libextra/lib.rs
@@ -38,6 +38,8 @@ extern mod sync;
 #[cfg(not(stage0))]
 extern mod serialize;
 
+extern mod collections;
+
 #[cfg(stage0)]
 pub mod serialize {
     #[allow(missing_doc)];
@@ -47,29 +49,10 @@ pub mod serialize {
                                    EncoderHelpers, DecoderHelpers};
 }
 
-#[cfg(stage0)]
-macro_rules! if_ok (
-    ($e:expr) => (match $e { Ok(e) => e, Err(e) => return Err(e) })
-)
-
 // Utility modules
 
 pub mod c_vec;
 
-// Collections
-
-pub mod container;
-pub mod bitv;
-pub mod list;
-pub mod ringbuf;
-pub mod priority_queue;
-pub mod smallintmap;
-
-pub mod dlist;
-pub mod treemap;
-pub mod btree;
-pub mod lru_cache;
-
 // And ... other stuff
 
 pub mod url;
diff --git a/src/libextra/test.rs b/src/libextra/test.rs
index 4af0fa16233..d1fffd9e515 100644
--- a/src/libextra/test.rs
+++ b/src/libextra/test.rs
@@ -24,7 +24,7 @@ use serialize::Decodable;
 use stats::Stats;
 use stats;
 use time::precise_time_ns;
-use treemap::TreeMap;
+use collections::TreeMap;
 
 use std::clone::Clone;
 use std::io;
diff --git a/src/libextra/workcache.rs b/src/libextra/workcache.rs
index d16edb7aa1e..007b54adbe5 100644
--- a/src/libextra/workcache.rs
+++ b/src/libextra/workcache.rs
@@ -14,7 +14,7 @@ use json;
 use json::ToJson;
 use serialize::{Encoder, Encodable, Decoder, Decodable};
 use sync::{Arc,RWArc};
-use treemap::TreeMap;
+use collections::TreeMap;
 use std::str;
 use std::io;
 use std::io::{File, MemWriter};
diff --git a/src/librustc/lib.rs b/src/librustc/lib.rs
index 452499af7cf..b6efd66dfbd 100644
--- a/src/librustc/lib.rs
+++ b/src/librustc/lib.rs
@@ -38,6 +38,7 @@ extern mod syntax;
 extern mod serialize;
 extern mod sync;
 extern mod getopts;
+extern mod collections;
 
 use back::link;
 use driver::session;
diff --git a/src/librustc/middle/lint.rs b/src/librustc/middle/lint.rs
index 3568f59d9a2..0ebfa8c393c 100644
--- a/src/librustc/middle/lint.rs
+++ b/src/librustc/middle/lint.rs
@@ -56,7 +56,7 @@ use std::u16;
 use std::u32;
 use std::u64;
 use std::u8;
-use extra::smallintmap::SmallIntMap;
+use collections::SmallIntMap;
 use syntax::ast_map;
 use syntax::ast_util::IdVisitingOperation;
 use syntax::attr::{AttrMetaMethods, AttributeMethods};
diff --git a/src/librustc/middle/typeck/infer/mod.rs b/src/librustc/middle/typeck/infer/mod.rs
index abaeefd5167..496170c3e47 100644
--- a/src/librustc/middle/typeck/infer/mod.rs
+++ b/src/librustc/middle/typeck/infer/mod.rs
@@ -20,7 +20,7 @@ pub use middle::typeck::infer::resolve::{resolve_ivar, resolve_all};
 pub use middle::typeck::infer::resolve::{resolve_nested_tvar};
 pub use middle::typeck::infer::resolve::{resolve_rvar};
 
-use extra::smallintmap::SmallIntMap;
+use collections::SmallIntMap;
 use middle::ty::{TyVid, IntVid, FloatVid, RegionVid, Vid};
 use middle::ty;
 use middle::ty_fold;
diff --git a/src/librustc/middle/typeck/infer/unify.rs b/src/librustc/middle/typeck/infer/unify.rs
index e34947930fa..c55bdcd0bf9 100644
--- a/src/librustc/middle/typeck/infer/unify.rs
+++ b/src/librustc/middle/typeck/infer/unify.rs
@@ -9,7 +9,7 @@
 // except according to those terms.
 
 
-use extra::smallintmap::SmallIntMap;
+use collections::SmallIntMap;
 
 use middle::ty::{Vid, expected_found, IntVarValue};
 use middle::ty;
diff --git a/src/librustc/middle/typeck/mod.rs b/src/librustc/middle/typeck/mod.rs
index 6d2e06c34ca..b6ad8cc6c43 100644
--- a/src/librustc/middle/typeck/mod.rs
+++ b/src/librustc/middle/typeck/mod.rs
@@ -71,8 +71,8 @@ use util::ppaux;
 use std::cell::RefCell;
 use std::hashmap::HashMap;
 use std::rc::Rc;
-use extra::list::List;
-use extra::list;
+use collections::List;
+use collections::list;
 use syntax::codemap::Span;
 use syntax::print::pprust::*;
 use syntax::{ast, ast_map, abi};
diff --git a/src/librustdoc/lib.rs b/src/librustdoc/lib.rs
index f659c8646f5..3dbf4726ae4 100644
--- a/src/librustdoc/lib.rs
+++ b/src/librustdoc/lib.rs
@@ -21,6 +21,7 @@ extern mod extra;
 extern mod serialize;
 extern mod sync;
 extern mod getopts;
+extern mod collections;
 
 use std::local_data;
 use std::io;
@@ -326,7 +327,7 @@ fn json_output(crate: clean::Crate, res: ~[plugins::PluginJson],
     //   "crate": { parsed crate ... },
     //   "plugins": { output of plugins ... }
     // }
-    let mut json = ~extra::treemap::TreeMap::new();
+    let mut json = ~collections::TreeMap::new();
     json.insert(~"schema", json::String(SCHEMA_VERSION.to_owned()));
     let plugins_json = ~res.move_iter().filter_map(|opt| opt).collect();
 
diff --git a/src/libsyntax/ast_map.rs b/src/libsyntax/ast_map.rs
index 89209ab2104..817668f2232 100644
--- a/src/libsyntax/ast_map.rs
+++ b/src/libsyntax/ast_map.rs
@@ -22,7 +22,7 @@ use util::small_vector::SmallVector;
 
 use std::logging;
 use std::cell::RefCell;
-use extra::smallintmap::SmallIntMap;
+use collections::SmallIntMap;
 
 #[deriving(Clone, Eq)]
 pub enum PathElem {
diff --git a/src/libsyntax/lib.rs b/src/libsyntax/lib.rs
index 3f305a4eb0e..613416bed1c 100644
--- a/src/libsyntax/lib.rs
+++ b/src/libsyntax/lib.rs
@@ -35,6 +35,7 @@ This API is completely unstable and subject to change.
 extern mod extra;
 extern mod serialize;
 extern mod term;
+extern mod collections;
 
 pub mod util {
     pub mod interner;
diff --git a/src/test/bench/core-map.rs b/src/test/bench/core-map.rs
index 4c75ca494ff..ed3874b1a6f 100644
--- a/src/test/bench/core-map.rs
+++ b/src/test/bench/core-map.rs
@@ -9,9 +9,10 @@
 // except according to those terms.
 
 extern mod extra;
+extern mod collections;
 
 use extra::time;
-use extra::treemap::TreeMap;
+use collections::TreeMap;
 use std::hashmap::{HashMap, HashSet};
 use std::os;
 use std::rand::{Rng, IsaacRng, SeedableRng};
diff --git a/src/test/bench/core-set.rs b/src/test/bench/core-set.rs
index c8f5dda41d8..eb985f8f7eb 100644
--- a/src/test/bench/core-set.rs
+++ b/src/test/bench/core-set.rs
@@ -11,9 +11,10 @@
 // except according to those terms.
 
 extern mod extra;
+extern mod collections;
 
-use extra::bitv::BitvSet;
-use extra::treemap::TreeSet;
+use collections::bitv::BitvSet;
+use collections::TreeSet;
 use std::hashmap::HashSet;
 use std::os;
 use std::rand;
diff --git a/src/test/bench/std-smallintmap.rs b/src/test/bench/std-smallintmap.rs
index e1b1f59298e..58f667b929f 100644
--- a/src/test/bench/std-smallintmap.rs
+++ b/src/test/bench/std-smallintmap.rs
@@ -11,8 +11,9 @@
 // Microbenchmark for the smallintmap library
 
 extern mod extra;
+extern mod collections;
 
-use extra::smallintmap::SmallIntMap;
+use collections::SmallIntMap;
 use std::os;
 use std::uint;
 
diff --git a/src/test/bench/task-perf-alloc-unwind.rs b/src/test/bench/task-perf-alloc-unwind.rs
index 58fdadc2064..42b564edbc5 100644
--- a/src/test/bench/task-perf-alloc-unwind.rs
+++ b/src/test/bench/task-perf-alloc-unwind.rs
@@ -11,8 +11,9 @@
 #[feature(managed_boxes)];
 
 extern mod extra;
+extern mod collections;
 
-use extra::list::{List, Cons, Nil};
+use collections::list::{List, Cons, Nil};
 use extra::time::precise_time_s;
 use std::os;
 use std::task;
diff --git a/src/test/run-pass/bitv-perf-test.rs b/src/test/run-pass/bitv-perf-test.rs
index a3e11d27f27..8839c53f14c 100644
--- a/src/test/run-pass/bitv-perf-test.rs
+++ b/src/test/run-pass/bitv-perf-test.rs
@@ -10,8 +10,8 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-extern mod extra;
-use extra::bitv::Bitv;
+extern mod collections;
+use collections::Bitv;
 
 fn bitv_test() {
     let mut v1 = ~Bitv::new(31, false);
diff --git a/src/test/run-pass/issue-2383.rs b/src/test/run-pass/issue-2383.rs
index 0314c7fed02..e7eea698ae7 100644
--- a/src/test/run-pass/issue-2383.rs
+++ b/src/test/run-pass/issue-2383.rs
@@ -10,9 +10,9 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-extern mod extra;
-use extra::ringbuf::RingBuf;
-use extra::container::Deque;
+extern mod collections;
+use collections::RingBuf;
+use collections::Deque;
 
 pub fn main() {
     let mut q = RingBuf::new();
diff --git a/src/test/run-pass/log-knows-the-names-of-variants-in-std.rs b/src/test/run-pass/log-knows-the-names-of-variants-in-std.rs
index 77bac4d12fc..a96c01e56d9 100644
--- a/src/test/run-pass/log-knows-the-names-of-variants-in-std.rs
+++ b/src/test/run-pass/log-knows-the-names-of-variants-in-std.rs
@@ -10,8 +10,8 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-extern mod extra;
-use extra::list;
+extern mod collections;
+use collections::list;
 
 #[deriving(Clone)]
 enum foo {
diff --git a/src/test/run-pass/non-boolean-pure-fns.rs b/src/test/run-pass/non-boolean-pure-fns.rs
index 408c6c037cc..e6fe0873d62 100644
--- a/src/test/run-pass/non-boolean-pure-fns.rs
+++ b/src/test/run-pass/non-boolean-pure-fns.rs
@@ -12,9 +12,9 @@
 
 #[feature(managed_boxes)];
 
-extern mod extra;
+extern mod collections;
 
-use extra::list::{List, Cons, Nil, head, is_empty};
+use collections::list::{List, Cons, Nil, head, is_empty};
 
 fn pure_length_go<T:Clone>(ls: @List<T>, acc: uint) -> uint {
     match *ls { Nil => { acc } Cons(_, tl) => { pure_length_go(tl, acc + 1u) } }
diff --git a/src/test/run-pass/send_str_treemap.rs b/src/test/run-pass/send_str_treemap.rs
index 23ad0ac3091..6332d779e5e 100644
--- a/src/test/run-pass/send_str_treemap.rs
+++ b/src/test/run-pass/send_str_treemap.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-extern mod extra;
+extern mod collections;
 
 use std::clone::{Clone, DeepClone};
 use std::cmp::{TotalEq, Ord, TotalOrd, Equiv};
@@ -18,7 +18,7 @@ use std::default::Default;
 use std::send_str::{SendStr, SendStrOwned, SendStrStatic};
 use std::str::Str;
 use std::to_str::ToStr;
-use self::extra::treemap::TreeMap;
+use self::collections::TreeMap;
 use std::option::Some;
 
 pub fn main() {