mf2_syntax/
cst.rs

1//! The concrete syntax tree: a flat, pre-order arena of nodes and tokens.
2//!
3//! Every byte of the source belongs to exactly one **token** (a leaf), and
4//! the tokens, in order, spell the source: the CST is lossless
5//! (`cst.to_string() == source`). Whitespace and bidi marks are
6//! [`SyntaxKind::Trivia`] tokens; input the parser could not use is kept in
7//! [`SyntaxKind::Error`] tokens. **Nodes** group tokens and other nodes; each
8//! records the index one past its last descendant, so the tree is navigated
9//! without pointers or recursion.
10//!
11//! [`crate::parse_model`] fills the same arena without trivia and punctuation
12//! tokens (lowering does not need them); such an arena is not lossless.
13
14use alloc::vec::Vec;
15use core::fmt;
16
17use mf2_model::{Diagnostic, Diagnostics, Parsed, Span};
18
19/// What a node or token is.
20#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
21#[repr(u8)]
22#[non_exhaustive]
23pub enum SyntaxKind {
24    // ── nodes ──────────────────────────────────────────────────────────
25    /// Root of a simple message: one [`SyntaxKind::Pattern`].
26    SimpleMessage,
27    /// Root of a complex message: declarations, then a body.
28    ComplexMessage,
29    /// `.input {$name …}`.
30    InputDeclaration,
31    /// `.local $name = {…}`.
32    LocalDeclaration,
33    /// `{{` pattern `}}`.
34    QuotedPattern,
35    /// Text and placeholders.
36    Pattern,
37    /// `.match` selectors variants.
38    Matcher,
39    /// Keys and a quoted pattern.
40    Variant,
41    /// `{operand :function @attribute}`.
42    Expression,
43    /// `{#name …}`.
44    MarkupOpen,
45    /// `{#name … /}`.
46    MarkupStandalone,
47    /// `{/name …}`.
48    MarkupClose,
49    /// `:identifier options`.
50    Function,
51    /// `identifier = value`.
52    Option,
53    /// `@identifier [= literal]`.
54    Attribute,
55    /// `$name`.
56    Variable,
57    /// `[namespace :] name`.
58    Identifier,
59    /// `|…|`.
60    QuotedLiteral,
61
62    // ── tokens ─────────────────────────────────────────────────────────
63    /// A run of text characters in a pattern (no escapes).
64    Text,
65    /// A two-character escape sequence: `\\`, `\{`, `\|` or `\}`.
66    Escape,
67    /// A run of characters inside a quoted literal (no escapes).
68    LiteralText,
69    /// An unquoted literal.
70    UnquotedLiteral,
71    /// A name (of a variable, or one part of an identifier).
72    Name,
73    /// The catch-all key `*`.
74    Star,
75    /// `.input`.
76    KwInput,
77    /// `.local`.
78    KwLocal,
79    /// `.match`.
80    KwMatch,
81    /// `{`.
82    LBrace,
83    /// `}`.
84    RBrace,
85    /// `{{`.
86    LBrace2,
87    /// `}}`.
88    RBrace2,
89    /// `|`.
90    Pipe,
91    /// `$`.
92    Dollar,
93    /// `:` (function sigil or namespace separator).
94    Colon,
95    /// `#`.
96    Hash,
97    /// `/` (markup-close sigil or standalone marker).
98    Slash,
99    /// `@`.
100    At,
101    /// `=`.
102    Equals,
103    /// Whitespace and bidi marks outside text and literals.
104    Trivia,
105    /// Input the parser could not use (a syntax error was reported for it).
106    Error,
107}
108
109impl SyntaxKind {
110    /// A leaf (token) kind.
111    pub fn is_token(self) -> bool {
112        (self as u8) >= (SyntaxKind::Text as u8)
113    }
114
115    /// A node kind.
116    pub fn is_node(self) -> bool {
117        !self.is_token()
118    }
119
120    /// Tokens the data model needs; the others (trivia, punctuation,
121    /// keywords, errors) are left out of [`crate::parse_model`]'s arena.
122    pub(crate) fn is_semantic_token(self) -> bool {
123        matches!(
124            self,
125            SyntaxKind::Text
126                | SyntaxKind::Escape
127                | SyntaxKind::LiteralText
128                | SyntaxKind::UnquotedLiteral
129                | SyntaxKind::Name
130                | SyntaxKind::Star
131        )
132    }
133
134    /// A markup node kind.
135    pub fn is_markup(self) -> bool {
136        matches!(
137            self,
138            SyntaxKind::MarkupOpen | SyntaxKind::MarkupStandalone | SyntaxKind::MarkupClose
139        )
140    }
141}
142
143/// One entry of the arena.
144#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
145pub struct Node {
146    pub(crate) start: u32,
147    pub(crate) end: u32,
148    /// Index one past the last descendant (`index + 1` for a token).
149    pub(crate) last: u32,
150    pub(crate) kind: SyntaxKind,
151}
152
153impl Node {
154    /// What it is.
155    pub fn kind(&self) -> SyntaxKind {
156        self.kind
157    }
158
159    /// Where it is.
160    pub fn span(&self) -> Span {
161        Span {
162            start: self.start,
163            end: self.end,
164        }
165    }
166
167    pub(crate) fn range(&self) -> core::ops::Range<usize> {
168        self.start as usize..self.end as usize
169    }
170}
171
172/// A borrowed CST: the source, the arena and the syntax diagnostics.
173#[derive(Clone, Copy, Debug)]
174pub struct CstRef<'a, 'src> {
175    pub(crate) src: &'src str,
176    pub(crate) nodes: &'a [Node],
177    pub(crate) diagnostics: &'a [Diagnostic],
178}
179
180impl<'a, 'src> CstRef<'a, 'src> {
181    /// The source.
182    pub fn source(&self) -> &'src str {
183        self.src
184    }
185
186    /// The root node (`None` only for a source over `u32::MAX` bytes, which
187    /// is rejected with [`crate::code::SOURCE_TOO_LONG`]).
188    pub fn root(&self) -> Option<SyntaxNode<'a, 'src>> {
189        (!self.nodes.is_empty()).then_some(SyntaxNode {
190            src: self.src,
191            nodes: self.nodes,
192            index: 0,
193        })
194    }
195
196    /// The whole arena, in pre-order.
197    pub fn nodes(&self) -> &'a [Node] {
198        self.nodes
199    }
200
201    /// The syntax errors, in source order of detection.
202    pub fn diagnostics(&self) -> &'a [Diagnostic] {
203        self.diagnostics
204    }
205
206    /// Whether any syntax error was reported.
207    pub fn has_errors(&self) -> bool {
208        !self.diagnostics.is_empty()
209    }
210
211    /// The tokens (leaves), in source order.
212    pub fn tokens(&self) -> impl Iterator<Item = SyntaxNode<'a, 'src>> + use<'a, 'src> {
213        let (src, nodes) = (self.src, self.nodes);
214        nodes
215            .iter()
216            .enumerate()
217            .filter(|(_, n)| n.kind.is_token())
218            .map(move |(i, _)| SyntaxNode {
219                src,
220                nodes,
221                // Arena indices fit in u32: sources over u32::MAX bytes are
222                // rejected before parsing.
223                index: u32::try_from(i).unwrap_or(u32::MAX),
224            })
225    }
226
227    /// Lowers the CST to the data model and validates it (spans included);
228    /// with a syntax error, no model and the syntax diagnostics.
229    pub fn to_model(&self) -> Parsed<'src> {
230        if self.has_errors() || self.nodes.is_empty() {
231            return Parsed {
232                message: None,
233                diagnostics: Diagnostics::from(self.diagnostics.to_vec()),
234            };
235        }
236        crate::model_from_arena(self.src, self.nodes)
237    }
238}
239
240impl fmt::Display for CstRef<'_, '_> {
241    /// Writes the tokens' text in order, which is the source.
242    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
243        for t in self.tokens() {
244            f.write_str(t.text())?;
245        }
246        Ok(())
247    }
248}
249
250/// An owned CST (see [`crate::parse_cst`]).
251#[derive(Clone, Debug)]
252pub struct Cst<'src> {
253    pub(crate) src: &'src str,
254    pub(crate) nodes: Vec<Node>,
255    pub(crate) diagnostics: Vec<Diagnostic>,
256}
257
258impl<'src> Cst<'src> {
259    /// The borrowed view, with every accessor.
260    pub fn view(&self) -> CstRef<'_, 'src> {
261        CstRef {
262            src: self.src,
263            nodes: &self.nodes,
264            diagnostics: &self.diagnostics,
265        }
266    }
267
268    /// The source.
269    pub fn source(&self) -> &'src str {
270        self.src
271    }
272
273    /// The root node (see [`CstRef::root`]).
274    pub fn root(&self) -> Option<SyntaxNode<'_, 'src>> {
275        self.view().root()
276    }
277
278    /// The syntax errors.
279    pub fn diagnostics(&self) -> &[Diagnostic] {
280        &self.diagnostics
281    }
282
283    /// Whether any syntax error was reported.
284    pub fn has_errors(&self) -> bool {
285        !self.diagnostics.is_empty()
286    }
287
288    /// See [`CstRef::to_model`].
289    pub fn to_model(&self) -> Parsed<'src> {
290        self.view().to_model()
291    }
292}
293
294impl fmt::Display for Cst<'_> {
295    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
296        fmt::Display::fmt(&self.view(), f)
297    }
298}
299
300/// A node or token of a CST, with navigation.
301#[derive(Clone, Copy, Debug)]
302pub struct SyntaxNode<'a, 'src> {
303    src: &'src str,
304    nodes: &'a [Node],
305    index: u32,
306}
307
308impl<'a, 'src> SyntaxNode<'a, 'src> {
309    fn node(&self) -> Node {
310        self.nodes[self.index as usize]
311    }
312
313    /// Its index in the arena.
314    pub fn index(&self) -> usize {
315        self.index as usize
316    }
317
318    /// What it is.
319    pub fn kind(&self) -> SyntaxKind {
320        self.node().kind
321    }
322
323    /// Where it is.
324    pub fn span(&self) -> Span {
325        self.node().span()
326    }
327
328    /// The source text it covers.
329    pub fn text(&self) -> &'src str {
330        self.src.get(self.node().range()).unwrap_or("")
331    }
332
333    /// Whether it is a token (leaf).
334    pub fn is_token(&self) -> bool {
335        self.kind().is_token()
336    }
337
338    /// Its direct children, in order.
339    pub fn children(&self) -> impl Iterator<Item = SyntaxNode<'a, 'src>> + use<'a, 'src> {
340        let (src, nodes) = (self.src, self.nodes);
341        let end = self.node().last;
342        let mut next = self.index + 1;
343        core::iter::from_fn(move || {
344            if next >= end {
345                return None;
346            }
347            let index = next;
348            next = nodes.get(index as usize).map_or(end, |n| n.last);
349            Some(SyntaxNode { src, nodes, index })
350        })
351    }
352
353    /// Its descendants (not itself), in pre-order.
354    pub fn descendants(&self) -> impl Iterator<Item = SyntaxNode<'a, 'src>> + use<'a, 'src> {
355        let (src, nodes) = (self.src, self.nodes);
356        (self.index + 1..self.node().last).map(move |index| SyntaxNode { src, nodes, index })
357    }
358}
mf2_syntax/cst.rs

mf2_syntax/
cst.rs
