2 files changed, 45 insertions, 24 deletions

diff --git a/crates/ra_assists/src/ast_editor.rs b/crates/ra_assists/src/ast_editor.rs
index 2936c094b..2a685f26e 100644
--- a/crates/ra_assists/src/ast_editor.rs
+++ b/crates/ra_assists/src/ast_editor.rs
@@ -7,7 +7,7 @@ use ra_fmt::leading_indent;
 use ra_syntax::{
     algo,
     ast::{self, TypeBoundsOwner},
-    AstNode, Direction, InsertPosition, NodeOrToken, SyntaxElement,
+    AstNode, Direction, InsertPosition, SyntaxElement,
     SyntaxKind::*,
     T,
 };
@@ -27,29 +27,8 @@ impl<N: AstNode> AstEditor<N> {
     }
 
     pub fn into_text_edit(self, builder: &mut TextEditBuilder) {
-        // 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())
+        for (from, to) in algo::diff(&self.original_ast.syntax(), self.ast().syntax()) {
+            builder.replace(from.text_range(), to.to_string())
         }
     }
 
diff --git a/crates/ra_syntax/src/algo.rs b/crates/ra_syntax/src/algo.rs
index f0ed96a17..46680a08f 100644
--- a/crates/ra_syntax/src/algo.rs
+++ b/crates/ra_syntax/src/algo.rs
@@ -63,6 +63,48 @@ pub enum InsertPosition<T> {
     After(T),
 }
 
+/// Finds minimal the diff, which, applied to `from`, will result in `to`.
+///
+/// Specifically, returns a map whose keys are descendants of `from` and values
+/// are descendants of `to`, such that  `replace_descendants(from, map) == to`.
+///
+/// A trivial solution is a singletom map `{ from: to }`, but this function
+/// tries to find a more fine-grained diff.
+pub fn diff(from: &SyntaxNode, to: &SyntaxNode) -> FxHashMap<SyntaxElement, SyntaxElement> {
+    let mut buf = FxHashMap::default();
+    // FIXME: this is both horrible inefficient and gives larger than
+    // necessary diff. I bet there's a cool algorithm to diff trees properly.
+    go(&mut buf, from.clone().into(), to.clone().into());
+    return buf;
+
+    fn go(
+        buf: &mut FxHashMap<SyntaxElement, SyntaxElement>,
+        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.green() == rhs.green() || 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.insert(lhs, rhs);
+    }
+}
+
 /// Adds specified children (tokens or nodes) to the current node at the
 /// specific position.
 ///