Change implementation of syntax::util::SmallVector to use data_structures::SmallVec.

14 files changed, 572 insertions, 285 deletions

diff --git a/src/Cargo.lock b/src/Cargo.lock
index d3517175d4c..ee38a043b12 100644
--- a/src/Cargo.lock
+++ b/src/Cargo.lock
@@ -621,6 +621,7 @@ version = "0.0.0"
 dependencies = [
  "log 0.0.0",
  "rustc_bitflags 0.0.0",
+ "rustc_data_structures 0.0.0",
  "rustc_errors 0.0.0",
  "serialize 0.0.0",
  "syntax_pos 0.0.0",
diff --git a/src/librustc/infer/combine.rs b/src/librustc/infer/combine.rs
index fda08eba021..641273d2b76 100644
--- a/src/librustc/infer/combine.rs
+++ b/src/librustc/infer/combine.rs
@@ -184,7 +184,7 @@ impl<'infcx, 'gcx, 'tcx> CombineFields<'infcx, 'gcx, 'tcx> {
     {
         // We use SmallVector here instead of Vec because this code is hot and
         // it's rare that the stack length exceeds 1.
-        let mut stack = SmallVector::zero();
+        let mut stack = SmallVector::new();
         stack.push((a_ty, dir, b_vid));
         loop {
             // For each turn of the loop, we extract a tuple
diff --git a/src/librustc_data_structures/accumulate_vec.rs b/src/librustc_data_structures/accumulate_vec.rs
index 3894db40277..937cb3f6007 100644
--- a/src/librustc_data_structures/accumulate_vec.rs
+++ b/src/librustc_data_structures/accumulate_vec.rs
@@ -11,22 +11,68 @@
 //! A vector type intended to be used for collecting from iterators onto the stack.
 //!
 //! Space for up to N elements is provided on the stack.  If more elements are collected, Vec is
-//! used to store the values on the heap. This type does not support re-allocating onto the heap,
-//! and there is no way to push more elements onto the existing storage.
+//! used to store the values on the heap.
 //!
 //! The N above is determined by Array's implementor, by way of an associatated constant.
 
-use std::ops::Deref;
-use std::iter::{IntoIterator, FromIterator};
+use std::ops::{Deref, DerefMut};
+use std::iter::{self, IntoIterator, FromIterator};
+use std::slice;
+use std::vec;
 
-use array_vec::{Array, ArrayVec};
+use rustc_serialize::{Encodable, Encoder, Decodable, Decoder};
 
-#[derive(Debug)]
+use array_vec::{self, Array, ArrayVec};
+
+#[derive(PartialEq, Eq, Hash, Debug)]
 pub enum AccumulateVec<A: Array> {
     Array(ArrayVec<A>),
     Heap(Vec<A::Element>)
 }
 
+impl<A> Clone for AccumulateVec<A>
+    where A: Array,
+          A::Element: Clone {
+    fn clone(&self) -> Self {
+        match *self {
+            AccumulateVec::Array(ref arr) => AccumulateVec::Array(arr.clone()),
+            AccumulateVec::Heap(ref vec) => AccumulateVec::Heap(vec.clone()),
+        }
+    }
+}
+
+impl<A: Array> AccumulateVec<A> {
+    pub fn new() -> AccumulateVec<A> {
+        AccumulateVec::Array(ArrayVec::new())
+    }
+
+    pub fn one(el: A::Element) -> Self {
+        iter::once(el).collect()
+    }
+
+    pub fn many<I: IntoIterator<Item=A::Element>>(iter: I) -> Self {
+        iter.into_iter().collect()
+    }
+
+    pub fn len(&self) -> usize {
+        match *self {
+            AccumulateVec::Array(ref arr) => arr.len(),
+            AccumulateVec::Heap(ref vec) => vec.len(),
+        }
+    }
+
+    pub fn is_empty(&self) -> bool {
+        self.len() == 0
+    }
+
+    pub fn pop(&mut self) -> Option<A::Element> {
+        match *self {
+            AccumulateVec::Array(ref mut arr) => arr.pop(),
+            AccumulateVec::Heap(ref mut vec) => vec.pop(),
+        }
+    }
+}
+
 impl<A: Array> Deref for AccumulateVec<A> {
     type Target = [A::Element];
     fn deref(&self) -> &Self::Target {
@@ -37,6 +83,15 @@ impl<A: Array> Deref for AccumulateVec<A> {
     }
 }
 
+impl<A: Array> DerefMut for AccumulateVec<A> {
+    fn deref_mut(&mut self) -> &mut [A::Element] {
+        match *self {
+            AccumulateVec::Array(ref mut v) => &mut v[..],
+            AccumulateVec::Heap(ref mut v) => &mut v[..],
+        }
+    }
+}
+
 impl<A: Array> FromIterator<A::Element> for AccumulateVec<A> {
     fn from_iter<I>(iter: I) -> AccumulateVec<A> where I: IntoIterator<Item=A::Element> {
         let iter = iter.into_iter();
@@ -50,3 +105,94 @@ impl<A: Array> FromIterator<A::Element> for AccumulateVec<A> {
     }
 }
 
+pub struct IntoIter<A: Array> {
+    repr: IntoIterRepr<A>,
+}
+
+enum IntoIterRepr<A: Array> {
+    Array(array_vec::Iter<A>),
+    Heap(vec::IntoIter<A::Element>),
+}
+
+impl<A: Array> Iterator for IntoIter<A> {
+    type Item = A::Element;
+
+    fn next(&mut self) -> Option<A::Element> {
+        match self.repr {
+            IntoIterRepr::Array(ref mut arr) => arr.next(),
+            IntoIterRepr::Heap(ref mut iter) => iter.next(),
+        }
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        match self.repr {
+            IntoIterRepr::Array(ref iter) => iter.size_hint(),
+            IntoIterRepr::Heap(ref iter) => iter.size_hint(),
+        }
+    }
+}
+
+impl<A: Array> IntoIterator for AccumulateVec<A> {
+    type Item = A::Element;
+    type IntoIter = IntoIter<A>;
+    fn into_iter(self) -> Self::IntoIter {
+        IntoIter {
+            repr: match self {
+                AccumulateVec::Array(arr) => IntoIterRepr::Array(arr.into_iter()),
+                AccumulateVec::Heap(vec) => IntoIterRepr::Heap(vec.into_iter()),
+            }
+        }
+    }
+}
+
+impl<'a, A: Array> IntoIterator for &'a AccumulateVec<A> {
+    type Item = &'a A::Element;
+    type IntoIter = slice::Iter<'a, A::Element>;
+    fn into_iter(self) -> Self::IntoIter {
+        self.iter()
+    }
+}
+
+impl<'a, A: Array> IntoIterator for &'a mut AccumulateVec<A> {
+    type Item = &'a mut A::Element;
+    type IntoIter = slice::IterMut<'a, A::Element>;
+    fn into_iter(self) -> Self::IntoIter {
+        self.iter_mut()
+    }
+}
+
+impl<A: Array> From<Vec<A::Element>> for AccumulateVec<A> {
+    fn from(v: Vec<A::Element>) -> AccumulateVec<A> {
+        AccumulateVec::many(v)
+    }
+}
+
+impl<A: Array> Default for AccumulateVec<A> {
+    fn default() -> AccumulateVec<A> {
+        AccumulateVec::new()
+    }
+}
+
+impl<A> Encodable for AccumulateVec<A>
+    where A: Array,
+          A::Element: Encodable {
+    fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
+        s.emit_seq(self.len(), |s| {
+            for (i, e) in self.iter().enumerate() {
+                try!(s.emit_seq_elt(i, |s| e.encode(s)));
+            }
+            Ok(())
+        })
+    }
+}
+
+impl<A> Decodable for AccumulateVec<A>
+    where A: Array,
+          A::Element: Decodable {
+    fn decode<D: Decoder>(d: &mut D) -> Result<AccumulateVec<A>, D::Error> {
+        d.read_seq(|d, len| {
+            Ok(try!((0..len).map(|i| d.read_seq_elt(i, |d| Decodable::decode(d))).collect()))
+        })
+    }
+}
+
diff --git a/src/librustc_data_structures/array_vec.rs b/src/librustc_data_structures/array_vec.rs
index f87426cee59..631cf2cfcf6 100644
--- a/src/librustc_data_structures/array_vec.rs
+++ b/src/librustc_data_structures/array_vec.rs
@@ -9,15 +9,15 @@
 // except according to those terms.
 
 //! A stack-allocated vector, allowing storage of N elements on the stack.
-//!
-//! Currently, only the N = 8 case is supported (due to Array only being impl-ed for [T; 8]).
 
 use std::marker::Unsize;
 use std::iter::Extend;
-use std::ptr::drop_in_place;
-use std::ops::{Deref, DerefMut};
+use std::ptr::{self, drop_in_place};
+use std::ops::{Deref, DerefMut, Range};
+use std::hash::{Hash, Hasher};
 use std::slice;
 use std::fmt;
+use std::mem;
 
 pub unsafe trait Array {
     type Element;
@@ -25,6 +25,12 @@ pub unsafe trait Array {
     const LEN: usize;
 }
 
+unsafe impl<T> Array for [T; 1] {
+    type Element = T;
+    type PartialStorage = [ManuallyDrop<T>; 1];
+    const LEN: usize = 1;
+}
+
 unsafe impl<T> Array for [T; 8] {
     type Element = T;
     type PartialStorage = [ManuallyDrop<T>; 8];
@@ -36,6 +42,32 @@ pub struct ArrayVec<A: Array> {
     values: A::PartialStorage
 }
 
+impl<A> Hash for ArrayVec<A>
+    where A: Array,
+          A::Element: Hash {
+    fn hash<H>(&self, state: &mut H) where H: Hasher {
+        (&self[..]).hash(state);
+    }
+}
+
+impl<A: Array> PartialEq for ArrayVec<A> {
+    fn eq(&self, other: &Self) -> bool {
+        self == other
+    }
+}
+
+impl<A: Array> Eq for ArrayVec<A> {}
+
+impl<A> Clone for ArrayVec<A>
+    where A: Array,
+          A::Element: Clone {
+    fn clone(&self) -> Self {
+        let mut v = ArrayVec::new();
+        v.extend(self.iter().cloned());
+        v
+    }
+}
+
 impl<A: Array> ArrayVec<A> {
     pub fn new() -> Self {
         ArrayVec {
@@ -43,6 +75,41 @@ impl<A: Array> ArrayVec<A> {
             values: Default::default(),
         }
     }
+
+    pub fn len(&self) -> usize {
+        self.count
+    }
+
+    pub unsafe fn set_len(&mut self, len: usize) {
+        self.count = len;
+    }
+
+    /// Panics when the stack vector is full.
+    pub fn push(&mut self, el: A::Element) {
+        let arr = &mut self.values as &mut [ManuallyDrop<_>];
+        arr[self.count] = ManuallyDrop { value: el };
+        self.count += 1;
+    }
+
+    pub fn pop(&mut self) -> Option<A::Element> {
+        if self.count > 0 {
+            let arr = &mut self.values as &mut [ManuallyDrop<_>];
+            self.count -= 1;
+            unsafe {
+                let value = ptr::read(&arr[self.count]);
+                Some(value.value)
+            }
+        } else {
+            None
+        }
+    }
+}
+
+impl<A> Default for ArrayVec<A>
+    where A: Array {
+    fn default() -> Self {
+        ArrayVec::new()
+    }
 }
 
 impl<A> fmt::Debug for ArrayVec<A>
@@ -81,15 +148,69 @@ impl<A: Array> Drop for ArrayVec<A> {
 impl<A: Array> Extend<A::Element> for ArrayVec<A> {
     fn extend<I>(&mut self, iter: I) where I: IntoIterator<Item=A::Element> {
         for el in iter {
-            unsafe {
-                let arr = &mut self.values as &mut [ManuallyDrop<_>];
-                arr[self.count].value = el;
-            }
-            self.count += 1;
+            self.push(el);
+        }
+    }
+}
+
+pub struct Iter<A: Array> {
+    indices: Range<usize>,
+    store: A::PartialStorage,
+}
+
+impl<A: Array> Drop for Iter<A> {
+    fn drop(&mut self) {
+        for _ in self {}
+    }
+}
+
+impl<A: Array> Iterator for Iter<A> {
+    type Item = A::Element;
+
+    fn next(&mut self) -> Option<A::Element> {
+        let arr = &self.store as &[ManuallyDrop<_>];
+        unsafe {
+            self.indices.next().map(|i| ptr::read(&arr[i]).value)
+        }
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.indices.size_hint()
+    }
+}
+
+impl<A: Array> IntoIterator for ArrayVec<A> {
+    type Item = A::Element;
+    type IntoIter = Iter<A>;
+    fn into_iter(self) -> Self::IntoIter {
+        let store = unsafe {
+            ptr::read(&self.values)
+        };
+        let indices = 0..self.count;
+        mem::forget(self);
+        Iter {
+            indices: indices,
+            store: store,
         }
     }
 }
 
+impl<'a, A: Array> IntoIterator for &'a ArrayVec<A> {
+    type Item = &'a A::Element;
+    type IntoIter = slice::Iter<'a, A::Element>;
+    fn into_iter(self) -> Self::IntoIter {
+        self.iter()
+    }
+}
+
+impl<'a, A: Array> IntoIterator for &'a mut ArrayVec<A> {
+    type Item = &'a mut A::Element;
+    type IntoIter = slice::IterMut<'a, A::Element>;
+    fn into_iter(self) -> Self::IntoIter {
+        self.iter_mut()
+    }
+}
+
 // FIXME: This should use repr(transparent) from rust-lang/rfcs#1758.
 #[allow(unions_with_drop_fields)]
 pub union ManuallyDrop<T> {
@@ -98,9 +219,17 @@ pub union ManuallyDrop<T> {
     empty: (),
 }
 
+impl<T> ManuallyDrop<T> {
+    fn new() -> ManuallyDrop<T> {
+        ManuallyDrop {
+            empty: ()
+        }
+    }
+}
+
 impl<T> Default for ManuallyDrop<T> {
     fn default() -> Self {
-        ManuallyDrop { empty: () }
+        ManuallyDrop::new()
     }
 }
 
diff --git a/src/librustc_data_structures/lib.rs b/src/librustc_data_structures/lib.rs
index fdcbec6bac1..2e4206d2ee1 100644
--- a/src/librustc_data_structures/lib.rs
+++ b/src/librustc_data_structures/lib.rs
@@ -46,6 +46,7 @@ extern crate libc;
 
 pub mod array_vec;
 pub mod accumulate_vec;
+pub mod small_vec;
 pub mod bitslice;
 pub mod blake2b;
 pub mod bitvec;
diff --git a/src/librustc_data_structures/small_vec.rs b/src/librustc_data_structures/small_vec.rs
new file mode 100644
index 00000000000..565a3c443a3
--- /dev/null
+++ b/src/librustc_data_structures/small_vec.rs
@@ -0,0 +1,203 @@
+// Copyright 2016 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.
+
+//! A vector type intended to be used for collecting from iterators onto the stack.
+//!
+//! Space for up to N elements is provided on the stack.  If more elements are collected, Vec is
+//! used to store the values on the heap. SmallVec is similar to AccumulateVec, but adds
+//! the ability to push elements.
+//!
+//! The N above is determined by Array's implementor, by way of an associatated constant.
+
+use std::ops::{Deref, DerefMut};
+use std::iter::{IntoIterator, FromIterator};
+use std::fmt::{self, Debug};
+use std::mem;
+use std::ptr;
+
+use rustc_serialize::{Encodable, Encoder, Decodable, Decoder};
+
+use accumulate_vec::{IntoIter, AccumulateVec};
+use array_vec::Array;
+
+pub struct SmallVec<A: Array>(AccumulateVec<A>);
+
+impl<A> Clone for SmallVec<A>
+    where A: Array,
+          A::Element: Clone {
+    fn clone(&self) -> Self {
+        SmallVec(self.0.clone())
+    }
+}
+
+impl<A> Debug for SmallVec<A>
+    where A: Array + Debug,
+          A::Element: Debug {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        f.debug_tuple("SmallVec").field(&self.0).finish()
+    }
+}
+
+impl<A: Array> SmallVec<A> {
+    pub fn new() -> Self {
+        SmallVec(AccumulateVec::new())
+    }
+
+    pub fn with_capacity(cap: usize) -> Self {
+        let mut vec = SmallVec::new();
+        vec.reserve(cap);
+        vec
+    }
+
+    pub fn one(el: A::Element) -> Self {
+        SmallVec(AccumulateVec::one(el))
+    }
+
+    pub fn many<I: IntoIterator<Item=A::Element>>(els: I) -> Self {
+        SmallVec(AccumulateVec::many(els))
+    }
+
+    pub fn expect_one(self, err: &'static str) -> A::Element {
+        assert!(self.len() == 1, err);
+        match self.0 {
+            AccumulateVec::Array(arr) => arr.into_iter().next().unwrap(),
+            AccumulateVec::Heap(vec) => vec.into_iter().next().unwrap(),
+        }
+    }
+
+    /// Will reallocate onto the heap if needed.
+    pub fn push(&mut self, el: A::Element) {
+        self.reserve(1);
+        match self.0 {
+            AccumulateVec::Array(ref mut array) => array.push(el),
+            AccumulateVec::Heap(ref mut vec) => vec.push(el),
+        }
+    }
+
+    pub fn reserve(&mut self, n: usize) {
+        match self.0 {
+            AccumulateVec::Array(_) => {
+                if self.len() + n > A::LEN {
+                    let len = self.len();
+                    let array = mem::replace(&mut self.0,
+                            AccumulateVec::Heap(Vec::with_capacity(len + n)));
+                    if let AccumulateVec::Array(array) = array {
+                        match self.0 {
+                            AccumulateVec::Heap(ref mut vec) => vec.extend(array),
+                            _ => unreachable!()
+                        }
+                    }
+                }
+            }
+            AccumulateVec::Heap(ref mut vec) => vec.reserve(n)
+        }
+    }
+
+    pub unsafe fn set_len(&mut self, len: usize) {
+        match self.0 {
+            AccumulateVec::Array(ref mut arr) => arr.set_len(len),
+            AccumulateVec::Heap(ref mut vec) => vec.set_len(len),
+        }
+    }
+
+    pub fn insert(&mut self, index: usize, element: A::Element) {
+        let len = self.len();
+
+        // Reserve space for shifting elements to the right
+        self.reserve(1);
+
+        assert!(index <= len);
+
+        unsafe {
+            // infallible
+            // The spot to put the new value
+            {
+                let p = self.as_mut_ptr().offset(index as isize);
+                // Shift everything over to make space. (Duplicating the
+                // `index`th element into two consecutive places.)
+                ptr::copy(p, p.offset(1), len - index);
+                // Write it in, overwriting the first copy of the `index`th
+                // element.
+                ptr::write(p, element);
+            }
+            self.set_len(len + 1);
+        }
+    }
+}
+
+impl<A: Array> Deref for SmallVec<A> {
+    type Target = AccumulateVec<A>;
+    fn deref(&self) -> &Self::Target {
+        &self.0
+    }
+}
+
+impl<A: Array> DerefMut for SmallVec<A> {
+    fn deref_mut(&mut self) -> &mut AccumulateVec<A> {
+        &mut self.0
+    }
+}
+
+impl<A: Array> FromIterator<A::Element> for SmallVec<A> {
+    fn from_iter<I>(iter: I) -> Self where I: IntoIterator<Item=A::Element> {
+        SmallVec(iter.into_iter().collect())
+    }
+}
+
+impl<A: Array> Extend<A::Element> for SmallVec<A> {
+    fn extend<I: IntoIterator<Item=A::Element>>(&mut self, iter: I) {
+        let iter = iter.into_iter();
+        self.reserve(iter.size_hint().0);
+        for el in iter {
+            self.push(el);
+        }
+    }
+}
+
+impl<A: Array> IntoIterator for SmallVec<A> {
+    type Item = A::Element;
+    type IntoIter = IntoIter<A>;
+    fn into_iter(self) -> Self::IntoIter {
+        self.0.into_iter()
+    }
+}
+
+impl<A: Array> Default for SmallVec<A> {
+    fn default() -> SmallVec<A> {
+        SmallVec::new()
+    }
+}
+
+impl<A> Encodable for SmallVec<A>
+    where A: Array,
+          A::Element: Encodable {
+    fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
+        s.emit_seq(self.len(), |s| {
+            for (i, e) in self.iter().enumerate() {
+                try!(s.emit_seq_elt(i, |s| e.encode(s)));
+            }
+            Ok(())
+        })
+    }
+}
+
+impl<A> Decodable for SmallVec<A>
+    where A: Array,
+          A::Element: Decodable {
+    fn decode<D: Decoder>(d: &mut D) -> Result<SmallVec<A>, D::Error> {
+        d.read_seq(|d, len| {
+            let mut vec = SmallVec::with_capacity(len);
+            for i in 0..len {
+                vec.push(try!(d.read_seq_elt(i, |d| Decodable::decode(d))));
+            }
+            Ok(vec)
+        })
+    }
+}
diff --git a/src/libsyntax/Cargo.toml b/src/libsyntax/Cargo.toml
index 8b61e1b0d3a..0b38f5450b6 100644
--- a/src/libsyntax/Cargo.toml
+++ b/src/libsyntax/Cargo.toml
@@ -14,3 +14,4 @@ log = { path = "../liblog" }
 rustc_bitflags = { path = "../librustc_bitflags" }
 syntax_pos = { path = "../libsyntax_pos" }
 rustc_errors = { path = "../librustc_errors" }
+rustc_data_structures = { path = "../librustc_data_structures" }
diff --git a/src/libsyntax/config.rs b/src/libsyntax/config.rs
index 946257a16d5..02429f02738 100644
--- a/src/libsyntax/config.rs
+++ b/src/libsyntax/config.rs
@@ -277,7 +277,7 @@ impl<'a> fold::Folder for StripUnconfigured<'a> {
     fn fold_stmt(&mut self, stmt: ast::Stmt) -> SmallVector<ast::Stmt> {
         match self.configure_stmt(stmt) {
             Some(stmt) => fold::noop_fold_stmt(stmt, self),
-            None => return SmallVector::zero(),
+            None => return SmallVector::new(),
         }
     }
 
diff --git a/src/libsyntax/ext/base.rs b/src/libsyntax/ext/base.rs
index 63eee7df9e8..b4ac576f57a 100644
--- a/src/libsyntax/ext/base.rs
+++ b/src/libsyntax/ext/base.rs
@@ -440,7 +440,7 @@ impl MacResult for DummyResult {
         if self.expr_only {
             None
         } else {
-            Some(SmallVector::zero())
+            Some(SmallVector::new())
         }
     }
 
@@ -448,7 +448,7 @@ impl MacResult for DummyResult {
         if self.expr_only {
             None
         } else {
-            Some(SmallVector::zero())
+            Some(SmallVector::new())
         }
     }
 
@@ -456,7 +456,7 @@ impl MacResult for DummyResult {
         if self.expr_only {
             None
         } else {
-            Some(SmallVector::zero())
+            Some(SmallVector::new())
         }
     }
 
diff --git a/src/libsyntax/ext/expand.rs b/src/libsyntax/ext/expand.rs
index c3608aac0b4..877b312539f 100644
--- a/src/libsyntax/ext/expand.rs
+++ b/src/libsyntax/ext/expand.rs
@@ -89,7 +89,7 @@ macro_rules! expansions {
                     Expansion::OptExpr(Some(ref expr)) => visitor.visit_expr(expr),
                     Expansion::OptExpr(None) => {}
                     $($( Expansion::$kind(ref ast) => visitor.$visit(ast), )*)*
-                    $($( Expansion::$kind(ref ast) => for ast in ast.as_slice() {
+                    $($( Expansion::$kind(ref ast) => for ast in &ast[..] {
                         visitor.$visit_elt(ast);
                     }, )*)*
                 }
@@ -511,28 +511,28 @@ impl<'a> Parser<'a> {
                            -> PResult<'a, Expansion> {
         Ok(match kind {
             ExpansionKind::Items => {
-                let mut items = SmallVector::zero();
+                let mut items = SmallVector::new();
                 while let Some(item) = self.parse_item()? {
                     items.push(item);
                 }
                 Expansion::Items(items)
             }
             ExpansionKind::TraitItems => {
-                let mut items = SmallVector::zero();
+                let mut items = SmallVector::new();
                 while self.token != token::Eof {
                     items.push(self.parse_trait_item()?);
                 }
                 Expansion::TraitItems(items)
             }
             ExpansionKind::ImplItems => {
-                let mut items = SmallVector::zero();
+                let mut items = SmallVector::new();
                 while self.token != token::Eof {
                     items.push(self.parse_impl_item()?);
                 }
                 Expansion::ImplItems(items)
             }
             ExpansionKind::Stmts => {
-                let mut stmts = SmallVector::zero();
+                let mut stmts = SmallVector::new();
                 while self.token != token::Eof &&
                       // won't make progress on a `}`
                       self.token != token::CloseDelim(token::Brace) {
@@ -573,7 +573,7 @@ macro_rules! fully_configure {
     ($this:ident, $node:ident, $noop_fold:ident) => {
         match $noop_fold($node, &mut $this.cfg).pop() {
             Some(node) => node,
-            None => return SmallVector::zero(),
+            None => return SmallVector::new(),
         }
     }
 }
@@ -689,7 +689,7 @@ impl<'a, 'b> Folder for InvocationCollector<'a, 'b> {
     fn fold_stmt(&mut self, stmt: ast::Stmt) -> SmallVector<ast::Stmt> {
         let stmt = match self.cfg.configure_stmt(stmt) {
             Some(stmt) => stmt,
-            None => return SmallVector::zero(),
+            None => return SmallVector::new(),
         };
 
         let (mac, style, attrs) = if let StmtKind::Mac(mac) = stmt.node {
diff --git a/src/libsyntax/ext/source_util.rs b/src/libsyntax/ext/source_util.rs
index ec48cae3f76..bda84cdaf39 100644
--- a/src/libsyntax/ext/source_util.rs
+++ b/src/libsyntax/ext/source_util.rs
@@ -104,7 +104,7 @@ pub fn expand_include<'cx>(cx: &'cx mut ExtCtxt, sp: Span, tts: &[tokenstream::T
         }
         fn make_items(mut self: Box<ExpandResult<'a>>)
                       -> Option<SmallVector<P<ast::Item>>> {
-            let mut ret = SmallVector::zero();
+            let mut ret = SmallVector::new();
             while self.p.token != token::Eof {
                 match panictry!(self.p.parse_item()) {
                     Some(item) => ret.push(item),
diff --git a/src/libsyntax/lib.rs b/src/libsyntax/lib.rs
index feed400897c..34280812421 100644
--- a/src/libsyntax/lib.rs
+++ b/src/libsyntax/lib.rs
@@ -45,6 +45,7 @@ extern crate libc;
 extern crate rustc_unicode;
 pub extern crate rustc_errors as errors;
 extern crate syntax_pos;
+extern crate rustc_data_structures;
 
 extern crate serialize as rustc_serialize; // used by deriving
 
diff --git a/src/libsyntax/util/move_map.rs b/src/libsyntax/util/move_map.rs
index e1078b719bf..fe05e2958b3 100644
--- a/src/libsyntax/util/move_map.rs
+++ b/src/libsyntax/util/move_map.rs
@@ -10,6 +10,8 @@
 
 use std::ptr;
 
+use util::small_vector::SmallVector;
+
 pub trait MoveMap<T>: Sized {
     fn move_map<F>(self, mut f: F) -> Self where F: FnMut(T) -> T {
         self.move_flat_map(|e| Some(f(e)))
@@ -75,3 +77,50 @@ impl<T> MoveMap<T> for ::ptr::P<[T]> {
         ::ptr::P::from_vec(self.into_vec().move_flat_map(f))
     }
 }
+
+impl<T> MoveMap<T> for SmallVector<T> {
+    fn move_flat_map<F, I>(mut self, mut f: F) -> Self
+        where F: FnMut(T) -> I,
+              I: IntoIterator<Item=T>
+    {
+        let mut read_i = 0;
+        let mut write_i = 0;
+        unsafe {
+            let mut old_len = self.len();
+            self.set_len(0); // make sure we just leak elements in case of panic
+
+            while read_i < old_len {
+                // move the read_i'th item out of the vector and map it
+                // to an iterator
+                let e = ptr::read(self.get_unchecked(read_i));
+                let mut iter = f(e).into_iter();
+                read_i += 1;
+
+                while let Some(e) = iter.next() {
+                    if write_i < read_i {
+                        ptr::write(self.get_unchecked_mut(write_i), e);
+                        write_i += 1;
+                    } else {
+                        // If this is reached we ran out of space
+                        // in the middle of the vector.
+                        // However, the vector is in a valid state here,
+                        // so we just do a somewhat inefficient insert.
+                        self.set_len(old_len);
+                        self.insert(write_i, e);
+
+                        old_len = self.len();
+                        self.set_len(0);
+
+                        read_i += 1;
+                        write_i += 1;
+                    }
+                }
+            }
+
+            // write_i tracks the number of actually written new items.
+            self.set_len(write_i);
+        }
+
+        self
+    }
+}
diff --git a/src/libsyntax/util/small_vector.rs b/src/libsyntax/util/small_vector.rs
index 9be7dbd6817..31e675836fc 100644
--- a/src/libsyntax/util/small_vector.rs
+++ b/src/libsyntax/util/small_vector.rs
@@ -8,253 +8,9 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use self::SmallVectorRepr::*;
-use self::IntoIterRepr::*;
+use rustc_data_structures::small_vec::SmallVec;
 
-use core::ops;
-use std::iter::{IntoIterator, FromIterator};
-use std::mem;
-use std::slice;
-use std::vec;
-
-use util::move_map::MoveMap;
-
-/// A vector type optimized for cases where the size is almost always 0 or 1
-#[derive(Clone)]
-pub struct SmallVector<T> {
-    repr: SmallVectorRepr<T>,
-}
-
-#[derive(Clone)]
-enum SmallVectorRepr<T> {
-    Zero,
-    One(T),
-    Many(Vec<T>),
-}
-
-impl<T> Default for SmallVector<T> {
-    fn default() -> Self {
-        SmallVector { repr: Zero }
-    }
-}
-
-impl<T> Into<Vec<T>> for SmallVector<T> {
-    fn into(self) -> Vec<T> {
-        match self.repr {
-            Zero => Vec::new(),
-            One(t) => vec![t],
-            Many(vec) => vec,
-        }
-    }
-}
-
-impl<T> FromIterator<T> for SmallVector<T> {
-    fn from_iter<I: IntoIterator<Item=T>>(iter: I) -> SmallVector<T> {
-        let mut v = SmallVector::zero();
-        v.extend(iter);
-        v
-    }
-}
-
-impl<T> Extend<T> for SmallVector<T> {
-    fn extend<I: IntoIterator<Item=T>>(&mut self, iter: I) {
-        for val in iter {
-            self.push(val);
-        }
-    }
-}
-
-impl<T> SmallVector<T> {
-    pub fn zero() -> SmallVector<T> {
-        SmallVector { repr: Zero }
-    }
-
-    pub fn one(v: T) -> SmallVector<T> {
-        SmallVector { repr: One(v) }
-    }
-
-    pub fn many(vs: Vec<T>) -> SmallVector<T> {
-        SmallVector { repr: Many(vs) }
-    }
-
-    pub fn as_slice(&self) -> &[T] {
-        self
-    }
-
-    pub fn as_mut_slice(&mut self) -> &mut [T] {
-        self
-    }
-
-    pub fn pop(&mut self) -> Option<T> {
-        match self.repr {
-            Zero => None,
-            One(..) => {
-                let one = mem::replace(&mut self.repr, Zero);
-                match one {
-                    One(v1) => Some(v1),
-                    _ => unreachable!()
-                }
-            }
-            Many(ref mut vs) => vs.pop(),
-        }
-    }
-
-    pub fn push(&mut self, v: T) {
-        match self.repr {
-            Zero => self.repr = One(v),
-            One(..) => {
-                let one = mem::replace(&mut self.repr, Zero);
-                match one {
-                    One(v1) => mem::replace(&mut self.repr, Many(vec![v1, v])),
-                    _ => unreachable!()
-                };
-            }
-            Many(ref mut vs) => vs.push(v)
-        }
-    }
-
-    pub fn push_all(&mut self, other: SmallVector<T>) {
-        for v in other.into_iter() {
-            self.push(v);
-        }
-    }
-
-    pub fn get(&self, idx: usize) -> &T {
-        match self.repr {
-            One(ref v) if idx == 0 => v,
-            Many(ref vs) => &vs[idx],
-            _ => panic!("out of bounds access")
-        }
-    }
-
-    pub fn expect_one(self, err: &'static str) -> T {
-        match self.repr {
-            One(v) => v,
-            Many(v) => {
-                if v.len() == 1 {
-                    v.into_iter().next().unwrap()
-                } else {
-                    panic!(err)
-                }
-            }
-            _ => panic!(err)
-        }
-    }
-
-    pub fn len(&self) -> usize {
-        match self.repr {
-            Zero => 0,
-            One(..) => 1,
-            Many(ref vals) => vals.len()
-        }
-    }
-
-    pub fn is_empty(&self) -> bool { self.len() == 0 }
-
-    pub fn map<U, F: FnMut(T) -> U>(self, mut f: F) -> SmallVector<U> {
-        let repr = match self.repr {
-            Zero => Zero,
-            One(t) => One(f(t)),
-            Many(vec) => Many(vec.into_iter().map(f).collect()),
-        };
-        SmallVector { repr: repr }
-    }
-}
-
-impl<T> ops::Deref for SmallVector<T> {
-    type Target = [T];
-
-    fn deref(&self) -> &[T] {
-        match self.repr {
-            Zero => {
-                let result: &[T] = &[];
-                result
-            }
-            One(ref v) => {
-                unsafe { slice::from_raw_parts(v, 1) }
-            }
-            Many(ref vs) => vs
-        }
-    }
-}
-
-impl<T> ops::DerefMut for SmallVector<T> {
-    fn deref_mut(&mut self) -> &mut [T] {
-        match self.repr {
-            Zero => {
-                let result: &mut [T] = &mut [];
-                result
-            }
-            One(ref mut v) => {
-                unsafe { slice::from_raw_parts_mut(v, 1) }
-            }
-            Many(ref mut vs) => vs
-        }
-    }
-}
-
-impl<T> IntoIterator for SmallVector<T> {
-    type Item = T;
-    type IntoIter = IntoIter<T>;
-    fn into_iter(self) -> Self::IntoIter {
-        let repr = match self.repr {
-            Zero => ZeroIterator,
-            One(v) => OneIterator(v),
-            Many(vs) => ManyIterator(vs.into_iter())
-        };
-        IntoIter { repr: repr }
-    }
-}
-
-pub struct IntoIter<T> {
-    repr: IntoIterRepr<T>,
-}
-
-enum IntoIterRepr<T> {
-    ZeroIterator,
-    OneIterator(T),
-    ManyIterator(vec::IntoIter<T>),
-}
-
-impl<T> Iterator for IntoIter<T> {
-    type Item = T;
-
-    fn next(&mut self) -> Option<T> {
-        match self.repr {
-            ZeroIterator => None,
-            OneIterator(..) => {
-                let mut replacement = ZeroIterator;
-                mem::swap(&mut self.repr, &mut replacement);
-                match replacement {
-                    OneIterator(v) => Some(v),
-                    _ => unreachable!()
-                }
-            }
-            ManyIterator(ref mut inner) => inner.next()
-        }
-    }
-
-    fn size_hint(&self) -> (usize, Option<usize>) {
-        match self.repr {
-            ZeroIterator => (0, Some(0)),
-            OneIterator(..) => (1, Some(1)),
-            ManyIterator(ref inner) => inner.size_hint()
-        }
-    }
-}
-
-impl<T> MoveMap<T> for SmallVector<T> {
-    fn move_flat_map<F, I>(self, mut f: F) -> Self
-        where F: FnMut(T) -> I,
-              I: IntoIterator<Item=T>
-    {
-        match self.repr {
-            Zero => Self::zero(),
-            One(v) => f(v).into_iter().collect(),
-            Many(vs) => SmallVector { repr: Many(vs.move_flat_map(f)) },
-        }
-    }
-}
+pub type SmallVector<T> = SmallVec<[T; 1]>;
 
 #[cfg(test)]
 mod tests {
@@ -262,7 +18,7 @@ mod tests {
 
     #[test]
     fn test_len() {
-        let v: SmallVector<isize> = SmallVector::zero();
+        let v: SmallVector<isize> = SmallVector::new();
         assert_eq!(0, v.len());
 
         assert_eq!(1, SmallVector::one(1).len());
@@ -271,30 +27,30 @@ mod tests {
 
     #[test]
     fn test_push_get() {
-        let mut v = SmallVector::zero();
+        let mut v = SmallVector::new();
         v.push(1);
         assert_eq!(1, v.len());
-        assert_eq!(&1, v.get(0));
+        assert_eq!(1, v[0]);
         v.push(2);
         assert_eq!(2, v.len());
-        assert_eq!(&2, v.get(1));
+        assert_eq!(2, v[1]);
         v.push(3);
         assert_eq!(3, v.len());
-        assert_eq!(&3, v.get(2));
+        assert_eq!(3, v[2]);
     }
 
     #[test]
     fn test_from_iter() {
         let v: SmallVector<isize> = (vec![1, 2, 3]).into_iter().collect();
         assert_eq!(3, v.len());
-        assert_eq!(&1, v.get(0));
-        assert_eq!(&2, v.get(1));
-        assert_eq!(&3, v.get(2));
+        assert_eq!(1, v[0]);
+        assert_eq!(2, v[1]);
+        assert_eq!(3, v[2]);
     }
 
     #[test]
     fn test_move_iter() {
-        let v = SmallVector::zero();
+        let v = SmallVector::new();
         let v: Vec<isize> = v.into_iter().collect();
         assert_eq!(v, Vec::new());
 
@@ -308,7 +64,7 @@ mod tests {
     #[test]
     #[should_panic]
     fn test_expect_one_zero() {
-        let _: isize = SmallVector::zero().expect_one("");
+        let _: isize = SmallVector::new().expect_one("");
     }
 
     #[test]