1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
|
//! `AstIdMap` allows to create stable IDs for "large" syntax nodes like items
//! and macro calls.
//!
//! Specifically, it enumerates all items in a file and uses position of a an
//! item as an ID. That way, id's don't change unless the set of items itself
//! changes.
use std::{
any::type_name,
fmt,
hash::{Hash, Hasher},
marker::PhantomData,
};
use la_arena::{Arena, Idx};
use syntax::{ast, match_ast, AstNode, AstPtr, SyntaxNode, SyntaxNodePtr};
/// `AstId` points to an AST node in a specific file.
pub struct FileAstId<N: AstNode> {
raw: ErasedFileAstId,
_ty: PhantomData<fn() -> N>,
}
impl<N: AstNode> Clone for FileAstId<N> {
fn clone(&self) -> FileAstId<N> {
*self
}
}
impl<N: AstNode> Copy for FileAstId<N> {}
impl<N: AstNode> PartialEq for FileAstId<N> {
fn eq(&self, other: &Self) -> bool {
self.raw == other.raw
}
}
impl<N: AstNode> Eq for FileAstId<N> {}
impl<N: AstNode> Hash for FileAstId<N> {
fn hash<H: Hasher>(&self, hasher: &mut H) {
self.raw.hash(hasher);
}
}
impl<N: AstNode> fmt::Debug for FileAstId<N> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "FileAstId::<{}>({})", type_name::<N>(), self.raw.into_raw())
}
}
impl<N: AstNode> FileAstId<N> {
// Can't make this a From implementation because of coherence
pub fn upcast<M: AstNode>(self) -> FileAstId<M>
where
N: Into<M>,
{
FileAstId { raw: self.raw, _ty: PhantomData }
}
}
type ErasedFileAstId = Idx<SyntaxNodePtr>;
/// Maps items' `SyntaxNode`s to `ErasedFileAstId`s and back.
#[derive(Debug, PartialEq, Eq, Default)]
pub struct AstIdMap {
arena: Arena<SyntaxNodePtr>,
}
impl AstIdMap {
pub(crate) fn from_source(node: &SyntaxNode) -> AstIdMap {
assert!(node.parent().is_none());
let mut res = AstIdMap { arena: Arena::default() };
// By walking the tree in breadth-first order we make sure that parents
// 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.
bdfs(node, |it| {
match_ast! {
match it {
ast::Item(module_item) => {
res.alloc(module_item.syntax());
true
},
ast::BlockExpr(block) => {
res.alloc(block.syntax());
true
},
_ => false,
}
}
});
res
}
pub fn ast_id<N: AstNode>(&self, item: &N) -> FileAstId<N> {
let raw = self.erased_ast_id(item.syntax());
FileAstId { raw, _ty: PhantomData }
}
fn erased_ast_id(&self, item: &SyntaxNode) -> ErasedFileAstId {
let ptr = SyntaxNodePtr::new(item);
match self.arena.iter().find(|(_id, i)| **i == ptr) {
Some((it, _)) => it,
None => panic!(
"Can't find {:?} in AstIdMap:\n{:?}",
item,
self.arena.iter().map(|(_id, i)| i).collect::<Vec<_>>(),
),
}
}
pub fn get<N: AstNode>(&self, id: FileAstId<N>) -> AstPtr<N> {
self.arena[id.raw].clone().cast::<N>().unwrap()
}
fn alloc(&mut self, item: &SyntaxNode) -> ErasedFileAstId {
self.arena.alloc(SyntaxNodePtr::new(item))
}
}
/// 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| {
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);
}
}
|
