import std;
import dictionary;

// Integer spans keep the syntax and value pools independent of stack lifetimes.
struct Span { start: i64, len: i64 }
var text: u8[>..] = [];
fn save(s: u8[:]) -> Span {
    let result = Span { text.len, s.len };
    text.append(s);
    return result;
}
fn view(s: Span) -> u8[:] { text[s.start..s.start + s.len] }
fn number(n: i64) -> Span {
    let start = text.len;
    format(text, n);
    return Span { start, text.len - start };
}

const DECIMAL_BASE = 10;
fn decimal_prefix(s: u8[:], start: i64, limit: i64) -> i64, i64 {
    var value = 0;
    var i = start;
    while i < s.len && ascii::is_digit(s[i]) {
        let digit = (s[i] - '0') as i64;
        // Clamp to the list bound to prevent integer overflow.
        if value > limit / DECIMAL_BASE || (value == limit / DECIMAL_BASE && digit > limit % DECIMAL_BASE) { value = limit; }
        else { value = value * DECIMAL_BASE + digit; }
        i += 1;
    }
    return value, i;
}

enum TokenKind { End, Word, Quoted, Here, HereQuoted, Var, Count, Join, Dollar, Backtick,
    Lparen, Rparen, Lbrace, Rbrace, Semi, Amp, Pipe, And, Or, Caret, Equal,
    Bang, Subshell, Redir }
struct Token { kind: TokenKind, text: Span, start: i64, end: i64 }
var tokens: Token[>..] = [];

enum Kind { Empty, Literal, Variable, Count, Join, Concat, List, Capture,
    InputPipe, OutputPipe, Simple, Assign, Redirect, Sequence, And, Or, Pipe,
    Background, Subshell, Not, If, IfNot, For, While, Function, Switch, Args, ArgCommand }
var script_name: Span = Span { 0, 0 };
var parse_error: Span = Span { 0, 0 };
struct Node {
    kind: Kind, a: i64 = -1, b: i64 = -1, c: i64 = -1, d: i64 = -1,
    text: Span         = Span { 0, 0 }, next: i64 = -1,
    line: i64 = 1,
    source: Span = Span { 0, 0 }, path: Span = Span { 0, 0 }, offset: i64 = 0,
}
var nodes: Node[>..] = [];
fn node(kind: Kind, a: i64 = -1, b: i64 = -1) -> i64 {
    let id = nodes.len;
    nodes.push(Node { kind: kind, a: a, b: b });
    return id;
}
enum QuoteMode { Unquoted, Quoted }
const QUOTED_LITERAL = 1;
const HERE_EXPAND = 0;
const HERE_LITERAL = 1;
const HERE_FUNCTION = 2;
fn literal(value: Span, quoted: QuoteMode = QuoteMode.Unquoted) -> i64 {
    let id = node(Kind.Literal);
    nodes[id].text = value;
    nodes[id].a = if quoted == QuoteMode.Quoted { QUOTED_LITERAL } else { 0 };
    return id;
}

struct Value { text: Span, pattern: Span }
struct Values { start: i64, len: i64 }
var values: Value[>..]  = [];
var ranges: Values[>..] = [];
const STATUS_COUNT = 256;
var status_cache: Values[STATUS_COUNT] = [Values { 0, 0 }; STATUS_COUNT];
var status_name:  Span                 = Span { 0, 0 };
fn plain(s: Span) -> Value { Value { s, s } }
fn singleton(s: Span) -> Values {
    let start = values.len;
    values.push(plain(s));
    return Values { start, 1 };
}
fn item(v: Values, i: i64) -> Value { values[v.start + i] }
fn bytes(v: Values, i: i64) -> u8[:] { view(item(v, i).text) }
fn value_end(start: i64) -> Values { Values { start, values.len - start } }
fn concat_span(a: Span, b: Span) -> Span {
    let start = text.len;
    text.append(view(a));
    text.append(view(b));
    return Span { start, text.len - start };
}
fn join_values(v: Values, sep: u8[:]) -> Span {
    let start = text.len;
    for i in v.len {
        if i > 0 { text.append(sep); }
        text.append(bytes(v, i));
    }
    return Span { start, text.len - start };
}

struct Binding { name: Span, value: Values, collision: i64, exported: bool = true }
var bindings:      Binding[>..]         = [];
var binding_index: dictionary<u64, i64> = dictionary<u64, i64> {};
var scopes:        i64[>..<]            = [];
var free_bindings: i64[>..<]            = [];
fn lookup(name: u8[:]) -> i64 {
    let found = binding_index.get(hash(name));
    if !found { return -1; }
    var i = found;
    while i >= 0 {
        if view(bindings[i].name) == name { return i; }
        i = bindings[i].collision;
    }
    return -1;
}
fn get(name: u8[:]) -> Values {
    let i = lookup(name);
    if i < 0 { return Values { 0, 0 }; }
    return bindings[i].value;
}
fn binding_slot(name: Span, value: Values) -> i64 {
    let key = hash(view(name));
    let bucket = binding_index.get(key);
    let collision = if bucket { bucket } else { -1 };
    var index = bindings.len;
    if free_bindings.len > 0 {
        index = free_bindings.pop();
        bindings[index] = Binding { name, value, collision };
    } else { bindings.push(Binding { name, value, collision }); }
    binding_index.insert(key, index);
    return index;
}
fn bind(name: Span, value: Values) {
    scopes.push(binding_slot(name, value));
}
fn unbind(mark: i64) {
    while scopes.len > mark {
        let i = scopes.pop();
        let b = bindings[i];
        let key = hash(view(b.name));
        let bucket = binding_index.get(key);
        guard bucket else { assert(false); return; }
        var head = bucket;
        if head == i {
            if b.collision < 0 { binding_index.remove(key); }
            else { binding_index.insert(key, b.collision); }
        } else {
            while bindings[head].collision != i { head = bindings[head].collision; }
            bindings[head].collision = b.collision;
        }
        free_bindings.push(i);
    }
}
fn set(name: Span, value: Values) {
    let i = lookup(view(name));
    if i < 0 { binding_slot(name, value); return; }
    bindings[i].value = value;
    bindings[i].exported = true;
}

struct Definition { name: Span, body: i64, source: Span, exported: bool = true }
var functions: Definition[>..] = [];
var history:   Span[>..]       = [];
enum ProcessState { Running, Stopped, Done }
struct JobProcess { pid: i64, code: i64 = 0, state: ProcessState = ProcessState.Running }
struct Job {
    id:       i64, group: i64, start: i64, len: i64, command: Span,
    terminal: Span = Span { 0, 0 }, consumed: bool = false,
}
var jobs:          Job[>..]        = [];
var job_processes: JobProcess[>..] = [];
fn function(name: u8[:]) -> i64 {
    var i = functions.len;
    while i > 0 {
        i -= 1;
        if view(functions[i].name) == name { return functions[i].body; }
    }
    return -1;
}
fn definition(name: u8[:]) -> i64 {
    var i = functions.len;
    while i > 0 {
        i -= 1;
        if view(functions[i].name) == name { return i; }
    }
    return -1;
}