Skip to main content

concrete_syntax_tree/
lib.rs

1#![doc = include_str!("../README.md")]
2
3//! A small, lossless concrete syntax tree for parser tooling.
4
5use std::ops::Range;
6
7/// Trait implemented by each language's concrete-syntax-tree node kind.
8pub trait CstKind: Copy + Eq + std::fmt::Debug {
9    /// Returns `true` if this node kind represents trivia such as whitespace
10    /// or a comment.
11    fn is_trivia(self) -> bool;
12
13    /// Returns a human-readable name for this node kind, suitable for
14    /// diagnostics.
15    fn description(self) -> &'static str;
16}
17
18/// A node in a concrete syntax tree.
19///
20/// Each node represents either a leaf token or a branch grammar production.
21/// The node kind is supplied by the language-specific parser.
22#[derive(Debug, Clone, PartialEq, Eq)]
23pub struct CstNode<K> {
24    /// The syntactic construct represented by this node.
25    pub kind: K,
26    /// The byte range in the source text covered by this node.
27    pub span: Range<usize>,
28    /// Child nodes. This is empty for leaf nodes.
29    pub children: Vec<CstNode<K>>,
30    /// The exact token text for a leaf node. Branch nodes contain `None`.
31    pub text: Option<String>,
32}
33
34impl<K: CstKind> CstNode<K> {
35    /// Creates a leaf node from a token.
36    #[must_use]
37    pub fn leaf(kind: K, span: Range<usize>, text: &str) -> Self {
38        Self {
39            kind,
40            span,
41            children: Vec::new(),
42            text: Some(text.to_owned()),
43        }
44    }
45
46    /// Creates a branch node containing the supplied children.
47    #[must_use]
48    pub fn branch(kind: K, children: Vec<CstNode<K>>) -> Self {
49        let span = if children.is_empty() {
50            0..0
51        } else {
52            let start = children.first().map_or(0, |c| c.span.start);
53            let end = children.last().map_or(0, |c| c.span.end);
54            start..end
55        };
56        Self {
57            kind,
58            span,
59            children,
60            text: None,
61        }
62    }
63
64    /// Reconstructs source text from this node and its descendants.
65    ///
66    /// Leaf text is returned directly. Branch text is the concatenation of
67    /// descendant leaf text in source order.
68    #[must_use]
69    pub fn to_source(&self) -> String {
70        if let Some(text) = &self.text {
71            return text.clone();
72        }
73
74        let mut buf = String::new();
75        for child in &self.children {
76            buf.push_str(&child.to_source());
77        }
78        buf
79    }
80
81    /// Returns whether this node represents trivia.
82    #[must_use]
83    pub fn is_trivia(&self) -> bool {
84        self.kind.is_trivia()
85    }
86}
87
88#[cfg(test)]
89mod tests {
90    use super::*;
91
92    #[derive(Debug, Clone, Copy, PartialEq, Eq)]
93    enum TestKind {
94        Root,
95        Word,
96        Space,
97    }
98
99    impl CstKind for TestKind {
100        fn is_trivia(self) -> bool {
101            matches!(self, Self::Space)
102        }
103
104        fn description(self) -> &'static str {
105            match self {
106                Self::Root => "root",
107                Self::Word => "word",
108                Self::Space => "space",
109            }
110        }
111    }
112
113    #[test]
114    fn leaf_round_trip() {
115        let leaf = CstNode::leaf(TestKind::Word, 0..5, "hello");
116        assert_eq!(leaf.to_source(), "hello");
117        assert!(!leaf.is_trivia());
118    }
119
120    #[test]
121    fn branch_round_trip() {
122        let a = CstNode::leaf(TestKind::Word, 0..5, "hello");
123        let ws = CstNode::leaf(TestKind::Space, 5..6, " ");
124        let b = CstNode::leaf(TestKind::Word, 6..11, "world");
125        let root = CstNode::branch(TestKind::Root, vec![a, ws, b]);
126        assert_eq!(root.to_source(), "hello world");
127        assert_eq!(root.span, 0..11);
128    }
129
130    #[test]
131    fn trivia_detection() {
132        let ws = CstNode::leaf(TestKind::Space, 0..1, " ");
133        assert!(ws.is_trivia());
134        let word = CstNode::leaf(TestKind::Word, 0..3, "foo");
135        assert!(!word.is_trivia());
136    }
137
138    #[test]
139    fn empty_branch() {
140        let branch: CstNode<TestKind> = CstNode::branch(TestKind::Root, vec![]);
141        assert_eq!(branch.span, 0..0);
142        assert_eq!(branch.to_source(), "");
143    }
144}