bashParser.ts

/**
 * Bash parser — recursive descent producing tree-sitter-bash-compatible AST
 * (docs §11.2.1).
 *
 * Grammar coverage (pragmatic — common agent commands):
 *   - pipelines:    cmd | cmd | cmd
 *   - lists:        cmd ; cmd   cmd && cmd   cmd || cmd   cmd &
 *   - subshells:    ( list )
 *   - compound:     { list ; }
 *   - if/for/while/case
 *   - function defs: name() { ... }   function name() { ... }
 *   - variable assignments: VAR=val   VAR=val cmd
 *   - redirects:    > >> < << <<- <<< &> 2>&1
 *   - command substitution: $(...) `...`
 *   - process substitution: <(...) >(...)
 *   - expansions:   $VAR  ${VAR}
 *
 * Resource limits: 50ms wall-clock + 50,000 node budget (docs §11.2.1).
 * Unknown/unhandled constructs raise ParseError (caller treats as 'too-complex').
 */
import { lex, type Token } from './lexer.js'
import type {
  ProgramNode,
  BashNode,
  SimpleCommandNode,
  VariableAssignmentNode,
  WordNode,
  RedirectNode,
  ListNode,
  PipelineNode,
  CaseItemNode,
} from './types.js'

export class ParseError extends Error {
  constructor(message: string) {
    super(message)
    this.name = 'ParseError'
  }
}

const PARSE_TIMEOUT_MS = 50
const MAX_NODE_BUDGET = 50_000

/** Keywords that terminate a block or belong to an enclosing construct —
 *  the parser stops a simple_command/pipeline when it sees one. */
const BLOCK_KEYWORDS = new Set([
  'then', 'else', 'elif', 'fi', 'do', 'done', 'esac', 'in', '}',
])

export interface ParseOptions {
  startTime?: number
  nodeBudget?: { count: number }
}

export function parse(source: string): ProgramNode {
  const tokens = lex(source)
  const parser = new Parser(tokens)
  return parser.parseProgram()
}

class Parser {
  private pos = 0
  private startTime: number
  private nodeCount = 0

  constructor(private tokens: Token[]) {
    this.startTime = Date.now()
  }

  private peek(offset = 0): Token {
    return this.tokens[Math.min(this.pos + offset, this.tokens.length - 1)]!
  }

  private next(): Token {
    return this.tokens[this.pos++] ?? this.tokens[this.tokens.length - 1]!
  }

  private at(type: Token['type']): boolean {
    return this.peek().type === type
  }

  private consume(type: Token['type']): Token {
    if (!this.at(type)) {
      throw new ParseError(`Expected ${type} but got ${this.peek().type} (${this.peek().text})`)
    }
    return this.next()
  }

  private checkBudget(): void {
    this.nodeCount++
    if (this.nodeCount > MAX_NODE_BUDGET) {
      throw new ParseError('Node budget exceeded (too-complex)')
    }
    if (Date.now() - this.startTime > PARSE_TIMEOUT_MS) {
      throw new ParseError('Parse timeout (too-complex)')
    }
  }

  private skipNewlines(): void {
    while (this.at('NEWLINE')) this.next()
  }

  parseProgram(): ProgramNode {
    this.checkBudget()
    const children: BashNode[] = []
    this.skipNewlines()
    while (!this.at('EOF')) {
      const node = this.parseList()
      if (node) children.push(node)
      this.skipNewlines()
      // Consume trailing separators
      while (this.at('SEMICOLON') || this.at('BACKGROUND') || this.at('NEWLINE')) {
        this.next()
      }
    }
    return { type: 'program', children }
  }

  /** list := pipeline ( ('&&'|'||'|';'|'&') pipeline )* */
  private parseList(): BashNode | null {
    let left = this.parsePipeline()
    if (!left) return null
    const children: BashNode[] = [left]
    let isBackground = false
    while (true) {
      this.skipNewlines()
      if (this.at('AND')) {
        this.next()
        this.skipNewlines()
        const right = this.parsePipeline()
        if (right) children.push({ type: 'and_op', text: '&&' }, right)
        else break
      } else if (this.at('OR')) {
        this.next()
        this.skipNewlines()
        const right = this.parsePipeline()
        if (right) children.push({ type: 'or_op', text: '||' }, right)
        else break
      } else if (this.at('SEMICOLON')) {
        this.next()
        this.skipNewlines()
        const right = this.parsePipeline()
        if (right) children.push({ type: 'semicolon', text: ';' }, right)
        else break
      } else if (this.at('BACKGROUND')) {
        this.next()
        children.push({ type: 'background', text: '&' })
        isBackground = true
        this.skipNewlines()
        const right = this.parsePipeline()
        if (right) children.push(right)
        else break
      } else {
        break
      }
      left = children[children.length - 1]!
    }
    if (children.length === 1) return left
    return { type: 'list', children }
  }

  /** pipeline := command ( '|' command )* */
  private parsePipeline(): BashNode | null {
    let cmd = this.parseCommand()
    if (!cmd) return null
    const children: BashNode[] = [cmd]
    while (this.at('PIPE')) {
      this.next()
      this.skipNewlines()
      const right = this.parseCommand()
      if (!right) break
      children.push({ type: 'pipe', text: '|' }, right)
    }
    if (children.length === 1) return cmd
    return { type: 'pipeline', children }
  }

  /** command := simple_command | subshell | compound | if | for | while | case | function */
  private parseCommand(): BashNode | null {
    this.checkBudget()
    const tok = this.peek()

    if (tok.type === 'LPAREN') {
      return this.parseSubshell()
    }
    if (tok.type === 'LBRACE') {
      return this.parseCompound()
    }
    if (tok.type === 'WORD') {
      // Keywords
      if (tok.text === 'if') return this.parseIf()
      if (tok.text === 'for') return this.parseFor()
      if (tok.text === 'while' || tok.text === 'until') return this.parseWhile()
      if (tok.text === 'case') return this.parseCase()
      if (tok.text === 'function') return this.parseFunction()
      // Stop at block terminators / keywords that belong to an enclosing construct.
      if (BLOCK_KEYWORDS.has(tok.text)) return null
      // function def without keyword: name() { ... }
      if (this.peek(1).type === 'LPAREN' && this.peek(2).type === 'RPAREN') {
        return this.parseFunction()
      }
    }
    return this.parseSimpleCommand()
  }

  private parseSubshell(): BashNode {
    this.consume('LPAREN')
    this.skipNewlines()
    const children: BashNode[] = []
    while (!this.at('RPAREN') && !this.at('EOF')) {
      const n = this.parseList()
      if (n) children.push(n)
      this.skipNewlines()
      while (this.at('SEMICOLON') || this.at('NEWLINE')) this.next()
    }
    this.consume('RPAREN')
    return { type: 'subshell', children }
  }

  private parseCompound(): BashNode {
    this.consume('LBRACE')
    this.skipNewlines()
    const children: BashNode[] = []
    while (!this.at('RBRACE') && !this.at('EOF')) {
      const n = this.parseList()
      if (n) children.push(n)
      this.skipNewlines()
      while (this.at('SEMICOLON') || this.at('NEWLINE')) this.next()
    }
    this.consume('RBRACE')
    return { type: 'compound_statement', children }
  }

  private parseIf(): BashNode {
    this.next() // 'if'
    const condition = this.parseList()!
    this.skipNewlines()
    this.expectWord('then')
    this.skipNewlines()
    const consequence = this.parseList()!
    let alternative: BashNode | undefined
    this.skipNewlines()
    if (this.atWord('elif')) {
      alternative = this.parseIf()
    } else if (this.atWord('else')) {
      this.next()
      this.skipNewlines()
      alternative = this.parseList()!
    }
    this.skipNewlines()
    this.expectWord('fi')
    return { type: 'if_statement', condition, consequence, alternative }
  }

  private parseFor(): BashNode {
    this.next() // 'for'
    const varName = this.consume('WORD').text
    this.skipNewlines()
    let iterable: BashNode | undefined
    if (this.atWord('in')) {
      this.next()
      const args: BashNode[] = []
      while (
        !this.at('NEWLINE') &&
        !this.at('SEMICOLON') &&
        !this.at('EOF') &&
        !this.atWord('do')
      ) {
        args.push(this.parseWord())
      }
      iterable = args.length === 1 ? args[0] : { type: 'concatenation', children: args }
    }
    this.skipNewlines()
    while (this.at('SEMICOLON')) this.next()
    this.skipNewlines()
    this.expectWord('do')
    this.skipNewlines()
    const body = this.parseList()!
    this.skipNewlines()
    this.expectWord('done')
    return { type: 'for_statement', variable: varName, iterable, body }
  }

  private parseWhile(): BashNode {
    this.next() // while/until
    const condition = this.parseList()!
    this.skipNewlines()
    this.expectWord('do')
    this.skipNewlines()
    const body = this.parseList()!
    this.skipNewlines()
    this.expectWord('done')
    return { type: 'while_statement', condition, body }
  }

  private parseCase(): BashNode {
    this.next() // 'case'
    const value = this.parseWord()
    this.skipNewlines()
    this.expectWord('in')
    this.skipNewlines()
    const items: BashNode[] = []
    while (!this.atWord('esac') && !this.at('EOF')) {
      // pattern ( | pattern )* ) body ;;
      const patterns: BashNode[] = [this.parseWord()]
      while (this.at('PIPE')) {
        this.next()
        patterns.push(this.parseWord())
      }
      this.consume('RPAREN')
      this.skipNewlines()
      const bodyChildren: BashNode[] = []
      while (!this.at('SEMICOLON') && !this.at('EOF') && !this.atWord('esac')) {
        const n = this.parseList()
        if (n) bodyChildren.push(n)
        this.skipNewlines()
        if (this.at('SEMICOLON')) break
      }
      // expect ;;
      if (this.at('SEMICOLON')) {
        this.next()
        if (this.at('SEMICOLON')) this.next()
      }
      items.push({ type: 'case_item', patterns, body: bodyChildren.length ? { type: 'compound_statement', children: bodyChildren } : { type: 'compound_statement', children: [] } })
      this.skipNewlines()
    }
    this.expectWord('esac')
    return { type: 'case_statement', value, items: items as CaseItemNode[] }
  }

  private parseFunction(): BashNode {
    let name = ''
    if (this.atWord('function')) {
      this.next()
      name = this.consume('WORD').text
      if (this.at('LPAREN')) {
        this.next()
        this.consume('RPAREN')
      }
    } else {
      name = this.consume('WORD').text
      this.consume('LPAREN')
      this.consume('RPAREN')
    }
    this.skipNewlines()
    const body = this.parseCompound()
    return { type: 'function_definition', name, body }
  }

  /** simple_command := assignment* (word arg*)? redirect* */
  private parseSimpleCommand(): BashNode | null {
    const assignments: VariableAssignmentNode[] = []
    let name: WordNode | undefined
    const args: BashNode[] = []
    const redirects: RedirectNode[] = []

    // Leading assignments.
    while (this.at('WORD') && /^[A-Za-z_][A-Za-z0-9_]*(\+?=)/.test(this.peek().text)) {
      assignments.push(this.parseAssignment())
    }

    // Command name (first non-redirect word). Stop at block keywords.
    if (this.at('WORD') && !BLOCK_KEYWORDS.has(this.peek().text)) {
      name = this.parseWord()
    }

    // Arguments and redirects.
    while (true) {
      if ((this.at('WORD') && !BLOCK_KEYWORDS.has(this.peek().text)) || this.at('RAW_STRING') || this.at('STRING')) {
        args.push(this.parseWord())
      } else if (this.at('REDIRECT')) {
        redirects.push(this.parseRedirect())
      } else if (this.at('HEREDOC_START')) {
        redirects.push(this.parseHeredocRedirect())
      } else {
        break
      }
    }

    if (!name && assignments.length === 0 && redirects.length === 0) return null

    const cmd: SimpleCommandNode = {
      type: 'simple_command',
      assignments,
      name: name ? { type: 'command_name', children: [name] } : undefined,
      arguments: args,
      redirects,
    }
    return cmd
  }

  private parseAssignment(): VariableAssignmentNode {
    const tok = this.consume('WORD')
    const eqIdx = tok.text.indexOf('=') >= 0 ? tok.text.indexOf('=') : tok.text.indexOf('+=')
    const isAppend = tok.text[eqIdx] === '+'
    const name = tok.text.slice(0, eqIdx - (isAppend ? 1 : 0))
    const valueStr = tok.text.slice(eqIdx + 1)
    const value: WordNode | undefined = valueStr
      ? { type: 'word', text: valueStr, hasExpansion: valueStr.includes('$') }
      : undefined
    return {
      type: 'environment_variable_assignment',
      name,
      value,
      append: isAppend,
    }
  }

  private parseWord(): WordNode {
    const tok = this.next()
    let type: WordNode['type'] = 'word'
    if (tok.type === 'RAW_STRING') type = 'raw_string'
    else if (tok.type === 'STRING') type = 'string'
    const hasExpansion = /[$`]/.test(tok.text) && tok.type !== 'RAW_STRING'
    return { type, text: tok.text, hasExpansion }
  }

  private parseRedirect(): RedirectNode {
    const tok = this.consume('REDIRECT')
    // Destination is the next word.
    let destination: BashNode | undefined
    if (this.at('WORD') || this.at('RAW_STRING') || this.at('STRING')) {
      destination = this.parseWord()
    }
    return {
      type: 'file_redirect',
      descriptor: tok.fd,
      operator: tok.redirectOp,
      destination,
    }
  }

  private parseHeredocRedirect(): RedirectNode {
    const tok = this.consume('HEREDOC_START')
    // Body is the next WORD token (the lexer attached it).
    let body = ''
    if (this.at('WORD')) {
      body = this.next().text
    }
    return {
      type: 'heredoc_redirect',
      descriptor: tok.fd,
      operator: tok.redirectOp,
      heredocDelimiter: tok.heredocDelimiter,
      heredocQuoted: tok.heredocQuoted,
      heredocBody: body,
    }
  }

  private atWord(word: string): boolean {
    return this.at('WORD') && this.peek().text === word
  }

  private expectWord(word: string): void {
    if (!this.atWord(word)) {
      throw new ParseError(`Expected "${word}" but got ${this.peek().type} "${this.peek().text}"`)
    }
    this.next()
  }
}

/**
 * Strip safe wrappers (docs §11.2.3): timeout, time, nice, nohup, and safe env
 * vars, so permission rules match the underlying command.
 */
const SAFE_WRAPPERS = new Set(['timeout', 'time', 'nice', 'nohup', 'command', 'env'])
const SAFE_ENV_VARS = new Set(['LANG', 'LC_ALL', 'LC_CTYPE', 'PATH', 'TERM', 'HOME', 'USER'])

export function stripSafeWrappers(command: string): string {
  let s = command.trim()
  // Strip leading env vars: FOO=bar BAZ=qux cmd → cmd (for safe vars only)
  s = s.replace(/^(?:[A-Za-z_][A-Za-z0-9_]*=\S+\s+)+/, (match) => {
    const stripped = match
      .trim()
      .split(/\s+/)
      .filter((assign) => {
        const name = assign.slice(0, assign.indexOf('='))
        return !SAFE_ENV_VARS.has(name)
      })
    return stripped.length ? stripped.join(' ') + ' ' : ''
  })
  // Strip leading safe-wrapper command + its args until the real command.
  // timeout takes a duration arg; time/nice/nohup take the command directly.
  const parts = s.trim().split(/\s+/)
  if (parts.length > 1 && SAFE_WRAPPERS.has(parts[0]!)) {
    if (parts[0] === 'timeout' && parts.length > 2) {
      return parts.slice(2).join(' ')
    }
    return parts.slice(1).join(' ')
  }
  return s.trim()
}