examples/spreadsheet/

# The formula language, and the thing a spreadsheet is actually for: a cell that
# reads other cells.
#
#     expression := term (('+' | '-') term)*
#     term       := factor (('*' | '/') factor)*
#     factor     := number | cell | 'SUM' '(' range ')' | '(' expression ')' | '-' factor
#
# **The cycle is the interesting part.** `A1 = B1` and `B1 = A1` is a program
# that would recur until the stack ends, and no type in this language can prevent
# it — so the chain of cells currently being evaluated travels with the
# evaluation, as a plain `[str]`. Value semantics is what makes that cheap to
# say: `visiting.push(name)` hands the callee a **copy**, so there is nothing to
# pop on the way back and no way to forget to.

use sheet

## Error codes
#
# One `constant` per code, so a typo is `error[unknown_name]` here rather
# than a comparison that is quietly false forever (panel 034 R4).

constant ERR_CIRCULAR_REFERENCE: str
    "circular_reference"

constant ERR_DIVISION_BY_ZERO: str
    "division_by_zero"

constant ERR_EXPECTED_PAREN: str
    "expected_paren"

constant ERR_TRAILING_INPUT: str
    "trailing_input"

constant ERR_UNCLOSED_PAREN: str
    "unclosed_paren"

constant ERR_UNEXPECTED_CHARACTER: str
    "unexpected_character"

constant ERR_UNEXPECTED_END: str
    "unexpected_end"

constant ERR_UNKNOWN_NAME: str
    "unknown_name"

record Parse
    text: str
    pos: i64

function at_end(p: Parse) -> bool
    return p.pos >= p.text.len()

function here(p: Parse) -> u8
    return p.text[p.pos]

function advance(@p: Parse)
    p.pos @ p.pos + 1

function skip_space(@p: Parse)
    while !at_end(p) && (here(p) == ' ' || here(p) == '\t')
        advance(@p)

function contains(known: [str], name: str) -> bool
    for one in known
        if one == name
            return true

    return false

## Cells

# What a cell is worth. A cell nothing was written into is 0, which is what makes
# `SUM(A1:A9)` over a short column mean what a reader expects.
function value_of(s: sheet.Sheet, name: str, visiting: [str]) -> f64?
    if contains(visiting, name)
        return fail(code: ERR_CIRCULAR_REFERENCE, msg: "cell " + name + " is defined in terms of itself")
    source = s.cells[name].default("")

    if source == ""
        return ok(0.0)
    p: Parse @= Parse(text: source, pos: 0)
    v = expression(@p, s, visiting.push(name))?
    skip_space(@p)

    if !at_end(p)
        return fail(code: ERR_TRAILING_INPUT, msg: name + ": the formula does not end at " + p.pos.to_str())
    return ok(v)

## The grammar

function expression(@p: Parse, s: sheet.Sheet, visiting: [str]) -> f64?
    total: f64 @= term(@p, s, visiting)?
    more: bool @= true

    while more
        skip_space(@p)

        if !at_end(p) && here(p) == '+'
            advance(@p)
            total @ total + term(@p, s, visiting)?
        else if !at_end(p) && here(p) == '-'
            advance(@p)
            total @ total - term(@p, s, visiting)?
        else
            more @ false

    return ok(total)

function term(@p: Parse, s: sheet.Sheet, visiting: [str]) -> f64?
    total: f64 @= factor(@p, s, visiting)?
    more: bool @= true

    while more
        skip_space(@p)

        if !at_end(p) && here(p) == '*'
            advance(@p)
            total @ total * factor(@p, s, visiting)?
        else if !at_end(p) && here(p) == '/'
            advance(@p)
            divisor = factor(@p, s, visiting)?

            if divisor == 0.0
                return fail(code: ERR_DIVISION_BY_ZERO, msg: "a formula divides by zero")
            total @ total / divisor
        else
            more @ false

    return ok(total)

function factor(@p: Parse, s: sheet.Sheet, visiting: [str]) -> f64?
    skip_space(@p)

    if at_end(p)
        return fail(code: ERR_UNEXPECTED_END, msg: "the formula ends where a value was expected")
    c = here(p)

    if c == '('
        advance(@p)
        inner = expression(@p, s, visiting)?
        skip_space(@p)

        if at_end(p) || here(p) != ')'
            return fail(code: ERR_UNCLOSED_PAREN, msg: "expected `)` at " + p.pos.to_str())
        advance(@p)
        return ok(inner)

    if c == '-'
        advance(@p)
        return ok(-factor(@p, s, visiting)?)

    if sheet.is_digit(c)
        return ok(number(@p))

    if sheet.is_letter(c)
        return named(@p, s, visiting)
    return fail(code: ERR_UNEXPECTED_CHARACTER, msg: "no value starts at " + p.pos.to_str())

# A literal, built digit by digit: the language offers no conversion from `str`
# to a number, on purpose, because parsing can fail and a conversion may not.
function number(@p: Parse) -> f64
    whole: f64 @= 0.0

    while !at_end(p) && sheet.is_digit(here(p))
        whole @ whole * 10.0 + to_f64(to_i64(here(p) - '0').must())
        advance(@p)

    if !at_end(p) && here(p) == '.'
        advance(@p)
        scale: f64 @= 1.0

        while !at_end(p) && sheet.is_digit(here(p))
            scale @ scale / 10.0
            whole @ whole + to_f64(to_i64(here(p) - '0').must()) * scale
            advance(@p)
    return whole

# A name: either `SUM(` and a range, or a cell.
function named(@p: Parse, s: sheet.Sheet, visiting: [str]) -> f64?
    word = word_at(@p)

    if word == "SUM"
        return sum_of(@p, s, visiting)

    if !sheet.is_name(word)
        return fail(code: ERR_UNKNOWN_NAME, msg: "`" + word + "` is neither a cell nor `SUM`")
    return value_of(s, word, visiting)

function word_at(@p: Parse) -> str
    start = p.pos

    while !at_end(p) && (sheet.is_letter(here(p)) || sheet.is_digit(here(p)))
        advance(@p)

    return p.text.slice(from: start, to: p.pos)

# `SUM(A1:C2)` — the one function this language has, and enough to make ranges
# worth having at all.
function sum_of(@p: Parse, s: sheet.Sheet, visiting: [str]) -> f64?
    skip_space(@p)

    if at_end(p) || here(p) != '('
        return fail(code: ERR_EXPECTED_PAREN, msg: "`SUM` needs a range in parentheses")
    advance(@p)
    start = p.pos

    while !at_end(p) && here(p) != ')'
        advance(@p)

    if at_end(p)
        return fail(code: ERR_UNCLOSED_PAREN, msg: "`SUM(` is never closed")
    inside = p.text.slice(from: start, to: p.pos)
    advance(@p)
    total: f64 @= 0.0

    for name in sheet.expand(inside)?
        total @ total + value_of(s, name, visiting)?

    return ok(total)

test "arithmetic, with the usual precedence"
    s = sheet.read("A1 = 2 + 3 * 4\nA2 = (2 + 3) * 4\nA3 = 10 / 4\nA4 = -3 + 1\n").must()
    assert value_of(s, "A1", []).must() == 14.0
    assert value_of(s, "A2", []).must() == 20.0
    assert value_of(s, "A3", []).must() == 2.5
    assert value_of(s, "A4", []).must() == 0.0 - 2.0

test "a cell reads another cell, as deep as it likes"
    s = sheet.read("A1 = 2\nB1 = A1 * 3\nC1 = B1 + A1\n").must()
    assert value_of(s, "C1", []).must() == 8.0

test "an empty cell is zero, so a range may be longer than the column"
    s = sheet.read("A1 = 1\nA2 = 2\nB1 = SUM(A1:A9)\n").must()
    assert value_of(s, "B1", []).must() == 3.0
    assert value_of(s, "Z9", []).must() == 0.0

test "a rectangle sums row by row"
    s = sheet.read("A1 = 1\nB1 = 2\nA2 = 3\nB2 = 4\nC1 = SUM(A1:B2)\n").must()
    assert value_of(s, "C1", []).must() == 10.0

test "a cycle is a diagnosis, not a stack overflow"
    direct = sheet.read("A1 = A1\n").must()
    two = sheet.read("A1 = B1 + 1\nB1 = A1 + 1\n").must()
    long = sheet.read("A1 = B1\nB1 = C1\nC1 = A1\n").must()
    through_sum = sheet.read("A1 = SUM(B1:B2)\nB1 = A1\n").must()
    assert code_of(direct, "A1") == ERR_CIRCULAR_REFERENCE
    assert code_of(two, "A1") == ERR_CIRCULAR_REFERENCE
    assert code_of(long, "A1") == ERR_CIRCULAR_REFERENCE
    assert code_of(through_sum, "A1") == ERR_CIRCULAR_REFERENCE

test "a cell that is read twice without a cycle is not one"
    s = sheet.read("A1 = 1\nB1 = A1 + A1\nC1 = B1 + A1\n").must()
    assert value_of(s, "C1", []).must() == 3.0

test "every other failure says what and where"
    assert code_of(sheet.read("A1 = 1 / 0\n").must(), "A1") == ERR_DIVISION_BY_ZERO
    assert code_of(sheet.read("A1 = 1 +\n").must(), "A1") == ERR_UNEXPECTED_END
    assert code_of(sheet.read("A1 = (1\n").must(), "A1") == ERR_UNCLOSED_PAREN
    assert code_of(sheet.read("A1 = 1 2\n").must(), "A1") == ERR_TRAILING_INPUT
    assert code_of(sheet.read("A1 = TOTAL\n").must(), "A1") == ERR_UNKNOWN_NAME
    assert code_of(sheet.read("A1 = SUM A1\n").must(), "A1") == ERR_EXPECTED_PAREN
    assert code_of(sheet.read("A1 = SUM(A1\n").must(), "A1") == ERR_UNCLOSED_PAREN
    assert code_of(sheet.read("A1 = SUM(B1)\n").must(), "A1") == sheet.ERR_BAD_RANGE
    assert code_of(sheet.read("A1 = $\n").must(), "A1") == ERR_UNEXPECTED_CHARACTER

# The code a cell fails with — or `no_error`, which no arm above can produce, so
# a test asserting a failure cannot pass by the cell turning out to be fine.
function code_of(s: sheet.Sheet, name: str) -> str
    return match value_of(s, name, [])
        .ok _  => "no_error"
        .err e => e.code

# The grid: cell names, ranges, and the file they are read from.
#
# A cell name is **one letter and one or more digits** — `A1`, `C12`. One letter
# rather than Excel's `AA`, and the reason is written here rather than assumed:
# it makes a column a number between 0 and 25, so `A1:C1` is a loop and not a
# base-26 conversion. A program that needed 27 columns would change this file and
# nothing else.
#
# The file is one cell per line, `NAME = formula`. Blank lines and `#` comments
# are skipped, which is what makes the sample readable.

## Error codes
#
# One `constant` per code, so a typo is `error[unknown_name]` here rather
# than a comparison that is quietly false forever (panel 034 R4).

constant ERR_BAD_CELL_NAME: str
    "bad_cell_name"

constant ERR_BAD_RANGE: str
    "bad_range"

constant ERR_NO_ASSIGNMENT: str
    "no_assignment"

constant LETTERS: str
    "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

record Cell
    column: i64
    row: i64

record Sheet
    cells: {str: str}

function is_letter(c: u8) -> bool
    return c >= 'A' && c <= 'Z'

function is_digit(c: u8) -> bool
    return c >= '0' && c <= '9'

function is_space(c: u8) -> bool
    return c == ' ' || c == '\t' || c == 13

function trimmed(line: str) -> str
    from: i64 @= 0

    while from < line.len() && is_space(line[from])
        from @ from + 1

    to: i64 @= line.len()

    while to > from && is_space(line[to - 1])
        to @ to - 1

    return line.slice(from: from, to: to)

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

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

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

## Names

# `A1` as a `Cell`, or an error naming what was wrong with it.
function cell_of(name: str) -> Cell?
    if name.len() < 2 || !is_letter(name[0])
        return fail(code: ERR_BAD_CELL_NAME, msg: "`" + name + "` is not a cell: one letter then digits")
    row: i64 @= 0
    i: i64 @= 1

    while i < name.len()
        if !is_digit(name[i])
            return fail(code: ERR_BAD_CELL_NAME, msg: "`" + name + "` is not a cell: one letter then digits")
        row @ row * 10 + to_i64(name[i] - '0').must()
        i @ i + 1

    if row == 0
        return fail(code: ERR_BAD_CELL_NAME, msg: "`" + name + "` has no row: rows start at 1")
    return ok(Cell(column: to_i64(name[0] - 'A').must(), row: row))

# The name a `Cell` had. There is no `chr` in this language, so the letter comes
# out of a constant by slicing it — which is exactly what a character table is.
function name_of(c: Cell) -> str
    return LETTERS.slice(from: c.column, to: c.column + 1) + c.row.to_str()

function is_name(word: str) -> bool
    return !cell_of(word).is_err()

## Ranges

# `A1:C2` as the names it covers, row by row. Both corners are inclusive, and a
# range whose end is before its start is empty rather than an error — the same
# answer `range(from: 3, to: 1)` gives, so there is one rule to remember.
function expand(text: str) -> [str]?
    at = index_of(text, ':')

    if at < 0
        return fail(code: ERR_BAD_RANGE, msg: "`" + text + "` is not a range: two cells joined by `:`")
    from = cell_of(trimmed(text.slice(from: 0, to: at)))?
    to = cell_of(trimmed(text.slice(from: at + 1, to: text.len())))?
    out: [str] @= []

    for row in range(from: from.row, to: to.row + 1)
        for column in range(from: from.column, to: to.column + 1)
            out @ out.push(name_of(Cell(column: column, row: row)))

    return ok(out)

function index_of(text: str, c: u8) -> i64
    i: i64 @= 0

    while i < text.len()
        if text[i] == c
            return i
        i @ i + 1

    return 0 - 1

## The file

# `NAME = formula` per line, `#` a comment, blank lines skipped.
function read(text: str) -> Sheet?
    cells: {str: str} @= {}

    for line in split_lines(text)
        head = trimmed(line)

        if head == "" || head[0] == '#'
            continue
        at = index_of(head, '=')

        if at < 0
            return fail(code: ERR_NO_ASSIGNMENT, msg: "`" + head + "` is not `NAME = formula`")
        name = trimmed(head.slice(from: 0, to: at))

        if !is_name(name)
            return fail(code: ERR_BAD_CELL_NAME, msg: "`" + name + "` is not a cell name")
        cells[name] @ trimmed(head.slice(from: at + 1, to: head.len()))

    return ok(Sheet(cells: cells))

# Every cell the sheet has, in the order a reader expects: down the rows, then
# across the columns. `sort(keys(m))` would put `A10` before `A2`, because that
# is what sorting text does.
function names(s: Sheet) -> [str]
    known = sort(keys(s.cells))
    out: [str] @= []

    for row in range(from: 1, to: highest_row(known) + 1)
        for column in range(from: 0, to: 26)
            name = name_of(Cell(column: column, row: row))

            if !s.cells[name].is_err()
                out @ out.push(name)

    return out

function highest_row(known: [str]) -> i64
    best: i64 @= 0

    for name in known
        match cell_of(name)
            .ok c  => best @ larger(a: best, b: c.row)
            .err _ => continue

    return best

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

test "a cell name is one letter and digits"
    assert cell_of("A1").must() == Cell(column: 0, row: 1)
    assert cell_of("C12").must() == Cell(column: 2, row: 12)
    assert cell_of("1A").is_err()
    assert cell_of("A").is_err()
    assert cell_of("A0").is_err()
    assert cell_of("AA1").is_err()

test "a name survives a round trip"
    assert name_of(cell_of("Z9").must()) == "Z9"
    assert name_of(Cell(column: 25, row: 100)) == "Z100"

test "a range is a rectangle, row by row"
    assert expand("A1:A3").must() == ["A1", "A2", "A3"]
    assert expand("A1:C1").must() == ["A1", "B1", "C1"]
    assert expand("A1:B2").must() == ["A1", "B1", "A2", "B2"]
    assert expand("B2:A1").must() == []
    assert expand("A1").is_err()

test "the file is one cell per line, with comments"
    s = read("# a note\n\nA1 = 2\nB1 = A1 * 3\n").must()
    assert len(s.cells) == 2
    assert s.cells["B1"].must() == "A1 * 3"
    assert read("A1 2\n").is_err()
    assert read("1A = 2\n").is_err()

test "the cells come back in reading order, not in sorted order"
    s = read("A10 = 1\nA2 = 1\nB2 = 1\n").must()
    assert names(s) == ["A2", "B2", "A10"]
    assert sort(keys(s.cells)) == ["A10", "A2", "B2"]