car-policy 0.63.0

//! Whether a shell command line runs a given program.
//!
//! The egress inspector denies `nc` and `netcat` *when they run*. A raw
//! substring test denied every `rsync` and `async fn` (car#3409), and a
//! whole-word test anywhere denied `git commit -m "fix nc"` and `man nc`. So
//! this reads the line the way a shell would — quoting, comments,
//! substitutions, here-documents — and, within each simple command, finds:
//!
//! - the command word itself (`nc …`, `/usr/bin/nc …`, `"nc" …`), and
//! - any argument equal to the program or a path to it once quoting is
//!   removed (`'nc'`, `\nc` and `"nc"` are still one word a shell runs),
//!   because a program that takes a command as its arguments runs it (`sudo nc`,
//!   `timeout 5 nc`, `docker run alpine nc -z db 5432`, `watch nc`). The list
//!   of such programs never ends, so it is not kept; the short list kept is
//!   the opposite one, [`NAMING`] — programs that only name, look up, install,
//!   print, inspect or manage their arguments (`man nc`, `brew install netcat`,
//!   `grep nc f`, `pkill nc`), minus their runner forms (`npm exec`,
//!   `git bisect run`, `rg --pre`, `vim -c`, `make --eval`, `cargo --config`).
//!
//! A quoted argument holding whitespace is a string, not a program name, and is
//! left alone (`git commit -m "fix nc"`), except where the shell itself runs it
//! as a script: `sh|bash|zsh|dash|ksh|fish -c`, `su -c`, `script -c`,
//! `env -S`, `eval`, a here-string or here-document whose reader is a shell
//! (`source`/`.` included) or pipes into one, what `echo`/`printf` print into a
//! pipe that reaches a shell, and a `<(…)` given to a shell or `source`/`.`.
//! So is the text a runner form runs: what follows each `!` in a `vim -c`,
//! `--cmd` or `+…` script (also `vi`, `nvim`, `view`, `ex`), the makefile text
//! of `make --eval`/`-E` with each `$(shell …)` in it, a program-valued key of
//! `cargo --config` (`runner`, `linker`, `rustc`, `rustc-wrapper`), and the
//! program `rg --pre=` names.
//! `$(…)`, backticks, `<(…)` and `>(…)` are followed wherever they occur,
//! including inside `${…}` and an unquoted here-document.
//!
//! It is a heuristic, not a shell parser. Not found: a multi-word quoted
//! argument of a program other than those (`ssh -o ProxyCommand='nc %h %p'`,
//! `tmux new 'nc …'`, `python3 -c "os.system('nc …')"`), a script read from a
//! file (`bash script.sh`, `cat f | sh`, `echo … > f; sh f`), a command built
//! at run time (`N=nc; $N`, `bash -c "$(echo nc …)"`, `{nc,host,1}`), a locale
//! string (`$"nc"`), an option or assignment value (`-o ProxyCommand=nc`,
//! `LESSOPEN='|nc …' less`), a pager or editor running one some other way
//! (`less +'!nc'`, `nano --speller=…`, `vim -c 'call system(…)'`), the
//! arguments `cargo run -- nc …` passes to the user's own program, and a
//! Makefile target that runs it. Input a shell would reject as
//! unterminated (an open quote, substitution or here-document) is not given
//! the benefit of the doubt: if the program's name appears in it as a whole
//! word, it counts.

/// How deep nested command text is followed. Deeper counts as a hit: no real
/// command nests this far, and stopping silently would be a way through.
const MAX_NESTING: usize = 8;

/// What [`find_command`] reports for text nested deeper than [`MAX_NESTING`].
pub(crate) const TOO_DEEP: &str = "command nesting deeper than 8";

/// Words that come before a command without being one.
const RESERVED: &[&str] = &[
    "if", "then", "else", "elif", "do", "while", "until", "!", "time",
];

/// Programs that only name, look up, install, print, inspect or manage their
/// arguments, so an argument equal to a program is not that program running.
/// The runner forms of a few of them (`npm exec`, `git bisect run`,
/// `rg --pre`, `vim -c`, `make --eval`, `cargo --config`) are not exempt; see
/// [`runs_an_argument`].
const NAMING: &[&str] = &[
    // Name, look up, install, print.
    "man", "which", "type", "whatis", "whereis", "apropos", "info", "tldr", "brew", "port", "apt",
    "apt-get", "dnf", "yum", "pip", "pip3", "npm", "pnpm", "yarn", "cargo", "make", "grep",
    "egrep", "rg", "ag", "echo", "printf", "git", // Files and binaries.
    "ls", "cat", "less", "head", "tail", "file", "stat", "otool", "strings", "codesign", "cp",
    "mv", "ln", "rm", "mkdir", "touch", "chmod", "du", "diff", "cd", "vim", "nano",
    // Processes.
    "lsof", "pgrep", "pkill", "killall",
];

/// Shells whose `-c` script, `<<<` here-string and here-document are command
/// text, wherever they appear in a command (`sudo sh`, `xargs sh -c`).
const SHELLS: &[&str] = &["sh", "bash", "zsh", "dash", "ksh", "fish"];

/// Builtins that run a file as shell script, counted only as the command word:
/// `.` is an ordinary argument everywhere else (`jq .`, `find .`).
const SOURCERS: &[&str] = &["source", "."];

/// Naming programs whose output is the text of their arguments, so piped into
/// a shell their arguments are script.
const PRINTERS: &[&str] = &["echo", "printf"];

/// vim and the editors that share its `-c`/`+` scripts.
const VIMS: &[&str] = &["vim", "vi", "nvim", "view", "ex"];

/// make and its GNU name.
const MAKES: &[&str] = &["make", "gmake"];

/// make's options whose value is makefile text.
const MAKE_EVAL: [&str; 2] = ["--eval", "-E"];

/// cargo configuration keys whose value is a program cargo runs.
const CARGO_PROGRAM_KEYS: &[&str] = &[
    "runner",
    "linker",
    "rustc",
    "rustc-wrapper",
    "rustc-workspace-wrapper",
];

/// Shell options that take the next word as their value.
const SHELL_VALUE_OPTIONS: &[&str] = &["-o", "+o", "-O", "+O", "--rcfile", "--init-file"];

#[derive(Clone, Copy, PartialEq)]
enum SepKind {
    /// `|` or `|&`: the next command reads this one's output.
    Pipe,
    Other,
}

enum Tok {
    /// A word with quoting removed; `quoted` if any part of it was quoted or
    /// escaped; `procsubs` holds the body of each `<(…)` in it.
    Word {
        text: String,
        quoted: bool,
        procsubs: Vec<String>,
    },
    Sep(SepKind),
    /// A redirection operator; the word after it is its target, not a command.
    Redir(String),
    /// A here-document body; `literal` when its delimiter was quoted.
    HereDoc {
        body: String,
        literal: bool,
    },
}

/// A here-document announced on the current line: its delimiter, whether
/// leading tabs are stripped (`<<-`), and the index of its placeholder token,
/// which sits where the `<<` did so the body belongs to that command.
struct PendingHereDoc {
    delimiter: String,
    strip_tabs: bool,
    tok: usize,
}

/// One word being assembled.
#[derive(Default)]
struct WordBuf {
    text: String,
    started: bool,
    quoted: bool,
    procsubs: Vec<String>,
}

/// Finish the word being assembled: a here-document's delimiter, or a word.
fn end_word(
    word: &mut WordBuf,
    toks: &mut Vec<Tok>,
    expect_delimiter: &mut Option<bool>,
    pending: &mut Vec<PendingHereDoc>,
    case_depth: &mut usize,
) {
    if !word.started {
        return;
    }
    let done = std::mem::take(word);
    // A `case` pattern's `)` must not close an enclosing `$(`.
    if !done.quoted && expect_delimiter.is_none() {
        match done.text.as_str() {
            "case" => *case_depth += 1,
            "esac" => *case_depth = case_depth.saturating_sub(1),
            _ => {}
        }
    }
    match expect_delimiter.take() {
        Some(strip_tabs) => {
            toks.push(Tok::HereDoc {
                body: String::new(),
                literal: done.quoted,
            });
            pending.push(PendingHereDoc {
                delimiter: done.text,
                strip_tabs,
                tok: toks.len() - 1,
            });
        }
        None => toks.push(Tok::Word {
            text: done.text,
            quoted: done.quoted,
            procsubs: done.procsubs,
        }),
    }
}

/// The first of `programs` that `text` runs, if any — or [`TOO_DEEP`].
pub(crate) fn find_command(text: &str, programs: &[&'static str]) -> Option<&'static str> {
    scan(text, programs, 0)
}

fn scan(text: &str, programs: &[&'static str], depth: usize) -> Option<&'static str> {
    if depth > MAX_NESTING {
        return Some(TOO_DEEP);
    }
    let chars: Vec<char> = text.chars().collect();
    let mut lexer = Lexer::new(&chars, programs, depth);
    let toks = lexer.lex(false);
    lexer
        .hit
        .or_else(|| analyze(&toks, programs, depth))
        .or_else(|| {
            // Unterminated: a shell would reject it, so there is no reading to
            // trust. Fall back to the name appearing as a whole word.
            if lexer.broken {
                programs.iter().copied().find(|p| has_whole_word(text, p))
            } else {
                None
            }
        })
}

struct Lexer<'a> {
    chars: &'a [char],
    i: usize,
    programs: &'a [&'static str],
    depth: usize,
    hit: Option<&'static str>,
    broken: bool,
}

impl<'a> Lexer<'a> {
    fn new(chars: &'a [char], programs: &'a [&'static str], depth: usize) -> Self {
        Self {
            chars,
            i: 0,
            programs,
            depth,
            hit: None,
            broken: false,
        }
    }

    fn peek(&self, offset: usize) -> Option<char> {
        self.chars.get(self.i + offset).copied()
    }

    /// Scan nested command text given as a string.
    fn nested_text(&mut self, text: &str) {
        if self.hit.is_none() {
            self.hit = scan(text, self.programs, self.depth + 1);
        }
    }

    /// Lex `$(…)`, `<(…)` or `>(…)` from just after its `(`, and analyze what
    /// it runs.
    fn nested_paren(&mut self) {
        if self.depth + 1 > MAX_NESTING {
            self.hit.get_or_insert(TOO_DEEP);
            return;
        }
        self.depth += 1;
        let toks = self.lex(true);
        if self.hit.is_none() {
            self.hit = analyze(&toks, self.programs, self.depth);
        }
        self.depth -= 1;
    }

    /// Tokens up to the end of input or, with `in_paren`, the `)` that closes
    /// the substitution being lexed (consumed).
    fn lex(&mut self, in_paren: bool) -> Vec<Tok> {
        let mut toks = Vec::new();
        let mut word = WordBuf::default();
        let mut parens = 0usize;
        let mut expect_delimiter: Option<bool> = None;
        let mut pending: Vec<PendingHereDoc> = Vec::new();
        let mut case_depth = 0usize;

        while self.i < self.chars.len() && self.hit.is_none() {
            let c = self.chars[self.i];
            let next = self.peek(1);
            match c {
                '\\' => match next {
                    Some('\n') => self.i += 2,
                    Some('\r') if self.peek(2) == Some('\n') => self.i += 3,
                    Some(n) => {
                        word.text.push(n);
                        word.started = true;
                        word.quoted = true;
                        self.i += 2;
                    }
                    None => self.i += 1,
                },
                '\'' => {
                    self.i += 1;
                    match self.find('\'') {
                        Some(end) => {
                            word.text.extend(&self.chars[self.i..end]);
                            self.i = end + 1;
                        }
                        None => self.unterminated(),
                    }
                    word.started = true;
                    word.quoted = true;
                }
                '"' => {
                    self.i += 1;
                    self.double_quoted(&mut word.text);
                    word.started = true;
                    word.quoted = true;
                }
                '$' if next == Some('\'') => {
                    self.i += 2;
                    self.ansi_c_quoted(&mut word.text);
                    word.started = true;
                    word.quoted = true;
                }
                '$' if next == Some('{') => {
                    let start = self.i;
                    self.i += 2;
                    self.skip_braced();
                    word.text
                        .extend(&self.chars[start..self.i.min(self.chars.len())]);
                    word.started = true;
                }
                '$' | '<' | '>' if next == Some('(') => {
                    self.i += 2;
                    let start = self.i;
                    self.nested_paren();
                    if c == '<' {
                        // Kept so a shell given it as an operand can read it
                        // as the script it is (`bash <(echo …)`).
                        let end = self.i.saturating_sub(1).max(start);
                        word.procsubs.push(self.chars[start..end].iter().collect());
                    }
                    word.started = true;
                }
                '`' => {
                    self.i += 1;
                    let body = self.backtick_body();
                    self.nested_text(&body);
                    word.started = true;
                }
                '#' if !word.started => {
                    while self.i < self.chars.len() && self.chars[self.i] != '\n' {
                        self.i += 1;
                    }
                }
                '<' | '>' => {
                    // A file-descriptor number belongs to the redirection.
                    if word.started && !word.quoted && word.text.chars().all(|d| d.is_ascii_digit())
                    {
                        word = WordBuf::default();
                    }
                    end_word(
                        &mut word,
                        &mut toks,
                        &mut expect_delimiter,
                        &mut pending,
                        &mut case_depth,
                    );
                    let start = self.i;
                    while self.i < self.chars.len() && matches!(self.chars[self.i], '<' | '>' | '&')
                    {
                        self.i += 1;
                    }
                    let mut op: String = self.chars[start..self.i].iter().collect();
                    if op == "<<" && self.peek(0) == Some('-') {
                        op.push('-');
                        self.i += 1;
                    }
                    match op.as_str() {
                        "<<" => expect_delimiter = Some(false),
                        "<<-" => expect_delimiter = Some(true),
                        _ => {}
                    }
                    toks.push(Tok::Redir(op));
                }
                '&' if next == Some('>') => {
                    end_word(
                        &mut word,
                        &mut toks,
                        &mut expect_delimiter,
                        &mut pending,
                        &mut case_depth,
                    );
                    let start = self.i;
                    while self.i < self.chars.len() && matches!(self.chars[self.i], '>' | '&') {
                        self.i += 1;
                    }
                    toks.push(Tok::Redir(self.chars[start..self.i].iter().collect()));
                }
                '\n' => {
                    end_word(
                        &mut word,
                        &mut toks,
                        &mut expect_delimiter,
                        &mut pending,
                        &mut case_depth,
                    );
                    self.i += 1;
                    for doc in std::mem::take(&mut pending) {
                        let text = self.heredoc_body(&doc.delimiter, doc.strip_tabs);
                        if let Some(Tok::HereDoc { body, .. }) = toks.get_mut(doc.tok) {
                            *body = text;
                        }
                    }
                    toks.push(Tok::Sep(SepKind::Other));
                }
                '|' => {
                    end_word(
                        &mut word,
                        &mut toks,
                        &mut expect_delimiter,
                        &mut pending,
                        &mut case_depth,
                    );
                    let kind = if next == Some('|') {
                        self.i += 2;
                        SepKind::Other
                    } else {
                        self.i += if next == Some('&') { 2 } else { 1 };
                        SepKind::Pipe
                    };
                    toks.push(Tok::Sep(kind));
                }
                ';' | '&' => {
                    end_word(
                        &mut word,
                        &mut toks,
                        &mut expect_delimiter,
                        &mut pending,
                        &mut case_depth,
                    );
                    self.i += 1;
                    toks.push(Tok::Sep(SepKind::Other));
                }
                '(' => {
                    end_word(
                        &mut word,
                        &mut toks,
                        &mut expect_delimiter,
                        &mut pending,
                        &mut case_depth,
                    );
                    parens += 1;
                    self.i += 1;
                    toks.push(Tok::Sep(SepKind::Other));
                }
                ')' => {
                    end_word(
                        &mut word,
                        &mut toks,
                        &mut expect_delimiter,
                        &mut pending,
                        &mut case_depth,
                    );
                    self.i += 1;
                    if parens == 0 && case_depth == 0 && in_paren {
                        self.close_heredocs(&pending);
                        return toks;
                    }
                    parens = parens.saturating_sub(1);
                    toks.push(Tok::Sep(SepKind::Other));
                }
                '{' | '}'
                    if !word.started && next.is_none_or(|n| n.is_whitespace() || n == ';') =>
                {
                    self.i += 1;
                    toks.push(Tok::Sep(SepKind::Other));
                }
                c if c.is_whitespace() => {
                    end_word(
                        &mut word,
                        &mut toks,
                        &mut expect_delimiter,
                        &mut pending,
                        &mut case_depth,
                    );
                    self.i += 1;
                }
                c => {
                    word.text.push(c);
                    word.started = true;
                    self.i += 1;
                }
            }
        }
        end_word(
            &mut word,
            &mut toks,
            &mut expect_delimiter,
            &mut pending,
            &mut case_depth,
        );
        self.close_heredocs(&pending);
        if in_paren && self.hit.is_none() {
            self.unterminated();
        }
        toks
    }

    /// A here-document whose body never arrived is unterminated input.
    fn close_heredocs(&mut self, pending: &[PendingHereDoc]) {
        if !pending.is_empty() {
            self.unterminated();
        }
    }

    fn unterminated(&mut self) {
        self.broken = true;
        self.i = self.chars.len();
    }

    /// Index of the next `target` at or after the cursor.
    fn find(&self, target: char) -> Option<usize> {
        (self.i..self.chars.len()).find(|&j| self.chars[j] == target)
    }

    /// ANSI-C quoting, from just after `$'` through the closing `'`; `\'` does
    /// not end it.
    fn ansi_c_quoted(&mut self, word: &mut String) {
        loop {
            match self.peek(0) {
                None => return self.unterminated(),
                Some('\\') => {
                    if let Some(n) = self.peek(1) {
                        word.push(n);
                    }
                    self.i += 2;
                }
                Some('\'') => {
                    self.i += 1;
                    return;
                }
                Some(ch) => {
                    word.push(ch);
                    self.i += 1;
                }
            }
        }
    }

    /// The inside of a double-quoted string, from just after its `"` through
    /// the closing one. Substitutions in it are followed.
    fn double_quoted(&mut self, word: &mut String) {
        while self.hit.is_none() {
            match self.peek(0) {
                None => return self.unterminated(),
                Some('"') => {
                    self.i += 1;
                    return;
                }
                Some('\\') => {
                    match self.peek(1) {
                        Some('\n') | None => {}
                        Some(n) if matches!(n, '"' | '\\' | '$' | '`') => word.push(n),
                        Some(n) => {
                            word.push('\\');
                            word.push(n);
                        }
                    }
                    self.i += 2;
                }
                Some('$') if self.peek(1) == Some('(') => {
                    self.i += 2;
                    self.nested_paren();
                }
                Some('$') if self.peek(1) == Some('{') => {
                    let start = self.i;
                    self.i += 2;
                    self.skip_braced();
                    word.extend(&self.chars[start..self.i.min(self.chars.len())]);
                }
                Some('`') => {
                    self.i += 1;
                    let body = self.backtick_body();
                    self.nested_text(&body);
                }
                Some(ch) => {
                    word.push(ch);
                    self.i += 1;
                }
            }
        }
    }

    /// Past the `}` closing a `${…}` that began just before the cursor,
    /// honouring quotes and nested `${`.
    fn skip_braced(&mut self) {
        let mut depth = 1usize;
        while let Some(ch) = self.peek(0) {
            match ch {
                '\\' => self.i += 2,
                '\'' => {
                    self.i += 1;
                    match self.find('\'') {
                        Some(end) => self.i = end + 1,
                        None => return self.unterminated(),
                    }
                }
                '"' => {
                    self.i += 1;
                    let mut ignored = String::new();
                    self.double_quoted(&mut ignored);
                }
                '$' if self.peek(1) == Some('{') => {
                    depth += 1;
                    self.i += 2;
                }
                '$' if self.peek(1) == Some('(') => {
                    self.i += 2;
                    self.nested_paren();
                    if self.hit.is_some() {
                        return;
                    }
                }
                '`' => {
                    self.i += 1;
                    let body = self.backtick_body();
                    self.nested_text(&body);
                    if self.hit.is_some() {
                        return;
                    }
                }
                '}' => {
                    self.i += 1;
                    depth -= 1;
                    if depth == 0 {
                        return;
                    }
                }
                _ => self.i += 1,
            }
        }
        self.unterminated();
    }

    /// The command text of a backtick substitution, from just after its
    /// opening backtick through the closing one, with `` \` ``, `\\` and `\$`
    /// unescaped the way the shell does before running it.
    fn backtick_body(&mut self) -> String {
        let mut body = String::new();
        loop {
            match self.peek(0) {
                None => {
                    self.unterminated();
                    return body;
                }
                Some('`') => {
                    self.i += 1;
                    return body;
                }
                Some('\\') => {
                    match self.peek(1) {
                        Some(n) if matches!(n, '`' | '\\' | '$') => body.push(n),
                        Some(n) => {
                            body.push('\\');
                            body.push(n);
                        }
                        None => {}
                    }
                    self.i += 2;
                }
                Some(ch) => {
                    body.push(ch);
                    self.i += 1;
                }
            }
        }
    }

    /// The lines from the cursor up to a line equal to `delimiter` (leading
    /// tabs stripped with `<<-`); the cursor ends on that line's newline.
    fn heredoc_body(&mut self, delimiter: &str, strip_tabs: bool) -> String {
        let mut body = String::new();
        while self.i < self.chars.len() {
            let end = self.find('\n').unwrap_or(self.chars.len());
            let line: String = self.chars[self.i..end].iter().collect();
            let line = line.trim_end_matches('\r');
            let candidate = if strip_tabs {
                line.trim_start_matches('\t')
            } else {
                line
            };
            if candidate == delimiter {
                self.i = end;
                return body;
            }
            body.push_str(line);
            body.push('\n');
            self.i = (end + 1).min(self.chars.len());
        }
        self.unterminated();
        body
    }
}

/// The substitutions in an unquoted here-document body: the shell runs those
/// even when no shell reads the body.
fn scan_substitutions(body: &str, programs: &[&'static str], depth: usize) -> Option<&'static str> {
    let chars: Vec<char> = body.chars().collect();
    let mut lexer = Lexer::new(&chars, programs, depth);
    while lexer.i < chars.len() && lexer.hit.is_none() {
        match (chars[lexer.i], lexer.peek(1)) {
            ('\\', _) => lexer.i += 2,
            ('$', Some('(')) => {
                lexer.i += 2;
                lexer.nested_paren();
            }
            ('`', _) => {
                lexer.i += 1;
                let text = lexer.backtick_body();
                lexer.nested_text(&text);
            }
            _ => lexer.i += 1,
        }
    }
    lexer.hit
}

/// A simple command's words, here-strings, here-documents and `<(…)` bodies.
#[derive(Default)]
struct Command<'a> {
    words: Vec<(&'a str, bool)>,
    here_strings: Vec<&'a str>,
    heredocs: Vec<(&'a str, bool)>,
    procsubs: Vec<&'a str>,
}

/// Extract the literal arguments/stdin of patch invocations using the same
/// quote and here-document handling as command detection. This does not run
/// shell expansions or read scripts from disk.
pub(crate) fn patches(text: &str) -> Vec<String> {
    fn collect(text: &str, depth: usize, out: &mut Vec<String>) {
        if depth > MAX_NESTING {
            // Still check the tool gates if nesting prevents path extraction.
            out.push(String::new());
            return;
        }
        let chars: Vec<char> = text.chars().collect();
        let mut lexer = Lexer::new(&chars, &[], 0);
        let toks = lexer.lex(false);
        for (command, _) in commands(&toks) {
            let Some(c) = command_index(&command.words) else {
                continue;
            };
            if is_naming(&command.words, c) {
                continue;
            }
            for (index, (word, _)) in command.words.iter().enumerate().skip(c) {
                let name = program_name(word);
                if matches!(name, "apply_patch" | "applypatch") {
                    let patch = command
                        .words
                        .get(index + 1)
                        .map(|(w, _)| *w)
                        .or_else(|| command.heredocs.first().map(|(body, _)| *body))
                        .or_else(|| command.here_strings.first().copied())
                        .unwrap_or_default();
                    out.push(patch.to_owned());
                    break;
                }
                if SHELLS.contains(&name) {
                    if let Some(script) = shell_script(&command.words[index + 1..]) {
                        collect(script, depth + 1, out);
                    } else {
                        for (body, _) in &command.heredocs {
                            collect(body, depth + 1, out);
                        }
                        for body in &command.here_strings {
                            collect(body, depth + 1, out);
                        }
                    }
                    break;
                }
            }
        }
    }
    let mut out = Vec::new();
    collect(text, 0, &mut out);
    out
}

/// Split tokens into simple commands, each with whether it pipes into the next.
fn commands(toks: &[Tok]) -> Vec<(Command<'_>, bool)> {
    let mut commands: Vec<(Command<'_>, bool)> = Vec::new();
    let mut current = Command::default();
    let mut iter = toks.iter();
    while let Some(tok) = iter.next() {
        match tok {
            Tok::Word {
                text,
                quoted,
                procsubs,
            } => {
                current.words.push((text, *quoted));
                current.procsubs.extend(procsubs.iter().map(String::as_str));
            }
            // A here-document's delimiter became its placeholder, not a word.
            Tok::Redir(op) if op.starts_with("<<") && op != "<<<" => {}
            Tok::Redir(op) => {
                if let Some(Tok::Word { text, .. }) = iter.next() {
                    if op == "<<<" {
                        current.here_strings.push(text);
                    }
                }
            }
            Tok::HereDoc { body, literal } => current.heredocs.push((body, *literal)),
            Tok::Sep(kind) => {
                commands.push((std::mem::take(&mut current), *kind == SepKind::Pipe));
            }
        }
    }
    commands.push((current, false));
    commands
}

/// The programs `toks` runs. With `output_to_shell`, what the commands print
/// is itself read by a shell (the body of `bash <(…)`).
fn analyze_with(
    toks: &[Tok],
    programs: &[&'static str],
    depth: usize,
    output_to_shell: bool,
) -> Option<&'static str> {
    let commands = commands(toks);
    // Walking back along each pipeline: does this command's output reach a
    // shell, and does its input (a here-document or here-string) reach one?
    let mut output = vec![false; commands.len()];
    let mut input = vec![false; commands.len()];
    for k in (0..commands.len()).rev() {
        let piped = commands[k].1 && k + 1 < commands.len();
        output[k] = if piped { input[k + 1] } else { output_to_shell };
        input[k] = runs_a_shell(&commands[k].0) || output[k];
    }
    commands
        .iter()
        .enumerate()
        .find_map(|(k, (command, _))| scan_command(command, input[k], output[k], programs, depth))
}

fn analyze(toks: &[Tok], programs: &[&'static str], depth: usize) -> Option<&'static str> {
    analyze_with(toks, programs, depth, false)
}

/// Rescan `text` as commands whose output a shell reads.
fn scan_feeding_shell(text: &str, programs: &[&'static str], depth: usize) -> Option<&'static str> {
    if depth > MAX_NESTING {
        return Some(TOO_DEEP);
    }
    let chars: Vec<char> = text.chars().collect();
    let mut lexer = Lexer::new(&chars, programs, depth);
    let toks = lexer.lex(false);
    lexer
        .hit
        .or_else(|| analyze_with(&toks, programs, depth, true))
}

/// Whether some command in `text` receives a pipe and runs a shell, looking
/// through prefixes (`| sudo sh`, `| xargs -0 sh -c …`): the shell's name.
pub(crate) fn pipes_into_a_shell(text: &str) -> Option<&'static str> {
    let chars: Vec<char> = text.chars().collect();
    let mut lexer = Lexer::new(&chars, &[], 0);
    let toks = lexer.lex(false);
    let commands = commands(&toks);
    commands.windows(2).find_map(|pair| {
        let ((_, piped), (next, _)) = (&pair[0], &pair[1]);
        if !*piped {
            return None;
        }
        let c = command_index(&next.words)?;
        if is_naming(&next.words, c) {
            return None;
        }
        let first = program_name(next.words[c].0);
        SOURCERS.iter().copied().find(|s| *s == first).or_else(|| {
            next.words[c..].iter().find_map(|(w, _)| {
                let name = program_name(w);
                SHELLS.iter().copied().find(|s| *s == name)
            })
        })
    })
}

/// Index of the command word: the first that is not an assignment or a
/// reserved word.
fn command_index(words: &[(&str, bool)]) -> Option<usize> {
    words
        .iter()
        .position(|(w, _)| !is_assignment(w) && !RESERVED.contains(w))
}

/// Whether the command only names its arguments ([`NAMING`], `command -v`),
/// and is not one of a naming program's runner forms.
fn is_naming(words: &[(&str, bool)], c: usize) -> bool {
    let program = program_name(words[c].0);
    (NAMING.contains(&program) && !runs_an_argument(program, &words[c + 1..]))
        || (program == "command"
            && words[c + 1..]
                .iter()
                .take_while(|(w, _)| w.starts_with('-'))
                .any(|(w, _)| *w == "-v" || *w == "-V"))
}

/// The forms of naming programs that run a program they are given:
/// `npm exec`/`npm x`, `pnpm exec`/`pnpm dlx`, `yarn exec`/`yarn dlx`,
/// `git bisect run`, `rg --pre`, `vim -c`/`--cmd`/`+…`, `make --eval`/`-E`
/// and `cargo --config`.
fn runs_an_argument(program: &str, args: &[(&str, bool)]) -> bool {
    let subcommand = || args.iter().map(|(w, _)| *w).find(|w| !w.starts_with('-'));
    match program {
        "npm" => matches!(subcommand(), Some("exec" | "x")),
        "pnpm" | "yarn" => matches!(subcommand(), Some("exec" | "dlx")),
        "git" => args
            .windows(2)
            .any(|pair| pair[0].0 == "bisect" && pair[1].0 == "run"),
        "rg" => !option_values(args, &["--pre"]).is_empty(),
        "vim" => !vim_scripts(args).is_empty(),
        "make" => !option_values(args, &MAKE_EVAL).is_empty(),
        "cargo" => !option_values(args, &["--config"]).is_empty(),
        _ => false,
    }
}

fn runs_a_shell(command: &Command<'_>) -> bool {
    let Some(c) = command_index(&command.words) else {
        return false;
    };
    !is_naming(&command.words, c)
        && (SOURCERS.contains(&program_name(command.words[c].0))
            || command.words[c..]
                .iter()
                .any(|(w, _)| SHELLS.contains(&program_name(w))))
}

fn scan_command(
    command: &Command<'_>,
    input_to_shell: bool,
    output_to_shell: bool,
    programs: &[&'static str],
    depth: usize,
) -> Option<&'static str> {
    let rescan = |text: &str| scan(text, programs, depth + 1);
    for (body, literal) in &command.heredocs {
        let found = if input_to_shell {
            rescan(body)
        } else if !literal {
            scan_substitutions(body, programs, depth + 1)
        } else {
            None
        };
        if found.is_some() {
            return found;
        }
    }

    if input_to_shell {
        if let found @ Some(_) = command.here_strings.iter().find_map(|h| rescan(h)) {
            return found;
        }
    }

    let words = &command.words;
    let c = command_index(words)?;
    let names = |w: &str| programs.iter().copied().find(|p| program_name(w) == *p);
    if let found @ Some(_) = names(words[c].0) {
        return found;
    }
    if is_naming(words, c) {
        // `echo '…' | sh`: what a printer prints, a shell runs.
        if output_to_shell && PRINTERS.contains(&program_name(words[c].0)) {
            let printed: Vec<&str> = words[c + 1..].iter().map(|(w, _)| *w).collect();
            return rescan(&printed.join(" "));
        }
        return None;
    }
    // An argument that is the program, or a path to it, runs it. Quoting does
    // not change that for a single word (`sudo 'nc' …`); a quoted string with
    // whitespace in it is text, not a program name.
    if let found @ Some(_) = words[c + 1..]
        .iter()
        .filter(|(w, quoted)| !quoted || !w.chars().any(char::is_whitespace))
        .find_map(|(w, _)| names(w))
    {
        return found;
    }
    // Quoted text a program runs as a script.
    for j in c..words.len() {
        let program = program_name(words[j].0);
        let args = &words[j + 1..];
        let scripts: Vec<String> = if SHELLS.contains(&program) {
            owned(shell_script(args).into_iter().collect())
        } else if program == "su" || program == "script" {
            owned(option_values(args, &["-c", "--command"]))
        } else if program == "env" {
            owned(option_values(args, &["-S", "--split-string"]))
        } else if program == "eval" {
            let joined: Vec<&str> = args.iter().map(|(w, _)| *w).collect();
            return rescan(&joined.join(" "));
        } else if VIMS.contains(&program) {
            owned(vim_commands(args))
        } else if MAKES.contains(&program) {
            owned(make_scripts(args))
        } else if program == "cargo" {
            cargo_programs(args)
        } else if program == "rg" {
            // `--pre=nc`: the value is the program, run on each file.
            if let found @ Some(_) = option_values(args, &["--pre"]).into_iter().find_map(&names) {
                return found;
            }
            Vec::new()
        } else {
            Vec::new()
        };
        if let found @ Some(_) = scripts.iter().find_map(|script| rescan(script)) {
            return found;
        }
    }
    // `bash <(echo …)`, `source <(…)`: the body's output is the script.
    if runs_a_shell(command) {
        return command
            .procsubs
            .iter()
            .find_map(|body| scan_feeding_shell(body, programs, depth + 1));
    }
    None
}

/// The script of a shell's `-c`: the first operand after the options, where
/// `-c` may sit in a cluster (`-lc`), options in [`SHELL_VALUE_OPTIONS`] take a
/// value (`-o pipefail`), and `--` ends the options.
fn shell_script<'a>(args: &[(&'a str, bool)]) -> Option<&'a str> {
    let mut has_c = false;
    let mut k = 0;
    while let Some(&(arg, _)) = args.get(k) {
        if arg == "--" {
            k += 1;
            break;
        }
        if SHELL_VALUE_OPTIONS.contains(&arg) {
            k += 2;
            continue;
        }
        if arg.starts_with("--") {
            k += 1;
            continue;
        }
        match arg.strip_prefix('-').or_else(|| arg.strip_prefix('+')) {
            Some(cluster) if !cluster.is_empty() => {
                has_c |= arg.starts_with('-') && cluster.contains('c');
                // A cluster ending in `o`/`O` takes the next word (`-eo pipefail`).
                k += if cluster.ends_with(['o', 'O']) { 2 } else { 1 };
            }
            _ => break,
        }
    }
    if has_c {
        args.get(k).map(|(w, _)| *w)
    } else {
        None
    }
}

/// The value of each of `names` among `args`, in order: the next word, or the
/// text after `=` or attached to a short option.
fn option_values<'a>(args: &[(&'a str, bool)], names: &[&str]) -> Vec<&'a str> {
    let mut values = Vec::new();
    let mut iter = args.iter();
    while let Some(&(arg, _)) = iter.next() {
        match names.iter().find_map(|name| option_match(arg, name)) {
            Some(Some(value)) => values.push(value),
            Some(None) => values.extend(iter.next().map(|(w, _)| *w)),
            None => {}
        }
    }
    values
}

/// Whether `arg` is the option `name`: `Some(Some(value))` with its value
/// attached, `Some(None)` when the value is the next word. A short option may
/// sit in a cluster (`-qc`, `-lc`, `-iS`), its value the rest of the cluster.
fn option_match<'a>(arg: &'a str, name: &str) -> Option<Option<&'a str>> {
    if arg == name {
        return Some(None);
    }
    if let Some(long) = name.strip_prefix("--") {
        return arg
            .strip_prefix("--")
            .and_then(|a| a.strip_prefix(long))
            .and_then(|rest| rest.strip_prefix('='))
            .map(Some);
    }
    let letter = name.trim_start_matches('-');
    let cluster = arg.strip_prefix('-').filter(|a| !a.starts_with('-'))?;
    let at = cluster.find(letter)?;
    let rest = &cluster[at + letter.len()..];
    Some((!rest.is_empty()).then(|| rest.strip_prefix('=').unwrap_or(rest)))
}

fn owned(texts: Vec<&str>) -> Vec<String> {
    texts.into_iter().map(str::to_owned).collect()
}

/// vim's scripts: each `-c`, `--cmd` and `+…` value.
fn vim_scripts<'a>(args: &[(&'a str, bool)]) -> Vec<&'a str> {
    let mut scripts = option_values(args, &["-c", "--cmd"]);
    scripts.extend(args.iter().filter_map(|(w, _)| w.strip_prefix('+')));
    scripts
}

/// The shell commands in vim's scripts: the text after each `!`, which is how
/// an Ex command runs one (`!nc …`, `silent !nc …`, `r !nc …`).
fn vim_commands<'a>(args: &[(&'a str, bool)]) -> Vec<&'a str> {
    vim_scripts(args)
        .into_iter()
        .flat_map(|script| {
            script
                .match_indices('!')
                .map(move |(at, _)| &script[at + 1..])
        })
        .collect()
}

/// The shell text in make's `--eval`/`-E` makefile text: the text itself, in
/// which a recipe line is a command, and what follows each `$(shell` or
/// `${shell`.
fn make_scripts<'a>(args: &[(&'a str, bool)]) -> Vec<&'a str> {
    let mut scripts = Vec::new();
    for text in option_values(args, &MAKE_EVAL) {
        scripts.push(text);
        for open in ["$(shell", "${shell"] {
            scripts.extend(
                text.match_indices(open)
                    .map(|(at, _)| &text[at + open.len()..]),
            );
        }
    }
    scripts
}

/// The programs a `cargo --config KEY=VALUE` sets, where KEY is one of
/// [`CARGO_PROGRAM_KEYS`] (`target.x.runner="nc evil 1"`), with the TOML
/// quoting and array punctuation turned to spaces.
fn cargo_programs(args: &[(&str, bool)]) -> Vec<String> {
    option_values(args, &["--config"])
        .into_iter()
        .filter_map(|setting| {
            let (key, value) = setting.split_once('=')?;
            let key = key.trim().rsplit('.').next()?.trim_matches(['"', '\'']);
            CARGO_PROGRAM_KEYS.contains(&key).then(|| {
                value
                    .chars()
                    .map(|c| {
                        if matches!(c, '"' | '\'' | '[' | ']' | ',') {
                            ' '
                        } else {
                            c
                        }
                    })
                    .collect()
            })
        })
        .collect()
}

/// The program a word names: the last path component of a word with a `/` in
/// it (`/usr/bin/nc`, `bin/nc`, `$HOME/nc`), unless it is a URL.
fn program_name(word: &str) -> &str {
    if word.contains('/') && !word.contains("://") {
        word.rsplit('/').next().unwrap_or(word)
    } else {
        word
    }
}

/// `NAME=value` before a command sets its environment; it is not the command.
fn is_assignment(word: &str) -> bool {
    word.split_once('=').is_some_and(|(name, _)| {
        !name.is_empty()
            && name.chars().all(|c| c.is_ascii_alphanumeric() || c == '_')
            && !name.starts_with(|c: char| c.is_ascii_digit())
    })
}

/// Whether `name` appears in `text` with no word character beside it.
fn has_whole_word(text: &str, name: &str) -> bool {
    let is_word = |c: char| c.is_ascii_alphanumeric() || matches!(c, '_' | '-' | '.');
    text.match_indices(name).any(|(at, _)| {
        let before = text[..at].chars().next_back();
        let after = text[at + name.len()..].chars().next();
        !before.is_some_and(is_word) && !after.is_some_and(is_word)
    })
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn patches_extracts_both_spellings_and_codex_subcommands() {
        let patch = "*** Begin Patch\n*** Update File: README.md\n@@\n-old\n+new\n*** End Patch";
        for name in [
            "apply_patch",
            "applypatch",
            "codex apply_patch",
            "codex applypatch",
        ] {
            let direct = format!("{name} '{patch}'");
            for command in [
                direct.clone(),
                format!("zsh -lc \"{direct}\""),
                format!("bash -c \"{direct}\""),
                format!("sh -c \"{direct}\""),
                format!("{name} <<'PATCH'\n{patch}\nPATCH"),
                format!("{name} <<< '{patch}'"),
                format!("zsh -lc \"{name} <<'PATCH'\n{patch}\nPATCH\""),
            ] {
                let extracted = patches(&command);
                assert_eq!(extracted.len(), 1, "{command}: {extracted:?}");
                assert_eq!(extracted[0].trim_end(), patch, "{command}");
            }
            assert!(patches(&format!("echo \"{direct}\"")).is_empty());
        }
    }
}