7 files changed, 1948 insertions, 0 deletions

diff --git a/crates/ra_ssr/Cargo.toml b/crates/ra_ssr/Cargo.toml
new file mode 100644
index 000000000..fe098aaee
--- /dev/null
+++ b/crates/ra_ssr/Cargo.toml
@@ -0,0 +1,20 @@
+[package]
+edition = "2018"
+name = "ra_ssr"
+version = "0.1.0"
+authors = ["rust-analyzer developers"]
+license = "MIT OR Apache-2.0"
+description = "Structural search and replace of Rust code"
+repository = "https://github.com/rust-analyzer/rust-analyzer"
+
+[lib]
+doctest = false
+
+[dependencies]
+ra_text_edit = { path = "../ra_text_edit" }
+ra_syntax = { path = "../ra_syntax" }
+ra_db = { path = "../ra_db" }
+ra_ide_db = { path = "../ra_ide_db" }
+hir = { path = "../ra_hir", package = "ra_hir" }
+rustc-hash = "1.1.0"
+test_utils = { path = "../test_utils" }
diff --git a/crates/ra_ssr/src/errors.rs b/crates/ra_ssr/src/errors.rs
new file mode 100644
index 000000000..c02bacae6
--- /dev/null
+++ b/crates/ra_ssr/src/errors.rs
@@ -0,0 +1,29 @@
+//! Code relating to errors produced by SSR.
+
+/// Constructs an SsrError taking arguments like the format macro.
+macro_rules! _error {
+    ($fmt:expr) => {$crate::SsrError::new(format!($fmt))};
+    ($fmt:expr, $($arg:tt)+) => {$crate::SsrError::new(format!($fmt, $($arg)+))}
+}
+pub(crate) use _error as error;
+
+/// Returns from the current function with an error, supplied by arguments as for format!
+macro_rules! _bail {
+    ($($tokens:tt)*) => {return Err(crate::errors::error!($($tokens)*))}
+}
+pub(crate) use _bail as bail;
+
+#[derive(Debug, PartialEq)]
+pub struct SsrError(pub(crate) String);
+
+impl std::fmt::Display for SsrError {
+    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
+        write!(f, "Parse error: {}", self.0)
+    }
+}
+
+impl SsrError {
+    pub(crate) fn new(message: impl Into<String>) -> SsrError {
+        SsrError(message.into())
+    }
+}
diff --git a/crates/ra_ssr/src/lib.rs b/crates/ra_ssr/src/lib.rs
new file mode 100644
index 000000000..cca4576ce
--- /dev/null
+++ b/crates/ra_ssr/src/lib.rs
@@ -0,0 +1,285 @@
+//! Structural Search Replace
+//!
+//! Allows searching the AST for code that matches one or more patterns and then replacing that code
+//! based on a template.
+
+mod matching;
+mod parsing;
+mod replacing;
+#[macro_use]
+mod errors;
+#[cfg(test)]
+mod tests;
+
+pub use crate::errors::SsrError;
+pub use crate::matching::Match;
+use crate::matching::{record_match_fails_reasons_scope, MatchFailureReason};
+use hir::Semantics;
+use ra_db::{FileId, FileRange};
+use ra_syntax::{ast, AstNode, SmolStr, SyntaxKind, 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,
+    /// What we'll replace it with.
+    template: parsing::SsrTemplate,
+}
+
+#[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>,
+}
+
+#[derive(Debug, Default)]
+pub struct SsrMatches {
+    pub matches: Vec<Match>,
+}
+
+/// Searches a crate for pattern matches and possibly replaces them with something else.
+pub struct MatchFinder<'db> {
+    /// Our source of information about the user's code.
+    sema: Semantics<'db, ra_ide_db::RootDatabase>,
+    rules: Vec<SsrRule>,
+}
+
+impl<'db> MatchFinder<'db> {
+    pub fn new(db: &'db ra_ide_db::RootDatabase) -> MatchFinder<'db> {
+        MatchFinder { sema: Semantics::new(db), rules: Vec::new() }
+    }
+
+    pub fn add_rule(&mut self, rule: SsrRule) {
+        self.rules.push(rule);
+    }
+
+    /// 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() })
+    }
+
+    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)))
+        }
+    }
+
+    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.find_matches(code, &None, &mut matches);
+        matches
+    }
+
+    /// Finds all nodes in `file_id` whose text is exactly equal to `snippet` and attempts to match
+    /// them, while recording reasons why they don't match. This API is useful for command
+    /// line-based debugging where providing a range is difficult.
+    pub fn debug_where_text_equal(&self, file_id: FileId, snippet: &str) -> Vec<MatchDebugInfo> {
+        use ra_db::SourceDatabaseExt;
+        let file = self.sema.parse(file_id);
+        let mut res = Vec::new();
+        let file_text = self.sema.db.file_text(file_id);
+        let mut remaining_text = file_text.as_str();
+        let mut base = 0;
+        let len = snippet.len() as u32;
+        while let Some(offset) = remaining_text.find(snippet) {
+            let start = base + offset as u32;
+            let end = start + len;
+            self.output_debug_for_nodes_at_range(
+                file.syntax(),
+                FileRange { file_id, range: TextRange::new(start.into(), end.into()) },
+                &None,
+                &mut res,
+            );
+            remaining_text = &remaining_text[offset + snippet.len()..];
+            base = end;
+        }
+        res
+    }
+
+    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,
+        range: FileRange,
+        restrict_range: &Option<FileRange>,
+        out: &mut Vec<MatchDebugInfo>,
+    ) {
+        for node in node.children() {
+            let node_range = self.sema.original_range(&node);
+            if node_range.file_id != range.file_id || !node_range.range.contains_range(range.range)
+            {
+                continue;
+            }
+            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());
+                    out.push(MatchDebugInfo {
+                        matched: matching::get_match(true, rule, &node, restrict_range, &self.sema)
+                            .map_err(|e| MatchFailureReason {
+                                reason: e.reason.unwrap_or_else(|| {
+                                    "Match failed, but no reason was given".to_owned()
+                                }),
+                            }),
+                        pattern,
+                        node: node.clone(),
+                    });
+                }
+            } else if let Some(macro_call) = ast::MacroCall::cast(node.clone()) {
+                if let Some(expanded) = self.sema.expand(&macro_call) {
+                    if let Some(tt) = macro_call.token_tree() {
+                        self.output_debug_for_nodes_at_range(
+                            &expanded,
+                            range,
+                            &Some(self.sema.original_range(tt.syntax())),
+                            out,
+                        );
+                    }
+                }
+            }
+            self.output_debug_for_nodes_at_range(&node, range, restrict_range, out);
+        }
+    }
+}
+
+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>,
+    matched: Result<Match, MatchFailureReason>,
+}
+
+impl std::fmt::Debug for MatchDebugInfo {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        match &self.matched {
+            Ok(_) => writeln!(f, "Node matched")?,
+            Err(reason) => writeln!(f, "Node failed to match because: {}", reason.reason)?,
+        }
+        writeln!(
+            f,
+            "============ AST ===========\n\
+            {:#?}",
+            self.node
+        )?;
+        writeln!(f, "========= PATTERN ==========")?;
+        match &self.pattern {
+            Ok(pattern) => {
+                writeln!(f, "{:#?}", pattern)?;
+            }
+            Err(err) => {
+                writeln!(f, "{}", err.reason)?;
+            }
+        }
+        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 {
+        let mut out = SsrMatches::default();
+        self.flatten_into(&mut out);
+        out
+    }
+
+    fn flatten_into(self, out: &mut SsrMatches) {
+        for mut m in self.matches {
+            for p in m.placeholder_values.values_mut() {
+                std::mem::replace(&mut p.inner_matches, SsrMatches::default()).flatten_into(out);
+            }
+            out.matches.push(m);
+        }
+    }
+}
+
+impl Match {
+    pub fn matched_text(&self) -> String {
+        self.matched_node.text().to_string()
+    }
+}
+
+impl std::error::Error for SsrError {}
+
+#[cfg(test)]
+impl MatchDebugInfo {
+    pub(crate) fn match_failure_reason(&self) -> Option<&str> {
+        self.matched.as_ref().err().map(|r| r.reason.as_str())
+    }
+}
diff --git a/crates/ra_ssr/src/matching.rs b/crates/ra_ssr/src/matching.rs
new file mode 100644
index 000000000..50b29eab2
--- /dev/null
+++ b/crates/ra_ssr/src/matching.rs
@@ -0,0 +1,623 @@
+//! This module is responsible for matching a search pattern against a node in the AST. In the
+//! process of matching, placeholder values are recorded.
+
+use crate::{
+    parsing::{Constraint, NodeKind, Placeholder, SsrTemplate},
+    SsrMatches, SsrPattern, SsrRule,
+};
+use hir::Semantics;
+use ra_db::FileRange;
+use ra_syntax::ast::{AstNode, AstToken};
+use ra_syntax::{ast, SyntaxElement, SyntaxElementChildren, SyntaxKind, SyntaxNode, SyntaxToken};
+use rustc_hash::FxHashMap;
+use std::{cell::Cell, iter::Peekable};
+use test_utils::mark;
+
+// Creates a match error. If we're currently attempting to match some code that we thought we were
+// going to match, as indicated by the --debug-snippet flag, then populate the reason field.
+macro_rules! match_error {
+    ($e:expr) => {{
+            MatchFailed {
+                reason: if recording_match_fail_reasons() {
+                    Some(format!("{}", $e))
+                } else {
+                    None
+                }
+            }
+    }};
+    ($fmt:expr, $($arg:tt)+) => {{
+        MatchFailed {
+            reason: if recording_match_fail_reasons() {
+                Some(format!($fmt, $($arg)+))
+            } else {
+                None
+            }
+        }
+    }};
+}
+
+// Fails the current match attempt, recording the supplied reason if we're recording match fail reasons.
+macro_rules! fail_match {
+    ($($args:tt)*) => {return Err(match_error!($($args)*))};
+}
+
+/// Information about a match that was found.
+#[derive(Debug)]
+pub struct Match {
+    pub(crate) range: FileRange,
+    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: SsrTemplate,
+}
+
+/// Represents a `$var` in an SSR query.
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
+pub(crate) struct Var(pub String);
+
+/// Information about a placeholder bound in a match.
+#[derive(Debug)]
+pub(crate) struct PlaceholderMatch {
+    /// The node that the placeholder matched to. If set, then we'll search for further matches
+    /// within this node. It isn't set when we match tokens within a macro call's token tree.
+    pub(crate) node: Option<SyntaxNode>,
+    pub(crate) range: FileRange,
+    /// More matches, found within `node`.
+    pub(crate) inner_matches: SsrMatches,
+}
+
+#[derive(Debug)]
+pub(crate) struct MatchFailureReason {
+    pub(crate) reason: String,
+}
+
+/// An "error" indicating that matching failed. Use the fail_match! macro to create and return this.
+#[derive(Clone)]
+pub(crate) struct MatchFailed {
+    /// The reason why we failed to match. Only present when debug_active true in call to
+    /// `get_match`.
+    pub(crate) reason: Option<String>,
+}
+
+/// Checks if `code` matches the search pattern found in `search_scope`, returning information about
+/// the match, if it does. Since we only do matching in this module and searching is done by the
+/// parent module, we don't populate nested matches.
+pub(crate) fn get_match(
+    debug_active: bool,
+    rule: &SsrRule,
+    code: &SyntaxNode,
+    restrict_range: &Option<FileRange>,
+    sema: &Semantics<ra_ide_db::RootDatabase>,
+) -> Result<Match, MatchFailed> {
+    record_match_fails_reasons_scope(debug_active, || {
+        Matcher::try_match(rule, code, restrict_range, sema)
+    })
+}
+
+/// Checks if our search pattern matches a particular node of the AST.
+struct Matcher<'db, 'sema> {
+    sema: &'sema Semantics<'db, ra_ide_db::RootDatabase>,
+    /// If any placeholders come from anywhere outside of this range, then the match will be
+    /// rejected.
+    restrict_range: Option<FileRange>,
+    rule: &'sema SsrRule,
+}
+
+/// Which phase of matching we're currently performing. We do two phases because most attempted
+/// matches will fail and it means we can defer more expensive checks to the second phase.
+enum Phase<'a> {
+    /// On the first phase, we perform cheap checks. No state is mutated and nothing is recorded.
+    First,
+    /// On the second phase, we construct the `Match`. Things like what placeholders bind to is
+    /// recorded.
+    Second(&'a mut Match),
+}
+
+impl<'db, 'sema> Matcher<'db, 'sema> {
+    fn try_match(
+        rule: &'sema SsrRule,
+        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.validate_range(&sema.original_range(code))?;
+        let mut the_match = Match {
+            range: sema.original_range(code),
+            matched_node: code.clone(),
+            placeholder_values: FxHashMap::default(),
+            ignored_comments: Vec::new(),
+            template: rule.template.clone(),
+        };
+        // 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)?;
+        Ok(the_match)
+    }
+
+    /// Checks that `range` is within the permitted range if any. This is applicable when we're
+    /// processing a macro expansion and we want to fail the match if we're working with a node that
+    /// didn't originate from the token tree of the macro call.
+    fn validate_range(&self, range: &FileRange) -> Result<(), MatchFailed> {
+        if let Some(restrict_range) = &self.restrict_range {
+            if restrict_range.file_id != range.file_id
+                || !restrict_range.range.contains_range(range.range)
+            {
+                fail_match!("Node originated from a macro");
+            }
+        }
+        Ok(())
+    }
+
+    fn attempt_match_node(
+        &self,
+        phase: &mut Phase,
+        pattern: &SyntaxNode,
+        code: &SyntaxNode,
+    ) -> Result<(), MatchFailed> {
+        // Handle placeholders.
+        if let Some(placeholder) = self.get_placeholder(&SyntaxElement::Node(pattern.clone())) {
+            for constraint in &placeholder.constraints {
+                self.check_constraint(constraint, code)?;
+            }
+            if let Phase::Second(matches_out) = phase {
+                let original_range = self.sema.original_range(code);
+                // We validated the range for the node when we started the match, so the placeholder
+                // probably can't fail range validation, but just to be safe...
+                self.validate_range(&original_range)?;
+                matches_out.placeholder_values.insert(
+                    Var(placeholder.ident.to_string()),
+                    PlaceholderMatch::new(code, original_range),
+                );
+            }
+            return Ok(());
+        }
+        // Non-placeholders.
+        if pattern.kind() != code.kind() {
+            fail_match!(
+                "Pattern had a `{}` ({:?}), code had `{}` ({:?})",
+                pattern.text(),
+                pattern.kind(),
+                code.text(),
+                code.kind()
+            );
+        }
+        // Some kinds of nodes have special handling. For everything else, we fall back to default
+        // matching.
+        match code.kind() {
+            SyntaxKind::RECORD_FIELD_LIST => {
+                self.attempt_match_record_field_list(phase, pattern, code)
+            }
+            SyntaxKind::TOKEN_TREE => self.attempt_match_token_tree(phase, pattern, code),
+            _ => self.attempt_match_node_children(phase, pattern, code),
+        }
+    }
+
+    fn attempt_match_node_children(
+        &self,
+        phase: &mut Phase,
+        pattern: &SyntaxNode,
+        code: &SyntaxNode,
+    ) -> Result<(), MatchFailed> {
+        self.attempt_match_sequences(
+            phase,
+            PatternIterator::new(pattern),
+            code.children_with_tokens(),
+        )
+    }
+
+    fn attempt_match_sequences(
+        &self,
+        phase: &mut Phase,
+        pattern_it: PatternIterator,
+        mut code_it: SyntaxElementChildren,
+    ) -> Result<(), MatchFailed> {
+        let mut pattern_it = pattern_it.peekable();
+        loop {
+            match phase.next_non_trivial(&mut code_it) {
+                None => {
+                    if let Some(p) = pattern_it.next() {
+                        fail_match!("Part of the pattern was unmatched: {:?}", p);
+                    }
+                    return Ok(());
+                }
+                Some(SyntaxElement::Token(c)) => {
+                    self.attempt_match_token(phase, &mut pattern_it, &c)?;
+                }
+                Some(SyntaxElement::Node(c)) => match pattern_it.next() {
+                    Some(SyntaxElement::Node(p)) => {
+                        self.attempt_match_node(phase, &p, &c)?;
+                    }
+                    Some(p) => fail_match!("Pattern wanted '{}', code has {}", p, c.text()),
+                    None => fail_match!("Pattern reached end, code has {}", c.text()),
+                },
+            }
+        }
+    }
+
+    fn attempt_match_token(
+        &self,
+        phase: &mut Phase,
+        pattern: &mut Peekable<PatternIterator>,
+        code: &ra_syntax::SyntaxToken,
+    ) -> Result<(), MatchFailed> {
+        phase.record_ignored_comments(code);
+        // Ignore whitespace and comments.
+        if code.kind().is_trivia() {
+            return Ok(());
+        }
+        if let Some(SyntaxElement::Token(p)) = pattern.peek() {
+            // If the code has a comma and the pattern is about to close something, then accept the
+            // comma without advancing the pattern. i.e. ignore trailing commas.
+            if code.kind() == SyntaxKind::COMMA && is_closing_token(p.kind()) {
+                return Ok(());
+            }
+            // Conversely, if the pattern has a comma and the code doesn't, skip that part of the
+            // pattern and continue to match the code.
+            if p.kind() == SyntaxKind::COMMA && is_closing_token(code.kind()) {
+                pattern.next();
+            }
+        }
+        // Consume an element from the pattern and make sure it matches.
+        match pattern.next() {
+            Some(SyntaxElement::Token(p)) => {
+                if p.kind() != code.kind() || p.text() != code.text() {
+                    fail_match!(
+                        "Pattern wanted token '{}' ({:?}), but code had token '{}' ({:?})",
+                        p.text(),
+                        p.kind(),
+                        code.text(),
+                        code.kind()
+                    )
+                }
+            }
+            Some(SyntaxElement::Node(p)) => {
+                // Not sure if this is actually reachable.
+                fail_match!(
+                    "Pattern wanted {:?}, but code had token '{}' ({:?})",
+                    p,
+                    code.text(),
+                    code.kind()
+                );
+            }
+            None => {
+                fail_match!("Pattern exhausted, while code remains: `{}`", code.text());
+            }
+        }
+        Ok(())
+    }
+
+    fn check_constraint(
+        &self,
+        constraint: &Constraint,
+        code: &SyntaxNode,
+    ) -> Result<(), MatchFailed> {
+        match constraint {
+            Constraint::Kind(kind) => {
+                kind.matches(code)?;
+            }
+            Constraint::Not(sub) => {
+                if self.check_constraint(&*sub, code).is_ok() {
+                    fail_match!("Constraint {:?} failed for '{}'", constraint, code.text());
+                }
+            }
+        }
+        Ok(())
+    }
+
+    /// 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(
+        &self,
+        phase: &mut Phase,
+        pattern: &SyntaxNode,
+        code: &SyntaxNode,
+    ) -> Result<(), MatchFailed> {
+        // Build a map keyed by field name.
+        let mut fields_by_name = FxHashMap::default();
+        for child in code.children() {
+            if let Some(record) = ast::RecordField::cast(child.clone()) {
+                if let Some(name) = record.field_name() {
+                    fields_by_name.insert(name.text().clone(), child.clone());
+                }
+            }
+        }
+        for p in pattern.children_with_tokens() {
+            if let SyntaxElement::Node(p) = p {
+                if let Some(name_element) = p.first_child_or_token() {
+                    if self.get_placeholder(&name_element).is_some() {
+                        // If the pattern is using placeholders for field names then order
+                        // independence doesn't make sense. Fall back to regular ordered
+                        // matching.
+                        return self.attempt_match_node_children(phase, pattern, code);
+                    }
+                    if let Some(ident) = only_ident(name_element) {
+                        let code_record = fields_by_name.remove(ident.text()).ok_or_else(|| {
+                            match_error!(
+                                "Placeholder has record field '{}', but code doesn't",
+                                ident
+                            )
+                        })?;
+                        self.attempt_match_node(phase, &p, &code_record)?;
+                    }
+                }
+            }
+        }
+        if let Some(unmatched_fields) = fields_by_name.keys().next() {
+            fail_match!(
+                "{} field(s) of a record literal failed to match, starting with {}",
+                fields_by_name.len(),
+                unmatched_fields
+            );
+        }
+        Ok(())
+    }
+
+    /// Outside of token trees, a placeholder can only match a single AST node, whereas in a token
+    /// tree it can match a sequence of tokens. Note, that this code will only be used when the
+    /// pattern matches the macro invocation. For matches within the macro call, we'll already have
+    /// expanded the macro.
+    fn attempt_match_token_tree(
+        &self,
+        phase: &mut Phase,
+        pattern: &SyntaxNode,
+        code: &ra_syntax::SyntaxNode,
+    ) -> Result<(), MatchFailed> {
+        let mut pattern = PatternIterator::new(pattern).peekable();
+        let mut children = code.children_with_tokens();
+        while let Some(child) = children.next() {
+            if let Some(placeholder) = pattern.peek().and_then(|p| self.get_placeholder(p)) {
+                pattern.next();
+                let next_pattern_token = pattern
+                    .peek()
+                    .and_then(|p| match p {
+                        SyntaxElement::Token(t) => Some(t.clone()),
+                        SyntaxElement::Node(n) => n.first_token(),
+                    })
+                    .map(|p| p.text().to_string());
+                let first_matched_token = child.clone();
+                let mut last_matched_token = child;
+                // Read code tokens util we reach one equal to the next token from our pattern
+                // or we reach the end of the token tree.
+                while let Some(next) = children.next() {
+                    match &next {
+                        SyntaxElement::Token(t) => {
+                            if Some(t.to_string()) == next_pattern_token {
+                                pattern.next();
+                                break;
+                            }
+                        }
+                        SyntaxElement::Node(n) => {
+                            if let Some(first_token) = n.first_token() {
+                                if Some(first_token.to_string()) == next_pattern_token {
+                                    if let Some(SyntaxElement::Node(p)) = pattern.next() {
+                                        // We have a subtree that starts with the next token in our pattern.
+                                        self.attempt_match_token_tree(phase, &p, &n)?;
+                                        break;
+                                    }
+                                }
+                            }
+                        }
+                    };
+                    last_matched_token = next;
+                }
+                if let Phase::Second(match_out) = phase {
+                    match_out.placeholder_values.insert(
+                        Var(placeholder.ident.to_string()),
+                        PlaceholderMatch::from_range(FileRange {
+                            file_id: self.sema.original_range(code).file_id,
+                            range: first_matched_token
+                                .text_range()
+                                .cover(last_matched_token.text_range()),
+                        }),
+                    );
+                }
+                continue;
+            }
+            // Match literal (non-placeholder) tokens.
+            match child {
+                SyntaxElement::Token(token) => {
+                    self.attempt_match_token(phase, &mut pattern, &token)?;
+                }
+                SyntaxElement::Node(node) => match pattern.next() {
+                    Some(SyntaxElement::Node(p)) => {
+                        self.attempt_match_token_tree(phase, &p, &node)?;
+                    }
+                    Some(SyntaxElement::Token(p)) => fail_match!(
+                        "Pattern has token '{}', code has subtree '{}'",
+                        p.text(),
+                        node.text()
+                    ),
+                    None => fail_match!("Pattern has nothing, code has '{}'", node.text()),
+                },
+            }
+        }
+        if let Some(p) = pattern.next() {
+            fail_match!("Reached end of token tree in code, but pattern still has {:?}", p);
+        }
+        Ok(())
+    }
+
+    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()))
+    }
+}
+
+impl Phase<'_> {
+    fn next_non_trivial(&mut self, code_it: &mut SyntaxElementChildren) -> Option<SyntaxElement> {
+        loop {
+            let c = code_it.next();
+            if let Some(SyntaxElement::Token(t)) = &c {
+                self.record_ignored_comments(t);
+                if t.kind().is_trivia() {
+                    continue;
+                }
+            }
+            return c;
+        }
+    }
+
+    fn record_ignored_comments(&mut self, token: &SyntaxToken) {
+        if token.kind() == SyntaxKind::COMMENT {
+            if let Phase::Second(match_out) = self {
+                if let Some(comment) = ast::Comment::cast(token.clone()) {
+                    match_out.ignored_comments.push(comment);
+                }
+            }
+        }
+    }
+}
+
+fn is_closing_token(kind: SyntaxKind) -> bool {
+    kind == SyntaxKind::R_PAREN || kind == SyntaxKind::R_CURLY || kind == SyntaxKind::R_BRACK
+}
+
+pub(crate) fn record_match_fails_reasons_scope<F, T>(debug_active: bool, f: F) -> T
+where
+    F: Fn() -> T,
+{
+    RECORDING_MATCH_FAIL_REASONS.with(|c| c.set(debug_active));
+    let res = f();
+    RECORDING_MATCH_FAIL_REASONS.with(|c| c.set(false));
+    res
+}
+
+// For performance reasons, we don't want to record the reason why every match fails, only the bit
+// of code that the user indicated they thought would match. We use a thread local to indicate when
+// we are trying to match that bit of code. This saves us having to pass a boolean into all the bits
+// of code that can make the decision to not match.
+thread_local! {
+    pub static RECORDING_MATCH_FAIL_REASONS: Cell<bool> = Cell::new(false);
+}
+
+fn recording_match_fail_reasons() -> bool {
+    RECORDING_MATCH_FAIL_REASONS.with(|c| c.get())
+}
+
+impl PlaceholderMatch {
+    fn new(node: &SyntaxNode, range: FileRange) -> Self {
+        Self { node: Some(node.clone()), range, inner_matches: SsrMatches::default() }
+    }
+
+    fn from_range(range: FileRange) -> Self {
+        Self { node: None, range, inner_matches: SsrMatches::default() }
+    }
+}
+
+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 {
+            Self::Literal => {
+                mark::hit!(literal_constraint);
+                ast::Literal::can_cast(node.kind())
+            }
+        };
+        if !ok {
+            fail_match!("Code '{}' isn't of kind {:?}", node.text(), self);
+        }
+        Ok(())
+    }
+}
+
+// If `node` contains nothing but an ident then return it, otherwise return None.
+fn only_ident(element: SyntaxElement) -> Option<SyntaxToken> {
+    match element {
+        SyntaxElement::Token(t) => {
+            if t.kind() == SyntaxKind::IDENT {
+                return Some(t);
+            }
+        }
+        SyntaxElement::Node(n) => {
+            let mut children = n.children_with_tokens();
+            if let (Some(only_child), None) = (children.next(), children.next()) {
+                return only_ident(only_child);
+            }
+        }
+    }
+    None
+}
+
+struct PatternIterator {
+    iter: SyntaxElementChildren,
+}
+
+impl Iterator for PatternIterator {
+    type Item = SyntaxElement;
+
+    fn next(&mut self) -> Option<SyntaxElement> {
+        while let Some(element) = self.iter.next() {
+            if !element.kind().is_trivia() {
+                return Some(element);
+            }
+        }
+        None
+    }
+}
+
+impl PatternIterator {
+    fn new(parent: &SyntaxNode) -> Self {
+        Self { iter: parent.children_with_tokens() }
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use crate::{MatchFinder, SsrRule};
+
+    #[test]
+    fn parse_match_replace() {
+        let rule: SsrRule = "foo($x) ==>> bar($x)".parse().unwrap();
+        let input = "fn foo() {} fn main() { foo(1+2); }";
+
+        use ra_db::fixture::WithFixture;
+        let (db, file_id) = ra_ide_db::RootDatabase::with_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);
+        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);
+        assert_eq!(
+            matches.matches[0].placeholder_values[&Var("x".to_string())]
+                .node
+                .as_ref()
+                .unwrap()
+                .text(),
+            "1+2"
+        );
+
+        let edit = crate::replacing::matches_to_edit(&matches, input);
+        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
new file mode 100644
index 000000000..4aee97bb2
--- /dev/null
+++ b/crates/ra_ssr/src/parsing.rs
@@ -0,0 +1,343 @@
+//! This file contains code for parsing SSR rules, which look something like `foo($a) ==>> bar($b)`.
+//! We first split everything before and after the separator `==>>`. Next, both the search pattern
+//! and the replacement template get tokenized by the Rust tokenizer. Tokens are then searched for
+//! placeholders, which start with `$`. For replacement templates, this is the final form. For
+//! search patterns, we go further and parse the pattern as each kind of thing that we can match.
+//! e.g. expressions, type references etc.
+
+use crate::errors::bail;
+use crate::{SsrError, SsrPattern, SsrRule};
+use ra_syntax::{ast, AstNode, SmolStr, SyntaxKind, T};
+use rustc_hash::{FxHashMap, FxHashSet};
+use std::str::FromStr;
+
+#[derive(Clone, Debug)]
+pub(crate) struct SsrTemplate {
+    pub(crate) tokens: Vec<PatternElement>,
+}
+
+#[derive(Debug)]
+pub(crate) struct RawSearchPattern {
+    tokens: Vec<PatternElement>,
+}
+
+// Part of a search or replace pattern.
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub(crate) enum PatternElement {
+    Token(Token),
+    Placeholder(Placeholder),
+}
+
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub(crate) struct Placeholder {
+    /// The name of this placeholder. e.g. for "$a", this would be "a"
+    pub(crate) ident: SmolStr,
+    /// A unique name used in place of this placeholder when we parse the pattern as Rust code.
+    stand_in_name: String,
+    pub(crate) constraints: Vec<Constraint>,
+}
+
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub(crate) enum Constraint {
+    Kind(NodeKind),
+    Not(Box<Constraint>),
+}
+
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub(crate) enum NodeKind {
+    Literal,
+}
+
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub(crate) struct Token {
+    kind: SyntaxKind,
+    pub(crate) text: SmolStr,
+}
+
+impl FromStr for SsrRule {
+    type Err = SsrError;
+
+    fn from_str(query: &str) -> Result<SsrRule, SsrError> {
+        let mut it = query.split("==>>");
+        let pattern = it.next().expect("at least empty string").trim();
+        let template = it
+            .next()
+            .ok_or_else(|| SsrError("Cannot find delimiter `==>>`".into()))?
+            .trim()
+            .to_string();
+        if it.next().is_some() {
+            return Err(SsrError("More than one delimiter found".into()));
+        }
+        let rule = SsrRule { pattern: pattern.parse()?, template: template.parse()? };
+        validate_rule(&rule)?;
+        Ok(rule)
+    }
+}
+
+impl FromStr for RawSearchPattern {
+    type Err = SsrError;
+
+    fn from_str(pattern_str: &str) -> Result<RawSearchPattern, SsrError> {
+        Ok(RawSearchPattern { tokens: parse_pattern(pattern_str)? })
+    }
+}
+
+impl RawSearchPattern {
+    /// 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();
+        for t in &self.tokens {
+            res.push_str(match t {
+                PatternElement::Token(token) => token.text.as_str(),
+                PatternElement::Placeholder(placeholder) => placeholder.stand_in_name.as_str(),
+            });
+        }
+        res
+    }
+
+    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 {
+                res.insert(SmolStr::new(placeholder.stand_in_name.clone()), placeholder.clone());
+            }
+        }
+        res
+    }
+}
+
+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)
+    }
+}
+
+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.
+fn parse_pattern(pattern_str: &str) -> Result<Vec<PatternElement>, SsrError> {
+    let mut res = Vec::new();
+    let mut placeholder_names = FxHashSet::default();
+    let mut tokens = tokenize(pattern_str)?.into_iter();
+    while let Some(token) = tokens.next() {
+        if token.kind == T![$] {
+            let placeholder = parse_placeholder(&mut tokens)?;
+            if !placeholder_names.insert(placeholder.ident.clone()) {
+                bail!("Name `{}` repeats more than once", placeholder.ident);
+            }
+            res.push(PatternElement::Placeholder(placeholder));
+        } else {
+            res.push(PatternElement::Token(token));
+        }
+    }
+    Ok(res)
+}
+
+/// Checks for errors in a rule. e.g. the replace pattern referencing placeholders that the search
+/// pattern didn't define.
+fn validate_rule(rule: &SsrRule) -> Result<(), SsrError> {
+    let mut defined_placeholders = FxHashSet::default();
+    for p in &rule.pattern.raw.tokens {
+        if let PatternElement::Placeholder(placeholder) = p {
+            defined_placeholders.insert(&placeholder.ident);
+        }
+    }
+    let mut undefined = Vec::new();
+    for p in &rule.template.tokens {
+        if let PatternElement::Placeholder(placeholder) = p {
+            if !defined_placeholders.contains(&placeholder.ident) {
+                undefined.push(format!("${}", placeholder.ident));
+            }
+            if !placeholder.constraints.is_empty() {
+                bail!("Replacement placeholders cannot have constraints");
+            }
+        }
+    }
+    if !undefined.is_empty() {
+        bail!("Replacement contains undefined placeholders: {}", undefined.join(", "));
+    }
+    Ok(())
+}
+
+fn tokenize(source: &str) -> Result<Vec<Token>, SsrError> {
+    let mut start = 0;
+    let (raw_tokens, errors) = ra_syntax::tokenize(source);
+    if let Some(first_error) = errors.first() {
+        bail!("Failed to parse pattern: {}", first_error);
+    }
+    let mut tokens: Vec<Token> = Vec::new();
+    for raw_token in raw_tokens {
+        let token_len = usize::from(raw_token.len);
+        tokens.push(Token {
+            kind: raw_token.kind,
+            text: SmolStr::new(&source[start..start + token_len]),
+        });
+        start += token_len;
+    }
+    Ok(tokens)
+}
+
+fn parse_placeholder(tokens: &mut std::vec::IntoIter<Token>) -> Result<Placeholder, SsrError> {
+    let mut name = None;
+    let mut constraints = Vec::new();
+    if let Some(token) = tokens.next() {
+        match token.kind {
+            SyntaxKind::IDENT => {
+                name = Some(token.text);
+            }
+            T!['{'] => {
+                let token =
+                    tokens.next().ok_or_else(|| SsrError::new("Unexpected end of placeholder"))?;
+                if token.kind == SyntaxKind::IDENT {
+                    name = Some(token.text);
+                }
+                loop {
+                    let token = tokens
+                        .next()
+                        .ok_or_else(|| SsrError::new("Placeholder is missing closing brace '}'"))?;
+                    match token.kind {
+                        T![:] => {
+                            constraints.push(parse_constraint(tokens)?);
+                        }
+                        T!['}'] => break,
+                        _ => bail!("Unexpected token while parsing placeholder: '{}'", token.text),
+                    }
+                }
+            }
+            _ => {
+                bail!("Placeholders should either be $name or ${{name:constraints}}");
+            }
+        }
+    }
+    let name = name.ok_or_else(|| SsrError::new("Placeholder ($) with no name"))?;
+    Ok(Placeholder::new(name, constraints))
+}
+
+fn parse_constraint(tokens: &mut std::vec::IntoIter<Token>) -> Result<Constraint, SsrError> {
+    let constraint_type = tokens
+        .next()
+        .ok_or_else(|| SsrError::new("Found end of placeholder while looking for a constraint"))?
+        .text
+        .to_string();
+    match constraint_type.as_str() {
+        "kind" => {
+            expect_token(tokens, "(")?;
+            let t = tokens.next().ok_or_else(|| {
+                SsrError::new("Unexpected end of constraint while looking for kind")
+            })?;
+            if t.kind != SyntaxKind::IDENT {
+                bail!("Expected ident, found {:?} while parsing kind constraint", t.kind);
+            }
+            expect_token(tokens, ")")?;
+            Ok(Constraint::Kind(NodeKind::from(&t.text)?))
+        }
+        "not" => {
+            expect_token(tokens, "(")?;
+            let sub = parse_constraint(tokens)?;
+            expect_token(tokens, ")")?;
+            Ok(Constraint::Not(Box::new(sub)))
+        }
+        x => bail!("Unsupported constraint type '{}'", x),
+    }
+}
+
+fn expect_token(tokens: &mut std::vec::IntoIter<Token>, expected: &str) -> Result<(), SsrError> {
+    if let Some(t) = tokens.next() {
+        if t.text == expected {
+            return Ok(());
+        }
+        bail!("Expected {} found {}", expected, t.text);
+    }
+    bail!("Expected {} found end of stream", expected);
+}
+
+impl NodeKind {
+    fn from(name: &SmolStr) -> Result<NodeKind, SsrError> {
+        Ok(match name.as_str() {
+            "literal" => NodeKind::Literal,
+            _ => bail!("Unknown node kind '{}'", name),
+        })
+    }
+}
+
+impl Placeholder {
+    fn new(name: SmolStr, constraints: Vec<Constraint>) -> Self {
+        Self { stand_in_name: format!("__placeholder_{}", name), constraints, ident: name }
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn parser_happy_case() {
+        fn token(kind: SyntaxKind, text: &str) -> PatternElement {
+            PatternElement::Token(Token { kind, text: SmolStr::new(text) })
+        }
+        fn placeholder(name: &str) -> PatternElement {
+            PatternElement::Placeholder(Placeholder::new(SmolStr::new(name), Vec::new()))
+        }
+        let result: SsrRule = "foo($a, $b) ==>> bar($b, $a)".parse().unwrap();
+        assert_eq!(
+            result.pattern.raw.tokens,
+            vec![
+                token(SyntaxKind::IDENT, "foo"),
+                token(T!['('], "("),
+                placeholder("a"),
+                token(T![,], ","),
+                token(SyntaxKind::WHITESPACE, " "),
+                placeholder("b"),
+                token(T![')'], ")"),
+            ]
+        );
+        assert_eq!(
+            result.template.tokens,
+            vec![
+                token(SyntaxKind::IDENT, "bar"),
+                token(T!['('], "("),
+                placeholder("b"),
+                token(T![,], ","),
+                token(SyntaxKind::WHITESPACE, " "),
+                placeholder("a"),
+                token(T![')'], ")"),
+            ]
+        );
+    }
+}
diff --git a/crates/ra_ssr/src/replacing.rs b/crates/ra_ssr/src/replacing.rs
new file mode 100644
index 000000000..e43cc5167
--- /dev/null
+++ b/crates/ra_ssr/src/replacing.rs
@@ -0,0 +1,66 @@
+//! 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 ra_syntax::ast::AstToken;
+use ra_syntax::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())
+}
+
+fn matches_to_edit_at_offset(
+    matches: &SsrMatches,
+    file_src: &str,
+    relative_start: TextSize,
+) -> 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),
+        );
+    }
+    edit_builder.finish()
+}
+
+fn render_replace(match_info: &Match, file_src: &str) -> String {
+    let mut out = String::new();
+    for r in &match_info.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
+                    );
+                }
+            }
+        }
+    }
+    for comment in &match_info.ignored_comments {
+        out.push_str(&comment.syntax().to_string());
+    }
+    out
+}
diff --git a/crates/ra_ssr/src/tests.rs b/crates/ra_ssr/src/tests.rs
new file mode 100644
index 000000000..f20ae2cdf
--- /dev/null
+++ b/crates/ra_ssr/src/tests.rs
@@ -0,0 +1,582 @@
+use crate::{MatchFinder, SsrRule};
+use ra_db::{FileId, SourceDatabaseExt};
+use test_utils::mark;
+
+fn parse_error_text(query: &str) -> String {
+    format!("{}", query.parse::<SsrRule>().unwrap_err())
+}
+
+#[test]
+fn parser_empty_query() {
+    assert_eq!(parse_error_text(""), "Parse error: Cannot find delimiter `==>>`");
+}
+
+#[test]
+fn parser_no_delimiter() {
+    assert_eq!(parse_error_text("foo()"), "Parse error: Cannot find delimiter `==>>`");
+}
+
+#[test]
+fn parser_two_delimiters() {
+    assert_eq!(
+        parse_error_text("foo() ==>> a ==>> b "),
+        "Parse error: More than one delimiter found"
+    );
+}
+
+#[test]
+fn parser_repeated_name() {
+    assert_eq!(
+        parse_error_text("foo($a, $a) ==>>"),
+        "Parse error: Name `a` repeats more than once"
+    );
+}
+
+#[test]
+fn parser_invalid_pattern() {
+    assert_eq!(
+        parse_error_text(" ==>> ()"),
+        "Parse error: Pattern is not a valid Rust expression, type, item, path or pattern"
+    );
+}
+
+#[test]
+fn parser_invalid_template() {
+    assert_eq!(
+        parse_error_text("() ==>> )"),
+        "Parse error: Replacement is not a valid Rust expression, type, item, path or pattern"
+    );
+}
+
+#[test]
+fn parser_undefined_placeholder_in_replacement() {
+    assert_eq!(
+        parse_error_text("42 ==>> $a"),
+        "Parse error: Replacement contains undefined placeholders: $a"
+    );
+}
+
+fn single_file(code: &str) -> (ra_ide_db::RootDatabase, FileId) {
+    use ra_db::fixture::WithFixture;
+    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 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) {
+    let (db, file_id) = single_file(input);
+    let mut match_finder = MatchFinder::new(&db);
+    for rule in rules {
+        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 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);
+    } else {
+        panic!("No edits were made");
+    }
+}
+
+fn print_match_debug_info(match_finder: &MatchFinder, file_id: FileId, snippet: &str) {
+    let debug_info = match_finder.debug_where_text_equal(file_id, snippet);
+    println!(
+        "Match debug info: {} nodes had text exactly equal to '{}'",
+        debug_info.len(),
+        snippet
+    );
+    for (index, d) in debug_info.iter().enumerate() {
+        println!("Node #{}\n{:#?}\n", index, d);
+    }
+}
+
+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();
+    if matched_strings != expected && !expected.is_empty() {
+        print_match_debug_info(&match_finder, 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);
+    match_finder.add_search_pattern(pattern.parse().unwrap());
+    let matches = match_finder.find_matches_in_file(file_id).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);
+    }
+}
+
+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);
+    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) {
+        if let Some(reason) = d.match_failure_reason() {
+            reasons.push(reason.to_owned());
+        }
+    }
+    assert_eq!(reasons, vec![expected_reason]);
+}
+
+#[test]
+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) } }",
+    )
+}
+
+#[test]
+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)) }",
+    )
+}
+
+#[test]
+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) }",
+    );
+}
+
+#[test]
+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) }",
+    );
+}
+
+#[test]
+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 */)) }",
+    )
+}
+
+#[test]
+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 */ }",
+    )
+}
+
+#[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} }",
+        "fn foo() {} fn main() { foo::new(1, 2) }",
+    )
+}
+
+#[test]
+fn ignores_whitespace() {
+    assert_matches("1+2", "fn f() -> i32 {1  +  2}", &["1  +  2"]);
+    assert_matches("1 + 2", "fn f() -> i32 {1+2}", &["1+2"]);
+}
+
+#[test]
+fn no_match() {
+    assert_no_match("1 + 3", "fn f() -> i32 {1  +  2}");
+}
+
+#[test]
+fn match_fn_definition() {
+    assert_matches("fn $a($b: $t) {$c}", "fn f(a: i32) {bar()}", &["fn f(a: i32) {bar()}"]);
+}
+
+#[test]
+fn match_struct_definition() {
+    let code = r#"
+        struct Option<T> {}
+        struct Bar {}
+        struct Foo {name: Option<String>}"#;
+    assert_matches("struct $n {$f: Option<String>}", code, &["struct Foo {name: Option<String>}"]);
+}
+
+#[test]
+fn match_expr() {
+    let code = r#"
+        fn foo() {}
+        fn f() -> i32 {foo(40 + 2, 42)}"#;
+    assert_matches("foo($a, $b)", code, &["foo(40 + 2, 42)"]);
+    assert_no_match("foo($a, $b, $c)", code);
+    assert_no_match("foo($a)", code);
+}
+
+#[test]
+fn match_nested_method_calls() {
+    assert_matches(
+        "$a.z().z().z()",
+        "fn f() {h().i().j().z().z().z().d().e()}",
+        &["h().i().j().z().z().z()"],
+    );
+}
+
+// Make sure that our node matching semantics don't differ within macro calls.
+#[test]
+fn match_nested_method_calls_with_macro_call() {
+    assert_matches(
+        "$a.z().z().z()",
+        r#"
+            macro_rules! m1 { ($a:expr) => {$a}; }
+            fn f() {m1!(h().i().j().z().z().z().d().e())}"#,
+        &["h().i().j().z().z().z()"],
+    );
+}
+
+#[test]
+fn match_complex_expr() {
+    let code = r#"
+        fn foo() {} fn bar() {}
+        fn f() -> i32 {foo(bar(40, 2), 42)}"#;
+    assert_matches("foo($a, $b)", code, &["foo(bar(40, 2), 42)"]);
+    assert_no_match("foo($a, $b, $c)", code);
+    assert_no_match("foo($a)", code);
+    assert_matches("bar($a, $b)", code, &["bar(40, 2)"]);
+}
+
+// Trailing commas in the code should be ignored.
+#[test]
+fn match_with_trailing_commas() {
+    // Code has comma, pattern doesn't.
+    assert_matches("foo($a, $b)", "fn foo() {} fn f() {foo(1, 2,);}", &["foo(1, 2,)"]);
+    assert_matches("Foo{$a, $b}", "struct Foo {} fn f() {Foo{1, 2,};}", &["Foo{1, 2,}"]);
+
+    // Pattern has comma, code doesn't.
+    assert_matches("foo($a, $b,)", "fn foo() {} fn f() {foo(1, 2);}", &["foo(1, 2)"]);
+    assert_matches("Foo{$a, $b,}", "struct Foo {} fn f() {Foo{1, 2};}", &["Foo{1, 2}"]);
+}
+
+#[test]
+fn match_type() {
+    assert_matches("i32", "fn f() -> i32 {1  +  2}", &["i32"]);
+    assert_matches(
+        "Option<$a>",
+        "struct Option<T> {} fn f() -> Option<i32> {42}",
+        &["Option<i32>"],
+    );
+    assert_no_match(
+        "Option<$a>",
+        "struct Option<T> {} struct Result<T, E> {} fn f() -> Result<i32, ()> {42}",
+    );
+}
+
+#[test]
+fn match_struct_instantiation() {
+    let code = r#"
+        struct Foo {bar: i32, baz: i32}
+        fn f() {Foo {bar: 1, baz: 2}}"#;
+    assert_matches("Foo {bar: 1, baz: 2}", code, &["Foo {bar: 1, baz: 2}"]);
+    // Now with placeholders for all parts of the struct.
+    assert_matches("Foo {$a: $b, $c: $d}", code, &["Foo {bar: 1, baz: 2}"]);
+    assert_matches("Foo {}", "struct Foo {} fn f() {Foo {}}", &["Foo {}"]);
+}
+
+#[test]
+fn match_path() {
+    let code = r#"
+        mod foo {
+            fn bar() {}
+        }
+        fn f() {foo::bar(42)}"#;
+    assert_matches("foo::bar", code, &["foo::bar"]);
+    assert_matches("$a::bar", code, &["foo::bar"]);
+    assert_matches("foo::$b", code, &["foo::bar"]);
+}
+
+#[test]
+fn match_pattern() {
+    assert_matches("Some($a)", "struct Some(); fn f() {if let Some(x) = foo() {}}", &["Some(x)"]);
+}
+
+#[test]
+fn literal_constraint() {
+    mark::check!(literal_constraint);
+    let code = r#"
+        enum Option<T> { Some(T), None }
+        use Option::Some;
+        fn f1() {
+            let x1 = Some(42);
+            let x2 = Some("foo");
+            let x3 = Some(x1);
+            let x4 = Some(40 + 2);
+            let x5 = Some(true);
+        }
+        "#;
+    assert_matches("Some(${a:kind(literal)})", code, &["Some(42)", "Some(\"foo\")", "Some(true)"]);
+    assert_matches("Some(${a:not(kind(literal))})", code, &["Some(x1)", "Some(40 + 2)"]);
+}
+
+#[test]
+fn match_reordered_struct_instantiation() {
+    assert_matches(
+        "Foo {aa: 1, b: 2, ccc: 3}",
+        "struct Foo {} fn f() {Foo {b: 2, ccc: 3, aa: 1}}",
+        &["Foo {b: 2, ccc: 3, aa: 1}"],
+    );
+    assert_no_match("Foo {a: 1}", "struct Foo {} fn f() {Foo {b: 1}}");
+    assert_no_match("Foo {a: 1}", "struct Foo {} fn f() {Foo {a: 2}}");
+    assert_no_match("Foo {a: 1, b: 2}", "struct Foo {} fn f() {Foo {a: 1}}");
+    assert_no_match("Foo {a: 1, b: 2}", "struct Foo {} fn f() {Foo {b: 2}}");
+    assert_no_match("Foo {a: 1, }", "struct Foo {} fn f() {Foo {a: 1, b: 2}}");
+    assert_no_match("Foo {a: 1, z: 9}", "struct Foo {} fn f() {Foo {a: 1}}");
+}
+
+#[test]
+fn match_macro_invocation() {
+    assert_matches(
+        "foo!($a)",
+        "macro_rules! foo {() => {}} fn() {foo(foo!(foo()))}",
+        &["foo!(foo())"],
+    );
+    assert_matches(
+        "foo!(41, $a, 43)",
+        "macro_rules! foo {() => {}} fn() {foo!(41, 42, 43)}",
+        &["foo!(41, 42, 43)"],
+    );
+    assert_no_match("foo!(50, $a, 43)", "macro_rules! foo {() => {}} fn() {foo!(41, 42, 43}");
+    assert_no_match("foo!(41, $a, 50)", "macro_rules! foo {() => {}} fn() {foo!(41, 42, 43}");
+    assert_matches(
+        "foo!($a())",
+        "macro_rules! foo {() => {}} fn() {foo!(bar())}",
+        &["foo!(bar())"],
+    );
+}
+
+// When matching within a macro expansion, we only allow matches of nodes that originated from
+// the macro call, not from the macro definition.
+#[test]
+fn no_match_expression_from_macro() {
+    assert_no_match(
+        "$a.clone()",
+        r#"
+            macro_rules! m1 {
+                () => {42.clone()}
+            }
+            fn f1() {m1!()}
+            "#,
+    );
+}
+
+// We definitely don't want to allow matching of an expression that part originates from the
+// macro call `42` and part from the macro definition `.clone()`.
+#[test]
+fn no_match_split_expression() {
+    assert_no_match(
+        "$a.clone()",
+        r#"
+            macro_rules! m1 {
+                ($x:expr) => {$x.clone()}
+            }
+            fn f1() {m1!(42)}
+            "#,
+    );
+}
+
+#[test]
+fn replace_function_call() {
+    assert_ssr_transform(
+        "foo() ==>> bar()",
+        "fn foo() {} fn f1() {foo(); foo();}",
+        "fn foo() {} fn f1() {bar(); bar();}",
+    );
+}
+
+#[test]
+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)}",
+    );
+}
+
+#[test]
+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))}",
+    );
+}
+
+#[test]
+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()}",
+    );
+}
+
+#[test]
+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)}",
+    );
+}
+
+#[test]
+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()?);}",
+    );
+    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);}",
+    );
+}
+
+#[test]
+fn replace_binary_op() {
+    assert_ssr_transform(
+        "$a + $b ==>> $b + $a",
+        "fn f() {2 * 3 + 4 * 5}",
+        "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}",
+    );
+}
+
+#[test]
+fn match_binary_op() {
+    assert_matches("$a + $b", "fn f() {1 + 2 + 3 + 4}", &["1 + 2", "1 + 2 + 3", "1 + 2 + 3 + 4"]);
+}
+
+#[test]
+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))}",
+    )
+}
+
+#[test]
+fn match_within_macro_invocation() {
+    let code = r#"
+            macro_rules! foo {
+                ($a:stmt; $b:expr) => {
+                    $b
+                };
+            }
+            struct A {}
+            impl A {
+                fn bar() {}
+            }
+            fn f1() {
+                let aaa = A {};
+                foo!(macro_ignores_this(); aaa.bar());
+            }
+        "#;
+    assert_matches("$a.bar()", code, &["aaa.bar()"]);
+}
+
+#[test]
+fn replace_within_macro_expansion() {
+    assert_ssr_transform(
+        "$a.foo() ==>> bar($a)",
+        r#"
+            macro_rules! macro1 {
+                ($a:expr) => {$a}
+            }
+            fn f() {macro1!(5.x().foo().o2())}"#,
+        r#"
+            macro_rules! macro1 {
+                ($a:expr) => {$a}
+            }
+            fn f() {macro1!(bar(5.x()).o2())}"#,
+    )
+}
+
+#[test]
+fn preserves_whitespace_within_macro_expansion() {
+    assert_ssr_transform(
+        "$a + $b ==>> $b - $a",
+        r#"
+            macro_rules! macro1 {
+                ($a:expr) => {$a}
+            }
+            fn f() {macro1!(1   *   2 + 3 + 4}"#,
+        r#"
+            macro_rules! macro1 {
+                ($a:expr) => {$a}
+            }
+            fn f() {macro1!(4 - 3 - 1   *   2}"#,
+    )
+}
+
+#[test]
+fn match_failure_reasons() {
+    let code = r#"
+        fn bar() {}
+        macro_rules! foo {
+            ($a:expr) => {
+                1 + $a + 2
+            };
+        }
+        fn f1() {
+            bar(1, 2);
+            foo!(5 + 43.to_string() + 5);
+        }
+        "#;
+    assert_match_failure_reason(
+        "bar($a, 3)",
+        code,
+        "bar(1, 2)",
+        r#"Pattern wanted token '3' (INT_NUMBER), but code had token '2' (INT_NUMBER)"#,
+    );
+    assert_match_failure_reason(
+        "42.to_string()",
+        code,
+        "43.to_string()",
+        r#"Pattern wanted token '42' (INT_NUMBER), but code had token '43' (INT_NUMBER)"#,
+    );
+}