// Mini arithmetic language, written in ASPL.
//
// Ticket 15 slice: read one expression program from a file, tokenize it,
// parse it, and interpret integer arithmetic. Ticket 16 slice: extend the
// same program with variables and control flow. Ticket 17 slice: extend
// this same program with ASPL source generation alongside interpretation.
//
// Grammar:
//   program    := expression | var_section? statement+
//   expression := term (("+" | "-") term)*
//   term       := factor (("*" | "/" | "%") factor)*
//   factor     := "-" factor | primary
//   primary    := number | variable | "(" expression ")"
//   var_section:= ("var" name ("," name)* (";" | "."))+
//   statement  := assignment | print_statement | if_statement | while_statement
//   assignment := name "=" expression (";" | ".")
//   print_statement := "print" expression (";" | ".")
//   if_statement   := "if" "(" condition ")" "{" statement* "}"
//                    ("else" "{" statement* "}")?
//   while_statement:= "while" "(" condition ")" "{" statement* "}"
//   condition  := expression ("==" | "!=" | "<" | "<=" | ">" | ">=") expression
//
// A program whose first token is an identifier parses as the statement
// form (with an optional leading "var" section). Anything else parses as
// the ticket 15 bare-expression form, which keeps its original behavior:
// identifiers there are still a syntax error. Reserved words, never usable
// as variable names: "var", "print", "if", "else", "while".
//
// Declarations live only in the initial program-wide section and are
// visible to every later statement; there are no block scopes and no
// declarations inside loop bodies. Every declared variable starts at 0.
// Duplicate declarations and uses of undeclared variables fail with
// "duplicate-variable" and "undeclared-variable" instead of silently
// producing a value.
//
// Precedence, highest first: parentheses, unary minus, "*", "/", "%", then
// "+" and "-". Operators at the same level associate to the left. Integer
// division truncates toward zero and "%" takes the sign of its left side,
// exactly like ASPL. Arithmetic uses ASPL's checked operations, so overflow
// and division by zero trap exactly as they do in an ASPL program.
// Conditions compare two integer expressions with the six comparison
// operators and produce an ASPL boolean for the branch or loop decision.
// Branches run one side only; while bodies repeat until the condition is
// false, using ASPL's own control flow, so a runaway loop stays stoppable
// through the existing execution controls.
//
// Identifier alphabet: the first scalar is an ASCII letter, "_", or an
// Arabic letter from U+0627 through U+064A. Following scalars may also be
// ASCII digits. This documents a small Arabic-letter subset on purpose and
// does not claim ASPL's full Unicode identifier profile.
//
// Token kinds: 0 integer, 1 "+", 2 "-", 3 "*", 4 "/", 5 "%", 6 "(", 7 ")",
// 8 identifier or keyword, 9 end of input, 10 "=", 11 "==", 12 "!=", 13 "<",
// 14 "<=", 15 ">", 16 ">=", 17 "{", 18 "}", 19 ",", 20 ";" or ".".
// Node kinds reuse the token codes for expressions (0 numbers, 1-5 binary
// operators, 6 unary negation) and comparisons (11-16). Variable loads are
// 30 (holding the source spelling in the name field) so that node kinds
// never share a code with a token kind. Statement nodes are
// 40 assignment (name plus value in left), 41 print (value in left),
// 42 if (condition in left, then-branch head in extra, else-branch head in
// number with -1 for none), and 43 while (condition in left, body head in
// extra). Statements chain through right (-1 ends the sequence); a missing
// expression child is -1.
//
// Diagnostics are recoverable values, never unchecked branches. Failures
// carry a stable ASCII code plus a "line:column" position measured in
// Unicode scalar values starting at 1. Variable failures append the
// offending source spelling after the position with its bytes preserved.
// File failures forward the read_text_file code without a position.
//
// Generation maps every declared mini-language name to an indexed ASPL
// name ("m_var_0", "m_var_1", ...) by declaration order. The generated
// source never copies the original spelling, so Arabic names, ASPL
// reserved words, and collisions with generated temporaries cannot
// produce invalid or changed-meaning output. Fragments accumulate in a
// typed list<string> and join once; numbers format through format_i64.

record Token { kind: i64, text: string, line: i64, column: i64 }
record Node { kind: i64, number: i64, left: i64, right: i64, line: i64, column: i64, extra: i64, name: string }
record ParserState { tokens: list<Token>, pos: i64, nodes: list<Node>, declared: list<string>, allow_names: bool }
record ParseStep { state: ParserState, node: i64 }
record Binding { name: string, value: i64 }
record ElseStep { state: ParserState, head: i64 }
record CondBody { state: ParserState, cond: i64, body: i64 }

fn is_digit(codepoint: i64) -> bool {
    return codepoint >= 48 and codepoint <= 57;
}

fn is_name_start(codepoint: i64) -> bool {
    if (codepoint matches 95) { return true; }
    if (codepoint >= 65 and codepoint <= 90) { return true; }
    if (codepoint >= 97 and codepoint <= 122) { return true; }
    if (codepoint >= 1575 and codepoint <= 1610) { return true; }
    return false;
}

fn scan_run(source: string, pos: i64, count: i64, allow_names: bool) -> i64 {
    var end = pos;
    var scanning = true;
    while (scanning) {
        if (end >= count) {
            scanning = false;
        } else {
            let codepoint = codepoint_at(source, end);
            if (is_digit(codepoint)) {
                end = end + 1;
            } else {
                if (allow_names and is_name_start(codepoint)) {
                    end = end + 1;
                } else {
                    scanning = false;
                }
            }
        }
    }
    return end;
}

fn is_operator(codepoint: i64) -> bool {
    if (codepoint matches 43 or codepoint matches 45) { return true; }
    if (codepoint matches 42 or codepoint matches 47) { return true; }
    if (codepoint matches 37 or codepoint matches 40) { return true; }
    if (codepoint matches 41 or codepoint matches 123) { return true; }
    if (codepoint matches 125 or codepoint matches 44) { return true; }
    return codepoint matches 59 or codepoint matches 46;
}

fn operator_kind(codepoint: i64) -> i64 {
    if (codepoint matches 43) { return 1; }
    if (codepoint matches 45) { return 2; }
    if (codepoint matches 42) { return 3; }
    if (codepoint matches 47) { return 4; }
    if (codepoint matches 37) { return 5; }
    if (codepoint matches 40) { return 6; }
    if (codepoint matches 123) { return 17; }
    if (codepoint matches 125) { return 18; }
    if (codepoint matches 44) { return 19; }
    if (codepoint matches 59) { return 20; }
    if (codepoint matches 46) { return 20; }
    return 7;
}

fn double_kind(source: string, pos: i64, count: i64, codepoint: i64) -> i64 {
    var pair = "";
    if (pos + 1 < count) {
        pair = slice(source, pos, pos + 2);
    }
    if (pair matches "==") { return 11; }
    if (pair matches "!=") { return 12; }
    if (pair matches "<=") { return 14; }
    if (pair matches ">=") { return 16; }
    if (codepoint matches 61) { return 10; }
    if (codepoint matches 60) { return 13; }
    if (codepoint matches 62) { return 15; }
    return -1;
}

fn double_width(kind: i64) -> i64 {
    if (kind matches 11 or kind matches 12) { return 2; }
    if (kind matches 14 or kind matches 16) { return 2; }
    return 1;
}

fn is_keyword(text: string) -> bool {
    if (text matches "var") { return true; }
    if (text matches "print") { return true; }
    if (text matches "if") { return true; }
    if (text matches "else") { return true; }
    return text matches "while";
}

fn is_comparison(kind: i64) -> bool {
    if (kind matches 11 or kind matches 12) { return true; }
    if (kind matches 13 or kind matches 14) { return true; }
    return kind matches 15 or kind matches 16;
}

fn is_declared(declared: list<string>, name: string) -> bool {
    var i = 0;
    while (i < length(declared)) {
        if (declared[i] matches name) { return true; }
        i = i + 1;
    }
    return false;
}

fn position_text(line: i64, column: i64) -> string {
    return format_i64(line) + ":" + format_i64(column);
}

fn position_name_text(line: i64, column: i64, name: string) -> string {
    return format_i64(line) + ":" + format_i64(column) + " " + name;
}

fn tokenize_source(source: string) -> result<list<Token>> {
    var tokens: list<Token> = [];
    var pos = 0;
    var line = 1;
    var column = 1;
    let count = length(source);
    while (pos < count) {
        let codepoint = codepoint_at(source, pos);
        if (codepoint matches 32 or codepoint matches 9 or codepoint matches 13) {
            pos = pos + 1;
            column = column + 1;
        } else {
            if (codepoint matches 10) {
                pos = pos + 1;
                line = line + 1;
                column = 1;
            } else {
                if (is_digit(codepoint)) {
                    let end = scan_run(source, pos, count, false);
                    let spelling = slice(source, pos, end);
                    let parsed: result<i64> = parse_i64(spelling);
                    if (parsed::ok or spelling matches "9223372036854775808") {
                        append(tokens, Token { kind: 0, text: spelling, line: line, column: column });
                        column = column + (end - pos);
                        pos = end;
                    } else {
                        return failure(parsed::error::code, position_text(line, column));
                    }
                } else {
                    if (is_name_start(codepoint)) {
                        let end = scan_run(source, pos, count, true);
                        append(tokens, Token { kind: 8, text: slice(source, pos, end), line: line, column: column });
                        column = column + (end - pos);
                        pos = end;
                    } else {
                        if (codepoint matches 61 or codepoint matches 33 or codepoint matches 60 or codepoint matches 62) {
                            let kind = double_kind(source, pos, count, codepoint);
                            if (kind < 0) {
                                return failure("invalid-character", position_text(line, column));
                            }
                            let width = double_width(kind);
                            append(tokens, Token { kind: kind, text: slice(source, pos, pos + width), line: line, column: column });
                            pos = pos + width;
                            column = column + width;
                        } else {
                            if (is_operator(codepoint)) {
                                append(tokens, Token { kind: operator_kind(codepoint), text: char_at(source, pos), line: line, column: column });
                                pos = pos + 1;
                                column = column + 1;
                            } else {
                                return failure("invalid-character", position_text(line, column));
                            }
                        }
                    }
                }
            }
        }
    }
    append(tokens, Token { kind: 9, text: "", line: line, column: column });
    return success(tokens);
}

fn at_end(state: ParserState) -> bool {
    return state::pos >= length(state::tokens);
}

fn current(state: ParserState) -> Token {
    return state::tokens[state::pos];
}

fn append_node(state: ParserState, kind: i64, number: i64, left: i64, right: i64, line: i64, column: i64, extra: i64, name: string) -> ParseStep {
    var moving: ParserState = state;
    append(moving::nodes, Node { kind: kind, number: number, left: left, right: right, line: line, column: column, extra: extra, name: name });
    return ParseStep { state: moving, node: length(moving::nodes) - 1 };
}

fn expect_token(state: ParserState, kind: i64) -> result<ParserState> {
    if (at_end(state)) {
        let last: Token = state::tokens[length(state::tokens) - 1];
        return failure("syntax-error", position_text(last::line, last::column));
    }
    let tok: Token = current(state);
    if (tok::kind matches kind) {
        var moving: ParserState = state;
        moving::pos = moving::pos + 1;
        return success(moving);
    }
    return failure("syntax-error", position_text(tok::line, tok::column));
}

fn parse_expression(state: ParserState) -> result<ParseStep> {
    let first: result<ParseStep> = parse_term(state);
    if (first::ok) {
        var moving: ParserState = first::value::state;
        var root = first::value::node;
        var running = true;
        while (running) {
            if (at_end(moving)) {
                running = false;
            } else {
                let kind = current(moving)::kind;
                if (kind matches 1 or kind matches 2) {
                    let operator_token: Token = current(moving);
                    var next: ParserState = moving;
                    next::pos = next::pos + 1;
                    let rhs: result<ParseStep> = parse_term(next);
                    if (rhs::ok) {
                        let placed: ParseStep = append_node(rhs::value::state, kind, 0, root, rhs::value::node, operator_token::line, operator_token::column, -1, "");
                        moving = placed::state;
                        root = placed::node;
                    } else {
                        return rhs;
                    }
                } else {
                    running = false;
                }
            }
        }
        return success(ParseStep { state: moving, node: root });
    }
    return first;
}

fn parse_term(state: ParserState) -> result<ParseStep> {
    let first: result<ParseStep> = parse_factor(state);
    if (first::ok) {
        var moving: ParserState = first::value::state;
        var root = first::value::node;
        var running = true;
        while (running) {
            if (at_end(moving)) {
                running = false;
            } else {
                let kind = current(moving)::kind;
                if (kind matches 3 or kind matches 4 or kind matches 5) {
                    let operator_token: Token = current(moving);
                    var next: ParserState = moving;
                    next::pos = next::pos + 1;
                    let rhs: result<ParseStep> = parse_factor(next);
                    if (rhs::ok) {
                        let placed: ParseStep = append_node(rhs::value::state, kind, 0, root, rhs::value::node, operator_token::line, operator_token::column, -1, "");
                        moving = placed::state;
                        root = placed::node;
                    } else {
                        return rhs;
                    }
                } else {
                    running = false;
                }
            }
        }
        return success(ParseStep { state: moving, node: root });
    }
    return first;
}

fn parse_factor(state: ParserState) -> result<ParseStep> {
    if (at_end(state)) {
        let last: Token = state::tokens[length(state::tokens) - 1];
        return failure("syntax-error", position_text(last::line, last::column));
    }
    let tok: Token = current(state);
    if (tok::kind matches 0) {
        let parsed: result<i64> = parse_i64(tok::text);
        if (parsed::ok) {
            var moving: ParserState = state;
            moving::pos = moving::pos + 1;
            return success(append_node(moving, 0, parsed::value, -1, -1, tok::line, tok::column, -1, ""));
        }
        return failure(parsed::error::code, position_text(tok::line, tok::column));
    }
    if (tok::kind matches 8) {
        if (state::allow_names) {
            if (is_keyword(tok::text)) {
                return failure("syntax-error", position_text(tok::line, tok::column));
            }
            if (is_declared(state::declared, tok::text)) {
                var moving: ParserState = state;
                moving::pos = moving::pos + 1;
                return success(append_node(moving, 30, 0, -1, -1, tok::line, tok::column, -1, tok::text));
            }
            return failure("undeclared-variable", position_name_text(tok::line, tok::column, tok::text));
        }
        return failure("syntax-error", position_text(tok::line, tok::column));
    }
    if (tok::kind matches 2) {
        var moving: ParserState = state;
        moving::pos = moving::pos + 1;
        if (not at_end(moving)) {
            let magnitude: Token = current(moving);
            if (magnitude::kind matches 0 and magnitude::text matches "9223372036854775808") {
                moving::pos = moving::pos + 1;
                return success(append_node(
                    moving,
                    0,
                    -9223372036854775807 - 1,
                    -1,
                    -1,
                    tok::line,
                    tok::column,
                    -1,
                    ""
                ));
            }
        }
        let inner: result<ParseStep> = parse_factor(moving);
        if (inner::ok) {
            return success(append_node(inner::value::state, 6, 0, inner::value::node, -1, tok::line, tok::column, -1, ""));
        }
        return inner;
    }
    if (tok::kind matches 6) {
        var moving: ParserState = state;
        moving::pos = moving::pos + 1;
        let inner: result<ParseStep> = parse_expression(moving);
        if (inner::ok) {
            var after: ParserState = inner::value::state;
            if (at_end(after)) {
                return failure("syntax-error", position_text(tok::line, tok::column));
            }
            let closing: Token = current(after);
            if (closing::kind matches 7) {
                after::pos = after::pos + 1;
                return success(ParseStep { state: after, node: inner::value::node });
            }
            return failure("syntax-error", position_text(closing::line, closing::column));
        }
        return inner;
    }
    return failure("syntax-error", position_text(tok::line, tok::column));
}

fn expect_end(state: ParserState) -> result<ParserState> {
    if (at_end(state)) {
        return success(state);
    }
    let tok: Token = current(state);
    if (tok::kind matches 9) {
        return success(state);
    }
    return failure("syntax-error", position_text(tok::line, tok::column));
}

fn parse_var_name(state: ParserState) -> result<ParserState> {
    if (at_end(state)) {
        let last: Token = state::tokens[length(state::tokens) - 1];
        return failure("syntax-error", position_text(last::line, last::column));
    }
    let tok: Token = current(state);
    if (tok::kind matches 8) {
        if (is_keyword(tok::text)) {
            return failure("syntax-error", position_text(tok::line, tok::column));
        }
        if (is_declared(state::declared, tok::text)) {
            return failure("duplicate-variable", position_name_text(tok::line, tok::column, tok::text));
        }
        var moving: ParserState = state;
        moving::pos = moving::pos + 1;
        append(moving::declared, tok::text);
        return success(moving);
    }
    return failure("syntax-error", position_text(tok::line, tok::column));
}

fn parse_var_line(state: ParserState) -> result<ParserState> {
    var moving: ParserState = state;
    moving::pos = moving::pos + 1;
    let first: result<ParserState> = parse_var_name(moving);
    if (first::ok) {
        moving = first::value;
    } else {
        return first;
    }
    var running = true;
    while (running) {
        if (at_end(moving)) {
            running = false;
        } else {
            let tok: Token = current(moving);
            if (tok::kind matches 19) {
                moving::pos = moving::pos + 1;
                let named: result<ParserState> = parse_var_name(moving);
                if (named::ok) {
                    moving = named::value;
                } else {
                    return named;
                }
            } else {
                running = false;
            }
        }
    }
    let closed: result<ParserState> = expect_token(moving, 20);
    if (closed::ok) {
        return closed;
    }
    return failure(closed::error::code, closed::error::message);
}

fn parse_var_section(state: ParserState) -> result<ParserState> {
    var moving: ParserState = state;
    var running = true;
    while (running) {
        if (at_end(moving)) {
            running = false;
        } else {
            let tok: Token = current(moving);
            if (tok::kind matches 8 and tok::text matches "var") {
                let lined: result<ParserState> = parse_var_line(moving);
                if (lined::ok) {
                    moving = lined::value;
                } else {
                    return lined;
                }
            } else {
                running = false;
            }
        }
    }
    return success(moving);
}

fn parse_condition(state: ParserState) -> result<ParseStep> {
    let lhs: result<ParseStep> = parse_expression(state);
    if (lhs::ok) {
        var moving: ParserState = lhs::value::state;
        if (at_end(moving)) {
            let last: Token = moving::tokens[length(moving::tokens) - 1];
            return failure("syntax-error", position_text(last::line, last::column));
        }
        let op: Token = current(moving);
        if (is_comparison(op::kind)) {
            moving::pos = moving::pos + 1;
            let rhs: result<ParseStep> = parse_expression(moving);
            if (rhs::ok) {
                return success(append_node(rhs::value::state, op::kind, 0, lhs::value::node, rhs::value::node, op::line, op::column, -1, ""));
            }
            return rhs;
        }
        return failure("syntax-error", position_text(op::line, op::column));
    }
    return lhs;
}

fn parse_print_statement(state: ParserState, tok: Token) -> result<ParseStep> {
    var moving: ParserState = state;
    moving::pos = moving::pos + 1;
    let valued: result<ParseStep> = parse_expression(moving);
    if (valued::ok) {
        let closed: result<ParserState> = expect_token(valued::value::state, 20);
        if (closed::ok) {
            return success(append_node(closed::value, 41, 0, valued::value::node, -1, tok::line, tok::column, -1, ""));
        }
        return failure(closed::error::code, closed::error::message);
    }
    return valued;
}

fn parse_assignment(state: ParserState, tok: Token) -> result<ParseStep> {
    if (is_keyword(tok::text)) {
        return failure("syntax-error", position_text(tok::line, tok::column));
    }
    if (is_declared(state::declared, tok::text)) {
        var moving: ParserState = state;
        moving::pos = moving::pos + 1;
        let assign_op: result<ParserState> = expect_token(moving, 10);
        if (assign_op::ok) {
            let valued: result<ParseStep> = parse_expression(assign_op::value);
            if (valued::ok) {
                let closed: result<ParserState> = expect_token(valued::value::state, 20);
                if (closed::ok) {
                    return success(append_node(closed::value, 40, 0, valued::value::node, -1, tok::line, tok::column, -1, tok::text));
                }
                return failure(closed::error::code, closed::error::message);
            }
            return valued;
        }
        return failure(assign_op::error::code, assign_op::error::message);
    }
    return failure("undeclared-variable", position_name_text(tok::line, tok::column, tok::text));
}

fn parse_block(state: ParserState) -> result<ParseStep> {
    var moving: ParserState = state;
    var head = -1;
    var tail = -1;
    var running = true;
    while (running) {
        if (at_end(moving)) {
            let last: Token = moving::tokens[length(moving::tokens) - 1];
            return failure("syntax-error", position_text(last::line, last::column));
        }
        let tok: Token = current(moving);
        if (tok::kind matches 18) {
            running = false;
        } else {
            if (tok::kind matches 9) {
                return failure("syntax-error", position_text(tok::line, tok::column));
            }
            let next: result<ParseStep> = parse_statement(moving);
            if (next::ok) {
                moving = next::value::state;
                if (head < 0) {
                    head = next::value::node;
                } else {
                    moving::nodes[tail]::right = next::value::node;
                }
                tail = next::value::node;
            } else {
                return next;
            }
        }
    }
    return success(ParseStep { state: moving, node: head });
}

fn parse_else(state: ParserState) -> result<ElseStep> {
    if (at_end(state)) {
        return success(ElseStep { state: state, head: -1 });
    }
    let tok: Token = current(state);
    if (tok::kind matches 8 and tok::text matches "else") {
        var moving: ParserState = state;
        moving::pos = moving::pos + 1;
        let braced: result<ParserState> = expect_token(moving, 17);
        if (braced::ok) {
            let body: result<ParseStep> = parse_block(braced::value);
            if (body::ok) {
                let shut: result<ParserState> = expect_token(body::value::state, 18);
                if (shut::ok) {
                    return success(ElseStep { state: shut::value, head: body::value::node });
                }
                return failure(shut::error::code, shut::error::message);
            }
            return failure(body::error::code, body::error::message);
        }
        return failure(braced::error::code, braced::error::message);
    }
    return success(ElseStep { state: state, head: -1 });
}

fn parse_cond_body(state: ParserState) -> result<CondBody> {
    let opened: result<ParserState> = expect_token(state, 6);
    if (opened::ok) {
        let cond: result<ParseStep> = parse_condition(opened::value);
        if (cond::ok) {
            let closed_paren: result<ParserState> = expect_token(cond::value::state, 7);
            if (closed_paren::ok) {
                let braced: result<ParserState> = expect_token(closed_paren::value, 17);
                if (braced::ok) {
                    let body: result<ParseStep> = parse_block(braced::value);
                    if (body::ok) {
                        let shut: result<ParserState> = expect_token(body::value::state, 18);
                        if (shut::ok) {
                            return success(CondBody { state: shut::value, cond: cond::value::node, body: body::value::node });
                        }
                        return failure(shut::error::code, shut::error::message);
                    }
                    return failure(body::error::code, body::error::message);
                }
                return failure(braced::error::code, braced::error::message);
            }
            return failure(closed_paren::error::code, closed_paren::error::message);
        }
        return failure(cond::error::code, cond::error::message);
    }
    return failure(opened::error::code, opened::error::message);
}

fn parse_if_statement(state: ParserState, tok: Token) -> result<ParseStep> {
    var moving: ParserState = state;
    moving::pos = moving::pos + 1;
    let both: result<CondBody> = parse_cond_body(moving);
    if (both::ok) {
        let otherwise: result<ElseStep> = parse_else(both::value::state);
        if (otherwise::ok) {
            return success(append_node(otherwise::value::state, 42, otherwise::value::head, both::value::cond, -1, tok::line, tok::column, both::value::body, ""));
        }
        return failure(otherwise::error::code, otherwise::error::message);
    }
    return failure(both::error::code, both::error::message);
}

fn parse_while_statement(state: ParserState, tok: Token) -> result<ParseStep> {
    var moving: ParserState = state;
    moving::pos = moving::pos + 1;
    let both: result<CondBody> = parse_cond_body(moving);
    if (both::ok) {
        return success(append_node(both::value::state, 43, 0, both::value::cond, -1, tok::line, tok::column, both::value::body, ""));
    }
    return failure(both::error::code, both::error::message);
}

fn parse_statement(state: ParserState) -> result<ParseStep> {
    if (at_end(state)) {
        let last: Token = state::tokens[length(state::tokens) - 1];
        return failure("syntax-error", position_text(last::line, last::column));
    }
    let tok: Token = current(state);
    if (tok::kind matches 8) {
        if (tok::text matches "print") {
            return parse_print_statement(state, tok);
        }
        if (tok::text matches "if") {
            return parse_if_statement(state, tok);
        }
        if (tok::text matches "while") {
            return parse_while_statement(state, tok);
        }
        return parse_assignment(state, tok);
    }
    return failure("syntax-error", position_text(tok::line, tok::column));
}

fn parse_statement_list(state: ParserState) -> result<ParseStep> {
    let first: result<ParseStep> = parse_statement(state);
    if (first::ok) {
        var moving: ParserState = first::value::state;
        var head = first::value::node;
        var tail = head;
        var running = true;
        while (running) {
            if (at_end(moving)) {
                running = false;
            } else {
                let tok: Token = current(moving);
                if (tok::kind matches 9) {
                    running = false;
                } else {
                    let next: result<ParseStep> = parse_statement(moving);
                    if (next::ok) {
                        moving = next::value::state;
                        moving::nodes[tail]::right = next::value::node;
                        tail = next::value::node;
                    } else {
                        return next;
                    }
                }
            }
        }
        return success(ParseStep { state: moving, node: head });
    }
    return first;
}

fn initial_bindings(declared: list<string>) -> list<Binding> {
    var bindings: list<Binding> = [];
    var i = 0;
    while (i < length(declared)) {
        append(bindings, Binding { name: declared[i], value: 0 });
        i = i + 1;
    }
    return bindings;
}

fn binding_value(bindings: list<Binding>, name: string) -> i64 {
    var i = 0;
    while (i < length(bindings)) {
        if (bindings[i]::name matches name) {
            return bindings[i]::value;
        }
        i = i + 1;
    }
    return 0;
}

fn eval_expr(nodes: list<Node>, bindings: list<Binding>, index: i64) -> i64 {
    let node: Node = nodes[index];
    if (node::kind matches 0) { return node::number; }
    if (node::kind matches 6) { return -eval_expr(nodes, bindings, node::left); }
    if (node::kind matches 30) { return binding_value(bindings, node::name); }
    let left = eval_expr(nodes, bindings, node::left);
    let right = eval_expr(nodes, bindings, node::right);
    if (node::kind matches 1) { return left + right; }
    if (node::kind matches 2) { return left - right; }
    if (node::kind matches 3) { return left * right; }
    if (node::kind matches 4) { return left / right; }
    return left % right;
}

fn eval_cond(nodes: list<Node>, bindings: list<Binding>, index: i64) -> bool {
    let node: Node = nodes[index];
    let left = eval_expr(nodes, bindings, node::left);
    let right = eval_expr(nodes, bindings, node::right);
    if (node::kind matches 11) { return left matches right; }
    if (node::kind matches 12) { return left not match right; }
    if (node::kind matches 13) { return left < right; }
    if (node::kind matches 14) { return left <= right; }
    if (node::kind matches 15) { return right < left; }
    return right <= left;
}

fn exec_one(nodes: list<Node>, bindings: list<Binding>, index: i64) -> list<Binding> {
    let node: Node = nodes[index];
    if (node::kind matches 40) {
        let val = eval_expr(nodes, bindings, node::left);
        var owned: list<Binding> = bindings;
        var i = 0;
        while (i < length(owned)) {
            if (owned[i]::name matches node::name) {
                owned[i]::value = val;
            }
            i = i + 1;
        }
        return owned;
    }
    if (node::kind matches 41) {
        print(format_i64(eval_expr(nodes, bindings, node::left)));
        print("\n");
        return bindings;
    }
    if (node::kind matches 42) {
        var owned: list<Binding> = bindings;
        if (eval_cond(nodes, owned, node::left)) {
            owned = exec_list(nodes, owned, node::extra);
        } else {
            if (node::number >= 0) {
                owned = exec_list(nodes, owned, node::number);
            }
        }
        return owned;
    }
    var owned: list<Binding> = bindings;
    while (eval_cond(nodes, owned, node::left)) {
        owned = exec_list(nodes, owned, node::extra);
    }
    return owned;
}

fn exec_list(nodes: list<Node>, bindings: list<Binding>, head: i64) -> list<Binding> {
    var owned: list<Binding> = bindings;
    var pc = head;
    while (pc >= 0) {
        owned = exec_one(nodes, owned, pc);
        pc = nodes[pc]::right;
    }
    return owned;
}

fn evaluate(nodes: list<Node>, index: i64) -> i64 {
    let node: Node = nodes[index];
    if (node::kind matches 0) { return node::number; }
    if (node::kind matches 6) { return -evaluate(nodes, node::left); }
    let left = evaluate(nodes, node::left);
    let right = evaluate(nodes, node::right);
    if (node::kind matches 1) { return left + right; }
    if (node::kind matches 2) { return left - right; }
    if (node::kind matches 3) { return left * right; }
    if (node::kind matches 4) { return left / right; }
    return left % right;
}

fn report_error(code: string, detail: string) -> i64 {
    print("error: ");
    print(code);
    if (detail matches "") {
        print("\n");
    } else {
        print(" ");
        print(detail);
        print("\n");
    }
    return 0;
}

fn interpret_statements(toks: list<Token>) -> i64 {
    var state: ParserState = ParserState { tokens: toks, pos: 0, nodes: [], declared: [], allow_names: true };
    let section: result<ParserState> = parse_var_section(state);
    if (section::ok) {
        let parsed: result<ParseStep> = parse_statement_list(section::value);
        if (parsed::ok) {
            let finished: result<ParserState> = expect_end(parsed::value::state);
            if (finished::ok) {
                var bindings: list<Binding> = initial_bindings(finished::value::declared);
                bindings = exec_list(finished::value::nodes, bindings, parsed::value::node);
            } else {
                return report_error(finished::error::code, finished::error::message);
            }
        } else {
            return report_error(parsed::error::code, parsed::error::message);
        }
    } else {
        return report_error(section::error::code, section::error::message);
    }
    return 0;
}

fn interpret(source: string) -> i64 {
    let lexed: result<list<Token>> = tokenize_source(source);
    if (lexed::ok) {
        let toks: list<Token> = lexed::value;
        if (length(toks) > 1 and toks[0]::kind matches 8) {
            return interpret_statements(toks);
        }
        var state: ParserState = ParserState { tokens: toks, pos: 0, nodes: [], declared: [], allow_names: false };
        let parsed: result<ParseStep> = parse_expression(state);
        if (parsed::ok) {
            let finished: result<ParserState> = expect_end(parsed::value::state);
            if (finished::ok) {
                print(format_i64(evaluate(finished::value::nodes, parsed::value::node)));
                print("\n");
            } else {
                return report_error(finished::error::code, finished::error::message);
            }
        } else {
            return report_error(parsed::error::code, parsed::error::message);
        }
    } else {
        return report_error(lexed::error::code, lexed::error::message);
    }
    return 0;
}

fn declared_index(declared: list<string>, name: string) -> i64 {
    var i = 0;
    while (i < length(declared)) {
        if (declared[i] matches name) { return i; }
        i = i + 1;
    }
    return -1;
}

fn generated_name(index: i64) -> string {
    return "m_var_" + format_i64(index);
}

fn gen_expr(parts: list<string>, nodes: list<Node>, declared: list<string>, index: i64) -> list<string> {
    var out: list<string> = parts;
    let node: Node = nodes[index];
    if (node::kind matches 0) {
        append(out, format_i64(node::number));
        return out;
    }
    if (node::kind matches 6) {
        append(out, "(-");
        out = gen_expr(out, nodes, declared, node::left);
        append(out, ")");
        return out;
    }
    if (node::kind matches 30) {
        append(out, generated_name(declared_index(declared, node::name)));
        return out;
    }
    append(out, "(");
    out = gen_expr(out, nodes, declared, node::left);
    if (node::kind matches 1) {
        append(out, " + ");
    } else {
        if (node::kind matches 2) {
            append(out, " - ");
        } else {
            if (node::kind matches 3) {
                append(out, " * ");
            } else {
                if (node::kind matches 4) {
                    append(out, " / ");
                } else {
                    append(out, " % ");
                }
            }
        }
    }
    out = gen_expr(out, nodes, declared, node::right);
    append(out, ")");
    return out;
}

fn gen_cond(parts: list<string>, nodes: list<Node>, declared: list<string>, index: i64) -> list<string> {
    var out: list<string> = parts;
    let node: Node = nodes[index];
    append(out, "(");
    out = gen_expr(out, nodes, declared, node::left);
    if (node::kind matches 11) {
        append(out, " matches ");
    } else {
        if (node::kind matches 12) {
            append(out, " not match ");
        } else {
            if (node::kind matches 13) {
                append(out, " < ");
            } else {
                if (node::kind matches 14) {
                    append(out, " <= ");
                } else {
                    if (node::kind matches 15) {
                        append(out, " > ");
                    } else {
                        append(out, " >= ");
                    }
                }
            }
        }
    }
    out = gen_expr(out, nodes, declared, node::right);
    append(out, ")");
    return out;
}

fn gen_one(parts: list<string>, nodes: list<Node>, declared: list<string>, index: i64) -> list<string> {
    var out: list<string> = parts;
    let node: Node = nodes[index];
    if (node::kind matches 40) {
        append(out, generated_name(declared_index(declared, node::name)));
        append(out, " = ");
        out = gen_expr(out, nodes, declared, node::left);
        append(out, ";\n");
        return out;
    }
    if (node::kind matches 41) {
        append(out, "print(format_i64(");
        out = gen_expr(out, nodes, declared, node::left);
        append(out, "));\n");
        append(out, "print(\"\\n\");\n");
        return out;
    }
    if (node::kind matches 42) {
        append(out, "if ");
        out = gen_cond(out, nodes, declared, node::left);
        append(out, " {\n");
        out = gen_list(out, nodes, declared, node::extra);
        if (node::number >= 0) {
            append(out, "} else {\n");
            out = gen_list(out, nodes, declared, node::number);
            append(out, "}\n");
        } else {
            append(out, "}\n");
        }
        return out;
    }
    append(out, "while ");
    out = gen_cond(out, nodes, declared, node::left);
    append(out, " {\n");
    out = gen_list(out, nodes, declared, node::extra);
    append(out, "}\n");
    return out;
}

fn gen_list(parts: list<string>, nodes: list<Node>, declared: list<string>, head: i64) -> list<string> {
    var out: list<string> = parts;
    var pc = head;
    while (pc >= 0) {
        out = gen_one(out, nodes, declared, pc);
        pc = nodes[pc]::right;
    }
    return out;
}

fn generate_statements_source(declared: list<string>, nodes: list<Node>, head: i64) -> string {
    var parts: list<string> = [];
    append(parts, "fn start_main() -> i64 {\n");
    var i = 0;
    while (i < length(declared)) {
        append(parts, "var ");
        append(parts, generated_name(i));
        append(parts, ": i64 = 0;\n");
        i = i + 1;
    }
    parts = gen_list(parts, nodes, declared, head);
    append(parts, "return 0;\n}\n");
    return join(parts, "");
}

fn generate_expression_source(nodes: list<Node>, index: i64) -> string {
    var parts: list<string> = [];
    var empty: list<string> = [];
    append(parts, "fn start_main() -> i64 {\nprint(format_i64(");
    parts = gen_expr(parts, nodes, empty, index);
    append(parts, "));\n");
    append(parts, "print(\"\\n\");\n");
    append(parts, "return 0;\n}\n");
    return join(parts, "");
}

fn generate_statements(toks: list<Token>, out: string) -> i64 {
    var state: ParserState = ParserState { tokens: toks, pos: 0, nodes: [], declared: [], allow_names: true };
    let section: result<ParserState> = parse_var_section(state);
    if (section::ok) {
        let parsed: result<ParseStep> = parse_statement_list(section::value);
        if (parsed::ok) {
            let finished: result<ParserState> = expect_end(parsed::value::state);
            if (finished::ok) {
                let text = generate_statements_source(finished::value::declared, finished::value::nodes, parsed::value::node);
                let saved: result<unit> = write_text_file(out, text);
                if (saved::ok) {
                    return 0;
                }
                return report_error(saved::error::code, "");
            }
            return report_error(finished::error::code, finished::error::message);
        }
        return report_error(parsed::error::code, parsed::error::message);
    }
    return report_error(section::error::code, section::error::message);
}

fn generate_expression(toks: list<Token>, out: string) -> i64 {
    var state: ParserState = ParserState { tokens: toks, pos: 0, nodes: [], declared: [], allow_names: false };
    let parsed: result<ParseStep> = parse_expression(state);
    if (parsed::ok) {
        let finished: result<ParserState> = expect_end(parsed::value::state);
        if (finished::ok) {
            let text = generate_expression_source(finished::value::nodes, parsed::value::node);
            let saved: result<unit> = write_text_file(out, text);
            if (saved::ok) {
                return 0;
            }
            return report_error(saved::error::code, "");
        }
        return report_error(finished::error::code, finished::error::message);
    }
    return report_error(parsed::error::code, parsed::error::message);
}

fn generate_program(source: string, out: string) -> i64 {
    let lexed: result<list<Token>> = tokenize_source(source);
    if (lexed::ok) {
        let toks: list<Token> = lexed::value;
        if (length(toks) > 1 and toks[0]::kind matches 8) {
            return generate_statements(toks, out);
        }
        return generate_expression(toks, out);
    }
    return report_error(lexed::error::code, lexed::error::message);
}

fn generate_file(name: string, out: string) -> i64 {
    let content: result<string> = read_text_file(name);
    if (content::ok) {
        return generate_program(content::value, out);
    }
    return report_error(content::error::code, "");
}

fn run_file(name: string) -> i64 {
    let content: result<string> = read_text_file(name);
    if (content::ok) {
        return interpret(content::value);
    }
    return report_error(content::error::code, "");
}

fn start_main() -> i64 {
    print("File: ");
    let name = read_line();
    print("Operation: ");
    let operation = read_line();
    if (operation matches "interpret") {
        return run_file(name);
    }
    if (operation matches "generate") {
        print("Output: ");
        let out = read_line();
        return generate_file(name, out);
    }
    return report_error("unknown-operation", "");
}