diff options
Diffstat (limited to 'crates/ra_syntax')
-rw-r--r-- | crates/ra_syntax/src/algo.rs | 42 |
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. | ||
73 | pub 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 | /// |