package main

// Parser and executor for command lines and scripts: lists (; & && || and
// newlines), pipelines, ! and the compound commands if, for, while, until,
// case, { ...; } and ( ... ), and function definitions. Simple commands (with their pipes and redirections) are kept as
// text; they are expanded and run by execCommand only when they are
// executed, so that e.g. the variable of a for loop is expanded anew in
// every iteration.

import (
	"errors"
	"fmt"
	"os"
	"path"
	"slices"
	"strconv"
	"strings"
	"syscall"
)

// incompleteError is returned by parse if the input ends inside a
// construct (if without fi, an open quote, a trailing && ...): an
// interactive shell then reads another line.
type incompleteError struct{}

func (incompleteError) Error() string { return "syntax error: unexpected end of input" }

var errIncomplete error = incompleteError{}

// loopControl is returned by break and continue and ends the given number of
// enclosing loops (break) or iterations (continue).
type loopControl struct {
	isBreak bool
	n       int
}

func (c loopControl) Error() string {
	if c.isBreak {
		return "break"
	}
	return "continue"
}

// loopDepth is the number of loops that are currently running.
var loopDepth int

// aliasExpansion is false while the result of an alias expansion runs, so
// that it is not expanded again.
var aliasExpansion = true

// reserved words that end a list; they are only recognized as the first word
// of a command.
var terminators = map[string]bool{
	"then": true, "elif": true, "else": true, "fi": true, "do": true, "done": true,
	"esac": true, "}": true,
}

// compoundStarts are the reserved words that start a compound command.
var compoundStarts = map[string]bool{"if": true, "for": true, "while": true, "until": true, "case": true, "{": true}

// ---------------------------------------------------------------------------
// Lexer

type tokenKind int

const (
	tWord tokenKind = iota
	tOp             // ; ;; & && || | ( ) or newline
)

type rawToken struct {
	kind       tokenKind
	text       string
	start, end int
}

// joinContinuationLines removes backslash-newline (outside single quotes),
// which continues a line. continued reports whether src ends with such a
// continuation (so that the command goes on in the next line).
func joinContinuationLines(src string) (joined string, continued bool) {
	if !strings.Contains(src, "\\\n") {
		return src, false
	}
	var b strings.Builder
	var quote byte
	for i := 0; i < len(src); i++ {
		ch := src[i]
		switch {
		case quote == '\'':
			if ch == '\'' {
				quote = 0
			}
		case ch == '\\' && i+1 < len(src):
			if src[i+1] == '\n' {
				i++
				continued = i == len(src)-1
				continue
			}
			continued = false
			b.WriteByte(ch)
			i++
			ch = src[i]
		case ch == '"':
			if quote == '"' {
				quote = 0
			} else {
				quote = '"'
			}
		case ch == '\'' && quote == 0:
			quote = '\''
		}
		if ch != '\n' && ch != ' ' && ch != '\t' {
			continued = false
		}
		b.WriteByte(ch)
	}
	return b.String(), continued
}

// lex splits src into words and list operators. Words keep their quotes,
// escapes, $(...) and redirections; they are only split at blanks and list
// operators.
func lex(src string) ([]rawToken, error) {
	var toks []rawToken
	op := func(text string, i int) {
		toks = append(toks, rawToken{tOp, text, i, i + len(text)})
	}
	for i := 0; i < len(src); {
		ch := src[i]
		next := byte(0)
		if i+1 < len(src) {
			next = src[i+1]
		}
		switch {
		case ch == ' ' || ch == '\t':
			i++
		case ch == ';' && next == ';':
			op(";;", i)
			i += 2
		case ch == '\n' || ch == ';':
			op(string(ch), i)
			i++
		case ch == '#':
			// Comment until the end of the line
			for i < len(src) && src[i] != '\n' {
				i++
			}
		case ch == '|' && next == '|', ch == '&' && next == '&':
			op(src[i:i+2], i)
			i += 2
		case ch == '|', ch == '&' && next != '>', ch == '(', ch == ')':
			op(string(ch), i)
			i++
		default:
			end, err := lexWord(src, i)
			if err != nil {
				return nil, err
			}
			toks = append(toks, rawToken{tWord, src[i:end], i, end})
			i = end
		}
	}
	return toks, nil
}

// lexWord returns the end of the word that starts at src[i].
func lexWord(src string, i int) (int, error) {
	var quote byte
	for j := i; j < len(src); j++ {
		ch := src[j]
		switch {
		case quote == '\'':
			if ch == '\'' {
				quote = 0
			}
		case ch == '\\':
			if j+1 == len(src) {
				return 0, errIncomplete
			}
			j++
			if isSubstStart(src, j) {
				// \$(...) is literal text, but its ( and ) belong to the word
				if end := substEnd(src, j); end >= 0 {
					j = end
				}
			}
		case isSubstStart(src, j):
			end := substEnd(src, j)
			if end < 0 {
				return 0, errIncomplete
			}
			j = end
		case ch == '$' && j+1 < len(src) && src[j+1] == '{':
			if k := strings.IndexByte(src[j:], '}'); k >= 0 {
				j += k
			}
		case quote == '"':
			if ch == '"' {
				quote = 0
			}
		case ch == '"' || ch == '\'':
			quote = ch
		case ch == ' ' || ch == '\t' || ch == '\n' || ch == ';' || ch == '|' || ch == '(' || ch == ')':
			return j, nil
		case ch == '&':
			// &>, >& and <& are redirections, not the & operator
			if !(j+1 < len(src) && src[j+1] == '>') && !(j > i && (src[j-1] == '>' || src[j-1] == '<')) {
				return j, nil
			}
		}
	}
	if quote != 0 {
		return 0, errIncomplete
	}
	return len(src), nil
}

// ---------------------------------------------------------------------------
// Syntax tree

// node is a command that can be executed: it returns the error of the last
// command it ran (so that exitStatus gives its status).
type node interface {
	exec() error
}

// listNode is a list of and-or lists separated by ;, & or newlines.
type listNode struct {
	items []listEntry
}

type listEntry struct {
	andOr      *andOrNode
	background bool
}

// andOrNode is a pipeline followed by && and || pipelines.
type andOrNode struct {
	first *pipelineNode
	rest  []andOrPart
	text  string // the source, to run it in a subshell in the background
}

type andOrPart struct {
	op       string // && or ||
	pipeline *pipelineNode
}

// pipelineNode is a pipeline (a simpleNode or pipeNode) or a single
// compound command, optionally negated with !.
type pipelineNode struct {
	negate bool
	cmd    node
}

// simpleNode is the text of a pipeline of simple commands.
type simpleNode struct {
	text string
}

// pipeNode is a pipeline that contains compound commands. Like all commands
// of a pipeline in sh, they run in subshells (new gosh processes), since
// the commands of a pipeline run concurrently.
type pipeNode struct {
	elems []pipeElem
	text  string
}

type pipeElem struct {
	text     string // the source of the command, with its redirections
	compound bool
	subshell string // for ( list ): the list, which runs in the subshell directly
}

// redirNode is a compound command with redirections; they apply to all
// commands in it.
type redirNode struct {
	cmd    node
	redirs string // the source text of the redirections
}

// subshellNode is ( list ): the list runs in a new gosh process, so that it
// cannot change the shell.
type subshellNode struct {
	text string // the source of the list
}

type ifNode struct {
	conds    []*listNode
	bodies   []*listNode
	elseBody *listNode
}

type forNode struct {
	name  string
	words string // the words after "in", expanded when the loop starts
	hasIn bool
	body  *listNode
}

type whileNode struct {
	until bool
	cond  *listNode
	body  *listNode
}

// caseNode is case word in pattern|pattern) list ;; ... esac.
type caseNode struct {
	word    string // expanded when the case command runs
	clauses []caseClause
}

type caseClause struct {
	patterns []string // expanded when they are tried
	body     *listNode
}

// groupNode is { list; }.
type groupNode struct {
	body *listNode
}

// funcDefNode is a function definition name() compound-command.
type funcDefNode struct {
	def *funcDef
}

// singleSimple returns the simple command if the list is just that.
func (l *listNode) singleSimple() *simpleNode {
	if len(l.items) != 1 || l.items[0].background {
		return nil
	}
	ao := l.items[0].andOr
	if len(ao.rest) > 0 || ao.first.negate {
		return nil
	}
	s, _ := ao.first.cmd.(*simpleNode)
	return s
}

// ---------------------------------------------------------------------------
// Parser

type parser struct {
	src  string
	toks []rawToken
	pos  int
}

// parse parses a command line or script. It returns errIncomplete if the
// input ends inside a construct.
func parse(src string) (*listNode, error) {
	src, err := extractHeredocs(src)
	if err != nil {
		return nil, err
	}
	src, continued := joinContinuationLines(src)
	if continued {
		return nil, errIncomplete
	}
	toks, err := lex(src)
	if err != nil {
		return nil, err
	}
	p := &parser{src: src, toks: toks}
	list, err := p.parseList(nil)
	if err != nil {
		return nil, err
	}
	if t := p.peek(); t != nil {
		return nil, p.unexpected(t)
	}
	return list, nil
}

func (p *parser) peek() *rawToken {
	if p.pos < len(p.toks) {
		return &p.toks[p.pos]
	}
	return nil
}

func (p *parser) peekWord(words ...string) bool {
	t := p.peek()
	if t == nil || t.kind != tWord {
		return false
	}
	for _, w := range words {
		if t.text == w {
			return true
		}
	}
	return false
}

func (p *parser) skipNewlines() {
	for t := p.peek(); t != nil && t.kind == tOp && t.text == "\n"; t = p.peek() {
		p.pos++
	}
}

func (p *parser) unexpected(t *rawToken) error {
	if t.text == "\n" {
		return syntaxError("newline")
	}
	return syntaxError(t.text)
}

// expect consumes the reserved word w.
func (p *parser) expect(w string) error {
	t := p.peek()
	if t == nil {
		return errIncomplete
	}
	if t.kind != tWord || t.text != w {
		return p.unexpected(t)
	}
	p.pos++
	return nil
}

// parseList parses and-or lists until the end of the input or one of the
// reserved words in terms at the start of a command.
func (p *parser) parseList(terms map[string]bool) (*listNode, error) {
	list := &listNode{}
	for {
		p.skipNewlines()
		t := p.peek()
		if t == nil || terms[t.text] {
			return list, nil
		}
		ao, err := p.parseAndOr()
		if err != nil {
			return nil, err
		}
		entry := listEntry{andOr: ao}

		t = p.peek()
		switch {
		case t == nil:
		case t.kind == tOp && (t.text == ";" || t.text == "&" || t.text == "\n"):
			p.pos++
			entry.background = t.text == "&"
		case terms[t.text]:
			// e.g. "fi" right after the end of a nested control structure,
			// or ;; after a command in a case clause
		default:
			return nil, p.unexpected(t)
		}
		list.items = append(list.items, entry)
	}
}

// nonEmpty returns an error if a list that must contain commands is empty.
func (p *parser) nonEmpty(list *listNode) error {
	if len(list.items) > 0 {
		return nil
	}
	if t := p.peek(); t != nil {
		return p.unexpected(t)
	}
	return errIncomplete
}

func (p *parser) parseAndOr() (*andOrNode, error) {
	start := p.peek().start
	first, err := p.parsePipeline()
	if err != nil {
		return nil, err
	}
	ao := &andOrNode{first: first}
	for {
		t := p.peek()
		if t == nil || t.kind != tOp || (t.text != "&&" && t.text != "||") {
			ao.text = p.src[start:p.toks[p.pos-1].end]
			return ao, nil
		}
		p.pos++
		p.skipNewlines()
		if p.peek() == nil {
			return nil, errIncomplete
		}
		next, err := p.parsePipeline()
		if err != nil {
			return nil, err
		}
		ao.rest = append(ao.rest, andOrPart{op: t.text, pipeline: next})
	}
}

// parsePipeline parses [!] command [| command]... A pipeline of simple
// commands stays one simpleNode (its text is split into the commands when it
// runs); a pipeline with compound commands becomes a pipeNode.
func (p *parser) parsePipeline() (*pipelineNode, error) {
	pl := &pipelineNode{}
	if p.peekWord("!") {
		pl.negate = true
		p.pos++
	}
	var (
		elems []pipeElem
		cmds  []node
		start = -1
	)
	for {
		t := p.peek()
		if t == nil {
			return nil, errIncomplete
		}
		if t.kind == tOp && t.text != "(" || t.kind == tWord && terminators[t.text] {
			return nil, p.unexpected(t)
		}
		if start < 0 {
			start = t.start
		}
		cmd, compound, err := p.parseCommand()
		if err != nil {
			return nil, err
		}
		elem := pipeElem{text: p.src[t.start:p.toks[p.pos-1].end], compound: compound}
		if sub, ok := cmd.(*subshellNode); ok {
			elem.subshell = sub.text
		}
		elems = append(elems, elem)
		cmds = append(cmds, cmd)

		if t := p.peek(); t == nil || t.kind != tOp || t.text != "|" {
			break
		}
		p.pos++
		p.skipNewlines()
		if p.peek() == nil {
			return nil, errIncomplete
		}
	}

	text := p.src[start:p.toks[p.pos-1].end]
	compound := false
	for i, e := range elems {
		if _, ok := cmds[i].(*funcDefNode); ok && len(elems) > 1 {
			return nil, errors.New("function definitions in pipelines are not supported")
		}
		compound = compound || e.compound
	}
	switch {
	case len(elems) == 1:
		pl.cmd = cmds[0]
	case !compound:
		pl.cmd = &simpleNode{text: text}
	default:
		pl.cmd = &pipeNode{elems: elems, text: text}
	}
	return pl, nil
}

// parseCommand parses a simple command, a compound command with its
// redirections or a function definition, and reports whether it is not a
// simple command.
func (p *parser) parseCommand() (node, bool, error) {
	t := p.peek()
	start := t.start
	if name, ok := p.funcDefName(); ok {
		def, err := p.parseFuncDef(name, start)
		if err != nil {
			return nil, true, err
		}
		if t := p.peek(); t != nil && t.kind == tWord && !terminators[t.text] {
			return nil, true, errors.New("redirections of function definitions are not supported")
		}
		return def, true, nil
	}
	if !isCompoundStart(t) {
		cmd, err := p.parseSimple()
		return cmd, false, err
	}
	cmd, err := p.parseCompound()
	if err != nil {
		return nil, true, err
	}
	redirs, err := p.parseRedirections()
	if err != nil {
		return nil, true, err
	}
	if redirs != "" {
		cmd = &redirNode{cmd: cmd, redirs: redirs}
	}
	return cmd, true, nil
}

// isCompoundStart reports whether a compound command starts at t.
func isCompoundStart(t *rawToken) bool {
	return t.kind == tWord && compoundStarts[t.text] || t.kind == tOp && t.text == "("
}

// parseRedirections parses the redirections after a compound command and
// returns their source text (expanded when the command runs).
func (p *parser) parseRedirections() (string, error) {
	start, end := -1, -1
	for t := p.peek(); t != nil && t.kind == tWord && !terminators[t.text]; t = p.peek() {
		needsTarget, ok := redirectionWord(t.text)
		if !ok {
			return "", syntaxError(t.text)
		}
		if start < 0 {
			start = t.start
		}
		end = t.end
		p.pos++
		if needsTarget {
			t = p.peek()
			if t == nil || t.kind != tWord {
				if t == nil {
					return "", syntaxError("newline")
				}
				return "", p.unexpected(t)
			}
			end = t.end
			p.pos++
		}
	}
	if start < 0 {
		return "", nil
	}
	return p.src[start:end], nil
}

// redirectionWord reports whether word starts with a redirection operator
// (optionally after a file descriptor), and whether the target is the next
// word (2> file instead of 2>file).
func redirectionWord(word string) (needsTarget, ok bool) {
	w := strings.TrimLeft(word, "0123456789")
	for _, op := range []string{"&>>", "&>", "<<<", ">>", ">&", "<&", ">", "<"} {
		if strings.HasPrefix(w, op) {
			if op[0] == '&' && len(w) != len(word) {
				return false, false
			}
			return w == op, true
		}
	}
	return false, false
}

// parseSimple parses a simple command (without pipes) and returns its text.
func (p *parser) parseSimple() (*simpleNode, error) {
	start := p.toks[p.pos].start
	end := start
	for t := p.peek(); t != nil && t.kind == tWord; t = p.peek() {
		end = t.end
		p.pos++
	}
	return &simpleNode{text: p.src[start:end]}, nil
}

// parseCompound parses the compound command that starts at the current
// token.
func (p *parser) parseCompound() (node, error) {
	switch p.peek().text {
	case "if":
		return p.parseIf()
	case "for":
		return p.parseFor()
	case "while", "until":
		return p.parseWhile()
	case "case":
		return p.parseCase()
	case "(":
		return p.parseSubshell()
	default: // {
		return p.parseGroup()
	}
}

func (p *parser) parseIf() (*ifNode, error) {
	p.pos++ // if
	n := &ifNode{}
	for {
		cond, err := p.parseList(map[string]bool{"then": true})
		if err == nil {
			err = p.nonEmpty(cond)
		}
		if err == nil {
			err = p.expect("then")
		}
		if err != nil {
			return nil, err
		}
		body, err := p.parseList(map[string]bool{"elif": true, "else": true, "fi": true})
		if err == nil {
			err = p.nonEmpty(body)
		}
		if err != nil {
			return nil, err
		}
		n.conds = append(n.conds, cond)
		n.bodies = append(n.bodies, body)

		t := p.peek()
		if t == nil {
			return nil, errIncomplete
		}
		p.pos++
		switch t.text {
		case "elif":
			continue
		case "else":
			body, err := p.parseList(map[string]bool{"fi": true})
			if err == nil {
				err = p.nonEmpty(body)
			}
			if err == nil {
				err = p.expect("fi")
			}
			if err != nil {
				return nil, err
			}
			n.elseBody = body
		}
		return n, nil // fi
	}
}

func (p *parser) parseFor() (*forNode, error) {
	p.pos++ // for
	t := p.peek()
	if t == nil {
		return nil, errIncomplete
	}
	if t.kind != tWord || !isVarName(t.text) {
		return nil, fmt.Errorf("for: `%s': not a valid identifier", sanitize(t.text))
	}
	n := &forNode{name: t.text}
	p.pos++

	p.skipNewlines()
	if p.peekWord("in") {
		p.pos++
		n.hasIn = true
		var words []string
		for t := p.peek(); t != nil && t.kind == tWord; t = p.peek() {
			words = append(words, t.text)
			p.pos++
		}
		n.words = strings.Join(words, " ")
	}
	t = p.peek()
	switch {
	case t == nil:
		return nil, errIncomplete
	case t.kind == tOp && (t.text == ";" || t.text == "\n"):
		p.pos++
	case !n.hasIn && t.kind == tWord && t.text == "do":
	default:
		return nil, p.unexpected(t)
	}

	p.skipNewlines()
	body, err := p.parseLoopBody()
	if err != nil {
		return nil, err
	}
	n.body = body
	return n, nil
}

func (p *parser) parseWhile() (*whileNode, error) {
	n := &whileNode{until: p.peek().text == "until"}
	p.pos++
	cond, err := p.parseList(map[string]bool{"do": true})
	if err == nil {
		err = p.nonEmpty(cond)
	}
	if err != nil {
		return nil, err
	}
	n.cond = cond
	body, err := p.parseLoopBody()
	if err != nil {
		return nil, err
	}
	n.body = body
	return n, nil
}

// parseGroup parses { list; }.
func (p *parser) parseGroup() (*groupNode, error) {
	p.pos++ // {
	body, err := p.parseList(map[string]bool{"}": true})
	if err == nil {
		err = p.nonEmpty(body)
	}
	if err == nil {
		err = p.expect("}")
	}
	if err != nil {
		return nil, err
	}
	return &groupNode{body: body}, nil
}

// parseSubshell parses ( list ).
func (p *parser) parseSubshell() (*subshellNode, error) {
	p.pos++ // (
	start := p.toks[p.pos-1].end
	body, err := p.parseList(map[string]bool{")": true})
	if err == nil {
		err = p.nonEmpty(body)
	}
	if err != nil {
		return nil, err
	}
	t := p.peek()
	if t == nil {
		return nil, errIncomplete
	}
	if t.kind != tOp || t.text != ")" {
		return nil, p.unexpected(t)
	}
	p.pos++
	return &subshellNode{text: p.src[start:t.start]}, nil
}

// parseCase parses case word in [(]pattern[|pattern]...) list ;; ... esac.
// The last clause may omit the ;;.
func (p *parser) parseCase() (*caseNode, error) {
	p.pos++ // case
	t := p.peek()
	if t == nil {
		return nil, errIncomplete
	}
	if t.kind != tWord {
		return nil, p.unexpected(t)
	}
	n := &caseNode{word: t.text}
	p.pos++
	p.skipNewlines()
	if err := p.expect("in"); err != nil {
		return nil, err
	}
	for {
		p.skipNewlines()
		t := p.peek()
		if t == nil {
			return nil, errIncomplete
		}
		if t.kind == tWord && t.text == "esac" {
			p.pos++
			return n, nil
		}
		patterns, err := p.parsePatterns()
		if err != nil {
			return nil, err
		}
		body, err := p.parseList(map[string]bool{";;": true, "esac": true})
		if err != nil {
			return nil, err
		}
		n.clauses = append(n.clauses, caseClause{patterns: patterns, body: body})
		if t := p.peek(); t == nil {
			return nil, errIncomplete
		} else if t.text == ";;" {
			p.pos++
		}
	}
}

// parsePatterns parses the patterns of a case clause up to and including the
// ).
func (p *parser) parsePatterns() ([]string, error) {
	if t := p.peek(); t.kind == tOp && t.text == "(" {
		p.pos++ // the optional ( before the first pattern
	}
	var patterns []string
	for {
		t := p.peek()
		if t == nil {
			return nil, errIncomplete
		}
		if t.kind != tWord {
			return nil, p.unexpected(t)
		}
		patterns = append(patterns, t.text)
		p.pos++
		t = p.peek()
		switch {
		case t == nil:
			return nil, errIncomplete
		case t.kind == tOp && t.text == "|":
			p.pos++
		case t.kind == tOp && t.text == ")":
			p.pos++
			return patterns, nil
		default:
			return nil, p.unexpected(t)
		}
	}
}

// funcDefName reports whether a function definition starts at the current
// token: name(), or function name [()]. It consumes the tokens up to the
// body.
func (p *parser) funcDefName() (string, bool) {
	start := p.pos
	if t := p.peek(); t.kind != tWord {
		return "", false
	} else if t.text == "function" {
		p.pos++
		if t := p.peek(); t == nil || t.kind != tWord || !isFuncName(t.text) {
			p.pos = start
			return "", false
		}
	}
	name := p.peek().text
	isOp := func(i int, text string) bool {
		return i < len(p.toks) && p.toks[i].kind == tOp && p.toks[i].text == text
	}
	switch {
	case isOp(p.pos+1, "(") && isOp(p.pos+2, ")") && isFuncName(name):
		p.pos += 3
	case p.pos > start:
		p.pos++ // function name
	default:
		return "", false
	}
	return name, true
}

// parseFuncDef parses the body of a function definition that started at
// src[start]: a compound command.
func (p *parser) parseFuncDef(name string, start int) (*funcDefNode, error) {
	p.skipNewlines()
	t := p.peek()
	if t == nil {
		return nil, errIncomplete
	}
	if !isCompoundStart(t) {
		return nil, fmt.Errorf("%s: the body of a function must be a compound command like { ...; }", sanitize(name))
	}
	body, err := p.parseCompound()
	if err != nil {
		return nil, err
	}
	return &funcDefNode{def: &funcDef{name: name, body: body, text: p.src[start:p.toks[p.pos-1].end]}}, nil
}

// parseLoopBody parses "do list done".
func (p *parser) parseLoopBody() (*listNode, error) {
	if err := p.expect("do"); err != nil {
		return nil, err
	}
	body, err := p.parseList(map[string]bool{"done": true})
	if err == nil {
		err = p.nonEmpty(body)
	}
	if err == nil {
		err = p.expect("done")
	}
	return body, err
}

// ---------------------------------------------------------------------------
// Execution

// isAbort reports whether err stops the execution of the enclosing lists:
// break, continue, return, or a command that was interrupted with Ctrl+C
// (like in bash, Ctrl+C aborts the whole command line, e.g. a loop).
func isAbort(err error) bool {
	var (
		lc  loopControl
		ret returnSignal
	)
	return errors.As(err, &lc) || errors.As(err, &ret) || exitStatus(err) == 128+int(syscall.SIGINT)
}

// silent returns an error with only the exit status of err, for errors that
// were already reported.
func silent(err error) error {
	if err == nil {
		return nil
	}
	return statusError(exitStatus(err))
}

func (l *listNode) exec() error {
	var err error
	for _, entry := range l.items {
		printError(err)
		if entry.background {
			err = entry.andOr.runBackground()
		} else {
			err = entry.andOr.exec()
		}
		lastStatus = exitStatus(err)
		if isAbort(err) {
			return err
		}
	}
	return err
}

func (a *andOrNode) exec() error {
	err := a.first.exec()
	for _, part := range a.rest {
		lastStatus = exitStatus(err)
		if isAbort(err) {
			return err
		}
		if (part.op == "&&") != (lastStatus == 0) {
			continue
		}
		printError(err)
		err = part.pipeline.exec()
	}
	return err
}

// runBackground starts the and-or list as a background job. Pipelines run
// like in the foreground, everything else in a subshell.
func (a *andOrNode) runBackground() error {
	if len(a.rest) == 0 && !a.first.negate {
		switch cmd := a.first.cmd.(type) {
		case *simpleNode:
			return cmd.run(true)
		case *pipeNode:
			return cmd.run(true)
		case *subshellNode:
			return runPipeline([]stage{{script: cmd.text}}, a.text, true)
		}
	}
	return runPipeline([]stage{{script: a.text}}, a.text, true)
}

func (pl *pipelineNode) exec() error {
	err := pl.cmd.exec()
	if !pl.negate || isAbort(err) {
		return err
	}
	printError(err)
	if exitStatus(err) == 0 {
		return statusError(1)
	}
	return nil
}

func (s *simpleNode) exec() error {
	return s.run(false)
}

// run executes the simple command, in the background if background is set.
// Aliases are expanded here (in interactive shells), so that they work at
// the start of every command, also inside control structures.
func (s *simpleNode) run(background bool) error {
	text := s.text
	if interactiveShell && aliasExpansion {
		if expanded := expandAliases(text); expanded != text {
			tree, err := parse(expanded)
			if err != nil {
				return err
			}
			if simple := tree.singleSimple(); simple != nil {
				text = simple.text
			} else {
				if background {
					return errors.New("an alias with a command list cannot run in the background")
				}
				aliasExpansion = false
				defer func() { aliasExpansion = true }()
				return tree.exec()
			}
		}
	}
	return execCommand(text, background)
}

func (n *ifNode) exec() error {
	for i, cond := range n.conds {
		err := cond.exec()
		if isAbort(err) {
			return err
		}
		printError(err)
		if exitStatus(err) == 0 {
			return n.bodies[i].exec()
		}
	}
	if n.elseBody != nil {
		return n.elseBody.exec()
	}
	lastStatus = 0
	return nil
}

// runLoopBody runs one iteration of a loop. It returns whether the loop
// must stop, and the error to return from the loop.
func runLoopBody(body *listNode, result *error) (stop bool, err error) {
	err = body.exec()
	var lc loopControl
	if errors.As(err, &lc) {
		*result = nil
		if lc.n > 1 {
			lc.n--
			return true, lc // ends an outer loop too
		}
		return lc.isBreak, nil
	}
	if isAbort(err) {
		return true, err
	}
	printError(err)
	*result = silent(err)
	return false, nil
}

func (n *whileNode) exec() error {
	loopDepth++
	defer func() { loopDepth-- }()

	var result error
	for {
		err := n.cond.exec()
		if isAbort(err) {
			return err
		}
		printError(err)
		if (exitStatus(err) == 0) == n.until {
			break
		}
		if stop, err := runLoopBody(n.body, &result); stop {
			if err != nil {
				return err
			}
			break
		}
	}
	lastStatus = exitStatus(result)
	return result
}

func (n *forNode) exec() error {
	// Without "in", the loop runs over the positional parameters
	words := slices.Clone(positional)
	if n.hasIn {
		var err error
		if words, err = expandWordList(n.words); err != nil {
			return err
		}
	}

	loopDepth++
	defer func() { loopDepth-- }()

	var result error
	for _, word := range words {
		os.Setenv(n.name, word)
		if stop, err := runLoopBody(n.body, &result); stop {
			if err != nil {
				return err
			}
			break
		}
	}
	lastStatus = exitStatus(result)
	return result
}

func (n *groupNode) exec() error {
	return n.body.exec()
}

func (n *subshellNode) exec() error {
	return runPipeline([]stage{{script: n.text}}, "("+strings.TrimSpace(n.text)+")", false)
}

// exec runs the compound command with stdin, stdout and stderr of the shell
// redirected.
func (n *redirNode) exec() error {
	fds, opened, err := openRedirections(n.redirs)
	if err != nil {
		return err
	}
	saved := ioOverride
	ioOverride = fds
	defer func() {
		ioOverride = saved
		for _, f := range opened {
			f.Close()
		}
	}()
	return n.cmd.exec()
}

func (n *pipeNode) exec() error {
	return n.run(false)
}

// run builds the stages of the pipeline: simple commands are expanded,
// compound commands run in subshells.
func (n *pipeNode) run(background bool) error {
	substStatus = 0
	var stages []stage
	for _, e := range n.elems {
		switch {
		case e.subshell != "":
			stages = append(stages, stage{script: e.subshell})
		case e.compound:
			stages = append(stages, stage{script: e.text})
		default:
			text := e.text
			if interactiveShell && aliasExpansion {
				if tree, err := parse(expandAliases(text)); err == nil {
					if simple := tree.singleSimple(); simple != nil {
						text = simple.text
					}
				}
			}
			st, err := expandStages(text)
			if err != nil {
				return err
			}
			if len(st) == 0 {
				st = []stage{{}}
			}
			stages = append(stages, st...)
		}
	}
	return runPipeline(stages, n.text, background)
}

func (n *funcDefNode) exec() error {
	defineFunction(n.def)
	return nil
}

// exec runs the body of the first clause with a pattern that matches the
// word. The status is 0 if no pattern matches.
func (n *caseNode) exec() error {
	word, err := expandCaseWord(n.word)
	if err != nil {
		return err
	}
	for _, clause := range n.clauses {
		for _, pattern := range clause.patterns {
			ok, err := caseMatch(pattern, word)
			if err != nil {
				return err
			}
			if ok {
				return clause.body.exec()
			}
		}
	}
	lastStatus = 0
	return nil
}

// expandCaseWord expands the word of a case command: like an argument, but
// without brace expansion, wildcards and splitting.
func expandCaseWord(text string) (string, error) {
	tokens, err := tokenize(text)
	if err != nil {
		return "", fmt.Errorf("invalid input: %w", err)
	}
	var words []string
	for _, t := range tokens {
		if t.op != "" {
			return "", syntaxError(t.op)
		}
		words = append(words, t.word)
	}
	return strings.Join(words, " "), nil
}

// caseMatch reports whether word matches the pattern of a case clause. The
// pattern is expanded first; quoted characters in it match literally. Unlike
// for file names, * and ? also match a /.
func caseMatch(pattern, word string) (bool, error) {
	tokens, err := tokenize(pattern)
	if err != nil {
		return false, fmt.Errorf("invalid input: %w", err)
	}
	var literal, glob []string
	isGlob := false
	for _, t := range tokens {
		if t.op != "" {
			return false, syntaxError(t.op)
		}
		literal = append(literal, t.word)
		glob = append(glob, t.pattern)
		isGlob = isGlob || t.glob
	}
	if !isGlob {
		return word == strings.Join(literal, " "), nil
	}
	// path.Match does not let * match a /; NUL can be in neither string
	toNUL := strings.NewReplacer("/", "\x00")
	ok, err := path.Match(toNUL.Replace(strings.Join(glob, " ")), toNUL.Replace(word))
	if err != nil {
		// An invalid pattern only matches itself
		return word == strings.Join(literal, " "), nil
	}
	return ok, nil
}

// expandWordList expands the words of a for loop like the arguments of a
// command (braces, ~, variables, $(...), wildcards).
func expandWordList(text string) ([]string, error) {
	text, err := expandBraceWords(text)
	if err != nil {
		return nil, err
	}
	tokens, err := tokenize(text)
	if err != nil {
		return nil, fmt.Errorf("invalid input: %w", err)
	}
	var words []string
	for _, t := range tokens {
		if t.op != "" {
			return nil, syntaxError(t.op)
		}
		words = append(words, expandWord(t)...)
	}
	return words, nil
}

// builtinLoopControl implements break [n] and continue [n].
func builtinLoopControl(args []string) error {
	n := 1
	if len(args) > 1 {
		var err error
		if n, err = strconv.Atoi(args[1]); err != nil || n < 1 {
			return fmt.Errorf("%s: %s: loop count out of range", args[0], sanitize(args[1]))
		}
	}
	if loopDepth == 0 {
		return fmt.Errorf("%s: only meaningful in a loop", args[0])
	}
	return loopControl{isBreak: args[0] == "break", n: min(n, loopDepth)}
}