examples/assembler/

# Two passes: where the labels are, then what the words say.
#
# Two passes rather than one because a `jmp` may name a label further down, and
# nothing else in this assembler needs the second pass at all. The first pass
# counts instructions without encoding any of them, which is only possible
# because every instruction is the same width (`program.WORDS`).
#
# A duplicate label is refused. It is the mistake whose one-pass behaviour is
# "the last one wins", and a jump that silently goes to the wrong copy of `loop`
# is the failure mode this whole project is about.

use program

## 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_OPERAND_COUNT: str
    "bad_operand_count"

constant ERR_DUPLICATE_LABEL: str
    "duplicate_label"

constant ERR_UNKNOWN_INSTRUCTION: str
    "unknown_instruction"

constant ERR_UNKNOWN_LABEL: str
    "unknown_label"

record Assembled
    code: [i64]
    labels: {str: i64}

## Pass one

function label_table(lines: [program.Line]) -> {str: i64}?
    labels: {str: i64} @= {}
    at: i64 @= 0

    for line in lines
        if line.label != ""
            if !labels[line.label].is_err()
                return fail(
                    code: ERR_DUPLICATE_LABEL,
                    msg: "line " + line.number.to_str() + ": `" + line.label + "` is defined twice"
                )
            labels[line.label] @ at

        if line.mnemonic != ""
            at @ at + 1

    return ok(labels)

## Pass two

function assemble(lines: [program.Line]) -> Assembled?
    labels = label_table(lines)?
    code: [i64] @= []

    for line in lines
        if line.mnemonic == ""
            continue

        for word in encode(line, labels)?
            code @ code.push(word)

    return ok(Assembled(code: code, labels: labels))

# One instruction, as its three words. Every arm checks its own operand count
# first, so `add r0` is refused for the reason it is wrong rather than by an
# index that aborts.
function encode(line: program.Line, labels: {str: i64}) -> [i64]?
    m = line.mnemonic

    if m == "load"
        _ = expect(line, 2)?
        return ok(
            [program.OP_LOAD, program.register_of(line.operands[0], line.number)?, program.number_of(line.operands[1], line.number)?]
        )

    if m == "copy" || m == "add" || m == "sub"
        _ = expect(line, 2)?
        return ok(
            [opcode_of(m), program.register_of(line.operands[0], line.number)?, program.register_of(line.operands[1], line.number)?]
        )

    if m == "print"
        _ = expect(line, 1)?
        return ok([program.OP_PRINT, program.register_of(line.operands[0], line.number)?, 0])

    if m == "jmpz"
        _ = expect(line, 2)?
        return ok(
            [program.OP_JMPZ, program.register_of(line.operands[0], line.number)?, target_of(line.operands[1], labels, line.number)?]
        )

    if m == "jmp"
        _ = expect(line, 1)?
        return ok([program.OP_JMP, target_of(line.operands[0], labels, line.number)?, 0])

    if m == "halt"
        _ = expect(line, 0)?
        return ok([program.OP_HALT, 0, 0])
    return fail(
        code: ERR_UNKNOWN_INSTRUCTION,
        msg: "line " + line.number.to_str() + ": there is no `" + m + "` instruction"
    )

function opcode_of(m: str) -> i64
    if m == "copy"
        return program.OP_COPY

    if m == "add"
        return program.OP_ADD
    return program.OP_SUB

function expect(line: program.Line, wanted: i64) -> i64?
    if line.operands.len() != wanted
        return fail(
            code: ERR_BAD_OPERAND_COUNT,
            msg: "line " + line.number.to_str() + ": `" + line.mnemonic + "` takes " + wanted.to_str() + ", not " + line.operands.len().to_str()
        )
    return ok(wanted)

# A label becomes the instruction index it stands at — times the width, because
# the machine counts in words.
function target_of(name: str, labels: {str: i64}, number: i64) -> i64?
    match labels[name]
        .ok at => return ok(at * program.WORDS)
        .err _ => return fail(
            code: ERR_UNKNOWN_LABEL,
            msg: "line " + number.to_str() + ": there is no label `" + name + "`"
        )

test "labels are instruction indices, and blank lines do not count"
    lines = program.read("start:\n\n  load r0, 1   ; one\nagain:\n  print r0\n  jmp again\n")
    labels = label_table(lines).must()
    assert labels["start"].must() == 0
    assert labels["again"].must() == 1

test "an instruction is three words, whether it needs them or not"
    out = assemble(program.read("load r0, 7\nhalt\n")).must()
    assert out.code == [program.OP_LOAD, 0, 7, program.OP_HALT, 0, 0]

test "a jump resolves to a word offset"
    out = assemble(program.read("here:\n  jmp here\n")).must()
    assert out.code == [program.OP_JMP, 0, 0]
    forward = assemble(program.read("jmp end\nhalt\nend:\n  halt\n")).must()
    assert forward.code[1] == 2 * program.WORDS

test "every way to get it wrong has its own code and its own line"
    assert code_of("add r0\n") == ERR_BAD_OPERAND_COUNT
    assert code_of("frob r0, r1\n") == ERR_UNKNOWN_INSTRUCTION
    assert code_of("add r0, r9\n") == program.ERR_BAD_REGISTER
    assert code_of("load r0, x\n") == program.ERR_BAD_NUMBER
    assert code_of("jmp nowhere\n") == ERR_UNKNOWN_LABEL
    assert code_of("a:\nhalt\na:\nhalt\n") == ERR_DUPLICATE_LABEL

test "the message names the line the reader has to open"
    match assemble(program.read("halt\nhalt\nfrob\n"))
        .ok _  => assert false
        .err e => assert e.msg == "line 3: there is no `frob` instruction"

function code_of(text: str) -> str
    return match assemble(program.read(text))
        .ok _  => "no_error"
        .err e => e.code

# The machine the assembler assembles for.
#
# Assembling without running proves nothing: an encoding is only right if
# something decodes it, and the two halves are written from the same constants
# in `program.hero` so they cannot drift apart.
#
# **The run is bounded by fuel.** A program that loops forever is a program and
# not a defect in the machine — but a corpus that hangs is a corpus nobody runs,
# and a test suite has no operator to press ^C. So the machine stops and says
# `out_of_fuel`, which is a result the caller can assert.

use assemble
use program

## 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_OPCODE: str
    "bad_opcode"

constant ERR_OUT_OF_FUEL: str
    "out_of_fuel"

constant ERR_RAN_OFF_THE_END: str
    "ran_off_the_end"

record Machine
    registers: [i64]
    pc: i64
    output: [str]

function run(code: [i64], fuel: i64) -> [str]?
    m: Machine @= Machine(registers: [0, 0, 0, 0], pc: 0, output: [])
    left: i64 @= fuel

    while left > 0
        left @ left - 1

        if m.pc < 0 || m.pc + program.WORDS > code.len()
            return fail(code: ERR_RAN_OFF_THE_END, msg: "the machine stepped past the last instruction")
        opcode = code[m.pc]
        a = code[m.pc + 1]
        b = code[m.pc + 2]

        if opcode == program.OP_HALT
            return ok(m.output)
        _ = step(@m, opcode: opcode, a: a, b: b)?

    return fail(code: ERR_OUT_OF_FUEL, msg: "the program ran for " + fuel.to_str() + " steps without halting")

# One instruction. The program counter moves here and nowhere else, so a jump is
# the arm that does *not* fall through to the advance.
function step(@m: Machine, opcode: i64, a: i64, b: i64) -> i64?
    if opcode == program.OP_LOAD
        m.registers[a] @ b
    else if opcode == program.OP_COPY
        m.registers[a] @ m.registers[b]
    else if opcode == program.OP_ADD
        m.registers[a] @ m.registers[a] + m.registers[b]
    else if opcode == program.OP_SUB
        m.registers[a] @ m.registers[a] - m.registers[b]
    else if opcode == program.OP_PRINT
        m.output @ m.output.push(m.registers[a].to_str())
    else if opcode == program.OP_JMP
        m.pc @ a
        return ok(opcode)
    else if opcode == program.OP_JMPZ
        if m.registers[a] == 0
            m.pc @ b
            return ok(opcode)
    else
        return fail(code: ERR_BAD_OPCODE, msg: "the code holds " + opcode.to_str() + ", which is not an instruction")
    m.pc @ m.pc + program.WORDS
    return ok(opcode)

# Assemble and run, which is what the program does — and what every test below
# asks, so the encoding and the decoding are checked against each other rather
# than each against a table someone wrote twice.
function execute(text: str, fuel: i64) -> [str]?
    out = assemble.assemble(program.read(text))?
    return run(out.code, fuel)

test "load, add and print do what their names say"
    assert execute("load r0, 2\nload r1, 3\nadd r0, r1\nprint r0\nhalt\n", 100).must() == ["5"]

test "copy and sub, and a register left alone stays zero"
    assert execute("load r0, 9\ncopy r1, r0\nsub r1, r0\nprint r1\nprint r3\nhalt\n", 100).must() == ["0", "0"]

test "a loop counts down and stops"
    countdown = "load r0, 3\nload r1, 1\nagain:\n  print r0\n  sub r0, r1\n  jmpz r0, done\n  jmp again\ndone:\n  halt\n"
    assert execute(countdown, 100).must() == ["3", "2", "1"]

test "a program that never halts runs out of fuel instead of running forever"
    assert code_of("here:\n  jmp here\n", 50) == ERR_OUT_OF_FUEL

test "falling off the end is not the same as halting"
    assert code_of("load r0, 1\n", 100) == ERR_RAN_OFF_THE_END

test "the fuel is spent per instruction, so a short program needs little"
    assert execute("halt\n", 1).must() == []
    assert code_of("load r0, 1\nhalt\n", 1) == ERR_OUT_OF_FUEL

function code_of(text: str, fuel: i64) -> str
    return match execute(text, fuel)
        .ok _  => "no_error"
        .err e => e.code

# The instruction set, and one line of assembly.
#
# A register machine with four registers and seven instructions, which is the
# smallest set that can compute something worth printing:
#
#     load  rD, n        rD = n
#     copy  rD, rS       rD = rS
#     add   rD, rS       rD = rD + rS
#     sub   rD, rS       rD = rD - rS
#     print rD           write rD
#     jmpz  rS, label    go to label when rS is zero
#     jmp   label        go there
#     halt               stop
#
# **Every instruction is three words**: the opcode and two operands, whether it
# uses them or not. Fixed width because the assembler resolves a label to an
# *instruction index*, and an index is only arithmetic when instructions are all
# the same size — a variable-width encoding would need a second pass over
# addresses rather than over labels.
#
# A line is `[label:] [mnemonic [operand, operand]] [; comment]`, and any part
# may be missing.

## 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_NUMBER: str
    "bad_number"

constant ERR_BAD_REGISTER: str
    "bad_register"

constant OP_LOAD: i64
    0

constant OP_COPY: i64
    1

constant OP_ADD: i64
    2

constant OP_SUB: i64
    3

constant OP_PRINT: i64
    4

constant OP_JMPZ: i64
    5

constant OP_JMP: i64
    6

constant OP_HALT: i64
    7

constant WORDS: i64
    3

constant REGISTERS: i64
    4

record Line
    label: str
    mnemonic: str
    operands: [str]
    number: i64

## Text

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

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

# Split at `c`, with the empty pieces dropped. `add r0, r1` and `add r0,r1` are
# the same instruction: the separator is the comma and the spaces are noise.
function split_on(text: str, c: u8) -> [str]
    out: [str] @= []
    start: i64 @= 0
    i: i64 @= 0

    while i <= text.len()
        if i == text.len() || text[i] == c
            piece = trimmed(text.slice(from: start, to: i))

            if piece != ""
                out @ out.push(piece)
            start @ i + 1
        i @ i + 1

    return out

## Lines

# One source line, taken apart. Nothing here is refused — an unknown mnemonic is
# the assembler's business, and a reader who mistypes one wants to be told which
# line it was on, which is why `number` travels with it.
function read_line(text: str, number: i64) -> Line
    body: str @= text
    at = index_of(body, ';')

    if at >= 0
        body @ body.slice(from: 0, to: at)
    body @ trimmed(body)
    label: str @= ""
    colon = index_of(body, ':')

    if colon >= 0
        label @ trimmed(body.slice(from: 0, to: colon))
        body @ trimmed(body.slice(from: colon + 1, to: body.len()))

    if body == ""
        return Line(label: label, mnemonic: "", operands: [], number: number)
    space = index_of(body, ' ')

    if space < 0
        return Line(label: label, mnemonic: body, operands: [], number: number)
    mnemonic = body.slice(from: 0, to: space)
    rest = body.slice(from: space + 1, to: body.len())
    return Line(label: label, mnemonic: mnemonic, operands: split_on(rest, ','), number: number)

function read(text: str) -> [Line]
    out: [Line] @= []
    number: i64 @= 0

    for line in split_lines(text)
        number @ number + 1
        out @ out.push(read_line(line, number))

    return out

## Operands

# `r0` … `r3`, and nothing else. The message names the range, because a reader
# who wrote `r9` needs to know what would have fitted (§4.17).
function register_of(word: str, number: i64) -> i64?
    if word.len() != 2 || word[0] != 'r'
        return fail(
            code: ERR_BAD_REGISTER,
            msg: "line " + number.to_str() + ": `" + word + "` is not a register — r0 to r3"
        )
    n = to_i64(word[1] - '0').must()

    if n < 0 || n >= REGISTERS
        return fail(
            code: ERR_BAD_REGISTER,
            msg: "line " + number.to_str() + ": `" + word + "` is not a register — r0 to r3"
        )
    return ok(n)

function number_of(word: str, number: i64) -> i64?
    body: str @= word
    negative: bool @= false

    if body.len() > 0 && body[0] == '-'
        negative @ true
        body @ body.slice(from: 1, to: body.len())

    if body.len() == 0
        return fail(code: ERR_BAD_NUMBER, msg: "line " + number.to_str() + ": `" + word + "` is not a number")
    v: i64 @= 0

    for i in range(from: 0, to: body.len())
        if body[i] < '0' || body[i] > '9'
            return fail(code: ERR_BAD_NUMBER, msg: "line " + number.to_str() + ": `" + word + "` is not a number")
        v @ v * 10 + to_i64(body[i] - '0').must()

    if negative
        return ok(-v)
    return ok(v)

test "a line comes apart into its four pieces"
    plain = read_line("  add r0, r1   ; sum", 7)
    assert plain.label == ""
    assert plain.mnemonic == "add"
    assert plain.operands == ["r0", "r1"]
    assert plain.number == 7

test "a label may stand alone or open a line"
    alone = read_line("loop:", 1)
    assert alone.label == "loop"
    assert alone.mnemonic == ""
    both = read_line("loop: jmp loop", 2)
    assert both.label == "loop"
    assert both.mnemonic == "jmp"
    assert both.operands == ["loop"]

test "a comment and blank space leave nothing behind"
    empty = read_line("   ; nothing at all", 3)
    assert empty.label == ""
    assert empty.mnemonic == ""
    assert empty.operands == []

test "spaces around a comma are noise"
    assert read_line("add r0,r1", 1).operands == ["r0", "r1"]
    assert read_line("add  r0 ,  r1 ", 1).operands == ["r0", "r1"]

test "a register is r0 to r3, and a number may be negative"
    assert register_of("r2", 1).must() == 2
    assert register_of("r4", 1).is_err()
    assert register_of("rx", 1).is_err()
    assert register_of("r", 1).is_err()
    assert number_of("42", 1).must() == 42
    assert number_of("-7", 1).must() == 0 - 7
    assert number_of("x", 1).is_err()
    assert number_of("-", 1).is_err()