Skip to main content

wright/parser/
cst.rs

1//! The concrete syntax tree (CST) and the parser that produces it.
2//!
3//! The parser itself is generated at build time by [lelwel] from the grammar in `src/parser/wright.llw` and
4//! included here. This module implements the [ParserCallbacks] trait that the generated code relies on for:
5//! - Tokenization (delegated to [crate::lexer], see `lexer.rs` in this module).
6//! - Creating [Diagnostic]s for syntax errors.
7//! - The semantic predicates (`?N`) and actions (`#N`) referenced by the grammar.
8//!
9//! The CST is lossless -- every token from the source (including whitespace and comments) is in it. It's mostly
10//! useful as an intermediate step to the [AST](crate::ast), but is also exposed via [SyntaxTree] for tooling such as
11//! formatters that need every token.
12//!
13//! [lelwel]: https://crates.io/crates/lelwel
14
15// The generated code doesn't document or derive everything this crate usually requires.
16#![allow(
17    missing_docs,
18    missing_debug_implementations,
19    missing_copy_implementations,
20    clippy::all,
21    unused_qualifications
22)]
23
24use crate::lexer::token::TokenTy as Token;
25use crate::source_tracking::{SourceRef, fragment::Fragment};
26use crate::terminal_interface::reporting::{Diagnostic, Highlight};
27use std::fmt;
28
29include!(concat!(env!("OUT_DIR"), "/generated.rs"));
30
31/// Context carried through a parse and used by the semantic predicates and actions.
32#[derive(Debug)]
33pub struct ParseContext {
34    /// The source being parsed. Used to create [Fragment]s for [Diagnostic]s.
35    source: SourceRef,
36
37    /// The number of tokens that have been split in two (see [Parser::split_leading_gt]).
38    split_count: usize,
39
40    /// A stack tracking whether record literals (`Name { field: value }`) are allowed in the current expression
41    /// context. They are not allowed directly in the header of an `if`, `while`, or `for` (since `if x { ... }` would
42    /// be ambiguous), but nesting the expression in parentheses, brackets, or a block allows them again.
43    record_literals_allowed: Vec<bool>,
44}
45
46impl ParseContext {
47    /// Create a new [ParseContext] for parsing the given source.
48    fn new(source: SourceRef) -> Self {
49        ParseContext {
50            source,
51            split_count: 0,
52            record_literals_allowed: Vec::new(),
53        }
54    }
55
56    /// Are record literals allowed in the current context?
57    fn record_literals_allowed(&self) -> bool {
58        self.record_literals_allowed.last().copied().unwrap_or(true)
59    }
60}
61
62/// Describe a token for use in a diagnostic message.
63fn describe_token(token: Token, text: &str) -> String {
64    match token {
65        Token::EOF | Token::EOFExpr | Token::EOFTy => "end of input".to_owned(),
66        Token::Identifier => format!("identifier `{text}`"),
67        Token::IntegerLiteral => format!("integer literal `{text}`"),
68        Token::FloatLiteral => format!("float literal `{text}`"),
69        Token::StringLiteral | Token::FormatStringLiteral => "string literal".to_owned(),
70        Token::CharLiteral => format!("character literal {text}"),
71        _ if text.starts_with(|c: char| c.is_ascii_alphabetic()) => format!("keyword `{text}`"),
72        _ => format!("`{text}`"),
73    }
74}
75
76/// Groups of tokens that commonly appear together in the "expected" lists of syntax errors, which are collapsed
77/// into a single description when every token in the group is expected. Order matters -- earlier groups are
78/// collapsed first.
79const EXPECTED_GROUPS: &[(&str, &[&str])] = &[
80    (
81        "a statement",
82        &[
83            "'let'",
84            "'var'",
85            "'return'",
86            "'break'",
87            "'continue'",
88            "'@'",
89            "'!'",
90            "<character literal>",
91            "<float literal>",
92            "<format string literal>",
93            "<identifier>",
94            "<integer literal>",
95            "'false'",
96            "'for'",
97            "'if'",
98            "'loop'",
99            "'true'",
100            "'while'",
101            "'['",
102            "'{'",
103            "'('",
104            "'-'",
105            "'*'",
106            "<string literal>",
107            "'~'",
108        ],
109    ),
110    (
111        "an expression",
112        &[
113            "'@'",
114            "'!'",
115            "<character literal>",
116            "<float literal>",
117            "<format string literal>",
118            "<identifier>",
119            "<integer literal>",
120            "'false'",
121            "'for'",
122            "'if'",
123            "'loop'",
124            "'true'",
125            "'while'",
126            "'['",
127            "'{'",
128            "'('",
129            "'-'",
130            "'*'",
131            "<string literal>",
132            "'~'",
133        ],
134    ),
135    (
136        "a type",
137        &[
138            "'@'",
139            "<identifier>",
140            "'['",
141            "'func'",
142            "'bool'",
143            "'char'",
144            "'u8'",
145            "'i8'",
146            "'u16'",
147            "'i16'",
148            "'u32'",
149            "'i32'",
150            "'u64'",
151            "'i64'",
152            "'f32'",
153            "'f64'",
154        ],
155    ),
156    (
157        "an item",
158        &[
159            "'const'", "'enum'", "'func'", "'impl'", "'mod'", "'naked'", "'pub'", "'pure'",
160            "'record'", "'type'", "'union'", "'unsafe'", "'use'",
161        ],
162    ),
163    (
164        "an operator",
165        &[
166            "'*'", "'/'", "'%'", "'+'", "'-'", "'<<'", "'>>'", "'&'", "'^'", "'|'", "'=='", "'!='",
167            "'<'", "'<='", "'>'", "'>='", "'&&'", "'||'", "'..'", "'..='", "'as'",
168        ],
169    ),
170    (
171        "an assignment",
172        &[
173            "'='", "'+='", "'-='", "'*='", "'/='", "'%='", "'^='", "'&='", "'|='", "'<<='", "'>>='",
174        ],
175    ),
176];
177
178/// Turn the message generated by lelwel for a syntax error (such as `invalid syntax, expected one of: 'a', 'b'`)
179/// into a description of what was expected (such as `` `a` or `b` ``). Large groups of related tokens are collapsed
180/// into descriptions like "an expression".
181fn describe_expected(message: &str) -> String {
182    let list = message.strip_prefix("invalid syntax, ").unwrap_or(message);
183    let list = list
184        .strip_prefix("expected one of: ")
185        .or_else(|| list.strip_prefix("expected: "))
186        .unwrap_or(list);
187
188    let all_items: Vec<&str> = list.split(", ").collect();
189    let mut items: Vec<&str> = all_items.clone();
190    let mut descriptions: Vec<String> = Vec::new();
191
192    // Groups overlap (`-` is both an expression start and an operator), so check each group against the original
193    // list rather than what's left after collapsing earlier groups. Skip groups that an earlier group entirely
194    // covered though (every expression start is also a statement start).
195    for (description, group) in EXPECTED_GROUPS {
196        if group.iter().all(|item| all_items.contains(item))
197            && group.iter().any(|item| items.contains(item))
198        {
199            items.retain(|item| !group.contains(item));
200            descriptions.push((*description).to_owned());
201        }
202    }
203
204    descriptions.extend(items.into_iter().map(|item| {
205        match item {
206            "<end of file>" => "end of input".to_owned(),
207            // Quoted token symbols like `'('` become `` `(` ``.
208            quoted if quoted.len() > 2 && quoted.starts_with('\'') && quoted.ends_with('\'') => {
209                format!("`{}`", &quoted[1..quoted.len() - 1])
210            }
211            // Token classes like `<identifier>` become `identifier`.
212            class => class
213                .trim_start_matches('<')
214                .trim_end_matches('>')
215                .to_owned(),
216        }
217    }));
218
219    match descriptions.as_slice() {
220        [] => "something else".to_owned(),
221        [one] => one.clone(),
222        [first, second] => format!("{first} or {second}"),
223        [init @ .., last] => format!("{}, or {last}", init.join(", ")),
224    }
225}
226
227impl<'a> Parser<'a> {
228    /// Split the current token if it's a `>>`, `>=`, or `>>=` (in that order of preference), leaving a `>` as the
229    /// current token followed by the rest of the original token.
230    fn split_leading_gt(&mut self) {
231        let rest = match self.current {
232            Token::GtGt => Token::Gt,
233            Token::GtEq => Token::Eq,
234            Token::GtGtEq => Token::GtEq,
235            _ => return,
236        };
237
238        let span = self.cst.data.spans[self.pos].clone();
239        let split = span.start + 1;
240
241        self.tokens[self.pos] = Token::Gt;
242        self.tokens.insert(self.pos + 1, rest);
243        self.cst.data.spans[self.pos] = span.start..split;
244        self.cst.data.spans.insert(self.pos + 1, split..span.end);
245        self.current = Token::Gt;
246        self.context.split_count += 1;
247    }
248
249    /// Run at the end of an entry point rule, before the generated code checks that all tokens were consumed.
250    ///
251    /// The generated code compares the final position to the number of tokens from *before* parsing, which doesn't
252    /// account for tokens inserted by [Parser::split_leading_gt]. To keep that check accurate, consume any remaining
253    /// tokens here (the same way the generated code would) and then offset the position by the number of splits.
254    fn finish_entry(&mut self, diags: &mut Vec<Diagnostic>) {
255        if self.context.split_count == 0 {
256            return;
257        }
258
259        if self.pos < self.tokens.len() {
260            self.close_error_node(diags);
261            self.error(diags, err![self, "invalid syntax, expected: <end of file>"]);
262            let error_tree = self.open(diags);
263
264            while self.pos < self.tokens.len() {
265                let token = self.tokens[self.pos];
266                self.cst.data.advance(token, Self::is_skipped(token));
267                self.pos += 1;
268            }
269
270            self.cst.data.close(error_tree, Rule::Error);
271        }
272
273        self.pos -= self.context.split_count;
274    }
275
276    /// Is the next non-skipped token after the current one a token that closes a generic list?
277    fn next_closes_generics(&self) -> bool {
278        matches!(self.peek(1), Token::Gt | Token::GtGt | Token::GtEq | Token::GtGtEq)
279    }
280
281    fn push_record_literals_allowed(&mut self, allowed: bool) {
282        self.context.record_literals_allowed.push(allowed);
283    }
284
285    fn pop_record_literals_allowed(&mut self) {
286        self.context.record_literals_allowed.pop();
287    }
288}
289
290impl<'a> ParserCallbacks<'a> for Parser<'a> {
291    type Diagnostic = Diagnostic;
292    type Context = ParseContext;
293
294    fn create_tokens(
295        context: &mut Self::Context,
296        _source: &'a str,
297        diags: &mut Vec<Self::Diagnostic>,
298    ) -> (Vec<Token>, Vec<Span>) {
299        super::lexer::tokenize(&context.source, diags)
300    }
301
302    fn create_diagnostic(&self, span: Span, message: String) -> Self::Diagnostic {
303        let fragment = Fragment {
304            source: self.context.source.clone(),
305            range: span.clone(),
306        };
307
308        let expected = describe_expected(&message);
309        let found = describe_token(self.current, &self.cst.source[span]);
310
311        Diagnostic::error()
312            .with_message(format!("syntax error: expected {expected}, found {found}"))
313            .with_highlights([Highlight::primary(fragment, format!("unexpected {found}"))])
314    }
315
316    fn predicate_param_list_1(&self) -> bool {
317        self.peek(1) != Token::RightParen
318    }
319
320    fn predicate_record_body_1(&self) -> bool {
321        self.peek(1) != Token::RightCurly
322    }
323
324    fn predicate_enum_body_1(&self) -> bool {
325        self.peek(1) != Token::RightCurly
326    }
327
328    fn predicate_generic_params_1(&self) -> bool {
329        !self.next_closes_generics()
330    }
331
332    fn predicate_named_ty_1(&self) -> bool {
333        true
334    }
335
336    fn predicate_generic_args_1(&self) -> bool {
337        !self.next_closes_generics()
338    }
339
340    fn predicate_func_ty_1(&self) -> bool {
341        self.peek(1) != Token::RightParen
342    }
343
344    fn predicate_path_expr_1(&self) -> bool {
345        self.context.record_literals_allowed()
346    }
347
348    fn predicate_record_lit_fields_1(&self) -> bool {
349        self.peek(1) != Token::RightCurly
350    }
351
352    fn predicate_arg_list_1(&self) -> bool {
353        self.peek(1) != Token::RightParen
354    }
355
356    fn predicate_array_expr_1(&self) -> bool {
357        self.peek(1) != Token::RightBracket
358    }
359
360    fn action_generic_close_1(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
361        self.split_leading_gt();
362    }
363
364    // Delimited contexts allow record literals again.
365
366    fn action_block_1(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
367        self.push_record_literals_allowed(true);
368    }
369
370    fn action_block_2(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
371        self.pop_record_literals_allowed();
372    }
373
374    fn action_record_lit_fields_1(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
375        self.push_record_literals_allowed(true);
376    }
377
378    fn action_record_lit_fields_2(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
379        self.pop_record_literals_allowed();
380    }
381
382    fn action_arg_list_1(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
383        self.push_record_literals_allowed(true);
384    }
385
386    fn action_arg_list_2(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
387        self.pop_record_literals_allowed();
388    }
389
390    fn action_index_inner_1(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
391        self.push_record_literals_allowed(true);
392    }
393
394    fn action_index_inner_2(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
395        self.pop_record_literals_allowed();
396    }
397
398    fn action_paren_expr_1(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
399        self.push_record_literals_allowed(true);
400    }
401
402    fn action_paren_expr_2(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
403        self.pop_record_literals_allowed();
404    }
405
406    fn action_array_expr_1(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
407        self.push_record_literals_allowed(true);
408    }
409
410    fn action_array_expr_2(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
411        self.pop_record_literals_allowed();
412    }
413
414    // Control flow headers disallow record literals.
415
416    fn action_if_expr_1(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
417        self.push_record_literals_allowed(false);
418    }
419
420    fn action_if_expr_2(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
421        self.pop_record_literals_allowed();
422    }
423
424    fn action_while_expr_1(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
425        self.push_record_literals_allowed(false);
426    }
427
428    fn action_while_expr_2(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
429        self.pop_record_literals_allowed();
430    }
431
432    fn action_for_expr_1(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
433        self.push_record_literals_allowed(false);
434    }
435
436    fn action_for_expr_2(&mut self, _diags: &mut Vec<Self::Diagnostic>) {
437        self.pop_record_literals_allowed();
438    }
439}
440
441/// Which grammar rule to start parsing from.
442#[derive(Clone, Copy, Debug, PartialEq, Eq)]
443pub(crate) enum EntryPoint {
444    /// A whole source file (the grammar's start rule).
445    SourceFile,
446    /// A single expression.
447    Expr,
448    /// A single type signature.
449    Ty,
450}
451
452/// Run the generated parser over a source, starting from the given [EntryPoint].
453pub(crate) fn parse(
454    source: &SourceRef,
455    entry: EntryPoint,
456    diags: &mut Vec<Diagnostic>,
457) -> SyntaxTree {
458    let text: &str = source.source().as_str();
459    let parser = Parser::new_with_context(text, diags, ParseContext::new(source.clone()));
460
461    let cst: Cst<'_> = match entry {
462        EntryPoint::SourceFile => parser.parse_rule(
463            |p, d| {
464                p.rule_source_file(d);
465                p.finish_entry(d);
466            },
467            diags,
468            Rule::SourceFile,
469        ),
470
471        // These mirror the generated `parse_expr` and `parse_ty` functions for `part` rules, with the extra call to
472        // `finish_entry`.
473        EntryPoint::Expr => {
474            let mut parser = parser;
475            parser.end_of_input = Token::EOFExpr;
476
477            parser.parse_rule(
478                |p, d| {
479                    p.rule_expr(d);
480                    p.finish_entry(d);
481                },
482                diags,
483                Rule::Part,
484            )
485        }
486
487        EntryPoint::Ty => {
488            let mut parser = parser;
489            parser.end_of_input = Token::EOFTy;
490
491            parser.parse_rule(
492                |p, d| {
493                    p.rule_ty(d);
494                    p.finish_entry(d);
495                },
496                diags,
497                Rule::Part,
498            )
499        }
500    };
501
502    SyntaxTree {
503        source: source.clone(),
504        data: cst.into_data(),
505    }
506}
507
508/// A lossless concrete syntax tree for a [Source](crate::source_tracking::source::Source), as produced by the
509/// generated parser.
510///
511/// Nodes are referenced using [NodeRef]s, and are either [Node::Rule]s (with children) or [Node::Token]s (leaves).
512/// [SyntaxTree::ROOT] is always a [Node::Rule].
513#[derive(Debug)]
514pub struct SyntaxTree {
515    source: SourceRef,
516    data: CstData,
517}
518
519impl SyntaxTree {
520    /// The root node of every [SyntaxTree].
521    pub const ROOT: NodeRef = NodeRef::ROOT;
522
523    /// The source this tree was parsed from.
524    pub fn source(&self) -> &SourceRef {
525        &self.source
526    }
527
528    /// Get the [Node] referenced by the given [NodeRef].
529    pub fn get(&self, node: NodeRef) -> Node {
530        self.data.get(node)
531    }
532
533    /// Get the [Rule] of a node if it's a rule node.
534    pub fn rule(&self, node: NodeRef) -> Option<Rule> {
535        match self.data.get(node) {
536            Node::Rule(rule, _) => Some(rule),
537            Node::Token(..) => None,
538        }
539    }
540
541    /// Get the [Token] type of a node if it's a token node.
542    pub fn token(&self, node: NodeRef) -> Option<Token> {
543        match self.data.get(node) {
544            Node::Token(token, _) => Some(token),
545            Node::Rule(..) => None,
546        }
547    }
548
549    /// Get an iterator over the direct children of a node. Token nodes have no children.
550    pub fn children(&self, node: NodeRef) -> CstChildren<'_> {
551        self.data.children(node)
552    }
553
554    /// Get the byte range in the source covered by a node.
555    ///
556    /// For rule nodes, this is from the start of their first token to the end of their last. Rule nodes without any
557    /// tokens (possible when the parser recovers from errors) have an empty range where they would be.
558    pub fn span(&self, node: NodeRef) -> std::ops::Range<usize> {
559        self.data.span(node)
560    }
561
562    /// Get a [Fragment] of the source covered by a node (see [SyntaxTree::span]).
563    pub fn fragment(&self, node: NodeRef) -> Fragment {
564        Fragment {
565            source: self.source.clone(),
566            range: self.span(node),
567        }
568    }
569
570    /// Get the source text covered by a node (see [SyntaxTree::span]).
571    pub fn text(&self, node: NodeRef) -> &str {
572        &self.source.source().as_str()[self.span(node)]
573    }
574}
575
576impl fmt::Display for SyntaxTree {
577    /// Print the tree with one node per line, indented by depth. Each line has the rule or token kind and the byte
578    /// range it covers, and tokens also include their source text.
579    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
580        // Use an explicit stack rather than recursion, since syntax trees can be very deep.
581        let mut stack: Vec<(NodeRef, usize)> = vec![(Self::ROOT, 0)];
582
583        while let Some((node, depth)) = stack.pop() {
584            let indent = "    ".repeat(depth);
585            let span = self.span(node);
586
587            match self.get(node) {
588                Node::Rule(rule, _) => {
589                    writeln!(f, "{indent}{rule:?} [{span:?}]")?;
590                    let children: Vec<NodeRef> = self.children(node).collect();
591                    stack.extend(children.into_iter().rev().map(|child| (child, depth + 1)));
592                }
593
594                Node::Token(token, _) => {
595                    writeln!(f, "{indent}{token:?} {:?} [{span:?}]", self.text(node))?;
596                }
597            }
598        }
599
600        Ok(())
601    }
602}
603
604#[cfg(test)]
605mod tests {
606    use super::describe_expected;
607
608    #[test]
609    fn expected_single_token() {
610        assert_eq!(describe_expected("invalid syntax, expected: ';'"), "`;`");
611        assert_eq!(describe_expected("invalid syntax, expected: <identifier>"), "identifier");
612        assert_eq!(describe_expected("invalid syntax, expected: <end of file>"), "end of input");
613    }
614
615    #[test]
616    fn expected_lists() {
617        assert_eq!(describe_expected("invalid syntax, expected one of: ',', '}'"), "`,` or `}`");
618        assert_eq!(
619            describe_expected("invalid syntax, expected one of: ',', '}', <identifier>"),
620            "`,`, `}`, or identifier"
621        );
622    }
623
624    #[test]
625    fn expected_groups_collapse() {
626        let expression_starts = "'@', '!', <character literal>, <float literal>, <format string literal>, \
627            <identifier>, <integer literal>, 'false', 'for', 'if', 'loop', 'true', 'while', '[', '{', '(', '-', '*', \
628            <string literal>, '~'";
629
630        assert_eq!(
631            describe_expected(&format!("invalid syntax, expected one of: {expression_starts}")),
632            "an expression"
633        );
634
635        assert_eq!(
636            describe_expected(&format!(
637                "invalid syntax, expected one of: {expression_starts}, ';'"
638            )),
639            "an expression or `;`"
640        );
641
642        // Statements include all the expression starts, so only "a statement" should be listed.
643        assert_eq!(
644            describe_expected(&format!(
645                "invalid syntax, expected one of: 'let', 'var', 'return', 'break', 'continue', {expression_starts}"
646            )),
647            "a statement"
648        );
649    }
650}