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

//! Lays a program out the way `zig fmt` lays out Zig.
//!
//! The rules are Zig's, so that a struthio file sitting beside Zig looks like
//! it belongs there:
//!
//! * Four spaces of indent, single spaces around binary operators and after
//!   commas, and none inside parentheses or brackets.
//! * A struct or list literal, a call's arguments and a switch's prongs go on
//!   one line -- `.{ 1, 2 }` -- unless the last of them is followed by a
//!   comma. Then each goes on a line of its own, followed by a comma. The
//!   trailing comma is how a person asks for the long form, as it is in Zig.
//!   So is a comment inside, or anything inside that cannot be on one line.
//!   A switch prong's cases follow the same rule.
//! * A line break written after a binary operator is kept, and what follows
//!   it is indented once more. One written anywhere else is not.
//! * A multiline string starts on a line of its own, one indent in from the
//!   line it belongs to, and what follows it starts on the next.
//! * Comments stay where they were: at the end of the line they were on, or
//!   on a line of their own. A run of blank lines becomes one, and a blank
//!   line just inside a bracket goes.
//!
//! Strings, numbers and names are copied as they are written, and so is
//! everything inside a `${ }`. Formatting changes only the space between
//! tokens and the trailing commas, and never what a program means.
//!
//! It parses with a parser of its own rather than `Parser.zig`'s, because
//! that one resolves names, reads included files and keeps no record of the
//! layout. This one keeps every token, looks nothing up, and accepts any
//! function name, so a file can be formatted without the host that runs it.
//! It accepts what that one accepts, in the same shapes; a little more, too,
//! since it checks no names, arities or duplicates.

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

const Diagnostic = @import("Diagnostic.zig");
const Tokenizer = @import("Tokenizer.zig");
const Token = Tokenizer.Token;
const Tag = Tokenizer.Tag;

pub const Error = error{
    OutOfMemory,
    /// The source does not parse; the diagnostic says where.
    Syntax,
};

pub const Options = struct {
    /// How deeply expressions may nest, as `Limits.max_depth`.
    max_depth: u32 = 64,
};

/// `source`, formatted. The caller owns the result.
pub fn format(gpa: Allocator, source: []const u8, options: Options, diag: *Diagnostic) Error![]u8 {
    var arena_state: std.heap.ArenaAllocator = .init(gpa);
    defer arena_state.deinit();
    const arena = arena_state.allocator();

    if (source.len >= std.math.maxInt(u32)) {
        diag.set(.{}, "program too large", .{});
        return error.Syntax;
    }
    var p: Parser = .{
        .arena = arena,
        .source = source,
        .toks = try tokenize(arena, source, diag),
        .diag = diag,
        .max_depth = options.max_depth,
    };
    const file = try p.parseFile();

    var out: std.ArrayList(u8) = .empty;
    errdefer out.deinit(gpa);
    var r: Renderer = .{ .gpa = gpa, .source = source, .toks = p.toks, .out = &out };
    try r.file(file);
    return out.toOwnedSlice(gpa);
}

fn tokenize(arena: Allocator, source: []const u8, diag: *Diagnostic) Error![]const Token {
    var toks: std.ArrayList(Token) = .empty;
    var t: Tokenizer = .init(source);
    while (true) {
        const tok = t.next();
        if (tok.tag == .invalid) return invalidToken(source, tok, diag);
        try toks.append(arena, tok);
        if (tok.tag == .eof) return toks.items;
    }
}

fn invalidToken(source: []const u8, tok: Token, diag: *Diagnostic) error{Syntax} {
    const c = source[tok.start];
    const pos: Diagnostic.Pos = .of(source, tok.start);
    switch (c) {
        '"' => diag.set(pos, "unterminated string", .{}),
        '\'' => diag.set(pos, "unterminated character literal", .{}),
        '@' => diag.set(pos, "expected a builtin name or a quoted identifier after '@'", .{}),
        else => if (std.ascii.isPrint(c))
            diag.set(pos, "unexpected character '{c}'", .{c})
        else
            diag.set(pos, "unexpected byte 0x{x:0>2}", .{c}),
    }
    return error.Syntax;
}

// -- the tree -----------------------------------------------------------------

/// A piece of the program, by the tokens it spans. Most of its punctuation
/// is not recorded, because the grammar says exactly where it is: an `if`'s
/// `(` is the token after its first, and its `)` the token after its
/// condition's last.
const Node = struct {
    first: u32,
    last: u32,
    data: Data,
    /// The `${ }`s inside a string or a multiline string, in order.
    interpolations: []const Interpolation = &.{},
};

/// What is inside one `${ }`. Its tokens are a list of their own, which the
/// renderer never sees: it copies the string they are in as it is written.
const Interpolation = struct {
    toks: []const Token,
    node: *const Node,
};

const Data = union(enum) {
    /// One token: a number, a character, a string, a name, `true`, `false`
    /// or `null`.
    token,
    /// One or more `\\` lines, which are one string.
    multiline,
    /// `.name`
    enum_literal,
    /// `(inner)`
    paren: *const Node,
    /// `!x` or `-x`, the operator being `first`.
    unary: *const Node,
    binary: struct { lhs: *const Node, op: u32, rhs: *const Node },
    /// `object.name`, the name being `last`.
    field: *const Node,
    /// `object.?`
    unwrap: *const Node,
    /// `object[index]`
    index: struct { object: *const Node, index: *const Node },
    /// `@name(args)`: `(` is the token after the name, and `)` is `last`.
    call: []const *const Node,
    /// `.{ items }`, an item being an expression or a `field_init`.
    literal: []const *const Node,
    /// `.name = value`
    field_init: *const Node,
    @"if": struct {
        cond: *const Node,
        /// The name in `|name|`.
        capture: ?u32,
        then: *const Node,
        @"else": ?*const Node,
    },
    /// `switch (subject) { prongs }`
    @"switch": struct { subject: *const Node, prongs: []const *const Node },
    /// `cases => |capture| value`, or `else => value` with no cases.
    prong: struct { cases: []const *const Node, arrow: u32, capture: ?u32, value: *const Node },
    /// `lo...hi`
    range: struct { lo: *const Node, hi: *const Node },
};

const File = struct {
    lets: []const Let,
    root: *const Node,
    eof: u32,
};

/// `let name = value;`: `let` is `value.first - 3`.
const Let = struct { value: *const Node };

// -- parsing ------------------------------------------------------------------

/// The same descent as `Parser.zig`, level for level, recording tokens
/// instead of meaning.
const Parser = struct {
    arena: Allocator,
    source: []const u8,
    toks: []const Token,
    i: u32 = 0,
    diag: *Diagnostic,
    depth: u32 = 0,
    max_depth: u32,

    fn tag(p: *const Parser) Tag {
        return p.toks[p.i].tag;
    }

    fn fail(p: *Parser, at: u32, comptime fmt: []const u8, args: anytype) error{Syntax} {
        p.diag.set(.of(p.source, p.toks[at].start), fmt, args);
        return error.Syntax;
    }

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

    fn advance(p: *Parser) void {
        if (p.tag() != .eof) p.i += 1;
    }

    fn expect(p: *Parser, t: Tag) Error!u32 {
        if (p.tag() != t) return p.fail(p.i, "expected {s}, found {s}", .{ t.describe(), p.tag().describe() });
        const at = p.i;
        p.advance();
        return at;
    }

    fn expectName(p: *Parser) Error!u32 {
        return switch (p.tag()) {
            .identifier, .quoted_identifier => blk: {
                const at = p.i;
                p.advance();
                break :blk at;
            },
            else => p.unexpected("an identifier"),
        };
    }

    /// A node from `first` to the token just consumed.
    fn node(p: *Parser, first: u32, data: Data) Error!*Node {
        const n = try p.arena.create(Node);
        n.* = .{ .first = first, .last = p.i - 1, .data = data };
        return n;
    }

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

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

    fn parseFile(p: *Parser) Error!File {
        var lets: std.ArrayList(Let) = .empty;
        while (p.tag() == .keyword_let) {
            p.advance();
            _ = try p.expectName();
            _ = try p.expect(.equal);
            const value = try p.parseExpr();
            _ = try p.expect(.semicolon);
            try lets.append(p.arena, .{ .value = value });
        }
        const root = try p.parseExpr();
        if (p.tag() != .eof) return p.unexpected("an operator or the end of the program");
        return .{ .lets = lets.items, .root = root, .eof = p.i };
    }

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

    fn binary(p: *Parser, lhs: *const Node, comptime next: fn (*Parser) Error!*const Node) Error!*const Node {
        const op = p.i;
        p.advance();
        const rhs = try next(p);
        return p.node(lhs.first, .{ .binary = .{ .lhs = lhs, .op = op, .rhs = rhs } });
    }

    fn parseOr(p: *Parser) Error!*const Node {
        var lhs = try p.parseAnd();
        while (p.tag() == .keyword_or) lhs = try p.binary(lhs, parseAnd);
        return lhs;
    }

    fn parseAnd(p: *Parser) Error!*const Node {
        var lhs = try p.parseCompare();
        while (p.tag() == .keyword_and) lhs = try p.binary(lhs, parseCompare);
        return lhs;
    }

    fn isCompare(t: Tag) bool {
        return switch (t) {
            .equal_equal,
            .bang_equal,
            .angle_bracket_left,
            .angle_bracket_left_equal,
            .angle_bracket_right,
            .angle_bracket_right_equal,
            => true,
            else => false,
        };
    }

    fn parseCompare(p: *Parser) Error!*const Node {
        const lhs = try p.parseOrelse();
        if (!isCompare(p.tag())) return lhs;
        const n = try p.binary(lhs, parseOrelse);
        if (isCompare(p.tag())) return p.fail(p.i, "comparisons cannot be chained", .{});
        return n;
    }

    fn parseOrelse(p: *Parser) Error!*const Node {
        var lhs = try p.parseAdditive();
        while (p.tag() == .keyword_orelse) lhs = try p.binary(lhs, parseAdditive);
        return lhs;
    }

    fn parseAdditive(p: *Parser) Error!*const Node {
        var lhs = try p.parseMultiplicative();
        while (p.tag() == .plus or p.tag() == .minus or p.tag() == .plus_plus) lhs = try p.binary(lhs, parseMultiplicative);
        return lhs;
    }

    fn parseMultiplicative(p: *Parser) Error!*const Node {
        var lhs = try p.parseUnary();
        while (p.tag() == .asterisk or p.tag() == .slash or p.tag() == .percent) lhs = try p.binary(lhs, parseUnary);
        return lhs;
    }

    /// `-5.?` is `(-5).?` to the real parser, which reads a negative number
    /// as one literal, and `-(x.?)` otherwise. Either is the same tokens in
    /// the same order, which is all that matters here.
    fn parseUnary(p: *Parser) Error!*const Node {
        if (p.tag() != .bang and p.tag() != .minus) return p.parsePostfix();
        try p.enter();
        defer p.leave();
        const first = p.i;
        p.advance();
        const operand = try p.parseUnary();
        return p.node(first, .{ .unary = operand });
    }

    fn parsePostfix(p: *Parser) Error!*const Node {
        var n = try p.parsePrimary();
        while (true) {
            switch (p.tag()) {
                .period => {
                    p.advance();
                    _ = try p.expectName();
                    n = try p.node(n.first, .{ .field = n });
                },
                .period_question => {
                    p.advance();
                    n = try p.node(n.first, .{ .unwrap = n });
                },
                .l_bracket => {
                    p.advance();
                    const index = try p.parseExpr();
                    _ = try p.expect(.r_bracket);
                    n = try p.node(n.first, .{ .index = .{ .object = n, .index = index } });
                },
                else => return n,
            }
        }
    }

    fn parsePrimary(p: *Parser) Error!*const Node {
        const first = p.i;
        switch (p.tag()) {
            .number,
            .char_literal,
            .keyword_true,
            .keyword_false,
            .keyword_null,
            .identifier,
            .quoted_identifier,
            => {
                p.advance();
                return p.node(first, .token);
            },
            .string => {
                p.advance();
                const n = try p.node(first, .token);
                const t = p.toks[first];
                n.interpolations = try p.interpolations(t.start + 1, t.end - 1, true);
                return n;
            },
            .multiline_string_line => {
                var found: std.ArrayList(Interpolation) = .empty;
                while (p.tag() == .multiline_string_line) {
                    const t = p.toks[p.i];
                    try found.appendSlice(p.arena, try p.interpolations(t.start + 2, t.end, false));
                    p.advance();
                }
                const n = try p.node(first, .multiline);
                n.interpolations = found.items;
                return n;
            },
            .builtin => return p.parseCall(),
            .period => {
                p.advance();
                _ = try p.expectName();
                return p.node(first, .enum_literal);
            },
            .period_brace => return p.parseLiteral(),
            .l_paren => {
                p.advance();
                const inner = try p.parseExpr();
                _ = try p.expect(.r_paren);
                return p.node(first, .{ .paren = inner });
            },
            .keyword_if => return p.parseIf(),
            .keyword_switch => return p.parseSwitch(),
            else => return p.unexpected("an expression"),
        }
    }

    /// An `else` is optional everywhere here. The real parser allows leaving
    /// it out only of a field's value or a list's item, but that is a rule of
    /// meaning, and where it is allowed an `else` binds to the nearest `if`,
    /// which is what this does everywhere.
    fn parseIf(p: *Parser) Error!*const Node {
        try p.enter();
        defer p.leave();
        const first = p.i;
        p.advance();
        _ = try p.expect(.l_paren);
        const cond = try p.parseExpr();
        _ = try p.expect(.r_paren);
        var capture: ?u32 = null;
        if (p.tag() == .pipe) {
            p.advance();
            capture = try p.expectName();
            _ = try p.expect(.pipe);
        }
        const then = try p.parseBranch();
        var otherwise: ?*const Node = null;
        if (p.tag() == .keyword_else) {
            p.advance();
            otherwise = try p.parseBranch();
        }
        return p.node(first, .{ .@"if" = .{ .cond = cond, .capture = capture, .then = then, .@"else" = otherwise } });
    }

    fn parseBranch(p: *Parser) Error!*const Node {
        if (p.tag() == .keyword_if) return p.parseIf();
        return p.parseExpr();
    }

    fn parseSwitch(p: *Parser) Error!*const Node {
        try p.enter();
        defer p.leave();
        const first = p.i;
        p.advance();
        _ = try p.expect(.l_paren);
        const subject = try p.parseExpr();
        _ = try p.expect(.r_paren);
        _ = try p.expect(.l_brace);

        var prongs: std.ArrayList(*const Node) = .empty;
        while (p.tag() != .r_brace) {
            const prong_first = p.i;
            var cases: std.ArrayList(*const Node) = .empty;
            if (p.tag() == .keyword_else) {
                p.advance();
            } else while (true) {
                const lo = try p.parseExpr();
                if (p.tag() == .ellipsis3) {
                    p.advance();
                    const hi = try p.parseExpr();
                    try cases.append(p.arena, try p.node(lo.first, .{ .range = .{ .lo = lo, .hi = hi } }));
                } else {
                    try cases.append(p.arena, lo);
                }
                if (p.tag() != .comma) break;
                p.advance();
                if (p.tag() == .equal_angle_bracket_right) break;
            }
            const arrow = try p.expect(.equal_angle_bracket_right);
            var capture: ?u32 = null;
            if (p.tag() == .pipe) {
                p.advance();
                capture = try p.expectName();
                _ = try p.expect(.pipe);
            }
            const value = try p.parseExpr();
            try prongs.append(p.arena, try p.node(prong_first, .{ .prong = .{
                .cases = cases.items,
                .arrow = arrow,
                .capture = capture,
                .value = value,
            } }));
            if (p.tag() == .comma) {
                p.advance();
            } else if (p.tag() != .r_brace) {
                return p.unexpected("',' or '}}'");
            }
        }
        p.advance();
        if (prongs.items.len == 0) return p.fail(first, "a switch needs at least one prong", .{});
        return p.node(first, .{ .@"switch" = .{ .subject = subject, .prongs = prongs.items } });
    }

    fn parseItem(p: *Parser) Error!*const Node {
        if (p.tag() == .keyword_if) return p.parseIf();
        return p.parseExpr();
    }

    fn parseLiteral(p: *Parser) Error!*const Node {
        try p.enter();
        defer p.leave();
        const first = p.i;
        p.advance();
        var items: std.ArrayList(*const Node) = .empty;
        if (p.tag() == .r_brace) {
            p.advance();
            return p.node(first, .{ .literal = items.items });
        }
        const is_record = p.tag() == .period and
            (p.toks[p.i + 1].tag == .identifier or p.toks[p.i + 1].tag == .quoted_identifier) and
            p.toks[p.i + 2].tag == .equal;
        while (true) {
            if (is_record) {
                const field_first = p.i;
                if (p.tag() != .period) return p.unexpected("'.name = value' or '}}'");
                p.advance();
                _ = try p.expectName();
                _ = try p.expect(.equal);
                const value = try p.parseItem();
                try items.append(p.arena, try p.node(field_first, .{ .field_init = value }));
            } else {
                try items.append(p.arena, try p.parseItem());
            }
            switch (p.tag()) {
                .comma => {
                    p.advance();
                    if (p.tag() == .r_brace) break;
                },
                .r_brace => break,
                else => return p.unexpected("',' or '}}'"),
            }
        }
        p.advance();
        return p.node(first, .{ .literal = items.items });
    }

    /// Each `${ }` in the string content `source[start..end]`, parsed as
    /// `Parser.zig` parses it, by pointing a second tokenizer at its inside.
    /// `escapes` is whether a `\` escapes the byte after it, as it does in
    /// a string and not in a multiline string's line. The tokenizer has
    /// already checked that every `${` is closed, and how deeply strings nest.
    fn interpolations(p: *Parser, start: u32, end: u32, escapes: bool) Error![]const Interpolation {
        var found: std.ArrayList(Interpolation) = .empty;
        var i = start;
        while (i < end) {
            if (p.source[i] == '\\' and escapes) {
                i += 2;
            } else if (p.source[i] == '$' and i + 1 < end and p.source[i + 1] == '{') {
                const close = Tokenizer.skipInterpolation(p.source, i + 2, end, 0) orelse {
                    p.diag.set(.of(p.source, i), "unterminated interpolation", .{});
                    return error.Syntax;
                };
                try found.append(p.arena, try p.interpolation(i, close));
                i = close + 1;
            } else i += 1;
        }
        return found.items;
    }

    fn interpolation(p: *Parser, dollar: u32, close: u32) Error!Interpolation {
        var toks: std.ArrayList(Token) = .empty;
        var t: Tokenizer = .{ .source = p.source, .index = dollar + 2, .limit = close };
        while (true) {
            const tok = t.next();
            if (tok.tag == .invalid) return invalidToken(p.source, tok, p.diag);
            try toks.append(p.arena, tok);
            if (tok.tag == .eof) break;
        }
        if (toks.items.len == 1) {
            p.diag.set(.of(p.source, dollar), "empty interpolation", .{});
            return error.Syntax;
        }
        const saved_toks = p.toks;
        const saved_i = p.i;
        defer {
            p.toks = saved_toks;
            p.i = saved_i;
        }
        p.toks = toks.items;
        p.i = 0;
        const n = try p.parseExpr();
        if (p.tag() != .eof) return p.unexpected("'}}'");
        return .{ .toks = toks.items, .node = n };
    }

    fn parseCall(p: *Parser) Error!*const Node {
        try p.enter();
        defer p.leave();
        const first = p.i;
        p.advance();
        _ = try p.expect(.l_paren);
        var args: std.ArrayList(*const Node) = .empty;
        while (p.tag() != .r_paren) {
            try args.append(p.arena, try p.parseExpr());
            if (p.tag() == .comma) {
                p.advance();
            } else if (p.tag() != .r_paren) {
                return p.unexpected("',' or ')'");
            }
        }
        p.advance();
        return p.node(first, .{ .call = args.items });
    }
};

// -- outline ------------------------------------------------------------------

/// What a `Span` is: the shape of the source it covers.
pub const SpanKind = enum {
    /// The whole program, from its first token to its last.
    file,
    /// `let name = value;`
    let,
    /// `.{ ... }`, a struct or list literal.
    literal,
    /// `.name = value`, inside a struct literal.
    field,
    /// `@name(args)`
    call,
    @"switch",
    /// `cases => value`, inside a switch.
    prong,
    @"if",
    /// One or more `\\` lines.
    multiline_string,
    /// A name used as a value: `ctx`, a `let`, a capture, `inf` or `nan`.
    name,
    /// Any other expression: a number, a string, an operator and its
    /// operands, `x.name`, `x[i]`, `(x)`, `lo...hi`.
    expression,
};

/// Where a name is written, by byte offsets into the source.
pub const NameSpan = struct { start: u32, end: u32 };

/// A piece of a program, by where it starts and ends in the source.
pub const Span = struct {
    /// Byte offsets: `source[start..end]` is the span, comments within it
    /// included and comments around it not.
    start: u32,
    end: u32,
    kind: SpanKind,
    /// The index of the span this one is inside, which comes before it, or
    /// null for the `file`.
    parent: ?u32,
    /// The name the span binds or calls, which is not a span of its own: a
    /// `let`'s name, an `if`'s or a prong's `|name|`, a field's `.name`
    /// without its `.`, or a call's `@name` with its `@`.
    name: ?NameSpan = null,
};

/// The program in `source` as a tree of spans, for an editor to fold or to
/// grow a selection by. Every span comes before the spans inside it, and
/// after any that end before it starts, so the spans holding an offset are
/// a chain whose innermost is the last of them. The caller frees the
/// result.
///
/// It parses as `format` does: names are not resolved, nor files included,
/// and any function name is accepted. What is inside a string's `${ }` is
/// outlined too, inside the string's span.
pub fn outline(gpa: Allocator, source: []const u8, options: Options, diag: *Diagnostic) Error![]Span {
    var arena_state: std.heap.ArenaAllocator = .init(gpa);
    defer arena_state.deinit();
    const arena = arena_state.allocator();

    if (source.len >= std.math.maxInt(u32)) {
        diag.set(.{}, "program too large", .{});
        return error.Syntax;
    }
    var p: Parser = .{
        .arena = arena,
        .source = source,
        .toks = try tokenize(arena, source, diag),
        .diag = diag,
        .max_depth = options.max_depth,
    };
    const file = try p.parseFile();

    var o: Outliner = .{ .gpa = gpa, .toks = p.toks };
    errdefer o.spans.deinit(gpa);
    const root = try o.add(0, file.eof - 1, .file, null);
    for (file.lets) |let| {
        const index = try o.add(let.value.first - 3, let.value.last + 1, .let, root);
        o.named(index, let.value.first - 2);
        try o.node(let.value, index);
    }
    try o.node(file.root, root);
    return o.spans.toOwnedSlice(gpa);
}

const Outliner = struct {
    gpa: Allocator,
    toks: []const Token,
    spans: std.ArrayList(Span) = .empty,

    /// A span from token `first` to token `last`, both included.
    fn add(o: *Outliner, first: u32, last: u32, kind: SpanKind, parent: ?u32) Allocator.Error!u32 {
        const index: u32 = @intCast(o.spans.items.len);
        try o.spans.append(o.gpa, .{
            .start = o.toks[first].start,
            .end = o.toks[last].end,
            .kind = kind,
            .parent = parent,
        });
        return index;
    }

    /// Give span `index` the name that is token `tok`.
    fn named(o: *Outliner, index: u32, tok: u32) void {
        o.spans.items[index].name = .{ .start = o.toks[tok].start, .end = o.toks[tok].end };
    }

    /// `n` and everything inside it. The parser bounds how deeply nodes
    /// nest, which bounds how deeply this recurses.
    fn node(o: *Outliner, n: *const Node, parent: u32) Allocator.Error!void {
        const kind: SpanKind = switch (n.data) {
            .token => switch (o.toks[n.first].tag) {
                .identifier, .quoted_identifier => .name,
                else => .expression,
            },
            .multiline => .multiline_string,
            .call => .call,
            .literal => .literal,
            .field_init => .field,
            .@"if" => .@"if",
            .@"switch" => .@"switch",
            .prong => .prong,
            else => .expression,
        };
        const index = try o.add(n.first, n.last, kind, parent);
        switch (n.data) {
            .call => o.named(index, n.first),
            .field_init => o.named(index, n.first + 1),
            .@"if" => |x| if (x.capture) |c| o.named(index, c),
            .prong => |x| if (x.capture) |c| o.named(index, c),
            else => {},
        }
        if (n.interpolations.len > 0) {
            const saved = o.toks;
            defer o.toks = saved;
            for (n.interpolations) |x| {
                o.toks = x.toks;
                try o.node(x.node, index);
            }
        }
        switch (n.data) {
            .token, .multiline, .enum_literal => {},
            .paren, .unary, .field, .unwrap, .field_init => |inner| try o.node(inner, index),
            .binary => |b| {
                try o.node(b.lhs, index);
                try o.node(b.rhs, index);
            },
            .index => |x| {
                try o.node(x.object, index);
                try o.node(x.index, index);
            },
            .call, .literal => |items| for (items) |item| try o.node(item, index),
            .@"if" => |x| {
                try o.node(x.cond, index);
                try o.node(x.then, index);
                if (x.@"else") |e| try o.node(e, index);
            },
            .@"switch" => |x| {
                try o.node(x.subject, index);
                for (x.prongs) |prong| try o.node(prong, index);
            },
            .prong => |x| {
                for (x.cases) |case| try o.node(case, index);
                try o.node(x.value, index);
            },
            .range => |x| {
                try o.node(x.lo, index);
                try o.node(x.hi, index);
            },
        }
    }
};

// -- rendering ----------------------------------------------------------------

/// Writes tokens in order, with the comments between them.
///
/// Space and line breaks are asked for rather than written, and only written
/// when the next thing is: so a space asked for before a line break is never
/// written, and a comment that was at the end of a line can still be put
/// there after the break before the next token has been asked for.
const Renderer = struct {
    gpa: Allocator,
    source: []const u8,
    toks: []const Token,
    out: *std.ArrayList(u8),
    indent: u32 = 0,
    /// Comments have been written from the gaps before every token below
    /// this one.
    gaps_done: u32 = 0,
    /// Where the last token or comment written ends in the source.
    last_end: u32 = 0,
    /// The last token written, or null if a comment came after it.
    last_tag: ?Tag = null,
    space: bool = false,
    /// Line breaks asked for: one, or two for a blank line.
    newlines: u2 = 0,

    const indent_width = 4;

    fn file(r: *Renderer, f: File) Error!void {
        for (f.lets) |let| {
            const v = let.value;
            try r.token(v.first - 3); // let
            r.space = true;
            try r.token(v.first - 2); // name
            r.space = true;
            try r.token(v.first - 1); // =
            r.space = true;
            try r.expr(v);
            try r.token(v.last + 1); // ;
            r.lineBreak();
        }
        try r.expr(f.root);
        try r.comments(f.eof);
        try r.out.append(r.gpa, '\n');
    }

    fn lineBreak(r: *Renderer) void {
        r.newlines = @max(r.newlines, 1);
    }

    fn atLineStart(r: *const Renderer) bool {
        return r.out.items.len == 0 or r.newlines > 0;
    }

    /// Write the space and the line breaks asked for, if anything has been
    /// written yet: a file starts with what is in it.
    fn begin(r: *Renderer) Error!void {
        if (r.out.items.len == 0) {
            r.newlines = 0;
            r.space = false;
            return;
        }
        if (r.newlines > 0) {
            try r.out.appendNTimes(r.gpa, '\n', r.newlines);
            try r.out.appendNTimes(r.gpa, ' ', r.indent);
        } else if (r.space) {
            try r.out.append(r.gpa, ' ');
        }
        r.newlines = 0;
        r.space = false;
    }

    /// Ask for a blank line before what starts at `start`, if the source had
    /// one there and a line break has been asked for anyway.
    fn keepBlankLine(r: *Renderer, start: u32, next: ?Tag) void {
        if (r.newlines == 0 or r.out.items.len == 0) return;
        if (r.last_tag) |t| if (opens(t)) return;
        if (next) |t| if (closes(t)) return;
        if (r.last_tag == .multiline_string_line and next == .multiline_string_line) return;
        if (std.mem.count(u8, r.source[r.last_end..start], "\n") >= 2) r.newlines = 2;
    }

    /// Write token `i`, after the comments before it.
    fn token(r: *Renderer, i: u32) Error!void {
        try r.comments(i);
        const t = r.toks[i];
        r.keepBlankLine(t.start, t.tag);
        try r.begin();
        var bytes = r.source[t.start..t.end];
        // A line ending in `\r\n` is written with `\n`. The parser drops one
        // `\r` from the end of a line and keeps any others as content, so the
        // `\r` goes only if what is left does not end with another -- which
        // would then be the one dropped, and lost.
        if (t.tag == .multiline_string_line and std.mem.endsWith(u8, bytes, "\r") and
            !std.mem.endsWith(u8, bytes[0 .. bytes.len - 1], "\r"))
        {
            bytes = bytes[0 .. bytes.len - 1];
        }
        try r.out.appendSlice(r.gpa, bytes);
        r.last_end = t.end;
        r.last_tag = t.tag;
    }

    /// Write text that is not in the source: a trailing comma.
    fn text(r: *Renderer, s: []const u8) Error!void {
        try r.begin();
        try r.out.appendSlice(r.gpa, s);
    }

    /// Write the comments in the gaps before every token up to `i`.
    fn comments(r: *Renderer, i: u32) Error!void {
        while (r.gaps_done <= i) : (r.gaps_done += 1) {
            const k = r.gaps_done;
            var pos: u32 = if (k == 0) 0 else r.toks[k - 1].end;
            const end = r.toks[k].start;
            while (pos < end) {
                if (r.source[pos] == '/') {
                    const stop: u32 = @intCast(std.mem.findScalarPos(u8, r.source[0..end], pos, '\n') orelse end);
                    try r.comment(pos, stop);
                    pos = stop;
                } else pos += 1;
            }
        }
    }

    fn comment(r: *Renderer, start: u32, end: u32) Error!void {
        const body = std.mem.trimEnd(u8, r.source[start..end], " \t\r");
        const same_line = r.out.items.len != 0 and
            std.mem.findScalar(u8, r.source[r.last_end..start], '\n') == null;
        if (same_line) {
            // Where it was: at the end of the line, even if a line break has
            // been asked for since.
            try r.out.append(r.gpa, ' ');
            try r.out.appendSlice(r.gpa, body);
        } else {
            r.lineBreak();
            r.keepBlankLine(start, null);
            try r.begin();
            try r.out.appendSlice(r.gpa, body);
        }
        r.space = false;
        r.lineBreak();
        r.last_end = end;
        r.last_tag = null;
    }

    fn opens(t: Tag) bool {
        return t == .period_brace or t == .l_brace or t == .l_paren or t == .l_bracket;
    }

    fn closes(t: Tag) bool {
        return t == .r_brace or t == .r_paren or t == .r_bracket;
    }

    // -- what breaks ----------------------------------------------------------

    /// Whether there is a comment in a gap before any of the tokens after
    /// `first`, up to and including `last`.
    fn hasComment(r: *const Renderer, first: u32, last: u32) bool {
        var k = first + 1;
        while (k <= last) : (k += 1) {
            const gap = r.source[r.toks[k - 1].end..r.toks[k].start];
            if (std.mem.find(u8, gap, "//") != null) return true;
        }
        return false;
    }

    fn newlineAfter(r: *const Renderer, i: u32) bool {
        return std.mem.findScalar(u8, r.source[r.toks[i].end..r.toks[i + 1].start], '\n') != null;
    }

    /// Whether `n` cannot be written on one line: what it renders has a line
    /// break in it.
    fn breaks(r: *const Renderer, n: *const Node) bool {
        if (r.hasComment(n.first, n.last)) return true;
        return switch (n.data) {
            .token, .enum_literal => false,
            .multiline => true,
            .paren, .unary, .field, .unwrap, .field_init => |x| r.breaks(x),
            .binary => |b| r.newlineAfter(b.op) or r.breaks(b.lhs) or r.breaks(b.rhs),
            .index => |x| r.breaks(x.object) or r.breaks(x.index),
            .call => |args| r.tall(n.first + 1, args, n.last),
            .literal => |items| r.tall(n.first, items, n.last),
            .@"if" => |x| r.breaks(x.cond) or r.breaks(x.then) or
                (if (x.@"else") |e| r.breaks(e) else false),
            .@"switch" => |x| r.breaks(x.subject) or r.tall(x.subject.last + 2, x.prongs, n.last),
            .prong => |x| r.tallCases(x.cases, x.arrow) or r.breaks(x.value),
            .range => |x| r.breaks(x.lo) or r.breaks(x.hi),
        };
    }

    /// Whether the items between `open` and `close` go one to a line.
    fn tall(r: *const Renderer, open: u32, items: []const *const Node, close: u32) bool {
        if (r.hasComment(open, close)) return true;
        if (items.len == 0) return false;
        if (r.toks[items[items.len - 1].last + 1].tag == .comma) return true;
        for (items) |item| if (r.breaks(item)) return true;
        return false;
    }

    fn tallCases(r: *const Renderer, cases: []const *const Node, arrow: u32) bool {
        if (cases.len == 0) return false;
        if (r.hasComment(cases[0].first, arrow)) return true;
        if (r.toks[arrow - 1].tag == .comma) return true;
        for (cases) |c| if (r.breaks(c)) return true;
        return false;
    }

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

    fn expr(r: *Renderer, n: *const Node) Error!void {
        switch (n.data) {
            .token => try r.token(n.first),
            .multiline => try r.multiline(n),
            .enum_literal => {
                try r.token(n.first);
                try r.token(n.first + 1);
            },
            .paren => |inner| {
                try r.token(n.first);
                try r.expr(inner);
                try r.token(n.last);
            },
            .unary => |operand| {
                try r.token(n.first);
                try r.expr(operand);
            },
            .binary => |b| {
                try r.expr(b.lhs);
                r.space = true;
                try r.token(b.op);
                if (r.newlineAfter(b.op)) {
                    r.indent += indent_width;
                    r.lineBreak();
                    try r.expr(b.rhs);
                    r.indent -= indent_width;
                } else {
                    r.space = true;
                    try r.expr(b.rhs);
                }
            },
            .field => |object| {
                try r.expr(object);
                // `0x1 .a` written as `0x1.a` would be one hex number.
                if (r.toks[object.last].tag == .number) r.space = true;
                try r.token(n.last - 1);
                try r.token(n.last);
            },
            .unwrap => |object| {
                try r.expr(object);
                try r.token(n.last);
            },
            .index => |x| {
                try r.expr(x.object);
                try r.token(x.index.first - 1);
                try r.expr(x.index);
                try r.token(n.last);
            },
            .call => |args| {
                try r.token(n.first);
                try r.list(n.first + 1, args, n.last, false);
            },
            .literal => |items| try r.list(n.first, items, n.last, true),
            .field_init => |value| {
                try r.token(n.first);
                try r.token(n.first + 1);
                r.space = true;
                try r.token(n.first + 2);
                r.space = true;
                try r.expr(value);
            },
            .@"if" => |x| {
                try r.token(n.first);
                r.space = true;
                try r.token(n.first + 1);
                try r.expr(x.cond);
                try r.token(x.cond.last + 1);
                if (x.capture) |name| try r.capture(name);
                r.space = true;
                try r.expr(x.then);
                if (x.@"else") |otherwise| {
                    r.space = true;
                    try r.token(x.then.last + 1);
                    r.space = true;
                    try r.expr(otherwise);
                }
            },
            .@"switch" => |x| {
                try r.token(n.first);
                r.space = true;
                try r.token(n.first + 1);
                try r.expr(x.subject);
                try r.token(x.subject.last + 1);
                r.space = true;
                try r.list(x.subject.last + 2, x.prongs, n.last, true);
            },
            .prong => |x| {
                if (x.cases.len == 0) {
                    try r.token(n.first); // else
                    r.space = true;
                } else if (r.tallCases(x.cases, x.arrow)) {
                    for (x.cases, 0..) |c, i| {
                        if (i > 0) r.lineBreak();
                        try r.expr(c);
                        try r.comma(c);
                    }
                    r.lineBreak();
                } else {
                    for (x.cases, 0..) |c, i| {
                        if (i > 0) {
                            try r.token(x.cases[i - 1].last + 1);
                            r.space = true;
                        }
                        try r.expr(c);
                    }
                    r.space = true;
                }
                try r.token(x.arrow);
                if (x.capture) |name| try r.capture(name);
                r.space = true;
                try r.expr(x.value);
            },
            .range => |x| {
                try r.expr(x.lo);
                try r.token(x.lo.last + 1);
                try r.expr(x.hi);
            },
        }
    }

    /// ` |name|`, given the name.
    fn capture(r: *Renderer, name: u32) Error!void {
        r.space = true;
        try r.token(name - 1);
        try r.token(name);
        try r.token(name + 1);
    }

    /// The comma after `item`: its own, or a new one.
    fn comma(r: *Renderer, item: *const Node) Error!void {
        if (r.toks[item.last + 1].tag == .comma) return r.token(item.last + 1);
        return r.text(",");
    }

    /// `open items close`, on one line or one item to a line. `padded` puts
    /// a space inside the brackets when they are on one line, as Zig does for
    /// `.{ 1, 2 }` and not for a call's `(1, 2)`.
    fn list(r: *Renderer, open: u32, items: []const *const Node, close: u32, padded: bool) Error!void {
        const is_tall = r.tall(open, items, close);
        try r.token(open);
        if (is_tall) {
            r.indent += indent_width;
            for (items) |item| {
                r.lineBreak();
                try r.expr(item);
                try r.comma(item);
            }
            // What is left before the bracket -- comments after the last
            // item -- belongs to the items, at their indent.
            try r.comments(close);
            r.indent -= indent_width;
            r.lineBreak();
        } else if (items.len != 0) {
            r.space = padded;
            for (items, 0..) |item, i| {
                if (i > 0) {
                    try r.token(items[i - 1].last + 1);
                    r.space = true;
                }
                try r.expr(item);
            }
            r.space = padded;
        }
        try r.token(close);
    }

    /// Each `\\` line on a line of its own: one indent in, if the string does
    /// not already start a line. Whatever follows starts on the next line.
    fn multiline(r: *Renderer, n: *const Node) Error!void {
        const extra: u32 = if (r.atLineStart()) 0 else indent_width;
        r.indent += extra;
        var i = n.first;
        while (i <= n.last) : (i += 1) {
            r.lineBreak();
            try r.token(i);
        }
        r.indent -= extra;
        r.lineBreak();
    }
};

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

const testing = std.testing;

fn expectFormat(source: []const u8, expected: []const u8) !void {
    var d: Diagnostic = .{};
    const got = format(testing.allocator, source, .{}, &d) catch |err| {
        std.debug.print("{f}\n", .{&d});
        return err;
    };
    defer testing.allocator.free(got);
    try testing.expectEqualStrings(expected, got);
    // Formatting what is formatted changes nothing.
    const again = try format(testing.allocator, got, .{}, &d);
    defer testing.allocator.free(again);
    try testing.expectEqualStrings(got, again);
}

test "spacing" {
    try expectFormat("let  a=1 ;let b =a+ -2*3;b", "let a = 1;\nlet b = a + -2 * 3;\nb\n");
    try expectFormat("! ctx . a .? or ctx.xs[ 0 ]orelse(1)", "!ctx.a.? or ctx.xs[0] orelse (1)\n");
    try expectFormat("@max( 1 , 2 )", "@max(1, 2)\n");
    try expectFormat("if(ctx.a)|v|v else  if (true) 2 else 3", "if (ctx.a) |v| v else if (true) 2 else 3\n");
    try expectFormat(".@\"two words\"", ".@\"two words\"\n");
}

test "a literal is one line unless it ends with a comma" {
    try expectFormat(".{.a=1,.b=.{1,2}}", ".{ .a = 1, .b = .{ 1, 2 } }\n");
    try expectFormat(".{ }", ".{}\n");
    try expectFormat(".{.a=1,.b=2,}",
        \\.{
        \\    .a = 1,
        \\    .b = 2,
        \\}
        \\
    );
    // A tall literal inside makes the one around it tall too.
    try expectFormat(".{ .a = .{ 1, }, .b = 2 }",
        \\.{
        \\    .a = .{
        \\        1,
        \\    },
        \\    .b = 2,
        \\}
        \\
    );
    try expectFormat("@join(.{ \"a\", \"b\" }, \",\",)",
        \\@join(
        \\    .{ "a", "b" },
        \\    ",",
        \\)
        \\
    );
}

test "comments stay where they were" {
    try expectFormat(
        \\// a file
        \\
        \\
        \\let a = 1;   // one
        \\
        \\// the value
        \\.{
        \\
        \\    .a = a, // a
        \\    // b next
        \\    .b = 2
        \\    // the end
        \\
        \\}
    ,
        \\// a file
        \\
        \\let a = 1; // one
        \\
        \\// the value
        \\.{
        \\    .a = a, // a
        \\    // b next
        \\    .b = 2,
        \\    // the end
        \\}
        \\
    );
    // A comment makes a literal tall, and is kept even in an empty one. One
    // after the opening bracket stays there, as it does in Zig.
    try expectFormat(".{ 1, 2 // two\n}", ".{\n    1,\n    2, // two\n}\n");
    try expectFormat(".{\n// nothing\n}", ".{\n    // nothing\n}\n");
    try expectFormat(".{ // first\n1 }", ".{ // first\n    1,\n}\n");
}

test "a line break after an operator is kept" {
    try expectFormat("ctx.a and\nctx.b and\n   ctx.c", "ctx.a and\n    ctx.b and\n    ctx.c\n");
    try expectFormat("ctx.a\nand ctx.b", "ctx.a and ctx.b\n");
    try expectFormat("1 + // one\n2", "1 + // one\n    2\n");
}

test "multiline strings are lines of their own" {
    // The spaces after `${x}` are part of the string, and stay.
    try expectFormat(
        ".{ .a = \\\\one\n  \\\\two ${x}  \n, .b = 1 }",
        ".{\n    .a =\n        \\\\one\n        \\\\two ${x}  \n    ,\n    .b = 1,\n}\n",
    );
    try expectFormat("let s = \\\\x\n; s", "let s =\n    \\\\x\n;\ns\n");
    try expectFormat("\\\\a\r\n\\\\b\r\n", "\\\\a\n\\\\b\n");
}

test "switch" {
    try expectFormat("switch(ctx.n){1...4=>8,5,6=>|v|v,else=>0}", "switch (ctx.n) { 1...4 => 8, 5, 6 => |v| v, else => 0 }\n");
    try expectFormat("switch (ctx.n) { 1 => 2, else => 3, }",
        \\switch (ctx.n) {
        \\    1 => 2,
        \\    else => 3,
        \\}
        \\
    );
    try expectFormat("switch (ctx.n) { .a, .b, => 1 }",
        \\switch (ctx.n) {
        \\    .a,
        \\    .b,
        \\    => 1,
        \\}
        \\
    );
}

test "a number keeps its distance from a field" {
    try expectFormat("0x1 .a", "0x1 .a\n");
}

test "a program that does not parse is an error with a position" {
    var d: Diagnostic = .{};
    try testing.expectError(error.Syntax, format(testing.allocator, ".{ .a = }", .{}, &d));
    try testing.expectEqual(Diagnostic.Pos{ .line = 1, .column = 9 }, d.pos);
    try testing.expectError(error.Syntax, format(testing.allocator, "\"abc", .{}, &d));
    try testing.expectEqualStrings("unterminated string", d.message());
}

test "an outline is the program's spans, outermost first" {
    const source =
        \\let a = 1;
        \\.{ .b = @max(a, 2) }
    ;
    var d: Diagnostic = .{};
    const spans = try outline(testing.allocator, source, .{}, &d);
    defer testing.allocator.free(spans);

    var got: std.Io.Writer.Allocating = .init(testing.allocator);
    defer got.deinit();
    for (spans) |span| {
        try got.writer.print("{t} {?d} '{s}'", .{ span.kind, span.parent, source[span.start..span.end] });
        if (span.name) |n| try got.writer.print(" named '{s}'", .{source[n.start..n.end]});
        try got.writer.writeByte('\n');
    }
    try testing.expectEqualStrings(
        \\file null 'let a = 1;
        \\.{ .b = @max(a, 2) }'
        \\let 0 'let a = 1;' named 'a'
        \\expression 1 '1'
        \\literal 0 '.{ .b = @max(a, 2) }'
        \\field 3 '.b = @max(a, 2)' named 'b'
        \\call 4 '@max(a, 2)' named '@max'
        \\name 5 'a'
        \\expression 5 '2'
        \\
    , got.written());
}

test "an outline names captures" {
    const source = "if (ctx.a) |x| switch (x) { else => |y| y } else 0";
    var d: Diagnostic = .{};
    const spans = try outline(testing.allocator, source, .{}, &d);
    defer testing.allocator.free(spans);
    var names: std.ArrayList(u8) = .empty;
    defer names.deinit(testing.allocator);
    for (spans) |span| if (span.name) |n| {
        try names.print(testing.allocator, "{t}:{s} ", .{ span.kind, source[n.start..n.end] });
    };
    try testing.expectEqualStrings("if:x prong:y ", names.items);
}

test "an outline looks inside a string's interpolations" {
    const source = "let a = 1;\n.{ \"x${a}y${\"${@f(a)}\"}\\${a}\",\n\\\\${a + 1}\n}";
    var d: Diagnostic = .{};
    const spans = try outline(testing.allocator, source, .{}, &d);
    defer testing.allocator.free(spans);
    var got: std.ArrayList(u8) = .empty;
    defer got.deinit(testing.allocator);
    for (spans[4..]) |span| {
        try got.print(testing.allocator, "{t} {?d} '{s}'\n", .{ span.kind, span.parent, source[span.start..span.end] });
    }
    try testing.expectEqualStrings(
        \\expression 3 '"x${a}y${"${@f(a)}"}\${a}"'
        \\name 4 'a'
        \\expression 4 '"${@f(a)}"'
        \\call 6 '@f(a)'
        \\name 7 'a'
        \\multiline_string 3 '\\${a + 1}'
        \\expression 9 'a + 1'
        \\name 10 'a'
        \\expression 10 '1'
        \\
    , got.items);
}

test "an interpolation that does not parse is an error with a position" {
    var d: Diagnostic = .{};
    try testing.expectError(error.Syntax, outline(testing.allocator, "\"ab${}\"", .{}, &d));
    try testing.expectEqual(Diagnostic.Pos{ .line = 1, .column = 4 }, d.pos);
    try testing.expectEqualStrings("empty interpolation", d.message());
    try testing.expectError(error.Syntax, format(testing.allocator, "\"${1 +}\"", .{}, &d));
    try testing.expectEqual(Diagnostic.Pos{ .line = 1, .column = 7 }, d.pos);
}

test "an outline of a program that does not parse is an error with a position" {
    var d: Diagnostic = .{};
    try testing.expectError(error.Syntax, outline(testing.allocator, ".{ .a = }", .{}, &d));
    try testing.expectEqual(Diagnostic.Pos{ .line = 1, .column = 9 }, d.pos);
}

// -- formatting never changes what a program means ----------------------------

const ast = @import("ast.zig");
const RealParser = @import("Parser.zig");

/// Whether two trees mean the same, wherever they were written.
fn sameNode(a: *const ast.Node, b: *const ast.Node) bool {
    if (std.meta.activeTag(a.data) != std.meta.activeTag(b.data)) return false;
    return switch (a.data) {
        .null, .ctx => true,
        .bool => |x| x == b.data.bool,
        .int => |x| x == b.data.int,
        // By bits, so that a NaN is the same as itself.
        .float => |x| @as(u64, @bitCast(x)) == @as(u64, @bitCast(b.data.float)),
        .string => |x| std.mem.eql(u8, x, b.data.string),
        .enum_literal => |x| std.mem.eql(u8, x, b.data.enum_literal),
        .slot => |x| x == b.data.slot,
        .template => |x| x.len == b.data.template.len and for (x, b.data.template) |p, q| {
            if (std.meta.activeTag(p) != std.meta.activeTag(q)) break false;
            if (!switch (p) {
                .text => |t| std.mem.eql(u8, t, q.text),
                .expr => |e| sameNode(e, q.expr),
            }) break false;
        } else true,
        .record => |x| x.len == b.data.record.len and for (x, b.data.record) |f, g| {
            if (!std.mem.eql(u8, f.name, g.name) or !sameNode(f.value, g.value)) break false;
        } else true,
        .list => |x| sameNodes(x, b.data.list),
        .field => |x| std.mem.eql(u8, x.name, b.data.field.name) and sameNode(x.object, b.data.field.object),
        .index => |x| sameNode(x.object, b.data.index.object) and sameNode(x.index, b.data.index.index),
        .unwrap => |x| sameNode(x, b.data.unwrap),
        .unary => |x| x.op == b.data.unary.op and sameNode(x.operand, b.data.unary.operand),
        .binary => |x| x.op == b.data.binary.op and sameNode(x.lhs, b.data.binary.lhs) and sameNode(x.rhs, b.data.binary.rhs),
        .@"if" => |x| {
            const y = b.data.@"if";
            return x.capture == y.capture and sameNode(x.cond, y.cond) and sameNode(x.then, y.then) and
                sameOptional(x.@"else", y.@"else");
        },
        .@"switch" => |x| {
            const y = b.data.@"switch";
            if (!sameNode(x.subject, y.subject) or x.prongs.len != y.prongs.len) return false;
            for (x.prongs, y.prongs) |p, q| if (!sameProng(p, q)) return false;
            if ((x.@"else" == null) != (y.@"else" == null)) return false;
            return x.@"else" == null or sameProng(x.@"else".?, y.@"else".?);
        },
        .call => |x| std.meta.eql(x.func, b.data.call.func) and sameNodes(x.args, b.data.call.args),
    };
}

fn sameNodes(a: []const *const ast.Node, b: []const *const ast.Node) bool {
    if (a.len != b.len) return false;
    for (a, b) |x, y| if (!sameNode(x, y)) return false;
    return true;
}

fn sameOptional(a: ?*const ast.Node, b: ?*const ast.Node) bool {
    if (a == null or b == null) return a == null and b == null;
    return sameNode(a.?, b.?);
}

fn sameProng(a: ast.Prong, b: ast.Prong) bool {
    if (a.capture != b.capture or a.cases.len != b.cases.len or !sameNode(a.value, b.value)) return false;
    for (a.cases, b.cases) |c, d| {
        if (std.meta.activeTag(c) != std.meta.activeTag(d)) return false;
        if (!switch (c) {
            .value => |v| sameNode(v, d.value),
            .range => |r| sameNode(r.lo, d.range.lo) and sameNode(r.hi, d.range.hi),
        }) return false;
    }
    return true;
}

/// For any program the real parser accepts: it formats, what it formats to
/// parses to the same tree, and formatting that changes nothing.
fn checkFormat(gpa: Allocator, src: []const u8) !void {
    var arena_state: std.heap.ArenaAllocator = .init(gpa);
    defer arena_state.deinit();
    const arena = arena_state.allocator();
    var d: Diagnostic = .{};
    const before = RealParser.parse(arena, src, .{}, &d) catch |err| switch (err) {
        error.OutOfMemory => return err,
        else => return,
    };
    const out = format(gpa, src, .{}, &d) catch |err| {
        std.debug.print("{s}\nformat: {f}\n", .{ src, &d });
        return err;
    };
    defer gpa.free(out);
    const after = RealParser.parse(arena, out, .{}, &d) catch |err| {
        std.debug.print("{s}\nformatted to\n{s}\nwhich does not parse: {f}\n", .{ src, out, &d });
        return err;
    };
    const same = sameNode(before.root, after.root) and before.slots.len == after.slots.len and
        for (before.slots, after.slots) |x, y| {
            if (!sameOptional(x, y)) break false;
        } else true;
    if (!same) {
        std.debug.print("{s}\nformatted to\n{s}\nwhich means something else\n", .{ src, out });
        return error.FormattingChangedTheMeaning;
    }
    const again = try format(gpa, out, .{}, &d);
    defer gpa.free(again);
    if (!std.mem.eql(u8, out, again)) {
        std.debug.print("{s}\nformatted to\n{s}\nand then to\n{s}\n", .{ src, out, again });
        return error.FormattingIsNotIdempotent;
    }
}

const corpus = [_][]const u8{
    "1",
    "let a = 1; let b = a + 1; .{ .x = b }",
    ".{ .a = 1, .b = \"two\", .c = .three, .d = .{ 4, 5 }, .e = null, .f = 'x', }",
    "if (ctx.b) |x| x else if (false) 2 else 3",
    "\"a${ctx.s}b${\"c${1}\"}d\\${e}\"",
    "\\\\one ${ctx.n}\n\\\\two\n",
    ".{ \\\\one\n// between\n\\\\two\n, 1 }",
    "@join(@split(\"a,b\", \",\"), \"-\") ++ @lower(\"X\")",
    "-9223372036854775808 + 0x7fff_ffff * 1.5e3 / 2 % 3",
    "ctx.m.b.c[0] == 100 and !(ctx.n < 2) or ctx.none orelse 1 != 2",
    ".{ 1, if (true) 2, if (false) 3 else if (true) 4 }",
    ".{ .@\"if\" = inf, .b = -nan }",
    "switch (ctx.n) { 1...5, 9 => |v| v, -3 => 0, else => 1 }",
    "switch (ctx.n) { 1...5, // small\n 9, => |v| v,\n\n\n -3 => 0, else => 1, }",
    "-5.? + - -1 - !!true",
    "0x1 .a + 1 .b + 0x1.8p1 .c",
    "// only a comment before\n1 // and after\n// and below",
    "let a = 1 + // why\n 2;\n\n\n// and\nlet b = a\n* 3;\n.{ .x = a and\nb, .y = .{ // first\n}, }",
    "@max(1, \\\\x\n, 3)",
    "\\\\a\n\n\\\\b\n++ \"c\" ++ \\\\d\n",
    // A string that ends in a carriage return, written with and without a
    // line ending of its own.
    "\\\\\r\r",
    "\\\\\r\r\n",
    "\\\\a\r\n\\\\b\r\r\r\n",
    "let s = \\\\x\n; switch (s) { \\\\x\n => \\\\y\n, else => .{} }",
    "if (ctx.a) .{ 1, } else .{ .a = .{} }",
    "1 + if (ctx.a) 2 else 3 * 4",
};

test "formatting keeps the meaning, and formatting twice changes nothing" {
    for (corpus) |src| try checkFormat(testing.allocator, src);
}

fn fuzzFormat(_: void, smith: *std.testing.Smith) anyerror!void {
    var buf: [4096]u8 = undefined;
    try checkFormat(testing.allocator, buf[0..smith.slice(&buf)]);
}

test "fuzz format" {
    try testing.fuzz({}, fuzzFormat, .{});
}