diff options
Diffstat (limited to 'crates/ra_hir_expand/src/ast_id_map.rs')
-rw-r--r-- | crates/ra_hir_expand/src/ast_id_map.rs | 106 |
1 files changed, 106 insertions, 0 deletions
diff --git a/crates/ra_hir_expand/src/ast_id_map.rs b/crates/ra_hir_expand/src/ast_id_map.rs new file mode 100644 index 000000000..cb464c3ff --- /dev/null +++ b/crates/ra_hir_expand/src/ast_id_map.rs | |||
@@ -0,0 +1,106 @@ | |||
1 | //! `AstIdMap` allows to create stable IDs for "large" syntax nodes like items | ||
2 | //! and macro calls. | ||
3 | //! | ||
4 | //! Specifically, it enumerates all items in a file and uses position of a an | ||
5 | //! item as an ID. That way, id's don't change unless the set of items itself | ||
6 | //! changes. | ||
7 | |||
8 | use std::{ | ||
9 | hash::{Hash, Hasher}, | ||
10 | marker::PhantomData, | ||
11 | }; | ||
12 | |||
13 | use ra_arena::{impl_arena_id, Arena, RawId}; | ||
14 | use ra_syntax::{ast, AstNode, AstPtr, SyntaxNode, SyntaxNodePtr}; | ||
15 | |||
16 | /// `AstId` points to an AST node in a specific file. | ||
17 | #[derive(Debug)] | ||
18 | pub struct FileAstId<N: AstNode> { | ||
19 | raw: ErasedFileAstId, | ||
20 | _ty: PhantomData<fn() -> N>, | ||
21 | } | ||
22 | |||
23 | impl<N: AstNode> Clone for FileAstId<N> { | ||
24 | fn clone(&self) -> FileAstId<N> { | ||
25 | *self | ||
26 | } | ||
27 | } | ||
28 | impl<N: AstNode> Copy for FileAstId<N> {} | ||
29 | |||
30 | impl<N: AstNode> PartialEq for FileAstId<N> { | ||
31 | fn eq(&self, other: &Self) -> bool { | ||
32 | self.raw == other.raw | ||
33 | } | ||
34 | } | ||
35 | impl<N: AstNode> Eq for FileAstId<N> {} | ||
36 | impl<N: AstNode> Hash for FileAstId<N> { | ||
37 | fn hash<H: Hasher>(&self, hasher: &mut H) { | ||
38 | self.raw.hash(hasher); | ||
39 | } | ||
40 | } | ||
41 | |||
42 | #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)] | ||
43 | struct ErasedFileAstId(RawId); | ||
44 | impl_arena_id!(ErasedFileAstId); | ||
45 | |||
46 | /// Maps items' `SyntaxNode`s to `ErasedFileAstId`s and back. | ||
47 | #[derive(Debug, PartialEq, Eq, Default)] | ||
48 | pub struct AstIdMap { | ||
49 | arena: Arena<ErasedFileAstId, SyntaxNodePtr>, | ||
50 | } | ||
51 | |||
52 | impl AstIdMap { | ||
53 | pub(crate) fn from_source(node: &SyntaxNode) -> AstIdMap { | ||
54 | assert!(node.parent().is_none()); | ||
55 | let mut res = AstIdMap { arena: Arena::default() }; | ||
56 | // By walking the tree in bread-first order we make sure that parents | ||
57 | // get lower ids then children. That is, adding a new child does not | ||
58 | // change parent's id. This means that, say, adding a new function to a | ||
59 | // trait does not change ids of top-level items, which helps caching. | ||
60 | bfs(node, |it| { | ||
61 | if let Some(module_item) = ast::ModuleItem::cast(it.clone()) { | ||
62 | res.alloc(module_item.syntax()); | ||
63 | } else if let Some(macro_call) = ast::MacroCall::cast(it) { | ||
64 | res.alloc(macro_call.syntax()); | ||
65 | } | ||
66 | }); | ||
67 | res | ||
68 | } | ||
69 | |||
70 | pub fn ast_id<N: AstNode>(&self, item: &N) -> FileAstId<N> { | ||
71 | let raw = self.erased_ast_id(item.syntax()); | ||
72 | FileAstId { raw, _ty: PhantomData } | ||
73 | } | ||
74 | fn erased_ast_id(&self, item: &SyntaxNode) -> ErasedFileAstId { | ||
75 | let ptr = SyntaxNodePtr::new(item); | ||
76 | match self.arena.iter().find(|(_id, i)| **i == ptr) { | ||
77 | Some((it, _)) => it, | ||
78 | None => panic!( | ||
79 | "Can't find {:?} in AstIdMap:\n{:?}", | ||
80 | item, | ||
81 | self.arena.iter().map(|(_id, i)| i).collect::<Vec<_>>(), | ||
82 | ), | ||
83 | } | ||
84 | } | ||
85 | |||
86 | pub(crate) fn get<N: AstNode>(&self, id: FileAstId<N>) -> AstPtr<N> { | ||
87 | self.arena[id.raw].cast::<N>().unwrap() | ||
88 | } | ||
89 | |||
90 | fn alloc(&mut self, item: &SyntaxNode) -> ErasedFileAstId { | ||
91 | self.arena.alloc(SyntaxNodePtr::new(item)) | ||
92 | } | ||
93 | } | ||
94 | |||
95 | /// Walks the subtree in bfs order, calling `f` for each node. | ||
96 | fn bfs(node: &SyntaxNode, mut f: impl FnMut(SyntaxNode)) { | ||
97 | let mut curr_layer = vec![node.clone()]; | ||
98 | let mut next_layer = vec![]; | ||
99 | while !curr_layer.is_empty() { | ||
100 | curr_layer.drain(..).for_each(|node| { | ||
101 | next_layer.extend(node.children()); | ||
102 | f(node); | ||
103 | }); | ||
104 | std::mem::swap(&mut curr_layer, &mut next_layer); | ||
105 | } | ||
106 | } | ||