8 files changed, 225 insertions, 5 deletions

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);