aboutsummaryrefslogtreecommitdiff
path: root/crates/hir_expand/src/ast_id_map.rs
diff options
context:
space:
mode:
Diffstat (limited to 'crates/hir_expand/src/ast_id_map.rs')
-rw-r--r--crates/hir_expand/src/ast_id_map.rs119
1 files changed, 119 insertions, 0 deletions
diff --git a/crates/hir_expand/src/ast_id_map.rs b/crates/hir_expand/src/ast_id_map.rs
new file mode 100644
index 000000000..f63629b30
--- /dev/null
+++ b/crates/hir_expand/src/ast_id_map.rs
@@ -0,0 +1,119 @@
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
8use std::{
9 any::type_name,
10 fmt,
11 hash::{Hash, Hasher},
12 marker::PhantomData,
13};
14
15use arena::{Arena, Idx};
16use syntax::{ast, AstNode, AstPtr, SyntaxNode, SyntaxNodePtr};
17
18/// `AstId` points to an AST node in a specific file.
19pub struct FileAstId<N: AstNode> {
20 raw: ErasedFileAstId,
21 _ty: PhantomData<fn() -> N>,
22}
23
24impl<N: AstNode> Clone for FileAstId<N> {
25 fn clone(&self) -> FileAstId<N> {
26 *self
27 }
28}
29impl<N: AstNode> Copy for FileAstId<N> {}
30
31impl<N: AstNode> PartialEq for FileAstId<N> {
32 fn eq(&self, other: &Self) -> bool {
33 self.raw == other.raw
34 }
35}
36impl<N: AstNode> Eq for FileAstId<N> {}
37impl<N: AstNode> Hash for FileAstId<N> {
38 fn hash<H: Hasher>(&self, hasher: &mut H) {
39 self.raw.hash(hasher);
40 }
41}
42
43impl<N: AstNode> fmt::Debug for FileAstId<N> {
44 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
45 write!(f, "FileAstId::<{}>({})", type_name::<N>(), self.raw.into_raw())
46 }
47}
48
49impl<N: AstNode> FileAstId<N> {
50 // Can't make this a From implementation because of coherence
51 pub fn upcast<M: AstNode>(self) -> FileAstId<M>
52 where
53 N: Into<M>,
54 {
55 FileAstId { raw: self.raw, _ty: PhantomData }
56 }
57}
58
59type ErasedFileAstId = Idx<SyntaxNodePtr>;
60
61/// Maps items' `SyntaxNode`s to `ErasedFileAstId`s and back.
62#[derive(Debug, PartialEq, Eq, Default)]
63pub struct AstIdMap {
64 arena: Arena<SyntaxNodePtr>,
65}
66
67impl AstIdMap {
68 pub(crate) fn from_source(node: &SyntaxNode) -> AstIdMap {
69 assert!(node.parent().is_none());
70 let mut res = AstIdMap { arena: Arena::default() };
71 // By walking the tree in breadth-first order we make sure that parents
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
74 // trait does not change ids of top-level items, which helps caching.
75 bfs(node, |it| {
76 if let Some(module_item) = ast::Item::cast(it) {
77 res.alloc(module_item.syntax());
78 }
79 });
80 res
81 }
82
83 pub fn ast_id<N: AstNode>(&self, item: &N) -> FileAstId<N> {
84 let raw = self.erased_ast_id(item.syntax());
85 FileAstId { raw, _ty: PhantomData }
86 }
87 fn erased_ast_id(&self, item: &SyntaxNode) -> ErasedFileAstId {
88 let ptr = SyntaxNodePtr::new(item);
89 match self.arena.iter().find(|(_id, i)| **i == ptr) {
90 Some((it, _)) => it,
91 None => panic!(
92 "Can't find {:?} in AstIdMap:\n{:?}",
93 item,
94 self.arena.iter().map(|(_id, i)| i).collect::<Vec<_>>(),
95 ),
96 }
97 }
98
99 pub fn get<N: AstNode>(&self, id: FileAstId<N>) -> AstPtr<N> {
100 self.arena[id.raw].clone().cast::<N>().unwrap()
101 }
102
103 fn alloc(&mut self, item: &SyntaxNode) -> ErasedFileAstId {
104 self.arena.alloc(SyntaxNodePtr::new(item))
105 }
106}
107
108/// Walks the subtree in bfs order, calling `f` for each node.
109fn bfs(node: &SyntaxNode, mut f: impl FnMut(SyntaxNode)) {
110 let mut curr_layer = vec![node.clone()];
111 let mut next_layer = vec![];
112 while !curr_layer.is_empty() {
113 curr_layer.drain(..).for_each(|node| {
114 next_layer.extend(node.children());
115 f(node);
116 });
117 std::mem::swap(&mut curr_layer, &mut next_layer);
118 }
119}