diff options
Diffstat (limited to 'crates/hir_expand')
-rw-r--r-- | crates/hir_expand/src/ast_id_map.rs | 30 |
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 |
109 | fn 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. | ||
117 | fn 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 | } |