aboutsummaryrefslogtreecommitdiff
path: root/crates/hir_expand
diff options
context:
space:
mode:
Diffstat (limited to 'crates/hir_expand')
-rw-r--r--crates/hir_expand/src/ast_id_map.rs30
1 files changed, 24 insertions, 6 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 }