wolf_parser/
lib.rs

1//! The wolfpack parser: tokens to a syntax tree (spec chapters 2 and 3).
2//!
3//! Recursive descent for declarations and statements, a Pratt parser for expressions. The parser
4//! checks the file skeleton (chapter 2) while it reads the sections. It never stops at an error:
5//! it reports the problem, skips to a safe point (the end of the line or a closing delimiter) and
6//! continues, so that all errors of a file are shown at once. It never panics, and a nesting limit
7//! (E0314) keeps deep input from overflowing the stack.
8
9mod expr;
10mod items;
11mod skeleton;
12mod ty;
13
14use wolf_ast::{File, NodeId};
15use wolf_diag::{Diagnostic, codes};
16use wolf_lexer::{Token, TokenKind};
17use wolf_span::{FileId, Span};
18
19/// The deepest nesting of expressions, statements, types and patterns the parser accepts.
20pub const MAX_DEPTH: u32 = 256;
21
22/// The stack size needed to parse, print and drop a tree nested up to [`MAX_DEPTH`] in a debug
23/// build, with a wide margin. The `wolf` binary runs the compiler on a thread of this size;
24/// other users of the parser should do the same.
25pub const STACK_SIZE: usize = 64 * 1024 * 1024;
26
27/// The result of parsing one file.
28#[derive(Debug)]
29pub struct Parsed {
30    /// The syntax tree, possibly with error nodes.
31    pub file: File,
32    /// Syntax errors, in the order they were found.
33    pub diagnostics: Vec<Diagnostic>,
34}
35
36/// Parses the tokens of one file, as produced by `wolf_lexer::lex`.
37pub fn parse(file: FileId, text: &str, tokens: &[Token]) -> Parsed {
38    let mut parser = Parser::new(file, text, tokens);
39    let tree = parser.file();
40    let too_deep = parser.depth_reported;
41    let mut diagnostics = parser.diagnostics;
42    if !too_deep {
43        diagnostics.extend(skeleton::check(file, &tree));
44    }
45    Parsed {
46        file: tree,
47        diagnostics,
48    }
49}
50
51/// Whether newlines are significant in the current delimiter (spec chapter 1, section 7).
52#[derive(Clone, Copy, PartialEq, Eq)]
53enum Lines {
54    /// Inside a block, a `match`, a declaration or at the top level: a newline ends things.
55    Significant,
56    /// Inside `( )`, `[ ]` or the braces of a literal or pattern: newlines are ignored.
57    Ignored,
58}
59
60pub(crate) struct Parser<'a> {
61    file: FileId,
62    text: &'a str,
63    /// The tokens; the parser may split `>>` into two `>` tokens in type context.
64    tokens: Vec<Token>,
65    pos: usize,
66    lines: Vec<Lines>,
67    pub(crate) diagnostics: Vec<Diagnostic>,
68    next_id: u32,
69    depth: u32,
70    depth_reported: bool,
71    /// Set when a section header was found inside a block: every open block closes at once.
72    pub(crate) resync_to_top: bool,
73    /// Set when an `Error` token from the lexer was consumed. The rest of the line is skipped
74    /// without further messages, because the lexer already reported the problem.
75    poisoned: bool,
76    /// Error count at the start of the current section entry.
77    pub(crate) line_errors: usize,
78}
79
80impl<'a> Parser<'a> {
81    fn new(file: FileId, text: &'a str, tokens: &[Token]) -> Parser<'a> {
82        let mut tokens = tokens.to_vec();
83        let ends_with_eof = tokens.last().is_some_and(|t| t.kind == TokenKind::Eof);
84        if !ends_with_eof {
85            let end = u32::try_from(text.len()).unwrap_or(u32::MAX);
86            tokens.push(Token {
87                kind: TokenKind::Eof,
88                span: Span::new(file, end, end),
89            });
90        }
91        Parser {
92            file,
93            text,
94            tokens,
95            pos: 0,
96            lines: vec![Lines::Significant],
97            diagnostics: Vec::new(),
98            next_id: 0,
99            depth: 0,
100            depth_reported: false,
101            resync_to_top: false,
102            poisoned: false,
103            line_errors: 0,
104        }
105    }
106
107    // ----- token access ----------------------------------------------------------------------
108
109    /// The token `n` positions ahead of `pos`, without skipping anything. Clamped to `Eof`.
110    fn raw(&self, n: usize) -> &Token {
111        let index = (self.pos + n).min(self.tokens.len().saturating_sub(1));
112        // `tokens` always ends with Eof, so it is never empty.
113        match self.tokens.get(index) {
114            Some(token) => token,
115            None => &EOF_TOKEN,
116        }
117    }
118
119    fn ignoring_lines(&self) -> bool {
120        self.lines.last() == Some(&Lines::Ignored)
121    }
122
123    /// Index of the `n`-th next token that is visible in the current newline mode.
124    fn visible_index(&self, n: usize) -> usize {
125        let mut index = self.pos;
126        let mut seen = 0;
127        loop {
128            let token = self.tokens.get(index);
129            let skip = self.ignoring_lines() && token.is_some_and(|t| t.kind == TokenKind::Newline);
130            if !skip {
131                if seen == n || token.is_none_or(|t| t.kind == TokenKind::Eof) {
132                    return index.min(self.tokens.len().saturating_sub(1));
133                }
134                seen += 1;
135            }
136            index += 1;
137        }
138    }
139
140    /// The `n`-th next visible token.
141    pub(crate) fn nth(&self, n: usize) -> &Token {
142        match self.tokens.get(self.visible_index(n)) {
143            Some(token) => token,
144            None => &EOF_TOKEN,
145        }
146    }
147
148    pub(crate) fn peek(&self) -> &TokenKind {
149        &self.nth(0).kind
150    }
151
152    pub(crate) fn peek_span(&self) -> Span {
153        self.nth(0).span
154    }
155
156    /// Whether the next visible token has the same kind as `kind` (literal values are ignored).
157    pub(crate) fn at(&self, kind: &TokenKind) -> bool {
158        same_kind(self.peek(), kind)
159    }
160
161    pub(crate) fn nth_is(&self, n: usize, kind: &TokenKind) -> bool {
162        same_kind(&self.nth(n).kind, kind)
163    }
164
165    /// Whether the next visible token is the identifier `word` (a contextual keyword).
166    pub(crate) fn at_word(&self, word: &str) -> bool {
167        self.nth_word(0, word)
168    }
169
170    pub(crate) fn nth_word(&self, n: usize, word: &str) -> bool {
171        let token = self.nth(n);
172        token.kind == TokenKind::Ident && self.source(token.span) == word
173    }
174
175    /// Consumes the next visible token and returns it.
176    pub(crate) fn bump(&mut self) -> Token {
177        let index = self.visible_index(0);
178        let token = self.tokens.get(index).cloned().unwrap_or(EOF_TOKEN.clone());
179        if token.kind == TokenKind::Error {
180            self.poisoned = true;
181        }
182        if token.kind != TokenKind::Eof {
183            self.pos = index + 1;
184        } else {
185            self.pos = index;
186        }
187        token
188    }
189
190    pub(crate) fn eat(&mut self, kind: &TokenKind) -> bool {
191        if self.at(kind) {
192            self.bump();
193            true
194        } else {
195            false
196        }
197    }
198
199    /// Consumes `kind` and then any newlines: after `.`, `:`, `->`, `=` and binary operators a
200    /// line break does not end anything (spec chapter 1, section 7, rule 2).
201    pub(crate) fn eat_then_lines(&mut self, kind: &TokenKind) -> bool {
202        if self.eat(kind) {
203            self.skip_newlines();
204            true
205        } else {
206            false
207        }
208    }
209
210    /// Like [`Parser::expect`], then skips newlines.
211    pub(crate) fn expect_then_lines(&mut self, kind: &TokenKind, what: &str) -> Option<Span> {
212        let span = self.expect(kind, what)?;
213        self.skip_newlines();
214        Some(span)
215    }
216
217    pub(crate) fn eat_word(&mut self, word: &str) -> bool {
218        if self.at_word(word) {
219            self.bump();
220            true
221        } else {
222            false
223        }
224    }
225
226    /// Consumes `kind` or reports E0301. Returns the span of the token when it was there.
227    pub(crate) fn expect(&mut self, kind: &TokenKind, what: &str) -> Option<Span> {
228        if self.at(kind) {
229            return Some(self.bump().span);
230        }
231        self.unexpected(what);
232        None
233    }
234
235    /// Skips newline tokens, even where they are significant.
236    pub(crate) fn skip_newlines(&mut self) {
237        while self.raw(0).kind == TokenKind::Newline {
238            self.pos += 1;
239        }
240    }
241
242    /// Whether the next raw token ends the current line (or the file).
243    pub(crate) fn at_line_end(&self) -> bool {
244        matches!(self.raw(0).kind, TokenKind::Newline | TokenKind::Eof)
245    }
246
247    pub(crate) fn source(&self, span: Span) -> &'a str {
248        self.text.get(span.range()).unwrap_or("")
249    }
250
251    pub(crate) fn prev_span(&self) -> Span {
252        let index = self.pos.saturating_sub(1);
253        self.tokens
254            .get(index)
255            .map(|t| t.span)
256            .unwrap_or(Span::new(self.file, 0, 0))
257    }
258
259    pub(crate) fn span_from(&self, start: Span) -> Span {
260        let end = self.prev_span();
261        if end.end < start.start {
262            start
263        } else {
264            start.to(end)
265        }
266    }
267
268    pub(crate) fn with_lines<T>(&mut self, mode: Lines, f: impl FnOnce(&mut Self) -> T) -> T {
269        self.lines.push(mode);
270        let result = f(self);
271        self.lines.pop();
272        result
273    }
274
275    pub(crate) fn ignore_lines<T>(&mut self, f: impl FnOnce(&mut Self) -> T) -> T {
276        self.with_lines(Lines::Ignored, f)
277    }
278
279    pub(crate) fn significant_lines<T>(&mut self, f: impl FnOnce(&mut Self) -> T) -> T {
280        self.with_lines(Lines::Significant, f)
281    }
282
283    pub(crate) fn id(&mut self) -> NodeId {
284        let id = NodeId(self.next_id);
285        self.next_id += 1;
286        id
287    }
288
289    // ----- errors -----------------------------------------------------------------------------
290
291    pub(crate) fn report(&mut self, diagnostic: Diagnostic) {
292        // After the nesting limit the parser skips to the end; anything else would be noise.
293        if self.depth_reported && diagnostic.code != codes::E0314 {
294            return;
295        }
296        self.diagnostics.push(diagnostic);
297    }
298
299    /// Reports E0301 at the next token, unless it is an `Error` token (already reported by the
300    /// lexer) or the nesting limit was hit.
301    pub(crate) fn unexpected(&mut self, expected: &str) {
302        let token = self.nth(0).clone();
303        if token.kind == TokenKind::Error || self.depth_reported || self.poisoned {
304            return;
305        }
306        let found = describe(&token, self.source(token.span));
307        // Point at the end of the line, not at the line break itself.
308        let span = if token.kind == TokenKind::Newline {
309            Span::new(token.span.file, token.span.start, token.span.start)
310        } else {
311            token.span
312        };
313        self.report(
314            Diagnostic::new(codes::E0301, format!("expected {expected}, found {found}"))
315                .primary(span, format!("expected {expected}")),
316        );
317    }
318
319    /// Ends the current line after a statement or entry. If the line contained a lexer error,
320    /// the rest of it is skipped silently and `true` is returned.
321    pub(crate) fn end_line_if_poisoned(&mut self) -> bool {
322        if !self.poisoned {
323            return false;
324        }
325        self.recover();
326        self.poisoned = false;
327        true
328    }
329
330    /// Clears the poisoned state at the start of a line and remembers how many errors there
331    /// were, so the end of the line can tell whether this line already reported one.
332    pub(crate) fn start_line(&mut self) -> usize {
333        self.poisoned = false;
334        self.diagnostics.len()
335    }
336
337    /// At the end of a statement or entry: if the line already has an error, or the next token
338    /// is a range (E0307), handle that and skip the rest of the line. Returns `true` if handled.
339    pub(crate) fn end_line_after_error(&mut self, errors_before: usize) -> bool {
340        // A section header was found inside a block: stay right there.
341        if self.resync_to_top {
342            return true;
343        }
344        if self.end_line_if_poisoned() {
345            return true;
346        }
347        if matches!(self.raw(0).kind, TokenKind::DotDot | TokenKind::DotDotEq) {
348            let span = self.raw(0).span;
349            self.report(
350                Diagnostic::new(codes::E0307, "range outside `for` or index brackets").primary(
351                    span,
352                    "ranges are allowed only in `for i in a..b` and `items[a..b]`",
353                ),
354            );
355            self.recover();
356            return true;
357        }
358        if self.diagnostics.len() > errors_before {
359            self.recover();
360            return true;
361        }
362        false
363    }
364
365    /// Skips to a safe point: the next newline outside nested delimiters, or before a closing
366    /// delimiter that belongs to an enclosing construct.
367    pub(crate) fn recover(&mut self) {
368        let mut depth = 0u32;
369        loop {
370            let kind = self.raw(0).kind.clone();
371            match kind {
372                TokenKind::Eof => return,
373                TokenKind::Newline if depth == 0 && !self.ignoring_lines() => return,
374                TokenKind::LParen | TokenKind::LBracket | TokenKind::LBrace => depth += 1,
375                TokenKind::RParen | TokenKind::RBracket | TokenKind::RBrace => {
376                    if depth == 0 {
377                        return;
378                    }
379                    depth -= 1;
380                }
381                _ => {}
382            }
383            self.pos += 1;
384        }
385    }
386
387    /// Enters one nesting level. Returns `false` (and reports E0314 once) past the limit.
388    pub(crate) fn enter(&mut self) -> bool {
389        self.depth += 1;
390        if self.depth <= MAX_DEPTH {
391            return true;
392        }
393        if !self.depth_reported {
394            self.depth_reported = true;
395            let span = self.peek_span();
396            self.report(
397                Diagnostic::new(codes::E0314, "nesting too deep")
398                    .primary(span, format!("more than {MAX_DEPTH} nested levels"))
399                    .help("split the expression or the code into smaller parts"),
400            );
401        }
402        false
403    }
404
405    pub(crate) fn leave(&mut self) {
406        self.depth = self.depth.saturating_sub(1);
407    }
408
409    /// Skips everything up to the end of the file. Used after the nesting limit was hit.
410    pub(crate) fn give_up(&mut self) {
411        self.pos = self.tokens.len().saturating_sub(1);
412    }
413
414    pub(crate) fn too_deep(&self) -> bool {
415        self.depth_reported
416    }
417}
418
419static EOF_TOKEN: Token = Token {
420    kind: TokenKind::Eof,
421    span: Span {
422        file: FILE_ZERO,
423        start: 0,
424        end: 0,
425    },
426};
427
428const FILE_ZERO: FileId = wolf_span::FileId::ZERO;
429
430/// Compares token kinds without looking at literal values.
431pub(crate) fn same_kind(a: &TokenKind, b: &TokenKind) -> bool {
432    std::mem::discriminant(a) == std::mem::discriminant(b)
433}
434
435/// "identifier `foo`", "`}`", "new line" for messages.
436pub(crate) fn describe(token: &Token, source: &str) -> String {
437    match token.kind {
438        TokenKind::Ident => format!("identifier `{source}`"),
439        TokenKind::Int(_) | TokenKind::Float(_) | TokenKind::Str(_) => format!("`{source}`"),
440        _ => token.kind.to_string(),
441    }
442}
wolf_parser/lib.rs

wolf_parser/
lib.rs
