From 738fc79c92a0c0dd1147f843a57ed36458644ad4 Mon Sep 17 00:00:00 2001
From: Aleksey Kladov <aleksey.kladov@gmail.com>
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/src/algo.rs')

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<SyntaxNode> {
-    let u_ancestors = u.ancestors().collect::<FxHashSet<SyntaxNode>>();
-    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<T: AstNode>(me: &T, direction: Direction) -> Option<T> {
-- 
cgit v1.2.3