Merge #2484

2484: DynMap r=matklad a=matklad

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.

Co-authored-by: Aleksey Kladov <[email protected]>

9 files changed, 355 insertions, 318 deletions

diff --git a/crates/ra_hir/src/from_source.rs b/crates/ra_hir/src/from_source.rs
index 5cb222bd3..437f800c1 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 cf3a446fc..b1923bbf2 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 000000000..a3574a9db
--- /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 37d4b7870..000000000
--- 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 000000000..6f269d7b0
--- /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 000000000..447b7e3ba
--- /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 e02622f62..68e66d276 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_ty/src/tests.rs b/crates/ra_hir_ty/src/tests.rs
index f1b67555f..d724ee122 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)) {
diff --git a/crates/ra_syntax/src/ptr.rs b/crates/ra_syntax/src/ptr.rs
index e049fce61..db6230aab 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 }