aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_syntax
diff options
context:
space:
mode:
Diffstat (limited to 'crates/ra_syntax')
-rw-r--r--crates/ra_syntax/src/algo.rs42
1 files changed, 42 insertions, 0 deletions
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///