From b38414c7f4e2e62baa8f09e6ce162ac39391bb8c Mon Sep 17 00:00:00 2001
From: Aleksey Kladov <aleksey.kladov@gmail.com>
Date: Sat, 16 Jan 2021 22:38:22 +0300
Subject: When building an item-tree, keep fewer nodes in memory

---
 Cargo.lock                          |  4 ++--
 crates/hir_expand/src/ast_id_map.rs | 30 ++++++++++++++++++++++++------
 crates/syntax/Cargo.toml            |  2 +-
 3 files changed, 27 insertions(+), 9 deletions(-)

diff --git a/Cargo.lock b/Cargo.lock
index 7ba7aea15..0c6e9ff61 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -1325,9 +1325,9 @@ checksum = "3b181ba2dcf07aaccad5448e8ead58db5b742cf85dfe035e2227f137a539a189"
 
 [[package]]
 name = "rowan"
-version = "0.10.2"
+version = "0.10.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "5093b337dccf58ace6c6d1fe7e28a0b8229c1e72579ae66bae258fbe53df3e0e"
+checksum = "d55d358c5fda3d5c4484f71a4808f5eeb39a0aff93bf3acebc680a6d15376f3c"
 dependencies = [
  "rustc-hash",
  "smol_str",
diff --git a/crates/hir_expand/src/ast_id_map.rs b/crates/hir_expand/src/ast_id_map.rs
index f4f6e11fd..2401b0cc5 100644
--- a/crates/hir_expand/src/ast_id_map.rs
+++ b/crates/hir_expand/src/ast_id_map.rs
@@ -72,10 +72,12 @@ impl AstIdMap {
         // get lower ids then children. That is, adding a new child does not
         // change parent's id. This means that, say, adding a new function to a
         // trait does not change ids of top-level items, which helps caching.
-        bfs(node, |it| {
-            if let Some(module_item) = ast::Item::cast(it) {
+        bdfs(node, |it| match ast::Item::cast(it) {
+            Some(module_item) => {
                 res.alloc(module_item.syntax());
+                true
             }
+            None => false,
         });
         res
     }
@@ -105,14 +107,30 @@ impl AstIdMap {
     }
 }
 
-/// Walks the subtree in bfs order, calling `f` for each node.
-fn bfs(node: &SyntaxNode, mut f: impl FnMut(SyntaxNode)) {
+/// Walks the subtree in bdfs order, calling `f` for each node. What is bdfs
+/// order? It is a mix of breadth-first and depth first orders. Nodes for which
+/// `f` returns true are visited breadth-first, all the other nodes are explored
+/// depth-first.
+///
+/// In other words, the size of the bfs queue is bound by the number of "true"
+/// nodes.
+fn bdfs(node: &SyntaxNode, mut f: impl FnMut(SyntaxNode) -> bool) {
     let mut curr_layer = vec![node.clone()];
     let mut next_layer = vec![];
     while !curr_layer.is_empty() {
         curr_layer.drain(..).for_each(|node| {
-            next_layer.extend(node.children());
-            f(node);
+            let mut preorder = node.preorder();
+            while let Some(event) = preorder.next() {
+                match event {
+                    syntax::WalkEvent::Enter(node) => {
+                        if f(node.clone()) {
+                            next_layer.extend(node.children());
+                            preorder.skip_subtree();
+                        }
+                    }
+                    syntax::WalkEvent::Leave(_) => {}
+                }
+            }
         });
         std::mem::swap(&mut curr_layer, &mut next_layer);
     }
diff --git a/crates/syntax/Cargo.toml b/crates/syntax/Cargo.toml
index ad8b797fe..52394b337 100644
--- a/crates/syntax/Cargo.toml
+++ b/crates/syntax/Cargo.toml
@@ -12,7 +12,7 @@ doctest = false
 
 [dependencies]
 itertools = "0.10.0"
-rowan = "0.10.1"
+rowan = "0.10.3"
 rustc_lexer = { version = "697.0.0", package = "rustc-ap-rustc_lexer" }
 rustc-hash = "1.1.0"
 arrayvec = "0.5.1"
-- 
cgit v1.2.3