Skip to main content

wright/parser/
mod.rs

1//! Wright's parser, which turns source code into an [abstract syntax tree](crate::ast).
2//!
3//! Parsing happens in three stages:
4//! 1. The [lexer](crate::lexer) splits the source into tokens (see `lexer.rs` in this module).
5//! 2. A resilient LL(1) parser generated by [lelwel] from the grammar in `src/parser/wright.llw` builds a lossless
6//!    [concrete syntax tree](cst::SyntaxTree) from the tokens.
7//! 3. The concrete syntax tree is lowered into the [AST](crate::ast) (see `lower.rs`).
8//!
9//! Parsing never fails outright. Syntax errors are reported as [Diagnostic]s, and the parser recovers and keeps going,
10//! so a single parse reports as many problems as possible and still produces an AST for the parts of the source that
11//! make sense. See [crate::ast] for how errors show up in the AST.
12//!
13//! ```
14//! # use std::sync::Arc;
15//! # use wright::source_tracking::{filename::FileName, source::Source};
16//! use wright::parser::parse_source_file;
17//!
18//! let source = Arc::new(Source::new_from_static_str(FileName::None, "func main() { println(\"hi\"); }"));
19//! let parsed = parse_source_file(source);
20//!
21//! assert!(!parsed.has_errors());
22//! assert_eq!(parsed.ast.items.len(), 1);
23//! ```
24//!
25//! [lelwel]: https://crates.io/crates/lelwel
26
27use crate::ast::{SourceFile, expr::Expr, ty::Type};
28use crate::source_tracking::SourceRef;
29use crate::terminal_interface::reporting::{Diagnostic, Severity};
30use cst::{EntryPoint, SyntaxTree};
31use lower::Lowerer;
32
33pub mod cst;
34mod lexer;
35mod lower;
36
37/// The maximum nesting depth the parser supports.
38///
39/// The parser (and lowering, and many passes over the AST) are recursive, so this limit keeps deeply nested source
40/// code from overflowing the stack. Nesting includes delimiters (`(`, `[`, `{`), `else if` chains, and chains of
41/// operators in a single expression (since `a + b + c` is nested as `(a + b) + c`). Source code nested more deeply
42/// than this produces an error.
43pub const MAX_NESTING_DEPTH: usize = 256;
44
45/// The size of the stack for the thread that parsing runs on.
46///
47/// Parsing runs on its own thread so that it has plenty of stack space for deeply nested code, regardless of the stack
48/// size of the calling thread. The memory is only reserved, not committed, so a large size is cheap.
49const PARSER_STACK_SIZE: usize = if cfg!(target_pointer_width = "64") {
50    256 * 1024 * 1024
51} else {
52    32 * 1024 * 1024
53};
54
55/// Sources at most this many bytes long are parsed on the calling thread instead of a new thread (see
56/// [PARSER_STACK_SIZE]). Every level of nesting takes at least one byte, so short sources can't nest deeply enough to
57/// need a large stack, and spawning a thread would dominate the time it takes to parse them.
58const INLINE_PARSE_MAX_BYTES: usize = 64;
59
60/// The result of parsing some source code: an AST, the syntax tree it was lowered from, and any diagnostics.
61#[derive(Debug)]
62pub struct Parsed<T> {
63    /// The abstract syntax tree. If there were errors, parts of it may be [error nodes](crate::ast).
64    pub ast: T,
65
66    /// The lossless concrete syntax tree that the AST was lowered from.
67    pub syntax_tree: SyntaxTree,
68
69    /// All the diagnostics (errors and warnings) produced while parsing, sorted by where they occur in the source.
70    pub diagnostics: Vec<Diagnostic>,
71}
72
73impl<T> Parsed<T> {
74    /// Were any errors (as opposed to warnings) reported while parsing?
75    pub fn has_errors(&self) -> bool {
76        self.diagnostics
77            .iter()
78            .any(|diagnostic| matches!(diagnostic.0.severity, Severity::Error | Severity::Bug))
79    }
80
81    /// Get the AST if no errors were reported, or the diagnostics otherwise. Warnings are discarded.
82    pub fn into_result(self) -> Result<T, Vec<Diagnostic>> {
83        if self.has_errors() {
84            Err(self.diagnostics)
85        } else {
86            Ok(self.ast)
87        }
88    }
89}
90
91/// Run the parser on a source from the given entry point, then lower the result with the given function.
92///
93/// This runs on a separate thread with a large stack (see [PARSER_STACK_SIZE]) if possible.
94fn parse_with<T: Send>(
95    source: SourceRef,
96    entry: EntryPoint,
97    lower: fn(&mut Lowerer<'_>) -> T,
98) -> Parsed<T> {
99    let job = || parse_on_current_thread(source.clone(), entry, lower);
100
101    if source.source().len() <= INLINE_PARSE_MAX_BYTES {
102        return job();
103    }
104
105    std::thread::scope(|scope| {
106        let spawned = std::thread::Builder::new()
107            .name("wright-parser".to_owned())
108            .stack_size(PARSER_STACK_SIZE)
109            .spawn_scoped(scope, job);
110
111        match spawned {
112            Ok(handle) => handle
113                .join()
114                .unwrap_or_else(|panic| std::panic::resume_unwind(panic)),
115
116            // Threads may not be available on some platforms -- fall back to the current thread.
117            Err(_) => job(),
118        }
119    })
120}
121
122/// Run the parser and lowering on the current thread. See [parse_with].
123fn parse_on_current_thread<T>(
124    source: SourceRef,
125    entry: EntryPoint,
126    lower: fn(&mut Lowerer<'_>) -> T,
127) -> Parsed<T> {
128    let mut diagnostics = Vec::new();
129    let syntax_tree = cst::parse(&source, entry, &mut diagnostics);
130    let ast = lower(&mut Lowerer::new(&syntax_tree, &mut diagnostics));
131
132    // Sort diagnostics by the location of their first label, so they read in source order. The sort is stable, so
133    // diagnostics at the same location keep the order they were produced in (lexer, parser, then lowering).
134    diagnostics.sort_by_key(|diagnostic| {
135        diagnostic
136            .0
137            .labels
138            .first()
139            .map_or(usize::MAX, |label| label.range.start)
140    });
141
142    Parsed {
143        ast,
144        syntax_tree,
145        diagnostics,
146    }
147}
148
149/// Parse an entire source file.
150pub fn parse_source_file(source: SourceRef) -> Parsed<SourceFile> {
151    parse_with(source, EntryPoint::SourceFile, |lowerer| lowerer.lower_source_file())
152}
153
154/// Parse a source containing a single expression (such as input to a REPL).
155pub fn parse_expr(source: SourceRef) -> Parsed<Expr> {
156    parse_with(source, EntryPoint::Expr, |lowerer| lowerer.lower_entry_expr())
157}
158
159/// Parse a source containing a single type signature.
160pub fn parse_type(source: SourceRef) -> Parsed<Type> {
161    parse_with(source, EntryPoint::Ty, |lowerer| lowerer.lower_entry_ty())
162}