import expand;
import os;
import memory;
import declaration;
import resources;
import jobs;
import binding_context;
import history;
import terminal_text;

const MAX_CALL_DEPTH = 256;
var call_depth = 0;
var last_if: i64 = -1;
var trace = false;
var errexit = false;
var parse_only = false;
var tested = 0;
enum Flow { Normal, Break, Continue, Return }
var flow = Flow.Normal;
var loop_depth = 0;
var function_depth = 0;
var background:       i64[>..]  = [];
var waited:           bool[>..] = [];
var background_codes: i64[>..]  = [];
fn reap_background() {
    for i in background.len {
        if waited[i] || background_codes[i] >= 0 { continue; }
        let code = native_try_wait(background[i]);
        if code >= 0 { background_codes[i] = code; }
    }
}
fn clear_waited() {
    if call_depth != 0 { return; }
    clear_jobs();
    var target = 0;
    for i in background.len {
        if waited[i] { continue; }
        background[target] = background[i];
        background_codes[target] = background_codes[i];
        waited[target] = false;
        target += 1;
    }
    background.resize(target); background_codes.resize(target); waited.resize(target);
}
const SIGNAL_NAMES: const u8[:][8] = ["sighup", "sigint", "sigquit", "sigalrm", "sigfpe", "sigterm", "sigusr1", "sigusr2"];
var in_signal = false;
var interactive_sources = 0;
var source_interrupted = false;
const RC_FLAGS = "cdeiIlmnprsvVx";
var flags: bool[256] = [false; 256];
enum FlagSetting { Clear, Set }
fn set_flag(flag: u8, setting: FlagSetting) {
    let enabled = setting == FlagSetting.Set;
    flags[flag] = enabled;
    if flag == 'x' { trace = enabled; }
    if flag == 'e' { errexit = enabled; }
    if flag == 'n' { parse_only = enabled; }
}
fn trace_node(n: i64) {
    var message: u8[>..] = [];
    format(message, "rc2: node ", n, " ", nodes[n].kind, "\n");
    write(2, message);
}

recursive fn dispatch_signals() {
    if in_signal || stopping || flow != Flow.Normal { return; }
    in_signal = true;
    native_defer(1);
    loop {
        // Finish a default action or explicit exit before another signal can replace it.
        if stopping { break; }
        let signal = native_pending();
        if signal < 0 { break; }
        let body = function(SIGNAL_NAMES[signal]);
        if body >= 0 { execute(body); }
        else {
            status_set(native_signal_code(signal)); stopping = true;
            if interactive_sources > 0 && (SIGNAL_NAMES[signal] == "sigint" || SIGNAL_NAMES[signal] == "sigquit") {
                source_interrupted = true;
            }
        }
    }
    in_signal = false;
    native_defer(0);
    reap_background();
    reap_jobs();
}
recursive fn wait_process(pid: i64) -> i64 {
    loop {
        dispatch_signals();
        if stopping { interrupt_wait(pid); return status; }
        let code = native_wait(pid);
        if code != IO_INTERRUPTED { return code; }
        dispatch_signals();
        if stopping { interrupt_wait(pid); return status; }
    }
    return 1;
}
fn interrupt_wait(pid: i64) {
    if !source_interrupted { return; }
    native_interrupt(pid, status);
    for prior, i in background {
        if prior != pid { continue; }
        waited[i] = false;
        return;
    }
    // A canceled foreground wait still retains its child for later reclamation.
    background.push(pid); waited.push(false); background_codes.push(PROCESS_RUNNING);
}
fn read_line(prompt: u8[:], out: u8[>..]&) -> bool {
    write(2, prompt);
    loop {
        dispatch_signals();
        if stopping { return false; }
        let result = native_line("", out);
        if result != IO_INTERRUPTED { return result > 0 || out.len > 0; }
        dispatch_signals();
        if stopping { return false; }
    }
    return false;
}
fn finish() {
    let code = status;
    let body = function("sigexit");
    if body >= 0 {
        stopping = false; failed = false;
        execute(body);
    }
    native_cooked();
    if job_control { jobs_finish(); }
    native_exit(code);
}

fn environment() -> u8[>..] {
    var out: u8[>..] = [];
    for b, i in bindings {
        if !b.exported || lookup(view(b.name)) != i || b.value.len == 0 { continue; }
        out.append(view(b.name)); out.push('=');
        for j in b.value.len {
            if j > 0 { out.push(1); }
            out.append(bytes(b.value, j));
        }
        out.push(0);
    }
    for f, i in functions {
        if !f.exported || f.body < 0 || definition(view(f.name)) != i { continue; }
        out.append("fn#"); out.append(view(f.name)); out.append("=fn ");
        out.append(view(quote(view(f.name)))); out.append(" {");
        out.append(view(f.source)); out.append("}\x00");
    }
    return out;
}
fn import_function(name: u8[:], source: u8[:]) {
    // Imported text must contain exactly one literal function definition.
    let root = parse(source);
    if parse_error.len != 0 || root < 0 { return; }
    let entry = nodes[root];
    if entry.kind != Kind.Sequence || entry.b >= 0 || entry.a < 0 { return; }
    let f = nodes[entry.a];
    if f.kind != Kind.Function || f.a < 0 || f.b < 0 { return; }
    let word = nodes[f.a];
    if word.kind != Kind.Literal || word.next >= 0 || view(word.text) != name { return; }
    functions.push(Definition { save(name), f.b, f.text });
    trap(name, TrapAction.Handle);
}

enum FileMode { Executable, Source }
enum ProcessMode { Wait, Replace }
enum Dispatch { Normal, Builtin, Exec }

fn resolve(name: Span, mode: FileMode = FileMode.Executable) -> Span {
    let s = view(name);
    if contains(s, '/') { return name; }
    let path = get("path");
    for i in path.len {
        let directory = if item(path, i).text.len == 0 { save(".") } else { item(path, i).text };
        let candidate = concat_span(concat_span(directory, save("/")), name);
        if mode == FileMode.Executable && native_executable(view(candidate)) { return candidate; }
        if mode == FileMode.Source && file_exists(view(candidate)) { return candidate; }
    }
    return Span { 0, 0 };
}
fn command_missing(name: u8[:]) {
    write(2, "rc2: command not found: "); write(2, name); write(2, "\n");
    status_set(127);
}
recursive fn external(args: Values, mode: ProcessMode) {
    dispatch_signals();
    if stopping { return; }
    let path = resolve(item(args, 0).text);
    if path.len == 0 { command_missing(bytes(args, 0)); return; }
    let start = values.len;
    values.push(plain(path));
    for i in 1..args.len { values.push(item(args, i)); }
    if job_control && mode != ProcessMode.Replace {
        let index = job_add(0, join_values(args, " "));
        let pid = fork_job(0, JobMode.Foreground);
        if pid == 0 {
            child_state();
            external(args, ProcessMode.Replace); native_exit(status);
        }
        if pid < 0 { native_job_end(0); status_set(1); return; }
        jobs[index].group = pid;
        job_process(index, pid);
        job_wait(index);
        return;
    }
    var pid = -1;
    {
        let argv = pack(value_end(start));
        let env = environment();
        if mode == ProcessMode.Replace { status_set(native_exec(argv, env)); return; }
        let io: i32[4] = [-1, 0, -1, 1];
        pid = native_spawn(argv, env, io, []);
    }
    if pid < 0 { status_set(-pid); return; }
    status_set(wait_process(pid));
}
fn arg_tail(args: Values, count: i64 = 1) -> Values {
    return Values { args.start + min(count, args.len), max(0, args.len - count) };
}
fn quote(s: u8[:]) -> Span {
    let start = text.len;
    text.push('\'');
    for c in s { text.push(c); if c == '\'' { text.push(c); } }
    text.push('\'');
    return Span { start, text.len - start };
}
const BUILTIN_NAMES: const u8[:][23] = ["echo", "cd", "~", "exit", "eval", "exec", "shift", "wait", "whatis", "builtin", ".", "flag", "rfork", "return", "break", "continue", "umask", "limit", "newpgrp", "jobs", "fg", "bg", "bind"];
fn bind_command(args: Values) {
    if args.len >= 2 && bytes(args, 1) == "-read0" {
        if (args.len != 3 && args.len != 4) || !variable_name(bytes(args, 2)) { diagnostic("usage: bind -read0 variable [file]"); status_set(2); return; }
        let fd = if args.len == 4 { native_source_open(bytes(args, 3)) } else { 0 };
        if fd < 0 { diagnostic("cannot open NUL records"); status_set(2); return; }
        let result, ok = read_records(fd);
        if args.len == 4 { native_close(fd); }
        if stopping { return; }
        if ok { set(item(args, 2).text, result); }
        status_set(if !ok { 2 } else if result.len == 0 { 1 } else { 0 });
        return;
    }
    if args.len >= 2 && bytes(args, 1) == "-history0" {
        if args.len > 3 { diagnostic("usage: bind -history0 [file]"); status_set(2); return; }
        status_set(if history_zero(if args.len == 3 { item(args, 2).text } else { Span { 0, 0 } }) { 0 } else { 1 });
        return;
    }
    if args.len == 1 {
        for binding in key_bindings {
            write(1, "bind "); write(1, view(quote(view(binding.name))));
            write(1, if binding.action == BindAction.Replace { " replace " } else if binding.action == BindAction.Insert { " insert " }
                else if binding.action == BindAction.Token { " token " } else if binding.action == BindAction.Line { " line " } else { " run " });
            write(1, view(quote(view(binding.hook)))); write(1, "\n");
        }
        status_set(0); return;
    }
    let erase = args.len == 3 && bytes(args, 1) == "-e";
    if args.len != 4 && !erase {
        diagnostic("usage: bind [key replace|insert|run|token|line function] | bind -e key"); status_set(2); return;
    }
    let name = item(args, if erase { 2 } else { 1 }).text;
    let key = binding_key(view(name));
    if key < 0 { diagnostic("bind: expected ctrl-a through ctrl-z, or alt-character"); status_set(2); return; }
    let index = key_binding(key);
    if erase {
        if index >= 0 { remove_at(key_bindings, index); }
        status_set(0); return;
    }
    let mode = bytes(args, 2);
    if mode != "replace" && mode != "insert" && mode != "run" && mode != "token" && mode != "line" {
        diagnostic("bind: expected replace, insert, run, token, or line"); status_set(2); return;
    }
    let action = if mode == "replace" { BindAction.Replace } else if mode == "insert" { BindAction.Insert }
        else if mode == "token" { BindAction.Token } else if mode == "line" { BindAction.Line } else { BindAction.Run };
    let binding = KeyBinding { key, action, name, item(args, 3).text };
    if index < 0 { key_bindings.push(binding); } else { key_bindings[index] = binding; }
    status_set(0);
}
fn run_binding(index: i64, line: u8[:], cursor: i64, context: BindingContext) -> BindingResult {
    let binding = key_bindings[index];
    if function(view(binding.hook)) < 0 {
        diagnostic("bind: function not found"); return BindingResult { Values { 0, 0 } };
    }
    var signals: u8[>..] = [];
    if !native_source_enter(signals) { diagnostic("bind: cannot restore signals"); return BindingResult { Values { 0, 0 } }; }
    let scope = scopes.len;
    bind(save("status"), get("status"));
    bind(save("bind_result"), Values { 0, 0 });
    bind(save("bind_cursor"), Values { 0, 0 });
    bind(save("bind_token"), singleton(context.token));
    bind(save("bind_prefix"), singleton(context.prefix));
    bind(save("bind_root"), singleton(context.root));
    bind(save("bind_query"), singleton(context.query));
    bind(save("bind_line"), singleton(save(line[context.line_begin..context.line_end])));
    let start = values.len;
    values.push(plain(binding.hook));
    values.push(plain(save(line)));
    values.push(plain(number(cursor)));
    let args = value_end(start);
    var error: u8[>..] = []; error.append(view(parse_error));
    let incomplete = parse_incomplete;
    let continued = parse_continued;
    let prior_if = last_if;
    failed = false;
    interactive_sources += 1;
    simple(args);
    interactive_sources -= 1;
    var result = BindingResult { Values { 0, 0 } };
    if status == 0 && !failed && !source_interrupted && !stopping {
        result.words = get("bind_result"); result.state = BindingState.Ready;
        let requested = get("bind_cursor");
        if requested.len > 0 {
            let position, valid = parse_int(bytes(requested, 0));
            if requested.len != 1 || !valid || position < 0 {
                diagnostic("bind: invalid cursor"); result.state = BindingState.Blocked;
            } else { result.cursor = position; }
        }
    }
    if source_interrupted { source_interrupted = false; stopping = false; }
    let final_status = get("status");
    native_source_leave(signals);
    unbind(scope);
    if stopping { set(save("status"), final_status); }
    status_sync();
    failed = false;
    last_if = prior_if;
    parse_error = save(error); parse_incomplete = incomplete; parse_continued = continued;
    return result;
}

var in_prompt = false;
var prompt_signals: u8[>..] = [];
var prompt_error: u8[>..] = [];
recursive fn run_prompt() {
    if in_prompt || parse_only || function("prompt") < 0 { return; }
    prompt_signals.clear();
    if !native_source_enter(prompt_signals) { diagnostic("prompt: cannot restore signals"); return; }
    let scope = scopes.len;
    bind(save("status"), get("status"));
    bind(save("prompt"), get("prompt"));
    let prior_status = status;
    let prior_failed = failed;
    let prior_if = last_if;
    let prior_tested = tested;
    prompt_error.clear(); prompt_error.append(view(parse_error));
    let incomplete = parse_incomplete;
    let continued = parse_continued;

    // A prompt failure must not replace the command status or trigger errexit.
    in_prompt = true;
    failed = false;
    tested += 1;
    interactive_sources += 1;
    simple(singleton(save("prompt")));
    interactive_sources -= 1;
    in_prompt = false;
    let success = status == 0 && !failed && !source_interrupted;
    let result = get("prompt");
    if source_interrupted { source_interrupted = false; stopping = false; }
    let final_status = get("status");
    let final_code = status;
    native_source_leave(prompt_signals);
    unbind(scope);
    if success { set(save("prompt"), result); }
    if stopping { set(save("status"), final_status); }
    status = if stopping { final_code } else { prior_status };
    failed = prior_failed;
    tested = prior_tested;
    last_if = prior_if;
    parse_error = save(prompt_error); parse_incomplete = incomplete; parse_continued = continued;
}
fn is_builtin(name: u8[:]) -> bool {
    for builtin in BUILTIN_NAMES { if name == builtin { return true; } }
    return false;
}
enum WhatKind { Variable, Function, Path, Signal, Builtin }
fn what_selected(kinds: WhatKind[:], kind: WhatKind) -> bool {
    if kinds.len == 0 { return true; }
    for selected in kinds { if selected == kind { return true; } }
    return false;
}
fn show_variable(index: i64) {
    let binding = bindings[index];
    write(1, view(quote(view(binding.name)))); write(1, "=(");
    for i in binding.value.len {
        if i > 0 { write(1, " "); }
        write(1, view(quote(bytes(binding.value, i))));
    }
    write(1, ")\n");
}
fn show_function(index: i64) {
    let f = functions[index];
    write(1, "fn "); write(1, view(quote(view(f.name)))); write(1, " {");
    write(1, view(f.source)); write(1, "}\n");
}
fn show_builtin(name: u8[:]) {
    write(1, "builtin "); write(1, name); write(1, "\n");
}
fn signal_name(name: u8[:]) -> bool {
    return native_signal_known(name);
}
fn whatis_command(args: Values) {
    var kinds: WhatKind[>..] = [];
    var first = 1;
    while first < args.len {
        let word = bytes(args, first);
        if word == "--" { first += 1; break; }
        if word.len < 2 || word[0] != '-' { break; }
        for c in word[1..] {
            if c == 'v' { kinds.push(WhatKind.Variable); }
            else if c == 'f' { kinds.push(WhatKind.Function); }
            else if c == 'p' { kinds.push(WhatKind.Path); }
            else if c == 's' { kinds.push(WhatKind.Signal); }
            else if c == 'b' { kinds.push(WhatKind.Builtin); }
            else { diagnostic("usage: whatis [-sfvpb] [--] [name ...]"); status_set(1); return; }
        }
        first += 1;
    }
    if first == args.len {
        if what_selected(kinds, WhatKind.Variable) {
            for b, i in bindings {
                if lookup(view(b.name)) == i && b.value.len > 0 { show_variable(i); }
            }
        }
        if what_selected(kinds, WhatKind.Function) {
            for f, i in functions { if definition(view(f.name)) == i && f.body >= 0 { show_function(i); } }
        }
        if kinds.len > 0 && what_selected(kinds, WhatKind.Signal) {
            var packet: u8[>..] = [];
            native_signal_names(packet);
            let signals = unpack(packet);
            for i in signals.len {
                let name = bytes(signals, i);
                let index = definition(name);
                if index >= 0 && functions[index].body >= 0 { show_function(index); continue; }
                write(1, "fn "); write(1, name);
                if native_signal_ignored(name) { write(1, " {}"); }
                write(1, "\n");
            }
        }
        if kinds.len > 0 && what_selected(kinds, WhatKind.Builtin) { for name in BUILTIN_NAMES { show_builtin(name); } }
        if kinds.len > 0 && what_selected(kinds, WhatKind.Path) { diagnostic("whatis -p: must specify argument"); }
        status_set(0); return;
    }
    var missing = false;
    for i in first..args.len {
        let name = bytes(args, i);
        var found = false;
        let variable = lookup(name);
        if what_selected(kinds, WhatKind.Variable) && variable >= 0 && bindings[variable].value.len > 0 {
            show_variable(variable); found = true;
        }
        // Functions hide builtins and paths. Variables do not hide command definitions.
        let f = definition(name);
        if (what_selected(kinds, WhatKind.Function) || (what_selected(kinds, WhatKind.Signal) && signal_name(name))) && f >= 0 && functions[f].body >= 0 {
            show_function(f); found = true;
        } else if what_selected(kinds, WhatKind.Builtin) && is_builtin(name) {
            show_builtin(name); found = true;
        } else if what_selected(kinds, WhatKind.Path) {
            let path = resolve(item(args, i).text);
            if path.len > 0 { write(1, view(quote(view(path)))); write(1, "\n"); found = true; }
        }
        if found { continue; }
        diagnostic(view(concat_span(item(args, i).text, save(" not found")))); missing = true;
    }
    status_set(if missing { 1 } else { 0 });
}
recursive fn simple(args: Values, dispatch: Dispatch = Dispatch.Normal, mode: ProcessMode = ProcessMode.Wait) {
    if failed { return; }
    if args.len == 0 { status_set(0); return; }
    let name = bytes(args, 0);
    if trace { write(2, view(join_values(args, " "))); write(2, "\n"); }
    let body = function(name);
    if dispatch == Dispatch.Normal && body >= 0 {
        let mark = scopes.len;
        bind(save("*"), arg_tail(args));
        function_depth += 1;
        execute(body, mode);
        function_depth -= 1;
        if flow == Flow.Return { flow = Flow.Normal; }
        unbind(mark);
        return;
    }
    if dispatch == Dispatch.Exec { external(args, ProcessMode.Replace); return; }
    if name == "builtin" { simple(arg_tail(args), Dispatch.Builtin, mode); return; }
    if name == "echo" {
        var first = 1;
        var newline = true;
        if args.len > 1 && bytes(args, 1) == "-n" { first = 2; newline = false; }
        var ok = write(1, view(join_values(arg_tail(args, first), " ")));
        if newline { let ended = write(1, "\n"); ok = ok && ended; }
        if !ok { diagnostic("cannot write standard output"); }
        status_set(if ok { 0 } else { 1 });
        return;
    }
    if name == "~" {
        if args.len < 2 { fail("~ requires a subject"); return; }
        var code = 1;
        for i in 2..args.len {
            if match_text(bytes(args, i), bytes(args, 1)) { code = 0; break; }
        }
        status_set(code);
        return;
    }
    if name == "exit" {
        if args.len > 2 { fail("exit takes one status"); return; }
        if args.len == 2 {
            set(save("status"), singleton(item(args, 1).text));
            status_sync();
        }
        stopping = true;
        return;
    }
    if name == "exec" {
        if args.len == 1 { native_keep_redirects(); status_set(0); return; }
        simple(arg_tail(args), Dispatch.Exec, mode);
        return;
    }
    if name == "return" || name == "break" || name == "continue" {
        if name == "return" {
            if function_depth == 0 { diagnostic("return requires a function"); status_set(1); return; }
            if args.len > 1 { set(save("status"), arg_tail(args)); status_sync(); }
            flow = Flow.Return;
            return;
        }
        if args.len != 1 || loop_depth == 0 { diagnostic("loop control requires an enclosing loop and no arguments"); status_set(1); return; }
        flow = if name == "break" { Flow.Break } else { Flow.Continue };
        return;
    }
    if name == "cd" {
        if args.len > 2 { fail("cd takes one directory"); return; }
        let target = if args.len == 1 { one(get("home")) } else { item(args, 1).text };
        let direct = starts_with(view(target), "/") || view(target) == "." || view(target) == "..";
        var ok = false;
        if direct { ok = native_chdir(view(target)); }
        else {
            let dirs = get("cdpath");
            if dirs.len == 0 { ok = native_chdir(view(target)); }
            for i in dirs.len {
                let directory = if item(dirs, i).text.len == 0 { save(".") } else { item(dirs, i).text };
                let p = concat_span(concat_span(directory, save("/")), target);
                if native_chdir(view(p)) { ok = true; break; }
            }
        }
        if !ok { diagnostic("cannot change directory"); }
        status_set(if ok { 0 } else { 1 });
        return;
    }
    if name == "shift" {
        if args.len > 2 { fail("invalid shift count"); return; }
        let current = get("*");
        var count = min(1, current.len);
        if args.len == 2 {
            let s = bytes(args, 1);
            var start = 0;
            while start < s.len && contains(" \t\r\n\x0b\x0c", s[start]) { start += 1; }
            let negative = start < s.len && s[start] == '-';
            if start < s.len && (s[start] == '-' || s[start] == '+') { start += 1; }
            let number, rest = decimal_prefix(s, start, current.len);
            // Plan 9 consumes a decimal prefix. Excess and negative counts drain the list.
            count = if negative && number != 0 { current.len } else { number };
        }
        set(save("*"), arg_tail(current, count));
        status_set(0);
        return;
    }
    if name == "eval" { run_source(view(join_values(arg_tail(args), " "))); return; }
    if name == "bind" { bind_command(args); return; }
    if name == "." {
        if args.len < 2 { fail(". requires a file"); return; }
        if bytes(args, 1) == "-i" { source_interactive(arg_tail(args, 2)); return; }
        let file = resolve(item(args, 1).text, FileMode.Source);
        let saved = load_source(file);
        if failed || stopping { return; }
        let mark = scopes.len;
        bind(save("*"), arg_tail(args, 2));
        run_source(view(saved), file);
        unbind(mark);
        return;
    }
    if name == "wait" {
        wait_builtin(args);
        return;
    }
    if name == "jobs" || name == "fg" || name == "bg" { job_command(args); return; }
    if name == "rfork" { rfork_builtin(args); return; }
    if name == "umask" { umask_command(args); return; }
    if name == "limit" { limit_command(args); return; }
    if name == "newpgrp" {
        if args.len != 1 { diagnostic("newpgrp takes no arguments"); status_set(1); return; }
        status_set(if native_group() { 0 } else { 1 }); return;
    }
    if name == "whatis" {
        whatis_command(args);
        return;
    }
    if name == "flag" {
        if args.len < 2 || args.len > 3 { fail("flag requires a flag and optional + or -"); return; }
        let flag = bytes(args, 1);
        if flag.len != 1 || !contains(RC_FLAGS, flag[0]) { fail("unsupported flag"); return; }
        if args.len == 3 {
            let value = bytes(args, 2);
            if value != "+" && value != "-" { fail("invalid flag value"); return; }
            set_flag(flag[0], if value == "+" { FlagSetting.Set } else { FlagSetting.Clear });
            status_set(0);
        } else { status_set(if flags[flag[0]] { 0 } else { 1 }); }
        return;
    }
    external(args, mode);
}
recursive fn wait_builtin(args: Values) {
    if args.len > 2 { fail("wait takes one process ID"); return; }
    var target = -1;
    if args.len == 2 {
        let pid, ok = parse_int(bytes(args, 1));
        if !ok || pid <= 0 { fail("invalid process ID"); return; }
        target = pid;
    }
    var code = 0;
    var found = target < 0;
    let job_end = jobs.len;
    for i in job_end {
        if jobs[i].consumed || (target >= 0 && jobs[i].group != target) { continue; }
        found = true;
        job_wait(i);
        code = status;
    }
    let end = background.len;
    for i in end {
        if waited[i] || (target >= 0 && background[i] != target) { continue; }
        found = true;
        waited[i] = true;
        code = if background_codes[i] >= 0 { background_codes[i] } else { wait_process(background[i]) };
    }
    if !found { diagnostic("wait: process is not a child"); code = 1; }
    status_set(code);
}
fn rfork_builtin(args: Values) {
    if args.len > 2 { diagnostic("rfork takes one flag string"); status_set(1); return; }
    let options = if args.len == 1 { "ens" } else { bytes(args, 1) };
    for c in options {
        if !contains("nNeEsfFm", c) { diagnostic("invalid rfork flag"); status_set(1); return; }
        if contains("nNm", c) { diagnostic("rfork namespace flags are unavailable on POSIX"); status_set(1); return; }
    }
    if contains(options, 's') && !native_group() { diagnostic("cannot create a process group"); status_set(1); return; }
    if contains(options, 'F') && !native_empty_fds() { diagnostic("cannot clear the descriptor table"); status_set(1); return; }
    if contains(options, 'E') {
        for i in bindings.len { bindings[i].exported = false; }
        for i in functions.len { functions[i].exported = false; }
    }
    status_set(0);
}
recursive fn execute(n: i64, mode: ProcessMode = ProcessMode.Wait) {
    if n < 0 || failed || stopping || flow != Flow.Normal { return; }
    call_depth += 1;
    if call_depth > MAX_CALL_DEPTH { call_depth -= 1; fail("execution nesting limit exceeded"); return; }
    status_sync();
    if flags['r'] { trace_node(n); }

    // Each evaluation owns its substitution endpoints, including redirection targets.
    let fd_mark = process_fds.len;
    execute_inner(n, mode);
    for i in fd_mark..process_fds.len { native_close(process_fds[i]); }
    process_fds.resize(fd_mark);

    reap_background();
    dispatch_signals();
    status_sync();
    call_depth -= 1;
}
recursive fn execute_inner(n: i64, mode: ProcessMode) {
    let t = nodes[n];
    if t.kind != Kind.Sequence && t.kind != Kind.IfNot { last_if = -1; }
    match t.kind {
        Empty => { status_set(0); },
        Args => { execute_args(t.a); },
        ArgCommand => { fail("command declaration requires an argument block"); },
        Sequence => {
            let mark = pool_mark();
            var cur = n;
            while cur >= 0 && !failed && !stopping && flow == Flow.Normal {
                let entry = nodes[cur];
                execute(entry.a, if entry.b < 0 { mode } else { ProcessMode.Wait });
                cur = entry.b;
                collect(mark);
            }
        },
        Simple => {
            let args = expand_words(t.a);
            let raw = args.len > 0 && bytes(args, 0) == "~";
            simple(if raw { args } else { glob_values(args) }, Dispatch.Normal, mode);
            if flags['s'] && status != 0 {
                write(2, "status="); write(2, view(join_values(get("status"), " "))); write(2, "\n");
            }
            if errexit && tested == 0 && status != 0 { stopping = true; }
        },
        Assign => {
            let name = one(expand(t.a));
            let val = glob_values(expand(t.b));
            if failed { return; }
            if t.d < 0 { set(name, val); execute(t.c, mode); return; }
            let mark = scopes.len;
            bind(name, val);
            execute(t.c, mode);
            unbind(mark);
        },
        Redirect => {
            let spec, valid = redir_spec(view(t.text));
            if !valid { fail("invalid redirection descriptor"); return; }
            var target = save("");
            if t.a >= 0 { target = one(glob_values(expand(t.a))); }
            if failed { return; }
            if t.b == HERE_EXPAND || t.b == HERE_FUNCTION { target = here_expand(view(target)); }
            let handle = redirect(spec, view(target));
            if handle < 0 { fail("redirection failed"); return; }
            execute(t.c, mode);
            restore_redirect(handle, process_fds);
        },
        And => {
            tested += 1; execute(t.a); tested -= 1;
            if status == 0 { execute(t.b, mode); }
        },
        Or => {
            tested += 1; execute(t.a); tested -= 1;
            if status != 0 { execute(t.b, mode); }
        },
        Not => {
            tested += 1; execute(t.a); tested -= 1;
            status_set(if status == 0 { 1 } else { 0 });
        },
        If => {
            tested += 1; execute(t.a); tested -= 1;
            let condition = status;
            if condition == 0 { execute(t.b, mode); }
            last_if = condition;
        },
        IfNot => {
            if last_if < 0 { fail("if not requires a preceding if"); return; }
            let condition = last_if;
            last_if = -1;
            if condition != 0 { execute(t.a, mode); }
        },
        While => {
            let mark = pool_mark();
            loop_depth += 1;
            loop {
                tested += 1; execute(t.a); tested -= 1;
                if flow == Flow.Break || flow == Flow.Return || failed || stopping { break; }
                if flow == Flow.Continue { flow = Flow.Normal; continue; }
                if status != 0 { break; }
                execute(t.b);
                collect(mark);
                if flow == Flow.Break || flow == Flow.Return { break; }
                if flow == Flow.Continue { flow = Flow.Normal; }
            }
            loop_depth -= 1;
            if flow == Flow.Break { flow = Flow.Normal; }
        },
        For => {
            let name = one(expand(t.c));
            let args = if t.a < 0 { get("*") } else { glob_values(expand(t.a)) };
            let mark = pool_mark();
            loop_depth += 1;
            for i in args.len {
                if failed || stopping || flow == Flow.Break || flow == Flow.Return { break; }
                if flow == Flow.Continue { flow = Flow.Normal; }
                set(name, Values { args.start + i, 1 });
                execute(t.b);
                collect(mark);
            }
            loop_depth -= 1;
            if flow == Flow.Break || flow == Flow.Continue { flow = Flow.Normal; }
        },
        Function => {
            let names = expand_words(t.a);
            for i in names.len {
                let name = item(names, i).text;
                functions.push(Definition { name, t.b, t.text });
                trap(view(name), if t.b < 0 { TrapAction.Default } else { TrapAction.Handle });
            }
        },
        Switch => { switch_run(one(expand(t.a)), t.b); },
        Subshell => {
            let index = if job_control { job_add(0, save("subshell")) } else { -1 };
            let pid = if job_control { fork_job(0, JobMode.Foreground) } else { native_fork() };
            if pid == 0 { child_state(); execute(t.a, ProcessMode.Replace); native_exit(status); }
            if pid < 0 { fail("cannot fork"); return; }
            if index >= 0 { jobs[index].group = pid; job_process(index, pid); job_wait(index); return; }
            status_set(wait_process(pid));
        },
        Background => {
            let index = if job_control { job_add(0, save("background command")) } else { -1 };
            let pid = if job_control { fork_job(0, JobMode.Background) } else { native_fork() };
            if pid == 0 { child_state(); execute(t.a, ProcessMode.Replace); native_exit(status); }
            if pid < 0 { fail("cannot fork"); return; }
            if index >= 0 { jobs[index].group = pid; job_process(index, pid); }
            else { background.push(pid); waited.push(false); background_codes.push(PROCESS_RUNNING); }
            set(save("apid"), singleton(number(pid)));
        },
        Pipe => { pipeline_run(n); },
        _ => { fail("invalid command node"); },
    }
}
fn execute_args(body: i64) {
    var parsed: ParsedBinding[>..] = [];
    var output: u8[>..]            = [];
    let program = if script_name.len > 0 { script_name } else { save("rc2") };
    let result = parse_declaration(body, program, get("*"), parsed, output);
    if result.state == DeclarationState.Error {
        diagnostic(view(result.error)); status_set(2); stopping = true;
        return;
    }
    if output.len > 0 { write(1, output); }
    for binding in parsed { set(binding.name, binding.value); }
    status_set(0);
    if result.state == DeclarationState.Stop { stopping = true; }
}
struct PipeStage { node: i64, input: i64 = 0, output: i64 = 1 }
enum WalkMode { Visit, Edge }
struct PipeWalk { node: i64, mode: WalkMode }
var pipe_stages: PipeStage[>..] = [];
var pipe_fds:    i32[>..]       = [];
var pipe_pids:   i64[>..]       = [];
var pipe_codes:  i64[>..]       = [];

fn pipe_ends(op: u8[:]) -> i64, i64 {
    var output = 1;
    var input = 0;
    let bracket = position(op, '[');
    if bracket >= 0 {
        let qualifier = op[bracket + 1..op.len - 1];
        let equal = position(qualifier, '=');
        if equal < 0 { output = descriptor(qualifier); }
        else {
            input = descriptor(qualifier[..equal]);
            output = descriptor(qualifier[equal + 1..]);
        }
        if output < 0 || input < 0 { fail("invalid pipe descriptor"); }
    }
    return input, output;
}
fn collect_pipe(root: i64) {
    // In-order traversal makes one process per stage, even for long pipelines.
    var todo: PipeWalk[>..<] = [];
    todo.push(PipeWalk { root, WalkMode.Visit });
    var input = 0;
    while todo.len > 0 && !failed {
        let work = todo.pop();
        let t = nodes[work.node];
        if work.mode == WalkMode.Edge {
            let next, output = pipe_ends(view(t.text));
            pipe_stages[pipe_stages.len - 1].output = output;
            input = next;
            continue;
        }
        if t.kind != Kind.Pipe { pipe_stages.push(PipeStage { node: work.node, input: input }); continue; }
        todo.push(PipeWalk { t.b, WalkMode.Visit });
        todo.push(PipeWalk { work.node, WalkMode.Edge });
        todo.push(PipeWalk { t.a, WalkMode.Visit });
    }
}
recursive fn pipeline_run(root: i64) {
    let job = if job_control { job_add(0, save("pipeline")) } else { -1 };
    var group = 0;
    let stage_start = pipe_stages.len;
    let fd_start = pipe_fds.len;
    let pid_start = pipe_pids.len;
    collect_pipe(root);
    let count = pipe_stages.len - stage_start;
    if failed { pipe_stages.resize(stage_start); return; }
    for i in count - 1 {
        var fds: i32[2] = [0, 0];
        if !native_pipe(fds) { fail("cannot create a pipe"); break; }
        pipe_fds.append(fds);
    }
    if !failed {
        for i in count {
            let stage = pipe_stages[stage_start + i];
            let input = if i == 0 { -1 } else { pipe_fds[fd_start + (i - 1) * 2] };
            let output = if i + 1 == count { -1 } else { pipe_fds[fd_start + i * 2 + 1] };
            let io: i32[4] = [input, stage.input as i32, output, stage.output as i32];
            var pid = spawn_stage(stage.node, io, fd_start);
            if pid == -1 { pid = if job_control { fork_job(group, JobMode.Foreground) } else { native_fork() }; }
            if pid == 0 {
                child_state();
                if !native_pipe_io(io, pipe_fds[fd_start..]) { native_exit(1); }
                execute(stage.node, ProcessMode.Replace); native_exit(status);
            }
            if job >= 0 && pid > 0 {
                if group == 0 { group = pid; jobs[job].group = pid; }
                job_process(job, pid);
            }
            pipe_pids.push(if pid > 0 { pid } else { 0 });
            pipe_codes.push(if pid < 0 { -pid } else { 0 });
        }
    }
    for i in fd_start..pipe_fds.len { native_close(pipe_fds[i]); }
    pipe_fds.resize(fd_start);
    if job >= 0 {
        job_wait(job);
        pipe_pids.resize(pid_start); pipe_codes.resize(pid_start); pipe_stages.resize(stage_start);
        return;
    }
    for i in pid_start..pipe_pids.len {
        if pipe_pids[i] > 0 {
            let code = wait_process(pipe_pids[i]);
            pipe_codes[i] = code;
        }
    }
    if !failed {
        let start = text.len;
        for i in pid_start..pipe_pids.len {
            if i > pid_start { text.push('|'); }
            if pipe_codes[i] != 0 { format(text, pipe_codes[i]); }
        }
        set(status_name, singleton(Span { start, text.len - start }));
        status_sync();
    }
    pipe_pids.resize(pid_start); pipe_codes.resize(pid_start);
    pipe_stages.resize(stage_start);
}
recursive fn safe_word(n: i64) -> bool {
    if n < 0 { return true; }
    let t = nodes[n];
    match t.kind {
        Literal => { return true; },
        Variable => { return safe_word(t.a) && safe_words(t.b); },
        Count => { return safe_word(t.a); },
        Join => { return safe_word(t.a); },
        Concat => { return safe_word(t.a) && safe_word(t.b); },
        List => { return safe_words(t.a); },
        _ => { return false; },
    }
}
recursive fn safe_words(first: i64) -> bool {
    var n = first;
    while n >= 0 {
        if !safe_word(n) { return false; }
        n = nodes[n].next;
    }
    return true;
}
fn spawn_stage(n: i64, io: const i32[4]&, closing_start: i64) -> i64 {
    if job_control { return -1; }
    let t = nodes[n];
    if t.kind != Kind.Simple || nodes[t.a].kind != Kind.Literal || !safe_words(t.a) { return -1; }
    let name = view(nodes[t.a].text);
    if is_builtin(name) || function(name) >= 0 { return -1; }
    // Pure expansion can precede spawn. Substitutions stay inside the child evaluator.
    let args = glob_values(expand_words(t.a));
    if failed || args.len == 0 { return -126; }
    if trace { write(2, view(join_values(args, " "))); write(2, "\n"); }
    let path = resolve(item(args, 0).text);
    if path.len == 0 { command_missing(bytes(args, 0)); return -127; }
    let start = values.len;
    values.push(plain(path));
    for i in 1..args.len { values.push(item(args, i)); }
    let argv = pack(value_end(start));
    let env = environment();
    return native_spawn(argv, env, io, pipe_fds[closing_start..]);
}

// Flatten only the top-level sequence. Nested case words do not select a branch.
var statements: i64[>..] = [];
recursive fn flatten(n: i64) {
    if n < 0 { return; }
    if nodes[n].kind != Kind.Sequence { statements.push(n); return; }
    var cur = n;
    while cur >= 0 { statements.push(nodes[cur].a); cur = nodes[cur].b; }
}
recursive fn switch_run(subject: Span, body: i64) {
    let start = statements.len;
    flatten(body);
    let end = statements.len;
    var active = false;
    for i in start..end {
        let n = nodes[statements[i]];
        if n.kind == Kind.Simple && nodes[n.a].kind == Kind.Literal && view(nodes[n.a].text) == "case" {
            if active { break; }
            let patterns = expand_words(nodes[n.a].next);
            for j in patterns.len {
                if match_text(bytes(patterns, j), view(subject)) { active = true; break; }
            }
            continue;
        }
        if active { execute(statements[i]); }
    }
    statements.resize(start);
}
var source_text: u8[>..] = [];
recursive fn load_source(file: Span) -> Span {
    let fd = native_source_open(view(file));
    if fd < 0 { fail("cannot read source file"); return Span { 0, 0 }; }
    let start = source_text.len;
    loop {
        dispatch_signals();
        if stopping || failed { break; }
        let result = native_read(fd, source_text);
        if result == IO_INTERRUPTED { continue; }
        if result == IO_ERROR { fail("cannot read source file"); }
        break;
    }
    native_close(fd);
    // Nested traps share the source buffer but restore their own suffix before return.
    let saved = if failed || stopping { Span { 0, 0 } } else { save(source_text[start..]) };
    source_text.resize(start);
    return saved;
}
recursive fn source_interactive(args: Values) {
    if args.len == 0 { return; }
    let file = resolve(item(args, 0).text, FileMode.Source);
    let fd = native_source_open(view(file));
    if fd < 0 { diagnostic("cannot read source file"); status_set(1); return; }
    var signals = Span { 0, 0 };
    {
        var state: u8[>..] = [];
        if !native_source_enter(state) { native_close(fd); fail("cannot enter interactive source mode"); return; }
        signals = save(state);
    }
    interactive_sources += 1;
    let scope = scopes.len;
    bind(save("*"), arg_tail(args));
    let prior = flags['i'];
    let prior_function = function_depth;
    let prior_loop = loop_depth;
    function_depth = 0;
    loop_depth = 0;
    set_flag('i', FlagSetting.Set);
    let start = source_text.len;
    let mark = pool_mark();
    {
        var continuation = false;
        var pending = -1;
        var pending_start = nodes.len;
        loop {
            if !continuation { run_prompt(); }
            if stopping { break; }
            let prompts = get("prompt");
            let part = if continuation && prompts.len > 1 { 1 } else { 0 };
            if prompts.len > 0 {
                var output: u8[>..] = [];
                append_display(output, bytes(prompts, part), DisplayMode.Prompt);
                write(2, output);
            }
            let line_start = source_text.len;
            var result = IO_INTERRUPTED;
            while result == IO_INTERRUPTED && !stopping {
                dispatch_signals();
                if stopping { break; }
                result = native_source_line(fd, source_text);
            }
            if recover_source(start) { continuation = false; pending = -1; continue; }
            if stopping { break; }
            if result == IO_ERROR { diagnostic("cannot read source file"); status_set(1); break; }
            if result == 0 && source_text.len == line_start {
                if continuation {
                    if parse_error.len == 0 && parse_continued {
                        execute_input(pending, pending_start);
                    } else { fail("incomplete command at end of input"); }
                }
                if recover_source(start) { continuation = false; pending = -1; continue; }
                break;
            }
            if flags['v'] { write(2, source_text[line_start..]); }
            failed = false;
            pending_start = nodes.len;
            let root = parse(source_text[start..]);
            pending = root;
            continuation = (parse_error.len > 0 && parse_incomplete) || parse_continued;
            if continuation { continue; }
            if parse_error.len > 0 { fail(view(parse_error)); }
            else { execute_input(root, pending_start); }
            source_text.resize(start);
            collect(mark);
            clear_waited();
            failed = false;
            if recover_source(start) { continuation = false; pending = -1; continue; }
            if stopping || flow != Flow.Normal { break; }
        }
    }
    source_text.resize(start);
    interactive_sources -= 1;
    native_source_leave(view(signals));
    // Interactive input recovers from errors without changing the caller's input mode.
    failed = false;
    set_flag('i', if prior { FlagSetting.Set } else { FlagSetting.Clear });
    function_depth = prior_function;
    loop_depth = prior_loop;
    unbind(scope);
    native_close(fd);
}
fn recover_source(start: i64) -> bool {
    if !source_interrupted { return false; }
    source_interrupted = false;
    stopping = false;
    failed = false;
    source_text.resize(start);
    write(2, "\n");
    return true;
}
recursive fn execute_input(root: i64, first: i64) {
    if parse_only { return; }
    // Freeze bodies before any command in this input unit can change their variables.
    for i in first..nodes.len {
        let t = nodes[i];
        if t.kind != Kind.Redirect || t.b != HERE_EXPAND { continue; }
        let body = here_expand(view(nodes[t.a].text));
        nodes[t.a].text = body;
        nodes[i].b = HERE_LITERAL;
    }
    execute(root);
}
recursive fn run_source(source: u8[:], path: Span = Span { 0, 0 }) {
    let start = source_text.len;
    source_text.append(source);
    run_owned(Span { start, source.len }, path);
    source_text.resize(start);
}
recursive fn run_owned(source: Span, path: Span) {
    let mark = pool_mark();
    if flags['v'] { write(2, source_text[source.start..source.start + source.len]); }
    var begin = 0;
    var line = 1;
    for i in source.len {
        let c = source_text[source.start + i];
        if c != '\n' && i + 1 < source.len { continue; }
        let end = i + 1;
        let first = nodes.len;
        let n = parse(source_text[source.start + begin..source.start + end], line, path);
        if parse_continued && end < source.len { continue; }
        if parse_error.len > 0 && parse_incomplete && end < source.len { continue; }
        if parse_error.len > 0 { fail(view(parse_error)); return; }
        execute_input(n, first);
        collect(mark);
        clear_waited();
        if failed || stopping || flow != Flow.Normal { return; }
        for j in begin..end { if source_text[source.start + j] == '\n' { line += 1; } }
        begin = end;
    }
}