Add HIR for impl blocks

Since we need to be able to go from def to containing impl block, as well as the
other direction, and to find all impls for a certain type, a design similar to
the one for modules, where we collect all impls for the whole crate and keep
them in an arena, seemed fitting. The ImplBlock type, which provides the public
interface, then consists only of an Arc to the arena containing all impls, and
the index into it.

11 files changed, 269 insertions, 8 deletions

diff --git a/crates/ra_analysis/src/db.rs b/crates/ra_analysis/src/db.rs
index d7740f0c4..d7e51a597 100644
--- a/crates/ra_analysis/src/db.rs
+++ b/crates/ra_analysis/src/db.rs
@@ -105,6 +105,7 @@ salsa::database_storage! {
             fn type_for_field() for hir::db::TypeForFieldQuery;
             fn struct_data() for hir::db::StructDataQuery;
             fn enum_data() for hir::db::EnumDataQuery;
+            fn impls_in_crate() for hir::db::ImplsInCrateQuery;
         }
     }
 }
diff --git a/crates/ra_hir/src/db.rs b/crates/ra_hir/src/db.rs
index 73a4cdc5c..6d5235ba4 100644
--- a/crates/ra_hir/src/db.rs
+++ b/crates/ra_hir/src/db.rs
@@ -4,7 +4,7 @@ use ra_syntax::{SyntaxNode, SourceFileNode};
 use ra_db::{SourceRootId, LocationIntener, SyntaxDatabase, Cancelable};
 
 use crate::{
-    DefLoc, DefId, MacroCallLoc, MacroCallId, Name, HirFileId,
+    Crate, DefLoc, DefId, MacroCallLoc, MacroCallId, Name, HirFileId,
     SourceFileItems, SourceItemId,
     query_definitions,
     FnScopes,
@@ -13,6 +13,7 @@ use crate::{
     nameres::{ItemMap, InputModuleItems}},
     ty::{InferenceResult, Ty},
     adt::{StructData, EnumData},
+    impl_block::CrateImplBlocks,
 };
 
 salsa::query_group! {
@@ -87,6 +88,11 @@ pub trait HirDatabase: SyntaxDatabase
         type ModuleTreeQuery;
         use fn crate::module::imp::module_tree;
     }
+
+    fn impls_in_crate(krate: Crate) -> Cancelable<Arc<CrateImplBlocks>> {
+        type ImplsInCrateQuery;
+        use fn crate::impl_block::impls_in_crate;
+    }
 }
 
 }
diff --git a/crates/ra_hir/src/function.rs b/crates/ra_hir/src/function.rs
index 5a44132fc..75ef308ae 100644
--- a/crates/ra_hir/src/function.rs
+++ b/crates/ra_hir/src/function.rs
@@ -11,11 +11,11 @@ use ra_syntax::{
     ast::{self, AstNode, DocCommentsOwner, NameOwner},
 };
 
-use crate::{DefId, DefKind, HirDatabase, ty::InferenceResult, Module};
+use crate::{DefId, DefKind, HirDatabase, ty::InferenceResult, Module, Crate, impl_block::ImplBlock};
 
 pub use self::scope::FnScopes;
 
-#[derive(Debug)]
+#[derive(Debug, Clone, PartialEq, Eq)]
 pub struct Function {
     def_id: DefId,
 }
@@ -25,6 +25,10 @@ impl Function {
         Function { def_id }
     }
 
+    pub fn def_id(&self) -> DefId {
+        self.def_id
+    }
+
     pub fn syntax(&self, db: &impl HirDatabase) -> ast::FnDefNode {
         let def_loc = self.def_id.loc(db);
         assert!(def_loc.kind == DefKind::Function);
@@ -48,6 +52,15 @@ impl Function {
     pub fn module(&self, db: &impl HirDatabase) -> Cancelable<Module> {
         self.def_id.module(db)
     }
+
+    pub fn krate(&self, db: &impl HirDatabase) -> Cancelable<Option<Crate>> {
+        self.def_id.krate(db)
+    }
+
+    /// The containing impl block, if this is a method.
+    pub fn impl_block(&self, db: &impl HirDatabase) -> Cancelable<Option<ImplBlock>> {
+        self.def_id.impl_block(db)
+    }
 }
 
 #[derive(Debug, Clone)]
diff --git a/crates/ra_hir/src/ids.rs b/crates/ra_hir/src/ids.rs
index 66adacc7d..c98be66f9 100644
--- a/crates/ra_hir/src/ids.rs
+++ b/crates/ra_hir/src/ids.rs
@@ -2,7 +2,7 @@ use ra_db::{SourceRootId, LocationIntener, Cancelable, FileId};
 use ra_syntax::{SourceFileNode, SyntaxKind, SyntaxNode, SyntaxNodeRef, SourceFile, AstNode, ast};
 use ra_arena::{Arena, RawId, impl_arena_id};
 
-use crate::{HirDatabase, PerNs, ModuleId, Module, Def, Function, Struct, Enum};
+use crate::{HirDatabase, PerNs, ModuleId, Module, Def, Function, Struct, Enum, ImplBlock, Crate};
 
 /// hir makes a heavy use of ids: integer (u32) handlers to various things. You
 /// can think of id as a pointer (but without a lifetime) or a file descriptor
@@ -177,6 +177,17 @@ impl DefId {
         let loc = self.loc(db);
         Module::new(db, loc.source_root_id, loc.module_id)
     }
+
+    /// Returns the containing crate.
+    pub fn krate(&self, db: &impl HirDatabase) -> Cancelable<Option<Crate>> {
+        Ok(self.module(db)?.krate(db))
+    }
+
+    /// Returns the containing impl block, if this is an impl item.
+    pub fn impl_block(self, db: &impl HirDatabase) -> Cancelable<Option<ImplBlock>> {
+        let crate_impls = db.impls_in_crate(ctry!(self.krate(db)?))?;
+        Ok(ImplBlock::containing(crate_impls, self))
+    }
 }
 
 impl DefLoc {
diff --git a/crates/ra_hir/src/impl_block.rs b/crates/ra_hir/src/impl_block.rs
new file mode 100644
index 000000000..22f0a4461
--- /dev/null
+++ b/crates/ra_hir/src/impl_block.rs
@@ -0,0 +1,172 @@
+use std::sync::Arc;
+use rustc_hash::FxHashMap;
+
+use ra_arena::{Arena, RawId, impl_arena_id};
+use ra_syntax::ast::{self, AstNode};
+use ra_db::{LocationIntener, Cancelable};
+
+use crate::{
+    Crate, DefId, DefLoc, DefKind, SourceItemId, SourceFileItems,
+    Module, Function,
+    db::HirDatabase,
+    type_ref::TypeRef,
+    module::{ModuleSourceNode},
+};
+
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct ImplBlock {
+    crate_impl_blocks: Arc<CrateImplBlocks>,
+    impl_id: ImplId,
+}
+
+impl ImplBlock {
+    pub(crate) fn containing(
+        crate_impl_blocks: Arc<CrateImplBlocks>,
+        def_id: DefId,
+    ) -> Option<ImplBlock> {
+        let impl_id = *crate_impl_blocks.impls_by_def.get(&def_id)?;
+        Some(ImplBlock {
+            crate_impl_blocks,
+            impl_id,
+        })
+    }
+
+    fn impl_data(&self) -> &ImplData {
+        &self.crate_impl_blocks.impls[self.impl_id]
+    }
+
+    pub fn target(&self) -> &TypeRef {
+        &self.impl_data().impl_for
+    }
+
+    pub fn items(&self) -> &[ImplItem] {
+        &self.impl_data().items
+    }
+}
+
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct ImplData {
+    impl_for: TypeRef,
+    items: Vec<ImplItem>,
+}
+
+impl ImplData {
+    pub(crate) fn from_ast(
+        db: &impl AsRef<LocationIntener<DefLoc, DefId>>,
+        file_items: &SourceFileItems,
+        module: &Module,
+        node: ast::ImplBlock,
+    ) -> Self {
+        let impl_for = TypeRef::from_ast_opt(node.target_type());
+        let file_id = module.source().file_id();
+        let items = if let Some(item_list) = node.item_list() {
+            item_list
+                .impl_items()
+                .map(|item_node| {
+                    let kind = match item_node {
+                        ast::ImplItem::FnDef(..) => DefKind::Function,
+                        ast::ImplItem::ConstDef(..) => DefKind::Item,
+                        ast::ImplItem::TypeDef(..) => DefKind::Item,
+                    };
+                    let item_id = file_items.id_of_unchecked(item_node.syntax());
+                    let def_loc = DefLoc {
+                        kind,
+                        source_root_id: module.source_root_id,
+                        module_id: module.module_id,
+                        source_item_id: SourceItemId {
+                            file_id,
+                            item_id: Some(item_id),
+                        },
+                    };
+                    let def_id = def_loc.id(db);
+                    match item_node {
+                        ast::ImplItem::FnDef(..) => ImplItem::Method(Function::new(def_id)),
+                        ast::ImplItem::ConstDef(..) => ImplItem::Const(def_id),
+                        ast::ImplItem::TypeDef(..) => ImplItem::Type(def_id),
+                    }
+                })
+                .collect()
+        } else {
+            Vec::new()
+        };
+        ImplData { impl_for, items }
+    }
+}
+
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub enum ImplItem {
+    Method(Function),
+    // these don't have their own types yet
+    Const(DefId),
+    Type(DefId),
+    // Existential
+}
+
+impl ImplItem {
+    pub fn def_id(&self) -> DefId {
+        match self {
+            ImplItem::Method(f) => f.def_id(),
+            ImplItem::Const(def_id) => *def_id,
+            ImplItem::Type(def_id) => *def_id,
+        }
+    }
+}
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
+pub struct ImplId(pub RawId);
+impl_arena_id!(ImplId);
+
+/// We have to collect all impl blocks in a crate, to later be able to find
+/// impls for specific types.
+#[derive(Debug, PartialEq, Eq)]
+pub struct CrateImplBlocks {
+    impls: Arena<ImplId, ImplData>,
+    impls_by_def: FxHashMap<DefId, ImplId>,
+}
+
+impl CrateImplBlocks {
+    fn new() -> Self {
+        CrateImplBlocks {
+            impls: Arena::default(),
+            impls_by_def: FxHashMap::default(),
+        }
+    }
+
+    fn collect(&mut self, db: &impl HirDatabase, module: Module) -> Cancelable<()> {
+        let module_source_node = module.source().resolve(db);
+        let node = match &module_source_node {
+            ModuleSourceNode::SourceFile(node) => node.borrowed().syntax(),
+            ModuleSourceNode::Module(node) => node.borrowed().syntax(),
+        };
+
+        let source_file_items = db.file_items(module.source().file_id());
+
+        for impl_block_ast in node.children().filter_map(ast::ImplBlock::cast) {
+            let impl_block = ImplData::from_ast(db, &source_file_items, &module, impl_block_ast);
+            let id = self.impls.alloc(impl_block);
+            for impl_item in &self.impls[id].items {
+                self.impls_by_def.insert(impl_item.def_id(), id);
+            }
+        }
+
+        for (_, child) in module.children() {
+            self.collect(db, child)?;
+        }
+
+        Ok(())
+    }
+}
+
+pub(crate) fn impls_in_crate(
+    db: &impl HirDatabase,
+    krate: Crate,
+) -> Cancelable<Arc<CrateImplBlocks>> {
+    let mut result = CrateImplBlocks::new();
+    let root_module = if let Some(root) = krate.root_module(db)? {
+        root
+    } else {
+        return Ok(Arc::new(result));
+    };
+    result.collect(db, root_module)?;
+    Ok(Arc::new(result))
+}
diff --git a/crates/ra_hir/src/krate.rs b/crates/ra_hir/src/krate.rs
index a0821d15d..5194e280b 100644
--- a/crates/ra_hir/src/krate.rs
+++ b/crates/ra_hir/src/krate.rs
@@ -5,7 +5,7 @@ use crate::{HirDatabase, Module, Name, AsName, HirFileId};
 /// hir::Crate describes a single crate. It's the main inteface with which
 /// crate's dependencies interact. Mostly, it should be just a proxy for the
 /// root module.
-#[derive(Debug)]
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
 pub struct Crate {
     crate_id: CrateId,
 }
diff --git a/crates/ra_hir/src/lib.rs b/crates/ra_hir/src/lib.rs
index 344b543b6..2abcec441 100644
--- a/crates/ra_hir/src/lib.rs
+++ b/crates/ra_hir/src/lib.rs
@@ -31,6 +31,7 @@ mod function;
 mod adt;
 mod type_ref;
 mod ty;
+mod impl_block;
 
 use crate::{
     db::HirDatabase,
@@ -48,6 +49,7 @@ pub use self::{
     function::{Function, FnScopes},
     adt::{Struct, Enum},
     ty::Ty,
+    impl_block::{ImplBlock, ImplItem},
 };
 
 pub use self::function::FnSignatureInfo;
diff --git a/crates/ra_hir/src/mock.rs b/crates/ra_hir/src/mock.rs
index 89b18194a..ef245ec7a 100644
--- a/crates/ra_hir/src/mock.rs
+++ b/crates/ra_hir/src/mock.rs
@@ -203,6 +203,7 @@ salsa::database_storage! {
             fn type_for_field() for db::TypeForFieldQuery;
             fn struct_data() for db::StructDataQuery;
             fn enum_data() for db::EnumDataQuery;
+            fn impls_in_crate() for db::ImplsInCrateQuery;
         }
     }
 }
diff --git a/crates/ra_hir/src/module.rs b/crates/ra_hir/src/module.rs
index c70dc54dd..b9821115c 100644
--- a/crates/ra_hir/src/module.rs
+++ b/crates/ra_hir/src/module.rs
@@ -71,6 +71,21 @@ impl Module {
         })
     }
 
+    /// Returns an iterator of all children of this module.
+    pub fn children<'a>(&'a self) -> impl Iterator<Item = (Name, Module)> + 'a {
+        self.module_id
+            .children(&self.tree)
+            .map(move |(name, module_id)| {
+                (
+                    name,
+                    Module {
+                        module_id,
+                        ..self.clone()
+                    },
+                )
+            })
+    }
+
     /// Returns the crate this module is part of.
     pub fn krate(&self, db: &impl HirDatabase) -> Option<Crate> {
         let root_id = self.module_id.crate_root(&self.tree);
diff --git a/crates/ra_syntax/src/ast/generated.rs b/crates/ra_syntax/src/ast/generated.rs
index c1c63f555..91de17ddf 100644
--- a/crates/ra_syntax/src/ast/generated.rs
+++ b/crates/ra_syntax/src/ast/generated.rs
@@ -1442,7 +1442,39 @@ impl<R: TreeRoot<RaTypes>> ImplBlockNode<R> {
 }
 
 
-impl<'a> ImplBlock<'a> {}
+impl<'a> ImplBlock<'a> {
+    pub fn item_list(self) -> Option<ItemList<'a>> {
+        super::child_opt(self)
+    }
+}
+
+// ImplItem
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub enum ImplItem<'a> {
+    FnDef(FnDef<'a>),
+    TypeDef(TypeDef<'a>),
+    ConstDef(ConstDef<'a>),
+}
+
+impl<'a> AstNode<'a> for ImplItem<'a> {
+    fn cast(syntax: SyntaxNodeRef<'a>) -> Option<Self> {
+        match syntax.kind() {
+            FN_DEF => Some(ImplItem::FnDef(FnDef { syntax })),
+            TYPE_DEF => Some(ImplItem::TypeDef(TypeDef { syntax })),
+            CONST_DEF => Some(ImplItem::ConstDef(ConstDef { syntax })),
+            _ => None,
+        }
+    }
+    fn syntax(self) -> SyntaxNodeRef<'a> {
+        match self {
+            ImplItem::FnDef(inner) => inner.syntax(),
+            ImplItem::TypeDef(inner) => inner.syntax(),
+            ImplItem::ConstDef(inner) => inner.syntax(),
+        }
+    }
+}
+
+impl<'a> ImplItem<'a> {}
 
 // ImplTraitType
 #[derive(Debug, Clone, Copy,)]
@@ -1555,7 +1587,11 @@ impl<R: TreeRoot<RaTypes>> ItemListNode<R> {
 
 impl<'a> ast::FnDefOwner<'a> for ItemList<'a> {}
 impl<'a> ast::ModuleItemOwner<'a> for ItemList<'a> {}
-impl<'a> ItemList<'a> {}
+impl<'a> ItemList<'a> {
+    pub fn impl_items(self) -> impl Iterator<Item = ImplItem<'a>> + 'a {
+        super::children(self)
+    }
+}
 
 // Label
 #[derive(Debug, Clone, Copy,)]
diff --git a/crates/ra_syntax/src/grammar.ron b/crates/ra_syntax/src/grammar.ron
index 9a4a96fac..688a4af1e 100644
--- a/crates/ra_syntax/src/grammar.ron
+++ b/crates/ra_syntax/src/grammar.ron
@@ -284,6 +284,7 @@ Grammar(
             options: [ "ItemList" ]
         ),
         "ItemList": (
+            collections: [["impl_items", "ImplItem"]],
             traits: [ "FnDefOwner", "ModuleItemOwner" ],
         ),
         "ConstDef": ( traits: [
@@ -307,7 +308,7 @@ Grammar(
             "AttrsOwner",
             "DocCommentsOwner"
         ] ),
-        "ImplBlock": (collections: []),
+        "ImplBlock": (options: ["ItemList"]),
 
         "ParenType": (options: ["TypeRef"]),
         "TupleType": ( collections: [["fields", "TypeRef"]] ),
@@ -351,6 +352,9 @@ Grammar(
             enum: ["StructDef", "EnumDef", "FnDef", "TraitDef", "TypeDef", "ImplBlock",
                    "UseItem", "ExternCrateItem", "ConstDef", "StaticDef", "Module" ]
         ),
+        "ImplItem": (
+            enum: ["FnDef", "TypeDef", "ConstDef"]
+        ),
 
         "TupleExpr": (),
         "ArrayExpr": (),