10 files changed, 446 insertions, 376 deletions

diff --git a/crates/ra_hir_def/src/body.rs b/crates/ra_hir_def/src/body.rs
index 7b385f3fd..b3bc336cf 100644
--- a/crates/ra_hir_def/src/body.rs
+++ b/crates/ra_hir_def/src/body.rs
@@ -6,9 +6,7 @@ pub mod scope;
 use std::{ops::Index, sync::Arc};
 
 use either::Either;
-use hir_expand::{
-    hygiene::Hygiene, AstId, HirFileId, InFile, MacroCallKind, MacroDefId, MacroFileKind,
-};
+use hir_expand::{hygiene::Hygiene, AstId, HirFileId, InFile, MacroCallKind, MacroDefId};
 use ra_arena::{map::ArenaMap, Arena};
 use ra_syntax::{ast, AstNode, AstPtr};
 use rustc_hash::FxHashMap;
@@ -49,7 +47,7 @@ impl Expander {
         if let Some(path) = macro_call.path().and_then(|path| self.parse_path(path)) {
             if let Some(def) = self.resolve_path_as_macro(db, &path) {
                 let call_id = def.as_call_id(db, MacroCallKind::FnLike(ast_id));
-                let file_id = call_id.as_file(MacroFileKind::Expr);
+                let file_id = call_id.as_file();
                 if let Some(node) = db.parse_or_expand(file_id) {
                     if let Some(expr) = ast::Expr::cast(node) {
                         log::debug!("macro expansion {:#?}", expr.syntax());
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/generics.rs b/crates/ra_hir_def/src/generics.rs
index 5f648ffc3..976cf72d0 100644
--- a/crates/ra_hir_def/src/generics.rs
+++ b/crates/ra_hir_def/src/generics.rs
@@ -4,21 +4,29 @@
 //! in rustc.
 use std::sync::Arc;
 
-use hir_expand::name::{self, AsName, Name};
+use either::Either;
+use hir_expand::{
+    name::{self, AsName, Name},
+    InFile,
+};
+use ra_arena::{map::ArenaMap, Arena};
+use ra_db::FileId;
 use ra_syntax::ast::{self, NameOwner, TypeBoundsOwner, TypeParamsOwner};
 
 use crate::{
+    child_by_source::ChildBySource,
     db::DefDatabase,
+    dyn_map::DynMap,
+    keys,
+    src::HasChildSource,
     src::HasSource,
     type_ref::{TypeBound, TypeRef},
-    AdtId, AstItemDef, ContainerId, GenericDefId, Lookup,
+    AdtId, AstItemDef, GenericDefId, LocalTypeParamId, Lookup, TypeParamId,
 };
 
 /// Data about a generic parameter (to a function, struct, impl, ...).
 #[derive(Clone, PartialEq, Eq, Debug)]
-pub struct GenericParam {
-    // FIXME: give generic params proper IDs
-    pub idx: u32,
+pub struct TypeParamData {
     pub name: Name,
     pub default: Option<TypeRef>,
 }
@@ -26,8 +34,8 @@ pub struct GenericParam {
 /// Data about the generic parameters of a function, struct, impl, etc.
 #[derive(Clone, PartialEq, Eq, Debug)]
 pub struct GenericParams {
-    pub parent_params: Option<Arc<GenericParams>>,
-    pub params: Vec<GenericParam>,
+    pub types: Arena<LocalTypeParamId, TypeParamData>,
+    // lifetimes: Arena<LocalLifetimeParamId, LifetimeParamData>,
     pub where_predicates: Vec<WherePredicate>,
 }
 
@@ -41,63 +49,87 @@ pub struct WherePredicate {
     pub bound: TypeBound,
 }
 
+type SourceMap = ArenaMap<LocalTypeParamId, Either<ast::TraitDef, ast::TypeParam>>;
+
 impl GenericParams {
     pub(crate) fn generic_params_query(
         db: &impl DefDatabase,
         def: GenericDefId,
     ) -> Arc<GenericParams> {
-        let parent_generics = parent_generic_def(db, def).map(|it| db.generic_params(it));
-        Arc::new(GenericParams::new(db, def.into(), parent_generics))
+        let (params, _source_map) = GenericParams::new(db, def.into());
+        Arc::new(params)
     }
 
-    fn new(
-        db: &impl DefDatabase,
-        def: GenericDefId,
-        parent_params: Option<Arc<GenericParams>>,
-    ) -> GenericParams {
-        let mut generics =
-            GenericParams { params: Vec::new(), parent_params, where_predicates: Vec::new() };
-        let start = generics.parent_params.as_ref().map(|p| p.params.len()).unwrap_or(0) as u32;
+    fn new(db: &impl DefDatabase, def: GenericDefId) -> (GenericParams, InFile<SourceMap>) {
+        let mut generics = GenericParams { types: Arena::default(), where_predicates: Vec::new() };
+        let mut sm = ArenaMap::default();
         // FIXME: add `: Sized` bound for everything except for `Self` in traits
-        match def {
-            GenericDefId::FunctionId(it) => generics.fill(&it.lookup(db).source(db).value, start),
-            GenericDefId::AdtId(AdtId::StructId(it)) => generics.fill(&it.source(db).value, start),
-            GenericDefId::AdtId(AdtId::UnionId(it)) => generics.fill(&it.source(db).value, start),
-            GenericDefId::AdtId(AdtId::EnumId(it)) => generics.fill(&it.source(db).value, start),
+        let file_id = match def {
+            GenericDefId::FunctionId(it) => {
+                let src = it.lookup(db).source(db);
+                generics.fill(&mut sm, &src.value);
+                src.file_id
+            }
+            GenericDefId::AdtId(AdtId::StructId(it)) => {
+                let src = it.source(db);
+                generics.fill(&mut sm, &src.value);
+                src.file_id
+            }
+            GenericDefId::AdtId(AdtId::UnionId(it)) => {
+                let src = it.source(db);
+                generics.fill(&mut sm, &src.value);
+                src.file_id
+            }
+            GenericDefId::AdtId(AdtId::EnumId(it)) => {
+                let src = it.source(db);
+                generics.fill(&mut sm, &src.value);
+                src.file_id
+            }
             GenericDefId::TraitId(it) => {
+                let src = it.source(db);
+
                 // traits get the Self type as an implicit first type parameter
-                generics.params.push(GenericParam {
-                    idx: start,
-                    name: name::SELF_TYPE,
-                    default: None,
-                });
-                generics.fill(&it.source(db).value, start + 1);
+                let self_param_id =
+                    generics.types.alloc(TypeParamData { name: name::SELF_TYPE, default: None });
+                sm.insert(self_param_id, Either::Left(src.value.clone()));
                 // add super traits as bounds on Self
                 // i.e., trait Foo: Bar is equivalent to trait Foo where Self: Bar
                 let self_param = TypeRef::Path(name::SELF_TYPE.into());
-                generics.fill_bounds(&it.source(db).value, self_param);
+                generics.fill_bounds(&src.value, self_param);
+
+                generics.fill(&mut sm, &src.value);
+                src.file_id
+            }
+            GenericDefId::TypeAliasId(it) => {
+                let src = it.lookup(db).source(db);
+                generics.fill(&mut sm, &src.value);
+                src.file_id
             }
-            GenericDefId::TypeAliasId(it) => generics.fill(&it.lookup(db).source(db).value, start),
             // Note that we don't add `Self` here: in `impl`s, `Self` is not a
             // type-parameter, but rather is a type-alias for impl's target
             // type, so this is handled by the resolver.
-            GenericDefId::ImplId(it) => generics.fill(&it.source(db).value, start),
-            GenericDefId::EnumVariantId(_) | GenericDefId::ConstId(_) => {}
-        }
+            GenericDefId::ImplId(it) => {
+                let src = it.source(db);
+                generics.fill(&mut sm, &src.value);
+                src.file_id
+            }
+            // We won't be using this ID anyway
+            GenericDefId::EnumVariantId(_) | GenericDefId::ConstId(_) => FileId(!0).into(),
+        };
 
-        generics
+        (generics, InFile::new(file_id, sm))
     }
 
-    fn fill(&mut self, node: &impl TypeParamsOwner, start: u32) {
+    fn fill(&mut self, sm: &mut SourceMap, node: &dyn TypeParamsOwner) {
         if let Some(params) = node.type_param_list() {
-            self.fill_params(params, start)
+            self.fill_params(sm, params)
         }
         if let Some(where_clause) = node.where_clause() {
             self.fill_where_predicates(where_clause);
         }
     }
 
-    fn fill_bounds(&mut self, node: &impl ast::TypeBoundsOwner, type_ref: TypeRef) {
+    fn fill_bounds(&mut self, node: &dyn ast::TypeBoundsOwner, type_ref: TypeRef) {
         for bound in
             node.type_bound_list().iter().flat_map(|type_bound_list| type_bound_list.bounds())
         {
@@ -105,13 +137,14 @@ impl GenericParams {
         }
     }
 
-    fn fill_params(&mut self, params: ast::TypeParamList, start: u32) {
-        for (idx, type_param) in params.type_params().enumerate() {
+    fn fill_params(&mut self, sm: &mut SourceMap, params: ast::TypeParamList) {
+        for type_param in params.type_params() {
             let name = type_param.name().map_or_else(Name::missing, |it| it.as_name());
             // FIXME: Use `Path::from_src`
             let default = type_param.default_type().map(TypeRef::from_ast);
-            let param = GenericParam { idx: idx as u32 + start, name: name.clone(), default };
-            self.params.push(param);
+            let param = TypeParamData { name: name.clone(), default };
+            let param_id = self.types.alloc(param);
+            sm.insert(param_id, Either::Right(type_param.clone()));
 
             let type_ref = TypeRef::Path(name.into());
             self.fill_bounds(&type_param, type_ref);
@@ -140,45 +173,31 @@ impl GenericParams {
         self.where_predicates.push(WherePredicate { type_ref, bound });
     }
 
-    pub fn find_by_name(&self, name: &Name) -> Option<&GenericParam> {
-        self.params.iter().find(|p| &p.name == name)
-    }
-
-    pub fn count_parent_params(&self) -> usize {
-        self.parent_params.as_ref().map(|p| p.count_params_including_parent()).unwrap_or(0)
-    }
-
-    pub fn count_params_including_parent(&self) -> usize {
-        let parent_count = self.count_parent_params();
-        parent_count + self.params.len()
-    }
-
-    fn for_each_param<'a>(&'a self, f: &mut impl FnMut(&'a GenericParam)) {
-        if let Some(parent) = &self.parent_params {
-            parent.for_each_param(f);
-        }
-        self.params.iter().for_each(f);
+    pub fn find_by_name(&self, name: &Name) -> Option<LocalTypeParamId> {
+        self.types.iter().find_map(|(id, p)| if &p.name == name { Some(id) } else { None })
     }
+}
 
-    pub fn params_including_parent(&self) -> Vec<&GenericParam> {
-        let mut vec = Vec::with_capacity(self.count_params_including_parent());
-        self.for_each_param(&mut |p| vec.push(p));
-        vec
+impl HasChildSource for GenericDefId {
+    type ChildId = LocalTypeParamId;
+    type Value = Either<ast::TraitDef, ast::TypeParam>;
+    fn child_source(&self, db: &impl DefDatabase) -> InFile<SourceMap> {
+        let (_, sm) = GenericParams::new(db, *self);
+        sm
     }
 }
 
-fn parent_generic_def(db: &impl DefDatabase, def: GenericDefId) -> Option<GenericDefId> {
-    let container = match def {
-        GenericDefId::FunctionId(it) => it.lookup(db).container,
-        GenericDefId::TypeAliasId(it) => it.lookup(db).container,
-        GenericDefId::ConstId(it) => it.lookup(db).container,
-        GenericDefId::EnumVariantId(it) => return Some(it.parent.into()),
-        GenericDefId::AdtId(_) | GenericDefId::TraitId(_) | GenericDefId::ImplId(_) => return None,
-    };
-
-    match container {
-        ContainerId::ImplId(it) => Some(it.into()),
-        ContainerId::TraitId(it) => Some(it.into()),
-        ContainerId::ModuleId(_) => None,
+impl ChildBySource for GenericDefId {
+    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, src) in arena_map.value.iter() {
+            let id = TypeParamId { parent: *self, local_id };
+            if let Either::Right(type_param) = src {
+                res[keys::TYPE_PARAM].insert(arena_map.with_value(type_param.clone()), id)
+            }
+        }
+        res
     }
 }
diff --git a/crates/ra_hir_def/src/keys.rs b/crates/ra_hir_def/src/keys.rs
new file mode 100644
index 000000000..be702a4f8
--- /dev/null
+++ b/crates/ra_hir_def/src/keys.rs
@@ -0,0 +1,49 @@
+//! 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, TypeParamId,
+};
+
+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();
+pub const TYPE_PARAM: Key<ast::TypeParam, TypeParamId> = 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..569da4f28 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;
@@ -315,6 +318,16 @@ macro_rules! impl_froms {
 }
 
 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
+pub struct TypeParamId {
+    pub parent: GenericDefId,
+    pub local_id: LocalTypeParamId,
+}
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
+pub struct LocalTypeParamId(RawId);
+impl_arena_id!(LocalTypeParamId);
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
 pub enum ContainerId {
     ModuleId(ModuleId),
     ImplId(ImplId),
@@ -512,6 +525,20 @@ impl HasModule for DefWithBodyId {
     }
 }
 
+impl HasModule for GenericDefId {
+    fn module(&self, db: &impl db::DefDatabase) -> ModuleId {
+        match self {
+            GenericDefId::FunctionId(it) => it.lookup(db).module(db),
+            GenericDefId::AdtId(it) => it.module(db),
+            GenericDefId::TraitId(it) => it.module(db),
+            GenericDefId::TypeAliasId(it) => it.lookup(db).module(db),
+            GenericDefId::ImplId(it) => it.module(db),
+            GenericDefId::EnumVariantId(it) => it.parent.module(db),
+            GenericDefId::ConstId(it) => it.lookup(db).module(db),
+        }
+    }
+}
+
 impl HasModule for StaticLoc {
     fn module(&self, _db: &impl db::DefDatabase) -> ModuleId {
         self.container
diff --git a/crates/ra_hir_def/src/nameres/collector.rs b/crates/ra_hir_def/src/nameres/collector.rs
index 3b3f30eec..3ff071f9e 100644
--- a/crates/ra_hir_def/src/nameres/collector.rs
+++ b/crates/ra_hir_def/src/nameres/collector.rs
@@ -7,7 +7,7 @@ use hir_expand::{
     builtin_derive::find_builtin_derive,
     builtin_macro::find_builtin_macro,
     name::{self, AsName, Name},
-    HirFileId, MacroCallId, MacroCallKind, MacroDefId, MacroDefKind, MacroFileKind,
+    HirFileId, MacroCallId, MacroCallKind, MacroDefId, MacroDefKind,
 };
 use ra_cfg::CfgOptions;
 use ra_db::{CrateId, FileId};
@@ -624,7 +624,7 @@ where
         self.macro_stack_monitor.increase(macro_def_id);
 
         if !self.macro_stack_monitor.is_poison(macro_def_id) {
-            let file_id: HirFileId = macro_call_id.as_file(MacroFileKind::Items);
+            let file_id: HirFileId = macro_call_id.as_file();
             let raw_items = self.db.raw_items(file_id);
             let mod_dir = self.mod_dirs[&module_id].clone();
             ModCollector {
diff --git a/crates/ra_hir_def/src/per_ns.rs b/crates/ra_hir_def/src/per_ns.rs
index 00e866bf9..3a5105028 100644
--- a/crates/ra_hir_def/src/per_ns.rs
+++ b/crates/ra_hir_def/src/per_ns.rs
@@ -11,8 +11,6 @@ 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_def/src/resolver.rs b/crates/ra_hir_def/src/resolver.rs
index 7d4df222e..4c859e497 100644
--- a/crates/ra_hir_def/src/resolver.rs
+++ b/crates/ra_hir_def/src/resolver.rs
@@ -19,11 +19,12 @@ use crate::{
     per_ns::PerNs,
     AdtId, AstItemDef, ConstId, ContainerId, DefWithBodyId, EnumId, EnumVariantId, FunctionId,
     GenericDefId, HasModule, ImplId, LocalModuleId, Lookup, ModuleDefId, ModuleId, StaticId,
-    StructId, TraitId, TypeAliasId,
+    StructId, TraitId, TypeAliasId, TypeParamId,
 };
 
 #[derive(Debug, Clone, Default)]
 pub struct Resolver {
+    // FIXME: all usages generally call `.rev`, so maybe reverse once in consturciton?
     scopes: Vec<Scope>,
 }
 
@@ -58,7 +59,7 @@ enum Scope {
 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
 pub enum TypeNs {
     SelfType(ImplId),
-    GenericParam(u32),
+    GenericParam(TypeParamId),
     AdtId(AdtId),
     AdtSelfType(AdtId),
     // Yup, enum variants are added to the types ns, but any usage of variant as
@@ -152,10 +153,13 @@ impl Resolver {
                 Scope::ExprScope(_) => continue,
                 Scope::GenericParams { .. } | Scope::ImplBlockScope(_) if skip_to_mod => continue,
 
-                Scope::GenericParams { params, .. } => {
-                    if let Some(param) = params.find_by_name(first_name) {
+                Scope::GenericParams { params, def } => {
+                    if let Some(local_id) = params.find_by_name(first_name) {
                         let idx = if path.segments.len() == 1 { None } else { Some(1) };
-                        return Some((TypeNs::GenericParam(param.idx), idx));
+                        return Some((
+                            TypeNs::GenericParam(TypeParamId { local_id, parent: *def }),
+                            idx,
+                        ));
                     }
                 }
                 Scope::ImplBlockScope(impl_) => {
@@ -246,9 +250,9 @@ impl Resolver {
                 }
                 Scope::ExprScope(_) => continue,
 
-                Scope::GenericParams { params, .. } if n_segments > 1 => {
-                    if let Some(param) = params.find_by_name(first_name) {
-                        let ty = TypeNs::GenericParam(param.idx);
+                Scope::GenericParams { params, def } if n_segments > 1 => {
+                    if let Some(local_id) = params.find_by_name(first_name) {
+                        let ty = TypeNs::GenericParam(TypeParamId { local_id, parent: *def });
                         return Some(ResolveValueResult::Partial(ty, 1));
                     }
                 }
@@ -368,6 +372,7 @@ impl Resolver {
     ) -> impl Iterator<Item = &'a crate::generics::WherePredicate> + 'a {
         self.scopes
             .iter()
+            .rev()
             .filter_map(|scope| match scope {
                 Scope::GenericParams { params, .. } => Some(params),
                 _ => None,
@@ -376,14 +381,14 @@ impl Resolver {
     }
 
     pub fn generic_def(&self) -> Option<GenericDefId> {
-        self.scopes.iter().find_map(|scope| match scope {
+        self.scopes.iter().rev().find_map(|scope| match scope {
             Scope::GenericParams { def, .. } => Some(*def),
             _ => None,
         })
     }
 
     pub fn body_owner(&self) -> Option<DefWithBodyId> {
-        self.scopes.iter().find_map(|scope| match scope {
+        self.scopes.iter().rev().find_map(|scope| match scope {
             Scope::ExprScope(it) => Some(it.owner),
             _ => None,
         })
@@ -394,7 +399,7 @@ pub enum ScopeDef {
     PerNs(PerNs),
     ImplSelfType(ImplId),
     AdtSelfType(AdtId),
-    GenericParam(u32),
+    GenericParam(TypeParamId),
     Local(PatId),
 }
 
@@ -425,9 +430,12 @@ impl Scope {
                     });
                 }
             }
-            Scope::GenericParams { params, .. } => {
-                for param in params.params.iter() {
-                    f(param.name.clone(), ScopeDef::GenericParam(param.idx))
+            Scope::GenericParams { params, def } => {
+                for (local_id, param) in params.types.iter() {
+                    f(
+                        param.name.clone(),
+                        ScopeDef::GenericParam(TypeParamId { local_id, parent: *def }),
+                    )
                 }
             }
             Scope::ImplBlockScope(i) => {
@@ -473,7 +481,7 @@ impl Resolver {
 
     fn push_generic_params_scope(self, db: &impl DefDatabase, def: GenericDefId) -> Resolver {
         let params = db.generic_params(def);
-        if params.params.is_empty() {
+        if params.types.is_empty() {
             self
         } else {
             self.push_scope(Scope::GenericParams { def, params })