5 files changed, 97 insertions, 25 deletions
diff --git a/crates/ra_arena/src/lib.rs b/crates/ra_arena/src/lib.rs
index a5eeb4118..040977dc4 100644
--- a/crates/ra_arena/src/lib.rs
+++ b/crates/ra_arena/src/lib.rs
@@ -6,6 +6,8 @@ use std::{
    ops::{Index, IndexMut},
 };
+pub mod map;
 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
 pub struct RawId(u32);
diff --git a/crates/ra_arena/src/map.rs b/crates/ra_arena/src/map.rs
new file mode 100644
index 000000000..2f09d677f
--- /dev/null
+++ b/crates/ra_arena/src/map.rs
@@ -0,0 +1,70 @@
+//! A map from arena IDs to some other type. Space requirement is O(highest ID).
+use std::marker::PhantomData;
+use super::ArenaId;
+/// A map from arena IDs to some other type. Space requirement is O(highest ID).
+#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
+pub struct ArenaMap<ID, T> {
+    v: Vec<Option<T>>,
+    _ty: PhantomData<ID>,
+}
+impl<ID: ArenaId, T> ArenaMap<ID, T> {
+    pub fn insert(&mut self, id: ID, t: T) {
+        let idx = Self::to_idx(id);
+        if self.v.capacity() <= idx {
+            self.v.reserve(idx + 1 - self.v.capacity());
+        }
+        if self.v.len() <= idx {
+            while self.v.len() <= idx {
+                self.v.push(None);
+            }
+        }
+        self.v[idx] = Some(t);
+    }
+    pub fn get(&self, id: ID) -> Option<&T> {
+        self.v.get(Self::to_idx(id)).and_then(|it| it.as_ref())
+    }
+    pub fn values(&self) -> impl Iterator<Item = &T> {
+        self.v.iter().filter_map(|o| o.as_ref())
+    }
+    pub fn values_mut(&mut self) -> impl Iterator<Item = &mut T> {
+        self.v.iter_mut().filter_map(|o| o.as_mut())
+    }
+    pub fn iter(&self) -> impl Iterator<Item = (ID, &T)> {
+        self.v
+            .iter()
+            .enumerate()
+            .filter_map(|(idx, o)| Some((Self::from_idx(idx), o.as_ref()?)))
+    }
+    fn to_idx(id: ID) -> usize {
+        u32::from(id.into_raw()) as usize
+    }
+    fn from_idx(idx: usize) -> ID {
+        ID::from_raw((idx as u32).into())
+    }
+}
+impl<ID: ArenaId, T> std::ops::Index<ID> for ArenaMap<ID, T> {
+    type Output = T;
+    fn index(&self, id: ID) -> &T {
+        self.v[Self::to_idx(id)].as_ref().unwrap()
+    }
+}
+impl<ID, T> Default for ArenaMap<ID, T> {
+    fn default() -> Self {
+        ArenaMap {
+            v: Vec::new(),
+            _ty: PhantomData,
+        }
+    }
+}
diff --git a/crates/ra_hir/src/expr.rs b/crates/ra_hir/src/expr.rs
index c87d76735..69144e94f 100644
--- a/crates/ra_hir/src/expr.rs
+++ b/crates/ra_hir/src/expr.rs
@@ -3,7 +3,7 @@ use std::sync::Arc;
 use rustc_hash::FxHashMap;
-use ra_arena::{Arena, RawId, impl_arena_id};
+use ra_arena::{Arena, RawId, impl_arena_id, map::ArenaMap};
 use ra_db::{LocalSyntaxPtr, Cancelable};
 use ra_syntax::{SyntaxNodeRef, ast::{self, AstNode, LoopBodyOwner, ArgListOwner, NameOwner}};
@@ -39,9 +39,9 @@ pub struct Body {
 pub struct BodySyntaxMapping {
    body: Arc<Body>,
    expr_syntax_mapping: FxHashMap<LocalSyntaxPtr, ExprId>,
-    expr_syntax_mapping_back: FxHashMap<ExprId, LocalSyntaxPtr>,
+    expr_syntax_mapping_back: ArenaMap<ExprId, LocalSyntaxPtr>,
    pat_syntax_mapping: FxHashMap<LocalSyntaxPtr, PatId>,
-    pat_syntax_mapping_back: FxHashMap<PatId, LocalSyntaxPtr>,
+    pat_syntax_mapping_back: ArenaMap<PatId, LocalSyntaxPtr>,
 }
 impl Body {
@@ -72,7 +72,7 @@ impl Index<PatId> for Body {
 impl BodySyntaxMapping {
    pub fn expr_syntax(&self, expr: ExprId) -> Option<LocalSyntaxPtr> {
-        self.expr_syntax_mapping_back.get(&expr).cloned()
+        self.expr_syntax_mapping_back.get(expr).cloned()
    }
    pub fn syntax_expr(&self, ptr: LocalSyntaxPtr) -> Option<ExprId> {
        self.expr_syntax_mapping.get(&ptr).cloned()
@@ -83,7 +83,7 @@ impl BodySyntaxMapping {
            .cloned()
    }
    pub fn pat_syntax(&self, pat: PatId) -> Option<LocalSyntaxPtr> {
-        self.pat_syntax_mapping_back.get(&pat).cloned()
+        self.pat_syntax_mapping_back.get(pat).cloned()
    }
    pub fn syntax_pat(&self, ptr: LocalSyntaxPtr) -> Option<PatId> {
        self.pat_syntax_mapping.get(&ptr).cloned()
@@ -334,9 +334,9 @@ struct ExprCollector {
    exprs: Arena<ExprId, Expr>,
    pats: Arena<PatId, Pat>,
    expr_syntax_mapping: FxHashMap<LocalSyntaxPtr, ExprId>,
-    expr_syntax_mapping_back: FxHashMap<ExprId, LocalSyntaxPtr>,
+    expr_syntax_mapping_back: ArenaMap<ExprId, LocalSyntaxPtr>,
    pat_syntax_mapping: FxHashMap<LocalSyntaxPtr, PatId>,
-    pat_syntax_mapping_back: FxHashMap<PatId, LocalSyntaxPtr>,
+    pat_syntax_mapping_back: ArenaMap<PatId, LocalSyntaxPtr>,
 }
 impl ExprCollector {
@@ -345,9 +345,9 @@ impl ExprCollector {
            exprs: Arena::default(),
            pats: Arena::default(),
            expr_syntax_mapping: FxHashMap::default(),
-            expr_syntax_mapping_back: FxHashMap::default(),
+            expr_syntax_mapping_back: ArenaMap::default(),
            pat_syntax_mapping: FxHashMap::default(),
-            pat_syntax_mapping_back: FxHashMap::default(),
+            pat_syntax_mapping_back: ArenaMap::default(),
        }
    }
diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs
index 6bdfdd7b4..d57990cd2 100644
--- a/crates/ra_hir/src/ty.rs
+++ b/crates/ra_hir/src/ty.rs
@@ -22,8 +22,8 @@ use std::sync::Arc;
 use std::{fmt, mem};
 use log;
-use rustc_hash::FxHashMap;
 use ena::unify::{InPlaceUnificationTable, UnifyKey, UnifyValue, NoError};
+use ra_arena::map::ArenaMap;
 use ra_db::Cancelable;
@@ -470,15 +470,15 @@ pub(super) fn type_for_field(db: &impl HirDatabase, def_id: DefId, field: Name)
 /// The result of type inference: A mapping from expressions and patterns to types.
 #[derive(Clone, PartialEq, Eq, Debug)]
 pub struct InferenceResult {
-    type_of_expr: FxHashMap<ExprId, Ty>,
+    type_of_expr: ArenaMap<ExprId, Ty>,
-    type_of_pat: FxHashMap<PatId, Ty>,
+    type_of_pat: ArenaMap<PatId, Ty>,
 }
 impl Index<ExprId> for InferenceResult {
    type Output = Ty;
    fn index(&self, expr: ExprId) -> &Ty {
-        self.type_of_expr.get(&expr).unwrap_or(&Ty::Unknown)
+        self.type_of_expr.get(expr).unwrap_or(&Ty::Unknown)
    }
 }
@@ -486,7 +486,7 @@ impl Index<PatId> for InferenceResult {
    type Output = Ty;
    fn index(&self, pat: PatId) -> &Ty {
-        self.type_of_pat.get(&pat).unwrap_or(&Ty::Unknown)
+        self.type_of_pat.get(pat).unwrap_or(&Ty::Unknown)
    }
 }
@@ -499,8 +499,8 @@ struct InferenceContext<'a, D: HirDatabase> {
    module: Module,
    impl_block: Option<ImplBlock>,
    var_unification_table: InPlaceUnificationTable<TypeVarId>,
-    type_of_expr: FxHashMap<ExprId, Ty>,
+    type_of_expr: ArenaMap<ExprId, Ty>,
-    type_of_pat: FxHashMap<PatId, Ty>,
+    type_of_pat: ArenaMap<PatId, Ty>,
    /// The return type of the function being inferred.
    return_ty: Ty,
 }
@@ -528,8 +528,8 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
        impl_block: Option<ImplBlock>,
    ) -> Self {
        InferenceContext {
-            type_of_expr: FxHashMap::default(),
+            type_of_expr: ArenaMap::default(),
-            type_of_pat: FxHashMap::default(),
+            type_of_pat: ArenaMap::default(),
            var_unification_table: InPlaceUnificationTable::new(),
            return_ty: Ty::Unknown, // set in collect_fn_signature
            db,
@@ -541,12 +541,12 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
    }
    fn resolve_all(mut self) -> InferenceResult {
-        let mut expr_types = mem::replace(&mut self.type_of_expr, FxHashMap::default());
+        let mut expr_types = mem::replace(&mut self.type_of_expr, ArenaMap::default());
        for ty in expr_types.values_mut() {
            let resolved = self.resolve_ty_completely(mem::replace(ty, Ty::Unknown));
            *ty = resolved;
        }
-        let mut pat_types = mem::replace(&mut self.type_of_pat, FxHashMap::default());
+        let mut pat_types = mem::replace(&mut self.type_of_pat, ArenaMap::default());
        for ty in pat_types.values_mut() {
            let resolved = self.resolve_ty_completely(mem::replace(ty, Ty::Unknown));
            *ty = resolved;
@@ -666,7 +666,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
            // resolve locally
            let name = path.as_ident().cloned().unwrap_or_else(Name::self_param);
            if let Some(scope_entry) = self.scopes.resolve_local_name(expr, name) {
-                let ty = ctry!(self.type_of_pat.get(&scope_entry.pat()));
+                let ty = ctry!(self.type_of_pat.get(scope_entry.pat()));
                let ty = self.resolve_ty_as_possible(ty.clone());
                return Ok(Some(ty));
            };
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs
index 20fb783b8..030a20f1b 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -195,16 +195,16 @@ fn infer(content: &str) -> String {
        let inference_result = func.infer(&db).unwrap();
        let body_syntax_mapping = func.body_syntax_mapping(&db).unwrap();
        let mut types = Vec::new();
-        for (pat, ty) in &inference_result.type_of_pat {
+        for (pat, ty) in inference_result.type_of_pat.iter() {
-            let syntax_ptr = if let Some(sp) = body_syntax_mapping.pat_syntax(*pat) {
+            let syntax_ptr = if let Some(sp) = body_syntax_mapping.pat_syntax(pat) {
                sp
            } else {
                continue;
            };
            types.push((syntax_ptr, ty));
        }
-        for (expr, ty) in &inference_result.type_of_expr {
+        for (expr, ty) in inference_result.type_of_expr.iter() {
-            let syntax_ptr = if let Some(sp) = body_syntax_mapping.expr_syntax(*expr) {
+            let syntax_ptr = if let Some(sp) = body_syntax_mapping.expr_syntax(expr) {
                sp
            } else {
                continue;