Auto merge of #53384 - gootorov:use-servo-smallvec, r=michaelwoerister

Use optimized SmallVec implementation

This PR replaces current SmallVec implementation with the one from the Servo project.

Closes https://github.com/rust-lang/rust/issues/51640

r? @Mark-Simulacrum

46 files changed, 156 insertions, 434 deletions

diff --git a/src/Cargo.lock b/src/Cargo.lock
index eabd26c6e67..62e7a58cd36 100644
--- a/src/Cargo.lock
+++ b/src/Cargo.lock
@@ -554,7 +554,7 @@ dependencies = [
  "crossbeam-utils 0.4.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "parking_lot 0.5.5 (registry+https://github.com/rust-lang/crates.io-index)",
  "rand 0.5.4 (registry+https://github.com/rust-lang/crates.io-index)",
- "smallvec 0.6.3 (registry+https://github.com/rust-lang/crates.io-index)",
+ "smallvec 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
@@ -1488,7 +1488,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "libc 0.2.43 (registry+https://github.com/rust-lang/crates.io-index)",
  "rand 0.4.2 (registry+https://github.com/rust-lang/crates.io-index)",
- "smallvec 0.6.3 (registry+https://github.com/rust-lang/crates.io-index)",
+ "smallvec 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)",
  "winapi 0.3.5 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
@@ -1925,6 +1925,7 @@ dependencies = [
  "rustc_target 0.0.0",
  "scoped-tls 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "serialize 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",
  "tempfile 3.0.2 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -2086,6 +2087,7 @@ dependencies = [
  "rustc_data_structures 0.0.0",
  "rustc_errors 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",
 ]
@@ -2172,6 +2174,7 @@ dependencies = [
  "rustc-rayon-core 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "rustc_cratesio_shim 0.0.0",
  "serialize 0.0.0",
+ "smallvec 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)",
  "stable_deref_trait 1.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
@@ -2317,6 +2320,7 @@ dependencies = [
  "rustc_errors 0.0.0",
  "rustc_target 0.0.0",
  "serialize 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",
 ]
@@ -2422,6 +2426,7 @@ dependencies = [
  "log 0.4.3 (registry+https://github.com/rust-lang/crates.io-index)",
  "rustc 0.0.0",
  "rustc_data_structures 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",
 ]
@@ -2597,6 +2602,9 @@ dependencies = [
 [[package]]
 name = "serialize"
 version = "0.0.0"
+dependencies = [
+ "smallvec 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)",
+]
 
 [[package]]
 name = "shell-escape"
@@ -2615,7 +2623,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
 name = "smallvec"
-version = "0.6.3"
+version = "0.6.5"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "unreachable 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -2771,6 +2779,7 @@ dependencies = [
  "rustc_target 0.0.0",
  "scoped-tls 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "serialize 0.0.0",
+ "smallvec 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)",
  "syntax_pos 0.0.0",
 ]
 
@@ -2783,6 +2792,7 @@ dependencies = [
  "rustc_data_structures 0.0.0",
  "rustc_errors 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",
 ]
@@ -3327,7 +3337,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 "checksum shell-escape 0.1.4 (registry+https://github.com/rust-lang/crates.io-index)" = "170a13e64f2a51b77a45702ba77287f5c6829375b04a69cf2222acd17d0cfab9"
 "checksum shlex 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "7fdf1b9db47230893d76faad238fd6097fd6d6a9245cd7a4d90dbd639536bbd2"
 "checksum siphasher 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)" = "0df90a788073e8d0235a67e50441d47db7c8ad9debd91cbf43736a2a92d36537"
-"checksum smallvec 0.6.3 (registry+https://github.com/rust-lang/crates.io-index)" = "26df3bb03ca5eac2e64192b723d51f56c1b1e0860e7c766281f4598f181acdc8"
+"checksum smallvec 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)" = "153ffa32fd170e9944f7e0838edf824a754ec4c1fc64746fcc9fe1f8fa602e5d"
 "checksum socket2 0.3.7 (registry+https://github.com/rust-lang/crates.io-index)" = "962a516af4d3a7c272cb3a1d50a8cc4e5b41802e4ad54cfb7bee8ba61d37d703"
 "checksum stable_deref_trait 1.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "ffbc596e092fe5f598b12ef46cc03754085ac2f4d8c739ad61c4ae266cc3b3fa"
 "checksum string_cache 0.7.3 (registry+https://github.com/rust-lang/crates.io-index)" = "25d70109977172b127fe834e5449e5ab1740b9ba49fa18a2020f509174f25423"
diff --git a/src/librustc/Cargo.toml b/src/librustc/Cargo.toml
index 59b5b58e61e..fc5d4a9c923 100644
--- a/src/librustc/Cargo.toml
+++ b/src/librustc/Cargo.toml
@@ -33,6 +33,7 @@ parking_lot = "0.5.5"
 byteorder = { version = "1.1", features = ["i128"]}
 chalk-engine = { version = "0.7.0", default-features=false }
 rustc_fs_util = { path = "../librustc_fs_util" }
+smallvec = { version = "0.6.5", features = ["union"] }
 
 # Note that these dependencies are a lie, they're just here to get linkage to
 # work.
diff --git a/src/librustc/dep_graph/graph.rs b/src/librustc/dep_graph/graph.rs
index e308f2924a0..a2853996571 100644
--- a/src/librustc/dep_graph/graph.rs
+++ b/src/librustc/dep_graph/graph.rs
@@ -12,7 +12,7 @@ use errors::DiagnosticBuilder;
 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
 use rustc_data_structures::indexed_vec::{Idx, IndexVec};
-use rustc_data_structures::small_vec::SmallVec;
+use smallvec::SmallVec;
 use rustc_data_structures::sync::{Lrc, Lock};
 use std::env;
 use std::hash::Hash;
@@ -1025,7 +1025,7 @@ impl CurrentDepGraph {
         } = task {
             debug_assert_eq!(node, key);
             let krate_idx = self.node_to_node_index[&DepNode::new_no_params(DepKind::Krate)];
-            self.alloc_node(node, SmallVec::one(krate_idx))
+            self.alloc_node(node, smallvec![krate_idx])
         } else {
             bug!("complete_eval_always_task() - Expected eval always task to be popped");
         }
diff --git a/src/librustc/hir/lowering.rs b/src/librustc/hir/lowering.rs
index acfda4c0055..cb05f7b44c3 100644
--- a/src/librustc/hir/lowering.rs
+++ b/src/librustc/hir/lowering.rs
@@ -3178,18 +3178,18 @@ impl<'a> LoweringContext<'a> {
     fn lower_item_id(&mut self, i: &Item) -> OneVector<hir::ItemId> {
         match i.node {
             ItemKind::Use(ref use_tree) => {
-                let mut vec = OneVector::one(hir::ItemId { id: i.id });
+                let mut vec = smallvec![hir::ItemId { id: i.id }];
                 self.lower_item_id_use_tree(use_tree, i.id, &mut vec);
                 vec
             }
             ItemKind::MacroDef(..) => OneVector::new(),
             ItemKind::Fn(ref decl, ref header, ..) => {
-                let mut ids = OneVector::one(hir::ItemId { id: i.id });
+                let mut ids = smallvec![hir::ItemId { id: i.id }];
                 self.lower_impl_trait_ids(decl, header, &mut ids);
                 ids
             },
             ItemKind::Impl(.., None, _, ref items) => {
-                let mut ids = OneVector::one(hir::ItemId { id: i.id });
+                let mut ids = smallvec![hir::ItemId { id: i.id }];
                 for item in items {
                     if let ImplItemKind::Method(ref sig, _) = item.node {
                         self.lower_impl_trait_ids(&sig.decl, &sig.header, &mut ids);
@@ -3197,7 +3197,7 @@ impl<'a> LoweringContext<'a> {
                 }
                 ids
             },
-            _ => OneVector::one(hir::ItemId { id: i.id }),
+            _ => smallvec![hir::ItemId { id: i.id }],
         }
     }
 
@@ -4297,7 +4297,7 @@ impl<'a> LoweringContext<'a> {
     }
 
     fn lower_stmt(&mut self, s: &Stmt) -> OneVector<hir::Stmt> {
-        OneVector::one(match s.node {
+        smallvec![match s.node {
             StmtKind::Local(ref l) => Spanned {
                 node: hir::StmtKind::Decl(
                     P(Spanned {
@@ -4336,7 +4336,7 @@ impl<'a> LoweringContext<'a> {
                 span: s.span,
             },
             StmtKind::Mac(..) => panic!("Shouldn't exist here"),
-        })
+        }]
     }
 
     fn lower_capture_clause(&mut self, c: CaptureBy) -> hir::CaptureClause {
diff --git a/src/librustc/infer/canonical/canonicalizer.rs b/src/librustc/infer/canonical/canonicalizer.rs
index 16c33e9adf8..fbe9165ae97 100644
--- a/src/librustc/infer/canonical/canonicalizer.rs
+++ b/src/librustc/infer/canonical/canonicalizer.rs
@@ -27,7 +27,7 @@ use ty::{self, CanonicalVar, Lift, List, Ty, TyCtxt, TypeFlags};
 
 use rustc_data_structures::fx::FxHashMap;
 use rustc_data_structures::indexed_vec::Idx;
-use rustc_data_structures::small_vec::SmallVec;
+use smallvec::SmallVec;
 
 impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
     /// Canonicalizes a query value `V`. When we canonicalize a query,
@@ -380,7 +380,7 @@ impl<'cx, 'gcx, 'tcx> Canonicalizer<'cx, 'gcx, 'tcx> {
         // avoid allocations in those cases. We also don't use `indices` to
         // determine if a kind has been seen before until the limit of 8 has
         // been exceeded, to also avoid allocations for `indices`.
-        if var_values.is_array() {
+        if !var_values.spilled() {
             // `var_values` is stack-allocated. `indices` isn't used yet. Do a
             // direct linear search of `var_values`.
             if let Some(idx) = var_values.iter().position(|&k| k == kind) {
@@ -395,7 +395,7 @@ impl<'cx, 'gcx, 'tcx> Canonicalizer<'cx, 'gcx, 'tcx> {
 
                 // If `var_values` has become big enough to be heap-allocated,
                 // fill up `indices` to facilitate subsequent lookups.
-                if !var_values.is_array() {
+                if var_values.spilled() {
                     assert!(indices.is_empty());
                     *indices =
                         var_values.iter()
diff --git a/src/librustc/infer/canonical/mod.rs b/src/librustc/infer/canonical/mod.rs
index cb1e39bb9f7..2e57ef7b17d 100644
--- a/src/librustc/infer/canonical/mod.rs
+++ b/src/librustc/infer/canonical/mod.rs
@@ -33,7 +33,7 @@
 
 use infer::{InferCtxt, RegionVariableOrigin, TypeVariableOrigin};
 use rustc_data_structures::indexed_vec::IndexVec;
-use rustc_data_structures::small_vec::SmallVec;
+use smallvec::SmallVec;
 use rustc_data_structures::sync::Lrc;
 use serialize::UseSpecializedDecodable;
 use std::ops::Index;
diff --git a/src/librustc/lib.rs b/src/librustc/lib.rs
index a232bcd6710..d43ebf8d415 100644
--- a/src/librustc/lib.rs
+++ b/src/librustc/lib.rs
@@ -108,6 +108,9 @@ extern crate rustc_apfloat;
 extern crate byteorder;
 extern crate backtrace;
 
+#[macro_use]
+extern crate smallvec;
+
 // Note that librustc doesn't actually depend on these crates, see the note in
 // `Cargo.toml` for this crate about why these are here.
 #[allow(unused_extern_crates)]
diff --git a/src/librustc/mir/mod.rs b/src/librustc/mir/mod.rs
index 66a42cfb11a..14981a700a3 100644
--- a/src/librustc/mir/mod.rs
+++ b/src/librustc/mir/mod.rs
@@ -24,7 +24,7 @@ use rustc_apfloat::Float;
 use rustc_data_structures::graph::dominators::{dominators, Dominators};
 use rustc_data_structures::graph::{self, GraphPredecessors, GraphSuccessors};
 use rustc_data_structures::indexed_vec::{Idx, IndexVec};
-use rustc_data_structures::small_vec::SmallVec;
+use smallvec::SmallVec;
 use rustc_data_structures::sync::Lrc;
 use rustc_data_structures::sync::ReadGuard;
 use rustc_serialize as serialize;
diff --git a/src/librustc/traits/query/dropck_outlives.rs b/src/librustc/traits/query/dropck_outlives.rs
index b479cafd1ce..3a0f7700824 100644
--- a/src/librustc/traits/query/dropck_outlives.rs
+++ b/src/librustc/traits/query/dropck_outlives.rs
@@ -10,7 +10,7 @@
 
 use infer::at::At;
 use infer::InferOk;
-use rustc_data_structures::small_vec::SmallVec;
+use smallvec::SmallVec;
 use std::iter::FromIterator;
 use syntax::source_map::Span;
 use ty::subst::Kind;
diff --git a/src/librustc/traits/query/evaluate_obligation.rs b/src/librustc/traits/query/evaluate_obligation.rs
index 93fcadceb16..6bd92678362 100644
--- a/src/librustc/traits/query/evaluate_obligation.rs
+++ b/src/librustc/traits/query/evaluate_obligation.rs
@@ -9,7 +9,7 @@
 // except according to those terms.
 
 use infer::InferCtxt;
-use rustc_data_structures::small_vec::SmallVec;
+use smallvec::SmallVec;
 use traits::{EvaluationResult, PredicateObligation, SelectionContext,
              TraitQueryMode, OverflowError};
 
diff --git a/src/librustc/traits/query/normalize.rs b/src/librustc/traits/query/normalize.rs
index 7b81989c641..f8b3933e2a1 100644
--- a/src/librustc/traits/query/normalize.rs
+++ b/src/librustc/traits/query/normalize.rs
@@ -15,7 +15,7 @@
 use infer::at::At;
 use infer::{InferCtxt, InferOk};
 use mir::interpret::{ConstValue, GlobalId};
-use rustc_data_structures::small_vec::SmallVec;
+use smallvec::SmallVec;
 use traits::project::Normalized;
 use traits::{Obligation, ObligationCause, PredicateObligation, Reveal};
 use ty::fold::{TypeFoldable, TypeFolder};
diff --git a/src/librustc/traits/query/outlives_bounds.rs b/src/librustc/traits/query/outlives_bounds.rs
index 868b8dfc885..47c8ee357fb 100644
--- a/src/librustc/traits/query/outlives_bounds.rs
+++ b/src/librustc/traits/query/outlives_bounds.rs
@@ -11,7 +11,7 @@
 use infer::InferCtxt;
 use syntax::ast;
 use syntax::source_map::Span;
-use rustc_data_structures::small_vec::SmallVec;
+use smallvec::SmallVec;
 use traits::{FulfillmentContext, ObligationCause, TraitEngine, TraitEngineExt};
 use traits::query::NoSolution;
 use ty::{self, Ty, TyCtxt};
diff --git a/src/librustc/traits/query/type_op/mod.rs b/src/librustc/traits/query/type_op/mod.rs
index be5e2838963..3b16dab22f2 100644
--- a/src/librustc/traits/query/type_op/mod.rs
+++ b/src/librustc/traits/query/type_op/mod.rs
@@ -11,7 +11,7 @@
 use infer::canonical::{Canonical, Canonicalized, CanonicalizedQueryResult, QueryRegionConstraint,
                        QueryResult};
 use infer::{InferCtxt, InferOk};
-use rustc_data_structures::small_vec::SmallVec;
+use smallvec::SmallVec;
 use std::fmt;
 use std::rc::Rc;
 use traits::query::Fallible;
diff --git a/src/librustc/ty/inhabitedness/def_id_forest.rs b/src/librustc/ty/inhabitedness/def_id_forest.rs
index 3629709e6a4..c152c0fb8e9 100644
--- a/src/librustc/ty/inhabitedness/def_id_forest.rs
+++ b/src/librustc/ty/inhabitedness/def_id_forest.rs
@@ -9,7 +9,7 @@
 // except according to those terms.
 
 use std::mem;
-use rustc_data_structures::small_vec::SmallVec;
+use smallvec::SmallVec;
 use syntax::ast::CRATE_NODE_ID;
 use ty::context::TyCtxt;
 use ty::{DefId, DefIdTree};
@@ -83,14 +83,14 @@ impl<'a, 'gcx, 'tcx> DefIdForest {
         let mut next_ret = SmallVec::new();
         let mut old_ret: SmallVec<[DefId; 1]> = SmallVec::new();
         for next_forest in iter {
-            for id in ret.root_ids.drain(..) {
+            for id in ret.root_ids.drain() {
                 if next_forest.contains(tcx, id) {
                     next_ret.push(id);
                 } else {
                     old_ret.push(id);
                 }
             }
-            ret.root_ids.extend(old_ret.drain(..));
+            ret.root_ids.extend(old_ret.drain());
 
             for id in next_forest.root_ids {
                 if ret.contains(tcx, id) {
@@ -99,7 +99,7 @@ impl<'a, 'gcx, 'tcx> DefIdForest {
             }
 
             mem::swap(&mut next_ret, &mut ret.root_ids);
-            next_ret.drain(..);
+            next_ret.drain();
         }
         ret
     }
@@ -112,7 +112,7 @@ impl<'a, 'gcx, 'tcx> DefIdForest {
         let mut ret = DefIdForest::empty();
         let mut next_ret = SmallVec::new();
         for next_forest in iter {
-            for id in ret.root_ids.drain(..) {
+            for id in ret.root_ids.drain() {
                 if !next_forest.contains(tcx, id) {
                     next_ret.push(id);
                 }
@@ -125,7 +125,7 @@ impl<'a, 'gcx, 'tcx> DefIdForest {
             }
 
             mem::swap(&mut next_ret, &mut ret.root_ids);
-            next_ret.drain(..);
+            next_ret.drain();
         }
         ret
     }
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index 8d5006d17b3..77b4d32c397 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -55,7 +55,7 @@ use syntax::ext::hygiene::Mark;
 use syntax::symbol::{keywords, Symbol, LocalInternedString, InternedString};
 use syntax_pos::{DUMMY_SP, Span};
 
-use rustc_data_structures::accumulate_vec::IntoIter as AccIntoIter;
+use smallvec;
 use rustc_data_structures::stable_hasher::{StableHasher, StableHasherResult,
                                            HashStable};
 
@@ -2382,7 +2382,7 @@ impl<'tcx> TyS<'tcx> {
     /// Iterator that walks the immediate children of `self`.  Hence
     /// `Foo<Bar<i32>, u32>` yields the sequence `[Bar<i32>, u32]`
     /// (but not `i32`, like `walk`).
-    pub fn walk_shallow(&'tcx self) -> AccIntoIter<walk::TypeWalkerArray<'tcx>> {
+    pub fn walk_shallow(&'tcx self) -> smallvec::IntoIter<walk::TypeWalkerArray<'tcx>> {
         walk::walk_shallow(self)
     }
 
diff --git a/src/librustc/ty/walk.rs b/src/librustc/ty/walk.rs
index e2df7c32f58..6d3ba22c57f 100644
--- a/src/librustc/ty/walk.rs
+++ b/src/librustc/ty/walk.rs
@@ -13,8 +13,7 @@
 
 use mir::interpret::ConstValue;
 use ty::{self, Ty};
-use rustc_data_structures::small_vec::SmallVec;
-use rustc_data_structures::accumulate_vec::IntoIter as AccIntoIter;
+use smallvec::{self, SmallVec};
 
 // The TypeWalker's stack is hot enough that it's worth going to some effort to
 // avoid heap allocations.
@@ -28,7 +27,7 @@ pub struct TypeWalker<'tcx> {
 
 impl<'tcx> TypeWalker<'tcx> {
     pub fn new(ty: Ty<'tcx>) -> TypeWalker<'tcx> {
-        TypeWalker { stack: SmallVec::one(ty), last_subtree: 1, }
+        TypeWalker { stack: smallvec![ty], last_subtree: 1, }
     }
 
     /// Skips the subtree of types corresponding to the last type
@@ -67,7 +66,7 @@ impl<'tcx> Iterator for TypeWalker<'tcx> {
     }
 }
 
-pub fn walk_shallow<'tcx>(ty: Ty<'tcx>) -> AccIntoIter<TypeWalkerArray<'tcx>> {
+pub fn walk_shallow<'tcx>(ty: Ty<'tcx>) -> smallvec::IntoIter<TypeWalkerArray<'tcx>> {
     let mut stack = SmallVec::new();
     push_subtypes(&mut stack, ty);
     stack.into_iter()
diff --git a/src/librustc_allocator/Cargo.toml b/src/librustc_allocator/Cargo.toml
index 83a918f2af8..cd3ef6a1f04 100644
--- a/src/librustc_allocator/Cargo.toml
+++ b/src/librustc_allocator/Cargo.toml
@@ -16,3 +16,4 @@ rustc_target = { path = "../librustc_target" }
 syntax = { path = "../libsyntax" }
 syntax_pos = { path = "../libsyntax_pos" }
 log = "0.4"
+smallvec = { version = "0.6.5", features = ["union"] }
diff --git a/src/librustc_allocator/expand.rs b/src/librustc_allocator/expand.rs
index da60f41ee68..5999416cecf 100644
--- a/src/librustc_allocator/expand.rs
+++ b/src/librustc_allocator/expand.rs
@@ -78,20 +78,20 @@ impl<'a> Folder for ExpandAllocatorDirectives<'a> {
             _ => {
                 self.handler
                     .span_err(item.span, "allocators must be statics");
-                return OneVector::one(item);
+                return smallvec![item];
             }
         }
 
         if self.in_submod > 0 {
             self.handler
                 .span_err(item.span, "`global_allocator` cannot be used in submodules");
-            return OneVector::one(item);
+            return smallvec![item];
         }
 
         if self.found {
             self.handler
                 .span_err(item.span, "cannot define more than one #[global_allocator]");
-            return OneVector::one(item);
+            return smallvec![item];
         }
         self.found = true;
 
diff --git a/src/librustc_allocator/lib.rs b/src/librustc_allocator/lib.rs
index d020fe96335..2a3404ee830 100644
--- a/src/librustc_allocator/lib.rs
+++ b/src/librustc_allocator/lib.rs
@@ -18,6 +18,8 @@ extern crate rustc_errors;
 extern crate rustc_target;
 extern crate syntax;
 extern crate syntax_pos;
+#[macro_use]
+extern crate smallvec;
 
 pub mod expand;
 
diff --git a/src/librustc_data_structures/Cargo.toml b/src/librustc_data_structures/Cargo.toml
index fc5fe91c977..0376cf81157 100644
--- a/src/librustc_data_structures/Cargo.toml
+++ b/src/librustc_data_structures/Cargo.toml
@@ -19,6 +19,7 @@ parking_lot_core = "0.2.8"
 rustc-rayon = "0.1.1"
 rustc-rayon-core = "0.1.1"
 rustc-hash = "1.0.1"
+smallvec = { version = "0.6.5", features = ["union"] }
 
 [dependencies.parking_lot]
 version = "0.5"
diff --git a/src/librustc_data_structures/lib.rs b/src/librustc_data_structures/lib.rs
index c3ee48d20f6..1eef7870c01 100644
--- a/src/librustc_data_structures/lib.rs
+++ b/src/librustc_data_structures/lib.rs
@@ -48,6 +48,8 @@ extern crate rustc_rayon as rayon;
 extern crate rustc_rayon_core as rayon_core;
 extern crate rustc_hash;
 extern crate serialize;
+#[cfg_attr(test, macro_use)]
+extern crate smallvec;
 
 // See librustc_cratesio_shim/Cargo.toml for a comment explaining this.
 #[allow(unused_extern_crates)]
diff --git a/src/librustc_data_structures/small_vec.rs b/src/librustc_data_structures/small_vec.rs
index 689aad25b43..e4e6a3d1a9c 100644
--- a/src/librustc_data_structures/small_vec.rs
+++ b/src/librustc_data_structures/small_vec.rs
@@ -16,265 +16,27 @@
 //!
 //! The N above is determined by Array's implementor, by way of an associated 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>);
+use smallvec::{Array, SmallVec};
 
 pub type OneVector<T> = SmallVec<[T; 1]>;
 
-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()
-    }
+pub trait ExpectOne<A: Array> {
+    fn expect_one(self, err: &'static str) -> A::Item;
 }
 
-impl<A: Array> SmallVec<A> {
-    pub fn new() -> Self {
-        SmallVec(AccumulateVec::new())
-    }
-
-    pub fn is_array(&self) -> bool {
-        self.0.is_array()
-    }
-
-    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 {
+impl<A: Array> ExpectOne<A> for SmallVec<A> {
+    fn expect_one(self, err: &'static str) -> A::Item {
         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().add(index);
-                // 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);
-        }
-    }
-
-    pub fn truncate(&mut self, len: usize) {
-        unsafe {
-            while len < self.len() {
-                // Decrement len before the drop_in_place(), so a panic on Drop
-                // doesn't re-drop the just-failed value.
-                let newlen = self.len() - 1;
-                self.set_len(newlen);
-                ::std::ptr::drop_in_place(self.get_unchecked_mut(newlen));
-            }
-        }
-    }
-}
-
-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);
-        match self.0 {
-            AccumulateVec::Heap(ref mut vec) => vec.extend(iter),
-            _ => iter.for_each(|el| 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() {
-                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);
-            // FIXME(#48994) - could just be collected into a Result<SmallVec, D::Error>
-            for i in 0..len {
-                vec.push(d.read_seq_elt(i, |d| Decodable::decode(d))?);
-            }
-            Ok(vec)
-        })
+        self.into_iter().next().unwrap()
     }
 }
 
 #[cfg(test)]
 mod tests {
     extern crate test;
-    use self::test::Bencher;
-
     use super::*;
 
     #[test]
-    fn test_len() {
-        let v: OneVector<isize> = OneVector::new();
-        assert_eq!(0, v.len());
-
-        assert_eq!(1, OneVector::one(1).len());
-        assert_eq!(5, OneVector::many(vec![1, 2, 3, 4, 5]).len());
-    }
-
-    #[test]
-    fn test_push_get() {
-        let mut v = OneVector::new();
-        v.push(1);
-        assert_eq!(1, v.len());
-        assert_eq!(1, v[0]);
-        v.push(2);
-        assert_eq!(2, v.len());
-        assert_eq!(2, v[1]);
-        v.push(3);
-        assert_eq!(3, v.len());
-        assert_eq!(3, v[2]);
-    }
-
-    #[test]
-    fn test_from_iter() {
-        let v: OneVector<isize> = (vec![1, 2, 3]).into_iter().collect();
-        assert_eq!(3, v.len());
-        assert_eq!(1, v[0]);
-        assert_eq!(2, v[1]);
-        assert_eq!(3, v[2]);
-    }
-
-    #[test]
-    fn test_move_iter() {
-        let v = OneVector::new();
-        let v: Vec<isize> = v.into_iter().collect();
-        assert_eq!(v, Vec::new());
-
-        let v = OneVector::one(1);
-        assert_eq!(v.into_iter().collect::<Vec<_>>(), [1]);
-
-        let v = OneVector::many(vec![1, 2, 3]);
-        assert_eq!(v.into_iter().collect::<Vec<_>>(), [1, 2, 3]);
-    }
-
-    #[test]
     #[should_panic]
     fn test_expect_one_zero() {
         let _: isize = OneVector::new().expect_one("");
@@ -283,120 +45,12 @@ mod tests {
     #[test]
     #[should_panic]
     fn test_expect_one_many() {
-        OneVector::many(vec![1, 2]).expect_one("");
+        OneVector::from_vec(vec![1, 2]).expect_one("");
     }
 
     #[test]
     fn test_expect_one_one() {
-        assert_eq!(1, OneVector::one(1).expect_one(""));
-        assert_eq!(1, OneVector::many(vec![1]).expect_one(""));
-    }
-
-    #[bench]
-    fn fill_small_vec_1_10_with_cap(b: &mut Bencher) {
-        b.iter(|| {
-            let mut sv: SmallVec<[usize; 1]> = SmallVec::with_capacity(10);
-
-            sv.extend(0..10);
-        })
-    }
-
-    #[bench]
-    fn fill_small_vec_1_10_wo_cap(b: &mut Bencher) {
-        b.iter(|| {
-            let mut sv: SmallVec<[usize; 1]> = SmallVec::new();
-
-            sv.extend(0..10);
-        })
-    }
-
-    #[bench]
-    fn fill_small_vec_8_10_with_cap(b: &mut Bencher) {
-        b.iter(|| {
-            let mut sv: SmallVec<[usize; 8]> = SmallVec::with_capacity(10);
-
-            sv.extend(0..10);
-        })
-    }
-
-    #[bench]
-    fn fill_small_vec_8_10_wo_cap(b: &mut Bencher) {
-        b.iter(|| {
-            let mut sv: SmallVec<[usize; 8]> = SmallVec::new();
-
-            sv.extend(0..10);
-        })
-    }
-
-    #[bench]
-    fn fill_small_vec_32_10_with_cap(b: &mut Bencher) {
-        b.iter(|| {
-            let mut sv: SmallVec<[usize; 32]> = SmallVec::with_capacity(10);
-
-            sv.extend(0..10);
-        })
-    }
-
-    #[bench]
-    fn fill_small_vec_32_10_wo_cap(b: &mut Bencher) {
-        b.iter(|| {
-            let mut sv: SmallVec<[usize; 32]> = SmallVec::new();
-
-            sv.extend(0..10);
-        })
-    }
-
-    #[bench]
-    fn fill_small_vec_1_50_with_cap(b: &mut Bencher) {
-        b.iter(|| {
-            let mut sv: SmallVec<[usize; 1]> = SmallVec::with_capacity(50);
-
-            sv.extend(0..50);
-        })
-    }
-
-    #[bench]
-    fn fill_small_vec_1_50_wo_cap(b: &mut Bencher) {
-        b.iter(|| {
-            let mut sv: SmallVec<[usize; 1]> = SmallVec::new();
-
-            sv.extend(0..50);
-        })
-    }
-
-    #[bench]
-    fn fill_small_vec_8_50_with_cap(b: &mut Bencher) {
-        b.iter(|| {
-            let mut sv: SmallVec<[usize; 8]> = SmallVec::with_capacity(50);
-
-            sv.extend(0..50);
-        })
-    }
-
-    #[bench]
-    fn fill_small_vec_8_50_wo_cap(b: &mut Bencher) {
-        b.iter(|| {
-            let mut sv: SmallVec<[usize; 8]> = SmallVec::new();
-
-            sv.extend(0..50);
-        })
-    }
-
-    #[bench]
-    fn fill_small_vec_32_50_with_cap(b: &mut Bencher) {
-        b.iter(|| {
-            let mut sv: SmallVec<[usize; 32]> = SmallVec::with_capacity(50);
-
-            sv.extend(0..50);
-        })
-    }
-
-    #[bench]
-    fn fill_small_vec_32_50_wo_cap(b: &mut Bencher) {
-        b.iter(|| {
-            let mut sv: SmallVec<[usize; 32]> = SmallVec::new();
-
-            sv.extend(0..50);
-        })
+        assert_eq!(1, (smallvec![1] as OneVector<_>).expect_one(""));
+        assert_eq!(1, OneVector::from_vec(vec![1]).expect_one(""));
     }
 }
diff --git a/src/librustc_mir/Cargo.toml b/src/librustc_mir/Cargo.toml
index 0fd1f92a516..2da0ede9d15 100644
--- a/src/librustc_mir/Cargo.toml
+++ b/src/librustc_mir/Cargo.toml
@@ -25,3 +25,4 @@ syntax = { path = "../libsyntax" }
 syntax_pos = { path = "../libsyntax_pos" }
 byteorder = { version = "1.1", features = ["i128"] }
 rustc_apfloat = { path = "../librustc_apfloat" }
+smallvec = { version = "0.6.5", features = ["union"] }
diff --git a/src/librustc_mir/borrow_check/mod.rs b/src/librustc_mir/borrow_check/mod.rs
index f96f6127349..70b6c8f2580 100644
--- a/src/librustc_mir/borrow_check/mod.rs
+++ b/src/librustc_mir/borrow_check/mod.rs
@@ -29,7 +29,7 @@ use rustc_data_structures::graph::dominators::Dominators;
 use rustc_data_structures::fx::FxHashSet;
 use rustc_data_structures::indexed_set::IdxSet;
 use rustc_data_structures::indexed_vec::Idx;
-use rustc_data_structures::small_vec::SmallVec;
+use smallvec::SmallVec;
 
 use std::rc::Rc;
 
diff --git a/src/librustc_mir/lib.rs b/src/librustc_mir/lib.rs
index 6a8157df0cc..617efed31d9 100644
--- a/src/librustc_mir/lib.rs
+++ b/src/librustc_mir/lib.rs
@@ -61,6 +61,7 @@ extern crate log_settings;
 extern crate rustc_apfloat;
 extern crate byteorder;
 extern crate core;
+extern crate smallvec;
 
 // Once we can use edition 2018 in the compiler,
 // replace this with real try blocks.
diff --git a/src/librustc_resolve/macros.rs b/src/librustc_resolve/macros.rs
index 0e843ae66da..879b4ea3fe5 100644
--- a/src/librustc_resolve/macros.rs
+++ b/src/librustc_resolve/macros.rs
@@ -43,6 +43,7 @@ use errors::Applicability;
 use std::cell::Cell;
 use std::mem;
 use rustc_data_structures::sync::Lrc;
+use rustc_data_structures::small_vec::ExpectOne;
 
 crate struct FromPrelude(bool);
 crate struct FromExpansion(bool);
diff --git a/src/librustc_traits/Cargo.toml b/src/librustc_traits/Cargo.toml
index 3e1a6ca9aff..cd21ee601a7 100644
--- a/src/librustc_traits/Cargo.toml
+++ b/src/librustc_traits/Cargo.toml
@@ -17,3 +17,4 @@ rustc_data_structures = { path = "../librustc_data_structures" }
 syntax = { path = "../libsyntax" }
 syntax_pos = { path = "../libsyntax_pos" }
 chalk-engine = { version = "0.7.0", default-features=false }
+smallvec = { version = "0.6.5", features = ["union"] }
diff --git a/src/librustc_traits/chalk_context.rs b/src/librustc_traits/chalk_context.rs
index 4227144e204..4c28df97bdf 100644
--- a/src/librustc_traits/chalk_context.rs
+++ b/src/librustc_traits/chalk_context.rs
@@ -25,7 +25,7 @@ use rustc::traits::{
 use rustc::ty::fold::{TypeFoldable, TypeFolder, TypeVisitor};
 use rustc::ty::subst::Kind;
 use rustc::ty::{self, TyCtxt};
-use rustc_data_structures::small_vec::SmallVec;
+use smallvec::SmallVec;
 
 use std::fmt::{self, Debug};
 use std::marker::PhantomData;
diff --git a/src/librustc_traits/lib.rs b/src/librustc_traits/lib.rs
index ba6b2c57bfa..700efbd6ba9 100644
--- a/src/librustc_traits/lib.rs
+++ b/src/librustc_traits/lib.rs
@@ -28,6 +28,7 @@ extern crate rustc;
 extern crate rustc_data_structures;
 extern crate syntax;
 extern crate syntax_pos;
+extern crate smallvec;
 
 mod chalk_context;
 mod dropck_outlives;
diff --git a/src/libserialize/Cargo.toml b/src/libserialize/Cargo.toml
index a896c4a634c..66140d9c01f 100644
--- a/src/libserialize/Cargo.toml
+++ b/src/libserialize/Cargo.toml
@@ -7,3 +7,6 @@ version = "0.0.0"
 name = "serialize"
 path = "lib.rs"
 crate-type = ["dylib", "rlib"]
+
+[dependencies]
+smallvec = { version = "0.6.5", features = ["union"] }
diff --git a/src/libserialize/collection_impls.rs b/src/libserialize/collection_impls.rs
index 9748a506392..3e028d755c6 100644
--- a/src/libserialize/collection_impls.rs
+++ b/src/libserialize/collection_impls.rs
@@ -17,6 +17,38 @@ use std::collections::{LinkedList, VecDeque, BTreeMap, BTreeSet, HashMap, HashSe
 use std::rc::Rc;
 use std::sync::Arc;
 
+use smallvec::{Array, SmallVec};
+
+impl<A> Encodable for SmallVec<A>
+    where A: Array,
+          A::Item: 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 SmallVec<A>
+    where A: Array,
+          A::Item: 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);
+            // FIXME(#48994) - could just be collected into a Result<SmallVec, D::Error>
+            for i in 0..len {
+                vec.push(d.read_seq_elt(i, |d| Decodable::decode(d))?);
+            }
+            Ok(vec)
+        })
+    }
+}
+
 impl<T: Encodable> Encodable for LinkedList<T> {
     fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
         s.emit_seq(self.len(), |s| {
diff --git a/src/libserialize/lib.rs b/src/libserialize/lib.rs
index 794fc095096..1f6ee3d867b 100644
--- a/src/libserialize/lib.rs
+++ b/src/libserialize/lib.rs
@@ -32,6 +32,8 @@ pub use self::serialize::{Decoder, Encoder, Decodable, Encodable};
 pub use self::serialize::{SpecializationError, SpecializedEncoder, SpecializedDecoder};
 pub use self::serialize::{UseSpecializedEncodable, UseSpecializedDecodable};
 
+extern crate smallvec;
+
 mod serialize;
 mod collection_impls;
 
diff --git a/src/libsyntax/Cargo.toml b/src/libsyntax/Cargo.toml
index d1a5ab0211b..519cc7aa92c 100644
--- a/src/libsyntax/Cargo.toml
+++ b/src/libsyntax/Cargo.toml
@@ -17,3 +17,4 @@ syntax_pos = { path = "../libsyntax_pos" }
 rustc_errors = { path = "../librustc_errors" }
 rustc_data_structures = { path = "../librustc_data_structures" }
 rustc_target = { path = "../librustc_target" }
+smallvec = { version = "0.6.5", features = ["union"] }
diff --git a/src/libsyntax/diagnostics/plugin.rs b/src/libsyntax/diagnostics/plugin.rs
index d044efa3c38..c5a2cd5ac0b 100644
--- a/src/libsyntax/diagnostics/plugin.rs
+++ b/src/libsyntax/diagnostics/plugin.rs
@@ -131,7 +131,7 @@ pub fn expand_register_diagnostic<'cx>(ecx: &'cx mut ExtCtxt,
     let sym = Ident::with_empty_ctxt(Symbol::gensym(&format!(
         "__register_diagnostic_{}", code
     )));
-    MacEager::items(OneVector::many(vec![
+    MacEager::items(OneVector::from_vec(vec![
         ecx.item_mod(
             span,
             span,
@@ -214,7 +214,7 @@ pub fn expand_build_diagnostic_array<'cx>(ecx: &'cx mut ExtCtxt,
         ),
     );
 
-    MacEager::items(OneVector::many(vec![
+    MacEager::items(OneVector::from_vec(vec![
         P(ast::Item {
             ident: *name,
             attrs: Vec::new(),
diff --git a/src/libsyntax/ext/base.rs b/src/libsyntax/ext/base.rs
index c9925b41498..75d24df7b62 100644
--- a/src/libsyntax/ext/base.rs
+++ b/src/libsyntax/ext/base.rs
@@ -316,11 +316,11 @@ impl<F> IdentMacroExpander for F
 // Use a macro because forwarding to a simple function has type system issues
 macro_rules! make_stmts_default {
     ($me:expr) => {
-        $me.make_expr().map(|e| OneVector::one(ast::Stmt {
+        $me.make_expr().map(|e| smallvec![ast::Stmt {
             id: ast::DUMMY_NODE_ID,
             span: e.span,
             node: ast::StmtKind::Expr(e),
-        }))
+        }])
     }
 }
 
@@ -548,11 +548,11 @@ impl MacResult for DummyResult {
     }
 
     fn make_stmts(self: Box<DummyResult>) -> Option<OneVector<ast::Stmt>> {
-        Some(OneVector::one(ast::Stmt {
+        Some(smallvec![ast::Stmt {
             id: ast::DUMMY_NODE_ID,
             node: ast::StmtKind::Expr(DummyResult::raw_expr(self.span)),
             span: self.span,
-        }))
+        }])
     }
 
     fn make_ty(self: Box<DummyResult>) -> Option<P<ast::Ty>> {
diff --git a/src/libsyntax/ext/expand.rs b/src/libsyntax/ext/expand.rs
index 494f6d29832..a2e84b508dc 100644
--- a/src/libsyntax/ext/expand.rs
+++ b/src/libsyntax/ext/expand.rs
@@ -37,6 +37,7 @@ use visit::{self, Visitor};
 use std::collections::HashMap;
 use std::fs::File;
 use std::io::Read;
+use std::iter::FromIterator;
 use std::{iter, mem};
 use std::rc::Rc;
 use std::path::PathBuf;
@@ -131,7 +132,7 @@ macro_rules! ast_fragments {
                 self.expand_fragment(AstFragment::$Kind(ast)).$make_ast()
             })*)*
             $($(fn $fold_ast_elt(&mut self, ast_elt: <$AstTy as IntoIterator>::Item) -> $AstTy {
-                self.expand_fragment(AstFragment::$Kind(OneVector::one(ast_elt))).$make_ast()
+                self.expand_fragment(AstFragment::$Kind(smallvec![ast_elt])).$make_ast()
             })*)*
         }
 
@@ -270,7 +271,7 @@ impl<'a, 'b> MacroExpander<'a, 'b> {
 
         let orig_mod_span = krate.module.inner;
 
-        let krate_item = AstFragment::Items(OneVector::one(P(ast::Item {
+        let krate_item = AstFragment::Items(smallvec![P(ast::Item {
             attrs: krate.attrs,
             span: krate.span,
             node: ast::ItemKind::Mod(krate.module),
@@ -278,7 +279,7 @@ impl<'a, 'b> MacroExpander<'a, 'b> {
             id: ast::DUMMY_NODE_ID,
             vis: respan(krate.span.shrink_to_lo(), ast::VisibilityKind::Public),
             tokens: None,
-        })));
+        })]);
 
         match self.expand_fragment(krate_item).make_items().pop().map(P::into_inner) {
             Some(ast::Item { attrs, node: ast::ItemKind::Mod(module), .. }) => {
@@ -1404,7 +1405,7 @@ impl<'a, 'b> Folder for InvocationCollector<'a, 'b> {
                         ui
                     });
 
-                    OneVector::many(
+                    OneVector::from_iter(
                         self.fold_unnameable(item).into_iter()
                             .chain(self.fold_unnameable(use_item)))
                 } else {
diff --git a/src/libsyntax/ext/placeholders.rs b/src/libsyntax/ext/placeholders.rs
index 18b4119fde8..7a8ccfddf8e 100644
--- a/src/libsyntax/ext/placeholders.rs
+++ b/src/libsyntax/ext/placeholders.rs
@@ -46,37 +46,37 @@ pub fn placeholder(kind: AstFragmentKind, id: ast::NodeId) -> AstFragment {
     match kind {
         AstFragmentKind::Expr => AstFragment::Expr(expr_placeholder()),
         AstFragmentKind::OptExpr => AstFragment::OptExpr(Some(expr_placeholder())),
-        AstFragmentKind::Items => AstFragment::Items(OneVector::one(P(ast::Item {
+        AstFragmentKind::Items => AstFragment::Items(smallvec![P(ast::Item {
             id, span, ident, vis, attrs,
             node: ast::ItemKind::Mac(mac_placeholder()),
             tokens: None,
-        }))),
-        AstFragmentKind::TraitItems => AstFragment::TraitItems(OneVector::one(ast::TraitItem {
+        })]),
+        AstFragmentKind::TraitItems => AstFragment::TraitItems(smallvec![ast::TraitItem {
             id, span, ident, attrs, generics,
             node: ast::TraitItemKind::Macro(mac_placeholder()),
             tokens: None,
-        })),
-        AstFragmentKind::ImplItems => AstFragment::ImplItems(OneVector::one(ast::ImplItem {
+        }]),
+        AstFragmentKind::ImplItems => AstFragment::ImplItems(smallvec![ast::ImplItem {
             id, span, ident, vis, attrs, generics,
             node: ast::ImplItemKind::Macro(mac_placeholder()),
             defaultness: ast::Defaultness::Final,
             tokens: None,
-        })),
+        }]),
         AstFragmentKind::ForeignItems =>
-            AstFragment::ForeignItems(OneVector::one(ast::ForeignItem {
+            AstFragment::ForeignItems(smallvec![ast::ForeignItem {
                 id, span, ident, vis, attrs,
                 node: ast::ForeignItemKind::Macro(mac_placeholder()),
-            })),
+            }]),
         AstFragmentKind::Pat => AstFragment::Pat(P(ast::Pat {
             id, span, node: ast::PatKind::Mac(mac_placeholder()),
         })),
         AstFragmentKind::Ty => AstFragment::Ty(P(ast::Ty {
             id, span, node: ast::TyKind::Mac(mac_placeholder()),
         })),
-        AstFragmentKind::Stmts => AstFragment::Stmts(OneVector::one({
+        AstFragmentKind::Stmts => AstFragment::Stmts(smallvec![{
             let mac = P((mac_placeholder(), ast::MacStmtStyle::Braces, ThinVec::new()));
             ast::Stmt { id, span, node: ast::StmtKind::Mac(mac) }
-        })),
+        }]),
     }
 }
 
@@ -118,7 +118,7 @@ impl<'a, 'b> Folder for PlaceholderExpander<'a, 'b> {
     fn fold_item(&mut self, item: P<ast::Item>) -> OneVector<P<ast::Item>> {
         match item.node {
             ast::ItemKind::Mac(_) => return self.remove(item.id).make_items(),
-            ast::ItemKind::MacroDef(_) => return OneVector::one(item),
+            ast::ItemKind::MacroDef(_) => return smallvec![item],
             _ => {}
         }
 
diff --git a/src/libsyntax/ext/tt/macro_parser.rs b/src/libsyntax/ext/tt/macro_parser.rs
index 7d98fa661c0..dcdeee5c2e7 100644
--- a/src/libsyntax/ext/tt/macro_parser.rs
+++ b/src/libsyntax/ext/tt/macro_parser.rs
@@ -644,7 +644,7 @@ pub fn parse(
     // This MatcherPos instance is allocated on the stack. All others -- and
     // there are frequently *no* others! -- are allocated on the heap.
     let mut initial = initial_matcher_pos(ms, parser.span.lo());
-    let mut cur_items = OneVector::one(MatcherPosHandle::Ref(&mut initial));
+    let mut cur_items = smallvec![MatcherPosHandle::Ref(&mut initial)];
     let mut next_items = Vec::new();
 
     loop {
diff --git a/src/libsyntax/ext/tt/transcribe.rs b/src/libsyntax/ext/tt/transcribe.rs
index d451227e77c..67a15b149f6 100644
--- a/src/libsyntax/ext/tt/transcribe.rs
+++ b/src/libsyntax/ext/tt/transcribe.rs
@@ -70,7 +70,7 @@ pub fn transcribe(cx: &ExtCtxt,
                   interp: Option<HashMap<Ident, Rc<NamedMatch>>>,
                   src: Vec<quoted::TokenTree>)
                   -> TokenStream {
-    let mut stack = OneVector::one(Frame::new(src));
+    let mut stack: OneVector<Frame> = smallvec![Frame::new(src)];
     let interpolations = interp.unwrap_or_else(HashMap::new); /* just a convenience */
     let mut repeats = Vec::new();
     let mut result: Vec<TokenStream> = Vec::new();
diff --git a/src/libsyntax/fold.rs b/src/libsyntax/fold.rs
index 050d21674f9..660056e15e0 100644
--- a/src/libsyntax/fold.rs
+++ b/src/libsyntax/fold.rs
@@ -31,6 +31,7 @@ use tokenstream::*;
 use util::move_map::MoveMap;
 
 use rustc_data_structures::sync::Lrc;
+use rustc_data_structures::small_vec::ExpectOne;
 
 pub trait Folder : Sized {
     // Any additions to this trait should happen in form
@@ -962,7 +963,7 @@ pub fn noop_fold_item_kind<T: Folder>(i: ItemKind, folder: &mut T) -> ItemKind {
 
 pub fn noop_fold_trait_item<T: Folder>(i: TraitItem, folder: &mut T)
                                        -> OneVector<TraitItem> {
-    OneVector::one(TraitItem {
+    smallvec![TraitItem {
         id: folder.new_id(i.id),
         ident: folder.fold_ident(i.ident),
         attrs: fold_attrs(i.attrs, folder),
@@ -986,12 +987,12 @@ pub fn noop_fold_trait_item<T: Folder>(i: TraitItem, folder: &mut T)
         },
         span: folder.new_span(i.span),
         tokens: i.tokens,
-    })
+    }]
 }
 
 pub fn noop_fold_impl_item<T: Folder>(i: ImplItem, folder: &mut T)
                                       -> OneVector<ImplItem> {
-    OneVector::one(ImplItem {
+    smallvec![ImplItem {
         id: folder.new_id(i.id),
         vis: folder.fold_vis(i.vis),
         ident: folder.fold_ident(i.ident),
@@ -1014,7 +1015,7 @@ pub fn noop_fold_impl_item<T: Folder>(i: ImplItem, folder: &mut T)
         },
         span: folder.new_span(i.span),
         tokens: i.tokens,
-    })
+    }]
 }
 
 pub fn noop_fold_fn_header<T: Folder>(mut header: FnHeader, folder: &mut T) -> FnHeader {
@@ -1067,7 +1068,7 @@ pub fn noop_fold_crate<T: Folder>(Crate {module, attrs, span}: Crate,
 
 // fold one item into possibly many items
 pub fn noop_fold_item<T: Folder>(i: P<Item>, folder: &mut T) -> OneVector<P<Item>> {
-    OneVector::one(i.map(|i| folder.fold_item_simple(i)))
+    smallvec![i.map(|i| folder.fold_item_simple(i))]
 }
 
 // fold one item into exactly one item
@@ -1089,7 +1090,7 @@ pub fn noop_fold_item_simple<T: Folder>(Item {id, ident, attrs, node, vis, span,
 
 pub fn noop_fold_foreign_item<T: Folder>(ni: ForeignItem, folder: &mut T)
 -> OneVector<ForeignItem> {
-    OneVector::one(folder.fold_foreign_item_simple(ni))
+    smallvec![folder.fold_foreign_item_simple(ni)]
 }
 
 pub fn noop_fold_foreign_item_simple<T: Folder>(ni: ForeignItem, folder: &mut T) -> ForeignItem {
@@ -1377,7 +1378,7 @@ pub fn noop_fold_stmt<T: Folder>(Stmt {node, span, id}: Stmt, folder: &mut T) ->
 
 pub fn noop_fold_stmt_kind<T: Folder>(node: StmtKind, folder: &mut T) -> OneVector<StmtKind> {
     match node {
-        StmtKind::Local(local) => OneVector::one(StmtKind::Local(folder.fold_local(local))),
+        StmtKind::Local(local) => smallvec![StmtKind::Local(folder.fold_local(local))],
         StmtKind::Item(item) => folder.fold_item(item).into_iter().map(StmtKind::Item).collect(),
         StmtKind::Expr(expr) => {
             folder.fold_opt_expr(expr).into_iter().map(StmtKind::Expr).collect()
@@ -1385,9 +1386,9 @@ pub fn noop_fold_stmt_kind<T: Folder>(node: StmtKind, folder: &mut T) -> OneVect
         StmtKind::Semi(expr) => {
             folder.fold_opt_expr(expr).into_iter().map(StmtKind::Semi).collect()
         }
-        StmtKind::Mac(mac) => OneVector::one(StmtKind::Mac(mac.map(|(mac, semi, attrs)| {
+        StmtKind::Mac(mac) => smallvec![StmtKind::Mac(mac.map(|(mac, semi, attrs)| {
             (folder.fold_mac(mac), semi, fold_attrs(attrs.into(), folder).into())
-        }))),
+        }))],
     }
 }
 
diff --git a/src/libsyntax/lib.rs b/src/libsyntax/lib.rs
index 366b91fc828..2aaab6aaa16 100644
--- a/src/libsyntax/lib.rs
+++ b/src/libsyntax/lib.rs
@@ -40,6 +40,8 @@ extern crate syntax_pos;
 extern crate rustc_data_structures;
 extern crate rustc_target;
 #[macro_use] extern crate scoped_tls;
+#[macro_use]
+extern crate smallvec;
 
 extern crate serialize as rustc_serialize; // used by deriving
 
diff --git a/src/libsyntax/test.rs b/src/libsyntax/test.rs
index 988f50b4f0c..49ab0c2256e 100644
--- a/src/libsyntax/test.rs
+++ b/src/libsyntax/test.rs
@@ -41,6 +41,7 @@ use ptr::P;
 use OneVector;
 use symbol::{self, Symbol, keywords};
 use ThinVec;
+use rustc_data_structures::small_vec::ExpectOne;
 
 enum ShouldPanic {
     No,
@@ -183,7 +184,7 @@ impl<'a> fold::Folder for TestHarnessGenerator<'a> {
         if ident.name != keywords::Invalid.name() {
             self.cx.path.pop();
         }
-        OneVector::one(P(item))
+        smallvec![P(item)]
     }
 
     fn fold_mac(&mut self, mac: ast::Mac) -> ast::Mac { mac }
@@ -235,7 +236,7 @@ impl fold::Folder for EntryPointCleaner {
             EntryPointType::OtherMain => folded,
         };
 
-        OneVector::one(folded)
+        smallvec![folded]
     }
 
     fn fold_mac(&mut self, mac: ast::Mac) -> ast::Mac { mac }
diff --git a/src/libsyntax_ext/Cargo.toml b/src/libsyntax_ext/Cargo.toml
index 1676757d9b8..8dba34583be 100644
--- a/src/libsyntax_ext/Cargo.toml
+++ b/src/libsyntax_ext/Cargo.toml
@@ -15,4 +15,5 @@ rustc_errors = { path = "../librustc_errors" }
 syntax = { path = "../libsyntax" }
 syntax_pos = { path = "../libsyntax_pos" }
 rustc_data_structures = { path = "../librustc_data_structures" }
-rustc_target = { path = "../librustc_target" }
\ No newline at end of file
+rustc_target = { path = "../librustc_target" }
+smallvec = { version = "0.6.5", features = ["union"] }
diff --git a/src/libsyntax_ext/global_asm.rs b/src/libsyntax_ext/global_asm.rs
index 56f28d04e9d..1130a50537d 100644
--- a/src/libsyntax_ext/global_asm.rs
+++ b/src/libsyntax_ext/global_asm.rs
@@ -18,8 +18,6 @@
 /// LLVM's `module asm "some assembly here"`. All of LLVM's caveats
 /// therefore apply.
 
-use rustc_data_structures::small_vec::OneVector;
-
 use syntax::ast;
 use syntax::source_map::respan;
 use syntax::ext::base;
@@ -52,7 +50,7 @@ pub fn expand_global_asm<'cx>(cx: &'cx mut ExtCtxt,
         None => return DummyResult::any(sp),
     };
 
-    MacEager::items(OneVector::one(P(ast::Item {
+    MacEager::items(smallvec![P(ast::Item {
         ident: ast::Ident::with_empty_ctxt(Symbol::intern("")),
         attrs: Vec::new(),
         id: ast::DUMMY_NODE_ID,
@@ -63,5 +61,5 @@ pub fn expand_global_asm<'cx>(cx: &'cx mut ExtCtxt,
         vis: respan(sp.shrink_to_lo(), ast::VisibilityKind::Inherited),
         span: sp,
         tokens: None,
-    })))
+    })])
 }
diff --git a/src/libsyntax_ext/lib.rs b/src/libsyntax_ext/lib.rs
index 1ba4ab47425..790a42007fb 100644
--- a/src/libsyntax_ext/lib.rs
+++ b/src/libsyntax_ext/lib.rs
@@ -29,6 +29,8 @@ extern crate proc_macro;
 extern crate rustc_data_structures;
 extern crate rustc_errors as errors;
 extern crate rustc_target;
+#[macro_use]
+extern crate smallvec;
 
 mod diagnostics;
 
diff --git a/src/test/run-pass-fulldeps/auxiliary/issue-16723.rs b/src/test/run-pass-fulldeps/auxiliary/issue-16723.rs
index ff5d9a59bfa..533d0ac490c 100644
--- a/src/test/run-pass-fulldeps/auxiliary/issue-16723.rs
+++ b/src/test/run-pass-fulldeps/auxiliary/issue-16723.rs
@@ -31,7 +31,7 @@ pub fn plugin_registrar(reg: &mut Registry) {
 
 fn expand(cx: &mut ExtCtxt, _: syntax_pos::Span, _: &[tokenstream::TokenTree])
           -> Box<MacResult+'static> {
-    MacEager::items(OneVector::many(vec![
+    MacEager::items(OneVector::from_vec(vec![
         quote_item!(cx, struct Struct1;).unwrap(),
         quote_item!(cx, struct Struct2;).unwrap()
     ]))