use crate::ParseError;
use crate::block::check_callback_tails;
use crate::block::condition;
use crate::block::stmt;
use crate::datatype::data_decl;
use crate::datatype::derive_template;
use crate::datatype::errors_decl;
use crate::datatype::generalise;
use crate::expr::parse_expr;
use crate::expr::parse_spine;
use crate::item::const_decl;
use crate::item::declares_an_operator;
use crate::item::extern_block;
use crate::item::import_decl;
use crate::item::module_decl;
use crate::item::operator_decl;
use crate::item::pattern_synonym;
use crate::item::test_decl;
use crate::item::type_alias;
use crate::item::visibility;
use crate::pattern::pattern_alt;
use crate::pattern::patterns;
use crate::signature::SignatureHead;
use crate::signature::TypeStop;
use crate::signature::capture_type;
use crate::signature::clause;
use crate::signature::signature_from;
use crate::signature::signature_only;
use crate::support::MAX_NESTING;
use crate::support::nesting_depth;
use crate::token::inline_rust;
use crate::type_class::class_decl;
use crate::type_class::constraints;
use crate::type_class::given_clause;
use crate::type_class::instance_decl;
use crate::where_clause::where_predicates;
use voltaic_ast::Binding;
use voltaic_ast::Block;
use voltaic_ast::Expr;
use voltaic_ast::Fixity;
use voltaic_ast::FnDecl;
use voltaic_ast::Guard;
use voltaic_ast::Ident;
use voltaic_ast::Item;
use voltaic_ast::Program;
use voltaic_ast::Stmt;
use voltaic_ast::TypeExpr;
use voltaic_ast::Visibility;
use voltaic_diag::Code;
use voltaic_lexer::Keyword;
use voltaic_lexer::Span;
use voltaic_lexer::Token;
use voltaic_lexer::TokenKind;
use voltaic_lexer::Trivia;
pub fn parse(toks: &[Token], src_len: usize) -> Result<Program, Vec<ParseError>> {
let deepest = nesting_depth(toks);
if deepest > MAX_NESTING {
let message = format!(
"this input nests brackets {} deep, and the limit is {}: deeper than that overflows the parser's stack",
deepest, MAX_NESTING
);
return Err(vec![ParseError {
code: Code::NestingTooDeep,
message,
span: (0, 0),
help: None,
}]);
}
Parser::new(toks).run(src_len)
}
pub(crate) struct Parser<'a> {
toks: &'a [Token],
pos: usize,
pub(crate) r#errors: Vec<ParseError>,
class_heads: std::collections::BTreeMap<(String, String), SignatureHead>,
pub(crate) fixities: std::collections::BTreeMap<String, (Fixity, u8, String)>,
}
impl<'a> Parser<'a> {
pub(crate) fn new(toks: &'a [Token]) -> Self {
Parser {
toks,
pos: 0,
r#errors: Vec::new(),
class_heads: std::collections::BTreeMap::new(),
fixities: std::collections::BTreeMap::new(),
}
}
pub(crate) fn run(mut self, src_len: usize) -> Result<Program, Vec<ParseError>> {
let items = self.program();
if self.r#errors.is_empty() {
let probe = Program {
items: items.clone(),
span: (0, src_len),
trailing: Vec::new(),
};
self.r#errors.extend(check_callback_tails(&probe));
}
if self.r#errors.is_empty() {
let trailing = self.eof_trivia();
return Ok(Program {
items,
span: (0, src_len),
trailing,
});
}
Err(self.r#errors)
}
fn program(&mut self) -> Vec<Item> {
let mut items = Vec::new();
self.skip_separators();
while !self.at_eof() {
match self.item() {
Ok(found) => items.push(found),
Err(e) => {
self.r#errors.push(e);
self.recover_to_item()
}
};
self.skip_separators();
}
items
}
pub(crate) fn items_until_dedent(&mut self) -> Result<Vec<Item>, ParseError> {
let mut items = Vec::new();
loop {
self.skip_separators();
if self.check(&TokenKind::Dedent) || self.at_eof() {
break;
}
match self.item() {
Ok(found) => items.push(found),
Err(e) => {
self.r#errors.push(e);
self.recover_to_item()
}
};
}
self.expect(&TokenKind::Dedent, "expected the module body to end")?;
Ok(items)
}
pub(crate) fn item(&mut self) -> Result<Item, ParseError> {
let leading = self.peek_leading();
let start = self.peek_span().0;
let marker = visibility(self)?;
if self.check(&TokenKind::Kw(Keyword::Data))
|| self.check(&TokenKind::Kw(Keyword::Newtype))
|| self.check(&TokenKind::Kw(Keyword::Union))
{
let decl = data_decl(self, leading, start, marker)?;
self.newline_with_trailing("expected a line break after the declaration")?;
return Ok(Item::Data(decl));
}
if self.check(&TokenKind::Kw(Keyword::Type)) {
let alias = type_alias(self, leading, start, marker)?;
self.newline_with_trailing("expected a line break after the alias")?;
return Ok(Item::Type(alias));
}
if self.check(&TokenKind::Kw(Keyword::Const)) || self.check(&TokenKind::Kw(Keyword::Static)) {
let decl = const_decl(self, leading, start, marker)?;
self.newline_with_trailing("expected a line break after the binding")?;
return Ok(Item::Const(decl));
}
if self.check(&TokenKind::Kw(Keyword::Import)) {
let decl = import_decl(self, leading, start, marker)?;
self.newline_with_trailing("expected a line break after the import")?;
return Ok(Item::Import(decl));
}
if self.check(&TokenKind::Kw(Keyword::Module)) {
let decl = module_decl(self, leading, start, marker)?;
self.newline_with_trailing("expected a line break after the module")?;
return Ok(Item::Module(decl));
}
if self.check(&TokenKind::Kw(Keyword::Test)) {
let decl = test_decl(self, leading, start)?;
self.newline_with_trailing("expected a line break after the test")?;
return Ok(Item::Test(decl));
}
if self.check(&TokenKind::Kw(Keyword::Rust)) {
let block = inline_rust(self, leading, start)?;
self.newline_with_trailing("expected a line break after the inline Rust")?;
return Ok(Item::InlineRust(block));
}
let word_is_pattern = match &self.peek().kind {
TokenKind::Ident(text) => text == "pattern",
_ => false,
};
let names_a_constructor = self.peek_at(1).is_some_and(|t| match &t.kind {
TokenKind::Ident(next) => next.chars().next().is_some_and(char::is_uppercase),
_ => false,
});
if word_is_pattern && names_a_constructor {
let decl = pattern_synonym(self, leading, start)?;
return Ok(Item::PatternSynonym(decl));
}
if declares_an_operator(self) {
let decl = operator_decl(self, leading, start)?;
return Ok(Item::OperatorDecl(decl));
}
if self.check(&TokenKind::Kw(Keyword::Deriving)) {
let decl = derive_template(self, leading, start)?;
self.newline_with_trailing("expected a line break after the deriving template")?;
return Ok(Item::DeriveTemplate(decl));
}
if self.check(&TokenKind::Kw(Keyword::Extern)) {
let block = extern_block(self, leading, start)?;
return Ok(Item::Extern(block));
}
if self.check(&TokenKind::Kw(Keyword::Errors)) {
let decl = errors_decl(self, leading, start, marker)?;
self.newline_with_trailing("expected a line break after the declaration")?;
return Ok(Item::Errors(decl));
}
if self.check(&TokenKind::Kw(Keyword::Class)) {
let decl = class_decl(self, leading, start, marker)?;
self.newline_with_trailing("expected a line break after the class")?;
return Ok(Item::Class(decl));
}
if self.check(&TokenKind::Kw(Keyword::Instance)) {
let decl = instance_decl(self, leading, start)?;
self.newline_with_trailing("expected a line break after the instance")?;
return Ok(Item::Instance(decl));
}
let mut decl = self.function(&[])?;
decl.leading = leading;
decl.visibility = marker;
decl.span = (start, decl.span.1);
Ok(Item::Fn(decl))
}
pub(crate) fn function(&mut self, reserved: &[String]) -> Result<FnDecl, ParseError> {
let leading = self.peek_leading();
let start = self.peek_span().0;
let name = self.ident("expected a name to begin a declaration")?;
let head = self.signature_head(&name)?;
self.equations(name, leading, start, &head, reserved, false)
}
pub(crate) fn where_function(&mut self) -> Result<FnDecl, ParseError> {
let leading = self.peek_leading();
let start = self.peek_span().0;
let name = self.ident("expected a name to begin a declaration")?;
let head = self.signature_head(&name)?;
self.equations(name, leading, start, &head, &[], true)
}
pub(crate) fn signature_head(&mut self, name: &Ident) -> Result<SignatureHead, ParseError> {
let binds_on_this_line = self.check(&TokenKind::Eq)
&& self
.peek_at(1)
.is_some_and(|t| t.kind != TokenKind::Newline);
if binds_on_this_line {
let message = format!(
"a module-scope binding needs `const` or `static` and a type: `const {} : T = …`. Rust forbids `let` at module scope, and doc 03 §13.4 corrects doc 01 §4.3 accordingly",
name.text
);
return Err(ParseError::r#with(
Code::ModuleScopeBinding,
message,
name.span,
));
}
self.expect(
&TokenKind::Colon,
"expected `:` after the name, to begin the signature",
)?;
let binder = given_clause(self)?;
let bounds = if binder.is_some() {
Vec::new()
} else {
constraints(self)?
};
let is_const = self.eat_keyword(Keyword::Const);
let is_async = self.eat_keyword(Keyword::Async);
let is_unsafe = self.eat_keyword(Keyword::Unsafe);
let spine = parse_spine(self)?;
let predicates = where_predicates(self)?;
self.newline_with_trailing("expected a line break after the signature")?;
Ok(SignatureHead {
types: spine,
bounds,
r#given: binder,
predicates,
is_const,
is_async,
is_unsafe,
})
}
pub(crate) fn record_head(&mut self, class_name: &str, member: &str, head: &SignatureHead) {
let key = (class_name.to_string(), member.to_string());
self.class_heads.insert(key, head.clone());
();
}
pub(crate) fn borrowed_head(&self, class_name: &str, member: &str) -> Option<SignatureHead> {
let key = (class_name.to_string(), member.to_string());
self.class_heads.get(&key).cloned()
}
pub(crate) fn equations(
&mut self,
name: Ident,
leading: Vec<Trivia>,
start: usize,
head: &SignatureHead,
reserved: &[String],
ends_on_a_new_name: bool,
) -> Result<FnDecl, ParseError> {
let spine = &head.types;
let bounds = &head.bounds;
let mut clauses = Vec::new();
let mut sig = None;
loop {
let is_equation = match &self.peek().kind {
TokenKind::Ident(_) => !self.peek_at(1).is_some_and(|t| t.kind == TokenKind::Colon),
_ => false,
};
if !is_equation {
break;
}
if declares_an_operator(self) {
break;
}
let same_name = match &self.peek().kind {
TokenKind::Ident(text) if text == &name.text => true,
_ => false,
};
if ends_on_a_new_name && !same_name {
break;
}
let again = self.ident("expected the equation to repeat the name")?;
if again.text != name.text {
let message = format!(
"this equation defines `{}`, but the signature above it is for `{}`",
again.text, name.text
);
return Err(ParseError::r#with(Code::ExpectedName, message, again.span));
}
let row = patterns(self)?;
let built = signature_from(spine, &row, (again.span.0, self.prev_span().1))?;
let returns_unit = built.returns_unit();
if sig.is_none() {
sig = Some(built);
}
clauses.push(clause(row, &name, returns_unit, self)?);
self.skip_separators();
}
let mut settled =
sig.unwrap_or_else(|| signature_only(spine, (name.span.0, self.prev_span().1)));
settled.r#given = head.r#given.clone();
settled.predicates = head.predicates.clone();
generalise(&mut settled, bounds, reserved);
settled.is_const = head.is_const;
settled.is_async = head.is_async;
settled.is_unsafe = head.is_unsafe;
let end = self.prev_span().1;
let trailing = clauses.last().and_then(|c| c.trailing.clone());
Ok(FnDecl {
name,
sig: settled,
clauses,
visibility: Visibility::Private,
span: (start, end),
leading,
trailing,
})
}
pub(crate) fn statements(&mut self) -> Result<Block, ParseError> {
let start = self.peek_span().0;
let mut stmts = Vec::new();
loop {
self.skip_separators();
if self.check(&TokenKind::Dedent) || self.at_eof() {
break;
}
match stmt(self) {
Ok(found) => stmts.push(found),
Err(e) => {
self.r#errors.push(e);
self.recover_to_stmt()
}
};
}
let end = self.prev_span().1;
self.expect(&TokenKind::Dedent, "expected the body to end")?;
if stmts.is_empty() && self.r#errors.is_empty() {
return Err(ParseError::r#with(
Code::EmptyBody,
"a declaration body must contain at least one statement",
(start, start),
));
}
Ok(Block {
stmts,
span: (start, end),
})
}
pub(crate) fn indented_block(&mut self, code: Code, message: &str) -> Result<Block, ParseError> {
self.expect_with(code, &TokenKind::Indent, message)?;
self.statements()
}
pub(crate) fn statement_block(&mut self, message: &str) -> Result<Block, ParseError> {
self.newline_with_trailing("expected a line break before the body")?;
self.indented_block(Code::EmptyBody, message)
}
pub(crate) fn at_statement_end(&self) -> bool {
self.check(&TokenKind::Newline) || self.check(&TokenKind::Dedent) || self.at_eof()
}
pub(crate) fn if_statement(&mut self) -> Result<Expr, ParseError> {
let open = self.peek_span().0;
self.expect(&TokenKind::Kw(Keyword::If), "expected `if`")?;
let cond = condition(self)?;
let then_block = self.statement_block("expected an indented `if` body")?;
self.skip_separators();
if !self.check(&TokenKind::Kw(Keyword::Else)) {
return Ok(Expr::If {
condition: cond,
then_block,
r#otherwise: None,
span: (open, self.prev_span().1),
});
}
self.advance();
if self.check(&TokenKind::Kw(Keyword::If)) {
let start = self.peek_span().0;
let nested = self.if_statement()?;
let end = self.prev_span().1;
let only = Stmt {
expr: nested,
span: (start, end),
leading: Vec::new(),
trailing: None,
};
let chained = Block {
stmts: vec![only],
span: (start, end),
};
return Ok(Expr::If {
condition: cond,
then_block,
r#otherwise: Some(chained),
span: (open, end),
});
}
let fallback = self.statement_block("expected an indented `else` body")?;
Ok(Expr::If {
condition: cond,
then_block,
r#otherwise: Some(fallback),
span: (open, self.prev_span().1),
})
}
pub(crate) fn inline_body(&mut self) -> Result<Block, ParseError> {
let start = self.peek_span().0;
let value = parse_expr(self, 0)?;
let end = self.prev_span().1;
let only = Stmt {
expr: value,
span: (start, end),
leading: Vec::new(),
trailing: None,
};
Ok(Block {
stmts: vec![only],
span: (start, end),
})
}
pub(crate) fn opens_a_guard_list(&self) -> bool {
self.check(&TokenKind::Newline)
&& self.peek_at(1).is_some_and(|t| t.kind == TokenKind::Indent)
&& self.peek_at(2).is_some_and(|t| t.kind == TokenKind::Or)
}
pub(crate) fn guards(&mut self) -> Result<Vec<Guard>, ParseError> {
let mut rows = Vec::new();
loop {
self.skip_separators();
if !self.check(&TokenKind::Or) {
break;
}
let start = self.peek_span().0;
self.advance();
let cond = if self.check(&TokenKind::Kw(Keyword::Otherwise)) {
self.advance();
None
} else {
Some(parse_expr(self, 0)?)
};
self.expect(&TokenKind::Eq, "expected `=` after a guard's condition")?;
let body = self.inline_body()?;
self.newline_with_trailing("expected a line break after a guard's body")?;
rows.push(Guard {
condition: cond,
body,
span: (start, self.prev_span().1),
});
}
debug_assert!(
!rows.is_empty(),
"`opens_a_guard_list` guarantees a first `|`"
);
Ok(rows)
}
pub(crate) fn try_draw(&mut self) -> Result<Option<Expr>, ParseError> {
if !self.check(&TokenKind::Kw(Keyword::With)) {
return Ok(None);
}
let start = self.peek_span().0;
self.advance();
let name = self.ident("expected a name after `with`")?;
self.expect(
&TokenKind::Eq,
"expected `=` after a `with` binder — doc 30 §3.3",
)?;
let value = Box::new(parse_expr(self, 0)?);
Ok(Some(Expr::Draw {
name,
value,
span: (start, self.prev_span().1),
}))
}
pub(crate) fn try_binding(&mut self) -> Result<Option<Binding>, ParseError> {
let is_mut = self.check(&TokenKind::Kw(Keyword::Mut));
if !is_mut && !self.looks_like_a_binding() {
return Ok(None);
}
let start = self.peek_span().0;
if is_mut {
self.advance();
}
let bound = pattern_alt(self)?;
let ty = if self.check(&TokenKind::Colon) {
self.advance();
Some(self.type_expr("expected a type after `:`")?)
} else {
None
};
self.expect(&TokenKind::Eq, "expected `=` in a binding")?;
let value = parse_expr(self, 0)?;
Ok(Some(Binding {
pattern: bound,
ty,
value,
is_mut,
span: (start, self.prev_span().1),
}))
}
fn looks_like_a_binding(&self) -> bool {
match &self.peek().kind {
TokenKind::Ident(_) => {
let opener = if let Some(next) = self.peek_at(1) {
match next.kind {
TokenKind::Eq | TokenKind::Colon | TokenKind::LBrace => true,
_ => false,
}
} else {
false
};
opener && self.reaches_a_binding_eq()
}
TokenKind::LParen | TokenKind::LBracket => self.reaches_a_binding_eq(),
_ => false,
}
}
pub(crate) fn reaches_a_binding_eq(&self) -> bool {
let mut depth: i32 = 0;
let mut i = 0;
while let Some(tok) = self.peek_at(i) {
match &tok.kind {
TokenKind::Eq if depth == 0 => {
return true;
}
TokenKind::LParen | TokenKind::LBracket | TokenKind::LBrace => depth += 1,
TokenKind::RParen | TokenKind::RBracket | TokenKind::RBrace => {
depth -= 1;
if depth < 0 {
return false;
}
}
TokenKind::Newline | TokenKind::Indent | TokenKind::Dedent | TokenKind::Eof => {
return false;
}
_ => (),
};
i += 1;
}
false
}
pub(crate) fn type_expr(&mut self, message: &str) -> Result<TypeExpr, ParseError> {
capture_type(self, message, TypeStop::Greedy)
}
pub(crate) fn peek(&self) -> &'a Token {
self.toks.get(self.pos).unwrap_or_else(|| {
self
.toks
.last()
.expect("the token stream always contains at least Eof")
})
}
pub(crate) fn peek_at(&self, n: usize) -> Option<&'a Token> {
self.toks.get(self.pos + n)
}
pub(crate) fn peek_span(&self) -> Span {
self.peek().span
}
pub(crate) fn peek_leading(&self) -> Vec<Trivia> {
self.peek().leading.clone()
}
pub(crate) fn prev_span(&self) -> Span {
if self.pos == 0 {
return (0, 0);
}
self.toks[self.pos - 1].span
}
pub(crate) fn at_eof(&self) -> bool {
match self.peek().kind {
TokenKind::Eof => true,
_ => false,
}
}
pub(crate) fn check(&self, kind: &TokenKind) -> bool {
&self.peek().kind == kind
}
pub(crate) fn advance(&mut self) {
if !self.at_eof() {
self.pos += 1;
}
();
}
pub(crate) fn expect(&mut self, kind: &TokenKind, message: &str) -> Result<(), ParseError> {
self.expect_with(Code::ExpectedToken, kind, message)
}
pub(crate) fn expect_with(
&mut self,
code: Code,
kind: &TokenKind,
message: &str,
) -> Result<(), ParseError> {
if self.check(kind) {
self.advance();
return Ok(());
}
Err(ParseError::r#with(code, message, self.peek_span()))
}
pub(crate) fn eat_keyword(&mut self, kw: Keyword) -> bool {
if self.check(&TokenKind::Kw(kw)) {
self.advance();
return true;
}
false
}
pub(crate) fn position(&self) -> usize {
self.pos
}
pub(crate) fn rewind(&mut self, mark: usize) {
self.pos = mark;
();
}
pub(crate) fn try_ident(&mut self) -> Option<Ident> {
if let TokenKind::Ident(text) = &self.peek().kind {
let found = Ident {
text: text.clone(),
span: self.peek_span(),
};
self.advance();
return Some(found);
}
None
}
pub(crate) fn ident(&mut self, message: &str) -> Result<Ident, ParseError> {
if let TokenKind::Ident(text) = &self.peek().kind {
let found = Ident {
text: text.clone(),
span: self.peek_span(),
};
self.advance();
return Ok(found);
}
Err(ParseError::r#with(
Code::ExpectedName,
message,
self.peek_span(),
))
}
pub(crate) fn newline_with_trailing(
&mut self,
message: &str,
) -> Result<Option<Trivia>, ParseError> {
if self.check(&TokenKind::Newline) {
let trailing = self.peek().trailing.clone();
self.advance();
return Ok(trailing);
}
if self.at_eof() || self.check(&TokenKind::Dedent) || self.just_dedented() {
return Ok(None);
}
Err(ParseError::expected(message, self.peek_span()))
}
pub(crate) fn just_dedented(&self) -> bool {
self
.pos
.checked_sub(1)
.and_then(|i| self.toks.get(i))
.is_some_and(|t| t.kind == TokenKind::Dedent)
}
pub(crate) fn skip_separators(&mut self) {
while self.check(&TokenKind::Newline) {
self.advance();
}
();
}
pub(crate) fn skip_layout(&mut self) {
while self.check(&TokenKind::Newline)
|| self.check(&TokenKind::Indent)
|| self.check(&TokenKind::Dedent)
{
self.advance();
}
();
}
fn eof_trivia(&self) -> Vec<Trivia> {
let Some(last) = self.toks.last() else {
return Vec::new();
};
let ends = match last.kind {
TokenKind::Eof => true,
_ => false,
};
if !ends {
return Vec::new();
}
last.leading.clone()
}
fn recover_to_item(&mut self) {
let mut depth: usize = 0;
let mut running = true;
while running {
match &self.peek().kind {
TokenKind::Eof => running = false,
TokenKind::Indent => {
depth += 1;
self.advance()
}
TokenKind::Dedent => {
depth = depth.saturating_sub(1);
self.advance()
}
TokenKind::Ident(_) if depth == 0 => running = false,
_ => self.advance(),
};
}
();
}
fn recover_to_stmt(&mut self) {
let mut depth: usize = 0;
let mut running = true;
while running {
match &self.peek().kind {
TokenKind::Eof => running = false,
TokenKind::Newline if depth == 0 => {
self.advance();
running = false;
}
TokenKind::Dedent if depth == 0 => running = false,
TokenKind::Indent => {
depth += 1;
self.advance()
}
TokenKind::Dedent => {
depth = depth.saturating_sub(1);
self.advance()
}
_ => self.advance(),
};
}
();
}
}