meta_language/grammar/feature_runtime/
tree.rs

1//! The public concrete syntax tree of the native grammar executor and its
2//! compact, stable text rendering (docs/grammar/feature-union.md#syntax-tree),
3//! as `js/src/grammar-runtime/syntax-tree.js`. Every node keeps its byte span,
4//! every token its exact text, and trivia, ERROR, MISSING and
5//! embedded-language nodes stay in the tree, so the tree reproduces the input
6//! byte for byte.
7
8use std::collections::BTreeMap;
9use std::fmt::Write as _;
10
11use super::operations::OperationValue;
12use super::program::Compiled;
13use super::results::{Tree, TreeType};
14use super::text::{hex_of, quote_text, text_of};
15
16/// The attributes semantic actions set on a node or token, by name.
17pub type SyntaxAttributes = BTreeMap<String, OperationValue>;
18
19/// The text of a leaf: the exact UTF-8 text, or the hexadecimal spelling of
20/// bytes that are not well-formed UTF-8.
21#[derive(Clone, Debug, PartialEq, Eq)]
22pub enum LeafText {
23    /// Well-formed UTF-8 text.
24    Text(String),
25    /// The lower-case hexadecimal spelling of the bytes.
26    Hex(String),
27}
28
29impl LeafText {
30    fn of(bytes: &[u8], start: usize, end: usize) -> Self {
31        text_of(bytes, start, end).map_or_else(|| Self::Hex(hex_of(bytes, start, end)), Self::Text)
32    }
33
34    fn render(&self) -> String {
35        match self {
36            Self::Text(text) => quote_text(text),
37            Self::Hex(hex) => format!("<{hex}>"),
38        }
39    }
40}
41
42/// One node of a concrete syntax tree; offsets are byte offsets into the input.
43#[derive(Clone, Debug, PartialEq, Eq)]
44pub enum SyntaxTree {
45    /// A node a rule (or an alias) built.
46    Node {
47        /// The node kind.
48        kind: String,
49        /// The field the node is captured under.
50        field: Option<String>,
51        /// Whether the node is trivia (an extra of a rule that builds a node).
52        trivia: bool,
53        /// The first byte.
54        start: usize,
55        /// The byte after the last.
56        end: usize,
57        /// The children, trivia included.
58        children: Vec<Self>,
59        /// The attributes semantic actions set.
60        attributes: Option<SyntaxAttributes>,
61    },
62    /// A leaf: a literal, a token rule, an external token or trivia.
63    Token {
64        /// The token kind; `None` for an anonymous literal.
65        kind: Option<String>,
66        /// The field the token is captured under.
67        field: Option<String>,
68        /// Whether the token is trivia (an extra or a channel token).
69        trivia: bool,
70        /// The first byte.
71        start: usize,
72        /// The byte after the last.
73        end: usize,
74        /// The attributes semantic actions set.
75        attributes: Option<SyntaxAttributes>,
76        /// The token text.
77        text: LeafText,
78    },
79    /// Input error recovery skipped, or the whole input of a refused parse.
80    Error {
81        /// The first byte.
82        start: usize,
83        /// The byte after the last.
84        end: usize,
85        /// The skipped text.
86        text: LeafText,
87        /// Why the input is an error node, when it is not skipped input.
88        reason: Option<String>,
89    },
90    /// A zero-width node error recovery inserted for an absent item.
91    Missing {
92        /// The missing rule kind or literal.
93        kind: Option<String>,
94        /// The offset.
95        start: usize,
96        /// The offset again: missing nodes are empty.
97        end: usize,
98        /// Whether `kind` is a literal.
99        literal: bool,
100    },
101    /// A region another language parsed.
102    Embed {
103        /// The embedded language.
104        language: String,
105        /// The first byte.
106        start: usize,
107        /// The byte after the last.
108        end: usize,
109        /// The tree of the embedded language.
110        root: Box<Self>,
111    },
112}
113
114impl SyntaxTree {
115    /// The first byte of the node.
116    #[must_use]
117    pub const fn start(&self) -> usize {
118        match self {
119            Self::Node { start, .. }
120            | Self::Token { start, .. }
121            | Self::Error { start, .. }
122            | Self::Missing { start, .. }
123            | Self::Embed { start, .. } => *start,
124        }
125    }
126
127    /// The byte after the last byte of the node.
128    #[must_use]
129    pub const fn end(&self) -> usize {
130        match self {
131            Self::Node { end, .. }
132            | Self::Token { end, .. }
133            | Self::Error { end, .. }
134            | Self::Missing { end, .. }
135            | Self::Embed { end, .. } => *end,
136        }
137    }
138
139    /// The first ERROR or MISSING node, in preorder.
140    #[must_use]
141    pub fn first_recovery(&self) -> Option<&Self> {
142        match self {
143            Self::Error { .. } | Self::Missing { .. } => Some(self),
144            Self::Node { children, .. } => children.iter().find_map(Self::first_recovery),
145            Self::Embed { root, .. } => root.first_recovery(),
146            Self::Token { .. } => None,
147        }
148    }
149
150    /// The compact text rendering: `(kind {attributes} child ...)` for a
151    /// node, `field:` before a captured child, the quoted text of an
152    /// anonymous token, `(kind "text")` for a named one, `~` before trivia,
153    /// and `(ERROR@S..E "text")`, `(MISSING@P kind)` and
154    /// `(EMBED language@S..E root)`.
155    #[must_use]
156    pub fn render(&self) -> String {
157        let mut rendered = String::new();
158        self.render_into(&mut rendered);
159        rendered
160    }
161
162    fn render_into(&self, out: &mut String) {
163        match self {
164            Self::Node {
165                kind,
166                field,
167                trivia,
168                children,
169                attributes,
170                ..
171            } => {
172                render_field(field.as_deref(), out);
173                if *trivia {
174                    out.push('~');
175                }
176                out.push('(');
177                out.push_str(&render_name(kind));
178                if let Some(attributes) = attributes {
179                    out.push(' ');
180                    render_attributes(attributes, out);
181                }
182                for child in children {
183                    out.push(' ');
184                    child.render_into(out);
185                }
186                out.push(')');
187            }
188            Self::Token {
189                kind,
190                field,
191                trivia,
192                attributes,
193                text,
194                ..
195            } => {
196                render_field(field.as_deref(), out);
197                if *trivia {
198                    out.push('~');
199                }
200                if kind.is_none() && attributes.is_none() {
201                    out.push_str(&text.render());
202                    return;
203                }
204                out.push('(');
205                out.push_str(&kind.as_deref().map_or_else(|| "_".to_owned(), render_name));
206                if let Some(attributes) = attributes {
207                    out.push(' ');
208                    render_attributes(attributes, out);
209                }
210                out.push(' ');
211                out.push_str(&text.render());
212                out.push(')');
213            }
214            Self::Error {
215                start, end, text, ..
216            } => {
217                let _ = write!(out, "(ERROR@{start}..{end} {})", text.render());
218            }
219            Self::Missing {
220                kind,
221                start,
222                literal,
223                ..
224            } => match kind {
225                None => {
226                    let _ = write!(out, "(MISSING@{start})");
227                }
228                Some(kind) => {
229                    let name = if *literal {
230                        quote_text(kind)
231                    } else {
232                        render_name(kind)
233                    };
234                    let _ = write!(out, "(MISSING@{start} {name})");
235                }
236            },
237            Self::Embed {
238                language,
239                start,
240                end,
241                root,
242            } => {
243                let _ = write!(out, "(EMBED {}@{start}..{end} ", render_name(language));
244                root.render_into(out);
245                out.push(')');
246            }
247        }
248    }
249}
250
251fn render_field(field: Option<&str>, out: &mut String) {
252    if let Some(field) = field {
253        out.push_str(&render_name(field));
254        out.push(':');
255    }
256}
257
258fn render_name(name: &str) -> String {
259    let mut chars = name.chars();
260    let plain = chars
261        .next()
262        .is_some_and(|first| first.is_ascii_alphabetic() || first == '_')
263        && chars.all(|c| c.is_ascii_alphanumeric() || c == '_' || c == '-');
264    if plain {
265        name.to_owned()
266    } else {
267        quote_text(name)
268    }
269}
270
271fn render_attributes(attributes: &SyntaxAttributes, out: &mut String) {
272    out.push('{');
273    for (index, (name, value)) in attributes.iter().enumerate() {
274        if index > 0 {
275            out.push(',');
276        }
277        out.push_str(&render_name(name));
278        out.push('=');
279        match value {
280            OperationValue::Text(text) => out.push_str(&quote_text(text)),
281            OperationValue::Integer(integer) => {
282                let _ = write!(out, "{integer}");
283            }
284        }
285    }
286    out.push('}');
287}
288
289/// Copies an executor tree into the public shape.
290pub(super) fn public_tree(node: &Tree, bytes: &[u8]) -> SyntaxTree {
291    let name = |value: &Option<super::program::Name>| value.as_deref().map(str::to_owned);
292    match node.ty {
293        TreeType::Node => SyntaxTree::Node {
294            kind: name(&node.kind).unwrap_or_default(),
295            field: name(&node.field),
296            trivia: node.trivia,
297            start: node.start,
298            end: node.end,
299            children: node
300                .children
301                .iter()
302                .map(|child| public_tree(child, bytes))
303                .collect(),
304            attributes: node.attributes.clone(),
305        },
306        TreeType::Token => SyntaxTree::Token {
307            kind: name(&node.kind),
308            field: name(&node.field),
309            trivia: node.trivia,
310            start: node.start,
311            end: node.end,
312            attributes: node.attributes.clone(),
313            text: LeafText::of(bytes, node.start, node.end),
314        },
315        TreeType::Error => error_tree(bytes, node.start, node.end, None),
316        TreeType::Missing => SyntaxTree::Missing {
317            kind: name(&node.kind),
318            start: node.start,
319            end: node.end,
320            literal: node.literal,
321        },
322        TreeType::Embed => SyntaxTree::Embed {
323            language: name(&node.language).unwrap_or_default(),
324            start: node.start,
325            end: node.end,
326            root: Box::new(node.root.as_ref().map_or_else(
327                || error_tree(bytes, node.start, node.end, None),
328                |root| public_tree(root, bytes),
329            )),
330        },
331    }
332}
333
334pub(super) fn error_tree(
335    bytes: &[u8],
336    start: usize,
337    end: usize,
338    reason: Option<&str>,
339) -> SyntaxTree {
340    SyntaxTree::Error {
341        start,
342        end,
343        text: LeafText::of(bytes, start, end),
344        reason: reason.map(str::to_owned),
345    }
346}
347
348/// An ambiguous node outside the declared conflicts.
349#[derive(Clone, Debug, PartialEq, Eq)]
350pub struct Ambiguity {
351    /// The rule (or alias) that built the node.
352    pub rule: String,
353    /// The first byte.
354    pub start: usize,
355    /// The byte after the last.
356    pub end: usize,
357}
358
359/// The ambiguous nodes of an executor tree, in preorder, outside the declared conflicts.
360pub(super) fn collect_ambiguities(
361    node: &Tree,
362    compiled: &Compiled,
363    program: usize,
364    found: &mut Vec<Ambiguity>,
365) {
366    match node.ty {
367        TreeType::Node => {
368            let conflicts = &compiled.programs[program].conflicts;
369            if node.ambiguous
370                && !node
371                    .rule
372                    .as_deref()
373                    .is_some_and(|rule| conflicts.contains(rule))
374            {
375                found.push(Ambiguity {
376                    rule: node
377                        .rule
378                        .as_deref()
379                        .or(node.kind.as_deref())
380                        .unwrap_or_default()
381                        .to_owned(),
382                    start: node.start,
383                    end: node.end,
384                });
385            }
386            for child in node.children.iter() {
387                collect_ambiguities(child, compiled, program, found);
388            }
389        }
390        TreeType::Embed => {
391            if let Some(root) = &node.root {
392                collect_ambiguities(root, compiled, node.program, found);
393            }
394        }
395        _ => {}
396    }
397}
meta_language/grammar/feature_runtime/tree.rs

meta_language/grammar/feature_runtime/
tree.rs
