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#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
59pub struct SyntaxNodePtr<L: Language> {
60 kind: L::Kind,
61 range: TextRange,
62}
63
64impl<L: Language> SyntaxNodePtr<L> {
65 /// Returns a [`SyntaxNodePtr`] for the node.
66 pub fn new(node: &SyntaxNode<L>) -> Self {
67 Self { kind: node.kind(), range: node.text_range() }
68 }
69
70 /// Like [`Self::try_to_node`] but panics instead of returning `None` on
71 /// failure.
72 pub fn to_node(&self, root: &SyntaxNode<L>) -> SyntaxNode<L> {
73 self.try_to_node(root).unwrap_or_else(|| panic!("can't resolve {self:?} with {root:?}"))
74 }
75
76 /// "Dereferences" the pointer to get the [`SyntaxNode`] it points to.
77 ///
78 /// Returns `None` if the node is not found, so make sure that the `root`
79 /// syntax tree is equivalent to (i.e. is build from the same text from) the
80 /// tree which was originally used to get this [`SyntaxNodePtr`].
81 ///
82 /// Also returns `None` if `root` is not actually a root (i.e. it has a
83 /// parent).
84 ///
85 /// The complexity is linear in the depth of the tree and logarithmic in
86 /// tree width. As most trees are shallow, thinking about this as
87 /// `O(log(N))` in the size of the tree is not too wrong!
88 pub fn try_to_node(&self, root: &SyntaxNode<L>) -> Option<SyntaxNode<L>> {
89 if root.parent().is_some() {
90 return None;
91 }
92 successors(Some(root.clone()), |node| node.child_or_token_at_range(self.range)?.into_node())
93 .find(|it| it.text_range() == self.range && it.kind() == self.kind)
94 }
95
96 /// Casts this to an [`AstPtr`] to the given node type if possible.
97 pub fn cast<N: AstNode<Language = L>>(self) -> Option<AstPtr<N>> {
98 if !N::can_cast(self.kind) {
99 return None;
100 }
101 Some(AstPtr { raw: self })
102 }
103
104 /// Returns the kind of the syntax node this points to.
105 pub fn kind(&self) -> L::Kind {
106 self.kind
107 }
108
109 /// Returns the range of the syntax node this points to.
110 pub fn text_range(&self) -> TextRange {
111 self.range
112 }
113}
114
115/// Like [`SyntaxNodePtr`], but remembers the type of node.
116pub struct AstPtr<N: AstNode> {
117 raw: SyntaxNodePtr<N::Language>,
118}
119
120impl<N: AstNode> AstPtr<N> {
121 /// Returns an [`AstPtr`] for the node.
122 pub fn new(node: &N) -> Self {
123 Self { raw: SyntaxNodePtr::new(node.syntax()) }
124 }
125
126 /// Like `Self::try_to_node` but panics on failure.
127 pub fn to_node(&self, root: &SyntaxNode<N::Language>) -> N {
128 self.try_to_node(root).unwrap_or_else(|| panic!("can't resolve {self:?} with {root:?}"))
129 }
130
131 /// Given the root node containing the node `n` that `self` is a pointer to,
132 /// returns `n` if possible. See [`SyntaxNodePtr::try_to_node`].
133 pub fn try_to_node(&self, root: &SyntaxNode<N::Language>) -> Option<N> {
134 N::cast(self.raw.try_to_node(root)?)
135 }
136
137 /// Returns the underlying [`SyntaxNodePtr`].
138 pub fn syntax_node_ptr(&self) -> SyntaxNodePtr<N::Language> {
139 self.raw.clone()
140 }
141
142 /// Casts this to an [`AstPtr`] to the given node type if possible.
143 pub fn cast<U: AstNode<Language = N::Language>>(self) -> Option<AstPtr<U>> {
144 if !U::can_cast(self.raw.kind) {
145 return None;
146 }
147 Some(AstPtr { raw: self.raw })
148 }
149}
150
151impl<N: AstNode> fmt::Debug for AstPtr<N> {
152 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
153 f.debug_struct("AstPtr").field(name:"raw", &self.raw).finish()
154 }
155}
156
157impl<N: AstNode> Clone for AstPtr<N> {
158 fn clone(&self) -> Self {
159 Self { raw: self.raw.clone() }
160 }
161}
162
163impl<N: AstNode> PartialEq for AstPtr<N> {
164 fn eq(&self, other: &AstPtr<N>) -> bool {
165 self.raw == other.raw
166 }
167}
168
169impl<N: AstNode> Eq for AstPtr<N> {}
170
171impl<N: AstNode> Hash for AstPtr<N> {
172 fn hash<H: Hasher>(&self, state: &mut H) {
173 self.raw.hash(state)
174 }
175}
176
177impl<N: AstNode> From<AstPtr<N>> for SyntaxNodePtr<N::Language> {
178 fn from(ptr: AstPtr<N>) -> SyntaxNodePtr<N::Language> {
179 ptr.raw
180 }
181}
182
183#[derive(Debug, Clone)]
184pub struct AstChildren<N: AstNode> {
185 inner: SyntaxNodeChildren<N::Language>,
186 ph: PhantomData<N>,
187}
188
189impl<N: AstNode> AstChildren<N> {
190 fn new(parent: &SyntaxNode<N::Language>) -> Self {
191 AstChildren { inner: parent.children(), ph: PhantomData }
192 }
193}
194
195impl<N: AstNode> Iterator for AstChildren<N> {
196 type Item = N;
197 fn next(&mut self) -> Option<N> {
198 self.inner.find_map(N::cast)
199 }
200}
201
202pub mod support {
203 use super::{AstChildren, AstNode};
204 use crate::{Language, SyntaxNode, SyntaxToken};
205
206 pub fn child<N: AstNode>(parent: &SyntaxNode<N::Language>) -> Option<N> {
207 parent.children().find_map(N::cast)
208 }
209
210 pub fn children<N: AstNode>(parent: &SyntaxNode<N::Language>) -> AstChildren<N> {
211 AstChildren::new(parent)
212 }
213
214 pub fn token<L: Language>(parent: &SyntaxNode<L>, kind: L::Kind) -> Option<SyntaxToken<L>> {
215 parent.children_with_tokens().filter_map(|it: NodeOrToken, …>| it.into_token()).find(|it: &SyntaxToken| it.kind() == kind)
216 }
217}
218