14 files changed, 279 insertions, 18 deletions

diff --git a/README.md b/README.md
index ad600d162..cffc00953 100644
--- a/README.md
+++ b/README.md
@@ -120,7 +120,7 @@ and trait selection) to the existing rustc.
 - [ ] [textDocument/declaration](https://microsoft.github.io/language-server-protocol/specification#textDocument_declaration)
 - [x] [textDocument/definition](https://microsoft.github.io/language-server-protocol/specification#textDocument_definition)
 - [ ] [textDocument/typeDefinition](https://microsoft.github.io/language-server-protocol/specification#textDocument_typeDefinition)
-- [ ] [textDocument/implementation](https://microsoft.github.io/language-server-protocol/specification#textDocument_implementation)
+- [x] [textDocument/implementation](https://microsoft.github.io/language-server-protocol/specification#textDocument_implementation)
 - [x] [textDocument/references](https://microsoft.github.io/language-server-protocol/specification#textDocument_references)
 - [x] [textDocument/documentHighlight](https://microsoft.github.io/language-server-protocol/specification#textDocument_documentHighlight)
 - [x] [textDocument/documentSymbol](https://microsoft.github.io/language-server-protocol/specification#textDocument_documentSymbol)
diff --git a/crates/ra_hir/src/code_model_api.rs b/crates/ra_hir/src/code_model_api.rs
index e4008058c..691cd5798 100644
--- a/crates/ra_hir/src/code_model_api.rs
+++ b/crates/ra_hir/src/code_model_api.rs
@@ -10,12 +10,13 @@ use crate::{
     nameres::{ModuleScope, lower::ImportId},
     db::HirDatabase,
     expr::BodySyntaxMapping,
-    ty::InferenceResult,
+    ty::{InferenceResult},
     adt::{EnumVariantId, StructFieldId, VariantDef},
     generics::GenericParams,
     docs::{Documentation, Docs, docs_from_ast},
     module_tree::ModuleId,
     ids::{FunctionId, StructId, EnumId, AstItemDef, ConstId, StaticId, TraitId, TypeId},
+    impl_block::ImplId,
 };
 
 /// hir::Crate describes a single crate. It's the main interface with which
@@ -23,7 +24,7 @@ use crate::{
 /// root module.
 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
 pub struct Crate {
-    pub(crate) crate_id: CrateId,
+    pub crate_id: CrateId,
 }
 
 #[derive(Debug)]
@@ -126,6 +127,11 @@ impl Module {
         self.import_source_impl(db, import)
     }
 
+    /// Returns the syntax of the impl block in this module
+    pub fn impl_source(&self, db: &impl HirDatabase, impl_id: ImplId) -> TreeArc<ast::ImplBlock> {
+        self.impl_source_impl(db, impl_id)
+    }
+
     /// Returns the crate this module is part of.
     pub fn krate(&self, db: &impl HirDatabase) -> Option<Crate> {
         self.krate_impl(db)
@@ -272,6 +278,10 @@ impl Struct {
     pub fn generic_params(&self, db: &impl HirDatabase) -> Arc<GenericParams> {
         db.generic_params((*self).into())
     }
+
+    pub fn ty(&self, db: &impl HirDatabase) -> Ty {
+        db.type_for_def((*self).into())
+    }
 }
 
 impl Docs for Struct {
@@ -317,6 +327,10 @@ impl Enum {
     pub fn generic_params(&self, db: &impl HirDatabase) -> Arc<GenericParams> {
         db.generic_params((*self).into())
     }
+
+    pub fn ty(&self, db: &impl HirDatabase) -> Ty {
+        db.type_for_def((*self).into())
+    }
 }
 
 impl Docs for Enum {
diff --git a/crates/ra_hir/src/code_model_impl/module.rs b/crates/ra_hir/src/code_model_impl/module.rs
index 418d59c91..c6f85ac82 100644
--- a/crates/ra_hir/src/code_model_impl/module.rs
+++ b/crates/ra_hir/src/code_model_impl/module.rs
@@ -5,6 +5,7 @@ use crate::{
     Module, ModuleSource, Problem,
     Crate, Name,
     module_tree::ModuleId,
+    impl_block::ImplId,
     nameres::{lower::ImportId},
     db::HirDatabase,
 };
@@ -51,11 +52,21 @@ impl Module {
         db: &impl HirDatabase,
         import: ImportId,
     ) -> TreeArc<ast::PathSegment> {
-        let source_map = db.lower_module_source_map(self.clone());
+        let source_map = db.lower_module_source_map(*self);
         let (_, source) = self.definition_source(db);
         source_map.get(&source, import)
     }
 
+    pub(crate) fn impl_source_impl(
+        &self,
+        db: &impl HirDatabase,
+        impl_id: ImplId,
+    ) -> TreeArc<ast::ImplBlock> {
+        let source_map = db.impls_in_module_source_map(*self);
+        let (_, source) = self.definition_source(db);
+        source_map.get(&source, impl_id)
+    }
+
     pub(crate) fn krate_impl(&self, _db: &impl HirDatabase) -> Option<Crate> {
         Some(Crate::new(self.krate))
     }
diff --git a/crates/ra_hir/src/db.rs b/crates/ra_hir/src/db.rs
index 3f76b769d..70d9de212 100644
--- a/crates/ra_hir/src/db.rs
+++ b/crates/ra_hir/src/db.rs
@@ -14,7 +14,7 @@ use crate::{
     nameres::{ItemMap, lower::{LoweredModule, ImportSourceMap}},
     ty::{InferenceResult, Ty, method_resolution::CrateImplBlocks, TypableDef},
     adt::{StructData, EnumData},
-    impl_block::ModuleImplBlocks,
+    impl_block::{ModuleImplBlocks, ImplSourceMap},
     generics::{GenericParams, GenericDef},
     ids::SourceFileItemId,
 };
@@ -73,9 +73,18 @@ pub trait HirDatabase: SourceDatabase + AsRef<HirInterner> {
     #[salsa::invoke(crate::module_tree::ModuleTree::module_tree_query)]
     fn module_tree(&self, crate_id: CrateId) -> Arc<ModuleTree>;
 
+    #[salsa::invoke(crate::impl_block::impls_in_module_with_source_map_query)]
+    fn impls_in_module_with_source_map(
+        &self,
+        module: Module,
+    ) -> (Arc<ModuleImplBlocks>, Arc<ImplSourceMap>);
+
     #[salsa::invoke(crate::impl_block::impls_in_module)]
     fn impls_in_module(&self, module: Module) -> Arc<ModuleImplBlocks>;
 
+    #[salsa::invoke(crate::impl_block::impls_in_module_source_map_query)]
+    fn impls_in_module_source_map(&self, module: Module) -> Arc<ImplSourceMap>;
+
     #[salsa::invoke(crate::ty::method_resolution::CrateImplBlocks::impls_in_crate_query)]
     fn impls_in_crate(&self, krate: Crate) -> Arc<CrateImplBlocks>;
 
diff --git a/crates/ra_hir/src/impl_block.rs b/crates/ra_hir/src/impl_block.rs
index 222e47349..5fc26324a 100644
--- a/crates/ra_hir/src/impl_block.rs
+++ b/crates/ra_hir/src/impl_block.rs
@@ -1,8 +1,10 @@
 use std::sync::Arc;
 use rustc_hash::FxHashMap;
 
-use ra_arena::{Arena, RawId, impl_arena_id};
-use ra_syntax::ast::{self, AstNode};
+use ra_arena::{Arena, RawId, impl_arena_id, map::ArenaMap};
+use ra_syntax::{
+    AstPtr, SourceFile, TreeArc,
+ast::{self, AstNode}};
 
 use crate::{
     Const, Type,
@@ -14,6 +16,26 @@ use crate::{
 
 use crate::code_model_api::{Module, ModuleSource};
 
+#[derive(Debug, Default, PartialEq, Eq)]
+pub struct ImplSourceMap {
+    map: ArenaMap<ImplId, AstPtr<ast::ImplBlock>>,
+}
+
+impl ImplSourceMap {
+    fn insert(&mut self, impl_id: ImplId, impl_block: &ast::ImplBlock) {
+        self.map.insert(impl_id, AstPtr::new(impl_block))
+    }
+
+    pub fn get(&self, source: &ModuleSource, impl_id: ImplId) -> TreeArc<ast::ImplBlock> {
+        let file = match source {
+            ModuleSource::SourceFile(file) => &*file,
+            ModuleSource::Module(m) => m.syntax().ancestors().find_map(SourceFile::cast).unwrap(),
+        };
+
+        self.map[impl_id].to_node(file).to_owned()
+    }
+}
+
 #[derive(Debug, Clone, PartialEq, Eq)]
 pub struct ImplBlock {
     module_impl_blocks: Arc<ModuleImplBlocks>,
@@ -39,6 +61,10 @@ impl ImplBlock {
         }
     }
 
+    pub fn id(&self) -> ImplId {
+        self.impl_id
+    }
+
     fn impl_data(&self) -> &ImplData {
         &self.module_impl_blocks.impls[self.impl_id]
     }
@@ -148,7 +174,7 @@ impl ModuleImplBlocks {
         }
     }
 
-    fn collect(&mut self, db: &impl HirDatabase, module: Module) {
+    fn collect(&mut self, db: &impl HirDatabase, module: Module, source_map: &mut ImplSourceMap) {
         let (file_id, module_source) = module.definition_source(db);
         let file_id: HirFileId = file_id.into();
         let node = match &module_source {
@@ -165,12 +191,31 @@ impl ModuleImplBlocks {
             for &impl_item in &self.impls[id].items {
                 self.impls_by_def.insert(impl_item, id);
             }
+
+            source_map.insert(id, impl_block_ast);
         }
     }
 }
 
-pub(crate) fn impls_in_module(db: &impl HirDatabase, module: Module) -> Arc<ModuleImplBlocks> {
+pub(crate) fn impls_in_module_with_source_map_query(
+    db: &impl HirDatabase,
+    module: Module,
+) -> (Arc<ModuleImplBlocks>, Arc<ImplSourceMap>) {
+    let mut source_map = ImplSourceMap::default();
+
     let mut result = ModuleImplBlocks::new();
-    result.collect(db, module);
-    Arc::new(result)
+    result.collect(db, module, &mut source_map);
+
+    (Arc::new(result), Arc::new(source_map))
+}
+
+pub(crate) fn impls_in_module(db: &impl HirDatabase, module: Module) -> Arc<ModuleImplBlocks> {
+    db.impls_in_module_with_source_map(module).0
+}
+
+pub(crate) fn impls_in_module_source_map_query(
+    db: &impl HirDatabase,
+    module: Module,
+) -> Arc<ImplSourceMap> {
+    db.impls_in_module_with_source_map(module).1
 }
diff --git a/crates/ra_hir/src/source_binder.rs b/crates/ra_hir/src/source_binder.rs
index f523f0647..589efd023 100644
--- a/crates/ra_hir/src/source_binder.rs
+++ b/crates/ra_hir/src/source_binder.rs
@@ -13,7 +13,7 @@ use ra_syntax::{
 };
 
 use crate::{
-    HirDatabase, Function, ModuleDef,
+    HirDatabase, Function, ModuleDef, Struct, Enum,
     AsName, Module, HirFileId,
     ids::{LocationCtx, SourceFileItemId},
 };
@@ -128,6 +128,28 @@ pub fn function_from_child_node(
     function_from_source(db, file_id, fn_def)
 }
 
+pub fn struct_from_module(
+    db: &impl HirDatabase,
+    module: Module,
+    struct_def: &ast::StructDef,
+) -> Struct {
+    let (file_id, _) = module.definition_source(db);
+    let file_id = file_id.into();
+    let ctx = LocationCtx::new(db, module, file_id);
+    Struct {
+        id: ctx.to_def(struct_def),
+    }
+}
+
+pub fn enum_from_module(db: &impl HirDatabase, module: Module, enum_def: &ast::EnumDef) -> Enum {
+    let (file_id, _) = module.definition_source(db);
+    let file_id = file_id.into();
+    let ctx = LocationCtx::new(db, module, file_id);
+    Enum {
+        id: ctx.to_def(enum_def),
+    }
+}
+
 pub fn macro_symbols(db: &impl HirDatabase, file_id: FileId) -> Vec<(SmolStr, TextRange)> {
     let module = match module_from_file_id(db, file_id) {
         Some(it) => it,
diff --git a/crates/ra_hir/src/ty/method_resolution.rs b/crates/ra_hir/src/ty/method_resolution.rs
index 9a571c2aa..d70a24582 100644
--- a/crates/ra_hir/src/ty/method_resolution.rs
+++ b/crates/ra_hir/src/ty/method_resolution.rs
@@ -44,7 +44,7 @@ impl CrateImplBlocks {
         &'a self,
         db: &'a impl HirDatabase,
         ty: &Ty,
-    ) -> impl Iterator<Item = ImplBlock> + 'a {
+    ) -> impl Iterator<Item = (Module, ImplBlock)> + 'a {
         let fingerprint = TyFingerprint::for_impl(ty);
         fingerprint
             .and_then(|f| self.impls.get(&f))
@@ -56,7 +56,7 @@ impl CrateImplBlocks {
                     module_id: *module_id,
                 };
                 let module_impl_blocks = db.impls_in_module(module);
-                ImplBlock::from_id(module_impl_blocks, *impl_id)
+                (module, ImplBlock::from_id(module_impl_blocks, *impl_id))
             })
     }
 
@@ -152,7 +152,7 @@ impl Ty {
             };
             let impls = db.impls_in_crate(krate);
 
-            for impl_block in impls.lookup_impl_blocks(db, &derefed_ty) {
+            for (_, impl_block) in impls.lookup_impl_blocks(db, &derefed_ty) {
                 for item in impl_block.items() {
                     match item {
                         ImplItem::Method(f) => {
diff --git a/crates/ra_ide_api/src/impls.rs b/crates/ra_ide_api/src/impls.rs
new file mode 100644
index 000000000..16a05758a
--- /dev/null
+++ b/crates/ra_ide_api/src/impls.rs
@@ -0,0 +1,121 @@
+use ra_db::{SourceDatabase};
+use ra_syntax::{
+    AstNode, ast,
+    algo::find_node_at_offset,
+};
+use hir::{db::HirDatabase, source_binder};
+
+use crate::{FilePosition, NavigationTarget, db::RootDatabase, RangeInfo};
+
+pub(crate) fn goto_implementation(
+    db: &RootDatabase,
+    position: FilePosition,
+) -> Option<RangeInfo<Vec<NavigationTarget>>> {
+    let file = db.parse(position.file_id);
+    let syntax = file.syntax();
+
+    let krate_id = db.crate_for(position.file_id).pop()?;
+    let krate = hir::Crate { crate_id: krate_id };
+    let module = source_binder::module_from_position(db, position)?;
+
+    let node = find_node_at_offset::<ast::NominalDef>(syntax, position.offset)?;
+    let ty = match node.kind() {
+        ast::NominalDefKind::StructDef(def) => {
+            source_binder::struct_from_module(db, module, &def).ty(db)
+        }
+        ast::NominalDefKind::EnumDef(def) => {
+            source_binder::enum_from_module(db, module, &def).ty(db)
+        }
+    };
+
+    let impls = db.impls_in_crate(krate);
+
+    let navs = impls
+        .lookup_impl_blocks(db, &ty)
+        .map(|(module, imp)| NavigationTarget::from_impl_block(db, module, &imp));
+
+    Some(RangeInfo::new(node.syntax().range(), navs.collect()))
+}
+
+#[cfg(test)]
+mod tests {
+    use crate::mock_analysis::analysis_and_position;
+
+    fn check_goto(fixuture: &str, expected: &[&str]) {
+        let (analysis, pos) = analysis_and_position(fixuture);
+
+        let navs = analysis.goto_implementation(pos).unwrap().unwrap().info;
+        assert_eq!(navs.len(), expected.len());
+        navs.into_iter()
+            .enumerate()
+            .for_each(|(i, nav)| nav.assert_match(expected[i]));
+    }
+
+    #[test]
+    fn goto_implementation_works() {
+        check_goto(
+            "
+            //- /lib.rs
+            struct Foo<|>;
+            impl Foo {}
+            ",
+            &["impl IMPL_BLOCK FileId(1) [12; 23)"],
+        );
+    }
+
+    #[test]
+    fn goto_implementation_works_multiple_blocks() {
+        check_goto(
+            "
+            //- /lib.rs
+            struct Foo<|>;
+            impl Foo {}
+            impl Foo {}
+            ",
+            &[
+                "impl IMPL_BLOCK FileId(1) [12; 23)",
+                "impl IMPL_BLOCK FileId(1) [24; 35)",
+            ],
+        );
+    }
+
+    #[test]
+    fn goto_implementation_works_multiple_mods() {
+        check_goto(
+            "
+            //- /lib.rs
+            struct Foo<|>;
+            mod a {
+                impl super::Foo {}
+            }
+            mod b {
+                impl super::Foo {}
+            }
+            ",
+            &[
+                "impl IMPL_BLOCK FileId(1) [24; 42)",
+                "impl IMPL_BLOCK FileId(1) [57; 75)",
+            ],
+        );
+    }
+
+    #[test]
+    fn goto_implementation_works_multiple_files() {
+        check_goto(
+            "
+            //- /lib.rs
+            struct Foo<|>;
+            mod a;
+            mod b;
+            //- /a.rs
+            impl crate::Foo {}
+            //- /b.rs
+            impl crate::Foo {}
+            ",
+            &[
+                "impl IMPL_BLOCK FileId(2) [0; 18)",
+                "impl IMPL_BLOCK FileId(3) [0; 18)",
+            ],
+        );
+    }
+}
diff --git a/crates/ra_ide_api/src/lib.rs b/crates/ra_ide_api/src/lib.rs
index 51947e4cc..9ec4fdd95 100644
--- a/crates/ra_ide_api/src/lib.rs
+++ b/crates/ra_ide_api/src/lib.rs
@@ -25,6 +25,7 @@ mod call_info;
 mod syntax_highlighting;
 mod parent_module;
 mod rename;
+mod impls;
 
 #[cfg(test)]
 mod marks;
@@ -415,6 +416,13 @@ impl Analysis {
         self.with_db(|db| goto_definition::goto_definition(db, position))
     }
 
+    pub fn goto_implementation(
+        &self,
+        position: FilePosition,
+    ) -> Cancelable<Option<RangeInfo<Vec<NavigationTarget>>>> {
+        self.with_db(|db| impls::goto_implementation(db, position))
+    }
+
     /// Finds all usages of the reference at point.
     pub fn find_all_refs(&self, position: FilePosition) -> Cancelable<Vec<(FileId, TextRange)>> {
         self.with_db(|db| db.find_all_refs(position))
diff --git a/crates/ra_ide_api/src/navigation_target.rs b/crates/ra_ide_api/src/navigation_target.rs
index d73d4afa7..5ccb5cc2e 100644
--- a/crates/ra_ide_api/src/navigation_target.rs
+++ b/crates/ra_ide_api/src/navigation_target.rs
@@ -147,6 +147,16 @@ impl NavigationTarget {
         }
     }
 
+    pub(crate) fn from_impl_block(
+        db: &RootDatabase,
+        module: hir::Module,
+        impl_block: &hir::ImplBlock,
+    ) -> NavigationTarget {
+        let (file_id, _) = module.definition_source(db);
+        let node = module.impl_source(db, impl_block.id());
+        NavigationTarget::from_syntax(file_id, "impl".into(), None, node.syntax())
+    }
+
     #[cfg(test)]
     pub(crate) fn assert_match(&self, expected: &str) {
         let actual = self.debug_render();
diff --git a/crates/ra_lsp_server/src/caps.rs b/crates/ra_lsp_server/src/caps.rs
index bca079d65..254624487 100644
--- a/crates/ra_lsp_server/src/caps.rs
+++ b/crates/ra_lsp_server/src/caps.rs
@@ -2,7 +2,7 @@ use lsp_types::{
     CodeActionProviderCapability, CodeLensOptions, CompletionOptions, DocumentOnTypeFormattingOptions,
     ExecuteCommandOptions, FoldingRangeProviderCapability, RenameOptions, RenameProviderCapability,
     ServerCapabilities, SignatureHelpOptions, TextDocumentSyncCapability, TextDocumentSyncKind,
-    TextDocumentSyncOptions,
+    TextDocumentSyncOptions, ImplementationProviderCapability,
 };
 
 pub fn server_capabilities() -> ServerCapabilities {
@@ -26,7 +26,7 @@ pub fn server_capabilities() -> ServerCapabilities {
         }),
         definition_provider: Some(true),
         type_definition_provider: None,
-        implementation_provider: None,
+        implementation_provider: Some(ImplementationProviderCapability::Simple(true)),
         references_provider: Some(true),
         document_highlight_provider: Some(true),
         document_symbol_provider: Some(true),
diff --git a/crates/ra_lsp_server/src/main_loop.rs b/crates/ra_lsp_server/src/main_loop.rs
index e430ac6de..df390c19e 100644
--- a/crates/ra_lsp_server/src/main_loop.rs
+++ b/crates/ra_lsp_server/src/main_loop.rs
@@ -305,6 +305,7 @@ fn on_request(
         .on::<req::DocumentSymbolRequest>(handlers::handle_document_symbol)?
         .on::<req::WorkspaceSymbol>(handlers::handle_workspace_symbol)?
         .on::<req::GotoDefinition>(handlers::handle_goto_definition)?
+        .on::<req::GotoImplementation>(handlers::handle_goto_implementation)?
         .on::<req::ParentModule>(handlers::handle_parent_module)?
         .on::<req::Runnables>(handlers::handle_runnables)?
         .on::<req::DecorationsRequest>(handlers::handle_decorations)?
diff --git a/crates/ra_lsp_server/src/main_loop/handlers.rs b/crates/ra_lsp_server/src/main_loop/handlers.rs
index 9478ebfb8..e94d76903 100644
--- a/crates/ra_lsp_server/src/main_loop/handlers.rs
+++ b/crates/ra_lsp_server/src/main_loop/handlers.rs
@@ -229,6 +229,26 @@ pub fn handle_goto_definition(
     Ok(Some(req::GotoDefinitionResponse::Link(res)))
 }
 
+pub fn handle_goto_implementation(
+    world: ServerWorld,
+    params: req::TextDocumentPositionParams,
+) -> Result<Option<req::GotoImplementationResponse>> {
+    let position = params.try_conv_with(&world)?;
+    let line_index = world.analysis().file_line_index(position.file_id);
+    let nav_info = match world.analysis().goto_implementation(position)? {
+        None => return Ok(None),
+        Some(it) => it,
+    };
+    let nav_range = nav_info.range;
+    let res = nav_info
+        .info
+        .into_iter()
+        .map(|nav| RangeInfo::new(nav_range, nav))
+        .map(|nav| to_location_link(&nav, &world, &line_index))
+        .collect::<Result<Vec<_>>>()?;
+    Ok(Some(req::GotoDefinitionResponse::Link(res)))
+}
+
 pub fn handle_parent_module(
     world: ServerWorld,
     params: req::TextDocumentPositionParams,
diff --git a/crates/ra_lsp_server/src/req.rs b/crates/ra_lsp_server/src/req.rs
index a4d890755..e224ede80 100644
--- a/crates/ra_lsp_server/src/req.rs
+++ b/crates/ra_lsp_server/src/req.rs
@@ -8,7 +8,7 @@ pub use lsp_types::{
     CompletionParams, CompletionResponse, DocumentOnTypeFormattingParams, DocumentSymbolParams,
     DocumentSymbolResponse, ExecuteCommandParams, Hover, InitializeResult,
     PublishDiagnosticsParams, ReferenceParams, SignatureHelp, TextDocumentEdit,
-    TextDocumentPositionParams, TextEdit, WorkspaceEdit, WorkspaceSymbolParams,
+    TextDocumentPositionParams, TextEdit, WorkspaceEdit, WorkspaceSymbolParams
 };
 
 pub enum AnalyzerStatus {}