Fix ordering problem between qualifying paths and substituting params

7 files changed, 206 insertions, 126 deletions

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 942b34dc1..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 {
@@ -146,24 +147,11 @@ fn add_missing_impl_members_inner(
             None,
         )
         .module();
-        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 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(trait_file_id, it), &substs_by_param)
-            })
-            .map(|it| match module {
-                Some(module) => qualify_paths(db, hir::InFile::new(trait_file_id, it), module),
-                None => it,
-            })
+            .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,
@@ -188,99 +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 + Clone>(
-    db: &impl HirDatabase,
-    node: hir::InFile<N>,
-    substs: &HashMap<hir::TypeParam, ast::TypeRef>,
-) -> N {
-    let type_param_replacements = node
-        .clone()
-        .descendants::<ast::TypeRef>()
-        .filter_map(|n| {
-            let path = match &n.value {
-                ast::TypeRef::PathType(path_type) => path_type.path()?,
-                _ => return None,
-            };
-            let analyzer = hir::SourceAnalyzer::new(db, n.syntax(), None);
-            let resolution = analyzer.resolve_path(db, &path)?;
-            match resolution {
-                hir::PathResolution::TypeParam(tp) => Some((n.value, 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())
-    }
-}
-
-use hir::PathResolution;
-
-// FIXME extract this to a general utility as well
-// FIXME handle value ns?
-// FIXME this doesn't 'commute' with `substitute_type_params`, since type params in newly generated type arg lists don't resolve. Currently we can avoid this problem, but it's worth thinking about a solution
-fn qualify_paths<N: AstNode>(db: &impl HirDatabase, node: hir::InFile<N>, from: hir::Module) -> N {
-    let path_replacements = node
-        .value
-        .syntax()
-        .descendants()
-        .filter_map(ast::Path::cast)
-        .filter_map(|p| {
-            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;
-            }
-            // FIXME check if some ancestor is already being replaced, if so skip this
-            let analyzer = hir::SourceAnalyzer::new(db, node.with_value(p.syntax()), None);
-            let resolution = analyzer.resolve_path(db, &p)?;
-            match resolution {
-                PathResolution::Def(def) => {
-                    let found_path = from.find_path(db, def)?;
-                    // TODO fix type arg replacements being qualified
-                    let args = p
-                        .segment()
-                        .and_then(|s| s.type_arg_list())
-                        .map(|arg_list| qualify_paths(db, node.with_value(arg_list), from));
-                    Some((p, make::path_with_type_arg_list(found_path.to_ast(), args)))
-                }
-                PathResolution::Local(_)
-                | PathResolution::TypeParam(_)
-                | PathResolution::SelfType(_) => None,
-                PathResolution::Macro(_) => None,
-                PathResolution::AssocItem(_) => None,
-            }
-        })
-        .collect::<Vec<_>>();
-
-    if path_replacements.is_empty() {
-        node.value
-    } else {
-        edit::replace_descendants(&node.value, path_replacements.into_iter())
-    }
-}
-
 /// Given an `ast::ImplBlock`, resolves the target trait (the one being
 /// implemented) to a `ast::TraitDef`.
 fn resolve_target_trait_def(
diff --git a/crates/ra_assists/src/ast_transform.rs b/crates/ra_assists/src/ast_transform.rs
new file mode 100644
index 000000000..846661587
--- /dev/null
+++ b/crates/ra_assists/src/ast_transform.rs
@@ -0,0 +1,178 @@
+//! `AstTransformer`s are functions that replace nodes in an AST and can be easily combined.
+use std::collections::HashMap;
+
+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: HashMap<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: 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();
+        return SubstituteTypeParams {
+            db,
+            substs: substs_by_param,
+            previous: Box::new(NullTransformer),
+        };
+
+        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_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(found_path.to_ast(), 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 })
+    }
+}
+
+// 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)
+
+// FIXME: This should be a general utility (not even just for assists)
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;
diff --git a/crates/ra_ide/src/expand_macro.rs b/crates/ra_ide/src/expand_macro.rs
index bdbc31704..0f7b6e875 100644
--- a/crates/ra_ide/src/expand_macro.rs
+++ b/crates/ra_ide/src/expand_macro.rs
@@ -7,8 +7,7 @@ use rustc_hash::FxHashMap;
 
 use ra_syntax::{
     algo::{find_node_at_offset, replace_descendants},
-    ast::{self},
-    AstNode, NodeOrToken, SyntaxKind, SyntaxNode, WalkEvent, T,
+    ast, AstNode, NodeOrToken, SyntaxElement, SyntaxKind, SyntaxNode, WalkEvent, T,
 };
 
 pub struct ExpandedMacro {
@@ -43,7 +42,7 @@ fn expand_macro_recur(
     let mut expanded: SyntaxNode = db.parse_or_expand(macro_file_id)?;
 
     let children = expanded.descendants().filter_map(ast::MacroCall::cast);
-    let mut replaces = FxHashMap::default();
+    let mut replaces: FxHashMap<SyntaxElement, SyntaxElement> = FxHashMap::default();
 
     for child in children.into_iter() {
         let node = hir::InFile::new(macro_file_id, &child);
@@ -59,7 +58,7 @@ fn expand_macro_recur(
         }
     }
 
-    Some(replace_descendants(&expanded, &replaces))
+    Some(replace_descendants(&expanded, &|n| replaces.get(n).cloned()))
 }
 
 // FIXME: It would also be cool to share logic here and in the mbe tests,
diff --git a/crates/ra_syntax/src/algo.rs b/crates/ra_syntax/src/algo.rs
index 2b2b295f9..30a479f01 100644
--- a/crates/ra_syntax/src/algo.rs
+++ b/crates/ra_syntax/src/algo.rs
@@ -184,17 +184,17 @@ pub fn replace_children(
 /// to create a type-safe abstraction on top of it instead.
 pub fn replace_descendants(
     parent: &SyntaxNode,
-    map: &FxHashMap<SyntaxElement, SyntaxElement>,
+    map: &impl Fn(&SyntaxElement) -> Option<SyntaxElement>,
 ) -> SyntaxNode {
     //  FIXME: this could be made much faster.
     let new_children = parent.children_with_tokens().map(|it| go(map, it)).collect::<Vec<_>>();
     return with_children(parent, new_children);
 
     fn go(
-        map: &FxHashMap<SyntaxElement, SyntaxElement>,
+        map: &impl Fn(&SyntaxElement) -> Option<SyntaxElement>,
         element: SyntaxElement,
     ) -> NodeOrToken<rowan::GreenNode, rowan::GreenToken> {
-        if let Some(replacement) = map.get(&element) {
+        if let Some(replacement) = map(&element) {
             return match replacement {
                 NodeOrToken::Node(it) => NodeOrToken::Node(it.green().clone()),
                 NodeOrToken::Token(it) => NodeOrToken::Token(it.green().clone()),
diff --git a/crates/ra_syntax/src/ast/edit.rs b/crates/ra_syntax/src/ast/edit.rs
index ae5d63927..b736098ac 100644
--- a/crates/ra_syntax/src/ast/edit.rs
+++ b/crates/ra_syntax/src/ast/edit.rs
@@ -236,8 +236,8 @@ pub fn replace_descendants<N: AstNode, D: AstNode>(
 ) -> N {
     let map = replacement_map
         .map(|(from, to)| (from.syntax().clone().into(), to.syntax().clone().into()))
-        .collect::<FxHashMap<_, _>>();
-    let new_syntax = algo::replace_descendants(parent.syntax(), &map);
+        .collect::<FxHashMap<SyntaxElement, _>>();
+    let new_syntax = algo::replace_descendants(parent.syntax(), &|n| map.get(n).cloned());
     N::cast(new_syntax).unwrap()
 }
 
@@ -292,7 +292,7 @@ impl IndentLevel {
                 )
             })
             .collect();
-        algo::replace_descendants(&node, &replacements)
+        algo::replace_descendants(&node, &|n| replacements.get(n).cloned())
     }
 
     pub fn decrease_indent<N: AstNode>(self, node: N) -> N {
@@ -320,7 +320,7 @@ impl IndentLevel {
                 )
             })
             .collect();
-        algo::replace_descendants(&node, &replacements)
+        algo::replace_descendants(&node, &|n| replacements.get(n).cloned())
     }
 }
 
diff --git a/crates/ra_syntax/src/ast/make.rs b/crates/ra_syntax/src/ast/make.rs
index 68d64a0cc..9781b748f 100644
--- a/crates/ra_syntax/src/ast/make.rs
+++ b/crates/ra_syntax/src/ast/make.rs
@@ -2,7 +2,7 @@
 //! of smaller pieces.
 use itertools::Itertools;
 
-use crate::{ast, AstNode, SourceFile};
+use crate::{algo, ast, AstNode, SourceFile};
 
 pub fn name(text: &str) -> ast::Name {
     ast_from_text(&format!("mod {};", text))
@@ -23,7 +23,14 @@ fn path_from_text(text: &str) -> ast::Path {
 }
 pub fn path_with_type_arg_list(path: ast::Path, args: Option<ast::TypeArgList>) -> ast::Path {
     if let Some(args) = args {
-        ast_from_text(&format!("const X: {}{}", path.syntax(), args.syntax()))
+        let syntax = path.syntax();
+        // FIXME: remove existing type args
+        let new_syntax = algo::insert_children(
+            syntax,
+            crate::algo::InsertPosition::Last,
+            &mut Some(args).into_iter().map(|n| n.syntax().clone().into()),
+        );
+        ast::Path::cast(new_syntax).unwrap()
     } else {
         path
     }