Repository: rust-analyzer/rust-analyzer
Pull request #2484 (2019-12-05 23:03:53)

DynMap
Implement a `DynMap` a semi-dynamic, semi-static map, which helps to thread heterogeneously typed info in a uniform way. Totally inspired by https://github.com/JetBrains/kotlin/blob/df3bee30384787d8951ea548a4257c2cb52a16a3/compiler/frontend/src/org/jetbrains/kotlin/resolve/BindingContext.java. 

@flodiebold wdyt? Seems like a potentially useful pattern for various source-map-like things.

matklad: The main idea here is that `DynMap` is both:

* dynamic enough to process heterogeneous collection of items in a single action, without statically dispatching on every time
* static enough that shooting yourself in the foot with runtime "type" error is, while not impossible, highly unlikely. 
matklad: So, @flodiebold what's your feeling here? Is this in general a worthwhile thing to try?
flodiebold: Sure, I think it's worth a try!
matklad: bors r+

Patch:
diff --git a/Cargo.lock b/Cargo.lock
index 0e7594f807..a95f9139f1 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -13,6 +13,11 @@ name = "anyhow"
 version = "1.0.25"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
+[[package]]
+name = "anymap"
+version = "0.12.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
 [[package]]
 name = "arrayvec"
 version = "0.5.1"
@@ -958,6 +963,7 @@ dependencies = [
 name = "ra_hir_def"
 version = "0.1.0"
 dependencies = [
+ "anymap 0.12.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "either 1.5.3 (registry+https://github.com/rust-lang/crates.io-index)",
  "insta 0.12.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "log 0.4.8 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -1776,6 +1782,7 @@ dependencies = [
 [metadata]
 "checksum aho-corasick 0.7.6 (registry+https://github.com/rust-lang/crates.io-index)" = "58fb5e95d83b38284460a5fda7d6470aa0b8844d283a0b614b8535e880800d2d"
 "checksum anyhow 1.0.25 (registry+https://github.com/rust-lang/crates.io-index)" = "9267dff192e68f3399525901e709a48c1d3982c9c072fa32f2127a0cb0babf14"
+"checksum anymap 0.12.1 (registry+https://github.com/rust-lang/crates.io-index)" = "33954243bd79057c2de7338850b85983a44588021f8a5fee574a8888c6de4344"
 "checksum arrayvec 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)" = "cff77d8686867eceff3105329d4698d96c2391c176d5d03adc90c7389162b5b8"
 "checksum atty 0.2.13 (registry+https://github.com/rust-lang/crates.io-index)" = "1803c647a3ec87095e7ae7acfca019e98de5ec9a7d01343f611cf3152ed71a90"
 "checksum autocfg 0.1.7 (registry+https://github.com/rust-lang/crates.io-index)" = "1d49d90015b3c36167a20fe2810c5cd875ad504b39cff3d4eae7977e6b7c1cb2"
diff --git a/crates/ra_hir/src/from_source.rs b/crates/ra_hir/src/from_source.rs
index 5cb222bd38..437f800c1e 100644
--- a/crates/ra_hir/src/from_source.rs
+++ b/crates/ra_hir/src/from_source.rs
@@ -1,9 +1,7 @@
 //! FIXME: write short doc here
-use either::Either;
-
 use hir_def::{
-    child_from_source::ChildFromSource, nameres::ModuleSource, AstItemDef, EnumVariantId, ImplId,
-    LocationCtx, ModuleId, TraitId, VariantId,
+    child_by_source::ChildBySource, dyn_map::DynMap, keys, nameres::ModuleSource, AstItemDef,
+    EnumVariantId, LocationCtx, ModuleId, VariantId,
 };
 use hir_expand::{name::AsName, AstId, MacroDefId, MacroDefKind};
 use ra_syntax::{
@@ -53,8 +51,9 @@ impl FromSource for Trait {
 impl FromSource for Function {
     type Ast = ast::FnDef;
     fn from_source(db: &(impl DefDatabase + AstDatabase), src: InFile<Self::Ast>) -> Option<Self> {
-        Container::find(db, src.as_ref().map(|it| it.syntax()))?
-            .child_from_source(db, src)
+        Container::find(db, src.as_ref().map(|it| it.syntax()))?.child_by_source(db)[keys::FUNCTION]
+            .get(&src)
+            .copied()
             .map(Function::from)
     }
 }
@@ -62,26 +61,29 @@ impl FromSource for Function {
 impl FromSource for Const {
     type Ast = ast::ConstDef;
     fn from_source(db: &(impl DefDatabase + AstDatabase), src: InFile<Self::Ast>) -> Option<Self> {
-        Container::find(db, src.as_ref().map(|it| it.syntax()))?
-            .child_from_source(db, src)
+        Container::find(db, src.as_ref().map(|it| it.syntax()))?.child_by_source(db)[keys::CONST]
+            .get(&src)
+            .copied()
             .map(Const::from)
     }
 }
 impl FromSource for Static {
     type Ast = ast::StaticDef;
     fn from_source(db: &(impl DefDatabase + AstDatabase), src: InFile<Self::Ast>) -> Option<Self> {
-        match Container::find(db, src.as_ref().map(|it| it.syntax()))? {
-            Container::Module(it) => it.id.child_from_source(db, src).map(Static::from),
-            Container::Trait(_) | Container::ImplBlock(_) => None,
-        }
+        Container::find(db, src.as_ref().map(|it| it.syntax()))?.child_by_source(db)[keys::STATIC]
+            .get(&src)
+            .copied()
+            .map(Static::from)
     }
 }
 
 impl FromSource for TypeAlias {
     type Ast = ast::TypeAliasDef;
     fn from_source(db: &(impl DefDatabase + AstDatabase), src: InFile<Self::Ast>) -> Option<Self> {
-        Container::find(db, src.as_ref().map(|it| it.syntax()))?
-            .child_from_source(db, src)
+        Container::find(db, src.as_ref().map(|it| it.syntax()))?.child_by_source(db)
+            [keys::TYPE_ALIAS]
+            .get(&src)
+            .copied()
             .map(TypeAlias::from)
     }
 }
@@ -116,32 +118,41 @@ impl FromSource for EnumVariant {
         let parent_enum = src.value.parent_enum();
         let src_enum = InFile { file_id: src.file_id, value: parent_enum };
         let parent_enum = Enum::from_source(db, src_enum)?;
-        parent_enum.id.child_from_source(db, src).map(EnumVariant::from)
+        parent_enum.id.child_by_source(db)[keys::ENUM_VARIANT]
+            .get(&src)
+            .copied()
+            .map(EnumVariant::from)
     }
 }
 
 impl FromSource for StructField {
     type Ast = FieldSource;
     fn from_source(db: &(impl DefDatabase + AstDatabase), src: InFile<Self::Ast>) -> Option<Self> {
+        let src = src.as_ref();
+
+        // FIXME this is buggy
         let variant_id: VariantId = match src.value {
-            FieldSource::Named(ref field) => {
+            FieldSource::Named(field) => {
                 let value = field.syntax().ancestors().find_map(ast::StructDef::cast)?;
                 let src = InFile { file_id: src.file_id, value };
                 let def = Struct::from_source(db, src)?;
                 def.id.into()
             }
-            FieldSource::Pos(ref field) => {
+            FieldSource::Pos(field) => {
                 let value = field.syntax().ancestors().find_map(ast::EnumVariant::cast)?;
                 let src = InFile { file_id: src.file_id, value };
                 let def = EnumVariant::from_source(db, src)?;
                 EnumVariantId::from(def).into()
             }
         };
-        let src = src.map(|field_source| match field_source {
-            FieldSource::Pos(it) => Either::Left(it),
-            FieldSource::Named(it) => Either::Right(it),
-        });
-        variant_id.child_from_source(db, src).map(StructField::from)
+
+        let dyn_map = variant_id.child_by_source(db);
+        match src.value {
+            FieldSource::Pos(it) => dyn_map[keys::TUPLE_FIELD].get(&src.with_value(it.clone())),
+            FieldSource::Named(it) => dyn_map[keys::RECORD_FIELD].get(&src.with_value(it.clone())),
+        }
+        .copied()
+        .map(StructField::from)
     }
 }
 
@@ -255,21 +266,12 @@ impl Container {
     }
 }
 
-impl<CHILD, SOURCE> ChildFromSource<CHILD, SOURCE> for Container
-where
-    TraitId: ChildFromSource<CHILD, SOURCE>,
-    ImplId: ChildFromSource<CHILD, SOURCE>,
-    ModuleId: ChildFromSource<CHILD, SOURCE>,
-{
-    fn child_from_source(
-        &self,
-        db: &impl DefDatabase,
-        child_source: InFile<SOURCE>,
-    ) -> Option<CHILD> {
+impl ChildBySource for Container {
+    fn child_by_source(&self, db: &impl DefDatabase) -> DynMap {
         match self {
-            Container::Trait(it) => it.id.child_from_source(db, child_source),
-            Container::ImplBlock(it) => it.id.child_from_source(db, child_source),
-            Container::Module(it) => it.id.child_from_source(db, child_source),
+            Container::Trait(it) => it.id.child_by_source(db),
+            Container::ImplBlock(it) => it.id.child_by_source(db),
+            Container::Module(it) => it.id.child_by_source(db),
         }
     }
 }
diff --git a/crates/ra_hir_def/Cargo.toml b/crates/ra_hir_def/Cargo.toml
index cf3a446fcc..b1923bbf2e 100644
--- a/crates/ra_hir_def/Cargo.toml
+++ b/crates/ra_hir_def/Cargo.toml
@@ -12,6 +12,7 @@ log = "0.4.5"
 once_cell = "1.0.1"
 rustc-hash = "1.0"
 either = "1.5"
+anymap = "0.12"
 
 ra_arena = { path = "../ra_arena" }
 ra_db = { path = "../ra_db" }
diff --git a/crates/ra_hir_def/src/child_by_source.rs b/crates/ra_hir_def/src/child_by_source.rs
new file mode 100644
index 0000000000..a3574a9dbb
--- /dev/null
+++ b/crates/ra_hir_def/src/child_by_source.rs
@@ -0,0 +1,139 @@
+//! When *constructing* `hir`, we start at some parent syntax node and recursively
+//! lower the children.
+//!
+//! This modules allows one to go in the opposite direction: start with a syntax
+//! node for a *child*, and get its hir.
+
+use either::Either;
+
+use crate::{
+    db::DefDatabase,
+    dyn_map::DynMap,
+    keys,
+    src::{HasChildSource, HasSource},
+    AssocItemId, EnumId, EnumVariantId, ImplId, Lookup, ModuleDefId, ModuleId, StructFieldId,
+    TraitId, VariantId,
+};
+
+pub trait ChildBySource {
+    fn child_by_source(&self, db: &impl DefDatabase) -> DynMap;
+}
+
+impl ChildBySource for TraitId {
+    fn child_by_source(&self, db: &impl DefDatabase) -> DynMap {
+        let mut res = DynMap::default();
+
+        let data = db.trait_data(*self);
+        for (_name, item) in data.items.iter() {
+            match *item {
+                AssocItemId::FunctionId(func) => {
+                    let src = func.lookup(db).source(db);
+                    res[keys::FUNCTION].insert(src, func)
+                }
+                AssocItemId::ConstId(konst) => {
+                    let src = konst.lookup(db).source(db);
+                    res[keys::CONST].insert(src, konst)
+                }
+                AssocItemId::TypeAliasId(ty) => {
+                    let src = ty.lookup(db).source(db);
+                    res[keys::TYPE_ALIAS].insert(src, ty)
+                }
+            }
+        }
+
+        res
+    }
+}
+
+impl ChildBySource for ImplId {
+    fn child_by_source(&self, db: &impl DefDatabase) -> DynMap {
+        let mut res = DynMap::default();
+
+        let data = db.impl_data(*self);
+        for &item in data.items.iter() {
+            match item {
+                AssocItemId::FunctionId(func) => {
+                    let src = func.lookup(db).source(db);
+                    res[keys::FUNCTION].insert(src, func)
+                }
+                AssocItemId::ConstId(konst) => {
+                    let src = konst.lookup(db).source(db);
+                    res[keys::CONST].insert(src, konst)
+                }
+                AssocItemId::TypeAliasId(ty) => {
+                    let src = ty.lookup(db).source(db);
+                    res[keys::TYPE_ALIAS].insert(src, ty)
+                }
+            }
+        }
+
+        res
+    }
+}
+
+impl ChildBySource for ModuleId {
+    fn child_by_source(&self, db: &impl DefDatabase) -> DynMap {
+        let mut res = DynMap::default();
+
+        let crate_def_map = db.crate_def_map(self.krate);
+        for item in crate_def_map[self.local_id].scope.declarations() {
+            match item {
+                ModuleDefId::FunctionId(func) => {
+                    let src = func.lookup(db).source(db);
+                    res[keys::FUNCTION].insert(src, func)
+                }
+                ModuleDefId::ConstId(konst) => {
+                    let src = konst.lookup(db).source(db);
+                    res[keys::CONST].insert(src, konst)
+                }
+                ModuleDefId::StaticId(statik) => {
+                    let src = statik.lookup(db).source(db);
+                    res[keys::STATIC].insert(src, statik)
+                }
+                ModuleDefId::TypeAliasId(ty) => {
+                    let src = ty.lookup(db).source(db);
+                    res[keys::TYPE_ALIAS].insert(src, ty)
+                }
+                _ => (),
+            }
+        }
+
+        res
+    }
+}
+
+impl ChildBySource for VariantId {
+    fn child_by_source(&self, db: &impl DefDatabase) -> DynMap {
+        let mut res = DynMap::default();
+
+        let arena_map = self.child_source(db);
+        let arena_map = arena_map.as_ref();
+        for (local_id, source) in arena_map.value.iter() {
+            let id = StructFieldId { parent: *self, local_id };
+            match source {
+                Either::Left(source) => {
+                    res[keys::TUPLE_FIELD].insert(arena_map.with_value(source.clone()), id)
+                }
+                Either::Right(source) => {
+                    res[keys::RECORD_FIELD].insert(arena_map.with_value(source.clone()), id)
+                }
+            }
+        }
+        res
+    }
+}
+
+impl ChildBySource for EnumId {
+    fn child_by_source(&self, db: &impl DefDatabase) -> DynMap {
+        let mut res = DynMap::default();
+
+        let arena_map = self.child_source(db);
+        let arena_map = arena_map.as_ref();
+        for (local_id, source) in arena_map.value.iter() {
+            let id = EnumVariantId { parent: *self, local_id };
+            res[keys::ENUM_VARIANT].insert(arena_map.with_value(source.clone()), id)
+        }
+
+        res
+    }
+}
diff --git a/crates/ra_hir_def/src/child_from_source.rs b/crates/ra_hir_def/src/child_from_source.rs
deleted file mode 100644
index 37d4b78706..0000000000
--- a/crates/ra_hir_def/src/child_from_source.rs
+++ /dev/null
@@ -1,276 +0,0 @@
-//! When *constructing* `hir`, we start at some parent syntax node and recursively
-//! lower the children.
-//!
-//! This modules allows one to go in the opposite direction: start with a syntax
-//! node for a *child*, and get its hir.
-
-use either::Either;
-use hir_expand::InFile;
-use ra_syntax::{ast, AstNode, AstPtr};
-
-use crate::{
-    db::DefDatabase,
-    src::{HasChildSource, HasSource},
-    AssocItemId, ConstId, EnumId, EnumVariantId, FunctionId, ImplId, Lookup, ModuleDefId, ModuleId,
-    StaticId, StructFieldId, TraitId, TypeAliasId, VariantId,
-};
-
-pub trait ChildFromSource<CHILD, SOURCE> {
-    fn child_from_source(
-        &self,
-        db: &impl DefDatabase,
-        child_source: InFile<SOURCE>,
-    ) -> Option<CHILD>;
-}
-
-impl ChildFromSource<FunctionId, ast::FnDef> for TraitId {
-    fn child_from_source(
-        &self,
-        db: &impl DefDatabase,
-        child_source: InFile<ast::FnDef>,
-    ) -> Option<FunctionId> {
-        let data = db.trait_data(*self);
-        data.items
-            .iter()
-            .filter_map(|(_, item)| match item {
-                AssocItemId::FunctionId(it) => Some(*it),
-                _ => None,
-            })
-            .find(|func| {
-                let source = func.lookup(db).source(db);
-                same_source(&source, &child_source)
-            })
-    }
-}
-
-impl ChildFromSource<FunctionId, ast::FnDef> for ImplId {
-    fn child_from_source(
-        &self,
-        db: &impl DefDatabase,
-        child_source: InFile<ast::FnDef>,
-    ) -> Option<FunctionId> {
-        let data = db.impl_data(*self);
-        data.items
-            .iter()
-            .filter_map(|item| match item {
-                AssocItemId::FunctionId(it) => Some(*it),
-                _ => None,
-            })
-            .find(|func| {
-                let source = func.lookup(db).source(db);
-                same_source(&source, &child_source)
-            })
-    }
-}
-
-impl ChildFromSource<FunctionId, ast::FnDef> for ModuleId {
-    fn child_from_source(
-        &self,
-        db: &impl DefDatabase,
-        child_source: InFile<ast::FnDef>,
-    ) -> Option<FunctionId> {
-        let crate_def_map = db.crate_def_map(self.krate);
-        let res = crate_def_map[self.local_id]
-            .scope
-            .declarations()
-            .filter_map(|item| match item {
-                ModuleDefId::FunctionId(it) => Some(it),
-                _ => None,
-            })
-            .find(|func| {
-                let source = func.lookup(db).source(db);
-                same_source(&source, &child_source)
-            });
-        res
-    }
-}
-
-impl ChildFromSource<ConstId, ast::ConstDef> for TraitId {
-    fn child_from_source(
-        &self,
-        db: &impl DefDatabase,
-        child_source: InFile<ast::ConstDef>,
-    ) -> Option<ConstId> {
-        let data = db.trait_data(*self);
-        data.items
-            .iter()
-            .filter_map(|(_, item)| match item {
-                AssocItemId::ConstId(it) => Some(*it),
-                _ => None,
-            })
-            .find(|func| {
-                let source = func.lookup(db).source(db);
-                same_source(&source, &child_source)
-            })
-    }
-}
-
-impl ChildFromSource<ConstId, ast::ConstDef> for ImplId {
-    fn child_from_source(
-        &self,
-        db: &impl DefDatabase,
-        child_source: InFile<ast::ConstDef>,
-    ) -> Option<ConstId> {
-        let data = db.impl_data(*self);
-        data.items
-            .iter()
-            .filter_map(|item| match item {
-                AssocItemId::ConstId(it) => Some(*it),
-                _ => None,
-            })
-            .find(|func| {
-                let source = func.lookup(db).source(db);
-                same_source(&source, &child_source)
-            })
-    }
-}
-
-impl ChildFromSource<ConstId, ast::ConstDef> for ModuleId {
-    fn child_from_source(
-        &self,
-        db: &impl DefDatabase,
-        child_source: InFile<ast::ConstDef>,
-    ) -> Option<ConstId> {
-        let crate_def_map = db.crate_def_map(self.krate);
-        let res = crate_def_map[self.local_id]
-            .scope
-            .declarations()
-            .filter_map(|item| match item {
-                ModuleDefId::ConstId(it) => Some(it),
-                _ => None,
-            })
-            .find(|func| {
-                let source = func.lookup(db).source(db);
-                same_source(&source, &child_source)
-            });
-        res
-    }
-}
-
-impl ChildFromSource<TypeAliasId, ast::TypeAliasDef> for TraitId {
-    fn child_from_source(
-        &self,
-        db: &impl DefDatabase,
-        child_source: InFile<ast::TypeAliasDef>,
-    ) -> Option<TypeAliasId> {
-        let data = db.trait_data(*self);
-        data.items
-            .iter()
-            .filter_map(|(_, item)| match item {
-                AssocItemId::TypeAliasId(it) => Some(*it),
-                _ => None,
-            })
-            .find(|func| {
-                let source = func.lookup(db).source(db);
-                same_source(&source, &child_source)
-            })
-    }
-}
-
-impl ChildFromSource<TypeAliasId, ast::TypeAliasDef> for ImplId {
-    fn child_from_source(
-        &self,
-        db: &impl DefDatabase,
-        child_source: InFile<ast::TypeAliasDef>,
-    ) -> Option<TypeAliasId> {
-        let data = db.impl_data(*self);
-        data.items
-            .iter()
-            .filter_map(|item| match item {
-                AssocItemId::TypeAliasId(it) => Some(*it),
-                _ => None,
-            })
-            .find(|func| {
-                let source = func.lookup(db).source(db);
-                same_source(&source, &child_source)
-            })
-    }
-}
-
-impl ChildFromSource<TypeAliasId, ast::TypeAliasDef> for ModuleId {
-    fn child_from_source(
-        &self,
-        db: &impl DefDatabase,
-        child_source: InFile<ast::TypeAliasDef>,
-    ) -> Option<TypeAliasId> {
-        let crate_def_map = db.crate_def_map(self.krate);
-        let res = crate_def_map[self.local_id]
-            .scope
-            .declarations()
-            .filter_map(|item| match item {
-                ModuleDefId::TypeAliasId(it) => Some(it),
-                _ => None,
-            })
-            .find(|func| {
-                let source = func.lookup(db).source(db);
-                same_source(&source, &child_source)
-            });
-        res
-    }
-}
-
-impl ChildFromSource<StaticId, ast::StaticDef> for ModuleId {
-    fn child_from_source(
-        &self,
-        db: &impl DefDatabase,
-        child_source: InFile<ast::StaticDef>,
-    ) -> Option<StaticId> {
-        let crate_def_map = db.crate_def_map(self.krate);
-        let res = crate_def_map[self.local_id]
-            .scope
-            .declarations()
-            .filter_map(|item| match item {
-                ModuleDefId::StaticId(it) => Some(it),
-                _ => None,
-            })
-            .find(|func| {
-                let source = func.lookup(db).source(db);
-                same_source(&source, &child_source)
-            });
-        res
-    }
-}
-
-impl ChildFromSource<StructFieldId, Either<ast::TupleFieldDef, ast::RecordFieldDef>> for VariantId {
-    fn child_from_source(
-        &self,
-        db: &impl DefDatabase,
-        child_source: InFile<Either<ast::TupleFieldDef, ast::RecordFieldDef>>,
-    ) -> Option<StructFieldId> {
-        let arena_map = self.child_source(db);
-        let (local_id, _) = arena_map.as_ref().value.iter().find(|(_local_id, source)| {
-            child_source.file_id == arena_map.file_id
-                && match (source, &child_source.value) {
-                    (Either::Left(a), Either::Left(b)) => AstPtr::new(a) == AstPtr::new(b),
-                    (Either::Right(a), Either::Right(b)) => AstPtr::new(a) == AstPtr::new(b),
-                    _ => false,
-                }
-        })?;
-        Some(StructFieldId { parent: *self, local_id })
-    }
-}
-
-impl ChildFromSource<EnumVariantId, ast::EnumVariant> for EnumId {
-    fn child_from_source(
-        &self,
-        db: &impl DefDatabase,
-        child_source: InFile<ast::EnumVariant>,
-    ) -> Option<EnumVariantId> {
-        let arena_map = self.child_source(db);
-        let (local_id, _) = arena_map.as_ref().value.iter().find(|(_local_id, source)| {
-            child_source.file_id == arena_map.file_id
-                && AstPtr::new(*source) == AstPtr::new(&child_source.value)
-        })?;
-        Some(EnumVariantId { parent: *self, local_id })
-    }
-}
-
-/// XXX: AST Nodes and SyntaxNodes have identity equality semantics: nodes are
-/// equal if they point to exactly the same object.
-///
-/// In general, we do not guarantee that we have exactly one instance of a
-/// syntax tree for each file. We probably should add such guarantee, but, for
-/// the time being, we will use identity-less AstPtr comparison.
-fn same_source<N: AstNode>(s1: &InFile<N>, s2: &InFile<N>) -> bool {
-    s1.as_ref().map(AstPtr::new) == s2.as_ref().map(AstPtr::new)
-}
diff --git a/crates/ra_hir_def/src/dyn_map.rs b/crates/ra_hir_def/src/dyn_map.rs
new file mode 100644
index 0000000000..6f269d7b01
--- /dev/null
+++ b/crates/ra_hir_def/src/dyn_map.rs
@@ -0,0 +1,108 @@
+//! This module defines a `DynMap` -- a container for heterogeneous maps.
+//!
+//! This means that `DynMap` stores a bunch of hash maps inside, and those maps
+//! can be of different types.
+//!
+//! It is used like this:
+//!
+//! ```
+//! // keys define submaps of a `DynMap`
+//! const STRING_TO_U32: Key<String, u32> = Key::new();
+//! const U32_TO_VEC: Key<u32, Vec<bool>> = Key::new();
+//!
+//! // Note: concrete type, no type params!
+//! let mut map = DynMap::new();
+//!
+//! // To access a specific map, index the `DynMap` by `Key`:
+//! map[STRING_TO_U32].insert("hello".to_string(), 92);
+//! let value = map[U32_TO_VEC].get(92);
+//! assert!(value.is_none());
+//! ```
+//!
+//! This is a work of fiction. Any similarities to Kotlin's `BindingContext` are
+//! a coincidence.
+use std::{
+    hash::Hash,
+    marker::PhantomData,
+    ops::{Index, IndexMut},
+};
+
+use anymap::Map;
+use rustc_hash::FxHashMap;
+
+pub struct Key<K, V, P = (K, V)> {
+    _phantom: PhantomData<(K, V, P)>,
+}
+
+impl<K, V, P> Key<K, V, P> {
+    pub(crate) const fn new() -> Key<K, V, P> {
+        Key { _phantom: PhantomData }
+    }
+}
+
+impl<K, V, P> Copy for Key<K, V, P> {}
+
+impl<K, V, P> Clone for Key<K, V, P> {
+    fn clone(&self) -> Key<K, V, P> {
+        *self
+    }
+}
+
+pub trait Policy {
+    type K;
+    type V;
+
+    fn insert(map: &mut DynMap, key: Self::K, value: Self::V);
+    fn get<'a>(map: &'a DynMap, key: &Self::K) -> Option<&'a Self::V>;
+}
+
+impl<K: Hash + Eq + 'static, V: 'static> Policy for (K, V) {
+    type K = K;
+    type V = V;
+    fn insert(map: &mut DynMap, key: K, value: V) {
+        map.map.entry::<FxHashMap<K, V>>().or_insert_with(Default::default).insert(key, value);
+    }
+    fn get<'a>(map: &'a DynMap, key: &K) -> Option<&'a V> {
+        map.map.get::<FxHashMap<K, V>>()?.get(key)
+    }
+}
+
+pub struct DynMap {
+    pub(crate) map: Map,
+}
+
+impl Default for DynMap {
+    fn default() -> Self {
+        DynMap { map: Map::new() }
+    }
+}
+
+#[repr(transparent)]
+pub struct KeyMap<KEY> {
+    map: DynMap,
+    _phantom: PhantomData<KEY>,
+}
+
+impl<P: Policy> KeyMap<Key<P::K, P::V, P>> {
+    pub fn insert(&mut self, key: P::K, value: P::V) {
+        P::insert(&mut self.map, key, value)
+    }
+    pub fn get(&self, key: &P::K) -> Option<&P::V> {
+        P::get(&self.map, key)
+    }
+}
+
+impl<P: Policy> Index<Key<P::K, P::V, P>> for DynMap {
+    type Output = KeyMap<Key<P::K, P::V, P>>;
+    fn index(&self, _key: Key<P::K, P::V, P>) -> &Self::Output {
+        // Safe due to `#[repr(transparent)]`.
+        unsafe { std::mem::transmute::<&DynMap, &KeyMap<Key<P::K, P::V, P>>>(self) }
+    }
+}
+
+impl<P: Policy> IndexMut<Key<P::K, P::V, P>> for DynMap {
+    fn index_mut(&mut self, _key: Key<P::K, P::V, P>) -> &mut Self::Output {
+        // Safe due to `#[repr(transparent)]`.
+        unsafe { std::mem::transmute::<&mut DynMap, &mut KeyMap<Key<P::K, P::V, P>>>(self) }
+    }
+}
diff --git a/crates/ra_hir_def/src/keys.rs b/crates/ra_hir_def/src/keys.rs
new file mode 100644
index 0000000000..447b7e3baa
--- /dev/null
+++ b/crates/ra_hir_def/src/keys.rs
@@ -0,0 +1,48 @@
+//! keys to be used with `DynMap`
+
+use std::marker::PhantomData;
+
+use hir_expand::InFile;
+use ra_syntax::{ast, AstNode, AstPtr};
+use rustc_hash::FxHashMap;
+
+use crate::{
+    dyn_map::{DynMap, Policy},
+    ConstId, EnumVariantId, FunctionId, StaticId, StructFieldId, TypeAliasId,
+};
+
+type Key<K, V> = crate::dyn_map::Key<InFile<K>, V, AstPtrPolicy<K, V>>;
+
+pub const FUNCTION: Key<ast::FnDef, FunctionId> = Key::new();
+pub const CONST: Key<ast::ConstDef, ConstId> = Key::new();
+pub const STATIC: Key<ast::StaticDef, StaticId> = Key::new();
+pub const ENUM_VARIANT: Key<ast::EnumVariant, EnumVariantId> = Key::new();
+pub const TYPE_ALIAS: Key<ast::TypeAliasDef, TypeAliasId> = Key::new();
+pub const TUPLE_FIELD: Key<ast::TupleFieldDef, StructFieldId> = Key::new();
+pub const RECORD_FIELD: Key<ast::RecordFieldDef, StructFieldId> = Key::new();
+
+/// XXX: AST Nodes and SyntaxNodes have identity equality semantics: nodes are
+/// equal if they point to exactly the same object.
+///
+/// In general, we do not guarantee that we have exactly one instance of a
+/// syntax tree for each file. We probably should add such guarantee, but, for
+/// the time being, we will use identity-less AstPtr comparison.
+pub struct AstPtrPolicy<AST, ID> {
+    _phantom: PhantomData<(AST, ID)>,
+}
+
+impl<AST: AstNode + 'static, ID: 'static> Policy for AstPtrPolicy<AST, ID> {
+    type K = InFile<AST>;
+    type V = ID;
+    fn insert(map: &mut DynMap, key: InFile<AST>, value: ID) {
+        let key = key.as_ref().map(AstPtr::new);
+        map.map
+            .entry::<FxHashMap<InFile<AstPtr<AST>>, ID>>()
+            .or_insert_with(Default::default)
+            .insert(key, value);
+    }
+    fn get<'a>(map: &'a DynMap, key: &InFile<AST>) -> Option<&'a ID> {
+        let key = key.as_ref().map(AstPtr::new);
+        map.map.get::<FxHashMap<InFile<AstPtr<AST>>, ID>>()?.get(&key)
+    }
+}
diff --git a/crates/ra_hir_def/src/lib.rs b/crates/ra_hir_def/src/lib.rs
index e02622f62e..68e66d2765 100644
--- a/crates/ra_hir_def/src/lib.rs
+++ b/crates/ra_hir_def/src/lib.rs
@@ -16,6 +16,9 @@ pub mod builtin_type;
 pub mod diagnostics;
 pub mod per_ns;
 
+pub mod dyn_map;
+pub mod keys;
+
 pub mod adt;
 pub mod data;
 pub mod generics;
@@ -30,7 +33,7 @@ mod trace;
 pub mod nameres;
 
 pub mod src;
-pub mod child_from_source;
+pub mod child_by_source;
 
 #[cfg(test)]
 mod test_db;
diff --git a/crates/ra_hir_def/src/per_ns.rs b/crates/ra_hir_def/src/per_ns.rs
index 3a5105028f..00e866bf9f 100644
--- a/crates/ra_hir_def/src/per_ns.rs
+++ b/crates/ra_hir_def/src/per_ns.rs
@@ -11,6 +11,8 @@ use crate::ModuleDefId;
 pub struct PerNs {
     pub types: Option<ModuleDefId>,
     pub values: Option<ModuleDefId>,
+    /// Since macros has different type, many methods simply ignore it.
+    /// We can only use special method like `get_macros` to access it.
     pub macros: Option<MacroDefId>,
 }
 
diff --git a/crates/ra_hir_ty/src/infer/expr.rs b/crates/ra_hir_ty/src/infer/expr.rs
index b8df277063..1e78f6efd4 100644
--- a/crates/ra_hir_ty/src/infer/expr.rs
+++ b/crates/ra_hir_ty/src/infer/expr.rs
@@ -201,7 +201,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
             }
             Expr::Return { expr } => {
                 if let Some(expr) = expr {
-                    self.infer_expr_coerce(*expr, &Expectation::has_type(self.return_ty.clone()));
+                    self.infer_expr(*expr, &Expectation::has_type(self.return_ty.clone()));
                 }
                 Ty::simple(TypeCtor::Never)
             }
@@ -245,7 +245,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 ty
             }
             Expr::Field { expr, name } => {
-                let receiver_ty = self.infer_expr_inner(*expr, &Expectation::none());
+                let receiver_ty = self.infer_expr(*expr, &Expectation::none());
                 let canonicalized = self.canonicalizer().canonicalize_ty(receiver_ty);
                 let ty = autoderef::autoderef(
                     self.db,
@@ -280,7 +280,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 self.normalize_associated_types_in(ty)
             }
             Expr::Await { expr } => {
-                let inner_ty = self.infer_expr_inner(*expr, &Expectation::none());
+                let inner_ty = self.infer_expr(*expr, &Expectation::none());
                 let ty = match self.resolve_future_future_output() {
                     Some(future_future_output_alias) => {
                         let ty = self.table.new_type_var();
@@ -299,7 +299,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 ty
             }
             Expr::Try { expr } => {
-                let inner_ty = self.infer_expr_inner(*expr, &Expectation::none());
+                let inner_ty = self.infer_expr(*expr, &Expectation::none());
                 let ty = match self.resolve_ops_try_ok() {
                     Some(ops_try_ok_alias) => {
                         let ty = self.table.new_type_var();
@@ -318,7 +318,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 ty
             }
             Expr::Cast { expr, type_ref } => {
-                let _inner_ty = self.infer_expr_inner(*expr, &Expectation::none());
+                let _inner_ty = self.infer_expr(*expr, &Expectation::none());
                 let cast_ty = self.make_ty(type_ref);
                 // FIXME check the cast...
                 cast_ty
@@ -334,11 +334,12 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                     } else {
                         Expectation::none()
                     };
-                let inner_ty = self.infer_expr_inner(*expr, &expectation);
+                // FIXME reference coercions etc.
+                let inner_ty = self.infer_expr(*expr, &expectation);
                 Ty::apply_one(TypeCtor::Ref(*mutability), inner_ty)
             }
             Expr::Box { expr } => {
-                let inner_ty = self.infer_expr_inner(*expr, &Expectation::none());
+                let inner_ty = self.infer_expr(*expr, &Expectation::none());
                 if let Some(box_) = self.resolve_boxed_box() {
                     Ty::apply_one(TypeCtor::Adt(box_), inner_ty)
                 } else {
@@ -346,7 +347,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 }
             }
             Expr::UnaryOp { expr, op } => {
-                let inner_ty = self.infer_expr_inner(*expr, &Expectation::none());
+                let inner_ty = self.infer_expr(*expr, &Expectation::none());
                 match op {
                     UnaryOp::Deref => match self.resolver.krate() {
                         Some(krate) => {
@@ -416,7 +417,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 _ => Ty::Unknown,
             },
             Expr::Range { lhs, rhs, range_type } => {
-                let lhs_ty = lhs.map(|e| self.infer_expr_inner(e, &Expectation::none()));
+                let lhs_ty = lhs.map(|e| self.infer_expr(e, &Expectation::none()));
                 let rhs_expect = lhs_ty
                     .as_ref()
                     .map_or_else(Expectation::none, |ty| Expectation::has_type(ty.clone()));
@@ -454,7 +455,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 }
             }
             Expr::Index { base, index } => {
-                let _base_ty = self.infer_expr_inner(*base, &Expectation::none());
+                let _base_ty = self.infer_expr(*base, &Expectation::none());
                 let _index_ty = self.infer_expr(*index, &Expectation::none());
                 // FIXME: use `std::ops::Index::Output` to figure out the real return type
                 Ty::Unknown
diff --git a/crates/ra_syntax/src/ptr.rs b/crates/ra_syntax/src/ptr.rs
index e049fce611..db6230aab9 100644
--- a/crates/ra_syntax/src/ptr.rs
+++ b/crates/ra_syntax/src/ptr.rs
@@ -1,6 +1,10 @@
 //! FIXME: write short doc here
 
-use std::{iter::successors, marker::PhantomData};
+use std::{
+    hash::{Hash, Hasher},
+    iter::successors,
+    marker::PhantomData,
+};
 
 use crate::{AstNode, SyntaxKind, SyntaxNode, TextRange};
 
@@ -43,7 +47,7 @@ impl SyntaxNodePtr {
 }
 
 /// Like `SyntaxNodePtr`, but remembers the type of node
-#[derive(Debug, Hash)]
+#[derive(Debug)]
 pub struct AstPtr<N: AstNode> {
     raw: SyntaxNodePtr,
     _ty: PhantomData<fn() -> N>,
@@ -64,6 +68,12 @@ impl<N: AstNode> PartialEq for AstPtr<N> {
     }
 }
 
+impl<N: AstNode> Hash for AstPtr<N> {
+    fn hash<H: Hasher>(&self, state: &mut H) {
+        self.raw.hash(state)
+    }
+}
+
 impl<N: AstNode> AstPtr<N> {
     pub fn new(node: &N) -> AstPtr<N> {
         AstPtr { raw: SyntaxNodePtr::new(node.syntax()), _ty: PhantomData }


Test patch:
diff --git a/crates/ra_hir_ty/src/tests.rs b/crates/ra_hir_ty/src/tests.rs
index f1b67555f2..6920ac747e 100644
--- a/crates/ra_hir_ty/src/tests.rs
+++ b/crates/ra_hir_ty/src/tests.rs
@@ -11,8 +11,8 @@ use std::fmt::Write;
 use std::sync::Arc;
 
 use hir_def::{
-    body::BodySourceMap, child_from_source::ChildFromSource, db::DefDatabase, nameres::CrateDefMap,
-    AssocItemId, DefWithBodyId, LocalModuleId, Lookup, ModuleDefId,
+    body::BodySourceMap, child_by_source::ChildBySource, db::DefDatabase, keys,
+    nameres::CrateDefMap, AssocItemId, DefWithBodyId, LocalModuleId, Lookup, ModuleDefId,
 };
 use hir_expand::InFile;
 use insta::assert_snapshot;
@@ -33,7 +33,9 @@ fn type_at_pos(db: &TestDB, pos: FilePosition) -> String {
     let expr = algo::find_node_at_offset::<ast::Expr>(file.syntax(), pos.offset).unwrap();
     let fn_def = expr.syntax().ancestors().find_map(ast::FnDef::cast).unwrap();
     let module = db.module_for_file(pos.file_id);
-    let func = module.child_from_source(db, InFile::new(pos.file_id.into(), fn_def)).unwrap();
+    let func = *module.child_by_source(db)[keys::FUNCTION]
+        .get(&InFile::new(pos.file_id.into(), fn_def))
+        .unwrap();
 
     let (_body, source_map) = db.body_with_source_map(func.into());
     if let Some(expr_id) = source_map.node_expr(InFile::new(pos.file_id.into(), &expr)) {
@@ -50,10 +52,6 @@ fn type_at(content: &str) -> String {
 }
 
 fn infer(content: &str) -> String {
-    infer_with_mismatches(content, false)
-}
-
-fn infer_with_mismatches(content: &str, include_mismatches: bool) -> String {
     let (db, file_id) = TestDB::with_single_file(content);
 
     let mut acc = String::new();
@@ -61,7 +59,6 @@ fn infer_with_mismatches(content: &str, include_mismatches: bool) -> String {
     let mut infer_def = |inference_result: Arc<InferenceResult>,
                          body_source_map: Arc<BodySourceMap>| {
         let mut types = Vec::new();
-        let mut mismatches = Vec::new();
 
         for (pat, ty) in inference_result.type_of_pat.iter() {
             let syntax_ptr = match body_source_map.pat_syntax(pat) {
@@ -81,9 +78,6 @@ fn infer_with_mismatches(content: &str, include_mismatches: bool) -> String {
                 None => continue,
             };
             types.push((syntax_ptr, ty));
-            if let Some(mismatch) = inference_result.type_mismatch_for_expr(expr) {
-                mismatches.push((syntax_ptr, mismatch));
-            }
         }
 
         // sort ranges for consistency
@@ -109,24 +103,6 @@ fn infer_with_mismatches(content: &str, include_mismatches: bool) -> String {
             )
             .unwrap();
         }
-        if include_mismatches {
-            mismatches.sort_by_key(|(src_ptr, _)| {
-                (src_ptr.value.range().start(), src_ptr.value.range().end())
-            });
-            for (src_ptr, mismatch) in &mismatches {
-                let range = src_ptr.value.range();
-                let macro_prefix = if src_ptr.file_id != file_id.into() { "!" } else { "" };
-                write!(
-                    acc,
-                    "{}{}: expected {}, got {}\n",
-                    macro_prefix,
-                    range,
-                    mismatch.expected.display(&db),
-                    mismatch.actual.display(&db),
-                )
-                .unwrap();
-            }
-        }
     };
 
     let module = db.module_for_file(file_id);
diff --git a/crates/ra_hir_ty/src/tests/coercion.rs b/crates/ra_hir_ty/src/tests/coercion.rs
index 58b22396fc..1530fcc637 100644
--- a/crates/ra_hir_ty/src/tests/coercion.rs
+++ b/crates/ra_hir_ty/src/tests/coercion.rs
@@ -1,4 +1,3 @@
-use super::infer_with_mismatches;
 use insta::assert_snapshot;
 use test_utils::covers;
 
@@ -368,38 +367,3 @@ fn test() {
     "###
     );
 }
-
-#[test]
-fn coerce_autoderef() {
-    assert_snapshot!(
-        infer_with_mismatches(r#"
-struct Foo;
-fn takes_ref_foo(x: &Foo) {}
-fn test() {
-    takes_ref_foo(&Foo);
-    takes_ref_foo(&&Foo);
-    takes_ref_foo(&&&Foo);
-}
-"#, true),
-        @r###"
-    [30; 31) 'x': &Foo
-    [39; 41) '{}': ()
-    [52; 133) '{     ...oo); }': ()
-    [58; 71) 'takes_ref_foo': fn takes_ref_foo(&Foo) -> ()
-    [58; 77) 'takes_...(&Foo)': ()
-    [72; 76) '&Foo': &Foo
-    [73; 76) 'Foo': Foo
-    [83; 96) 'takes_ref_foo': fn takes_ref_foo(&Foo) -> ()
-    [83; 103) 'takes_...&&Foo)': ()
-    [97; 102) '&&Foo': &&Foo
-    [98; 102) '&Foo': &Foo
-    [99; 102) 'Foo': Foo
-    [109; 122) 'takes_ref_foo': fn takes_ref_foo(&Foo) -> ()
-    [109; 130) 'takes_...&&Foo)': ()
-    [123; 129) '&&&Foo': &&&Foo
-    [124; 129) '&&Foo': &&Foo
-    [125; 129) '&Foo': &Foo
-    [126; 129) 'Foo': Foo
-    "###
-    );
-}