rustc: use indexmap instead of a plain vector for upvars.

26 files changed, 198 insertions, 115 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 7b0905db9af..0eee3461ed6 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -1184,6 +1184,11 @@ dependencies = [
 ]
 
 [[package]]
+name = "indexmap"
+version = "1.0.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
 name = "installer"
 version = "0.0.0"
 dependencies = [
@@ -2719,6 +2724,7 @@ dependencies = [
  "cfg-if 0.1.8 (registry+https://github.com/rust-lang/crates.io-index)",
  "ena 0.13.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "graphviz 0.0.0",
+ "indexmap 1.0.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "jobserver 0.1.13 (registry+https://github.com/rust-lang/crates.io-index)",
  "lazy_static 1.3.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "log 0.4.6 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -2970,6 +2976,7 @@ version = "0.0.0"
 dependencies = [
  "arena 0.0.0",
  "bitflags 1.0.4 (registry+https://github.com/rust-lang/crates.io-index)",
+ "indexmap 1.0.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "log 0.4.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "rustc 0.0.0",
  "rustc_data_structures 0.0.0",
@@ -3236,6 +3243,7 @@ dependencies = [
 name = "serialize"
 version = "0.0.0"
 dependencies = [
+ "indexmap 1.0.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "smallvec 0.6.7 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
@@ -4199,6 +4207,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 "checksum if_chain 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "c3360c7b59e5ffa2653671fb74b4741a5d343c03f331c0a4aeda42b5c2b0ec7d"
 "checksum ignore 0.4.7 (registry+https://github.com/rust-lang/crates.io-index)" = "8dc57fa12805f367736a38541ac1a9fc6a52812a0ca959b1d4d4b640a89eb002"
 "checksum im-rc 13.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "0a0197597d095c0d11107975d3175173f810ee572c2501ff4de64f4f3f119806"
+"checksum indexmap 1.0.2 (registry+https://github.com/rust-lang/crates.io-index)" = "7e81a7c05f79578dbc15793d8b619db9ba32b4577003ef3af1a91c416798c58d"
 "checksum iovec 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "dbe6e417e7d0975db6512b90796e8ce223145ac4e33c377e4a42882a0e88bb08"
 "checksum is-match 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "7e5b386aef33a1c677be65237cb9d32c3f3ef56bd035949710c4bb13083eb053"
 "checksum itertools 0.7.8 (registry+https://github.com/rust-lang/crates.io-index)" = "f58856976b776fedd95533137617a02fb25719f40e7d9b01c7043cd65474f450"
diff --git a/src/librustc/hir/mod.rs b/src/librustc/hir/mod.rs
index 66535079e1d..7ec24647b4d 100644
--- a/src/librustc/hir/mod.rs
+++ b/src/librustc/hir/mod.rs
@@ -30,6 +30,7 @@ use syntax::util::parser::ExprPrecedence;
 use crate::ty::AdtKind;
 use crate::ty::query::Providers;
 
+use rustc_data_structures::fx::FxIndexMap;
 use rustc_data_structures::sync::{par_for_each_in, Send, Sync};
 use rustc_data_structures::thin_vec::ThinVec;
 use rustc_macros::HashStable;
@@ -2493,10 +2494,7 @@ impl ForeignItemKind {
 
 /// A variable captured by a closure.
 #[derive(Debug, Copy, Clone, RustcEncodable, RustcDecodable, HashStable)]
-pub struct Upvar<Id = HirId> {
-    /// The variable being captured.
-    pub var_id: Id,
-
+pub struct Upvar {
     /// Whether this is not a direct capture (comes from parent closure).
     pub has_parent: bool,
 
@@ -2504,17 +2502,7 @@ pub struct Upvar<Id = HirId> {
     pub span: Span
 }
 
-impl<Id: fmt::Debug + Copy> Upvar<Id> {
-    pub fn map_id<R>(self, map: impl FnOnce(Id) -> R) -> Upvar<R> {
-        Upvar {
-            var_id: map(self.var_id),
-            has_parent: self.has_parent,
-            span: self.span,
-        }
-    }
-}
-
-pub type UpvarMap = NodeMap<Vec<Upvar<ast::NodeId>>>;
+pub type UpvarMap = NodeMap<FxIndexMap<ast::NodeId, Upvar>>;
 
 pub type CaptureModeMap = NodeMap<CaptureClause>;
 
diff --git a/src/librustc/middle/expr_use_visitor.rs b/src/librustc/middle/expr_use_visitor.rs
index 034f60875e7..11faaa4df18 100644
--- a/src/librustc/middle/expr_use_visitor.rs
+++ b/src/librustc/middle/expr_use_visitor.rs
@@ -924,14 +924,15 @@ impl<'a, 'gcx, 'tcx> ExprUseVisitor<'a, 'gcx, 'tcx> {
 
         let closure_def_id = self.tcx().hir().local_def_id_from_hir_id(closure_expr.hir_id);
         if let Some(upvars) = self.tcx().upvars(closure_def_id) {
-            for upvar in upvars.iter() {
+            for (&var_id, upvar) in upvars.iter() {
                 let upvar_id = ty::UpvarId {
-                    var_path: ty::UpvarPath { hir_id: upvar.var_id },
+                    var_path: ty::UpvarPath { hir_id: var_id },
                     closure_expr_id: closure_def_id.to_local(),
                 };
                 let upvar_capture = self.mc.tables.upvar_capture(upvar_id);
                 let cmt_var = return_if_err!(self.cat_captured_var(closure_expr.hir_id,
                                                                    fn_decl_span,
+                                                                   var_id,
                                                                    upvar));
                 match upvar_capture {
                     ty::UpvarCapture::ByValue => {
@@ -957,6 +958,7 @@ impl<'a, 'gcx, 'tcx> ExprUseVisitor<'a, 'gcx, 'tcx> {
     fn cat_captured_var(&mut self,
                         closure_hir_id: hir::HirId,
                         closure_span: Span,
+                        var_id: hir::HirId,
                         upvar: &hir::Upvar)
                         -> mc::McResult<mc::cmt_<'tcx>> {
         // Create the cmt for the variable being borrowed, from the
@@ -965,11 +967,11 @@ impl<'a, 'gcx, 'tcx> ExprUseVisitor<'a, 'gcx, 'tcx> {
             let closure_def_id = self.tcx().hir().local_def_id_from_hir_id(closure_hir_id);
             let parent_def_id = self.tcx().parent(closure_def_id).unwrap();
             assert!(self.tcx().is_closure(parent_def_id));
-            let var_nid = self.tcx().hir().hir_to_node_id(upvar.var_id);
+            let var_nid = self.tcx().hir().hir_to_node_id(var_id);
             self.mc.cat_upvar(closure_hir_id, closure_span, var_nid, parent_def_id)
         } else {
-            let var_ty = self.mc.node_ty(upvar.var_id)?;
-            self.mc.cat_res(closure_hir_id, closure_span, var_ty, Res::Local(upvar.var_id))
+            let var_ty = self.mc.node_ty(var_id)?;
+            self.mc.cat_res(closure_hir_id, closure_span, var_ty, Res::Local(var_id))
         }
     }
 }
diff --git a/src/librustc/middle/liveness.rs b/src/librustc/middle/liveness.rs
index 22930cc1989..873c2dd4805 100644
--- a/src/librustc/middle/liveness.rs
+++ b/src/librustc/middle/liveness.rs
@@ -485,10 +485,10 @@ fn visit_expr<'a, 'tcx>(ir: &mut IrMaps<'a, 'tcx>, expr: &'tcx Expr) {
         let mut call_caps = Vec::new();
         let closure_def_id = ir.tcx.hir().local_def_id_from_hir_id(expr.hir_id);
         if let Some(upvars) = ir.tcx.upvars(closure_def_id) {
-            call_caps.extend(upvars.iter().filter_map(|upvar| {
+            call_caps.extend(upvars.iter().filter_map(|(&var_id, upvar)| {
                 if !upvar.has_parent {
                     let upvar_ln = ir.add_live_node(UpvarNode(upvar.span));
-                    Some(CaptureInfo { ln: upvar_ln, var_hid: upvar.var_id })
+                    Some(CaptureInfo { ln: upvar_ln, var_hid: var_id })
                 } else {
                     None
                 }
diff --git a/src/librustc/mir/mod.rs b/src/librustc/mir/mod.rs
index 1f29b370d27..6213eda6514 100644
--- a/src/librustc/mir/mod.rs
+++ b/src/librustc/mir/mod.rs
@@ -2562,8 +2562,8 @@ impl<'tcx> Debug for Rvalue<'tcx> {
                             let mut struct_fmt = fmt.debug_struct(&name);
 
                             if let Some(upvars) = tcx.upvars(def_id) {
-                                for (upvar, place) in upvars.iter().zip(places) {
-                                    let var_name = tcx.hir().name_by_hir_id(upvar.var_id);
+                                for (&var_id, place) in upvars.keys().zip(places) {
+                                    let var_name = tcx.hir().name_by_hir_id(var_id);
                                     struct_fmt.field(&var_name.as_str(), place);
                                 }
                             }
@@ -2581,8 +2581,8 @@ impl<'tcx> Debug for Rvalue<'tcx> {
                             let mut struct_fmt = fmt.debug_struct(&name);
 
                             if let Some(upvars) = tcx.upvars(def_id) {
-                                for (upvar, place) in upvars.iter().zip(places) {
-                                    let var_name = tcx.hir().name_by_hir_id(upvar.var_id);
+                                for (&var_id, place) in upvars.keys().zip(places) {
+                                    let var_name = tcx.hir().name_by_hir_id(var_id);
                                     struct_fmt.field(&var_name.as_str(), place);
                                 }
                             }
diff --git a/src/librustc/query/mod.rs b/src/librustc/query/mod.rs
index b8621c8ad30..18308f54442 100644
--- a/src/librustc/query/mod.rs
+++ b/src/librustc/query/mod.rs
@@ -826,7 +826,7 @@ rustc_queries! {
             desc { "generating a postorder list of CrateNums" }
         }
 
-        query upvars(_: DefId) -> Option<&'tcx [hir::Upvar]> {
+        query upvars(_: DefId) -> Option<&'tcx FxIndexMap<hir::HirId, hir::Upvar>> {
             eval_always
         }
         query maybe_unused_trait_import(_: DefId) -> bool {
diff --git a/src/librustc/ty/context.rs b/src/librustc/ty/context.rs
index b4823db9920..f8f869b9842 100644
--- a/src/librustc/ty/context.rs
+++ b/src/librustc/ty/context.rs
@@ -54,6 +54,7 @@ use rustc_data_structures::stable_hasher::{HashStable, hash_stable_hashmap,
                                            StableHasher, StableHasherResult,
                                            StableVec};
 use arena::SyncDroplessArena;
+use rustc_data_structures::fx::FxIndexMap;
 use rustc_data_structures::indexed_vec::{Idx, IndexVec};
 use rustc_data_structures::sync::{Lrc, Lock, WorkerLocal};
 use std::any::Any;
@@ -1065,7 +1066,7 @@ pub struct GlobalCtxt<'tcx> {
     // Records the captured variables referenced by every closure
     // expression. Do not track deps for this, just recompute it from
     // scratch every time.
-    upvars: FxHashMap<DefId, Vec<hir::Upvar>>,
+    upvars: FxHashMap<DefId, FxIndexMap<hir::HirId, hir::Upvar>>,
 
     maybe_unused_trait_imports: FxHashSet<DefId>,
     maybe_unused_extern_crates: Vec<(DefId, Span)>,
@@ -1297,11 +1298,11 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
                 }).collect();
                 (k, exports)
             }).collect(),
-            upvars: resolutions.upvars.into_iter().map(|(k, v)| {
-                let vars: Vec<_> = v.into_iter().map(|e| {
-                    e.map_id(|id| hir.node_to_hir_id(id))
+            upvars: resolutions.upvars.into_iter().map(|(k, upvars)| {
+                let upvars: FxIndexMap<_, _> = upvars.into_iter().map(|(var_id, upvar)| {
+                    (hir.node_to_hir_id(var_id), upvar)
                 }).collect();
-                (hir.local_def_id(k), vars)
+                (hir.local_def_id(k), upvars)
             }).collect(),
             maybe_unused_trait_imports:
                 resolutions.maybe_unused_trait_imports
@@ -3023,7 +3024,7 @@ pub fn provide(providers: &mut ty::query::Providers<'_>) {
         assert_eq!(id, LOCAL_CRATE);
         tcx.arena.alloc(middle::lang_items::collect(tcx))
     };
-    providers.upvars = |tcx, id| tcx.gcx.upvars.get(&id).map(|v| &v[..]);
+    providers.upvars = |tcx, id| tcx.gcx.upvars.get(&id);
     providers.maybe_unused_trait_import = |tcx, id| {
         tcx.maybe_unused_trait_imports.contains(&id)
     };
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index 094e1d05aeb..c0f582d5d13 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -51,6 +51,7 @@ use syntax::symbol::{kw, sym, Symbol, LocalInternedString, InternedString};
 use syntax_pos::Span;
 
 use smallvec;
+use rustc_data_structures::fx::FxIndexMap;
 use rustc_data_structures::indexed_vec::{Idx, IndexVec};
 use rustc_data_structures::stable_hasher::{StableHasher, StableHasherResult,
                                            HashStable};
@@ -808,7 +809,7 @@ pub struct UpvarBorrow<'tcx> {
     pub region: ty::Region<'tcx>,
 }
 
-pub type UpvarListMap = FxHashMap<DefId, Vec<UpvarId>>;
+pub type UpvarListMap = FxHashMap<DefId, FxIndexMap<hir::HirId, UpvarId>>;
 pub type UpvarCaptureMap<'tcx> = FxHashMap<UpvarId, UpvarCapture<'tcx>>;
 
 #[derive(Copy, Clone)]
diff --git a/src/librustc/ty/print/pretty.rs b/src/librustc/ty/print/pretty.rs
index 03c7226c1af..a8a6bca4fd4 100644
--- a/src/librustc/ty/print/pretty.rs
+++ b/src/librustc/ty/print/pretty.rs
@@ -585,16 +585,16 @@ pub trait PrettyPrinter<'gcx: 'tcx, 'tcx>:
                 if let Some(hir_id) = self.tcx().hir().as_local_hir_id(did) {
                     p!(write("@{:?}", self.tcx().hir().span_by_hir_id(hir_id)));
                     let mut sep = " ";
-                    for (upvar, upvar_ty) in self.tcx().upvars(did)
+                    for (&var_id, upvar_ty) in self.tcx().upvars(did)
                         .as_ref()
-                        .map_or(&[][..], |v| &v[..])
                         .iter()
+                        .flat_map(|v| v.keys())
                         .zip(upvar_tys)
                     {
                         p!(
                             write("{}{}:",
                                     sep,
-                                    self.tcx().hir().name_by_hir_id(upvar.var_id)),
+                                    self.tcx().hir().name_by_hir_id(var_id)),
                             print(upvar_ty));
                         sep = ", ";
                     }
@@ -628,16 +628,16 @@ pub trait PrettyPrinter<'gcx: 'tcx, 'tcx>:
                         p!(write("@{:?}", self.tcx().hir().span_by_hir_id(hir_id)));
                     }
                     let mut sep = " ";
-                    for (upvar, upvar_ty) in self.tcx().upvars(did)
+                    for (&var_id, upvar_ty) in self.tcx().upvars(did)
                         .as_ref()
-                        .map_or(&[][..], |v| &v[..])
                         .iter()
+                        .flat_map(|v| v.keys())
                         .zip(upvar_tys)
                     {
                         p!(
                             write("{}{}:",
                                     sep,
-                                    self.tcx().hir().name_by_hir_id(upvar.var_id)),
+                                    self.tcx().hir().name_by_hir_id(var_id)),
                             print(upvar_ty));
                         sep = ", ";
                     }
diff --git a/src/librustc/ty/query/mod.rs b/src/librustc/ty/query/mod.rs
index a2bced97102..e595b52876f 100644
--- a/src/librustc/ty/query/mod.rs
+++ b/src/librustc/ty/query/mod.rs
@@ -45,7 +45,7 @@ use crate::util::profiling::ProfileCategory::*;
 use rustc_data_structures::svh::Svh;
 use rustc_data_structures::bit_set::BitSet;
 use rustc_data_structures::indexed_vec::IndexVec;
-use rustc_data_structures::fx::{FxHashMap, FxHashSet};
+use rustc_data_structures::fx::{FxIndexMap, FxHashMap, FxHashSet};
 use rustc_data_structures::stable_hasher::StableVec;
 use rustc_data_structures::sync::Lrc;
 use rustc_data_structures::fingerprint::Fingerprint;
diff --git a/src/librustc_data_structures/Cargo.toml b/src/librustc_data_structures/Cargo.toml
index 5f3bac866d6..cd792d31187 100644
--- a/src/librustc_data_structures/Cargo.toml
+++ b/src/librustc_data_structures/Cargo.toml
@@ -11,6 +11,7 @@ crate-type = ["dylib"]
 
 [dependencies]
 ena = "0.13"
+indexmap = "1"
 log = "0.4"
 jobserver_crate = { version = "0.1.13", package = "jobserver" }
 lazy_static = "1"
diff --git a/src/librustc_data_structures/fx.rs b/src/librustc_data_structures/fx.rs
index a2afeffe730..cf73fe8cf85 100644
--- a/src/librustc_data_structures/fx.rs
+++ b/src/librustc_data_structures/fx.rs
@@ -1 +1,6 @@
+use std::hash::BuildHasherDefault;
+
 pub use rustc_hash::{FxHasher, FxHashMap, FxHashSet};
+
+pub type FxIndexMap<K, V> = indexmap::IndexMap<K, V, BuildHasherDefault<FxHasher>>;
+pub type FxIndexSet<V> = indexmap::IndexSet<V, BuildHasherDefault<FxHasher>>;
diff --git a/src/librustc_data_structures/stable_hasher.rs b/src/librustc_data_structures/stable_hasher.rs
index 2b844aa24d4..270d9520627 100644
--- a/src/librustc_data_structures/stable_hasher.rs
+++ b/src/librustc_data_structures/stable_hasher.rs
@@ -323,6 +323,37 @@ impl<T: HashStable<CTX>, CTX> HashStable<CTX> for Vec<T> {
     }
 }
 
+impl<K, V, R, CTX> HashStable<CTX> for indexmap::IndexMap<K, V, R>
+    where K: HashStable<CTX> + Eq + Hash,
+          V: HashStable<CTX>,
+          R: BuildHasher,
+{
+    #[inline]
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          ctx: &mut CTX,
+                                          hasher: &mut StableHasher<W>) {
+        self.len().hash_stable(ctx, hasher);
+        for kv in self {
+            kv.hash_stable(ctx, hasher);
+        }
+    }
+}
+
+impl<K, R, CTX> HashStable<CTX> for indexmap::IndexSet<K, R>
+    where K: HashStable<CTX> + Eq + Hash,
+          R: BuildHasher,
+{
+    #[inline]
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          ctx: &mut CTX,
+                                          hasher: &mut StableHasher<W>) {
+        self.len().hash_stable(ctx, hasher);
+        for key in self {
+            key.hash_stable(ctx, hasher);
+        }
+    }
+}
+
 impl<A, CTX> HashStable<CTX> for SmallVec<[A; 1]> where A: HashStable<CTX> {
     #[inline]
     fn hash_stable<W: StableHasherResult>(&self,
diff --git a/src/librustc_mir/borrow_check/error_reporting.rs b/src/librustc_mir/borrow_check/error_reporting.rs
index 74601cc3891..31af20fdb77 100644
--- a/src/librustc_mir/borrow_check/error_reporting.rs
+++ b/src/librustc_mir/borrow_check/error_reporting.rs
@@ -348,9 +348,10 @@ impl<'cx, 'gcx, 'tcx> MirBorrowckCtxt<'cx, 'gcx, 'tcx> {
                     // `tcx.upvars(def_id)` returns an `Option`, which is `None` in case
                     // the closure comes from another crate. But in that case we wouldn't
                     // be borrowck'ing it, so we can just unwrap:
-                    let upvar = self.infcx.tcx.upvars(def_id).unwrap()[field.index()];
+                    let (&var_id, _) = self.infcx.tcx.upvars(def_id).unwrap()
+                        .get_index(field.index()).unwrap();
 
-                    self.infcx.tcx.hir().name_by_hir_id(upvar.var_id).to_string()
+                    self.infcx.tcx.hir().name_by_hir_id(var_id).to_string()
                 }
                 _ => {
                     // Might need a revision when the fields in trait RFC is implemented
@@ -645,12 +646,12 @@ impl<'cx, 'gcx, 'tcx> MirBorrowckCtxt<'cx, 'gcx, 'tcx> {
         if let hir::ExprKind::Closure(
             .., args_span, _
         ) = expr {
-            for (v, place) in self.infcx.tcx.upvars(def_id)?.iter().zip(places) {
+            for (upvar, place) in self.infcx.tcx.upvars(def_id)?.values().zip(places) {
                 match place {
                     Operand::Copy(place) |
                     Operand::Move(place) if target_place == place => {
                         debug!("closure_span: found captured local {:?}", place);
-                        return Some((*args_span, v.span));
+                        return Some((*args_span, upvar.span));
                     },
                     _ => {}
                 }
diff --git a/src/librustc_mir/borrow_check/mod.rs b/src/librustc_mir/borrow_check/mod.rs
index 82be2405701..4ae4d039d60 100644
--- a/src/librustc_mir/borrow_check/mod.rs
+++ b/src/librustc_mir/borrow_check/mod.rs
@@ -149,7 +149,7 @@ fn do_mir_borrowck<'a, 'gcx, 'tcx>(
         .upvar_list
         .get(&def_id)
         .into_iter()
-        .flatten()
+        .flat_map(|v| v.values())
         .map(|upvar_id| {
             let var_hir_id = upvar_id.var_path.hir_id;
             let var_node_id = tcx.hir().hir_to_node_id(var_hir_id);
diff --git a/src/librustc_mir/build/mod.rs b/src/librustc_mir/build/mod.rs
index 5797f9c3478..123b46cb048 100644
--- a/src/librustc_mir/build/mod.rs
+++ b/src/librustc_mir/build/mod.rs
@@ -651,10 +651,9 @@ fn construct_fn<'a, 'gcx, 'tcx, A>(hir: Cx<'a, 'gcx, 'tcx>,
         .get(&fn_def_id)
         .into_iter()
         .flatten()
-        .map(|upvar_id| {
-            let var_hir_id = upvar_id.var_path.hir_id;
+        .map(|(&var_hir_id, &upvar_id)| {
             let var_node_id = tcx_hir.hir_to_node_id(var_hir_id);
-            let capture = hir_tables.upvar_capture(*upvar_id);
+            let capture = hir_tables.upvar_capture(upvar_id);
             let by_ref = match capture {
                 ty::UpvarCapture::ByValue => false,
                 ty::UpvarCapture::ByRef(..) => true,
diff --git a/src/librustc_mir/hair/cx/expr.rs b/src/librustc_mir/hair/cx/expr.rs
index 4d32f1eec44..dc9451fefb8 100644
--- a/src/librustc_mir/hair/cx/expr.rs
+++ b/src/librustc_mir/hair/cx/expr.rs
@@ -515,7 +515,7 @@ fn make_mirror_unadjusted<'a, 'gcx, 'tcx>(cx: &mut Cx<'a, 'gcx, 'tcx>,
             let upvars = cx.tcx.upvars(def_id).iter()
                 .flat_map(|upvars| upvars.iter())
                 .zip(substs.upvar_tys(def_id, cx.tcx))
-                .map(|(upvar, ty)| capture_upvar(cx, expr, upvar, ty))
+                .map(|((&var_hir_id, upvar), ty)| capture_upvar(cx, expr, var_hir_id, upvar, ty))
                 .collect();
             ExprKind::Closure {
                 closure_id: def_id,
@@ -964,7 +964,7 @@ fn convert_path_expr<'a, 'gcx, 'tcx>(cx: &mut Cx<'a, 'gcx, 'tcx>,
         Res::Upvar(var_hir_id, closure_node_id) => {
             let closure_def_id = cx.tcx.hir().local_def_id(closure_node_id);
             assert_eq!(cx.body_owner, closure_def_id);
-            assert!(cx.upvar_indices.contains_key(&var_hir_id));
+            assert!(cx.tables().upvar_list[&cx.body_owner].contains_key(&var_hir_id));
 
             convert_var(cx, expr, var_hir_id)
         }
@@ -978,7 +978,8 @@ fn convert_var(
     expr: &'tcx hir::Expr,
     var_hir_id: hir::HirId,
 ) -> ExprKind<'tcx> {
-    let upvar_index = cx.upvar_indices.get(&var_hir_id).cloned();
+    let upvar_index = cx.tables().upvar_list.get(&cx.body_owner)
+        .and_then(|upvars| upvars.get_full(&var_hir_id).map(|(i, _, _)| i));
 
     debug!("convert_var({:?}): upvar_index={:?}, body_owner={:?}",
            var_hir_id, upvar_index, cx.body_owner);
@@ -1186,26 +1187,31 @@ fn overloaded_place<'a, 'gcx, 'tcx>(
 
 fn capture_upvar<'a, 'gcx, 'tcx>(cx: &mut Cx<'a, 'gcx, 'tcx>,
                                    closure_expr: &'tcx hir::Expr,
+                                   var_hir_id: hir::HirId,
                                    upvar: &hir::Upvar,
                                    upvar_ty: Ty<'tcx>)
                                    -> ExprRef<'tcx> {
     let upvar_id = ty::UpvarId {
-        var_path: ty::UpvarPath { hir_id: upvar.var_id },
+        var_path: ty::UpvarPath { hir_id: var_hir_id },
         closure_expr_id: cx.tcx.hir().local_def_id_from_hir_id(closure_expr.hir_id).to_local(),
     };
     let upvar_capture = cx.tables().upvar_capture(upvar_id);
     let temp_lifetime = cx.region_scope_tree.temporary_scope(closure_expr.hir_id.local_id);
-    let var_ty = cx.tables().node_type(upvar.var_id);
+    let var_ty = cx.tables().node_type(var_hir_id);
     if upvar.has_parent {
         let closure_def_id = upvar_id.closure_expr_id.to_def_id();
         assert_eq!(cx.body_owner, cx.tcx.parent(closure_def_id).unwrap());
     }
-    assert_eq!(upvar.has_parent, cx.upvar_indices.contains_key(&upvar.var_id));
+    assert_eq!(
+        upvar.has_parent,
+        cx.tables().upvar_list.get(&cx.body_owner)
+            .map_or(false, |upvars| upvars.contains_key(&var_hir_id)),
+    );
     let captured_var = Expr {
         temp_lifetime,
         ty: var_ty,
         span: closure_expr.span,
-        kind: convert_var(cx, closure_expr, upvar.var_id),
+        kind: convert_var(cx, closure_expr, var_hir_id),
     };
     match upvar_capture {
         ty::UpvarCapture::ByValue => captured_var.to_ref(),
diff --git a/src/librustc_mir/hair/cx/mod.rs b/src/librustc_mir/hair/cx/mod.rs
index 251bc24bbd2..f4a23a90dee 100644
--- a/src/librustc_mir/hair/cx/mod.rs
+++ b/src/librustc_mir/hair/cx/mod.rs
@@ -5,7 +5,6 @@
 use crate::hair::*;
 use crate::hair::util::UserAnnotatedTyHelpers;
 
-use rustc_data_structures::fx::FxHashMap;
 use rustc_data_structures::indexed_vec::Idx;
 use rustc::hir::def_id::DefId;
 use rustc::hir::Node;
@@ -50,9 +49,6 @@ pub struct Cx<'a, 'gcx: 'a + 'tcx, 'tcx: 'a> {
 
     /// See field with the same name on `mir::Body`.
     control_flow_destroyed: Vec<(Span, String)>,
-
-    /// Reverse map, from upvar variable `HirId`s to their indices.
-    upvar_indices: FxHashMap<hir::HirId, usize>,
 }
 
 impl<'a, 'gcx, 'tcx> Cx<'a, 'gcx, 'tcx> {
@@ -83,14 +79,6 @@ impl<'a, 'gcx, 'tcx> Cx<'a, 'gcx, 'tcx> {
         // Constants always need overflow checks.
         check_overflow |= constness == hir::Constness::Const;
 
-        // Compute reverse mapping, of uvpars to their indices.
-        let mut upvar_indices = FxHashMap::default();
-        if let Some(upvars) = tables.upvar_list.get(&src_def_id) {
-            upvar_indices.extend(
-                upvars.iter().enumerate().map(|(i, upvar_id)| (upvar_id.var_path.hir_id, i)),
-            );
-        }
-
         Cx {
             tcx,
             infcx,
@@ -104,7 +92,6 @@ impl<'a, 'gcx, 'tcx> Cx<'a, 'gcx, 'tcx> {
             body_owner_kind,
             check_overflow,
             control_flow_destroyed: Vec::new(),
-            upvar_indices,
         }
     }
 
diff --git a/src/librustc_mir/interpret/validity.rs b/src/librustc_mir/interpret/validity.rs
index 851d32203db..552628ee1ce 100644
--- a/src/librustc_mir/interpret/validity.rs
+++ b/src/librustc_mir/interpret/validity.rs
@@ -174,8 +174,7 @@ impl<'rt, 'a, 'mir, 'tcx, M: Machine<'a, 'mir, 'tcx>> ValidityVisitor<'rt, 'a, '
                     if let Some(upvars) = tables.upvar_list.get(&def_id) {
                         // Sometimes the index is beyond the number of upvars (seen
                         // for a generator).
-                        if let Some(upvar_id) = upvars.get(field) {
-                            let var_hir_id = upvar_id.var_path.hir_id;
+                        if let Some((&var_hir_id, _)) = upvars.get_index(field) {
                             let var_node_id = self.ecx.tcx.hir().hir_to_node_id(var_hir_id);
                             if let hir::Node::Binding(pat) = self.ecx.tcx.hir().get(var_node_id) {
                                 if let hir::PatKind::Binding(_, _, ident, _) = pat.node {
diff --git a/src/librustc_resolve/Cargo.toml b/src/librustc_resolve/Cargo.toml
index 968a45e241e..8e3359c7752 100644
--- a/src/librustc_resolve/Cargo.toml
+++ b/src/librustc_resolve/Cargo.toml
@@ -12,6 +12,7 @@ test = false
 
 [dependencies]
 bitflags = "1.0"
+indexmap = "1"
 log = "0.4"
 syntax = { path = "../libsyntax" }
 rustc = { path = "../librustc" }
diff --git a/src/librustc_resolve/lib.rs b/src/librustc_resolve/lib.rs
index 790c4356630..beb36989474 100644
--- a/src/librustc_resolve/lib.rs
+++ b/src/librustc_resolve/lib.rs
@@ -1669,7 +1669,6 @@ pub struct Resolver<'a> {
     label_res_map: NodeMap<NodeId>,
 
     pub upvars: UpvarMap,
-    upvars_seen: NodeMap<NodeSet>,
     pub export_map: ExportMap<NodeId>,
     pub trait_map: TraitMap,
 
@@ -2033,7 +2032,6 @@ impl<'a> Resolver<'a> {
             import_res_map: Default::default(),
             label_res_map: Default::default(),
             upvars: Default::default(),
-            upvars_seen: Default::default(),
             export_map: FxHashMap::default(),
             trait_map: Default::default(),
             module_map,
@@ -4055,26 +4053,18 @@ impl<'a> Resolver<'a> {
                                 Res::Upvar(..) => true,
                                 _ => false,
                             };
-
-                            let seen = self.upvars_seen
-                                           .entry(function_id)
-                                           .or_default();
-                            if seen.contains(&var_id) {
-                                res = Res::Upvar(var_id, function_id);
-                                continue;
-                            }
-                            let vec = self.upvars
-                                          .entry(function_id)
-                                          .or_default();
                             res = Res::Upvar(var_id, function_id);
 
-                            if record_used {
-                                vec.push(Upvar {
-                                    var_id,
-                                    has_parent,
-                                    span,
-                                });
-                                seen.insert(var_id);
+                            match self.upvars.entry(function_id).or_default().entry(var_id) {
+                                indexmap::map::Entry::Occupied(_) => continue,
+                                indexmap::map::Entry::Vacant(entry) => {
+                                    if record_used {
+                                        entry.insert(Upvar {
+                                            has_parent,
+                                            span,
+                                        });
+                                    }
+                                }
                             }
                         }
                         ItemRibKind | FnItemRibKind | AssocItemRibKind => {
diff --git a/src/librustc_typeck/check/upvar.rs b/src/librustc_typeck/check/upvar.rs
index a4f9ede37c9..8ceca20eb07 100644
--- a/src/librustc_typeck/check/upvar.rs
+++ b/src/librustc_typeck/check/upvar.rs
@@ -41,6 +41,7 @@ use rustc::hir::def_id::LocalDefId;
 use rustc::hir::intravisit::{self, NestedVisitorMap, Visitor};
 use rustc::infer::UpvarRegion;
 use rustc::ty::{self, Ty, TyCtxt, UpvarSubsts};
+use rustc_data_structures::fx::FxIndexMap;
 use syntax::ast;
 use syntax_pos::Span;
 
@@ -122,18 +123,19 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
         };
 
         if let Some(upvars) = self.tcx.upvars(closure_def_id) {
-            let mut upvar_list: Vec<ty::UpvarId> = Vec::with_capacity(upvars.len());
-            for upvar in upvars.iter() {
+            let mut upvar_list: FxIndexMap<hir::HirId, ty::UpvarId> =
+                FxIndexMap::with_capacity_and_hasher(upvars.len(), Default::default());
+            for (&var_hir_id, _) in upvars.iter() {
                 let upvar_id = ty::UpvarId {
                     var_path: ty::UpvarPath {
-                        hir_id: upvar.var_id,
+                        hir_id: var_hir_id,
                     },
                     closure_expr_id: LocalDefId::from_def_id(closure_def_id),
                 };
                 debug!("seed upvar_id {:?}", upvar_id);
                 // Adding the upvar Id to the list of Upvars, which will be added
                 // to the map for the closure at the end of the for loop.
-                upvar_list.push(upvar_id);
+                upvar_list.insert(var_hir_id, upvar_id);
 
                 let capture_kind = match capture_clause {
                     hir::CaptureByValue => ty::UpvarCapture::ByValue,
@@ -249,17 +251,17 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
         tcx.upvars(closure_def_id).iter().flat_map(|upvars| {
             upvars
                 .iter()
-                .map(|upvar| {
-                    let upvar_ty = self.node_ty(upvar.var_id);
+                .map(|(&var_hir_id, _)| {
+                    let upvar_ty = self.node_ty(var_hir_id);
                     let upvar_id = ty::UpvarId {
-                        var_path: ty::UpvarPath { hir_id: upvar.var_id },
+                        var_path: ty::UpvarPath { hir_id: var_hir_id },
                         closure_expr_id: LocalDefId::from_def_id(closure_def_id),
                     };
                     let capture = self.tables.borrow().upvar_capture(upvar_id);
 
                     debug!(
                         "var_id={:?} upvar_ty={:?} capture={:?}",
-                        upvar.var_id, upvar_ty, capture
+                        var_hir_id, upvar_ty, capture
                     );
 
                     match capture {
diff --git a/src/librustc_typeck/check/writeback.rs b/src/librustc_typeck/check/writeback.rs
index 9e60bff200e..a535f776dfe 100644
--- a/src/librustc_typeck/check/writeback.rs
+++ b/src/librustc_typeck/check/writeback.rs
@@ -54,7 +54,6 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
         }
         wbcx.visit_body(body);
         wbcx.visit_upvar_capture_map();
-        wbcx.visit_upvar_list_map();
         wbcx.visit_closures();
         wbcx.visit_liberated_fn_sigs();
         wbcx.visit_fru_field_types();
@@ -74,6 +73,11 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
         );
         wbcx.tables.used_trait_imports = used_trait_imports;
 
+        wbcx.tables.upvar_list = mem::replace(
+            &mut self.tables.borrow_mut().upvar_list,
+            Default::default(),
+        );
+
         wbcx.tables.tainted_by_errors = self.is_tainted_by_errors();
 
         debug!(
@@ -343,21 +347,6 @@ impl<'cx, 'gcx, 'tcx> WritebackCx<'cx, 'gcx, 'tcx> {
         }
     }
 
-    /// Runs through the function context's upvar list map and adds the same to
-    /// the TypeckTables. upvarlist is a hashmap of the list of upvars referred
-    /// to in a closure..
-    fn visit_upvar_list_map(&mut self) {
-        for (closure_def_id, upvar_list) in self.fcx.tables.borrow().upvar_list.iter() {
-            debug!(
-                "UpvarIDs captured by closure {:?} are: {:?}",
-                closure_def_id, upvar_list
-            );
-            self.tables
-                .upvar_list
-                .insert(*closure_def_id, upvar_list.to_vec());
-        }
-    }
-
     fn visit_closures(&mut self) {
         let fcx_tables = self.fcx.tables.borrow();
         debug_assert_eq!(fcx_tables.local_id_root, self.tables.local_id_root);
diff --git a/src/libserialize/Cargo.toml b/src/libserialize/Cargo.toml
index 949af0e2b97..fa31a68a75b 100644
--- a/src/libserialize/Cargo.toml
+++ b/src/libserialize/Cargo.toml
@@ -10,4 +10,5 @@ path = "lib.rs"
 crate-type = ["dylib", "rlib"]
 
 [dependencies]
+indexmap = "1"
 smallvec = { version = "0.6.7", features = ["union", "may_dangle"] }
diff --git a/src/libserialize/collection_impls.rs b/src/libserialize/collection_impls.rs
index c0a8fa9d001..80aeecb84d7 100644
--- a/src/libserialize/collection_impls.rs
+++ b/src/libserialize/collection_impls.rs
@@ -217,6 +217,75 @@ impl<T, S> Decodable for HashSet<T, S>
     }
 }
 
+impl<K, V, S> Encodable for indexmap::IndexMap<K, V, S>
+    where K: Encodable + Hash + Eq,
+          V: Encodable,
+          S: BuildHasher,
+{
+    fn encode<E: Encoder>(&self, e: &mut E) -> Result<(), E::Error> {
+        e.emit_map(self.len(), |e| {
+            let mut i = 0;
+            for (key, val) in self {
+                e.emit_map_elt_key(i, |e| key.encode(e))?;
+                e.emit_map_elt_val(i, |e| val.encode(e))?;
+                i += 1;
+            }
+            Ok(())
+        })
+    }
+}
+
+impl<K, V, S> Decodable for indexmap::IndexMap<K, V, S>
+    where K: Decodable + Hash + Eq,
+          V: Decodable,
+          S: BuildHasher + Default,
+{
+    fn decode<D: Decoder>(d: &mut D) -> Result<indexmap::IndexMap<K, V, S>, D::Error> {
+        d.read_map(|d, len| {
+            let state = Default::default();
+            let mut map = indexmap::IndexMap::with_capacity_and_hasher(len, state);
+            for i in 0..len {
+                let key = d.read_map_elt_key(i, |d| Decodable::decode(d))?;
+                let val = d.read_map_elt_val(i, |d| Decodable::decode(d))?;
+                map.insert(key, val);
+            }
+            Ok(map)
+        })
+    }
+}
+
+impl<T, S> Encodable for indexmap::IndexSet<T, S>
+    where T: Encodable + Hash + Eq,
+          S: BuildHasher,
+{
+    fn encode<E: Encoder>(&self, s: &mut E) -> Result<(), E::Error> {
+        s.emit_seq(self.len(), |s| {
+            let mut i = 0;
+            for e in self {
+                s.emit_seq_elt(i, |s| e.encode(s))?;
+                i += 1;
+            }
+            Ok(())
+        })
+    }
+}
+
+impl<T, S> Decodable for indexmap::IndexSet<T, S>
+    where T: Decodable + Hash + Eq,
+          S: BuildHasher + Default,
+{
+    fn decode<D: Decoder>(d: &mut D) -> Result<indexmap::IndexSet<T, S>, D::Error> {
+        d.read_seq(|d, len| {
+            let state = Default::default();
+            let mut set = indexmap::IndexSet::with_capacity_and_hasher(len, state);
+            for i in 0..len {
+                set.insert(d.read_seq_elt(i, |d| Decodable::decode(d))?);
+            }
+            Ok(set)
+        })
+    }
+}
+
 impl<T: Encodable> Encodable for Rc<[T]> {
     fn encode<E: Encoder>(&self, s: &mut E) -> Result<(), E::Error> {
         s.emit_seq(self.len(), |s| {
diff --git a/src/tools/tidy/src/deps.rs b/src/tools/tidy/src/deps.rs
index ad3ac986c94..7922cb14eec 100644
--- a/src/tools/tidy/src/deps.rs
+++ b/src/tools/tidy/src/deps.rs
@@ -92,6 +92,7 @@ const WHITELIST: &[Crate<'_>] = &[
     Crate("fuchsia-zircon-sys"),
     Crate("getopts"),
     Crate("humantime"),
+    Crate("indexmap"),
     Crate("itertools"),
     Crate("jobserver"),
     Crate("kernel32-sys"),