Merge #2727

2727: Qualify paths in 'add impl members' r=flodiebold a=flodiebold

This makes the 'add impl members' assist qualify paths, so that they should resolve to the same thing as in the definition. To do that, it adds an algorithm that finds a path to refer to any item from any module (if possible), which is actually probably the more important part of this PR :smile: It handles visibility, reexports, renamed crates, prelude etc.; I think the only thing that's missing is support for local items. I'm not sure about the performance, since it takes into account every location where the target item has been `pub use`d, and then recursively goes up the module tree; there's probably potential for optimization by memoizing more, but I think the general shape of the algorithm is necessary to handle every case in Rust's module system.

~The 'find path' part is actually pretty complete, I think; I'm still working on the assist (hence the failing tests).~

Fixes #1943.

Co-authored-by: Florian Diebold <[email protected]>
Co-authored-by: Florian Diebold <[email protected]>

4 files changed, 365 insertions, 67 deletions

diff --git a/crates/ra_assists/Cargo.toml b/crates/ra_assists/Cargo.toml
index 434e6656c..50be8d9bc 100644
--- a/crates/ra_assists/Cargo.toml
+++ b/crates/ra_assists/Cargo.toml
@@ -10,6 +10,7 @@ doctest = false
 [dependencies]
 format-buf = "1.0.0"
 join_to_string = "0.1.3"
+rustc-hash = "1.0"
 itertools = "0.8.0"
 
 ra_syntax = { path = "../ra_syntax" }
diff --git a/crates/ra_assists/src/assists/add_missing_impl_members.rs b/crates/ra_assists/src/assists/add_missing_impl_members.rs
index bc49e71fe..bf1136193 100644
--- a/crates/ra_assists/src/assists/add_missing_impl_members.rs
+++ b/crates/ra_assists/src/assists/add_missing_impl_members.rs
@@ -1,12 +1,13 @@
-use std::collections::HashMap;
-
-use hir::{db::HirDatabase, HasSource};
+use hir::{db::HirDatabase, HasSource, InFile};
 use ra_syntax::{
     ast::{self, edit, make, AstNode, NameOwner},
     SmolStr,
 };
 
-use crate::{Assist, AssistCtx, AssistId};
+use crate::{
+    ast_transform::{self, AstTransform, QualifyPaths, SubstituteTypeParams},
+    Assist, AssistCtx, AssistId,
+};
 
 #[derive(PartialEq)]
 enum AddMissingImplMembersMode {
@@ -134,25 +135,23 @@ fn add_missing_impl_members_inner(
         return None;
     }
 
-    let file_id = ctx.frange.file_id;
     let db = ctx.db;
+    let file_id = ctx.frange.file_id;
+    let trait_file_id = trait_.source(db).file_id;
 
     ctx.add_assist(AssistId(assist_id), label, |edit| {
         let n_existing_items = impl_item_list.impl_items().count();
-        let substs = get_syntactic_substs(impl_node).unwrap_or_default();
-        let generic_def: hir::GenericDef = trait_.into();
-        let substs_by_param: HashMap<_, _> = generic_def
-            .params(db)
-            .into_iter()
-            // this is a trait impl, so we need to skip the first type parameter -- this is a bit hacky
-            .skip(1)
-            .zip(substs.into_iter())
-            .collect();
+        let module = hir::SourceAnalyzer::new(
+            db,
+            hir::InFile::new(file_id.into(), impl_node.syntax()),
+            None,
+        )
+        .module();
+        let ast_transform = QualifyPaths::new(db, module)
+            .or(SubstituteTypeParams::for_trait_impl(db, trait_, impl_node));
         let items = missing_items
             .into_iter()
-            .map(|it| {
-                substitute_type_params(db, hir::InFile::new(file_id.into(), it), &substs_by_param)
-            })
+            .map(|it| ast_transform::apply(&*ast_transform, InFile::new(trait_file_id, it)))
             .map(|it| match it {
                 ast::ImplItem::FnDef(def) => ast::ImplItem::FnDef(add_body(def)),
                 _ => it,
@@ -177,56 +176,6 @@ fn add_body(fn_def: ast::FnDef) -> ast::FnDef {
     }
 }
 
-// FIXME: It would probably be nicer if we could get this via HIR (i.e. get the
-// trait ref, and then go from the types in the substs back to the syntax)
-// FIXME: This should be a general utility (not even just for assists)
-fn get_syntactic_substs(impl_block: ast::ImplBlock) -> Option<Vec<ast::TypeRef>> {
-    let target_trait = impl_block.target_trait()?;
-    let path_type = match target_trait {
-        ast::TypeRef::PathType(path) => path,
-        _ => return None,
-    };
-    let type_arg_list = path_type.path()?.segment()?.type_arg_list()?;
-    let mut result = Vec::new();
-    for type_arg in type_arg_list.type_args() {
-        let type_arg: ast::TypeArg = type_arg;
-        result.push(type_arg.type_ref()?);
-    }
-    Some(result)
-}
-
-// FIXME: This should be a general utility (not even just for assists)
-fn substitute_type_params<N: AstNode>(
-    db: &impl HirDatabase,
-    node: hir::InFile<N>,
-    substs: &HashMap<hir::TypeParam, ast::TypeRef>,
-) -> N {
-    let type_param_replacements = node
-        .value
-        .syntax()
-        .descendants()
-        .filter_map(ast::TypeRef::cast)
-        .filter_map(|n| {
-            let path = match &n {
-                ast::TypeRef::PathType(path_type) => path_type.path()?,
-                _ => return None,
-            };
-            let analyzer = hir::SourceAnalyzer::new(db, node.with_value(n.syntax()), None);
-            let resolution = analyzer.resolve_path(db, &path)?;
-            match resolution {
-                hir::PathResolution::TypeParam(tp) => Some((n, substs.get(&tp)?.clone())),
-                _ => None,
-            }
-        })
-        .collect::<Vec<_>>();
-
-    if type_param_replacements.is_empty() {
-        node.value
-    } else {
-        edit::replace_descendants(&node.value, type_param_replacements.into_iter())
-    }
-}
-
 /// Given an `ast::ImplBlock`, resolves the target trait (the one being
 /// implemented) to a `ast::TraitDef`.
 fn resolve_target_trait_def(
@@ -401,6 +350,174 @@ impl Foo for S {
     }
 
     #[test]
+    fn test_qualify_path_1() {
+        check_assist(
+            add_missing_impl_members,
+            "
+mod foo {
+    pub struct Bar;
+    trait Foo { fn foo(&self, bar: Bar); }
+}
+struct S;
+impl foo::Foo for S { <|> }",
+            "
+mod foo {
+    pub struct Bar;
+    trait Foo { fn foo(&self, bar: Bar); }
+}
+struct S;
+impl foo::Foo for S {
+    <|>fn foo(&self, bar: foo::Bar) { unimplemented!() }
+}",
+        );
+    }
+
+    #[test]
+    fn test_qualify_path_generic() {
+        check_assist(
+            add_missing_impl_members,
+            "
+mod foo {
+    pub struct Bar<T>;
+    trait Foo { fn foo(&self, bar: Bar<u32>); }
+}
+struct S;
+impl foo::Foo for S { <|> }",
+            "
+mod foo {
+    pub struct Bar<T>;
+    trait Foo { fn foo(&self, bar: Bar<u32>); }
+}
+struct S;
+impl foo::Foo for S {
+    <|>fn foo(&self, bar: foo::Bar<u32>) { unimplemented!() }
+}",
+        );
+    }
+
+    #[test]
+    fn test_qualify_path_and_substitute_param() {
+        check_assist(
+            add_missing_impl_members,
+            "
+mod foo {
+    pub struct Bar<T>;
+    trait Foo<T> { fn foo(&self, bar: Bar<T>); }
+}
+struct S;
+impl foo::Foo<u32> for S { <|> }",
+            "
+mod foo {
+    pub struct Bar<T>;
+    trait Foo<T> { fn foo(&self, bar: Bar<T>); }
+}
+struct S;
+impl foo::Foo<u32> for S {
+    <|>fn foo(&self, bar: foo::Bar<u32>) { unimplemented!() }
+}",
+        );
+    }
+
+    #[test]
+    fn test_substitute_param_no_qualify() {
+        // when substituting params, the substituted param should not be qualified!
+        check_assist(
+            add_missing_impl_members,
+            "
+mod foo {
+    trait Foo<T> { fn foo(&self, bar: T); }
+    pub struct Param;
+}
+struct Param;
+struct S;
+impl foo::Foo<Param> for S { <|> }",
+            "
+mod foo {
+    trait Foo<T> { fn foo(&self, bar: T); }
+    pub struct Param;
+}
+struct Param;
+struct S;
+impl foo::Foo<Param> for S {
+    <|>fn foo(&self, bar: Param) { unimplemented!() }
+}",
+        );
+    }
+
+    #[test]
+    fn test_qualify_path_associated_item() {
+        check_assist(
+            add_missing_impl_members,
+            "
+mod foo {
+    pub struct Bar<T>;
+    impl Bar<T> { type Assoc = u32; }
+    trait Foo { fn foo(&self, bar: Bar<u32>::Assoc); }
+}
+struct S;
+impl foo::Foo for S { <|> }",
+            "
+mod foo {
+    pub struct Bar<T>;
+    impl Bar<T> { type Assoc = u32; }
+    trait Foo { fn foo(&self, bar: Bar<u32>::Assoc); }
+}
+struct S;
+impl foo::Foo for S {
+    <|>fn foo(&self, bar: foo::Bar<u32>::Assoc) { unimplemented!() }
+}",
+        );
+    }
+
+    #[test]
+    fn test_qualify_path_nested() {
+        check_assist(
+            add_missing_impl_members,
+            "
+mod foo {
+    pub struct Bar<T>;
+    pub struct Baz;
+    trait Foo { fn foo(&self, bar: Bar<Baz>); }
+}
+struct S;
+impl foo::Foo for S { <|> }",
+            "
+mod foo {
+    pub struct Bar<T>;
+    pub struct Baz;
+    trait Foo { fn foo(&self, bar: Bar<Baz>); }
+}
+struct S;
+impl foo::Foo for S {
+    <|>fn foo(&self, bar: foo::Bar<foo::Baz>) { unimplemented!() }
+}",
+        );
+    }
+
+    #[test]
+    fn test_qualify_path_fn_trait_notation() {
+        check_assist(
+            add_missing_impl_members,
+            "
+mod foo {
+    pub trait Fn<Args> { type Output; }
+    trait Foo { fn foo(&self, bar: dyn Fn(u32) -> i32); }
+}
+struct S;
+impl foo::Foo for S { <|> }",
+            "
+mod foo {
+    pub trait Fn<Args> { type Output; }
+    trait Foo { fn foo(&self, bar: dyn Fn(u32) -> i32); }
+}
+struct S;
+impl foo::Foo for S {
+    <|>fn foo(&self, bar: dyn Fn(u32) -> i32) { unimplemented!() }
+}",
+        );
+    }
+
+    #[test]
     fn test_empty_trait() {
         check_assist_not_applicable(
             add_missing_impl_members,
diff --git a/crates/ra_assists/src/ast_transform.rs b/crates/ra_assists/src/ast_transform.rs
new file mode 100644
index 000000000..cbddc50ac
--- /dev/null
+++ b/crates/ra_assists/src/ast_transform.rs
@@ -0,0 +1,179 @@
+//! `AstTransformer`s are functions that replace nodes in an AST and can be easily combined.
+use rustc_hash::FxHashMap;
+
+use hir::{db::HirDatabase, InFile, PathResolution};
+use ra_syntax::ast::{self, make, AstNode};
+
+pub trait AstTransform<'a> {
+    fn get_substitution(
+        &self,
+        node: InFile<&ra_syntax::SyntaxNode>,
+    ) -> Option<ra_syntax::SyntaxNode>;
+
+    fn chain_before(self, other: Box<dyn AstTransform<'a> + 'a>) -> Box<dyn AstTransform<'a> + 'a>;
+    fn or<T: AstTransform<'a> + 'a>(self, other: T) -> Box<dyn AstTransform<'a> + 'a>
+    where
+        Self: Sized + 'a,
+    {
+        self.chain_before(Box::new(other))
+    }
+}
+
+struct NullTransformer;
+
+impl<'a> AstTransform<'a> for NullTransformer {
+    fn get_substitution(
+        &self,
+        _node: InFile<&ra_syntax::SyntaxNode>,
+    ) -> Option<ra_syntax::SyntaxNode> {
+        None
+    }
+    fn chain_before(self, other: Box<dyn AstTransform<'a> + 'a>) -> Box<dyn AstTransform<'a> + 'a> {
+        other
+    }
+}
+
+pub struct SubstituteTypeParams<'a, DB: HirDatabase> {
+    db: &'a DB,
+    substs: FxHashMap<hir::TypeParam, ast::TypeRef>,
+    previous: Box<dyn AstTransform<'a> + 'a>,
+}
+
+impl<'a, DB: HirDatabase> SubstituteTypeParams<'a, DB> {
+    pub fn for_trait_impl(
+        db: &'a DB,
+        trait_: hir::Trait,
+        impl_block: ast::ImplBlock,
+    ) -> SubstituteTypeParams<'a, DB> {
+        let substs = get_syntactic_substs(impl_block).unwrap_or_default();
+        let generic_def: hir::GenericDef = trait_.into();
+        let substs_by_param: FxHashMap<_, _> = generic_def
+            .params(db)
+            .into_iter()
+            // this is a trait impl, so we need to skip the first type parameter -- this is a bit hacky
+            .skip(1)
+            .zip(substs.into_iter())
+            .collect();
+        return SubstituteTypeParams {
+            db,
+            substs: substs_by_param,
+            previous: Box::new(NullTransformer),
+        };
+
+        // FIXME: It would probably be nicer if we could get this via HIR (i.e. get the
+        // trait ref, and then go from the types in the substs back to the syntax)
+        fn get_syntactic_substs(impl_block: ast::ImplBlock) -> Option<Vec<ast::TypeRef>> {
+            let target_trait = impl_block.target_trait()?;
+            let path_type = match target_trait {
+                ast::TypeRef::PathType(path) => path,
+                _ => return None,
+            };
+            let type_arg_list = path_type.path()?.segment()?.type_arg_list()?;
+            let mut result = Vec::new();
+            for type_arg in type_arg_list.type_args() {
+                let type_arg: ast::TypeArg = type_arg;
+                result.push(type_arg.type_ref()?);
+            }
+            Some(result)
+        }
+    }
+    fn get_substitution_inner(
+        &self,
+        node: InFile<&ra_syntax::SyntaxNode>,
+    ) -> Option<ra_syntax::SyntaxNode> {
+        let type_ref = ast::TypeRef::cast(node.value.clone())?;
+        let path = match &type_ref {
+            ast::TypeRef::PathType(path_type) => path_type.path()?,
+            _ => return None,
+        };
+        let analyzer = hir::SourceAnalyzer::new(self.db, node, None);
+        let resolution = analyzer.resolve_path(self.db, &path)?;
+        match resolution {
+            hir::PathResolution::TypeParam(tp) => Some(self.substs.get(&tp)?.syntax().clone()),
+            _ => None,
+        }
+    }
+}
+
+impl<'a, DB: HirDatabase> AstTransform<'a> for SubstituteTypeParams<'a, DB> {
+    fn get_substitution(
+        &self,
+        node: InFile<&ra_syntax::SyntaxNode>,
+    ) -> Option<ra_syntax::SyntaxNode> {
+        self.get_substitution_inner(node).or_else(|| self.previous.get_substitution(node))
+    }
+    fn chain_before(self, other: Box<dyn AstTransform<'a> + 'a>) -> Box<dyn AstTransform<'a> + 'a> {
+        Box::new(SubstituteTypeParams { previous: other, ..self })
+    }
+}
+
+pub struct QualifyPaths<'a, DB: HirDatabase> {
+    db: &'a DB,
+    from: Option<hir::Module>,
+    previous: Box<dyn AstTransform<'a> + 'a>,
+}
+
+impl<'a, DB: HirDatabase> QualifyPaths<'a, DB> {
+    pub fn new(db: &'a DB, from: Option<hir::Module>) -> Self {
+        Self { db, from, previous: Box::new(NullTransformer) }
+    }
+
+    fn get_substitution_inner(
+        &self,
+        node: InFile<&ra_syntax::SyntaxNode>,
+    ) -> Option<ra_syntax::SyntaxNode> {
+        // FIXME handle value ns?
+        let from = self.from?;
+        let p = ast::Path::cast(node.value.clone())?;
+        if p.segment().and_then(|s| s.param_list()).is_some() {
+            // don't try to qualify `Fn(Foo) -> Bar` paths, they are in prelude anyway
+            return None;
+        }
+        let analyzer = hir::SourceAnalyzer::new(self.db, node, None);
+        let resolution = analyzer.resolve_path(self.db, &p)?;
+        match resolution {
+            PathResolution::Def(def) => {
+                let found_path = from.find_use_path(self.db, def)?;
+                let args = p
+                    .segment()
+                    .and_then(|s| s.type_arg_list())
+                    .map(|arg_list| apply(self, node.with_value(arg_list)));
+                Some(make::path_with_type_arg_list(path_to_ast(found_path), args).syntax().clone())
+            }
+            PathResolution::Local(_)
+            | PathResolution::TypeParam(_)
+            | PathResolution::SelfType(_) => None,
+            PathResolution::Macro(_) => None,
+            PathResolution::AssocItem(_) => None,
+        }
+    }
+}
+
+pub fn apply<'a, N: AstNode>(transformer: &dyn AstTransform<'a>, node: InFile<N>) -> N {
+    let syntax = node.value.syntax();
+    let result = ra_syntax::algo::replace_descendants(syntax, &|element| match element {
+        ra_syntax::SyntaxElement::Node(n) => {
+            let replacement = transformer.get_substitution(node.with_value(&n))?;
+            Some(replacement.into())
+        }
+        _ => None,
+    });
+    N::cast(result).unwrap()
+}
+
+impl<'a, DB: HirDatabase> AstTransform<'a> for QualifyPaths<'a, DB> {
+    fn get_substitution(
+        &self,
+        node: InFile<&ra_syntax::SyntaxNode>,
+    ) -> Option<ra_syntax::SyntaxNode> {
+        self.get_substitution_inner(node).or_else(|| self.previous.get_substitution(node))
+    }
+    fn chain_before(self, other: Box<dyn AstTransform<'a> + 'a>) -> Box<dyn AstTransform<'a> + 'a> {
+        Box::new(QualifyPaths { previous: other, ..self })
+    }
+}
+
+fn path_to_ast(path: hir::ModPath) -> ast::Path {
+    let parse = ast::SourceFile::parse(&path.to_string());
+    parse.tree().syntax().descendants().find_map(ast::Path::cast).unwrap()
+}
diff --git a/crates/ra_assists/src/lib.rs b/crates/ra_assists/src/lib.rs
index 98fb20b22..712ff6f6a 100644
--- a/crates/ra_assists/src/lib.rs
+++ b/crates/ra_assists/src/lib.rs
@@ -11,6 +11,7 @@ mod marks;
 mod doc_tests;
 #[cfg(test)]
 mod test_db;
+pub mod ast_transform;
 
 use hir::db::HirDatabase;
 use ra_db::FileRange;