aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAleksey Kladov <[email protected]>2020-04-09 12:56:45 +0100
committerAleksey Kladov <[email protected]>2020-04-09 12:56:45 +0100
commit738fc79c92a0c0dd1147f843a57ed36458644ad4 (patch)
tree49448cb990672c8385dc7b9688b7a7741049a55d
parent1647d5ac60eb5d5c80e7fbadcea55597ec7efaa0 (diff)
Remove allocations from LCA
I haven't actually profiled this, but not allocating a hash map (or anything, really) seems like a good idea
-rw-r--r--crates/ra_syntax/src/algo.rs16
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
8use itertools::Itertools; 8use itertools::Itertools;
9use ra_text_edit::TextEditBuilder; 9use ra_text_edit::TextEditBuilder;
10use rustc_hash::{FxHashMap, FxHashSet}; 10use rustc_hash::FxHashMap;
11 11
12use crate::{ 12use 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
74pub fn least_common_ancestor(u: &SyntaxNode, v: &SyntaxNode) -> Option<SyntaxNode> { 74pub 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
79pub fn neighbor<T: AstNode>(me: &T, direction: Direction) -> Option<T> { 89pub fn neighbor<T: AstNode>(me: &T, direction: Direction) -> Option<T> {