Remove `AccumulateVec` and its uses.

It's basically just a less capable version of `SmallVec`.

13 files changed, 40 insertions, 301 deletions

diff --git a/src/Cargo.lock b/src/Cargo.lock
index 9d5f3bbd9e3..37a6f9130f5 100644
--- a/src/Cargo.lock
+++ b/src/Cargo.lock
@@ -2354,6 +2354,7 @@ dependencies = [
  "rustc_errors 0.0.0",
  "rustc_platform_intrinsics 0.0.0",
  "rustc_target 0.0.0",
+ "smallvec 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)",
  "syntax 0.0.0",
  "syntax_pos 0.0.0",
 ]
diff --git a/src/librustc/ich/hcx.rs b/src/librustc/ich/hcx.rs
index f03ad98c7de..371f631737c 100644
--- a/src/librustc/ich/hcx.rs
+++ b/src/librustc/ich/hcx.rs
@@ -34,8 +34,8 @@ use syntax_pos::hygiene;
 use rustc_data_structures::stable_hasher::{HashStable,
                                            StableHasher, StableHasherResult,
                                            ToStableHashKey};
-use rustc_data_structures::accumulate_vec::AccumulateVec;
 use rustc_data_structures::fx::{FxHashSet, FxHashMap};
+use smallvec::SmallVec;
 
 fn compute_ignored_attr_names() -> FxHashSet<Symbol> {
     debug_assert!(ich::IGNORED_ATTRIBUTES.len() > 0);
@@ -405,7 +405,7 @@ pub fn hash_stable_trait_impls<'a, 'gcx, W, R>(
           R: std_hash::BuildHasher,
 {
     {
-        let mut blanket_impls: AccumulateVec<[_; 8]> = blanket_impls
+        let mut blanket_impls: SmallVec<[_; 8]> = blanket_impls
             .iter()
             .map(|&def_id| hcx.def_path_hash(def_id))
             .collect();
@@ -418,7 +418,7 @@ pub fn hash_stable_trait_impls<'a, 'gcx, W, R>(
     }
 
     {
-        let mut keys: AccumulateVec<[_; 8]> =
+        let mut keys: SmallVec<[_; 8]> =
             non_blanket_impls.keys()
                              .map(|k| (k, k.map_def(|d| hcx.def_path_hash(d))))
                              .collect();
@@ -426,7 +426,7 @@ pub fn hash_stable_trait_impls<'a, 'gcx, W, R>(
         keys.len().hash_stable(hcx, hasher);
         for (key, ref stable_key) in keys {
             stable_key.hash_stable(hcx, hasher);
-            let mut impls : AccumulateVec<[_; 8]> = non_blanket_impls[key]
+            let mut impls : SmallVec<[_; 8]> = non_blanket_impls[key]
                 .iter()
                 .map(|&impl_id| hcx.def_path_hash(impl_id))
                 .collect();
diff --git a/src/librustc/ich/impls_syntax.rs b/src/librustc/ich/impls_syntax.rs
index 4811f84635c..ac5fdb2fe27 100644
--- a/src/librustc/ich/impls_syntax.rs
+++ b/src/librustc/ich/impls_syntax.rs
@@ -25,9 +25,9 @@ use syntax_pos::SourceFile;
 
 use hir::def_id::{DefId, CrateNum, CRATE_DEF_INDEX};
 
+use smallvec::SmallVec;
 use rustc_data_structures::stable_hasher::{HashStable, ToStableHashKey,
                                            StableHasher, StableHasherResult};
-use rustc_data_structures::accumulate_vec::AccumulateVec;
 
 impl<'a> HashStable<StableHashingContext<'a>> for InternedString {
     #[inline]
@@ -207,7 +207,7 @@ impl<'a> HashStable<StableHashingContext<'a>> for [ast::Attribute] {
         }
 
         // Some attributes are always ignored during hashing.
-        let filtered: AccumulateVec<[&ast::Attribute; 8]> = self
+        let filtered: SmallVec<[&ast::Attribute; 8]> = self
             .iter()
             .filter(|attr| {
                 !attr.is_sugared_doc && !hcx.is_ignored_attr(attr.name())
diff --git a/src/librustc/traits/structural_impls.rs b/src/librustc/traits/structural_impls.rs
index 87535a6ae8d..10e930d1c92 100644
--- a/src/librustc/traits/structural_impls.rs
+++ b/src/librustc/traits/structural_impls.rs
@@ -9,7 +9,7 @@
 // except according to those terms.
 
 use chalk_engine;
-use rustc_data_structures::accumulate_vec::AccumulateVec;
+use smallvec::SmallVec;
 use traits;
 use traits::project::Normalized;
 use ty::fold::{TypeFoldable, TypeFolder, TypeVisitor};
@@ -624,7 +624,7 @@ impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::List<traits::Goal<'tcx>> {
     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
         let v = self.iter()
             .map(|t| t.fold_with(folder))
-            .collect::<AccumulateVec<[_; 8]>>();
+            .collect::<SmallVec<[_; 8]>>();
         folder.tcx().intern_goals(&v)
     }
 
@@ -662,7 +662,7 @@ impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::List<traits::Clause<'tcx>> {
     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
         let v = self.iter()
             .map(|t| t.fold_with(folder))
-            .collect::<AccumulateVec<[_; 8]>>();
+            .collect::<SmallVec<[_; 8]>>();
         folder.tcx().intern_clauses(&v)
     }
 
diff --git a/src/librustc/ty/context.rs b/src/librustc/ty/context.rs
index 424139e7527..65298a070b7 100644
--- a/src/librustc/ty/context.rs
+++ b/src/librustc/ty/context.rs
@@ -52,7 +52,7 @@ use ty::BindingMode;
 use ty::CanonicalTy;
 use util::nodemap::{DefIdSet, ItemLocalMap};
 use util::nodemap::{FxHashMap, FxHashSet};
-use rustc_data_structures::accumulate_vec::AccumulateVec;
+use smallvec::SmallVec;
 use rustc_data_structures::stable_hasher::{HashStable, hash_stable_hashmap,
                                            StableHasher, StableHasherResult,
                                            StableVec};
@@ -2840,7 +2840,7 @@ pub trait InternIteratorElement<T, R>: Sized {
 impl<T, R> InternIteratorElement<T, R> for T {
     type Output = R;
     fn intern_with<I: Iterator<Item=Self>, F: FnOnce(&[T]) -> R>(iter: I, f: F) -> Self::Output {
-        f(&iter.collect::<AccumulateVec<[_; 8]>>())
+        f(&iter.collect::<SmallVec<[_; 8]>>())
     }
 }
 
@@ -2849,14 +2849,14 @@ impl<'a, T, R> InternIteratorElement<T, R> for &'a T
 {
     type Output = R;
     fn intern_with<I: Iterator<Item=Self>, F: FnOnce(&[T]) -> R>(iter: I, f: F) -> Self::Output {
-        f(&iter.cloned().collect::<AccumulateVec<[_; 8]>>())
+        f(&iter.cloned().collect::<SmallVec<[_; 8]>>())
     }
 }
 
 impl<T, R, E> InternIteratorElement<T, R> for Result<T, E> {
     type Output = Result<R, E>;
     fn intern_with<I: Iterator<Item=Self>, F: FnOnce(&[T]) -> R>(iter: I, f: F) -> Self::Output {
-        Ok(f(&iter.collect::<Result<AccumulateVec<[_; 8]>, _>>()?))
+        Ok(f(&iter.collect::<Result<SmallVec<[_; 8]>, _>>()?))
     }
 }
 
diff --git a/src/librustc/ty/structural_impls.rs b/src/librustc/ty/structural_impls.rs
index e6c10358279..6a5df553f3d 100644
--- a/src/librustc/ty/structural_impls.rs
+++ b/src/librustc/ty/structural_impls.rs
@@ -16,8 +16,8 @@
 use mir::interpret::{ConstValue, ConstEvalErr};
 use ty::{self, Lift, Ty, TyCtxt};
 use ty::fold::{TypeFoldable, TypeFolder, TypeVisitor};
-use rustc_data_structures::accumulate_vec::AccumulateVec;
 use rustc_data_structures::indexed_vec::{IndexVec, Idx};
+use smallvec::SmallVec;
 use mir::interpret;
 
 use std::rc::Rc;
@@ -741,7 +741,7 @@ BraceStructTypeFoldableImpl! {
 
 impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::List<ty::ExistentialPredicate<'tcx>> {
     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
-        let v = self.iter().map(|p| p.fold_with(folder)).collect::<AccumulateVec<[_; 8]>>();
+        let v = self.iter().map(|p| p.fold_with(folder)).collect::<SmallVec<[_; 8]>>();
         folder.tcx().intern_existential_predicates(&v)
     }
 
@@ -760,7 +760,7 @@ EnumTypeFoldableImpl! {
 
 impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::List<Ty<'tcx>> {
     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
-        let v = self.iter().map(|t| t.fold_with(folder)).collect::<AccumulateVec<[_; 8]>>();
+        let v = self.iter().map(|t| t.fold_with(folder)).collect::<SmallVec<[_; 8]>>();
         folder.tcx().intern_type_list(&v)
     }
 
@@ -1016,7 +1016,7 @@ BraceStructTypeFoldableImpl! {
 
 impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::List<ty::Predicate<'tcx>> {
     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
-        let v = self.iter().map(|p| p.fold_with(folder)).collect::<AccumulateVec<[_; 8]>>();
+        let v = self.iter().map(|p| p.fold_with(folder)).collect::<SmallVec<[_; 8]>>();
         folder.tcx().intern_predicates(&v)
     }
 
diff --git a/src/librustc/ty/subst.rs b/src/librustc/ty/subst.rs
index 6dadc507036..b6ffcd55d91 100644
--- a/src/librustc/ty/subst.rs
+++ b/src/librustc/ty/subst.rs
@@ -17,9 +17,8 @@ use ty::fold::{TypeFoldable, TypeFolder, TypeVisitor};
 
 use serialize::{self, Encodable, Encoder, Decodable, Decoder};
 use syntax_pos::{Span, DUMMY_SP};
-use rustc_data_structures::accumulate_vec::AccumulateVec;
-use rustc_data_structures::array_vec::ArrayVec;
 use rustc_data_structures::indexed_vec::Idx;
+use smallvec::SmallVec;
 
 use core::intrinsics;
 use std::cmp::Ordering;
@@ -203,11 +202,7 @@ impl<'a, 'gcx, 'tcx> Substs<'tcx> {
     {
         let defs = tcx.generics_of(def_id);
         let count = defs.count();
-        let mut substs = if count <= 8 {
-            AccumulateVec::Array(ArrayVec::new())
-        } else {
-            AccumulateVec::Heap(Vec::with_capacity(count))
-        };
+        let mut substs = SmallVec::with_capacity(count);
         Substs::fill_item(&mut substs, tcx, defs, &mut mk_kind);
         tcx.intern_substs(&substs)
     }
@@ -227,7 +222,7 @@ impl<'a, 'gcx, 'tcx> Substs<'tcx> {
         })
     }
 
-    fn fill_item<F>(substs: &mut AccumulateVec<[Kind<'tcx>; 8]>,
+    fn fill_item<F>(substs: &mut SmallVec<[Kind<'tcx>; 8]>,
                     tcx: TyCtxt<'a, 'gcx, 'tcx>,
                     defs: &ty::Generics,
                     mk_kind: &mut F)
@@ -240,7 +235,7 @@ impl<'a, 'gcx, 'tcx> Substs<'tcx> {
         Substs::fill_single(substs, defs, mk_kind)
     }
 
-    fn fill_single<F>(substs: &mut AccumulateVec<[Kind<'tcx>; 8]>,
+    fn fill_single<F>(substs: &mut SmallVec<[Kind<'tcx>; 8]>,
                       defs: &ty::Generics,
                       mk_kind: &mut F)
     where F: FnMut(&ty::GenericParamDef, &[Kind<'tcx>]) -> Kind<'tcx>
@@ -248,10 +243,7 @@ impl<'a, 'gcx, 'tcx> Substs<'tcx> {
         for param in &defs.params {
             let kind = mk_kind(param, substs);
             assert_eq!(param.index as usize, substs.len());
-            match *substs {
-                AccumulateVec::Array(ref mut arr) => arr.push(kind),
-                AccumulateVec::Heap(ref mut vec) => vec.push(kind),
-            }
+            substs.push(kind);
         }
     }
 
@@ -325,7 +317,7 @@ impl<'a, 'gcx, 'tcx> Substs<'tcx> {
 
 impl<'tcx> TypeFoldable<'tcx> for &'tcx Substs<'tcx> {
     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
-        let params: AccumulateVec<[_; 8]> = self.iter().map(|k| k.fold_with(folder)).collect();
+        let params: SmallVec<[_; 8]> = self.iter().map(|k| k.fold_with(folder)).collect();
 
         // If folding doesn't change the substs, it's faster to avoid
         // calling `mk_substs` and instead reuse the existing substs.
diff --git a/src/librustc_data_structures/accumulate_vec.rs b/src/librustc_data_structures/accumulate_vec.rs
deleted file mode 100644
index 9423e6b3256..00000000000
--- a/src/librustc_data_structures/accumulate_vec.rs
+++ /dev/null
@@ -1,242 +0,0 @@
-// 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.
-//!
-//! The N above is determined by Array's implementor, by way of an associated constant.
-
-use std::ops::{Deref, DerefMut, RangeBounds};
-use std::iter::{self, IntoIterator, FromIterator};
-use std::slice;
-use std::vec;
-
-use rustc_serialize::{Encodable, Encoder, Decodable, Decoder};
-
-use array_vec::{self, Array, ArrayVec};
-
-#[derive(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 is_array(&self) -> bool {
-        match self {
-            AccumulateVec::Array(..) => true,
-            AccumulateVec::Heap(..) => false,
-        }
-    }
-
-    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(),
-        }
-    }
-
-    pub fn drain<R>(&mut self, range: R) -> Drain<A>
-        where R: RangeBounds<usize>
-    {
-        match *self {
-            AccumulateVec::Array(ref mut v) => {
-                Drain::Array(v.drain(range))
-            },
-            AccumulateVec::Heap(ref mut v) => {
-                Drain::Heap(v.drain(range))
-            },
-        }
-    }
-}
-
-impl<A: Array> Deref for AccumulateVec<A> {
-    type Target = [A::Element];
-    fn deref(&self) -> &Self::Target {
-        match *self {
-            AccumulateVec::Array(ref v) => v,
-            AccumulateVec::Heap(ref v) => v,
-        }
-    }
-}
-
-impl<A: Array> DerefMut for AccumulateVec<A> {
-    fn deref_mut(&mut self) -> &mut [A::Element] {
-        match *self {
-            AccumulateVec::Array(ref mut v) => v,
-            AccumulateVec::Heap(ref mut v) => 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();
-        if iter.size_hint().1.map_or(false, |n| n <= A::LEN) {
-            let mut v = ArrayVec::new();
-            v.extend(iter);
-            AccumulateVec::Array(v)
-        } else {
-            AccumulateVec::Heap(iter.collect())
-        }
-    }
-}
-
-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(),
-        }
-    }
-}
-
-pub enum Drain<'a, A: Array>
-        where A::Element: 'a
-{
-    Array(array_vec::Drain<'a, A>),
-    Heap(vec::Drain<'a, A::Element>),
-}
-
-impl<'a, A: Array> Iterator for Drain<'a, A> {
-    type Item = A::Element;
-
-    fn next(&mut self) -> Option<A::Element> {
-        match *self {
-            Drain::Array(ref mut drain) => drain.next(),
-            Drain::Heap(ref mut drain) => drain.next(),
-        }
-    }
-
-    fn size_hint(&self) -> (usize, Option<usize>) {
-        match *self {
-            Drain::Array(ref drain) => drain.size_hint(),
-            Drain::Heap(ref drain) => drain.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() {
-                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| {
-            (0..len).map(|i| d.read_seq_elt(i, |d| Decodable::decode(d))).collect()
-        })
-    }
-}
diff --git a/src/librustc_data_structures/lib.rs b/src/librustc_data_structures/lib.rs
index 936dec92409..7915650fd89 100644
--- a/src/librustc_data_structures/lib.rs
+++ b/src/librustc_data_structures/lib.rs
@@ -61,7 +61,6 @@ extern crate rustc_cratesio_shim;
 pub use rustc_serialize::hex::ToHex;
 
 pub mod svh;
-pub mod accumulate_vec;
 pub mod array_vec;
 pub mod base_n;
 pub mod bitslice;
diff --git a/src/librustc_data_structures/small_vec.rs b/src/librustc_data_structures/small_vec.rs
index e4e6a3d1a9c..075b70c6426 100644
--- a/src/librustc_data_structures/small_vec.rs
+++ b/src/librustc_data_structures/small_vec.rs
@@ -8,11 +8,10 @@
 // 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.
+//! A vector type intended to be used for small vectors.
 //!
-//! 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.
+//! 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.
 //!
 //! The N above is determined by Array's implementor, by way of an associated constant.
 
diff --git a/src/librustc_typeck/Cargo.toml b/src/librustc_typeck/Cargo.toml
index 184cb9826ba..881fa2604bc 100644
--- a/src/librustc_typeck/Cargo.toml
+++ b/src/librustc_typeck/Cargo.toml
@@ -10,12 +10,13 @@ crate-type = ["dylib"]
 test = false
 
 [dependencies]
-log = "0.4"
-syntax = { path = "../libsyntax" }
 arena = { path = "../libarena" }
+log = "0.4"
 rustc = { path = "../librustc" }
 rustc_data_structures = { path = "../librustc_data_structures" }
+rustc_errors = { path = "../librustc_errors" }
 rustc_platform_intrinsics = { path = "../librustc_platform_intrinsics" }
 rustc_target = { path = "../librustc_target" }
+smallvec = { version = "0.6.5", features = ["union"] }
+syntax = { path = "../libsyntax" }
 syntax_pos = { path = "../libsyntax_pos" }
-rustc_errors = { path = "../librustc_errors" }
diff --git a/src/librustc_typeck/astconv.rs b/src/librustc_typeck/astconv.rs
index 3c9452835fd..804aad3c0ec 100644
--- a/src/librustc_typeck/astconv.rs
+++ b/src/librustc_typeck/astconv.rs
@@ -12,8 +12,7 @@
 //! representation.  The main routine here is `ast_ty_to_ty()`: each use
 //! is parameterized by an instance of `AstConv`.
 
-use rustc_data_structures::accumulate_vec::AccumulateVec;
-use rustc_data_structures::array_vec::ArrayVec;
+use smallvec::SmallVec;
 use hir::{self, GenericArg, GenericArgs};
 use hir::def::Def;
 use hir::def_id::DefId;
@@ -431,18 +430,7 @@ impl<'o, 'gcx: 'tcx, 'tcx> dyn AstConv<'gcx, 'tcx>+'o {
         // We manually build up the substitution, rather than using convenience
         // methods in subst.rs so that we can iterate over the arguments and
         // parameters in lock-step linearly, rather than trying to match each pair.
-        let mut substs: AccumulateVec<[Kind<'tcx>; 8]> = if count <= 8 {
-            AccumulateVec::Array(ArrayVec::new())
-        } else {
-            AccumulateVec::Heap(Vec::with_capacity(count))
-        };
-
-        fn push_kind<'tcx>(substs: &mut AccumulateVec<[Kind<'tcx>; 8]>, kind: Kind<'tcx>) {
-            match substs {
-                AccumulateVec::Array(ref mut arr) => arr.push(kind),
-                AccumulateVec::Heap(ref mut vec) => vec.push(kind),
-            }
-        }
+        let mut substs: SmallVec<[Kind<'tcx>; 8]> = SmallVec::with_capacity(count);
 
         // Iterate over each segment of the path.
         while let Some((def_id, defs)) = stack.pop() {
@@ -451,7 +439,7 @@ impl<'o, 'gcx: 'tcx, 'tcx> dyn AstConv<'gcx, 'tcx>+'o {
             // If we have already computed substitutions for parents, we can use those directly.
             while let Some(&param) = params.peek() {
                 if let Some(&kind) = parent_substs.get(param.index as usize) {
-                    push_kind(&mut substs, kind);
+                    substs.push(kind);
                     params.next();
                 } else {
                     break;
@@ -463,7 +451,7 @@ impl<'o, 'gcx: 'tcx, 'tcx> dyn AstConv<'gcx, 'tcx>+'o {
                 if let Some(&param) = params.peek() {
                     if param.index == 0 {
                         if let GenericParamDefKind::Type { .. } = param.kind {
-                            push_kind(&mut substs, self_ty.map(|ty| ty.into())
+                            substs.push(self_ty.map(|ty| ty.into())
                                 .unwrap_or_else(|| inferred_kind(None, param, true)));
                             params.next();
                         }
@@ -487,7 +475,7 @@ impl<'o, 'gcx: 'tcx, 'tcx> dyn AstConv<'gcx, 'tcx>+'o {
                         match (arg, &param.kind) {
                             (GenericArg::Lifetime(_), GenericParamDefKind::Lifetime)
                             | (GenericArg::Type(_), GenericParamDefKind::Type { .. }) => {
-                                push_kind(&mut substs, provided_kind(param, arg));
+                                substs.push(provided_kind(param, arg));
                                 args.next();
                                 params.next();
                             }
@@ -501,7 +489,7 @@ impl<'o, 'gcx: 'tcx, 'tcx> dyn AstConv<'gcx, 'tcx>+'o {
                             (GenericArg::Type(_), GenericParamDefKind::Lifetime) => {
                                 // We expected a lifetime argument, but got a type
                                 // argument. That means we're inferring the lifetimes.
-                                push_kind(&mut substs, inferred_kind(None, param, infer_types));
+                                substs.push(inferred_kind(None, param, infer_types));
                                 params.next();
                             }
                         }
@@ -518,7 +506,7 @@ impl<'o, 'gcx: 'tcx, 'tcx> dyn AstConv<'gcx, 'tcx>+'o {
                         match param.kind {
                             GenericParamDefKind::Lifetime | GenericParamDefKind::Type { .. } => {
                                 let kind = inferred_kind(Some(&substs), param, infer_types);
-                                push_kind(&mut substs, kind);
+                                substs.push(kind);
                             }
                         }
                         args.next();
@@ -1041,7 +1029,7 @@ impl<'o, 'gcx: 'tcx, 'tcx> dyn AstConv<'gcx, 'tcx>+'o {
             .chain(auto_traits.into_iter().map(ty::ExistentialPredicate::AutoTrait))
             .chain(existential_projections
                    .map(|x| ty::ExistentialPredicate::Projection(*x.skip_binder())))
-            .collect::<AccumulateVec<[_; 8]>>();
+            .collect::<SmallVec<[_; 8]>>();
         v.sort_by(|a, b| a.stable_cmp(tcx, b));
         let existential_predicates = ty::Binder::bind(tcx.mk_existential_predicates(v.into_iter()));
 
diff --git a/src/librustc_typeck/lib.rs b/src/librustc_typeck/lib.rs
index e31ae8eb8c7..f465ff4d621 100644
--- a/src/librustc_typeck/lib.rs
+++ b/src/librustc_typeck/lib.rs
@@ -96,6 +96,7 @@ extern crate rustc_platform_intrinsics as intrinsics;
 extern crate rustc_data_structures;
 extern crate rustc_errors as errors;
 extern crate rustc_target;
+extern crate smallvec;
 
 use rustc::hir;
 use rustc::lint;