auto merge of #15611 : brson/rust/pushpop, r=alexcrichton

This fixes naming conventions for `push`/`pop` from either end of a structure by partially implementing @erickt's suggestion from https://github.com/rust-lang/rust/issues/10852#issuecomment-30823343, namely:

* push/pop from the 'back' are called `push` and `pop`.
* push/pop from the 'front' are called `push_front` and `pop_front`.
* `push`/`pop` are declared on the `MutableSeq` trait.
* Implement `MutableSeq` for `Vec`, `DList`, and `RingBuf`.
* Add `MutableSeq` to the prelude.

I did not make any further refactorings because there is some more extensive thought that needs to be put into the collections traits. This is an easy first step that should close https://github.com/rust-lang/rust/issues/10852.

I left the `push_back` and `pop_back` methods on `DList` and `RingBuf` deprecated. Because `MutableSeq` is in the prelude it shouldn't break many, but it is a breaking change.

44 files changed, 212 insertions, 237 deletions

diff --git a/src/compiletest/runtest.rs b/src/compiletest/runtest.rs
index c3ac40e8f08..6720b9a530f 100644
--- a/src/compiletest/runtest.rs
+++ b/src/compiletest/runtest.rs
@@ -1178,7 +1178,7 @@ fn make_run_args(config: &Config, props: &TestProps, testfile: &Path) ->
     // Add the arguments in the run_flags directive
     args.push_all_move(split_maybe_args(&props.run_flags));
 
-    let prog = args.shift().unwrap();
+    let prog = args.remove(0).unwrap();
     return ProcArgs {
         prog: prog,
         args: args,
diff --git a/src/etc/vim/syntax/rust.vim b/src/etc/vim/syntax/rust.vim
index e3fadccd1c9..0204d42a726 100644
--- a/src/etc/vim/syntax/rust.vim
+++ b/src/etc/vim/syntax/rust.vim
@@ -100,7 +100,7 @@ syn keyword rustTrait Clone
 syn keyword rustTrait PartialEq PartialOrd Eq Ord Equiv
 syn keyword rustEnum Ordering
 syn keyword rustEnumVariant Less Equal Greater
-syn keyword rustTrait Collection Mutable Map MutableMap
+syn keyword rustTrait Collection Mutable Map MutableMap MutableSeq
 syn keyword rustTrait Set MutableSet
 syn keyword rustTrait FromIterator Extendable ExactSize
 syn keyword rustTrait Iterator DoubleEndedIterator
diff --git a/src/liballoc/arc.rs b/src/liballoc/arc.rs
index 9b4f879e61e..27174de8e74 100644
--- a/src/liballoc/arc.rs
+++ b/src/liballoc/arc.rs
@@ -268,6 +268,7 @@ impl<T: Share + Send> Drop for Weak<T> {
 #[allow(experimental)]
 mod tests {
     use std::clone::Clone;
+    use std::collections::MutableSeq;
     use std::comm::channel;
     use std::mem::drop;
     use std::ops::Drop;
diff --git a/src/libcollections/bitv.rs b/src/libcollections/bitv.rs
index f1e9eabe8d1..44af3d52db9 100644
--- a/src/libcollections/bitv.rs
+++ b/src/libcollections/bitv.rs
@@ -72,7 +72,7 @@ use core::slice;
 use core::uint;
 use std::hash;
 
-use {Collection, Mutable, Set, MutableSet};
+use {Collection, Mutable, Set, MutableSet, MutableSeq};
 use vec::Vec;
 
 
@@ -1574,7 +1574,7 @@ mod tests {
     use std::rand::Rng;
     use test::Bencher;
 
-    use {Set, Mutable, MutableSet};
+    use {Set, Mutable, MutableSet, MutableSeq};
     use bitv::{Bitv, BitvSet, from_fn, from_bytes};
     use bitv;
     use vec::Vec;
diff --git a/src/libcollections/btree.rs b/src/libcollections/btree.rs
index e4605527ce5..947c87daa84 100644
--- a/src/libcollections/btree.rs
+++ b/src/libcollections/btree.rs
@@ -24,7 +24,7 @@ use alloc::boxed::Box;
 use core::fmt;
 use core::fmt::Show;
 
-use Collection;
+use {Collection, MutableSeq};
 use vec::Vec;
 
 #[allow(missing_doc)]
@@ -782,6 +782,8 @@ mod test_btree {
 
     use super::{BTree, Node, LeafElt};
 
+    use MutableSeq;
+
     //Tests the functionality of the insert methods (which are unfinished).
     #[test]
     fn insert_test_one() {
diff --git a/src/libcollections/dlist.rs b/src/libcollections/dlist.rs
index 48ea1bd1c01..68b6416b69b 100644
--- a/src/libcollections/dlist.rs
+++ b/src/libcollections/dlist.rs
@@ -30,7 +30,7 @@ use core::iter;
 use core::mem;
 use core::ptr;
 
-use {Collection, Mutable, Deque};
+use {Collection, Mutable, Deque, MutableSeq};
 
 /// A doubly-linked list.
 pub struct DList<T> {
@@ -249,18 +249,13 @@ impl<T> Deque<T> for DList<T> {
     fn pop_front(&mut self) -> Option<T> {
         self.pop_front_node().map(|box Node{value, ..}| value)
     }
+}
 
-    /// Add an element last in the list
-    ///
-    /// O(1)
-    fn push_back(&mut self, elt: T) {
+impl<T> MutableSeq<T> for DList<T> {
+    fn push(&mut self, elt: T) {
         self.push_back_node(box Node::new(elt))
     }
-
-    /// Remove the last element and return it, or None if the list is empty
-    ///
-    /// O(1)
-    fn pop_back(&mut self) -> Option<T> {
+    fn pop(&mut self) -> Option<T> {
         self.pop_back_node().map(|box Node{value, ..}| value)
     }
 }
@@ -284,12 +279,12 @@ impl<T> DList<T> {
     /// # Example
     ///
     /// ```rust
-    /// use std::collections::{DList, Deque};
+    /// use std::collections::DList;
     ///
     /// let mut dl = DList::new();
-    /// dl.push_back(1i);
-    /// dl.push_back(2);
-    /// dl.push_back(3);
+    /// dl.push(1i);
+    /// dl.push(2);
+    /// dl.push(3);
     ///
     /// dl.rotate_forward();
     ///
@@ -311,12 +306,12 @@ impl<T> DList<T> {
     /// # Example
     ///
     /// ```rust
-    /// use std::collections::{DList, Deque};
+    /// use std::collections::DList;
     ///
     /// let mut dl = DList::new();
-    /// dl.push_back(1i);
-    /// dl.push_back(2);
-    /// dl.push_back(3);
+    /// dl.push(1i);
+    /// dl.push(2);
+    /// dl.push(3);
     ///
     /// dl.rotate_backward();
     ///
@@ -338,14 +333,14 @@ impl<T> DList<T> {
     /// # Example
     ///
     /// ```rust
-    /// use std::collections::{DList, Deque};
+    /// use std::collections::DList;
     ///
     /// let mut a = DList::new();
     /// let mut b = DList::new();
-    /// a.push_back(1i);
-    /// a.push_back(2);
-    /// b.push_back(3i);
-    /// b.push_back(4);
+    /// a.push(1i);
+    /// a.push(2);
+    /// b.push(3i);
+    /// b.push(4);
     ///
     /// a.append(b);
     ///
@@ -379,14 +374,14 @@ impl<T> DList<T> {
     /// # Example
     ///
     /// ```rust
-    /// use std::collections::{DList, Deque};
+    /// use std::collections::DList;
     ///
     /// let mut a = DList::new();
     /// let mut b = DList::new();
-    /// a.push_back(1i);
-    /// a.push_back(2);
-    /// b.push_back(3i);
-    /// b.push_back(4);
+    /// a.push(1i);
+    /// a.push(2);
+    /// b.push(3i);
+    /// b.push(4);
     ///
     /// a.prepend(b);
     ///
@@ -408,13 +403,13 @@ impl<T> DList<T> {
     /// # Example
     ///
     /// ```rust
-    /// use std::collections::{DList, Deque};
+    /// use std::collections::DList;
     ///
     /// let mut a: DList<int> = DList::new();
-    /// a.push_back(2i);
-    /// a.push_back(4);
-    /// a.push_back(7);
-    /// a.push_back(8);
+    /// a.push(2i);
+    /// a.push(4);
+    /// a.push(7);
+    /// a.push(8);
     ///
     /// // insert 11 before the first odd number in the list
     /// a.insert_when(11, |&e, _| e % 2 == 1);
@@ -719,7 +714,7 @@ mod tests {
     use test::Bencher;
     use test;
 
-    use Deque;
+    use {Deque, MutableSeq};
     use super::{DList, Node, ListInsertion};
     use vec::Vec;
 
diff --git a/src/libcollections/enum_set.rs b/src/libcollections/enum_set.rs
index 1360b412c23..ca3f6a746f3 100644
--- a/src/libcollections/enum_set.rs
+++ b/src/libcollections/enum_set.rs
@@ -141,6 +141,8 @@ mod test {
 
     use enum_set::{EnumSet, CLike};
 
+    use MutableSeq;
+
     #[deriving(PartialEq, Show)]
     #[repr(uint)]
     enum Foo {
diff --git a/src/libcollections/hash/sip.rs b/src/libcollections/hash/sip.rs
index 7168af89b59..485dc8c5959 100644
--- a/src/libcollections/hash/sip.rs
+++ b/src/libcollections/hash/sip.rs
@@ -281,6 +281,8 @@ mod tests {
     use super::super::{Hash, Writer};
     use super::{SipState, hash, hash_with_keys};
 
+    use MutableSeq;
+
     // Hash just the bytes of the slice, without length prefix
     struct Bytes<'a>(&'a [u8]);
 
diff --git a/src/libcollections/lib.rs b/src/libcollections/lib.rs
index fba89df1bbc..d2d8ad696d7 100644
--- a/src/libcollections/lib.rs
+++ b/src/libcollections/lib.rs
@@ -325,6 +325,30 @@ pub trait MutableSet<T>: Set<T> + Mutable {
     fn remove(&mut self, value: &T) -> bool;
 }
 
+pub trait MutableSeq<T>: Mutable {
+    /// Append an element to the back of a collection.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// let mut vec = vec!(1i, 2);
+    /// vec.push(3);
+    /// assert_eq!(vec, vec!(1, 2, 3));
+    /// ```
+    fn push(&mut self, t: T);
+    /// Remove the last element from a collection and return it, or `None` if it is
+    /// empty.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// let mut vec = vec!(1i, 2, 3);
+    /// assert_eq!(vec.pop(), Some(3));
+    /// assert_eq!(vec, vec!(1, 2));
+    /// ```
+    fn pop(&mut self) -> Option<T>;
+}
+
 /// A double-ended sequence that allows querying, insertion and deletion at both
 /// ends.
 ///
@@ -336,9 +360,9 @@ pub trait MutableSet<T>: Set<T> + Mutable {
 /// use std::collections::{RingBuf, Deque};
 ///
 /// let mut queue = RingBuf::new();
-/// queue.push_back(1i);
-/// queue.push_back(2i);
-/// queue.push_back(3i);
+/// queue.push(1i);
+/// queue.push(2i);
+/// queue.push(3i);
 ///
 /// // Will print 1, 2, 3
 /// while !queue.is_empty() {
@@ -374,17 +398,17 @@ pub trait MutableSet<T>: Set<T> + Mutable {
 /// // Init deque with 1, 2, 3, 4
 /// deque.push_front(2i);
 /// deque.push_front(1i);
-/// deque.push_back(3i);
-/// deque.push_back(4i);
+/// deque.push(3i);
+/// deque.push(4i);
 ///
 /// // Will print (1, 4) and (2, 3)
 /// while !deque.is_empty() {
 ///     let f = deque.pop_front().unwrap();
-///     let b = deque.pop_back().unwrap();
+///     let b = deque.pop().unwrap();
 ///     println!("{}", (f, b));
 /// }
 /// ```
-pub trait Deque<T> : Mutable {
+pub trait Deque<T> : MutableSeq<T> {
     /// Provide a reference to the front element, or `None` if the sequence is
     /// empty.
     ///
@@ -396,8 +420,8 @@ pub trait Deque<T> : Mutable {
     /// let mut d = RingBuf::new();
     /// assert_eq!(d.front(), None);
     ///
-    /// d.push_back(1i);
-    /// d.push_back(2i);
+    /// d.push(1i);
+    /// d.push(2i);
     /// assert_eq!(d.front(), Some(&1i));
     /// ```
     fn front<'a>(&'a self) -> Option<&'a T>;
@@ -413,8 +437,8 @@ pub trait Deque<T> : Mutable {
     /// let mut d = RingBuf::new();
     /// assert_eq!(d.front_mut(), None);
     ///
-    /// d.push_back(1i);
-    /// d.push_back(2i);
+    /// d.push(1i);
+    /// d.push(2i);
     /// match d.front_mut() {
     ///     Some(x) => *x = 9i,
     ///     None => (),
@@ -434,8 +458,8 @@ pub trait Deque<T> : Mutable {
     /// let mut d = DList::new();
     /// assert_eq!(d.back(), None);
     ///
-    /// d.push_back(1i);
-    /// d.push_back(2i);
+    /// d.push(1i);
+    /// d.push(2i);
     /// assert_eq!(d.back(), Some(&2i));
     /// ```
     fn back<'a>(&'a self) -> Option<&'a T>;
@@ -451,8 +475,8 @@ pub trait Deque<T> : Mutable {
     /// let mut d = DList::new();
     /// assert_eq!(d.back(), None);
     ///
-    /// d.push_back(1i);
-    /// d.push_back(2i);
+    /// d.push(1i);
+    /// d.push(2i);
     /// match d.back_mut() {
     ///     Some(x) => *x = 9i,
     ///     None => (),
@@ -479,7 +503,7 @@ pub trait Deque<T> : Mutable {
     ///
     /// # Example
     ///
-    /// ```
+    /// ```ignore
     /// use std::collections::{DList, Deque};
     ///
     /// let mut d = DList::new();
@@ -487,13 +511,14 @@ pub trait Deque<T> : Mutable {
     /// d.push_back(2i);
     /// assert_eq!(d.front(), Some(&1i));
     /// ```
-    fn push_back(&mut self, elt: T);
+    #[deprecated = "use the `push` method"]
+    fn push_back(&mut self, elt: T) { self.push(elt) }
 
     /// Remove the last element and return it, or `None` if the sequence is empty.
     ///
     /// # Example
     ///
-    /// ```
+    /// ```ignore
     /// use std::collections::{RingBuf, Deque};
     ///
     /// let mut d = RingBuf::new();
@@ -504,7 +529,8 @@ pub trait Deque<T> : Mutable {
     /// assert_eq!(d.pop_back(), Some(1i));
     /// assert_eq!(d.pop_back(), None);
     /// ```
-    fn pop_back(&mut self) -> Option<T>;
+    #[deprecated = "use the `pop` method"]
+    fn pop_back(&mut self) -> Option<T> { self.pop() }
 
     /// Remove the first element and return it, or `None` if the sequence is empty.
     ///
@@ -514,8 +540,8 @@ pub trait Deque<T> : Mutable {
     /// use std::collections::{RingBuf, Deque};
     ///
     /// let mut d = RingBuf::new();
-    /// d.push_back(1i);
-    /// d.push_back(2i);
+    /// d.push(1i);
+    /// d.push(2i);
     ///
     /// assert_eq!(d.pop_front(), Some(1i));
     /// assert_eq!(d.pop_front(), Some(2i));
@@ -535,4 +561,8 @@ mod std {
     pub use core::clone;    // deriving(Clone)
     pub use core::cmp;      // deriving(Eq, Ord, etc.)
     pub use hash;           // deriving(Hash)
+
+    pub mod collections {
+        pub use MutableSeq;
+    }
 }
diff --git a/src/libcollections/priority_queue.rs b/src/libcollections/priority_queue.rs
index 9451f2521c8..6e1a3ec1cb6 100644
--- a/src/libcollections/priority_queue.rs
+++ b/src/libcollections/priority_queue.rs
@@ -154,7 +154,7 @@ use core::default::Default;
 use core::mem::{zeroed, replace, swap};
 use core::ptr;
 
-use {Collection, Mutable};
+use {Collection, Mutable, MutableSeq};
 use slice;
 use vec::Vec;
 
@@ -388,6 +388,7 @@ mod tests {
 
     use priority_queue::PriorityQueue;
     use vec::Vec;
+    use MutableSeq;
 
     #[test]
     fn test_iterator() {
diff --git a/src/libcollections/ringbuf.rs b/src/libcollections/ringbuf.rs
index 5e19accdd67..3a4e66b38ae 100644
--- a/src/libcollections/ringbuf.rs
+++ b/src/libcollections/ringbuf.rs
@@ -20,7 +20,7 @@ use core::default::Default;
 use core::fmt;
 use core::iter::RandomAccessIterator;
 
-use {Deque, Collection, Mutable};
+use {Deque, Collection, Mutable, MutableSeq};
 use vec::Vec;
 
 static INITIAL_CAPACITY: uint = 8u; // 2^3
@@ -80,17 +80,6 @@ impl<T> Deque<T> for RingBuf<T> {
         result
     }
 
-    /// Remove and return the last element in the RingBuf, or None if it is empty
-    fn pop_back(&mut self) -> Option<T> {
-        if self.nelts > 0 {
-            self.nelts -= 1;
-            let hi = self.raw_index(self.nelts);
-            self.elts.get_mut(hi).take()
-        } else {
-            None
-        }
-    }
-
     /// Prepend an element to the RingBuf
     fn push_front(&mut self, t: T) {
         if self.nelts == self.elts.len() {
@@ -102,9 +91,10 @@ impl<T> Deque<T> for RingBuf<T> {
         *self.elts.get_mut(self.lo) = Some(t);
         self.nelts += 1u;
     }
+}
 
-    /// Append an element to the RingBuf
-    fn push_back(&mut self, t: T) {
+impl<T> MutableSeq<T> for RingBuf<T> {
+    fn push(&mut self, t: T) {
         if self.nelts == self.elts.len() {
             grow(self.nelts, &mut self.lo, &mut self.elts);
         }
@@ -112,6 +102,15 @@ impl<T> Deque<T> for RingBuf<T> {
         *self.elts.get_mut(hi) = Some(t);
         self.nelts += 1u;
     }
+    fn pop(&mut self) -> Option<T> {
+        if self.nelts > 0 {
+            self.nelts -= 1;
+            let hi = self.raw_index(self.nelts);
+            self.elts.get_mut(hi).take()
+        } else {
+            None
+        }
+    }
 }
 
 impl<T> Default for RingBuf<T> {
@@ -423,7 +422,7 @@ mod tests {
     use test::Bencher;
     use test;
 
-    use {Deque, Mutable};
+    use {Deque, Mutable, MutableSeq};
     use super::RingBuf;
     use vec::Vec;
 
diff --git a/src/libcollections/slice.rs b/src/libcollections/slice.rs
index 6c3c8437e25..64062dc0ccb 100644
--- a/src/libcollections/slice.rs
+++ b/src/libcollections/slice.rs
@@ -107,7 +107,7 @@ use core::mem;
 use core::ptr;
 use core::iter::{range_step, MultiplicativeIterator};
 
-use Collection;
+use {Collection, MutableSeq};
 use vec::Vec;
 
 pub use core::slice::{ref_slice, mut_ref_slice, Splits, Windows};
@@ -731,7 +731,7 @@ mod tests {
     use std::rt;
     use slice::*;
 
-    use Mutable;
+    use {Mutable, MutableSeq};
     use vec::Vec;
 
     fn square(n: uint) -> uint { n * n }
@@ -2133,6 +2133,7 @@ mod bench {
     use test::Bencher;
 
     use vec::Vec;
+    use MutableSeq;
 
     #[bench]
     fn iterator(b: &mut Bencher) {
diff --git a/src/libcollections/smallintmap.rs b/src/libcollections/smallintmap.rs
index ca62b1235d5..eb97215c721 100644
--- a/src/libcollections/smallintmap.rs
+++ b/src/libcollections/smallintmap.rs
@@ -22,7 +22,7 @@ use core::fmt;
 use core::iter::{Enumerate, FilterMap};
 use core::mem::replace;
 
-use {Collection, Mutable, Map, MutableMap};
+use {Collection, Mutable, Map, MutableMap, MutableSeq};
 use {vec, slice};
 use vec::Vec;
 
diff --git a/src/libcollections/str.rs b/src/libcollections/str.rs
index 48bc492e25c..c0e903677de 100644
--- a/src/libcollections/str.rs
+++ b/src/libcollections/str.rs
@@ -77,7 +77,7 @@ use core::cmp;
 use core::iter::AdditiveIterator;
 use core::mem;
 
-use Collection;
+use {Collection, MutableSeq};
 use hash;
 use string::String;
 use unicode;
@@ -562,6 +562,8 @@ pub mod raw {
     use string::String;
     use vec::Vec;
 
+    use MutableSeq;
+
     pub use core::str::raw::{from_utf8, c_str_to_static_slice, slice_bytes};
     pub use core::str::raw::{slice_unchecked};
 
@@ -818,7 +820,7 @@ mod tests {
     use std::option::{Some, None};
     use std::ptr::RawPtr;
     use std::iter::{Iterator, DoubleEndedIterator};
-    use Collection;
+    use {Collection, MutableSeq};
 
     use super::*;
     use std::slice::{Vector, ImmutableVector};
diff --git a/src/libcollections/string.rs b/src/libcollections/string.rs
index b19bef68590..d58dfdd10d1 100644
--- a/src/libcollections/string.rs
+++ b/src/libcollections/string.rs
@@ -20,7 +20,7 @@ use core::mem;
 use core::ptr;
 use core::raw::Slice;
 
-use {Collection, Mutable};
+use {Collection, Mutable, MutableSeq};
 use hash;
 use str;
 use str::{CharRange, StrAllocating, MaybeOwned, Owned, Slice};
@@ -575,7 +575,7 @@ mod tests {
     use std::prelude::*;
     use test::Bencher;
 
-    use Mutable;
+    use {Mutable, MutableSeq};
     use str;
     use str::{Str, StrSlice, Owned, Slice};
     use super::String;
diff --git a/src/libcollections/treemap.rs b/src/libcollections/treemap.rs
index 8c24326c840..5658d07a1d1 100644
--- a/src/libcollections/treemap.rs
+++ b/src/libcollections/treemap.rs
@@ -40,7 +40,7 @@ use core::mem::{replace, swap};
 use core::ptr;
 use std::hash::{Writer, Hash};
 
-use {Collection, Mutable, Set, MutableSet, MutableMap, Map};
+use {Collection, Mutable, Set, MutableSet, MutableMap, Map, MutableSeq};
 use vec::Vec;
 
 // This is implemented as an AA tree, which is a simplified variation of
@@ -1127,7 +1127,7 @@ mod test_treemap {
     use std::rand::Rng;
     use std::rand;
 
-    use {Map, MutableMap, Mutable};
+    use {Map, MutableMap, Mutable, MutableSeq};
     use super::{TreeMap, TreeNode};
 
     #[test]
@@ -1659,7 +1659,7 @@ mod test_set {
     use std::prelude::*;
     use std::hash;
 
-    use {Set, MutableSet, Mutable, MutableMap};
+    use {Set, MutableSet, Mutable, MutableMap, MutableSeq};
     use super::{TreeMap, TreeSet};
 
     #[test]
diff --git a/src/libcollections/trie.rs b/src/libcollections/trie.rs
index 424cda92c12..5a00c4b85da 100644
--- a/src/libcollections/trie.rs
+++ b/src/libcollections/trie.rs
@@ -682,7 +682,7 @@ mod test_map {
     use std::uint;
     use std::hash;
 
-    use {MutableMap, Map};
+    use {MutableMap, Map, MutableSeq};
     use super::{TrieMap, TrieNode, Internal, External, Nothing};
 
     fn check_integrity<T>(trie: &TrieNode<T>) {
@@ -1105,7 +1105,7 @@ mod test_set {
     use std::prelude::*;
     use std::uint;
 
-    use {MutableSet, Set};
+    use {MutableSet, Set, MutableSeq};
     use super::TrieSet;
 
     #[test]
diff --git a/src/libcollections/vec.rs b/src/libcollections/vec.rs
index 0002867495c..dcee92f6dbc 100644
--- a/src/libcollections/vec.rs
+++ b/src/libcollections/vec.rs
@@ -23,7 +23,7 @@ use core::num;
 use core::ptr;
 use core::uint;
 
-use {Collection, Mutable};
+use {Collection, Mutable, MutableSeq};
 use slice::{MutableOrdVector, MutableVectorAllocating, CloneableVector};
 use slice::{Items, MutItems};
 
@@ -666,67 +666,6 @@ impl<T> Vec<T> {
         }
     }
 
-    /// Remove the last element from a vector and return it, or `None` if it is
-    /// empty.
-    ///
-    /// # Example
-    ///
-    /// ```
-    /// let mut vec = vec![1i, 2, 3];
-    /// assert_eq!(vec.pop(), Some(3));
-    /// assert_eq!(vec, vec![1, 2]);
-    /// ```
-    #[inline]
-    pub fn pop(&mut self) -> Option<T> {
-        if self.len == 0 {
-            None
-        } else {
-            unsafe {
-                self.len -= 1;
-                Some(ptr::read(self.as_slice().unsafe_ref(self.len())))
-            }
-        }
-    }
-
-    /// Append an element to a vector.
-    ///
-    /// # Failure
-    ///
-    /// Fails if the number of elements in the vector overflows a `uint`.
-    ///
-    /// # Example
-    ///
-    /// ```
-    /// let mut vec = vec![1i, 2];
-    /// vec.push(3);
-    /// assert_eq!(vec, vec![1, 2, 3]);
-    /// ```
-    #[inline]
-    pub fn push(&mut self, value: T) {
-        if mem::size_of::<T>() == 0 {
-            // zero-size types consume no memory, so we can't rely on the address space running out
-            self.len = self.len.checked_add(&1).expect("length overflow");
-            unsafe { mem::forget(value); }
-            return
-        }
-        if self.len == self.cap {
-            let old_size = self.cap * mem::size_of::<T>();
-            let size = max(old_size, 2 * mem::size_of::<T>()) * 2;
-            if old_size > size { fail!("capacity overflow") }
-            unsafe {
-                self.ptr = alloc_or_realloc(self.ptr, size,
-                                            self.cap * mem::size_of::<T>());
-            }
-            self.cap = max(self.cap, 2) * 2;
-        }
-
-        unsafe {
-            let end = (self.ptr as *const T).offset(self.len as int) as *mut T;
-            ptr::write(&mut *end, value);
-            self.len += 1;
-        }
-    }
-
     /// Appends one element to the vector provided. The vector itself is then
     /// returned for use again.
     ///
@@ -1042,12 +981,13 @@ impl<T> Vec<T> {
     ///
     /// # Example
     ///
-    /// ```
+    /// ```ignore
     /// let mut vec = vec![1i, 2, 3];
     /// vec.unshift(4);
     /// assert_eq!(vec, vec![4, 1, 2, 3]);
     /// ```
     #[inline]
+    #[deprecated = "use insert(0, ...)"]
     pub fn unshift(&mut self, element: T) {
         self.insert(0, element)
     }
@@ -1068,6 +1008,7 @@ impl<T> Vec<T> {
     /// assert_eq!(vec, vec![2, 3]);
     /// ```
     #[inline]
+    #[deprecated = "use remove(0)"]
     pub fn shift(&mut self) -> Option<T> {
         self.remove(0)
     }
@@ -1615,6 +1556,60 @@ impl<T:fmt::Show> fmt::Show for Vec<T> {
     }
 }
 
+impl<T> MutableSeq<T> for Vec<T> {
+    /// Append an element to the back of a collection.
+    ///
+    /// # Failure
+    ///
+    /// Fails if the number of elements in the vector overflows a `uint`.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// let mut vec = vec!(1i, 2);
+    /// vec.push(3);
+    /// assert_eq!(vec, vec!(1, 2, 3));
+    /// ```
+    #[inline]
+    fn push(&mut self, value: T) {
+        if mem::size_of::<T>() == 0 {
+            // zero-size types consume no memory, so we can't rely on the address space running out
+            self.len = self.len.checked_add(&1).expect("length overflow");
+            unsafe { mem::forget(value); }
+            return
+        }
+        if self.len == self.cap {
+            let old_size = self.cap * mem::size_of::<T>();
+            let size = max(old_size, 2 * mem::size_of::<T>()) * 2;
+            if old_size > size { fail!("capacity overflow") }
+            unsafe {
+                self.ptr = alloc_or_realloc(self.ptr, size,
+                                            self.cap * mem::size_of::<T>());
+            }
+            self.cap = max(self.cap, 2) * 2;
+        }
+
+        unsafe {
+            let end = (self.ptr as *const T).offset(self.len as int) as *mut T;
+            ptr::write(&mut *end, value);
+            self.len += 1;
+        }
+    }
+
+    #[inline]
+    fn pop(&mut self) -> Option<T> {
+        if self.len == 0 {
+            None
+        } else {
+            unsafe {
+                self.len -= 1;
+                Some(ptr::read(self.as_slice().unsafe_ref(self.len())))
+            }
+        }
+    }
+
+}
+
 /// An iterator that moves out of a vector.
 pub struct MoveItems<T> {
     allocation: *mut T, // the block of memory allocated for the vector
@@ -1704,6 +1699,8 @@ mod tests {
     use test::Bencher;
     use super::{unzip, raw, Vec};
 
+    use MutableSeq;
+
     #[test]
     fn test_small_vec_struct() {
         assert!(size_of::<Vec<u8>>() == size_of::<uint>() * 3);
diff --git a/src/libregex/parse.rs b/src/libregex/parse.rs
index d53fed7aa80..a1fd62cecbe 100644
--- a/src/libregex/parse.rs
+++ b/src/libregex/parse.rs
@@ -998,7 +998,7 @@ fn concat_flatten(x: Ast, y: Ast) -> Ast {
     match (x, y) {
         (Cat(mut xs), Cat(ys)) => { xs.push_all_move(ys); Cat(xs) }
         (Cat(mut xs), ast) => { xs.push(ast); Cat(xs) }
-        (ast, Cat(mut xs)) => { xs.unshift(ast); Cat(xs) }
+        (ast, Cat(mut xs)) => { xs.insert(0, ast); Cat(xs) }
         (ast1, ast2) => Cat(vec!(ast1, ast2)),
     }
 }
diff --git a/src/librustc/lib/llvmdeps.rs b/src/librustc/lib/llvmdeps.rs
deleted file mode 100644
index 05e5e585a63..00000000000
--- a/src/librustc/lib/llvmdeps.rs
+++ /dev/null
@@ -1,64 +0,0 @@
-// Copyright 2013 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.
-
-// WARNING: THIS IS A GENERATED FILE, DO NOT MODIFY
-//          take a look at src/etc/mklldeps.py if you're interested
-
-#[cfg(target_arch = "x86_64", target_os = "linux")]
-#[link(name = "LLVMInstrumentation", kind = "static")]
-#[link(name = "LLVMInterpreter", kind = "static")]
-#[link(name = "LLVMMCJIT", kind = "static")]
-#[link(name = "LLVMRuntimeDyld", kind = "static")]
-#[link(name = "LLVMJIT", kind = "static")]
-#[link(name = "LLVMExecutionEngine", kind = "static")]
-#[link(name = "LLVMAsmParser", kind = "static")]
-#[link(name = "LLVMLinker", kind = "static")]
-#[link(name = "LLVMBitWriter", kind = "static")]
-#[link(name = "LLVMipo", kind = "static")]
-#[link(name = "LLVMVectorize", kind = "static")]
-#[link(name = "LLVMMipsDisassembler", kind = "static")]
-#[link(name = "LLVMMipsCodeGen", kind = "static")]
-#[link(name = "LLVMMipsAsmParser", kind = "static")]
-#[link(name = "LLVMMipsDesc", kind = "static")]
-#[link(name = "LLVMMipsInfo", kind = "static")]
-#[link(name = "LLVMMipsAsmPrinter", kind = "static")]
-#[link(name = "LLVMARMDisassembler", kind = "static")]
-#[link(name = "LLVMARMCodeGen", kind = "static")]
-#[link(name = "LLVMARMAsmParser", kind = "static")]
-#[link(name = "LLVMARMDesc", kind = "static")]
-#[link(name = "LLVMARMInfo", kind = "static")]
-#[link(name = "LLVMARMAsmPrinter", kind = "static")]
-#[link(name = "LLVMX86Disassembler", kind = "static")]
-#[link(name = "LLVMX86AsmParser", kind = "static")]
-#[link(name = "LLVMX86CodeGen", kind = "static")]
-#[link(name = "LLVMSelectionDAG", kind = "static")]
-#[link(name = "LLVMAsmPrinter", kind = "static")]
-#[link(name = "LLVMMCParser", kind = "static")]
-#[link(name = "LLVMCodeGen", kind = "static")]
-#[link(name = "LLVMScalarOpts", kind = "static")]
-#[link(name = "LLVMInstCombine", kind = "static")]
-#[link(name = "LLVMTransformUtils", kind = "static")]
-#[link(name = "LLVMipa", kind = "static")]
-#[link(name = "LLVMAnalysis", kind = "static")]
-#[link(name = "LLVMTarget", kind = "static")]
-#[link(name = "LLVMX86Desc", kind = "static")]
-#[link(name = "LLVMX86Info", kind = "static")]
-#[link(name = "LLVMX86AsmPrinter", kind = "static")]
-#[link(name = "LLVMMC", kind = "static")]
-#[link(name = "LLVMObject", kind = "static")]
-#[link(name = "LLVMBitReader", kind = "static")]
-#[link(name = "LLVMCore", kind = "static")]
-#[link(name = "LLVMX86Utils", kind = "static")]
-#[link(name = "LLVMSupport", kind = "static")]
-#[link(name = "pthread")]
-#[link(name = "dl")]
-#[link(name = "m")]
-#[link(name = "stdc++")]
-extern {}
diff --git a/src/librustdoc/lib.rs b/src/librustdoc/lib.rs
index 76b3a012dbf..b992a11bc64 100644
--- a/src/librustdoc/lib.rs
+++ b/src/librustdoc/lib.rs
@@ -361,7 +361,7 @@ fn rust_input(cratefile: &str, externs: core::Externs, matches: &getopts::Matche
     }
     if default_passes {
         for name in DEFAULT_PASSES.iter().rev() {
-            passes.unshift(name.to_string());
+            passes.insert(0, name.to_string());
         }
     }
 
diff --git a/src/librustdoc/markdown.rs b/src/librustdoc/markdown.rs
index 47009c1f2cc..416018cadd2 100644
--- a/src/librustdoc/markdown.rs
+++ b/src/librustdoc/markdown.rs
@@ -136,7 +136,7 @@ pub fn test(input: &str, libs: HashSet<Path>, externs: core::Externs,
 
     let mut collector = Collector::new(input.to_string(), libs, externs, true);
     find_testable_code(input_str.as_slice(), &mut collector);
-    test_args.unshift("rustdoctest".to_string());
+    test_args.insert(0, "rustdoctest".to_string());
     testing::test_main(test_args.as_slice(), collector.tests);
     0
 }
diff --git a/src/librustdoc/test.rs b/src/librustdoc/test.rs
index 2ed35469dfa..aef6af1677a 100644
--- a/src/librustdoc/test.rs
+++ b/src/librustdoc/test.rs
@@ -97,7 +97,7 @@ pub fn run(input: &str,
                                        false);
     collector.fold_crate(krate);
 
-    test_args.unshift("rustdoctest".to_string());
+    test_args.insert(0, "rustdoctest".to_string());
 
     testing::test_main(test_args.as_slice(),
                        collector.tests.move_iter().collect());
diff --git a/src/librustrt/at_exit_imp.rs b/src/librustrt/at_exit_imp.rs
index 1faf492e498..c9188e81975 100644
--- a/src/librustrt/at_exit_imp.rs
+++ b/src/librustrt/at_exit_imp.rs
@@ -15,6 +15,7 @@
 use core::prelude::*;
 
 use alloc::boxed::Box;
+use collections::MutableSeq;
 use collections::vec::Vec;
 use core::atomics;
 use core::mem;
diff --git a/src/librustrt/local_data.rs b/src/librustrt/local_data.rs
index 7434951d3ee..b7366f440d0 100644
--- a/src/librustrt/local_data.rs
+++ b/src/librustrt/local_data.rs
@@ -41,6 +41,7 @@ assert_eq!(*key_vector.get().unwrap(), vec![4]);
 use core::prelude::*;
 
 use alloc::boxed::Box;
+use collections::MutableSeq;
 use collections::vec::Vec;
 use core::kinds::marker;
 use core::mem;
diff --git a/src/librustuv/access.rs b/src/librustuv/access.rs
index 63d9aa7ead0..bcbcde3fba5 100644
--- a/src/librustuv/access.rs
+++ b/src/librustuv/access.rs
@@ -114,7 +114,7 @@ impl<'a> Drop for Guard<'a> {
             mem::transmute(self.access.inner.get())
         };
 
-        match inner.queue.shift() {
+        match inner.queue.remove(0) {
             // Here we have found a task that was waiting for access, and we
             // current have the "access lock" we need to relinquish access to
             // this sleeping task.
diff --git a/src/libserialize/collection_impls.rs b/src/libserialize/collection_impls.rs
index b74d20ffc54..79166935a5e 100644
--- a/src/libserialize/collection_impls.rs
+++ b/src/libserialize/collection_impls.rs
@@ -15,7 +15,7 @@ use std::default::Default;
 use std::hash::{Hash, Hasher};
 
 use {Decodable, Encodable, Decoder, Encoder};
-use std::collections::{DList, RingBuf, TreeMap, TreeSet, Deque, HashMap, HashSet,
+use std::collections::{DList, RingBuf, TreeMap, TreeSet, HashMap, HashSet,
                        TrieMap, TrieSet};
 use std::collections::enum_set::{EnumSet, CLike};
 
@@ -39,7 +39,7 @@ impl<E, D:Decoder<E>,T:Decodable<D, E>> Decodable<D, E> for DList<T> {
         d.read_seq(|d, len| {
             let mut list = DList::new();
             for i in range(0u, len) {
-                list.push_back(try!(d.read_seq_elt(i, |d| Decodable::decode(d))));
+                list.push(try!(d.read_seq_elt(i, |d| Decodable::decode(d))));
             }
             Ok(list)
         })
@@ -66,7 +66,7 @@ impl<E, D:Decoder<E>,T:Decodable<D, E>> Decodable<D, E> for RingBuf<T> {
         d.read_seq(|d, len| {
             let mut deque: RingBuf<T> = RingBuf::new();
             for i in range(0u, len) {
-                deque.push_back(try!(d.read_seq_elt(i, |d| Decodable::decode(d))));
+                deque.push(try!(d.read_seq_elt(i, |d| Decodable::decode(d))));
             }
             Ok(deque)
         })
diff --git a/src/libstd/collections/hashmap.rs b/src/libstd/collections/hashmap.rs
index a05fad3705d..922858e963c 100644
--- a/src/libstd/collections/hashmap.rs
+++ b/src/libstd/collections/hashmap.rs
@@ -1291,7 +1291,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     ///         // new value based on the first letter of the key.
     ///         |key, already, new| {
     ///             if key.as_slice().starts_with("z") {
-    ///                 already.unshift(new);
+    ///                 already.insert(0, new);
     ///             } else {
     ///                 already.push(new);
     ///             }
diff --git a/src/libstd/collections/mod.rs b/src/libstd/collections/mod.rs
index ccef1c0fd2a..d98d490a84b 100644
--- a/src/libstd/collections/mod.rs
+++ b/src/libstd/collections/mod.rs
@@ -15,7 +15,7 @@
 #![experimental]
 
 pub use core_collections::{Collection, Mutable, Map, MutableMap};
-pub use core_collections::{Set, MutableSet, Deque};
+pub use core_collections::{Set, MutableSet, Deque, MutableSeq};
 pub use core_collections::{Bitv, BitvSet, BTree, DList, EnumSet};
 pub use core_collections::{PriorityQueue, RingBuf, SmallIntMap};
 pub use core_collections::{TreeMap, TreeSet, TrieMap, TrieSet};
diff --git a/src/libstd/dynamic_lib.rs b/src/libstd/dynamic_lib.rs
index 86283f03381..5980245fa79 100644
--- a/src/libstd/dynamic_lib.rs
+++ b/src/libstd/dynamic_lib.rs
@@ -20,6 +20,7 @@ A simple wrapper over the platform's dynamic library facilities
 #![allow(missing_doc)]
 
 use clone::Clone;
+use collections::MutableSeq;
 use c_str::ToCStr;
 use iter::Iterator;
 use mem;
diff --git a/src/libstd/io/extensions.rs b/src/libstd/io/extensions.rs
index ca3eee01575..5215aec5dfb 100644
--- a/src/libstd/io/extensions.rs
+++ b/src/libstd/io/extensions.rs
@@ -15,7 +15,7 @@
 // FIXME: Not sure how this should be structured
 // FIXME: Iteration should probably be considered separately
 
-use collections::Collection;
+use collections::{Collection, MutableSeq};
 use iter::Iterator;
 use option::{Option, Some, None};
 use result::{Ok, Err};
diff --git a/src/libstd/io/fs.rs b/src/libstd/io/fs.rs
index afd88ee0ed9..c7dec49a76d 100644
--- a/src/libstd/io/fs.rs
+++ b/src/libstd/io/fs.rs
@@ -53,7 +53,7 @@ fs::unlink(&path);
 
 use c_str::ToCStr;
 use clone::Clone;
-use collections::Collection;
+use collections::{Collection, MutableSeq};
 use io::standard_error;
 use io::{FilePermission, Write, UnstableFileStat, Open, FileAccess, FileMode};
 use io::{IoResult, IoError, FileStat, SeekStyle, Seek, Writer, Reader};
diff --git a/src/libstd/io/net/tcp.rs b/src/libstd/io/net/tcp.rs
index 642654ba6ed..cb754135bc1 100644
--- a/src/libstd/io/net/tcp.rs
+++ b/src/libstd/io/net/tcp.rs
@@ -18,6 +18,7 @@
 //! listener (socket server) implements the `Listener` and `Acceptor` traits.
 
 use clone::Clone;
+use collections::MutableSeq;
 use io::IoResult;
 use iter::Iterator;
 use slice::ImmutableVector;
diff --git a/src/libstd/io/signal.rs b/src/libstd/io/signal.rs
index d46f437cddd..c126866e715 100644
--- a/src/libstd/io/signal.rs
+++ b/src/libstd/io/signal.rs
@@ -20,6 +20,7 @@ definitions for a number of signals.
 */
 
 use clone::Clone;
+use collections::MutableSeq;
 use comm::{Sender, Receiver, channel};
 use io;
 use iter::Iterator;
diff --git a/src/libstd/lib.rs b/src/libstd/lib.rs
index e14092bc8dc..125c3fdf5d9 100644
--- a/src/libstd/lib.rs
+++ b/src/libstd/lib.rs
@@ -288,4 +288,6 @@ mod std {
     #[cfg(test)] pub use os = realstd::os;
     // The test runner requires std::slice::Vector, so re-export std::slice just for it.
     #[cfg(test)] pub use slice;
+
+    pub use collections; // vec!() uses MutableSeq
 }
diff --git a/src/libstd/num/strconv.rs b/src/libstd/num/strconv.rs
index cc30acf064b..c8528e752e8 100644
--- a/src/libstd/num/strconv.rs
+++ b/src/libstd/num/strconv.rs
@@ -14,7 +14,7 @@
 
 use char;
 use clone::Clone;
-use collections::Collection;
+use collections::{Collection, MutableSeq};
 use num::{NumCast, Zero, One, cast, Int};
 use num::{Float, FPNaN, FPInfinite, ToPrimitive};
 use num;
diff --git a/src/libstd/os.rs b/src/libstd/os.rs
index 96d3b3e3e6a..f71f1d22d00 100644
--- a/src/libstd/os.rs
+++ b/src/libstd/os.rs
@@ -32,7 +32,7 @@
 #![allow(non_snake_case_functions)]
 
 use clone::Clone;
-use collections::Collection;
+use collections::{Collection, MutableSeq};
 use fmt;
 use io::{IoResult, IoError};
 use iter::Iterator;
diff --git a/src/libstd/path/mod.rs b/src/libstd/path/mod.rs
index ececfab5f74..0c93f8e6de9 100644
--- a/src/libstd/path/mod.rs
+++ b/src/libstd/path/mod.rs
@@ -65,7 +65,7 @@ println!("path exists: {}", path.exists());
 
 #![experimental]
 
-use collections::Collection;
+use collections::{Collection, MutableSeq};
 use c_str::CString;
 use clone::Clone;
 use fmt;
diff --git a/src/libstd/path/posix.rs b/src/libstd/path/posix.rs
index 007686aa05c..877ca2c7e01 100644
--- a/src/libstd/path/posix.rs
+++ b/src/libstd/path/posix.rs
@@ -13,7 +13,7 @@
 use c_str::{CString, ToCStr};
 use clone::Clone;
 use cmp::{PartialEq, Eq, PartialOrd, Ord, Ordering};
-use collections::Collection;
+use collections::{Collection, MutableSeq};
 use from_str::FromStr;
 use hash;
 use io::Writer;
diff --git a/src/libstd/path/windows.rs b/src/libstd/path/windows.rs
index 4a6ed561233..d9b802b38fd 100644
--- a/src/libstd/path/windows.rs
+++ b/src/libstd/path/windows.rs
@@ -16,7 +16,7 @@ use ascii::AsciiCast;
 use c_str::{CString, ToCStr};
 use clone::Clone;
 use cmp::{PartialEq, Eq, PartialOrd, Ord, Ordering};
-use collections::Collection;
+use collections::{Collection, MutableSeq};
 use from_str::FromStr;
 use hash;
 use io::Writer;
diff --git a/src/libstd/prelude.rs b/src/libstd/prelude.rs
index 0fa223305a6..0ce7497cf30 100644
--- a/src/libstd/prelude.rs
+++ b/src/libstd/prelude.rs
@@ -63,7 +63,7 @@
 #[doc(no_inline)] pub use clone::Clone;
 #[doc(no_inline)] pub use cmp::{PartialEq, PartialOrd, Eq, Ord};
 #[doc(no_inline)] pub use cmp::{Ordering, Less, Equal, Greater, Equiv};
-#[doc(no_inline)] pub use collections::{Collection, Mutable, Map, MutableMap};
+#[doc(no_inline)] pub use collections::{Collection, Mutable, Map, MutableMap, MutableSeq};
 #[doc(no_inline)] pub use collections::{Set, MutableSet};
 #[doc(no_inline)] pub use iter::{FromIterator, Extendable, ExactSize};
 #[doc(no_inline)] pub use iter::{Iterator, DoubleEndedIterator};
diff --git a/src/libsync/deque.rs b/src/libsync/deque.rs
index 913a58010d4..c541cc02774 100644
--- a/src/libsync/deque.rs
+++ b/src/libsync/deque.rs
@@ -55,7 +55,7 @@ use core::prelude::*;
 use alloc::arc::Arc;
 use alloc::heap::{allocate, deallocate};
 use alloc::boxed::Box;
-use collections::Vec;
+use collections::{Vec, MutableSeq};
 use core::kinds::marker;
 use core::mem::{forget, min_align_of, size_of, transmute};
 use core::ptr;
diff --git a/src/libsync/raw.rs b/src/libsync/raw.rs
index d056566bb9a..1bdf24ea7dd 100644
--- a/src/libsync/raw.rs
+++ b/src/libsync/raw.rs
@@ -22,7 +22,7 @@ use core::finally::Finally;
 use core::kinds::marker;
 use core::mem;
 use core::ty::Unsafe;
-use collections::Vec;
+use collections::{Vec, MutableSeq};
 
 use mutex;
 use comm::{Receiver, Sender, channel};
diff --git a/src/libterm/terminfo/parm.rs b/src/libterm/terminfo/parm.rs
index db76e78d161..1410f225a29 100644
--- a/src/libterm/terminfo/parm.rs
+++ b/src/libterm/terminfo/parm.rs
@@ -514,12 +514,12 @@ fn format(val: Param, op: FormatOp, flags: Flags) -> Result<Vec<u8> ,String> {
                 FormatDigit => {
                     if flags.space && !(s[0] == '-' as u8 ||
                                         s[0] == '+' as u8) {
-                        s.unshift(' ' as u8);
+                        s.insert(0, ' ' as u8);
                     }
                 }
                 FormatOctal => {
                     if flags.alternate && s[0] != '0' as u8 {
-                        s.unshift('0' as u8);
+                        s.insert(0, '0' as u8);
                     }
                 }
                 FormatHex => {