aboutsummaryrefslogtreecommitdiff
path: root/crates
diff options
context:
space:
mode:
authorAleksey Kladov <[email protected]>2021-01-16 19:38:22 +0000
committerAleksey Kladov <[email protected]>2021-01-16 20:07:28 +0000
commitb38414c7f4e2e62baa8f09e6ce162ac39391bb8c (patch)
tree612d3deafdcd6ae6801f65b1e7eab9fde1d24276 /crates
parent842ed790eaac94a573492087581a31e5063693c3 (diff)
When building an item-tree, keep fewer nodes in memory
Diffstat (limited to 'crates')
-rw-r--r--crates/hir_expand/src/ast_id_map.rs30
-rw-r--r--crates/syntax/Cargo.toml2
2 files changed, 25 insertions, 7 deletions
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 {
72 // get lower ids then children. That is, adding a new child does not 72 // get lower ids then children. That is, adding a new child does not
73 // change parent's id. This means that, say, adding a new function to a 73 // change parent's id. This means that, say, adding a new function to a
74 // trait does not change ids of top-level items, which helps caching. 74 // trait does not change ids of top-level items, which helps caching.
75 bfs(node, |it| { 75 bdfs(node, |it| match ast::Item::cast(it) {
76 if let Some(module_item) = ast::Item::cast(it) { 76 Some(module_item) => {
77 res.alloc(module_item.syntax()); 77 res.alloc(module_item.syntax());
78 true
78 } 79 }
80 None => false,
79 }); 81 });
80 res 82 res
81 } 83 }
@@ -105,14 +107,30 @@ impl AstIdMap {
105 } 107 }
106} 108}
107 109
108/// Walks the subtree in bfs order, calling `f` for each node. 110/// Walks the subtree in bdfs order, calling `f` for each node. What is bdfs
109fn bfs(node: &SyntaxNode, mut f: impl FnMut(SyntaxNode)) { 111/// order? It is a mix of breadth-first and depth first orders. Nodes for which
112/// `f` returns true are visited breadth-first, all the other nodes are explored
113/// depth-first.
114///
115/// In other words, the size of the bfs queue is bound by the number of "true"
116/// nodes.
117fn bdfs(node: &SyntaxNode, mut f: impl FnMut(SyntaxNode) -> bool) {
110 let mut curr_layer = vec![node.clone()]; 118 let mut curr_layer = vec![node.clone()];
111 let mut next_layer = vec![]; 119 let mut next_layer = vec![];
112 while !curr_layer.is_empty() { 120 while !curr_layer.is_empty() {
113 curr_layer.drain(..).for_each(|node| { 121 curr_layer.drain(..).for_each(|node| {
114 next_layer.extend(node.children()); 122 let mut preorder = node.preorder();
115 f(node); 123 while let Some(event) = preorder.next() {
124 match event {
125 syntax::WalkEvent::Enter(node) => {
126 if f(node.clone()) {
127 next_layer.extend(node.children());
128 preorder.skip_subtree();
129 }
130 }
131 syntax::WalkEvent::Leave(_) => {}
132 }
133 }
116 }); 134 });
117 std::mem::swap(&mut curr_layer, &mut next_layer); 135 std::mem::swap(&mut curr_layer, &mut next_layer);
118 } 136 }
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
12 12
13[dependencies] 13[dependencies]
14itertools = "0.10.0" 14itertools = "0.10.0"
15rowan = "0.10.1" 15rowan = "0.10.3"
16rustc_lexer = { version = "697.0.0", package = "rustc-ap-rustc_lexer" } 16rustc_lexer = { version = "697.0.0", package = "rustc-ap-rustc_lexer" }
17rustc-hash = "1.1.0" 17rustc-hash = "1.1.0"
18arrayvec = "0.5.1" 18arrayvec = "0.5.1"