9 files changed, 873 insertions, 25 deletions

diff --git a/crates/ra_ide/src/completion.rs b/crates/ra_ide/src/completion.rs
index fedc02e14..4bdc6ba23 100644
--- a/crates/ra_ide/src/completion.rs
+++ b/crates/ra_ide/src/completion.rs
@@ -15,6 +15,7 @@ mod complete_path;
 mod complete_scope;
 mod complete_postfix;
 mod complete_macro_in_item_position;
+mod complete_trait_impl;
 
 use ra_db::SourceDatabase;
 use ra_ide_db::RootDatabase;
@@ -74,5 +75,7 @@ pub(crate) fn completions(db: &RootDatabase, position: FilePosition) -> Option<C
     complete_pattern::complete_pattern(&mut acc, &ctx);
     complete_postfix::complete_postfix(&mut acc, &ctx);
     complete_macro_in_item_position::complete_macro_in_item_position(&mut acc, &ctx);
+    complete_trait_impl::complete_trait_impl(&mut acc, &ctx);
+
     Some(acc)
 }
diff --git a/crates/ra_ide/src/completion/complete_trait_impl.rs b/crates/ra_ide/src/completion/complete_trait_impl.rs
new file mode 100644
index 000000000..6ff10c017
--- /dev/null
+++ b/crates/ra_ide/src/completion/complete_trait_impl.rs
@@ -0,0 +1,436 @@
+//! Completion for associated items in a trait implementation.
+//!
+//! This module adds the completion items related to implementing associated
+//! items within a `impl Trait for Struct` block. The current context node
+//! must be within either a `FN_DEF`, `TYPE_ALIAS_DEF`, or `CONST_DEF` node
+//! and an direct child of an `IMPL_BLOCK`.
+//!
+//! # Examples
+//!
+//! Considering the following trait `impl`:
+//!
+//! ```ignore
+//! trait SomeTrait {
+//!     fn foo();
+//! }
+//!
+//! impl SomeTrait for () {
+//!     fn f<|>
+//! }
+//! ```
+//!
+//! may result in the completion of the following method:
+//!
+//! ```ignore
+//! # trait SomeTrait {
+//! #    fn foo();
+//! # }
+//!
+//! impl SomeTrait for () {
+//!     fn foo() {}<|>
+//! }
+//! ```
+
+use hir::{self, Docs, HasSource};
+use ra_assists::utils::get_missing_impl_items;
+use ra_syntax::{
+    ast::{self, edit},
+    AstNode, SyntaxKind, SyntaxNode, TextRange,
+};
+use ra_text_edit::TextEdit;
+
+use crate::{
+    completion::{
+        CompletionContext, CompletionItem, CompletionItemKind, CompletionKind, Completions,
+    },
+    display::FunctionSignature,
+};
+
+pub(crate) fn complete_trait_impl(acc: &mut Completions, ctx: &CompletionContext) {
+    let trigger = ctx.token.ancestors().find(|p| match p.kind() {
+        SyntaxKind::FN_DEF
+        | SyntaxKind::TYPE_ALIAS_DEF
+        | SyntaxKind::CONST_DEF
+        | SyntaxKind::BLOCK_EXPR => true,
+        _ => false,
+    });
+
+    let impl_block = trigger
+        .as_ref()
+        .and_then(|node| node.parent())
+        .and_then(|node| node.parent())
+        .and_then(|node| ast::ImplBlock::cast(node));
+
+    if let (Some(trigger), Some(impl_block)) = (trigger, impl_block) {
+        match trigger.kind() {
+            SyntaxKind::FN_DEF => {
+                for missing_fn in get_missing_impl_items(ctx.db, &ctx.analyzer, &impl_block)
+                    .iter()
+                    .filter_map(|item| match item {
+                        hir::AssocItem::Function(fn_item) => Some(fn_item),
+                        _ => None,
+                    })
+                {
+                    add_function_impl(&trigger, acc, ctx, &missing_fn);
+                }
+            }
+
+            SyntaxKind::TYPE_ALIAS_DEF => {
+                for missing_fn in get_missing_impl_items(ctx.db, &ctx.analyzer, &impl_block)
+                    .iter()
+                    .filter_map(|item| match item {
+                        hir::AssocItem::TypeAlias(type_item) => Some(type_item),
+                        _ => None,
+                    })
+                {
+                    add_type_alias_impl(&trigger, acc, ctx, &missing_fn);
+                }
+            }
+
+            SyntaxKind::CONST_DEF => {
+                for missing_fn in get_missing_impl_items(ctx.db, &ctx.analyzer, &impl_block)
+                    .iter()
+                    .filter_map(|item| match item {
+                        hir::AssocItem::Const(const_item) => Some(const_item),
+                        _ => None,
+                    })
+                {
+                    add_const_impl(&trigger, acc, ctx, &missing_fn);
+                }
+            }
+
+            _ => {}
+        }
+    }
+}
+
+fn add_function_impl(
+    fn_def_node: &SyntaxNode,
+    acc: &mut Completions,
+    ctx: &CompletionContext,
+    func: &hir::Function,
+) {
+    let display = FunctionSignature::from_hir(ctx.db, func.clone());
+
+    let fn_name = func.name(ctx.db).to_string();
+
+    let label = if func.params(ctx.db).len() > 0 {
+        format!("fn {}(..)", fn_name)
+    } else {
+        format!("fn {}()", fn_name)
+    };
+
+    let builder = CompletionItem::new(CompletionKind::Magic, ctx.source_range(), label.clone())
+        .lookup_by(fn_name)
+        .set_documentation(func.docs(ctx.db));
+
+    let completion_kind = if func.has_self_param(ctx.db) {
+        CompletionItemKind::Method
+    } else {
+        CompletionItemKind::Function
+    };
+
+    let snippet = format!("{} {{}}", display);
+
+    let range = TextRange::from_to(fn_def_node.text_range().start(), ctx.source_range().end());
+
+    builder.text_edit(TextEdit::replace(range, snippet)).kind(completion_kind).add_to(acc);
+}
+
+fn add_type_alias_impl(
+    type_def_node: &SyntaxNode,
+    acc: &mut Completions,
+    ctx: &CompletionContext,
+    type_alias: &hir::TypeAlias,
+) {
+    let alias_name = type_alias.name(ctx.db).to_string();
+
+    let snippet = format!("type {} = ", alias_name);
+
+    let range = TextRange::from_to(type_def_node.text_range().start(), ctx.source_range().end());
+
+    CompletionItem::new(CompletionKind::Magic, ctx.source_range(), snippet.clone())
+        .text_edit(TextEdit::replace(range, snippet))
+        .lookup_by(alias_name)
+        .kind(CompletionItemKind::TypeAlias)
+        .set_documentation(type_alias.docs(ctx.db))
+        .add_to(acc);
+}
+
+fn add_const_impl(
+    const_def_node: &SyntaxNode,
+    acc: &mut Completions,
+    ctx: &CompletionContext,
+    const_: &hir::Const,
+) {
+    let const_name = const_.name(ctx.db).map(|n| n.to_string());
+
+    if let Some(const_name) = const_name {
+        let snippet = make_const_compl_syntax(&const_.source(ctx.db).value);
+
+        let range =
+            TextRange::from_to(const_def_node.text_range().start(), ctx.source_range().end());
+
+        CompletionItem::new(CompletionKind::Magic, ctx.source_range(), snippet.clone())
+            .text_edit(TextEdit::replace(range, snippet))
+            .lookup_by(const_name)
+            .kind(CompletionItemKind::Const)
+            .set_documentation(const_.docs(ctx.db))
+            .add_to(acc);
+    }
+}
+
+fn make_const_compl_syntax(const_: &ast::ConstDef) -> String {
+    let const_ = edit::strip_attrs_and_docs(const_);
+
+    let const_start = const_.syntax().text_range().start();
+    let const_end = const_.syntax().text_range().end();
+
+    let start =
+        const_.syntax().first_child_or_token().map_or(const_start, |f| f.text_range().start());
+
+    let end = const_
+        .syntax()
+        .children_with_tokens()
+        .find(|s| s.kind() == SyntaxKind::SEMI || s.kind() == SyntaxKind::EQ)
+        .map_or(const_end, |f| f.text_range().start());
+
+    let len = end - start;
+    let range = TextRange::from_to(0.into(), len);
+
+    let syntax = const_.syntax().text().slice(range).to_string();
+
+    format!("{} = ", syntax.trim_end())
+}
+
+#[cfg(test)]
+mod tests {
+    use crate::completion::{do_completion, CompletionItem, CompletionKind};
+    use insta::assert_debug_snapshot;
+
+    fn complete(code: &str) -> Vec<CompletionItem> {
+        do_completion(code, CompletionKind::Magic)
+    }
+
+    #[test]
+    fn single_function() {
+        let completions = complete(
+            r"
+            trait Test {
+                fn foo();
+            }
+
+            struct T1;
+
+            impl Test for T1 {
+                fn f<|>
+            }
+            ",
+        );
+        assert_debug_snapshot!(completions, @r###"
+        [
+            CompletionItem {
+                label: "fn foo()",
+                source_range: [141; 142),
+                delete: [138; 142),
+                insert: "fn foo() {}",
+                kind: Function,
+                lookup: "foo",
+            },
+        ]
+        "###);
+    }
+
+    #[test]
+    fn hide_implemented_fn() {
+        let completions = complete(
+            r"
+            trait Test {
+                fn foo();
+                fn foo_bar();
+            }
+
+            struct T1;
+
+            impl Test for T1 {
+                fn foo() {}
+
+                fn f<|>
+            }
+            ",
+        );
+        assert_debug_snapshot!(completions, @r###"
+        [
+            CompletionItem {
+                label: "fn foo_bar()",
+                source_range: [200; 201),
+                delete: [197; 201),
+                insert: "fn foo_bar() {}",
+                kind: Function,
+                lookup: "foo_bar",
+            },
+        ]
+        "###);
+    }
+
+    #[test]
+    fn completes_only_on_top_level() {
+        let completions = complete(
+            r"
+            trait Test {
+                fn foo();
+
+                fn foo_bar();
+            }
+
+            struct T1;
+
+            impl Test for T1 {
+                fn foo() {
+                    <|>
+                }
+            }
+            ",
+        );
+        assert_debug_snapshot!(completions, @r###"[]"###);
+    }
+
+    #[test]
+    fn generic_fn() {
+        let completions = complete(
+            r"
+            trait Test {
+                fn foo<T>();
+            }
+
+            struct T1;
+
+            impl Test for T1 {
+                fn f<|>
+            }
+            ",
+        );
+        assert_debug_snapshot!(completions, @r###"
+        [
+            CompletionItem {
+                label: "fn foo()",
+                source_range: [144; 145),
+                delete: [141; 145),
+                insert: "fn foo<T>() {}",
+                kind: Function,
+                lookup: "foo",
+            },
+        ]
+        "###);
+    }
+
+    #[test]
+    fn generic_constrait_fn() {
+        let completions = complete(
+            r"
+            trait Test {
+                fn foo<T>() where T: Into<String>;
+            }
+
+            struct T1;
+
+            impl Test for T1 {
+                fn f<|>
+            }
+            ",
+        );
+        assert_debug_snapshot!(completions, @r###"
+        [
+            CompletionItem {
+                label: "fn foo()",
+                source_range: [166; 167),
+                delete: [163; 167),
+                insert: "fn foo<T>()\nwhere T: Into<String> {}",
+                kind: Function,
+                lookup: "foo",
+            },
+        ]
+        "###);
+    }
+
+    #[test]
+    fn associated_type() {
+        let completions = complete(
+            r"
+            trait Test {
+                type SomeType;
+            }
+
+            impl Test for () {
+                type S<|>
+            }
+            ",
+        );
+        assert_debug_snapshot!(completions, @r###"
+        [
+            CompletionItem {
+                label: "type SomeType = ",
+                source_range: [124; 125),
+                delete: [119; 125),
+                insert: "type SomeType = ",
+                kind: TypeAlias,
+                lookup: "SomeType",
+            },
+        ]
+        "###);
+    }
+
+    #[test]
+    fn associated_const() {
+        let completions = complete(
+            r"
+            trait Test {
+                const SOME_CONST: u16;
+            }
+
+            impl Test for () {
+                const S<|>
+            }
+            ",
+        );
+        assert_debug_snapshot!(completions, @r###"
+        [
+            CompletionItem {
+                label: "const SOME_CONST: u16 = ",
+                source_range: [133; 134),
+                delete: [127; 134),
+                insert: "const SOME_CONST: u16 = ",
+                kind: Const,
+                lookup: "SOME_CONST",
+            },
+        ]
+        "###);
+    }
+
+    #[test]
+    fn associated_const_with_default() {
+        let completions = complete(
+            r"
+            trait Test {
+                const SOME_CONST: u16 = 42;
+            }
+
+            impl Test for () {
+                const S<|>
+            }
+            ",
+        );
+        assert_debug_snapshot!(completions, @r###"
+        [
+            CompletionItem {
+                label: "const SOME_CONST: u16 = ",
+                source_range: [138; 139),
+                delete: [132; 139),
+                insert: "const SOME_CONST: u16 = ",
+                kind: Const,
+                lookup: "SOME_CONST",
+            },
+        ]
+        "###);
+    }
+}
diff --git a/crates/ra_ide/src/completion/completion_context.rs b/crates/ra_ide/src/completion/completion_context.rs
index 5a0407fd7..8678a3234 100644
--- a/crates/ra_ide/src/completion/completion_context.rs
+++ b/crates/ra_ide/src/completion/completion_context.rs
@@ -25,6 +25,7 @@ pub(crate) struct CompletionContext<'a> {
     pub(super) use_item_syntax: Option<ast::UseItem>,
     pub(super) record_lit_syntax: Option<ast::RecordLit>,
     pub(super) record_lit_pat: Option<ast::RecordPat>,
+    pub(super) impl_block: Option<ast::ImplBlock>,
     pub(super) is_param: bool,
     /// If a name-binding or reference to a const in a pattern.
     /// Irrefutable patterns (like let) are excluded.
@@ -72,6 +73,7 @@ impl<'a> CompletionContext<'a> {
             use_item_syntax: None,
             record_lit_syntax: None,
             record_lit_pat: None,
+            impl_block: None,
             is_param: false,
             is_pat_binding: false,
             is_trivial_path: false,
@@ -148,6 +150,13 @@ impl<'a> CompletionContext<'a> {
             self.record_lit_syntax = find_node_at_offset(original_file.syntax(), self.offset);
         }
 
+        self.impl_block = self
+            .token
+            .parent()
+            .ancestors()
+            .take_while(|it| it.kind() != SOURCE_FILE && it.kind() != MODULE)
+            .find_map(ast::ImplBlock::cast);
+
         let top_node = name_ref
             .syntax()
             .ancestors()
diff --git a/crates/ra_ide/src/lib.rs b/crates/ra_ide/src/lib.rs
index 689921f3f..f86f98be7 100644
--- a/crates/ra_ide/src/lib.rs
+++ b/crates/ra_ide/src/lib.rs
@@ -37,6 +37,7 @@ mod display;
 mod inlay_hints;
 mod expand;
 mod expand_macro;
+mod ssr;
 
 #[cfg(test)]
 mod marks;
@@ -71,8 +72,9 @@ pub use crate::{
     references::{
         Declaration, Reference, ReferenceAccess, ReferenceKind, ReferenceSearchResult, SearchScope,
     },
-    runnables::{Runnable, RunnableKind},
+    runnables::{Runnable, RunnableKind, TestId},
     source_change::{FileSystemEdit, SourceChange, SourceFileEdit},
+    ssr::SsrError,
     syntax_highlighting::HighlightedRange,
 };
 
@@ -464,6 +466,16 @@ impl Analysis {
         self.with_db(|db| references::rename(db, position, new_name))
     }
 
+    pub fn structural_search_replace(
+        &self,
+        query: &str,
+    ) -> Cancelable<Result<SourceChange, SsrError>> {
+        self.with_db(|db| {
+            let edits = ssr::parse_search_replace(query, db)?;
+            Ok(SourceChange::source_file_edits("ssr", edits))
+        })
+    }
+
     /// Performs an operation on that may be Canceled.
     fn with_db<F: FnOnce(&RootDatabase) -> T + std::panic::UnwindSafe, T>(
         &self,
diff --git a/crates/ra_ide/src/runnables.rs b/crates/ra_ide/src/runnables.rs
index b6b0c70f9..be2a67d0a 100644
--- a/crates/ra_ide/src/runnables.rs
+++ b/crates/ra_ide/src/runnables.rs
@@ -1,6 +1,6 @@
 //! FIXME: write short doc here
 
-use hir::InFile;
+use hir::{InFile, SourceBinder};
 use itertools::Itertools;
 use ra_db::SourceDatabase;
 use ra_ide_db::RootDatabase;
@@ -10,6 +10,7 @@ use ra_syntax::{
 };
 
 use crate::FileId;
+use std::fmt::Display;
 
 #[derive(Debug)]
 pub struct Runnable {
@@ -18,38 +19,84 @@ pub struct Runnable {
 }
 
 #[derive(Debug)]
+pub enum TestId {
+    Name(String),
+    Path(String),
+}
+
+impl Display for TestId {
+    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
+        match self {
+            TestId::Name(name) => write!(f, "{}", name),
+            TestId::Path(path) => write!(f, "{}", path),
+        }
+    }
+}
+
+#[derive(Debug)]
 pub enum RunnableKind {
-    Test { name: String },
+    Test { test_id: TestId },
     TestMod { path: String },
-    Bench { name: String },
+    Bench { test_id: TestId },
     Bin,
 }
 
 pub(crate) fn runnables(db: &RootDatabase, file_id: FileId) -> Vec<Runnable> {
     let parse = db.parse(file_id);
-    parse.tree().syntax().descendants().filter_map(|i| runnable(db, file_id, i)).collect()
+    let mut sb = SourceBinder::new(db);
+    parse.tree().syntax().descendants().filter_map(|i| runnable(db, &mut sb, file_id, i)).collect()
 }
 
-fn runnable(db: &RootDatabase, file_id: FileId, item: SyntaxNode) -> Option<Runnable> {
+fn runnable(
+    db: &RootDatabase,
+    source_binder: &mut SourceBinder<RootDatabase>,
+    file_id: FileId,
+    item: SyntaxNode,
+) -> Option<Runnable> {
     match_ast! {
         match item {
-            ast::FnDef(it) => { runnable_fn(it) },
-            ast::Module(it) => { runnable_mod(db, file_id, it) },
+            ast::FnDef(it) => { runnable_fn(db, source_binder, file_id, it) },
+            ast::Module(it) => { runnable_mod(db, source_binder, file_id, it) },
             _ => { None },
         }
     }
 }
 
-fn runnable_fn(fn_def: ast::FnDef) -> Option<Runnable> {
-    let name = fn_def.name()?.text().clone();
-    let kind = if name == "main" {
+fn runnable_fn(
+    db: &RootDatabase,
+    source_binder: &mut SourceBinder<RootDatabase>,
+    file_id: FileId,
+    fn_def: ast::FnDef,
+) -> Option<Runnable> {
+    let name_string = fn_def.name()?.text().to_string();
+
+    let kind = if name_string == "main" {
         RunnableKind::Bin
-    } else if has_test_related_attribute(&fn_def) {
-        RunnableKind::Test { name: name.to_string() }
-    } else if fn_def.has_atom_attr("bench") {
-        RunnableKind::Bench { name: name.to_string() }
     } else {
-        return None;
+        let test_id = if let Some(module) = source_binder
+            .to_def(InFile::new(file_id.into(), fn_def.clone()))
+            .map(|def| def.module(db))
+        {
+            let path = module
+                .path_to_root(db)
+                .into_iter()
+                .rev()
+                .filter_map(|it| it.name(db))
+                .map(|name| name.to_string())
+                .chain(std::iter::once(name_string))
+                .join("::");
+            TestId::Path(path)
+        } else {
+            TestId::Name(name_string)
+        };
+
+        if has_test_related_attribute(&fn_def) {
+            RunnableKind::Test { test_id }
+        } else if fn_def.has_atom_attr("bench") {
+            RunnableKind::Bench { test_id }
+        } else {
+            return None;
+        }
     };
     Some(Runnable { range: fn_def.syntax().text_range(), kind })
 }
@@ -68,7 +115,12 @@ fn has_test_related_attribute(fn_def: &ast::FnDef) -> bool {
         .any(|attribute_text| attribute_text.contains("test"))
 }
 
-fn runnable_mod(db: &RootDatabase, file_id: FileId, module: ast::Module) -> Option<Runnable> {
+fn runnable_mod(
+    db: &RootDatabase,
+    source_binder: &mut SourceBinder<RootDatabase>,
+    file_id: FileId,
+    module: ast::Module,
+) -> Option<Runnable> {
     let has_test_function = module
         .item_list()?
         .items()
@@ -76,13 +128,12 @@ fn runnable_mod(db: &RootDatabase, file_id: FileId, module: ast::Module) -> Opti
             ast::ModuleItem::FnDef(it) => Some(it),
             _ => None,
         })
-        .any(|f| f.has_atom_attr("test"));
+        .any(|f| has_test_related_attribute(&f));
     if !has_test_function {
         return None;
     }
     let range = module.syntax().text_range();
-    let mut sb = hir::SourceBinder::new(db);
-    let module = sb.to_def(InFile::new(file_id.into(), module))?;
+    let module = source_binder.to_def(InFile::new(file_id.into(), module))?;
 
     let path = module.path_to_root(db).into_iter().rev().filter_map(|it| it.name(db)).join("::");
     Some(Runnable { range, kind: RunnableKind::TestMod { path } })
@@ -121,13 +172,17 @@ mod tests {
             Runnable {
                 range: [22; 46),
                 kind: Test {
-                    name: "test_foo",
+                    test_id: Path(
+                        "test_foo",
+                    ),
                 },
             },
             Runnable {
                 range: [47; 81),
                 kind: Test {
-                    name: "test_foo",
+                    test_id: Path(
+                        "test_foo",
+                    ),
                 },
             },
         ]
@@ -160,7 +215,9 @@ mod tests {
             Runnable {
                 range: [28; 57),
                 kind: Test {
-                    name: "test_foo1",
+                    test_id: Path(
+                        "test_mod::test_foo1",
+                    ),
                 },
             },
         ]
@@ -195,7 +252,9 @@ mod tests {
             Runnable {
                 range: [46; 79),
                 kind: Test {
-                    name: "test_foo1",
+                    test_id: Path(
+                        "foo::test_mod::test_foo1",
+                    ),
                 },
             },
         ]
@@ -232,7 +291,9 @@ mod tests {
             Runnable {
                 range: [68; 105),
                 kind: Test {
-                    name: "test_foo1",
+                    test_id: Path(
+                        "foo::bar::test_mod::test_foo1",
+                    ),
                 },
             },
         ]
diff --git a/crates/ra_ide/src/snapshots/highlighting.html b/crates/ra_ide/src/snapshots/highlighting.html
index 1cc55e78b..a02dbaf2f 100644
--- a/crates/ra_ide/src/snapshots/highlighting.html
+++ b/crates/ra_ide/src/snapshots/highlighting.html
@@ -16,6 +16,7 @@ pre                 { color: #DCDCCC; background: #3F3F3F; font-size: 22px; padd
 .literal            { color: #BFEBBF; }
 .literal\.numeric  { color: #6A8759; }
 .macro              { color: #94BFF3; }
+.module             { color: #AFD8AF; }
 .variable           { color: #DCDCCC; }
 .variable\.mut     { color: #DCDCCC; text-decoration: underline; }
 
diff --git a/crates/ra_ide/src/snapshots/rainbow_highlighting.html b/crates/ra_ide/src/snapshots/rainbow_highlighting.html
index 918fd4b97..95f038f00 100644
--- a/crates/ra_ide/src/snapshots/rainbow_highlighting.html
+++ b/crates/ra_ide/src/snapshots/rainbow_highlighting.html
@@ -16,6 +16,7 @@ pre                 { color: #DCDCCC; background: #3F3F3F; font-size: 22px; padd
 .literal            { color: #BFEBBF; }
 .literal\.numeric  { color: #6A8759; }
 .macro              { color: #94BFF3; }
+.module             { color: #AFD8AF; }
 .variable           { color: #DCDCCC; }
 .variable\.mut     { color: #DCDCCC; text-decoration: underline; }
 
diff --git a/crates/ra_ide/src/ssr.rs b/crates/ra_ide/src/ssr.rs
new file mode 100644
index 000000000..14eb0b8b2
--- /dev/null
+++ b/crates/ra_ide/src/ssr.rs
@@ -0,0 +1,324 @@
+//!  structural search replace
+
+use crate::source_change::SourceFileEdit;
+use ra_ide_db::RootDatabase;
+use ra_syntax::ast::make::expr_from_text;
+use ra_syntax::AstNode;
+use ra_syntax::SyntaxElement;
+use ra_syntax::SyntaxNode;
+use ra_text_edit::{TextEdit, TextEditBuilder};
+use rustc_hash::FxHashMap;
+use std::collections::HashMap;
+use std::str::FromStr;
+
+pub use ra_db::{SourceDatabase, SourceDatabaseExt};
+use ra_ide_db::symbol_index::SymbolsDatabase;
+
+#[derive(Debug, PartialEq)]
+pub struct SsrError(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 std::error::Error for SsrError {}
+
+pub fn parse_search_replace(
+    query: &str,
+    db: &RootDatabase,
+) -> Result<Vec<SourceFileEdit>, SsrError> {
+    let mut edits = vec![];
+    let query: SsrQuery = query.parse()?;
+    for &root in db.local_roots().iter() {
+        let sr = db.source_root(root);
+        for file_id in sr.walk() {
+            dbg!(db.file_relative_path(file_id));
+            let matches = find(&query.pattern, db.parse(file_id).tree().syntax());
+            if !matches.matches.is_empty() {
+                edits.push(SourceFileEdit { file_id, edit: replace(&matches, &query.template) });
+            }
+        }
+    }
+    Ok(edits)
+}
+
+#[derive(Debug)]
+struct SsrQuery {
+    pattern: SsrPattern,
+    template: SsrTemplate,
+}
+
+#[derive(Debug)]
+struct SsrPattern {
+    pattern: SyntaxNode,
+    vars: Vec<Var>,
+}
+
+/// represents an `$var` in an SSR query
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
+struct Var(String);
+
+#[derive(Debug)]
+struct SsrTemplate {
+    template: SyntaxNode,
+    placeholders: FxHashMap<SyntaxNode, Var>,
+}
+
+type Binding = HashMap<Var, SyntaxNode>;
+
+#[derive(Debug)]
+struct Match {
+    place: SyntaxNode,
+    binding: Binding,
+}
+
+#[derive(Debug)]
+struct SsrMatches {
+    matches: Vec<Match>,
+}
+
+impl FromStr for SsrQuery {
+    type Err = SsrError;
+
+    fn from_str(query: &str) -> Result<SsrQuery, SsrError> {
+        let mut it = query.split("==>>");
+        let pattern = it.next().expect("at least empty string").trim();
+        let mut template =
+            it.next().ok_or(SsrError("Cannot find delemiter `==>>`".into()))?.trim().to_string();
+        if it.next().is_some() {
+            return Err(SsrError("More than one delimiter found".into()));
+        }
+        let mut vars = vec![];
+        let mut it = pattern.split('$');
+        let mut pattern = it.next().expect("something").to_string();
+
+        for part in it.map(split_by_var) {
+            let (var, var_type, remainder) = part?;
+            is_expr(var_type)?;
+            let new_var = create_name(var, &mut vars)?;
+            pattern.push_str(new_var);
+            pattern.push_str(remainder);
+            template = replace_in_template(template, var, new_var);
+        }
+
+        let template = expr_from_text(&template).syntax().clone();
+        let mut placeholders = FxHashMap::default();
+
+        traverse(&template, &mut |n| {
+            if let Some(v) = vars.iter().find(|v| v.0.as_str() == n.text()) {
+                placeholders.insert(n.clone(), v.clone());
+                false
+            } else {
+                true
+            }
+        });
+
+        let pattern = SsrPattern { pattern: expr_from_text(&pattern).syntax().clone(), vars };
+        let template = SsrTemplate { template, placeholders };
+        Ok(SsrQuery { pattern, template })
+    }
+}
+
+fn traverse(node: &SyntaxNode, go: &mut impl FnMut(&SyntaxNode) -> bool) {
+    if !go(node) {
+        return;
+    }
+    for ref child in node.children() {
+        traverse(child, go);
+    }
+}
+
+fn split_by_var(s: &str) -> Result<(&str, &str, &str), SsrError> {
+    let end_of_name = s.find(":").ok_or(SsrError("Use $<name>:expr".into()))?;
+    let name = &s[0..end_of_name];
+    is_name(name)?;
+    let type_begin = end_of_name + 1;
+    let type_length = s[type_begin..].find(|c| !char::is_ascii_alphanumeric(&c)).unwrap_or(s.len());
+    let type_name = &s[type_begin..type_begin + type_length];
+    Ok((name, type_name, &s[type_begin + type_length..]))
+}
+
+fn is_name(s: &str) -> Result<(), SsrError> {
+    if s.chars().all(|c| c.is_ascii_alphanumeric() || c == '_') {
+        Ok(())
+    } else {
+        Err(SsrError("Name can contain only alphanumerics and _".into()))
+    }
+}
+
+fn is_expr(s: &str) -> Result<(), SsrError> {
+    if s == "expr" {
+        Ok(())
+    } else {
+        Err(SsrError("Only $<name>:expr is supported".into()))
+    }
+}
+
+fn replace_in_template(template: String, var: &str, new_var: &str) -> String {
+    let name = format!("${}", var);
+    template.replace(&name, new_var)
+}
+
+fn create_name<'a>(name: &str, vars: &'a mut Vec<Var>) -> Result<&'a str, SsrError> {
+    let sanitized_name = format!("__search_pattern_{}", name);
+    if vars.iter().any(|a| a.0 == sanitized_name) {
+        return Err(SsrError(format!("Name `{}` repeats more than once", name)));
+    }
+    vars.push(Var(sanitized_name));
+    Ok(&vars.last().unwrap().0)
+}
+
+fn find(pattern: &SsrPattern, code: &SyntaxNode) -> SsrMatches {
+    fn check(
+        pattern: &SyntaxElement,
+        code: &SyntaxElement,
+        placeholders: &[Var],
+        match_: &mut Match,
+    ) -> bool {
+        match (pattern, code) {
+            (SyntaxElement::Token(ref pattern), SyntaxElement::Token(ref code)) => {
+                pattern.text() == code.text()
+            }
+            (SyntaxElement::Node(ref pattern), SyntaxElement::Node(ref code)) => {
+                if placeholders.iter().find(|&n| n.0.as_str() == pattern.text()).is_some() {
+                    match_.binding.insert(Var(pattern.text().to_string()), code.clone());
+                    true
+                } else {
+                    pattern.green().children().count() == code.green().children().count()
+                        && pattern
+                            .children_with_tokens()
+                            .zip(code.children_with_tokens())
+                            .all(|(a, b)| check(&a, &b, placeholders, match_))
+                }
+            }
+            _ => false,
+        }
+    }
+    let kind = pattern.pattern.kind();
+    let matches = code
+        .descendants_with_tokens()
+        .filter(|n| n.kind() == kind)
+        .filter_map(|code| {
+            let mut match_ =
+                Match { place: code.as_node().unwrap().clone(), binding: HashMap::new() };
+            if check(
+                &SyntaxElement::from(pattern.pattern.clone()),
+                &code,
+                &pattern.vars,
+                &mut match_,
+            ) {
+                Some(match_)
+            } else {
+                None
+            }
+        })
+        .collect();
+    SsrMatches { matches }
+}
+
+fn replace(matches: &SsrMatches, template: &SsrTemplate) -> TextEdit {
+    let mut builder = TextEditBuilder::default();
+    for match_ in &matches.matches {
+        builder.replace(match_.place.text_range(), render_replace(&match_.binding, template));
+    }
+    builder.finish()
+}
+
+fn render_replace(binding: &Binding, template: &SsrTemplate) -> String {
+    let mut builder = TextEditBuilder::default();
+    for element in template.template.descendants() {
+        if let Some(var) = template.placeholders.get(&element) {
+            builder.replace(element.text_range(), binding[var].to_string())
+        }
+    }
+    builder.finish().apply(&template.template.text().to_string())
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use ra_syntax::SourceFile;
+
+    fn parse_error_text(query: &str) -> String {
+        format!("{}", query.parse::<SsrQuery>().unwrap_err())
+    }
+
+    #[test]
+    fn parser_happy_case() {
+        let result: SsrQuery = "foo($a:expr, $b:expr) ==>> bar($b, $a)".parse().unwrap();
+        assert_eq!(&result.pattern.pattern.text(), "foo(__search_pattern_a, __search_pattern_b)");
+        assert_eq!(result.pattern.vars.len(), 2);
+        assert_eq!(result.pattern.vars[0].0, "__search_pattern_a");
+        assert_eq!(result.pattern.vars[1].0, "__search_pattern_b");
+        assert_eq!(&result.template.template.text(), "bar(__search_pattern_b, __search_pattern_a)");
+        dbg!(result.template.placeholders);
+    }
+
+    #[test]
+    fn parser_empty_query() {
+        assert_eq!(parse_error_text(""), "Parse error: Cannot find delemiter `==>>`");
+    }
+
+    #[test]
+    fn parser_no_delimiter() {
+        assert_eq!(parse_error_text("foo()"), "Parse error: Cannot find delemiter `==>>`");
+    }
+
+    #[test]
+    fn parser_two_delimiters() {
+        assert_eq!(
+            parse_error_text("foo() ==>> a ==>> b "),
+            "Parse error: More than one delimiter found"
+        );
+    }
+
+    #[test]
+    fn parser_no_pattern_type() {
+        assert_eq!(parse_error_text("foo($a) ==>>"), "Parse error: Use $<name>:expr");
+    }
+
+    #[test]
+    fn parser_invalid_name() {
+        assert_eq!(
+            parse_error_text("foo($a+:expr) ==>>"),
+            "Parse error: Name can contain only alphanumerics and _"
+        );
+    }
+
+    #[test]
+    fn parser_invalid_type() {
+        assert_eq!(
+            parse_error_text("foo($a:ident) ==>>"),
+            "Parse error: Only $<name>:expr is supported"
+        );
+    }
+
+    #[test]
+    fn parser_repeated_name() {
+        assert_eq!(
+            parse_error_text("foo($a:expr, $a:expr) ==>>"),
+            "Parse error: Name `a` repeats more than once"
+        );
+    }
+
+    #[test]
+    fn parse_match_replace() {
+        let query: SsrQuery = "foo($x:expr) ==>> bar($x)".parse().unwrap();
+        let input = "fn main() { foo(1+2); }";
+
+        let code = SourceFile::parse(input).tree();
+        let matches = find(&query.pattern, code.syntax());
+        assert_eq!(matches.matches.len(), 1);
+        assert_eq!(matches.matches[0].place.text(), "foo(1+2)");
+        assert_eq!(matches.matches[0].binding.len(), 1);
+        assert_eq!(
+            matches.matches[0].binding[&Var("__search_pattern_x".to_string())].text(),
+            "1+2"
+        );
+
+        let edit = replace(&matches, &query.template);
+        assert_eq!(edit.apply(input), "fn main() { bar(1+2); }");
+    }
+}
diff --git a/crates/ra_ide/src/syntax_highlighting.rs b/crates/ra_ide/src/syntax_highlighting.rs
index 174e13595..20c414ca1 100644
--- a/crates/ra_ide/src/syntax_highlighting.rs
+++ b/crates/ra_ide/src/syntax_highlighting.rs
@@ -365,6 +365,7 @@ pre                 { color: #DCDCCC; background: #3F3F3F; font-size: 22px; padd
 .literal            { color: #BFEBBF; }
 .literal\\.numeric  { color: #6A8759; }
 .macro              { color: #94BFF3; }
+.module             { color: #AFD8AF; }
 .variable           { color: #DCDCCC; }
 .variable\\.mut     { color: #DCDCCC; text-decoration: underline; }