From 738fc79c92a0c0dd1147f843a57ed36458644ad4 Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Thu, 9 Apr 2020 13:56:45 +0200 Subject: Remove allocations from LCA I haven't actually profiled this, but not allocating a hash map (or anything, really) seems like a good idea --- crates/ra_syntax/src/algo.rs | 16 +++++++++++++--- 1 file changed, 13 insertions(+), 3 deletions(-) (limited to 'crates/ra_syntax') 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::{ use itertools::Itertools; use ra_text_edit::TextEditBuilder; -use rustc_hash::{FxHashMap, FxHashSet}; +use rustc_hash::FxHashMap; use crate::{ AstNode, Direction, NodeOrToken, SyntaxElement, SyntaxNode, SyntaxNodePtr, SyntaxToken, @@ -72,8 +72,18 @@ pub fn find_covering_element(root: &SyntaxNode, range: TextRange) -> SyntaxEleme } pub fn least_common_ancestor(u: &SyntaxNode, v: &SyntaxNode) -> Option { - let u_ancestors = u.ancestors().collect::>(); - v.ancestors().find(|it| u_ancestors.contains(it)) + if u == v { + return Some(u.clone()); + } + + let u_depth = u.ancestors().count(); + let v_depth = v.ancestors().count(); + let keep = u_depth.min(v_depth); + + let u_candidates = u.ancestors().skip(u_depth - keep); + let v_canidates = v.ancestors().skip(v_depth - keep); + let (res, _) = u_candidates.zip(v_canidates).find(|(x, y)| x == y)?; + Some(res) } pub fn neighbor(me: &T, direction: Direction) -> Option { -- cgit v1.2.3