From d86863aeb404b042a3ba1a60d5d961f392b8cb64 Mon Sep 17 00:00:00 2001 From: Lukas Wirth Date: Wed, 21 Oct 2020 14:17:00 +0200 Subject: Rewrite algo::diff to support insertion and deletion --- Cargo.lock | 1 + crates/ide/Cargo.toml | 2 +- crates/ide/src/diagnostics.rs | 2 +- crates/syntax/Cargo.toml | 1 + crates/syntax/src/algo.rs | 87 +++++++++++++++++++++++++++++++------------ 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 { After(T), } +type FxIndexMap = IndexMap>; + pub struct TreeDiff { replacements: FxHashMap, + deletions: Vec, + // the vec as well as the indexmap are both here to preserve order + insertions: FxIndexMap>, } 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, - 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); } } -- cgit v1.2.3