radiance · Radiance self-hosting compiler

compiler/ kernel/ lib/ examples/ std/ arch/ char/ collections/ lang/ alloc/ ast/ gen/ il/ module/ parser/ resolver/ scanner/ alloc.rad 7.1 KiB ast.rad 26.7 KiB gen.rad 513 B il.rad 19.5 KiB lower.rad 308.1 KiB module.rad 14.9 KiB package.rad 1.3 KiB parser.rad 89.5 KiB resolver.rad 439.6 KiB scanner.rad 18.0 KiB sexpr.rad 6.4 KiB strings.rad 2.2 KiB types.rad 1.6 KiB sys/ arch.rad 68 B char.rad 855 B collections.rad 39 B fmt.rad 8.3 KiB intrinsics.rad 467 B io.rad 1.7 KiB lang.rad 276 B mem.rad 2.3 KiB sys.rad 179 B testing.rad 2.4 KiB tests.rad 15.7 KiB vec.rad 3.2 KiB std.rad 281 B scripts/ seed/ sublime/ test/ vim/ .gitignore 336 B .gitsigners 112 B CONTRIBUTING 2.1 KiB LICENSE 1.1 KiB Makefile 9.2 KiB README 2.5 KiB STYLE 2.5 KiB std.lib 1.5 KiB std.lib.test 662 B
lib/std/lang/parser.rad 89.5 KiB raw
//! Recursive descent parser for the Radiance programming language.
@test export mod tests;

use std::mem;
use std::io;
use std::fmt;
use std::lang::alloc;
use std::lang::ast;
use std::lang::strings;
use std::lang::scanner;

/// Maximum `u32` value.
export constant U32_MAX: u32 = 0xFFFFFFFF;
/// Minimum `i64` value.
export constant I64_MIN: i64 = -0x8000000000000000;
/// Largest magnitude representable by a negative `i64`.
export constant I64_MIN_MAGNITUDE: u64 = 0x8000000000000000;
/// Maximum representable `i64` magnitude.
export constant I64_MAX_MAGNITUDE: u64 = 0x7FFFFFFFFFFFFFFF;
/// Maximum representable `u64` value.
export constant U64_MAX: u64 = 0xFFFFFFFFFFFFFFFF;
/// Maximum number of fields in a record.
export constant MAX_RECORD_FIELDS: u32 = 32;

/// Maximum number of parser errors before aborting.
constant MAX_ERRORS: u32 = 8;

/// Parser error type.
export union ParseError: Copy {
    /// Encountered a token that was not expected in the current context.
    UnexpectedToken,
}

/// Represents a parsed name-type-value triple.
///
/// Used for record field declarations, variable declarations,
/// and record field initializations.
record NameTypeValue: Copy {
    /// The identifier name.
    name: *ast::Node,
    /// The optional type annotation.
    type: ?*ast::Node,
    /// The optional initialization value.
    value: ?*ast::Node,
    /// The optional alignment specifier.
    alignment: ?*ast::Node,
}

/// Behavioural differences when parsing record field lists.
union RecordFieldMode: Copy {
    /// Labeled fields, allows for default values.
    Labeled,
    /// Unlabeled fields.
    Unlabeled,
}

/// Parser context differentiates between regular expressions and
/// conditional contexts where `{` begins a block.
union Context: Copy {
    /// Normal expression context where `{` may start a record literal
    /// and `if` may start a conditional expression.
    Normal,
    /// Pattern context where `{` may start a record literal
    /// but `if` is reserved for guards.
    Pattern,
    /// Conditional context where `{` always begins a block
    /// and `if` is reserved for guards.
    Condition,
}

/// A single parser error with location information.
export record Error: Copy {
    /// Human-readable error message.
    message: *[u8],
    /// The token where the error occurred.
    token: scanner::Token,
}

/// List of parser errors encountered during parsing.
record ErrorList: Copy {
    /// Fixed-size array of error records.
    list: [Error; MAX_ERRORS],
    /// Number of errors currently in the list.
    count: u32,
}

/// Snapshot of parser state for speculative parsing.
record SavedState: Copy {
    /// Scanner position, tokens, diagnostics, and expression context.
    parser: Parser,
    /// First byte available for tentative allocations.
    arena: u32,
    /// First node identifier available to the tentative parse.
    nextId: u32,
}

/// Operator metadata for precedence climbing.
record OpInfo: Copy {
    op: ast::BinaryOp,
    prec: i32,
}

/// Get operator info for a token kind using match-based dispatch.
/// Returns nil if the token is not a binary operator.
fn getOpInfo(kind: scanner::TokenKind) -> ?OpInfo {
    match kind {
        case scanner::TokenKind::Star =>
            return { op: ast::BinaryOp::Mul, prec: 7 },
        case scanner::TokenKind::Slash =>
            return { op: ast::BinaryOp::Div, prec: 7 },
        case scanner::TokenKind::Percent =>
            return { op: ast::BinaryOp::Mod, prec: 7 },
        case scanner::TokenKind::Plus =>
            return { op: ast::BinaryOp::Add, prec: 6 },
        case scanner::TokenKind::Minus =>
            return { op: ast::BinaryOp::Sub, prec: 6 },
        case scanner::TokenKind::LtLt =>
            return { op: ast::BinaryOp::Shl, prec: 5 },
        case scanner::TokenKind::GtGt =>
            return { op: ast::BinaryOp::Shr, prec: 5 },
        case scanner::TokenKind::Amp =>
            return { op: ast::BinaryOp::BitAnd, prec: 4 },
        case scanner::TokenKind::Caret =>
            return { op: ast::BinaryOp::BitXor, prec: 3 },
        case scanner::TokenKind::Pipe =>
            return { op: ast::BinaryOp::BitOr, prec: 2 },
        case scanner::TokenKind::EqualEqual =>
            return { op: ast::BinaryOp::Eq, prec: 1 },
        case scanner::TokenKind::LtGt =>
            return { op: ast::BinaryOp::Ne, prec: 1 },
        case scanner::TokenKind::Lt =>
            return { op: ast::BinaryOp::Lt, prec: 1 },
        case scanner::TokenKind::Gt =>
            return { op: ast::BinaryOp::Gt, prec: 1 },
        case scanner::TokenKind::LtEqual =>
            return { op: ast::BinaryOp::Lte, prec: 1 },
        case scanner::TokenKind::GtEqual =>
            return { op: ast::BinaryOp::Gte, prec: 1 },
        case scanner::TokenKind::And =>
            return { op: ast::BinaryOp::And, prec: 0 },
        case scanner::TokenKind::Or =>
            return { op: ast::BinaryOp::Or, prec: 0 },
        else =>
            return nil,
    }
}

/// Parser state.
export record Parser: Copy {
    /// The scanner that provides tokens.
    scanner: scanner::Scanner,
    /// The current token being examined.
    current: scanner::Token,
    /// The most recently consumed token.
    previous: scanner::Token,
    /// Collection of errors encountered during parsing.
    errors: ErrorList,
    /// Arena for node allocations. It must outlive the parser.
    arena: *unsafe mut ast::NodeArena,
    /// Allocator backed by the node arena.
    allocator: alloc::Allocator,
    /// Current parsing context (normal or conditional).
    context: Context,
}

/// Create a new parser initialized with the given source kind, source and node arena.
/// The node arena and string pool must outlive every copy of the parser.
export unsafe fn mkParser(sourceLoc: scanner::SourceLoc, source: *[u8], arena: &mut ast::NodeArena, pool: *unsafe mut strings::Pool) -> Parser {
    return Parser {
        scanner: scanner::scanner(sourceLoc, source, pool),
        current: scanner::invalid(0, ""),
        previous: scanner::invalid(0, ""),
        errors: ErrorList { list: undefined, count: 0 },
        arena: (&mut *arena) as *unsafe mut ast::NodeArena,
        allocator: alloc::arenaAllocator(&mut arena.arena),
        context: Context::Normal,
    };
}

/// Emit a `true` or `false` literal node.
unsafe fn nodeBool(p: &mut Parser, value: bool) -> *ast::Node {
    return node(p, ast::NodeValue::Bool(value));
}

/// Parse an integer literal while mapping shared errors into parser diagnostics.
fn parseIntLiteral(p: &mut Parser, text: *[u8]) -> fmt::IntLiteral
    throws (ParseError)
{
    let literal = try fmt::parseInt(text) catch err {
        match err {
            case fmt::ParseError::Invalid =>
                throw failParsing(p, "invalid integer literal"),
            case fmt::ParseError::InvalidDigit =>
                throw failParsing(p, "invalid digit in integer literal"),
            case fmt::ParseError::Overflow =>
                throw failParsing(p, "integer literal overflow"),
        }
    };
    return literal;
}

/// Emit an integer type node.
unsafe fn nodeTypeInt(p: &mut Parser, width: u8, sign: ast::Signedness) -> *ast::Node {
    return node(p, ast::NodeValue::TypeSig(
        ast::TypeSig::Integer { width, sign }
    ));
}

/// Emit a number literal node with the provided literal metadata.
unsafe fn nodeNumber(p: &mut Parser, literal: fmt::IntLiteral) -> *ast::Node {
    return node(p, ast::NodeValue::Number(literal));
}

/// Emit a `super` node.
unsafe fn nodeSuper(p: &mut Parser) -> *ast::Node {
    return node(p, ast::NodeValue::Super);
}

/// Emit a single attribute node.
unsafe fn nodeAttribute(p: &mut Parser, attr: ast::Attribute) -> *ast::Node {
    return node(p, ast::NodeValue::Attribute(attr));
}

/// Emit a unary operator node.
unsafe fn nodeUnary(p: &mut Parser, op: ast::UnaryOp, value: *ast::Node) -> *ast::Node {
    return node(p, ast::NodeValue::UnOp({ op, value }));
}

/// Parse one expression without inheriting a surrounding condition or pattern context.
unsafe fn parseNormalExpr(p: &mut Parser) -> *ast::Node throws (ParseError) {
    let saved = p.context;
    set p.context = Context::Normal;
    let expr = try parseExpr(p);
    set p.context = saved;
    return expr;
}

/// Parse a parenthesized expression without applying postfix operators.
unsafe fn parseParenthesized(p: &mut Parser) -> *ast::Node
    throws (ParseError)
{
    try expect(p, scanner::TokenKind::LParen, "expected `(`");

    let expr = try parseNormalExpr(p);

    try expect(p, scanner::TokenKind::RParen, "expected `)`");

    return expr;
}

/// Parse an array literal: `[a, b, c]` or `[item; count]`.
unsafe fn parseArrayLiteral(p: &mut Parser) -> *ast::Node
    throws (ParseError)
{
    try expect(p, scanner::TokenKind::LBracket, "expected `[`");
    if consume(p, scanner::TokenKind::RBracket) { // Empty array: `[]`.
        let empty: *mut [*ast::Node] = &mut [];
        return node(p, ast::NodeValue::ArrayLit(empty));
    }
    let firstExpr = try parseNormalExpr(p);

    if consume(p, scanner::TokenKind::Semicolon) {
        // Array repeat literal: `[item; count]`.
        let count = try parseNormalExpr(p);
        try expect(p, scanner::TokenKind::RBracket, "expected `]` after array repeat count");

        return node(p, ast::NodeValue::ArrayRepeatLit(
            ast::ArrayRepeatLit { item: firstExpr, count }
        ));
    }
    // Regular array literal: `[a, b, ...]`.
    let mut items = ast::nodeSlice(p.arena, 64).append(firstExpr, p.allocator);

    while consume(p, scanner::TokenKind::Comma) and not check(p, scanner::TokenKind::RBracket) {
        let elem = try parseNormalExpr(p);
        items.append(elem, p.allocator);
    }
    try expect(p, scanner::TokenKind::RBracket, "expected `]` after array elements");

    return node(p, ast::NodeValue::ArrayLit(items));
}

/// Parse a function call expression.
unsafe fn parseCall(p: &mut Parser, callee: *ast::Node) -> *ast::Node
    throws (ParseError)
{
    let args = try parseList(
        p,
        scanner::TokenKind::LParen,
        scanner::TokenKind::RParen,
        parseNormalExpr
    );
    return node(p, ast::NodeValue::Call(
        ast::Call { callee, args }
    ));
}

/// Parse zero or more trailing `as` casts applied to `expr`.
unsafe fn parseAsCast(p: &mut Parser, expr: *ast::Node) -> *ast::Node
    throws (ParseError)
{
    let mut result = expr;

    while consume(p, scanner::TokenKind::As) {
        let target = try parseType(p);

        set result = node(p, ast::NodeValue::As(
            ast::As { value: result, type: target }
        ));
    }
    return result;
}

/// Parse an optional conditional expression suffix.
///
///   `<thenExpr> if <condition> else <elseExpr>`
///
/// If no `if` keyword follows, returns the input expression unchanged.
unsafe fn parseCondExpr(p: &mut Parser, thenExpr: *ast::Node) -> *ast::Node
    throws (ParseError)
{
    // Only parse conditional expressions in normal context.
    // In conditional context, `if` is used for guards.
    if p.context <> Context::Normal {
        return thenExpr;
    }
    if not consume(p, scanner::TokenKind::If) {
        return thenExpr;
    }
    let condition = try parseCond(p);
    try expect(p, scanner::TokenKind::Else, "expected `else` in conditional expression");
    let elseExpr = try parseExpr(p);

    return node(p, ast::NodeValue::CondExpr(
        ast::CondExpr { condition, thenExpr, elseExpr }
    ));
}

/// Parse array subscript or slice expression after `[`.
unsafe fn parseSubscriptOrSlice(p: &mut Parser, container: *ast::Node) -> *ast::Node
    throws (ParseError)
{
    try expect(p, scanner::TokenKind::LBracket, "expected `[`");

    let mut index: *ast::Node = undefined;

    if consume(p, scanner::TokenKind::DotDot) {
        // Either `..` or `..end`.
        let mut endExpr: ?*ast::Node = nil;
        if not check(p, scanner::TokenKind::RBracket) {
            set endExpr = try parseNormalExpr(p);
        }
        set index = node(p, ast::NodeValue::Range(
            ast::Range { start: nil, end: endExpr }
        ));
    } else {
        // Either `n`, `n..` or `n..end`.
        let startExpr = try parseNormalExpr(p);

        if consume(p, scanner::TokenKind::DotDot) {
            // Either `n..` or `n..end`.
            let mut endExpr: ?*ast::Node = nil;
            if not check(p, scanner::TokenKind::RBracket) {
                set endExpr = try parseNormalExpr(p);
            }
            set index = node(p, ast::NodeValue::Range(
                ast::Range { start: startExpr, end: endExpr }
            ));
        } else {
            // Just `n` - regular indexing.
            set index = startExpr;
        }
    }
    try expect(p, scanner::TokenKind::RBracket, "expected `]` after array index");

    return node(p, ast::NodeValue::Subscript { container, index });
}

/// Parse postfix operators (eg. field access, function call etc.)
unsafe fn parsePostfix(p: &mut Parser, expr: *ast::Node) -> *ast::Node
    throws (ParseError)
{
    let mut result = expr;

    loop {
        match p.current.kind {
            case scanner::TokenKind::Dot => {
                advance(p);

                let mut field: *ast::Node = undefined;
                if consume(p, scanner::TokenKind::Set) {
                    set field = node(p, ast::NodeValue::Ident(p.previous.source));
                } else {
                    set field = try parseIdent(p, "expected field name after `.`");
                }
                set result = node(p, ast::NodeValue::FieldAccess(
                    ast::Access { parent: result, child: field }
                ));
            }
            case scanner::TokenKind::ColonColon => {
                advance(p);

                let ident = try parseIdent(p, "expected identifier after `::`");
                set result = node(p, ast::NodeValue::ScopeAccess(
                    ast::Access { parent: result, child: ident }
                ));
            }
            case scanner::TokenKind::Region => {
                let regions = try parseRegions(p);
                set result = node(p, ast::NodeValue::RegionApply { value: result, regions });
            }
            case scanner::TokenKind::LBracket => {
                set result = try parseSubscriptOrSlice(p, result);
            }
            case scanner::TokenKind::LParen => {
                set result = try parseCall(p, result);
            }
            case scanner::TokenKind::LBrace if p.context <> Context::Condition => {
                set result = try parseRecordLit(p, result);
            }
            else => {
                break;
            }
        }
    }
    return result;
}

/// Parse a conditional expression.
export unsafe fn parseCond(p: &mut Parser) -> *ast::Node throws (ParseError) {
    let saved = p.context;
    set p.context = Context::Condition;
    let expr = try parseExpr(p);
    set p.context = saved;

    return expr;
}

/// Parse unary expression followed by optional `as` cast.
/// `as` has higher precedence than binary ops but lower than unary.
unsafe fn parseUnary(p: &mut Parser) -> *ast::Node throws (ParseError) {
    let unary = try parseUnaryExpr(p);
    return try parseAsCast(p, unary);
}

/// Parse prefix unary expressions and defer to primary expressions otherwise.
unsafe fn parseUnaryExpr(p: &mut Parser) -> *ast::Node
    throws (ParseError)
{
    match p.current.kind {
        case scanner::TokenKind::Not => {
            advance(p);
            let value = try parseUnaryExpr(p);
            return nodeUnary(p, ast::UnaryOp::Not, value);
        }
        case scanner::TokenKind::Minus => {
            advance(p);
            let value = try parseUnaryExpr(p);
            return nodeUnary(p, ast::UnaryOp::Neg, value);
        }
        case scanner::TokenKind::Tilde => {
            advance(p);
            let value = try parseUnaryExpr(p);
            return nodeUnary(p, ast::UnaryOp::BitNot, value);
        }
        case scanner::TokenKind::Star => {
            advance(p);
            let value = try parseUnaryExpr(p);
            return node(p, ast::NodeValue::Deref(value));
        }
        case scanner::TokenKind::Amp => {
            advance(p);
            let kind = parseAddressKind(p);
            let target = try parseUnaryExpr(p);
            return node(p, ast::NodeValue::AddressOf({ target, kind }));
        }
        else => {
            return try parsePrimary(p);
        }
    }
}

/// Parse the access qualifier after an address operator.
unsafe fn parseAddressKind(p: &mut Parser) -> ast::AddressKind {
    if consume(p, scanner::TokenKind::Mut) {
        return ast::AddressKind::Mutable;
    }
    if check(p, scanner::TokenKind::Ident) and mem::eq(p.current.source, "cell") {
        advance(p);
        return ast::AddressKind::Cell;
    }
    return ast::AddressKind::Shared;
}

/// Find the operator info for a token if it has precedence greater than the
/// given minimum.
fn findNextOp(kind: scanner::TokenKind, minPrec: i32) -> ?OpInfo {
    if let opInfo = getOpInfo(kind) {
        if opInfo.prec > minPrec {
            return opInfo;
        }
    }
    return nil;
}

/// Determine whether the current token can terminate a range expression.
fn isRangeTerminator(kind: scanner::TokenKind) -> bool {
    match kind {
        case scanner::TokenKind::Comma,
             scanner::TokenKind::Semicolon,
             scanner::TokenKind::RParen,
             scanner::TokenKind::RBrace,
             scanner::TokenKind::RBracket,
             scanner::TokenKind::Else,
             scanner::TokenKind::In,
             scanner::TokenKind::LBrace,
             scanner::TokenKind::Eof =>
            return true,
        else =>
            return false,
    }
}

/// Build a range expression node with an optional start and end expression.
unsafe fn parseRangeExpr(p: &mut Parser, start: ?*ast::Node) -> *ast::Node
    throws (ParseError)
{
    let mut endExpr: ?*ast::Node = nil;

    if not isRangeTerminator(p.current.kind) {
        let right = try parseUnary(p);
        set endExpr = try parseBinary(p, right, -1);
    }
    return node(p, ast::NodeValue::Range(
        ast::Range { start, end: endExpr }
    ));
}

/// Parse binary expressions using precedence climbing.
unsafe fn parseBinary(p: &mut Parser, left: *ast::Node, minPrec: i32) -> *ast::Node
    throws (ParseError)
{
    let mut result = left;

    loop {
        if p.current.kind == scanner::TokenKind::DotDot {
            advance(p);
            set result = try parseRangeExpr(p, result);
        } else {
            let opInfo = findNextOp(p.current.kind, minPrec) else break;
            advance(p);

            let mut right = try parseUnary(p);

            while let _ = findNextOp(p.current.kind, opInfo.prec)  {
                set right = try parseBinary(p, right, opInfo.prec);
            }
            set result = node(p, ast::NodeValue::BinOp(ast::BinOp {
                op: opInfo.op, left: result, right,
            }));
        }
    }
    return result;
}

/// Check whether an expression may appear on the left side of an assignment.
fn isAssignableTarget(node: *ast::Node) -> bool {
    match node.value {
        case ast::NodeValue::Ident(_) =>
            return true,
        case ast::NodeValue::FieldAccess(_) =>
            return true,
        case ast::NodeValue::ScopeAccess(_) =>
            return true,
        case ast::NodeValue::Subscript { .. } =>
            return true,
        case ast::NodeValue::Deref(_) =>
            return true,
        else =>
            return false,
    }
}
/// Check if a statement requires a semicolon after it.
///
/// Statements that end with blocks don't require semicolons.
/// All other statements do.
fn expectsSemicolon(stmt: *ast::Node) -> bool {
    match stmt.value {
        case ast::NodeValue::If(_),
             ast::NodeValue::IfLet(_),
             ast::NodeValue::While(_),
             ast::NodeValue::WhileLet(_),
             ast::NodeValue::For(_),
             ast::NodeValue::Loop { .. },
             ast::NodeValue::Match(_),
             ast::NodeValue::Block(_),
             ast::NodeValue::RegionBlock { .. },
             ast::NodeValue::FnDecl(_),
             ast::NodeValue::RecordDecl(_),
             ast::NodeValue::UnionDecl(_),
             ast::NodeValue::TraitDecl { .. },
             ast::NodeValue::InstanceDecl { .. },
             ast::NodeValue::MethodDecl { .. } => return false,
        else => return true,
    }
}

/// Parse a primary leaf expression without postfix operators.
unsafe fn parseLeaf(p: &mut Parser) -> *ast::Node
    throws (ParseError)
{
    match p.current.kind {
        case scanner::TokenKind::True => {
            advance(p);
            return nodeBool(p, true);
        }
        case scanner::TokenKind::False => {
            advance(p);
            return nodeBool(p, false);
        }
        case scanner::TokenKind::Ident => {
            advance(p);
            return node(p, ast::NodeValue::Ident(p.previous.source));
        }
        case scanner::TokenKind::Super => {
            advance(p);
            return nodeSuper(p);
        }
        case scanner::TokenKind::Number => {
            advance(p);
            let source = p.previous.source;
            let literal = try parseIntLiteral(p, source);
            return nodeNumber(p, literal);
        }
        case scanner::TokenKind::LParen => {
            return try parseParenthesized(p);
        }
        case scanner::TokenKind::Try => {
            return try parseTryExpr(p);
        }
        case scanner::TokenKind::Nil => {
            advance(p);
            return node(p, ast::NodeValue::Nil);
        }
        case scanner::TokenKind::Undefined => {
            advance(p);
            return node(p, ast::NodeValue::Undef);
        }
        case scanner::TokenKind::Char => {
            advance(p);
            let ch = try fmt::parseChar(p.previous.source) catch {
                throw failParsing(p, "invalid char literal");
            };
            return node(p, ast::NodeValue::Char(ch));
        }
        case scanner::TokenKind::String => {
            advance(p);
            let src = p.previous.source;
            let raw = &src[1..src.len - 1]; // Strip quotes.

            // Process escape sequences into arena buffer.
            let buf = alloc::remainingBuf(&mut p.arena.arena);
            let len = fmt::unescapeString(raw, buf);
            alloc::commit(&mut p.arena.arena, len);

            return node(p, ast::NodeValue::String(&buf[..len]));
        }
        case scanner::TokenKind::Underscore => {
            advance(p);
            return node(p, ast::NodeValue::Placeholder);
        }
        case scanner::TokenKind::LBracket => {
            return try parseArrayLiteral(p);
        }
        case scanner::TokenKind::AtIdent => {
            return try parseBuiltin(p);
        }
        case scanner::TokenKind::DotDot => {
            advance(p);
            return try parseRangeExpr(p, nil);
        }
        case scanner::TokenKind::LBrace => {
            // Anonymous record literal: { x: 1, y: 2 }.
            // Only allowed in normal context, not in conditions.
            if p.context <> Context::Normal {
                throw failParsing(p, "unexpected `{` in this context");
            }
            return try parseRecordLit(p, nil);
        }
        else => {
            throw failParsing(p, "expected expression");
        }
    }
}

/// Parse a primary expression (leaf nodes followed by postfix operators).
unsafe fn parsePrimary(p: &mut Parser) -> *ast::Node
    throws (ParseError)
{
    let leaf = try parseLeaf(p);
    return try parsePostfix(p, leaf);
}

/// Parse a builtin function call like `@sizeOf(T)` or `@alignOf(T)`.
unsafe fn parseBuiltin(p: &mut Parser) -> *ast::Node
    throws (ParseError)
{
    // Skip the '@' to get the name.
    let ident = p.current.source;
    advance(p);

    let mut kind: ast::Builtin = undefined;
    // TODO: Use `match`.
    if ident == "@sizeOf" {
        set kind = ast::Builtin::SizeOf;
    } else if ident == "@alignOf" {
        set kind = ast::Builtin::AlignOf;
    } else if ident == "@sliceOf" {
        set kind = ast::Builtin::SliceOf;
    } else {
        throw failParsing(p, "unknown builtin");
    }
    try expect(p, scanner::TokenKind::LParen, "expected `(` after builtin name");

    // Parse arguments into a list. Use capacity 4 to handle any valid argument count
    // plus some extra for error recovery.
    let mut args = ast::nodeSlice(p.arena, 4);

    if kind == ast::Builtin::SliceOf {
        // Parse comma-separated expressions until closing paren.
        // Argument count validation is done in semantic analysis.
        while not check(p, scanner::TokenKind::RParen) {
            args.append(try parseExpr(p), p.allocator);
            if not consume(p, scanner::TokenKind::Comma) {
                break;
            }
        }
    } else {
        args.append(try parseType(p), p.allocator);
    }
    try expect(p, scanner::TokenKind::RParen, "expected `)` after builtin argument");

    return node(p, ast::NodeValue::BuiltinCall { kind, args });
}

/// Parse a single expression.
///
/// Parses unary and binary operators using precedence climbing.
/// Conditional expressions (`x if cond else y`) have lowest precedence.
export unsafe fn parseExpr(p: &mut Parser) -> *ast::Node
    throws (ParseError)
{
    let left = try parseUnary(p);
    let expr = try parseBinary(p, left, -1);
    return try parseCondExpr(p, expr);
}

/// Try to consume a compound assignment operator and return its binary op.
unsafe fn tryCompoundAssignOp(p: &mut Parser) -> ?ast::BinaryOp {
    match p.current.kind {
        case scanner::TokenKind::PlusEqual =>    { advance(p); return ast::BinaryOp::Add; }
        case scanner::TokenKind::MinusEqual =>   { advance(p); return ast::BinaryOp::Sub; }
        case scanner::TokenKind::StarEqual =>    { advance(p); return ast::BinaryOp::Mul; }
        case scanner::TokenKind::SlashEqual =>   { advance(p); return ast::BinaryOp::Div; }
        case scanner::TokenKind::PercentEqual => { advance(p); return ast::BinaryOp::Mod; }
        case scanner::TokenKind::AmpEqual =>     { advance(p); return ast::BinaryOp::BitAnd; }
        case scanner::TokenKind::PipeEqual =>    { advance(p); return ast::BinaryOp::BitOr; }
        case scanner::TokenKind::CaretEqual =>   { advance(p); return ast::BinaryOp::BitXor; }
        case scanner::TokenKind::LtLtEqual =>    { advance(p); return ast::BinaryOp::Shl; }
        case scanner::TokenKind::GtGtEqual =>    { advance(p); return ast::BinaryOp::Shr; }
        else => return nil,
    }
}

/// Parse an expression statement.
export unsafe fn parseExprStmt(p: &mut Parser) -> *ast::Node
    throws (ParseError)
{
    let expr = try parseExpr(p);
    return node(p, ast::NodeValue::ExprStmt(expr));
}

/// Parse a `set` statement assignment.
unsafe fn parseSetStmt(p: &mut Parser) -> *ast::Node
    throws (ParseError)
{
    let target = try parseUnary(p);
    if not ast::isPlaceExpr(target) {
        throw failParsing(p, "invalid assignment target");
    }
    if consume(p, scanner::TokenKind::Equal) {
        let value = try parseExpr(p);
        return node(p, ast::NodeValue::Assign(
            ast::Assign { left: target, right: value }
        ));
    }
    // Compound assignment: desugar `set x <op>= y` into `set x = x <op> y`.
    // The target node is shared with the binary operand.
    if let op = tryCompoundAssignOp(p) {
        let rhs = try parseExpr(p);
        let binop = node(p, ast::NodeValue::BinOp(
            ast::BinOp { op, left: target, right: rhs }
        ));
        return node(p, ast::NodeValue::Assign(
            ast::Assign { left: target, right: binop }
        ));
    }
    throw failParsing(p, "expected assignment after `set`");
}

/// Parse leading attributes and declaration modifiers.
unsafe fn parseAttributes(p: &mut Parser) -> ?ast::Attributes {
    let mut attrs = ast::nodeSlice(p.arena, 4);

    if let attr = tryParseAnnotation(p) {
        attrs.append(attr, p.allocator);
    }
    if consume(p, scanner::TokenKind::Export) {
        attrs.append(nodeAttribute(p, ast::Attribute::Export), p.allocator);
    }
    if consume(p, scanner::TokenKind::Unsafe) {
        attrs.append(nodeAttribute(p, ast::Attribute::Unsafe), p.allocator);
    }
    if attrs.len > 0 {
        return ast::Attributes { list: attrs };
    }
    return nil;
}

/// Try to parse an annotation like `@default`.
///
/// Returns `nil` if not a known annotation (e.g. `@sizeOf` or `@alignOf` which are builtins).
/// Only consumes tokens if a valid annotation is found.
unsafe fn tryParseAnnotation(p: &mut Parser) -> ?*ast::Node {
    if not check(p, scanner::TokenKind::AtIdent) {
        return nil;
    }
    // Token is @identifier, skip the '@' to get the name.
    let ident = p.current.source;
    if ident == "@default" {
        advance(p); // Consume `@default`.
        return nodeAttribute(p, ast::Attribute::Default);
    }
    if ident == "@test" {
        advance(p); // Consume `@test`.
        return nodeAttribute(p, ast::Attribute::Test);
    }
    if ident == "@intrinsic" {
        advance(p); // Consume `@intrinsic`.
        return nodeAttribute(p, ast::Attribute::Intrinsic);
    }
    return nil;
}

/// Parse a single statement.
///
/// Dispatches to the appropriate statement parser based on the current token.
export unsafe fn parseStmt(p: &mut Parser) -> *ast::Node
    throws (ParseError)
{
    // TODO: Why is `parseStmt` checking for attributes?
    // We should have a `parseDecl` which is top-level, and `parseStmt` which
    // is inside functions.
    let attrs = parseAttributes(p);
    if let list = attrs {
        if ast::attributesContains(&list, ast::Attribute::Unsafe)
            and p.current.kind == scanner::TokenKind::LBrace
        {
            if list.list.len <> 1 {
                throw failParsing(p, "unsafe blocks cannot have declaration attributes");
            }
            return try parseBlockBody(p, true);
        }
        if ast::attributesContains(&list, ast::Attribute::Unsafe)
            and p.current.kind <> scanner::TokenKind::Fn
            and p.current.kind <> scanner::TokenKind::Static
        {
            throw failParsing(p, "`unsafe` is only allowed on functions, blocks, and statics");
        }
        let allowed: bool =
            p.current.kind == scanner::TokenKind::Fn or
            p.current.kind == scanner::TokenKind::Union or
            p.current.kind == scanner::TokenKind::Record or
            p.current.kind == scanner::TokenKind::Mod or
            p.current.kind == scanner::TokenKind::Static or
            p.current.kind == scanner::TokenKind::Constant or
            p.current.kind == scanner::TokenKind::Use or
            p.current.kind == scanner::TokenKind::Trait;

        if not allowed {
            throw failParsing(p, "attributes are not allowed in this context");
        }
    }

    match p.current.kind {
        case scanner::TokenKind::If => {
            return try parseIf(p);
        }
        case scanner::TokenKind::LBrace => {
            return try parseBlock(p);
        }
        case scanner::TokenKind::While => {
            return try parseWhile(p);
        }
        case scanner::TokenKind::Loop => {
            return try parseLoop(p);
        }
        case scanner::TokenKind::For => {
            return try parseFor(p);
        }
        case scanner::TokenKind::Return => {
            return try parseReturn(p);
        }
        case scanner::TokenKind::Throw => {
            return try parseThrow(p);
        }
        case scanner::TokenKind::Panic => {
            return try parsePanic(p);
        }
        case scanner::TokenKind::Assert => {
            return try parseAssert(p);
        }
        case scanner::TokenKind::Break => {
            advance(p);
            return node(p, ast::NodeValue::Break);
        }
        case scanner::TokenKind::Continue => {
            advance(p);
            return node(p, ast::NodeValue::Continue);
        }
        case scanner::TokenKind::Match => {
            return try parseMatch(p);
        }
        case scanner::TokenKind::Let => {
            if isRegionBlock(p) {
                return try parseRegionBlock(p);
            }
            advance(p);
            if consume(p, scanner::TokenKind::Case) {
                return try parseLetCase(p);
            }
            if consume(p, scanner::TokenKind::Mut) {
                return try parseLet(p, true);
            }
            return try parseLet(p, false);
        }
        case scanner::TokenKind::Set => {
            advance(p);
            return try parseSetStmt(p);
        }
        case scanner::TokenKind::Constant => {
            return try parseConst(p, attrs);
        }
        case scanner::TokenKind::Static => {
            return try parseStatic(p, attrs);
        }
        case scanner::TokenKind::Fn => {
            return try parseFnDecl(p, attrs);
        }
        case scanner::TokenKind::Union => {
            return try parseUnionDecl(p, attrs);
        }
        case scanner::TokenKind::Record => {
            return try parseRecordDecl(p, attrs);
        }
        case scanner::TokenKind::Use => {
            if isSessionBlock(p) {
                return try parseSessionBlock(p);
            }
            return try parseUse(p, attrs);
        }
        case scanner::TokenKind::Mod => {
            return try parseMod(p, attrs);
        }
        case scanner::TokenKind::Trait => {
            return try parseTraitDecl(p, attrs);
        }
        case scanner::TokenKind::Instance => {
            return try parseInstanceDecl(p);
        }
        else => {
            return try parseExprStmt(p);
        }
    }
}

/// Return whether the current `let` statement starts a regional block.
unsafe fn isRegionBlock(p: &Parser) -> bool {
    let mut lookahead = p.scanner;
    return scanner::next(&mut lookahead).kind == scanner::TokenKind::Ident
        and scanner::next(&mut lookahead).kind == scanner::TokenKind::Colon
        and scanner::next(&mut lookahead).kind == scanner::TokenKind::Region;
}

/// Return whether the current `use` statement has an allocation-session header.
unsafe fn isSessionBlock(p: &mut Parser) -> bool {
    let saved = saveState(p);
    advance(p);
    let source: ?*ast::Node = try? parseUnaryExpr(p);
    let result = source <> nil
        and consume(p, scanner::TokenKind::As)
        and consume(p, scanner::TokenKind::Ident)
        and check(p, scanner::TokenKind::In);
    restoreState(p, &saved);
    return result;
}

/// Parse statements until the specified ending token is encountered.
///
/// Returns the completed immutable statement list.
export unsafe fn parseStmtsUntil(p: &mut Parser, end: scanner::TokenKind, capacity: u32) -> *[*ast::Node]
    throws (ParseError)
{
    let mut statements = ast::nodeSlice(p.arena, capacity);
    while not check(p, end) {
        let stmt = try parseStmt(p);
        statements.append(stmt, p.allocator);

        if check(p, end) or check(p, scanner::TokenKind::Eof) {
            break;
        }
        if not consume(p, scanner::TokenKind::Semicolon) {
            // Only require semicolon if the statement needs one.
            if expectsSemicolon(stmt) {
                throw failParsing(p, "expected `;` after statement");
            }
        }
    }
    return statements;
}

/// Parse a block of statements enclosed in curly braces.
export unsafe fn parseBlock(p: &mut Parser) -> *ast::Node
    throws (ParseError)
{
    return try parseBlockBody(p, false);
}

/// Parse a statement block with the specified unsafe permission.
unsafe fn parseBlockBody(p: &mut Parser, isUnsafe: bool) -> *ast::Node
    throws (ParseError)
{
    let start = p.current;

    if not consume(p, scanner::TokenKind::LBrace) {
        throw failParsing(p, "expected `{`");
    }
    let statements = try parseStmtsUntil(p, scanner::TokenKind::RBrace, 64);
    let blk = ast::Block { statements, isUnsafe };
    try expect(p, scanner::TokenKind::RBrace, "expected `}`");

    return node(p, ast::NodeValue::Block(blk));
}

/// Create a block containing a single statement node.
unsafe fn mkBlockWith(p: &mut Parser, node: *ast::Node) -> ast::Block {
    let stmts = ast::nodeSlice(p.arena, 1).append(node, p.allocator);
    return ast::Block { statements: stmts, isUnsafe: false };
}

/// Parse the branch that follows `else` in let-else style constructs.
///
/// Allows either a block, a single statement like `return`,
/// or a standalone expression which is returned directly.
unsafe fn parseLetElseBranch(p: &mut Parser) -> *ast::Node
    throws (ParseError)
{
    if check(p, scanner::TokenKind::LBrace) {
        return try parseBlock(p);
    }
    let branch = try parseStmt(p);

    if let case ast::NodeValue::ExprStmt(expr) = branch.value {
        return expr;
    }
    return branch;
}

/// Allocate a new node from the parser's arena.
unsafe fn node(p: &mut Parser, value: ast::NodeValue) -> *mut ast::Node {
    let span = ast::Span {
        offset: p.previous.offset,
        length: p.previous.source.len,
    };
    let n = ast::allocNode(p.arena, span, value);
    finishSpan(p, n);

    return n;
}

/// Update the span of `node` using the most recently consumed token.
fn finishSpan(p: &mut Parser, node: &mut ast::Node) {
    let start: u32 = node.span.offset;
    let mut end: u32 = p.previous.offset + p.previous.source.len;

    if end >= start {
        set node.span.length = end - start;
    } else {
        set node.span.length = 0;
    }
}

/// Save parser state for speculative parsing.
unsafe fn saveState(p: &Parser) -> SavedState {
    return SavedState {
        parser: *p,
        arena: alloc::save(&p.arena.arena),
        nextId: p.arena.nextId,
    };
}

/// Restore scanner state, diagnostics, arena storage, and node identifiers.
/// Tentative nodes must be unreachable from all state retained by the caller.
/// Interned tokens retain source storage, which must outlive the string pool.
unsafe fn restoreState(p: &mut Parser, s: &SavedState) {
    set *p = s.parser;
    alloc::restore(&mut p.arena.arena, s.arena);
    set p.arena.nextId = s.nextId;
}

/// Report a parser error.
fn reportError(p: &mut Parser, token: scanner::Token, message: *[u8]) {
    assert message.len > 0;

    // Ignore errors once the error list is full.
    if p.errors.count < p.errors.list.len {
        set p.errors.list[p.errors.count] = Error { message, token };
        set p.errors.count += 1;
    }
}

/// Fail the parsing process with the given error.
fn failParsing(p: &mut Parser, err: *[u8]) -> ParseError {
    let token = p.current;
    reportError(p, token, err);
    return ParseError::UnexpectedToken;
}

/// Print all errors that have been collected during parsing.
export fn printErrors(p: &Parser) {
    for i in 0..p.errors.count {
        let e = p.errors.list[i];
        if let loc = scanner::getLocation(
            p.scanner.sourceLoc, p.scanner.source, e.token.offset
        ) {
            if let case scanner::SourceLoc::File(path) = loc.source {
                io::print(path);
                io::print(":");
            }
            io::printU32(loc.line as u32);
            io::print(":");
            io::printU32(loc.col as u32);
            io::print(": error: ");
        } else {
            io::print("error: ");
        }
        io::print(e.message);
        if e.token.kind == scanner::TokenKind::Invalid {
            io::print(": ");
            io::print(e.token.source);
        } else {
            io::print(", got `");
            io::print(e.token.source);
            io::print("`");
        }
        io::print("\n");
    }
}

/// Check whether the current token matches the expected kind.
export fn check(p: &Parser, kind: scanner::TokenKind) -> bool {
    return p.current.kind == kind;
}

/// Advance the parser by one token.
export unsafe fn advance(p: &mut Parser) {
    set p.previous = p.current;
    set p.current = scanner::next(&mut p.scanner);
}

/// Parse an `if let` pattern matching statement.
///
/// Syntax: `if let binding = scrutinee { ... }`
/// Syntax: `if let mut binding = scrutinee { ... }`
unsafe fn parseIfLet(p: &mut Parser) -> *ast::Node throws (ParseError) {
    try expect(p, scanner::TokenKind::Let, "expected `let`");

    // Parse pattern: either `case <pattern>`, `mut <ident>`, or simple `<ident>`.
    let mut pattern: *ast::Node = undefined;
    let mut kind = ast::PatternKind::Binding;
    let mut mutable = false;

    if consume(p, scanner::TokenKind::Case) {
        set pattern = try parseMatchPattern(p);
        set kind = ast::PatternKind::Case;
    } else {
        set mutable = consume(p, scanner::TokenKind::Mut);
        set pattern = try parseIdentOrPlaceholder(p, "expected `case`, `mut`, or identifier after `let`");
    }
    try expect(p, scanner::TokenKind::Equal, "expected `=` after pattern");

    let scrutinee = try parseCond(p);
    let mut guard: ?*ast::Node = nil;

    if consume(p, scanner::TokenKind::Semicolon) {
        set guard = try parseCond(p);
    }
    let thenBranch = try parseBlock(p);
    let mut elseBranch: ?*ast::Node = nil;

    if consume(p, scanner::TokenKind::Else) {
        if check(p, scanner::TokenKind::If) {
            set elseBranch = node(p, ast::NodeValue::Block(
                mkBlockWith(p, try parseIf(p))
            ));
        } else {
            set elseBranch = try parseBlock(p);
        }
    }

    return node(p, ast::NodeValue::IfLet(ast::IfLet {
        pattern: ast::PatternMatch { pattern, scrutinee, guard, kind, mutable },
        thenBranch,
        elseBranch,
    }));
}

/// Parse a `while let` statement.
unsafe fn parseWhileLet(p: &mut Parser) -> *ast::Node
    throws (ParseError)
{
    try expect(p, scanner::TokenKind::Let, "expected `let`");

    // Parse pattern: either `case <pattern>`, `mut <ident>`, or simple `<ident>`.
    let mut pattern: *ast::Node = undefined;
    let mut kind = ast::PatternKind::Binding;
    let mut mutable = false;
    if consume(p, scanner::TokenKind::Case) {
        set pattern = try parseMatchPattern(p);
        set kind = ast::PatternKind::Case;
    } else {
        set mutable = consume(p, scanner::TokenKind::Mut);
        set pattern = try parseIdentOrPlaceholder(p, "expected `case`, `mut`, or identifier after `let`");
    }
    try expect(p, scanner::TokenKind::Equal, "expected `=` after pattern");

    let scrutinee = try parseCond(p);
    let mut guard: ?*ast::Node = nil;

    if consume(p, scanner::TokenKind::Semicolon) {
        set guard = try parseCond(p);
    }
    let body = try parseBlock(p);
    let mut elseBranch: ?*ast::Node = nil;

    if consume(p, scanner::TokenKind::Else) {
        set elseBranch = try parseBlock(p);
    }
    return node(p, ast::NodeValue::WhileLet(ast::WhileLet {
        pattern: ast::PatternMatch { pattern, scrutinee, guard, kind, mutable },
        body,
        elseBranch,
    }));
}

/// Parse a `while` statement.
unsafe fn parseWhile(p: &mut Parser) -> *ast::Node
    throws (ParseError)
{
    try expect(p, scanner::TokenKind::While, "expected `while`");

    // Check for `while let` or `while let case` syntax.
    if check(p, scanner::TokenKind::Let) {
        return try parseWhileLet(p);
    }
    let condition = try parseCond(p);
    let body = try parseBlock(p);
    let mut elseBranch: ?*ast::Node = nil;

    if consume(p, scanner::TokenKind::Else) {
        set elseBranch = try parseBlock(p);
    }
    return node(p, ast::NodeValue::While(ast::While {
        condition, body, elseBranch,
    }));
}

/// Parse a `loop` statement.
unsafe fn parseLoop(p: &mut Parser) -> *ast::Node
    throws (ParseError)
{
    try expect(p, scanner::TokenKind::Loop, "expected `loop`");
    let body = try parseBlock(p);

    return node(p, ast::NodeValue::Loop { body });
}

/// Parse a `for` statement.
unsafe fn parseFor(p: &mut Parser) -> *ast::Node
    throws (ParseError)
{
    try expect(p, scanner::TokenKind::For, "expected `for`");

    let binding = try parseIdentOrPlaceholder(p, "expected identifier or `_`");
    let mut index: ?*ast::Node = nil;

    if consume(p, scanner::TokenKind::Comma) {
        set index = try parseIdentOrPlaceholder(p, "expected index identifier or `_` after `,`");
    }
    try expect(p, scanner::TokenKind::In, "expected `in`");

    let iterable = try parseCond(p);
    let body = try parseBlock(p);
    let mut elseBranch: ?*ast::Node = nil;

    if consume(p, scanner::TokenKind::Else) {
        set elseBranch = try parseBlock(p);
    }
    return node(p, ast::NodeValue::For(ast::For {
        binding, index, iterable, body, elseBranch,
    }));
}

/// Parse a `return` statement.
unsafe fn parseReturn(p: &mut Parser) -> *ast::Node
    throws (ParseError)
{
    try expect(p, scanner::TokenKind::Return, "expected `return`");

    // Speculatively try to parse a return value expression.
    let saved = saveState(p);
    let value: ?*ast::Node = try? parseExpr(p);
    if value == nil {
        restoreState(p, &saved);
    }
    return node(p, ast::NodeValue::Return { value });
}

/// Parse a `throw` statement.
unsafe fn parseThrow(p: &mut Parser) -> *ast::Node
    throws (ParseError)
{
    try expect(p, scanner::TokenKind::Throw, "expected `throw`");
    let expr = try parseExpr(p);

    return node(p, ast::NodeValue::Throw { expr });
}

/// Parse a `panic` statement.
unsafe fn parsePanic(p: &mut Parser) -> *ast::Node
    throws (ParseError)
{
    try expect(p, scanner::TokenKind::Panic, "expected `panic`");

    // `panic { expr }`.
    if consume(p, scanner::TokenKind::LBrace) {
        let message: ?*ast::Node = try parseExpr(p);
        try expect(p, scanner::TokenKind::RBrace, "expected closing `}` after expression");
        return node(p, ast::NodeValue::Panic { message });
    }
    // `panic` or `panic "message"`.
    let saved = saveState(p);
    let message: ?*ast::Node = try? parseExpr(p);
    if message == nil {
        restoreState(p, &saved);
    }
    return node(p, ast::NodeValue::Panic { message });
}

/// Parse an `assert` statement.
///
/// Forms:
///   `assert <expr>`
///   `assert <expr>, "message"`
///   `assert { <expr> }, "message"`
unsafe fn parseAssert(p: &mut Parser) -> *ast::Node
    throws (ParseError)
{
    try expect(p, scanner::TokenKind::Assert, "expected `assert`");

    // `assert { expr }` block form or `assert <expr>`.
    let mut condition: *ast::Node = undefined;
    if consume(p, scanner::TokenKind::LBrace) {
        set condition = try parseExpr(p);
        try expect(p, scanner::TokenKind::RBrace, "expected closing `}` after expression");
    } else {
        set condition = try parseExpr(p);
    }
    let mut message: ?*ast::Node = nil;
    if consume(p, scanner::TokenKind::Comma) {
        set message = try parseExpr(p);
    }
    return node(p, ast::NodeValue::Assert { condition, message });
}

/// Parse a `try` expression with optional `catch` clause(s).
unsafe fn parseTryExpr(p: &mut Parser) -> *ast::Node
    throws (ParseError)
{
    try expect(p, scanner::TokenKind::Try, "expected `try`");

    let shouldPanic = consume(p, scanner::TokenKind::Bang);
    let returnsOptional = consume(p, scanner::TokenKind::Question);
    let expr = try parseUnaryExpr(p);
    let mut catches = ast::nodeSlice(p.arena, 4);

    while consume(p, scanner::TokenKind::Catch) {
        let mut binding: ?*ast::Node = nil;
        let mut typeNode: ?*ast::Node = nil;

        // Check for optional error binding: `catch ident { ... }` or
        // `catch ident as Type { ... }`.
        if check(p, scanner::TokenKind::Ident) {
            set binding = try parseIdent(p, "expected identifier after `catch`");
            if consume(p, scanner::TokenKind::As) {
                set typeNode = try parseType(p);
            }
        }
        if not check(p, scanner::TokenKind::LBrace) {
            throw failParsing(p, "expected `{` after `catch`");
        }
        let body = try parseBlock(p);
        let clause = node(p, ast::NodeValue::CatchClause(
            ast::CatchClause { binding, typeNode, body }
        ));
        catches.append(clause, p.allocator);
    }
    return node(p, ast::NodeValue::Try(
        ast::Try { expr, catches, shouldPanic, returnsOptional }
    ));
}

/// Parse an `if` expression, with optional `else` or `else if` clauses.
///
/// The `else if` construct is handled by creating a recursive structure:
/// 1. When an `else` is followed by an `if`, we create a new block node.
/// 2. We parse the nested `if` statement recursively using `parseIf`.
/// 3. We put this nested `if` statement inside the block node.
/// 4. This block node becomes the `elseBranch` of the parent `if`.
///
/// This approach naturally handles multiple `else if` chains through recursion.
///
/// For example:
///   if x {
///       a
///   } else if y {
///       b
///   } else if z {
///       c
///   } else {
///       d
///   }
///
/// Is represented as a nested structure like:
///
///   if x {
///       a
///   } else {
///       if y {
///           b
///       } else {
///           if z {
///               c
///           } else {
///               d
///           }
///       }
///   }
///
unsafe fn parseIf(p: &mut Parser) -> *ast::Node throws (ParseError) {
    try expect(p, scanner::TokenKind::If, "expected `if`");

    // Check for `if let` or `if let case` syntax.
    if check(p, scanner::TokenKind::Let) {
        return try parseIfLet(p);
    }
    // Regular if statement.
    let cond = try parseCond(p);
    let thenBranch = try parseBlock(p);
    let mut elseBranch: ?*ast::Node = nil;

    if consume(p, scanner::TokenKind::Else) {
        // Check for `else if` construct.
        if check(p, scanner::TokenKind::If) {
            // Set the else branch to a block containing the nested if.
            set elseBranch = node(p, ast::NodeValue::Block(
                mkBlockWith(p, try parseIf(p))
            ));
        } else {
            // Regular else clause.
            set elseBranch = try parseBlock(p);
        }
    }
    return node(p, ast::NodeValue::If(ast::If {
        condition: cond, thenBranch, elseBranch,
    }));
}

/// Parse a `match` statement.
unsafe fn parseMatch(p: &mut Parser) -> *ast::Node
    throws (ParseError)
{
    try expect(p, scanner::TokenKind::Match, "expected `match`");

    let subject = try parseCond(p);
    try expect(p, scanner::TokenKind::LBrace, "expected `{` before match prongs");

    let mut prongs = ast::nodeSlice(p.arena, 128);
    while not check(p, scanner::TokenKind::RBrace) and
          not check(p, scanner::TokenKind::Eof) // TODO: We shouldn't have to manually check for EOF.
    {
        let prongNode = try parseMatchProng(p);
        prongs.append(prongNode, p.allocator);
        consume(p, scanner::TokenKind::Comma);
    }
    try expect(p, scanner::TokenKind::RBrace, "expected `}` after match prongs");

    return node(p, ast::NodeValue::Match(
        ast::Match { subject, prongs }
    ));
}

/// Parse a single `match` prong.
unsafe fn parseMatchProng(p: &mut Parser) -> *ast::Node
    throws (ParseError)
{
    let mut guard: ?*ast::Node = nil;

    // Case prong: `case <pattern>, ... if <guard> => <body>`.
    if consume(p, scanner::TokenKind::Case) {
        let mut patterns = ast::nodeSlice(p.arena, 16);
        loop {
            let pattern = try parseMatchPattern(p);
            patterns.append(pattern, p.allocator);

            if not consume(p, scanner::TokenKind::Comma) {
                break;
            }
            // After a comma, check for tokens that start a new prong.
            // This catches mistakes like `case A, case B`.
            if check(p, scanner::TokenKind::Case) or check(p, scanner::TokenKind::Else) {
                throw failParsing(p, "unexpected keyword after `,` in case pattern list");
            }
        }
        if consume(p, scanner::TokenKind::If) {
            set guard = try parseCond(p);
        }
        try expect(p, scanner::TokenKind::FatArrow, "expected `=>` after case pattern");
        let body = try parseStmt(p);

        return node(p, ast::NodeValue::MatchProng(
            ast::MatchProng { arm: ast::ProngArm::Case(patterns), guard, body }
        ));
    }
    // Else prong: `else if <guard> => <body>`.
    if consume(p, scanner::TokenKind::Else) {
        if consume(p, scanner::TokenKind::If) {
            set guard = try parseCond(p);
        }
        try expect(p, scanner::TokenKind::FatArrow, "expected `=>` after else");
        let body = try parseStmt(p);

        return node(p, ast::NodeValue::MatchProng(
            ast::MatchProng { arm: ast::ProngArm::Else, guard, body }
        ));
    }
    // Binding prong: `<ident> if <guard> => <body>` or `_ if <guard> => <body>`.
    let binding = try parseIdentOrPlaceholder(p, "expected `case`, `else`, or identifier");

    if consume(p, scanner::TokenKind::If) {
        set guard = try parseCond(p);
    }
    try expect(p, scanner::TokenKind::FatArrow, "expected `=>` after binding");
    let body = try parseStmt(p);

    return node(p, ast::NodeValue::MatchProng(
        ast::MatchProng { arm: ast::ProngArm::Binding(binding), guard, body }
    ));
}

/// Parse a pattern expression used by `case` constructs.
/// Uses `Pattern` context to allow record literals but not conditional expressions.
unsafe fn parseMatchPattern(p: &mut Parser) -> *ast::Node
    throws (ParseError)
{
    let saved = p.context;
    set p.context = Context::Pattern;
    let pattern = try parseExpr(p);
    set p.context = saved;

    return pattern;
}

/// Parse a region name.
unsafe fn parseRegion(p: &mut Parser) -> *ast::Node throws (ParseError) {
    let name = try expect(p, scanner::TokenKind::Region, "expected region name");
    return node(p, ast::NodeValue::Region { name, parent: nil });
}

/// Parse consecutive region names.
unsafe fn parseRegions(p: &mut Parser) -> *mut [*ast::Node] throws (ParseError) {
    let mut regions = ast::nodeSlice(p.arena, 4);
    while check(p, scanner::TokenKind::Region) {
        regions.append(try parseRegion(p), p.allocator);
    }
    return regions;
}

/// Parse region bounds for a declaration.
unsafe fn parseRegionBounds(p: &mut Parser, regions: &mut [*ast::Node])
    throws (ParseError)
{
    if not consume(p, scanner::TokenKind::Where) {
        return;
    }
    loop {
        let parent = try parseRegion(p);
        try expect(p, scanner::TokenKind::Colon, "expected `:` in region bound");
        let childName = try expect(p, scanner::TokenKind::Region, "expected region name");
        let mut matched = false;
        for i in 0..regions.len {
            let region = regions[i];
            if let case ast::NodeValue::Region { name, parent: declaredParent } = region.value;
                mem::eq(name, childName)
            {
                if declaredParent <> nil {
                    throw failParsing(p, "region parameter already has a bound");
                }
                set regions[i] = node(p, ast::NodeValue::Region { name, parent });
                set matched = true;
                break;
            }
        }
        if not matched {
            throw failParsing(p, "expected declared region parameter in bound");
        }
        if not consume(p, scanner::TokenKind::Comma) {
            break;
        }
    }
}

/// Parse scoped borrow bindings.
unsafe fn parseRegionBlock(p: &mut Parser) -> *ast::Node throws (ParseError) {
    advance(p);
    let mut binding = try parseIdent(p, "expected region binding name");
    try expect(p, scanner::TokenKind::Colon, "expected `:` after region binding");
    let regionName = try expect(p, scanner::TokenKind::Region, "expected region name after `:`");
    let mut region = node(p, ast::NodeValue::Region { name: regionName, parent: nil });
    let mut bindings = ast::nodeSlice(p.arena, 4);
    loop {
        try expect(p, scanner::TokenKind::Equal, "expected `=` after region binding");
        try expect(p, scanner::TokenKind::Amp, "expected `&` before borrowed place");
        let kind = parseAddressKind(p);
        let target = try parseUnaryExpr(p);
        let value = node(p, ast::NodeValue::AddressOf({ target, kind }));
        bindings.append(node(p, ast::NodeValue::RegionBinding({ label: binding, value })), p.allocator);
        if not consume(p, scanner::TokenKind::Comma) {
            break;
        }
        set binding = try parseIdent(p, "expected region binding name");
    }
    if consume(p, scanner::TokenKind::Where) {
        let parent = try parseRegion(p);
        try expect(p, scanner::TokenKind::Colon, "expected `:` in region bound");
        let childName = try expect(p, scanner::TokenKind::Region, "expected child region in bound");
        if not mem::eq(regionName, childName) {
            throw failParsing(p, "region bound must name the declared region");
        }
        set region = node(p, ast::NodeValue::Region { name: regionName, parent });
    }
    try expect(p, scanner::TokenKind::In, "expected `in` after region bindings");
    let body = try parseBlock(p);
    return node(p, ast::NodeValue::RegionBlock { region, bindings, body, isSession: false });
}

/// Create a region name from an allocation-session binding name.
unsafe fn sessionRegion(p: &mut Parser, binding: *ast::Node) -> *ast::Node {
    let case ast::NodeValue::Ident(name) = binding.value
        else panic "sessionRegion: invalid binding";
    let len = name.len + 1;
    let buf = alloc::remainingBuf(&mut p.arena.arena);
    assert buf.len >= len, "sessionRegion: node arena is full";
    set buf[0] = 39;
    try! mem::copy(&mut buf[1..len], name);
    alloc::commit(&mut p.arena.arena, len);
    return node(p, ast::NodeValue::Region { name: &buf[..len], parent: nil });
}

/// Parse an allocation session with an implicit exclusive source borrow.
unsafe fn parseSessionBlock(p: &mut Parser) -> *ast::Node throws (ParseError) {
    try expect(p, scanner::TokenKind::Use, "expected `use`");
    let target = try parseUnaryExpr(p);
    let value = node(p, ast::NodeValue::AddressOf({ target, kind: ast::AddressKind::Mutable }));
    try expect(p, scanner::TokenKind::As, "expected `as` after allocation source");
    let binding = try parseIdent(p, "expected allocation binding after `as`");
    let region = sessionRegion(p, binding);
    try expect(p, scanner::TokenKind::In, "expected `in` after allocation binding");
    let bindings = ast::nodeSlice(p.arena, 1).append(
        node(p, ast::NodeValue::RegionBinding({ label: binding, value })),
        p.allocator,
    );
    let body = try parseBlock(p);
    return node(p, ast::NodeValue::RegionBlock { region, bindings, body, isSession: true });
}

/// Parse an identifier.
unsafe fn parseIdent(p: &mut Parser, err: *[u8]) -> *ast::Node
    throws (ParseError)
{
    let source = try expect(p, scanner::TokenKind::Ident, err);
    return node(p, ast::NodeValue::Ident(source));
}

/// Parse either an identifier or a placeholder (`_`).
unsafe fn parseIdentOrPlaceholder(p: &mut Parser, err: *[u8]) -> *ast::Node
    throws (ParseError)
{
    if consume(p, scanner::TokenKind::Underscore) {
        return node(p, ast::NodeValue::Placeholder);
    }
    return try parseIdent(p, err);
}

/// Parse an alignment specifier.
///
/// Syntax: `align(N)` where N is a power of 2.
unsafe fn parseAlign(p: &mut Parser) -> *ast::Node
    throws (ParseError)
{
    try expect(p, scanner::TokenKind::Align, "expected `align`");
    let value = try parseParenthesized(p);
    return node(p, ast::NodeValue::Align { value });
}

/// Parse a comma-separated list of record fields.
/// The opening delimiter should already be consumed.
/// For labeled fields: `{ name: T, ... }`.
/// For unlabeled fields: `(T, T, ...)`.
unsafe fn parseRecordFields(
    p: &mut Parser,
    mode: RecordFieldMode
) -> *mut [*ast::Node]
    throws (ParseError)
{
    let terminator = scanner::TokenKind::RBrace if mode == RecordFieldMode::Labeled
        else scanner::TokenKind::RParen;
    let mut fields = ast::nodeSlice(p.arena, MAX_RECORD_FIELDS);
    while not check(p, terminator) {
        let mut recordField: ast::NodeValue = undefined;
        match mode {
            case RecordFieldMode::Labeled => {
                // Allow optional `let` keyword before field name.
                consume(p, scanner::TokenKind::Let);

                let field = try parseNameTypeValue(p);
                let type = field.type else {
                    throw failParsing(p, "expected type annotation in record field");
                };
                if field.alignment <> nil {
                    throw failParsing(p, "record fields cannot specify alignment");
                }
                if field.value <> nil and mode <> RecordFieldMode::Labeled {
                    throw failParsing(p, "record fields cannot have initializers");
                }
                set recordField = ast::NodeValue::RecordField {
                    field: field.name, type, value: field.value,
                };
            }
            case RecordFieldMode::Unlabeled => {
                let type = try parseType(p);
                set recordField = ast::NodeValue::RecordField {
                    field: nil, type, value: nil,
                };
            }
        }
        fields.append(node(p, recordField), p.allocator);

        if not consume(p, scanner::TokenKind::Comma) {
            break;
        }
    }
    try expect(p, terminator, "expected closing delimiter after record fields");

    return fields;
}

/// Parse an optional declaration list and separate regions from derives.
unsafe fn parseNominalClauses(
    p: &mut Parser,
    regions: &mut *mut [*ast::Node],
    derives: &mut *mut [*ast::Node],
) throws (ParseError) {
    if not consume(p, scanner::TokenKind::Colon) {
        return;
    }
    set *regions = ast::nodeSlice(p.arena, 4);
    set *derives = ast::nodeSlice(p.arena, 4);
    loop {
        if check(p, scanner::TokenKind::Region) {
            regions.append(try parseRegion(p), p.allocator);
        } else {
            derives.append(
                try parseIdent(p, "expected region or trait name in declaration list"),
                p.allocator,
            );
        }

        if not consume(p, scanner::TokenKind::Plus) {
            break;
        }
    }
}

/// Parse an optional list of trait names.
unsafe fn parseDerives(p: &mut Parser) -> *mut [*ast::Node] throws (ParseError) {
    if not consume(p, scanner::TokenKind::Colon) {
        return &mut [];
    }
    let mut derives = ast::nodeSlice(p.arena, 4);
    loop {
        derives.append(try parseIdent(p, "expected trait name"), p.allocator);
        if not consume(p, scanner::TokenKind::Plus) {
            break;
        }
    }
    return derives;
}

/// Parse a single record literal field.
/// Can be either labeled, or shorthand.
unsafe fn parseRecordLitField(p: &mut Parser) -> *ast::Node
    throws (ParseError)
{
    let name = try parseIdent(p, "expected field name");
    if consume(p, scanner::TokenKind::Colon) {
        // Labeled field: `name: value`.
        let value = try parseExpr(p);
        return node(p, ast::NodeValue::RecordLitField(
            ast::Arg { label: name, value }
        ));
    }
    // Shorthand syntax: `{ x }` is equivalent to `{ x: x }`.
    return node(p, ast::NodeValue::RecordLitField(
        ast::Arg { label: name, value: name }
    ));
}

/// Parse a record literal body.
/// Eg. `{ x: 1, y: 2 }`
/// Eg. `{ x: 1, .. }`
unsafe fn parseRecordLit(p: &mut Parser, typeName: ?*ast::Node) -> *ast::Node
    throws (ParseError)
{
    let mut fields = ast::nodeSlice(p.arena, MAX_RECORD_FIELDS);
    let mut ignoreRest = false;
    try expect(p, scanner::TokenKind::LBrace, "expected `{` to begin record literal");

    while not check(p, scanner::TokenKind::RBrace) {
        // Check for `..` to ignore remaining fields.
        if consume(p, scanner::TokenKind::DotDot) {
            set ignoreRest = true;
            break;
        }
        let field = try parseRecordLitField(p);
        fields.append(field, p.allocator);

        if not consume(p, scanner::TokenKind::Comma) {
            break;
        }
    }
    try expect(p, scanner::TokenKind::RBrace, "expected `}` to end record literal");

    return node(p, ast::NodeValue::RecordLit(
        ast::RecordLit { typeName, fields, ignoreRest }
    ));
}

/// Parse a named record declaration.
/// `record Point { x: i32, y: i32 }`, or `record Pair(i32, i32);`
unsafe fn parseRecordDecl(p: &mut Parser, attrs: ?ast::Attributes) -> *ast::Node
    throws (ParseError)
{
    try expect(p, scanner::TokenKind::Record, "expected `record`");

    let name = try parseIdent(p, "expected record name");
    let mut regions: *mut [*ast::Node] = &mut [];
    let mut derives: *mut [*ast::Node] = &mut [];
    try parseNominalClauses(p, &mut regions, &mut derives);
    try parseRegionBounds(p, &mut regions[..]);

    if consume(p, scanner::TokenKind::LParen) {
        let fields = try parseRecordFields(p, RecordFieldMode::Unlabeled);
        try expect(p, scanner::TokenKind::Semicolon, "expected `;` after record");
        return node(p, ast::NodeValue::RecordDecl(
            ast::RecordDecl {
                name, fields, attrs, regions, derives, labeled: false,
            }
        ));
    } else {
        try expect(p, scanner::TokenKind::LBrace, "expected `{` before record body");
        let fields = try parseRecordFields(p, RecordFieldMode::Labeled);
        return node(p, ast::NodeValue::RecordDecl(
            ast::RecordDecl {
                name, fields, attrs, regions, derives, labeled: true,
            }
        ));
    }
}

/// Parse a union declaration.
/// Example: `union Color { Red, Green, Blue = 5 }`
unsafe fn parseUnionDecl(p: &mut Parser, attrs: ?ast::Attributes) -> *ast::Node
    throws (ParseError)
{
    try expect(p, scanner::TokenKind::Union, "expected `union`");

    let name = try parseIdent(p, "expected union name");
    let mut regions: *mut [*ast::Node] = &mut [];
    let mut derives: *mut [*ast::Node] = &mut [];
    try parseNominalClauses(p, &mut regions, &mut derives);
    try parseRegionBounds(p, &mut regions[..]);

    try expect(p, scanner::TokenKind::LBrace, "expected `{` before union body");

    let mut variants = ast::nodeSlice(p.arena, 128);
    while not check(p, scanner::TokenKind::RBrace) {
        // Allow optional `case` keyword before variant name.
        consume(p, scanner::TokenKind::Case);

        let variantName = try parseIdent(p, "expected variant name");
        let mut payloadType: ?*ast::Node = nil;
        let mut explicitValue: ?*ast::Node = nil;

        if consume(p, scanner::TokenKind::LParen) { // `Variant(T, U)`.
            let fields = try parseRecordFields(p, RecordFieldMode::Unlabeled);
            set payloadType = node(p, ast::NodeValue::TypeSig(
                ast::TypeSig::Record { fields, labeled: false }
            ));
        } else if consume(p, scanner::TokenKind::LBrace) { // `Variant { x: T, y: T }`.
            let fields = try parseRecordFields(p, RecordFieldMode::Labeled);
            set payloadType = node(p, ast::NodeValue::TypeSig(
                ast::TypeSig::Record { fields, labeled: true }
            ));
        } else if consume(p, scanner::TokenKind::Equal) {
            // TODO: Support constant expressions.
            try expect(p, scanner::TokenKind::Number, "expected integer literal after `=`");
            let source = p.previous.source;
            let literal = try parseIntLiteral(p, source);
            set explicitValue = nodeNumber(p, literal);
        }

        let variant = node(p, ast::NodeValue::UnionDeclVariant(
            ast::UnionDeclVariant {
                name: variantName, index: variants.len as u32, value: explicitValue, type: payloadType,
            }
        ));
        variants.append(variant, p.allocator);

        if not consume(p, scanner::TokenKind::Comma) {
            break;
        }
    }
    try expect(p, scanner::TokenKind::RBrace, "expected `}`");

    return node(p, ast::NodeValue::UnionDecl(
        ast::UnionDecl {
            name, variants, attrs, regions, derives,
        }
    ));
}

/// Parse a function parameter.
unsafe fn parseFnParam(p: &mut Parser) -> *ast::Node
    throws (ParseError)
{
    let ntv = try parseNameTypeValue(p);
    let type = ntv.type
        else throw failParsing(p, "missing type in function parameter");

    return node(p, ast::NodeValue::FnParam(
        ast::FnParam { name: ntv.name, type }
    ));
}

/// Parse an optional `throws` clause and return the collected type list.
unsafe fn parseThrowList(p: &mut Parser) -> *mut [*ast::Node]
    throws (ParseError)
{
    if not consume(p, scanner::TokenKind::Throws) {
        return ast::nodeSlice(p.arena, 0);
    }
    return try parseList(
        p,
        scanner::TokenKind::LParen,
        scanner::TokenKind::RParen,
        parseType
    );
}

/// Parse a function type signature.
unsafe fn parseFnType(p: &mut Parser) -> *ast::Node
    throws (ParseError)
{
    let isUnsafe = consume(p, scanner::TokenKind::Unsafe);
    try expect(p, scanner::TokenKind::Fn, "expected `fn`");
    let params = try parseList(
        p,
        scanner::TokenKind::LParen,
        scanner::TokenKind::RParen,
        parseType
    );
    let mut returnType: ?*ast::Node = nil;

    if consume(p, scanner::TokenKind::Arrow) {
        set returnType = try parseReturnType(p);
    }
    let throwList = try parseThrowList(p);
    let sig = ast::FnSig { params, returnType, throwList };
    return node(p, ast::NodeValue::TypeSig(
        ast::TypeSig::Fn { sig, isUnsafe }
    ));
}

/// Parse a function signature following the function name.
unsafe fn parseFnTypeSig(p: &mut Parser) -> ast::FnSig
    throws (ParseError)
{
    try expect(p, scanner::TokenKind::LParen, "expected `(` after function name");
    let mut params = ast::nodeSlice(p.arena, 8);

    while not check(p, scanner::TokenKind::RParen) {
        let param = try parseFnParam(p);
        params.append(param, p.allocator);

        if not consume(p, scanner::TokenKind::Comma) {
            break;
        }
    }
    try expect(p, scanner::TokenKind::RParen, "expected `)` after function parameters");

    let mut returnType: ?*ast::Node = nil;
    if consume(p, scanner::TokenKind::Arrow) {
        set returnType = try parseReturnType(p);
    }
    let throwList = try parseThrowList(p);

    return ast::FnSig { params, returnType, throwList };
}

/// Parse a function return type, including the uninhabited type.
unsafe fn parseReturnType(p: &mut Parser) -> *ast::Node throws (ParseError) {
    if consume(p, scanner::TokenKind::Bang) {
        return node(p, ast::NodeValue::TypeSig(ast::TypeSig::Never));
    }
    return try parseType(p);
}

/// Parse a function declaration.
unsafe fn parseFnDecl(p: &mut Parser, attrs: ?ast::Attributes) -> *ast::Node
    throws (ParseError)
{
    try expect(p, scanner::TokenKind::Fn, "expected `fn`");

    // Method syntax: `fn (recv: *Type) name(params) { body }`.
    if check(p, scanner::TokenKind::LParen) {
        return try parseMethodDecl(p, attrs);
    }
    let name = try parseIdent(p, "expected function name");
    let regions = try parseRegions(p);
    let sig = try parseFnTypeSig(p);
    try parseRegionBounds(p, &mut regions[..]);
    let mut body: ?*ast::Node = nil;
    let mut fnAttrs = attrs;

    if consume(p, scanner::TokenKind::Semicolon) {
        if let a = attrs; ast::attributesContains(&a, ast::Attribute::Extern) {
            // Keep existing attributes unchanged.
        } else {
            let mut list = ast::nodeSlice(p.arena, 4);
            if let a = attrs {
                for i in 0..a.list.len {
                    list.append(a.list[i], p.allocator);
                }
            }
            let attrNode = nodeAttribute(p, ast::Attribute::Extern);
            list.append(attrNode, p.allocator);
            set fnAttrs = ast::Attributes { list };
        }
    } else {
        set body = try parseBlock(p);
    }
    return node(p, ast::NodeValue::FnDecl(
        ast::FnDecl { name, regions, sig, body, attrs: fnAttrs }
    ));
}

/// Parse a pointer-like type after its ownership prefix.
unsafe fn parsePointerLikeType(
    p: &mut Parser,
    class: ast::PointerClass,
) -> *ast::Node throws (ParseError) {
    if check(p, scanner::TokenKind::Ident) and mem::eq(p.current.source, "cell") {
        advance(p);
        let payload = try parseType(p);
        return node(p, ast::NodeValue::TypeSig(ast::TypeSig::Cell { class, payload }));
    }
    let mutable = consume(p, scanner::TokenKind::Mut);

    if consume(p, scanner::TokenKind::LBracket) {
        let itemType = try parseType(p);
        try expect(p, scanner::TokenKind::RBracket, "expected `]` after slice element type");

        return node(p, ast::NodeValue::TypeSig(
            ast::TypeSig::Slice { class, itemType, mutable }
        ));
    }
    // Check for an opaque trait object.
    if consume(p, scanner::TokenKind::Opaque) {
        if check(p, scanner::TokenKind::Ident) or check(p, scanner::TokenKind::Super) {
            let traitName = try parseTypePath(p);
            return node(p, ast::NodeValue::TypeSig(
                ast::TypeSig::TraitObject { class, traitName, mutable }
            ));
        }
        // Plain opaque target.
        let valueType = node(p, ast::NodeValue::TypeSig(ast::TypeSig::Opaque));
        return node(p, ast::NodeValue::TypeSig(
            ast::TypeSig::Pointer { class, valueType, mutable }
        ));
    }
    let valueType = try parseType(p);

    return node(p, ast::NodeValue::TypeSig(
        ast::TypeSig::Pointer { class, valueType, mutable }
    ));
}

/// Parse an array type.
unsafe fn parseArrayType(p: &mut Parser) -> *ast::Node
    throws (ParseError)
{
    try expect(p, scanner::TokenKind::LBracket, "expected `[`");
    let itemType = try parseType(p);

    try expect(p, scanner::TokenKind::Semicolon, "expected `;` in array type");
    let length = try parseExpr(p);

    try expect(p, scanner::TokenKind::RBracket, "expected `]` after array length");
    return node(p, ast::NodeValue::TypeSig(
        ast::TypeSig::Array { itemType, length }
    ));
}

/// Parse a type path: an identifier optionally followed by `::` scope access.
/// Returns an identifier node or a scope access chain.
unsafe fn parseTypePath(p: &mut Parser) -> *ast::Node
    throws (ParseError)
{
    let mut path: *ast::Node = undefined;
    if p.current.kind == scanner::TokenKind::Super {
        advance(p);
        set path = nodeSuper(p);
    } else {
        set path = try parseIdent(p, "expected type identifier");
    }
    while consume(p, scanner::TokenKind::ColonColon) {
        let part = try parseIdent(p, "expected identifier after `::`");
        set path = node(p, ast::NodeValue::ScopeAccess(
            ast::Access { parent: path, child: part }
        ));
    }
    return path;
}

/// Parse a type annotation.
export unsafe fn parseType(p: &mut Parser) -> *ast::Node
    throws (ParseError)
{
    match p.current.kind {
        case scanner::TokenKind::Question => {
            advance(p);
            let valueType = try parseType(p);

            return node(p, ast::NodeValue::TypeSig(
                ast::TypeSig::Optional { valueType }
            ));
        }
        case scanner::TokenKind::Star => {
            advance(p);
            let class = ast::PointerClass::Unsafe
                if consume(p, scanner::TokenKind::Unsafe)
                else ast::PointerClass::Owned;
            return try parsePointerLikeType(p, class);
        }
        case scanner::TokenKind::Amp => {
            advance(p);
            let mut region: ?*ast::Node = nil;
            if check(p, scanner::TokenKind::Region) {
                set region = try parseRegion(p);
            }
            let type = try parsePointerLikeType(p, ast::PointerClass::Ref);
            if let r = region {
                return node(p, ast::NodeValue::TypeSig(ast::TypeSig::RegionRef { region: r, type }));
            }
            return type;
        }
        case scanner::TokenKind::LBracket => {
            return try parseArrayType(p);
        }
        case scanner::TokenKind::Super, scanner::TokenKind::Ident => {
            let path = try parseTypePath(p);
            if check(p, scanner::TokenKind::Region) {
                let regions = try parseRegions(p);
                return node(p, ast::NodeValue::TypeSig(ast::TypeSig::Applied { name: path, regions }));
            }
            return node(p, ast::NodeValue::TypeSig(
                ast::TypeSig::Nominal(path)
            ));
        }
        case scanner::TokenKind::U8 => {
            advance(p);
            return nodeTypeInt(p, 1, ast::Signedness::Unsigned);
        }
        case scanner::TokenKind::U16 => {
            advance(p);
            return nodeTypeInt(p, 2, ast::Signedness::Unsigned);
        }
        case scanner::TokenKind::U32 => {
            advance(p);
            return nodeTypeInt(p, 4, ast::Signedness::Unsigned);
        }
        case scanner::TokenKind::U64 => {
            advance(p);
            return nodeTypeInt(p, 8, ast::Signedness::Unsigned);
        }
        case scanner::TokenKind::I8 => {
            advance(p);
            return nodeTypeInt(p, 1, ast::Signedness::Signed);
        }
        case scanner::TokenKind::I16 => {
            advance(p);
            return nodeTypeInt(p, 2, ast::Signedness::Signed);
        }
        case scanner::TokenKind::I32 => {
            advance(p);
            return nodeTypeInt(p, 4, ast::Signedness::Signed);
        }
        case scanner::TokenKind::I64 => {
            advance(p);
            return nodeTypeInt(p, 8, ast::Signedness::Signed);
        }
        case scanner::TokenKind::Bool => {
            advance(p);
            return node(p, ast::NodeValue::TypeSig(ast::TypeSig::Bool));
        }
        case scanner::TokenKind::Opaque => {
            advance(p);
            return node(p, ast::NodeValue::TypeSig(ast::TypeSig::Opaque));
        }
        case scanner::TokenKind::Fn, scanner::TokenKind::Unsafe => {
            return try parseFnType(p);
        }
        else => {
            throw failParsing(p, "expected type");
        }
    }
}

/// Parse a name, optional type, and optional value.
///
/// Used for record field declarations, variable declarations,
/// and record field initializations.
unsafe fn parseNameTypeValue(p: &mut Parser) -> NameTypeValue
    throws (ParseError)
{
    let name = try parseIdentOrPlaceholder(p, "expected identifier or `_`");
    let mut type: ?*ast::Node = nil;
    let mut alignment: ?*ast::Node = nil;
    let mut value: ?*ast::Node = nil;

    if consume(p, scanner::TokenKind::Colon) {
        set type = try parseType(p);

        if check(p, scanner::TokenKind::Align) {
            set alignment = try parseAlign(p);
        }
    }
    if consume(p, scanner::TokenKind::Equal) {
        set value = try parseExpr(p);
    }
    return NameTypeValue { name, type, value, alignment };
}

/// Parse a constant declaration.
unsafe fn parseConst(p: &mut Parser, attrs: ?ast::Attributes) -> *ast::Node
    throws (ParseError)
{
    try expect(p, scanner::TokenKind::Constant, "expected `constant`");

    let ident = try parseIdent(p, "expected identifier in constant declaration");
    try expect(p, scanner::TokenKind::Colon, "expected `:` after identifier");

    let type = try parseType(p);
    try expect(p, scanner::TokenKind::Equal, "expected `=` in constant declaration");

    let value = try parseExpr(p);

    return node(p, ast::NodeValue::ConstDecl(
        ast::ConstDecl { ident, type, value, attrs }
    ));
}

/// Parse a static declaration.
unsafe fn parseStatic(p: &mut Parser, attrs: ?ast::Attributes) -> *ast::Node
    throws (ParseError)
{
    try expect(p, scanner::TokenKind::Static, "expected `static`");

    let ident = try parseIdent(p, "expected identifier in static declaration");
    try expect(p, scanner::TokenKind::Colon, "expected `:` after identifier");

    let type = try parseType(p);
    try expect(p, scanner::TokenKind::Equal, "expected `=` in static declaration");

    let value = try parseExpr(p);

    return node(p, ast::NodeValue::StaticDecl(
        ast::StaticDecl { ident, type, value, attrs }
    ));
}

/// Parse a `use` declaration.
unsafe fn parseUse(p: &mut Parser, attrs: ?ast::Attributes) -> *ast::Node
    throws (ParseError)
{
    try expect(p, scanner::TokenKind::Use, "expected `use`");

    // Allow `super` or identifier as the first part of the path.
    let mut path: *ast::Node = undefined;
    if consume(p, scanner::TokenKind::Super) {
        set path = nodeSuper(p);
    } else {
        set path = try parseIdent(p, "expected module name or `super` after `use`");
    }
    while consume(p, scanner::TokenKind::ColonColon) {
        // Check for wildcard import (e.g., `use parser::*`)
        if consume(p, scanner::TokenKind::Star) {
            return node(p, ast::NodeValue::Use(
                ast::Use { path, wildcard: true, attrs }
            ));
        }
        let part = try parseIdent(p, "expected identifier or `*` after `::`");
        set path = node(p, ast::NodeValue::ScopeAccess(
            ast::Access { parent: path, child: part }
        ));
    }
    return node(p, ast::NodeValue::Use(
        ast::Use { path, wildcard: false, attrs }
    ));
}

/// Parse a `mod` declaration.
unsafe fn parseMod(p: &mut Parser, attrs: ?ast::Attributes) -> *ast::Node
    throws (ParseError)
{
    try expect(p, scanner::TokenKind::Mod, "expected `mod`");
    let name = try parseIdent(p, "expected module name after `mod`");

    return node(p, ast::NodeValue::Mod(
        ast::Mod { name, attrs }
    ));
}

/// Parse a `let case` guard statement.
///
/// Eg. `let case <pattern> = <expr> else { ... };`
/// Eg. `let case <pattern> = <expr> if <guard> else { ... };`
///
/// Expects `let case` tokens to have already been consumed.
unsafe fn parseLetCase(p: &mut Parser) -> *ast::Node throws (ParseError) {
    let pattern = try parseMatchPattern(p);

    try expect(p, scanner::TokenKind::Equal, "expected `=` after pattern");
    let expr = try parseCond(p);

    let mut guard: ?*ast::Node = nil;
    if consume(p, scanner::TokenKind::If) {
        set guard = try parseCond(p);
    }

    try expect(p, scanner::TokenKind::Else, "expected `else` after pattern");
    let elseBranch = try parseLetElseBranch(p);

    return node(p, ast::NodeValue::LetElse(ast::LetElse {
        pattern: ast::PatternMatch { pattern, scrutinee: expr, guard, kind: ast::PatternKind::Case, mutable: false },
        elseBranch,
    }));
}

/// Parse a `let` binding statement.
///
/// Eg. `let <ident> = <expr>;`
/// Eg. `let <ident> = <expr> else { ... };`
/// Eg. `let mut <ident> = <expr> else { ... };`
/// Eg. `let <ident> = <expr> if <guard> else { ... };`
/// Eg. `mut <ident> = <expr>;`
///
/// Expects `let` or `mut` token to have already been consumed.
unsafe fn parseLet(p: &mut Parser, mutable: bool) -> *ast::Node throws (ParseError) {
    let binding = try parseNameTypeValue(p);
    let value = binding.value
        else throw failParsing(p, "expected value initializer");

    // Check for optional `else` clause (let-else).
    if consume(p, scanner::TokenKind::Else) {
        let elseBranch = try parseLetElseBranch(p);

        return node(p, ast::NodeValue::LetElse(ast::LetElse {
            pattern: ast::PatternMatch { pattern: binding.name, scrutinee: value, guard: nil, kind: ast::PatternKind::Binding, mutable },
            elseBranch,
        }));
    }
    return node(p, ast::NodeValue::Let(ast::Let {
        ident: binding.name, type: binding.type, value, alignment: binding.alignment, mutable,
    }));
}

/// Parse a module from source text using the provided arena for node storage.
export unsafe fn parse(sourceLoc: scanner::SourceLoc, input: *[u8], arena: &mut ast::NodeArena, pool: *unsafe mut strings::Pool) -> *mut ast::Node
    throws (ParseError)
{
    let mut p = mkParser(sourceLoc, input, arena, pool);
    return try parseModule(&mut p) catch {
        printErrors(&p);
        throw ParseError::UnexpectedToken;
    };
}

/// Parse a complete module into a block of top-level statements.
///
/// This is the main entry point for parsing an entire Radiance source file.
/// The parser must already be initialized with source code.
export unsafe fn parseModule(p: &mut Parser) -> *mut ast::Node
    throws (ParseError)
{
    advance(p); // Set the parser up with a first token.

    let statements = try parseStmtsUntil(p, scanner::TokenKind::Eof, 512);
    let blk = ast::Block { statements, isUnsafe: false };
    consume(p, scanner::TokenKind::Eof);

    return node(p, ast::NodeValue::Block(blk));
}

/// Consume a token of the given kind if present.
export unsafe fn consume(p: &mut Parser, kind: scanner::TokenKind) -> bool {
    if check(p, kind) {
        advance(p);
        return true;
    }
    return false;
}

/// Expect a token of the given kind or report an error.
export unsafe fn expect(p: &mut Parser, kind: scanner::TokenKind, message: *[u8]) -> *[u8]
    throws (ParseError)
{
    if not consume(p, kind) {
        let token = p.current;
        reportError(p, token, message);
        throw ParseError::UnexpectedToken;
    }
    return p.previous.source;
}

/// Return a generic expectation message for a delimiter token.
fn listExpectMessage(kind: scanner::TokenKind) -> *[u8] {
    match kind {
        case scanner::TokenKind::LParen => return "expected `(`",
        case scanner::TokenKind::RParen => return "expected `)`",
        case scanner::TokenKind::LBracket => return "expected `[`",
        case scanner::TokenKind::RBracket => return "expected `]`",
        case scanner::TokenKind::LBrace => return "expected `{`",
        case scanner::TokenKind::RBrace => return "expected `}`",
        else => return "expected delimiter",
    }
}

/// Parse a trait declaration.
/// Syntax: `trait Name { fn (*Trait) method(...) -> T; ... }`
unsafe fn parseTraitDecl(p: &mut Parser, attrs: ?ast::Attributes) -> *ast::Node
    throws (ParseError)
{
    try expect(p, scanner::TokenKind::Trait, "expected `trait`");
    let name = try parseIdent(p, "expected trait name");
    let supertraits = try parseDerives(p);
    try expect(p, scanner::TokenKind::LBrace, "expected `{` after trait name");

    let mut methods = ast::nodeSlice(p.arena, ast::MAX_TRAIT_METHODS);
    while not check(p, scanner::TokenKind::RBrace) and
          not check(p, scanner::TokenKind::Eof)
    {
        let method = try parseTraitMethodSig(p);
        methods.append(method, p.allocator);
    }
    try expect(p, scanner::TokenKind::RBrace, "expected `}` after trait methods");

    return node(p, ast::NodeValue::TraitDecl { name, supertraits, methods, attrs });
}

/// Parse a trait method signature.
/// Syntax: `fn (*Trait) fnord(<params>) -> ReturnType;`
unsafe fn parseTraitMethodSig(p: &mut Parser) -> *ast::Node
    throws (ParseError)
{
    let attrs = parseAttributes(p);
    try expect(p, scanner::TokenKind::Fn, "expected `fn`");
    try expect(p, scanner::TokenKind::LParen, "expected `(` before receiver");

    let receiver = try parseType(p);

    try expect(p, scanner::TokenKind::RParen, "expected `)` after receiver");

    let name = try parseIdent(p, "expected method name");
    let mut regions = try parseRegions(p);
    let sig = try parseFnTypeSig(p);
    try parseRegionBounds(p, &mut regions[..]);
    try expect(p, scanner::TokenKind::Semicolon, "expected `;` after method signature");

    let modifiers = try! alloc::alloc(
        &mut p.arena.arena, @sizeOf(ast::MethodModifiers), @alignOf(ast::MethodModifiers)
    ) as *mut ast::MethodModifiers;
    set *modifiers = ast::MethodModifiers { regions, attrs };
    return node(p, ast::NodeValue::TraitMethodSig { name, modifiers, receiver, sig });
}

/// Parse an instance block.
/// Syntax: `instance Trait for Type { fn (t: *mut Type) fnord(..) {..} }`
///
/// Instance declarations do not accept attributes (e.g. `export`).
/// Visibility is determined by the trait declaration itself.
unsafe fn parseInstanceDecl(p: &mut Parser) -> *ast::Node
    throws (ParseError)
{
    try expect(p, scanner::TokenKind::Instance, "expected `instance`");
    let traitName = try parseTypePath(p);
    try expect(p, scanner::TokenKind::For, "expected `for` after trait name");
    let targetType = try parseTypePath(p);
    let mut regions = try parseRegions(p);
    try parseRegionBounds(p, &mut regions[..]);
    try expect(p, scanner::TokenKind::LBrace, "expected `{` after target type");

    let mut methods = ast::nodeSlice(p.arena, ast::MAX_TRAIT_METHODS);

    while not check(p, scanner::TokenKind::RBrace) and
          not check(p, scanner::TokenKind::Eof)
    {
        let attrs = parseAttributes(p);
        try expect(p, scanner::TokenKind::Fn, "expected `fn`");
        let method = try parseMethodDecl(p, attrs);

        methods.append(method, p.allocator);
    }
    try expect(p, scanner::TokenKind::RBrace, "expected `}` after instance methods");

    return node(p, ast::NodeValue::InstanceDecl { traitName, targetType, regions, methods });
}

/// Parse a method declaration with a receiver.
/// Syntax: `fn (t: *mut Type) fnord(<params>) -> ReturnType { body }`
///
/// Used both inside `instance` blocks and as standalone methods at the top level.
/// Expects the `fn` token to have already been consumed.
unsafe fn parseMethodDecl(p: &mut Parser, attrs: ?ast::Attributes) -> *ast::Node
    throws (ParseError)
{
    try expect(p, scanner::TokenKind::LParen, "expected `(` before receiver");

    let receiverName = try parseIdent(p, "expected receiver name");
    try expect(p, scanner::TokenKind::Colon, "expected `:` after receiver name");
    let receiverType = try parseType(p);

    try expect(p, scanner::TokenKind::RParen, "expected `)` after receiver type");

    let name = try parseIdent(p, "expected method name");
    let mut regions = try parseRegions(p);
    let sig = try parseFnTypeSig(p);
    try parseRegionBounds(p, &mut regions[..]);
    let body = try parseBlock(p);

    let modifiers = try! alloc::alloc(
        &mut p.arena.arena, @sizeOf(ast::MethodModifiers), @alignOf(ast::MethodModifiers)
    ) as *mut ast::MethodModifiers;
    set *modifiers = ast::MethodModifiers { regions, attrs };
    return node(p, ast::NodeValue::MethodDecl {
        name, modifiers, receiverName, receiverType, sig, body,
    });
}

/// Parse a comma-separated list enclosed by the given delimiters.
unsafe fn parseList(
    p: &mut Parser,
    open: scanner::TokenKind,
    close: scanner::TokenKind,
    parseItem: unsafe fn (&mut Parser) -> *ast::Node throws (ParseError)
) -> *mut [*ast::Node] throws (ParseError) {
    try expect(p, open, listExpectMessage(open));
    let mut items = ast::nodeSlice(p.arena, 8);

    while not check(p, close) {
        let item = try parseItem(p);
        items.append(item, p.allocator);

        if not consume(p, scanner::TokenKind::Comma) {
            break;
        }
    }
    try expect(p, close, listExpectMessage(close));

    return items;
}