// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>
// SPDX-License-Identifier: MIT

//! Turns source into a tree, resolving every name as it goes.
//!
//! Recursive descent, one function per level of precedence, which follows
//! Zig's own: from loosest to tightest, `or`, `and`, the comparisons,
//! `orelse`, `+ - ++`, `* / %`, then the prefix operators. As in Zig an `if`
//! is a primary expression whose branches extend as far right as they can,
//! so `1 + if (a) 2 else 3 * 4` is `1 + (if (a) 2 else (3 * 4))`.
//!
//! Every name is looked up when it is parsed. A `let` is only in scope after
//! its own `;`, which is the whole of why a program cannot recurse: nothing
//! can refer to itself, or to anything defined after it.
//!
//! `@include("path")` is done here too, not when evaluating: the host reads
//! the file, it is parsed where it is named, and its value becomes a slot of
//! its own, as if it were a `let` with no name. Files are named by `file:`
//! URIs, and the path in an `@include` is a URI reference resolved against
//! the URI of the file it is written in. Each file is parsed once
//! however often it is included, and a file that includes itself, however
//! indirectly, is an error, so includes cannot recurse either.

const std = @import("std");
const Allocator = std.mem.Allocator;

const ast = @import("ast.zig");
const Node = ast.Node;
const Builtin = ast.Builtin;
const Diagnostic = @import("Diagnostic.zig");
const Tokenizer = @import("Tokenizer.zig");
const Token = Tokenizer.Token;
const Tag = Tokenizer.Tag;
const Function = @import("eval.zig").Function;
const Uri = @import("uri").Uri;

const Parser = @This();

pub const Error = error{
    OutOfMemory,
    Syntax,
    /// A file named by `@include` could not be read. The diagnostic names
    /// the file, and the error the host returned.
    Include,
    /// The program's filename is not a `file:` URI naming a file on this
    /// machine. The diagnostic says why.
    InvalidFilename,
};

/// How a host reads the files a program names with `@include`.
pub const Include = struct {
    /// What the host wants handed back to it, as `read`'s `context`.
    context: ?*anyopaque = null,
    /// Return the contents of the file named by `file_uri`, or an error.
    ///
    /// `file_uri` is always a `file:` URI naming a file on this machine, in
    /// one spelling: `file:///path`, with an empty host and no query or
    /// fragment, and `.` and `..` resolved. It is what the program wrote,
    /// resolved against the URI of the file that includes it. Anything
    /// further, such as refusing a path outside some directory, is for the
    /// host to decide.
    ///
    /// What it returns must live as long as the program, which is so of
    /// anything allocated from `arena`: that belongs to the program, and is
    /// freed with it.
    read: *const fn (context: ?*anyopaque, arena: Allocator, file_uri: []const u8) anyerror![]const u8,
};

pub const Config = struct {
    /// The `file:` URI of the file the source was read from, for
    /// diagnostics and for resolving the files it includes against.
    name: ?[]const u8 = null,
    functions: []const Function = &.{},
    /// Null when the host does not support `@include`.
    include: ?Include = null,
    max_depth: u32 = 64,
    max_includes: u32 = 256,
};

/// A parsed program.
pub const Tree = struct {
    /// The program's file and every file it includes, in order of `base`.
    sources: []const Diagnostic.Source,
    root: *const Node,
    /// One per `let` and per `if` capture, in the order they were defined.
    /// A `let` has the expression it is bound to; a capture has null, and is
    /// filled in when its `if` is evaluated.
    slots: []const ?*const Node,
};

const Name = struct { name: []const u8, slot: u32 };

/// Names that mean something already and cannot be bound by `let` or `|x|`.
const reserved = std.StaticStringMap(void).initComptime(.{
    .{"ctx"}, .{"inf"}, .{"nan"},
});

arena: Allocator,
source: []const u8,
tok: Tokenizer,
cur: Token,
diag: *Diagnostic,
depth: u32 = 0,
max_depth: u32,
scope: std.ArrayList(Name) = .empty,
slots: std.ArrayList(?*const Node) = .empty,
functions: []const Function,
/// The name of the file being parsed, which `source` holds: the text of
/// `uri`.
name: ?[]const u8 = null,
uri: ?Uri = null,
/// Where `source` starts among the offsets of all of the program's files.
/// The tokenizer works in offsets into `source`, and the tree in offsets
/// into the whole program, so every position put into a node has this added.
base: u32 = 0,
sources: std.ArrayList(Diagnostic.Source) = .empty,
include: ?Include,
max_includes: u32,
/// Every file included so far, and the slot that holds its value: null
/// while the file is still being parsed, which is how a cycle is noticed.
files: std.StringHashMapUnmanaged(?u32) = .empty,

/// Parse `source`. Everything allocated, the tree included, belongs to
/// `arena`, and the tree points into `source`, which must outlive it.
pub fn parse(arena: Allocator, source: []const u8, config: Config, diag: *Diagnostic) Error!Tree {
    var p: Parser = .{
        .arena = arena,
        .source = source,
        .tok = .init(source),
        .cur = undefined,
        .diag = diag,
        .max_depth = config.max_depth,
        .functions = config.functions,
        .include = config.include,
        .max_includes = config.max_includes,
    };
    if (config.name) |name| {
        const u = Uri.parse(arena, name) catch |err| switch (err) {
            error.OutOfMemory => return error.OutOfMemory,
            else => {
                diag.set(.{}, "the filename '{s}' is not a URI", .{name});
                return error.InvalidFilename;
            },
        };
        p.uri = localFile(arena, u) catch |err| switch (err) {
            error.OutOfMemory => return error.OutOfMemory,
            else => |e| {
                diag.set(.{}, "the filename '{s}' {s}", .{ name, notLocal(e) });
                return error.InvalidFilename;
            },
        };
        p.name = try p.uri.?.toText(arena, .{});
        try p.files.put(arena, p.name.?, null);
    }
    if (source.len >= std.math.maxInt(u32)) {
        diag.setIn(p.name, .{}, "program too large", .{});
        return error.Syntax;
    }
    try p.sources.append(arena, .{ .name = p.name, .text = source, .base = 0 });
    const root = try p.parseFile();
    return .{ .sources = p.sources.items, .root = root, .slots = p.slots.items };
}

/// `let`s and then an expression: the whole of a file.
fn parseFile(self: *Parser) Error!*const Node {
    try self.advance();
    while (self.cur.tag == .keyword_let) try self.parseLet();
    const root = try self.parseExpr();
    if (self.cur.tag != .eof) return self.unexpected("an operator or the end of the program");
    return root;
}

// -- tokens -------------------------------------------------------------------

fn fail(self: *Parser, pos: u32, comptime fmt: []const u8, args: anytype) error{Syntax} {
    self.diag.setIn(self.name, .of(self.source, pos), fmt, args);
    return error.Syntax;
}

fn unexpected(self: *Parser, comptime wanted: []const u8) error{Syntax} {
    return self.fail(self.cur.start, "expected " ++ wanted ++ ", found {s}", .{self.cur.tag.describe()});
}

fn advance(self: *Parser) error{Syntax}!void {
    self.cur = self.tok.next();
    if (self.cur.tag != .invalid) return;
    const c = self.source[self.cur.start];
    return switch (c) {
        '"' => self.fail(self.cur.start, "unterminated string", .{}),
        '\'' => self.fail(self.cur.start, "unterminated character literal", .{}),
        '@' => self.fail(self.cur.start, "expected a builtin name or a quoted identifier after '@'", .{}),
        else => if (std.ascii.isPrint(c))
            self.fail(self.cur.start, "unexpected character '{c}'", .{c})
        else
            self.fail(self.cur.start, "unexpected byte 0x{x:0>2}", .{c}),
    };
}

fn expect(self: *Parser, tag: Tag) Error!Token {
    if (self.cur.tag != tag) {
        return self.fail(self.cur.start, "expected {s}, found {s}", .{ tag.describe(), self.cur.tag.describe() });
    }
    const t = self.cur;
    try self.advance();
    return t;
}

fn text(self: *const Parser, t: Token) []const u8 {
    return self.source[t.start..t.end];
}

fn node(self: *Parser, pos: u32, data: ast.Data) Error!*const Node {
    const n = try self.arena.create(Node);
    n.* = .{ .pos = self.base + pos, .data = data };
    return n;
}

fn enter(self: *Parser) error{Syntax}!void {
    self.depth += 1;
    if (self.depth > self.max_depth) return self.fail(self.cur.start, "expression nested too deeply", .{});
}

fn leave(self: *Parser) void {
    self.depth -= 1;
}

// -- names --------------------------------------------------------------------

/// An identifier token's name: as written, or decoded from `@"..."`.
fn identName(self: *Parser, t: Token) Error![]const u8 {
    return switch (t.tag) {
        .identifier => self.text(t),
        .quoted_identifier => self.decodeString(t.start + 2, t.end - 1),
        else => self.fail(t.start, "expected an identifier, found {s}", .{t.tag.describe()}),
    };
}

fn expectName(self: *Parser) Error!struct { []const u8, u32 } {
    const t = self.cur;
    const name = try self.identName(t);
    try self.advance();
    return .{ name, t.start };
}

/// Make `name` a new slot. Zig does not allow shadowing, and neither does
/// this: a name that is already bound is an error, not a new binding.
fn bind(self: *Parser, name: []const u8, pos: u32, value: ?*const Node) Error!u32 {
    if (reserved.has(name)) return self.fail(pos, "'{s}' is reserved and cannot be redefined", .{name});
    for (self.scope.items) |n| {
        if (std.mem.eql(u8, n.name, name)) return self.fail(pos, "'{s}' is already defined", .{name});
    }
    const slot: u32 = @intCast(self.slots.items.len);
    try self.slots.append(self.arena, value);
    try self.scope.append(self.arena, .{ .name = name, .slot = slot });
    return slot;
}

fn resolve(self: *Parser, name: []const u8, pos: u32) Error!*const Node {
    if (std.mem.eql(u8, name, "ctx")) return self.node(pos, .ctx);
    if (std.mem.eql(u8, name, "inf")) return self.node(pos, .{ .float = std.math.inf(f64) });
    if (std.mem.eql(u8, name, "nan")) return self.node(pos, .{ .float = std.math.nan(f64) });
    var i = self.scope.items.len;
    while (i > 0) {
        i -= 1;
        const n = self.scope.items[i];
        if (std.mem.eql(u8, n.name, name)) return self.node(pos, .{ .slot = n.slot });
    }
    return self.fail(pos, "unknown name '{s}'", .{name});
}

// -- statements ---------------------------------------------------------------

fn parseLet(self: *Parser) Error!void {
    try self.advance();
    const name, const pos = try self.expectName();
    _ = try self.expect(.equal);
    const value = try self.parseExpr();
    _ = try self.expect(.semicolon);
    _ = try self.bind(name, pos, value);
}

// -- expressions --------------------------------------------------------------

fn parseExpr(self: *Parser) Error!*const Node {
    try self.enter();
    defer self.leave();
    return self.parseOr();
}

fn binary(self: *Parser, op: ast.BinaryOp, pos: u32, lhs: *const Node, rhs: *const Node) Error!*const Node {
    return self.node(pos, .{ .binary = .{ .op = op, .lhs = lhs, .rhs = rhs } });
}

fn parseOr(self: *Parser) Error!*const Node {
    var lhs = try self.parseAnd();
    while (self.cur.tag == .keyword_or) {
        const pos = self.cur.start;
        try self.advance();
        lhs = try self.binary(.@"or", pos, lhs, try self.parseAnd());
    }
    return lhs;
}

fn parseAnd(self: *Parser) Error!*const Node {
    var lhs = try self.parseCompare();
    while (self.cur.tag == .keyword_and) {
        const pos = self.cur.start;
        try self.advance();
        lhs = try self.binary(.@"and", pos, lhs, try self.parseCompare());
    }
    return lhs;
}

fn compareOp(tag: Tag) ?ast.BinaryOp {
    return switch (tag) {
        .equal_equal => .eq,
        .bang_equal => .ne,
        .angle_bracket_left => .lt,
        .angle_bracket_left_equal => .le,
        .angle_bracket_right => .gt,
        .angle_bracket_right_equal => .ge,
        else => null,
    };
}

/// Comparisons do not chain, as in Zig: `a < b < c` is an error rather than
/// a comparison of a bool with `c`.
fn parseCompare(self: *Parser) Error!*const Node {
    const lhs = try self.parseOrelse();
    const op = compareOp(self.cur.tag) orelse return lhs;
    const pos = self.cur.start;
    try self.advance();
    const result = try self.binary(op, pos, lhs, try self.parseOrelse());
    if (compareOp(self.cur.tag) != null) return self.fail(self.cur.start, "comparisons cannot be chained", .{});
    return result;
}

fn parseOrelse(self: *Parser) Error!*const Node {
    var lhs = try self.parseAdditive();
    while (self.cur.tag == .keyword_orelse) {
        const pos = self.cur.start;
        try self.advance();
        lhs = try self.binary(.@"orelse", pos, lhs, try self.parseAdditive());
    }
    return lhs;
}

fn parseAdditive(self: *Parser) Error!*const Node {
    var lhs = try self.parseMultiplicative();
    while (true) {
        const op: ast.BinaryOp = switch (self.cur.tag) {
            .plus => .add,
            .minus => .sub,
            .plus_plus => .concat,
            else => return lhs,
        };
        const pos = self.cur.start;
        try self.advance();
        lhs = try self.binary(op, pos, lhs, try self.parseMultiplicative());
    }
}

fn parseMultiplicative(self: *Parser) Error!*const Node {
    var lhs = try self.parseUnary();
    while (true) {
        const op: ast.BinaryOp = switch (self.cur.tag) {
            .asterisk => .mul,
            .slash => .div,
            .percent => .rem,
            else => return lhs,
        };
        const pos = self.cur.start;
        try self.advance();
        lhs = try self.binary(op, pos, lhs, try self.parseUnary());
    }
}

fn parseUnary(self: *Parser) Error!*const Node {
    const op: ast.UnaryOp = switch (self.cur.tag) {
        .bang => .not,
        .minus => .negate,
        else => return self.parsePostfix(),
    };
    try self.enter();
    defer self.leave();
    const pos = self.cur.start;
    try self.advance();
    // A negative literal is read as one, so that the most negative `i64`,
    // whose magnitude does not fit in one, can be written.
    if (op == .negate and self.cur.tag == .number) {
        const t = self.cur;
        try self.advance();
        return self.parsePostfixOf(try self.number(t, true, pos));
    }
    return self.node(pos, .{ .unary = .{ .op = op, .operand = try self.parseUnary() } });
}

fn parsePostfix(self: *Parser) Error!*const Node {
    return self.parsePostfixOf(try self.parsePrimary());
}

fn parsePostfixOf(self: *Parser, primary: *const Node) Error!*const Node {
    var n = primary;
    while (true) {
        const pos = self.cur.start;
        switch (self.cur.tag) {
            .period => {
                try self.advance();
                const name, _ = try self.expectName();
                n = try self.node(pos, .{ .field = .{ .object = n, .name = name } });
            },
            .period_question => {
                try self.advance();
                n = try self.node(pos, .{ .unwrap = n });
            },
            .l_bracket => {
                try self.advance();
                const index = try self.parseExpr();
                _ = try self.expect(.r_bracket);
                n = try self.node(pos, .{ .index = .{ .object = n, .index = index } });
            },
            else => return n,
        }
    }
}

fn parsePrimary(self: *Parser) Error!*const Node {
    const t = self.cur;
    switch (t.tag) {
        .number => {
            try self.advance();
            return self.number(t, false, t.start);
        },
        .char_literal => {
            try self.advance();
            return self.node(t.start, .{ .int = try self.charLiteral(t) });
        },
        .string => {
            const n = try self.stringLiteral(t);
            try self.advance();
            return n;
        },
        .multiline_string_line => return self.multilineString(),
        .keyword_true, .keyword_false => {
            try self.advance();
            return self.node(t.start, .{ .bool = t.tag == .keyword_true });
        },
        .keyword_null => {
            try self.advance();
            return self.node(t.start, .null);
        },
        .identifier, .quoted_identifier => {
            const name, const pos = try self.expectName();
            return self.resolve(name, pos);
        },
        .builtin => return self.parseCall(),
        .period => {
            try self.advance();
            const name, _ = try self.expectName();
            return self.node(t.start, .{ .enum_literal = name });
        },
        .period_brace => return self.parseLiteral(),
        .l_paren => {
            try self.advance();
            const n = try self.parseExpr();
            _ = try self.expect(.r_paren);
            return n;
        },
        .keyword_if => return self.parseIf(false),
        .keyword_switch => return self.parseSwitch(),
        else => return self.unexpected("an expression"),
    }
}

/// `if (cond) a else b`, or `if (optional) |x| a else b`. `allow_no_else` is
/// for a field's value and a list's item, where a missing `else` means "leave
/// it out"; it carries into an `else if` chain and into nested branches.
fn parseIf(self: *Parser, allow_no_else: bool) Error!*const Node {
    try self.enter();
    defer self.leave();
    const pos = self.cur.start;
    try self.advance();
    _ = try self.expect(.l_paren);
    const cond = try self.parseExpr();
    _ = try self.expect(.r_paren);

    var capture: ?u32 = null;
    if (self.cur.tag == .pipe) {
        try self.advance();
        const name, const name_pos = try self.expectName();
        _ = try self.expect(.pipe);
        capture = try self.bind(name, name_pos, null);
    }
    const then = try self.parseBranch(allow_no_else);
    // The capture is in scope for the `then` branch only.
    if (capture != null) _ = self.scope.pop();

    var otherwise: ?*const Node = null;
    if (self.cur.tag == .keyword_else) {
        try self.advance();
        otherwise = try self.parseBranch(allow_no_else);
    } else if (!allow_no_else) {
        if (self.cur.tag == .eof or self.cur.tag == .comma or self.cur.tag == .r_brace or self.cur.tag == .semicolon or self.cur.tag == .r_paren) {
            return self.fail(pos, "an 'if' without 'else' can only be a struct field's value or a list item", .{});
        }
        return self.unexpected("'else'");
    }
    return self.node(pos, .{ .@"if" = .{ .cond = cond, .capture = capture, .then = then, .@"else" = otherwise } });
}

/// `switch (subject) { cases => value, ..., else => value }`, where a prong's
/// cases are values and `lo...hi` ranges, separated by commas, and a prong
/// may capture with `|name|` after its `=>`, as in Zig.
fn parseSwitch(self: *Parser) Error!*const Node {
    try self.enter();
    defer self.leave();
    const pos = self.cur.start;
    try self.advance();
    _ = try self.expect(.l_paren);
    const subject = try self.parseExpr();
    _ = try self.expect(.r_paren);
    _ = try self.expect(.l_brace);

    var prongs: std.ArrayList(ast.Prong) = .empty;
    var otherwise: ?ast.Prong = null;
    // Every case that is a literal, to find one written twice.
    var literals: std.ArrayList(*const Node) = .empty;
    while (self.cur.tag != .r_brace) {
        var cases: std.ArrayList(ast.Case) = .empty;
        if (self.cur.tag == .keyword_else) {
            if (otherwise != null) return self.fail(self.cur.start, "a switch can have only one 'else'", .{});
            try self.advance();
        } else while (true) {
            const case_pos = self.cur.start;
            const lo = try self.parseExpr();
            if (self.cur.tag == .ellipsis3) {
                try self.advance();
                try cases.append(self.arena, .{ .range = .{ .lo = lo, .hi = try self.parseExpr() } });
            } else {
                if (literal(lo)) {
                    for (literals.items) |prev| {
                        if (sameLiteral(prev, lo)) return self.fail(case_pos, "duplicate switch case", .{});
                    }
                    try literals.append(self.arena, lo);
                }
                try cases.append(self.arena, .{ .value = lo });
            }
            if (self.cur.tag != .comma) break;
            try self.advance();
            // `a, b, => x` is allowed, as Zig allows it.
            if (self.cur.tag == .equal_angle_bracket_right) break;
        }
        _ = try self.expect(.equal_angle_bracket_right);

        var capture: ?u32 = null;
        if (self.cur.tag == .pipe) {
            try self.advance();
            const name, const name_pos = try self.expectName();
            _ = try self.expect(.pipe);
            capture = try self.bind(name, name_pos, null);
        }
        const value = try self.parseExpr();
        // The capture is in scope for its own prong only.
        if (capture != null) _ = self.scope.pop();

        const prong: ast.Prong = .{ .cases = cases.items, .capture = capture, .value = value };
        if (cases.items.len == 0) otherwise = prong else try prongs.append(self.arena, prong);

        if (self.cur.tag == .comma) {
            try self.advance();
        } else if (self.cur.tag != .r_brace) {
            return self.unexpected("',' or '}}'");
        }
    }
    try self.advance();
    if (prongs.items.len == 0 and otherwise == null) return self.fail(pos, "a switch needs at least one prong", .{});
    return self.node(pos, .{ .@"switch" = .{ .subject = subject, .prongs = prongs.items, .@"else" = otherwise } });
}

/// Whether `n` is a value written out, which two cases cannot both be.
fn literal(n: *const Node) bool {
    return switch (n.data) {
        .null, .bool, .int, .string, .enum_literal => true,
        else => false,
    };
}

fn sameLiteral(a: *const Node, b: *const Node) bool {
    if (std.meta.activeTag(a.data) != std.meta.activeTag(b.data)) return false;
    return switch (a.data) {
        .null => true,
        .bool => |x| x == b.data.bool,
        .int => |x| x == b.data.int,
        .string => |x| std.mem.eql(u8, x, b.data.string),
        .enum_literal => |x| std.mem.eql(u8, x, b.data.enum_literal),
        else => false,
    };
}

fn parseBranch(self: *Parser, allow_no_else: bool) Error!*const Node {
    if (allow_no_else and self.cur.tag == .keyword_if) return self.parseIf(true);
    return self.parseExpr();
}

/// A field's value or a list's item: an expression, or an `if` that need not
/// have an `else`.
fn parseItem(self: *Parser) Error!*const Node {
    if (self.cur.tag == .keyword_if) return self.parseIf(true);
    return self.parseExpr();
}

/// `.{ ... }`: a struct if it starts `.name =`, a list otherwise, and empty
/// -- which decodes as either -- if it is `.{}`.
fn parseLiteral(self: *Parser) Error!*const Node {
    try self.enter();
    defer self.leave();
    const pos = self.cur.start;
    try self.advance();
    if (self.cur.tag == .r_brace) {
        try self.advance();
        return self.node(pos, .{ .record = &.{} });
    }

    const is_record = blk: {
        if (self.cur.tag != .period) break :blk false;
        var look = self.tok;
        const name = look.next();
        if (name.tag != .identifier and name.tag != .quoted_identifier) break :blk false;
        break :blk look.next().tag == .equal;
    };

    if (is_record) {
        var fields: std.ArrayList(ast.Field) = .empty;
        while (true) {
            if (self.cur.tag != .period) return self.unexpected("'.name = value' or '}}'");
            try self.advance();
            const name, const name_pos = try self.expectName();
            for (fields.items) |f| {
                if (std.mem.eql(u8, f.name, name)) return self.fail(name_pos, "duplicate field '{s}'", .{name});
            }
            _ = try self.expect(.equal);
            const value = try self.parseItem();
            try fields.append(self.arena, .{ .name = name, .pos = self.base + name_pos, .value = value });
            if (try self.endOfList()) break;
        }
        return self.node(pos, .{ .record = fields.items });
    }

    var list: std.ArrayList(ast.Item) = .empty;
    while (true) {
        try list.append(self.arena, try self.parseItem());
        if (try self.endOfList()) break;
    }
    return self.node(pos, .{ .list = list.items });
}

/// After an item of a list: `,` and maybe `}`, or just `}`. True at the end.
fn endOfList(self: *Parser) Error!bool {
    switch (self.cur.tag) {
        .comma => {
            try self.advance();
            if (self.cur.tag != .r_brace) return false;
            try self.advance();
            return true;
        },
        .r_brace => {
            try self.advance();
            return true;
        },
        else => return self.unexpected("',' or '}}'"),
    }
}

fn parseCall(self: *Parser) Error!*const Node {
    try self.enter();
    defer self.leave();
    const t = self.cur;
    const name = self.source[t.start + 1 .. t.end];
    const is_include = std.mem.eql(u8, name, "include");
    const func: ast.Func, const min: usize, const max: usize = blk: {
        if (is_include) {
            if (self.include == null) return self.fail(t.start, "@include is not supported here", .{});
            break :blk .{ undefined, 1, 1 };
        }
        if (std.meta.stringToEnum(Builtin, name)) |b| {
            const arity = b.arity();
            break :blk .{ .{ .builtin = b }, arity.min, arity.max };
        }
        for (self.functions, 0..) |f, i| {
            if (std.mem.eql(u8, f.name, name)) break :blk .{ .{ .host = @intCast(i) }, f.min_args, f.max_args };
        }
        return self.fail(t.start, "unknown function '@{s}'", .{name});
    };
    try self.advance();
    _ = try self.expect(.l_paren);

    // Where the first argument starts, which its node may not: `a.b` is
    // where its `.` is.
    const first_arg = self.cur.start;
    var args: std.ArrayList(*const Node) = .empty;
    while (self.cur.tag != .r_paren) {
        try args.append(self.arena, try self.parseExpr());
        if (self.cur.tag == .comma) {
            try self.advance();
        } else if (self.cur.tag != .r_paren) {
            return self.unexpected("',' or ')'");
        }
    }
    try self.advance();

    if (args.items.len < min or args.items.len > max) {
        if (min == max) return self.fail(t.start, "@{s} takes {d} argument{s}, not {d}", .{ name, min, if (min == 1) "" else "s", args.items.len });
        if (args.items.len < min) return self.fail(t.start, "@{s} takes at least {d} argument{s}, not {d}", .{ name, min, if (min == 1) "" else "s", args.items.len });
        return self.fail(t.start, "@{s} takes at most {d} argument{s}, not {d}", .{ name, max, if (max == 1) "" else "s", args.items.len });
    }
    if (is_include) return self.includeFile(t.start, first_arg, args.items[0]);
    return self.node(t.start, .{ .call = .{ .func = func, .args = args.items } });
}

// -- includes -----------------------------------------------------------------

const LocalError = error{ OutOfMemory, NotFile, NotLocal, NotAbsolute };

/// `u`, which must be a `file:` URI naming a file on this machine, in the
/// one spelling every such URI is given here: `file:///path`, with dot
/// segments resolved, the host empty rather than `localhost`, and no query
/// or fragment, neither of which names anything on a filesystem.
fn localFile(arena: Allocator, u: Uri) LocalError!Uri {
    const scheme = u.scheme orelse return error.NotFile;
    if (!std.ascii.eqlIgnoreCase(scheme, "file")) return error.NotFile;
    if (u.host) |host| switch (host) {
        .hostname => |h| if (h.len != 0 and !std.ascii.eqlIgnoreCase(h, "localhost")) return error.NotLocal,
        .ipv4, .ipv6 => return error.NotLocal,
    };
    if (u.username != null or u.password != null or u.port != null) return error.NotLocal;
    if (!u.rooted) return error.NotAbsolute;
    var c = (try u.normalize(arena, .{})).parts();
    c.host = .{ .hostname = "" };
    c.query = &.{};
    c.fragment = null;
    return Uri.init(arena, c);
}

/// What is wrong with a URI that `localFile` refused, to follow its text.
fn notLocal(err: LocalError) []const u8 {
    return switch (err) {
        error.NotFile => "is not a file: URI",
        error.NotLocal => "names a file on another machine",
        error.NotAbsolute => "has no absolute path",
        error.OutOfMemory => unreachable,
    };
}

/// The `file:` URI that `path`, written in the file being parsed, names.
fn resolveInclude(self: *Parser, pos: u32, path: []const u8) Error!Uri {
    const ref = Uri.parse(self.arena, path) catch |err| switch (err) {
        error.OutOfMemory => return error.OutOfMemory,
        else => return self.fail(pos, "'{s}' is not a URI reference", .{path}),
    };
    // With no URI of its own, a program can still include an absolute path,
    // and a URI, but has nothing to resolve a relative path against.
    const base = self.uri orelse blk: {
        if (ref.scheme == null and ref.host == null and !ref.rooted) {
            return self.fail(pos, "'{s}' is relative, and this program has no filename to resolve it against", .{path});
        }
        break :blk Uri.parse(self.arena, "file:///") catch |err| switch (err) {
            error.OutOfMemory => return error.OutOfMemory,
            else => unreachable,
        };
    };
    const target = base.clickUri(self.arena, ref) catch |err| switch (err) {
        error.OutOfMemory => return error.OutOfMemory,
        else => return self.fail(pos, "'{s}' cannot be resolved", .{path}),
    };
    return localFile(self.arena, target) catch |err| switch (err) {
        error.OutOfMemory => return error.OutOfMemory,
        else => |e| self.fail(pos, "'{s}' {s}", .{ path, notLocal(e) }),
    };
}

/// `@include(path)`, at `pos`, with `path` starting at `arg_pos`: parse the
/// file and stand a slot in for it.
fn includeFile(self: *Parser, pos: u32, arg_pos: u32, arg: *const Node) Error!*const Node {
    const include = self.include.?;
    const path = switch (arg.data) {
        .string => |s| s,
        else => return self.fail(arg_pos, "@include takes a string literal", .{}),
    };
    const file_uri = try self.resolveInclude(arg_pos, path);
    const name = try file_uri.toText(self.arena, .{});

    if (self.files.get(name)) |state| {
        const slot = state orelse return self.fail(pos, "'{s}' includes itself", .{name});
        return self.node(pos, .{ .slot = slot });
    }
    if (self.files.count() >= self.max_includes) {
        return self.fail(pos, "more than {d} files included", .{self.max_includes});
    }
    try self.files.put(self.arena, name, null);

    const contents = include.read(include.context, self.arena, name) catch |err| switch (err) {
        error.OutOfMemory => return error.OutOfMemory,
        else => {
            self.diag.setIn(self.name, .of(self.source, pos), "cannot include '{s}': {s}", .{ name, @errorName(err) });
            return error.Include;
        },
    };
    const last = self.sources.items[self.sources.items.len - 1];
    // One past the end of the file before, so that the end of one file is
    // not the start of the next.
    const base = @as(u64, last.base) + last.text.len + 1;
    if (base + contents.len >= std.math.maxInt(u32)) return self.fail(pos, "program too large", .{});
    try self.sources.append(self.arena, .{ .name = name, .text = contents, .base = @intCast(base) });

    // The file is parsed with this parser, but as a program of its own: its
    // `let`s are not seen by the file that includes it, nor that file's by
    // it. Nesting carries on counting, which bounds how deeply includes nest.
    const saved = .{ self.source, self.tok, self.cur, self.name, self.uri, self.base, self.scope };
    self.source = contents;
    self.tok = .init(contents);
    self.name = name;
    self.uri = file_uri;
    self.base = @intCast(base);
    self.scope = .empty;
    const root = try self.parseFile();
    self.source, self.tok, self.cur, self.name, self.uri, self.base, self.scope = saved;

    const slot: u32 = @intCast(self.slots.items.len);
    try self.slots.append(self.arena, root);
    try self.files.put(self.arena, name, slot);
    return self.node(pos, .{ .slot = slot });
}

// -- literals -----------------------------------------------------------------

fn number(self: *Parser, t: Token, negative: bool, pos: u32) Error!*const Node {
    const bytes = self.text(t);
    switch (std.zig.parseNumberLiteral(bytes)) {
        .int => |u| {
            const limit: u64 = if (negative) 1 << 63 else std.math.maxInt(i64);
            if (u > limit) return self.fail(pos, "integer literal does not fit in an i64", .{});
            const i: i64 = if (negative) @intCast(-@as(i128, u)) else @intCast(u);
            return self.node(pos, .{ .int = i });
        },
        .big_int => return self.fail(pos, "integer literal does not fit in an i64", .{}),
        .float => {
            const f = std.fmt.parseFloat(f64, bytes) catch return self.fail(t.start, "invalid number literal", .{});
            return self.node(pos, .{ .float = if (negative) -f else f });
        },
        .failure => return self.fail(t.start, "invalid number literal '{s}'", .{bytes}),
    }
}

fn charLiteral(self: *Parser, t: Token) Error!i64 {
    const content = self.source[t.start + 1 .. t.end - 1];
    if (content.len == 0) return self.fail(t.start, "empty character literal", .{});
    var buf: std.ArrayList(u8) = .empty;
    var i: usize = 0;
    if (content[0] == '\\') {
        i = try self.escape(&buf, t.start + 1);
        if (i != content.len) return self.fail(t.start, "a character literal holds one character", .{});
        const cp = std.unicode.utf8Decode(buf.items) catch return @intCast(buf.items[0]);
        return cp;
    }
    const n = std.unicode.utf8ByteSequenceLength(content[0]) catch return self.fail(t.start + 1, "invalid UTF-8", .{});
    if (n != content.len) return self.fail(t.start, "a character literal holds one character", .{});
    return std.unicode.utf8Decode(content) catch self.fail(t.start + 1, "invalid UTF-8", .{});
}

/// Decode the escape sequence at `source[at]` (the backslash) onto `buf`, and
/// return how many bytes of source it took.
fn escape(self: *Parser, buf: *std.ArrayList(u8), at: u32) Error!u32 {
    const s = self.source;
    if (at + 1 >= s.len) return self.fail(at, "unterminated escape sequence", .{});
    const c = s[at + 1];
    const simple: ?u8 = switch (c) {
        'n' => '\n',
        'r' => '\r',
        't' => '\t',
        '\\' => '\\',
        '\'' => '\'',
        '"' => '"',
        '$' => '$',
        else => null,
    };
    if (simple) |b| {
        try buf.append(self.arena, b);
        return 2;
    }
    switch (c) {
        'x' => {
            if (at + 4 > s.len) return self.fail(at, "invalid escape sequence", .{});
            const b = std.fmt.parseInt(u8, s[at + 2 .. at + 4], 16) catch return self.fail(at, "invalid escape sequence", .{});
            try buf.append(self.arena, b);
            return 4;
        },
        'u' => {
            if (at + 2 >= s.len or s[at + 2] != '{') return self.fail(at, "invalid escape sequence", .{});
            const close = std.mem.findScalarPos(u8, s, at + 3, '}') orelse return self.fail(at, "invalid escape sequence", .{});
            const cp = std.fmt.parseInt(u21, s[at + 3 .. close], 16) catch return self.fail(at, "invalid escape sequence", .{});
            var enc: [4]u8 = undefined;
            const n = std.unicode.utf8Encode(cp, &enc) catch return self.fail(at, "invalid Unicode code point", .{});
            try buf.appendSlice(self.arena, enc[0..n]);
            return @intCast(close + 1 - at);
        },
        else => return self.fail(at, "invalid escape sequence '\\{c}'", .{c}),
    }
}

/// The bytes of a string without interpolation, escapes decoded.
fn decodeString(self: *Parser, start: u32, end: u32) Error![]const u8 {
    if (std.mem.findScalar(u8, self.source[start..end], '\\') == null) return self.source[start..end];
    var buf: std.ArrayList(u8) = .empty;
    var i = start;
    while (i < end) {
        if (self.source[i] == '\\') {
            i += try self.escape(&buf, i);
        } else {
            try buf.append(self.arena, self.source[i]);
            i += 1;
        }
    }
    return buf.items;
}

/// Collects the pieces of a string that may have `${ }` in it.
const Template = struct {
    parts: std.ArrayList(ast.Part) = .empty,
    buf: std.ArrayList(u8) = .empty,

    fn flush(self: *Template, arena: Allocator) Error!void {
        if (self.buf.items.len == 0) return;
        try self.parts.append(arena, .{ .text = self.buf.items });
        self.buf = .empty;
    }

    fn finish(self: *Template, p: *Parser, pos: u32) Error!*const Node {
        if (self.parts.items.len == 0) return p.node(pos, .{ .string = self.buf.items });
        try self.flush(p.arena);
        return p.node(pos, .{ .template = self.parts.items });
    }
};

/// Read `source[start..end]` into `t`: one string's content, or one line of
/// a multiline string, which has no escapes.
fn templateContent(self: *Parser, t: *Template, start: u32, end: u32, escapes: bool) Error!void {
    var i = start;
    while (i < end) {
        const c = self.source[i];
        if (c == '\\' and escapes) {
            i += try self.escape(&t.buf, i);
        } else if (c == '$' and i + 1 < end and self.source[i + 1] == '{') {
            const close = Tokenizer.skipInterpolation(self.source, i + 2, end, 0) orelse
                return self.fail(i, "unterminated interpolation", .{});
            try t.flush(self.arena);
            try t.parts.append(self.arena, .{ .expr = try self.interpolation(i, close) });
            i = close + 1;
        } else {
            try t.buf.append(self.arena, c);
            i += 1;
        }
    }
}

/// Parse what is inside `${ }`, by pointing a second tokenizer at it.
fn interpolation(self: *Parser, dollar: u32, close: u32) Error!*const Node {
    const saved_tok = self.tok;
    const saved_cur = self.cur;
    self.tok = .{ .source = self.source, .index = dollar + 2, .limit = close };
    try self.advance();
    if (self.cur.tag == .eof) return self.fail(dollar, "empty interpolation", .{});
    const n = try self.parseExpr();
    if (self.cur.tag != .eof) return self.unexpected("'}}'");
    self.tok = saved_tok;
    self.cur = saved_cur;
    return n;
}

fn stringLiteral(self: *Parser, t: Token) Error!*const Node {
    var tmpl: Template = .{};
    try self.templateContent(&tmpl, t.start + 1, t.end - 1, true);
    return tmpl.finish(self, t.start);
}

/// Consecutive `\\` lines are one string, joined with newlines, as in Zig.
fn multilineString(self: *Parser) Error!*const Node {
    const pos = self.cur.start;
    var tmpl: Template = .{};
    var first = true;
    while (self.cur.tag == .multiline_string_line) {
        if (!first) try tmpl.buf.append(self.arena, '\n');
        first = false;
        var end = self.cur.end;
        if (end > self.cur.start + 2 and self.source[end - 1] == '\r') end -= 1;
        try self.templateContent(&tmpl, self.cur.start + 2, end, false);
        try self.advance();
    }
    return tmpl.finish(self, pos);
}

// -- tests --------------------------------------------------------------------

const testing = std.testing;

fn parseTest(arena: Allocator, source: []const u8, diag: *Diagnostic) Error!Tree {
    return parse(arena, source, .{}, diag);
}

fn expectSyntaxError(source: []const u8, line: u32, column: u32, message: []const u8) !void {
    var arena: std.heap.ArenaAllocator = .init(testing.allocator);
    defer arena.deinit();
    var d: Diagnostic = .{};
    if (parseTest(arena.allocator(), source, &d)) |_| {
        std.debug.print("parsed, but expected: {s}\n", .{message});
        return error.TestUnexpectedSuccess;
    } else |err| try testing.expectEqual(error.Syntax, err);
    testing.expectEqualStrings(message, d.message()) catch |err| {
        std.debug.print("source: {s}\n", .{source});
        return err;
    };
    try testing.expectEqual(Diagnostic.Pos{ .line = line, .column = column }, d.pos);
}

test "plain ZON parses" {
    var arena: std.heap.ArenaAllocator = .init(testing.allocator);
    defer arena.deinit();
    var d: Diagnostic = .{};
    const tree = try parseTest(arena.allocator(),
        \\.{
        \\    .name = .struthio,
        \\    .version = "0.1.0",
        \\    .fingerprint = 0x1234,
        \\    .@"min zig" = -1.5e3,
        \\    .paths = .{ "build.zig", "src", },
        \\    .deps = .{},
        \\    .c = 'é',
        \\}
    , &d);
    const r = tree.root.data.record;
    try testing.expectEqual(@as(usize, 7), r.len);
    try testing.expectEqualStrings("struthio", r[0].value.data.enum_literal);
    try testing.expectEqual(@as(i64, 0x1234), r[2].value.data.int);
    try testing.expectEqualStrings("min zig", r[3].name);
    try testing.expectEqual(@as(f64, -1500), r[3].value.data.float);
    try testing.expectEqual(@as(usize, 2), r[4].value.data.list.len);
    try testing.expectEqual(@as(i64, 0xe9), r[6].value.data.int);
}

test "precedence follows Zig" {
    var arena: std.heap.ArenaAllocator = .init(testing.allocator);
    defer arena.deinit();
    var d: Diagnostic = .{};
    // or < and < == < orelse < + < *
    const tree = try parseTest(arena.allocator(), "let a = null; a orelse 1 + 2 * 3 == 7 and true or false", &d);
    const top = tree.root.data.binary;
    try testing.expectEqual(ast.BinaryOp.@"or", top.op);
    const and_ = top.lhs.data.binary;
    try testing.expectEqual(ast.BinaryOp.@"and", and_.op);
    const eq = and_.lhs.data.binary;
    try testing.expectEqual(ast.BinaryOp.eq, eq.op);
    const orelse_ = eq.lhs.data.binary;
    try testing.expectEqual(ast.BinaryOp.@"orelse", orelse_.op);
    try testing.expectEqual(ast.BinaryOp.add, orelse_.rhs.data.binary.op);
}

test "templates split into parts" {
    var arena: std.heap.ArenaAllocator = .init(testing.allocator);
    defer arena.deinit();
    var d: Diagnostic = .{};
    const tree = try parseTest(arena.allocator(), "\"a\\${b}${ctx.x}c${@join(ctx.y, \"}\")}\"", &d);
    const parts = tree.root.data.template;
    try testing.expectEqual(@as(usize, 4), parts.len);
    try testing.expectEqualStrings("a${b}", parts[0].text);
    try testing.expectEqualStrings("x", parts[1].expr.data.field.name);
    try testing.expectEqualStrings("c", parts[2].text);
    try testing.expectEqual(Builtin.join, parts[3].expr.data.call.func.builtin);
}

test "the most negative integer can be written" {
    var arena: std.heap.ArenaAllocator = .init(testing.allocator);
    defer arena.deinit();
    var d: Diagnostic = .{};
    const tree = try parseTest(arena.allocator(), "-9223372036854775808", &d);
    try testing.expectEqual(@as(i64, std.math.minInt(i64)), tree.root.data.int);
}

test "syntax errors say where" {
    try expectSyntaxError("let x = 1; y", 1, 12, "unknown name 'y'");
    try expectSyntaxError("let x = x; x", 1, 9, "unknown name 'x'");
    try expectSyntaxError("let x = 1;\nlet x = 2; x", 2, 5, "'x' is already defined");
    try expectSyntaxError("let ctx = 1; 2", 1, 5, "'ctx' is reserved and cannot be redefined");
    try expectSyntaxError(".{ .a = 1, .a = 2 }", 1, 13, "duplicate field 'a'");
    try expectSyntaxError("if (true) 1", 1, 1, "an 'if' without 'else' can only be a struct field's value or a list item");
    try expectSyntaxError("1 < 2 < 3", 1, 7, "comparisons cannot be chained");
    try expectSyntaxError("\"abc", 1, 1, "unterminated string");
    try expectSyntaxError("\"a${}\"", 1, 3, "empty interpolation");
    try expectSyntaxError("\"a${1 2}\"", 1, 7, "expected '}', found a number");
    try expectSyntaxError("\"\\q\"", 1, 2, "invalid escape sequence '\\q'");
    try expectSyntaxError("@nope(1)", 1, 1, "unknown function '@nope'");
    try expectSyntaxError("switch (1) {}", 1, 1, "a switch needs at least one prong");
    try expectSyntaxError("switch (1) { .a, .b => 1, .a => 2 }", 1, 27, "duplicate switch case");
    try expectSyntaxError("switch (1) { else => 1, else => 2 }", 1, 25, "a switch can have only one 'else'");
    try expectSyntaxError("switch (1) { 1 => 1 2 }", 1, 21, "expected ',' or '}', found a number");
    try expectSyntaxError("switch (1) { 1, 2 }", 1, 19, "expected '=>', found '}'");
    try expectSyntaxError("switch (ctx.a) { .b => |v| v, else => v }", 1, 39, "unknown name 'v'");
    try expectSyntaxError("@include(\"x\")", 1, 1, "@include is not supported here");
    try expectSyntaxError("@lower()", 1, 1, "@lower takes 1 argument, not 0");
    try expectSyntaxError(".{ 1 2 }", 1, 6, "expected ',' or '}', found a number");
    try expectSyntaxError("99999999999999999999", 1, 1, "integer literal does not fit in an i64");
    try expectSyntaxError("1 #", 1, 3, "unexpected character '#'");
    try expectSyntaxError("if (ctx.a) |v| v else v", 1, 23, "unknown name 'v'");
}

test "nesting is bounded" {
    var src: std.ArrayList(u8) = .empty;
    defer src.deinit(testing.allocator);
    for (0..100) |_| try src.appendSlice(testing.allocator, "(");
    try src.appendSlice(testing.allocator, "1");
    for (0..100) |_| try src.appendSlice(testing.allocator, ")");
    var arena: std.heap.ArenaAllocator = .init(testing.allocator);
    defer arena.deinit();
    var d: Diagnostic = .{};
    try testing.expectError(error.Syntax, parseTest(arena.allocator(), src.items, &d));
    try testing.expectEqualStrings("expression nested too deeply", d.message());
}