aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorbors[bot] <26634292+bors[bot]@users.noreply.github.com>2019-09-26 13:58:54 +0100
committerGitHub <[email protected]>2019-09-26 13:58:54 +0100
commit53a30d9e69ee5149e4fdb1c6fe4081281e879d0e (patch)
treeacb80dc5a8a91853f49ddf632a461a66df180ad4
parent3882231f3231db03144107f72c6052f773fe2375 (diff)
parent1a4b42400544a652a053a34263967689d47f554b (diff)
Merge #1919
1919: move diff to ra_syntax r=matklad a=matklad Co-authored-by: Aleksey Kladov <[email protected]>
-rw-r--r--crates/ra_assists/src/ast_editor.rs27
-rw-r--r--crates/ra_syntax/src/algo.rs42
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;
7use ra_syntax::{ 7use ra_syntax::{
8 algo, 8 algo,
9 ast::{self, TypeBoundsOwner}, 9 ast::{self, TypeBoundsOwner},
10 AstNode, Direction, InsertPosition, NodeOrToken, SyntaxElement, 10 AstNode, Direction, InsertPosition, SyntaxElement,
11 SyntaxKind::*, 11 SyntaxKind::*,
12 T, 12 T,
13}; 13};
@@ -27,29 +27,8 @@ impl<N: AstNode> AstEditor<N> {
27 } 27 }
28 28
29 pub fn into_text_edit(self, builder: &mut TextEditBuilder) { 29 pub fn into_text_edit(self, builder: &mut TextEditBuilder) {
30 // FIXME: this is both horrible inefficient and gives larger than 30 for (from, to) in algo::diff(&self.original_ast.syntax(), self.ast().syntax()) {
31 // necessary diff. I bet there's a cool algorithm to diff trees properly. 31 builder.replace(from.text_range(), to.to_string())
32 go(builder, self.original_ast.syntax().clone().into(), self.ast().syntax().clone().into());
33
34 fn go(buf: &mut TextEditBuilder, lhs: SyntaxElement, rhs: SyntaxElement) {
35 if lhs.kind() == rhs.kind() && lhs.text_range().len() == rhs.text_range().len() {
36 if match (&lhs, &rhs) {
37 (NodeOrToken::Node(lhs), NodeOrToken::Node(rhs)) => lhs.text() == rhs.text(),
38 (NodeOrToken::Token(lhs), NodeOrToken::Token(rhs)) => lhs.text() == rhs.text(),
39 _ => false,
40 } {
41 return;
42 }
43 }
44 if let (Some(lhs), Some(rhs)) = (lhs.as_node(), rhs.as_node()) {
45 if lhs.children_with_tokens().count() == rhs.children_with_tokens().count() {
46 for (lhs, rhs) in lhs.children_with_tokens().zip(rhs.children_with_tokens()) {
47 go(buf, lhs, rhs)
48 }
49 return;
50 }
51 }
52 buf.replace(lhs.text_range(), rhs.to_string())
53 } 32 }
54 } 33 }
55 34
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> {
63 After(T), 63 After(T),
64} 64}
65 65
66/// Finds minimal the diff, which, applied to `from`, will result in `to`.
67///
68/// Specifically, returns a map whose keys are descendants of `from` and values
69/// are descendants of `to`, such that `replace_descendants(from, map) == to`.
70///
71/// A trivial solution is a singletom map `{ from: to }`, but this function
72/// tries to find a more fine-grained diff.
73pub fn diff(from: &SyntaxNode, to: &SyntaxNode) -> FxHashMap<SyntaxElement, SyntaxElement> {
74 let mut buf = FxHashMap::default();
75 // FIXME: this is both horrible inefficient and gives larger than
76 // necessary diff. I bet there's a cool algorithm to diff trees properly.
77 go(&mut buf, from.clone().into(), to.clone().into());
78 return buf;
79
80 fn go(
81 buf: &mut FxHashMap<SyntaxElement, SyntaxElement>,
82 lhs: SyntaxElement,
83 rhs: SyntaxElement,
84 ) {
85 if lhs.kind() == rhs.kind() && lhs.text_range().len() == rhs.text_range().len() {
86 if match (&lhs, &rhs) {
87 (NodeOrToken::Node(lhs), NodeOrToken::Node(rhs)) => {
88 lhs.green() == rhs.green() || lhs.text() == rhs.text()
89 }
90 (NodeOrToken::Token(lhs), NodeOrToken::Token(rhs)) => lhs.text() == rhs.text(),
91 _ => false,
92 } {
93 return;
94 }
95 }
96 if let (Some(lhs), Some(rhs)) = (lhs.as_node(), rhs.as_node()) {
97 if lhs.children_with_tokens().count() == rhs.children_with_tokens().count() {
98 for (lhs, rhs) in lhs.children_with_tokens().zip(rhs.children_with_tokens()) {
99 go(buf, lhs, rhs)
100 }
101 return;
102 }
103 }
104 buf.insert(lhs, rhs);
105 }
106}
107
66/// Adds specified children (tokens or nodes) to the current node at the 108/// Adds specified children (tokens or nodes) to the current node at the
67/// specific position. 109/// specific position.
68/// 110///