From 2b53639e381b1f17c829fb33f6e4135a9c930f41 Mon Sep 17 00:00:00 2001
From: David Lattimore <dml@google.com>
Date: Tue, 21 Jul 2020 21:32:09 +1000
Subject: SSR: Use expect! in tests

---
 crates/ra_ssr/src/tests.rs | 71 ++++++++++++++++++++++------------------------
 1 file changed, 34 insertions(+), 37 deletions(-)

(limited to 'crates/ra_ssr/src')

diff --git a/crates/ra_ssr/src/tests.rs b/crates/ra_ssr/src/tests.rs
index f20ae2cdf..9f5306592 100644
--- a/crates/ra_ssr/src/tests.rs
+++ b/crates/ra_ssr/src/tests.rs
@@ -1,4 +1,5 @@
 use crate::{MatchFinder, SsrRule};
+use expect::{expect, Expect};
 use ra_db::{FileId, SourceDatabaseExt};
 use test_utils::mark;
 
@@ -61,16 +62,11 @@ fn single_file(code: &str) -> (ra_ide_db::RootDatabase, FileId) {
     ra_ide_db::RootDatabase::with_single_file(code)
 }
 
-fn assert_ssr_transform(rule: &str, input: &str, result: &str) {
-    assert_ssr_transforms(&[rule], input, result);
+fn assert_ssr_transform(rule: &str, input: &str, expected: Expect) {
+    assert_ssr_transforms(&[rule], input, expected);
 }
 
-fn normalize_code(code: &str) -> String {
-    let (db, file_id) = single_file(code);
-    db.file_text(file_id).to_string()
-}
-
-fn assert_ssr_transforms(rules: &[&str], input: &str, result: &str) {
+fn assert_ssr_transforms(rules: &[&str], input: &str, expected: Expect) {
     let (db, file_id) = single_file(input);
     let mut match_finder = MatchFinder::new(&db);
     for rule in rules {
@@ -80,12 +76,9 @@ fn assert_ssr_transforms(rules: &[&str], input: &str, result: &str) {
     if let Some(edits) = match_finder.edits_for_file(file_id) {
         // Note, db.file_text is not necessarily the same as `input`, since fixture parsing alters
         // stuff.
-        let mut after = db.file_text(file_id).to_string();
-        edits.apply(&mut after);
-        // Likewise, we need to make sure that whatever transformations fixture parsing applies,
-        // also get applied to our expected result.
-        let result = normalize_code(result);
-        assert_eq!(after, result);
+        let mut actual = db.file_text(file_id).to_string();
+        edits.apply(&mut actual);
+        expected.assert_eq(&actual);
     } else {
         panic!("No edits were made");
     }
@@ -149,7 +142,7 @@ fn ssr_function_to_method() {
     assert_ssr_transform(
         "my_function($a, $b) ==>> ($a).my_method($b)",
         "fn my_function() {} fn main() { loop { my_function( other_func(x, y), z + w) } }",
-        "fn my_function() {} fn main() { loop { (other_func(x, y)).my_method(z + w) } }",
+        expect![["fn my_function() {} fn main() { loop { (other_func(x, y)).my_method(z + w) } }"]],
     )
 }
 
@@ -158,7 +151,7 @@ fn ssr_nested_function() {
     assert_ssr_transform(
         "foo($a, $b, $c) ==>> bar($c, baz($a, $b))",
         "fn foo() {} fn main { foo  (x + value.method(b), x+y-z, true && false) }",
-        "fn foo() {} fn main { bar(true && false, baz(x + value.method(b), x+y-z)) }",
+        expect![["fn foo() {} fn main { bar(true && false, baz(x + value.method(b), x+y-z)) }"]],
     )
 }
 
@@ -167,7 +160,7 @@ fn ssr_expected_spacing() {
     assert_ssr_transform(
         "foo($x) + bar() ==>> bar($x)",
         "fn foo() {} fn bar() {} fn main() { foo(5) + bar() }",
-        "fn foo() {} fn bar() {} fn main() { bar(5) }",
+        expect![["fn foo() {} fn bar() {} fn main() { bar(5) }"]],
     );
 }
 
@@ -176,7 +169,7 @@ fn ssr_with_extra_space() {
     assert_ssr_transform(
         "foo($x  ) +    bar() ==>> bar($x)",
         "fn foo() {} fn bar() {} fn main() { foo(  5 )  +bar(   ) }",
-        "fn foo() {} fn bar() {} fn main() { bar(5) }",
+        expect![["fn foo() {} fn bar() {} fn main() { bar(5) }"]],
     );
 }
 
@@ -185,7 +178,7 @@ fn ssr_keeps_nested_comment() {
     assert_ssr_transform(
         "foo($x) ==>> bar($x)",
         "fn foo() {} fn main() { foo(other(5 /* using 5 */)) }",
-        "fn foo() {} fn main() { bar(other(5 /* using 5 */)) }",
+        expect![["fn foo() {} fn main() { bar(other(5 /* using 5 */)) }"]],
     )
 }
 
@@ -194,7 +187,7 @@ fn ssr_keeps_comment() {
     assert_ssr_transform(
         "foo($x) ==>> bar($x)",
         "fn foo() {} fn main() { foo(5 /* using 5 */) }",
-        "fn foo() {} fn main() { bar(5)/* using 5 */ }",
+        expect![["fn foo() {} fn main() { bar(5)/* using 5 */ }"]],
     )
 }
 
@@ -203,7 +196,7 @@ fn ssr_struct_lit() {
     assert_ssr_transform(
         "foo{a: $a, b: $b} ==>> foo::new($a, $b)",
         "fn foo() {} fn main() { foo{b:2, a:1} }",
-        "fn foo() {} fn main() { foo::new(1, 2) }",
+        expect![["fn foo() {} fn main() { foo::new(1, 2) }"]],
     )
 }
 
@@ -417,7 +410,7 @@ fn replace_function_call() {
     assert_ssr_transform(
         "foo() ==>> bar()",
         "fn foo() {} fn f1() {foo(); foo();}",
-        "fn foo() {} fn f1() {bar(); bar();}",
+        expect![["fn foo() {} fn f1() {bar(); bar();}"]],
     );
 }
 
@@ -426,7 +419,7 @@ fn replace_function_call_with_placeholders() {
     assert_ssr_transform(
         "foo($a, $b) ==>> bar($b, $a)",
         "fn foo() {} fn f1() {foo(5, 42)}",
-        "fn foo() {} fn f1() {bar(42, 5)}",
+        expect![["fn foo() {} fn f1() {bar(42, 5)}"]],
     );
 }
 
@@ -435,7 +428,7 @@ fn replace_nested_function_calls() {
     assert_ssr_transform(
         "foo($a) ==>> bar($a)",
         "fn foo() {} fn f1() {foo(foo(42))}",
-        "fn foo() {} fn f1() {bar(bar(42))}",
+        expect![["fn foo() {} fn f1() {bar(bar(42))}"]],
     );
 }
 
@@ -444,7 +437,7 @@ fn replace_type() {
     assert_ssr_transform(
         "Result<(), $a> ==>> Option<$a>",
         "struct Result<T, E> {} fn f1() -> Result<(), Vec<Error>> {foo()}",
-        "struct Result<T, E> {} fn f1() -> Option<Vec<Error>> {foo()}",
+        expect![["struct Result<T, E> {} fn f1() -> Option<Vec<Error>> {foo()}"]],
     );
 }
 
@@ -453,7 +446,7 @@ fn replace_struct_init() {
     assert_ssr_transform(
         "Foo {a: $a, b: $b} ==>> Foo::new($a, $b)",
         "struct Foo {} fn f1() {Foo{b: 1, a: 2}}",
-        "struct Foo {} fn f1() {Foo::new(2, 1)}",
+        expect![["struct Foo {} fn f1() {Foo::new(2, 1)}"]],
     );
 }
 
@@ -462,12 +455,12 @@ fn replace_macro_invocations() {
     assert_ssr_transform(
         "try!($a) ==>> $a?",
         "macro_rules! try {() => {}} fn f1() -> Result<(), E> {bar(try!(foo()));}",
-        "macro_rules! try {() => {}} fn f1() -> Result<(), E> {bar(foo()?);}",
+        expect![["macro_rules! try {() => {}} fn f1() -> Result<(), E> {bar(foo()?);}"]],
     );
     assert_ssr_transform(
         "foo!($a($b)) ==>> foo($b, $a)",
         "macro_rules! foo {() => {}} fn f1() {foo!(abc(def() + 2));}",
-        "macro_rules! foo {() => {}} fn f1() {foo(def() + 2, abc);}",
+        expect![["macro_rules! foo {() => {}} fn f1() {foo(def() + 2, abc);}"]],
     );
 }
 
@@ -476,12 +469,12 @@ fn replace_binary_op() {
     assert_ssr_transform(
         "$a + $b ==>> $b + $a",
         "fn f() {2 * 3 + 4 * 5}",
-        "fn f() {4 * 5 + 2 * 3}",
+        expect![["fn f() {4 * 5 + 2 * 3}"]],
     );
     assert_ssr_transform(
         "$a + $b ==>> $b + $a",
         "fn f() {1 + 2 + 3 + 4}",
-        "fn f() {4 + 3 + 2 + 1}",
+        expect![["fn f() {4 + 3 + 2 + 1}"]],
     );
 }
 
@@ -495,7 +488,7 @@ fn multiple_rules() {
     assert_ssr_transforms(
         &["$a + 1 ==>> add_one($a)", "$a + $b ==>> add($a, $b)"],
         "fn f() -> i32 {3 + 2 + 1}",
-        "fn f() -> i32 {add_one(add(3, 2))}",
+        expect![["fn f() -> i32 {add_one(add(3, 2))}"]],
     )
 }
 
@@ -527,12 +520,14 @@ fn replace_within_macro_expansion() {
             macro_rules! macro1 {
                 ($a:expr) => {$a}
             }
-            fn f() {macro1!(5.x().foo().o2())}"#,
-        r#"
+            fn f() {macro1!(5.x().foo().o2())}
+            "#,
+        expect![[r#"
             macro_rules! macro1 {
                 ($a:expr) => {$a}
             }
-            fn f() {macro1!(bar(5.x()).o2())}"#,
+            fn f() {macro1!(bar(5.x()).o2())}
+            "#]],
     )
 }
 
@@ -544,12 +539,14 @@ fn preserves_whitespace_within_macro_expansion() {
             macro_rules! macro1 {
                 ($a:expr) => {$a}
             }
-            fn f() {macro1!(1   *   2 + 3 + 4}"#,
-        r#"
+            fn f() {macro1!(1   *   2 + 3 + 4}
+            "#,
+        expect![[r#"
             macro_rules! macro1 {
                 ($a:expr) => {$a}
             }
-            fn f() {macro1!(4 - 3 - 1   *   2}"#,
+            fn f() {macro1!(4 - 3 - 1   *   2}
+            "#]],
     )
 }
 
-- 
cgit v1.2.3


From 1fce8b6ba32bebba36d588d07781e9e578845728 Mon Sep 17 00:00:00 2001
From: David Lattimore <dml@google.com>
Date: Fri, 3 Jul 2020 12:57:17 +1000
Subject: SSR: Change the way rules are stored internally.

Previously we had:

- Multiple rules
  - Each rule had its pattern parsed as an expression, path etc

This meant that there were two levels at which there could be multiple
rules.

Now we just have multiple rules. If a pattern can parse as more than one
kind of thing, then they get stored as multiple separate rules.

We also now don't have separate fields for the different kinds of things
that a pattern can parse as. This makes adding new kinds of things
simpler.

Previously, add_search_pattern would construct a rule with a dummy
replacement. Now the replacement is an Option. This is slightly cleaner
and also opens the way for parsing the replacement template as the same
kind of thing as the search pattern.
---
 crates/ra_ssr/src/lib.rs       |  76 +++++++++++++----------------
 crates/ra_ssr/src/matching.rs  |  42 ++++------------
 crates/ra_ssr/src/parsing.rs   | 106 +++++++++++++++++++++++++++++------------
 crates/ra_ssr/src/replacing.rs |   6 ++-
 4 files changed, 123 insertions(+), 107 deletions(-)

(limited to 'crates/ra_ssr/src')

diff --git a/crates/ra_ssr/src/lib.rs b/crates/ra_ssr/src/lib.rs
index cca4576ce..3009dcb93 100644
--- a/crates/ra_ssr/src/lib.rs
+++ b/crates/ra_ssr/src/lib.rs
@@ -13,35 +13,27 @@ mod tests;
 
 pub use crate::errors::SsrError;
 pub use crate::matching::Match;
-use crate::matching::{record_match_fails_reasons_scope, MatchFailureReason};
+use crate::matching::MatchFailureReason;
 use hir::Semantics;
+use parsing::SsrTemplate;
 use ra_db::{FileId, FileRange};
-use ra_syntax::{ast, AstNode, SmolStr, SyntaxKind, SyntaxNode, TextRange};
+use ra_syntax::{ast, AstNode, SyntaxNode, TextRange};
 use ra_text_edit::TextEdit;
-use rustc_hash::FxHashMap;
 
 // A structured search replace rule. Create by calling `parse` on a str.
 #[derive(Debug)]
 pub struct SsrRule {
     /// A structured pattern that we're searching for.
-    pattern: SsrPattern,
+    pattern: parsing::RawPattern,
     /// What we'll replace it with.
-    template: parsing::SsrTemplate,
+    template: SsrTemplate,
+    parsed_rules: Vec<parsing::ParsedRule>,
 }
 
 #[derive(Debug)]
 pub struct SsrPattern {
-    raw: parsing::RawSearchPattern,
-    /// Placeholders keyed by the stand-in ident that we use in Rust source code.
-    placeholders_by_stand_in: FxHashMap<SmolStr, parsing::Placeholder>,
-    // We store our search pattern, parsed as each different kind of thing we can look for. As we
-    // traverse the AST, we get the appropriate one of these for the type of node we're on. For many
-    // search patterns, only some of these will be present.
-    expr: Option<SyntaxNode>,
-    type_ref: Option<SyntaxNode>,
-    item: Option<SyntaxNode>,
-    path: Option<SyntaxNode>,
-    pattern: Option<SyntaxNode>,
+    raw: parsing::RawPattern,
+    parsed_rules: Vec<parsing::ParsedRule>,
 }
 
 #[derive(Debug, Default)]
@@ -53,7 +45,7 @@ pub struct SsrMatches {
 pub struct MatchFinder<'db> {
     /// Our source of information about the user's code.
     sema: Semantics<'db, ra_ide_db::RootDatabase>,
-    rules: Vec<SsrRule>,
+    rules: Vec<parsing::ParsedRule>,
 }
 
 impl<'db> MatchFinder<'db> {
@@ -61,14 +53,17 @@ impl<'db> MatchFinder<'db> {
         MatchFinder { sema: Semantics::new(db), rules: Vec::new() }
     }
 
+    /// Adds a rule to be applied. The order in which rules are added matters. Earlier rules take
+    /// precedence. If a node is matched by an earlier rule, then later rules won't be permitted to
+    /// match to it.
     pub fn add_rule(&mut self, rule: SsrRule) {
-        self.rules.push(rule);
+        self.add_parsed_rules(rule.parsed_rules);
     }
 
     /// Adds a search pattern. For use if you intend to only call `find_matches_in_file`. If you
     /// intend to do replacement, use `add_rule` instead.
     pub fn add_search_pattern(&mut self, pattern: SsrPattern) {
-        self.add_rule(SsrRule { pattern, template: "()".parse().unwrap() })
+        self.add_parsed_rules(pattern.parsed_rules);
     }
 
     pub fn edits_for_file(&self, file_id: FileId) -> Option<TextEdit> {
@@ -115,6 +110,14 @@ impl<'db> MatchFinder<'db> {
         res
     }
 
+    fn add_parsed_rules(&mut self, parsed_rules: Vec<parsing::ParsedRule>) {
+        // FIXME: This doesn't need to be a for loop, but does in a subsequent commit. Justify it
+        // being a for-loop.
+        for parsed_rule in parsed_rules {
+            self.rules.push(parsed_rule);
+        }
+    }
+
     fn find_matches(
         &self,
         code: &SyntaxNode,
@@ -177,8 +180,13 @@ impl<'db> MatchFinder<'db> {
             }
             if node_range.range == range.range {
                 for rule in &self.rules {
-                    let pattern =
-                        rule.pattern.tree_for_kind_with_reason(node.kind()).map(|p| p.clone());
+                    // For now we ignore rules that have a different kind than our node, otherwise
+                    // we get lots of noise. If at some point we add support for restricting rules
+                    // to a particular kind of thing (e.g. only match type references), then we can
+                    // relax this.
+                    if rule.pattern.kind() != node.kind() {
+                        continue;
+                    }
                     out.push(MatchDebugInfo {
                         matched: matching::get_match(true, rule, &node, restrict_range, &self.sema)
                             .map_err(|e| MatchFailureReason {
@@ -186,7 +194,7 @@ impl<'db> MatchFinder<'db> {
                                     "Match failed, but no reason was given".to_owned()
                                 }),
                             }),
-                        pattern,
+                        pattern: rule.pattern.clone(),
                         node: node.clone(),
                     });
                 }
@@ -209,9 +217,8 @@ impl<'db> MatchFinder<'db> {
 
 pub struct MatchDebugInfo {
     node: SyntaxNode,
-    /// Our search pattern parsed as the same kind of syntax node as `node`. e.g. expression, item,
-    /// etc. Will be absent if the pattern can't be parsed as that kind.
-    pattern: Result<SyntaxNode, MatchFailureReason>,
+    /// Our search pattern parsed as an expression or item, etc
+    pattern: SyntaxNode,
     matched: Result<Match, MatchFailureReason>,
 }
 
@@ -228,29 +235,12 @@ impl std::fmt::Debug for MatchDebugInfo {
             self.node
         )?;
         writeln!(f, "========= PATTERN ==========")?;
-        match &self.pattern {
-            Ok(pattern) => {
-                writeln!(f, "{:#?}", pattern)?;
-            }
-            Err(err) => {
-                writeln!(f, "{}", err.reason)?;
-            }
-        }
+        writeln!(f, "{:#?}", self.pattern)?;
         writeln!(f, "============================")?;
         Ok(())
     }
 }
 
-impl SsrPattern {
-    fn tree_for_kind_with_reason(
-        &self,
-        kind: SyntaxKind,
-    ) -> Result<&SyntaxNode, MatchFailureReason> {
-        record_match_fails_reasons_scope(true, || self.tree_for_kind(kind))
-            .map_err(|e| MatchFailureReason { reason: e.reason.unwrap() })
-    }
-}
-
 impl SsrMatches {
     /// Returns `self` with any nested matches removed and made into top-level matches.
     pub fn flattened(self) -> SsrMatches {
diff --git a/crates/ra_ssr/src/matching.rs b/crates/ra_ssr/src/matching.rs
index 50b29eab2..842f4b6f3 100644
--- a/crates/ra_ssr/src/matching.rs
+++ b/crates/ra_ssr/src/matching.rs
@@ -2,8 +2,8 @@
 //! process of matching, placeholder values are recorded.
 
 use crate::{
-    parsing::{Constraint, NodeKind, Placeholder, SsrTemplate},
-    SsrMatches, SsrPattern, SsrRule,
+    parsing::{Constraint, NodeKind, ParsedRule, Placeholder, SsrTemplate},
+    SsrMatches,
 };
 use hir::Semantics;
 use ra_db::FileRange;
@@ -50,7 +50,7 @@ pub struct Match {
     pub(crate) ignored_comments: Vec<ast::Comment>,
     // A copy of the template for the rule that produced this match. We store this on the match for
     // if/when we do replacement.
-    pub(crate) template: SsrTemplate,
+    pub(crate) template: Option<SsrTemplate>,
 }
 
 /// Represents a `$var` in an SSR query.
@@ -86,7 +86,7 @@ pub(crate) struct MatchFailed {
 /// parent module, we don't populate nested matches.
 pub(crate) fn get_match(
     debug_active: bool,
-    rule: &SsrRule,
+    rule: &ParsedRule,
     code: &SyntaxNode,
     restrict_range: &Option<FileRange>,
     sema: &Semantics<ra_ide_db::RootDatabase>,
@@ -102,7 +102,7 @@ struct Matcher<'db, 'sema> {
     /// If any placeholders come from anywhere outside of this range, then the match will be
     /// rejected.
     restrict_range: Option<FileRange>,
-    rule: &'sema SsrRule,
+    rule: &'sema ParsedRule,
 }
 
 /// Which phase of matching we're currently performing. We do two phases because most attempted
@@ -117,15 +117,14 @@ enum Phase<'a> {
 
 impl<'db, 'sema> Matcher<'db, 'sema> {
     fn try_match(
-        rule: &'sema SsrRule,
+        rule: &ParsedRule,
         code: &SyntaxNode,
         restrict_range: &Option<FileRange>,
         sema: &'sema Semantics<'db, ra_ide_db::RootDatabase>,
     ) -> Result<Match, MatchFailed> {
         let match_state = Matcher { sema, restrict_range: restrict_range.clone(), rule };
-        let pattern_tree = rule.pattern.tree_for_kind(code.kind())?;
         // First pass at matching, where we check that node types and idents match.
-        match_state.attempt_match_node(&mut Phase::First, &pattern_tree, code)?;
+        match_state.attempt_match_node(&mut Phase::First, &rule.pattern, code)?;
         match_state.validate_range(&sema.original_range(code))?;
         let mut the_match = Match {
             range: sema.original_range(code),
@@ -136,7 +135,7 @@ impl<'db, 'sema> Matcher<'db, 'sema> {
         };
         // Second matching pass, where we record placeholder matches, ignored comments and maybe do
         // any other more expensive checks that we didn't want to do on the first pass.
-        match_state.attempt_match_node(&mut Phase::Second(&mut the_match), &pattern_tree, code)?;
+        match_state.attempt_match_node(&mut Phase::Second(&mut the_match), &rule.pattern, code)?;
         Ok(the_match)
     }
 
@@ -444,8 +443,7 @@ impl<'db, 'sema> Matcher<'db, 'sema> {
     }
 
     fn get_placeholder(&self, element: &SyntaxElement) -> Option<&Placeholder> {
-        only_ident(element.clone())
-            .and_then(|ident| self.rule.pattern.placeholders_by_stand_in.get(ident.text()))
+        only_ident(element.clone()).and_then(|ident| self.rule.get_placeholder(&ident))
     }
 }
 
@@ -510,28 +508,6 @@ impl PlaceholderMatch {
     }
 }
 
-impl SsrPattern {
-    pub(crate) fn tree_for_kind(&self, kind: SyntaxKind) -> Result<&SyntaxNode, MatchFailed> {
-        let (tree, kind_name) = if ast::Expr::can_cast(kind) {
-            (&self.expr, "expression")
-        } else if ast::TypeRef::can_cast(kind) {
-            (&self.type_ref, "type reference")
-        } else if ast::ModuleItem::can_cast(kind) {
-            (&self.item, "item")
-        } else if ast::Path::can_cast(kind) {
-            (&self.path, "path")
-        } else if ast::Pat::can_cast(kind) {
-            (&self.pattern, "pattern")
-        } else {
-            fail_match!("Matching nodes of kind {:?} is not supported", kind);
-        };
-        match tree {
-            Some(tree) => Ok(tree),
-            None => fail_match!("Pattern cannot be parsed as a {}", kind_name),
-        }
-    }
-}
-
 impl NodeKind {
     fn matches(&self, node: &SyntaxNode) -> Result<(), MatchFailed> {
         let ok = match self {
diff --git a/crates/ra_ssr/src/parsing.rs b/crates/ra_ssr/src/parsing.rs
index 4aee97bb2..682b7011a 100644
--- a/crates/ra_ssr/src/parsing.rs
+++ b/crates/ra_ssr/src/parsing.rs
@@ -7,17 +7,24 @@
 
 use crate::errors::bail;
 use crate::{SsrError, SsrPattern, SsrRule};
-use ra_syntax::{ast, AstNode, SmolStr, SyntaxKind, T};
+use ra_syntax::{ast, AstNode, SmolStr, SyntaxKind, SyntaxNode, SyntaxToken, T};
 use rustc_hash::{FxHashMap, FxHashSet};
 use std::str::FromStr;
 
+#[derive(Debug)]
+pub(crate) struct ParsedRule {
+    pub(crate) placeholders_by_stand_in: FxHashMap<SmolStr, Placeholder>,
+    pub(crate) pattern: SyntaxNode,
+    pub(crate) template: Option<SsrTemplate>,
+}
+
 #[derive(Clone, Debug)]
 pub(crate) struct SsrTemplate {
     pub(crate) tokens: Vec<PatternElement>,
 }
 
 #[derive(Debug)]
-pub(crate) struct RawSearchPattern {
+pub(crate) struct RawPattern {
     tokens: Vec<PatternElement>,
 }
 
@@ -54,6 +61,50 @@ pub(crate) struct Token {
     pub(crate) text: SmolStr,
 }
 
+impl ParsedRule {
+    fn new(
+        pattern: &RawPattern,
+        template: Option<&SsrTemplate>,
+    ) -> Result<Vec<ParsedRule>, SsrError> {
+        let raw_pattern = pattern.as_rust_code();
+        let mut builder = RuleBuilder {
+            placeholders_by_stand_in: pattern.placeholders_by_stand_in(),
+            rules: Vec::new(),
+        };
+        builder.try_add(ast::Expr::parse(&raw_pattern), template);
+        builder.try_add(ast::TypeRef::parse(&raw_pattern), template);
+        builder.try_add(ast::ModuleItem::parse(&raw_pattern), template);
+        builder.try_add(ast::Path::parse(&raw_pattern), template);
+        builder.try_add(ast::Pat::parse(&raw_pattern), template);
+        builder.build()
+    }
+}
+
+struct RuleBuilder {
+    placeholders_by_stand_in: FxHashMap<SmolStr, Placeholder>,
+    rules: Vec<ParsedRule>,
+}
+
+impl RuleBuilder {
+    fn try_add<T: AstNode>(&mut self, pattern: Result<T, ()>, template: Option<&SsrTemplate>) {
+        match pattern {
+            Ok(pattern) => self.rules.push(ParsedRule {
+                placeholders_by_stand_in: self.placeholders_by_stand_in.clone(),
+                pattern: pattern.syntax().clone(),
+                template: template.cloned(),
+            }),
+            _ => {}
+        }
+    }
+
+    fn build(self) -> Result<Vec<ParsedRule>, SsrError> {
+        if self.rules.is_empty() {
+            bail!("Pattern is not a valid Rust expression, type, item, path or pattern");
+        }
+        Ok(self.rules)
+    }
+}
+
 impl FromStr for SsrRule {
     type Err = SsrError;
 
@@ -68,21 +119,24 @@ impl FromStr for SsrRule {
         if it.next().is_some() {
             return Err(SsrError("More than one delimiter found".into()));
         }
-        let rule = SsrRule { pattern: pattern.parse()?, template: template.parse()? };
+        let raw_pattern = pattern.parse()?;
+        let raw_template = template.parse()?;
+        let parsed_rules = ParsedRule::new(&raw_pattern, Some(&raw_template))?;
+        let rule = SsrRule { pattern: raw_pattern, template: raw_template, parsed_rules };
         validate_rule(&rule)?;
         Ok(rule)
     }
 }
 
-impl FromStr for RawSearchPattern {
+impl FromStr for RawPattern {
     type Err = SsrError;
 
-    fn from_str(pattern_str: &str) -> Result<RawSearchPattern, SsrError> {
-        Ok(RawSearchPattern { tokens: parse_pattern(pattern_str)? })
+    fn from_str(pattern_str: &str) -> Result<RawPattern, SsrError> {
+        Ok(RawPattern { tokens: parse_pattern(pattern_str)? })
     }
 }
 
-impl RawSearchPattern {
+impl RawPattern {
     /// Returns this search pattern as Rust source code that we can feed to the Rust parser.
     fn as_rust_code(&self) -> String {
         let mut res = String::new();
@@ -95,7 +149,7 @@ impl RawSearchPattern {
         res
     }
 
-    fn placeholders_by_stand_in(&self) -> FxHashMap<SmolStr, Placeholder> {
+    pub(crate) fn placeholders_by_stand_in(&self) -> FxHashMap<SmolStr, Placeholder> {
         let mut res = FxHashMap::default();
         for t in &self.tokens {
             if let PatternElement::Placeholder(placeholder) = t {
@@ -106,30 +160,22 @@ impl RawSearchPattern {
     }
 }
 
+impl ParsedRule {
+    pub(crate) fn get_placeholder(&self, token: &SyntaxToken) -> Option<&Placeholder> {
+        if token.kind() != SyntaxKind::IDENT {
+            return None;
+        }
+        self.placeholders_by_stand_in.get(token.text())
+    }
+}
+
 impl FromStr for SsrPattern {
     type Err = SsrError;
 
     fn from_str(pattern_str: &str) -> Result<SsrPattern, SsrError> {
-        let raw: RawSearchPattern = pattern_str.parse()?;
-        let raw_str = raw.as_rust_code();
-        let res = SsrPattern {
-            expr: ast::Expr::parse(&raw_str).ok().map(|n| n.syntax().clone()),
-            type_ref: ast::TypeRef::parse(&raw_str).ok().map(|n| n.syntax().clone()),
-            item: ast::ModuleItem::parse(&raw_str).ok().map(|n| n.syntax().clone()),
-            path: ast::Path::parse(&raw_str).ok().map(|n| n.syntax().clone()),
-            pattern: ast::Pat::parse(&raw_str).ok().map(|n| n.syntax().clone()),
-            placeholders_by_stand_in: raw.placeholders_by_stand_in(),
-            raw,
-        };
-        if res.expr.is_none()
-            && res.type_ref.is_none()
-            && res.item.is_none()
-            && res.path.is_none()
-            && res.pattern.is_none()
-        {
-            bail!("Pattern is not a valid Rust expression, type, item, path or pattern");
-        }
-        Ok(res)
+        let raw_pattern = pattern_str.parse()?;
+        let parsed_rules = ParsedRule::new(&raw_pattern, None)?;
+        Ok(SsrPattern { raw: raw_pattern, parsed_rules })
     }
 }
 
@@ -173,7 +219,7 @@ fn parse_pattern(pattern_str: &str) -> Result<Vec<PatternElement>, SsrError> {
 /// pattern didn't define.
 fn validate_rule(rule: &SsrRule) -> Result<(), SsrError> {
     let mut defined_placeholders = FxHashSet::default();
-    for p in &rule.pattern.raw.tokens {
+    for p in &rule.pattern.tokens {
         if let PatternElement::Placeholder(placeholder) = p {
             defined_placeholders.insert(&placeholder.ident);
         }
@@ -316,7 +362,7 @@ mod tests {
         }
         let result: SsrRule = "foo($a, $b) ==>> bar($b, $a)".parse().unwrap();
         assert_eq!(
-            result.pattern.raw.tokens,
+            result.pattern.tokens,
             vec![
                 token(SyntaxKind::IDENT, "foo"),
                 token(T!['('], "("),
diff --git a/crates/ra_ssr/src/replacing.rs b/crates/ra_ssr/src/replacing.rs
index e43cc5167..81f8634ba 100644
--- a/crates/ra_ssr/src/replacing.rs
+++ b/crates/ra_ssr/src/replacing.rs
@@ -31,7 +31,11 @@ fn matches_to_edit_at_offset(
 
 fn render_replace(match_info: &Match, file_src: &str) -> String {
     let mut out = String::new();
-    for r in &match_info.template.tokens {
+    let template = match_info
+        .template
+        .as_ref()
+        .expect("You called MatchFinder::edits after calling MatchFinder::add_search_pattern");
+    for r in &template.tokens {
         match r {
             PatternElement::Token(t) => out.push_str(t.text.as_str()),
             PatternElement::Placeholder(p) => {
-- 
cgit v1.2.3


From 113abbeefee671266d2d9bebdbd517eb8b802ef8 Mon Sep 17 00:00:00 2001
From: David Lattimore <dml@google.com>
Date: Wed, 22 Jul 2020 19:15:19 +1000
Subject: SSR: Parse template as Rust code.

This is in preparation for a subsequent commit where we add special
handling for paths in the template, allowing them to be qualified
differently in different contexts.
---
 crates/ra_ssr/src/lib.rs       |  14 +++---
 crates/ra_ssr/src/matching.rs  |  10 ++--
 crates/ra_ssr/src/parsing.rs   |  60 +++++++++++------------
 crates/ra_ssr/src/replacing.rs | 106 +++++++++++++++++++++++++++--------------
 crates/ra_ssr/src/tests.rs     |   4 +-
 5 files changed, 112 insertions(+), 82 deletions(-)

(limited to 'crates/ra_ssr/src')

diff --git a/crates/ra_ssr/src/lib.rs b/crates/ra_ssr/src/lib.rs
index 3009dcb93..b28913a65 100644
--- a/crates/ra_ssr/src/lib.rs
+++ b/crates/ra_ssr/src/lib.rs
@@ -15,7 +15,6 @@ pub use crate::errors::SsrError;
 pub use crate::matching::Match;
 use crate::matching::MatchFailureReason;
 use hir::Semantics;
-use parsing::SsrTemplate;
 use ra_db::{FileId, FileRange};
 use ra_syntax::{ast, AstNode, SyntaxNode, TextRange};
 use ra_text_edit::TextEdit;
@@ -26,7 +25,7 @@ pub struct SsrRule {
     /// A structured pattern that we're searching for.
     pattern: parsing::RawPattern,
     /// What we'll replace it with.
-    template: SsrTemplate,
+    template: parsing::RawPattern,
     parsed_rules: Vec<parsing::ParsedRule>,
 }
 
@@ -72,7 +71,11 @@ impl<'db> MatchFinder<'db> {
             None
         } else {
             use ra_db::SourceDatabaseExt;
-            Some(replacing::matches_to_edit(&matches, &self.sema.db.file_text(file_id)))
+            Some(replacing::matches_to_edit(
+                &matches,
+                &self.sema.db.file_text(file_id),
+                &self.rules,
+            ))
         }
     }
 
@@ -111,9 +114,8 @@ impl<'db> MatchFinder<'db> {
     }
 
     fn add_parsed_rules(&mut self, parsed_rules: Vec<parsing::ParsedRule>) {
-        // FIXME: This doesn't need to be a for loop, but does in a subsequent commit. Justify it
-        // being a for-loop.
-        for parsed_rule in parsed_rules {
+        for mut parsed_rule in parsed_rules {
+            parsed_rule.index = self.rules.len();
             self.rules.push(parsed_rule);
         }
     }
diff --git a/crates/ra_ssr/src/matching.rs b/crates/ra_ssr/src/matching.rs
index 842f4b6f3..486191635 100644
--- a/crates/ra_ssr/src/matching.rs
+++ b/crates/ra_ssr/src/matching.rs
@@ -2,7 +2,7 @@
 //! process of matching, placeholder values are recorded.
 
 use crate::{
-    parsing::{Constraint, NodeKind, ParsedRule, Placeholder, SsrTemplate},
+    parsing::{Constraint, NodeKind, ParsedRule, Placeholder},
     SsrMatches,
 };
 use hir::Semantics;
@@ -48,9 +48,7 @@ pub struct Match {
     pub(crate) matched_node: SyntaxNode,
     pub(crate) placeholder_values: FxHashMap<Var, PlaceholderMatch>,
     pub(crate) ignored_comments: Vec<ast::Comment>,
-    // A copy of the template for the rule that produced this match. We store this on the match for
-    // if/when we do replacement.
-    pub(crate) template: Option<SsrTemplate>,
+    pub(crate) rule_index: usize,
 }
 
 /// Represents a `$var` in an SSR query.
@@ -131,7 +129,7 @@ impl<'db, 'sema> Matcher<'db, 'sema> {
             matched_node: code.clone(),
             placeholder_values: FxHashMap::default(),
             ignored_comments: Vec::new(),
-            template: rule.template.clone(),
+            rule_index: rule.index,
         };
         // Second matching pass, where we record placeholder matches, ignored comments and maybe do
         // any other more expensive checks that we didn't want to do on the first pass.
@@ -591,7 +589,7 @@ mod tests {
             "1+2"
         );
 
-        let edit = crate::replacing::matches_to_edit(&matches, input);
+        let edit = crate::replacing::matches_to_edit(&matches, input, &match_finder.rules);
         let mut after = input.to_string();
         edit.apply(&mut after);
         assert_eq!(after, "fn foo() {} fn main() { bar(1+2); }");
diff --git a/crates/ra_ssr/src/parsing.rs b/crates/ra_ssr/src/parsing.rs
index 682b7011a..cf7fb517f 100644
--- a/crates/ra_ssr/src/parsing.rs
+++ b/crates/ra_ssr/src/parsing.rs
@@ -15,12 +15,8 @@ use std::str::FromStr;
 pub(crate) struct ParsedRule {
     pub(crate) placeholders_by_stand_in: FxHashMap<SmolStr, Placeholder>,
     pub(crate) pattern: SyntaxNode,
-    pub(crate) template: Option<SsrTemplate>,
-}
-
-#[derive(Clone, Debug)]
-pub(crate) struct SsrTemplate {
-    pub(crate) tokens: Vec<PatternElement>,
+    pub(crate) template: Option<SyntaxNode>,
+    pub(crate) index: usize,
 }
 
 #[derive(Debug)]
@@ -64,18 +60,23 @@ pub(crate) struct Token {
 impl ParsedRule {
     fn new(
         pattern: &RawPattern,
-        template: Option<&SsrTemplate>,
+        template: Option<&RawPattern>,
     ) -> Result<Vec<ParsedRule>, SsrError> {
         let raw_pattern = pattern.as_rust_code();
+        let raw_template = template.map(|t| t.as_rust_code());
+        let raw_template = raw_template.as_ref().map(|s| s.as_str());
         let mut builder = RuleBuilder {
             placeholders_by_stand_in: pattern.placeholders_by_stand_in(),
             rules: Vec::new(),
         };
-        builder.try_add(ast::Expr::parse(&raw_pattern), template);
-        builder.try_add(ast::TypeRef::parse(&raw_pattern), template);
-        builder.try_add(ast::ModuleItem::parse(&raw_pattern), template);
-        builder.try_add(ast::Path::parse(&raw_pattern), template);
-        builder.try_add(ast::Pat::parse(&raw_pattern), template);
+        builder.try_add(ast::Expr::parse(&raw_pattern), raw_template.map(ast::Expr::parse));
+        builder.try_add(ast::TypeRef::parse(&raw_pattern), raw_template.map(ast::TypeRef::parse));
+        builder.try_add(
+            ast::ModuleItem::parse(&raw_pattern),
+            raw_template.map(ast::ModuleItem::parse),
+        );
+        builder.try_add(ast::Path::parse(&raw_pattern), raw_template.map(ast::Path::parse));
+        builder.try_add(ast::Pat::parse(&raw_pattern), raw_template.map(ast::Pat::parse));
         builder.build()
     }
 }
@@ -86,12 +87,22 @@ struct RuleBuilder {
 }
 
 impl RuleBuilder {
-    fn try_add<T: AstNode>(&mut self, pattern: Result<T, ()>, template: Option<&SsrTemplate>) {
-        match pattern {
-            Ok(pattern) => self.rules.push(ParsedRule {
+    fn try_add<T: AstNode>(&mut self, pattern: Result<T, ()>, template: Option<Result<T, ()>>) {
+        match (pattern, template) {
+            (Ok(pattern), Some(Ok(template))) => self.rules.push(ParsedRule {
+                placeholders_by_stand_in: self.placeholders_by_stand_in.clone(),
+                pattern: pattern.syntax().clone(),
+                template: Some(template.syntax().clone()),
+                // For now we give the rule an index of 0. It's given a proper index when the rule
+                // is added to the SsrMatcher. Using an Option<usize>, instead would be slightly
+                // more correct, but we delete this field from ParsedRule in a subsequent commit.
+                index: 0,
+            }),
+            (Ok(pattern), None) => self.rules.push(ParsedRule {
                 placeholders_by_stand_in: self.placeholders_by_stand_in.clone(),
                 pattern: pattern.syntax().clone(),
-                template: template.cloned(),
+                template: None,
+                index: 0,
             }),
             _ => {}
         }
@@ -99,7 +110,7 @@ impl RuleBuilder {
 
     fn build(self) -> Result<Vec<ParsedRule>, SsrError> {
         if self.rules.is_empty() {
-            bail!("Pattern is not a valid Rust expression, type, item, path or pattern");
+            bail!("Not a valid Rust expression, type, item, path or pattern");
         }
         Ok(self.rules)
     }
@@ -179,21 +190,6 @@ impl FromStr for SsrPattern {
     }
 }
 
-impl FromStr for SsrTemplate {
-    type Err = SsrError;
-
-    fn from_str(pattern_str: &str) -> Result<SsrTemplate, SsrError> {
-        let tokens = parse_pattern(pattern_str)?;
-        // Validate that the template is a valid fragment of Rust code. We reuse the validation
-        // logic for search patterns since the only thing that differs is the error message.
-        if SsrPattern::from_str(pattern_str).is_err() {
-            bail!("Replacement is not a valid Rust expression, type, item, path or pattern");
-        }
-        // Our actual template needs to preserve whitespace, so we can't reuse `tokens`.
-        Ok(SsrTemplate { tokens })
-    }
-}
-
 /// Returns `pattern_str`, parsed as a search or replace pattern. If `remove_whitespace` is true,
 /// then any whitespace tokens will be removed, which we do for the search pattern, but not for the
 /// replace pattern.
diff --git a/crates/ra_ssr/src/replacing.rs b/crates/ra_ssr/src/replacing.rs
index 81f8634ba..f1c5bdf14 100644
--- a/crates/ra_ssr/src/replacing.rs
+++ b/crates/ra_ssr/src/replacing.rs
@@ -1,70 +1,104 @@
 //! Code for applying replacement templates for matches that have previously been found.
 
 use crate::matching::Var;
-use crate::parsing::PatternElement;
-use crate::{Match, SsrMatches};
+use crate::{parsing::ParsedRule, Match, SsrMatches};
 use ra_syntax::ast::AstToken;
-use ra_syntax::TextSize;
+use ra_syntax::{SyntaxElement, SyntaxNode, SyntaxToken, TextSize};
 use ra_text_edit::TextEdit;
 
 /// Returns a text edit that will replace each match in `matches` with its corresponding replacement
 /// template. Placeholders in the template will have been substituted with whatever they matched to
 /// in the original code.
-pub(crate) fn matches_to_edit(matches: &SsrMatches, file_src: &str) -> TextEdit {
-    matches_to_edit_at_offset(matches, file_src, 0.into())
+pub(crate) fn matches_to_edit(
+    matches: &SsrMatches,
+    file_src: &str,
+    rules: &[ParsedRule],
+) -> TextEdit {
+    matches_to_edit_at_offset(matches, file_src, 0.into(), rules)
 }
 
 fn matches_to_edit_at_offset(
     matches: &SsrMatches,
     file_src: &str,
     relative_start: TextSize,
+    rules: &[ParsedRule],
 ) -> TextEdit {
     let mut edit_builder = ra_text_edit::TextEditBuilder::default();
     for m in &matches.matches {
         edit_builder.replace(
             m.range.range.checked_sub(relative_start).unwrap(),
-            render_replace(m, file_src),
+            render_replace(m, file_src, rules),
         );
     }
     edit_builder.finish()
 }
 
-fn render_replace(match_info: &Match, file_src: &str) -> String {
+struct ReplacementRenderer<'a> {
+    match_info: &'a Match,
+    file_src: &'a str,
+    rules: &'a [ParsedRule],
+    rule: &'a ParsedRule,
+}
+
+fn render_replace(match_info: &Match, file_src: &str, rules: &[ParsedRule]) -> String {
     let mut out = String::new();
-    let template = match_info
+    let rule = &rules[match_info.rule_index];
+    let template = rule
         .template
         .as_ref()
         .expect("You called MatchFinder::edits after calling MatchFinder::add_search_pattern");
-    for r in &template.tokens {
-        match r {
-            PatternElement::Token(t) => out.push_str(t.text.as_str()),
-            PatternElement::Placeholder(p) => {
-                if let Some(placeholder_value) =
-                    match_info.placeholder_values.get(&Var(p.ident.to_string()))
-                {
-                    let range = &placeholder_value.range.range;
-                    let mut matched_text =
-                        file_src[usize::from(range.start())..usize::from(range.end())].to_owned();
-                    let edit = matches_to_edit_at_offset(
-                        &placeholder_value.inner_matches,
-                        file_src,
-                        range.start(),
-                    );
-                    edit.apply(&mut matched_text);
-                    out.push_str(&matched_text);
-                } else {
-                    // We validated that all placeholder references were valid before we
-                    // started, so this shouldn't happen.
-                    panic!(
-                        "Internal error: replacement referenced unknown placeholder {}",
-                        p.ident
-                    );
-                }
-            }
-        }
-    }
+    let renderer = ReplacementRenderer { match_info, file_src, rules, rule };
+    renderer.render_node_children(&template, &mut out);
     for comment in &match_info.ignored_comments {
         out.push_str(&comment.syntax().to_string());
     }
     out
 }
+
+impl ReplacementRenderer<'_> {
+    fn render_node_children(&self, node: &SyntaxNode, out: &mut String) {
+        for node_or_token in node.children_with_tokens() {
+            self.render_node_or_token(&node_or_token, out);
+        }
+    }
+
+    fn render_node_or_token(&self, node_or_token: &SyntaxElement, out: &mut String) {
+        match node_or_token {
+            SyntaxElement::Token(token) => {
+                self.render_token(&token, out);
+            }
+            SyntaxElement::Node(child_node) => {
+                self.render_node_children(&child_node, out);
+            }
+        }
+    }
+
+    fn render_token(&self, token: &SyntaxToken, out: &mut String) {
+        if let Some(placeholder) = self.rule.get_placeholder(&token) {
+            if let Some(placeholder_value) =
+                self.match_info.placeholder_values.get(&Var(placeholder.ident.to_string()))
+            {
+                let range = &placeholder_value.range.range;
+                let mut matched_text =
+                    self.file_src[usize::from(range.start())..usize::from(range.end())].to_owned();
+                let edit = matches_to_edit_at_offset(
+                    &placeholder_value.inner_matches,
+                    self.file_src,
+                    range.start(),
+                    self.rules,
+                );
+                edit.apply(&mut matched_text);
+                out.push_str(&matched_text);
+            } else {
+                // We validated that all placeholder references were valid before we
+                // started, so this shouldn't happen.
+                panic!(
+                    "Internal error: replacement referenced unknown placeholder {}",
+                    placeholder.ident
+                );
+            }
+        } else {
+            out.push_str(token.text().as_str());
+        }
+    }
+}
diff --git a/crates/ra_ssr/src/tests.rs b/crates/ra_ssr/src/tests.rs
index 9f5306592..1b03b7f4b 100644
--- a/crates/ra_ssr/src/tests.rs
+++ b/crates/ra_ssr/src/tests.rs
@@ -37,7 +37,7 @@ fn parser_repeated_name() {
 fn parser_invalid_pattern() {
     assert_eq!(
         parse_error_text(" ==>> ()"),
-        "Parse error: Pattern is not a valid Rust expression, type, item, path or pattern"
+        "Parse error: Not a valid Rust expression, type, item, path or pattern"
     );
 }
 
@@ -45,7 +45,7 @@ fn parser_invalid_pattern() {
 fn parser_invalid_template() {
     assert_eq!(
         parse_error_text("() ==>> )"),
-        "Parse error: Replacement is not a valid Rust expression, type, item, path or pattern"
+        "Parse error: Not a valid Rust expression, type, item, path or pattern"
     );
 }
 
-- 
cgit v1.2.3


From 13f901f636846e330699a4414059591ec2e67cd1 Mon Sep 17 00:00:00 2001
From: David Lattimore <dml@google.com>
Date: Wed, 22 Jul 2020 16:31:32 +1000
Subject: SSR: Move search code into a submodule

Also renamed find_matches to slow_scan_node to reflect that it's a slow
way to do things. Actually the name came from a later commit and
probably makes more sense once there's an alternative.
---
 crates/ra_ssr/src/lib.rs    | 50 ++---------------------------------------
 crates/ra_ssr/src/search.rs | 54 +++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 56 insertions(+), 48 deletions(-)
 create mode 100644 crates/ra_ssr/src/search.rs

(limited to 'crates/ra_ssr/src')

diff --git a/crates/ra_ssr/src/lib.rs b/crates/ra_ssr/src/lib.rs
index b28913a65..dac73c07c 100644
--- a/crates/ra_ssr/src/lib.rs
+++ b/crates/ra_ssr/src/lib.rs
@@ -6,6 +6,7 @@
 mod matching;
 mod parsing;
 mod replacing;
+mod search;
 #[macro_use]
 mod errors;
 #[cfg(test)]
@@ -83,7 +84,7 @@ impl<'db> MatchFinder<'db> {
         let file = self.sema.parse(file_id);
         let code = file.syntax();
         let mut matches = SsrMatches::default();
-        self.find_matches(code, &None, &mut matches);
+        self.slow_scan_node(code, &None, &mut matches.matches);
         matches
     }
 
@@ -120,53 +121,6 @@ impl<'db> MatchFinder<'db> {
         }
     }
 
-    fn find_matches(
-        &self,
-        code: &SyntaxNode,
-        restrict_range: &Option<FileRange>,
-        matches_out: &mut SsrMatches,
-    ) {
-        for rule in &self.rules {
-            if let Ok(mut m) = matching::get_match(false, rule, &code, restrict_range, &self.sema) {
-                // Continue searching in each of our placeholders.
-                for placeholder_value in m.placeholder_values.values_mut() {
-                    if let Some(placeholder_node) = &placeholder_value.node {
-                        // Don't search our placeholder if it's the entire matched node, otherwise we'd
-                        // find the same match over and over until we got a stack overflow.
-                        if placeholder_node != code {
-                            self.find_matches(
-                                placeholder_node,
-                                restrict_range,
-                                &mut placeholder_value.inner_matches,
-                            );
-                        }
-                    }
-                }
-                matches_out.matches.push(m);
-                return;
-            }
-        }
-        // If we've got a macro call, we already tried matching it pre-expansion, which is the only
-        // way to match the whole macro, now try expanding it and matching the expansion.
-        if let Some(macro_call) = ast::MacroCall::cast(code.clone()) {
-            if let Some(expanded) = self.sema.expand(&macro_call) {
-                if let Some(tt) = macro_call.token_tree() {
-                    // When matching within a macro expansion, we only want to allow matches of
-                    // nodes that originated entirely from within the token tree of the macro call.
-                    // i.e. we don't want to match something that came from the macro itself.
-                    self.find_matches(
-                        &expanded,
-                        &Some(self.sema.original_range(tt.syntax())),
-                        matches_out,
-                    );
-                }
-            }
-        }
-        for child in code.children() {
-            self.find_matches(&child, restrict_range, matches_out);
-        }
-    }
-
     fn output_debug_for_nodes_at_range(
         &self,
         node: &SyntaxNode,
diff --git a/crates/ra_ssr/src/search.rs b/crates/ra_ssr/src/search.rs
new file mode 100644
index 000000000..6f21452ac
--- /dev/null
+++ b/crates/ra_ssr/src/search.rs
@@ -0,0 +1,54 @@
+//! Searching for matches.
+
+use crate::{matching, Match, MatchFinder};
+use ra_db::FileRange;
+use ra_syntax::{ast, AstNode, SyntaxNode};
+
+impl<'db> MatchFinder<'db> {
+    pub(crate) fn slow_scan_node(
+        &self,
+        code: &SyntaxNode,
+        restrict_range: &Option<FileRange>,
+        matches_out: &mut Vec<Match>,
+    ) {
+        for rule in &self.rules {
+            if let Ok(mut m) = matching::get_match(false, rule, &code, restrict_range, &self.sema) {
+                // Continue searching in each of our placeholders.
+                for placeholder_value in m.placeholder_values.values_mut() {
+                    if let Some(placeholder_node) = &placeholder_value.node {
+                        // Don't search our placeholder if it's the entire matched node, otherwise we'd
+                        // find the same match over and over until we got a stack overflow.
+                        if placeholder_node != code {
+                            self.slow_scan_node(
+                                placeholder_node,
+                                restrict_range,
+                                &mut placeholder_value.inner_matches.matches,
+                            );
+                        }
+                    }
+                }
+                matches_out.push(m);
+                return;
+            }
+        }
+        // If we've got a macro call, we already tried matching it pre-expansion, which is the only
+        // way to match the whole macro, now try expanding it and matching the expansion.
+        if let Some(macro_call) = ast::MacroCall::cast(code.clone()) {
+            if let Some(expanded) = self.sema.expand(&macro_call) {
+                if let Some(tt) = macro_call.token_tree() {
+                    // When matching within a macro expansion, we only want to allow matches of
+                    // nodes that originated entirely from within the token tree of the macro call.
+                    // i.e. we don't want to match something that came from the macro itself.
+                    self.slow_scan_node(
+                        &expanded,
+                        &Some(self.sema.original_range(tt.syntax())),
+                        matches_out,
+                    );
+                }
+            }
+        }
+        for child in code.children() {
+            self.slow_scan_node(&child, restrict_range, matches_out);
+        }
+    }
+}
-- 
cgit v1.2.3


From a45682ed96f18f962ac403419b4d143d59ba5283 Mon Sep 17 00:00:00 2001
From: David Lattimore <dml@google.com>
Date: Wed, 22 Jul 2020 16:23:43 +1000
Subject: Move iteration over all files into the SSR crate

The methods `edits_for_file` and `find_matches_in_file` are replaced with just `edits` and `matches`. This simplifies the API a bit, but more importantly it makes it possible in a subsequent commit for SSR to decide to not search all files.
---
 crates/ra_ssr/src/lib.rs      | 48 ++++++++++++++++++++++++-------------------
 crates/ra_ssr/src/matching.rs | 15 +++++++-------
 crates/ra_ssr/src/search.rs   | 21 ++++++++++++++++++-
 crates/ra_ssr/src/tests.rs    | 40 ++++++++++++++++++++----------------
 4 files changed, 77 insertions(+), 47 deletions(-)

(limited to 'crates/ra_ssr/src')

diff --git a/crates/ra_ssr/src/lib.rs b/crates/ra_ssr/src/lib.rs
index dac73c07c..7b6409806 100644
--- a/crates/ra_ssr/src/lib.rs
+++ b/crates/ra_ssr/src/lib.rs
@@ -17,8 +17,9 @@ pub use crate::matching::Match;
 use crate::matching::MatchFailureReason;
 use hir::Semantics;
 use ra_db::{FileId, FileRange};
+use ra_ide_db::source_change::SourceFileEdit;
 use ra_syntax::{ast, AstNode, SyntaxNode, TextRange};
-use ra_text_edit::TextEdit;
+use rustc_hash::FxHashMap;
 
 // A structured search replace rule. Create by calling `parse` on a str.
 #[derive(Debug)]
@@ -60,32 +61,37 @@ impl<'db> MatchFinder<'db> {
         self.add_parsed_rules(rule.parsed_rules);
     }
 
+    /// Finds matches for all added rules and returns edits for all found matches.
+    pub fn edits(&self) -> Vec<SourceFileEdit> {
+        use ra_db::SourceDatabaseExt;
+        let mut matches_by_file = FxHashMap::default();
+        for m in self.matches().matches {
+            matches_by_file
+                .entry(m.range.file_id)
+                .or_insert_with(|| SsrMatches::default())
+                .matches
+                .push(m);
+        }
+        let mut edits = vec![];
+        for (file_id, matches) in matches_by_file {
+            let edit =
+                replacing::matches_to_edit(&matches, &self.sema.db.file_text(file_id), &self.rules);
+            edits.push(SourceFileEdit { file_id, edit });
+        }
+        edits
+    }
+
     /// Adds a search pattern. For use if you intend to only call `find_matches_in_file`. If you
     /// intend to do replacement, use `add_rule` instead.
     pub fn add_search_pattern(&mut self, pattern: SsrPattern) {
         self.add_parsed_rules(pattern.parsed_rules);
     }
 
-    pub fn edits_for_file(&self, file_id: FileId) -> Option<TextEdit> {
-        let matches = self.find_matches_in_file(file_id);
-        if matches.matches.is_empty() {
-            None
-        } else {
-            use ra_db::SourceDatabaseExt;
-            Some(replacing::matches_to_edit(
-                &matches,
-                &self.sema.db.file_text(file_id),
-                &self.rules,
-            ))
-        }
-    }
-
-    pub fn find_matches_in_file(&self, file_id: FileId) -> SsrMatches {
-        let file = self.sema.parse(file_id);
-        let code = file.syntax();
-        let mut matches = SsrMatches::default();
-        self.slow_scan_node(code, &None, &mut matches.matches);
-        matches
+    /// Returns matches for all added rules.
+    pub fn matches(&self) -> SsrMatches {
+        let mut matches = Vec::new();
+        self.find_all_matches(&mut matches);
+        SsrMatches { matches }
     }
 
     /// Finds all nodes in `file_id` whose text is exactly equal to `snippet` and attempts to match
diff --git a/crates/ra_ssr/src/matching.rs b/crates/ra_ssr/src/matching.rs
index 486191635..064e3a204 100644
--- a/crates/ra_ssr/src/matching.rs
+++ b/crates/ra_ssr/src/matching.rs
@@ -570,13 +570,12 @@ mod tests {
     #[test]
     fn parse_match_replace() {
         let rule: SsrRule = "foo($x) ==>> bar($x)".parse().unwrap();
-        let input = "fn foo() {} fn main() { foo(1+2); }";
+        let input = "fn foo() {} fn bar() {} fn main() { foo(1+2); }";
 
-        use ra_db::fixture::WithFixture;
-        let (db, file_id) = ra_ide_db::RootDatabase::with_single_file(input);
+        let (db, _) = crate::tests::single_file(input);
         let mut match_finder = MatchFinder::new(&db);
         match_finder.add_rule(rule);
-        let matches = match_finder.find_matches_in_file(file_id);
+        let matches = match_finder.matches();
         assert_eq!(matches.matches.len(), 1);
         assert_eq!(matches.matches[0].matched_node.text(), "foo(1+2)");
         assert_eq!(matches.matches[0].placeholder_values.len(), 1);
@@ -589,9 +588,11 @@ mod tests {
             "1+2"
         );
 
-        let edit = crate::replacing::matches_to_edit(&matches, input, &match_finder.rules);
+        let edits = match_finder.edits();
+        assert_eq!(edits.len(), 1);
+        let edit = &edits[0];
         let mut after = input.to_string();
-        edit.apply(&mut after);
-        assert_eq!(after, "fn foo() {} fn main() { bar(1+2); }");
+        edit.edit.apply(&mut after);
+        assert_eq!(after, "fn foo() {} fn bar() {} fn main() { bar(1+2); }");
     }
 }
diff --git a/crates/ra_ssr/src/search.rs b/crates/ra_ssr/src/search.rs
index 6f21452ac..ec3addcf8 100644
--- a/crates/ra_ssr/src/search.rs
+++ b/crates/ra_ssr/src/search.rs
@@ -5,7 +5,26 @@ use ra_db::FileRange;
 use ra_syntax::{ast, AstNode, SyntaxNode};
 
 impl<'db> MatchFinder<'db> {
-    pub(crate) fn slow_scan_node(
+    pub(crate) fn find_all_matches(&self, matches_out: &mut Vec<Match>) {
+        // FIXME: Use resolved paths in the pattern to find places to search instead of always
+        // scanning every node.
+        self.slow_scan(matches_out);
+    }
+
+    fn slow_scan(&self, matches_out: &mut Vec<Match>) {
+        use ra_db::SourceDatabaseExt;
+        use ra_ide_db::symbol_index::SymbolsDatabase;
+        for &root in self.sema.db.local_roots().iter() {
+            let sr = self.sema.db.source_root(root);
+            for file_id in sr.iter() {
+                let file = self.sema.parse(file_id);
+                let code = file.syntax();
+                self.slow_scan_node(code, &None, matches_out);
+            }
+        }
+    }
+
+    fn slow_scan_node(
         &self,
         code: &SyntaxNode,
         restrict_range: &Option<FileRange>,
diff --git a/crates/ra_ssr/src/tests.rs b/crates/ra_ssr/src/tests.rs
index 1b03b7f4b..c7c37af2f 100644
--- a/crates/ra_ssr/src/tests.rs
+++ b/crates/ra_ssr/src/tests.rs
@@ -1,6 +1,8 @@
 use crate::{MatchFinder, SsrRule};
 use expect::{expect, Expect};
-use ra_db::{FileId, SourceDatabaseExt};
+use ra_db::{salsa::Durability, FileId, SourceDatabaseExt};
+use rustc_hash::FxHashSet;
+use std::sync::Arc;
 use test_utils::mark;
 
 fn parse_error_text(query: &str) -> String {
@@ -57,9 +59,15 @@ fn parser_undefined_placeholder_in_replacement() {
     );
 }
 
-fn single_file(code: &str) -> (ra_ide_db::RootDatabase, FileId) {
+pub(crate) fn single_file(code: &str) -> (ra_ide_db::RootDatabase, FileId) {
     use ra_db::fixture::WithFixture;
-    ra_ide_db::RootDatabase::with_single_file(code)
+    use ra_ide_db::symbol_index::SymbolsDatabase;
+    let (db, file_id) = ra_ide_db::RootDatabase::with_single_file(code);
+    let mut db = db;
+    let mut local_roots = FxHashSet::default();
+    local_roots.insert(ra_db::fixture::WORKSPACE);
+    db.set_local_roots_with_durability(Arc::new(local_roots), Durability::HIGH);
+    (db, file_id)
 }
 
 fn assert_ssr_transform(rule: &str, input: &str, expected: Expect) {
@@ -73,15 +81,16 @@ fn assert_ssr_transforms(rules: &[&str], input: &str, expected: Expect) {
         let rule: SsrRule = rule.parse().unwrap();
         match_finder.add_rule(rule);
     }
-    if let Some(edits) = match_finder.edits_for_file(file_id) {
-        // Note, db.file_text is not necessarily the same as `input`, since fixture parsing alters
-        // stuff.
-        let mut actual = db.file_text(file_id).to_string();
-        edits.apply(&mut actual);
-        expected.assert_eq(&actual);
-    } else {
+    let edits = match_finder.edits();
+    if edits.is_empty() {
         panic!("No edits were made");
     }
+    assert_eq!(edits[0].file_id, file_id);
+    // Note, db.file_text is not necessarily the same as `input`, since fixture parsing alters
+    // stuff.
+    let mut actual = db.file_text(file_id).to_string();
+    edits[0].edit.apply(&mut actual);
+    expected.assert_eq(&actual);
 }
 
 fn print_match_debug_info(match_finder: &MatchFinder, file_id: FileId, snippet: &str) {
@@ -100,13 +109,8 @@ fn assert_matches(pattern: &str, code: &str, expected: &[&str]) {
     let (db, file_id) = single_file(code);
     let mut match_finder = MatchFinder::new(&db);
     match_finder.add_search_pattern(pattern.parse().unwrap());
-    let matched_strings: Vec<String> = match_finder
-        .find_matches_in_file(file_id)
-        .flattened()
-        .matches
-        .iter()
-        .map(|m| m.matched_text())
-        .collect();
+    let matched_strings: Vec<String> =
+        match_finder.matches().flattened().matches.iter().map(|m| m.matched_text()).collect();
     if matched_strings != expected && !expected.is_empty() {
         print_match_debug_info(&match_finder, file_id, &expected[0]);
     }
@@ -117,7 +121,7 @@ fn assert_no_match(pattern: &str, code: &str) {
     let (db, file_id) = single_file(code);
     let mut match_finder = MatchFinder::new(&db);
     match_finder.add_search_pattern(pattern.parse().unwrap());
-    let matches = match_finder.find_matches_in_file(file_id).flattened().matches;
+    let matches = match_finder.matches().flattened().matches;
     if !matches.is_empty() {
         print_match_debug_info(&match_finder, file_id, &matches[0].matched_text());
         panic!("Got {} matches when we expected none: {:#?}", matches.len(), matches);
-- 
cgit v1.2.3


From 6fcaaa1201c650ce22b71160f6e9bf2288d10a1a Mon Sep 17 00:00:00 2001
From: David Lattimore <dml@google.com>
Date: Wed, 22 Jul 2020 16:06:14 +1000
Subject: SSR tests: Define all paths needed for templates

In a later commit, paths in templates will be resolved. This allows us
to render the path with appropriate qualifiers for its context. Here we
prepare for that change by updating existing tests where I'd previously
not bothered to define the items that the template referred to.
---
 crates/ra_ssr/src/tests.rs | 102 +++++++++++++++++++++++++++++++++------------
 1 file changed, 76 insertions(+), 26 deletions(-)

(limited to 'crates/ra_ssr/src')

diff --git a/crates/ra_ssr/src/tests.rs b/crates/ra_ssr/src/tests.rs
index c7c37af2f..11512c8cc 100644
--- a/crates/ra_ssr/src/tests.rs
+++ b/crates/ra_ssr/src/tests.rs
@@ -154,8 +154,19 @@ fn ssr_function_to_method() {
 fn ssr_nested_function() {
     assert_ssr_transform(
         "foo($a, $b, $c) ==>> bar($c, baz($a, $b))",
-        "fn foo() {} fn main { foo  (x + value.method(b), x+y-z, true && false) }",
-        expect![["fn foo() {} fn main { bar(true && false, baz(x + value.method(b), x+y-z)) }"]],
+        r#"
+            //- /lib.rs crate:foo
+            fn foo() {}
+            fn bar() {}
+            fn baz() {}
+            fn main { foo  (x + value.method(b), x+y-z, true && false) }
+            "#,
+        expect![[r#"
+            fn foo() {}
+            fn bar() {}
+            fn baz() {}
+            fn main { bar(true && false, baz(x + value.method(b), x+y-z)) }
+        "#]],
     )
 }
 
@@ -181,8 +192,8 @@ fn ssr_with_extra_space() {
 fn ssr_keeps_nested_comment() {
     assert_ssr_transform(
         "foo($x) ==>> bar($x)",
-        "fn foo() {} fn main() { foo(other(5 /* using 5 */)) }",
-        expect![["fn foo() {} fn main() { bar(other(5 /* using 5 */)) }"]],
+        "fn foo() {} fn bar() {} fn main() { foo(other(5 /* using 5 */)) }",
+        expect![["fn foo() {} fn bar() {} fn main() { bar(other(5 /* using 5 */)) }"]],
     )
 }
 
@@ -190,17 +201,25 @@ fn ssr_keeps_nested_comment() {
 fn ssr_keeps_comment() {
     assert_ssr_transform(
         "foo($x) ==>> bar($x)",
-        "fn foo() {} fn main() { foo(5 /* using 5 */) }",
-        expect![["fn foo() {} fn main() { bar(5)/* using 5 */ }"]],
+        "fn foo() {} fn bar() {} fn main() { foo(5 /* using 5 */) }",
+        expect![["fn foo() {} fn bar() {} fn main() { bar(5)/* using 5 */ }"]],
     )
 }
 
 #[test]
 fn ssr_struct_lit() {
     assert_ssr_transform(
-        "foo{a: $a, b: $b} ==>> foo::new($a, $b)",
-        "fn foo() {} fn main() { foo{b:2, a:1} }",
-        expect![["fn foo() {} fn main() { foo::new(1, 2) }"]],
+        "Foo{a: $a, b: $b} ==>> Foo::new($a, $b)",
+        r#"
+            struct Foo() {}
+            impl Foo { fn new() {} }
+            fn main() { Foo{b:2, a:1} }
+            "#,
+        expect![[r#"
+            struct Foo() {}
+            impl Foo { fn new() {} }
+            fn main() { Foo::new(1, 2) }
+        "#]],
     )
 }
 
@@ -312,7 +331,7 @@ fn match_struct_instantiation() {
 fn match_path() {
     let code = r#"
         mod foo {
-            fn bar() {}
+            pub fn bar() {}
         }
         fn f() {foo::bar(42)}"#;
     assert_matches("foo::bar", code, &["foo::bar"]);
@@ -413,8 +432,8 @@ fn no_match_split_expression() {
 fn replace_function_call() {
     assert_ssr_transform(
         "foo() ==>> bar()",
-        "fn foo() {} fn f1() {foo(); foo();}",
-        expect![["fn foo() {} fn f1() {bar(); bar();}"]],
+        "fn foo() {} fn bar() {} fn f1() {foo(); foo();}",
+        expect![["fn foo() {} fn bar() {} fn f1() {bar(); bar();}"]],
     );
 }
 
@@ -422,8 +441,8 @@ fn replace_function_call() {
 fn replace_function_call_with_placeholders() {
     assert_ssr_transform(
         "foo($a, $b) ==>> bar($b, $a)",
-        "fn foo() {} fn f1() {foo(5, 42)}",
-        expect![["fn foo() {} fn f1() {bar(42, 5)}"]],
+        "fn foo() {} fn bar() {} fn f1() {foo(5, 42)}",
+        expect![["fn foo() {} fn bar() {} fn f1() {bar(42, 5)}"]],
     );
 }
 
@@ -431,26 +450,40 @@ fn replace_function_call_with_placeholders() {
 fn replace_nested_function_calls() {
     assert_ssr_transform(
         "foo($a) ==>> bar($a)",
-        "fn foo() {} fn f1() {foo(foo(42))}",
-        expect![["fn foo() {} fn f1() {bar(bar(42))}"]],
+        "fn foo() {} fn bar() {} fn f1() {foo(foo(42))}",
+        expect![["fn foo() {} fn bar() {} fn f1() {bar(bar(42))}"]],
     );
 }
 
 #[test]
-fn replace_type() {
+fn replace_associated_function_call() {
     assert_ssr_transform(
-        "Result<(), $a> ==>> Option<$a>",
-        "struct Result<T, E> {} fn f1() -> Result<(), Vec<Error>> {foo()}",
-        expect![["struct Result<T, E> {} fn f1() -> Option<Vec<Error>> {foo()}"]],
+        "Foo::new() ==>> Bar::new()",
+        r#"
+            struct Foo {}
+            impl Foo { fn new() {} }
+            struct Bar {}
+            impl Bar { fn new() {} }
+            fn f1() {Foo::new();}
+            "#,
+        expect![[r#"
+            struct Foo {}
+            impl Foo { fn new() {} }
+            struct Bar {}
+            impl Bar { fn new() {} }
+            fn f1() {Bar::new();}
+        "#]],
     );
 }
 
 #[test]
-fn replace_struct_init() {
+fn replace_type() {
     assert_ssr_transform(
-        "Foo {a: $a, b: $b} ==>> Foo::new($a, $b)",
-        "struct Foo {} fn f1() {Foo{b: 1, a: 2}}",
-        expect![["struct Foo {} fn f1() {Foo::new(2, 1)}"]],
+        "Result<(), $a> ==>> Option<$a>",
+        "struct Result<T, E> {} struct Option<T> {} fn f1() -> Result<(), Vec<Error>> {foo()}",
+        expect![[
+            "struct Result<T, E> {} struct Option<T> {} fn f1() -> Option<Vec<Error>> {foo()}"
+        ]],
     );
 }
 
@@ -491,8 +524,23 @@ fn match_binary_op() {
 fn multiple_rules() {
     assert_ssr_transforms(
         &["$a + 1 ==>> add_one($a)", "$a + $b ==>> add($a, $b)"],
-        "fn f() -> i32 {3 + 2 + 1}",
-        expect![["fn f() -> i32 {add_one(add(3, 2))}"]],
+        "fn add() {} fn add_one() {} fn f() -> i32 {3 + 2 + 1}",
+        expect![["fn add() {} fn add_one() {} fn f() -> i32 {add_one(add(3, 2))}"]],
+    )
+}
+
+#[test]
+fn multiple_rules_with_nested_matches() {
+    assert_ssr_transforms(
+        &["foo1($a) ==>> bar1($a)", "foo2($a) ==>> bar2($a)"],
+        r#"
+            fn foo1() {} fn foo2() {} fn bar1() {} fn bar2() {}
+            fn f() {foo1(foo2(foo1(foo2(foo1(42)))))}
+            "#,
+        expect![[r#"
+            fn foo1() {} fn foo2() {} fn bar1() {} fn bar2() {}
+            fn f() {bar1(bar2(bar1(bar2(bar1(42)))))}
+        "#]],
     )
 }
 
@@ -524,12 +572,14 @@ fn replace_within_macro_expansion() {
             macro_rules! macro1 {
                 ($a:expr) => {$a}
             }
+            fn bar() {}
             fn f() {macro1!(5.x().foo().o2())}
             "#,
         expect![[r#"
             macro_rules! macro1 {
                 ($a:expr) => {$a}
             }
+            fn bar() {}
             fn f() {macro1!(bar(5.x()).o2())}
             "#]],
     )
-- 
cgit v1.2.3


From 699619a65cf816b927fffa77b2b38f611d8460bc Mon Sep 17 00:00:00 2001
From: David Lattimore <dml@google.com>
Date: Wed, 22 Jul 2020 16:00:57 +1000
Subject: SSR: Add a couple of tests for non-recursive search

These tests already pass, however once we switch to non-recursive
search, it'd be easy for these tests to not pass.
---
 crates/ra_ssr/src/tests.rs | 33 +++++++++++++++++++++++++++++++++
 1 file changed, 33 insertions(+)

(limited to 'crates/ra_ssr/src')

diff --git a/crates/ra_ssr/src/tests.rs b/crates/ra_ssr/src/tests.rs
index 11512c8cc..523035b31 100644
--- a/crates/ra_ssr/src/tests.rs
+++ b/crates/ra_ssr/src/tests.rs
@@ -585,6 +585,27 @@ fn replace_within_macro_expansion() {
     )
 }
 
+#[test]
+fn replace_outside_and_within_macro_expansion() {
+    assert_ssr_transform(
+        "foo($a) ==>> bar($a)",
+        r#"
+            fn foo() {} fn bar() {}
+            macro_rules! macro1 {
+                ($a:expr) => {$a}
+            }
+            fn f() {foo(foo(macro1!(foo(foo(42)))))}
+            "#,
+        expect![[r#"
+            fn foo() {} fn bar() {}
+            macro_rules! macro1 {
+                ($a:expr) => {$a}
+            }
+            fn f() {bar(bar(macro1!(bar(bar(42)))))}
+        "#]],
+    )
+}
+
 #[test]
 fn preserves_whitespace_within_macro_expansion() {
     assert_ssr_transform(
@@ -631,3 +652,15 @@ fn match_failure_reasons() {
         r#"Pattern wanted token '42' (INT_NUMBER), but code had token '43' (INT_NUMBER)"#,
     );
 }
+
+#[test]
+fn overlapping_possible_matches() {
+    // There are three possible matches here, however the middle one, `foo(foo(foo(42)))` shouldn't
+    // match because it overlaps with the outer match. The inner match is permitted since it's is
+    // contained entirely within the placeholder of the outer match.
+    assert_matches(
+        "foo(foo($a))",
+        "fn foo() {} fn main() {foo(foo(foo(foo(42))))}",
+        &["foo(foo(42))", "foo(foo(foo(foo(42))))"],
+    );
+}
-- 
cgit v1.2.3


From 02fc3d50ee4d179cc5a443a790544c2a5e439cb0 Mon Sep 17 00:00:00 2001
From: David Lattimore <dml@google.com>
Date: Wed, 22 Jul 2020 16:48:12 +1000
Subject: SSR: Refactor to not rely on recursive search for nesting of matches

Previously, submatches were handled simply by searching in placeholders
for more matches. That only works if we search all nodes in the tree
recursively. In a subsequent commit, I intend to make search not always
be recursive recursive. This commit prepares for that by finding all
matches, even if they overlap, then nesting them and removing
overlapping matches.
---
 crates/ra_ssr/src/lib.rs      |  7 +++-
 crates/ra_ssr/src/matching.rs |  4 ++
 crates/ra_ssr/src/nester.rs   | 98 +++++++++++++++++++++++++++++++++++++++++++
 crates/ra_ssr/src/search.rs   | 38 ++++++-----------
 4 files changed, 120 insertions(+), 27 deletions(-)
 create mode 100644 crates/ra_ssr/src/nester.rs

(limited to 'crates/ra_ssr/src')

diff --git a/crates/ra_ssr/src/lib.rs b/crates/ra_ssr/src/lib.rs
index 7b6409806..6d578610b 100644
--- a/crates/ra_ssr/src/lib.rs
+++ b/crates/ra_ssr/src/lib.rs
@@ -4,6 +4,7 @@
 //! based on a template.
 
 mod matching;
+mod nester;
 mod parsing;
 mod replacing;
 mod search;
@@ -90,8 +91,10 @@ impl<'db> MatchFinder<'db> {
     /// Returns matches for all added rules.
     pub fn matches(&self) -> SsrMatches {
         let mut matches = Vec::new();
-        self.find_all_matches(&mut matches);
-        SsrMatches { matches }
+        for rule in &self.rules {
+            self.find_matches_for_rule(rule, &mut matches);
+        }
+        nester::nest_and_remove_collisions(matches, &self.sema)
     }
 
     /// Finds all nodes in `file_id` whose text is exactly equal to `snippet` and attempts to match
diff --git a/crates/ra_ssr/src/matching.rs b/crates/ra_ssr/src/matching.rs
index 064e3a204..005569f6f 100644
--- a/crates/ra_ssr/src/matching.rs
+++ b/crates/ra_ssr/src/matching.rs
@@ -49,6 +49,8 @@ pub struct Match {
     pub(crate) placeholder_values: FxHashMap<Var, PlaceholderMatch>,
     pub(crate) ignored_comments: Vec<ast::Comment>,
     pub(crate) rule_index: usize,
+    /// The depth of matched_node.
+    pub(crate) depth: usize,
 }
 
 /// Represents a `$var` in an SSR query.
@@ -130,10 +132,12 @@ impl<'db, 'sema> Matcher<'db, 'sema> {
             placeholder_values: FxHashMap::default(),
             ignored_comments: Vec::new(),
             rule_index: rule.index,
+            depth: 0,
         };
         // Second matching pass, where we record placeholder matches, ignored comments and maybe do
         // any other more expensive checks that we didn't want to do on the first pass.
         match_state.attempt_match_node(&mut Phase::Second(&mut the_match), &rule.pattern, code)?;
+        the_match.depth = sema.ancestors_with_macros(the_match.matched_node.clone()).count();
         Ok(the_match)
     }
 
diff --git a/crates/ra_ssr/src/nester.rs b/crates/ra_ssr/src/nester.rs
new file mode 100644
index 000000000..b3e20579b
--- /dev/null
+++ b/crates/ra_ssr/src/nester.rs
@@ -0,0 +1,98 @@
+//! Converts a flat collection of matches into a nested form suitable for replacement. When there
+//! are multiple matches for a node, or that overlap, priority is given to the earlier rule. Nested
+//! matches are only permitted if the inner match is contained entirely within a placeholder of an
+//! outer match.
+//!
+//! For example, if our search pattern is `foo(foo($a))` and the code had `foo(foo(foo(foo(42))))`,
+//! then we'll get 3 matches, however only the outermost and innermost matches can be accepted. The
+//! middle match would take the second `foo` from the outer match.
+
+use crate::{Match, SsrMatches};
+use ra_syntax::SyntaxNode;
+use rustc_hash::FxHashMap;
+
+pub(crate) fn nest_and_remove_collisions(
+    mut matches: Vec<Match>,
+    sema: &hir::Semantics<ra_ide_db::RootDatabase>,
+) -> SsrMatches {
+    // We sort the matches by depth then by rule index. Sorting by depth means that by the time we
+    // see a match, any parent matches or conflicting matches will have already been seen. Sorting
+    // by rule_index means that if there are two matches for the same node, the rule added first
+    // will take precedence.
+    matches.sort_by(|a, b| a.depth.cmp(&b.depth).then_with(|| a.rule_index.cmp(&b.rule_index)));
+    let mut collector = MatchCollector::default();
+    for m in matches {
+        collector.add_match(m, sema);
+    }
+    collector.into()
+}
+
+#[derive(Default)]
+struct MatchCollector {
+    matches_by_node: FxHashMap<SyntaxNode, Match>,
+}
+
+impl MatchCollector {
+    /// Attempts to add `m` to matches. If it conflicts with an existing match, it is discarded. If
+    /// it is entirely within the a placeholder of an existing match, then it is added as a child
+    /// match of the existing match.
+    fn add_match(&mut self, m: Match, sema: &hir::Semantics<ra_ide_db::RootDatabase>) {
+        let matched_node = m.matched_node.clone();
+        if let Some(existing) = self.matches_by_node.get_mut(&matched_node) {
+            try_add_sub_match(m, existing, sema);
+            return;
+        }
+        for ancestor in sema.ancestors_with_macros(m.matched_node.clone()) {
+            if let Some(existing) = self.matches_by_node.get_mut(&ancestor) {
+                try_add_sub_match(m, existing, sema);
+                return;
+            }
+        }
+        self.matches_by_node.insert(matched_node, m);
+    }
+}
+
+/// Attempts to add `m` as a sub-match of `existing`.
+fn try_add_sub_match(
+    m: Match,
+    existing: &mut Match,
+    sema: &hir::Semantics<ra_ide_db::RootDatabase>,
+) {
+    for p in existing.placeholder_values.values_mut() {
+        // Note, no need to check if p.range.file is equal to m.range.file, since we
+        // already know we're within `existing`.
+        if p.range.range.contains_range(m.range.range) {
+            // Convert the inner matches in `p` into a temporary MatchCollector. When
+            // we're done, we then convert it back into an SsrMatches. If we expected
+            // lots of inner matches, it might be worthwhile keeping a MatchCollector
+            // around for each placeholder match. However we expect most placeholder
+            // will have 0 and a few will have 1. More than that should hopefully be
+            // exceptional.
+            let mut collector = MatchCollector::default();
+            for m in std::mem::replace(&mut p.inner_matches.matches, Vec::new()) {
+                collector.matches_by_node.insert(m.matched_node.clone(), m);
+            }
+            collector.add_match(m, sema);
+            p.inner_matches = collector.into();
+            break;
+        }
+    }
+}
+
+impl From<MatchCollector> for SsrMatches {
+    fn from(mut match_collector: MatchCollector) -> Self {
+        let mut matches = SsrMatches::default();
+        for (_, m) in match_collector.matches_by_node.drain() {
+            matches.matches.push(m);
+        }
+        matches.matches.sort_by(|a, b| {
+            // Order matches by file_id then by start range. This should be sufficient since ranges
+            // shouldn't be overlapping.
+            a.range
+                .file_id
+                .cmp(&b.range.file_id)
+                .then_with(|| a.range.range.start().cmp(&b.range.range.start()))
+        });
+        matches
+    }
+}
diff --git a/crates/ra_ssr/src/search.rs b/crates/ra_ssr/src/search.rs
index ec3addcf8..a28e9f341 100644
--- a/crates/ra_ssr/src/search.rs
+++ b/crates/ra_ssr/src/search.rs
@@ -1,17 +1,20 @@
 //! Searching for matches.
 
-use crate::{matching, Match, MatchFinder};
+use crate::{matching, parsing::ParsedRule, Match, MatchFinder};
 use ra_db::FileRange;
 use ra_syntax::{ast, AstNode, SyntaxNode};
 
 impl<'db> MatchFinder<'db> {
-    pub(crate) fn find_all_matches(&self, matches_out: &mut Vec<Match>) {
+    /// Adds all matches for `rule` to `matches_out`. Matches may overlap in ways that make
+    /// replacement impossible, so further processing is required in order to properly nest matches
+    /// and remove overlapping matches. This is done in the `nesting` module.
+    pub(crate) fn find_matches_for_rule(&self, rule: &ParsedRule, matches_out: &mut Vec<Match>) {
         // FIXME: Use resolved paths in the pattern to find places to search instead of always
         // scanning every node.
-        self.slow_scan(matches_out);
+        self.slow_scan(rule, matches_out);
     }
 
-    fn slow_scan(&self, matches_out: &mut Vec<Match>) {
+    fn slow_scan(&self, rule: &ParsedRule, matches_out: &mut Vec<Match>) {
         use ra_db::SourceDatabaseExt;
         use ra_ide_db::symbol_index::SymbolsDatabase;
         for &root in self.sema.db.local_roots().iter() {
@@ -19,7 +22,7 @@ impl<'db> MatchFinder<'db> {
             for file_id in sr.iter() {
                 let file = self.sema.parse(file_id);
                 let code = file.syntax();
-                self.slow_scan_node(code, &None, matches_out);
+                self.slow_scan_node(code, rule, &None, matches_out);
             }
         }
     }
@@ -27,28 +30,12 @@ impl<'db> MatchFinder<'db> {
     fn slow_scan_node(
         &self,
         code: &SyntaxNode,
+        rule: &ParsedRule,
         restrict_range: &Option<FileRange>,
         matches_out: &mut Vec<Match>,
     ) {
-        for rule in &self.rules {
-            if let Ok(mut m) = matching::get_match(false, rule, &code, restrict_range, &self.sema) {
-                // Continue searching in each of our placeholders.
-                for placeholder_value in m.placeholder_values.values_mut() {
-                    if let Some(placeholder_node) = &placeholder_value.node {
-                        // Don't search our placeholder if it's the entire matched node, otherwise we'd
-                        // find the same match over and over until we got a stack overflow.
-                        if placeholder_node != code {
-                            self.slow_scan_node(
-                                placeholder_node,
-                                restrict_range,
-                                &mut placeholder_value.inner_matches.matches,
-                            );
-                        }
-                    }
-                }
-                matches_out.push(m);
-                return;
-            }
+        if let Ok(m) = matching::get_match(false, rule, &code, restrict_range, &self.sema) {
+            matches_out.push(m);
         }
         // If we've got a macro call, we already tried matching it pre-expansion, which is the only
         // way to match the whole macro, now try expanding it and matching the expansion.
@@ -60,6 +47,7 @@ impl<'db> MatchFinder<'db> {
                     // i.e. we don't want to match something that came from the macro itself.
                     self.slow_scan_node(
                         &expanded,
+                        rule,
                         &Some(self.sema.original_range(tt.syntax())),
                         matches_out,
                     );
@@ -67,7 +55,7 @@ impl<'db> MatchFinder<'db> {
             }
         }
         for child in code.children() {
-            self.slow_scan_node(&child, restrict_range, matches_out);
+            self.slow_scan_node(&child, rule, restrict_range, matches_out);
         }
     }
 }
-- 
cgit v1.2.3


From 3975952601888d9f77e466c12e8e389748984b33 Mon Sep 17 00:00:00 2001
From: David Lattimore <dml@google.com>
Date: Wed, 22 Jul 2020 15:00:28 +1000
Subject: SSR: Pass current file position through to SSR code.

In a subsequent commit, it will be used for resolving paths.
---
 crates/ra_ssr/src/lib.rs      | 30 ++++++++++++++++++++++++++++--
 crates/ra_ssr/src/matching.rs |  4 ++--
 crates/ra_ssr/src/tests.rs    | 42 ++++++++++++++++++++++++------------------
 3 files changed, 54 insertions(+), 22 deletions(-)

(limited to 'crates/ra_ssr/src')

diff --git a/crates/ra_ssr/src/lib.rs b/crates/ra_ssr/src/lib.rs
index 6d578610b..a0a5c9762 100644
--- a/crates/ra_ssr/src/lib.rs
+++ b/crates/ra_ssr/src/lib.rs
@@ -13,11 +13,12 @@ mod errors;
 #[cfg(test)]
 mod tests;
 
+use crate::errors::bail;
 pub use crate::errors::SsrError;
 pub use crate::matching::Match;
 use crate::matching::MatchFailureReason;
 use hir::Semantics;
-use ra_db::{FileId, FileRange};
+use ra_db::{FileId, FilePosition, FileRange};
 use ra_ide_db::source_change::SourceFileEdit;
 use ra_syntax::{ast, AstNode, SyntaxNode, TextRange};
 use rustc_hash::FxHashMap;
@@ -51,10 +52,35 @@ pub struct MatchFinder<'db> {
 }
 
 impl<'db> MatchFinder<'db> {
-    pub fn new(db: &'db ra_ide_db::RootDatabase) -> MatchFinder<'db> {
+    /// Constructs a new instance where names will be looked up as if they appeared at
+    /// `lookup_context`.
+    pub fn in_context(
+        db: &'db ra_ide_db::RootDatabase,
+        _lookup_context: FilePosition,
+    ) -> MatchFinder<'db> {
+        // FIXME: Use lookup_context
         MatchFinder { sema: Semantics::new(db), rules: Vec::new() }
     }
 
+    /// Constructs an instance using the start of the first file in `db` as the lookup context.
+    pub fn at_first_file(db: &'db ra_ide_db::RootDatabase) -> Result<MatchFinder<'db>, SsrError> {
+        use ra_db::SourceDatabaseExt;
+        use ra_ide_db::symbol_index::SymbolsDatabase;
+        if let Some(first_file_id) = db
+            .local_roots()
+            .iter()
+            .next()
+            .and_then(|root| db.source_root(root.clone()).iter().next())
+        {
+            Ok(MatchFinder::in_context(
+                db,
+                FilePosition { file_id: first_file_id, offset: 0.into() },
+            ))
+        } else {
+            bail!("No files to search");
+        }
+    }
+
     /// Adds a rule to be applied. The order in which rules are added matters. Earlier rules take
     /// precedence. If a node is matched by an earlier rule, then later rules won't be permitted to
     /// match to it.
diff --git a/crates/ra_ssr/src/matching.rs b/crates/ra_ssr/src/matching.rs
index 005569f6f..a43d57c34 100644
--- a/crates/ra_ssr/src/matching.rs
+++ b/crates/ra_ssr/src/matching.rs
@@ -576,8 +576,8 @@ mod tests {
         let rule: SsrRule = "foo($x) ==>> bar($x)".parse().unwrap();
         let input = "fn foo() {} fn bar() {} fn main() { foo(1+2); }";
 
-        let (db, _) = crate::tests::single_file(input);
-        let mut match_finder = MatchFinder::new(&db);
+        let (db, position) = crate::tests::single_file(input);
+        let mut match_finder = MatchFinder::in_context(&db, position);
         match_finder.add_rule(rule);
         let matches = match_finder.matches();
         assert_eq!(matches.matches.len(), 1);
diff --git a/crates/ra_ssr/src/tests.rs b/crates/ra_ssr/src/tests.rs
index 523035b31..63d527894 100644
--- a/crates/ra_ssr/src/tests.rs
+++ b/crates/ra_ssr/src/tests.rs
@@ -1,6 +1,6 @@
 use crate::{MatchFinder, SsrRule};
 use expect::{expect, Expect};
-use ra_db::{salsa::Durability, FileId, SourceDatabaseExt};
+use ra_db::{salsa::Durability, FileId, FilePosition, SourceDatabaseExt};
 use rustc_hash::FxHashSet;
 use std::sync::Arc;
 use test_utils::mark;
@@ -59,15 +59,21 @@ fn parser_undefined_placeholder_in_replacement() {
     );
 }
 
-pub(crate) fn single_file(code: &str) -> (ra_ide_db::RootDatabase, FileId) {
+/// `code` may optionally contain a cursor marker `<|>`. If it doesn't, then the position will be
+/// the start of the file.
+pub(crate) fn single_file(code: &str) -> (ra_ide_db::RootDatabase, FilePosition) {
     use ra_db::fixture::WithFixture;
     use ra_ide_db::symbol_index::SymbolsDatabase;
-    let (db, file_id) = ra_ide_db::RootDatabase::with_single_file(code);
-    let mut db = db;
+    let (mut db, position) = if code.contains(test_utils::CURSOR_MARKER) {
+        ra_ide_db::RootDatabase::with_position(code)
+    } else {
+        let (db, file_id) = ra_ide_db::RootDatabase::with_single_file(code);
+        (db, FilePosition { file_id, offset: 0.into() })
+    };
     let mut local_roots = FxHashSet::default();
     local_roots.insert(ra_db::fixture::WORKSPACE);
     db.set_local_roots_with_durability(Arc::new(local_roots), Durability::HIGH);
-    (db, file_id)
+    (db, position)
 }
 
 fn assert_ssr_transform(rule: &str, input: &str, expected: Expect) {
@@ -75,8 +81,8 @@ fn assert_ssr_transform(rule: &str, input: &str, expected: Expect) {
 }
 
 fn assert_ssr_transforms(rules: &[&str], input: &str, expected: Expect) {
-    let (db, file_id) = single_file(input);
-    let mut match_finder = MatchFinder::new(&db);
+    let (db, position) = single_file(input);
+    let mut match_finder = MatchFinder::in_context(&db, position);
     for rule in rules {
         let rule: SsrRule = rule.parse().unwrap();
         match_finder.add_rule(rule);
@@ -85,10 +91,10 @@ fn assert_ssr_transforms(rules: &[&str], input: &str, expected: Expect) {
     if edits.is_empty() {
         panic!("No edits were made");
     }
-    assert_eq!(edits[0].file_id, file_id);
+    assert_eq!(edits[0].file_id, position.file_id);
     // Note, db.file_text is not necessarily the same as `input`, since fixture parsing alters
     // stuff.
-    let mut actual = db.file_text(file_id).to_string();
+    let mut actual = db.file_text(position.file_id).to_string();
     edits[0].edit.apply(&mut actual);
     expected.assert_eq(&actual);
 }
@@ -106,34 +112,34 @@ fn print_match_debug_info(match_finder: &MatchFinder, file_id: FileId, snippet:
 }
 
 fn assert_matches(pattern: &str, code: &str, expected: &[&str]) {
-    let (db, file_id) = single_file(code);
-    let mut match_finder = MatchFinder::new(&db);
+    let (db, position) = single_file(code);
+    let mut match_finder = MatchFinder::in_context(&db, position);
     match_finder.add_search_pattern(pattern.parse().unwrap());
     let matched_strings: Vec<String> =
         match_finder.matches().flattened().matches.iter().map(|m| m.matched_text()).collect();
     if matched_strings != expected && !expected.is_empty() {
-        print_match_debug_info(&match_finder, file_id, &expected[0]);
+        print_match_debug_info(&match_finder, position.file_id, &expected[0]);
     }
     assert_eq!(matched_strings, expected);
 }
 
 fn assert_no_match(pattern: &str, code: &str) {
-    let (db, file_id) = single_file(code);
-    let mut match_finder = MatchFinder::new(&db);
+    let (db, position) = single_file(code);
+    let mut match_finder = MatchFinder::in_context(&db, position);
     match_finder.add_search_pattern(pattern.parse().unwrap());
     let matches = match_finder.matches().flattened().matches;
     if !matches.is_empty() {
-        print_match_debug_info(&match_finder, file_id, &matches[0].matched_text());
+        print_match_debug_info(&match_finder, position.file_id, &matches[0].matched_text());
         panic!("Got {} matches when we expected none: {:#?}", matches.len(), matches);
     }
 }
 
 fn assert_match_failure_reason(pattern: &str, code: &str, snippet: &str, expected_reason: &str) {
-    let (db, file_id) = single_file(code);
-    let mut match_finder = MatchFinder::new(&db);
+    let (db, position) = single_file(code);
+    let mut match_finder = MatchFinder::in_context(&db, position);
     match_finder.add_search_pattern(pattern.parse().unwrap());
     let mut reasons = Vec::new();
-    for d in match_finder.debug_where_text_equal(file_id, snippet) {
+    for d in match_finder.debug_where_text_equal(position.file_id, snippet) {
         if let Some(reason) = d.match_failure_reason() {
             reasons.push(reason.to_owned());
         }
-- 
cgit v1.2.3


From 757f755c29e041fd319af466d7d0418f54cb090a Mon Sep 17 00:00:00 2001
From: David Lattimore <dml@google.com>
Date: Wed, 22 Jul 2020 16:46:29 +1000
Subject: SSR: Match paths based on what they resolve to

Also render template paths appropriately for their context.
---
 crates/ra_ssr/src/lib.rs       |  61 +++++++++++-----
 crates/ra_ssr/src/matching.rs  | 106 ++++++++++++++++++++++++++--
 crates/ra_ssr/src/parsing.rs   |  17 +----
 crates/ra_ssr/src/replacing.rs |  40 ++++++++---
 crates/ra_ssr/src/resolving.rs | 153 +++++++++++++++++++++++++++++++++++++++++
 crates/ra_ssr/src/search.rs    |   8 +--
 crates/ra_ssr/src/tests.rs     | 142 ++++++++++++++++++++++++++++++++++++--
 7 files changed, 469 insertions(+), 58 deletions(-)
 create mode 100644 crates/ra_ssr/src/resolving.rs

(limited to 'crates/ra_ssr/src')

diff --git a/crates/ra_ssr/src/lib.rs b/crates/ra_ssr/src/lib.rs
index a0a5c9762..286619f59 100644
--- a/crates/ra_ssr/src/lib.rs
+++ b/crates/ra_ssr/src/lib.rs
@@ -7,6 +7,7 @@ mod matching;
 mod nester;
 mod parsing;
 mod replacing;
+mod resolving;
 mod search;
 #[macro_use]
 mod errors;
@@ -21,6 +22,7 @@ use hir::Semantics;
 use ra_db::{FileId, FilePosition, FileRange};
 use ra_ide_db::source_change::SourceFileEdit;
 use ra_syntax::{ast, AstNode, SyntaxNode, TextRange};
+use resolving::ResolvedRule;
 use rustc_hash::FxHashMap;
 
 // A structured search replace rule. Create by calling `parse` on a str.
@@ -48,7 +50,9 @@ pub struct SsrMatches {
 pub struct MatchFinder<'db> {
     /// Our source of information about the user's code.
     sema: Semantics<'db, ra_ide_db::RootDatabase>,
-    rules: Vec<parsing::ParsedRule>,
+    rules: Vec<ResolvedRule>,
+    scope: hir::SemanticsScope<'db>,
+    hygiene: hir::Hygiene,
 }
 
 impl<'db> MatchFinder<'db> {
@@ -56,10 +60,24 @@ impl<'db> MatchFinder<'db> {
     /// `lookup_context`.
     pub fn in_context(
         db: &'db ra_ide_db::RootDatabase,
-        _lookup_context: FilePosition,
+        lookup_context: FilePosition,
     ) -> MatchFinder<'db> {
-        // FIXME: Use lookup_context
-        MatchFinder { sema: Semantics::new(db), rules: Vec::new() }
+        let sema = Semantics::new(db);
+        let file = sema.parse(lookup_context.file_id);
+        // Find a node at the requested position, falling back to the whole file.
+        let node = file
+            .syntax()
+            .token_at_offset(lookup_context.offset)
+            .left_biased()
+            .map(|token| token.parent())
+            .unwrap_or_else(|| file.syntax().clone());
+        let scope = sema.scope(&node);
+        MatchFinder {
+            sema: Semantics::new(db),
+            rules: Vec::new(),
+            scope,
+            hygiene: hir::Hygiene::new(db, lookup_context.file_id.into()),
+        }
     }
 
     /// Constructs an instance using the start of the first file in `db` as the lookup context.
@@ -84,8 +102,16 @@ impl<'db> MatchFinder<'db> {
     /// Adds a rule to be applied. The order in which rules are added matters. Earlier rules take
     /// precedence. If a node is matched by an earlier rule, then later rules won't be permitted to
     /// match to it.
-    pub fn add_rule(&mut self, rule: SsrRule) {
-        self.add_parsed_rules(rule.parsed_rules);
+    pub fn add_rule(&mut self, rule: SsrRule) -> Result<(), SsrError> {
+        for parsed_rule in rule.parsed_rules {
+            self.rules.push(ResolvedRule::new(
+                parsed_rule,
+                &self.scope,
+                &self.hygiene,
+                self.rules.len(),
+            )?);
+        }
+        Ok(())
     }
 
     /// Finds matches for all added rules and returns edits for all found matches.
@@ -110,8 +136,16 @@ impl<'db> MatchFinder<'db> {
 
     /// Adds a search pattern. For use if you intend to only call `find_matches_in_file`. If you
     /// intend to do replacement, use `add_rule` instead.
-    pub fn add_search_pattern(&mut self, pattern: SsrPattern) {
-        self.add_parsed_rules(pattern.parsed_rules);
+    pub fn add_search_pattern(&mut self, pattern: SsrPattern) -> Result<(), SsrError> {
+        for parsed_rule in pattern.parsed_rules {
+            self.rules.push(ResolvedRule::new(
+                parsed_rule,
+                &self.scope,
+                &self.hygiene,
+                self.rules.len(),
+            )?);
+        }
+        Ok(())
     }
 
     /// Returns matches for all added rules.
@@ -149,13 +183,6 @@ impl<'db> MatchFinder<'db> {
         res
     }
 
-    fn add_parsed_rules(&mut self, parsed_rules: Vec<parsing::ParsedRule>) {
-        for mut parsed_rule in parsed_rules {
-            parsed_rule.index = self.rules.len();
-            self.rules.push(parsed_rule);
-        }
-    }
-
     fn output_debug_for_nodes_at_range(
         &self,
         node: &SyntaxNode,
@@ -175,7 +202,7 @@ impl<'db> MatchFinder<'db> {
                     // we get lots of noise. If at some point we add support for restricting rules
                     // to a particular kind of thing (e.g. only match type references), then we can
                     // relax this.
-                    if rule.pattern.kind() != node.kind() {
+                    if rule.pattern.node.kind() != node.kind() {
                         continue;
                     }
                     out.push(MatchDebugInfo {
@@ -185,7 +212,7 @@ impl<'db> MatchFinder<'db> {
                                     "Match failed, but no reason was given".to_owned()
                                 }),
                             }),
-                        pattern: rule.pattern.clone(),
+                        pattern: rule.pattern.node.clone(),
                         node: node.clone(),
                     });
                 }
diff --git a/crates/ra_ssr/src/matching.rs b/crates/ra_ssr/src/matching.rs
index a43d57c34..f3cc60c29 100644
--- a/crates/ra_ssr/src/matching.rs
+++ b/crates/ra_ssr/src/matching.rs
@@ -2,7 +2,8 @@
 //! process of matching, placeholder values are recorded.
 
 use crate::{
-    parsing::{Constraint, NodeKind, ParsedRule, Placeholder},
+    parsing::{Constraint, NodeKind, Placeholder},
+    resolving::{ResolvedPattern, ResolvedRule},
     SsrMatches,
 };
 use hir::Semantics;
@@ -51,6 +52,8 @@ pub struct Match {
     pub(crate) rule_index: usize,
     /// The depth of matched_node.
     pub(crate) depth: usize,
+    // Each path in the template rendered for the module in which the match was found.
+    pub(crate) rendered_template_paths: FxHashMap<SyntaxNode, hir::ModPath>,
 }
 
 /// Represents a `$var` in an SSR query.
@@ -86,7 +89,7 @@ pub(crate) struct MatchFailed {
 /// parent module, we don't populate nested matches.
 pub(crate) fn get_match(
     debug_active: bool,
-    rule: &ParsedRule,
+    rule: &ResolvedRule,
     code: &SyntaxNode,
     restrict_range: &Option<FileRange>,
     sema: &Semantics<ra_ide_db::RootDatabase>,
@@ -102,7 +105,7 @@ struct Matcher<'db, 'sema> {
     /// If any placeholders come from anywhere outside of this range, then the match will be
     /// rejected.
     restrict_range: Option<FileRange>,
-    rule: &'sema ParsedRule,
+    rule: &'sema ResolvedRule,
 }
 
 /// Which phase of matching we're currently performing. We do two phases because most attempted
@@ -117,14 +120,14 @@ enum Phase<'a> {
 
 impl<'db, 'sema> Matcher<'db, 'sema> {
     fn try_match(
-        rule: &ParsedRule,
+        rule: &ResolvedRule,
         code: &SyntaxNode,
         restrict_range: &Option<FileRange>,
         sema: &'sema Semantics<'db, ra_ide_db::RootDatabase>,
     ) -> Result<Match, MatchFailed> {
         let match_state = Matcher { sema, restrict_range: restrict_range.clone(), rule };
         // First pass at matching, where we check that node types and idents match.
-        match_state.attempt_match_node(&mut Phase::First, &rule.pattern, code)?;
+        match_state.attempt_match_node(&mut Phase::First, &rule.pattern.node, code)?;
         match_state.validate_range(&sema.original_range(code))?;
         let mut the_match = Match {
             range: sema.original_range(code),
@@ -133,11 +136,19 @@ impl<'db, 'sema> Matcher<'db, 'sema> {
             ignored_comments: Vec::new(),
             rule_index: rule.index,
             depth: 0,
+            rendered_template_paths: FxHashMap::default(),
         };
         // Second matching pass, where we record placeholder matches, ignored comments and maybe do
         // any other more expensive checks that we didn't want to do on the first pass.
-        match_state.attempt_match_node(&mut Phase::Second(&mut the_match), &rule.pattern, code)?;
+        match_state.attempt_match_node(
+            &mut Phase::Second(&mut the_match),
+            &rule.pattern.node,
+            code,
+        )?;
         the_match.depth = sema.ancestors_with_macros(the_match.matched_node.clone()).count();
+        if let Some(template) = &rule.template {
+            the_match.render_template_paths(template, sema)?;
+        }
         Ok(the_match)
     }
 
@@ -195,6 +206,7 @@ impl<'db, 'sema> Matcher<'db, 'sema> {
                 self.attempt_match_record_field_list(phase, pattern, code)
             }
             SyntaxKind::TOKEN_TREE => self.attempt_match_token_tree(phase, pattern, code),
+            SyntaxKind::PATH => self.attempt_match_path(phase, pattern, code),
             _ => self.attempt_match_node_children(phase, pattern, code),
         }
     }
@@ -311,6 +323,64 @@ impl<'db, 'sema> Matcher<'db, 'sema> {
         Ok(())
     }
 
+    /// Paths are matched based on whether they refer to the same thing, even if they're written
+    /// differently.
+    fn attempt_match_path(
+        &self,
+        phase: &mut Phase,
+        pattern: &SyntaxNode,
+        code: &SyntaxNode,
+    ) -> Result<(), MatchFailed> {
+        if let Some(pattern_resolved) = self.rule.pattern.resolved_paths.get(pattern) {
+            let pattern_path = ast::Path::cast(pattern.clone()).unwrap();
+            let code_path = ast::Path::cast(code.clone()).unwrap();
+            if let (Some(pattern_segment), Some(code_segment)) =
+                (pattern_path.segment(), code_path.segment())
+            {
+                // Match everything within the segment except for the name-ref, which is handled
+                // separately via comparing what the path resolves to below.
+                self.attempt_match_opt(
+                    phase,
+                    pattern_segment.type_arg_list(),
+                    code_segment.type_arg_list(),
+                )?;
+                self.attempt_match_opt(
+                    phase,
+                    pattern_segment.param_list(),
+                    code_segment.param_list(),
+                )?;
+            }
+            if matches!(phase, Phase::Second(_)) {
+                let resolution = self
+                    .sema
+                    .resolve_path(&code_path)
+                    .ok_or_else(|| match_error!("Failed to resolve path `{}`", code.text()))?;
+                if pattern_resolved.resolution != resolution {
+                    fail_match!("Pattern had path `{}` code had `{}`", pattern.text(), code.text());
+                }
+            }
+        } else {
+            return self.attempt_match_node_children(phase, pattern, code);
+        }
+        Ok(())
+    }
+
+    fn attempt_match_opt<T: AstNode>(
+        &self,
+        phase: &mut Phase,
+        pattern: Option<T>,
+        code: Option<T>,
+    ) -> Result<(), MatchFailed> {
+        match (pattern, code) {
+            (Some(p), Some(c)) => self.attempt_match_node(phase, &p.syntax(), &c.syntax()),
+            (None, None) => Ok(()),
+            (Some(p), None) => fail_match!("Pattern `{}` had nothing to match", p.syntax().text()),
+            (None, Some(c)) => {
+                fail_match!("Nothing in pattern to match code `{}`", c.syntax().text())
+            }
+        }
+    }
+
     /// We want to allow the records to match in any order, so we have special matching logic for
     /// them.
     fn attempt_match_record_field_list(
@@ -449,6 +519,28 @@ impl<'db, 'sema> Matcher<'db, 'sema> {
     }
 }
 
+impl Match {
+    fn render_template_paths(
+        &mut self,
+        template: &ResolvedPattern,
+        sema: &Semantics<ra_ide_db::RootDatabase>,
+    ) -> Result<(), MatchFailed> {
+        let module = sema
+            .scope(&self.matched_node)
+            .module()
+            .ok_or_else(|| match_error!("Matched node isn't in a module"))?;
+        for (path, resolved_path) in &template.resolved_paths {
+            if let hir::PathResolution::Def(module_def) = resolved_path.resolution {
+                let mod_path = module.find_use_path(sema.db, module_def).ok_or_else(|| {
+                    match_error!("Failed to render template path `{}` at match location")
+                })?;
+                self.rendered_template_paths.insert(path.clone(), mod_path);
+            }
+        }
+        Ok(())
+    }
+}
+
 impl Phase<'_> {
     fn next_non_trivial(&mut self, code_it: &mut SyntaxElementChildren) -> Option<SyntaxElement> {
         loop {
@@ -578,7 +670,7 @@ mod tests {
 
         let (db, position) = crate::tests::single_file(input);
         let mut match_finder = MatchFinder::in_context(&db, position);
-        match_finder.add_rule(rule);
+        match_finder.add_rule(rule).unwrap();
         let matches = match_finder.matches();
         assert_eq!(matches.matches.len(), 1);
         assert_eq!(matches.matches[0].matched_node.text(), "foo(1+2)");
diff --git a/crates/ra_ssr/src/parsing.rs b/crates/ra_ssr/src/parsing.rs
index cf7fb517f..2d6f4e514 100644
--- a/crates/ra_ssr/src/parsing.rs
+++ b/crates/ra_ssr/src/parsing.rs
@@ -7,7 +7,7 @@
 
 use crate::errors::bail;
 use crate::{SsrError, SsrPattern, SsrRule};
-use ra_syntax::{ast, AstNode, SmolStr, SyntaxKind, SyntaxNode, SyntaxToken, T};
+use ra_syntax::{ast, AstNode, SmolStr, SyntaxKind, SyntaxNode, T};
 use rustc_hash::{FxHashMap, FxHashSet};
 use std::str::FromStr;
 
@@ -16,7 +16,6 @@ pub(crate) struct ParsedRule {
     pub(crate) placeholders_by_stand_in: FxHashMap<SmolStr, Placeholder>,
     pub(crate) pattern: SyntaxNode,
     pub(crate) template: Option<SyntaxNode>,
-    pub(crate) index: usize,
 }
 
 #[derive(Debug)]
@@ -93,16 +92,11 @@ impl RuleBuilder {
                 placeholders_by_stand_in: self.placeholders_by_stand_in.clone(),
                 pattern: pattern.syntax().clone(),
                 template: Some(template.syntax().clone()),
-                // For now we give the rule an index of 0. It's given a proper index when the rule
-                // is added to the SsrMatcher. Using an Option<usize>, instead would be slightly
-                // more correct, but we delete this field from ParsedRule in a subsequent commit.
-                index: 0,
             }),
             (Ok(pattern), None) => self.rules.push(ParsedRule {
                 placeholders_by_stand_in: self.placeholders_by_stand_in.clone(),
                 pattern: pattern.syntax().clone(),
                 template: None,
-                index: 0,
             }),
             _ => {}
         }
@@ -171,15 +165,6 @@ impl RawPattern {
     }
 }
 
-impl ParsedRule {
-    pub(crate) fn get_placeholder(&self, token: &SyntaxToken) -> Option<&Placeholder> {
-        if token.kind() != SyntaxKind::IDENT {
-            return None;
-        }
-        self.placeholders_by_stand_in.get(token.text())
-    }
-}
-
 impl FromStr for SsrPattern {
     type Err = SsrError;
 
diff --git a/crates/ra_ssr/src/replacing.rs b/crates/ra_ssr/src/replacing.rs
index f1c5bdf14..4b3f5509c 100644
--- a/crates/ra_ssr/src/replacing.rs
+++ b/crates/ra_ssr/src/replacing.rs
@@ -1,9 +1,9 @@
 //! Code for applying replacement templates for matches that have previously been found.
 
 use crate::matching::Var;
-use crate::{parsing::ParsedRule, Match, SsrMatches};
-use ra_syntax::ast::AstToken;
-use ra_syntax::{SyntaxElement, SyntaxNode, SyntaxToken, TextSize};
+use crate::{resolving::ResolvedRule, Match, SsrMatches};
+use ra_syntax::ast::{self, AstToken};
+use ra_syntax::{SyntaxElement, SyntaxKind, SyntaxNode, SyntaxToken, TextSize};
 use ra_text_edit::TextEdit;
 
 /// Returns a text edit that will replace each match in `matches` with its corresponding replacement
@@ -12,7 +12,7 @@ use ra_text_edit::TextEdit;
 pub(crate) fn matches_to_edit(
     matches: &SsrMatches,
     file_src: &str,
-    rules: &[ParsedRule],
+    rules: &[ResolvedRule],
 ) -> TextEdit {
     matches_to_edit_at_offset(matches, file_src, 0.into(), rules)
 }
@@ -21,7 +21,7 @@ fn matches_to_edit_at_offset(
     matches: &SsrMatches,
     file_src: &str,
     relative_start: TextSize,
-    rules: &[ParsedRule],
+    rules: &[ResolvedRule],
 ) -> TextEdit {
     let mut edit_builder = ra_text_edit::TextEditBuilder::default();
     for m in &matches.matches {
@@ -36,11 +36,11 @@ fn matches_to_edit_at_offset(
 struct ReplacementRenderer<'a> {
     match_info: &'a Match,
     file_src: &'a str,
-    rules: &'a [ParsedRule],
-    rule: &'a ParsedRule,
+    rules: &'a [ResolvedRule],
+    rule: &'a ResolvedRule,
 }
 
-fn render_replace(match_info: &Match, file_src: &str, rules: &[ParsedRule]) -> String {
+fn render_replace(match_info: &Match, file_src: &str, rules: &[ResolvedRule]) -> String {
     let mut out = String::new();
     let rule = &rules[match_info.rule_index];
     let template = rule
@@ -48,7 +48,7 @@ fn render_replace(match_info: &Match, file_src: &str, rules: &[ParsedRule]) -> S
         .as_ref()
         .expect("You called MatchFinder::edits after calling MatchFinder::add_search_pattern");
     let renderer = ReplacementRenderer { match_info, file_src, rules, rule };
-    renderer.render_node_children(&template, &mut out);
+    renderer.render_node(&template.node, &mut out);
     for comment in &match_info.ignored_comments {
         out.push_str(&comment.syntax().to_string());
     }
@@ -68,11 +68,31 @@ impl ReplacementRenderer<'_> {
                 self.render_token(&token, out);
             }
             SyntaxElement::Node(child_node) => {
-                self.render_node_children(&child_node, out);
+                self.render_node(&child_node, out);
             }
         }
     }
 
+    fn render_node(&self, node: &SyntaxNode, out: &mut String) {
+        use ra_syntax::ast::AstNode;
+        if let Some(mod_path) = self.match_info.rendered_template_paths.get(&node) {
+            out.push_str(&mod_path.to_string());
+            // Emit everything except for the segment's name-ref, since we already effectively
+            // emitted that as part of `mod_path`.
+            if let Some(path) = ast::Path::cast(node.clone()) {
+                if let Some(segment) = path.segment() {
+                    for node_or_token in segment.syntax().children_with_tokens() {
+                        if node_or_token.kind() != SyntaxKind::NAME_REF {
+                            self.render_node_or_token(&node_or_token, out);
+                        }
+                    }
+                }
+            }
+        } else {
+            self.render_node_children(&node, out);
+        }
+    }
+
     fn render_token(&self, token: &SyntaxToken, out: &mut String) {
         if let Some(placeholder) = self.rule.get_placeholder(&token) {
             if let Some(placeholder_value) =
diff --git a/crates/ra_ssr/src/resolving.rs b/crates/ra_ssr/src/resolving.rs
new file mode 100644
index 000000000..e9d052111
--- /dev/null
+++ b/crates/ra_ssr/src/resolving.rs
@@ -0,0 +1,153 @@
+//! This module is responsible for resolving paths within rules.
+
+use crate::errors::error;
+use crate::{parsing, SsrError};
+use parsing::Placeholder;
+use ra_syntax::{ast, SmolStr, SyntaxKind, SyntaxNode, SyntaxToken};
+use rustc_hash::{FxHashMap, FxHashSet};
+use test_utils::mark;
+
+pub(crate) struct ResolvedRule {
+    pub(crate) pattern: ResolvedPattern,
+    pub(crate) template: Option<ResolvedPattern>,
+    pub(crate) index: usize,
+}
+
+pub(crate) struct ResolvedPattern {
+    pub(crate) placeholders_by_stand_in: FxHashMap<SmolStr, parsing::Placeholder>,
+    pub(crate) node: SyntaxNode,
+    // Paths in `node` that we've resolved.
+    pub(crate) resolved_paths: FxHashMap<SyntaxNode, ResolvedPath>,
+}
+
+pub(crate) struct ResolvedPath {
+    pub(crate) resolution: hir::PathResolution,
+}
+
+impl ResolvedRule {
+    pub(crate) fn new(
+        rule: parsing::ParsedRule,
+        scope: &hir::SemanticsScope,
+        hygiene: &hir::Hygiene,
+        index: usize,
+    ) -> Result<ResolvedRule, SsrError> {
+        let resolver =
+            Resolver { scope, hygiene, placeholders_by_stand_in: rule.placeholders_by_stand_in };
+        let resolved_template = if let Some(template) = rule.template {
+            Some(resolver.resolve_pattern_tree(template)?)
+        } else {
+            None
+        };
+        Ok(ResolvedRule {
+            pattern: resolver.resolve_pattern_tree(rule.pattern)?,
+            template: resolved_template,
+            index,
+        })
+    }
+
+    pub(crate) fn get_placeholder(&self, token: &SyntaxToken) -> Option<&Placeholder> {
+        if token.kind() != SyntaxKind::IDENT {
+            return None;
+        }
+        self.pattern.placeholders_by_stand_in.get(token.text())
+    }
+}
+
+struct Resolver<'a, 'db> {
+    scope: &'a hir::SemanticsScope<'db>,
+    hygiene: &'a hir::Hygiene,
+    placeholders_by_stand_in: FxHashMap<SmolStr, parsing::Placeholder>,
+}
+
+impl Resolver<'_, '_> {
+    fn resolve_pattern_tree(&self, pattern: SyntaxNode) -> Result<ResolvedPattern, SsrError> {
+        let mut resolved_paths = FxHashMap::default();
+        self.resolve(pattern.clone(), &mut resolved_paths)?;
+        Ok(ResolvedPattern {
+            node: pattern,
+            resolved_paths,
+            placeholders_by_stand_in: self.placeholders_by_stand_in.clone(),
+        })
+    }
+
+    fn resolve(
+        &self,
+        node: SyntaxNode,
+        resolved_paths: &mut FxHashMap<SyntaxNode, ResolvedPath>,
+    ) -> Result<(), SsrError> {
+        use ra_syntax::ast::AstNode;
+        if let Some(path) = ast::Path::cast(node.clone()) {
+            // Check if this is an appropriate place in the path to resolve. If the path is
+            // something like `a::B::<i32>::c` then we want to resolve `a::B`. If the path contains
+            // a placeholder. e.g. `a::$b::c` then we want to resolve `a`.
+            if !path_contains_type_arguments(path.qualifier())
+                && !self.path_contains_placeholder(&path)
+            {
+                let resolution = self
+                    .resolve_path(&path)
+                    .ok_or_else(|| error!("Failed to resolve path `{}`", node.text()))?;
+                resolved_paths.insert(node, ResolvedPath { resolution });
+                return Ok(());
+            }
+        }
+        for node in node.children() {
+            self.resolve(node, resolved_paths)?;
+        }
+        Ok(())
+    }
+
+    /// Returns whether `path` contains a placeholder, but ignores any placeholders within type
+    /// arguments.
+    fn path_contains_placeholder(&self, path: &ast::Path) -> bool {
+        if let Some(segment) = path.segment() {
+            if let Some(name_ref) = segment.name_ref() {
+                if self.placeholders_by_stand_in.contains_key(name_ref.text()) {
+                    return true;
+                }
+            }
+        }
+        if let Some(qualifier) = path.qualifier() {
+            return self.path_contains_placeholder(&qualifier);
+        }
+        false
+    }
+
+    fn resolve_path(&self, path: &ast::Path) -> Option<hir::PathResolution> {
+        let hir_path = hir::Path::from_src(path.clone(), self.hygiene)?;
+        // First try resolving the whole path. This will work for things like
+        // `std::collections::HashMap`, but will fail for things like
+        // `std::collections::HashMap::new`.
+        if let Some(resolution) = self.scope.resolve_hir_path(&hir_path) {
+            return Some(resolution);
+        }
+        // Resolution failed, try resolving the qualifier (e.g. `std::collections::HashMap` and if
+        // that succeeds, then iterate through the candidates on the resolved type with the provided
+        // name.
+        let resolved_qualifier = self.scope.resolve_hir_path_qualifier(&hir_path.qualifier()?)?;
+        if let hir::PathResolution::Def(hir::ModuleDef::Adt(adt)) = resolved_qualifier {
+            adt.ty(self.scope.db).iterate_path_candidates(
+                self.scope.db,
+                self.scope.module()?.krate(),
+                &FxHashSet::default(),
+                Some(hir_path.segments().last()?.name),
+                |_ty, assoc_item| Some(hir::PathResolution::AssocItem(assoc_item)),
+            )
+        } else {
+            None
+        }
+    }
+}
+
+/// Returns whether `path` or any of its qualifiers contains type arguments.
+fn path_contains_type_arguments(path: Option<ast::Path>) -> bool {
+    if let Some(path) = path {
+        if let Some(segment) = path.segment() {
+            if segment.type_arg_list().is_some() {
+                mark::hit!(type_arguments_within_path);
+                return true;
+            }
+        }
+        return path_contains_type_arguments(path.qualifier());
+    }
+    false
+}
diff --git a/crates/ra_ssr/src/search.rs b/crates/ra_ssr/src/search.rs
index a28e9f341..ccc2d544a 100644
--- a/crates/ra_ssr/src/search.rs
+++ b/crates/ra_ssr/src/search.rs
@@ -1,6 +1,6 @@
 //! Searching for matches.
 
-use crate::{matching, parsing::ParsedRule, Match, MatchFinder};
+use crate::{matching, resolving::ResolvedRule, Match, MatchFinder};
 use ra_db::FileRange;
 use ra_syntax::{ast, AstNode, SyntaxNode};
 
@@ -8,13 +8,13 @@ impl<'db> MatchFinder<'db> {
     /// Adds all matches for `rule` to `matches_out`. Matches may overlap in ways that make
     /// replacement impossible, so further processing is required in order to properly nest matches
     /// and remove overlapping matches. This is done in the `nesting` module.
-    pub(crate) fn find_matches_for_rule(&self, rule: &ParsedRule, matches_out: &mut Vec<Match>) {
+    pub(crate) fn find_matches_for_rule(&self, rule: &ResolvedRule, matches_out: &mut Vec<Match>) {
         // FIXME: Use resolved paths in the pattern to find places to search instead of always
         // scanning every node.
         self.slow_scan(rule, matches_out);
     }
 
-    fn slow_scan(&self, rule: &ParsedRule, matches_out: &mut Vec<Match>) {
+    fn slow_scan(&self, rule: &ResolvedRule, matches_out: &mut Vec<Match>) {
         use ra_db::SourceDatabaseExt;
         use ra_ide_db::symbol_index::SymbolsDatabase;
         for &root in self.sema.db.local_roots().iter() {
@@ -30,7 +30,7 @@ impl<'db> MatchFinder<'db> {
     fn slow_scan_node(
         &self,
         code: &SyntaxNode,
-        rule: &ParsedRule,
+        rule: &ResolvedRule,
         restrict_range: &Option<FileRange>,
         matches_out: &mut Vec<Match>,
     ) {
diff --git a/crates/ra_ssr/src/tests.rs b/crates/ra_ssr/src/tests.rs
index 63d527894..33742dc8e 100644
--- a/crates/ra_ssr/src/tests.rs
+++ b/crates/ra_ssr/src/tests.rs
@@ -85,7 +85,7 @@ fn assert_ssr_transforms(rules: &[&str], input: &str, expected: Expect) {
     let mut match_finder = MatchFinder::in_context(&db, position);
     for rule in rules {
         let rule: SsrRule = rule.parse().unwrap();
-        match_finder.add_rule(rule);
+        match_finder.add_rule(rule).unwrap();
     }
     let edits = match_finder.edits();
     if edits.is_empty() {
@@ -114,7 +114,7 @@ fn print_match_debug_info(match_finder: &MatchFinder, file_id: FileId, snippet:
 fn assert_matches(pattern: &str, code: &str, expected: &[&str]) {
     let (db, position) = single_file(code);
     let mut match_finder = MatchFinder::in_context(&db, position);
-    match_finder.add_search_pattern(pattern.parse().unwrap());
+    match_finder.add_search_pattern(pattern.parse().unwrap()).unwrap();
     let matched_strings: Vec<String> =
         match_finder.matches().flattened().matches.iter().map(|m| m.matched_text()).collect();
     if matched_strings != expected && !expected.is_empty() {
@@ -126,7 +126,7 @@ fn assert_matches(pattern: &str, code: &str, expected: &[&str]) {
 fn assert_no_match(pattern: &str, code: &str) {
     let (db, position) = single_file(code);
     let mut match_finder = MatchFinder::in_context(&db, position);
-    match_finder.add_search_pattern(pattern.parse().unwrap());
+    match_finder.add_search_pattern(pattern.parse().unwrap()).unwrap();
     let matches = match_finder.matches().flattened().matches;
     if !matches.is_empty() {
         print_match_debug_info(&match_finder, position.file_id, &matches[0].matched_text());
@@ -137,7 +137,7 @@ fn assert_no_match(pattern: &str, code: &str) {
 fn assert_match_failure_reason(pattern: &str, code: &str, snippet: &str, expected_reason: &str) {
     let (db, position) = single_file(code);
     let mut match_finder = MatchFinder::in_context(&db, position);
-    match_finder.add_search_pattern(pattern.parse().unwrap());
+    match_finder.add_search_pattern(pattern.parse().unwrap()).unwrap();
     let mut reasons = Vec::new();
     for d in match_finder.debug_where_text_equal(position.file_id, snippet) {
         if let Some(reason) = d.match_failure_reason() {
@@ -350,6 +350,60 @@ fn match_pattern() {
     assert_matches("Some($a)", "struct Some(); fn f() {if let Some(x) = foo() {}}", &["Some(x)"]);
 }
 
+// If our pattern has a full path, e.g. a::b::c() and the code has c(), but c resolves to
+// a::b::c, then we should match.
+#[test]
+fn match_fully_qualified_fn_path() {
+    let code = r#"
+        mod a {
+            pub mod b {
+                pub fn c(_: i32) {}
+            }
+        }
+        use a::b::c;
+        fn f1() {
+            c(42);
+        }
+        "#;
+    assert_matches("a::b::c($a)", code, &["c(42)"]);
+}
+
+#[test]
+fn match_resolved_type_name() {
+    let code = r#"
+        mod m1 {
+            pub mod m2 {
+                pub trait Foo<T> {}
+            }
+        }
+        mod m3 {
+            trait Foo<T> {}
+            fn f1(f: Option<&dyn Foo<bool>>) {}
+        }
+        mod m4 {
+            use crate::m1::m2::Foo;
+            fn f1(f: Option<&dyn Foo<i32>>) {}
+        }
+        "#;
+    assert_matches("m1::m2::Foo<$t>", code, &["Foo<i32>"]);
+}
+
+#[test]
+fn type_arguments_within_path() {
+    mark::check!(type_arguments_within_path);
+    let code = r#"
+        mod foo {
+            pub struct Bar<T> {t: T}
+            impl<T> Bar<T> {
+                pub fn baz() {}
+            }
+        }
+        fn f1() {foo::Bar::<i32>::baz();}
+        "#;
+    assert_no_match("foo::Bar::<i64>::baz()", code);
+    assert_matches("foo::Bar::<i32>::baz()", code, &["foo::Bar::<i32>::baz()"]);
+}
+
 #[test]
 fn literal_constraint() {
     mark::check!(literal_constraint);
@@ -482,6 +536,86 @@ fn replace_associated_function_call() {
     );
 }
 
+#[test]
+fn replace_path_in_different_contexts() {
+    // Note the <|> inside module a::b which marks the point where the rule is interpreted. We
+    // replace foo with bar, but both need different path qualifiers in different contexts. In f4,
+    // foo is unqualified because of a use statement, however the replacement needs to be fully
+    // qualified.
+    assert_ssr_transform(
+        "c::foo() ==>> c::bar()",
+        r#"
+            mod a {
+                pub mod b {<|>
+                    pub mod c {
+                        pub fn foo() {}
+                        pub fn bar() {}
+                        fn f1() { foo() }
+                    }
+                    fn f2() { c::foo() }
+                }
+                fn f3() { b::c::foo() }
+            }
+            use a::b::c::foo;
+            fn f4() { foo() }
+            "#,
+        expect![[r#"
+            mod a {
+                pub mod b {
+                    pub mod c {
+                        pub fn foo() {}
+                        pub fn bar() {}
+                        fn f1() { bar() }
+                    }
+                    fn f2() { c::bar() }
+                }
+                fn f3() { b::c::bar() }
+            }
+            use a::b::c::foo;
+            fn f4() { a::b::c::bar() }
+            "#]],
+    );
+}
+
+#[test]
+fn replace_associated_function_with_generics() {
+    assert_ssr_transform(
+        "c::Foo::<$a>::new() ==>> d::Bar::<$a>::default()",
+        r#"
+            mod c {
+                pub struct Foo<T> {v: T}
+                impl<T> Foo<T> { pub fn new() {} }
+                fn f1() {
+                    Foo::<i32>::new();
+                }
+            }
+            mod d {
+                pub struct Bar<T> {v: T}
+                impl<T> Bar<T> { pub fn default() {} }
+                fn f1() {
+                    super::c::Foo::<i32>::new();
+                }
+            }
+            "#,
+        expect![[r#"
+            mod c {
+                pub struct Foo<T> {v: T}
+                impl<T> Foo<T> { pub fn new() {} }
+                fn f1() {
+                    crate::d::Bar::<i32>::default();
+                }
+            }
+            mod d {
+                pub struct Bar<T> {v: T}
+                impl<T> Bar<T> { pub fn default() {} }
+                fn f1() {
+                    Bar::<i32>::default();
+                }
+            }
+            "#]],
+    );
+}
+
 #[test]
 fn replace_type() {
     assert_ssr_transform(
-- 
cgit v1.2.3


From 63f500b0ee55443a52f078060004c911a7532a14 Mon Sep 17 00:00:00 2001
From: David Lattimore <dml@google.com>
Date: Wed, 22 Jul 2020 14:01:21 +1000
Subject: SSR: Use Definition::find_usages to speed up matching.

When the search pattern contains a path, this substantially speeds up finding matches, especially if the path references a private item.
---
 crates/ra_ssr/src/lib.rs       |   3 +-
 crates/ra_ssr/src/resolving.rs |   8 ++-
 crates/ra_ssr/src/search.rs    | 131 +++++++++++++++++++++++++++++++++++++++--
 3 files changed, 133 insertions(+), 9 deletions(-)

(limited to 'crates/ra_ssr/src')

diff --git a/crates/ra_ssr/src/lib.rs b/crates/ra_ssr/src/lib.rs
index 286619f59..5a71d4f31 100644
--- a/crates/ra_ssr/src/lib.rs
+++ b/crates/ra_ssr/src/lib.rs
@@ -151,8 +151,9 @@ impl<'db> MatchFinder<'db> {
     /// Returns matches for all added rules.
     pub fn matches(&self) -> SsrMatches {
         let mut matches = Vec::new();
+        let mut usage_cache = search::UsageCache::default();
         for rule in &self.rules {
-            self.find_matches_for_rule(rule, &mut matches);
+            self.find_matches_for_rule(rule, &mut usage_cache, &mut matches);
         }
         nester::nest_and_remove_collisions(matches, &self.sema)
     }
diff --git a/crates/ra_ssr/src/resolving.rs b/crates/ra_ssr/src/resolving.rs
index e9d052111..63fd217ce 100644
--- a/crates/ra_ssr/src/resolving.rs
+++ b/crates/ra_ssr/src/resolving.rs
@@ -22,6 +22,7 @@ pub(crate) struct ResolvedPattern {
 
 pub(crate) struct ResolvedPath {
     pub(crate) resolution: hir::PathResolution,
+    pub(crate) depth: u32,
 }
 
 impl ResolvedRule {
@@ -62,7 +63,7 @@ struct Resolver<'a, 'db> {
 impl Resolver<'_, '_> {
     fn resolve_pattern_tree(&self, pattern: SyntaxNode) -> Result<ResolvedPattern, SsrError> {
         let mut resolved_paths = FxHashMap::default();
-        self.resolve(pattern.clone(), &mut resolved_paths)?;
+        self.resolve(pattern.clone(), 0, &mut resolved_paths)?;
         Ok(ResolvedPattern {
             node: pattern,
             resolved_paths,
@@ -73,6 +74,7 @@ impl Resolver<'_, '_> {
     fn resolve(
         &self,
         node: SyntaxNode,
+        depth: u32,
         resolved_paths: &mut FxHashMap<SyntaxNode, ResolvedPath>,
     ) -> Result<(), SsrError> {
         use ra_syntax::ast::AstNode;
@@ -86,12 +88,12 @@ impl Resolver<'_, '_> {
                 let resolution = self
                     .resolve_path(&path)
                     .ok_or_else(|| error!("Failed to resolve path `{}`", node.text()))?;
-                resolved_paths.insert(node, ResolvedPath { resolution });
+                resolved_paths.insert(node, ResolvedPath { resolution, depth });
                 return Ok(());
             }
         }
         for node in node.children() {
-            self.resolve(node, resolved_paths)?;
+            self.resolve(node, depth + 1, resolved_paths)?;
         }
         Ok(())
     }
diff --git a/crates/ra_ssr/src/search.rs b/crates/ra_ssr/src/search.rs
index ccc2d544a..9a4e35e96 100644
--- a/crates/ra_ssr/src/search.rs
+++ b/crates/ra_ssr/src/search.rs
@@ -1,17 +1,106 @@
 //! Searching for matches.
 
-use crate::{matching, resolving::ResolvedRule, Match, MatchFinder};
+use crate::{
+    matching,
+    resolving::{ResolvedPath, ResolvedPattern, ResolvedRule},
+    Match, MatchFinder,
+};
 use ra_db::FileRange;
+use ra_ide_db::{
+    defs::Definition,
+    search::{Reference, SearchScope},
+};
 use ra_syntax::{ast, AstNode, SyntaxNode};
 
+/// A cache for the results of find_usages. This is for when we have multiple patterns that have the
+/// same path. e.g. if the pattern was `foo::Bar` that can parse as a path, an expression, a type
+/// and as a pattern. In each, the usages of `foo::Bar` are the same and we'd like to avoid finding
+/// them more than once.
+#[derive(Default)]
+pub(crate) struct UsageCache {
+    usages: Vec<(Definition, Vec<Reference>)>,
+}
+
 impl<'db> MatchFinder<'db> {
     /// Adds all matches for `rule` to `matches_out`. Matches may overlap in ways that make
     /// replacement impossible, so further processing is required in order to properly nest matches
     /// and remove overlapping matches. This is done in the `nesting` module.
-    pub(crate) fn find_matches_for_rule(&self, rule: &ResolvedRule, matches_out: &mut Vec<Match>) {
-        // FIXME: Use resolved paths in the pattern to find places to search instead of always
-        // scanning every node.
-        self.slow_scan(rule, matches_out);
+    pub(crate) fn find_matches_for_rule(
+        &self,
+        rule: &ResolvedRule,
+        usage_cache: &mut UsageCache,
+        matches_out: &mut Vec<Match>,
+    ) {
+        if pick_path_for_usages(&rule.pattern).is_none() {
+            self.slow_scan(rule, matches_out);
+            return;
+        }
+        self.find_matches_for_pattern_tree(rule, &rule.pattern, usage_cache, matches_out);
+    }
+
+    fn find_matches_for_pattern_tree(
+        &self,
+        rule: &ResolvedRule,
+        pattern: &ResolvedPattern,
+        usage_cache: &mut UsageCache,
+        matches_out: &mut Vec<Match>,
+    ) {
+        if let Some(first_path) = pick_path_for_usages(pattern) {
+            let definition: Definition = first_path.resolution.clone().into();
+            for reference in self.find_usages(usage_cache, definition) {
+                let file = self.sema.parse(reference.file_range.file_id);
+                if let Some(path) = self.sema.find_node_at_offset_with_descend::<ast::Path>(
+                    file.syntax(),
+                    reference.file_range.range.start(),
+                ) {
+                    if let Some(node_to_match) = self
+                        .sema
+                        .ancestors_with_macros(path.syntax().clone())
+                        .skip(first_path.depth as usize)
+                        .next()
+                    {
+                        if let Ok(m) =
+                            matching::get_match(false, rule, &node_to_match, &None, &self.sema)
+                        {
+                            matches_out.push(m);
+                        }
+                    }
+                }
+            }
+        }
+    }
+
+    fn find_usages<'a>(
+        &self,
+        usage_cache: &'a mut UsageCache,
+        definition: Definition,
+    ) -> &'a [Reference] {
+        // Logically if a lookup succeeds we should just return it. Unfortunately returning it would
+        // extend the lifetime of the borrow, then we wouldn't be able to do the insertion on a
+        // cache miss. This is a limitation of NLL and is fixed with Polonius. For now we do two
+        // lookups in the case of a cache hit.
+        if usage_cache.find(&definition).is_none() {
+            let usages = definition.find_usages(&self.sema, Some(self.search_scope()));
+            usage_cache.usages.push((definition, usages));
+            return &usage_cache.usages.last().unwrap().1;
+        }
+        usage_cache.find(&definition).unwrap()
+    }
+
+    /// Returns the scope within which we want to search. We don't want un unrestricted search
+    /// scope, since we don't want to find references in external dependencies.
+    fn search_scope(&self) -> SearchScope {
+        // FIXME: We should ideally have a test that checks that we edit local roots and not library
+        // roots. This probably would require some changes to fixtures, since currently everything
+        // seems to get put into a single source root.
+        use ra_db::SourceDatabaseExt;
+        use ra_ide_db::symbol_index::SymbolsDatabase;
+        let mut files = Vec::new();
+        for &root in self.sema.db.local_roots().iter() {
+            let sr = self.sema.db.source_root(root);
+            files.extend(sr.iter());
+        }
+        SearchScope::files(&files)
     }
 
     fn slow_scan(&self, rule: &ResolvedRule, matches_out: &mut Vec<Match>) {
@@ -59,3 +148,35 @@ impl<'db> MatchFinder<'db> {
         }
     }
 }
+
+impl UsageCache {
+    fn find(&mut self, definition: &Definition) -> Option<&[Reference]> {
+        // We expect a very small number of cache entries (generally 1), so a linear scan should be
+        // fast enough and avoids the need to implement Hash for Definition.
+        for (d, refs) in &self.usages {
+            if d == definition {
+                return Some(refs);
+            }
+        }
+        None
+    }
+}
+
+/// Returns a path that's suitable for path resolution. We exclude builtin types, since they aren't
+/// something that we can find references to. We then somewhat arbitrarily pick the path that is the
+/// longest as this is hopefully more likely to be less common, making it faster to find.
+fn pick_path_for_usages(pattern: &ResolvedPattern) -> Option<&ResolvedPath> {
+    // FIXME: Take the scope of the resolved path into account. e.g. if there are any paths that are
+    // private to the current module, then we definitely would want to pick them over say a path
+    // from std. Possibly we should go further than this and intersect the search scopes for all
+    // resolved paths then search only in that scope.
+    pattern
+        .resolved_paths
+        .iter()
+        .filter(|(_, p)| {
+            !matches!(p.resolution, hir::PathResolution::Def(hir::ModuleDef::BuiltinType(_)))
+        })
+        .map(|(node, resolved)| (node.text().len(), resolved))
+        .max_by(|(a, _), (b, _)| a.cmp(b))
+        .map(|(_, resolved)| resolved)
+}
-- 
cgit v1.2.3


From 8d09ab86edfc01405fd0045bef82e0642efd5f01 Mon Sep 17 00:00:00 2001
From: David Lattimore <dml@google.com>
Date: Thu, 23 Jul 2020 21:28:31 +1000
Subject: SSR: Disable matching within use declarations

It currently does the wrong thing when the use declaration contains
braces.
---
 crates/ra_ssr/src/search.rs | 29 ++++++++++++++++++++++++++++-
 crates/ra_ssr/src/tests.rs  | 23 +++++++++++++++++++++++
 2 files changed, 51 insertions(+), 1 deletion(-)

(limited to 'crates/ra_ssr/src')

diff --git a/crates/ra_ssr/src/search.rs b/crates/ra_ssr/src/search.rs
index 9a4e35e96..141e7d026 100644
--- a/crates/ra_ssr/src/search.rs
+++ b/crates/ra_ssr/src/search.rs
@@ -10,7 +10,8 @@ use ra_ide_db::{
     defs::Definition,
     search::{Reference, SearchScope},
 };
-use ra_syntax::{ast, AstNode, SyntaxNode};
+use ra_syntax::{ast, AstNode, SyntaxKind, SyntaxNode};
+use test_utils::mark;
 
 /// A cache for the results of find_usages. This is for when we have multiple patterns that have the
 /// same path. e.g. if the pattern was `foo::Bar` that can parse as a path, an expression, a type
@@ -59,6 +60,10 @@ impl<'db> MatchFinder<'db> {
                         .skip(first_path.depth as usize)
                         .next()
                     {
+                        if !is_search_permitted_ancestors(&node_to_match) {
+                            mark::hit!(use_declaration_with_braces);
+                            continue;
+                        }
                         if let Ok(m) =
                             matching::get_match(false, rule, &node_to_match, &None, &self.sema)
                         {
@@ -123,6 +128,9 @@ impl<'db> MatchFinder<'db> {
         restrict_range: &Option<FileRange>,
         matches_out: &mut Vec<Match>,
     ) {
+        if !is_search_permitted(code) {
+            return;
+        }
         if let Ok(m) = matching::get_match(false, rule, &code, restrict_range, &self.sema) {
             matches_out.push(m);
         }
@@ -149,6 +157,25 @@ impl<'db> MatchFinder<'db> {
     }
 }
 
+/// Returns whether we support matching within `node` and all of its ancestors.
+fn is_search_permitted_ancestors(node: &SyntaxNode) -> bool {
+    if let Some(parent) = node.parent() {
+        if !is_search_permitted_ancestors(&parent) {
+            return false;
+        }
+    }
+    is_search_permitted(node)
+}
+
+/// Returns whether we support matching within this kind of node.
+fn is_search_permitted(node: &SyntaxNode) -> bool {
+    // FIXME: Properly handle use declarations. At the moment, if our search pattern is `foo::bar`
+    // and the code is `use foo::{baz, bar}`, we'll match `bar`, since it resolves to `foo::bar`.
+    // However we'll then replace just the part we matched `bar`. We probably need to instead remove
+    // `bar` and insert a new use declaration.
+    node.kind() != SyntaxKind::USE_ITEM
+}
+
 impl UsageCache {
     fn find(&mut self, definition: &Definition) -> Option<&[Reference]> {
         // We expect a very small number of cache entries (generally 1), so a linear scan should be
diff --git a/crates/ra_ssr/src/tests.rs b/crates/ra_ssr/src/tests.rs
index 33742dc8e..f564c6129 100644
--- a/crates/ra_ssr/src/tests.rs
+++ b/crates/ra_ssr/src/tests.rs
@@ -804,3 +804,26 @@ fn overlapping_possible_matches() {
         &["foo(foo(42))", "foo(foo(foo(foo(42))))"],
     );
 }
+
+#[test]
+fn use_declaration_with_braces() {
+    // It would be OK for a path rule to match and alter a use declaration. We shouldn't mess it up
+    // though. In particular, we must not change `use foo::{baz, bar}` to `use foo::{baz,
+    // foo2::bar2}`.
+    mark::check!(use_declaration_with_braces);
+    assert_ssr_transform(
+        "foo::bar ==>> foo2::bar2",
+        r#"
+        mod foo { pub fn bar() {} pub fn baz() {} }
+        mod foo2 { pub fn bar2() {} }
+        use foo::{baz, bar};
+        fn main() { bar() }
+        "#,
+        expect![["
+        mod foo { pub fn bar() {} pub fn baz() {} }
+        mod foo2 { pub fn bar2() {} }
+        use foo::{baz, bar};
+        fn main() { foo2::bar2() }
+        "]],
+    )
+}
-- 
cgit v1.2.3


From 3dac31fe80b9d7279e87b94615b0d55805e83412 Mon Sep 17 00:00:00 2001
From: David Lattimore <dml@google.com>
Date: Fri, 24 Jul 2020 20:53:48 +1000
Subject: SSR: Allow function calls to match method calls

This differs from how this used to work before I removed it in that:
a) It's only one direction. Function calls in the pattern can match
method calls in the code, but not the other way around.
b) We now check that the function call in the pattern resolves to the
same function as the method call in the code.

The lack of (b) was the reason I felt the need to remove the feature
before.
---
 crates/ra_ssr/src/lib.rs       |  8 ++++--
 crates/ra_ssr/src/matching.rs  | 42 +++++++++++++++++++++++++--
 crates/ra_ssr/src/resolving.rs | 18 ++++++++++++
 crates/ra_ssr/src/search.rs    | 65 ++++++++++++++++++++++++++++--------------
 crates/ra_ssr/src/tests.rs     | 58 +++++++++++++++++++++++++++++++++++++
 5 files changed, 166 insertions(+), 25 deletions(-)

(limited to 'crates/ra_ssr/src')

diff --git a/crates/ra_ssr/src/lib.rs b/crates/ra_ssr/src/lib.rs
index 5a71d4f31..2fb326b45 100644
--- a/crates/ra_ssr/src/lib.rs
+++ b/crates/ra_ssr/src/lib.rs
@@ -202,8 +202,12 @@ impl<'db> MatchFinder<'db> {
                     // For now we ignore rules that have a different kind than our node, otherwise
                     // we get lots of noise. If at some point we add support for restricting rules
                     // to a particular kind of thing (e.g. only match type references), then we can
-                    // relax this.
-                    if rule.pattern.node.kind() != node.kind() {
+                    // relax this. We special-case expressions, since function calls can match
+                    // method calls.
+                    if rule.pattern.node.kind() != node.kind()
+                        && !(ast::Expr::can_cast(rule.pattern.node.kind())
+                            && ast::Expr::can_cast(node.kind()))
+                    {
                         continue;
                     }
                     out.push(MatchDebugInfo {
diff --git a/crates/ra_ssr/src/matching.rs b/crates/ra_ssr/src/matching.rs
index f3cc60c29..4862622bd 100644
--- a/crates/ra_ssr/src/matching.rs
+++ b/crates/ra_ssr/src/matching.rs
@@ -189,10 +189,17 @@ impl<'db, 'sema> Matcher<'db, 'sema> {
             }
             return Ok(());
         }
-        // Non-placeholders.
+        // We allow a UFCS call to match a method call, provided they resolve to the same function.
+        if let Some(pattern_function) = self.rule.pattern.ufcs_function_calls.get(pattern) {
+            if let (Some(pattern), Some(code)) =
+                (ast::CallExpr::cast(pattern.clone()), ast::MethodCallExpr::cast(code.clone()))
+            {
+                return self.attempt_match_ufcs(phase, &pattern, &code, *pattern_function);
+            }
+        }
         if pattern.kind() != code.kind() {
             fail_match!(
-                "Pattern had a `{}` ({:?}), code had `{}` ({:?})",
+                "Pattern had `{}` ({:?}), code had `{}` ({:?})",
                 pattern.text(),
                 pattern.kind(),
                 code.text(),
@@ -514,6 +521,37 @@ impl<'db, 'sema> Matcher<'db, 'sema> {
         Ok(())
     }
 
+    fn attempt_match_ufcs(
+        &self,
+        phase: &mut Phase,
+        pattern: &ast::CallExpr,
+        code: &ast::MethodCallExpr,
+        pattern_function: hir::Function,
+    ) -> Result<(), MatchFailed> {
+        use ast::ArgListOwner;
+        let code_resolved_function = self
+            .sema
+            .resolve_method_call(code)
+            .ok_or_else(|| match_error!("Failed to resolve method call"))?;
+        if pattern_function != code_resolved_function {
+            fail_match!("Method call resolved to a different function");
+        }
+        // Check arguments.
+        let mut pattern_args = pattern
+            .arg_list()
+            .ok_or_else(|| match_error!("Pattern function call has no args"))?
+            .args();
+        self.attempt_match_opt(phase, pattern_args.next(), code.expr())?;
+        let mut code_args =
+            code.arg_list().ok_or_else(|| match_error!("Code method call has no args"))?.args();
+        loop {
+            match (pattern_args.next(), code_args.next()) {
+                (None, None) => return Ok(()),
+                (p, c) => self.attempt_match_opt(phase, p, c)?,
+            }
+        }
+    }
+
     fn get_placeholder(&self, element: &SyntaxElement) -> Option<&Placeholder> {
         only_ident(element.clone()).and_then(|ident| self.rule.get_placeholder(&ident))
     }
diff --git a/crates/ra_ssr/src/resolving.rs b/crates/ra_ssr/src/resolving.rs
index 63fd217ce..75f556785 100644
--- a/crates/ra_ssr/src/resolving.rs
+++ b/crates/ra_ssr/src/resolving.rs
@@ -18,10 +18,12 @@ pub(crate) struct ResolvedPattern {
     pub(crate) node: SyntaxNode,
     // Paths in `node` that we've resolved.
     pub(crate) resolved_paths: FxHashMap<SyntaxNode, ResolvedPath>,
+    pub(crate) ufcs_function_calls: FxHashMap<SyntaxNode, hir::Function>,
 }
 
 pub(crate) struct ResolvedPath {
     pub(crate) resolution: hir::PathResolution,
+    /// The depth of the ast::Path that was resolved within the pattern.
     pub(crate) depth: u32,
 }
 
@@ -64,10 +66,26 @@ impl Resolver<'_, '_> {
     fn resolve_pattern_tree(&self, pattern: SyntaxNode) -> Result<ResolvedPattern, SsrError> {
         let mut resolved_paths = FxHashMap::default();
         self.resolve(pattern.clone(), 0, &mut resolved_paths)?;
+        let ufcs_function_calls = resolved_paths
+            .iter()
+            .filter_map(|(path_node, resolved)| {
+                if let Some(grandparent) = path_node.parent().and_then(|parent| parent.parent()) {
+                    if grandparent.kind() == SyntaxKind::CALL_EXPR {
+                        if let hir::PathResolution::AssocItem(hir::AssocItem::Function(function)) =
+                            &resolved.resolution
+                        {
+                            return Some((grandparent, *function));
+                        }
+                    }
+                }
+                None
+            })
+            .collect();
         Ok(ResolvedPattern {
             node: pattern,
             resolved_paths,
             placeholders_by_stand_in: self.placeholders_by_stand_in.clone(),
+            ufcs_function_calls,
         })
     }
 
diff --git a/crates/ra_ssr/src/search.rs b/crates/ra_ssr/src/search.rs
index 141e7d026..bcf0f0468 100644
--- a/crates/ra_ssr/src/search.rs
+++ b/crates/ra_ssr/src/search.rs
@@ -46,35 +46,58 @@ impl<'db> MatchFinder<'db> {
         usage_cache: &mut UsageCache,
         matches_out: &mut Vec<Match>,
     ) {
-        if let Some(first_path) = pick_path_for_usages(pattern) {
-            let definition: Definition = first_path.resolution.clone().into();
+        if let Some(resolved_path) = pick_path_for_usages(pattern) {
+            let definition: Definition = resolved_path.resolution.clone().into();
             for reference in self.find_usages(usage_cache, definition) {
-                let file = self.sema.parse(reference.file_range.file_id);
-                if let Some(path) = self.sema.find_node_at_offset_with_descend::<ast::Path>(
-                    file.syntax(),
-                    reference.file_range.range.start(),
-                ) {
-                    if let Some(node_to_match) = self
-                        .sema
-                        .ancestors_with_macros(path.syntax().clone())
-                        .skip(first_path.depth as usize)
-                        .next()
+                if let Some(node_to_match) = self.find_node_to_match(resolved_path, reference) {
+                    if !is_search_permitted_ancestors(&node_to_match) {
+                        mark::hit!(use_declaration_with_braces);
+                        continue;
+                    }
+                    if let Ok(m) =
+                        matching::get_match(false, rule, &node_to_match, &None, &self.sema)
                     {
-                        if !is_search_permitted_ancestors(&node_to_match) {
-                            mark::hit!(use_declaration_with_braces);
-                            continue;
-                        }
-                        if let Ok(m) =
-                            matching::get_match(false, rule, &node_to_match, &None, &self.sema)
-                        {
-                            matches_out.push(m);
-                        }
+                        matches_out.push(m);
                     }
                 }
             }
         }
     }
 
+    fn find_node_to_match(
+        &self,
+        resolved_path: &ResolvedPath,
+        reference: &Reference,
+    ) -> Option<SyntaxNode> {
+        let file = self.sema.parse(reference.file_range.file_id);
+        let depth = resolved_path.depth as usize;
+        let offset = reference.file_range.range.start();
+        if let Some(path) =
+            self.sema.find_node_at_offset_with_descend::<ast::Path>(file.syntax(), offset)
+        {
+            self.sema.ancestors_with_macros(path.syntax().clone()).skip(depth).next()
+        } else if let Some(path) =
+            self.sema.find_node_at_offset_with_descend::<ast::MethodCallExpr>(file.syntax(), offset)
+        {
+            // If the pattern contained a path and we found a reference to that path that wasn't
+            // itself a path, but was a method call, then we need to adjust how far up to try
+            // matching by how deep the path was within a CallExpr. The structure would have been
+            // CallExpr, PathExpr, Path - i.e. a depth offset of 2. We don't need to check if the
+            // path was part of a CallExpr because if it wasn't then all that will happen is we'll
+            // fail to match, which is the desired behavior.
+            const PATH_DEPTH_IN_CALL_EXPR: usize = 2;
+            if depth < PATH_DEPTH_IN_CALL_EXPR {
+                return None;
+            }
+            self.sema
+                .ancestors_with_macros(path.syntax().clone())
+                .skip(depth - PATH_DEPTH_IN_CALL_EXPR)
+                .next()
+        } else {
+            None
+        }
+    }
+
     fn find_usages<'a>(
         &self,
         usage_cache: &'a mut UsageCache,
diff --git a/crates/ra_ssr/src/tests.rs b/crates/ra_ssr/src/tests.rs
index f564c6129..b38807c0f 100644
--- a/crates/ra_ssr/src/tests.rs
+++ b/crates/ra_ssr/src/tests.rs
@@ -827,3 +827,61 @@ fn use_declaration_with_braces() {
         "]],
     )
 }
+
+#[test]
+fn ufcs_matches_method_call() {
+    let code = r#"
+    struct Foo {}
+    impl Foo {
+        fn new(_: i32) -> Foo { Foo {} }
+        fn do_stuff(&self, _: i32) {}
+    }
+    struct Bar {}
+    impl Bar {
+        fn new(_: i32) -> Bar { Bar {} }
+        fn do_stuff(&self, v: i32) {}
+    }
+    fn main() {
+        let b = Bar {};
+        let f = Foo {};
+        b.do_stuff(1);
+        f.do_stuff(2);
+        Foo::new(4).do_stuff(3);
+        // Too many / too few args - should never match
+        f.do_stuff(2, 10);
+        f.do_stuff();
+    }
+    "#;
+    assert_matches("Foo::do_stuff($a, $b)", code, &["f.do_stuff(2)", "Foo::new(4).do_stuff(3)"]);
+    // The arguments needs special handling in the case of a function call matching a method call
+    // and the first argument is different.
+    assert_matches("Foo::do_stuff($a, 2)", code, &["f.do_stuff(2)"]);
+    assert_matches("Foo::do_stuff(Foo::new(4), $b)", code, &["Foo::new(4).do_stuff(3)"]);
+
+    assert_ssr_transform(
+        "Foo::do_stuff(Foo::new($a), $b) ==>> Bar::new($b).do_stuff($a)",
+        code,
+        expect![[r#"
+            struct Foo {}
+            impl Foo {
+                fn new(_: i32) -> Foo { Foo {} }
+                fn do_stuff(&self, _: i32) {}
+            }
+            struct Bar {}
+            impl Bar {
+                fn new(_: i32) -> Bar { Bar {} }
+                fn do_stuff(&self, v: i32) {}
+            }
+            fn main() {
+                let b = Bar {};
+                let f = Foo {};
+                b.do_stuff(1);
+                f.do_stuff(2);
+                Bar::new(3).do_stuff(4);
+                // Too many / too few args - should never match
+                f.do_stuff(2, 10);
+                f.do_stuff();
+            }
+        "#]],
+    );
+}
-- 
cgit v1.2.3