diff options
author | bors[bot] <26634292+bors[bot]@users.noreply.github.com> | 2020-04-09 12:58:15 +0100 |
---|---|---|
committer | GitHub <[email protected]> | 2020-04-09 12:58:15 +0100 |
commit | d416d892fc149c226599d011063e6aaea61a5cc5 (patch) | |
tree | 49448cb990672c8385dc7b9688b7a7741049a55d /crates/ra_syntax/src/algo.rs | |
parent | 1647d5ac60eb5d5c80e7fbadcea55597ec7efaa0 (diff) | |
parent | 738fc79c92a0c0dd1147f843a57ed36458644ad4 (diff) |
Merge #3913
3913: Remove allocations from LCA r=matklad a=matklad
I haven't actually profiled this, but not allocating a hash map (or
anything, really) seems like a good idea
bors r+
🤖
Co-authored-by: Aleksey Kladov <[email protected]>
Diffstat (limited to 'crates/ra_syntax/src/algo.rs')
-rw-r--r-- | crates/ra_syntax/src/algo.rs | 16 |
1 files changed, 13 insertions, 3 deletions
diff --git a/crates/ra_syntax/src/algo.rs b/crates/ra_syntax/src/algo.rs index 8d1098036..7f87f4212 100644 --- a/crates/ra_syntax/src/algo.rs +++ b/crates/ra_syntax/src/algo.rs | |||
@@ -7,7 +7,7 @@ use std::{ | |||
7 | 7 | ||
8 | use itertools::Itertools; | 8 | use itertools::Itertools; |
9 | use ra_text_edit::TextEditBuilder; | 9 | use ra_text_edit::TextEditBuilder; |
10 | use rustc_hash::{FxHashMap, FxHashSet}; | 10 | use rustc_hash::FxHashMap; |
11 | 11 | ||
12 | use crate::{ | 12 | use crate::{ |
13 | AstNode, Direction, NodeOrToken, SyntaxElement, SyntaxNode, SyntaxNodePtr, SyntaxToken, | 13 | AstNode, Direction, NodeOrToken, SyntaxElement, SyntaxNode, SyntaxNodePtr, SyntaxToken, |
@@ -72,8 +72,18 @@ pub fn find_covering_element(root: &SyntaxNode, range: TextRange) -> SyntaxEleme | |||
72 | } | 72 | } |
73 | 73 | ||
74 | pub fn least_common_ancestor(u: &SyntaxNode, v: &SyntaxNode) -> Option<SyntaxNode> { | 74 | pub fn least_common_ancestor(u: &SyntaxNode, v: &SyntaxNode) -> Option<SyntaxNode> { |
75 | let u_ancestors = u.ancestors().collect::<FxHashSet<SyntaxNode>>(); | 75 | if u == v { |
76 | v.ancestors().find(|it| u_ancestors.contains(it)) | 76 | return Some(u.clone()); |
77 | } | ||
78 | |||
79 | let u_depth = u.ancestors().count(); | ||
80 | let v_depth = v.ancestors().count(); | ||
81 | let keep = u_depth.min(v_depth); | ||
82 | |||
83 | let u_candidates = u.ancestors().skip(u_depth - keep); | ||
84 | let v_canidates = v.ancestors().skip(v_depth - keep); | ||
85 | let (res, _) = u_candidates.zip(v_canidates).find(|(x, y)| x == y)?; | ||
86 | Some(res) | ||
77 | } | 87 | } |
78 | 88 | ||
79 | pub fn neighbor<T: AstNode>(me: &T, direction: Direction) -> Option<T> { | 89 | pub fn neighbor<T: AstNode>(me: &T, direction: Direction) -> Option<T> { |