1//! Working with abstract syntax trees.
2//!
3//! In rowan, syntax trees are transient objects. That means that we create
4//! trees when we need them, and tear them down to save memory. In this
5//! architecture, hanging on to a particular syntax node for a long time is
6//! ill-advisable, as that keeps the whole tree resident.
7//!
8//! Instead, we provide a [`SyntaxNodePtr`] type, which stores information about
9//! the _location_ of a particular syntax node in a tree. It's a small type
10//! which can be cheaply stored, and which can be resolved to a real
11//! [`SyntaxNode`] when necessary.
12//!
13//! We also provide an [`AstNode`] trait for typed AST wrapper APIs over rowan
14//! nodes.
15
16use std::{
17 fmt,
18 hash::{Hash, Hasher},
19 iter::successors,
20 marker::PhantomData,
21};
22
23use crate::{Language, SyntaxNode, SyntaxNodeChildren, TextRange};
24
25/// The main trait to go from untyped [`SyntaxNode`] to a typed AST. The
26/// conversion itself has zero runtime cost: AST and syntax nodes have exactly
27/// the same representation: a pointer to the tree root and a pointer to the
28/// node itself.
29pub trait AstNode {
30 type Language: Language;
31
32 fn can_cast(kind: <Self::Language as Language>::Kind) -> bool
33 where
34 Self: Sized;
35
36 fn cast(node: SyntaxNode<Self::Language>) -> Option<Self>
37 where
38 Self: Sized;
39
40 fn syntax(&self) -> &SyntaxNode<Self::Language>;
41
42 fn clone_for_update(&self) -> Self
43 where
44 Self: Sized,
45 {
46 Self::cast(self.syntax().clone_for_update()).unwrap()
47 }
48
49 fn clone_subtree(&self) -> Self
50 where
51 Self: Sized,
52 {
53 Self::cast(self.syntax().clone_subtree()).unwrap()
54 }
55}
56
57/// A "pointer" to a [`SyntaxNode`], via location in the source code.
58///
59/// ## Note
60/// Since the location is source code dependent, this must not be used
61/// with mutable syntax trees. Any changes made in such trees causes
62/// the pointed node's source location to change, invalidating the pointer.
63#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
64pub struct SyntaxNodePtr<L: Language> {
65 kind: L::Kind,
66 range: TextRange,
67}
68
69impl<L: Language> SyntaxNodePtr<L> {
70 /// Returns a [`SyntaxNodePtr`] for the node.
71 ///
72 /// Panics if the provided node is mutable
73 pub fn new(node: &SyntaxNode<L>) -> Self {
74 assert!(!node.is_mutable(), "tree is mutable");
75 Self { kind: node.kind(), range: node.text_range() }
76 }
77
78 /// Like [`Self::try_to_node`] but panics instead of returning `None` on
79 /// failure.
80 pub fn to_node(&self, root: &SyntaxNode<L>) -> SyntaxNode<L> {
81 self.try_to_node(root).unwrap_or_else(|| panic!("can't resolve {self:?} with {root:?}"))
82 }
83
84 /// "Dereferences" the pointer to get the [`SyntaxNode`] it points to.
85 ///
86 /// Returns `None` if the node is not found, so make sure that the `root`
87 /// syntax tree is equivalent to (i.e. is build from the same text from) the
88 /// tree which was originally used to get this [`SyntaxNodePtr`].
89 ///
90 /// Also returns `None` if `root` is not actually a root (i.e. it has a
91 /// parent).
92 ///
93 /// NOTE: If this function is called on a mutable tree, it will panic
94 ///
95 /// The complexity is linear in the depth of the tree and logarithmic in
96 /// tree width. As most trees are shallow, thinking about this as
97 /// `O(log(N))` in the size of the tree is not too wrong!
98 pub fn try_to_node(&self, root: &SyntaxNode<L>) -> Option<SyntaxNode<L>> {
99 assert!(!root.is_mutable(), "tree is mutable");
100 if root.parent().is_some() {
101 return None;
102 }
103 successors(Some(root.clone()), |node| node.child_or_token_at_range(self.range)?.into_node())
104 .find(|it| it.text_range() == self.range && it.kind() == self.kind)
105 }
106
107 /// Casts this to an [`AstPtr`] to the given node type if possible.
108 pub fn cast<N: AstNode<Language = L>>(self) -> Option<AstPtr<N>> {
109 if !N::can_cast(self.kind) {
110 return None;
111 }
112 Some(AstPtr { raw: self })
113 }
114
115 /// Returns the kind of the syntax node this points to.
116 pub fn kind(&self) -> L::Kind {
117 self.kind
118 }
119
120 /// Returns the range of the syntax node this points to.
121 pub fn text_range(&self) -> TextRange {
122 self.range
123 }
124}
125
126/// Like [`SyntaxNodePtr`], but remembers the type of node.
127///
128/// ## Note
129/// As with [`SyntaxNodePtr`], this must not be used on mutable
130/// syntax trees, since any mutation can cause the pointed node's
131/// source location to change, invalidating the pointer
132pub struct AstPtr<N: AstNode> {
133 raw: SyntaxNodePtr<N::Language>,
134}
135
136impl<N: AstNode> AstPtr<N> {
137 /// Returns an [`AstPtr`] for the node.
138 ///
139 /// Panics if the provided node is mutable
140 pub fn new(node: &N) -> Self {
141 // The above mentioned panic is handled by SyntaxNodePtr
142 Self { raw: SyntaxNodePtr::new(node.syntax()) }
143 }
144
145 /// Like `Self::try_to_node` but panics on failure.
146 pub fn to_node(&self, root: &SyntaxNode<N::Language>) -> N {
147 self.try_to_node(root).unwrap_or_else(|| panic!("can't resolve {self:?} with {root:?}"))
148 }
149
150 /// Given the root node containing the node `n` that `self` is a pointer to,
151 /// returns `n` if possible. Panics if `root` is mutable. See [`SyntaxNodePtr::try_to_node`].
152 pub fn try_to_node(&self, root: &SyntaxNode<N::Language>) -> Option<N> {
153 // The above mentioned panic is handled by SyntaxNodePtr
154 N::cast(self.raw.try_to_node(root)?)
155 }
156
157 /// Returns the underlying [`SyntaxNodePtr`].
158 pub fn syntax_node_ptr(&self) -> SyntaxNodePtr<N::Language> {
159 self.raw.clone()
160 }
161
162 /// Casts this to an [`AstPtr`] to the given node type if possible.
163 pub fn cast<U: AstNode<Language = N::Language>>(self) -> Option<AstPtr<U>> {
164 if !U::can_cast(self.raw.kind) {
165 return None;
166 }
167 Some(AstPtr { raw: self.raw })
168 }
169}
170
171impl<N: AstNode> fmt::Debug for AstPtr<N> {
172 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
173 f.debug_struct("AstPtr").field(name:"raw", &self.raw).finish()
174 }
175}
176
177impl<N: AstNode> Clone for AstPtr<N> {
178 fn clone(&self) -> Self {
179 Self { raw: self.raw.clone() }
180 }
181}
182
183impl<N: AstNode> PartialEq for AstPtr<N> {
184 fn eq(&self, other: &AstPtr<N>) -> bool {
185 self.raw == other.raw
186 }
187}
188
189impl<N: AstNode> Eq for AstPtr<N> {}
190
191impl<N: AstNode> Hash for AstPtr<N> {
192 fn hash<H: Hasher>(&self, state: &mut H) {
193 self.raw.hash(state)
194 }
195}
196
197impl<N: AstNode> From<AstPtr<N>> for SyntaxNodePtr<N::Language> {
198 fn from(ptr: AstPtr<N>) -> SyntaxNodePtr<N::Language> {
199 ptr.raw
200 }
201}
202
203#[derive(Debug, Clone)]
204pub struct AstChildren<N: AstNode> {
205 inner: SyntaxNodeChildren<N::Language>,
206 ph: PhantomData<N>,
207}
208
209impl<N: AstNode> AstChildren<N> {
210 fn new(parent: &SyntaxNode<N::Language>) -> Self {
211 AstChildren { inner: parent.children(), ph: PhantomData }
212 }
213}
214
215impl<N: AstNode> Iterator for AstChildren<N> {
216 type Item = N;
217 fn next(&mut self) -> Option<N> {
218 self.inner.find_map(N::cast)
219 }
220}
221
222pub mod support {
223 use super::{AstChildren, AstNode};
224 use crate::{Language, SyntaxNode, SyntaxToken};
225
226 pub fn child<N: AstNode>(parent: &SyntaxNode<N::Language>) -> Option<N> {
227 parent.children().find_map(N::cast)
228 }
229
230 pub fn children<N: AstNode>(parent: &SyntaxNode<N::Language>) -> AstChildren<N> {
231 AstChildren::new(parent)
232 }
233
234 pub fn token<L: Language>(parent: &SyntaxNode<L>, kind: L::Kind) -> Option<SyntaxToken<L>> {
235 parent.children_with_tokens().filter_map(|it: NodeOrToken, …>| it.into_token()).find(|it: &SyntaxToken| it.kind() == kind)
236 }
237}
238
239#[cfg(test)]
240mod tests {
241 use crate::{GreenNodeBuilder, Language, SyntaxKind, SyntaxNode};
242
243 use super::SyntaxNodePtr;
244
245 #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
246 struct TestLanguage;
247 impl Language for TestLanguage {
248 type Kind = SyntaxKind;
249
250 fn kind_from_raw(raw: SyntaxKind) -> Self::Kind {
251 raw
252 }
253
254 fn kind_to_raw(kind: Self::Kind) -> SyntaxKind {
255 kind
256 }
257 }
258
259 fn build_immut_tree() -> SyntaxNode<TestLanguage> {
260 // Creates a single-node tree
261 let mut builder = GreenNodeBuilder::new();
262 builder.start_node(SyntaxKind(0));
263 builder.finish_node();
264
265 SyntaxNode::<TestLanguage>::new_root(builder.finish())
266 }
267
268 #[test]
269 #[should_panic = "tree is mutable"]
270 fn ensure_mut_panic_on_create() {
271 // Make a mutable version
272 let tree = build_immut_tree().clone_for_update();
273
274 SyntaxNodePtr::new(&tree);
275 }
276
277 #[test]
278 #[should_panic = "tree is mutable"]
279 fn ensure_mut_panic_on_deref() {
280 let tree = build_immut_tree();
281 let tree_mut = tree.clone_for_update();
282
283 // Create on immutable, convert on mutable
284 let syn_ptr = SyntaxNodePtr::new(&tree);
285 syn_ptr.to_node(&tree_mut);
286 }
287}
288