safe_chains/cst/

parse.rs

use super::*;
use super::budget::{self, DepthGuard};
use winnow::ModalResult;
use winnow::combinator::{alt, delimited, not, opt, preceded, repeat, separated, terminated};
use winnow::error::{ContextError, ErrMode};
use winnow::prelude::*;
use winnow::token::{any, take_while};

pub fn parse(input: &str) -> Option<Script> {
    reset_heredoc_queue();
    budget::reset(input.len());
    let result = script.parse(input).ok().filter(|_| !budget::spent());
    reset_heredoc_queue();
    result
}

fn backtrack<T>() -> ModalResult<T> {
    Err(ErrMode::Backtrack(ContextError::new()))
}

/// Charge one parsing attempt; over budget it fails, and `parse` then refuses.
fn step() -> ModalResult<()> {
    if budget::charge(1, 0) { Ok(()) } else { backtrack() }
}

/// Charge `bytes` consumed or looked ahead at, outside any counted attempt.
fn scan(bytes: usize) -> ModalResult<()> {
    if budget::charge(0, bytes) { Ok(()) } else { backtrack() }
}

/// Run a parser, charging the step budget for what it consumed.
fn consumed<'a, O>(
    input: &mut &'a str,
    p: impl FnOnce(&mut &'a str) -> ModalResult<O>,
) -> ModalResult<O> {
    let before = input.len();
    let out = p(input);
    scan(before - input.len())?;
    out
}

fn comment(input: &mut &str) -> ModalResult<()> {
    if input.starts_with('#') {
        if let Some(pos) = input.find('\n') {
            *input = &input[pos + 1..];
        } else {
            *input = "";
        }
    }
    Ok(())
}

fn ws(input: &mut &str) -> ModalResult<()> {
    consumed(input, ws_raw)
}

fn ws_raw(input: &mut &str) -> ModalResult<()> {
    loop {
        take_while(0.., [' ', '\t']).void().parse_next(input)?;
        if input.starts_with('#') {
            comment(input)?;
        } else {
            break;
        }
    }
    Ok(())
}

fn sep(input: &mut &str) -> ModalResult<()> {
    consumed(input, sep_raw)
}

fn sep_raw(input: &mut &str) -> ModalResult<()> {
    loop {
        // Consume separators one at a time so a `;;` stays intact: it terminates a case arm, and
        // eating its first `;` here would let the arm's body run on into the next arm's pattern.
        while let Some(c) = input.chars().next() {
            if input.starts_with(";;") {
                return Ok(());
            }
            if !matches!(c, ' ' | '\t' | ';' | '\n') {
                break;
            }
            *input = &input[c.len_utf8()..];
        }
        if input.starts_with('#') {
            comment(input)?;
        } else {
            break;
        }
    }
    Ok(())
}

fn eat_keyword(input: &mut &str, kw: &str) -> ModalResult<()> {
    if !input.starts_with(kw) {
        return backtrack();
    }
    if input
        .as_bytes()
        .get(kw.len())
        .is_some_and(|&b| b.is_ascii_alphanumeric() || b == b'_')
    {
        return backtrack();
    }
    *input = &input[kw.len()..];
    Ok(())
}

const SCRIPT_STOPS: &[&str] = &["do", "done", "elif", "else", "esac", "fi", "then"];

fn at_script_stop(input: &str) -> bool {
    input.starts_with(')')
        || input.starts_with('}')
        // `;;` ends a case arm's body. Without this a body script would run on into the next arm's
        // pattern and read it as a command.
        || input.starts_with(";;")
        || SCRIPT_STOPS.iter().any(|kw| {
            input.starts_with(kw)
                && !input
                    .as_bytes()
                    .get(kw.len())
                    .is_some_and(|&b| b.is_ascii_alphanumeric() || b == b'_')
        })
}

fn is_word_boundary(c: char) -> bool {
    matches!(c, ' ' | '\t' | '\n' | ';' | '|' | '&' | ')' | '>' | '<')
}

fn is_word_literal(c: char) -> bool {
    !is_word_boundary(c) && !matches!(c, '\'' | '"' | '`' | '\\' | '(' | '$')
}

fn is_dq_literal(c: char) -> bool {
    !matches!(c, '"' | '\\' | '`' | '$')
}

// === Script ===

fn script(input: &mut &str) -> ModalResult<Script> {
    // Bound recursion depth: every nested `(`/`{`/`$(`/`<(`/`` ` `` funnels back through `script`,
    // so this one guard caps stack depth against deeply-nested adversarial input (see `budget`).
    let Some(_depth) = DepthGuard::enter() else {
        return backtrack();
    };
    sep.parse_next(input)?;
    let mut stmts = Vec::new();
    while let Some(pl) = opt(pipeline).parse_next(input)? {
        ws.parse_next(input)?;
        let op = opt(list_op).parse_next(input)?;
        stmts.push(Stmt { pipeline: pl, op });
        // Drain any heredoc bodies pending from this statement before
        // the next pipeline starts; otherwise the body would be parsed
        // as the next statement (which would either misvalidate or
        // misalign the line counter).
        drain_pending_heredocs(input);
        if op.is_none() {
            break;
        }
        sep.parse_next(input)?;
    }
    Ok(Script(stmts))
}

fn list_op(input: &mut &str) -> ModalResult<ListOp> {
    ws.parse_next(input)?;
    alt((
        "&&".value(ListOp::And),
        "||".value(ListOp::Or),
        '\n'.value(ListOp::Semi),
        // `;;` is a case-arm terminator, not a statement separator — matching the first `;` here
        // would let the body swallow it and continue into the next arm.
        (';', not(';')).value(ListOp::Semi),
        ('&', not('>')).value(ListOp::Amp),
    ))
    .parse_next(input)
}

/// A pipe. `|&` (bash) pipes stdout AND stderr into the next command; what flows through the pipe
/// does not change which commands run, so it classifies exactly as `|`. Matched before the bare
/// `|` so the `&` is not left to start a bogus background statement. `||` stays an OR, not a pipe.
fn pipe_sep(input: &mut &str) -> ModalResult<()> {
    (ws, alt(("|&".void(), ('|', not('|')).void())), ws).void().parse_next(input)
}

// === Pipeline ===

fn pipeline(input: &mut &str) -> ModalResult<Pipeline> {
    ws.parse_next(input)?;
    if at_script_stop(input) {
        return backtrack();
    }
    let bang = opt(terminated('!', ws)).parse_next(input)?.is_some();
    opt_time_keyword_before_compound(input);
    let commands: Vec<Cmd> = separated(1.., command, pipe_sep).parse_next(input)?;
    Ok(Pipeline { bang, commands })
}

/// Consume a leading `time` / `time -p` when it prefixes a COMPOUND command.
///
/// `time` is a shell reserved word, not just `/usr/bin/time`: bash lets it prefix a whole pipeline
/// or compound, so `time (cmd)` and `time { cmd; }` are ordinary shell. The parser only ever
/// offered `time` to `simple_cmd`, which wants a command NAME, so those forms did not parse at all
/// and fell to "could not parse this command" — fail-closed, but a prompt for valid shell that was
/// reported from real use.
///
/// NOT handled, deliberately: `time ! (cmd)`. bash accepts the keyword and the `!` in either order
/// (`bash -n` validates all four spellings), and the caller parses the bang first, so a bang
/// BETWEEN `time` and the compound leaves nothing this can commit on. `time ! ls` — the simple
/// form — does work, through the wrapper entry, so the two spellings genuinely disagree. It stays
/// unfixed because the fix is not local: the helper would have to consume the bang itself and hand
/// it back for `Pipeline.bang`, which means editing the shared `pipeline()` path that every command
/// in the corpus goes through. That is a poor trade against a form nobody writes, and the failure
/// is a prompt, not a hole — `time ! (rm -rf /)` denies, as does every other spelling of it.
///
/// Deliberately narrow: it commits ONLY when a `(` or `{` follows. `time ls` keeps going through
/// the existing `[command.wrapper]` entry in `commands/wrappers/time.toml`, which already handles
/// the simple-command form and its `-p` flag, so nothing that parses today changes shape. Widening
/// this to consume `time` unconditionally would work too, but it would silently retire that wrapper
/// entry for the bare spelling, and a maintenance fix should not move a path that already works.
fn opt_time_keyword_before_compound(input: &mut &str) -> bool {
    let mut probe = *input;
    if eat_keyword(&mut probe, "time").is_err() || !probe.starts_with([' ', '\t', '\n']) {
        return false;
    }
    if ws.parse_next(&mut probe).is_err() {
        return false;
    }
    // `time -p (…)` — the POSIX output flag, the only one the keyword form takes.
    if probe.starts_with("-p") {
        let mut with_flag = &probe[2..];
        if with_flag.starts_with([' ', '\t', '\n']) && ws.parse_next(&mut with_flag).is_ok() {
            probe = with_flag;
        }
    }
    if !probe.starts_with(['(', '{']) {
        return false;
    }
    *input = probe;
    true
}

// === Command ===

fn command(input: &mut &str) -> ModalResult<Cmd> {
    step()?;
    ws.parse_next(input)?;
    if at_script_stop(input) {
        return backtrack();
    }
    let committed = super::reserved::opens_compound(input);
    alt((
        subshell, brace_group, for_cmd, while_cmd, until_cmd, if_cmd, case_cmd, double_bracket_cmd,
        function_def,
        move |i: &mut &str| {
            if committed { backtrack() } else { simple_cmd.map(Cmd::Simple).parse_next(i) }
        },
    ))
    .parse_next(input)
}

/// `name() { body }` / `name() ( body )` (POSIX form) or `function name [()] { body }` (bash form).
/// Tried before `simple_cmd`; a bare `name` with no `()` and no `function` keyword backtracks so an
/// ordinary command is not misread as a definition.
fn function_def(input: &mut &str) -> ModalResult<Cmd> {
    let had_keyword = opt_function_keyword(input);
    let name = function_name(input)?;
    ws.parse_next(input)?;
    let has_parens = opt_paren_pair(input);
    if !had_keyword && !has_parens {
        return backtrack();
    }
    // The body may sit on the next line (`foo()\n{ … }`); consume ws/newlines but not `;`.
    blank(input)?;
    let body = function_body(input)?;
    Ok(Cmd::FunctionDef { name, body })
}

/// Consume a leading `function` keyword (must be followed by whitespace, else it's a command named
/// `function`). Returns whether it was present; only commits `*input` when it was.
fn opt_function_keyword(input: &mut &str) -> bool {
    let mut probe = *input;
    if eat_keyword(&mut probe, "function").is_ok()
        && probe.starts_with([' ', '\t', '\n'])
        && ws.parse_next(&mut probe).is_ok()
    {
        *input = probe;
        return true;
    }
    false
}

/// Consume a `(` ws `)` function-def paren pair. Commits `*input` only on a full match.
fn opt_paren_pair(input: &mut &str) -> bool {
    let mut probe = *input;
    if let Some(rest) = probe.strip_prefix('(') {
        probe = rest;
        if ws.parse_next(&mut probe).is_ok()
            && let Some(rest) = probe.strip_prefix(')')
        {
            *input = rest;
            return true;
        }
    }
    false
}

fn function_name(input: &mut &str) -> ModalResult<String> {
    run(input, |c| c.is_ascii_alphanumeric() || matches!(c, '_' | '-' | '.' | ':' | '+')).map(String::from)
}

/// A non-empty run of `pred` characters, charged to the step budget.
fn run<'a>(input: &mut &'a str, pred: fn(char) -> bool) -> ModalResult<&'a str> {
    consumed(input, |i| take_while(1.., pred).parse_next(i))
}

/// The compound body of a function — `{ …; }` or `( … )`. Redirects attached to the definition
/// itself (rare) are dropped, which is conservative for a construct classified Inert anyway.
fn function_body(input: &mut &str) -> ModalResult<Script> {
    if let Some(Cmd::BraceGroup { body, .. }) = opt(brace_group).parse_next(input)? {
        return Ok(body);
    }
    if let Some(Cmd::Subshell { body, .. }) = opt(subshell).parse_next(input)? {
        return Ok(body);
    }
    backtrack()
}

fn trailing_redirs(input: &mut &str) -> ModalResult<Vec<Redir>> {
    let mut redirs = Vec::new();
    loop {
        ws.parse_next(input)?;
        if let Some(r) = opt(redirect).parse_next(input)? {
            redirs.push(r);
        } else {
            break;
        }
    }
    Ok(redirs)
}

fn subshell(input: &mut &str) -> ModalResult<Cmd> {
    let body = delimited(('(', ws), script, (ws, ')')).parse_next(input)?;
    let redirs = trailing_redirs(input)?;
    Ok(Cmd::Subshell { body, redirs })
}

fn brace_group(input: &mut &str) -> ModalResult<Cmd> {
    if !input.starts_with('{') {
        return backtrack();
    }
    if !input
        .as_bytes()
        .get(1)
        .is_some_and(|b| matches!(b, b' ' | b'\t' | b'\n'))
    {
        return backtrack();
    }
    *input = &input[1..];
    sep.parse_next(input)?;
    let body = script.parse_next(input)?;
    if body.0.is_empty() {
        return backtrack();
    }
    sep.parse_next(input)?;
    if !input.starts_with('}') {
        return backtrack();
    }
    let last_op = body.0.last().and_then(|s| s.op);
    if last_op.is_none() {
        return backtrack();
    }
    *input = &input[1..];
    let redirs = trailing_redirs(input)?;
    Ok(Cmd::BraceGroup { body, redirs })
}

// === Simple Command ===

fn simple_cmd(input: &mut &str) -> ModalResult<SimpleCmd> {
    let env: Vec<(String, Word)> =
        repeat(0.., terminated(assignment, ws)).parse_next(input)?;
    let mut words = Vec::new();
    let mut redirs = Vec::new();

    loop {
        ws.parse_next(input)?;
        if at_cmd_end(input) {
            break;
        }
        if let Some(r) = opt(redirect).parse_next(input)? {
            redirs.push(r);
        } else if let Some(w) = opt(word).parse_next(input)? {
            words.push(w);
        } else {
            break;
        }
    }

    if env.is_empty() && words.is_empty() && redirs.is_empty() {
        return backtrack();
    }
    Ok(SimpleCmd { env, words, redirs })
}

fn at_cmd_end(input: &str) -> bool {
    // `&>`/`&>>` REDIRECT this command; only a bare `&` backgrounds it and ends it. Without this
    // the command stopped at the `&` and the redirect parser never saw the operator at all.
    if input.starts_with("&>") {
        return false;
    }
    input.is_empty()
        || matches!(
            input.as_bytes().first(),
            Some(b'\n' | b';' | b'|' | b'&' | b')')
        )
}

fn assignment(input: &mut &str) -> ModalResult<(String, Word)> {
    let n = run(input, |c| c.is_ascii_alphanumeric() || c == '_')?;
    '='.parse_next(input)?;
    let value = opt(word)
        .parse_next(input)?
        .unwrap_or(Word(vec![WordPart::Lit(String::new())]));
    Ok((n.to_string(), value))
}

// === Redirect ===

fn redirect(input: &mut &str) -> ModalResult<Redir> {
    let fd = opt(fd_prefix).parse_next(input)?;
    alt((
        preceded("<<<", (ws, word)).map(|(_, target)| Redir::HereStr(target)),
        heredoc,
        preceded(">>", (ws, word)).map(move |(_, target)| Redir::Write {
            fd: fd.unwrap_or(1),
            target,
            mode: WriteMode::Append,
        }),
        // `&>>` / `&>` send stdout AND stderr to a FILE (bash). `&>` must follow `&>>` so the
        // append form is not read as a truncate followed by a stray `>`.
        preceded("&>>", (ws, word)).map(|(_, target)| Redir::Write {
            fd: 1,
            target,
            mode: WriteMode::AppendBoth,
        }),
        preceded("&>", (ws, word)).map(|(_, target)| Redir::Write {
            fd: 1,
            target,
            mode: WriteMode::TruncateBoth,
        }),
        preceded(">&", fd_target).map(move |dst| Redir::DupFd {
            src: fd.unwrap_or(1),
            dst,
        }),
        // `>&WORD` where WORD is not a file descriptor is the older spelling of `&>`: it opens a
        // FILE for both streams. It must follow the `>&`-fd form, so `>&2` stays a descriptor dup
        // rather than a write to a file named `2`.
        preceded(">&", (ws, word)).map(|(_, target)| Redir::Write {
            fd: 1,
            target,
            mode: WriteMode::TruncateBoth,
        }),
        // `>|` (POSIX 2.7.2) overrides `noclobber`. The override is about whether the shell
        // REFUSES an existing file, not about what lands there, so it classifies as the plain
        // overwrite it is. Must precede `>` or the `|` reads as a pipe into an empty command.
        preceded(">|", (ws, word)).map(move |(_, target)| Redir::Write {
            fd: fd.unwrap_or(1),
            target,
            mode: WriteMode::Clobber,
        }),
        preceded('>', (ws, word)).map(move |(_, target)| Redir::Write {
            fd: fd.unwrap_or(1),
            target,
            mode: WriteMode::Truncate,
        }),
        // `<>` (POSIX 2.7.5) opens the target for BOTH reading and writing. Must precede `<`,
        // which would otherwise match and leave `>` to start a bogus second redirect.
        preceded("<>", (ws, word)).map(move |(_, target)| Redir::ReadWrite {
            fd: fd.unwrap_or(0),
            target,
        }),
        preceded('<', (ws, word)).map(move |(_, target)| Redir::Read {
            fd: fd.unwrap_or(0),
            target,
        }),
    ))
    .parse_next(input)
}

fn heredoc(input: &mut &str) -> ModalResult<Redir> {
    "<<".parse_next(input)?;
    let strip_tabs = opt('-').parse_next(input)?.is_some();
    ws.parse_next(input)?;
    let before = input.len();
    let delimiter = heredoc_delimiter.parse_next(input);
    scan(if delimiter.is_ok() { before - input.len() } else { before })?;
    let (delimiter, expands) = delimiter?;
    // With a BARE delimiter the shell expands the body, so `cat <<EOF` with `$(rm -rf /)` in it
    // runs that command. The body is looked up now (it is already present in `input`, after this
    // line) rather than at drain time, so the expansions land on the redirect that owns them.
    let body = if expands {
        heredoc_body_word(input, &delimiter, strip_tabs)?
    } else {
        Word(Vec::new())
    };
    // Bash semantics: the heredoc body lives on lines AFTER the
    // command line is finished, not immediately after `<<DELIM`. The
    // command line can continue with more redirects, a pipe, etc.
    // Push the delimiter onto a thread-local queue; the body is
    // drained at the next `\n`/`;` separator by drain_pending_heredocs.
    PENDING_HEREDOCS.with(|q| {
        q.borrow_mut().push(PendingHeredoc {
            delimiter: delimiter.clone(),
            strip_tabs,
        });
    });
    Ok(Redir::HereDoc { delimiter, strip_tabs, body })
}

/// This heredoc's body, parsed for the expansions the shell performs on it.
///
/// Bodies begin after the CURRENT line, and a heredoc declared earlier on the same line
/// (`cat <<A <<B`) owns an earlier body — so the pending queue is replayed to find where this
/// one starts. Reads without consuming; `drain_pending_heredocs` still does the consuming.
///
/// FAILS CLOSED: a body that does not parse (a lone backtick opens a substitution that is never
/// closed) refuses the whole parse, which denies. That matches the shell, which reports
/// `unexpected EOF while looking for matching backquote` and runs nothing.
fn heredoc_body_word(input: &str, delimiter: &str, strip_tabs: bool) -> ModalResult<Word> {
    let Some(nl) = input.find('\n') else {
        scan(input.len())?;
        return Ok(Word(Vec::new())); // no body yet; the drain will fail the parse
    };
    let mut rest = &input[nl + 1..];
    let priors: Vec<PendingHeredoc> = PENDING_HEREDOCS.with(|q| q.borrow().clone());
    for prior in &priors {
        let Some((_, after)) = split_heredoc_body(rest, &prior.delimiter, prior.strip_tabs) else {
            scan(input.len())?;
            return Ok(Word(Vec::new()));
        };
        rest = after;
    }
    let Some((body, after)) = split_heredoc_body(rest, delimiter, strip_tabs) else {
        scan(input.len())?;
        return Ok(Word(Vec::new()));
    };
    scan(input.len() - after.len())?;
    let mut text = body;
    let parts: Vec<WordPart> = repeat(0.., heredoc_part).parse_next(&mut text)?;
    if !text.is_empty() {
        return backtrack();
    }
    Ok(Word(parts))
}

/// A heredoc body expands like a double-quoted string, with one difference that matters: `"` and
/// `'` are ORDINARY characters there, so `'$(id)'` in a body still runs `id`. Skipping quoted spans
/// the way `find_sub_close` does would therefore miss a live substitution.
fn is_heredoc_literal(c: char) -> bool {
    !matches!(c, '"' | '\\' | '`' | '$')
}

fn heredoc_part(input: &mut &str) -> ModalResult<WordPart> {
    step()?;
    if input.is_empty() {
        return backtrack();
    }
    if input.starts_with('"') {
        *input = &input[1..];
        return Ok(WordPart::Lit("\"".to_string()));
    }
    alt((
        dq_escape,
        arith_sub,
        cmd_sub,
        backtick_part,
        dollar_lit(is_heredoc_literal),
        lit(is_heredoc_literal),
    ))
    .parse_next(input)
}

#[derive(Debug, Clone)]
struct PendingHeredoc {
    delimiter: String,
    strip_tabs: bool,
}

thread_local! {
    static PENDING_HEREDOCS: std::cell::RefCell<Vec<PendingHeredoc>> =
        const { std::cell::RefCell::new(Vec::new()) };
}

fn drain_pending_heredocs(input: &mut &str) {
    let pending: Vec<PendingHeredoc> =
        PENDING_HEREDOCS.with(|q| std::mem::take(&mut *q.borrow_mut()));
    for h in pending {
        if !skip_heredoc_body(input, &h.delimiter, h.strip_tabs) {
            // Couldn't find the matching delimiter line. Leave input
            // as-is; the parser will likely fail on the leftover body
            // text, which is the safe outcome (we deny on parse fail).
            return;
        }
    }
}

fn skip_heredoc_body(input: &mut &str, delimiter: &str, strip_tabs: bool) -> bool {
    let split = split_heredoc_body(input, delimiter, strip_tabs);
    let _ = scan(split.map_or(input.len(), |(_, rest)| input.len() - rest.len()));
    match split {
        Some((_, rest)) => {
            *input = rest;
            true
        }
        None => false,
    }
}

/// Split at the delimiter line: `(body, rest-after-the-delimiter-line)`, or `None` when the
/// delimiter never appears. `strip_tabs` (`<<-`) strips leading TABS only, matching the shell —
/// spaces do not terminate a `<<-` body.
fn split_heredoc_body<'a>(
    s: &'a str,
    delimiter: &str,
    strip_tabs: bool,
) -> Option<(&'a str, &'a str)> {
    let bytes = s.as_bytes();
    let mut line_start = 0;
    while line_start <= bytes.len() {
        let line_end = match s[line_start..].find('\n') {
            Some(rel) => line_start + rel,
            None => bytes.len(),
        };
        let line = &s[line_start..line_end];
        let line = if strip_tabs { line.trim_start_matches('\t') } else { line };
        if line == delimiter {
            let advance = line_end + usize::from(line_end < bytes.len());
            return Some((&s[..line_start], &s[advance..]));
        }
        if line_end >= bytes.len() {
            return None;
        }
        line_start = line_end + 1;
    }
    None
}

fn reset_heredoc_queue() {
    PENDING_HEREDOCS.with(|q| q.borrow_mut().clear());
}

/// The delimiter, and whether the body EXPANDS. Any quoting or escaping anywhere in the delimiter
/// suppresses expansion (`<<'EOF'`, `<<"EOF"`, `<<\EOF`, `<<E"O"F`); only a wholly bare word leaves
/// the body live. Reported as a flag because that single bit decides whether the body is data or
/// code, and treating a quoted body as code would over-deny every ordinary commit message.
fn heredoc_delimiter(input: &mut &str) -> ModalResult<(String, bool)> {
    alt((
        delimited('\'', take_while(0.., |c| c != '\''), '\'').map(|s: &str| (s.to_string(), false)),
        delimited('"', take_while(0.., |c| c != '"'), '"').map(|s: &str| (s.to_string(), false)),
        escaped_delimiter,
        take_while(1.., |c: char| c.is_ascii_alphanumeric() || c == '_')
            .map(|s: &str| (s.to_string(), true)),
    ))
    .parse_next(input)
}

/// A delimiter carrying a backslash or an inner quote — `<<\EOF`, `<<E"O"F`, `<<EO'F'`. The shell
/// treats ANY such quoting as suppressing expansion over the WHOLE delimiter, so these parse to the
/// unquoted spelling with expansion off. Without this they failed to parse at all, denying a valid
/// (and, being unexpanded, entirely inert) heredoc.
fn escaped_delimiter(input: &mut &str) -> ModalResult<(String, bool)> {
    let mut rest = *input;
    let mut name = String::new();
    let mut quoted = false;
    loop {
        let mut chars = rest.chars();
        match chars.next() {
            Some('\\') => match chars.next() {
                Some(c) => {
                    name.push(c);
                    quoted = true;
                    rest = &rest[1 + c.len_utf8()..];
                }
                None => break,
            },
            Some(q @ ('\'' | '"')) => {
                let inner_end = rest[1..].find(q).map(|i| i + 1);
                let Some(end) = inner_end else { break };
                name.push_str(&rest[1..end]);
                quoted = true;
                rest = &rest[end + 1..];
            }
            Some(c) if c.is_ascii_alphanumeric() || c == '_' => {
                name.push(c);
                rest = &rest[c.len_utf8()..];
            }
            _ => break,
        }
    }
    if !quoted || name.is_empty() {
        return backtrack();
    }
    *input = rest;
    Ok((name, false))
}

fn fd_prefix(input: &mut &str) -> ModalResult<u32> {
    let b = input.as_bytes();
    if b.len() >= 2 && b[0].is_ascii_digit() && matches!(b[1], b'>' | b'<') {
        let d = (b[0] - b'0') as u32;
        *input = &input[1..];
        Ok(d)
    } else {
        backtrack()
    }
}

fn fd_target(input: &mut &str) -> ModalResult<String> {
    alt((
        '-'.value("-".to_string()),
        take_while(1.., |c: char| c.is_ascii_digit()).map(|s: &str| s.to_string()),
    ))
    .parse_next(input)
}

// === Word ===

fn word(input: &mut &str) -> ModalResult<Word> {
    repeat(1.., word_part)
        .map(Word)
        .parse_next(input)
}

fn word_part(input: &mut &str) -> ModalResult<WordPart> {
    step()?;
    if input.is_empty() {
        return backtrack();
    }
    if input.starts_with("<(") || input.starts_with(">(") {
        return proc_sub(input);
    }
    if is_word_boundary(input.as_bytes()[0] as char) {
        return backtrack();
    }
    alt((single_quoted, double_quoted, arith_sub, cmd_sub, backtick_part, escaped, dollar_lit(is_word_literal), lit(is_word_literal)))
        .parse_next(input)
}

fn single_quoted(input: &mut &str) -> ModalResult<WordPart> {
    delimited_scan(input, '\'', |i| {
        delimited('\'', take_while(0.., |c| c != '\''), '\'')
            .map(|s: &str| WordPart::SQuote(s.to_string()))
            .parse_next(i)
    })
}

fn double_quoted(input: &mut &str) -> ModalResult<WordPart> {
    delimited('"', repeat(0.., dq_part).map(Word), '"')
        .map(WordPart::DQuote)
        .parse_next(input)
}

/// Byte offset of the `)` that closes a substitution body starting at `body[0]` — the first `)` at
/// paren-depth zero — or `None` if it is never closed. Quote (`'…'`, `"…"`), backtick, and backslash
/// spans are skipped so a `)` inside them does not count, mirroring how the grammar's own
/// `single_quoted`/`double_quoted`/`backtick`/`escaped` parsers treat those regions. This is what
/// keeps `cmd_sub`/`proc_sub` linear: the interior is parsed only once, over a bounded slice, instead
/// of the old `delimited(script, ')')` shape that recursed into the tail BEFORE knowing a close even
/// existed — the source of the `a$(a<(a` × N exponential.
fn find_sub_close(body: &str) -> Option<usize> {
    let b = body.as_bytes();
    let mut i = 0;
    let mut depth: usize = 0;
    while i < b.len() {
        match b[i] {
            b'\\' => i += 1, // escape: skip the next byte too (the trailing `+= 1` handles it)
            b'\'' => {
                i += 1;
                while i < b.len() && b[i] != b'\'' {
                    i += 1;
                }
                if i >= b.len() {
                    return None;
                }
            }
            b'"' => {
                i += 1;
                while i < b.len() && b[i] != b'"' {
                    i += if b[i] == b'\\' { 2 } else { 1 };
                }
                if i >= b.len() {
                    return None;
                }
            }
            b'`' => {
                i += 1;
                while i < b.len() && b[i] != b'`' {
                    // `bt_escape` treats `\<any>` inside backticks as a literal, so an escaped
                    // backtick does NOT close the span — skip the escaped byte too.
                    i += if b[i] == b'\\' { 2 } else { 1 };
                }
                if i >= b.len() {
                    return None;
                }
            }
            b'(' => depth += 1,
            b')' => {
                if depth == 0 {
                    return Some(i);
                }
                depth -= 1;
            }
            _ => {}
        }
        i += 1;
    }
    None
}

/// Parse a substitution body (`$( … )`, `<( … )`, `>( … )`) as a full script.
///
/// FAST PATH: `find_sub_close` locates the matching `)` and we parse only the bounded interior, so
/// nested substitutions stay linear instead of the old `delimited(script, ')')` shape that recursed
/// into the tail before knowing a close existed (the `a$(a<(a` × N exponential).
///
/// FALLBACK: a heredoc or a `case` moves the real close PAST that first balanced `)` (a heredoc body
/// is drained out-of-band; an arm's pattern ends in a bare `)`), so an interior holding either goes
/// to the EXACT old grammar over the full body instead. Otherwise the fast path is the ONLY reading:
/// a refused interior refuses the substitution. Re-running the grammar there doubled the work per
/// nested `$(`, since each level parsed its interior once bounded and once more in full.
///
/// A `None` from `find_sub_close` normally means no unquoted `)` exists at all, so the grammar
/// could not close the sub either and we fail fast. The exception is a heredoc: its body is data the scanner reads as code, so a lone apostrophe in prose (`the shell's
/// grammar`) opens a quote that never closes and swallows the real `)`. `git commit -m "$(cat <<EOF`
/// with any contraction in the message lands here, so `None` + a heredoc operator takes the grammar
/// fallback — which drains the body correctly — rather than failing the whole parse.
fn sub_body(input: &mut &str, open_len: usize) -> ModalResult<Script> {
    let body = &input[open_len..];
    let close = find_sub_close(body);
    scan(close.map_or(2 * body.len(), |rel| 3 * rel))?;
    let Some(rel) = close else {
        return if body.contains("<<") {
            sub_body_via_grammar(input, body)
        } else {
            backtrack()
        };
    };
    // A heredoc body is drained out-of-band (`drain_pending_heredocs`) and can run PAST `rel`, so the
    // bounded interior would be truncated mid-heredoc and still parse "clean" — the fast path is
    // unreliable whenever the interior holds a heredoc operator. Skip straight to the grammar fallback
    // there. `<<` covers `<<`, `<<-`, and `<<<`; the latter (herestring) is inline and would be fine,
    // but taking the fallback for it is merely slower, never wrong.
    let interior = &body[..rel];
    // `case` has the same hazard as a heredoc: the `)` closing an arm's pattern is not a nesting
    // paren, so `find_sub_close` stops at `$(case A in *)` and the truncated interior still parses
    // "clean" — as a simple command whose words are `case A in *`. A wrong-but-clean fast parse is
    // worse than a slow one, so hand any interior mentioning `case` to the grammar fallback. The
    // test is deliberately the bare substring: a literal word `case` merely costs a slower path.
    if !interior.contains("<<") && !interior.contains("case") {
        let mut fast: &str = interior;
        let parsed = script.parse_next(&mut fast)?;
        ws.parse_next(&mut fast)?;
        if !fast.is_empty() {
            return backtrack();
        }
        *input = &body[rel + 1..];
        return Ok(parsed);
    }
    sub_body_via_grammar(input, body)
}

/// The EXACT old grammar over the full body: it drains heredocs and tracks `case` arms, so it finds
/// a close that `find_sub_close`'s byte scan places wrongly or misses. Bounded by `budget`.
fn sub_body_via_grammar<'a>(input: &mut &'a str, body: &'a str) -> ModalResult<Script> {
    let mut rest: &str = body;
    ws.parse_next(&mut rest)?;
    let parsed = script.parse_next(&mut rest)?;
    ws.parse_next(&mut rest)?;
    if !rest.starts_with(')') {
        return backtrack();
    }
    *input = &rest[1..];
    Ok(parsed)
}

fn cmd_sub(input: &mut &str) -> ModalResult<WordPart> {
    if !input.starts_with("$(") {
        return backtrack();
    }
    sub_body(input, 2).map(WordPart::CmdSub)
}

fn proc_sub(input: &mut &str) -> ModalResult<WordPart> {
    if !(input.starts_with("<(") || input.starts_with(">(")) {
        return backtrack();
    }
    sub_body(input, 2).map(WordPart::ProcSub)
}

/// The parts of an arithmetic BODY: literal text plus the substitutions that actually run.
fn arith_body_part(input: &mut &str) -> ModalResult<WordPart> {
    step()?;
    if input.is_empty() {
        return backtrack();
    }
    alt((
        dq_escape,
        // Nested `$(( ))` must be recognised as ARITHMETIC before `cmd_sub` sees it, or `$((` is
        // read as `$(` plus a subshell and `$(( $((1+1)) ))` refuses on an inner "command" `(1+1)`.
        // It cannot be skipped as literal text either: `$(( $(( $(rm -rf /) )) ))` would then hide
        // a real substitution, which is a fail-OPEN. So it recurses, bounded by the guard below.
        arith_sub,
        cmd_sub,
        backtick_part,
        dollar_lit(is_heredoc_literal),
        lit(is_heredoc_literal),
    ))
    .parse_next(input)
}

fn arith_sub(input: &mut &str) -> ModalResult<WordPart> {
    if !input.starts_with("$((") {
        return backtrack();
    }
    // Parsing the body makes this a recursion source that does NOT funnel through `script()`, where
    // the depth cap is enforced — unguarded, `$((1+` x50000 overflowed the stack and ABORTED,
    // which for a hook is a fail-open crash `catch_unwind` cannot recover. Taking the guard here
    // was previously rejected because bailing backtracks into `cmd_sub`, which re-parsed the same
    // nest for 68 seconds; that is affordable now only because `budget` charges what each retry
    // reads, which bounds the retry as well as the descent.
    let Some(_depth) = DepthGuard::enter() else {
        return backtrack();
    };
    let body_start = 3;
    let bytes = input.as_bytes();
    let mut depth: i32 = 1;
    let mut i = body_start;
    while i < bytes.len() {
        match bytes[i] {
            b'(' => depth += 1,
            b')' => {
                if depth == 1 && i + 1 < bytes.len() && bytes[i + 1] == b')' {
                    // The body is PARSED, not kept as text. It used to backtrack whenever it held
                    // a substitution, which handed `$((` to `cmd_sub` and re-read it as `$(` plus a
                    // subshell — `--explain` rendered `$( (1 + …))`, a command nobody wrote, and
                    // refused it because `(1` is not a command. That cost a false deny on the
                    // everyday `$(( now - $(date +%s) ))`.
                    //
                    // The old backtrack was the conservative choice: treating the body as opaque
                    // text would hide the inner command, a fail-OPEN. Parsing keeps it visible and
                    // stops the misparse. `arith_body_part` deliberately excludes `arith_sub`, so
                    // arithmetic is not a recursion source — nested `$(( ))` is literal text here,
                    // which costs nothing since arithmetic is inert either way.
                    scan(i)?;
                    let mut body = &input[body_start..i];
                    let parts: Vec<WordPart> = repeat(0.., arith_body_part).parse_next(&mut body)?;
                    if !body.is_empty() {
                        return backtrack();
                    }
                    *input = &input[i + 2..];
                    return Ok(WordPart::Arith(Word(parts)));
                }
                depth -= 1;
                if depth < 0 {
                    scan(i)?;
                    return backtrack();
                }
            }
            _ => {}
        }
        i += 1;
    }
    scan(i)?;
    backtrack()
}

fn backtick_part(input: &mut &str) -> ModalResult<WordPart> {
    delimited_scan(input, '`', |i| {
        delimited('`', backtick_inner, '`').map(WordPart::Backtick).parse_next(i)
    })
}

/// A quoted span scans to its close, or to the end of the input when there is none, so an unclosed
/// one is charged for everything it read even though it consumes nothing.
fn delimited_scan<O>(
    input: &mut &str,
    open: char,
    p: impl FnOnce(&mut &str) -> ModalResult<O>,
) -> ModalResult<O> {
    if !input.starts_with(open) {
        return backtrack();
    }
    let before = input.len();
    let out = p(input);
    scan(if out.is_ok() { before - input.len() } else { before })?;
    out
}

fn escaped(input: &mut &str) -> ModalResult<WordPart> {
    preceded('\\', any).map(WordPart::Escape).parse_next(input)
}

fn lit(pred: fn(char) -> bool) -> impl FnMut(&mut &str) -> ModalResult<WordPart> {
    move |input: &mut &str| {
        let s: &str = consumed(input, |i| take_while(1.., pred).parse_next(i))?;
        Ok(WordPart::Lit(s.to_string()))
    }
}

fn dollar_lit(pred: fn(char) -> bool) -> impl FnMut(&mut &str) -> ModalResult<WordPart> {
    move |input: &mut &str| {
        ('$', not('(')).void().parse_next(input)?;
        let rest: &str = consumed(input, |i| take_while(0.., pred).parse_next(i))?;
        Ok(WordPart::Lit(format!("${rest}")))
    }
}

// === Double-quoted parts ===

fn dq_part(input: &mut &str) -> ModalResult<WordPart> {
    step()?;
    if input.is_empty() || input.starts_with('"') {
        return backtrack();
    }
    alt((dq_escape, arith_sub, cmd_sub, backtick_part, dollar_lit(is_dq_literal), lit(is_dq_literal)))
        .parse_next(input)
}

fn dq_escape(input: &mut &str) -> ModalResult<WordPart> {
    preceded('\\', any)
        .map(|c: char| match c {
            '"' | '\\' | '$' | '`' => WordPart::Escape(c),
            _ => WordPart::Lit(format!("\\{c}")),
        })
        .parse_next(input)
}

// === Backtick inner content ===

fn backtick_inner(input: &mut &str) -> ModalResult<String> {
    repeat(0.., alt((bt_escape, bt_literal)))
        .fold(String::new, |mut acc, chunk: &str| {
            acc.push_str(chunk);
            acc
        })
        .parse_next(input)
}

fn bt_escape<'a>(input: &mut &'a str) -> ModalResult<&'a str> {
    ('\\', any).take().parse_next(input)
}

fn bt_literal<'a>(input: &mut &'a str) -> ModalResult<&'a str> {
    take_while(1.., |c: char| c != '`' && c != '\\').parse_next(input)
}

// === Compound Commands ===

fn for_cmd(input: &mut &str) -> ModalResult<Cmd> {
    eat_keyword(input, "for")?;
    ws.parse_next(input)?;
    let var = name.parse_next(input)?;
    ws.parse_next(input)?;

    let items = if eat_keyword(input, "in").is_ok() {
        ws.parse_next(input)?;
        repeat(0.., terminated(word, ws)).parse_next(input)?
    } else {
        vec![]
    };

    let body = do_done_body.parse_next(input)?;
    let redirs = trailing_redirs(input)?;
    Ok(Cmd::For { var, items, body, redirs })
}

fn while_cmd(input: &mut &str) -> ModalResult<Cmd> {
    eat_keyword(input, "while")?;
    ws.parse_next(input)?;
    let cond = script.parse_next(input)?;
    let body = do_done_body.parse_next(input)?;
    let redirs = trailing_redirs(input)?;
    Ok(Cmd::While { cond, body, redirs })
}

fn until_cmd(input: &mut &str) -> ModalResult<Cmd> {
    eat_keyword(input, "until")?;
    ws.parse_next(input)?;
    let cond = script.parse_next(input)?;
    let body = do_done_body.parse_next(input)?;
    let redirs = trailing_redirs(input)?;
    Ok(Cmd::Until { cond, body, redirs })
}

fn do_done_body(input: &mut &str) -> ModalResult<Script> {
    sep.parse_next(input)?;
    eat_keyword(input, "do")?;
    sep.parse_next(input)?;
    let body = script.parse_next(input)?;
    sep.parse_next(input)?;
    eat_keyword(input, "done")?;
    Ok(body)
}

fn if_cmd(input: &mut &str) -> ModalResult<Cmd> {
    eat_keyword(input, "if")?;
    ws.parse_next(input)?;
    let mut branches = vec![cond_then_body.parse_next(input)?];
    let mut else_body = None;

    loop {
        sep.parse_next(input)?;
        if eat_keyword(input, "elif").is_ok() {
            ws.parse_next(input)?;
            branches.push(cond_then_body.parse_next(input)?);
        } else if eat_keyword(input, "else").is_ok() {
            sep.parse_next(input)?;
            else_body = Some(script.parse_next(input)?);
            break;
        } else {
            break;
        }
    }

    sep.parse_next(input)?;
    eat_keyword(input, "fi")?;
    let redirs = trailing_redirs(input)?;
    Ok(Cmd::If { branches, else_body, redirs })
}

fn cond_then_body(input: &mut &str) -> ModalResult<Branch> {
    let cond = script.parse_next(input)?;
    sep.parse_next(input)?;
    eat_keyword(input, "then")?;
    sep.parse_next(input)?;
    let body = script.parse_next(input)?;
    Ok(Branch { cond, body })
}

/// `case WORD in [(] PATTERN [| PATTERN]… ) BODY ;; … esac` (POSIX 2.9.4.3).
fn case_cmd(input: &mut &str) -> ModalResult<Cmd> {
    eat_keyword(input, "case")?;
    ws.parse_next(input)?;
    let subject = word.parse_next(input)?;
    blank.parse_next(input)?;
    eat_keyword(input, "in")?;

    let mut arms = Vec::new();
    loop {
        blank.parse_next(input)?;
        if eat_keyword(input, "esac").is_ok() {
            break;
        }
        let arm = case_arm.parse_next(input)?;
        let had_terminator = opt(";;").parse_next(input)?.is_some();
        arms.push(arm);
        // POSIX lets the LAST arm omit `;;`, and only the last. Anything else here is malformed —
        // backtrack rather than guess, so a shape we don't understand fails closed.
        if !had_terminator {
            blank.parse_next(input)?;
            eat_keyword(input, "esac")?;
            break;
        }
    }

    let redirs = trailing_redirs(input)?;
    Ok(Cmd::Case { subject, arms, redirs })
}

fn case_arm(input: &mut &str) -> ModalResult<CaseArm> {
    blank.parse_next(input)?;
    opt('(').parse_next(input)?;
    let mut patterns = Vec::new();
    loop {
        ws.parse_next(input)?;
        patterns.push(word.parse_next(input)?);
        ws.parse_next(input)?;
        if opt('|').parse_next(input)?.is_none() {
            break;
        }
    }
    ')'.parse_next(input)?;
    let body = script.parse_next(input)?;
    blank.parse_next(input)?;
    Ok(CaseArm { patterns, body })
}

/// Whitespace including newlines, but NOT `;` — used where a `;;` must stay visible to the caller.
fn blank(input: &mut &str) -> ModalResult<()> {
    consumed(input, |i| take_while(0.., [' ', '\t', '\n']).void().parse_next(i))
}

fn double_bracket_cmd(input: &mut &str) -> ModalResult<Cmd> {
    if !input.starts_with("[[") {
        return backtrack();
    }
    let bytes = input.as_bytes();
    if bytes.len() < 3 || !matches!(bytes[2], b' ' | b'\t' | b'\n') {
        return backtrack();
    }
    *input = &input[2..];

    let mut words: Vec<Word> = Vec::new();
    loop {
        ws.parse_next(input)?;
        if at_double_bracket_end(input) {
            *input = &input[2..];
            let redirs = trailing_redirs(input)?;
            return Ok(Cmd::DoubleBracket { words, redirs });
        }
        if input.is_empty() {
            return backtrack();
        }
        let w = bracket_word.parse_next(input)?;
        words.push(w);
    }
}

fn at_double_bracket_end(input: &str) -> bool {
    if !input.starts_with("]]") {
        return false;
    }
    let after = &input[2..];
    after.is_empty()
        || after.starts_with(|c: char| {
            matches!(c, ' ' | '\t' | '\n' | ';' | '&' | '|' | ')' | '>' | '<')
        })
}

fn bracket_word(input: &mut &str) -> ModalResult<Word> {
    repeat(1.., bracket_word_part).map(Word).parse_next(input)
}

fn bracket_word_part(input: &mut &str) -> ModalResult<WordPart> {
    step()?;
    if input.is_empty() {
        return backtrack();
    }
    if matches!(input.as_bytes()[0], b' ' | b'\t' | b'\n') {
        return backtrack();
    }
    if at_double_bracket_end(input) {
        return backtrack();
    }
    alt((
        single_quoted,
        double_quoted,
        arith_sub,
        cmd_sub,
        backtick_part,
        escaped,
        dollar_lit(is_bracket_literal),
        bracket_lit,
    ))
    .parse_next(input)
}

fn is_bracket_literal(c: char) -> bool {
    !matches!(c, '\'' | '"' | '`' | '\\' | '$' | ' ' | '\t' | '\n')
}

fn bracket_lit(input: &mut &str) -> ModalResult<WordPart> {
    // Byte-by-byte scan relies on every stop char being single-byte ASCII —
    // multibyte UTF-8 continuation bytes always pass `is_bracket_literal` and
    // get consumed as part of the same `Lit`, so `end` only lands on a char
    // boundary.
    let bytes = input.as_bytes();
    let mut end = 0;
    while end < bytes.len() {
        let c = bytes[end] as char;
        if !is_bracket_literal(c) {
            break;
        }
        if c == ']' && at_double_bracket_end(&input[end..]) {
            break;
        }
        end += 1;
    }
    scan(end)?;
    if end == 0 {
        return backtrack();
    }
    let lit = input[..end].to_string();
    *input = &input[end..];
    Ok(WordPart::Lit(lit))
}

fn name(input: &mut &str) -> ModalResult<String> {
    run(input, |c| c.is_ascii_alphanumeric() || c == '_').map(String::from)
}

#[cfg(test)]
mod tests {
    use super::budget::MAX_PARSE_WORK_CEILING;
    /// The parse work budget must bound NESTED input without refusing anything real.
    ///
    /// Both halves are measured, because the constant is only defensible as a ratio between them:
    ///
    ///   - Real commands are FLAT and cost 1-2 `script()` entries. Across every example the
    ///     registry ships (1338 of them) the most any one needs is 2 — the worst being
    ///     `eval "$(conda shell.bash hook)"`. Flat input is free regardless of size: 400
    ///     side-by-side `$((1))` in 2805 bytes costs ONE entry.
    ///   - Nested input is what blows up, and it blew up because the budget GREW with the input
    ///     (`16384 + 512 * len`), so a bigger adversarial input bought itself more time. At depth
    ///     400 that allowed 1_453_119 entries and took 1.55s in release purely to fail; depth 1000
    ///     read as a hang.
    ///
    /// So the guard pins the ratio, not a timing: real examples must stay far under the ceiling,
    /// and a deep nest must be stopped BY the ceiling rather than by exhausting a length-scaled
    /// allowance. Timings are deliberately not asserted — they are machine-dependent — but for the
    /// record the same depth-400 input now parses in 0.028s, below process startup.
    #[test]
    fn the_parse_work_budget_bounds_nesting_without_refusing_real_commands() {
        let worst_real = crate::registry::corpus_examples()
            .into_iter()
            .flat_map(|(_, safe, denied)| safe.iter().chain(denied.iter()).cloned().collect::<Vec<_>>())
            .map(|ex| {
                let _ = super::parse(&ex);
                budget::work()
            })
            .max()
            .expect("the registry ships examples");
        assert!(
            worst_real * 100 < MAX_PARSE_WORK_CEILING,
            "a real example needs {worst_real} entries against a {MAX_PARSE_WORK_CEILING} ceiling; \
             the margin that makes this constant safe is gone"
        );

        // Flat input stays LINEAR however long it is — that is why a flat ceiling is safe, and it
        // is the property, not a particular number. Arithmetic began costing one unit each when
        // `arith_sub` took the depth guard (it is a recursion source now), so 400 expansions cost
        // ~400 rather than the ~1 they cost when arithmetic was outside the accounting. Still two
        // orders of magnitude under the ceiling, which is what matters.
        let flat = format!("echo {}", "$((1)) ".repeat(400));
        let _ = super::parse(&flat);
        let flat_work = budget::work();
        assert!(
            flat_work < MAX_PARSE_WORK_CEILING / 10,
            "flat input cost {flat_work}, close to the {MAX_PARSE_WORK_CEILING} ceiling — a long \
             flat command is at risk of being refused"
        );

        // A deep nest is stopped by the CEILING, not by a length-scaled allowance. The property
        // asserted is that the work stops GROWING with the input — doubling the nest must not
        // double the work — which is precisely what the old `BASE + PER_BYTE * len` budget failed
        // to do. An exact cap is not asserted: `enter()` bumps the counter before it checks, so
        // calls on the unwind path overshoot slightly (59 entries when this was written).
        let work_at = |depth: usize| {
            let deep = format!("echo {}1{}", "$((1+".repeat(depth), "))".repeat(depth));
            let _ = super::parse(&deep);
            assert!(budget::spent(), "the nest should actually reach a bound, or this proves nothing");
            budget::work()
        };
        let (w2k, w4k) = (work_at(2000), work_at(4000));
        assert!(
            w4k <= w2k + w2k / 10,
            "work still scales with input length: depth 2000 used {w2k}, depth 4000 used {w4k}"
        );
        assert!(
            w4k < MAX_PARSE_WORK_CEILING + MAX_PARSE_WORK_CEILING / 10,
            "work {w4k} ran far past the {MAX_PARSE_WORK_CEILING} ceiling"
        );
    }


    use super::*;

    /// An unclosed compound, nested, must cost parse work LINEAR in its depth.
    ///
    /// Found by the `explain_render` fuzzer as a timeout: `{\n` repeated in front of a
    /// `"$([[ … <<` tail. Every level was parsed as a brace group, failed at the far end, and was
    /// parsed again as a simple command named `{`, so the work doubled per brace until the entry
    /// budget stopped it, 0.35s per parse and several parses per classification. The rule is not
    /// about braces: any reserved word that opens a compound had the same second reading. So this
    /// walks every opener `reserved` knows, and a new one without an unclosed form here fails.
    #[test]
    fn unclosed_compound_nesting_costs_linear_work() {
        let unclosed = |opener: &str| match opener {
            "{" => "{\n",
            "[[" => "[[ a\n",
            "if" => "if a; then\n",
            "for" => "for x in a; do\n",
            "while" => "while a; do\n",
            "until" => "until a; do\n",
            "case" => "case x in a)\n",
            "function" => "function f {\n",
            other => panic!("no unclosed form for the reserved word {other:?}; add one here"),
        };
        let tail = "\"$([[ <<\"\"<\"$( [[ x ]] ) $(ls <<EOF\n)\nEOF\n)\" ls";
        let openers = super::super::reserved::BLANK_OPENERS
            .iter()
            .chain(super::super::reserved::KEYWORD_OPENERS.iter());
        for opener in openers {
            let unit = unclosed(opener);
            for prefix in [unit.to_string(), format!("{unit}{{\n")] {
                for depth in [10u64, 20, 40] {
                    let text = format!("{}{tail}", prefix.repeat(depth as usize));
                    let _ = parse(&text);
                    let work = budget::work();
                    assert!(
                        work <= 4 * depth + 64,
                        "{depth} nested unclosed {prefix:?} cost {work} parse entries, more than \
                         linear in the nesting: a failed compound is being re-read another way"
                    );
                }
            }
        }
    }

    /// A refused substitution interior, nested, must also cost work linear in the nesting.
    ///
    /// `sub_body` used to follow a refused bounded interior with a full-grammar re-parse of the
    /// same text, so every `$(` level read its interior twice and depth 10 cost 2047 entries. The
    /// interiors here are refused for different reasons (an unclosed `[[`, an unclosed brace group,
    /// an `if` without `then`, a stray `}`), in plain and double-quoted substitutions, because the
    /// doubling did not depend on why the interior failed.
    #[test]
    fn refused_substitution_nesting_costs_linear_work() {
        for refused in ["[[ a", "{ a", "if a", "a; }"] {
            for (open, close) in [("$(", ")"), ("\"$(", ")\""), ("<(", ")")] {
                for depth in [10u64, 20, 40] {
                    let n = depth as usize;
                    let text = format!("echo {}x{}", format!("{open}{refused} ").repeat(n), close.repeat(n));
                    let _ = parse(&text);
                    let work = budget::work();
                    assert!(
                        work <= 4 * depth + 64,
                        "{depth} nested {open}{refused} cost {work} parse entries, more than linear: \
                         a refused interior is being parsed a second time"
                    );
                }
            }
        }
    }

    /// A nest that still backtracks is stopped by how much it READS, not by how often it enters.
    ///
    /// `$((` is read as arithmetic first and as `$(` plus a subshell when that fails, as bash does,
    /// so a failing nest of them still doubles per level. The entry ceiling caps the count at
    /// 20,000, but each entry here re-reads a 100 KB tail, and before the step budget that took 15s
    /// to refuse. Stopping it after a few hundred entries is the step budget doing its job; hitting
    /// the entry ceiling instead means some scan is not being charged.
    #[test]
    fn a_backtracking_nest_over_a_long_tail_is_stopped_by_what_it_reads() {
        let tail = "a ".repeat(50_000);
        for (open, close) in [("$(( $({ ", ") ))"), ("\"$(( $( [[ ", ") ))\"")] {
            let text = format!("echo {}x {tail}{}", open.repeat(20), close.repeat(20));
            assert!(parse(&text).is_none(), "{open:?} nest parsed");
            assert!(budget::spent(), "{open:?} nest was refused, but not by the budget");
            let work = budget::work();
            assert!(work < 1_000, "{open:?} nest ran {work} entries before the step budget stopped it");
        }
    }

    /// The explain_render timeout's own input, with its brace nest regrown to 10..40: parse work
    /// and steps must grow linearly in the braces, never double.
    ///
    /// The seed is the minimized fuzzer find. Its backtick body is an unclosed `{` nest in front of
    /// a `"$([[ … <<` tail, and classifying it re-parses that body several times, so before the
    /// fix it took 4s. Keeping the seed's actual tail here, rather than a hand-written look-alike,
    /// is what makes this the regression it claims to be.
    #[test]
    fn the_explain_render_timeout_seed_scales_linearly_in_its_braces() {
        let seed = include_bytes!("../../fuzz/corpus/explain_render/seed-unclosed-brace-nest");
        let seed = String::from_utf8_lossy(seed);
        let body = seed.split('`').nth(1).expect("the seed carries a backtick body");
        let deep = body.find("$([[").expect("the seed's tail opens a `$([[`");
        let tail = &body[body[..deep].rfind("\n{").expect("the nest ends before the tail") + 2..];
        let cost = |k: usize| {
            let _ = parse(&format!("{}{tail}", "{\n".repeat(k)));
            assert!(!budget::spent(), "{k} braces spent the budget; the nest is not linear");
            (budget::work(), budget::steps())
        };
        let [(w10, s10), (w20, s20), (w40, s40)] = [cost(10), cost(20), cost(40)];
        assert!(w40 - w20 <= 2 * (w20 - w10) + 4, "entries {w10}/{w20}/{w40} for 10/20/40 braces");
        assert!(s40 - s20 <= 2 * (s20 - s10) + 16, "steps {s10}/{s20}/{s40} for 10/20/40 braces");
        assert!(!crate::is_safe_command(&seed));
    }

    proptest::proptest! {
        #![proptest_config(proptest::prelude::ProptestConfig::with_cases(300))]

        /// A random nest of unclosed compounds and substitutions, then random material, parses in
        /// work linear in its size, and never by running out of budget.
        ///
        /// The two tests above pin the shapes that were found; this is the class. An unclosed
        /// compound used to be re-read as a simple command, and a refused substitution interior
        /// was re-parsed by the grammar, and either alone doubled the work per level of nesting.
        /// The nest is generated as one opener repeated on purpose: a random walk, and even a random
        /// mix of openers, almost never stacks ten failing levels, and both stayed green with the
        /// fixes reverted. Counting entries rather
        /// than timing makes the check exact on any machine. `$((` is left out because it still
        /// legitimately tries two readings, which the step budget bounds (see
        /// `a_backtracking_nest_over_a_long_tail_is_stopped_by_what_it_reads`).
        #[test]
        fn a_random_unclosed_nest_parses_in_linear_work(
            opener in proptest::sample::select(OPENERS.to_vec()),
            depth in 0..24usize,
            mixed in proptest::collection::vec(proptest::sample::select(OPENERS.to_vec()), 0..8),
            tail in proptest::collection::vec(proptest::sample::select(vec![
                "}", " ]]", "fi", "done", ";;", "esac", ")", "\"", "<<", "<<E\n", "\n", ";", "a ",
                "$(", "[[ ", "`",
            ]), 0..24),
            closes in 0..24usize,
        ) {
            let input = format!(
                "{}{}{}{}", opener.repeat(depth), mixed.concat(), tail.concat(), ")".repeat(closes)
            );
            let _ = parse(&input);
            let work = budget::work();
            let tokens = (depth + mixed.len() + tail.len() + closes) as u64;
            proptest::prop_assert!(!budget::spent(), "spent the budget on {input:?}");
            proptest::prop_assert!(work <= 4 * tokens + 16, "{work} entries for {tokens} tokens: {input:?}");
        }
    }

    const OPENERS: [&str; 14] = [
        "{\n", "{ ", "[[ a\n", "if a; then\n", "for x in a; do\n", "while a; do\n", "case x in a)\n",
        "function f {\n", "(\n", "$(", "\"$(", "<(", "$([[ ", "$({ ",
    ];

    /// Every committed seed of the two command-string fuzz targets parses without spending the
    /// budget, and in work linear in its length.
    ///
    /// `classifier_terminates_on_the_committed_fuzz_corpus` times the `parse` seeds against a
    /// clock; this counts work instead, and also walks `explain_render`, whose seed is the
    /// unclosed-brace-nest timeout. Enumerating the directories means a seed committed later is
    /// covered without editing this list.
    #[test]
    fn committed_command_seeds_parse_in_linear_work() {
        let root = std::path::Path::new(env!("CARGO_MANIFEST_DIR")).join("fuzz/corpus");
        let mut checked = 0;
        for target in ["parse", "explain_render"] {
            let dir = std::fs::read_dir(root.join(target)).expect("the fuzz corpus is committed");
            for path in dir.flatten().map(|e| e.path()) {
                if !path.file_name().and_then(|n| n.to_str()).is_some_and(|n| n.starts_with("seed-")) {
                    continue;
                }
                let text = String::from_utf8_lossy(&std::fs::read(&path).expect("readable seed")).into_owned();
                // A backtick body stays raw text in the tree and is parsed when classified, which
                // is where the brace-nest seed does its work, so each body is parsed here too.
                for piece in std::iter::once(text.as_str()).chain(text.split('`').skip(1).step_by(2)) {
                    let _ = parse(piece);
                    let (work, len) = (budget::work(), piece.len() as u64);
                    assert!(!budget::spent(), "{} spent the parse budget", path.display());
                    assert!(work <= len + 16, "{} cost {work} entries for {len} bytes", path.display());
                }
                checked += 1;
            }
        }
        assert!(checked >= 16, "only {checked} seeds found; the corpus has moved");
    }

    /// The step budget refuses nothing real: no registry example spends it, and long real shapes
    /// (a big heredoc commit message, a long flat script) stay far inside their allowance.
    #[test]
    fn the_step_budget_refuses_nothing_real() {
        for (_, safe, denied) in crate::registry::corpus_examples() {
            for example in safe.iter().chain(denied.iter()) {
                let _ = parse(example);
                assert!(!budget::spent(), "a registry example spent the step budget: {example}");
            }
        }
        let message = "it's a line of prose (with parens) and $vars\n".repeat(5_000);
        for text in [
            format!("git commit -m \"$(cat <<'EOF'\n{message}EOF\n)\""),
            "ls -la foo/bar; ".repeat(20_000),
        ] {
            assert!(parse(&text).is_some(), "a long real command no longer parses");
            let (steps, len) = (budget::steps(), text.len() as u64);
            assert!(
                steps * 4 < budget::STEPS_PER_BYTE * len,
                "{len} bytes of ordinary input spent {steps} steps, within 4x of the allowance"
            );
        }
    }

    fn p(input: &str) -> Script {
        parse(input).unwrap_or_else(|| panic!("failed to parse: {input}"))
    }

    fn words(script: &Script) -> Vec<String> {
        match &script.0[0].pipeline.commands[0] {
            Cmd::Simple(s) => s.words.iter().map(|w| w.eval()).collect(),
            _ => panic!("expected simple command"),
        }
    }

    fn simple(script: &Script) -> &SimpleCmd {
        match &script.0[0].pipeline.commands[0] {
            Cmd::Simple(s) => s,
            _ => panic!("expected simple command"),
        }
    }

    #[test]
    fn simple_command() { assert_eq!(words(&p("echo hello")), ["echo", "hello"]); }
    #[test]
    fn flags() { assert_eq!(words(&p("ls -la")), ["ls", "-la"]); }
    #[test]
    fn single_quoted() { assert_eq!(words(&p("echo 'hello world'")), ["echo", "hello world"]); }
    #[test]
    fn double_quoted() { assert_eq!(words(&p("echo \"hello world\"")), ["echo", "hello world"]); }
    #[test]
    fn mixed_quotes() { assert_eq!(words(&p("jq '.key' file.json")), ["jq", ".key", "file.json"]); }

    #[test]
    fn pipeline_test() { assert_eq!(p("grep foo | head -5").0[0].pipeline.commands.len(), 2); }
    #[test]
    fn sequence_and() { assert_eq!(p("ls && echo done").0[0].op, Some(ListOp::And)); }
    #[test]
    fn sequence_semi() { assert_eq!(p("ls; echo done").0.len(), 2); }
    #[test]
    fn newline_separator() { assert_eq!(p("echo foo\necho bar").0.len(), 2); }
    #[test]
    fn blank_line_between_statements() { assert_eq!(p("echo foo\n\necho bar").0.len(), 2); }
    #[test]
    fn multiple_blank_lines() { assert_eq!(p("echo foo\n\n\n\necho bar").0.len(), 2); }
    #[test]
    fn blank_line_with_whitespace() { assert_eq!(p("echo foo\n   \necho bar").0.len(), 2); }
    #[test]
    fn comment_between_statements() { assert_eq!(p("echo foo\n# comment\necho bar").0.len(), 2); }
    #[test]
    fn semi_then_blank() { assert_eq!(p("echo foo;\n\necho bar").0.len(), 2); }
    #[test]
    fn and_then_blank() { assert_eq!(p("echo foo &&\n\necho bar").0.len(), 2); }

    #[test]
    fn brace_group_simple() {
        assert!(matches!(
            &p("{ echo hello; }").0[0].pipeline.commands[0],
            Cmd::BraceGroup { body, redirs } if body.0.len() == 1 && redirs.is_empty()
        ));
    }
    #[test]
    fn brace_group_multiple_stmts() {
        if let Cmd::BraceGroup { body, .. } = &p("{ echo a; echo b; echo c; }").0[0].pipeline.commands[0] {
            assert_eq!(body.0.len(), 3);
        } else { panic!("expected BraceGroup"); }
    }
    #[test]
    fn brace_group_with_redirect() {
        if let Cmd::BraceGroup { redirs, .. } = &p("{ echo a; echo b; } > /tmp/out.txt").0[0].pipeline.commands[0] {
            assert_eq!(redirs.len(), 1);
            assert!(matches!(redirs[0], Redir::Write { .. }));
        } else { panic!("expected BraceGroup"); }
    }
    #[test]
    fn brace_group_with_append_redirect() {
        if let Cmd::BraceGroup { redirs, .. } = &p("{ echo a; } >> log.txt").0[0].pipeline.commands[0] {
            assert!(matches!(redirs[0], Redir::Write { mode: WriteMode::Append, .. }));
        } else { panic!("expected BraceGroup"); }
    }
    #[test]
    fn brace_group_with_stderr_redirect() {
        if let Cmd::BraceGroup { redirs, .. } = &p("{ echo a; } 2>&1").0[0].pipeline.commands[0] {
            assert!(matches!(redirs[0], Redir::DupFd { src: 2, .. }));
        } else { panic!("expected BraceGroup"); }
    }
    #[test]
    fn brace_group_newline_separated() {
        if let Cmd::BraceGroup { body, .. } = &p("{\n  echo a\n  echo b\n}").0[0].pipeline.commands[0] {
            assert_eq!(body.0.len(), 2);
        } else { panic!("expected BraceGroup"); }
    }
    /// `time` is a reserved word, so it may prefix a COMPOUND command — and those forms did not
    /// parse at all, falling to "could not parse this command" on valid shell.
    ///
    /// The compound must survive as itself: if `time` were swallowed into a simple command the
    /// subshell would vanish, and with it whatever the inner command is. That is what makes the
    /// classification still follow the inner command rather than the wrapper.
    #[test]
    fn time_keyword_prefixes_a_compound() {
        for (src, want_subshell) in
            [("time (ls)", true), ("time -p (ls)", true), ("time { ls; }", false)]
        {
            let pl = &p(src).0[0].pipeline;
            assert_eq!(pl.commands.len(), 1, "{src}: one compound command");
            if want_subshell {
                assert!(matches!(&pl.commands[0], Cmd::Subshell { .. }), "{src}: kept the subshell");
            } else {
                assert!(matches!(&pl.commands[0], Cmd::BraceGroup { .. }), "{src}: kept the group");
            }
        }
        // A pipeline inside the subshell survives too.
        let pl = &p("time (ls | head -5)").0[0].pipeline;
        assert!(matches!(&pl.commands[0], Cmd::Subshell { .. }));

        // NOT consumed for a simple command: `time ls` keeps going through the wrapper entry in
        // commands/wrappers/time.toml, so this fix cannot move a path that already worked.
        let pl = &p("time ls").0[0].pipeline;
        assert!(matches!(&pl.commands[0], Cmd::Simple(_)), "time ls stays a simple command");

        // And a command genuinely NAMED time-something is not mistaken for the keyword.
        let pl = &p("timeout 5 ls").0[0].pipeline;
        assert!(matches!(&pl.commands[0], Cmd::Simple(_)), "timeout is not the time keyword");

        // `! time (cmd)` parses — the bang is read first, then the keyword. The reverse spelling
        // `time ! (cmd)` does NOT, and is a known accepted false deny (see the fn's doc comment).
        // Pinned so that if anyone ever moves the bang handling, the change is deliberate: this
        // assertion flipping is the signal that the ordering was touched.
        let pl = &p("! time (ls)").0[0].pipeline;
        assert!(pl.bang, "the bang survives the time keyword");
        assert!(matches!(&pl.commands[0], Cmd::Subshell { .. }), "and the compound survives too");
    }

    #[test]
    fn brace_group_in_pipeline() {
        let pl = &p("{ echo a; echo b; } | grep a").0[0].pipeline;
        assert_eq!(pl.commands.len(), 2);
        assert!(matches!(&pl.commands[0], Cmd::BraceGroup { .. }));
    }
    #[test]
    fn brace_group_followed_by_other() {
        let stmts = &p("{ echo a; }; echo b").0;
        assert_eq!(stmts.len(), 2);
        assert!(matches!(&stmts[0].pipeline.commands[0], Cmd::BraceGroup { .. }));
    }
    #[test]
    fn brace_group_nested() {
        if let Cmd::BraceGroup { body, .. } = &p("{ { echo inner; }; echo outer; }").0[0].pipeline.commands[0] {
            assert_eq!(body.0.len(), 2);
            assert!(matches!(&body.0[0].pipeline.commands[0], Cmd::BraceGroup { .. }));
        } else { panic!("expected outer BraceGroup"); }
    }
    #[test]
    fn brace_group_with_subshell_inside() {
        if let Cmd::BraceGroup { body, .. } = &p("{ (echo sub); echo grp; }").0[0].pipeline.commands[0] {
            assert_eq!(body.0.len(), 2);
            assert!(matches!(&body.0[0].pipeline.commands[0], Cmd::Subshell { .. }));
        } else { panic!("expected BraceGroup"); }
    }
    #[test]
    fn brace_open_requires_whitespace() {
        // {echo (no space) is NOT a brace group; it's a literal word
        // that becomes part of a simple command. Parser should not
        // treat it as a brace group.
        let cmds = &p("{echo a}").0;
        // Either parsed as a simple_cmd with a literal `{echo` token,
        // or fails. Either way, it should NOT be a BraceGroup.
        if !cmds.is_empty() {
            assert!(!matches!(&cmds[0].pipeline.commands[0], Cmd::BraceGroup { .. }));
        }
    }
    #[test]
    fn subshell_with_redirect() {
        if let Cmd::Subshell { redirs, .. } = &p("(echo hello) > /tmp/out.txt").0[0].pipeline.commands[0] {
            assert_eq!(redirs.len(), 1);
        } else { panic!("expected Subshell with redir"); }
    }
    #[test]
    fn for_loop_with_redirect() {
        if let Cmd::For { redirs, .. } = &p("for f in a b; do echo $f; done 2>/dev/null").0[0].pipeline.commands[0] {
            assert_eq!(redirs.len(), 1);
        } else { panic!("expected For with redir"); }
    }
    #[test]
    fn for_loop_redirect_then_pipe() {
        // `done 2>&1 | head` — redirect on the loop, then a pipe.
        let pl = &p("for f in a b; do echo $f; done 2>&1 | head -5").0[0].pipeline;
        assert_eq!(pl.commands.len(), 2);
        assert!(matches!(&pl.commands[0], Cmd::For { redirs, .. } if redirs.len() == 1));
    }
    #[test]
    fn while_and_if_with_redirect() {
        assert!(matches!(
            &p("while true; do echo x; done 2>/dev/null").0[0].pipeline.commands[0],
            Cmd::While { redirs, .. } if redirs.len() == 1
        ));
        assert!(matches!(
            &p("if true; then echo x; fi 2>&1").0[0].pipeline.commands[0],
            Cmd::If { redirs, .. } if redirs.len() == 1
        ));
    }
    #[test]
    fn background() { assert_eq!(p("ls & echo done").0[0].op, Some(ListOp::Amp)); }

    #[test]
    fn redirect_dev_null() {
        let s = p("echo hello > /dev/null");
        let cmd = simple(&s);
        assert_eq!(cmd.words.len(), 2);
        assert!(matches!(&cmd.redirs[0], Redir::Write { fd: 1, mode: WriteMode::Truncate, .. }));
    }
    #[test]
    fn redirect_stderr() {
        assert!(matches!(&simple(&p("echo hello 2>&1")).redirs[0], Redir::DupFd { src: 2, dst } if dst == "1"));
    }
    #[test]
    fn here_string() {
        assert!(matches!(&simple(&p("grep -c , <<< 'hello,world,test'")).redirs[0], Redir::HereStr(_)));
    }
    #[test]
    fn heredoc_bare() {
        assert!(matches!(&simple(&p("cat <<EOF")).redirs[0], Redir::HereDoc { delimiter, strip_tabs: false, .. } if delimiter == "EOF"));
    }
    #[test]
    fn heredoc_with_content() {
        let s = p("cat <<EOF\nhello world\nEOF");
        assert!(matches!(&simple(&s).redirs[0], Redir::HereDoc { delimiter, .. } if delimiter == "EOF"));
    }
    #[test]
    fn heredoc_quoted_delimiter() {
        assert!(matches!(&simple(&p("cat <<'EOF'")).redirs[0], Redir::HereDoc { delimiter, .. } if delimiter == "EOF"));
    }
    #[test]
    fn heredoc_strip_tabs() {
        assert!(matches!(&simple(&p("cat <<-EOF")).redirs[0], Redir::HereDoc { strip_tabs: true, .. }));
    }
    #[test]
    fn heredoc_pipe_on_command_line() {
        // Correct bash: pipe is on the command line BEFORE the body,
        // body terminator is on its own line.
        let s = p("cat <<EOF | grep hello\nhello\nEOF");
        assert_eq!(s.0[0].pipeline.commands.len(), 2);
    }
    #[test]
    fn heredoc_body_does_not_swallow_pipe() {
        // Regression for the `cat <<EOF | bash\n...\nEOF` bypass: the
        // heredoc parser must NOT consume the pipe + downstream
        // commands as part of the body.
        let s = p("cat <<EOF | bash\nrm\nEOF");
        assert_eq!(
            s.0[0].pipeline.commands.len(),
            2,
            "pipeline must keep `bash` as a second command"
        );
    }
    #[test]
    fn heredoc_followed_by_next_statement() {
        // After the heredoc body terminator, the script can continue
        // with another statement.
        let s = p("cat <<EOF\nhello\nEOF\nls");
        assert_eq!(s.0.len(), 2);
    }

    #[test]
    fn env_prefix() {
        let s = p("FOO='bar baz' ls -la");
        let cmd = simple(&s);
        assert_eq!(cmd.env[0].0, "FOO");
        assert_eq!(cmd.env[0].1.eval(), "bar baz");
    }
    #[test]
    fn cmd_substitution() { assert!(matches!(&simple(&p("echo $(ls)")).words[1].0[0], WordPart::CmdSub(_))); }
    #[test]
    fn backtick_substitution() {
        // `pwd` declares `[command.output]`, so its value is bounded rather than worst-cased —
        // and a backtick must reach that the same way `$( … )` does.
        assert_eq!(simple(&p("ls `pwd`")).words[1].eval(), "__SAFE_CHAINS_CMDSUB_WORKTREE__");
        // An undeclared inner command keeps the opaque sentinel.
        assert_eq!(simple(&p("ls `hostname`")).words[1].eval(), "__SAFE_CHAINS_CMDSUB__");
    }
    #[test]
    fn nested_substitution() {
        if let WordPart::CmdSub(inner) = &simple(&p("echo $(echo $(ls))")).words[1].0[0] {
            assert!(matches!(&simple(inner).words[1].0[0], WordPart::CmdSub(_)));
        } else { panic!("expected CmdSub"); }
    }

    #[test]
    fn subshell_test() { assert!(matches!(&p("(echo hello)").0[0].pipeline.commands[0], Cmd::Subshell { .. })); }
    #[test]
    fn negation() { assert!(p("! echo hello").0[0].pipeline.bang); }

    #[test]
    fn for_loop() { assert!(matches!(&p("for x in 1 2 3; do echo $x; done").0[0].pipeline.commands[0], Cmd::For { var, .. } if var == "x")); }
    #[test]
    fn while_loop() { assert!(matches!(&p("while test -f /tmp/foo; do sleep 1; done").0[0].pipeline.commands[0], Cmd::While { .. })); }
    #[test]
    fn if_then_fi() {
        if let Cmd::If { branches, else_body, .. } = &p("if test -f foo; then echo exists; fi").0[0].pipeline.commands[0] {
            assert_eq!(branches.len(), 1);
            assert!(else_body.is_none());
        } else { panic!("expected If"); }
    }
    #[test]
    fn if_elif_else() {
        if let Cmd::If { branches, else_body, .. } = &p("if test -f a; then echo a; elif test -f b; then echo b; else echo c; fi").0[0].pipeline.commands[0] {
            assert_eq!(branches.len(), 2);
            assert!(else_body.is_some());
        } else { panic!("expected If"); }
    }

    #[test]
    fn escaped_outside_quotes() { assert_eq!(words(&p("echo hello\\ world")), ["echo", "hello world"]); }
    #[test]
    fn double_quoted_escape() { assert_eq!(words(&p("echo \"hello\\\"world\"")), ["echo", "hello\"world"]); }
    #[test]
    fn assign_subst() { assert_eq!(simple(&p("out=$(ls)")).env[0].0, "out"); }

    #[test]
    fn unmatched_single_quote_fails() { assert!(parse("echo 'hello").is_none()); }
    #[test]
    fn unmatched_double_quote_fails() { assert!(parse("echo \"hello").is_none()); }
    #[test]
    fn unclosed_subshell_fails() { assert!(parse("(echo hello").is_none()); }
    #[test]
    fn unclosed_cmd_sub_fails() { assert!(parse("echo $(ls").is_none()); }
    #[test]
    fn for_missing_do_fails() { assert!(parse("for x in 1 2 3; echo $x; done").is_none()); }
    #[test]
    fn if_missing_fi_fails() { assert!(parse("if true; then echo hello").is_none()); }

    #[test]
    fn subshell_for() {
        if let Cmd::Subshell { body, .. } = &p("(for x in 1 2; do echo $x; done)").0[0].pipeline.commands[0] {
            assert!(matches!(&body.0[0].pipeline.commands[0], Cmd::For { .. }));
        } else { panic!("expected Subshell"); }
    }
    #[test]
    fn proc_sub_input() {
        let s = p("diff <(sort a.txt) <(sort b.txt)");
        let cmd = simple(&s);
        assert_eq!(cmd.words.len(), 3);
        assert!(matches!(&cmd.words[1].0[0], WordPart::ProcSub(_)));
        assert!(matches!(&cmd.words[2].0[0], WordPart::ProcSub(_)));
    }
    #[test]
    fn proc_sub_output() {
        let s = p("tee >(grep error > /dev/null)");
        let cmd = simple(&s);
        assert_eq!(cmd.words.len(), 2);
        assert!(matches!(&cmd.words[1].0[0], WordPart::ProcSub(_)));
    }

    // === Function definitions ===
    fn func_def(s: &Script) -> (&str, &Script) {
        match &s.0[0].pipeline.commands[0] {
            Cmd::FunctionDef { name, body } => (name.as_str(), body),
            other => panic!("expected FunctionDef, got {other:?}"),
        }
    }
    #[test]
    fn function_def_posix_form() {
        let s = p("probe(){ echo hi; }");
        let (name, body) = func_def(&s);
        assert_eq!(name, "probe");
        assert_eq!(words(body), ["echo", "hi"]);
    }
    #[test]
    fn function_def_spaced_and_keyword_forms() {
        assert_eq!(func_def(&p("foo () { echo hi; }")).0, "foo");
        assert_eq!(func_def(&p("function foo { echo hi; }")).0, "foo");
        assert_eq!(func_def(&p("function foo () { echo hi; }")).0, "foo");
    }
    #[test]
    fn function_def_subshell_body() {
        let s = p("foo() ( echo sub )");
        assert_eq!(func_def(&s).0, "foo");
    }
    #[test]
    fn function_def_body_on_next_line() {
        assert_eq!(func_def(&p("foo()\n{\n  echo hi\n}")).0, "foo");
    }
    #[test]
    fn function_def_name_with_dashes_and_dots() {
        assert_eq!(func_def(&p("my-func.v2(){ echo hi; }")).0, "my-func.v2");
    }
    #[test]
    fn plain_command_is_not_a_function_def() {
        // A bare `name` with no `()` must NOT be read as a definition.
        assert!(matches!(&p("ls -la").0[0].pipeline.commands[0], Cmd::Simple(_)));
        assert!(matches!(&p("echo foo bar").0[0].pipeline.commands[0], Cmd::Simple(_)));
    }
    #[test]
    fn function_def_roundtrips() {
        let rendered = p("greet(){ echo hi; }").to_string();
        assert!(parse(&rendered).is_some(), "did not reparse: {rendered}");
        assert_eq!(func_def(&p(&rendered)).0, "greet");
    }
    #[test]
    fn comment_only() {
        let s = p("# just a comment");
        assert!(s.0.is_empty());
    }
    #[test]
    fn comment_before_command() {
        let s = p("# comment\necho hello");
        assert_eq!(words(&s), ["echo", "hello"]);
    }
    #[test]
    fn inline_comment() {
        let s = p("echo hello # this is a comment");
        assert_eq!(words(&s), ["echo", "hello"]);
    }
    #[test]
    fn comment_between_commands() {
        let s = p("echo hello\n# middle comment\necho world");
        assert_eq!(s.0.len(), 2);
    }
    #[test]
    fn comment_after_semicolon() {
        let s = p("echo hello; # comment\necho world");
        assert_eq!(s.0.len(), 2);
    }
    #[test]
    fn comment_in_for_loop() {
        assert!(parse("for x in 1 2; do\n# loop body\necho $x\ndone").is_some());
    }
    #[test]
    fn quoted_redirect_in_echo() {
        let s = p("echo 'greater > than' test");
        let cmd = simple(&s);
        assert_eq!(cmd.words.len(), 3);
        assert_eq!(cmd.redirs.len(), 0);
    }

    #[test]
    fn parses_all_safe_commands() {
        let cmds = [
            "grep foo file.txt", "cat /etc/hosts", "jq '.key' file.json", "base64 -d",
            "ls -la", "wc -l file.txt", "ps aux", "echo hello", "cat file.txt",
            "echo $(ls)", "ls `pwd`", "echo $(echo $(ls))", "echo \"$(ls)\"",
            "out=$(ls)", "out=$(git status)", "a=$(ls) b=$(pwd)",
            "(echo hello)", "(ls)", "(ls && echo done)", "(echo hello; echo world)",
            "(ls | grep foo)", "(echo hello) | grep hello", "(ls) && echo done",
            "((echo hello))", "(for x in 1 2; do echo $x; done)",
            "echo 'greater > than' test", "echo '$(safe)' arg",
            "FOO='bar baz' ls -la", "FOO=\"bar baz\" ls -la",
            "RACK_ENV=test bundle exec rspec spec/foo_spec.rb",
            "grep foo file.txt | head -5", "cat file | sort | uniq",
            "ls && echo done", "ls; echo done", "ls & echo done",
            "grep -c , <<< 'hello,world,test'",
            "cat <<EOF\nhello world\nEOF",
            "cat <<'MARKER'\nsome text\nMARKER",
            "cat <<-EOF\n\thello\nEOF",
            "echo foo\necho bar", "ls\ncat file.txt",
            "git log --oneline -20 | head -5",
            "echo hello > /dev/null", "echo hello 2> /dev/null",
            "echo hello >> /dev/null", "git log > /dev/null 2>&1",
            "ls 2>&1", "cargo clippy 2>&1", "git log < /dev/null",
            "for x in 1 2 3; do echo $x; done",
            "for f in *.txt; do cat $f | grep pattern; done",
            "for x in 1 2 3; do; done",
            "for x in 1 2; do echo $x; done; for y in a b; do echo $y; done",
            "for x in 1 2; do for y in a b; do echo $x $y; done; done",
            "for x in 1 2; do echo $x; done && echo finished",
            "for x in $(seq 1 5); do echo $x; done",
            "while test -f /tmp/foo; do sleep 1; done",
            "while ! test -f /tmp/done; do sleep 1; done",
            "until test -f /tmp/ready; do sleep 1; done",
            "if test -f foo; then echo exists; fi",
            "if test -f foo; then echo yes; else echo no; fi",
            "if test -f a; then echo a; elif test -f b; then echo b; else echo c; fi",
            "for x in 1 2; do if test $x = 1; then echo one; fi; done",
            "if true; then for x in 1 2; do echo $x; done; fi",
            "diff <(sort a.txt) <(sort b.txt)",
            "comm -23 file.txt <(sort other.txt)",
            "cat <(echo hello)",
            "# comment only",
            "# comment\necho hello",
            "echo hello # inline comment",
            "echo one\n# between\necho two",
            "! echo hello", "! test -f foo",
            "echo for; echo done; echo if; echo fi",
        ];
        let mut failures = Vec::new();
        for cmd in &cmds {
            if parse(cmd).is_none() { failures.push(*cmd); }
        }
        assert!(failures.is_empty(), "failed on {} commands:\n{}", failures.len(), failures.join("\n"));
    }

    // === Balanced-scan divergence guards ===
    // `cmd_sub`/`proc_sub` find their closing `)` with `find_sub_close`, then parse the bounded
    // interior. The `roundtrip` proptest exercises this, but its `arb_shell_word` is paren-free, so
    // these lock the case it can't reach: a `)` inside a quote / escape / backtick / nested sub must
    // NOT be mistaken for the substitution's own close.
    fn inner_sub(s: &Script) -> &Script {
        match &simple(s).words[1].0[0] {
            WordPart::CmdSub(inner) | WordPart::ProcSub(inner) => inner,
            other => panic!("expected a substitution, got {other:?}"),
        }
    }

    #[test]
    fn cmd_sub_squote_paren_is_not_close() {
        assert_eq!(words(inner_sub(&p("echo $(echo ')')"))), ["echo", ")"]);
    }
    #[test]
    fn cmd_sub_dquote_paren_is_not_close() {
        assert_eq!(words(inner_sub(&p("echo $(echo \")\")"))), ["echo", ")"]);
    }
    #[test]
    fn cmd_sub_escaped_paren_is_not_close() {
        assert_eq!(words(inner_sub(&p("echo $(echo \\))"))), ["echo", ")"]);
    }
    #[test]
    fn cmd_sub_backtick_paren_is_not_close() {
        // the ) lives inside a backtick span in the sub body; the real close is the final ).
        let s = p("echo $(x `)` y)");
        let inner = simple(inner_sub(&s));
        assert_eq!(inner.words.len(), 3);
        assert!(matches!(&inner.words[1].0[0], WordPart::Backtick(_)));
    }
    #[test]
    fn cmd_sub_escaped_backtick_does_not_end_span() {
        // The `\` escapes the next backtick, so the span — and the ) inside it — belong to the sub
        // body; the real close is the final ). Until find_sub_close honored backtick escapes it
        // mis-placed the span boundary and rejected this (a fail-closed divergence from the grammar).
        let s = p("echo $(`\\`)`)");
        assert!(matches!(&simple(&s).words[1].0[0], WordPart::CmdSub(_)));
    }
    #[test]
    fn proc_sub_squote_paren_is_not_close() {
        assert_eq!(words(inner_sub(&p("cat <(grep ')' f)"))), ["grep", ")", "f"]);
    }
    #[test]
    fn proc_sub_out_squote_paren_is_not_close() {
        assert_eq!(words(inner_sub(&p("tee >(grep ')' f)"))), ["grep", ")", "f"]);
    }
    #[test]
    fn cmd_sub_nested_picks_outer_close() {
        let s = p("echo $(a $(b) c)");
        let inner = simple(inner_sub(&s));
        assert_eq!(inner.words.len(), 3);
        assert!(matches!(&inner.words[1].0[0], WordPart::CmdSub(_)));
    }
    #[test]
    fn cmd_sub_literal_after_close_stays_in_outer_word() {
        let s = p("echo $(ls)tail");
        let w = &simple(&s).words[1];
        assert_eq!(w.0.len(), 2);
        assert!(matches!(&w.0[0], WordPart::CmdSub(_)));
        assert!(matches!(&w.0[1], WordPart::Lit(s) if s == "tail"));
    }
    #[test]
    fn cmd_sub_heredoc_body_paren_does_not_close() {
        // The ) sits in the heredoc body (drained out-of-band), so it must not close the sub — the
        // real close is the final ). find_sub_close can't see heredocs, so sub_body falls back to the
        // full grammar here. This parsed before the balanced-scan rewrite and must keep parsing.
        let s = p("x=$(cat <<EOF\na)b\nEOF\n)");
        assert!(matches!(&simple(&s).env[0].1.0[0], WordPart::CmdSub(_)));
    }
    #[test]
    fn cmd_sub_with_only_a_quoted_paren_is_unclosed() {
        // the sole ) is single-quoted, so the sub never closes → whole parse fails (fail closed).
        assert!(parse("echo $(echo ')").is_none());
    }
    #[test]
    fn proc_sub_with_only_a_quoted_paren_is_unclosed() {
        assert!(parse("cat <(grep ')").is_none());
    }
}