examples/query/

# One row of the table, and the deterministic generator that writes five
# thousand of them (spec § Types, § Strings, arrays, maps).
#
# Corpus material (CLAUDE.md §9), M-corpus-depth. **The generator is the
# point of this module and not scaffolding.** Every other program in
# `examples/` reads an input somebody committed beside it — the largest is
# 28 lines — so nothing in the corpus has ever handed the language a
# thousand values at once. Copy-on-write (design.md §4.10) is the part of
# this language whose cost is proportional to the data, and a corpus that
# never exceeds thirty rows cannot see it.
#
# **The numbers come from a linear congruential generator, so the file is a
# fact and not a fixture.** The same seed gives the same five thousand rows
# on every machine and in every configuration, which is what lets
# `main.expected` hold the answers: a random source would make this program
# untestable, and a committed 5,000-line CSV would make the repository
# carry data nobody can check. The recurrence is Park and Miller's classic
# `x = (a * x + c) mod m`, and the modulus is chosen so that `a * x` cannot
# overflow an `i64`: `1103515245 * 2147483647` is 2.4e18 against `i64`'s
# 9.2e18 ceiling, and an overflow here would abort rather than wrap
# (spec § Types).

# The generator's constants, glibc's, kept together so the recurrence can be
# read on one screen.
constant MULTIPLIER: i64
    1103515245

constant INCREMENT: i64
    12345

constant MODULUS: i64
    2147483648

# The seed. Written down rather than derived, because the whole point is
# that this file is the same everywhere.
constant SEED: i64
    20260903

# How many rows the table holds. Five thousand is the size at which the
# copy-on-write question stops being theoretical: the engine sorts and
# filters this array whole, several times per query.
constant ROWS: i64
    5000

record Row
    id: i64
    team: str
    name: str
    active: bool
    score: i64
    rate: f64

# The team table the join reads: eight teams, each in one region. Small on
# purpose — a join is interesting when one side is small and the other is
# not, which is every join anybody writes.
record Team
    team: str
    region: str

constant TEAMS: [str]
    [
        "argo"
        "borea"
        "cetra"
        "delta"
        "eolia"
        "fauno"
        "gerbo"
        "halo"
    ]

constant REGIONS: [str]
    [
        "north"
        "north"
        "south"
        "south"
        "east"
        "east"
        "west"
        "west"
    ]

# The team table as values. Two arrays walked in step, which is what the
# language gives you without a tuple.
function teams() -> [Team]
    out: [Team] @= []
    at: i64 @= 0

    while at < TEAMS.len()
        out @ out.push(Team(team: TEAMS[at], region: REGIONS[at]))
        at @ at + 1

    return out

# The next number in the sequence, and the reason this is a function rather
# than a line: it is the one place an overflow could hide, and the comment
# above it is the argument that it cannot.
function stepped(seed: i64) -> i64
    return (MULTIPLIER * seed + INCREMENT) % MODULUS

# The part of a seed worth using, and **this program measured why it needs
# one**. The first draft read every field off the low bits — `seed % 8` for
# the team, `seed % 3` for the active flag — and a test written to check
# that all four regions appear over five hundred rows FAILED: the low bits
# of a linear congruential generator with a power-of-two modulus have a
# period of their own, and the lowest three cycle every eight steps, so
# whole teams never came out at all. Knuth states it (TAOCP 2, §3.2.1.1);
# this file learned it from a red test, which is the better teacher.
# Shifting sixteen bits down takes the part with the full period.
function spread(seed: i64) -> i64
    return seed >> 16

# The whole table, generated. The seed is threaded by hand rather than kept
# in a cell, because a generator that reads a mutable global is a generator
# whose output depends on who called it first — and there are no mutable
# globals in this language anyway (spec § Top-level declarations).
function generated(rows: i64) -> [Row]
    out: [Row] @= []
    seed: i64 @= SEED
    id: i64 @= 1

    while id <= rows
        seed @ stepped(seed)
        team = TEAMS[spread(seed) % TEAMS.len()]
        seed @ stepped(seed)
        score = spread(seed) % 1000
        seed @ stepped(seed)
        active = spread(seed) % 3 != 0
        seed @ stepped(seed)
        rate = to_f64(spread(seed) % 10000) / 100.0
        out @ out.push(
            Row(id: id, team: team, name: "p" + id.to_str(), active: active, score: score, rate: rate)
        )
        id @ id + 1

    return out

## Writing the table out

# One row as a CSV line. `rate` prints through `to_str`, which gives a point
# or an exponent (spec § Strings, arrays, maps) — the reader below takes it
# back, and the round trip is asserted rather than assumed.
function line_of(r: Row) -> str
    fields: [str] = [
        r.id.to_str()
        r.team
        r.name
        bool_text(r.active)
        r.score.to_str()
        r.rate.to_str()
    ]
    return fields.join(",")

# `true`/`false` written the way the language prints them, so a reader of
# the file meets no third spelling.
function bool_text(b: bool) -> str
    if b
        return "true"
    return "false"

constant HEADER: str
    "id,team,name,active,score,rate"

# The whole table as text, header first. Built with `join` and not with `+`
# in a loop: `spec:174` says a concatenation loop is quadratic, and five
# thousand rows is where that stops being a remark.
function written(rows: [Row]) -> str
    lines: [str] @= [HEADER]

    for r in rows
        lines @ lines.push(line_of(r))

    return lines.join("\n") + "\n"

test "the generator is a fact: the same seed gives the same first rows"
    made = generated(4)
    assert made.len() == 4
    assert made[0].id == 1
    assert made[0].name == "p1"
    assert made[3].id == 4

    # The same call twice is the same table, which is what `main.expected`
    # rests on.
    again = generated(4)
    assert made == again

test "every generated field is inside the range its column promises"
    made = generated(200)

    for r in made
        assert r.score >= 0 && r.score < 1000
        assert r.rate >= 0.0 && r.rate < 100.0
        assert r.name == "p" + r.id.to_str()
        assert r.team.len() > 0

test "a row renders as six comma-separated fields"
    r = Row(id: 7, team: "argo", name: "p7", active: true, score: 42, rate: 1.5)
    assert line_of(r) == "7,argo,p7,true,42,1.5"
    assert bool_text(false) == "false"

test "the team table pairs eight teams with their regions"
    ts = teams()
    assert ts.len() == 8
    assert ts[0] == Team(team: "argo", region: "north")
    assert ts[7] == Team(team: "halo", region: "west")

test "the text starts with the header and holds one line per row"
    text = written(generated(3))
    assert text.slice(from: 0, to: HEADER.len()) == HEADER
    assert text[text.len() - 1] == '\n'

# The table read back from its file: text in, typed rows out, and a named
# refusal for every way the text can be wrong (spec § Failure).
#
# Corpus material (CLAUDE.md §9), M-corpus-depth. **This module is the other
# half of `row.hero`, and the pair is the point**: the program writes five
# thousand rows and reads them back, so every conversion in the language is
# exercised in both directions on data the program made rather than on a
# fixture somebody typed. `examples/csv/` reads the hard shape — quotes,
# commas inside them, the doubled quote — and this one reads a shape it
# generated, so it can afford to be **strict**: a field that is not a number
# is a refusal naming the line and the column, not a zero.
#
# THE STRICTNESS IS THE FEATURE. A reader that answers `0` for a field it
# could not parse turns a broken file into a wrong answer, which is the one
# failure this whole corpus exists to catch. Every conversion here is a `T?`
# and every one of them is propagated with `?` (spec § Failure), so the
# first bad byte in a five-thousand-line file stops the read and says where.

use data/row

constant ERR_HEADER: str
    "bad_header"

constant ERR_FIELDS: str
    "bad_field_count"

constant ERR_NUMBER: str
    "bad_number"

constant ERR_BOOL: str
    "bad_bool"

constant ERR_EMPTY: str
    "empty_table"

# How many fields a row has. Read off `row.HEADER` rather than written
# again, so the two cannot drift.
function columns() -> i64
    return split(text: row.HEADER, at: ',').len()

# Text split on one byte. Written here rather than imported because the
# language has no `split` built in (spec § Built-ins), and the shape a
# generated file needs is the simple one: no quoting, no escapes.
function split(text: str, at: u8) -> [str]
    out: [str] @= []
    start: i64 @= 0
    index: i64 @= 0

    while index < text.len()
        if text[index] == at
            out @ out.push(text.slice(from: start, to: index))
            start @ index + 1
        index @ index + 1

    out @ out.push(text.slice(from: start, to: text.len()))
    return out

# The lines of a text, with a trailing newline producing no empty last line.
function lines_of(text: str) -> [str]
    all_lines = split(text: text, at: '\n')

    if all_lines.len() > 0 && all_lines[all_lines.len() - 1] == ""
        return all_lines.slice(from: 0, to: all_lines.len() - 1)
    return all_lines

# `true` or `false`, and nothing else. A third spelling is a refusal rather
# than a guess, because guessing here is how a column silently becomes all
# false.
function bool_of(text: str, line: i64) -> bool?
    if text == "true"
        return ok(true)

    if text == "false"
        return ok(false)
    return fail(code: ERR_BOOL, msg: "line " + line.to_str() + ": `" + text + "` is neither `true` nor `false`")

# An `i64`, refusing what `to_i64` refuses and saying which line it was on.
# `to_i64` on a `str` does not exist in this language — a `str` has no
# conversion to a number (spec § Types) — so this walks the bytes, which is
# also where a leading `+`, a stray space or an empty field is caught.
function int_of(text: str, line: i64) -> i64?
    if text.len() == 0
        return fail(code: ERR_NUMBER, msg: "line " + line.to_str() + ": a number field is empty")
    negative = text[0] == '-'
    start: i64 @= 0

    if negative
        start @ 1

        if text.len() == 1
            return fail(code: ERR_NUMBER, msg: "line " + line.to_str() + ": `-` is not a number")
    total: i64 @= 0
    at: i64 @= start

    while at < text.len()
        digit = text[at]

        if digit < '0' || digit > '9'
            return fail(code: ERR_NUMBER, msg: "line " + line.to_str() + ": `" + text + "` is not a whole number")
        total @ total * 10 + to_i64(digit - '0').must()
        at @ at + 1

    if negative
        return ok(-total)
    return ok(total)

# An `f64`, read as ONE integer divided ONCE — which is not a style but a
# repair, and the round trip is what forced it.
#
# The first draft read the two halves separately and added them: `1` plus
# `64 / 100`. That is three operations where the writer performed one, and
# three roundings do not compose into one: the generator makes this rate as
# `to_f64(164) / 100.0`, which is `1.64` exactly, and `1.0 + 0.64` is
# `1.6400000000000001`. Row 127 of the table found it — `back == made`
# failed on a value that had been written and read by the same program.
#
# So this reads every digit on both sides of the point into one whole
# number and divides by the power of ten the point implies, which is the
# writer's own arithmetic performed backwards, bit for bit. A number with
# more digits than an `i64` can hold is a refusal rather than a wrap: an
# overflow here would abort (spec § Types), and a table full of aborts
# tells a reader less than one line saying which field was too long.
constant MOST_DIGITS: i64
    18

function float_of(text: str, line: i64) -> f64?
    halves = split(text: text, at: '.')

    if halves.len() > 2
        return fail(code: ERR_NUMBER, msg: "line " + line.to_str() + ": `" + text + "` has two points")
    negative = text.len() > 0 && text[0] == '-'
    whole_digits = digits_of(halves[0], line: line, negative: negative)?
    fraction_digits: str @= ""

    if halves.len() == 2
        fraction_digits @ halves[1]

        if fraction_digits.len() == 0
            return fail(code: ERR_NUMBER, msg: "line " + line.to_str() + ": `" + text + "` ends at its point")
    all_digits = whole_digits + fraction_digits

    if all_digits.len() > MOST_DIGITS
        return fail(
            code: ERR_NUMBER,
            msg: "line " + line.to_str() + ": `" + text + "` has " + all_digits.len().to_str() + " digits and an i64 holds " + MOST_DIGITS.to_str()
        )
    scaled: i64 @= 0
    at: i64 @= 0

    while at < all_digits.len()
        digit = all_digits[at]

        if digit < '0' || digit > '9'
            return fail(code: ERR_NUMBER, msg: "line " + line.to_str() + ": `" + text + "` is not a number")
        scaled @ scaled * 10 + to_i64(digit - '0').must()
        at @ at + 1

    scale: f64 @= 1.0
    left: i64 @= fraction_digits.len()

    while left > 0
        scale @ scale * 10.0
        left @ left - 1

    value = to_f64(scaled) / scale

    if negative
        return ok(-value)
    return ok(value)

# The digits of a whole part, with its sign taken off — and a refusal for a
# sign with nothing after it, which is the one shape `text[0] == \'-\'` alone
# would let through.
function digits_of(text: str, line: i64, negative: bool) -> str?
    if text.len() == 0
        return fail(code: ERR_NUMBER, msg: "line " + line.to_str() + ": a number field is empty")

    if negative
        if text.len() == 1
            return fail(code: ERR_NUMBER, msg: "line " + line.to_str() + ": `-` is not a number")
        return ok(text.slice(from: 1, to: text.len()))
    return ok(text)

# The whole table. The header is checked against the one this program
# writes, because a file whose columns moved is a file this reader would
# otherwise read in the wrong order and answer confidently about.
function read(text: str) -> [row.Row]?
    all_lines = lines_of(text)

    if all_lines.len() == 0
        return fail(code: ERR_EMPTY, msg: "the table is empty: not even a header")

    if all_lines[0] != row.HEADER
        return fail(
            code: ERR_HEADER,
            msg: "the header reads `" + all_lines[0] + "` and this program writes `" + row.HEADER + "`"
        )
    out: [row.Row] @= []
    number: i64 @= 1
    wanted = columns()

    for one in all_lines.slice(from: 1, to: all_lines.len())
        number @ number + 1
        fields = split(text: one, at: ',')

        if fields.len() != wanted
            return fail(
                code: ERR_FIELDS,
                msg: "line " + number.to_str() + ": " + fields.len().to_str() + " fields where the header has " + wanted.to_str()
            )
        out @ out.push(
            row.Row(id: int_of(fields[0], number)?, team: fields[1], name: fields[2], active: bool_of(fields[3], number)?, score: int_of(fields[4], number)?, rate: float_of(fields[5], number)?)
        )

    return ok(out)

test "the round trip is exact for every field, including the float"
    made = row.generated(50)
    back = read(row.written(made)).must()
    assert back.len() == made.len()
    assert back == made

test "a number that is not one stops the read and names its line"
    text = row.HEADER + "\n1,argo,p1,true,x,1.5\n"
    got = read(text)
    assert got.is_err()
    assert why(got).code == ERR_NUMBER
    assert holds(text: why(got).msg, needle: "line 2")

test "a third spelling of a boolean is refused rather than guessed"
    text = row.HEADER + "\n1,argo,p1,yes,10,1.5\n"
    assert why(read(text)).code == ERR_BOOL

test "a header that moved is refused before a single row is read"
    text = "id,name,team,active,score,rate\n1,argo,p1,true,10,1.5\n"
    assert why(read(text)).code == ERR_HEADER

test "a short row is refused with both counts in the message"
    text = row.HEADER + "\n1,argo,p1,true,10\n"
    assert why(read(text)).code == ERR_FIELDS
    assert holds(text: why(read(text)).msg, needle: "5 fields where the header has 6")

test "the pieces answer what they are asked, and refuse what they are not"
    assert int_of("0", 1).must() == 0
    assert int_of("-42", 1).must() == -42
    assert int_of("", 1).is_err()
    assert int_of("-", 1).is_err()
    assert int_of("1 ", 1).is_err()
    assert float_of("2", 1).must() == 2.0
    assert float_of("2.5", 1).must() == 2.5
    assert float_of("-0.25", 1).must() == -0.25
    assert float_of("2.", 1).is_err()
    assert float_of("2.5.5", 1).is_err()
    assert split(text: "a,b,,c", at: ',') == ["a", "b", "", "c"]
    assert lines_of("a\nb\n") == ["a", "b"]
    assert lines_of("a\nb") == ["a", "b"]

# The error of a failed read, for the tests above. `.must()` on the error
# side is not a thing, so this is the shape a test uses to look at one.
function why(got: [row.Row]?) -> Trouble
    return match got
        .ok _  => Trouble(code: "", msg: "")
        .err e => Trouble(code: e.code, msg: e.msg)

record Trouble
    code: str
    msg: str

# Whether `text` holds `needle`, for the message assertions above.
function holds(text: str, needle: str) -> bool
    if needle.len() > text.len()
        return false
    at: i64 @= 0

    while at + needle.len() <= text.len()
        if text.slice(from: at, to: at + needle.len()) == needle
            return true
        at @ at + 1

    return false

# The answer, rendered: columns that line up, and numbers that do not lie
# about how many rows they stand for (spec § Strings, arrays, maps).
#
# Corpus material (CLAUDE.md §9), M-corpus-depth. The rendering is here
# rather than in `run/engine.hero` for the reason `examples/todo/` states
# about its own split: every decision about *what* the answer is stays in a
# module with no `print` in it, so the engine's tests never have to read
# text to know whether a query was right. This module holds the padding and
# nothing else.
#
# WIDTHS ARE MEASURED IN BYTES, and the program says so rather than
# discovering it: `spec:56` indexes and measures a `str` in bytes, and every
# name this table prints is ASCII by construction — a team from a written
# list, a name the generator builds out of `p` and digits. A column of text
# somebody typed would need `chars()` and a different function, which is
# `examples/widths/`'s subject and not this one.

use data/row
use query/plan

# One column of the report: which field, and how wide it came out.
record Field
    column: plan.Column
    width: i64

# A line of cells padded to their column's width, joined by two spaces.
# Trailing space is trimmed by construction: the last cell is written
# without padding, because a line that ends in blanks is a line a diff
# argues about.
function padded(cells: [str], widths: [i64]) -> str
    out: str @= ""
    at: i64 @= 0

    while at < cells.len()
        if at > 0
            out @ out + "  "

        if at == cells.len() - 1
            out @ out + cells[at]
        else
            out @ out + wide(text: cells[at], to: widths[at])
        at @ at + 1

    return out

# `text` padded on the right to `to` bytes — never truncated, because a
# report that cuts a value to fit is a report that shows the wrong value.
function wide(text: str, to: i64) -> str
    if text.len() >= to
        return text
    return text + repeat(" ", to_u64(to - text.len()).must())

# The width each column needs: the widest of its heading and its values.
function widths_for(columns: [plan.Column], rows: [row.Row]) -> [i64]
    out: [i64] @= []

    for c in columns
        widest: i64 @= plan.heading(c).len()

        for r in rows
            here = plan.text_at(c, r).len()

            if here > widest
                widest @ here

        out @ out.push(widest)

    return out

# The rows as a table: a heading line, then one line per row.
function table(columns: [plan.Column], rows: [row.Row]) -> str
    widths = widths_for(columns, rows)
    headings: [str] @= []

    for c in columns
        headings @ headings.push(plan.heading(c))

    lines: [str] @= [padded(headings, widths)]

    for r in rows
        cells: [str] @= []

        for c in columns
            cells @ cells.push(plan.text_at(c, r))

        lines @ lines.push(padded(cells, widths))

    return lines.join("\n")

# A joined row's line: the row's own columns, then its region.
function joined_table(columns: [plan.Column], rows: [plan.Joined]) -> str
    plain: [row.Row] @= []

    for j in rows
        plain @ plain.push(j.r)

    widths = widths_for(columns, plain)
    headings: [str] @= []

    for c in columns
        headings @ headings.push(plan.heading(c))

    headings @ headings.push("region")
    with_region = widths.push(6)
    lines: [str] @= [padded(headings, with_region)]

    for j in rows
        cells: [str] @= []

        for c in columns
            cells @ cells.push(plan.text_at(c, j.r))

        cells @ cells.push(j.region)
        lines @ lines.push(padded(cells, with_region))

    return lines.join("\n")

# A group's line: the key, then its four numbers. The mean is printed
# through the `T?` that computes it, so an empty group would print the
# refusal's own word rather than a number nobody should trust — and it
# cannot happen, because a group exists only where a row put it.
function group_line(g: plan.Group, s: plan.Summary) -> str
    mean = plan.mean_of(s)
    shown: str @= "-"

    if !mean.is_err()
        shown @ rounded(mean.must())
    return wide(text: g.team, to: 6) + "  " + wide(text: active_text(g.active), to: 8) + "  " + wide(text: s.rows.to_str(), to: 5) + "  " + wide(text: s.total.to_str(), to: 7) + "  " + wide(text: s.best.to_str(), to: 4) + "  " + shown

function active_text(active: bool) -> str
    if active
        return "active"
    return "idle"

# A mean to two decimals, so a float's full spelling does not decide
# whether this program's output is stable.
#
# **It ROUNDS rather than truncating, and a test is why.** `to_i64`
# truncates toward zero (spec § Failure), and the first draft relied on
# that — then asserted `rounded(9.09) == "9.08"` on the reasoning that
# `9.09 * 100.0` lands a hair under 909. Measured on this machine it lands
# exactly on 909, so the assertion was a guess about floating point dressed
# as a fact, and the test failed on the program that was right. Adding a
# half before truncating makes the answer the nearest hundredth whatever
# the last bit does, which is what a reader of a mean expects anyway. The
# value here is never negative — it is a mean of non-negative rates — so
# the half goes on unconditionally.
function rounded(v: f64) -> str
    hundredths = to_i64(v * 100.0 + 0.5).must()
    whole = hundredths / 100
    rest = hundredths % 100
    tail: str @= rest.to_str()

    if rest < 10
        tail @ "0" + tail
    return whole.to_str() + "." + tail

constant GROUP_HEADING: str
    "team    state     rows   total    best  mean"

test "a cell is padded to its column and never cut"
    assert wide(text: "ab", to: 5) == "ab   "
    assert wide(text: "abcdef", to: 3) == "abcdef"
    assert wide(text: "", to: 2) == "  "

test "a line has no trailing blanks, however wide its last column"
    widths: [i64] = [4, 4]
    line = padded(["a", "b"], widths)
    assert line == "a     b"
    assert line[line.len() - 1] != ' '

test "a column is as wide as the widest of its heading and its values"
    rows: [row.Row] = [
        row.Row(id: 1, team: "argo", name: "p1", active: true, score: 1000, rate: 1.0)
        row.Row(id: 22, team: "b", name: "p22", active: false, score: 2, rate: 2.0)
    ]
    columns: [plan.Column] = [.id, .score]
    widths = widths_for(columns, rows)
    assert widths[0] == 2
    assert widths[1] == 5

test "the table's first line is its headings and it has one line per row"
    rows = row.generated(3)
    columns: [plan.Column] = [.id, .team, .score]
    text = table(columns, rows)
    lines = split_lines(text)
    assert lines.len() == 4
    assert lines[0].slice(from: 0, to: 2) == "id"

test "a mean prints to two decimals, and the second decimal is not dropped"
    assert rounded(1.5) == "1.50"
    assert rounded(0.0) == "0.00"
    assert rounded(0.25) == "0.25"
    assert rounded(12.5) == "12.50"

    # A value whose hundredth is exact either way, so this case says what
    # the function does rather than what the last bit of a double does.
    assert rounded(9.0) == "9.00"

test "a group line carries its key and its four numbers"
    s = plan.Summary(rows: 3, total: 30, best: 20, rate_sum: 6.0)
    line = group_line(plan.Group(team: "argo", active: true), s)
    assert line.slice(from: 0, to: 4) == "argo"
    assert holds(text: line, needle: "2.00")
    assert holds(text: group_line(plan.Group(team: "argo", active: false), s), needle: "idle")

function split_lines(text: str) -> [str]
    out: [str] @= []
    start: i64 @= 0
    at: i64 @= 0

    while at < text.len()
        if text[at] == '\n'
            out @ out.push(text.slice(from: start, to: at))
            start @ at + 1
        at @ at + 1

    out @ out.push(text.slice(from: start, to: text.len()))
    return out

function holds(text: str, needle: str) -> bool
    if needle.len() > text.len()
        return false
    at: i64 @= 0

    while at + needle.len() <= text.len()
        if text.slice(from: at, to: at + needle.len()) == needle
            return true
        at @ at + 1

    return false

# A query, as a value: what to keep, what to join, how to order, what to
# count (spec § Top-level declarations, § Control flow).
#
# Corpus material (CLAUDE.md §9), M-corpus-depth. **A query here is DATA and
# not a string.** The corpus already holds three programs that read a
# language — `calculator/`, `json/` and `interpreter/` — so a fourth parser
# would measure nothing this repository has not measured. What it has never
# measured is a `variant` used as an *instruction set*: a value the program
# builds, passes around, compares and prints, whose every case the checker
# forces the engine to handle. `run/engine.hero` cannot forget a case,
# because a `match` on a variant is exhaustive or it is a compile error
# (spec § Control flow) — which is the whole reason a query is spelled this
# way rather than as text somebody parses.
#
# THE COLUMNS ARE A VARIANT AND NOT A `str`, for the same reason. A column
# named by a string is a typo waiting to become an empty result; a column
# named by a case is a typo the compiler catches.

use data/row

variant Column
    id
    team
    name
    active
    score
    rate

# What a row must satisfy to be kept. `every_row` is the identity, and it
# exists so that a query with no filter is a value like any other rather
# than a `Where?` every caller has to unwrap.
variant Where
    every_row
    team_is
        team: str
    active_is
        want: bool
    score_at_least
        least: i64
    rate_below
        limit: f64
    both
        left: [Where]

# How the kept rows are ordered. `by_active` is here because sorting on a
# `bool` is a shape the corpus had never exercised — `sort` takes a number,
# a `str` or a `bool` (spec § Built-ins), and the third had no program.
variant Order
    unordered
    by_id
    by_score_high_first
    by_name
    by_active

# What is counted over the kept rows. Three aggregates, and `mean_rate` is
# the one that has to decide what the mean of nothing is — a question a
# `T?` answers and a zero does not.
variant Aggregate
    how_many
    total_score
    best_score
    mean_rate

# The whole query. `joined` asks for the team table to be joined in, which
# is what makes `region` available to the report.
record Query
    keep: Where
    order: Order
    joined: bool
    limit: i64

# A row with its team's region attached — what a join produces. It is a
# record and not a pair, because there are no tuples in this language and
# because a name is what makes a column readable in the report.
record Joined
    r: row.Row
    region: str

# The key a `group by` groups on. **A record used as a map key**, which is
# the shape this program was written to exercise: a generated `hash` and
# `eq` walk fields rather than bytes (CLAUDE.md §7), so two keys that are
# equal field by field are one key however they were built.
record Group
    team: str
    active: bool

# What one group holds. Kept as a record rather than four maps, so a group
# is one value that can be compared and printed whole.
record Summary
    rows: i64
    total: i64
    best: i64
    rate_sum: f64

# The empty summary a group starts from. `best` starts below every possible
# score rather than at zero, because a group whose scores are all zero and a
# group with no rows must not answer the same thing.
function nothing_yet() -> Summary
    return Summary(rows: 0, total: 0, best: -1, rate_sum: 0.0)

# One row folded into a summary.
function with_row(s: Summary, r: row.Row) -> Summary
    highest: i64 @= s.best

    if r.score > highest
        highest @ r.score
    return Summary(rows: s.rows + 1, total: s.total + r.score, best: highest, rate_sum: s.rate_sum + r.rate)

# The mean of a summary's rates — `fail` on an empty group, because the mean
# of nothing is not a number and answering `0.0` would put a lie in a
# column of real numbers.
function mean_of(s: Summary) -> f64?
    if s.rows == 0
        return fail(code: "empty_group", msg: "the mean of no rows is not a number")
    return ok(s.rate_sum / to_f64(s.rows))

# Whether a row satisfies a filter. Recursive through `both`, which is what
# makes a filter a tree rather than a list — and the recursion is over an
# array inside the case, because a variant may only contain itself through
# `[T]` or `{K: V}` (spec § Types).
function kept(w: Where, r: row.Row) -> bool
    return match w
        .every_row        => true
        .team_is t        => r.team == t.team
        .active_is a      => r.active == a.want
        .score_at_least s => r.score >= s.least
        .rate_below l     => r.rate < l.limit
        .both b =>
            for one in b.left
                if !kept(one, r)
                    return false

            true

# The column a row reads for an order, as text — used by the report and by
# `by_name`. A `match` here rather than a field lookup, because a column is
# a case and there is no other way to get from a case to a value.
function text_at(c: Column, r: row.Row) -> str
    return match c
        .id     => r.id.to_str()
        .team   => r.team
        .name   => r.name
        .active => bool_text(r.active)
        .score  => r.score.to_str()
        .rate   => r.rate.to_str()

function bool_text(b: bool) -> str
    if b
        return "true"
    return "false"

# The name of a column, for a report's heading. Kept beside `text_at` so
# that a column added to the variant makes both `match`es fail to compile
# rather than one of them print a wrong heading.
function heading(c: Column) -> str
    return match c
        .id     => "id"
        .team   => "team"
        .name   => "name"
        .active => "active"
        .score  => "score"
        .rate   => "rate"

test "a filter is a value, and an empty one keeps everything"
    r = row.Row(id: 1, team: "argo", name: "p1", active: true, score: 500, rate: 12.5)
    assert kept(.every_row, r)
    assert kept(.team_is(team: "argo"), r)
    assert !kept(.team_is(team: "borea"), r)
    assert kept(.active_is(want: true), r)
    assert !kept(.active_is(want: false), r)
    assert kept(.score_at_least(least: 500), r)
    assert !kept(.score_at_least(least: 501), r)
    assert kept(.rate_below(limit: 13.0), r)
    assert !kept(.rate_below(limit: 12.5), r)

test "filters compose, and every one of them must hold"
    r = row.Row(id: 1, team: "argo", name: "p1", active: true, score: 500, rate: 12.5)
    all_of: [Where] = [.team_is(team: "argo"), .score_at_least(least: 100)]
    assert kept(.both(left: all_of), r)
    one_fails: [Where] = [.team_is(team: "argo"), .score_at_least(least: 900)]
    assert !kept(.both(left: one_fails), r)

    # A `both` of nothing keeps the row: there is no condition to fail.
    none_at_all: [Where] = []
    assert kept(.both(left: none_at_all), r)

test "a summary counts, totals and remembers the highest"
    a = row.Row(id: 1, team: "argo", name: "p1", active: true, score: 10, rate: 1.0)
    b = row.Row(id: 2, team: "argo", name: "p2", active: false, score: 30, rate: 2.0)
    s = nothing_yet().with_row(a).with_row(b)
    assert s.rows == 2
    assert s.total == 40
    assert s.best == 30
    assert s.mean_of().must() == 1.5

test "the mean of an empty group is a refusal and not a zero"
    assert nothing_yet().mean_of().is_err()

    # And the empty summary's `best` is below every score, so a group of
    # zeroes is not the same value as a group of nothing.
    assert nothing_yet().best == -1

test "a group is a record, and two groups built apart are one key"
    m: {Group: i64} @= {}
    m[Group(team: "argo", active: true)] @ 1
    m[Group(team: "argo", active: true)] @ 2
    assert m.keys().len() == 1
    assert m[Group(team: "argo", active: true)].must() == 2
    assert m[Group(team: "argo", active: false)].is_err()

test "every column has a heading and a reading, and the two lists cannot drift"
    r = row.Row(id: 7, team: "argo", name: "p7", active: false, score: 42, rate: 1.5)
    every: [Column] = [.id, .team, .name, .active, .score, .rate]
    seen: [str] @= []

    for c in every
        seen @ seen.push(heading(c))

    assert seen == ["id", "team", "name", "active", "score", "rate"]
    assert text_at(.id, r) == "7"
    assert text_at(.active, r) == "false"
    assert text_at(.rate, r) == "1.5"

# The engine: filter, join, order, group, aggregate — over the whole table,
# at the size the table actually is (design.md §4.10; spec § Strings,
# arrays, maps).
#
# Corpus material (CLAUDE.md §9), M-corpus-depth. **This module exists to
# make copy-on-write cost something.** Value semantics say every value
# behaves as an independent copy (spec § Types), and the implementation
# pays for that lazily: an array is shared until somebody writes, and one
# write unshares it (CLAUDE.md §7's *one unshare per step*). Nothing in
# this corpus has ever handed that mechanism five thousand records and
# then filtered, sorted and grouped them — so nothing has ever measured
# it. `main.hero` runs this module under `--sanitize` like every other
# corpus program, which is where a copy that was not made and a copy made
# twice both show up.
#
# THE SORT IS A MERGE SORT AND THAT IS NOT A FLOURISH. `sort` in this
# language takes an array of numbers, of `str` or of `bool` (spec
# § Built-ins) — it cannot order records, because it has no way to be told
# which field to look at. Ordering five thousand records by insertion
# would be twenty-five million comparisons; the merge sort below is
# thirteen passes. **It is also the shape that makes the copies visible**:
# every level slices its input in two and joins two halves back, so a run
# over the whole table allocates and releases sixty-odd thousand rows'
# worth of array — which is exactly the traffic the leak gate and the
# sanitiser are watching.

use data/row
use query/plan

# The rows a filter keeps, in the order they arrived.
function filtered(rows: [row.Row], keep: plan.Where) -> [row.Row]
    out: [row.Row] @= []

    for r in rows
        if plan.kept(keep, r)
            out @ out.push(r)

    return out

# The team table as a map, built once per join rather than searched per
# row: eight lookups of eight entries is nothing, five thousand searches of
# eight is a habit worth not teaching.
function regions_of(teams: [row.Team]) -> {str: str}
    m: {str: str} @= {}

    for t in teams
        m[t.team] @ t.region

    return m

# The join. A row whose team is not in the table is **dropped and counted
# by its absence**, not given an empty region: a report with a blank column
# is a report somebody reads as data.
function joined_with(rows: [row.Row], teams: [row.Team]) -> [plan.Joined]
    lookup = regions_of(teams)
    out: [plan.Joined] @= []

    for r in rows
        found = lookup[r.team]

        if !found.is_err()
            out @ out.push(plan.Joined(r: r, region: found.must()))

    return out

# Whether `a` comes before `b` under an order. Total and deterministic: the
# id breaks every tie, so two runs over the same table give the same array
# and `main.expected` means something.
function before(o: plan.Order, a: row.Row, b: row.Row) -> bool
    return match o
        .unordered => a.id < b.id
        .by_id     => a.id < b.id
        .by_score_high_first =>
            if a.score != b.score
                a.score > b.score
            else
                a.id < b.id
        .by_name =>
            if a.name != b.name
                text_before(a: a.name, b: b.name)
            else
                a.id < b.id
        .by_active =>
            if a.active != b.active
                a.active
            else
                a.id < b.id

# Whether `a` sorts before `b`, byte by byte — **and the language taught
# this program that it was needed**. `sort` orders an array of `str`
# (spec § Built-ins), so a reader reasonably expects `<` to compare two of
# them; it does not. `error[bad_operand]: `<` takes `i64` or `f64`, found
# `str`` is what `a.name < b.name` answers, and the rule behind it is
# `spec:162`: a comparison takes a number, and nothing else. So a program
# that orders records by a text field writes this, and the six lines are
# the whole of it: the first byte that differs decides, and a prefix comes
# before what extends it.
function text_before(a: str, b: str) -> bool
    shortest: i64 @= a.len()

    if b.len() < shortest
        shortest @ b.len()
    at: i64 @= 0

    while at < shortest
        if a[at] != b[at]
            return a[at] < b[at]
        at @ at + 1

    return a.len() < b.len()

# The two halves merged, stable: when neither comes first the left one
# wins, which is what keeps the previous order inside a tie.
function merged(left: [row.Row], right: [row.Row], o: plan.Order) -> [row.Row]
    out: [row.Row] @= []
    at_left: i64 @= 0
    at_right: i64 @= 0

    while at_left < left.len() && at_right < right.len()
        if before(o, a: right[at_right], b: left[at_left])
            out @ out.push(right[at_right])
            at_right @ at_right + 1
        else
            out @ out.push(left[at_left])
            at_left @ at_left + 1

    while at_left < left.len()
        out @ out.push(left[at_left])
        at_left @ at_left + 1

    while at_right < right.len()
        out @ out.push(right[at_right])
        at_right @ at_right + 1

    return out

# The rows in order. Recursion depth is the logarithm of the table's size —
# thirteen levels for five thousand rows — which is why this is the sort a
# language with a recursion ceiling can afford.
function ordered(rows: [row.Row], o: plan.Order) -> [row.Row]
    if rows.len() <= 1
        return rows
    middle = rows.len() / 2
    return merged(
        left: ordered(rows.slice(from: 0, to: middle), o),
        right: ordered(rows.slice(from: middle, to: rows.len()), o),
        o: o
    )

# The first `n`, or all of them. A limit of zero or less means no limit,
# so a query that does not care carries no special case.
function limited(rows: [row.Row], n: i64) -> [row.Row]
    if n <= 0 || n >= rows.len()
        return rows
    return rows.slice(from: 0, to: n)

# One aggregate over the kept rows. Every one of them is an `i64` except
# the mean, which is why the mean has its own function and this one does
# not pretend to answer it.
function aggregate(rows: [row.Row], what: plan.Aggregate) -> i64
    s: plan.Summary @= plan.nothing_yet()

    for r in rows
        s @ plan.with_row(s, r)

    return match what
        .how_many    => s.rows
        .total_score => s.total
        .best_score  => s.best
        .mean_rate   => s.rows

# The rows grouped by team and by whether they are active — **a map keyed
# by a record**, which is the shape that makes the generated `hash` and
# `eq` earn their keep (CLAUDE.md §7: they walk fields, never bytes).
function grouped(rows: [row.Row]) -> {plan.Group: plan.Summary}
    out: {plan.Group: plan.Summary} @= {}

    for r in rows
        key = plan.Group(team: r.team, active: r.active)
        so_far = out[key]

        if so_far.is_err()
            out[key] @ plan.with_row(plan.nothing_yet(), r)
        else
            out[key] @ plan.with_row(so_far.must(), r)

    return out

# A group's keys in a fixed order — team first, then active before
# inactive. **The map has no order** (spec § Bindings: `keys(m)` gives the
# keys in no order), so a report that walked the map as it came would print
# a different table on a different day. This is the `# ORDER:` discipline
# `examples/words/` teaches, applied to a key that is a record and so
# cannot be handed to `sort` directly.
function group_order(m: {plan.Group: plan.Summary}) -> [plan.Group]
    labels: [str] @= []

    for k in m.keys()
        labels @ labels.push(label_of(k))

    out: [plan.Group] @= []

    for one in labels.sort()
        out @ out.push(group_of(one))

    return out

# A group as one sortable string, and back. The `~` is a byte no team name
# holds, so the split is exact — and `group_of` is the inverse, which the
# test below checks over every key the table produces rather than over one
# example.
function label_of(g: plan.Group) -> str
    if g.active
        return g.team + "~1"
    return g.team + "~0"

function group_of(label: str) -> plan.Group
    cut = label.len() - 2
    return plan.Group(team: label.slice(from: 0, to: cut), active: label[label.len() - 1] == '1')

test "a filter keeps what it says and nothing else"
    rows = row.generated(200)
    argo = filtered(rows, .team_is(team: "argo"))
    assert argo.len() > 0
    assert argo.len() < rows.len()

    for r in argo
        assert r.team == "argo"

test "the sort is total, stable and the same twice"
    rows = row.generated(400)
    by_score = ordered(rows, .by_score_high_first)
    assert by_score.len() == rows.len()
    at: i64 @= 1

    while at < by_score.len()
        earlier = by_score[at - 1]
        later = by_score[at]
        assert earlier.score > later.score || earlier.score == later.score && earlier.id < later.id
        at @ at + 1

    # The same input gives the same output, which is what `main.expected`
    # rests on — and a sort that lost or invented a row would fail here.
    assert ordered(rows, .by_score_high_first) == by_score

test "sorting on a bool puts the inactive rows last and keeps ids inside a tie"
    rows = row.generated(200)
    by_active = ordered(rows, .by_active)
    seen_inactive: bool @= false

    for r in by_active
        if !r.active
            seen_inactive @ true
        else
            assert !seen_inactive

test "the sort is a permutation: every row goes in and every row comes out"
    rows = row.generated(300)
    out = ordered(rows, .by_name)
    assert out.len() == rows.len()
    ids: [i64] @= []

    for r in out
        ids @ ids.push(r.id)

    at: i64 @= 0
    in_order = ids.sort()

    while at < in_order.len()
        assert in_order[at] == at + 1
        at @ at + 1

test "the join attaches a region to every row whose team is in the table"
    rows = row.generated(100)
    with_region = joined_with(rows, row.teams())
    assert with_region.len() == rows.len()

    for j in with_region
        assert j.region.len() > 0

test "a row whose team is not in the table is dropped rather than blanked"
    stranger = row.Row(id: 1, team: "nowhere", name: "p1", active: true, score: 1, rate: 1.0)
    only_one: [row.Row] = [stranger]
    assert joined_with(only_one, row.teams()).len() == 0

test "the groups partition the table: every row lands in exactly one"
    rows = row.generated(500)
    m = grouped(rows)
    total: i64 @= 0

    for k in group_order(m)
        total @ total + m[k].must().rows

    assert total == rows.len()

test "a group label survives the round trip for every key the table makes"
    m = grouped(row.generated(500))

    for k in m.keys()
        assert group_of(label_of(k)) == k

test "the aggregates agree with a second count taken another way"
    rows = filtered(row.generated(400), .team_is(team: "borea"))
    total: i64 @= 0
    best: i64 @= -1

    for r in rows
        total @ total + r.score

        if r.score > best
            best @ r.score

    assert aggregate(rows, .how_many) == rows.len()
    assert aggregate(rows, .total_score) == total
    assert aggregate(rows, .best_score) == best

test "a limit takes the first rows, and no limit takes them all"
    rows = row.generated(50)
    assert limited(rows, 10).len() == 10
    assert limited(rows, 0).len() == 50
    assert limited(rows, 500).len() == 50
    assert limited(rows, 10)[0] == rows[0]