examples/interpreter/

# Source text into tokens, one pass, no lookahead beyond the next byte.
#
# Part of `examples/interpreter/` — the root `main.hero` carries the program's
# argument. This module knows the shape of the little language's surface and
# nothing about its grammar: it says `.plus` where it sees `+` and never asks
# whether a `+` may stand there.
#
# WHAT IT REFUSES, and every refusal is named. A scanner that returns *no
# tokens* on bad input tells the caller nothing, so the four things that can go
# wrong here each carry a code and a message quoting the offending text:
# an unterminated string, an escape that is not one of the four, a byte that
# begins no token, and a number too large for an `i64`.
#
# THE LAST ONE IS A ROBUSTNESS RULE AND NOT A NICETY (design.md §1.12,
# CLAUDE.md §12). Heroes aborts on integer overflow at every width, so
# accumulating `value * 10 + digit` over a long run of digits does not wrap —
# it stops the whole interpreter with a panic. A script is INPUT, and input must
# not be able to kill the program reading it, so the multiplication is guarded
# before it happens rather than after. The test at the bottom feeds it
# nineteen and twenty digits and asserts a refusal, not a crash.
#
# **AND IT WORKS ON BYTES, WHICH IT DID NOT AT FIRST.** Every single-character
# decision below compares an `i64` taken from `source[at]`, never a
# `slice(from: at, to: at + 1)`. The first draft sliced, and the first script
# it was given killed it: `panic: string slice splits a character`, exit 134,
# because a comment in that script contained one em dash. A `str` is measured
# in bytes and a slice that splits a character ABORTS (spec § Failure), so
# slicing one byte at a time is safe only for ASCII — and a comment with an
# accented letter in it is not a strange input, it is the normal one. The
# slices that remain are all taken between ASCII boundaries (a whole word, a
# run of digits, a run inside a string literal), where they cannot split
# anything. This is the same rule as the number guard above, found the same
# way: by running the program instead of reasoning about it.
#
# THE LANGUAGE IS LINE-ORIENTED, so a newline is a token. Blank lines and
# comment-only lines collapse into the one `.newline` that follows them, which
# is what lets the parser say *a statement ends at the end of its line* without
# ever seeing an empty statement.

use lex/token

constant DIGITS: str
    "0123456789"

constant MAX: i64
    9223372036854775807

constant ERR_TEXT: str
    "unterminated_text"

constant ERR_ESCAPE: str
    "bad_escape"

constant ERR_BYTE: str
    "unknown_byte"

constant ERR_NUMBER: str
    "number_too_large"

# Every token in `source`, ending with exactly one `.finish`.
function scanned(source: str) -> [token.Token]?
    out: [token.Token] @= []
    at: i64 @= 0
    n = source.len()

    while at < n
        here = byte_at(source: source, at: at)

        if here == ' ' || here == '\t'
            at @ at + 1
        else if here == '#'
            at @ line_end(source: source, from: at)
        else if here == '\n'
            at @ at + 1

            # One `.newline` however many blank lines stood there, so the
            # parser never meets a statement with nothing in it.
            if !ends_with_newline(out)
                out @ out.push(.newline)
        else if is_digit(here)
            read = number_at(source: source, from: at)?
            out @ out.push(read.what)
            at @ read.next
        else if here == '"'
            read = text_at(source: source, from: at)?
            out @ out.push(read.what)
            at @ read.next
        else if is_word_start(here)
            read = word_at(source: source, from: at)
            out @ out.push(read.what)
            at @ read.next
        else
            read = operator_at(source: source, from: at)?
            out @ out.push(read.what)
            at @ read.next

    if !ends_with_newline(out) && out.len() > 0
        out @ out.push(.newline)

    return ok(out.push(.finish))

# One token and where the scanner continues. A record rather than two returns,
# because the two answers are one answer and splitting them is how a caller
# forgets to advance.
record Read
    what: token.Token
    next: i64

# Where the line holding `from` ends: the index of its `\n`, or the end of the
# source. Used to skip a comment.
function line_end(source: str, from: i64) -> i64
    at: i64 @= from

    while at < source.len() && byte_at(source: source, at: at) != '\n'
        at @ at + 1

    return at

# The byte at `at`, or -1 past the end — so every test below is one comparison
# and no caller has to check the length first. -1 is safe as *no byte* because
# a byte is 0..255 and this returns an `i64`.
function byte_at(source: str, at: i64) -> i64
    if at >= source.len() || at < 0
        return 0 - 1

    return source[at].to_i64().must()

function ends_with_newline(out: [token.Token]) -> bool
    if out.len() == 0
        return false

    return out[out.len() - 1] == .newline

function is_digit(b: i64) -> bool
    return b >= '0' && b <= '9'

# A letter or an underscore — what a name may begin with. Written as a range
# test on the byte rather than as a table, because the bytes of `a`..`z` are
# contiguous and a character literal is an integer (spec § Types).
function is_word_start(b: i64) -> bool
    return b >= 'a' && b <= 'z' || b >= 'A' && b <= 'Z' || b == '_'

function is_word_rest(b: i64) -> bool
    return is_word_start(b) || is_digit(b)

# The digits at `from`, accumulated — refusing rather than aborting when they
# do not fit. See the module header: this is the guard that keeps a script from
# panicking the interpreter.
function number_at(source: str, from: i64) -> Read?
    value: i64 @= 0
    at: i64 @= from

    while is_digit(byte_at(source: source, at: at))
        digit = byte_at(source: source, at: at) - '0'

        # `value * 10 + digit > MAX` is the test somebody writes first, and it
        # is the wrong one: computing it is the overflow. The division is what
        # makes the question answerable without asking it.
        if value > (MAX - digit) / 10
            return fail(
                code: ERR_NUMBER,
                msg: "`" + source.slice(from: from, to: at + 1) + "` does not fit in a 64-bit integer"
            )
        value @ value * 10 + digit
        at @ at + 1

    return ok(Read(what: .number(value: value), next: at))

# The string literal at `from`, with its four escapes decoded.
#
# Four and not six: `\n`, `\t`, `\"` and `\\`. The little language has no
# character literals, so `\'` would have nothing to escape, and `\r` is left
# out deliberately — a scanner that accepts an escape it cannot explain is a
# scanner whose author was copying.
function text_at(source: str, from: i64) -> Read?
    pieces: [str] @= []
    at: i64 @= from + 1

    # Where the current unescaped run began. The literal is copied a RUN at a
    # time rather than a byte at a time, and that is what keeps this safe on
    # text: every slice is taken between two ASCII bytes (the opening quote, an
    # escape's backslash, the closing quote), so none of them can split a
    # character. A byte-at-a-time loop aborts on the first accented letter.
    run: i64 @= at

    while at < source.len()
        one = byte_at(source: source, at: at)

        if one == '"'
            pieces @ pieces.push(source.slice(from: run, to: at))
            return ok(Read(what: .text(value: join(pieces, "")), next: at + 1))

        if one == '\n'
            return fail(code: ERR_TEXT, msg: "a string may not run past the end of its line")

        if one == '\\'
            pieces @ pieces.push(source.slice(from: run, to: at))
            next_one = byte_at(source: source, at: at + 1)

            if next_one == 0 - 1
                return fail(code: ERR_TEXT, msg: "the source ends inside a string")

            if next_one == 'n'
                pieces @ pieces.push("\n")
            else if next_one == 't'
                pieces @ pieces.push("\t")
            else if next_one == '"'
                pieces @ pieces.push("\"")
            else if next_one == '\\'
                pieces @ pieces.push("\\")
            else
                return fail(
                    code: ERR_ESCAPE,
                    msg: "`\\" + source.slice(from: at + 1, to: at + 2) + "` is not one of the four escapes `\\n` `\\t` `\\\"` `\\\\`"
                )
            at @ at + 2
            run @ at
        else
            at @ at + 1

    return fail(code: ERR_TEXT, msg: "the source ends inside a string")

# The word at `from`, resolved to a keyword or a name by `token.worded` — this
# module does not hold a list of keywords, and that is deliberate: one list, in
# the module that owns the vocabulary.
function word_at(source: str, from: i64) -> Read
    at: i64 @= from

    while is_word_rest(byte_at(source: source, at: at))
        at @ at + 1

    return Read(what: token.worded(source.slice(from: from, to: at)), next: at)

# The operator at `from`. The two-byte ones are tried before the one-byte ones
# they begin with, which is the whole subtlety here: `<=` read as `<` then `=`
# is a program that parses and means something else.
function operator_at(source: str, from: i64) -> Read?
    one = byte_at(source: source, at: from)
    two = byte_at(source: source, at: from + 1)

    if one == '<' && two == '='
        return ok(Read(what: .less_equal, next: from + 2))

    if one == '>' && two == '='
        return ok(Read(what: .greater_equal, next: from + 2))

    if one == '=' && two == '='
        return ok(Read(what: .equal_equal, next: from + 2))

    if one == '!' && two == '='
        return ok(Read(what: .bang_equal, next: from + 2))

    if one == '&' && two == '&'
        return ok(Read(what: .ampersands, next: from + 2))

    if one == '|' && two == '|'
        return ok(Read(what: .bars, next: from + 2))
    single = one_byte(one)

    if single.is_err()
        return unknown_byte(source: source, at: from)

    return ok(Read(what: single.must(), next: from + 1))

# A byte that begins no token, quoted in the refusal. The quoting is where the
# non-ASCII case has to be careful one last time: the offending byte may be the
# FIRST of a multi-byte character, so the message slices to the end of the
# line rather than to the next byte — a slice to `at + 1` would abort while
# building the diagnostic, which is the worst place to abort.
function unknown_byte(source: str, at: i64) -> Read?
    stop = line_end(source: source, from: at)
    return fail(
        code: ERR_BYTE,
        msg: "`" + source.slice(from: at, to: stop) + "` begins no token this language knows"
    )

function one_byte(b: i64) -> token.Token?
    if b == '+'
        return ok(.plus)

    if b == '-'
        return ok(.minus)

    if b == '*'
        return ok(.star)

    if b == '/'
        return ok(.slash)

    if b == '%'
        return ok(.percent)

    if b == '='
        return ok(.equals)

    if b == '<'
        return ok(.less)

    if b == '>'
        return ok(.greater)

    if b == '!'
        return ok(.bang)

    if b == '('
        return ok(.lparen)

    if b == ')'
        return ok(.rparen)

    if b == ','
        return ok(.comma)

    return fail(code: ERR_BYTE, msg: "not an operator")

# The code a scan refused with, or a sentence saying it did not — so a test
# asserts WHICH refusal in one line.
function refusal_of(said: [token.Token]?) -> str
    return match said
        .ok _  => "nothing was refused"
        .err e => e.code

test "a whole statement, token by token"
    got = scanned("let total = 3 + 4").must()
    assert got.len() == 8
    assert got[0] == .kw_let
    assert got[1] == .name(value: "total")
    assert got[2] == .equals
    assert got[3] == .number(value: 3)
    assert got[4] == .plus
    assert got[5] == .number(value: 4)
    assert got[6] == .newline
    assert got[7] == .finish

test "the empty source is one token, and it is the end"
    got = scanned("").must()
    assert got.len() == 1
    assert got[0] == .finish

test "blank lines and comments collapse into the newline that follows them"
    # Three lines of nothing between two statements must not become three
    # statements — the parser would then have to know what an empty statement
    # is, and it does not.
    got = scanned("print 1\n\n\n# a comment\n\nprint 2").must()
    newlines: i64 @= 0

    for one in got
        if one == .newline
            newlines @ newlines + 1

    assert newlines == 2
    assert got[0] == .kw_print
    assert got[3] == .kw_print

test "a comment runs to the end of its line and no further"
    got = scanned("print 1 # let x = 9\nprint 2").must()
    assert got.len() == 7
    assert got[0] == .kw_print
    assert got[1] == .number(value: 1)
    assert got[2] == .newline
    assert got[3] == .kw_print
    assert got[4] == .number(value: 2)

test "a two-byte operator is never read as the one it begins with"
    # `<=` read as `<` then `=` parses and means something else, which is the
    # one mistake in this module that a passing program would hide.
    got = scanned("a <= b >= c == d != e && f || g").must()
    assert got[1] == .less_equal
    assert got[3] == .greater_equal
    assert got[5] == .equal_equal
    assert got[7] == .bang_equal
    assert got[9] == .ampersands
    assert got[11] == .bars
    single = scanned("a < b > c = d ! e").must()
    assert single[1] == .less
    assert single[3] == .greater
    assert single[5] == .equals
    assert single[7] == .bang

test "a string keeps its spaces and decodes its four escapes"
    got = scanned("print \"a b\\tc\\nd\\\"e\\\\f\"").must()
    assert got[1] == .text(value: "a b\tc\nd\"e\\f")

test "the empty string is a token with nothing in it"
    got = scanned("print \"\"").must()
    assert got[1] == .text(value: "")

test "a name may hold digits and underscores but may not begin with a digit"
    got = scanned("total_2 _x").must()
    assert got[0] == .name(value: "total_2")
    assert got[1] == .name(value: "_x")
    mixed = scanned("2x").must()
    assert mixed[0] == .number(value: 2)
    assert mixed[1] == .name(value: "x")

test "the four refusals, each asserted by its code"
    assert refusal_of(scanned("print \"open")) == ERR_TEXT
    assert refusal_of(scanned("print \"line\nbreak\"")) == ERR_TEXT
    assert refusal_of(scanned("print \"\\q\"")) == ERR_ESCAPE
    assert refusal_of(scanned("print @")) == ERR_BYTE
    assert refusal_of(scanned("print 1")) == "nothing was refused"

test "a number too large is refused and does not abort the interpreter"
    # THE ROBUSTNESS CASE (design.md §1.12). Heroes aborts on overflow, so
    # without the guard in `number_at` these three lines would be a panic
    # rather than a diagnostic — and the input is a SCRIPT, which is the one
    # thing this program does not control.
    assert refusal_of(scanned("print 9223372036854775807")) == "nothing was refused"
    assert scanned("print 9223372036854775807").must()[1] == .number(value: MAX)
    assert refusal_of(scanned("print 9223372036854775808")) == ERR_NUMBER
    assert refusal_of(scanned("print 99999999999999999999")) == ERR_NUMBER
    assert refusal_of(scanned("print 123456789012345678901234567890")) == ERR_NUMBER

test "the source always ends in exactly one finish, whatever it held"
    sources = ["", " ", "\n", "# nothing\n", "print 1", "print 1\n", "print 1\n\n"]

    for source in sources
        got = scanned(source).must()
        finishes: i64 @= 0

        for one in got
            if one == .finish
                finishes @ finishes + 1

        assert finishes == 1
        assert got[got.len() - 1] == .finish

# What a token is, and nothing about how one is read.
#
# Part of `examples/interpreter/`, whose root `main.hero` carries the whole
# program's argument. This module is the vocabulary: `scan.hero` produces these
# and `syn/parse.hero` consumes them, and neither knows anything else about the
# other.
#
# WHY A VARIANT WITH PAYLOADS RATHER THAN A KIND AND A TEXT. A token that is a
# number carries an `i64`; one that is a name carries a `str`; one that is `+`
# carries nothing. Spelling that as `record Token { kind: Kind, text: str }`
# would give every token a `text` field that is empty for most of them and
# would move the question *is this number well formed* out of the scanner and
# into whoever reads it. The payload is where the answer belongs, and the
# `match` in `syn/parse.hero` is exhaustive or a compile error.

# One token of the little language this interpreter runs.
variant Token
    # A run of digits, already turned into a number.
    number
        value: i64
    # Text between double quotes, with its escapes already decoded.
    text
        value: str
    # A bare word that is not a keyword.
    name
        value: str
    # The keywords, one case each, so a `match` over them is exhaustive and a
    # new keyword cannot be forgotten by a reader.
    kw_let
    kw_print
    kw_if
    kw_else
    kw_while
    kw_fn
    kw_return
    kw_exit
    kw_end
    kw_true
    kw_false
    # The operators and the punctuation.
    plus
    minus
    star
    slash
    percent
    equals
    less
    less_equal
    greater
    greater_equal
    equal_equal
    bang_equal
    bang
    ampersands
    bars
    lparen
    rparen
    comma
    # One line's worth of newline, however many blank lines it stood for. The
    # language is line-oriented, so this is a token and not whitespace.
    newline
    # The end of the source, which the parser reads rather than testing an
    # index against a length.
    finish

# The keyword a word spells, or `.name` if it spells none. The scanner calls
# this once per word, so this list is the only place a keyword is written down.
function worded(word: str) -> Token
    if word == "let"
        return .kw_let

    if word == "print"
        return .kw_print

    if word == "if"
        return .kw_if

    if word == "else"
        return .kw_else

    if word == "while"
        return .kw_while

    if word == "fn"
        return .kw_fn

    if word == "return"
        return .kw_return

    if word == "exit"
        return .kw_exit

    if word == "end"
        return .kw_end

    if word == "true"
        return .kw_true

    if word == "false"
        return .kw_false

    return .name(value: word)

# How a token reads in a diagnostic. Every case has a spelling, including the
# two that have no text of their own, because a parse error that says
# `expected a name, found ` is a diagnostic with a hole in it.
function shown(t: Token) -> str
    return match t
        .number n      => n.value.to_str()
        .text x        => "\"" + x.value + "\""
        .name n        => n.value
        .kw_let        => "let"
        .kw_print      => "print"
        .kw_if         => "if"
        .kw_else       => "else"
        .kw_while      => "while"
        .kw_fn         => "fn"
        .kw_return     => "return"
        .kw_exit       => "exit"
        .kw_end        => "end"
        .kw_true       => "true"
        .kw_false      => "false"
        .plus          => "+"
        .minus         => "-"
        .star          => "*"
        .slash         => "/"
        .percent       => "%"
        .equals        => "="
        .less          => "<"
        .less_equal    => "<="
        .greater       => ">"
        .greater_equal => ">="
        .equal_equal   => "=="
        .bang_equal    => "!="
        .bang          => "!"
        .ampersands    => "&&"
        .bars          => "||"
        .lparen        => "("
        .rparen        => ")"
        .comma         => ","
        .newline       => "end of line"
        .finish        => "end of file"

# Whether this token can begin an expression — the one question the parser asks
# that is about the token alone, so it lives here beside the vocabulary.
# Every case is named, and the reason is the language: `_` as an arm over a
# `variant` is `error[wildcard_on_variant]` — *name every case, so that adding
# one breaks this `match` instead of silently falling through*. The first draft
# of this function wrote `_ => false` and the compiler refused it, which is the
# refusal doing its job: a thirty-fifth token added next month has to be
# classified here rather than defaulting to *cannot open a value*.
function opens_a_value(t: Token) -> bool
    return match t
        .number _ | .text _ | .name _ | .kw_true | .kw_false => true
        .minus | .bang | .lparen                             => true
        .kw_let | .kw_print | .kw_if | .kw_else | .kw_while  => false
        .kw_fn | .kw_return | .kw_exit | .kw_end             => false
        .plus | .star | .slash | .percent | .equals          => false
        .less | .less_equal | .greater | .greater_equal      => false
        .equal_equal | .bang_equal | .ampersands | .bars     => false
        .rparen | .comma | .newline | .finish                => false

test "a keyword is a keyword and a word that only looks like one is not"
    assert worded("let") == .kw_let
    assert worded("end") == .kw_end
    assert worded("letter") == .name(value: "letter")
    assert worded("ending") == .name(value: "ending")
    assert worded("iff") == .name(value: "iff")
    assert worded("") == .name(value: "")

test "every keyword this module knows round-trips through its own spelling"
    # The list is written twice on purpose — once in `worded` and once here —
    # because the second copy is what notices a keyword whose spelling and
    # whose case have drifted apart.
    words = ["let", "print", "if", "else", "while", "fn", "return", "exit", "end", "true", "false"]

    for word in words
        assert shown(worded(word)) == word
        assert worded(word) != .name(value: word)

test "a token that carries a payload shows the payload"
    assert shown(.number(value: 42)) == "42"
    assert shown(.number(value: 0 - 7)) == "-7"
    assert shown(.text(value: "hi")) == "\"hi\""
    assert shown(.name(value: "total")) == "total"

test "the two tokens with no text of their own still have a spelling"
    # A parse error naming `.newline` or `.finish` has to say something, and
    # what it says is checked here rather than discovered in a message.
    assert shown(.newline) == "end of line"
    assert shown(.finish) == "end of file"

test "what can open a value, and what cannot"
    assert opens_a_value(.number(value: 1))
    assert opens_a_value(.name(value: "x"))
    assert opens_a_value(.text(value: "s"))
    assert opens_a_value(.kw_true)
    assert opens_a_value(.minus)
    assert opens_a_value(.bang)
    assert opens_a_value(.lparen)
    assert !opens_a_value(.plus)
    assert !opens_a_value(.rparen)
    assert !opens_a_value(.kw_end)
    assert !opens_a_value(.newline)
    assert !opens_a_value(.finish)

test "two tokens are equal when their payloads are"
    # Structural equality over a variant, which the compiler generates by
    # walking fields (CLAUDE.md §7) — the parser leans on it for every
    # `expect`, so it is asserted rather than assumed.
    #
    # The annotations are not decoration: `.number(value: 3) == .number(value:
    # 3)` is `error[cannot_infer]`, because neither side of the `==` says which
    # variant `.number` belongs to. A case literal takes its type from the
    # context, and two case literals give each other none.
    three: Token = .number(value: 3)
    four: Token = .number(value: 4)
    letter_a: Token = .name(value: "a")
    text_a: Token = .text(value: "a")
    assert three == .number(value: 3)
    assert three != four
    assert letter_a != text_a
    assert worded("if") != worded("else")
    assert shown(three) == "3"

# What a statement does, and the door an expression uses to call a function.
#
# Part of `examples/interpreter/` — the root `main.hero` carries the program's
# argument. This module is the top of the runtime: it walks statements, and
# hands `run/expr.hero` its own `called` so that an expression holding a call
# can run a body without this module and that one importing each other (see
# that file's header for why the language forbids the cycle).
#
# WHERE THE GENERICS CROSS A `use` FOR THE SECOND TIME. `util/each.hero`'s
# templates are instantiated at `str` in `syn/parse.hero` and at
# `run/value.hero`'s `Value` here — `each.joined` renders the arguments a
# mismatched call was given. Two callers in two directories, two layouts, one
# template.
#
# WHAT A SCRIPT FUNCTION CAN SEE, decided rather than inherited: its
# parameters, and nothing else. No closures, no globals, no enclosing scope —
# so `called` builds a fresh variable map holding only the arguments, and puts
# the caller's map back afterwards. The alternative (a chain of scopes) is a
# bigger program and it would teach the corpus nothing it does not already
# carry; this one keeps the rule a reader can state in one line.
#
# THE RECURSION GUARD IS ROBUSTNESS AND NOT A LIMIT (design.md §1.12). A script
# that calls itself for ever would run this interpreter's own `body` for ever,
# and the answer to that in a compiled language is a stack overflow — which
# the runtime now catches and names (panel 104), but which is still a crash
# from the script's point of view. `DEPTH` refuses first, with the name of the
# function and the depth, which is a message a script author can act on.

use run/expr
use run/value
use syn/tree
use util/each

constant ERR_NAME: str
    "unknown_name"

constant ERR_ARITY: str
    "arity"

constant ERR_DEPTH: str
    "too_deep"

# How many nested script calls are allowed — and this number is MEASURED,
# not chosen. The first draft said 200 on the reasoning that a runaway
# recursion should stop "long before the machine's stack does", and 200 is
# past the machine's stack: a script recursing 150 deep exited **139 in
# silence** before the guard was ever consulted.
#
# **Re-measured, after panel 106's repair, and it moved.** The
# exit sweep stopped minting a load temporary per swept slot per returning
# block — 58.5% of every declared frame — so one script call costs a good
# deal less than it did. Nested script calls, one ceiling per configuration,
# binary-searched on this Mac with the guard lifted out of the way:
#
#                  before   after
#   --sanitize        40      76   (exit 134, ASan names it)
#   -O0               50     107
#   -O2               80     239
#
# One script call still costs about nine Heroes frames (`body` → `one` →
# `given_back` → `expr.evaluated` → `applied` → the function value →
# `called` → `entered` → `body`); each of those frames is now roughly half
# the size. So the guard moves 24 → **38**: under half of the tightest
# measured ceiling, which is margin enough for a machine with a smaller
# stack, and far above anything a script here needs
# (`scripts/tour.script`'s deepest is `factorial(10)`, ten frames).
#
# A GUARD ABOVE THE REAL CEILING IS NOT A GUARD. That is the whole lesson of
# this constant, and it was learned by running rather than by reasoning —
# twice now, because the ceiling moved and the guard had to be re-measured
# rather than left where a comment said it belonged.
constant DEPTH: i64
    38

# A whole program: every top-level statement in order, on a fresh frame.
function run(nodes: tree.Tree) -> value.Frame?
    return body(nodes: nodes, ids: nodes.top, f: value.fresh())

# A list of statements, stopping early the moment a `return` or an `exit` is in
# flight — which is the whole of this language's non-local control flow.
function body(nodes: tree.Tree, ids: [i64], f: value.Frame) -> value.Frame?
    walking: value.Frame @= f

    for id in ids
        if walking.returned || walking.stopping
            return ok(walking)
        walking @ one(nodes: nodes, id: id, f: walking)?

    return ok(walking)

function one(nodes: tree.Tree, id: i64, f: value.Frame) -> value.Frame?
    return match nodes.stmts[id]
        .bind b       => bound(nodes: nodes, name: b.name, at: b.value, f: f)
        .say s        => said(nodes: nodes, at: s.value, f: f)
        .when w       => chosen(nodes: nodes, at: w.condition, then: w.then, otherwise: w.otherwise, f: f)
        .while_loop w => looped(nodes: nodes, at: w.condition, inside: w.body, f: f)
        .give g       => given_back(nodes: nodes, at: g.value, f: f)
        .stop s       => stopped(nodes: nodes, at: s.code, f: f)
        .define d     => ok(with_function(f: f, name: d.name, at: id))
        .evaluate e   => spent(nodes: nodes, at: e.value, f: f)

function bound(nodes: tree.Tree, name: str, at: i64, f: value.Frame) -> value.Frame?
    step = expr.evaluated(nodes, at, f, called)?
    home: value.Frame @= step.frame
    home.vars[name] @ step.got
    return ok(home)

function said(nodes: tree.Tree, at: i64, f: value.Frame) -> value.Frame?
    step = expr.evaluated(nodes, at, f, called)?
    home: value.Frame @= step.frame
    home.lines @ home.lines.push(value.shown(step.got))
    return ok(home)

function chosen(nodes: tree.Tree, at: i64, then: [i64], otherwise: [i64], f: value.Frame) -> value.Frame?
    step = expr.evaluated(nodes, at, f, called)?

    if value.condition_of(step.got)?
        return body(nodes: nodes, ids: then, f: step.frame)

    return body(nodes: nodes, ids: otherwise, f: step.frame)

function looped(nodes: tree.Tree, at: i64, inside: [i64], f: value.Frame) -> value.Frame?
    walking: value.Frame @= f

    while true
        step = expr.evaluated(nodes, at, walking, called)?
        walking @ step.frame

        if !value.condition_of(step.got)?
            return ok(walking)
        walking @ body(nodes: nodes, ids: inside, f: walking)?

        if walking.returned || walking.stopping
            return ok(walking)

    return ok(walking)

function given_back(nodes: tree.Tree, at: i64, f: value.Frame) -> value.Frame?
    step = expr.evaluated(nodes, at, f, called)?
    home: value.Frame @= step.frame
    home.returned @ true
    home.result @ step.got
    return ok(home)

function stopped(nodes: tree.Tree, at: i64, f: value.Frame) -> value.Frame?
    step = expr.evaluated(nodes, at, f, called)?
    home: value.Frame @= step.frame
    home.stopping @ true
    home.code @ value.number_of(step.got)?
    return ok(home)

# A bare expression as a statement — a call written for what it prints. The
# value is thrown away on purpose, which is the one place this interpreter does
# what `_ =` does in Heroes.
function spent(nodes: tree.Tree, at: i64, f: value.Frame) -> value.Frame?
    step = expr.evaluated(nodes, at, f, called)?
    return ok(step.frame)

function with_function(f: value.Frame, name: str, at: i64) -> value.Frame
    home: value.Frame @= f
    home.fns[name] @ at
    return home

# THE DOOR. This is the function value `run/expr.hero` is handed, and its type
# is `(function(value.Request) -> value.Frame?)` — one parameter wide because
# `Request` packs the four things a call needs.
function called(r: value.Request) -> value.Frame?
    where = r.frame.fns[r.name]

    if where.is_err()
        return fail(code: ERR_NAME, msg: "no function is named `" + r.name + "`")

    if r.frame.depth >= DEPTH
        return fail(
            code: ERR_DEPTH,
            msg: "`" + r.name + "` is " + DEPTH.to_str() + " calls deep — a script that recurses without an end stops here rather than in the machine's stack"
        )

    return match r.nodes.stmts[where.must()]
        .define d                                  => entered(r: r, params: d.params, inside: d.body)
        .bind _ | .say _ | .when _ | .while_loop _ => not_a_function(r: r)
        .give _ | .stop _ | .evaluate _            => not_a_function(r: r)

function not_a_function(r: value.Request) -> value.Frame?
    return fail(code: ERR_NAME, msg: "`" + r.name + "` names something that is not a function")

# One call: bind the arguments, run the body on a frame that can see nothing
# else, then put the caller's variables back and carry the result home.
function entered(r: value.Request, params: [str], inside: [i64]) -> value.Frame?
    if params.len() != r.given.len()
        return fail(
            code: ERR_ARITY,
            msg: "`" + r.name + "` takes " + params.len().to_str() + " and was given " + r.given.len().to_str() + ": (" + each.joined(r.given, value.shown, ", ") + ")"
        )
    inner: value.Frame @= r.frame
    fresh_vars: {str: value.Value} @= {}
    i: i64 @= 0

    while i < params.len()
        fresh_vars[params[i]] @ r.given[i]
        i @ i + 1

    inner.vars @ fresh_vars
    inner.depth @ r.frame.depth + 1
    after = body(nodes: r.nodes, ids: inside, f: inner)?
    home: value.Frame @= after
    home.vars @ r.frame.vars
    home.depth @ r.frame.depth
    return ok(home)

# What an expression means — and the four ways arithmetic can stop a program
# that this module refuses instead of suffering.
#
# Part of `examples/interpreter/` — the root `main.hero` carries the program's
# argument. **This module's name collides with `syn/expr.hero`** and the header
# there explains why the collision is the honest one: that file reads an
# expression, this one gives it a meaning.
#
# HOW THIS MODULE CALLS A FUNCTION WITHOUT KNOWING HOW TO RUN A BODY. A script
# function's body is statements, and statements are `run/eval.hero`'s job — but
# an expression can hold a call, so the two need each other. Heroes refuses a
# module cycle (`error[module_cycle]`, on the `use` edge whatever it carries),
# so the loop is broken with a **function value**: `evaluated` takes
# `(function(value.Request) -> value.Frame?)` and `run/eval.hero` hands it its
# own `called`. The recursion is real and it crosses a `use` in one direction
# only, which is the shape a language without module cycles forces and the
# reason the corpus wanted a program this size.
#
# THE FOUR REFUSALS, and every one of them is Heroes aborting if it is not
# caught here (design.md §1.12, CLAUDE.md §12 — robustness beats every other
# criterion):
#
#   - division by zero, which the spec says aborts;
#   - `%` by zero, guarded like `/` for the same reason;
#   - `+`, `-` and `*` overflowing, which aborts at every width;
#   - `INT64_MIN / -1`, which is the one division that overflows.
#
# A script is INPUT. A program that a line of its input can kill is a program
# with a hole in it, so each of these is a named refusal with a message, and
# the tests at the bottom feed the extremes to prove it.

use run/value
use syn/tree

constant ERR_NAME: str
    "unknown_name"

constant ERR_MATH: str
    "arithmetic"

constant ERR_TYPE: str
    "type"

constant MAX: i64
    9223372036854775807

constant MIN: i64
    0 - 9223372036854775807 - 1

# A value, and the frame the evaluation left behind — a call can define nothing
# but it can print, so the frame comes back even from an expression.
record Answer
    frame: value.Frame
    got: value.Value

# One expression. `call` is `run/eval.hero`'s door: see the module header.
function evaluated(nodes: tree.Tree, id: i64, f: value.Frame, call: (function(value.Request) -> value.Frame?)) -> Answer?
    return match nodes.exprs[id]
        .number n => ok(Answer(frame: f, got: .number(v: n.value)))
        .text x   => ok(Answer(frame: f, got: .text(s: x.value)))
        .truth b  => ok(Answer(frame: f, got: .truth(b: b.value)))
        .name n   => looked_up(f: f, word: n.value)
        .negate u => negated(nodes: nodes, id: u.on, f: f, call: call)
        .invert u => inverted(nodes: nodes, id: u.on, f: f, call: call)
        .binary b => joined(nodes: nodes, op: b.op, left: b.left, right: b.right, f: f, call: call)
        .call c   => applied(nodes: nodes, name: c.name, ids: c.args, f: f, call: call)

function looked_up(f: value.Frame, word: str) -> Answer?
    held = f.vars[word]

    if held.is_err()
        return fail(code: ERR_NAME, msg: "`" + word + "` has no value — nothing has been let to that name")

    return ok(Answer(frame: f, got: held.must()))

function negated(nodes: tree.Tree, id: i64, f: value.Frame, call: (function(value.Request) -> value.Frame?)) -> Answer?
    inner = evaluated(nodes, id, f, call)?
    n = value.number_of(inner.got)?

    if n == MIN
        return fail(code: ERR_MATH, msg: "negating the smallest number has no answer that fits")

    return ok(Answer(frame: inner.frame, got: .number(v: 0 - n)))

function inverted(nodes: tree.Tree, id: i64, f: value.Frame, call: (function(value.Request) -> value.Frame?)) -> Answer?
    inner = evaluated(nodes, id, f, call)?
    return ok(Answer(frame: inner.frame, got: .truth(b: !value.condition_of(inner.got)?)))

# Two sides, or one where the operator short-circuits. `&&` and `||` do not
# evaluate their right side when the left decides the answer, which is the
# rule Heroes keeps for its own (spec § Operators) and the reason they cannot
# go through the same path as `+`.
function joined(nodes: tree.Tree, op: tree.Op, left: i64, right: i64, f: value.Frame, call: (function(value.Request) -> value.Frame?)) -> Answer?
    first = evaluated(nodes, left, f, call)?

    if op == .both
        if !value.condition_of(first.got)?
            return ok(Answer(frame: first.frame, got: .truth(b: false)))
        second = evaluated(nodes, right, first.frame, call)?
        return ok(Answer(frame: second.frame, got: .truth(b: value.condition_of(second.got)?)))

    if op == .either
        if value.condition_of(first.got)?
            return ok(Answer(frame: first.frame, got: .truth(b: true)))
        second = evaluated(nodes, right, first.frame, call)?
        return ok(Answer(frame: second.frame, got: .truth(b: value.condition_of(second.got)?)))
    second = evaluated(nodes, right, first.frame, call)?
    got = combined(op: op, a: first.got, b: second.got)?
    return ok(Answer(frame: second.frame, got: got))

# The operators that want both sides. Kept apart from `joined` so that the
# arithmetic can be tested without a frame, which is what the extremes at the
# bottom of this file do.
function combined(op: tree.Op, a: value.Value, b: value.Value) -> value.Value?
    if op == .add
        if is_text(a) || is_text(b)
            return ok(.text(s: value.text_of(a)? + value.text_of(b)?))

        return ok(.number(v: plus(a: value.number_of(a)?, b: value.number_of(b)?)?))

    if op == .subtract
        return ok(.number(v: minus(a: value.number_of(a)?, b: value.number_of(b)?)?))

    if op == .multiply
        return ok(.number(v: times(a: value.number_of(a)?, b: value.number_of(b)?)?))

    if op == .divide
        return ok(.number(v: over(a: value.number_of(a)?, b: value.number_of(b)?)?))

    if op == .remainder
        return ok(.number(v: rest(a: value.number_of(a)?, b: value.number_of(b)?)?))

    if op == .equal
        return ok(.truth(b: a == b))

    if op == .unequal
        return ok(.truth(b: a != b))

    return ordered(op: op, a: value.number_of(a)?, b: value.number_of(b)?)

function ordered(op: tree.Op, a: i64, b: i64) -> value.Value?
    if op == .less
        return ok(.truth(b: a < b))

    if op == .less_equal
        return ok(.truth(b: a <= b))

    if op == .greater
        return ok(.truth(b: a > b))

    if op == .greater_equal
        return ok(.truth(b: a >= b))

    return fail(code: ERR_TYPE, msg: "`" + tree.shown_op(op) + "` does not take two values here")

function is_text(v: value.Value) -> bool
    return match v
        .text _   => true
        .number _ => false
        .truth _  => false
        .nothing  => false

# `a + b`, refusing rather than aborting. The test is written as a subtraction
# against the limit because computing the sum is the overflow.
function plus(a: i64, b: i64) -> i64?
    if b > 0 && a > MAX - b
        return too_big(a: a, b: b, op: "+")

    if b < 0 && a < MIN - b
        return too_big(a: a, b: b, op: "+")

    return ok(a + b)

function minus(a: i64, b: i64) -> i64?
    if b < 0 && a > MAX + b
        return too_big(a: a, b: b, op: "-")

    if b > 0 && a < MIN + b
        return too_big(a: a, b: b, op: "-")

    return ok(a - b)

# `a * b`, refusing rather than aborting.
#
# The smallest number is handled first and on its own, because the usual trick
# — compare the magnitudes against `MAX / |b|` — needs to negate, and negating
# the smallest number is itself the overflow. What is left after that gate has
# a safe magnitude, so one division answers the question.
#
# ONE DELIBERATE CONSERVATISM, stated rather than hidden: the bound is `MAX`,
# and the true range of a product reaches `MIN`, whose magnitude is one larger.
# So a script that multiplies its way to exactly the smallest number gets a
# refusal instead of an answer. Refusing a value that fits is a smaller wrong
# than aborting, and the alternative is a second bound for the mixed-sign case
# that nothing in this program needs.
function times(a: i64, b: i64) -> i64?
    if a == 0 || b == 0
        return ok(0)

    if a == 1
        return ok(b)

    if b == 1
        return ok(a)

    if a == MIN || b == MIN
        return too_big(a: a, b: b, op: "*")
    am = size_of(a)
    bm = size_of(b)

    if am > MAX / bm
        return too_big(a: a, b: b, op: "*")

    return ok(a * b)

# `|n|`, for an `n` that is not the smallest number — the caller has already
# refused that one, and this function says so rather than guessing.
function size_of(n: i64) -> i64
    if n < 0
        return 0 - n

    return n

function over(a: i64, b: i64) -> i64?
    if b == 0
        return fail(code: ERR_MATH, msg: "dividing " + a.to_str() + " by zero has no answer")

    # The one division that overflows: the smallest number by -1. Heroes aborts
    # on it and the spec says so, so it is a refusal here.
    if a == MIN && b == 0 - 1
        return too_big(a: a, b: b, op: "/")

    return ok(a / b)

function rest(a: i64, b: i64) -> i64?
    if b == 0
        return fail(code: ERR_MATH, msg: "the remainder of " + a.to_str() + " by zero has no answer")

    if a == MIN && b == 0 - 1
        return too_big(a: a, b: b, op: "%")

    return ok(a % b)

function too_big(a: i64, b: i64, op: str) -> i64?
    return fail(
        code: ERR_MATH,
        msg: a.to_str() + " " + op + " " + b.to_str() + " does not fit in a 64-bit number"
    )

# A call: the arguments first, left to right, then the door into
# `run/eval.hero`.
function applied(nodes: tree.Tree, name: str, ids: [i64], f: value.Frame, call: (function(value.Request) -> value.Frame?)) -> Answer?
    walking: value.Frame @= f
    given: [value.Value] @= []

    for id in ids
        step = evaluated(nodes, id, walking, call)?
        walking @ step.frame
        given @ given.push(step.got)

    after = call(value.Request(nodes: nodes, name: name, given: given, frame: walking))?
    result = after.result
    home: value.Frame @= after
    home.returned @ false
    home.result @ .nothing
    return ok(Answer(frame: home, got: result))

# What a value is while the little language runs, and the state one run
# carries.
#
# Part of `examples/interpreter/` — the root `main.hero` carries the program's
# argument. `run/expr.hero` and `run/eval.hero` both read this and neither
# declares a value of its own.
#
# WHY THE STATE IS A VALUE AND NOT A THING BEING MUTATED. `Frame` is passed in
# and handed back rather than taken as an `@` parameter, and that is not a
# style choice: it is what makes the recursion between `run/eval.hero` and
# `run/expr.hero` expressible at all. Those two need each other — a statement
# holds expressions, and an expression can call a function whose body is
# statements — and Heroes refuses a module cycle, so one of them has to take
# the other as a **function value**. A function type in this language cannot
# carry an `@` parameter (`error[expected_type]: expected a type, found `@``,
# measured), so the state crosses that boundary by value or not at
# all. Copy-on-write is what makes it cheap: handing a `Frame` down costs a
# refcount until something writes to it.
#
# WHAT A FRAME HOLDS, and why each field is here rather than in a global:
# there are no mutable globals in Heroes (spec § Top-level declarations), so
# *everything* a running program accumulates is in this record — the variables,
# the output written so far, the functions the script has defined, whether a
# `return` or an `exit` is in flight, and how deep the calls are nested.

use syn/tree

constant ERR_TYPE: str
    "type"

# One value the script can hold. Four cases and no more: the little language
# has no arrays and no records, which keeps this program about the shape of an
# interpreter rather than about the size of a standard library.
variant Value
    number
        v: i64
    text
        s: str
    truth
        b: bool
    # What a call with no `return` gives back, and what `print` of nothing
    # would be. It is a value rather than an absence so that every path in the
    # evaluator produces one.
    nothing

# Everything one run accumulates.
record Frame
    vars: {str: Value}
    lines: [str]
    # A script function's name to the index of its `define` statement. The
    # body is in the tree; this is only the door.
    fns: {str: i64}
    returned: bool
    result: Value
    stopping: bool
    code: i64
    depth: i64

function fresh() -> Frame
    vars: {str: Value} = {}
    fns: {str: i64} = {}
    no_lines: [str] = []
    return Frame(
        vars: vars,
        lines: no_lines,
        fns: fns,
        returned: false,
        result: .nothing,
        stopping: false,
        code: 0,
        depth: 0
    )

# What `run/expr.hero` hands to the function value that runs a call — the four
# things a call needs, packed so that the function TYPE stays one parameter
# wide and a reader can hold it in their head:
#
#     (function(Request) -> Frame?)
#
# The alternative is a four-parameter function type written out at every
# signature that passes it on, which is the same information spelled three
# times.
record Request
    nodes: tree.Tree
    name: str
    given: [Value]
    frame: Frame

# How a value prints. This is what `print` writes and what an error message
# quotes, so it is one function and not two.
function shown(v: Value) -> str
    return match v
        .number n => n.v.to_str()
        .text x   => x.s
        .truth t  => t.b.to_str()
        .nothing  => "nothing"

# The name of a value's kind, for a message that has to say what it got.
function kind_of(v: Value) -> str
    return match v
        .number _ => "a number"
        .text _   => "a string"
        .truth _  => "a boolean"
        .nothing  => "nothing"

# A condition must BE a boolean — there is no truthiness, which is the rule
# Heroes itself keeps (spec § Control flow: *`if cond` takes only `bool`*), and
# the little language keeps it for the same reason: `if 0` reads differently to
# different people.
function condition_of(v: Value) -> bool?
    return match v
        .truth t  => ok(t.b)
        .number _ => not_a_condition(v)
        .text _   => not_a_condition(v)
        .nothing  => not_a_condition(v)

function not_a_condition(v: Value) -> bool?
    return fail(
        code: ERR_TYPE,
        msg: "a condition must be `true` or `false`, and this one is " + kind_of(v) + " (`" + shown(v) + "`)"
    )

# The number in a value, or a refusal naming what stood there.
function number_of(v: Value) -> i64?
    return match v
        .number n => ok(n.v)
        .text _   => wanted(what: "a number", v: v)
        .truth _  => wanted(what: "a number", v: v)
        .nothing  => wanted(what: "a number", v: v)

function text_of(v: Value) -> str?
    return match v
        .text x   => ok(x.s)
        .number _ => wanted(what: "a string", v: v)
        .truth _  => wanted(what: "a string", v: v)
        .nothing  => wanted(what: "a string", v: v)

# The one refusal `number_of` and `text_of` hand back, written ONCE: `A`
# appears only in the result, and each caller's declared result says what it
# is — `i64?` in `number_of`, `str?` in `text_of`. **This is the function that
# found a compiler defect**: written exactly like this, `heroes
# check` accepted it at exit 0 and `heroes build` died at exit 134 with a bare
# `assert failed: false`, because inference read the arguments only and left
# `A` as a silent error type all the way to the emitter. It was rewritten as two
# concrete functions for a few hours (defect 006), and it is one generic
# again because panel 105 ruled, the same evening, that a type parameter the
# arguments leave unbound takes the type the context asks for — the rule `fail`,
# `[]` and `nullptr` already followed. A call with no context, `x = wanted(...)`,
# is refused at the call.
function wanted<A>(what: str, v: Value) -> A?
    return fail(code: ERR_TYPE, msg: "expected " + what + ", found " + kind_of(v) + " (`" + shown(v) + "`)")

test "every value prints, including the one that is nothing"
    assert shown(.number(v: 42)) == "42"
    assert shown(.number(v: 0 - 1)) == "-1"
    assert shown(.text(s: "hi")) == "hi"
    assert shown(.text(s: "")) == ""
    assert shown(.truth(b: true)) == "true"
    assert shown(.truth(b: false)) == "false"
    assert shown(.nothing) == "nothing"

test "every kind has a name a message can use"
    assert kind_of(.number(v: 1)) == "a number"
    assert kind_of(.text(s: "x")) == "a string"
    assert kind_of(.truth(b: true)) == "a boolean"
    assert kind_of(.nothing) == "nothing"

test "a condition is a boolean and nothing else is one"
    assert condition_of(.truth(b: true)).must()
    assert !condition_of(.truth(b: false)).must()
    assert condition_of(.number(v: 1)).is_err()
    assert condition_of(.number(v: 0)).is_err()
    assert condition_of(.text(s: "yes")).is_err()
    assert condition_of(.nothing).is_err()

test "the refusal says what it wanted and what it found"
    said = condition_of(.number(v: 0))
    assert said.is_err()
    assert message_of_bool(said) == "a condition must be `true` or `false`, and this one is a number (`0`)"

test "a number is taken out of a number and refused out of everything else"
    assert number_of(.number(v: 7)).must() == 7
    assert number_of(.text(s: "7")).is_err()
    assert number_of(.truth(b: true)).is_err()
    assert number_of(.nothing).is_err()
    assert text_of(.text(s: "a")).must() == "a"
    assert text_of(.number(v: 1)).is_err()

test "a fresh frame holds nothing and is not going anywhere"
    f = fresh()
    assert len(f.vars) == 0
    assert len(f.fns) == 0
    assert f.lines.len() == 0
    assert !f.returned
    assert !f.stopping
    assert f.code == 0
    assert f.depth == 0
    assert f.result == .nothing

function message_of_bool(said: bool?) -> str
    return match said
        .ok _  => "nothing was refused"
        .err e => e.msg

# A place in a token list, and the four questions a parser asks of one.
#
# Part of `examples/interpreter/` — the root `main.hero` carries the program's
# argument. `syn/expr.hero` and `syn/parse.hero` both hold one of these and
# nothing else in the program knows what a token index is.
#
# WHY THIS IS ITS OWN MODULE. Everything here is four lines long and the
# temptation is to inline it into the parser, which is how a parser ends up
# with `c.at @ c.at + 1` written twenty times and one of them wrong. The
# interesting part is `expected`: it is the only function in the program that
# turns *the parser wanted something else* into a sentence a reader can act on,
# so it is written once, and the sentence names both what was wanted and what
# stood there (design.md §4.17 is the compiler's own rule for this and it is
# the right rule for a script too).
#
# THE CURSOR NEVER RUNS OFF THE END, and that is a property of the SCANNER
# rather than a check here: `lex/scan.hero` always ends its output with exactly
# one `.finish`, asserted by its own last test, so `here` on the last index
# returns `.finish` forever and no parser loop can index past the array. A
# guard here would be a second answer to a question already answered, and the
# comment is what stops somebody adding one.

use lex/token

constant ERR_PARSE: str
    "parse"

record Cursor
    tokens: [token.Token]
    at: i64

function over(tokens: [token.Token]) -> Cursor
    return Cursor(tokens: tokens, at: 0)

# The token the cursor stands on. `.finish` once the list is spent, because the
# scanner guarantees a `.finish` and never more than one.
function here(c: Cursor) -> token.Token
    if c.at >= c.tokens.len()
        return .finish

    return c.tokens[c.at]

# The token after this one, for the two places the grammar needs to look ahead:
# telling `name = value` from `name(args)`.
function after(c: Cursor) -> token.Token
    if c.at + 1 >= c.tokens.len()
        return .finish

    return c.tokens[c.at + 1]

# Take the token the cursor stands on and step past it.
function bump(@c: Cursor) -> token.Token
    taken = here(c)

    if c.at < c.tokens.len()
        c.at @ c.at + 1

    return taken

# Step past the token if it is the one wanted, and say whether it was.
function accepted(@c: Cursor, want: token.Token) -> bool
    if here(c) == want
        _ = bump(@c)
        return true

    return false

# Step past the token wanted, or refuse naming both sides.
function expected(@c: Cursor, want: token.Token) -> ()?
    if accepted(@c, want: want)
        return ok()

    return fail(
        code: ERR_PARSE,
        msg: "expected `" + token.shown(want) + "`, found `" + token.shown(here(c)) + "`"
    )

# A name, or a refusal saying what stood there instead.
function name_here(@c: Cursor) -> str?
    return match bump(@c)
        .number n => fail(code: ERR_PARSE, msg: "expected a name, found the number `" + n.value.to_str() + "`")
        .text x => fail(code: ERR_PARSE, msg: "expected a name, found the string `" + x.value + "`")
        .name n => ok(n.value)
        .kw_let | .kw_print | .kw_if | .kw_else | .kw_while => keyword_taken(t: .kw_let, said: "a keyword")
        .kw_fn | .kw_return | .kw_exit | .kw_end => keyword_taken(t: .kw_fn, said: "a keyword")
        .kw_true | .kw_false => keyword_taken(t: .kw_true, said: "a keyword")
        .plus | .minus | .star | .slash | .percent => keyword_taken(t: .plus, said: "an operator")
        .equals | .less | .less_equal | .greater | .greater_equal => keyword_taken(t: .equals, said: "an operator")
        .equal_equal | .bang_equal | .bang | .ampersands | .bars => keyword_taken(t: .bang, said: "an operator")
        .lparen | .rparen | .comma => keyword_taken(t: .lparen, said: "punctuation")
        .newline => fail(code: ERR_PARSE, msg: "expected a name, found the end of the line")
        .finish => fail(code: ERR_PARSE, msg: "expected a name, found the end of the file")

# The refusal `name_here`'s keyword and operator arms share. Grouping the arms
# with `|` costs the exact token — the arms would each have to name it — so the
# message says the CLASS, which is what a reader needs: *a keyword cannot be a
# name* is the whole diagnosis.
function keyword_taken(t: token.Token, said: str) -> str?
    _ = t
    return fail(code: ERR_PARSE, msg: "expected a name, found " + said)

# Step past however many line ends stand here. A block may hold blank lines and
# the parser should not have to know.
function skipped_lines(@c: Cursor)
    while here(c) == .newline
        _ = bump(@c)

# Whether the cursor is spent.
function done(c: Cursor) -> bool
    return here(c) == .finish

test "a cursor walks the list and then stands on the end for ever"
    c: Cursor @= over([.kw_print, .number(value: 1), .newline, .finish])
    assert here(c) == .kw_print
    assert after(c) == .number(value: 1)
    assert bump(@c) == .kw_print
    assert bump(@c) == .number(value: 1)
    assert bump(@c) == .newline
    assert here(c) == .finish
    assert bump(@c) == .finish
    assert bump(@c) == .finish
    assert done(c)

test "the cursor on an empty list is done, and reading it is safe"
    empty: [token.Token] = []
    c: Cursor @= over(empty)
    assert done(c)
    assert here(c) == .finish
    assert after(c) == .finish
    assert bump(@c) == .finish

test "accepted steps only when it matches"
    c: Cursor @= over([.kw_if, .newline, .finish])
    assert !accepted(@c, want: .kw_while)
    assert here(c) == .kw_if
    assert accepted(@c, want: .kw_if)
    assert here(c) == .newline

test "expected names both sides when it refuses"
    c: Cursor @= over([.kw_if, .finish])
    assert !expected(@c, want: .kw_if).is_err()
    said = expected(@c, want: .kw_end)
    assert said.is_err()
    assert refusal_message(said) == "expected `end`, found `end of file`"

test "a name is taken, and everything that is not one is refused by class"
    c: Cursor @= over([.name(value: "total"), .number(value: 3), .kw_let, .plus, .newline, .finish])
    assert name_here(@c).must() == "total"
    assert refusal_message_of_name(name_here(@c)) == "expected a name, found the number `3`"
    assert refusal_message_of_name(name_here(@c)) == "expected a name, found a keyword"
    assert refusal_message_of_name(name_here(@c)) == "expected a name, found an operator"
    assert refusal_message_of_name(name_here(@c)) == "expected a name, found the end of the line"
    assert refusal_message_of_name(name_here(@c)) == "expected a name, found the end of the file"

test "blank lines are stepped over together"
    c: Cursor @= over([.newline, .newline, .newline, .kw_print, .finish])
    skipped_lines(@c)
    assert here(c) == .kw_print

    # And on something that is not a line end it does nothing at all.
    skipped_lines(@c)
    assert here(c) == .kw_print

function refusal_message(said: ()?) -> str
    return match said
        .ok _  => "nothing was refused"
        .err e => e.msg

function refusal_message_of_name(said: str?) -> str
    return match said
        .ok _  => "nothing was refused"
        .err e => e.msg

# Tokens into an expression tree, by climbing one precedence level per
# function.
#
# Part of `examples/interpreter/` — the root `main.hero` carries the program's
# argument. **This module's name collides with `run/expr.hero` on purpose**,
# and the collision is the honest one a front end has: this file is *how an
# expression is read*, that one is *what an expression means*, and they are two
# jobs with one noun. A module that needs both must rename one at its `use`
# line, which is `use syn/expr as parse_expr` in `main.hero` — the language
# refuses two bindings of one name in a file (spec § Files and layout) and
# `examples/pipeline/` is the corpus's other program that cannot be written
# without `as`.
#
# WHY ONE FUNCTION PER LEVEL, and not a table of precedences. Seven small
# functions that each call the next are longer than one loop over a table, and
# they are what a reader can check against the grammar line by line: `summed`
# calls `scaled` and never the other way, so `2 + 3 * 4` cannot come out
# wrong without one of these seven reading wrong. The table version is the same
# program with the shape hidden in data, and the shape is the thing worth
# reading. `examples/calculator/` is the corpus's other recursive-descent
# parser and it is written the same way, one level per function.
#
# THE LEVELS, weakest binding first — the same order as the spec's own table
# for Heroes, minus the bitwise row this little language does not have:
#
#     ||   &&   comparison   + -   * / %   unary - !   call and literal

use lex/token
use syn/cursor
use syn/tree

constant ERR_PARSE: str
    "parse"

# One expression, however deep. The entry point every caller uses.
function parsed(@c: cursor.Cursor, @t: tree.Tree) -> i64?
    return either(@c, @t)

function either(@c: cursor.Cursor, @t: tree.Tree) -> i64?
    left: i64 @= both(@c, @t)?

    while cursor.here(c) == .bars
        _ = cursor.bump(@c)
        right = both(@c, @t)?
        left @ tree.added_expr(@t, .binary(op: .either, left: left, right: right))

    return ok(left)

function both(@c: cursor.Cursor, @t: tree.Tree) -> i64?
    left: i64 @= compared(@c, @t)?

    while cursor.here(c) == .ampersands
        _ = cursor.bump(@c)
        right = compared(@c, @t)?
        left @ tree.added_expr(@t, .binary(op: .both, left: left, right: right))

    return ok(left)

# Comparisons do NOT chain: `a < b < c` is a parse error rather than a
# left-nested pair that compares a bool with a number. This is one place where
# the little language is deliberately stricter than C, and the reason is the
# reason Heroes gives for the same choice — a program whose meaning a reader
# guesses wrong is worse than one that does not compile.
function compared(@c: cursor.Cursor, @t: tree.Tree) -> i64?
    left = summed(@c, @t)?
    op = comparison_of(cursor.here(c))

    if op.is_err()
        return ok(left)
    _ = cursor.bump(@c)
    right = summed(@c, @t)?
    made = tree.added_expr(@t, .binary(op: op.must(), left: left, right: right))
    second = comparison_of(cursor.here(c))

    if !second.is_err()
        return fail(
            code: ERR_PARSE,
            msg: "`" + token.shown(cursor.here(c)) + "` cannot follow a comparison — write it as two comparisons joined by `&&`"
        )

    return ok(made)

function summed(@c: cursor.Cursor, @t: tree.Tree) -> i64?
    left: i64 @= scaled(@c, @t)?

    while cursor.here(c) == .plus || cursor.here(c) == .minus
        op: tree.Op @= .add

        if cursor.bump(@c) == .minus
            op @ .subtract
        right = scaled(@c, @t)?
        left @ tree.added_expr(@t, .binary(op: op, left: left, right: right))

    return ok(left)

function scaled(@c: cursor.Cursor, @t: tree.Tree) -> i64?
    left: i64 @= unary(@c, @t)?

    while is_scaling(cursor.here(c))
        op: tree.Op @= .multiply
        taken = cursor.bump(@c)

        if taken == .slash
            op @ .divide

        if taken == .percent
            op @ .remainder
        right = unary(@c, @t)?
        left @ tree.added_expr(@t, .binary(op: op, left: left, right: right))

    return ok(left)

# `- -x` and `!!x` are both legal and both nest, which is why this function
# calls itself rather than calling `primary` once.
function unary(@c: cursor.Cursor, @t: tree.Tree) -> i64?
    if cursor.here(c) == .minus
        _ = cursor.bump(@c)
        on = unary(@c, @t)?
        return ok(tree.added_expr(@t, .negate(on: on)))

    if cursor.here(c) == .bang
        _ = cursor.bump(@c)
        on = unary(@c, @t)?
        return ok(tree.added_expr(@t, .invert(on: on)))

    return primary(@c, @t)

# A literal, a name, a call, or a parenthesised expression — and this is where
# the recursion turns around: `(` sends the parser back to `parsed`, which is
# how a 500-deep nest of parentheses becomes 500 turns through all seven of
# these functions. `main.hero` has that case and it must PASS, which is what
# makes it a positive witness for the runtime's stack guard rather than a test
# of it.
function primary(@c: cursor.Cursor, @t: tree.Tree) -> i64?
    return match cursor.bump(@c)
        .number n                                           => ok(tree.added_expr(@t, .number(value: n.value)))
        .text x                                             => ok(tree.added_expr(@t, .text(value: x.value)))
        .kw_true                                            => ok(tree.added_expr(@t, .truth(value: true)))
        .kw_false                                           => ok(tree.added_expr(@t, .truth(value: false)))
        .name n                                             => named(@c, @t, word: n.value)
        .lparen                                             => grouped(@c, @t)
        .kw_let | .kw_print | .kw_if | .kw_else | .kw_while => not_a_value(said: "a keyword")
        .kw_fn | .kw_return | .kw_exit | .kw_end            => not_a_value(said: "a keyword")
        .plus | .star | .slash | .percent                   => not_a_value(said: "an operator with nothing on its left")
        .equals | .less | .less_equal | .greater | .greater_equal => not_a_value(
            said: "an operator with nothing on its left"
        )
        .equal_equal | .bang_equal | .ampersands | .bars => not_a_value(said: "an operator with nothing on its left")
        .minus | .bang                                   => not_a_value(said: "a sign with nothing after it")
        .rparen                                          => not_a_value(said: "a `)` with no `(`")
        .comma                                           => not_a_value(said: "a `,` outside an argument list")
        .newline                                         => not_a_value(said: "the end of the line")
        .finish                                          => not_a_value(said: "the end of the file")

function not_a_value(said: str) -> i64?
    return fail(code: ERR_PARSE, msg: "expected a value, found " + said)

# A name, and then the one place this grammar looks ahead: a `(` right after a
# name makes it a call, and anything else leaves it a plain name.
function named(@c: cursor.Cursor, @t: tree.Tree, word: str) -> i64?
    if cursor.here(c) != .lparen
        return ok(tree.added_expr(@t, .name(value: word)))
    _ = cursor.bump(@c)

    # `given` and not `args`: `args` is a built-in of the language, so the
    # name is taken everywhere (`error[builtin_name_taken]`) even for a local.
    given: [i64] @= []

    if cursor.here(c) == .rparen
        _ = cursor.bump(@c)
        return ok(tree.added_expr(@t, .call(name: word, args: given)))

    # One argument, then as many as there are commas. Written this way rather
    # than as a `while true` holding the `return`, because the flow checker
    # does not read `while true` as *never falls through*: the loop form is
    # `error[missing_return]` unless a second `return` follows it, and an
    # unreachable `return` is a line a reader has to explain.
    given @ given.push(parsed(@c, @t)?)

    while cursor.accepted(@c, want: .comma)
        given @ given.push(parsed(@c, @t)?)

    cursor.expected(@c, want: .rparen)?
    return ok(tree.added_expr(@t, .call(name: word, args: given)))

function grouped(@c: cursor.Cursor, @t: tree.Tree) -> i64?
    inside = parsed(@c, @t)?
    cursor.expected(@c, want: .rparen)?
    return ok(inside)

function is_scaling(t: token.Token) -> bool
    return t == .star || t == .slash || t == .percent

# The operator a comparison token spells, or a refusal — used as a TEST rather
# than as a conversion, which is why it returns a fallible instead of an
# `Op?`-shaped pair with a bool.
function comparison_of(t: token.Token) -> tree.Op?
    if t == .less
        return ok(.less)

    if t == .less_equal
        return ok(.less_equal)

    if t == .greater
        return ok(.greater)

    if t == .greater_equal
        return ok(.greater_equal)

    if t == .equal_equal
        return ok(.equal)

    if t == .bang_equal
        return ok(.unequal)

    return fail(code: "not_a_comparison", msg: "`" + token.shown(t) + "` is not a comparison")

# Statements, blocks and a whole program — the layer above `syn/expr.hero`.
#
# Part of `examples/interpreter/` — the root `main.hero` carries the program's
# argument. This module owns the line-oriented shape of the little language:
# every statement begins with a keyword or is an expression, every statement
# ends at the end of its line, and every block ends at `end`.
#
# WHERE THE GENERICS CROSS A `use`. `util/each.hero` declares four templates
# and this file instantiates two of them at `str` — `joined` for the parameter
# list a duplicate-parameter refusal has to quote, and `every` for the check
# that a `fn`'s parameters are all names. `run/eval.hero` instantiates the same
# templates at `run/value.hero`'s `Value`. That is the shape the corpus was
# measured to be missing: three programs declared generics and
# **none instantiated one across a module boundary**, so monomorphisation had
# never been asked for two layouts from two callers that share nothing.
#
# AND WHERE THE LANGUAGE STOPS. The duplicate-parameter check below is a plain
# loop and not `each.counted`, because the predicate would have to know which
# name it is looking for — and Heroes has no closures (design.md Part 7 item 1,
# still unruled). A generic over a `(function(A) -> bool)` can therefore only
# ever be handed a TOP-LEVEL function, which is why every predicate this
# program passes is one: `is_a_name`, `itself`, `token.opens_a_value`. That is
# not a complaint, it is the count `M-closures-verdict` is owed, taken from a
# program rather than from a feeling.

use lex/scan
use lex/token
use syn/cursor
use syn/expr
use syn/tree
use util/each

constant ERR_PARSE: str
    "parse"

# A whole program: scanned, then read statement by statement until the tokens
# run out.
function program(source: str) -> tree.Tree?
    tokens = scan.scanned(source)?
    c: cursor.Cursor @= cursor.over(tokens)
    t: tree.Tree @= tree.empty()
    top: [i64] @= []
    cursor.skipped_lines(@c)

    while !cursor.done(c)
        top @ top.push(statement(@c, @t)?)
        cursor.skipped_lines(@c)

    t.top @ top
    return ok(t)

# One statement. The keyword decides, and a line that begins with none of them
# is an expression — which is how a bare call like `greet("world")` stands as a
# statement.
function statement(@c: cursor.Cursor, @t: tree.Tree) -> i64?
    if cursor.accepted(@c, want: .kw_let)
        return let_statement(@c, @t)

    if cursor.accepted(@c, want: .kw_print)
        value = expr.parsed(@c, @t)?
        line_end(@c)?
        return ok(tree.added_stmt(@t, .say(value: value)))

    if cursor.accepted(@c, want: .kw_if)
        return if_statement(@c, @t)

    if cursor.accepted(@c, want: .kw_while)
        return while_statement(@c, @t)

    if cursor.accepted(@c, want: .kw_fn)
        return fn_statement(@c, @t)

    if cursor.accepted(@c, want: .kw_return)
        value = expr.parsed(@c, @t)?
        line_end(@c)?
        return ok(tree.added_stmt(@t, .give(value: value)))

    if cursor.accepted(@c, want: .kw_exit)
        code = expr.parsed(@c, @t)?
        line_end(@c)?
        return ok(tree.added_stmt(@t, .stop(code: code)))

    if cursor.here(c) == .kw_end || cursor.here(c) == .kw_else
        return fail(
            code: ERR_PARSE,
            msg: "`" + token.shown(cursor.here(c)) + "` closes a block that was never opened"
        )
    value = expr.parsed(@c, @t)?
    line_end(@c)?
    return ok(tree.added_stmt(@t, .evaluate(value: value)))

function let_statement(@c: cursor.Cursor, @t: tree.Tree) -> i64?
    name = cursor.name_here(@c)?
    cursor.expected(@c, want: .equals)?
    value = expr.parsed(@c, @t)?
    line_end(@c)?
    return ok(tree.added_stmt(@t, .bind(name: name, value: value)))

function if_statement(@c: cursor.Cursor, @t: tree.Tree) -> i64?
    condition = expr.parsed(@c, @t)?
    line_end(@c)?
    then = block(@c, @t)?
    otherwise: [i64] @= []

    if cursor.accepted(@c, want: .kw_else)
        line_end(@c)?
        otherwise @ block(@c, @t)?
    cursor.expected(@c, want: .kw_end)?
    line_end(@c)?
    return ok(tree.added_stmt(@t, .when(condition: condition, then: then, otherwise: otherwise)))

function while_statement(@c: cursor.Cursor, @t: tree.Tree) -> i64?
    condition = expr.parsed(@c, @t)?
    line_end(@c)?
    body = block(@c, @t)?
    cursor.expected(@c, want: .kw_end)?
    line_end(@c)?
    return ok(tree.added_stmt(@t, .while_loop(condition: condition, body: body)))

function fn_statement(@c: cursor.Cursor, @t: tree.Tree) -> i64?
    name = cursor.name_here(@c)?
    cursor.expected(@c, want: .lparen)?
    params = parameters(@c)?
    line_end(@c)?
    body = block(@c, @t)?
    cursor.expected(@c, want: .kw_end)?
    line_end(@c)?
    return ok(tree.added_stmt(@t, .define(name: name, params: params, body: body)))

# A parameter list, refusing a repeated name — and quoting the whole list when
# it does, which is `each.joined` instantiated at `str` from this module.
function parameters(@c: cursor.Cursor) -> [str]?
    names: [str] @= []

    if cursor.accepted(@c, want: .rparen)
        return ok(names)
    names @ names.push(cursor.name_here(@c)?)

    while cursor.accepted(@c, want: .comma)
        names @ names.push(cursor.name_here(@c)?)

    cursor.expected(@c, want: .rparen)?

    if repeats(names)
        return fail(
            code: ERR_PARSE,
            msg: "a parameter is named twice in `(" + each.joined(names, itself, ", ") + ")`"
        )

    if !each.every(names, is_a_name)
        return fail(code: ERR_PARSE, msg: "a parameter may not be the empty name")

    return ok(names)

# Statements until the block's end — `end` or `else`, neither of which this
# function consumes: the caller does, because only the caller knows which of
# the two it is willing to see.
function block(@c: cursor.Cursor, @t: tree.Tree) -> [i64]?
    made: [i64] @= []
    cursor.skipped_lines(@c)

    while !closes_a_block(cursor.here(c))
        made @ made.push(statement(@c, @t)?)
        cursor.skipped_lines(@c)

    if cursor.done(c)
        return fail(code: ERR_PARSE, msg: "the file ends inside a block that no `end` closes")

    return ok(made)

function closes_a_block(t: token.Token) -> bool
    return t == .kw_end || t == .kw_else || t == .finish

# A statement ends at the end of its line, or at the end of the file. Anything
# else left on the line is a mistake worth naming, because the commonest one is
# a second statement written after the first.
function line_end(@c: cursor.Cursor) -> ()?
    if cursor.here(c) == .finish
        return ok()

    if cursor.accepted(@c, want: .newline)
        return ok()

    return fail(
        code: ERR_PARSE,
        msg: "a statement ends at the end of its line, and `" + token.shown(cursor.here(c)) + "` follows this one"
    )

# Whether any name in `names` appears twice. A plain loop and not a generic
# walk, for the reason the module header gives: the predicate would have to
# know which name it is hunting, and this language has no closures to carry it.
function repeats(names: [str]) -> bool
    i: i64 @= 0

    while i < names.len()
        j: i64 @= i + 1

        while j < names.len()
            if names[i] == names[j]
                return true
            j @ j + 1

        i @ i + 1

    return false

function is_a_name(word: str) -> bool
    return word.len() > 0

function itself(word: str) -> str
    return word

# The shapes a parsed program has, and the arena that holds them.
#
# Part of `examples/interpreter/` — the root `main.hero` carries the program's
# argument. This module declares the vocabulary and the storage; `syn/expr.hero`
# and `syn/parse.hero` fill it, `run/` walks it, and nobody outside builds a
# node without going through `added_expr`/`added_stmt`.
#
# WHY AN ARENA AND NOT A RECURSIVE VARIANT. Both work — `examples/binarytrees/`
# is a recursive `variant` and `examples/tree/` is an arena — and the choice
# here is the one a real front end makes, for a reason this program can
# demonstrate: a node is referred to from two places (a `while`'s test is read
# once per turn of the loop) and the parser builds children before parents, so
# an index is what the two want. It also makes the depth test cheap: a
# 500-deep parenthesised expression is 500 entries in one array rather than 500
# nested values that copy on every read.
#
# THE TWO ARENAS ARE SEPARATE on purpose. An expression index and a statement
# index are both `i64`, and putting them in one array would make them
# interchangeable to the type system while remaining different in fact. Two
# arrays cannot stop somebody passing one for the other either — that would
# want two distinct types, which this language does not have a cheap way to
# spell — but it does mean every `t.exprs[id]` and `t.stmts[id]` says which
# kind of index it just used, and a mistake is then visible in the line rather
# than only at run time.

# An operator with two sides. A variant rather than a `str`, so that the
# evaluator's `match` is exhaustive and a new operator cannot be added to the
# scanner without breaking every place that has to handle it.
variant Op
    add
    subtract
    multiply
    divide
    remainder
    less
    less_equal
    greater
    greater_equal
    equal
    unequal
    both
    either

# One expression. Children are indices into `Tree.exprs`.
variant Expr
    number
        value: i64
    text
        value: str
    truth
        value: bool
    name
        value: str
    negate
        on: i64
    invert
        on: i64
    binary
        op: Op
        left: i64
        right: i64
    call
        name: str
        args: [i64]

# One statement. `then`, `otherwise` and `body` are lists of statement indices;
# `value` and `condition` are expression indices.
#
# `condition` and not the obvious `test`, because `test` opens a test block in
# Heroes and a field may not take it: `error[expected_field]: expected a field
# name, found `test``, met on this file's first compile. A keyword list is a
# language's smallest surface and this is where a program meets it.
variant Stmt
    bind
        name: str
        value: i64
    say
        value: i64
    when
        condition: i64
        then: [i64]
        otherwise: [i64]
    while_loop
        condition: i64
        body: [i64]
    give
        value: i64
    stop
        code: i64
    define
        name: str
        params: [str]
        body: [i64]
    evaluate
        value: i64

# Every node of one program, and the top-level statements in order.
record Tree
    exprs: [Expr]
    stmts: [Stmt]
    top: [i64]

function empty() -> Tree
    no_exprs: [Expr] = []
    no_stmts: [Stmt] = []
    no_top: [i64] = []
    return Tree(exprs: no_exprs, stmts: no_stmts, top: no_top)

# Put an expression in the arena and hand back its index. The `@` parameter is
# the language's answer to *this function changes the thing you passed it*, and
# the index is returned rather than read back off the record, because a caller
# that computes `len(t.exprs) - 1` itself is a caller that will one day compute
# it after another push.
function added_expr(@t: Tree, e: Expr) -> i64
    t.exprs @ t.exprs.push(e)
    return t.exprs.len() - 1

function added_stmt(@t: Tree, s: Stmt) -> i64
    t.stmts @ t.stmts.push(s)
    return t.stmts.len() - 1

# How deep the expression at `id` nests. The 500-deep case in `main.hero`'s
# tests reads this, and so does the guard in `run/expr.hero`.
function expr_depth(t: Tree, id: i64) -> i64
    return match t.exprs[id]
        .number _ | .text _ | .truth _ | .name _ => 1
        .negate u                                => 1 + expr_depth(t, u.on)
        .invert u                                => 1 + expr_depth(t, u.on)
        .binary b                                => 1 + deeper(a: expr_depth(t, b.left), b: expr_depth(t, b.right))
        .call c                                  => 1 + deepest_of(t, c.args)

function deeper(a: i64, b: i64) -> i64
    if a > b
        return a

    return b

function deepest_of(t: Tree, ids: [i64]) -> i64
    most: i64 @= 0

    for id in ids
        most @ deeper(a: most, b: expr_depth(t, id))

    return most

# The operator a token spells, for the two tokens per operator that the
# scanner produces. `syn/expr.hero` asks this; keeping it here means the
# mapping and the `Op` cases are in one file and a new case cannot be added
# without meeting its spelling.
function shown_op(op: Op) -> str
    return match op
        .add           => "+"
        .subtract      => "-"
        .multiply      => "*"
        .divide        => "/"
        .remainder     => "%"
        .less          => "<"
        .less_equal    => "<="
        .greater       => ">"
        .greater_equal => ">="
        .equal         => "=="
        .unequal       => "!="
        .both          => "&&"
        .either        => "||"

# An expression written back out as text, parenthesised at every step so that
# the rendering says what the TREE holds rather than what the source said.
# `main.hero`'s tests read this: it is how a parse is checked without asserting
# on indices.
function shown_expr(t: Tree, id: i64) -> str
    return match t.exprs[id]
        .number n => n.value.to_str()
        .text x   => "\"" + x.value + "\""
        .truth b  => b.value.to_str()
        .name n   => n.value
        .negate u => "(-" + shown_expr(t, u.on) + ")"
        .invert u => "(!" + shown_expr(t, u.on) + ")"
        .binary b => "(" + shown_expr(t, b.left) + " " + shown_op(b.op) + " " + shown_expr(t, b.right) + ")"
        .call c   => c.name + "(" + shown_args(t, c.args) + ")"

function shown_args(t: Tree, ids: [i64]) -> str
    pieces: [str] @= []

    for id in ids
        pieces @ pieces.push(shown_expr(t, id))

    return join(pieces, ", ")

test "an arena hands back the index it just filled, and it is the last one"
    t: Tree @= empty()
    one = added_expr(@t, .number(value: 1))
    two = added_expr(@t, .number(value: 2))
    assert one == 0
    assert two == 1
    assert t.exprs.len() == 2
    sum = added_expr(@t, .binary(op: .add, left: one, right: two))
    assert sum == 2
    assert shown_expr(t, sum) == "(1 + 2)"

test "the two arenas count separately"
    t: Tree @= empty()
    e = added_expr(@t, .number(value: 7))
    s = added_stmt(@t, .say(value: e))
    assert e == 0
    assert s == 0
    assert t.exprs.len() == 1
    assert t.stmts.len() == 1

test "every operator has a spelling, and no two share one"
    ops: [Op] = [
        .add
        .subtract
        .multiply
        .divide
        .remainder
        .less
        .less_equal
        .greater
        .greater_equal
        .equal
        .unequal
        .both
        .either
    ]
    seen: {str: i64} @= {}

    for op in ops
        written = shown_op(op)
        assert written.len() > 0
        assert seen[written].is_err()
        seen[written] @ 1

    assert len(seen) == 13

test "a rendered expression says what the tree holds, not what the source said"
    # The rendering is fully parenthesised on purpose: `1 + 2 * 3` and
    # `(1 + 2) * 3` are different trees and must be different text, or the
    # parser's tests would pass on either.
    t: Tree @= empty()
    one = added_expr(@t, .number(value: 1))
    two = added_expr(@t, .number(value: 2))
    three = added_expr(@t, .number(value: 3))
    product = added_expr(@t, .binary(op: .multiply, left: two, right: three))
    left_first = added_expr(@t, .binary(op: .add, left: one, right: product))
    assert shown_expr(t, left_first) == "(1 + (2 * 3))"
    sum = added_expr(@t, .binary(op: .add, left: one, right: two))
    right_first = added_expr(@t, .binary(op: .multiply, left: sum, right: three))
    assert shown_expr(t, right_first) == "((1 + 2) * 3)"

test "a call renders its arguments in order, and no arguments is empty parentheses"
    t: Tree @= empty()
    a = added_expr(@t, .number(value: 1))
    b = added_expr(@t, .name(value: "x"))
    two_args = added_expr(@t, .call(name: "f", args: [a, b]))
    assert shown_expr(t, two_args) == "f(1, x)"
    none: [i64] = []
    no_args = added_expr(@t, .call(name: "now", args: none))
    assert shown_expr(t, no_args) == "now()"

test "depth counts the nesting and a leaf is one"
    t: Tree @= empty()
    leaf = added_expr(@t, .number(value: 1))
    assert expr_depth(t, leaf) == 1
    once = added_expr(@t, .negate(on: leaf))
    assert expr_depth(t, once) == 2
    twice = added_expr(@t, .invert(on: once))
    assert expr_depth(t, twice) == 3

    # A binary node takes the deeper of its two sides, not their sum.
    wide = added_expr(@t, .binary(op: .add, left: leaf, right: twice))
    assert expr_depth(t, wide) == 4

test "a thousand nodes deep is a number and not a crash"
    # Built by hand here; `main.hero` builds the same shape through the PARSER,
    # which is the case panel 104's stack guard is a positive witness for.
    t: Tree @= empty()
    at: i64 @= added_expr(@t, .number(value: 0))
    i: i64 @= 0

    while i < 999
        at @ added_expr(@t, .negate(on: at))
        i @ i + 1

    assert t.exprs.len() == 1000
    assert expr_depth(t, at) == 1000

test "the empty tree is empty in all three of its parts"
    t = empty()
    assert t.exprs.len() == 0
    assert t.stmts.len() == 0
    assert t.top.len() == 0

# Four generic walks over an array, declared here and instantiated from two
# other directories.
#
# Part of `examples/interpreter/` — the root `main.hero` carries the program's
# argument. **This module exists to be used from elsewhere**, and that is its
# point rather than a side effect. Measured over `examples/`: generics were
# declared in three programs (`calculator` 4, `deck` 5,
# `gallery` 3) and **instantiated across a `use` by none of them**. A generic
# that only its own file calls has never been asked the question
# monomorphisation exists to answer — one template, two type arguments, two
# emitted functions, from two different modules.
#
# Here `syn/parse.hero` instantiates them at `token.Token` and `run/eval.hero`
# at `value.Value`, so every function below is emitted twice with different
# layouts, from callers that share nothing.
#
# WHAT IS NOT HERE, and why the list is four rather than seven: `map`, `filter`
# and `fold` are the spec's own (§ Built-ins, *written in Heroes*), so
# redeclaring them would measure the corpus's ability to shadow a built-in
# rather than its ability to carry a generic. These four are the ones the
# interpreter actually needs and the spec does not have.

# How many of `xs` satisfy `fits`.
function counted<A>(xs: [A], fits: (function(A) -> bool)) -> i64
    total: i64 @= 0

    for one in xs
        if fits(one)
            total @ total + 1

    return total

# The first of `xs` that satisfies `fits`, or `fallback` if none does.
#
# `fallback` and not a `A?`: a generic cannot say `ok(x)` for a type parameter
# without the caller knowing what failure means here, and every caller in this
# program has a natural nothing — the `.finish` token, the unit value. Handing
# it in keeps this function total.
function first_of<A>(xs: [A], fits: (function(A) -> bool), fallback: A) -> A
    for one in xs
        if fits(one)
            return one

    return fallback

# `xs`, each rendered by `shown`, joined by `sep`. The one place this program
# turns a list of anything into a line of text.
function joined<A>(xs: [A], shown: (function(A) -> str), sep: str) -> str
    pieces: [str] @= []

    for one in xs
        pieces @ pieces.push(shown(one))

    return join(pieces, sep)

# Whether every one of `xs` satisfies `fits` — `all` in the spec's list is the
# same idea, and this one is here because it takes the SAME shape as the three
# above, which is what makes the four readable as a family.
function every<A>(xs: [A], fits: (function(A) -> bool)) -> bool
    for one in xs
        if !fits(one)
            return false

    return true

# Two predicates over `i64`, used only by this module's own tests — the
# instantiations that matter are in `syn/` and `run/`.
function is_even(n: i64) -> bool
    return n % 2 == 0

function is_negative(n: i64) -> bool
    return n < 0

function as_text(n: i64) -> str
    return n.to_str()

test "counted counts, and counts nothing in nothing"
    assert counted([1, 2, 3, 4, 5], is_even) == 2
    assert counted([2, 4], is_even) == 2
    assert counted([1, 3], is_even) == 0
    empty: [i64] = []
    assert counted(empty, is_even) == 0

test "first_of finds the first and not merely one"
    assert first_of([1, 3, 4, 6], is_even, 0 - 1) == 4
    assert first_of([2, 4, 6], is_even, 0 - 1) == 2
    assert first_of([1, 3, 5], is_even, 0 - 1) == 0 - 1
    empty: [i64] = []
    assert first_of(empty, is_even, 99) == 99

test "joined renders and joins, and an empty list is an empty line"
    assert joined([1, 2, 3], as_text, ", ") == "1, 2, 3"
    assert joined([7], as_text, ", ") == "7"
    empty: [i64] = []
    assert joined(empty, as_text, ", ") == ""
    assert joined([1, 2], as_text, "") == "12"

test "every is true of nothing, which is the answer that surprises people"
    empty: [i64] = []
    assert every(empty, is_even)
    assert every([2, 4, 6], is_even)
    assert !every([2, 3, 6], is_even)
    assert !every([1], is_negative)

test "the same template at str, which is the second instantiation in this file"
    # The two that matter cross a `use` and live in `syn/` and `run/`. This one
    # is here so that the module's own tests also cover more than one type
    # argument — a template tested at one type is a template whose
    # substitution nobody has checked.
    words = ["alpha", "be", "gamma"]
    assert counted(words, is_short) == 1
    assert first_of(words, is_short, "none") == "be"
    assert joined(words, itself, "-") == "alpha-be-gamma"
    assert !every(words, is_short)

function is_short(word: str) -> bool
    return word.len() < 3

function itself(word: str) -> str
    return word