7 files changed, 121 insertions, 31 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 74570a978..275b27775 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -903,6 +903,7 @@ dependencies = [
  "ra_hir 0.1.0",
  "ra_syntax 0.1.0",
  "ra_text_edit 0.1.0",
+ "rustc-hash 1.0.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "test_utils 0.1.0",
 ]
 
@@ -1088,6 +1089,7 @@ dependencies = [
  "ra_parser 0.1.0",
  "ra_text_edit 0.1.0",
  "rowan 0.6.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rustc-hash 1.0.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "rustc_lexer 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "smol_str 0.1.12 (registry+https://github.com/rust-lang/crates.io-index)",
  "test_utils 0.1.0",
diff --git a/crates/ra_assists/Cargo.toml b/crates/ra_assists/Cargo.toml
index 635d87611..02966bbda 100644
--- a/crates/ra_assists/Cargo.toml
+++ b/crates/ra_assists/Cargo.toml
@@ -10,6 +10,7 @@ once_cell = "1.0.1"
 join_to_string = "0.1.3"
 itertools = "0.8.0"
 arrayvec = "0.4.10"
+rustc-hash = "1.0.1"
 
 ra_syntax = { path = "../ra_syntax" }
 ra_text_edit = { path = "../ra_text_edit" }
diff --git a/crates/ra_assists/src/assists/move_bounds.rs b/crates/ra_assists/src/assists/move_bounds.rs
index 6fd2fb72b..671826013 100644
--- a/crates/ra_assists/src/assists/move_bounds.rs
+++ b/crates/ra_assists/src/assists/move_bounds.rs
@@ -3,10 +3,9 @@ use ra_syntax::{
     ast::{self, AstNode, NameOwner, TypeBoundsOwner},
     SyntaxElement,
     SyntaxKind::*,
-    TextRange,
 };
 
-use crate::{ast_builder::Make, Assist, AssistCtx, AssistId};
+use crate::{ast_builder::Make, ast_editor::AstEditor, Assist, AssistCtx, AssistId};
 
 pub(crate) fn move_bounds_to_where_clause(mut ctx: AssistCtx<impl HirDatabase>) -> Option<Assist> {
     let type_param_list = ctx.node_at_offset::<ast::TypeParamList>()?;
@@ -36,23 +35,23 @@ pub(crate) fn move_bounds_to_where_clause(mut ctx: AssistCtx<impl HirDatabase>)
         AssistId("move_bounds_to_where_clause"),
         "move_bounds_to_where_clause",
         |edit| {
-            let type_params = type_param_list.type_params().collect::<Vec<_>>();
-
-            for param in &type_params {
-                if let Some(bounds) = param.type_bound_list() {
-                    let colon = param
-                        .syntax()
-                        .children_with_tokens()
-                        .find(|it| it.kind() == COLON)
-                        .unwrap();
-                    let start = colon.text_range().start();
-                    let end = bounds.syntax().text_range().end();
-                    edit.delete(TextRange::from_to(start, end));
-                }
-            }
-
-            let predicates = type_params.iter().filter_map(build_predicate);
-            let where_clause = Make::<ast::WhereClause>::from_predicates(predicates);
+            let new_params = type_param_list
+                .type_params()
+                .filter(|it| it.type_bound_list().is_some())
+                .map(|type_param| {
+                    let without_bounds =
+                        AstEditor::new(type_param.clone()).remove_bounds().ast().clone();
+                    (type_param, without_bounds)
+                });
+
+            let mut ast_editor = AstEditor::new(type_param_list.clone());
+            ast_editor.replace_descendants(new_params);
+            ast_editor.into_text_edit(edit.text_edit_builder());
+
+            let where_clause = {
+                let predicates = type_param_list.type_params().filter_map(build_predicate);
+                Make::<ast::WhereClause>::from_predicates(predicates)
+            };
 
             let to_insert = match anchor.prev_sibling_or_token() {
                 Some(ref elem) if elem.kind() == WHITESPACE => {
@@ -68,7 +67,7 @@ pub(crate) fn move_bounds_to_where_clause(mut ctx: AssistCtx<impl HirDatabase>)
     ctx.build()
 }
 
-fn build_predicate(param: &ast::TypeParam) -> Option<ast::WherePred> {
+fn build_predicate(param: ast::TypeParam) -> Option<ast::WherePred> {
     let path = Make::<ast::Path>::from_name(param.name()?);
     let predicate = Make::<ast::WherePred>::from(path, param.type_bound_list()?.bounds());
     Some(predicate)
diff --git a/crates/ra_assists/src/ast_editor.rs b/crates/ra_assists/src/ast_editor.rs
index 55c0aa59f..4e253f0a4 100644
--- a/crates/ra_assists/src/ast_editor.rs
+++ b/crates/ra_assists/src/ast_editor.rs
@@ -1,11 +1,13 @@
 use std::{iter, ops::RangeInclusive};
 
 use arrayvec::ArrayVec;
+use rustc_hash::FxHashMap;
 
 use ra_fmt::leading_indent;
 use ra_syntax::{
-    algo::{insert_children, replace_children},
-    ast, AstNode, Direction, InsertPosition, SyntaxElement,
+    algo,
+    ast::{self, TypeBoundsOwner},
+    AstNode, Direction, InsertPosition, NodeOrToken, SyntaxElement,
     SyntaxKind::*,
     T,
 };
@@ -27,26 +29,55 @@ impl<N: AstNode> AstEditor<N> {
     }
 
     pub fn into_text_edit(self, builder: &mut TextEditBuilder) {
-        // FIXME: compute a more fine-grained diff here.
-        // If *you* know a nice algorithm to compute diff between two syntax
-        // tree, tell me about it!
-        builder.replace(
-            self.original_ast.syntax().text_range(),
-            self.ast().syntax().text().to_string(),
-        );
+        // FIXME: this is both horrible inefficient and gives larger than
+        // necessary diff. I bet there's a cool algorithm to diff trees properly.
+        go(builder, self.original_ast.syntax().clone().into(), self.ast().syntax().clone().into());
+
+        fn go(buf: &mut TextEditBuilder, lhs: SyntaxElement, rhs: SyntaxElement) {
+            if lhs.kind() == rhs.kind() && lhs.text_range().len() == rhs.text_range().len() {
+                if match (&lhs, &rhs) {
+                    (NodeOrToken::Node(lhs), NodeOrToken::Node(rhs)) => lhs.text() == rhs.text(),
+                    (NodeOrToken::Token(lhs), NodeOrToken::Token(rhs)) => lhs.text() == rhs.text(),
+                    _ => false,
+                } {
+                    return;
+                }
+            }
+            if let (Some(lhs), Some(rhs)) = (lhs.as_node(), rhs.as_node()) {
+                if lhs.children_with_tokens().count() == rhs.children_with_tokens().count() {
+                    for (lhs, rhs) in lhs.children_with_tokens().zip(rhs.children_with_tokens()) {
+                        go(buf, lhs, rhs)
+                    }
+                    return;
+                }
+            }
+            buf.replace(lhs.text_range(), rhs.to_string())
+        }
     }
 
     pub fn ast(&self) -> &N {
         &self.ast
     }
 
+    pub fn replace_descendants<T: AstNode>(
+        &mut self,
+        replacement_map: impl Iterator<Item = (T, T)>,
+    ) -> &mut Self {
+        let map = replacement_map
+            .map(|(from, to)| (from.syntax().clone().into(), to.syntax().clone().into()))
+            .collect::<FxHashMap<_, _>>();
+        let new_syntax = algo::replace_descendants(self.ast.syntax(), &map);
+        self.ast = N::cast(new_syntax).unwrap();
+        self
+    }
+
     #[must_use]
     fn insert_children(
         &self,
         position: InsertPosition<SyntaxElement>,
         mut to_insert: impl Iterator<Item = SyntaxElement>,
     ) -> N {
-        let new_syntax = insert_children(self.ast().syntax(), position, &mut to_insert);
+        let new_syntax = algo::insert_children(self.ast().syntax(), position, &mut to_insert);
         N::cast(new_syntax).unwrap()
     }
 
@@ -56,7 +87,7 @@ impl<N: AstNode> AstEditor<N> {
         to_delete: RangeInclusive<SyntaxElement>,
         mut to_insert: impl Iterator<Item = SyntaxElement>,
     ) -> N {
-        let new_syntax = replace_children(self.ast().syntax(), to_delete, &mut to_insert);
+        let new_syntax = algo::replace_children(self.ast().syntax(), to_delete, &mut to_insert);
         N::cast(new_syntax).unwrap()
     }
 
@@ -240,3 +271,18 @@ impl AstEditor<ast::FnDef> {
         self.ast = self.replace_children(replace_range, to_insert.into_iter())
     }
 }
+
+impl AstEditor<ast::TypeParam> {
+    pub fn remove_bounds(&mut self) -> &mut Self {
+        let colon = match self.ast.colon_token() {
+            Some(it) => it,
+            None => return self,
+        };
+        let end = match self.ast.type_bound_list() {
+            Some(it) => it.syntax().clone().into(),
+            None => colon.clone().into(),
+        };
+        self.ast = self.replace_children(RangeInclusive::new(colon.into(), end), iter::empty());
+        self
+    }
+}
diff --git a/crates/ra_syntax/Cargo.toml b/crates/ra_syntax/Cargo.toml
index d3a8b516a..724c38e17 100644
--- a/crates/ra_syntax/Cargo.toml
+++ b/crates/ra_syntax/Cargo.toml
@@ -11,6 +11,7 @@ repository = "https://github.com/rust-analyzer/rust-analyzer"
 itertools = "0.8.0"
 rowan = "0.6.1"
 rustc_lexer = "0.1.0"
+rustc-hash = "1.0.1"
 
 # ideally, `serde` should be enabled by `ra_lsp_server`, but we enable it here
 # to reduce number of compilations
diff --git a/crates/ra_syntax/src/algo.rs b/crates/ra_syntax/src/algo.rs
index 7ee5aa85b..f0ed96a17 100644
--- a/crates/ra_syntax/src/algo.rs
+++ b/crates/ra_syntax/src/algo.rs
@@ -3,6 +3,7 @@ pub mod visit;
 use std::ops::RangeInclusive;
 
 use itertools::Itertools;
+use rustc_hash::FxHashMap;
 
 use crate::{
     AstNode, Direction, NodeOrToken, SyntaxElement, SyntaxNode, SyntaxNodePtr, TextRange, TextUnit,
@@ -123,6 +124,37 @@ pub fn replace_children(
     with_children(parent, new_children)
 }
 
+/// Replaces descendants in the node, according to the mapping.
+///
+/// This is a type-unsafe low-level editing API, if you need to use it, prefer
+/// to create a type-safe abstraction on top of it instead.
+pub fn replace_descendants(
+    parent: &SyntaxNode,
+    map: &FxHashMap<SyntaxElement, SyntaxElement>,
+) -> SyntaxNode {
+    //  FIXME: this could be made much faster.
+    let new_children = parent.children_with_tokens().map(|it| go(map, it)).collect::<Box<[_]>>();
+    return with_children(parent, new_children);
+
+    fn go(
+        map: &FxHashMap<SyntaxElement, SyntaxElement>,
+        element: SyntaxElement,
+    ) -> NodeOrToken<rowan::GreenNode, rowan::GreenToken> {
+        if let Some(replacement) = map.get(&element) {
+            return match replacement {
+                NodeOrToken::Node(it) => NodeOrToken::Node(it.green().clone()),
+                NodeOrToken::Token(it) => NodeOrToken::Token(it.green().clone()),
+            };
+        }
+        match element {
+            NodeOrToken::Token(it) => NodeOrToken::Token(it.green().clone()),
+            NodeOrToken::Node(it) => {
+                NodeOrToken::Node(replace_descendants(&it, map).green().clone())
+            }
+        }
+    }
+}
+
 fn with_children(
     parent: &SyntaxNode,
     new_children: Box<[NodeOrToken<rowan::GreenNode, rowan::GreenToken>]>,
diff --git a/crates/ra_syntax/src/ast/extensions.rs b/crates/ra_syntax/src/ast/extensions.rs
index d3a375f87..5f7e9f5b1 100644
--- a/crates/ra_syntax/src/ast/extensions.rs
+++ b/crates/ra_syntax/src/ast/extensions.rs
@@ -373,6 +373,15 @@ impl ast::LifetimeParam {
     }
 }
 
+impl ast::TypeParam {
+    pub fn colon_token(&self) -> Option<SyntaxToken> {
+        self.syntax()
+            .children_with_tokens()
+            .filter_map(|it| it.into_token())
+            .find(|it| it.kind() == T![:])
+    }
+}
+
 impl ast::WherePred {
     pub fn lifetime_token(&self) -> Option<SyntaxToken> {
         self.syntax()