parser.oc

//* The parser

import std::buffer::{ Buffer }
import std::map::{ Map }
import std::span::{ Span, Location }
import std::vector::{ Vector }
import std::mem
import std::fs

import @ast::nodes::{ * }
import @ast::program::{ Namespace, Program }
import @ast::operators::{ Operator }
import @ast::scopes::{ Symbol, SymbolType, Template, EnumField }
import @attributes::{ Attribute, AttributeType }
import @errors::Error
import @lexer::Lexer
import @tokens::{ Token, TokenType }
import @types::{ Type, BaseType, FunctionType, ArrayType, MapShorthandType }
import @utils::directory_exists

@compiler c_include "libgen.h"
[extern] def dirname(path: str): str
[extern] def basename(path: str): str

struct Parser {
    tokens: &Vector<&Token>
    curr: u32

    curr_func: &Function
    program: &Program
    ns: &Namespace

    attrs: &Vector<&Attribute>
    attrs_span: Span
    attrs_start_tok: &Token

    //! The span of the last expression that caused an error
    prev_expr_error_span: Span
}

def Parser::make(program: &Program, ns: &Namespace): Parser {
    return Parser(
        tokens: null,
        curr: 0,
        curr_func: null,
        program: program,
        ns: ns,
        attrs: Vector<&Attribute>::new(),
        attrs_span: Span::default(),
        attrs_start_tok: null,
        prev_expr_error_span: Span::default(),
    )
}

def Parser::free(&this) {
    // FIXME: Actually free the attributes, not just the vector
    //        Also do this in `.clear_attributes()`
    .attrs.free()
}

def Parser::peek(&this, off: i32 = 1): &Token {
    let idx = .curr as i32 + off
    assert 0i32 <= idx < (.tokens.size as i32)
    return .tokens.at(idx as u32)
}

def Parser::error_msg(&this, msg: str): &Error {
    let err = Error::new(.token().span, msg)
    .program.errors.push(err)
    return err
}

def Parser::error(&this, err: &Error): &Error {
    .program.errors.push(err)
    return err
}

def Parser::unhandled_type(&this, func: str) {
    .error_msg(`Unexpected token in {func}: {.token().type.str()}`)
}

def Parser::token(&this): &Token {
    if .curr >= .tokens.size {
        .curr = .tokens.size - 1
        // If we run out of tokens without an error, report one.
        .error_msg("Unexpected end of file")
        .program.get_error_context().jump_back(1)
    }
    return .tokens.unchecked_at(.curr as u32)
}

def Parser::token_is(&this, type: TokenType): bool {
    if type == TokenType::Newline {
        return .token().seen_newline
    }
    return .token().type == type
}

def Parser::token_is_eof_or(&this, type: TokenType): bool {
    if .token_is(TokenType::EOF) return true
    return .token_is(type)
}

def Parser::token_is_identifier(&this, name: str): bool => .token().is_identifier(name)

def Parser::peek_token_is(&this, off: u32, type: TokenType): bool {
    if .curr + off >= .tokens.size return false
    let tok = .tokens.at(.curr + off)
    return tok.type == type
}

def Parser::consume_if(&this, type: TokenType): bool {
    if .token_is(type) {
        // Newline tokens are special because they don't consume a token.
        if type != TokenType::Newline {
            if .curr < .tokens.size - 1 then .curr += 1
        }
        return true
    }
    return false
}

def Parser::consume_newline_or(&this, type: TokenType) {
    if .token_is(type) {
        if .curr < .tokens.size - 1 then .curr += 1

    } else if not .token().seen_newline {
        .error_msg(`Expected {type.str()} or newline`)
        .program.get_error_context().jump_back(1)
    }
}

def Parser::consume_tokens_until_newline(&this) {
    while not .token().seen_newline {
        if .token_is(TokenType::EOF) break
        .curr += 1
    }
}

def Parser::consume(&this, type: TokenType): &Token {
    let tok = .token()
    if not .consume_if(type) {
        .error_msg(`Expected TokenType::{type.str()}`)
        .program.get_error_context().jump_back(1)
    }
    return tok
}

def Parser::is_end_of_statement(&this): bool {
    if .token_is(TokenType::CloseCurly) return true
    if .token_is(TokenType::Semicolon) return true
    if .token().seen_newline return true
    return false
}

def Parser::consume_end_of_statement(&this) {
    if .token_is(TokenType::CloseCurly) return
    .consume_newline_or(TokenType::Semicolon)
}

def Parser::clear_attributes(&this) {
    for attr in .attrs.iter() {
        mem::free(attr)
    }
    .attrs.clear()
    .attrs_start_tok = null
}

def Parser::is_compound_operator(&this, op: Operator): bool => match op {
    LeftShift => .token_is(LessThan) and .peek_token_is(1, LessThan)
    RightShift => .token_is(GreaterThan) and .peek_token_is(1, GreaterThan)
    LeftShiftEquals => .token_is(LessThan) and .peek_token_is(1, LessThanEquals)
    RightShiftEquals => .token_is(GreaterThan) and .peek_token_is(1, GreaterThanEquals)
    else => false
}

def Parser::consume_compound_operator(&this, op: Operator): Span {
    let span = .token().span
    match op {
        LeftShift => { .consume(LessThan); .consume(LessThan); }
        RightShift => { .consume(GreaterThan); .consume(GreaterThan); }
        LeftShiftEquals => { .consume(LessThan); .consume(LessThanEquals); }
        RightShiftEquals => { .consume(GreaterThan); .consume(GreaterThanEquals); }
        else => {
            .error(Error::new(span, f"Unknown operator {op} in Parser::consume_compound_operator"))
        }
    }
    let prev_token = .tokens[.curr - 1]
    return span.join(prev_token.span)
}

// NOTE: The parser _always_ returns an `Unresolved` base type, with the name of the type stored in
// the `name` field. The typechecker is responsible for resolving this, even for the built-in types.
def Parser::parse_type(&this): &Type => match .token().type {
    Identifier => {
        let ident = .parse_scoped_identifier()
        let name = if ident.type == ASTType::Identifier then ident.u.ident.name else "<unresolved>"
        let typ = Type::new_unresolved(name, ident.span)
        typ.u.unresolved = ident
        yield typ
    }

    Ampersand => {
        let amp = .consume(Ampersand)
        let base = .parse_type()
        let typ = Type::new_resolved(BaseType::Pointer, amp.span.join(base.span))
        typ.u.ptr = base
        yield typ
    }

    AtSign | Fn => {
        let start_span = .token().span
        let base_type = match .token().type {
            AtSign => {
                // FIXME: Currently we don't have a way to "branch" to anything else
                //        if we decide to use @ as shorthand for more types. This needs
                //        to be refactored, possibly by moving logic in top-level match
                //        branches into separate functions.
                .consume(TokenType::AtSign)
                .consume(TokenType::Fn)
                yield BaseType::Closure
            }
            Fn => {
                .consume(TokenType::Fn)
                yield BaseType::FunctionPtr
            }
            else => std::panic("unreachable")
        }
        .consume(TokenType::OpenParen)
        let params = Vector<&Variable>::new()
        let is_variadic = false
        while not .token_is_eof_or(TokenType::CloseParen) {
            if .token_is(TokenType::Ellipsis) {
                .consume(TokenType::Ellipsis)
                is_variadic = true
                break
            }

            let param_type = .parse_type()

            // No names for parameters needed for function types
            let var = Variable::new(param_type)
            var.sym = Symbol::from_local_variable("", var, param_type.span)
            params.push(var)

            if not .token_is(TokenType::CloseParen) {
                .consume(TokenType::Comma)
            }
        }
        let close = .consume(TokenType::CloseParen)
        let return_type: &Type
        if .consume_if(TokenType::Colon) {
            return_type = .parse_type()
        } else {
            return_type = Type::new_unresolved_base(BaseType::Void, start_span)
        }
        let type = Type::new_resolved(base_type, start_span.join(close.span))
        type.u.func = FunctionType(null, params, return_type, is_variadic)
        yield type
    }

    OpenSquare => {
        let start_span = .token().span
        .consume(TokenType::OpenSquare)
        let elem_type = .parse_type()
        .consume(TokenType::Semicolon)
        let size_expr = .parse_expression(end_type: TokenType::CloseSquare)
        let close = .consume(TokenType::CloseSquare)
        let typ = Type::new_resolved(BaseType::Array, start_span.join(close.span))
        typ.u.arr = ArrayType(elem_type, size_expr, size_known: false, size: 0)
        yield typ
    }

    Dollar => {
        let dollar = .consume(Dollar)
        yield match .token().type {
            OpenSquare => {
                .consume(OpenSquare)
                let elem_type = .parse_type()
                let close = .consume(CloseSquare)
                let typ = Type::new_resolved(VectorShorthand, dollar.span.join(close.span))
                typ.u.ptr = elem_type
                .import_from_stdlib("vector", typ.span)
                yield typ
            }
            OpenCurly => {
                .consume(OpenCurly)
                let key_type = .parse_type()
                .consume(Colon)
                let value_type = .parse_type()
                let close = .consume(CloseCurly)
                let typ = Type::new_resolved(MapShorthand, dollar.span.join(close.span))
                typ.u.map_types = MapShorthandType(key: key_type, value: value_type)
                .import_from_stdlib("compact_map", typ.span)
                yield typ
            }
            else => {
                .error(Error::new(.token().span, "Unexpected token after `$`"))
                yield null
            }
        }
    }

    else => {
        .unhandled_type("parse_type")
        yield Type::new_unresolved_base(BaseType::Error, .token().span)
    }
}

def Parser::parse_identifier(&this): &AST {
    let tok = .consume(TokenType::Identifier)
    let node = AST::new(Identifier, tok.span)
    node.u.ident.name = tok.text
    return node
}

def Parser::parse_scoped_identifier(&this, consume_template: bool = true): &AST {
    let node = .parse_identifier()

    while true {
        match .token().type {
            TokenType::ColonColon => {
                let colons = .consume(TokenType::ColonColon)

                let lookup = AST::new(NSLookup, node.span)
                lookup.u.lookup.lhs = node
                node = lookup

                if .token_is(Newline) or not .token_is(Identifier) {
                    let span = Span(colons.span.end, colons.span.end)
                    .error(Error::new(span, "Expected identifier after `::`"))
                    node.span.end = .token().span.start

                } else {
                    let name = .consume(TokenType::Identifier)
                    node.span = node.span.join(name.span)
                    node.u.lookup.rhs_name = name.text
                    node.u.lookup.rhs_span = name.span
                }
            }
            TokenType::LessThan => {
                if not consume_template return node
                // FIXME: Is there a more robust way to do this?
                // We want to be able to differentiate between a `<` that starts a specialization and
                // a `<` that is part of a less-than comparison before typechecking, I don't know of
                // the best way to do this, but here's a couple heuristics:

                // 1. Make sure that we don't have a space between the identifier and the `<`
                let prev_token = .tokens.at(.curr as u32 - 1)
                if not .token().span.starts_right_after(prev_token.span) {
                    return node
                }

                // 2. Make sure the token after that isn't a `.`
                let next_next_token = .tokens.at(.curr as u32 + 2)
                if next_next_token.type == TokenType::Dot {
                    return node
                }

                // Okay... so we're kinda-sorta sure that this is a specialization, let's parse it.
                let start = .consume(TokenType::LessThan)
                let args = Vector<&Type>::new()

                while not .token_is_eof_or(TokenType::GreaterThan) {
                    args.push(.parse_type())
                    if not .token_is(TokenType::GreaterThan) {
                        if not .consume_if(TokenType::Comma) {
                            .error(Error::new_note(
                                .token().span, "Parsing template specialization: expected `,` or `>`",
                                "If you're comparing values, put a space before the `<` earlier"
                            ))
                            return AST::new(Error, node.span)
                        }
                    }
                }
                let end = .consume(TokenType::GreaterThan)
                let spec = AST::new(Specialization, node.span.join(end.span))
                spec.u.spec = Specialization(
                    base: node,
                    parsed_template_args: args,
                    template_args: args,
                )
                node = spec
            }
            else => return node
        }
    }

    return null // unreachable
}


def Parser::parse_format_string(&this): &AST {
    let fstr = .consume(TokenType::FormatStringLiteral)
    let fstr_len = fstr.text.len()

    let expr_parts = Vector<str>::new()
    let expr_start = Vector<u32>::new()

    let format_parts = Vector<str>::new()
    let specifiers = Vector<str>::new()

    let specifier_loc = 0
    let specifier_found = false

    let count = 0
    let cur_start = 0

    for let i = 0; i < fstr_len; i += 1 {
        match fstr.text[i] {
            '\\' =>  i += 1
            '{' => {
                if count == 0 {
                    let part = fstr.text.substring(cur_start, i - cur_start)
                    format_parts.push(part)
                    cur_start = i + 1
                }
                count += 1
            }
            '}' => {
                count -= 1
                if count == 0 {
                    if specifier_loc > 0 {
                        let len = specifier_loc - cur_start
                        let part = fstr.text.substring(cur_start, len)
                        expr_parts.push(part)
                        expr_start.push(cur_start)

                        specifier_loc += 1
                        while specifier_loc < i and fstr.text[specifier_loc] == ' ' {
                            specifier_loc += 1
                        }

                        if specifier_loc == i {
                            let loc = fstr.span.start;
                            loc.col += specifier_loc + 1
                            let span = Span(loc, loc)
                            .error(Error::new(span, "Expected format specifier"))
                            return null
                        }

                        let spec = fstr.text.substring(specifier_loc, i - specifier_loc)
                        specifiers.push(spec)
                    } else {
                        let part = fstr.text.substring(cur_start, i - cur_start)
                        expr_parts.push(part)
                        expr_start.push(cur_start)
                        specifiers.push(null)
                    }
                    cur_start = i + 1
                    specifier_loc = 0
                    specifier_found = false

                } else if count < 0 {
                    .error(Error::new(fstr.span, "Unmatched '}' in format string"))
                    return null
                }

            }
            ':' => {
                // TODO: Handle errors properly (actually, maybe just add an assert)
                if count == 1 and fstr.text[i - 1] != ':' and fstr.text[i + 1] != ':' {
                    specifier_loc = i
                    specifier_found = true
                }
            }
            else => {}
        }
    }
    if count != 0 {
        .error(Error::new(fstr.span, "Unmatched '{' in format string"))
        return null
    }
    let part = fstr.text.substring(cur_start, fstr_len - cur_start)
    format_parts.push(part)

    let node = AST::new(FormatStringLiteral, fstr.span)
    node.u.fmt_str.parts = format_parts

    let fstr_start = fstr.span.start
    let expr_nodes = Vector<&AST>::new()
    for let i = 0; i < expr_parts.size; i += 1 {
        let part = expr_parts.at(i)
        let start = expr_start.at(i)

        let lexer = Lexer::make(part, fstr_start.filename, .program.errors)
        lexer.loc = fstr_start
        lexer.loc.col += start + 1

        let tokens = lexer.lex()
        let sub_parser = Parser::make(.program, .ns)
        sub_parser.tokens = tokens
        sub_parser.curr = 0
        sub_parser.curr_func = .curr_func

        let expr = sub_parser.parse_expression(end_type: TokenType::CloseCurly)
        if not sub_parser.token_is(TokenType::EOF) {
            .error(Error::new(expr.span, "Invalid expression in format string"))
        }

        expr_nodes.push(expr)
    }
    node.u.fmt_str.exprs = expr_nodes
    node.u.fmt_str.specs = specifiers
    expr_parts.free()
    expr_start.free()
    return node
}

def Parser::parse_match_case_conds(&this, end_type: TokenType): &Vector<&MatchCond> {
    let conds = Vector<&MatchCond>::new()
    while not .token_is_eof_or(end_type) {
        let expr = .parse_atom(TokenType::Line)

        let args: &Vector<&MatchCondArg> = null
        if .consume_if(OpenParen) {
            args = Vector<&MatchCondArg>::new()
            while not .token_is_eof_or(CloseParen) {
                let name = .consume(Identifier)
                let var = Variable::new(null)
                var.sym = Symbol::from_local_variable(name.text, var, name.span)
                args.push(@new MatchCondArg(var))

                if not .consume_if(Comma) {
                    break
                }
            }
            .consume(CloseParen)
        }
        conds.push(MatchCond::new(expr, args))
        if not .consume_if(Line) then break
    }

    return conds
}

def Parser::parse_match(&this): &AST {
    let op = .consume(TokenType::Match)
    let expr = .parse_expression(end_type: TokenType::OpenCurly)
    let node = AST::new(Match, op.span.join(expr.span))
    node.u.match_stmt.expr = expr
    node.u.match_stmt.match_span = op.span

    let cases = Vector<MatchCase>::new()
    node.u.match_stmt.cases = cases

    if not .token_is(TokenType::OpenCurly) {
        .error(Error::new(.token().span, "Expected '{' after match expression"))
        return node
    }
    .consume(TokenType::OpenCurly)
    while not .token_is_eof_or(TokenType::CloseCurly) {
        if .token_is(TokenType::Else) {
            node.u.match_stmt.defolt_span = .token().span
            .consume(TokenType::Else)
            if not .consume_if(TokenType::FatArrow) {
                .error(Error::new(.token().span, "Expected => after match case"))
            }
            node.u.match_stmt.defolt = .parse_statement()

        } else {
            let conds = .parse_match_case_conds(TokenType::FatArrow)
            if not .consume_if(TokenType::FatArrow) {
                .error(Error::new(.token().span, "Expected => after match case"))
            }
            let body = .parse_statement()
            if not .token_is(TokenType::CloseCurly) {
                .consume_newline_or(TokenType::Comma)
            }
            let _case = MatchCase(conds, body)
            cases.push(_case)
        }

        .consume_if(TokenType::Comma)
    }
    node.span = op.span.join(.token().span)
    .consume(TokenType::CloseCurly)
    node.u.match_stmt.cases = cases

    return node
}

//! Resets the parser state to the start of a top-level block
def Parser::sync_toplevel(&this) {
    while not (
        .token_is(TokenType::CloseCurly) or     // End of block
        .token_is(TokenType::OpenSquare) or     // Start of attribute
        .token_is(TokenType::Import) or         // Start of import
        .token_is(TokenType::Def) or            // Start of function
        .token_is(TokenType::Let) or            // Start of variable
        .token_is(TokenType::Const) or          // Start of constant
        .token_is(TokenType::Struct) or         // Start of struct
        .token_is(TokenType::Enum) or           // Start of enum
        .token_is(TokenType::AtSign) or         // Start of compiler directive
        .token_is(TokenType::EOF)               // EOF
    ) {
        .curr += 1
    }
}

def Parser::parse_literal_suffix_type(&this, suffix: &Token): &Type {
    if not suffix? return null

    let ident = AST::new(Identifier, suffix.span)
    ident.u.ident.name = suffix.text

    let typ = Type::new_unresolved(suffix.text, suffix.span)
    typ.u.unresolved = ident

    return typ
}

def Parser::parse_call(&this, callee: &AST): &AST {
    let start = .consume(TokenType::OpenParen)
    let args = Vector<&Argument>::new()
    while not .token_is_eof_or(TokenType::CloseParen) {
        let label_tok: &Token = null
        if .token_is(Identifier) and .peek_token_is(1, Colon) {
            label_tok = .consume(TokenType::Identifier)
            .consume(TokenType::Colon)
        }
        let expr = .parse_expression(end_type: TokenType::Comma)

        args.push(Argument::new(expr, label_tok))
        if not .token_is(TokenType::CloseParen) {
            .consume(TokenType::Comma)
        }
    }

    let end = .consume(TokenType::CloseParen)
    let call_type = ASTType::Call
    let call = AST::new(call_type, callee.span.join(end.span))
    call.u.call.callee = callee
    call.u.call.args = args
    call.u.call.open_paren_span = start.span
    call.u.call.close_paren_span = end.span
    return call
}

//* We also allow array literals when initializing a variable, so treat them separately.
def Parser::parse_var_initializer(&this): &AST {
    if .token_is(TokenType::OpenSquare) {
        let start = .consume(TokenType::OpenSquare)
        let elements = Vector<&AST>::new()
        while not .token_is_eof_or(TokenType::CloseSquare) {
            elements.push(.parse_var_initializer())
            if not .token_is(TokenType::CloseSquare) {
                .consume(TokenType::Comma)
            }
        }
        let close = .consume(TokenType::CloseSquare)
        let node = AST::new(ArrayLiteral, start.span.join(close.span))
        node.u.array_literal.elements = elements
        return node
    }
    return .parse_expression(TokenType::Newline)
}

def Parser::parse_var_declaration(&this): &AST {
    let start = .consume(TokenType::Let)
    let name = .consume(TokenType::Identifier)
    let end_span = name.span

    let type: &Type = null
    if .consume_if(TokenType::Colon) {
        type = .parse_type()
        end_span = type.span
    }
    let init: &AST = null
    if .consume_if(TokenType::Equals) {
        init = .parse_var_initializer()
        end_span = init.span
    }
    .consume_end_of_statement()

    let node = AST::new(VarDeclaration, start.span.join(end_span))

    let var = Variable::new(type)
    var.sym = Symbol::from_local_variable(name.text, var, name.span)
    var.default_value = init

    node.u.var_decl = var
    return node
}

def Parser::parse_global_value(&this, is_const: bool): &AST {
    let start_token = if is_const {
        yield .consume(TokenType::Const)
    } else {
        yield .consume(TokenType::Let)
    }

    let node = AST::new(VarDeclaration, .token().span)
    let name = if .token_is(TokenType::Identifier) {
        yield .consume(TokenType::Identifier)
    } else {
        .error(Error::new(.token().span, "Expected identifier"))
        return node
    }

    let type: &Type = null
    if .consume_if(TokenType::Colon) { type = .parse_type(); }

    let var = Variable::new(type)
    var.sym = Symbol::new_with_parent(Variable, .ns, .ns.sym, name.text, name.span)
    var.sym.u.var = var

    if is_const {
        var.sym.type = SymbolType::Constant
    }

    .parse_extern_into_symbol(var.sym)

    for attr in .attrs.iter() {
        match attr.type {
            Extern => .get_extern_from_attr(var.sym, attr)
            Atomic => var.is_atomic = true
            else => .error(Error::new(attr.span, "Unexpected attribute for variable"))
        }
    }

    node.u.var_decl = var
    if .consume_if(TokenType::Equals) {
        if is_const {
            var.default_value = .parse_expression(end_type: TokenType::Newline)
        } else {
            var.default_value = .parse_var_initializer()
        }
    }
    .consume_newline_or(TokenType::Semicolon)
    return node
}

def Parser::parse_atom(&this, end_type: TokenType): &AST {
    let node: &AST = null
    match .token().type {
        TokenType::If => node = .parse_if()
        TokenType::Match => node = .parse_match()
        TokenType::OpenCurly => node = .parse_block()
        TokenType::FormatStringLiteral => node = .parse_format_string()
        TokenType::Null => {
            let tok = .consume(TokenType::Null)
            node = AST::new(Null, tok.span)
        }
        TokenType::IntLiteral => {
            node = AST::new(IntLiteral, .token().span)
            let tok = .consume(TokenType::IntLiteral)
            node.u.num_literal = NumLiteral(
                text: tok.text,
                suffix: .parse_literal_suffix_type(tok.suffix)
            )
        }
        TokenType::FloatLiteral => {
            node = AST::new(FloatLiteral, .token().span)
            let tok = .consume(TokenType::FloatLiteral)
            node.u.num_literal = NumLiteral(
                text: tok.text,
                suffix: .parse_literal_suffix_type(tok.suffix)
            )
        }
        TokenType::StringLiteral => {
            node = AST::new(StringLiteral, .token().span)
            let tok = .consume(TokenType::StringLiteral)
            node.u.string_literal = tok.text
        }
        TokenType::CharLiteral => {
            node = AST::new(CharLiteral, .token().span)
            let tok = .consume(TokenType::CharLiteral)
            node.u.char_literal = tok.text
        }
        TokenType::Identifier => node = .parse_scoped_identifier()
        TokenType::True | TokenType::False => {
            let tok = .consume(.token().type)
            node = AST::new(BoolLiteral, tok.span)
            node.u.bool_literal = tok.type == TokenType::True
        }
        TokenType::OpenParen => {
            let start = .consume(TokenType::OpenParen)
            node = .parse_expression(end_type: TokenType::CloseParen)
            let end = .consume(TokenType::CloseParen)
            node.span = start.span.join(end.span)
        }
        TokenType::Dot => {
            let tok = .consume(TokenType::Dot)
            if not .curr_func? or not .curr_func.kind == Method or .curr_func.is_static {
                .error(Error::new(tok.span, "Cannot use dot shorthand outside of a method"))
                return AST::new(Error, tok.span)
            }

            let lhs = AST::new(Identifier, tok.span)
            lhs.u.ident.name = "this"

            node = AST::new(Member, tok.span)
            node.u.member.lhs = lhs
            node.u.member.dot_shorthand = true

            if not .token_is(TokenType::Identifier) {
                .error(Error::new(.token().span, "Expected identifier after `.`"))
                node.span.end = .token().span.start
            } else {
                let ident = .consume(TokenType::Identifier)
                node.span = tok.span.join(ident.span)
                node.u.member.rhs_name = ident.text
                node.u.member.rhs_span = ident.span
            }
        }
        TokenType::EOF => {
            .error(Error::new(.token().span, "Unexpected end of file"))
            return AST::new(Error, .token().span)
        }
        TokenType::Line => {
            let start_loc = .token().span.start
            let closure_func = .parse_closure()
            let node = AST::new(CreateClosure, closure_func.span)
            node.u.closure = closure_func

            let closure_name = `_Closure_{.program.closures.size}`
            .program.closures.push(closure_func)

            let parent_sym = if {
                .curr_func? => .curr_func.sym
                else => .ns.sym
            }
            let sym = Symbol::new_with_parent(Closure, .ns, parent_sym, closure_name, Span(start_loc, start_loc))
            sym.u.func = closure_func
            closure_func.sym = sym
            return node
        }
        TokenType::Dollar => {
            let dollar = .consume(Dollar)
            match .token().type {
                OpenSquare => {
                    let start = .consume(TokenType::OpenSquare)
                    let elements = Vector<&AST>::new()
                    while not .token_is_eof_or(TokenType::CloseSquare) {
                        elements.push(.parse_var_initializer())
                        if not .token_is(TokenType::CloseSquare) {
                            .consume(TokenType::Comma)
                        }
                    }
                    let close = .consume(TokenType::CloseSquare)
                    let node = AST::new(VectorLiteral, dollar.span.join(close.span))
                    node.u.vec_literal.elements = elements
                    node.u.vec_literal.start_span = dollar.span.join(start.span)
                    .import_from_stdlib("vector", node.span)
                    return node
                }
                OpenCurly => {
                    let start = .consume(TokenType::OpenCurly)
                    let elements: $[MapLiteralPair] = $[]
                    while not .token_is_eof_or(TokenType::CloseCurly) {
                        let key = .parse_expression(TokenType::Colon)
                        .consume(TokenType::Colon)
                        let value = .parse_expression(TokenType::Comma)
                        if not .token_is(TokenType::CloseCurly) {
                            .consume(TokenType::Comma)
                        }
                        elements += MapLiteralPair(key, value)
                    }
                    let close = .consume(TokenType::CloseCurly)
                    let node = AST::new(MapLiteral, dollar.span.join(close.span))
                    node.u.map_literal.elements = elements
                    node.u.map_literal.start_span = dollar.span.join(start.span)
                    .import_from_stdlib("compact_map", node.span)
                    return node
                }
                else => {
                    .error(Error::new(.token().span, f"Unexpected token: {.token().type}"))
                }
            }
        }
        else => {
            let prev_span = .tokens[.curr - 1].span
            let cur_span = .token().span

            let err_span = Span(prev_span.end, cur_span.start)
            if not .token_is(end_type) {
                .curr += 1
                err_span = cur_span
                .unhandled_type("parse_expression")

            // We want to try to be error-tolerant, and not consume the token
            // If we can avoid it (this may be an incomplete expression). However,
            // if we see the same error multiple times, then we bail.
            } else if .prev_expr_error_span == err_span {
                .curr += 1

            } else {
                .prev_expr_error_span = err_span
                .unhandled_type("parse_expression")

            }
            node = AST::new(Error, err_span)
        }
    }
    return node
}

def Parser::parse_postfix(&this, end_type: TokenType): &AST {
    let node = .parse_atom(end_type)

    let running = true
    while running {
        if .token_is(end_type) break
        match .token().type {
            TokenType::OpenParen => node = .parse_call(node)
            TokenType::Dot | TokenType::QuestionDot => {
                if .token_is(end_type) break
                let op = .consume(.token().type)
                let member = match op.type {
                    QuestionDot => AST::new(TryMember, node.span)
                    Dot => AST::new(Member, node.span)
                    else => std::panic("Unreachable")
                }
                member.u.member.lhs = node
                node = member

                if .token_is(end_type) or not .token_is(TokenType::Identifier) {
                    .error(Error::new(.token().span, "Expected identifier after `.`"))
                    node.span.end = .token().span.start

                } else {
                    let ident = .consume(TokenType::Identifier)
                    node.span = node.span.join(ident.span)
                    node.u.member.rhs_name = ident.text
                    node.u.member.rhs_span = ident.span
                }
            }
            TokenType::Question => {
                let tok = .consume(TokenType::Question)
                node = AST::new_unop(IsNotNull, node.span.join(tok.span), node)
            }
            TokenType::Exclamation => {
                let tok = .consume(TokenType::Exclamation)
                node = AST::new_unop(ErrorProp, node.span.join(tok.span), node)
                .import_from_stdlib("result", node.span)

            }
            TokenType::ExclamationExclamation => {
                let tok = .consume(TokenType::ExclamationExclamation)
                node = AST::new_unop(ErrorUnwrap, node.span.join(tok.span), node)
                .import_from_stdlib("result", node.span)
            }
            TokenType::OpenSquare => {
                let open = .consume(TokenType::OpenSquare)
                let index = .parse_expression(end_type: TokenType::CloseSquare)
                let close = .consume(TokenType::CloseSquare)

                // Contructing the binop here manually to properly handle the
                // spans of `]` being _after_ the index expression.
                let op = AST::new(BinaryOp, node.span.join(close.span))
                op.u.binary.op = Index
                op.u.binary.lhs = node
                op.u.binary.rhs = index
                op.u.binary.op_span = open.span
                node = op
            }
            TokenType::MinusMinus | TokenType::PlusPlus => {
                let span = node.span.join(.token().span)
                let op = if .token_is(TokenType::MinusMinus) {
                    .consume(TokenType::MinusMinus)
                    yield Operator::PostDecrement
                } else {
                    .consume(TokenType::PlusPlus)
                    yield Operator::PostIncrement
                }
                node = AST::new_unop(op, span, node)
            }
            else => running = false
        }
    }

    return node
}

def Parser::parse_prefix(&this, end_type: TokenType): &AST {
    match .token().type {
        TokenType::Ampersand => {
            let amp = .consume(TokenType::Ampersand)
            let expr = .parse_prefix(end_type)
            let node = AST::new_unop(Operator::Address, amp.span.join(expr.span), expr)
            return node
        }
        TokenType::MinusMinus | TokenType::PlusPlus => {
            let start_span = .token().span
            let op = if .token_is(TokenType::MinusMinus) {
                .consume(TokenType::MinusMinus)
                yield Operator::PreDecrement
            } else {
                .consume(TokenType::PlusPlus)
                yield Operator::PreIncrement
            }
            let expr = .parse_prefix(end_type)
            return AST::new_unop(op, start_span.join(expr.span), expr)
        }
        TokenType::SizeOf => {
            let start = .consume(TokenType::SizeOf)
            .consume(TokenType::OpenParen)
            let type = .parse_type()
            let close = .consume(TokenType::CloseParen)
            let node = AST::new(SizeOf, start.span.join(close.span))
            node.u.size_of_type = type
            return node
        }
        // Special compiler operations
        TokenType::AtSign => {
            let atsign = .consume(TokenType::AtSign)
            if not .token_is(TokenType::Identifier) {
                .error(Error::new(.token().span, "Expected compiler operation after @"))
                return AST::new(Error, atsign.span)
            }
            let ident = .consume(TokenType::Identifier)
            match ident.text {
                "new" => {
                    let expr = .parse_prefix(end_type)
                    let node = AST::new(CreateNew, atsign.span.join(expr.span))
                    node.u.child = expr
                    return node
                }
                else => {
                    .error(Error::new(ident.span, "Unknown compiler operation"))
                    return AST::new(Error, atsign.span)
                }
            }
        }
        TokenType::Star => {
            let star = .consume(TokenType::Star)
            let expr = .parse_prefix(end_type)
            let node = AST::new_unop(Dereference, star.span.join(expr.span), expr)
            return node
        }
        TokenType::Minus => {
            let minus = .consume(TokenType::Minus)
            let expr = .parse_prefix(end_type)
            let node = AST::new_unop(Negate, minus.span.join(expr.span), expr)
            return node
        }
        TokenType::Tilde => {
            let tok = .consume(TokenType::Tilde)
            let expr = .parse_prefix(end_type)
            let node = AST::new_unop(BitwiseNot, tok.span.join(expr.span), expr)
            return node
        }
        else => return .parse_postfix(end_type)
    }
}

def Parser::parse_cast(&this, end_type: TokenType): &AST {
    let lhs = .parse_prefix(end_type)
    while .token_is(TokenType::As) {
        if .token_is(end_type) break
        let tok = .consume(TokenType::As)
        let type_node = .parse_type()
        let op = AST::new(Cast, lhs.span.join(type_node.span))
        op.u.cast.lhs = lhs
        op.u.cast.to = type_node
        op.u.cast.parsed_to = type_node
        lhs = op
    }
    return lhs
}

def Parser::parse_term(&this, end_type: TokenType): &AST {
    let lhs = .parse_cast(end_type)
    while .token_is(TokenType::Star) or
            .token_is(TokenType::Slash) or
            .token_is(TokenType::Percent) {
        if .token_is(end_type) break
        let op_tok = .consume(.token().type)
        let op = Operator::from_token(op_tok)
        let rhs = .parse_cast(end_type)
        lhs = AST::new_binop(op, lhs, rhs, op_tok.span)
    }
    return lhs
}


def Parser::parse_additive(&this, end_type: TokenType): &AST {
    let lhs = .parse_term(end_type)
    while .token_is(TokenType::Plus) or .token_is(TokenType::Minus) {
        if .token_is(end_type) break
        let op_tok = .consume(.token().type)
        let op = Operator::from_token(op_tok)
        let rhs = .parse_term(end_type)
        lhs = AST::new_binop(op, lhs, rhs, op_tok.span)
    }
    return lhs
}

def Parser::parse_shift(&this, end_type: TokenType): &AST {
    let lhs = .parse_additive(end_type)
    while .is_compound_operator(LeftShift) or
            .is_compound_operator(RightShift) {

        let op = if .token().type == TokenType::LessThan {
            yield Operator::LeftShift
        } else {
            yield Operator::RightShift
        }
        let op_span = .consume_compound_operator(op)
        let rhs = .parse_additive(end_type)
        lhs = AST::new_binop(op, lhs, rhs, op_span)
    }
    return lhs
}

def Parser::parse_bw_and(&this, end_type: TokenType): &AST {
    let lhs = .parse_shift(end_type)
    while .token_is(TokenType::Ampersand) {
        if .token_is(end_type) break
        let op_tok = .consume(.token().type)
        let op = Operator::from_token(op_tok)
        let rhs = .parse_shift(end_type)
        lhs = AST::new_binop(op, lhs, rhs, op_tok.span)
    }
    return lhs
}

def Parser::parse_bw_xor(&this, end_type: TokenType): &AST {
    let lhs = .parse_bw_and(end_type)
    while .token_is(TokenType::Caret) {
        if .token_is(end_type) break
        let op_tok = .consume(.token().type)
        let op = Operator::from_token(op_tok)
        let rhs = .parse_bw_and(end_type)
        lhs = AST::new_binop(op, lhs, rhs, op_tok.span)
    }
    return lhs
}

def Parser::parse_bw_or(&this, end_type: TokenType): &AST {
    let lhs = .parse_bw_xor(end_type)
    while .token_is(TokenType::Line) {
        if .token_is(end_type) break
        let op_tok = .consume(.token().type)
        let op = Operator::from_token(op_tok)
        let rhs = .parse_bw_xor(end_type)
        lhs = AST::new_binop(op, lhs, rhs, op_tok.span)
    }
    return lhs
}

def Parser::parse_relational(&this, end_type: TokenType): &AST {
    let lhs = .parse_bw_or(end_type)

    let operands: &Vector<&AST> = null
    let operators: &Vector<&Token> = null
    while .token_is(TokenType::LessThan) or
            .token_is(TokenType::GreaterThan) or
            .token_is(TokenType::LessThanEquals) or
            .token_is(TokenType::GreaterThanEquals) or
            .token_is(TokenType::EqualEquals) or
            .token_is(TokenType::NotEquals) or
            .token_is_identifier("in") {

        if .token_is(end_type) break

        let done = match .token().type {
            LessThan => .is_compound_operator(LeftShiftEquals)
            GreaterThan => .is_compound_operator(RightShiftEquals)
            else => false
        }
        if done then break

        if not operators? {
            operators = Vector<&Token>::new(capacity: 2)
            operands = Vector<&AST>::new(capacity: 3)
            operands.push(lhs)
        }

        let token = .consume(.token().type)
        operators.push(token)
        let term = .parse_bw_or(end_type)
        operands.push(term)
    }

    if not operators? return lhs

    let root: &AST = null
    for let i = 0; i < operators.size; i += 1 {
        let tok = operators.at(i)
        let lhs = operands.at(i)
        let rhs = operands.at(i+1)
        let op = AST::new_binop(Operator::from_token(tok), lhs, rhs, tok.span)
        if root? {
            root = AST::new_binop(And, root, op, tok.span)
        } else {
            root = op
        }
    }

    operands.free()
    operators.free()

    return root
}

def Parser::parse_logical_not(&this, end_type: TokenType): &AST {
    if .token_is(TokenType::Not) {
        let tok = .consume(TokenType::Not)
        let expr = .parse_logical_not(end_type)
        return AST::new_unop(Not, tok.span.join(expr.span), expr)
    }
    return .parse_relational(end_type)
}

def Parser::parse_logical_and(&this, end_type: TokenType): &AST {
    let lhs = .parse_logical_not(end_type)
    while .token_is(TokenType::And) {
        if .token_is(end_type) break
        let op_tok = .consume(.token().type)
        let op = Operator::from_token(op_tok)
        let rhs = .parse_logical_not(end_type)
        lhs = AST::new_binop(op, lhs, rhs, op_tok.span)
    }
    return lhs
}

def Parser::parse_logical_or(&this, end_type: TokenType): &AST {
    let lhs = .parse_logical_and(end_type)
    while .token_is(TokenType::Or) {
        if .token_is(end_type) break
        let op_tok = .consume(.token().type)
        let op = Operator::from_token(op_tok)
        let rhs = .parse_logical_and(end_type)
        lhs = AST::new_binop(op, lhs, rhs, op_tok.span)
    }
    return lhs
}

//! Parse and return the AST for an expression
def Parser::parse_expression(&this, end_type: TokenType): &AST {
    let lhs = .parse_logical_or(end_type)
    while .token_is(TokenType::Equals) or
            .token_is(TokenType::PlusEquals) or
            .token_is(TokenType::MinusEquals) or
            .token_is(TokenType::StarEquals) or
            .token_is(TokenType::SlashEquals) or
            .is_compound_operator(LeftShiftEquals) or
            .is_compound_operator(RightShiftEquals) {
        if .token_is(end_type) break

        let op_span: Span
        let op = match .token().type {
            LessThan => {
                op_span = .consume_compound_operator(LeftShiftEquals)
                yield Operator::LeftShiftEquals
            }
            GreaterThan => {
                op_span = .consume_compound_operator(RightShiftEquals)
                yield Operator::RightShiftEquals
            }
            else => {
                let tok = .consume(.token().type)
                op_span = tok.span
                yield Operator::from_token(tok)
            }
        }

        // FIXME: expressions such as `foo[x] += 5` can't be overloaded
        //        properly since we only handle `foo[x] = 5` as a special
        //        case here. Figure out how to make this more general without
        //        Introducing more AST-types for all the different operators.
        if op == Assignment and lhs.type == BinaryOp and lhs.u.binary.op == Index {
            op = IndexAssign
        }

        let rhs = .parse_expression(end_type)
        lhs = AST::new_binop(op, lhs, rhs, op_span)
    }
    return lhs
}

def Parser::parse_multi_if(&this, start_tok: &Token): &AST {
    let start_span = start_tok.span

    let node = AST::new(If, start_span)
    .consume(TokenType::OpenCurly)
    let branches = Vector<IfBranch>::new()
    node.u.if_stmt.branches = branches
    node.u.if_stmt.if_span = start_span

    while not .token_is_eof_or(TokenType::CloseCurly) {
        if .token_is(TokenType::Else) {
            node.u.if_stmt.els_span = .token().span
            .consume(TokenType::Else)
            .consume(TokenType::FatArrow)
            node.u.if_stmt.els = .parse_statement()

        } else {
            let cond = .parse_expression(end_type: FatArrow)
            if not .consume_if(TokenType::FatArrow) {
                .error(Error::new(.token().span, "Expected `=>` after condition"))
            }
            let body = .parse_statement()
            branches.push(IfBranch(cond, body))
        }
        .consume_if(TokenType::Comma)
    }
    let end_span = .consume(TokenType::CloseCurly).span
    node.span = start_span.join(end_span)
    return node
}

def Parser::parse_if(&this): &AST {
    let start_tok = .consume(TokenType::If)
    let start_span = start_tok.span

    if .token_is(OpenCurly) return .parse_multi_if(start_tok)

    let cases = Vector<IfBranch>::new()
    let end_span = start_span
    while true {
        let cond = .parse_expression(end_type: TokenType::Newline)
        .consume_if(TokenType::Then)
        let body = .parse_statement()
        cases.push(IfBranch(cond, body))
        end_span = body.span

        if .token_is(Else) and .peek_token_is(1, If) {
            .consume(TokenType::Else)
            .consume(TokenType::If)

        } else {
            break
        }
    }
    let node = AST::new(If, start_span.join(end_span))
    node.u.if_stmt.branches = cases
    node.u.if_stmt.if_span = start_span

    if .token_is(TokenType::Else) {
        let els_tok = .consume(TokenType::Else)
        node.u.if_stmt.els = .parse_statement()
        node.u.if_stmt.els_span = els_tok.span
    }

    node.span = start_span.join(end_span)
    return node
}

//* Parse for-each loops syntax sugar
//*
//* This function is responsible for parsing
//*
//*      for i in expr {
//*          ...
//*      }
//*
//* and converting it into
//*
//*      for let __iter = expr; __iter.has_value(); __iter.next() {
//*          let i = __iter.get();
//*          {
//*             ...
//*          }
//*      }
def Parser::parse_for_each(&this, start_span: Span): &AST {

    let name = .consume(Identifier)
    if not .token_is_identifier("in") {
        .error(Error::new(.token().span, "Expected `in` after for-each loop variable"))
        return AST::new(Error, start_span)
    }
    .consume(.token().type)

    let expr = .parse_expression(end_type: TokenType::Newline)
    let iter_var_name = f"_i{.program.uid++}"

    let init = {
        let node = AST::new(VarDeclaration, start_span)
        let var = Variable::new(null)
        var.sym = Symbol::from_local_variable(iter_var_name, var, start_span)
        var.default_value = expr

        node.u.var_decl = var
        yield node
    }

    let cond = {
        let iter_name = AST::new(Identifier, start_span)
        iter_name.u.ident.name = iter_var_name

        let member = AST::new(Member,  start_span)
        member.u.member.lhs = iter_name
        member.u.member.rhs_name = "has_value"
        member.u.member.rhs_span = expr.span

        let node = AST::new(Call, start_span)
        node.u.call.callee = member
        node.u.call.args = Vector<&Argument>::new()
        node.u.call.open_paren_span = name.span
        node.u.call.close_paren_span = name.span
        yield node
    }

    let step = {
        let iter_name = AST::new(Identifier, start_span)
        iter_name.u.ident.name = iter_var_name

        let member = AST::new(Member, start_span)
        member.u.member.lhs = iter_name
        member.u.member.rhs_name = "next"
        member.u.member.rhs_span = expr.span

        let node = AST::new(Call, start_span)
        node.u.call.callee = member
        node.u.call.args = Vector<&Argument>::new()
        node.u.call.open_paren_span = name.span
        node.u.call.close_paren_span = name.span
        yield node
    }


    let loop_var_decl = {
        let var = Variable::new(null)
        var.sym = Symbol::from_local_variable(name.text, var, name.span)

        let iter_name = AST::new(Identifier, start_span)
        iter_name.u.ident.name = iter_var_name

        let member = AST::new(Member, start_span)
        member.u.member.lhs = iter_name
        member.u.member.rhs_name = "cur"
        member.u.member.rhs_span = expr.span

        let call = AST::new(Call, start_span)
        call.u.call.callee = member
        call.u.call.args = Vector<&Argument>::new()
        call.u.call.open_paren_span = name.span
        call.u.call.close_paren_span = name.span

        let node = AST::new(VarDeclaration, start_span)
        var.default_value = call
        node.u.var_decl = var
        yield node
    }

    let inner_body = .parse_block()

    let statements = Vector<&AST>::new()
    statements.push(loop_var_decl)
    statements.push(inner_body)

    let body = AST::new(Block, inner_body.span)
    body.u.block.statements = statements

    let node = AST::new(For, start_span.join(body.span))
    node.u.loop.init = init
    node.u.loop.cond = cond
    node.u.loop.step = step
    node.u.loop.body = body
    return node
}

def Parser::parse_for(&this): &AST {
    let tok = .consume(TokenType::For)

    if .token_is(Identifier) and .peek(1).is_identifier("in") {
        return .parse_for_each(start_span: tok.span)
    }

    let init: &AST = null
    if .token_is(TokenType::Let) {
        init = .parse_statement()
    } else if not .consume_if(TokenType::Semicolon) {
        init = .parse_expression(end_type: TokenType::Semicolon)
        .consume(TokenType::Semicolon)
    }
    let cond = if {
        .consume_if(TokenType::Semicolon) => null
        else => {
            let res = .parse_expression(end_type: TokenType::Semicolon)
            .consume(TokenType::Semicolon)
            yield res
        }
    }
    let step = if {
        .token_is(TokenType::OpenCurly) => null
        else => {
            let res = .parse_expression(end_type: TokenType::OpenCurly)
            yield res
        }
    }
    let body = .parse_block()
    let node = AST::new(For, tok.span.join(body.span))
    node.u.loop.init = init
    node.u.loop.cond = cond
    node.u.loop.step = step
    node.u.loop.body = body
    return node
}

def Parser::parse_statement(&this): &AST {
    let node: &AST = null
    let start_span = .token().span

    match .token().type {
        TokenType::OpenCurly => node = .parse_block()
        TokenType::Return => {
            let tok = .consume(TokenType::Return)
            let expr: &AST = null
            if not .is_end_of_statement() {
                expr = .parse_expression(end_type: TokenType::Newline)
            }
            node = AST::new(Return, start_span.join(.token().span))
            node.u.ret.expr = expr
            node.u.ret.return_span = tok.span
            .consume_end_of_statement()
        }
        TokenType::Yield => {
            .consume(TokenType::Yield)
            let expr = .parse_expression(end_type: TokenType::Newline)
            node = AST::new(Yield, start_span.join(.token().span))
            node.u.child = expr
            .consume_end_of_statement()
        }
        TokenType::Break => {
            .consume(TokenType::Break)
            node = AST::new(Break, start_span.join(.token().span))
            .consume_end_of_statement()
        }
        TokenType::Continue => {
            .consume(TokenType::Continue)
            node = AST::new(Continue, start_span.join(.token().span))
            .consume_end_of_statement()
        }
        TokenType::While => {
            let tok = .consume(TokenType::While)
            let cond = .parse_expression(end_type: TokenType::OpenCurly)
            let body = .parse_block()
            node = AST::new(While, tok.span.join(body.span))
            node.u.loop.cond = cond
            node.u.loop.body = body
        }
        TokenType::Assert => {
            let start = .consume(TokenType::Assert)
            let expr = .parse_expression(end_type: TokenType::Newline)

            let msg: &AST = null
            let end_span = expr.span

            if .consume_if(TokenType::Comma) {
                msg = .parse_expression(end_type: TokenType::Newline)
                end_span = msg.span
            }

            let node = AST::new(Assert, start.span.join(end_span))
            node.u.assertion.expr = expr
            node.u.assertion.msg = msg
            return node
        }
        TokenType::Defer => {
            .consume(TokenType::Defer)
            let expr = .parse_expression(end_type: TokenType::Newline)
            node = AST::new(Defer, start_span.join(.token().span))
            node.u.child = expr
            .consume_end_of_statement()
        }
        TokenType::Import => {
            node = .parse_import()
            .consume_end_of_statement()
        }
        TokenType::For => node = .parse_for()
        TokenType::Let => {
            node = .parse_var_declaration()
        }
        TokenType::TypeDef => {
            .error(Error::new(.token().span, "TypeDefs are only allowed in the global scope"))
            .curr += 1
            .consume_tokens_until_newline()
        }
        TokenType::Const => {
            .error(Error::new(.token().span, "Constants are only allowed in the global scope"))
            .curr += 1
            .consume_tokens_until_newline()
        }
        else => {
            node = .parse_expression(end_type: TokenType::Newline)
            .consume_if(TokenType::Semicolon)
        }
    }

    return node
}

def Parser::parse_block(&this): &AST {
    if not .token_is(TokenType::OpenCurly) {
        .error(Error::new(.token().span, "Expected '{'"))
        return AST::new(Error, .token().span)
    }
    let start = .consume(TokenType::OpenCurly)

    let statements = Vector<&AST>::new()
    while not .token_is_eof_or(TokenType::CloseCurly) {
        let statement = .parse_statement()
        if statement? statements.push(statement)
    }

    if not .token_is(TokenType::CloseCurly) {
        .error(Error::new(.token().span, "Expected '}' at end of block"))
        return AST::new(Error, .token().span)
    }
    let end = .consume(TokenType::CloseCurly)

    let node = AST::new(Block, start.span.join(end.span))
    node.u.block.statements = statements
    return node
}

def Parser::parse_template_params(&this, sym: &Symbol, out_span: &Span = null) {
    let start = .consume(TokenType::LessThan).span
    let params = Vector<&Symbol>::new()
    while not .token_is_eof_or(TokenType::GreaterThan) {
        let type = .consume(TokenType::Identifier)
        let name = type.text
        let sym = Symbol::new(TypeDef, .ns, name, name, name, type.span)
        sym.u.type_def = Type::new_unresolved(name, type.span)
        sym.u.type_def.sym = sym

        params.push(sym)

        if not .token_is(TokenType::GreaterThan) {
            .consume(TokenType::Comma)
        }
    }
    let end = .consume(TokenType::GreaterThan).span
    if out_span? {
        *out_span = start.join(end)
    }

    sym.template = Template::new(params)
}

def Parser::add_doc_comment(&this, sym: &Symbol, token: &Token) {
    if token.comment? {
        sym.comment = token.comment
        sym.comment_loc = token.comment_loc
    }

    if .attrs.size > 0 and .attrs_start_tok.comment? {
        if not sym.comment? {
            sym.comment = .attrs_start_tok.comment
            sym.comment_loc = .attrs_start_tok.comment_loc
        }
    }
}

def Parser::parse_function_args(&this, func: &Function, end: TokenType, need_types: bool = true) {
    let seen_default = false
    while not .token_is_eof_or(end) {

        // Ellipses are only allowed as the last parameter, so we break early if we see one
        if .token_is(Ellipsis) {
            if seen_default {
                .error(Error::new(.token().span, "Cannot have variadic parameters and default parameters"))
            }
            .consume(TokenType::Ellipsis)
            func.is_variadic = true
            break
        }

        let found_amp = .consume_if(TokenType::Ampersand)
        let var_name = .consume(TokenType::Identifier)
        let type: &Type = null
        if func.params.is_empty() and func.kind == Method {
            if var_name.text.eq("this") {
                type = func.parent_type
                if found_amp {
                    type = Type::new_resolved(BaseType::Pointer, func.parent_type.span)
                    type.u.ptr = func.parent_type
                }
                func.is_static = false
            } else if found_amp {
                .error(Error::new(var_name.span, "Expected 'this' over here"))
            }
        }
        if not type? {
            if need_types or .token_is(Colon) {
                .consume(TokenType::Colon)
                type = .parse_type()
            }
        }

        let default_value: &AST = null
        if .consume_if(TokenType::Equals) {
            default_value = .parse_expression(end_type: TokenType::Comma)
            seen_default = true

        } else if seen_default {
            .error(Error::new(var_name.span, "Cannot have non-default parameters after default parameters"))
        }

        let var = Variable::new(type)
        var.sym = Symbol::from_local_variable(var_name.text, var, var_name.span)
        var.default_value = default_value
        func.params.push(var)

        .add_doc_comment(var.sym, var_name)

        if not .token_is(end) {
            .consume(TokenType::Comma)
        }
    }
}

def Parser::parse_function_body(&this, func: &Function): &AST {
    if .token().type != FatArrow {
        func.is_arrow = false
        return .parse_block()
    }

    func.is_arrow = true
    let arrow = .consume(TokenType::FatArrow)
    if .token_is(TokenType::OpenCurly) {
        .error(Error::new(.token().span, "Expected an expression for an arrow function"))
        return null
    }

    let stmt = .parse_expression(end_type: TokenType::Newline)
    return stmt
}

def Parser::parse_closure(&this): &Function {
    let start = .consume(Line)
    let func = Function::new()
    func.name_ast = null
    func.kind = Closure

    .parse_function_args(func, Line, need_types: false)
    let end_span = .consume(Line).span

    if .consume_if(TokenType::Colon) {
        func.return_type = .parse_type()
        end_span = func.return_type.span
    } else {
        func.return_type = null  // Leave this as null so we can infer it later
    }

    func.parsed_return_type = func.return_type
    func.body = .parse_function_body(func)
    func.span = start.span.join(func.body.span)
    return func
}

def Parser::parse_function(&this): &Function {
    let start = .consume(TokenType::Def)

    let parent_type: &Type = null
    let kind = FunctionKind::Normal

    let ident = .parse_scoped_identifier(consume_template: false)
    if not ident? return null

    let name_span = ident.span

    let func = Function::new()
    func.name_ast = ident
    func.is_static = true
    func.kind = Normal
    let name = match ident.type {
        ASTType::Identifier => ident.u.ident.name
        ASTType::NSLookup => {
            parent_type = Type::new_unresolved("<unresolved>", ident.span)
            parent_type.u.unresolved = ident.u.lookup.lhs
            kind = Method
            name_span = ident.u.lookup.rhs_span
            func.parent_type = parent_type
            func.kind = Method
            yield ident.u.lookup.rhs_name
        }
        else => {
            .error(Error::new(ident.span, "Expected identifier"))
            yield "<error>"
        }
    }

    func.sym = Symbol::new_with_parent(Function, .ns, .ns.sym, name, name_span)
    func.sym.u.func = func
    .add_doc_comment(func.sym, start)

    if .token_is(TokenType::LessThan) {
        .parse_template_params(func.sym)
    }

    .consume(TokenType::OpenParen)
    .parse_function_args(func, CloseParen)
    let end_span = .consume(CloseParen).span

    let returns = false
    if .consume_if(TokenType::Colon) {
        func.return_type = .parse_type()
        end_span = func.return_type.span
        returns = true

    } else if func.sym.full_name.eq("main") {
        func.return_type = Type::new_unresolved_base(BaseType::I32, name_span)
        returns = true

    } else {
        func.return_type = Type::new_unresolved_base(BaseType::Void, name_span)

        // TODO: Deprecate this once we've fully moved to attributes
        if .token_is(TokenType::Identifier) and .token().text.eq("exits") {
            end_span = .consume(TokenType::Identifier).span
            func.exits = true
        }
    }

    func.parsed_return_type = func.return_type

    // TODO: Deprecate this once we've fully moved to attributes
    .parse_extern_into_symbol(func.sym)

    for attr in .attrs.iter() {
        match attr.type {
            Exits => func.exits = true
            Extern => .get_extern_from_attr(func.sym, attr)
            VariadicFormat => {
                if not func.is_variadic {
                    .error(Error::new(
                        attr.span, "Variadic format attribute can only be used on variadic functions"
                    ))
                }
                func.is_variadic_format = true
            }
            Operator => {
                let op = Operator::from_operator_overload(attr.args.at(0), func.params)
                if op == Error {
                    .error(Error::new(attr.span, "Invalid operator"))
                    continue
                }
                if not func.operator_overloads? {
                    func.operator_overloads = Vector<Operator>::new()
                }
                func.operator_overloads.push(op)
            }
            Alive => .program.explicit_alive_symbols.push(func.sym)
            else => .error(Error::new(attr.span, f"Invalid attribute for function: {attr.type}"))
        }
    }
    .clear_attributes()

    if func.sym.is_extern {
        func.span = start.span.join(end_span)
        return func
    }

    .curr_func = func

    func.body = .parse_function_body(func)

    .curr_func = null
    func.span = start.span.join(func.body.span)
    return func
}

def Parser::parse_extern_into_symbol(&this, sym: &Symbol) {
    if not .consume_if(TokenType::Extern) return
    sym.is_extern = true
    if .token_is(TokenType::OpenParen) {
        .consume(TokenType::OpenParen)
        let name = .consume(TokenType::StringLiteral)
        .consume(TokenType::CloseParen)
        sym.extern_name = name.text
    } else {
        sym.extern_name = sym.name
    }
}

def Parser::get_extern_from_attr(&this, sym: &Symbol, attr: &Attribute) {
    assert attr.type == Extern
    sym.is_extern = true
    if attr.args.size > 0 {
        sym.extern_name = attr.args.at(0)
    } else {
        sym.extern_name = sym.name
    }
}

def Parser::parse_import_path(&this, end_type: TokenType): &Vector<&ImportPart> {
    let parts = Vector<&ImportPart>::new()

    while true {
        let done = false

        if not .token_is(end_type) and .token().is_word() {
            let word = .token()
            .curr += 1

            let part = ImportPart::new(Single, word.span)
            part.u.single.name = word.text
            part.u.single.name_span = word.span

            if .consume_if(TokenType::As) {
                let alias = .consume(TokenType::Identifier)
                part.u.single.alias = alias.text
                part.u.single.alias_span = alias.span
                done = true
            }

            parts.push(part)

        } else if .token_is(TokenType::Star) {
            let tok = .consume(TokenType::Star)

            let part = ImportPart::new(Wildcard, tok.span)
            parts.push(part)
            done = true

        } else if .token_is(TokenType::OpenCurly) {
            let open = .consume(TokenType::OpenCurly)

            let sub_paths = Vector<&Vector<&ImportPart>>::new()
            while not .token_is_eof_or(TokenType::CloseCurly) {
                let sub_path = .parse_import_path(CloseCurly)
                if not sub_path? return null

                sub_paths.push(sub_path)
                if not .consume_if(TokenType::Comma) break
            }
            let close = .consume(TokenType::CloseCurly)

            let part = ImportPart::new(Multiple, open.span.join(close.span))
            part.u.multiple.paths = sub_paths
            part.u.multiple.open_curly_span = open.span
            part.u.multiple.close_curly_span = close.span
            parts.push(part)
            done = true

        } else {
            .error(Error::new(.token().span, "Expected identifier"))
            let prev_tok = .tokens[.curr - 1].span
            let part = ImportPart::new(Single, Span(prev_tok.end, prev_tok.end))
            part.u.single.name = null
            part.u.single.name_span = part.span
            parts.push(part)
            done = true
        }

        if done break
        if not (
            .consume_if(TokenType::ColonColon) or
            .consume_if(TokenType::Slash)
        ) break
    }
    return parts
}

def Parser::parse_import(&this): &AST {
    let span = .token().span
    .consume(TokenType::Import)

    let parent_count = 0
    let type = match .token().type {
        TokenType::AtSign => {
            .consume(TokenType::AtSign)
            yield ImportType::ProjectNamespace
        }
        TokenType::ColonColon | TokenType::Slash => {
            .consume(.token().type)
            yield ImportType::CurrentScope
        }
        TokenType::Dot | TokenType::Ellipsis => {
            let done = false
            while not done {
                match .token().type {
                    TokenType::Dot => {
                        .consume(TokenType::Dot)
                        parent_count += 1
                    }
                    TokenType::Ellipsis => {
                        .consume(TokenType::Ellipsis)
                        parent_count += 3
                    }
                    else => done = true
                }
            }
            yield ImportType::ParentNamespace
        }
        else => ImportType::GlobalNamespace
    }

    // If this is a "top-level" module, this is already at the parent directory level.
    if .ns.is_dir_with_mod {
        parent_count -= 1
    }

    let parts = .parse_import_path(Newline)
    if not parts? return null

    if parts.size == 0 {
        .error(Error::new(span, "Invalid import statement"))
        return null
    }

    let node = AST::new(Import, span)
    node.u.import_path = Import(
        parts,
        type,
        parent_count,
        export: false,
        root_sym: null
    )

    for attr in .attrs.iter() {
        match attr.type {
            Export => node.u.import_path.export = true
            else => .error(Error::new(attr.span, "Invalid attribute for import"))
        }
    }

    // We only want to actually import the file(s) once we're done parsing up until
    // the end of this file, this is to better handle cases where we have circular
    // depencies between files.
    .ns.unhandled_imports.push(node)
    return node
}

def Parser::parse_struct_field(&this, struc: &Structure): bool {
    // To allow `x, y, z: i32` syntax, we need to first parse all the identifiers
    // before we parse the type. All the identifiers are stored in here.
    let fields = Vector<&Variable>::new(capacity: 1)

    .parse_attributes_if_any()
    while true {
        if not .token_is(Identifier) {
            .error(Error::new(.token().span, "Expected identifier for field name"))
            return false
        }

        let name = .consume(TokenType::Identifier)
        let var = Variable::new(null)
        var.sym = Symbol::from_local_variable(name.text, var, name.span)
        .add_doc_comment(var.sym, name)

        fields.push(var)

        if not .consume_if(TokenType::Comma) break
    }

    if fields.size == 1 {
        let field = fields[0]
        for attr in .attrs.iter() {
            match attr.type {
                Extern => .get_extern_from_attr(field.sym, attr)
                Atomic => field.is_atomic = true
                else => .error(Error::new(attr.span, "Invalid attribute for field"))
            }
        }

    } else if fields.size > 1 and .attrs.size > 0 {
        .error(Error::new_note(
            fields[0].sym.span, "Can't use attributes on multi-field declaration",
            "Split this into separate field declarations"
        ))
    }

    if not .consume_if(TokenType::Colon) {
        .error(Error::new(.token().span, "Expected ':' after struct field names for type"))
        return false
    }

    let type = .parse_type()

    let default_value: &AST = null
    if .consume_if(TokenType::Equals) {
        default_value = .parse_expression(end_type: TokenType::Comma)
    }

    for var in fields.iter() {
        var.type = type
        var.parsed_type = type
        var.default_value = default_value
        struc.fields.push(var)
    }

    fields.free()
    return true
}

def Parser::parse_struct(&this): &Structure {
    let start = .token()
    let is_union = if .token_is(TokenType::Union) {
        .consume(TokenType::Union)
        yield true
    } else {
        .consume(TokenType::Struct)
        yield false
    }

    let name = .consume(TokenType::Identifier)
    let struc = Structure::new()
    struc.is_union = is_union
    struc.sym = Symbol::new_with_parent(Structure, .ns, .ns.sym, name.text, name.span)
    struc.sym.u.struc = struc
    .add_doc_comment(struc.sym, start)

    if .token_is(TokenType::LessThan) {
        .parse_template_params(struc.sym)
    }

    // TODO: Deprecate this once we've fully moved to attributes
    .parse_extern_into_symbol(struc.sym)

    for attr in .attrs.iter() {
        match attr.type {
            Extern => .get_extern_from_attr(struc.sym, attr)
            Formatting => {
                struc.format_spec = attr.args.at(0)
                struc.format_args = attr.args.at(1)
            }
            else => .error(Error::new(attr.span, "Invalid attribute for struct"))
        }
    }

    // Extern structs don't need to have a body.
    if not struc.sym.is_extern or .token_is(TokenType::OpenCurly) {
        .consume(TokenType::OpenCurly)
        while not .token_is_eof_or(TokenType::CloseCurly) {
            if not .parse_struct_field(struc) break
            if not .token_is(TokenType::CloseCurly) {
                .consume_newline_or(TokenType::Comma)
            }
        }
        let end = .consume(TokenType::CloseCurly)
        struc.span = start.span.join(end.span)
    }

    return struc
}

def Parser::parse_enum(&this): &Enum {
    let start = .consume(Enum)
    let name = .consume(Identifier)

    let enom = Enum::new(start.span)
    let sym = Symbol::new_with_parent(Enum, .ns, .ns.sym, name.text, name.span)
    sym.u.enom = enom
    enom.sym = sym

    if .token_is(TokenType::LessThan) {
        .parse_template_params(enom.sym)
    }

    .add_doc_comment(sym, start)
    enom.has_values = false

    let is_extern = false
    for attr in .attrs.iter() {
        match attr.type {
            Extern => {
                .get_extern_from_attr(enom.sym, attr)
                is_extern = true
            }
            else => .error(Error::new(attr.span, "Invalid attribute for value enum"))
        }
    }

    if .token_is(Extern) {
        .parse_extern_into_symbol(enom.sym)
    }

    .consume(OpenCurly)
    while not .token_is_eof_or(CloseCurly) {
        // Parse any attributes for the enum value
        .parse_attributes_if_any()

        let name = .consume(Identifier)

        // Shared field
        if .consume_if(Colon) {
            let type = .parse_type()
            let var = Variable::new(type)
            var.sym = Symbol::from_local_variable(name.text, var, name.span)
            .add_doc_comment(var.sym, name)
            enom.shared_fields.push(var)

            if .consume_if(Equals) {
                var.default_value = .parse_expression(end_type: TokenType::Comma)
            }

            .consume_if(Comma)
            enom.has_values = true
            continue
        }


        let variant = EnumVariant::new(name.span)
        let vsym = Symbol::new_with_parent(EnumVariant, .ns, sym, name.text, name.span)
        vsym.u.enum_var = variant
        variant.sym = vsym
        variant.parent = enom
        .add_doc_comment(vsym, name)

        if .token_is(OpenParen) {
            let start = .consume(OpenParen)
            while not .token_is_eof_or(CloseParen) {
                let ident = .consume(Identifier)
                .consume(Colon)
                let type = .parse_type()
                let var = Variable::new(type)
                var.sym = Symbol::from_local_variable(ident.text, var, ident.span)

                if .consume_if(Equals) {
                    var.default_value = .parse_expression(end_type: TokenType::Comma)
                }

                enom.has_values = true
                variant.specific_fields.push(var)
                .consume_if(Comma)
            }
            let end = .consume(CloseParen)
            if is_extern and variant.num_fields() > 0 {
                .error(Error::new(start.span + end.span, "Extern value enum variants cannot have fields"))
            }
        }

        // FIXME: Deprecate this
        if .consume_if(TokenType::Equals) {
            .parse_extern_into_symbol(variant.sym)
            if enom.has_values {
                .error(Error::new(variant.sym.span, "Non-trivial value enums can't be extern"))
            }
        }
        for attr in .attrs.iter() {
            match attr.type {
                Extern => {
                    .get_extern_from_attr(variant.sym, attr)
                    if enom.has_values {
                        .error(Error::new(variant.sym.span, "Non-trivial value enums can't be extern"))
                    }
                }
                else => .error(Error::new(attr.span, "Invalid attribute for value enum variant"))
            }
        }

        enom.variants += variant
        .consume_if(Comma)
    }
    let end_tok =.consume(CloseCurly)
    enom.span = start.span + end_tok.span
    return enom
}

def Parser::parse_attribute(&this) {
    let start = .consume(TokenType::OpenSquare)
    if .attrs.size == 0 {
        .attrs_span = start.span
        .attrs_start_tok = start
    }

    // FIXME: Should `extern` be a keyword once we have fully moved to attrs?
    if not (.token_is(Identifier) or .token_is(Extern)) {
        .error(Error::new(.token().span, "Expected attribute name here"))
        return
    }

    let name = .consume(.token().type)
    let attr_type = AttributeType::from_str(name.text)
    if attr_type == Invalid {
        .error(Error::new(name.span, "Unknown attribute type"))
        return
    }
    let attr = Attribute::new(attr_type, name.span)

    while not .token_is_eof_or(TokenType::CloseSquare) {
        if not .token_is(StringLiteral) {
            .error(Error::new(.token().span, "Only string literals supported in attribute arguments"))
            .curr += 1
            continue
        }

        let arg = .consume(TokenType::StringLiteral)
        attr.args.push(arg.text)
    }
    let close = .consume(TokenType::CloseSquare)
    .attrs_span = .attrs_span.join(close.span)

    // We don't want to handle invalid attributes, so we just ignore them.
    if not attr.validate(this) return

    .attrs.push(attr)
}

//! Clear the previous attributes, and parse any new ones
def Parser::parse_attributes_if_any(&this) {
    .clear_attributes()
    while .token_is(OpenSquare) {
        .parse_attribute()
    }
}

def Parser::parse_namespace_until(&this, end_type: TokenType) {
    .add_doc_comment(.ns.sym, .token())

    let ctx = .program.add_error_context()
    if ctx.set_jump_point() > 0 {
        // Presumably, we've seen some error while parsing this file. Try to sync
        // to the next top-level declaration.
        .sync_toplevel()
    }

    while not .token_is_eof_or(end_type) {

        .parse_attributes_if_any()
        match .token().type {
            Def => {
                let func = .parse_function()
                if func? then .ns.functions.push(func)
            }
            Import => {
                let import_ = .parse_import()
                if import_? then .ns.imports.push(import_)   // For typechecker...
            }
            Namespace => {
                if .attrs.size > 0 {
                    .error(Error::new(.token().span, "Attributes are not allowed on namespaces"))
                }

                let start = .consume(TokenType::Namespace).span
                let name = .consume(TokenType::Identifier)

                let old_ns = .ns
                let new_ns = Namespace::new(.ns, .ns.path)
                new_ns.sym = Symbol::new_with_parent(Namespace, old_ns, old_ns.sym, name.text, name.span)
                new_ns.sym.u.ns = new_ns

                new_ns.always_add_to_scope = true
                old_ns.namespaces.insert(name.text, new_ns)

                .ns = new_ns
                .consume(TokenType::OpenCurly)
                .parse_namespace_until(TokenType::CloseCurly)
                let end = .consume(TokenType::CloseCurly).span
                new_ns.span = start.join(end)

                .ns = old_ns
            }
            Struct | Union => {
                let struc = .parse_struct()
                if struc? then .ns.structs.push(struc)
            }
            TypeDef => {
                if .attrs.size > 0 {
                    .error(Error::new(.token().span, "Attributes are not allowed on typedefs"))
                }

                let start = .consume(TokenType::TypeDef).span
                let name = .consume(TokenType::Identifier)
                .consume(TokenType::Equals)
                let type = .parse_type()
                .consume_end_of_statement()

                let sym = Symbol::new(TypeDef, .ns, name.text, name.text, name.text, name.span)
                sym.u.type_def = type
                type.sym = sym

                if type? {
                    .ns.typedefs.insert(name.text, type)
                }
            }
            Enum => {
                let enom = .parse_enum()
                if enom? then .ns.enums.push(enom)
            }
            Let => {
                let var = .parse_global_value(is_const: false)
                if var? then .ns.variables.push(var)
            }
            Const => {
                let con = .parse_global_value(is_const: true)
                if con? then .ns.constants.push(con)
            }
            AtSign => .parse_compiler_option()
            else => {
                .error(Error::new(.token().span, `Unexpected token in Parser: {.token().type}`))
                .curr += 1
            }
        }
    }

    .program.pop_error_context()

    // After we've parsed everything in this file, go ahead and perform the imports
    while .ns.unhandled_imports.size > 0 {
        let imp = .ns.unhandled_imports.pop()
        .load_import_path(imp)
    }
}

def Parser::parse_compiler_option(&this) {
    if .attrs.size > 0 {
        .error(Error::new(.token().span, "Attributes are not allowed on compiler options"))
    }

    .consume(TokenType::AtSign)
    let compiler = .consume(TokenType::Identifier)
    if not compiler.text.eq("compiler") {
        .error(Error::new(compiler.span, "Expected 'compiler'"))
    }

    let name = .consume(TokenType::Identifier)
    match name.text {
        "c_include" => {
            let filename = .consume(TokenType::StringLiteral)
            .program.c_includes.push(filename.text)
        }
        "c_flag" => {
            let flag = .consume(TokenType::StringLiteral)
            .program.c_flags.push(flag.text)
        }
        "c_embed" => {
            let path = .consume(TokenType::StringLiteral)

            let cur_dir = if .ns.is_dir_with_mod {
                yield .ns.path
            } else {
                yield .ns.parent.path
            }

            let full_path = f"{cur_dir}/{path.text}"
            if not fs::file_exists(full_path) {
                .error(Error::new(path.span, f"File '{full_path}' does not exist"))
                return
            }

            let contents = fs::read_file(full_path)
            .program.c_embeds.insert(full_path, contents.str())
        }
        else => .error(Error::new(name.span, "Unknown compiler option"))
    }
}

def Parser::try_load_mod_for_namespace(&this, ns: &Namespace) {
    if ns.is_dir_with_mod return

    let mod_path = f"{ns.path}/mod.oc"
    // The `not ns.is_dir_with_mod` check is not strictly necessary, but it's just
    // an early exit in case we've already loaded in the `mod.oc` file.
    if fs::file_exists(mod_path){
        ns.is_dir_with_mod = true
        let parser = Parser::make(.program, ns)
        parser.load_file(mod_path)
    } else {
        mem::free(mod_path)
    }
}

def Parser::load_single_import_part(&this, base: &Namespace, name: str, span: Span): &Namespace {
    .try_load_mod_for_namespace(base)

    if not name? return null
    let sym = base.find_importable_symbol(name)

    // Special case for "this", we are not allowed to have a module with that name.
    // This is because we use "this" to refer to the current namespace in an import
    if name.eq("this") return base

    if sym? and sym.type != Namespace then return base
    let next = if sym? then sym.u.ns else null

    let part_path = `{base.path}/{name}`
    if not next? {
        let dir_exists = directory_exists(part_path)
        let path = `{base.path}/{name}.oc`
        let file_exists = fs::file_exists(path)

        if not dir_exists and not file_exists {
            .error(Error::new(span, `Could not find import path {part_path}(.oc)`))
            return null
        }

        next = Namespace::new(parent: base, path: part_path)
        next.sym = Symbol::new_with_parent(
            Namespace,
            ns: base,
            parent: base.sym,
            name,
            span
        )
        next.sym.u.ns = next

        base.namespaces.insert(name, next)

        if file_exists {
            let parser = Parser::make(.program, next)
            parser.load_file(path.copy())
        } else {
            // println(f" ++ Trying to load mod for {next.sym.name}")
            .try_load_mod_for_namespace(next)
        }
        mem::free(path)
    }

    return next
}

def Parser::load_import_path_from_base(&this, parts: &Vector<&ImportPart>, base: &Namespace): bool {
    for let i = 0; i < parts.size and (not base.is_a_file or base.is_dir_with_mod); i += 1 {
        let part = parts.at(i)

        match part.type {
            Wildcard => {
                .error(Error::new(part.span, `Wildcard import is not allowed from non-module`))
                return false
            }
            Multiple => {
                let paths = part.u.multiple.paths
                let success = true
                for path in paths.iter() {
                    success = .load_import_path_from_base(path, base) and success
                }
                return success
            }
            Single => {
                base = .load_single_import_part(base, part.u.single.name, part.span)
                if not base? return false
            }
        }
    }
    return true
}

struct LibraryInfo {
    parent_dir: str
    path: str
}

def Parser::find_external_library(&this, name: str): LibraryInfo {
    for lib_path in .program.library_paths.iter() {
        let dir_path = if lib_path.len() > 0 then  f"{lib_path}/{name}" else name.copy()
        if directory_exists(dir_path) {
            return LibraryInfo(
                fs::realpath(lib_path),
                fs::realpath(dir_path),
            )
        }
        mem::free(dir_path)

        let file_path = if lib_path.len() > 0 then  f"{lib_path}/{name}.oc" else f"{name}.oc"
        if fs::file_exists(file_path) {
            return LibraryInfo(
                fs::realpath(lib_path),
                fs::realpath(file_path),
            )
        }
        mem::free(file_path)
    }
    return LibraryInfo(null, null)
}

def Parser::import_from_stdlib(&this, name: str, span: Span): &Namespace {
    let std_ns = .find_or_import_stdlib()
    let ns = std_ns.namespaces.get(name, null)
    if not ns? {
        ns = .load_single_import_part(base: std_ns, name, span)
    }
    return ns
}

//* Finds the library with the name provided, and loads it into the program.
def Parser::import_external_lib(&this, name: str): &Namespace {
    let lib = .find_external_library(name)
    if not lib.path? return null

    let ns = Namespace::new(parent: .program.global, path: lib.path)
    ns.sym = Symbol::new_with_parent(
        Namespace,
        ns: .program.global,
        parent: .program.global.sym,
        name: name,
        Span::default()
    )
    ns.sym.u.ns = ns
    ns.always_add_to_scope = true
    ns.internal_project_root = ns

    if fs::directory_exists(lib.path) {
        .try_load_mod_for_namespace(ns)

    } else {
        let parser = Parser::make(.program, ns)
        parser.load_file(lib.path)
        parser.free()
    }
    return ns
}

def Parser::load_import_path(&this, import_stmt: &AST): bool {
    let path = &import_stmt.u.import_path

    let base = match path.type {
        GlobalNamespace => {
            let parts = path.parts
            assert parts.size > 0, "Expected at least one part in import path"
            assert parts.at(0).type == Single, "Expected first part to be a single import"

            let first_part = parts.at(0).u.single
            let lib_name = first_part.name

            if not .program.global.namespaces.contains(lib_name) {
                let lib = .import_external_lib(lib_name)
                if not lib? {
                    .error(Error::new(import_stmt.span, `Could not find library '{lib_name}'`))
                    return false
                }

                .program.global.namespaces.insert(lib_name, lib)
            }

            yield .program.global
        }
        ProjectNamespace => .ns.get_project_root(import_stmt.span, .program)
        ParentNamespace => {
            let cur = .ns
            for let i = 0; i < path.parent_count; i += 1 {
                if not cur.parent? {
                    let first_part = path.parts.at(0)
                    .error(Error::new(first_part.span, "Cannot import from parent of root namespace"))
                    .program.get_error_context().jump_back(1)
                }
                cur = cur.parent
            }
            yield cur
        }
        // We shouldn't have to import any files here, since they should already
        // be in the current scope.
        CurrentScope => {
            return true
        }
    }

    if not base? return false
    .load_import_path_from_base(path.parts, base)
    return true
}

def Parser::load_file(&this, filename: str, contents: str = null) {
    if .program.sources.contains(filename) return
    let loc = Location(filename.copy(), 0, 0, 0)
    let span = Span(loc, loc)
    .ns.span = span
    .ns.sym.span = span

    if not contents? {
        contents = fs::read_file(filename).str()
    }
    .program.sources.insert(filename, contents)

    let lexer = Lexer::make(contents, filename, .program.errors)
    .tokens = lexer.lex()
    .curr = 0

    .ns.is_a_file = true

    let start = .token().span
    .parse_namespace_until(TokenType::EOF)
    let end = .token().span
    .ns.span = start.join(end)
}

def Parser::couldnt_find_stdlib(&this) {
    println("--------------------------------------------------------------------------------")
    println("    Could not find standard library. Set OCEN_ROOT environment variable.")
    println("      Alternatively, compile from the root of `ocen` repository.")
    println("--------------------------------------------------------------------------------")
    .program.get_error_context().jump_back(1)
}

def Parser::find_or_import_stdlib(&this): &Namespace {
    let std_ns = .program.global.namespaces.get("std", null)
    if not std_ns? {
        let std_ns = .import_external_lib("std")
        .program.global.namespaces.insert("std", std_ns)
    }
    return std_ns
}

def Parser::include_prelude_only(&this) {
    // Want to manually include the prelude
    let stdlib = .find_external_library("std")
    if not stdlib.path? {
        .couldnt_find_stdlib()
    }
    let prelude_path = f"{stdlib.path}/prelude.h"
    if not fs::file_exists(prelude_path) {
        .couldnt_find_stdlib()
    }
    let content = fs::read_file(prelude_path)
    .program.c_embeds.insert(prelude_path, content.str())
}

//! This function is a bit of a hot-mess, it needs to basically be completely re-thought,
//! and combined with the logic from some of the other functions above.
//!
//! General Idea: Given an input file we are loading to the compiler, say `foo/bar/baz.oc`
//!               There's two possible options: It's either a standalone script or project.
//! Definitions:
//!   - Standalone: One-file script, no project-relative imports etc allowed. We just load the file.
//!   - Project: A project is a collection of files where we are allowed to do project-relative imports.
//!              In order to work with project-relative imports, we need to know the project root. A project
//!              *must* define it's root by having a `main.oc` file in the root directory. No other file anywhere
//!              in the project should have the name `main.oc`.
//!
//! The `single_flag` file below is supposed to tell us whether we are loading a standalone file or a project.
//! ***HOWEVER***: Currently, we don't really have a way of figuring this out automatically.
//!
//! Solution: We will naively try to traverse up the file system until we find a `main.oc` file. If we do, we
//!           consider it a project, and load the file as such. If we don't, we consider it a standalone file.
//!           In the future, we need to add flags to the compiler to be able to specify this.
def Parser::create_namespaces_for_initial_file(&this, filename: str, single_file: bool) {
    if not .program.include_stdlib {
        .include_prelude_only()
        return
    }

    // NOTE: We currently special-case the standard library path, since it's also a "project root"
    // for the standard library. We want to do this for all external libraries in the future, and have
    // some way of indicating it other than `main.oc` file.
    let std_lib_ns = .import_external_lib("std")
    if not std_lib_ns? then .couldnt_find_stdlib()
    let std_lib_ns_path = fs::realpath(std_lib_ns.path)

    let cur = fs::realpath(filename)
    if not cur? {
        .error(Error::new(Span::default(), f"Could not find file: {filename}"))
        .program.get_error_context().jump_back(1)
    }
    let namespace_paths = Vector<str>::new()
    let found_root = false
    while true {
        let base = dirname(cur.copy()).copy()

        namespace_paths.push(base)
        if base.eq("/") break

        if single_file break
        let potential_main_path = `{base}/main.oc`
        let main_exists = fs::file_exists(potential_main_path)
        potential_main_path.free()

        // What about other libraries??
        if base.eq(std_lib_ns_path) or main_exists {
            found_root = true
            break
        }
        cur = base
    }

    // If we didn't find a root, treat this as a standalone file. Only create one
    // directory above the file itself.
    let start: i32 = if found_root then namespace_paths.size as i32 else 0

    // Create all the necessary namespaces
    let cur_ns = .program.global
    for let i = start - 1; i >= 0; i -= 1 {
        let path = namespace_paths.data[i]
        let t1 = path.copy()
        let base = basename(t1).copy()
        t1.free()

        // If we've already loaded this before, skip
        // (This only happens for stdlib imports, which we've already loaded)
        if cur_ns.namespaces.contains(base) {
            cur_ns = cur_ns.namespaces.at(base)
            continue
        }

        let new_ns = Namespace::new(parent: cur_ns, path: path)
        let loc = Location(path, 0, 0, 0)
        new_ns.sym = Symbol::new_with_parent(Namespace, cur_ns, cur_ns.sym, base, Span(loc, loc))
        new_ns.sym.u.ns = new_ns

        if i == (start - 1) {
            new_ns.internal_project_root = new_ns
        }

        cur_ns.namespaces.insert(base, new_ns)
        cur_ns = new_ns
    }

    // Remove file extension
    let file_base = basename(filename).copy()
    if file_base.ends_with(".oc") {
        file_base[file_base.len() - 3] = '\0'
    }

    // If this is a `mod.oc` file, we don't create a separate namespace for it.
    if file_base.eq("mod") {
        cur_ns.is_dir_with_mod = true
        .ns = cur_ns
        return
    }

    // This almost certainly means we're looking at something that's in the standard library.
    // This is likely happening in LSP mode, so we don't particularly care about adjusting the
    // `full_name` field of the symbol here since we're not going to make it to codegen anyway.
    if cur_ns.namespaces.contains(file_base) {
        .ns = cur_ns.namespaces.at(file_base)
        return
    }

    // Create the namespace for the file
    let child_ns = Namespace::new(parent: cur_ns, path: filename)
    child_ns.sym = Symbol::new(Namespace,
        ns: cur_ns,
        name: file_base,
        display: "",
        full_name: "",
        Span::default()
    )
    child_ns.sym.u.ns = child_ns
    cur_ns.namespaces.insert(file_base, child_ns)

    // If generating code, don't prefix symbols in the file explicitly
    // specified as the input file.
    child_ns.sym.full_name = ""
    .ns = child_ns
}

def Parser::parse_toplevel(program: &Program, filename: str, file_contents: str = null, include_workspace_main: bool = true) {
    // Fallback for any unhandled errors...
    let ctx = program.add_error_context()
    if ctx.set_jump_point() > 0 {
        println("Error in parse_toplevel context")
        return
    }

    let parser = Parser::make(program, program.global)
    if program.include_stdlib {
        parser.find_or_import_stdlib()
    } else {
        parser.include_prelude_only()
    }
    parser.create_namespaces_for_initial_file(filename, false)
    parser.load_file(filename, file_contents)

    let file_ns = parser.ns
    if include_workspace_main and file_ns.internal_project_root? {
        let potential_main = f"{file_ns.internal_project_root.path}/main.oc"
        if fs::file_exists(potential_main) {
            let main_ns = file_ns.internal_project_root.namespaces.get("main", null)
            if main_ns == file_ns return

            if not main_ns? {
                // FIXME: why am I having to create the namespace here manually?
                let root = file_ns.internal_project_root
                main_ns = Namespace::new(parent: root, path: "main")
                main_ns.sym = Symbol::new_with_parent(Namespace, root, root.sym, "main", Span::default())
                main_ns.sym.u.ns = main_ns
                root.namespaces.insert("main", main_ns)
            }

            parser.ns = main_ns
            parser.load_file(potential_main)
        } else {
            potential_main.free()
        }
    }
}