Next gen IDs for functions

The current system with AstIds has two primaraly drawbacks:

* It is possible to manufacture IDs out of thin air.
  For example, it's possible to create IDs for items which are not
  considered in CrateDefMap due to cfg. Or it is possible to mixup
  structs and unions, because they share ID space.

* Getting the ID of a parent requires a secondary index.

Instead, the plan is to pursue the more traditional approach, where
each items stores the id of the parent declaration. This makes
`FromSource` more awkward, but also more correct: now, to get from an
AST to HIR, we first do this recursively for the parent item, and the
just search the children of the parent for the matching def

12 files changed, 190 insertions, 42 deletions

diff --git a/crates/ra_hir/src/code_model.rs b/crates/ra_hir/src/code_model.rs
index f436d5d5e..c49190a0f 100644
--- a/crates/ra_hir/src/code_model.rs
+++ b/crates/ra_hir/src/code_model.rs
@@ -12,7 +12,8 @@ use hir_def::{
     builtin_type::BuiltinType,
     traits::TraitData,
     type_ref::{Mutability, TypeRef},
-    AssocItemId, CrateModuleId, ImplId, LocalEnumVariantId, LocalStructFieldId, ModuleId, UnionId,
+    AssocItemId, CrateModuleId, FunctionContainerId, HasModule, ImplId, LocalEnumVariantId,
+    LocalStructFieldId, Lookup, ModuleId, UnionId,
 };
 use hir_expand::{
     diagnostics::DiagnosticSink,
@@ -647,7 +648,7 @@ impl FnData {
 
 impl Function {
     pub fn module(self, db: &impl DefDatabase) -> Module {
-        Module { id: self.id.module(db) }
+        self.id.lookup(db).module(db).into()
     }
 
     pub fn krate(self, db: &impl DefDatabase) -> Option<Crate> {
@@ -680,21 +681,25 @@ impl Function {
 
     /// The containing impl block, if this is a method.
     pub fn impl_block(self, db: &impl DefDatabase) -> Option<ImplBlock> {
-        ImplBlock::containing(db, self.into())
+        match self.container(db) {
+            Some(Container::ImplBlock(it)) => Some(it),
+            _ => None,
+        }
     }
 
     /// The containing trait, if this is a trait method definition.
     pub fn parent_trait(self, db: &impl DefDatabase) -> Option<Trait> {
-        db.trait_items_index(self.module(db).id).get_parent_trait(self.id.into()).map(Trait::from)
+        match self.container(db) {
+            Some(Container::Trait(it)) => Some(it),
+            _ => None,
+        }
     }
 
     pub fn container(self, db: &impl DefDatabase) -> Option<Container> {
-        if let Some(impl_block) = self.impl_block(db) {
-            Some(impl_block.into())
-        } else if let Some(trait_) = self.parent_trait(db) {
-            Some(trait_.into())
-        } else {
-            None
+        match self.id.lookup(db).container {
+            FunctionContainerId::TraitId(it) => Some(Container::Trait(it.into())),
+            FunctionContainerId::ImplId(it) => Some(Container::ImplBlock(it.into())),
+            FunctionContainerId::ModuleId(_) => None,
         }
     }
 
diff --git a/crates/ra_hir/src/code_model/src.rs b/crates/ra_hir/src/code_model/src.rs
index 556417b0f..91cab7414 100644
--- a/crates/ra_hir/src/code_model/src.rs
+++ b/crates/ra_hir/src/code_model/src.rs
@@ -1,5 +1,6 @@
 //! FIXME: write short doc here
 
+use hir_def::{HasSource as _, Lookup};
 use ra_syntax::ast::{self, AstNode};
 
 use crate::{
@@ -113,7 +114,7 @@ impl HasSource for EnumVariant {
 impl HasSource for Function {
     type Ast = ast::FnDef;
     fn source(self, db: &(impl DefDatabase + AstDatabase)) -> Source<ast::FnDef> {
-        self.id.source(db)
+        self.id.lookup(db).source(db)
     }
 }
 impl HasSource for Const {
diff --git a/crates/ra_hir/src/from_source.rs b/crates/ra_hir/src/from_source.rs
index f4dca25cb..303d5f138 100644
--- a/crates/ra_hir/src/from_source.rs
+++ b/crates/ra_hir/src/from_source.rs
@@ -4,15 +4,15 @@ use hir_def::{ModuleId, StructId, StructOrUnionId, UnionId};
 use hir_expand::{name::AsName, AstId, MacroDefId, MacroDefKind};
 use ra_syntax::{
     ast::{self, AstNode, NameOwner},
-    match_ast,
+    match_ast, AstPtr,
 };
 
 use crate::{
     db::{AstDatabase, DefDatabase, HirDatabase},
     ids::{AstItemDef, LocationCtx},
-    Const, DefWithBody, Enum, EnumVariant, FieldSource, Function, HasBody, HasSource, ImplBlock,
-    Local, MacroDef, Module, ModuleSource, Source, Static, Struct, StructField, Trait, TypeAlias,
-    Union, VariantDef,
+    AssocItem, Const, DefWithBody, Enum, EnumVariant, FieldSource, Function, HasBody, HasSource,
+    ImplBlock, Local, MacroDef, Module, ModuleDef, ModuleSource, Source, Static, Struct,
+    StructField, Trait, TypeAlias, Union, VariantDef,
 };
 
 pub trait FromSource: Sized {
@@ -52,10 +52,51 @@ impl FromSource for Trait {
 impl FromSource for Function {
     type Ast = ast::FnDef;
     fn from_source(db: &(impl DefDatabase + AstDatabase), src: Source<Self::Ast>) -> Option<Self> {
-        let id = from_source(db, src)?;
-        Some(Function { id })
+        // FIXME: this doesn't try to handle nested declarations
+        for container in src.value.syntax().ancestors() {
+            let res = match_ast! {
+                match container {
+                    ast::TraitDef(it) => {
+                        let c = Trait::from_source(db, src.with_value(it))?;
+                        c.items(db)
+                            .into_iter()
+                            .filter_map(|it| match it {
+                                AssocItem::Function(it) => Some(it),
+                                _ => None
+                            })
+                            .find(|it| same_source(&it.source(db), &src))?
+                    },
+                    ast::ImplBlock(it) => {
+                        let c = ImplBlock::from_source(db, src.with_value(it))?;
+                        c.items(db)
+                            .into_iter()
+                            .filter_map(|it| match it {
+                                AssocItem::Function(it) => Some(it),
+                                _ => None
+                            })
+                            .find(|it| same_source(&it.source(db), &src))?
+
+                     },
+                    _ => { continue },
+                }
+            };
+            return Some(res);
+        }
+
+        let module_source = ModuleSource::from_child_node(db, src.as_ref().map(|it| it.syntax()));
+        let c = Module::from_definition(db, src.with_value(module_source))?;
+        let res = c
+            .declarations(db)
+            .into_iter()
+            .filter_map(|it| match it {
+                ModuleDef::Function(it) => Some(it),
+                _ => None,
+            })
+            .find(|it| same_source(&it.source(db), &src));
+        res
     }
 }
+
 impl FromSource for Const {
     type Ast = ast::ConstDef;
     fn from_source(db: &(impl DefDatabase + AstDatabase), src: Source<Self::Ast>) -> Option<Self> {
@@ -108,7 +149,7 @@ impl FromSource for EnumVariant {
         let parent_enum = src.value.parent_enum();
         let src_enum = Source { file_id: src.file_id, value: parent_enum };
         let variants = Enum::from_source(db, src_enum)?.variants(db);
-        variants.into_iter().find(|v| v.source(db) == src)
+        variants.into_iter().find(|v| same_source(&v.source(db), &src))
     }
 }
 
@@ -216,3 +257,13 @@ where
     let ctx = LocationCtx::new(db, module.id, src.file_id);
     Some(DEF::from_ast(ctx, &src.value))
 }
+
+/// 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 guanratree, but, for
+/// the time being, we will use identity-less AstPtr comparison.
+fn same_source<N: AstNode>(s1: &Source<N>, s2: &Source<N>) -> bool {
+    s1.as_ref().map(AstPtr::new) == s2.as_ref().map(AstPtr::new)
+}
diff --git a/crates/ra_hir/src/source_binder.rs b/crates/ra_hir/src/source_binder.rs
index a1c1daacd..5d9e22ee2 100644
--- a/crates/ra_hir/src/source_binder.rs
+++ b/crates/ra_hir/src/source_binder.rs
@@ -70,7 +70,7 @@ fn def_with_body_from_child_node(
     child.value.ancestors().find_map(|node| {
         match_ast! {
             match node {
-                ast::FnDef(def)  => { Some(Function {id: ctx.to_def(&def) }.into()) },
+                ast::FnDef(def)  => { return Function::from_source(db, child.with_value(def)).map(DefWithBody::from); },
                 ast::ConstDef(def) => { Some(Const { id: ctx.to_def(&def) }.into()) },
                 ast::StaticDef(def) => { Some(Static { id: ctx.to_def(&def) }.into()) },
                 _ => { None },
diff --git a/crates/ra_hir_def/src/body.rs b/crates/ra_hir_def/src/body.rs
index 3804b65c7..b69d4dea6 100644
--- a/crates/ra_hir_def/src/body.rs
+++ b/crates/ra_hir_def/src/body.rs
@@ -17,7 +17,7 @@ use crate::{
     expr::{Expr, ExprId, Pat, PatId},
     nameres::CrateDefMap,
     path::Path,
-    AstItemDef, DefWithBodyId, ModuleId,
+    AstItemDef, DefWithBodyId, HasModule, HasSource, Lookup, ModuleId,
 };
 
 pub struct Expander {
@@ -149,6 +149,7 @@ impl Body {
 
         let (file_id, module, body) = match def {
             DefWithBodyId::FunctionId(f) => {
+                let f = f.lookup(db);
                 let src = f.source(db);
                 params = src.value.param_list();
                 (src.file_id, f.module(db), src.value.body().map(ast::Expr::from))
diff --git a/crates/ra_hir_def/src/db.rs b/crates/ra_hir_def/src/db.rs
index fb4402463..e4ffdebe9 100644
--- a/crates/ra_hir_def/src/db.rs
+++ b/crates/ra_hir_def/src/db.rs
@@ -14,13 +14,13 @@ use crate::{
         CrateDefMap,
     },
     traits::{TraitData, TraitItemsIndex},
-    DefWithBodyId, EnumId, ImplId, ItemLoc, ModuleId, StructOrUnionId, TraitId,
+    DefWithBodyId, EnumId, FunctionLoc, ImplId, ItemLoc, ModuleId, StructOrUnionId, TraitId,
 };
 
 #[salsa::query_group(InternDatabaseStorage)]
 pub trait InternDatabase: SourceDatabase {
     #[salsa::interned]
-    fn intern_function(&self, loc: ItemLoc<ast::FnDef>) -> crate::FunctionId;
+    fn intern_function(&self, loc: FunctionLoc) -> crate::FunctionId;
     #[salsa::interned]
     fn intern_struct_or_union(&self, loc: ItemLoc<ast::StructDef>) -> crate::StructOrUnionId;
     #[salsa::interned]
diff --git a/crates/ra_hir_def/src/generics.rs b/crates/ra_hir_def/src/generics.rs
index 4adfc16bb..11dd2a948 100644
--- a/crates/ra_hir_def/src/generics.rs
+++ b/crates/ra_hir_def/src/generics.rs
@@ -11,7 +11,7 @@ use ra_syntax::ast::{self, NameOwner, TypeBoundsOwner, TypeParamsOwner};
 use crate::{
     db::DefDatabase2,
     type_ref::{TypeBound, TypeRef},
-    AdtId, AstItemDef, GenericDefId,
+    AdtId, AstItemDef, GenericDefId, HasSource, Lookup,
 };
 
 /// Data about a generic parameter (to a function, struct, impl, ...).
@@ -53,7 +53,7 @@ impl GenericParams {
         let start = generics.parent_params.as_ref().map(|p| p.params.len()).unwrap_or(0) as u32;
         // FIXME: add `: Sized` bound for everything except for `Self` in traits
         match def {
-            GenericDefId::FunctionId(it) => generics.fill(&it.source(db).value, start),
+            GenericDefId::FunctionId(it) => generics.fill(&it.lookup(db).source(db).value, start),
             GenericDefId::AdtId(AdtId::StructId(it)) => {
                 generics.fill(&it.0.source(db).value, start)
             }
diff --git a/crates/ra_hir_def/src/impls.rs b/crates/ra_hir_def/src/impls.rs
index 4323dfcb6..9be38c5e1 100644
--- a/crates/ra_hir_def/src/impls.rs
+++ b/crates/ra_hir_def/src/impls.rs
@@ -5,11 +5,12 @@
 
 use std::sync::Arc;
 
+use hir_expand::AstId;
 use ra_syntax::ast;
 
 use crate::{
-    db::DefDatabase2, type_ref::TypeRef, AssocItemId, AstItemDef, ConstId, FunctionId, ImplId,
-    LocationCtx, TypeAliasId,
+    db::DefDatabase2, type_ref::TypeRef, AssocItemId, AstItemDef, ConstId, FunctionContainerId,
+    FunctionLoc, ImplId, Intern, LocationCtx, TypeAliasId,
 };
 
 #[derive(Debug, Clone, PartialEq, Eq)]
@@ -35,7 +36,12 @@ impl ImplData {
                 .impl_items()
                 .map(|item_node| match item_node {
                     ast::ImplItem::FnDef(it) => {
-                        FunctionId::from_ast_id(ctx, items.ast_id(&it)).into()
+                        let func_id = FunctionLoc {
+                            container: FunctionContainerId::ImplId(id),
+                            ast_id: AstId::new(src.file_id, items.ast_id(&it)),
+                        }
+                        .intern(db);
+                        func_id.into()
                     }
                     ast::ImplItem::ConstDef(it) => {
                         ConstId::from_ast_id(ctx, items.ast_id(&it)).into()
diff --git a/crates/ra_hir_def/src/lib.rs b/crates/ra_hir_def/src/lib.rs
index 38c110570..b9a13776f 100644
--- a/crates/ra_hir_def/src/lib.rs
+++ b/crates/ra_hir_def/src/lib.rs
@@ -199,16 +199,34 @@ pub trait AstItemDef<N: AstNode>: salsa::InternKey + Clone {
 pub struct FunctionId(salsa::InternId);
 impl_intern_key!(FunctionId);
 
-impl AstItemDef<ast::FnDef> for FunctionId {
-    fn intern(db: &impl InternDatabase, loc: ItemLoc<ast::FnDef>) -> Self {
-        db.intern_function(loc)
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
+pub struct FunctionLoc {
+    pub container: FunctionContainerId,
+    pub ast_id: AstId<ast::FnDef>,
+}
+
+impl Intern for FunctionLoc {
+    type ID = FunctionId;
+    fn intern(self, db: &impl db::DefDatabase2) -> FunctionId {
+        db.intern_function(self)
     }
-    fn lookup_intern(self, db: &impl InternDatabase) -> ItemLoc<ast::FnDef> {
-        db.lookup_intern_function(self)
+}
+
+impl Lookup for FunctionId {
+    type Data = FunctionLoc;
+    fn lookup(&self, db: &impl db::DefDatabase2) -> FunctionLoc {
+        db.lookup_intern_function(*self)
     }
 }
 
 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
+pub enum FunctionContainerId {
+    ModuleId(ModuleId),
+    ImplId(ImplId),
+    TraitId(TraitId),
+}
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
 pub struct StructOrUnionId(salsa::InternId);
 impl_intern_key!(StructOrUnionId);
 impl AstItemDef<ast::StructDef> for StructOrUnionId {
@@ -433,3 +451,41 @@ impl_froms!(
     EnumVariantId,
     ConstId
 );
+
+trait Intern {
+    type ID;
+    fn intern(self, db: &impl db::DefDatabase2) -> Self::ID;
+}
+
+pub trait Lookup {
+    type Data;
+    fn lookup(&self, db: &impl db::DefDatabase2) -> Self::Data;
+}
+
+pub trait HasModule {
+    fn module(&self, db: &impl db::DefDatabase2) -> ModuleId;
+}
+
+impl HasModule for FunctionLoc {
+    fn module(&self, db: &impl db::DefDatabase2) -> ModuleId {
+        match self.container {
+            FunctionContainerId::ModuleId(it) => it,
+            FunctionContainerId::ImplId(it) => it.module(db),
+            FunctionContainerId::TraitId(it) => it.module(db),
+        }
+    }
+}
+
+pub trait HasSource {
+    type Value;
+    fn source(&self, db: &impl db::DefDatabase2) -> Source<Self::Value>;
+}
+
+impl HasSource for FunctionLoc {
+    type Value = ast::FnDef;
+
+    fn source(&self, db: &impl db::DefDatabase2) -> Source<ast::FnDef> {
+        let node = self.ast_id.to_node(db);
+        Source::new(self.ast_id.file_id(), node)
+    }
+}
diff --git a/crates/ra_hir_def/src/nameres/collector.rs b/crates/ra_hir_def/src/nameres/collector.rs
index 8f426b097..d2ed94a87 100644
--- a/crates/ra_hir_def/src/nameres/collector.rs
+++ b/crates/ra_hir_def/src/nameres/collector.rs
@@ -19,9 +19,9 @@ use crate::{
         per_ns::PerNs, raw, CrateDefMap, ModuleData, Resolution, ResolveMode,
     },
     path::{Path, PathKind},
-    AdtId, AstId, AstItemDef, ConstId, CrateModuleId, EnumId, EnumVariantId, FunctionId, ImplId,
-    LocationCtx, ModuleDefId, ModuleId, StaticId, StructId, StructOrUnionId, TraitId, TypeAliasId,
-    UnionId,
+    AdtId, AstId, AstItemDef, ConstId, CrateModuleId, EnumId, EnumVariantId, FunctionContainerId,
+    FunctionLoc, ImplId, Intern, LocationCtx, ModuleDefId, ModuleId, StaticId, StructId,
+    StructOrUnionId, TraitId, TypeAliasId, UnionId,
 };
 
 pub(super) fn collect_defs(db: &impl DefDatabase2, mut def_map: CrateDefMap) -> CrateDefMap {
@@ -673,7 +673,12 @@ where
         let name = def.name.clone();
         let def: PerNs = match def.kind {
             raw::DefKind::Function(ast_id) => {
-                let f = FunctionId::from_ast_id(ctx, ast_id);
+                let f = FunctionLoc {
+                    container: FunctionContainerId::ModuleId(module),
+                    ast_id: AstId::new(self.file_id, ast_id),
+                }
+                .intern(self.def_collector.db);
+
                 PerNs::values(f.into())
             }
             raw::DefKind::Struct(ast_id) => {
diff --git a/crates/ra_hir_def/src/traits.rs b/crates/ra_hir_def/src/traits.rs
index a8ba31594..6e36bc0d0 100644
--- a/crates/ra_hir_def/src/traits.rs
+++ b/crates/ra_hir_def/src/traits.rs
@@ -2,14 +2,17 @@
 
 use std::sync::Arc;
 
-use hir_expand::name::{AsName, Name};
+use hir_expand::{
+    name::{AsName, Name},
+    AstId,
+};
 
 use ra_syntax::ast::{self, NameOwner};
 use rustc_hash::FxHashMap;
 
 use crate::{
-    db::DefDatabase2, AssocItemId, AstItemDef, ConstId, FunctionId, LocationCtx, ModuleDefId,
-    ModuleId, TraitId, TypeAliasId,
+    db::DefDatabase2, AssocItemId, AstItemDef, ConstId, FunctionContainerId, FunctionLoc, Intern,
+    LocationCtx, ModuleDefId, ModuleId, TraitId, TypeAliasId,
 };
 
 #[derive(Debug, Clone, PartialEq, Eq)]
@@ -26,11 +29,17 @@ impl TraitData {
         let module = tr.module(db);
         let ctx = LocationCtx::new(db, module, src.file_id);
         let auto = src.value.is_auto();
+        let ast_id_map = db.ast_id_map(src.file_id);
         let items = if let Some(item_list) = src.value.item_list() {
             item_list
                 .impl_items()
                 .map(|item_node| match item_node {
-                    ast::ImplItem::FnDef(it) => FunctionId::from_ast(ctx, &it).into(),
+                    ast::ImplItem::FnDef(it) => FunctionLoc {
+                        container: FunctionContainerId::TraitId(tr),
+                        ast_id: AstId::new(src.file_id, ast_id_map.ast_id(&it)),
+                    }
+                    .intern(db)
+                    .into(),
                     ast::ImplItem::ConstDef(it) => ConstId::from_ast(ctx, &it).into(),
                     ast::ImplItem::TypeAliasDef(it) => TypeAliasId::from_ast(ctx, &it).into(),
                 })
@@ -54,7 +63,13 @@ impl TraitItemsIndex {
         for decl in crate_def_map[module.module_id].scope.declarations() {
             if let ModuleDefId::TraitId(tr) = decl {
                 for item in db.trait_data(tr).items.iter() {
-                    index.traits_by_def.insert(*item, tr);
+                    match item {
+                        AssocItemId::FunctionId(_) => (),
+                        _ => {
+                            let prev = index.traits_by_def.insert(*item, tr);
+                            assert!(prev.is_none());
+                        }
+                    }
                 }
             }
         }
diff --git a/crates/ra_syntax/src/ptr.rs b/crates/ra_syntax/src/ptr.rs
index 31167cada..e049fce61 100644
--- a/crates/ra_syntax/src/ptr.rs
+++ b/crates/ra_syntax/src/ptr.rs
@@ -43,7 +43,7 @@ impl SyntaxNodePtr {
 }
 
 /// Like `SyntaxNodePtr`, but remembers the type of node
-#[derive(Debug, PartialEq, Eq, Hash)]
+#[derive(Debug, Hash)]
 pub struct AstPtr<N: AstNode> {
     raw: SyntaxNodePtr,
     _ty: PhantomData<fn() -> N>,
@@ -56,6 +56,14 @@ impl<N: AstNode> Clone for AstPtr<N> {
     }
 }
 
+impl<N: AstNode> Eq for AstPtr<N> {}
+
+impl<N: AstNode> PartialEq for AstPtr<N> {
+    fn eq(&self, other: &AstPtr<N>) -> bool {
+        self.raw == other.raw
+    }
+}
+
 impl<N: AstNode> AstPtr<N> {
     pub fn new(node: &N) -> AstPtr<N> {
         AstPtr { raw: SyntaxNodePtr::new(node.syntax()), _ty: PhantomData }