Merge remote-tracking branch 'rust-lang/master'

Conflicts:
	mk/tests.mk
	src/liballoc/arc.rs
	src/liballoc/boxed.rs
	src/liballoc/rc.rs
	src/libcollections/bit.rs
	src/libcollections/btree/map.rs
	src/libcollections/btree/set.rs
	src/libcollections/dlist.rs
	src/libcollections/ring_buf.rs
	src/libcollections/slice.rs
	src/libcollections/str.rs
	src/libcollections/string.rs
	src/libcollections/vec.rs
	src/libcollections/vec_map.rs
	src/libcore/any.rs
	src/libcore/array.rs
	src/libcore/borrow.rs
	src/libcore/error.rs
	src/libcore/fmt/mod.rs
	src/libcore/iter.rs
	src/libcore/marker.rs
	src/libcore/ops.rs
	src/libcore/result.rs
	src/libcore/slice.rs
	src/libcore/str/mod.rs
	src/libregex/lib.rs
	src/libregex/re.rs
	src/librustc/lint/builtin.rs
	src/libstd/collections/hash/map.rs
	src/libstd/collections/hash/set.rs
	src/libstd/sync/mpsc/mod.rs
	src/libstd/sync/mutex.rs
	src/libstd/sync/poison.rs
	src/libstd/sync/rwlock.rs
	src/libsyntax/feature_gate.rs
	src/libsyntax/test.rs

3 files changed, 86 insertions, 36 deletions

diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs
index 4ce9639bedb..ae295c3e8e4 100644
--- a/src/libstd/collections/hash/map.rs
+++ b/src/libstd/collections/hash/map.rs
@@ -1,4 +1,4 @@
-// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// Copyright 2014-2015 The Rust Project Developers. See the COPYRIGHT
 // file at the top-level directory of this distribution and at
 // http://rust-lang.org/COPYRIGHT.
 //
@@ -18,7 +18,7 @@ use borrow::BorrowFrom;
 use clone::Clone;
 use cmp::{max, Eq, PartialEq};
 use default::Default;
-use fmt::{self, Show};
+use fmt::{self, Debug};
 use hash::{self, Hash, SipHasher};
 use iter::{self, Iterator, ExactSizeIterator, IteratorExt, FromIterator, Extend, Map};
 use marker::Sized;
@@ -76,7 +76,7 @@ impl DefaultResizePolicy {
         // min_capacity(size) must be smaller than the internal capacity,
         // so that the map is not resized:
         // `min_capacity(usable_capacity(x)) <= x`.
-        // The lef-hand side can only be smaller due to flooring by integer
+        // The left-hand side can only be smaller due to flooring by integer
         // division.
         //
         // This doesn't have to be checked for overflow since allocation size
@@ -270,7 +270,7 @@ fn test_resize_policy() {
 /// ```
 /// use std::collections::HashMap;
 ///
-/// #[derive(Hash, Eq, PartialEq, Show)]
+/// #[derive(Hash, Eq, PartialEq, Debug)]
 /// struct Viking {
 ///     name: String,
 ///     country: String,
@@ -838,8 +838,8 @@ impl<K, V, S, H> HashMap<K, V, S>
     /// map.insert("b", 2);
     /// map.insert("c", 3);
     ///
-    /// for key in map.values() {
-    ///     println!("{}", key);
+    /// for val in map.values() {
+    ///     println!("{}", val);
     /// }
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
@@ -939,7 +939,7 @@ impl<K, V, S, H> HashMap<K, V, S>
         search_entry_hashed(&mut self.table, hash, key)
     }
 
-    /// Return the number of elements in the map.
+    /// Returns the number of elements in the map.
     ///
     /// # Example
     ///
@@ -954,7 +954,7 @@ impl<K, V, S, H> HashMap<K, V, S>
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn len(&self) -> uint { self.table.size() }
 
-    /// Return true if the map contains no elements.
+    /// Returns true if the map contains no elements.
     ///
     /// # Example
     ///
@@ -1218,8 +1218,8 @@ impl<K, V, S, H> Eq for HashMap<K, V, S>
 {}
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<K, V, S, H> Show for HashMap<K, V, S>
-    where K: Eq + Hash<H> + Show, V: Show,
+impl<K, V, S, H> Debug for HashMap<K, V, S>
+    where K: Eq + Hash<H> + Debug, V: Debug,
           S: HashState<Hasher=H>,
           H: hash::Hasher<Output=u64>
 {
@@ -1276,7 +1276,7 @@ impl<K, V, S, H, Q: ?Sized> IndexMut<Q> for HashMap<K, V, S>
     }
 }
 
-/// HashMap iterator
+/// HashMap iterator.
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct Iter<'a, K: 'a, V: 'a> {
     inner: table::Iter<'a, K, V>
@@ -1291,13 +1291,13 @@ impl<'a, K, V> Clone for Iter<'a, K, V> {
     }
 }
 
-/// HashMap mutable values iterator
+/// HashMap mutable values iterator.
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct IterMut<'a, K: 'a, V: 'a> {
     inner: table::IterMut<'a, K, V>
 }
 
-/// HashMap move iterator
+/// HashMap move iterator.
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct IntoIter<K, V> {
     inner: iter::Map<
@@ -1308,7 +1308,7 @@ pub struct IntoIter<K, V> {
     >
 }
 
-/// HashMap keys iterator
+/// HashMap keys iterator.
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct Keys<'a, K: 'a, V: 'a> {
     inner: Map<(&'a K, &'a V), &'a K, Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a K>
@@ -1323,7 +1323,7 @@ impl<'a, K, V> Clone for Keys<'a, K, V> {
     }
 }
 
-/// HashMap values iterator
+/// HashMap values iterator.
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct Values<'a, K: 'a, V: 'a> {
     inner: Map<(&'a K, &'a V), &'a V, Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a V>
@@ -1338,7 +1338,7 @@ impl<'a, K, V> Clone for Values<'a, K, V> {
     }
 }
 
-/// HashMap drain iterator
+/// HashMap drain iterator.
 #[unstable(feature = "std_misc",
            reason = "matches collection reform specification, waiting for dust to settle")]
 pub struct Drain<'a, K: 'a, V: 'a> {
@@ -1350,14 +1350,14 @@ pub struct Drain<'a, K: 'a, V: 'a> {
     >
 }
 
-/// A view into a single occupied location in a HashMap
+/// A view into a single occupied location in a HashMap.
 #[unstable(feature = "std_misc",
            reason = "precise API still being fleshed out")]
 pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
     elem: FullBucket<K, V, &'a mut RawTable<K, V>>,
 }
 
-/// A view into a single empty location in a HashMap
+/// A view into a single empty location in a HashMap.
 #[unstable(feature = "std_misc",
            reason = "precise API still being fleshed out")]
 pub struct VacantEntry<'a, K: 'a, V: 'a> {
@@ -1366,22 +1366,22 @@ pub struct VacantEntry<'a, K: 'a, V: 'a> {
     elem: VacantEntryState<K, V, &'a mut RawTable<K, V>>,
 }
 
-/// A view into a single location in a map, which may be vacant or occupied
+/// A view into a single location in a map, which may be vacant or occupied.
 #[unstable(feature = "std_misc",
            reason = "precise API still being fleshed out")]
 pub enum Entry<'a, K: 'a, V: 'a> {
-    /// An occupied Entry
+    /// An occupied Entry.
     Occupied(OccupiedEntry<'a, K, V>),
-    /// A vacant Entry
+    /// A vacant Entry.
     Vacant(VacantEntry<'a, K, V>),
 }
 
-/// Possible states of a VacantEntry
+/// Possible states of a VacantEntry.
 enum VacantEntryState<K, V, M> {
     /// The index is occupied, but the key to insert has precedence,
-    /// and will kick the current one out on insertion
+    /// and will kick the current one out on insertion.
     NeqElem(FullBucket<K, V, M>, uint),
-    /// The index is genuinely vacant
+    /// The index is genuinely vacant.
     NoElem(EmptyBucket<K, V, M>),
 }
 
@@ -1460,7 +1460,7 @@ impl<'a, K, V> ExactSizeIterator for Drain<'a, K, V> {
 #[unstable(feature = "std_misc",
            reason = "matches collection reform v2 specification, waiting for dust to settle")]
 impl<'a, K, V> Entry<'a, K, V> {
-    /// Returns a mutable reference to the entry if occupied, or the VacantEntry if vacant
+    /// Returns a mutable reference to the entry if occupied, or the VacantEntry if vacant.
     pub fn get(self) -> Result<&'a mut V, VacantEntry<'a, K, V>> {
         match self {
             Occupied(entry) => Ok(entry.into_mut()),
@@ -1472,12 +1472,12 @@ impl<'a, K, V> Entry<'a, K, V> {
 #[unstable(feature = "std_misc",
            reason = "matches collection reform v2 specification, waiting for dust to settle")]
 impl<'a, K, V> OccupiedEntry<'a, K, V> {
-    /// Gets a reference to the value in the entry
+    /// Gets a reference to the value in the entry.
     pub fn get(&self) -> &V {
         self.elem.read().1
     }
 
-    /// Gets a mutable reference to the value in the entry
+    /// Gets a mutable reference to the value in the entry.
     pub fn get_mut(&mut self) -> &mut V {
         self.elem.read_mut().1
     }
@@ -2009,8 +2009,8 @@ mod test_map {
 
         let map_str = format!("{:?}", map);
 
-        assert!(map_str == "HashMap {1i: 2i, 3i: 4i}" ||
-                map_str == "HashMap {3i: 4i, 1i: 2i}");
+        assert!(map_str == "HashMap {1: 2, 3: 4}" ||
+                map_str == "HashMap {3: 4, 1: 2}");
         assert_eq!(format!("{:?}", empty), "HashMap {}");
     }
 
diff --git a/src/libstd/collections/hash/set.rs b/src/libstd/collections/hash/set.rs
index a6ebc402ade..84f01f70c3e 100644
--- a/src/libstd/collections/hash/set.rs
+++ b/src/libstd/collections/hash/set.rs
@@ -15,7 +15,7 @@ use clone::Clone;
 use cmp::{Eq, PartialEq};
 use core::marker::Sized;
 use default::Default;
-use fmt::Show;
+use fmt::Debug;
 use fmt;
 use hash::{self, Hash};
 use iter::{Iterator, ExactSizeIterator, IteratorExt, FromIterator, Map, Chain, Extend};
@@ -71,7 +71,7 @@ use super::state::HashState;
 ///
 /// ```
 /// use std::collections::HashSet;
-/// #[derive(Hash, Eq, PartialEq, Show)]
+/// #[derive(Hash, Eq, PartialEq, Debug)]
 /// struct Viking<'a> {
 ///     name: &'a str,
 ///     power: uint,
@@ -597,8 +597,8 @@ impl<T, S, H> Eq for HashSet<T, S>
 {}
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<T, S, H> fmt::Show for HashSet<T, S>
-    where T: Eq + Hash<H> + fmt::Show,
+impl<T, S, H> fmt::Debug for HashSet<T, S>
+    where T: Eq + Hash<H> + fmt::Debug,
           S: HashState<Hasher=H>,
           H: hash::Hasher<Output=u64>
 {
@@ -1180,7 +1180,7 @@ mod test_set {
 
         let set_str = format!("{:?}", set);
 
-        assert!(set_str == "HashSet {1i, 2i}" || set_str == "HashSet {2i, 1i}");
+        assert!(set_str == "HashSet {1, 2}" || set_str == "HashSet {2, 1}");
         assert_eq!(format!("{:?}", empty), "HashSet {}");
     }
 
diff --git a/src/libstd/collections/mod.rs b/src/libstd/collections/mod.rs
index 1b8780120b1..0c55850b32a 100644
--- a/src/libstd/collections/mod.rs
+++ b/src/libstd/collections/mod.rs
@@ -49,8 +49,8 @@
 //! * You want a double-ended queue (deque).
 //!
 //! ### Use a `DList` when:
-//! * You want a `Vec` or `RingBuf` of unknown size, and can't tolerate inconsistent
-//! performance during insertions.
+//! * You want a `Vec` or `RingBuf` of unknown size, and can't tolerate amortization.
+//! * You want to efficiently split and append lists.
 //! * You are *absolutely* certain you *really*, *truly*, want a doubly linked list.
 //!
 //! ### Use a `HashMap` when:
@@ -85,6 +85,56 @@
 //! or "most important" one at any given time.
 //! * You want a priority queue.
 //!
+//! # Performance
+//!
+//! Choosing the right collection for the job requires an understanding of what each collection
+//! is good at. Here we briefly summarize the performance of different collections for certain
+//! important operations. For further details, see each type's documentation.
+//!
+//! Throughout the documentation, we will follow a few conventions. For all operations,
+//! the collection's size is denoted by n. If another collection is involved in the operation, it
+//! contains m elements. Operations which have an *amortized* cost are suffixed with a `*`.
+//! Operations with an *expected* cost are suffixed with a `~`.
+//!
+//! All amortized costs are for the potential need to resize when capacity is exhausted.
+//! If a resize occurs it will take O(n) time. Our collections never automatically shrink,
+//! so removal operations aren't amortized. Over a sufficiently large series of
+//! operations, the average cost per operation will deterministically equal the given cost.
+//!
+//! Only HashMap has expected costs, due to the probabilistic nature of hashing. It is
+//! theoretically possible, though very unlikely, for HashMap to experience worse performance.
+//!
+//! ## Sequences
+//!
+//! |         | get(i)         | insert(i)       | remove(i)      | append | split_off(i)   |
+//! |---------|----------------|-----------------|----------------|--------|----------------|
+//! | Vec     | O(1)           | O(n-i)*         | O(n-i)         | O(m)*  | O(n-i)         |
+//! | RingBuf | O(1)           | O(min(i, n-i))* | O(min(i, n-i)) | O(m)*  | O(min(i, n-i)) |
+//! | DList   | O(min(i, n-i)) | O(min(i, n-i))  | O(min(i, n-i)) | O(1)   | O(min(i, n-i)) |
+//! | Bitv    | O(1)           | O(n-i)*         | O(n-i)         | O(m)*  | O(n-i)         |
+//!
+//! Note that where ties occur, Vec is generally going to be faster than RingBuf, and RingBuf
+//! is generally going to be faster than DList. Bitv is not a general purpose collection, and
+//! therefore cannot reasonably be compared.
+//!
+//! ## Maps
+//!
+//! For Sets, all operations have the cost of the equivalent Map operation. For BitvSet,
+//! refer to VecMap.
+//!
+//! |          | get       | insert   | remove   | predecessor |
+//! |----------|-----------|----------|----------|-------------|
+//! | HashMap  | O(1)~     | O(1)~*   | O(1)~    | N/A         |
+//! | BTreeMap | O(log n)  | O(log n) | O(log n) | O(log n)    |
+//! | VecMap   | O(1)      | O(1)?    | O(1)     | O(n)        |
+//!
+//! Note that VecMap is *incredibly* inefficient in terms of space. The O(1) insertion time
+//! assumes space for the element is already allocated. Otherwise, a large key may require a
+//! massive reallocation, with no direct relation to the number of elements in the collection.
+//! VecMap should only be seriously considered for small keys.
+//!
+//! Note also that BTreeMap's precise preformance depends on the value of B.
+//!
 //! # Correct and Efficient Usage of Collections
 //!
 //! Of course, knowing which collection is the right one for the job doesn't instantly