//! 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;
}