gdck_syntax/
tree.rs

1//! The concrete syntax tree.
2//!
3//! Every byte of the source lives in exactly one token, and every token lives
4//! in the tree, so [`SyntaxTree::text`] reproduces the input exactly. That is
5//! what lets a formatter rewrite one construct while leaving the surrounding
6//! comments and blank lines untouched.
7//!
8//! Nodes live in a flat arena and refer to each other by index. Compared with
9//! `Rc`-based trees this keeps children contiguous and traversal
10//! cache-friendly, at the cost of needing the tree around to interpret a
11//! [`NodeId`].
12
13use std::fmt::{self, Write as _};
14
15use crate::error::SyntaxError;
16use crate::kind::SyntaxKind;
17use crate::lexer::Token;
18use crate::text::TextRange;
19
20/// An index into a [`SyntaxTree`]'s node arena.
21#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
22pub struct NodeId(u32);
23
24/// A child of a node: either a nested node or a leaf token.
25#[derive(Debug, Clone, Copy, PartialEq, Eq)]
26pub enum Element {
27    Node(NodeId),
28    Token(Token),
29}
30
31#[derive(Debug, Clone)]
32struct NodeData {
33    kind: SyntaxKind,
34    range: TextRange,
35    children: Vec<Element>,
36}
37
38/// A parsed GDScript file: the source text plus its tree and diagnostics.
39#[derive(Debug, Clone)]
40pub struct SyntaxTree {
41    source: String,
42    nodes: Vec<NodeData>,
43    root: NodeId,
44    errors: Vec<SyntaxError>,
45}
46
47impl SyntaxTree {
48    /// The source text this tree was built from.
49    #[must_use]
50    pub fn text(&self) -> &str {
51        &self.source
52    }
53
54    /// The outermost node, always [`SyntaxKind::SourceFile`].
55    #[must_use]
56    pub fn root(&self) -> SyntaxNode<'_> {
57        SyntaxNode {
58            tree: self,
59            id: self.root,
60        }
61    }
62
63    /// Diagnostics collected while lexing and parsing.
64    ///
65    /// A non-empty list does not mean the tree is unusable — it is still
66    /// complete and lossless, with the unparseable regions wrapped in
67    /// [`SyntaxKind::Error`] nodes.
68    #[must_use]
69    pub fn errors(&self) -> &[SyntaxError] {
70        &self.errors
71    }
72
73    /// Whether parsing found any problems.
74    #[must_use]
75    pub fn has_errors(&self) -> bool {
76        !self.errors.is_empty()
77    }
78
79    /// Resolve a node id obtained from this tree.
80    #[must_use]
81    pub fn node(&self, id: NodeId) -> SyntaxNode<'_> {
82        SyntaxNode { tree: self, id }
83    }
84
85    fn data(&self, id: NodeId) -> &NodeData {
86        &self.nodes[id.0 as usize]
87    }
88}
89
90/// A borrowed handle to one node in a [`SyntaxTree`].
91#[derive(Debug, Clone, Copy)]
92pub struct SyntaxNode<'a> {
93    tree: &'a SyntaxTree,
94    id: NodeId,
95}
96
97impl<'a> SyntaxNode<'a> {
98    #[must_use]
99    pub fn id(self) -> NodeId {
100        self.id
101    }
102
103    /// The tree this node belongs to.
104    ///
105    /// Needed to resolve the [`NodeId`]s handed out by [`Self::children`],
106    /// which is how a caller walks nodes and tokens together in source order.
107    #[must_use]
108    pub fn tree(self) -> &'a SyntaxTree {
109        self.tree
110    }
111
112    #[must_use]
113    pub fn kind(self) -> SyntaxKind {
114        self.tree.data(self.id).kind
115    }
116
117    #[must_use]
118    pub fn range(self) -> TextRange {
119        self.tree.data(self.id).range
120    }
121
122    /// The exact source text this node covers, trivia included.
123    #[must_use]
124    pub fn text(self) -> &'a str {
125        self.range().slice(self.tree.text())
126    }
127
128    /// Direct children, nodes and tokens interleaved in source order.
129    pub fn children(self) -> impl Iterator<Item = Element> + 'a {
130        self.tree.data(self.id).children.iter().copied()
131    }
132
133    /// Direct child nodes, skipping tokens.
134    pub fn child_nodes(self) -> impl Iterator<Item = SyntaxNode<'a>> + 'a {
135        let tree = self.tree;
136        self.children().filter_map(move |element| match element {
137            Element::Node(id) => Some(SyntaxNode { tree, id }),
138            Element::Token(_) => None,
139        })
140    }
141
142    /// Direct child tokens, skipping nodes.
143    pub fn child_tokens(self) -> impl Iterator<Item = Token> + 'a {
144        self.children().filter_map(|element| match element {
145            Element::Token(token) => Some(token),
146            Element::Node(_) => None,
147        })
148    }
149
150    /// The first direct child node of the given kind.
151    #[must_use]
152    pub fn child_node_of(self, kind: SyntaxKind) -> Option<SyntaxNode<'a>> {
153        self.child_nodes().find(|node| node.kind() == kind)
154    }
155
156    /// The first direct child token of the given kind.
157    #[must_use]
158    pub fn child_token_of(self, kind: SyntaxKind) -> Option<Token> {
159        self.child_tokens().find(|token| token.kind == kind)
160    }
161
162    /// Every node in this subtree, parents before children.
163    #[must_use]
164    pub fn descendants(self) -> Descendants<'a> {
165        Descendants { stack: vec![self] }
166    }
167}
168
169/// Pre-order iterator over a subtree. See [`SyntaxNode::descendants`].
170#[derive(Debug)]
171pub struct Descendants<'a> {
172    stack: Vec<SyntaxNode<'a>>,
173}
174
175impl<'a> Iterator for Descendants<'a> {
176    type Item = SyntaxNode<'a>;
177
178    fn next(&mut self) -> Option<Self::Item> {
179        let node = self.stack.pop()?;
180        // Push in reverse so children come back out in source order.
181        let children: Vec<_> = node.child_nodes().collect();
182        self.stack.extend(children.into_iter().rev());
183        Some(node)
184    }
185}
186
187impl fmt::Display for SyntaxTree {
188    /// Renders the tree in the indented form used by `gdck parse --tree`.
189    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
190        let mut out = String::new();
191        write_node(&mut out, self.root(), 0)?;
192        f.write_str(&out)
193    }
194}
195
196fn write_node(out: &mut String, node: SyntaxNode<'_>, depth: usize) -> fmt::Result {
197    let indent = "  ".repeat(depth);
198    writeln!(out, "{indent}{:?}@{}", node.kind(), node.range())?;
199    for element in node.children() {
200        match element {
201            Element::Node(id) => write_node(out, node.tree.node(id), depth + 1)?,
202            Element::Token(token) => {
203                let indent = "  ".repeat(depth + 1);
204                let text = token.text(node.tree.text());
205                if text.is_empty() {
206                    writeln!(out, "{indent}{:?}@{}", token.kind, token.range)?;
207                } else {
208                    writeln!(out, "{indent}{:?}@{} {:?}", token.kind, token.range, text)?;
209                }
210            }
211        }
212    }
213    Ok(())
214}
215
216// -- Builder ----------------------------------------------------------------
217
218/// A position in the child buffer that a node can later be opened at.
219///
220/// Needed because an expression parser only discovers it is looking at a binary
221/// expression *after* parsing the left operand.
222#[derive(Debug, Clone, Copy, PartialEq, Eq)]
223pub struct Checkpoint(usize);
224
225/// Builds a [`SyntaxTree`] as the parser walks the token stream.
226///
227/// Children accumulate in one flat buffer; closing a node drains its slice out
228/// of that buffer into the arena. This keeps [`TreeBuilder::checkpoint`] O(1),
229/// which matters because the Pratt expression parser takes one per operand.
230#[derive(Debug)]
231pub struct TreeBuilder {
232    nodes: Vec<NodeData>,
233    children: Vec<Element>,
234    stack: Vec<(SyntaxKind, usize)>,
235    /// Where the last token ended, so empty nodes still get a sensible position.
236    last_offset: u32,
237}
238
239impl TreeBuilder {
240    #[must_use]
241    pub fn new() -> Self {
242        Self {
243            nodes: Vec::new(),
244            children: Vec::new(),
245            stack: Vec::new(),
246            last_offset: 0,
247        }
248    }
249
250    pub fn start_node(&mut self, kind: SyntaxKind) {
251        debug_assert!(kind.is_node(), "{kind:?} is a token, not a node");
252        self.stack.push((kind, self.children.len()));
253    }
254
255    #[must_use]
256    pub fn checkpoint(&self) -> Checkpoint {
257        Checkpoint(self.children.len())
258    }
259
260    /// Open a node that retroactively contains everything added since
261    /// `checkpoint`.
262    pub fn start_node_at(&mut self, checkpoint: Checkpoint, kind: SyntaxKind) {
263        debug_assert!(kind.is_node(), "{kind:?} is a token, not a node");
264        debug_assert!(
265            checkpoint.0 <= self.children.len(),
266            "checkpoint outlived its buffer"
267        );
268        self.stack.push((kind, checkpoint.0));
269    }
270
271    pub fn token(&mut self, token: Token) {
272        debug_assert!(token.kind.is_token(), "{:?} is a node", token.kind);
273        self.last_offset = token.range.end();
274        self.children.push(Element::Token(token));
275    }
276
277    pub fn finish_node(&mut self) {
278        let (kind, start) = self.stack.pop().expect("finish_node without start_node");
279        let children: Vec<Element> = self.children.drain(start..).collect();
280
281        let range = children
282            .iter()
283            .map(|element| match element {
284                Element::Token(token) => token.range,
285                Element::Node(id) => self.nodes[id.0 as usize].range,
286            })
287            .reduce(TextRange::cover)
288            .unwrap_or_else(|| TextRange::empty(self.last_offset));
289
290        let id = NodeId(self.nodes.len() as u32);
291        self.nodes.push(NodeData {
292            kind,
293            range,
294            children,
295        });
296        self.children.push(Element::Node(id));
297    }
298
299    /// Close the builder, producing the finished tree.
300    ///
301    /// # Panics
302    ///
303    /// Panics if any node is still open, or if the builder produced anything
304    /// other than exactly one root node.
305    #[must_use]
306    pub fn finish(mut self, source: String, errors: Vec<SyntaxError>) -> SyntaxTree {
307        assert!(self.stack.is_empty(), "unclosed nodes remain");
308        assert_eq!(self.children.len(), 1, "expected exactly one root node");
309
310        let root = match self.children.pop().expect("checked non-empty") {
311            Element::Node(id) => id,
312            Element::Token(_) => panic!("root must be a node"),
313        };
314
315        SyntaxTree {
316            source,
317            nodes: self.nodes,
318            root,
319            errors,
320        }
321    }
322}
323
324impl Default for TreeBuilder {
325    fn default() -> Self {
326        Self::new()
327    }
328}
329
330#[cfg(test)]
331mod tests {
332    use super::*;
333
334    fn token(kind: SyntaxKind, start: u32, end: u32) -> Token {
335        Token {
336            kind,
337            range: TextRange::new(start, end),
338        }
339    }
340
341    #[test]
342    fn builds_a_nested_tree() {
343        let mut builder = TreeBuilder::new();
344        builder.start_node(SyntaxKind::SourceFile);
345        builder.start_node(SyntaxKind::PassStmt);
346        builder.token(token(SyntaxKind::PassKw, 0, 4));
347        builder.finish_node();
348        builder.token(token(SyntaxKind::Newline, 4, 5));
349        builder.finish_node();
350
351        let tree = builder.finish("pass\n".to_string(), Vec::new());
352        assert_eq!(tree.root().kind(), SyntaxKind::SourceFile);
353        assert_eq!(tree.root().range(), TextRange::new(0, 5));
354        assert_eq!(tree.text(), "pass\n");
355
356        let stmt = tree.root().child_nodes().next().expect("one child node");
357        assert_eq!(stmt.kind(), SyntaxKind::PassStmt);
358        assert_eq!(stmt.text(), "pass");
359    }
360
361    #[test]
362    fn checkpoint_wraps_already_added_children() {
363        // Mirrors how the Pratt parser turns `a + b` into a BinaryExpr only
364        // after `a` has already been emitted.
365        let mut builder = TreeBuilder::new();
366        builder.start_node(SyntaxKind::SourceFile);
367        let checkpoint = builder.checkpoint();
368        builder.token(token(SyntaxKind::Ident, 0, 1));
369        builder.start_node_at(checkpoint, SyntaxKind::BinaryExpr);
370        builder.token(token(SyntaxKind::Plus, 2, 3));
371        builder.token(token(SyntaxKind::Ident, 4, 5));
372        builder.finish_node();
373        builder.finish_node();
374
375        let tree = builder.finish("a + b".to_string(), Vec::new());
376        let binary = tree.root().child_nodes().next().expect("binary expr");
377        assert_eq!(binary.kind(), SyntaxKind::BinaryExpr);
378        assert_eq!(binary.range(), TextRange::new(0, 5));
379        assert_eq!(binary.child_tokens().count(), 3);
380    }
381
382    #[test]
383    fn empty_nodes_get_a_position() {
384        let mut builder = TreeBuilder::new();
385        builder.start_node(SyntaxKind::SourceFile);
386        builder.token(token(SyntaxKind::PassKw, 0, 4));
387        builder.start_node(SyntaxKind::Block);
388        builder.finish_node();
389        builder.finish_node();
390
391        let tree = builder.finish("pass".to_string(), Vec::new());
392        let block = tree.root().child_nodes().next().expect("block");
393        assert_eq!(block.range(), TextRange::empty(4));
394        assert_eq!(block.text(), "");
395    }
396
397    #[test]
398    fn descendants_walk_in_source_order() {
399        let mut builder = TreeBuilder::new();
400        builder.start_node(SyntaxKind::SourceFile);
401        builder.start_node(SyntaxKind::VarDecl);
402        builder.token(token(SyntaxKind::VarKw, 0, 3));
403        builder.finish_node();
404        builder.start_node(SyntaxKind::PassStmt);
405        builder.token(token(SyntaxKind::PassKw, 4, 8));
406        builder.finish_node();
407        builder.finish_node();
408
409        let tree = builder.finish("var pass".to_string(), Vec::new());
410        let kinds: Vec<_> = tree.root().descendants().map(SyntaxNode::kind).collect();
411        assert_eq!(
412            kinds,
413            vec![
414                SyntaxKind::SourceFile,
415                SyntaxKind::VarDecl,
416                SyntaxKind::PassStmt
417            ]
418        );
419    }
420}
gdck_syntax/tree.rs

gdck_syntax/
tree.rs
