Rewrite algo::diff to support insertion and deletion

5 files changed, 68 insertions, 25 deletions

diff --git a/Cargo.lock b/Cargo.lock
index e819297bd..59f743efa 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -1607,6 +1607,7 @@ version = "0.0.0"
 dependencies = [
  "arrayvec",
  "expect-test",
+ "indexmap",
  "itertools",
  "once_cell",
  "parser",
diff --git a/crates/ide/Cargo.toml b/crates/ide/Cargo.toml
index 63299dc31..76b52fa04 100644
--- a/crates/ide/Cargo.toml
+++ b/crates/ide/Cargo.toml
@@ -11,7 +11,7 @@ doctest = false
 
 [dependencies]
 either = "1.5.3"
-indexmap = "1.3.2"
+indexmap = "1.4.0"
 itertools = "0.9.0"
 log = "0.4.8"
 rustc-hash = "1.1.0"
diff --git a/crates/ide/src/diagnostics.rs b/crates/ide/src/diagnostics.rs
index 90574cb35..232074c3d 100644
--- a/crates/ide/src/diagnostics.rs
+++ b/crates/ide/src/diagnostics.rs
@@ -613,7 +613,7 @@ fn main() {
 pub struct Foo { pub a: i32, pub b: i32 }
 "#,
             r#"
-fn {a:42, b: ()} {}
+fn some(, b: ()} {}
 fn items() {}
 fn here() {}
 
diff --git a/crates/syntax/Cargo.toml b/crates/syntax/Cargo.toml
index c343f2f70..8c0b0abbb 100644
--- a/crates/syntax/Cargo.toml
+++ b/crates/syntax/Cargo.toml
@@ -17,6 +17,7 @@ rustc_lexer = { version = "683.0.0", package = "rustc-ap-rustc_lexer" }
 rustc-hash = "1.1.0"
 arrayvec = "0.5.1"
 once_cell = "1.3.1"
+indexmap = "1.4.0"
 # This crate transitively depends on `smol_str` via `rowan`.
 # ideally, `serde` should be enabled by `rust-analyzer`, but we enable it here
 # to reduce number of compilations
diff --git a/crates/syntax/src/algo.rs b/crates/syntax/src/algo.rs
index ea199f9b8..f53875f28 100644
--- a/crates/syntax/src/algo.rs
+++ b/crates/syntax/src/algo.rs
@@ -2,9 +2,11 @@
 
 use std::{
     fmt,
+    hash::BuildHasherDefault,
     ops::{self, RangeInclusive},
 };
 
+use indexmap::IndexMap;
 use itertools::Itertools;
 use rustc_hash::FxHashMap;
 use text_edit::TextEditBuilder;
@@ -106,42 +108,56 @@ pub enum InsertPosition<T> {
     After(T),
 }
 
+type FxIndexMap<K, V> = IndexMap<K, V, BuildHasherDefault<rustc_hash::FxHasher>>;
+
 pub struct TreeDiff {
     replacements: FxHashMap<SyntaxElement, SyntaxElement>,
+    deletions: Vec<SyntaxElement>,
+    // the vec as well as the indexmap are both here to preserve order
+    insertions: FxIndexMap<SyntaxElement, Vec<SyntaxElement>>,
 }
 
 impl TreeDiff {
     pub fn into_text_edit(&self, builder: &mut TextEditBuilder) {
+        for (anchor, to) in self.insertions.iter() {
+            to.iter().for_each(|to| builder.insert(anchor.text_range().end(), to.to_string()));
+        }
         for (from, to) in self.replacements.iter() {
             builder.replace(from.text_range(), to.to_string())
         }
+        for text_range in self.deletions.iter().map(SyntaxElement::text_range) {
+            builder.delete(text_range);
+        }
     }
 
     pub fn is_empty(&self) -> bool {
-        self.replacements.is_empty()
+        self.replacements.is_empty() && self.deletions.is_empty() && self.insertions.is_empty()
     }
 }
 
 /// 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`.
+/// Specifically, returns a structure that consists of a replacements, insertions and deletions
+/// such that applying this map on `from` will result in `to`.
 ///
-/// A trivial solution is a singleton map `{ from: to }`, but this function
-/// tries to find a more fine-grained diff.
+/// This function tries to find a fine-grained diff.
 pub fn diff(from: &SyntaxNode, to: &SyntaxNode) -> TreeDiff {
-    let mut buf = FxHashMap::default();
+    let mut diff = TreeDiff {
+        replacements: FxHashMap::default(),
+        insertions: FxIndexMap::default(),
+        deletions: Vec::new(),
+    };
+    let (from, to) = (from.clone().into(), to.clone().into());
+
     // 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 TreeDiff { replacements: buf };
+    if !syntax_element_eq(&from, &to) {
+        go(&mut diff, from, to);
+    }
+    return diff;
 
-    fn go(
-        buf: &mut FxHashMap<SyntaxElement, SyntaxElement>,
-        lhs: SyntaxElement,
-        rhs: SyntaxElement,
-    ) {
-        if lhs.kind() == rhs.kind()
+    fn syntax_element_eq(lhs: &SyntaxElement, rhs: &SyntaxElement) -> bool {
+        lhs.kind() == rhs.kind()
             && lhs.text_range().len() == rhs.text_range().len()
             && match (&lhs, &rhs) {
                 (NodeOrToken::Node(lhs), NodeOrToken::Node(rhs)) => {
@@ -150,18 +166,43 @@ pub fn diff(from: &SyntaxNode, to: &SyntaxNode) -> TreeDiff {
                 (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)
-                }
+    }
+
+    fn go(diff: &mut TreeDiff, lhs: SyntaxElement, rhs: SyntaxElement) {
+        let (lhs, rhs) = match lhs.as_node().zip(rhs.as_node()) {
+            Some((lhs, rhs)) => (lhs, rhs),
+            _ => {
+                diff.replacements.insert(lhs, rhs);
                 return;
             }
+        };
+
+        let mut rhs_children = rhs.children_with_tokens();
+        let mut lhs_children = lhs.children_with_tokens();
+        let mut last_lhs = None;
+        loop {
+            let lhs_child = lhs_children.next();
+            match (lhs_child.clone(), rhs_children.next()) {
+                (None, None) => break,
+                (None, Some(element)) => match last_lhs.clone() {
+                    Some(prev) => {
+                        diff.insertions.entry(prev).or_insert_with(Vec::new).push(element);
+                    }
+                    // first iteration, this means we got no anchor element to insert after
+                    // therefor replace the parent node instead
+                    None => {
+                        diff.replacements.insert(lhs.clone().into(), rhs.clone().into());
+                        break;
+                    }
+                },
+                (Some(element), None) => {
+                    diff.deletions.push(element);
+                }
+                (Some(ref lhs_ele), Some(ref rhs_ele)) if syntax_element_eq(lhs_ele, rhs_ele) => {}
+                (Some(lhs_ele), Some(rhs_ele)) => go(diff, lhs_ele, rhs_ele),
+            }
+            last_lhs = lhs_child.or(last_lhs);
         }
-        buf.insert(lhs, rhs);
     }
 }