mxsh 0.2.0

use std::borrow::Cow;
use std::time::{SystemTime, UNIX_EPOCH};

/// Source position within the input stream.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Default, Clone, Copy, PartialEq, Eq)]
pub struct Position {
    /// Byte offset from the start of input.
    pub offset: usize,
    /// One-indexed line number when known.
    ///
    /// `0` denotes an unknown or synthetic position.
    pub line: u32,
    /// One-indexed column number when known.
    ///
    /// `0` denotes an unknown or synthetic position.
    pub column: u32,
}

/// A range of source positions.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Default, Clone, Copy, PartialEq, Eq)]
pub struct Range {
    pub begin: Position,
    pub end: Position,
}

impl Position {
    pub fn is_known(&self) -> bool {
        self.line != 0 || self.column != 0 || self.offset != 0
    }
}

impl Range {
    pub fn unknown() -> Self {
        Self::default()
    }

    pub fn cover(self, other: Self) -> Self {
        match (self.begin.is_known(), other.begin.is_known()) {
            (false, false) => Self::unknown(),
            (false, true) => other,
            (true, false) => self,
            (true, true) => Self {
                begin: if self.begin.offset <= other.begin.offset {
                    self.begin
                } else {
                    other.begin
                },
                end: if self.end.offset >= other.end.offset {
                    self.end
                } else {
                    other.end
                },
            },
        }
    }
}

/// A syntax node that can report a source span.
pub trait Spanned {
    fn span(&self) -> Range;
}

// ── Word AST ─────────────────────────────────────────────────────────

/// Parameter expansion operator, e.g. `${var:-default}`.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ParameterOp {
    /// No operator — bare `$var` or `${var}`.
    None,
    /// `${var-word}` / `${var:-word}` — use default.
    Minus,
    /// `${var=word}` / `${var:=word}` — assign default.
    Equal,
    /// `${var?word}` / `${var:?word}` — error if unset.
    QMark,
    /// `${var+word}` / `${var:+word}` — use alternative.
    Plus,
    /// `${#var}` — string length.
    LeadingHash,
    /// `${var%pattern}` — remove shortest suffix.
    Percent,
    /// `${var%%pattern}` — remove longest suffix.
    DoublePercent,
    /// `${var#pattern}` — remove shortest prefix.
    Hash,
    /// `${var##pattern}` — remove longest prefix.
    DoubleHash,
}

/// Literal string segment metadata for [`Word::String`].
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct StringWord {
    pub(crate) value: String,
    pub(crate) single_quoted: bool,
    pub(crate) split_fields: bool,
    pub(crate) source: Option<String>,
    pub(crate) range: Range,
}

impl StringWord {
    pub fn new(
        value: impl Into<String>,
        single_quoted: bool,
        split_fields: bool,
        source: Option<String>,
        range: Range,
    ) -> Self {
        Self {
            value: value.into(),
            single_quoted,
            split_fields,
            source,
            range,
        }
    }

    pub fn value(&self) -> &str {
        &self.value
    }

    pub fn single_quoted(&self) -> bool {
        self.single_quoted
    }

    pub fn split_fields(&self) -> bool {
        self.split_fields
    }

    pub fn source(&self) -> Option<&str> {
        self.source.as_deref()
    }
}

impl Spanned for StringWord {
    fn span(&self) -> Range {
        self.range
    }
}

/// Parameter expansion metadata for [`Word::Parameter`].
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ParameterExpansion {
    pub(crate) name: String,
    pub(crate) op: ParameterOp,
    pub(crate) colon: bool,
    pub(crate) arg: Option<Box<Word>>,
    pub(crate) dollar_pos: Position,
    pub(crate) brace_end: Option<Position>,
    pub(crate) range: Range,
}

impl ParameterExpansion {
    pub fn new(
        name: impl Into<String>,
        op: ParameterOp,
        colon: bool,
        arg: Option<Box<Word>>,
        dollar_pos: Position,
        brace_end: Option<Position>,
        range: Range,
    ) -> Self {
        Self {
            name: name.into(),
            op,
            colon,
            arg,
            dollar_pos,
            brace_end,
            range,
        }
    }

    pub fn name(&self) -> &str {
        &self.name
    }

    pub fn op(&self) -> ParameterOp {
        self.op
    }

    pub fn colon(&self) -> bool {
        self.colon
    }

    pub fn arg(&self) -> Option<&Word> {
        self.arg.as_deref()
    }

    pub fn dollar_pos(&self) -> Position {
        self.dollar_pos
    }

    pub fn brace_end(&self) -> Option<Position> {
        self.brace_end
    }
}

impl Spanned for ParameterExpansion {
    fn span(&self) -> Range {
        self.range
    }
}

/// Command substitution metadata for [`Word::Command`].
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct CommandSubstitution {
    pub(crate) program: Program,
    pub(crate) source: Option<String>,
    pub(crate) back_quoted: bool,
    pub(crate) range: Range,
}

impl CommandSubstitution {
    pub fn new(program: Program, source: Option<String>, back_quoted: bool, range: Range) -> Self {
        Self {
            program,
            source,
            back_quoted,
            range,
        }
    }

    pub fn program(&self) -> &Program {
        &self.program
    }

    pub fn source(&self) -> Option<&str> {
        self.source.as_deref()
    }

    pub fn back_quoted(&self) -> bool {
        self.back_quoted
    }
}

impl Spanned for CommandSubstitution {
    fn span(&self) -> Range {
        self.range
    }
}

/// Arithmetic expansion metadata for [`Word::Arithmetic`].
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ArithmeticExpansion {
    pub(crate) body: ArithmExpr,
    pub(crate) range: Range,
}

impl ArithmeticExpansion {
    pub fn new(body: ArithmExpr, range: Range) -> Self {
        Self { body, range }
    }

    pub fn body(&self) -> &ArithmExpr {
        &self.body
    }

    pub fn body_mut(&mut self) -> &mut ArithmExpr {
        &mut self.body
    }
}

impl Spanned for ArithmeticExpansion {
    fn span(&self) -> Range {
        self.range
    }
}

/// Word-list metadata for [`Word::List`].
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct WordList {
    pub(crate) children: Vec<Word>,
    pub(crate) double_quoted: bool,
    pub(crate) range: Range,
}

impl WordList {
    pub fn new(children: Vec<Word>, double_quoted: bool, range: Range) -> Self {
        Self {
            children,
            double_quoted,
            range,
        }
    }

    pub fn children(&self) -> &[Word] {
        &self.children
    }

    pub fn children_mut(&mut self) -> &mut Vec<Word> {
        &mut self.children
    }

    pub fn double_quoted(&self) -> bool {
        self.double_quoted
    }
}

impl Spanned for WordList {
    fn span(&self) -> Range {
        self.range
    }
}

/// A word node in the AST.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Word {
    /// Literal text after quote removal and backslash processing for one contiguous segment.
    ///
    /// Parser-produced nodes obey these invariants:
    /// - `value` contains the bytes that participate in expansion, not the original syntax.  The
    ///   surrounding single quotes of `'...'`, shell escape characters, and continuation
    ///   backslash-newline pairs are removed before they reach this field.
    /// - `source`, when present, stores a shell fragment that reparses back into the same segment.
    ///   Unquoted and double-quoted fragments omit delimiters owned by their parent context, while
    ///   single-quoted fragments include their surrounding quotes.
    /// - `String` never represents parameter, command, or arithmetic expansion syntax.  Mixed
    ///   words such as `prefix"$var"suffix` are represented as `Word::List` whose children are
    ///   separate `String` / `Parameter` / `Command` / `Arithmetic` nodes.
    /// - `single_quoted` means the segment came from a single-quoted region, so `value` is the
    ///   literal body between the source quotes and `split_fields` is always `false`.
    /// - `split_fields` is only `true` for unquoted literal segments that should still participate
    ///   in field splitting after later expansions.  Quoted segments, here-document literal text,
    ///   and unquoted text whose IFS whitespace was backslash-escaped set this to `false`.
    /// - `range` covers the exact source span that produced the segment, including quotes or
    ///   escapes that were removed from `value`.
    String(StringWord),
    /// Parameter expansion: `$name` or `${...}`.
    Parameter(ParameterExpansion),
    /// Command substitution: `$(program)` or `` `program` ``.
    Command(CommandSubstitution),
    /// Arithmetic expansion: `$((expression))`.
    Arithmetic(ArithmeticExpansion),
    /// A list of word parts, possibly double-quoted.
    List(WordList),
}

impl Word {
    pub fn string(
        value: impl Into<String>,
        single_quoted: bool,
        split_fields: bool,
        source: Option<String>,
        range: Range,
    ) -> Self {
        Self::String(StringWord::new(
            value,
            single_quoted,
            split_fields,
            source,
            range,
        ))
    }

    pub fn parameter(
        name: impl Into<String>,
        op: ParameterOp,
        colon: bool,
        arg: Option<Box<Word>>,
        dollar_pos: Position,
        brace_end: Option<Position>,
        range: Range,
    ) -> Self {
        Self::Parameter(ParameterExpansion::new(
            name, op, colon, arg, dollar_pos, brace_end, range,
        ))
    }

    pub fn command(
        program: Program,
        source: Option<String>,
        back_quoted: bool,
        range: Range,
    ) -> Self {
        Self::Command(CommandSubstitution::new(
            program,
            source,
            back_quoted,
            range,
        ))
    }

    pub fn arithmetic(body: ArithmExpr, range: Range) -> Self {
        Self::Arithmetic(ArithmeticExpansion::new(body, range))
    }

    pub fn list(children: Vec<Word>, double_quoted: bool, range: Range) -> Self {
        Self::List(WordList::new(children, double_quoted, range))
    }

    /// Extract the quote-removed string value from a word, if it is entirely literal.
    pub fn as_str(&self) -> Option<Cow<'_, str>> {
        match self {
            Word::String(string) => Some(Cow::Borrowed(string.value())),
            Word::List(list) => {
                let children = list.children();
                if children.len() == 1 {
                    return children[0].as_str();
                }

                let mut literal = String::new();
                for child in children {
                    literal.push_str(child.as_str()?.as_ref());
                }
                Some(Cow::Owned(literal))
            }
            _ => None,
        }
    }
}

impl Spanned for Word {
    fn span(&self) -> Range {
        match self {
            Word::String(string) => string.span(),
            Word::Parameter(parameter) => parameter.span(),
            Word::Command(command) => command.span(),
            Word::Arithmetic(arithm) => arithm.span(),
            Word::List(list) => list.span(),
        }
    }
}

// ── Arithmetic Expression AST ────────────────────────────────────────

/// Binary arithmetic operator.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ArithmBinOp {
    Add,
    Sub,
    Mul,
    Div,
    Mod,
    Shl,
    Shr,
    LessThan,
    LessEq,
    GreaterThan,
    GreaterEq,
    Equal,
    NotEqual,
    BitAnd,
    BitXor,
    BitOr,
    LogAnd,
    LogOr,
}

/// Unary arithmetic operator.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ArithmUnOp {
    Plus,
    Minus,
    BitNot,
    LogNot,
}

/// Arithmetic assignment operator.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ArithmAssignOp {
    Equal,
    MulEq,
    DivEq,
    ModEq,
    AddEq,
    SubEq,
    ShlEq,
    ShrEq,
    AndEq,
    XorEq,
    OrEq,
}

/// An arithmetic expression node.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ArithmLiteral {
    pub(crate) value: i64,
    pub(crate) range: Range,
}

impl ArithmLiteral {
    pub fn new(value: i64, range: Range) -> Self {
        Self { value, range }
    }

    pub fn value(&self) -> i64 {
        self.value
    }
}

impl Spanned for ArithmLiteral {
    fn span(&self) -> Range {
        self.range
    }
}

#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ArithmVariable {
    pub(crate) name: String,
    pub(crate) range: Range,
}

impl ArithmVariable {
    pub fn new(name: impl Into<String>, range: Range) -> Self {
        Self {
            name: name.into(),
            range,
        }
    }

    pub fn name(&self) -> &str {
        &self.name
    }
}

impl Spanned for ArithmVariable {
    fn span(&self) -> Range {
        self.range
    }
}

#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ArithmRaw {
    pub(crate) expr: String,
    pub(crate) range: Range,
}

impl ArithmRaw {
    pub fn new(expr: impl Into<String>, range: Range) -> Self {
        Self {
            expr: expr.into(),
            range,
        }
    }

    pub fn expr(&self) -> &str {
        &self.expr
    }
}

impl Spanned for ArithmRaw {
    fn span(&self) -> Range {
        self.range
    }
}

#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ArithmBinaryExpr {
    pub(crate) op: ArithmBinOp,
    pub(crate) left: Box<ArithmExpr>,
    pub(crate) right: Box<ArithmExpr>,
    pub(crate) range: Range,
}

impl ArithmBinaryExpr {
    pub fn new(op: ArithmBinOp, left: ArithmExpr, right: ArithmExpr, range: Range) -> Self {
        Self {
            op,
            left: Box::new(left),
            right: Box::new(right),
            range,
        }
    }

    pub fn op(&self) -> ArithmBinOp {
        self.op
    }

    pub fn left(&self) -> &ArithmExpr {
        &self.left
    }

    pub fn right(&self) -> &ArithmExpr {
        &self.right
    }
}

impl Spanned for ArithmBinaryExpr {
    fn span(&self) -> Range {
        self.range
    }
}

#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ArithmUnaryExpr {
    pub(crate) op: ArithmUnOp,
    pub(crate) operand: Box<ArithmExpr>,
    pub(crate) range: Range,
}

impl ArithmUnaryExpr {
    pub fn new(op: ArithmUnOp, operand: ArithmExpr, range: Range) -> Self {
        Self {
            op,
            operand: Box::new(operand),
            range,
        }
    }

    pub fn op(&self) -> ArithmUnOp {
        self.op
    }

    pub fn operand(&self) -> &ArithmExpr {
        &self.operand
    }
}

impl Spanned for ArithmUnaryExpr {
    fn span(&self) -> Range {
        self.range
    }
}

#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ArithmConditionalExpr {
    pub(crate) cond: Box<ArithmExpr>,
    pub(crate) then_branch: Box<ArithmExpr>,
    pub(crate) else_branch: Box<ArithmExpr>,
    pub(crate) range: Range,
}

impl ArithmConditionalExpr {
    pub fn new(
        cond: ArithmExpr,
        then_branch: ArithmExpr,
        else_branch: ArithmExpr,
        range: Range,
    ) -> Self {
        Self {
            cond: Box::new(cond),
            then_branch: Box::new(then_branch),
            else_branch: Box::new(else_branch),
            range,
        }
    }

    pub fn cond(&self) -> &ArithmExpr {
        &self.cond
    }

    pub fn then_branch(&self) -> &ArithmExpr {
        &self.then_branch
    }

    pub fn else_branch(&self) -> &ArithmExpr {
        &self.else_branch
    }
}

impl Spanned for ArithmConditionalExpr {
    fn span(&self) -> Range {
        self.range
    }
}

#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ArithmAssignmentExpr {
    pub(crate) name: String,
    pub(crate) op: ArithmAssignOp,
    pub(crate) value: Box<ArithmExpr>,
    pub(crate) range: Range,
}

impl ArithmAssignmentExpr {
    pub fn new(
        name: impl Into<String>,
        op: ArithmAssignOp,
        value: ArithmExpr,
        range: Range,
    ) -> Self {
        Self {
            name: name.into(),
            op,
            value: Box::new(value),
            range,
        }
    }

    pub fn name(&self) -> &str {
        &self.name
    }

    pub fn op(&self) -> ArithmAssignOp {
        self.op
    }

    pub fn value(&self) -> &ArithmExpr {
        &self.value
    }
}

impl Spanned for ArithmAssignmentExpr {
    fn span(&self) -> Range {
        self.range
    }
}

/// An arithmetic expression node.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum ArithmExpr {
    Literal(ArithmLiteral),
    Variable(ArithmVariable),
    Raw(ArithmRaw),
    BinOp(ArithmBinaryExpr),
    UnOp(ArithmUnaryExpr),
    /// Ternary conditional: `cond ? then_branch : else_branch`.
    Cond(ArithmConditionalExpr),
    /// Assignment: `name op= value`.
    Assign(ArithmAssignmentExpr),
}

impl ArithmExpr {
    pub fn literal(value: i64, range: Range) -> Self {
        Self::Literal(ArithmLiteral::new(value, range))
    }

    pub fn variable(name: impl Into<String>, range: Range) -> Self {
        Self::Variable(ArithmVariable::new(name, range))
    }

    pub fn raw(expr: impl Into<String>, range: Range) -> Self {
        Self::Raw(ArithmRaw::new(expr, range))
    }

    pub fn bin_op(op: ArithmBinOp, left: ArithmExpr, right: ArithmExpr, range: Range) -> Self {
        Self::BinOp(ArithmBinaryExpr::new(op, left, right, range))
    }

    pub fn un_op(op: ArithmUnOp, operand: ArithmExpr, range: Range) -> Self {
        Self::UnOp(ArithmUnaryExpr::new(op, operand, range))
    }

    pub fn cond(
        cond: ArithmExpr,
        then_branch: ArithmExpr,
        else_branch: ArithmExpr,
        range: Range,
    ) -> Self {
        Self::Cond(ArithmConditionalExpr::new(
            cond,
            then_branch,
            else_branch,
            range,
        ))
    }

    pub fn assign(
        name: impl Into<String>,
        op: ArithmAssignOp,
        value: ArithmExpr,
        range: Range,
    ) -> Self {
        Self::Assign(ArithmAssignmentExpr::new(name, op, value, range))
    }
}

impl Spanned for ArithmExpr {
    fn span(&self) -> Range {
        match self {
            ArithmExpr::Literal(literal) => literal.span(),
            ArithmExpr::Variable(variable) => variable.span(),
            ArithmExpr::Raw(raw) => raw.span(),
            ArithmExpr::BinOp(binary) => binary.span(),
            ArithmExpr::UnOp(unary) => unary.span(),
            ArithmExpr::Cond(cond) => cond.span(),
            ArithmExpr::Assign(assign) => assign.span(),
        }
    }
}

// ── I/O Redirection ──────────────────────────────────────────────────

/// I/O redirection operator.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum IoRedirectOp {
    /// `<` — open for reading.
    Less,
    /// `>` — open for writing (truncate).
    Great,
    /// `>|` — open for writing (clobber, ignoring noclobber).
    Clobber,
    /// `>>` — open for appending.
    DGreat,
    /// `<&` — duplicate input file descriptor.
    LessAnd,
    /// `>&` — duplicate output file descriptor.
    GreatAnd,
    /// `<>` — open for reading and writing.
    LessGreat,
    /// `<<` — here-document.
    DLess,
    /// `<<-` — here-document with leading tab stripping.
    DLessDash,
}

/// A single I/O redirection.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct IoRedirect {
    /// Explicit file descriptor number, or `None` for the operator default.
    pub(crate) io_number: Option<u32>,
    pub(crate) op: IoRedirectOp,
    /// Target filename/word (for non-heredoc operators).
    pub(crate) name: Word,
    /// Lines of the here-document body (for `<<` and `<<-`).
    pub(crate) here_document: Vec<Word>,
    /// Whether the here-document body performs expansion.
    ///
    /// This is only meaningful for `<<` / `<<-` redirects.  When `false`,
    /// the delimiter was quoted and the body must be treated literally.
    pub(crate) here_document_expand: bool,
    pub(crate) range: Range,
}

impl IoRedirect {
    pub fn new(
        io_number: Option<u32>,
        op: IoRedirectOp,
        name: Word,
        here_document: Vec<Word>,
        here_document_expand: bool,
    ) -> Self {
        let range = name
            .span()
            .cover(span_for_iter(here_document.iter().map(Spanned::span)));
        Self {
            io_number,
            op,
            name,
            here_document,
            here_document_expand,
            range,
        }
    }

    pub fn with_range(
        io_number: Option<u32>,
        op: IoRedirectOp,
        name: Word,
        here_document: Vec<Word>,
        here_document_expand: bool,
        range: Range,
    ) -> Self {
        Self {
            io_number,
            op,
            name,
            here_document,
            here_document_expand,
            range,
        }
    }

    pub fn io_number(&self) -> Option<u32> {
        self.io_number
    }

    pub fn op(&self) -> IoRedirectOp {
        self.op
    }

    pub fn name(&self) -> &Word {
        &self.name
    }

    pub fn name_mut(&mut self) -> &mut Word {
        &mut self.name
    }

    pub fn here_document(&self) -> &[Word] {
        &self.here_document
    }

    pub fn here_document_mut(&mut self) -> &mut Vec<Word> {
        &mut self.here_document
    }

    pub fn here_document_expand(&self) -> bool {
        self.here_document_expand
    }
}

impl Spanned for IoRedirect {
    fn span(&self) -> Range {
        self.range
    }
}

// ── Assignment ───────────────────────────────────────────────────────

/// A variable assignment: `NAME=VALUE`.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Assignment {
    pub(crate) name: String,
    pub(crate) value: Word,
    pub(crate) range: Range,
}

impl Assignment {
    pub fn new(name: impl Into<String>, value: Word, range: Range) -> Self {
        Self {
            name: name.into(),
            value,
            range,
        }
    }

    pub fn name(&self) -> &str {
        &self.name
    }

    pub fn value(&self) -> &Word {
        &self.value
    }

    pub fn value_mut(&mut self) -> &mut Word {
        &mut self.value
    }
}

impl Spanned for Assignment {
    fn span(&self) -> Range {
        self.range
    }
}

// ── Command AST ──────────────────────────────────────────────────────

/// Compound-command payload used by brace groups and subshells.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct CompoundCommand {
    pub(crate) body: Vec<CommandList>,
    pub(crate) io_redirects: Vec<IoRedirect>,
    pub(crate) range: Range,
}

impl CompoundCommand {
    pub fn new(body: Vec<CommandList>, io_redirects: Vec<IoRedirect>) -> Self {
        let range = span_for_command_lists(&body).cover(span_for_redirects(&io_redirects));
        Self {
            body,
            io_redirects,
            range,
        }
    }

    pub fn with_range(body: Vec<CommandList>, io_redirects: Vec<IoRedirect>, range: Range) -> Self {
        Self {
            body,
            io_redirects,
            range,
        }
    }

    pub fn body(&self) -> &[CommandList] {
        &self.body
    }

    pub fn body_mut(&mut self) -> &mut Vec<CommandList> {
        &mut self.body
    }

    pub fn io_redirects(&self) -> &[IoRedirect] {
        &self.io_redirects
    }

    pub fn io_redirects_mut(&mut self) -> &mut Vec<IoRedirect> {
        &mut self.io_redirects
    }
}

impl Spanned for CompoundCommand {
    fn span(&self) -> Range {
        self.range
    }
}

/// A command node.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Command {
    /// A simple command: `[assignments...] [name [args...]] [redirections...]`.
    Simple(SimpleCommand),
    /// A brace group: `{ body }`.
    BraceGroup(CompoundCommand),
    /// A subshell: `( body )`.
    Subshell(CompoundCommand),
    /// An if clause: `if cond then body [elif/else] fi`.
    If(IfClause),
    /// A for clause: `for name [in words...] do body done`.
    For(ForClause),
    /// A while/until loop.
    Loop(LoopClause),
    /// A case clause: `case word in items... esac`.
    Case(CaseClause),
    /// A function definition: `name() body [redirections...]`.
    FunctionDef(FunctionDefinition),
}

impl Spanned for Command {
    fn span(&self) -> Range {
        match self {
            Command::Simple(simple) => simple.span(),
            Command::BraceGroup(group) | Command::Subshell(group) => group.span(),
            Command::If(if_clause) => if_clause.span(),
            Command::For(for_clause) => for_clause.span(),
            Command::Loop(loop_clause) => loop_clause.span(),
            Command::Case(case_clause) => case_clause.span(),
            Command::FunctionDef(function_definition) => function_definition.span(),
        }
    }
}

/// A simple command with optional assignments, arguments, and redirections.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct SimpleCommand {
    /// The command name word.
    pub(crate) name: Option<Word>,
    /// Positional arguments.
    pub(crate) arguments: Vec<Word>,
    /// I/O redirections.
    pub(crate) io_redirects: Vec<IoRedirect>,
    /// Variable assignments preceding the command.
    pub(crate) assignments: Vec<Assignment>,
    pub(crate) range: Range,
}

impl SimpleCommand {
    pub fn new(
        name: Option<Word>,
        arguments: Vec<Word>,
        io_redirects: Vec<IoRedirect>,
        assignments: Vec<Assignment>,
    ) -> Self {
        let range = span_for_assignments(&assignments)
            .cover(name.as_ref().map(Spanned::span).unwrap_or_default())
            .cover(span_for_words(&arguments))
            .cover(span_for_redirects(&io_redirects));
        Self {
            name,
            arguments,
            io_redirects,
            assignments,
            range,
        }
    }

    pub fn with_range(
        name: Option<Word>,
        arguments: Vec<Word>,
        io_redirects: Vec<IoRedirect>,
        assignments: Vec<Assignment>,
        range: Range,
    ) -> Self {
        Self {
            name,
            arguments,
            io_redirects,
            assignments,
            range,
        }
    }

    pub fn name(&self) -> Option<&Word> {
        self.name.as_ref()
    }

    pub fn name_mut(&mut self) -> Option<&mut Word> {
        self.name.as_mut()
    }

    pub fn arguments(&self) -> &[Word] {
        &self.arguments
    }

    pub fn arguments_mut(&mut self) -> &mut Vec<Word> {
        &mut self.arguments
    }

    pub fn io_redirects(&self) -> &[IoRedirect] {
        &self.io_redirects
    }

    pub fn io_redirects_mut(&mut self) -> &mut Vec<IoRedirect> {
        &mut self.io_redirects
    }

    pub fn assignments(&self) -> &[Assignment] {
        &self.assignments
    }

    pub fn assignments_mut(&mut self) -> &mut Vec<Assignment> {
        &mut self.assignments
    }
}

impl Spanned for SimpleCommand {
    fn span(&self) -> Range {
        self.range
    }
}

/// An if-elif-else clause.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct IfClause {
    pub(crate) condition: Vec<CommandList>,
    pub(crate) body: Vec<CommandList>,
    pub(crate) else_part: Option<Box<ElsePart>>,
    pub(crate) io_redirects: Vec<IoRedirect>,
    pub(crate) range: Range,
}

impl IfClause {
    pub fn new(
        condition: Vec<CommandList>,
        body: Vec<CommandList>,
        else_part: Option<Box<ElsePart>>,
    ) -> Self {
        Self::new_with_redirects(condition, body, else_part, Vec::new())
    }

    pub fn new_with_redirects(
        condition: Vec<CommandList>,
        body: Vec<CommandList>,
        else_part: Option<Box<ElsePart>>,
        io_redirects: Vec<IoRedirect>,
    ) -> Self {
        let range = span_for_command_lists(&condition)
            .cover(span_for_command_lists(&body))
            .cover(else_part.as_deref().map(Spanned::span).unwrap_or_default())
            .cover(span_for_redirects(&io_redirects));
        Self {
            condition,
            body,
            else_part,
            io_redirects,
            range,
        }
    }

    pub fn with_range(
        condition: Vec<CommandList>,
        body: Vec<CommandList>,
        else_part: Option<Box<ElsePart>>,
        range: Range,
    ) -> Self {
        Self::with_range_and_redirects(condition, body, else_part, Vec::new(), range)
    }

    pub fn with_range_and_redirects(
        condition: Vec<CommandList>,
        body: Vec<CommandList>,
        else_part: Option<Box<ElsePart>>,
        io_redirects: Vec<IoRedirect>,
        range: Range,
    ) -> Self {
        Self {
            condition,
            body,
            else_part,
            io_redirects,
            range,
        }
    }

    pub fn condition(&self) -> &[CommandList] {
        &self.condition
    }

    pub fn condition_mut(&mut self) -> &mut Vec<CommandList> {
        &mut self.condition
    }

    pub fn body(&self) -> &[CommandList] {
        &self.body
    }

    pub fn body_mut(&mut self) -> &mut Vec<CommandList> {
        &mut self.body
    }

    pub fn else_part(&self) -> Option<&ElsePart> {
        self.else_part.as_deref()
    }

    pub fn else_part_mut(&mut self) -> Option<&mut ElsePart> {
        self.else_part.as_deref_mut()
    }

    pub fn io_redirects(&self) -> &[IoRedirect] {
        &self.io_redirects
    }

    pub fn io_redirects_mut(&mut self) -> &mut Vec<IoRedirect> {
        &mut self.io_redirects
    }
}

impl Spanned for IfClause {
    fn span(&self) -> Range {
        self.range
    }
}

/// Else-body payload used by [`ElsePart::Else`].
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ElseClause {
    pub(crate) body: Vec<CommandList>,
    pub(crate) range: Range,
}

impl ElseClause {
    pub fn new(body: Vec<CommandList>) -> Self {
        let range = span_for_command_lists(&body);
        Self { body, range }
    }

    pub fn with_range(body: Vec<CommandList>, range: Range) -> Self {
        Self { body, range }
    }

    pub fn body(&self) -> &[CommandList] {
        &self.body
    }

    pub fn body_mut(&mut self) -> &mut Vec<CommandList> {
        &mut self.body
    }
}

impl Spanned for ElseClause {
    fn span(&self) -> Range {
        self.range
    }
}

/// The else/elif portion of an if clause.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum ElsePart {
    Elif(IfClause),
    Else(ElseClause),
}

impl Spanned for ElsePart {
    fn span(&self) -> Range {
        match self {
            ElsePart::Elif(if_clause) => if_clause.span(),
            ElsePart::Else(body) => body.span(),
        }
    }
}

/// A for loop clause.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ForClause {
    pub(crate) name: String,
    /// Whether `in` keyword was present.
    pub(crate) has_in: bool,
    /// The word list to iterate over.
    pub(crate) word_list: Vec<Word>,
    pub(crate) body: Vec<CommandList>,
    pub(crate) io_redirects: Vec<IoRedirect>,
    pub(crate) range: Range,
}

impl ForClause {
    pub fn new(
        name: impl Into<String>,
        has_in: bool,
        word_list: Vec<Word>,
        body: Vec<CommandList>,
    ) -> Self {
        Self::new_with_redirects(name, has_in, word_list, body, Vec::new())
    }

    pub fn new_with_redirects(
        name: impl Into<String>,
        has_in: bool,
        word_list: Vec<Word>,
        body: Vec<CommandList>,
        io_redirects: Vec<IoRedirect>,
    ) -> Self {
        let range = span_for_words(&word_list)
            .cover(span_for_command_lists(&body))
            .cover(span_for_redirects(&io_redirects));
        Self {
            name: name.into(),
            has_in,
            word_list,
            body,
            io_redirects,
            range,
        }
    }

    pub fn with_range(
        name: impl Into<String>,
        has_in: bool,
        word_list: Vec<Word>,
        body: Vec<CommandList>,
        range: Range,
    ) -> Self {
        Self::with_range_and_redirects(name, has_in, word_list, body, Vec::new(), range)
    }

    pub fn with_range_and_redirects(
        name: impl Into<String>,
        has_in: bool,
        word_list: Vec<Word>,
        body: Vec<CommandList>,
        io_redirects: Vec<IoRedirect>,
        range: Range,
    ) -> Self {
        Self {
            name: name.into(),
            has_in,
            word_list,
            body,
            io_redirects,
            range,
        }
    }

    pub fn name(&self) -> &str {
        &self.name
    }

    pub fn has_in(&self) -> bool {
        self.has_in
    }

    pub fn word_list(&self) -> &[Word] {
        &self.word_list
    }

    pub fn word_list_mut(&mut self) -> &mut Vec<Word> {
        &mut self.word_list
    }

    pub fn body(&self) -> &[CommandList] {
        &self.body
    }

    pub fn body_mut(&mut self) -> &mut Vec<CommandList> {
        &mut self.body
    }

    pub fn io_redirects(&self) -> &[IoRedirect] {
        &self.io_redirects
    }

    pub fn io_redirects_mut(&mut self) -> &mut Vec<IoRedirect> {
        &mut self.io_redirects
    }
}

impl Spanned for ForClause {
    fn span(&self) -> Range {
        self.range
    }
}

/// Loop type: while or until.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum LoopType {
    While,
    Until,
}

/// A while or until loop.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct LoopClause {
    pub(crate) loop_type: LoopType,
    pub(crate) condition: Vec<CommandList>,
    pub(crate) body: Vec<CommandList>,
    pub(crate) io_redirects: Vec<IoRedirect>,
    pub(crate) range: Range,
}

impl LoopClause {
    pub fn new(loop_type: LoopType, condition: Vec<CommandList>, body: Vec<CommandList>) -> Self {
        Self::new_with_redirects(loop_type, condition, body, Vec::new())
    }

    pub fn new_with_redirects(
        loop_type: LoopType,
        condition: Vec<CommandList>,
        body: Vec<CommandList>,
        io_redirects: Vec<IoRedirect>,
    ) -> Self {
        let range = span_for_command_lists(&condition)
            .cover(span_for_command_lists(&body))
            .cover(span_for_redirects(&io_redirects));
        Self {
            loop_type,
            condition,
            body,
            io_redirects,
            range,
        }
    }

    pub fn with_range(
        loop_type: LoopType,
        condition: Vec<CommandList>,
        body: Vec<CommandList>,
        range: Range,
    ) -> Self {
        Self::with_range_and_redirects(loop_type, condition, body, Vec::new(), range)
    }

    pub fn with_range_and_redirects(
        loop_type: LoopType,
        condition: Vec<CommandList>,
        body: Vec<CommandList>,
        io_redirects: Vec<IoRedirect>,
        range: Range,
    ) -> Self {
        Self {
            loop_type,
            condition,
            body,
            io_redirects,
            range,
        }
    }

    pub fn loop_type(&self) -> LoopType {
        self.loop_type
    }

    pub fn condition(&self) -> &[CommandList] {
        &self.condition
    }

    pub fn condition_mut(&mut self) -> &mut Vec<CommandList> {
        &mut self.condition
    }

    pub fn body(&self) -> &[CommandList] {
        &self.body
    }

    pub fn body_mut(&mut self) -> &mut Vec<CommandList> {
        &mut self.body
    }

    pub fn io_redirects(&self) -> &[IoRedirect] {
        &self.io_redirects
    }

    pub fn io_redirects_mut(&mut self) -> &mut Vec<IoRedirect> {
        &mut self.io_redirects
    }
}

impl Spanned for LoopClause {
    fn span(&self) -> Range {
        self.range
    }
}

/// A single case item: `pattern [| pattern]...) body ;;`.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct CaseItem {
    pub(crate) patterns: Vec<Word>,
    pub(crate) body: Vec<CommandList>,
    pub(crate) range: Range,
}

impl CaseItem {
    pub fn new(patterns: Vec<Word>, body: Vec<CommandList>) -> Self {
        let range = span_for_words(&patterns).cover(span_for_command_lists(&body));
        Self {
            patterns,
            body,
            range,
        }
    }

    pub fn with_range(patterns: Vec<Word>, body: Vec<CommandList>, range: Range) -> Self {
        Self {
            patterns,
            body,
            range,
        }
    }

    pub fn patterns(&self) -> &[Word] {
        &self.patterns
    }

    pub fn patterns_mut(&mut self) -> &mut Vec<Word> {
        &mut self.patterns
    }

    pub fn body(&self) -> &[CommandList] {
        &self.body
    }

    pub fn body_mut(&mut self) -> &mut Vec<CommandList> {
        &mut self.body
    }
}

impl Spanned for CaseItem {
    fn span(&self) -> Range {
        self.range
    }
}

/// A case clause.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct CaseClause {
    pub(crate) word: Word,
    pub(crate) items: Vec<CaseItem>,
    pub(crate) io_redirects: Vec<IoRedirect>,
    pub(crate) range: Range,
}

impl CaseClause {
    pub fn new(word: Word, items: Vec<CaseItem>) -> Self {
        Self::new_with_redirects(word, items, Vec::new())
    }

    pub fn new_with_redirects(
        word: Word,
        items: Vec<CaseItem>,
        io_redirects: Vec<IoRedirect>,
    ) -> Self {
        let range = word
            .span()
            .cover(span_for_case_items(&items))
            .cover(span_for_redirects(&io_redirects));
        Self {
            word,
            items,
            io_redirects,
            range,
        }
    }

    pub fn with_range(word: Word, items: Vec<CaseItem>, range: Range) -> Self {
        Self::with_range_and_redirects(word, items, Vec::new(), range)
    }

    pub fn with_range_and_redirects(
        word: Word,
        items: Vec<CaseItem>,
        io_redirects: Vec<IoRedirect>,
        range: Range,
    ) -> Self {
        Self {
            word,
            items,
            io_redirects,
            range,
        }
    }

    pub fn word(&self) -> &Word {
        &self.word
    }

    pub fn word_mut(&mut self) -> &mut Word {
        &mut self.word
    }

    pub fn items(&self) -> &[CaseItem] {
        &self.items
    }

    pub fn items_mut(&mut self) -> &mut Vec<CaseItem> {
        &mut self.items
    }

    pub fn io_redirects(&self) -> &[IoRedirect] {
        &self.io_redirects
    }

    pub fn io_redirects_mut(&mut self) -> &mut Vec<IoRedirect> {
        &mut self.io_redirects
    }
}

impl Spanned for CaseClause {
    fn span(&self) -> Range {
        self.range
    }
}

/// A function definition.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct FunctionDefinition {
    pub(crate) name: String,
    pub(crate) body: Box<Command>,
    pub(crate) io_redirects: Vec<IoRedirect>,
    pub(crate) range: Range,
}

impl FunctionDefinition {
    pub fn new(name: impl Into<String>, body: Command, io_redirects: Vec<IoRedirect>) -> Self {
        let range = body.span().cover(span_for_redirects(&io_redirects));
        Self {
            name: name.into(),
            body: Box::new(body),
            io_redirects,
            range,
        }
    }

    pub fn with_range(
        name: impl Into<String>,
        body: Command,
        io_redirects: Vec<IoRedirect>,
        range: Range,
    ) -> Self {
        Self {
            name: name.into(),
            body: Box::new(body),
            io_redirects,
            range,
        }
    }

    pub fn name(&self) -> &str {
        &self.name
    }

    pub fn body(&self) -> &Command {
        &self.body
    }

    pub fn body_mut(&mut self) -> &mut Command {
        &mut self.body
    }

    pub fn io_redirects(&self) -> &[IoRedirect] {
        &self.io_redirects
    }

    pub fn io_redirects_mut(&mut self) -> &mut Vec<IoRedirect> {
        &mut self.io_redirects
    }
}

impl Spanned for FunctionDefinition {
    fn span(&self) -> Range {
        self.range
    }
}

// ── And-Or List / Pipeline ───────────────────────────────────────────

/// Binary and-or metadata used by [`AndOrList::BinOp`].
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct AndOrBinary {
    pub(crate) op: BinOpType,
    pub(crate) left: Box<AndOrList>,
    pub(crate) right: Box<AndOrList>,
    pub(crate) range: Range,
}

impl AndOrBinary {
    pub fn new(op: BinOpType, left: AndOrList, right: AndOrList) -> Self {
        let range = left.span().cover(right.span());
        Self {
            op,
            left: Box::new(left),
            right: Box::new(right),
            range,
        }
    }

    pub fn with_range(op: BinOpType, left: AndOrList, right: AndOrList, range: Range) -> Self {
        Self {
            op,
            left: Box::new(left),
            right: Box::new(right),
            range,
        }
    }

    pub fn op(&self) -> BinOpType {
        self.op
    }

    pub fn left(&self) -> &AndOrList {
        &self.left
    }

    pub fn right(&self) -> &AndOrList {
        &self.right
    }
}

impl Spanned for AndOrBinary {
    fn span(&self) -> Range {
        self.range
    }
}

/// An and-or list node.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum AndOrList {
    /// A single pipeline.
    Pipeline(Pipeline),
    /// A binary `&&` or `||` operation.
    BinOp(AndOrBinary),
}

impl Spanned for AndOrList {
    fn span(&self) -> Range {
        match self {
            AndOrList::Pipeline(pipeline) => pipeline.span(),
            AndOrList::BinOp(bin_op) => bin_op.span(),
        }
    }
}

/// Type of binary and-or operator.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum BinOpType {
    And,
    Or,
}

/// A pipeline: `[!] cmd1 | cmd2 | ...`.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Pipeline {
    pub(crate) commands: Vec<Command>,
    /// Whether the pipeline is negated with `!`.
    pub(crate) bang: bool,
    pub(crate) range: Range,
}

impl Pipeline {
    pub fn new(commands: Vec<Command>, bang: bool, range: Range) -> Self {
        Self {
            commands,
            bang,
            range,
        }
    }

    pub fn commands(&self) -> &[Command] {
        &self.commands
    }

    pub fn commands_mut(&mut self) -> &mut Vec<Command> {
        &mut self.commands
    }

    pub fn bang(&self) -> bool {
        self.bang
    }
}

impl Spanned for Pipeline {
    fn span(&self) -> Range {
        self.range
    }
}

// ── Command List / Program ───────────────────────────────────────────

/// A command list entry: an and-or list optionally followed by `&`.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct CommandList {
    pub(crate) and_or_list: AndOrList,
    /// Whether terminated by `&` (asynchronous execution).
    pub(crate) ampersand: bool,
    pub(crate) range: Range,
}

impl CommandList {
    pub fn new(and_or_list: AndOrList, ampersand: bool, range: Range) -> Self {
        Self {
            and_or_list,
            ampersand,
            range,
        }
    }

    pub fn and_or_list(&self) -> &AndOrList {
        &self.and_or_list
    }

    pub fn and_or_list_mut(&mut self) -> &mut AndOrList {
        &mut self.and_or_list
    }

    pub fn ampersand(&self) -> bool {
        self.ampersand
    }
}

impl Spanned for CommandList {
    fn span(&self) -> Range {
        self.range
    }
}

/// A complete shell program.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Program {
    pub(crate) body: Vec<CommandList>,
    pub(crate) range: Range,
}

impl Program {
    pub fn new(body: Vec<CommandList>) -> Self {
        let range = span_for_command_lists(&body);
        Self { body, range }
    }

    pub fn with_range(body: Vec<CommandList>, range: Range) -> Self {
        Self { body, range }
    }

    pub fn body(&self) -> &[CommandList] {
        &self.body
    }

    pub fn body_mut(&mut self) -> &mut Vec<CommandList> {
        &mut self.body
    }

    /// Parse a full shell program with the default pure parse options.
    pub fn parse(text: &str) -> Result<Self, crate::parser::ParseError> {
        crate::parser::parse(text)
    }

    /// Parse a full shell program and collect non-fatal diagnostics.
    pub fn parse_with(
        text: &str,
        options: &crate::parser::ParseOptions,
    ) -> Result<crate::parser::ParsedProgram, crate::parser::ParseError> {
        crate::parser::parse_with(text, options)
    }

    /// Render this AST as a canonical shell script.
    ///
    /// This focuses on stable formatting and round-trippable syntax for the
    /// parser-supported constructs, including here-doc redirects.
    pub fn to_canonical(&self) -> String {
        canonical_program(self)
    }
}

impl Spanned for Program {
    fn span(&self) -> Range {
        self.range
    }
}

fn span_for_words(words: &[Word]) -> Range {
    span_for_iter(words.iter().map(Spanned::span))
}

fn span_for_redirects(io_redirects: &[IoRedirect]) -> Range {
    span_for_iter(io_redirects.iter().map(Spanned::span))
}

fn span_for_assignments(assignments: &[Assignment]) -> Range {
    span_for_iter(assignments.iter().map(Spanned::span))
}

fn span_for_command_lists(command_lists: &[CommandList]) -> Range {
    span_for_iter(command_lists.iter().map(Spanned::span))
}

fn span_for_case_items(items: &[CaseItem]) -> Range {
    span_for_iter(items.iter().map(Spanned::span))
}

fn span_for_iter(iter: impl IntoIterator<Item = Range>) -> Range {
    iter.into_iter()
        .fold(Range::unknown(), |span, item| span.cover(item))
}

/// AST visitor for traversing shell syntax trees.
///
/// Override the specific `visit_*` methods you care about and call the
/// corresponding `walk_*` function to continue descending recursively.
pub trait Visitor {
    fn visit_program(&mut self, program: &Program) {
        walk_program(self, program);
    }

    fn visit_command_list(&mut self, command_list: &CommandList) {
        walk_command_list(self, command_list);
    }

    fn visit_and_or_list(&mut self, and_or: &AndOrList) {
        walk_and_or_list(self, and_or);
    }

    fn visit_pipeline(&mut self, pipeline: &Pipeline) {
        walk_pipeline(self, pipeline);
    }

    fn visit_command(&mut self, command: &Command) {
        walk_command(self, command);
    }

    fn visit_brace_group(&mut self, body: &[CommandList], io_redirects: &[IoRedirect]) {
        walk_brace_group(self, body, io_redirects);
    }

    fn visit_subshell(&mut self, body: &[CommandList], io_redirects: &[IoRedirect]) {
        walk_subshell(self, body, io_redirects);
    }

    fn visit_simple_command(&mut self, simple: &SimpleCommand) {
        walk_simple_command(self, simple);
    }

    fn visit_if_clause(&mut self, if_clause: &IfClause) {
        walk_if_clause(self, if_clause);
    }

    fn visit_else_part(&mut self, else_part: &ElsePart) {
        walk_else_part(self, else_part);
    }

    fn visit_for_clause(&mut self, for_clause: &ForClause) {
        walk_for_clause(self, for_clause);
    }

    fn visit_loop_clause(&mut self, loop_clause: &LoopClause) {
        walk_loop_clause(self, loop_clause);
    }

    fn visit_case_clause(&mut self, case_clause: &CaseClause) {
        walk_case_clause(self, case_clause);
    }

    fn visit_case_item(&mut self, case_item: &CaseItem) {
        walk_case_item(self, case_item);
    }

    fn visit_function_definition(&mut self, function_definition: &FunctionDefinition) {
        walk_function_definition(self, function_definition);
    }

    fn visit_io_redirect(&mut self, io_redirect: &IoRedirect) {
        walk_io_redirect(self, io_redirect);
    }

    fn visit_assignment(&mut self, assignment: &Assignment) {
        walk_assignment(self, assignment);
    }

    fn visit_word(&mut self, word: &Word) {
        walk_word(self, word);
    }

    fn visit_arithm_expr(&mut self, expr: &ArithmExpr) {
        walk_arithm_expr(self, expr);
    }
}

/// Recursively walk a full program.
pub fn walk_program<V: Visitor + ?Sized>(visitor: &mut V, program: &Program) {
    for cl in program.body() {
        visitor.visit_command_list(cl);
    }
}

/// Recursively walk one command-list entry.
pub fn walk_command_list<V: Visitor + ?Sized>(visitor: &mut V, command_list: &CommandList) {
    visitor.visit_and_or_list(command_list.and_or_list());
}

/// Recursively walk an and-or list.
pub fn walk_and_or_list<V: Visitor + ?Sized>(visitor: &mut V, and_or: &AndOrList) {
    match and_or {
        AndOrList::Pipeline(p) => visitor.visit_pipeline(p),
        AndOrList::BinOp(bin_op) => {
            visitor.visit_and_or_list(bin_op.left());
            visitor.visit_and_or_list(bin_op.right());
        }
    }
}

/// Recursively walk a pipeline.
pub fn walk_pipeline<V: Visitor + ?Sized>(visitor: &mut V, pipeline: &Pipeline) {
    for command in pipeline.commands() {
        visitor.visit_command(command);
    }
}

/// Recursively walk a command.
pub fn walk_command<V: Visitor + ?Sized>(visitor: &mut V, command: &Command) {
    match command {
        Command::Simple(simple) => visitor.visit_simple_command(simple),
        Command::BraceGroup(group) => {
            visitor.visit_brace_group(group.body(), group.io_redirects());
        }
        Command::Subshell(group) => {
            visitor.visit_subshell(group.body(), group.io_redirects());
        }
        Command::If(if_clause) => visitor.visit_if_clause(if_clause),
        Command::For(for_clause) => visitor.visit_for_clause(for_clause),
        Command::Loop(loop_clause) => visitor.visit_loop_clause(loop_clause),
        Command::Case(case_clause) => visitor.visit_case_clause(case_clause),
        Command::FunctionDef(function_definition) => {
            visitor.visit_function_definition(function_definition);
        }
    }
}

/// Recursively walk a brace group body and its redirections.
pub fn walk_brace_group<V: Visitor + ?Sized>(
    visitor: &mut V,
    body: &[CommandList],
    io_redirects: &[IoRedirect],
) {
    for cl in body {
        visitor.visit_command_list(cl);
    }
    for redirect in io_redirects {
        visitor.visit_io_redirect(redirect);
    }
}

/// Recursively walk a subshell body and its redirections.
pub fn walk_subshell<V: Visitor + ?Sized>(
    visitor: &mut V,
    body: &[CommandList],
    io_redirects: &[IoRedirect],
) {
    for cl in body {
        visitor.visit_command_list(cl);
    }
    for redirect in io_redirects {
        visitor.visit_io_redirect(redirect);
    }
}

/// Recursively walk a simple command.
pub fn walk_simple_command<V: Visitor + ?Sized>(visitor: &mut V, simple: &SimpleCommand) {
    for assignment in simple.assignments() {
        visitor.visit_assignment(assignment);
    }
    if let Some(name) = simple.name() {
        visitor.visit_word(name);
    }
    for arg in simple.arguments() {
        visitor.visit_word(arg);
    }
    for redirect in simple.io_redirects() {
        visitor.visit_io_redirect(redirect);
    }
}

/// Recursively walk an if-clause.
pub fn walk_if_clause<V: Visitor + ?Sized>(visitor: &mut V, if_clause: &IfClause) {
    for cl in if_clause.condition() {
        visitor.visit_command_list(cl);
    }
    for cl in if_clause.body() {
        visitor.visit_command_list(cl);
    }
    if let Some(else_part) = if_clause.else_part() {
        visitor.visit_else_part(else_part);
    }
    for redirect in if_clause.io_redirects() {
        visitor.visit_io_redirect(redirect);
    }
}

/// Recursively walk an else-part.
pub fn walk_else_part<V: Visitor + ?Sized>(visitor: &mut V, else_part: &ElsePart) {
    match else_part {
        ElsePart::Elif(if_clause) => visitor.visit_if_clause(if_clause),
        ElsePart::Else(body) => {
            for cl in body.body() {
                visitor.visit_command_list(cl);
            }
        }
    }
}

/// Recursively walk a for-clause.
pub fn walk_for_clause<V: Visitor + ?Sized>(visitor: &mut V, for_clause: &ForClause) {
    for word in for_clause.word_list() {
        visitor.visit_word(word);
    }
    for cl in for_clause.body() {
        visitor.visit_command_list(cl);
    }
    for redirect in for_clause.io_redirects() {
        visitor.visit_io_redirect(redirect);
    }
}

/// Recursively walk a loop-clause.
pub fn walk_loop_clause<V: Visitor + ?Sized>(visitor: &mut V, loop_clause: &LoopClause) {
    for cl in loop_clause.condition() {
        visitor.visit_command_list(cl);
    }
    for cl in loop_clause.body() {
        visitor.visit_command_list(cl);
    }
    for redirect in loop_clause.io_redirects() {
        visitor.visit_io_redirect(redirect);
    }
}

/// Recursively walk a case-clause.
pub fn walk_case_clause<V: Visitor + ?Sized>(visitor: &mut V, case_clause: &CaseClause) {
    visitor.visit_word(case_clause.word());
    for item in case_clause.items() {
        visitor.visit_case_item(item);
    }
    for redirect in case_clause.io_redirects() {
        visitor.visit_io_redirect(redirect);
    }
}

/// Recursively walk one case-item.
pub fn walk_case_item<V: Visitor + ?Sized>(visitor: &mut V, case_item: &CaseItem) {
    for pattern in case_item.patterns() {
        visitor.visit_word(pattern);
    }
    for cl in case_item.body() {
        visitor.visit_command_list(cl);
    }
}

/// Recursively walk a function definition.
pub fn walk_function_definition<V: Visitor + ?Sized>(
    visitor: &mut V,
    function_definition: &FunctionDefinition,
) {
    visitor.visit_command(function_definition.body());
    for redirect in function_definition.io_redirects() {
        visitor.visit_io_redirect(redirect);
    }
}

/// Recursively walk one redirection.
pub fn walk_io_redirect<V: Visitor + ?Sized>(visitor: &mut V, io_redirect: &IoRedirect) {
    visitor.visit_word(io_redirect.name());
    for word in io_redirect.here_document() {
        visitor.visit_word(word);
    }
}

/// Recursively walk one assignment.
pub fn walk_assignment<V: Visitor + ?Sized>(visitor: &mut V, assignment: &Assignment) {
    visitor.visit_word(assignment.value());
}

/// Recursively walk one word tree.
pub fn walk_word<V: Visitor + ?Sized>(visitor: &mut V, word: &Word) {
    match word {
        Word::String(_) => {}
        Word::Parameter(parameter) => {
            if let Some(arg) = parameter.arg() {
                visitor.visit_word(arg);
            }
        }
        Word::Command(command) => visitor.visit_program(command.program()),
        Word::Arithmetic(arithm) => visitor.visit_arithm_expr(arithm.body()),
        Word::List(list) => {
            for child in list.children() {
                visitor.visit_word(child);
            }
        }
    }
}

/// Recursively walk one arithmetic expression tree.
pub fn walk_arithm_expr<V: Visitor + ?Sized>(visitor: &mut V, expr: &ArithmExpr) {
    match expr {
        ArithmExpr::Literal(_) | ArithmExpr::Variable(_) => {}
        ArithmExpr::Raw(_) => {}
        ArithmExpr::BinOp(binary) => {
            visitor.visit_arithm_expr(binary.left());
            visitor.visit_arithm_expr(binary.right());
        }
        ArithmExpr::UnOp(unary) => visitor.visit_arithm_expr(unary.operand()),
        ArithmExpr::Cond(cond) => {
            visitor.visit_arithm_expr(cond.cond());
            visitor.visit_arithm_expr(cond.then_branch());
            visitor.visit_arithm_expr(cond.else_branch());
        }
        ArithmExpr::Assign(assign) => visitor.visit_arithm_expr(assign.value()),
    }
}

fn canonical_program(program: &Program) -> String {
    let mut visitor = CanonicalVisitor::default();
    visitor.visit_program(program);
    visitor.programs.pop().unwrap_or_default()
}

#[derive(Default)]
struct CanonicalContext {
    next_heredoc_id: usize,
}

struct HereDocBlock {
    strip_tabs: bool,
    delimiter: String,
    lines: Vec<String>,
}

struct CanonicalRendered {
    text: String,
    heredocs: Vec<HereDocBlock>,
}

#[derive(Default)]
struct HeredocDetector {
    found: bool,
}

#[derive(Default)]
struct CanonicalVisitor {
    ctx: CanonicalContext,
    programs: Vec<String>,
    command_lists: Vec<String>,
    and_or_lists: Vec<CanonicalRendered>,
    pipelines: Vec<CanonicalRendered>,
    commands: Vec<CanonicalRendered>,
}

impl CanonicalVisitor {
    fn take_tail<T>(stack: &mut Vec<T>, start: usize) -> Vec<T> {
        stack.drain(start..).collect()
    }

    fn pop_rendered(stack: &mut Vec<CanonicalRendered>) -> CanonicalRendered {
        stack.pop().unwrap_or(CanonicalRendered {
            text: String::new(),
            heredocs: Vec::new(),
        })
    }

    fn render_command_lists(&mut self, lists: &[CommandList]) -> Vec<String> {
        let start = self.command_lists.len();
        for cl in lists {
            self.visit_command_list(cl);
        }
        Self::take_tail(&mut self.command_lists, start)
    }

    fn render_if_clause(&mut self, ic: &IfClause) -> String {
        let cond_inner = join_command_lists(&self.render_command_lists(ic.condition()));
        let cond_sep = separator_suffix(&cond_inner, " ; ");
        let body_inner = join_command_lists(&self.render_command_lists(ic.body()));
        let mut out = format!("if {cond_inner}{cond_sep}then {body_inner}");
        self.render_else_part(ic.else_part(), &mut out);
        out.push_str(separator_suffix(&out, " ; "));
        out.push_str("fi");
        out
    }

    fn render_else_part(&mut self, else_part: Option<&ElsePart>, out: &mut String) {
        if let Some(else_part) = else_part {
            match else_part {
                ElsePart::Elif(elif) => {
                    out.push_str(separator_suffix(out, " ; "));
                    out.push_str("elif ");
                    let cond_inner =
                        join_command_lists(&self.render_command_lists(elif.condition()));
                    out.push_str(&cond_inner);
                    out.push_str(separator_suffix(&cond_inner, " ; "));
                    out.push_str("then ");
                    let body_inner = join_command_lists(&self.render_command_lists(elif.body()));
                    out.push_str(&body_inner);
                    self.render_else_part(elif.else_part(), out);
                }
                ElsePart::Else(body) => {
                    out.push_str(separator_suffix(out, " ; "));
                    out.push_str("else ");
                    let body_inner = join_command_lists(&self.render_command_lists(body.body()));
                    out.push_str(&body_inner);
                }
            }
        }
    }

    fn render_case_item(&mut self, item: &CaseItem) -> String {
        let patterns = item
            .patterns
            .iter()
            .map(canonical_pattern_word)
            .collect::<Vec<_>>()
            .join(" | ");
        if item.body.is_empty() {
            format!("{patterns}) ;;")
        } else {
            let body_inner = join_command_lists(&self.render_command_lists(&item.body));
            format!("{patterns}) {body_inner} ;;")
        }
    }

    fn render_redirects(&mut self, io_redirects: &[IoRedirect]) -> (String, Vec<HereDocBlock>) {
        let mut heredocs = Vec::new();
        let text = io_redirects
            .iter()
            .map(|r| canonical_redirect(r, &mut self.ctx, &mut heredocs))
            .collect::<Vec<_>>()
            .join(" ");
        (text, heredocs)
    }

    fn append_redirects(
        &mut self,
        text: &mut String,
        heredocs: &mut Vec<HereDocBlock>,
        io_redirects: &[IoRedirect],
    ) {
        if io_redirects.is_empty() {
            return;
        }
        let (redirect_text, redirect_heredocs) = self.render_redirects(io_redirects);
        text.push(' ');
        text.push_str(&redirect_text);
        heredocs.extend(redirect_heredocs);
    }
}

impl Visitor for HeredocDetector {
    fn visit_io_redirect(&mut self, io_redirect: &IoRedirect) {
        if matches!(
            io_redirect.op,
            IoRedirectOp::DLess | IoRedirectOp::DLessDash
        ) {
            self.found = true;
        }
        walk_io_redirect(self, io_redirect);
    }
}

impl Visitor for CanonicalVisitor {
    fn visit_program(&mut self, program: &Program) {
        let rendered = self.render_command_lists(program.body());
        let mut out = String::new();
        for (idx, cl) in rendered.iter().enumerate() {
            if idx > 0 {
                if out.ends_with('&') {
                    out.push('\n');
                } else if !out.ends_with('\n') {
                    out.push_str(" ;\n");
                }
            }
            out.push_str(cl);
        }
        if !out.ends_with('\n') {
            out.push('\n');
        }
        self.programs.push(out);
    }

    fn visit_command_list(&mut self, cl: &CommandList) {
        self.visit_and_or_list(cl.and_or_list());
        let mut rendered = Self::pop_rendered(&mut self.and_or_lists);
        let mut out = rendered.text;
        if cl.ampersand() {
            out.push_str(" &");
        }
        append_heredocs(&mut out, std::mem::take(&mut rendered.heredocs));
        self.command_lists.push(out);
    }

    fn visit_and_or_list(&mut self, aol: &AndOrList) {
        match aol {
            AndOrList::Pipeline(p) => {
                self.visit_pipeline(p);
                self.and_or_lists
                    .push(Self::pop_rendered(&mut self.pipelines));
            }
            AndOrList::BinOp(bin_op) => {
                let op_text = match bin_op.op() {
                    BinOpType::And => "&&",
                    BinOpType::Or => "||",
                };
                self.visit_and_or_list(bin_op.left());
                self.visit_and_or_list(bin_op.right());
                let mut right_r = Self::pop_rendered(&mut self.and_or_lists);
                if and_or_right_requires_grouping(bin_op.op(), bin_op.right()) {
                    right_r.text = format!(
                        "{{ {}{}}}",
                        right_r.text,
                        missing_separator_suffix(&right_r.text, "; ")
                    );
                }
                let mut left_r = Self::pop_rendered(&mut self.and_or_lists);
                left_r.text = format!("{} {} {}", left_r.text, op_text, right_r.text);
                left_r.heredocs.extend(right_r.heredocs);
                self.and_or_lists.push(left_r);
            }
        }
    }

    fn visit_pipeline(&mut self, p: &Pipeline) {
        let start = self.commands.len();
        for c in p.commands() {
            self.visit_command(c);
        }
        let mut rendered = Self::take_tail(&mut self.commands, start).into_iter();
        let mut first = rendered.next().unwrap_or(CanonicalRendered {
            text: String::new(),
            heredocs: Vec::new(),
        });
        for next in rendered {
            first.text.push_str(" | ");
            first.text.push_str(&next.text);
            first.heredocs.extend(next.heredocs);
        }
        if p.bang() {
            first.text = format!("! {}", first.text);
        }
        self.pipelines.push(first);
    }

    fn visit_command(&mut self, c: &Command) {
        match c {
            Command::Simple(sc) => {
                let mut parts = Vec::new();
                parts.extend(
                    sc.assignments()
                        .iter()
                        .map(|a| format!("{}={}", a.name(), canonical_word(a.value()))),
                );
                if let Some(name) = sc.name() {
                    parts.push(canonical_word(name));
                    parts.extend(sc.arguments().iter().map(canonical_word));
                }
                let mut heredocs = Vec::new();
                parts.extend(
                    sc.io_redirects()
                        .iter()
                        .map(|r| canonical_redirect(r, &mut self.ctx, &mut heredocs)),
                );
                self.commands.push(CanonicalRendered {
                    text: parts.join(" "),
                    heredocs,
                });
            }
            Command::BraceGroup(group) => {
                let inner = join_command_lists(&self.render_command_lists(group.body()));
                let sep = missing_separator_suffix(&inner, "; ");
                let mut text = format!("{{ {inner}{sep}}}");
                let mut heredocs = Vec::new();
                self.append_redirects(&mut text, &mut heredocs, group.io_redirects());
                self.commands.push(CanonicalRendered { text, heredocs });
            }
            Command::Subshell(group) => {
                let inner = join_command_lists(&self.render_command_lists(group.body()));
                let mut text = format!("( {inner} )");
                let mut heredocs = Vec::new();
                self.append_redirects(&mut text, &mut heredocs, group.io_redirects());
                self.commands.push(CanonicalRendered { text, heredocs });
            }
            Command::If(ic) => {
                let mut text = self.render_if_clause(ic);
                let mut heredocs = Vec::new();
                self.append_redirects(&mut text, &mut heredocs, ic.io_redirects());
                self.commands.push(CanonicalRendered { text, heredocs });
            }
            Command::For(fc) => {
                let mut s = format!("for {}", fc.name());
                if fc.has_in() {
                    s.push_str(" in");
                    if !fc.word_list().is_empty() {
                        s.push(' ');
                        s.push_str(
                            &fc.word_list()
                                .iter()
                                .map(canonical_word)
                                .collect::<Vec<_>>()
                                .join(" "),
                        );
                    }
                }
                s.push_str(" ; do ");
                let body_inner = join_command_lists(&self.render_command_lists(fc.body()));
                s.push_str(&body_inner);
                s.push_str(missing_separator_suffix(&s, " ; "));
                s.push_str("done");
                let mut heredocs = Vec::new();
                self.append_redirects(&mut s, &mut heredocs, fc.io_redirects());
                self.commands.push(CanonicalRendered { text: s, heredocs });
            }
            Command::Loop(lc) => {
                let kw = match lc.loop_type() {
                    LoopType::While => "while",
                    LoopType::Until => "until",
                };
                let cond_inner = join_command_lists(&self.render_command_lists(lc.condition()));
                let body_inner = join_command_lists(&self.render_command_lists(lc.body()));
                let cond_sep = missing_separator_suffix(&cond_inner, " ; ");
                let body_sep = missing_separator_suffix(&body_inner, " ; ");
                let mut text = format!("{kw} {cond_inner}{cond_sep}do {body_inner}{body_sep}done",);
                let mut heredocs = Vec::new();
                self.append_redirects(&mut text, &mut heredocs, lc.io_redirects());
                self.commands.push(CanonicalRendered { text, heredocs });
            }
            Command::Case(cc) => {
                let items = cc
                    .items()
                    .iter()
                    .map(|item| self.render_case_item(item))
                    .collect::<Vec<_>>()
                    .join(" ");
                let mut text = format!("case {} in {} esac", canonical_word(cc.word()), items);
                let mut heredocs = Vec::new();
                self.append_redirects(&mut text, &mut heredocs, cc.io_redirects());
                self.commands.push(CanonicalRendered { text, heredocs });
            }
            Command::FunctionDef(fd) => {
                self.visit_command(fd.body());
                let body = Self::pop_rendered(&mut self.commands);
                let mut text = format!("{}() {}", fd.name(), body.text);
                let mut heredocs = Vec::new();
                self.append_redirects(&mut text, &mut heredocs, fd.io_redirects());
                self.commands.push(CanonicalRendered { text, heredocs });
            }
        }
    }
}

/// Return true when the string ends with a separator that acts as a command
/// terminator — either `&` or `\n` (from a heredoc delimiter line).  When
/// true, no additional `" ; "` is needed before the next command or keyword.
#[cfg(test)]
fn ends_with_separator(s: &str) -> bool {
    s.ends_with('&') || s.ends_with('\n')
}

fn missing_separator_suffix<'a>(s: &str, suffix: &'a str) -> &'a str {
    separator_suffix(s, suffix)
}

/// Join rendered command lists with `" ; "`, but skip the `" ; "` when the
/// previous element already ends with a separator (`&` or `\n` from a heredoc
/// delimiter).
fn join_command_lists(parts: &[String]) -> String {
    let mut out = String::new();
    for (idx, part) in parts.iter().enumerate() {
        if idx > 0 {
            out.push_str(separator_suffix(&out, " ; "));
        }
        out.push_str(part);
    }
    out
}

fn separator_suffix<'a>(s: &str, suffix: &'a str) -> &'a str {
    if s.ends_with('&') {
        " "
    } else if s.ends_with('\n') {
        ""
    } else {
        suffix
    }
}

fn and_or_right_requires_grouping(parent_op: BinOpType, right: &AndOrList) -> bool {
    matches!(right, AndOrList::BinOp(bin_op) if bin_op.op() != parent_op)
}

fn canonical_redirect(
    r: &IoRedirect,
    ctx: &mut CanonicalContext,
    heredocs: &mut Vec<HereDocBlock>,
) -> String {
    let io = if let Some(n) = r.io_number() {
        n.to_string()
    } else {
        String::new()
    };
    let op = match r.op() {
        IoRedirectOp::Less => "<",
        IoRedirectOp::Great => ">",
        IoRedirectOp::Clobber => ">|",
        IoRedirectOp::DGreat => ">>",
        IoRedirectOp::LessAnd => "<&",
        IoRedirectOp::GreatAnd => ">&",
        IoRedirectOp::LessGreat => "<>",
        IoRedirectOp::DLess => "<<",
        IoRedirectOp::DLessDash => "<<-",
    };
    if matches!(r.op(), IoRedirectOp::DLess | IoRedirectOp::DLessDash) {
        let expands = r.here_document_expand();
        let lines = if expands {
            r.here_document()
                .iter()
                .map(canonical_here_doc_word)
                .collect::<Vec<_>>()
        } else {
            r.here_document()
                .iter()
                .map(canonical_here_doc_literal_line)
                .collect::<Vec<_>>()
        };
        // `<<-` strips all leading tabs from each body line. If a stored line
        // already begins with a tab, re-emitting `<<-` would lose payload bytes.
        let strip_tabs =
            r.op() == IoRedirectOp::DLessDash && !lines.iter().any(|line| line.starts_with('\t'));
        let op = if strip_tabs { "<<-" } else { "<<" };
        let delimiter = choose_heredoc_delimiter(lines.as_slice(), strip_tabs, ctx);
        let delimiter_token = if expands {
            delimiter.clone()
        } else {
            quote_single(&delimiter)
        };
        heredocs.push(HereDocBlock {
            strip_tabs,
            delimiter: delimiter.clone(),
            lines,
        });
        return format!("{io}{op} {delimiter_token}");
    }
    format!("{io}{op} {}", canonical_word(r.name()))
}

fn append_heredocs(out: &mut String, heredocs: Vec<HereDocBlock>) {
    for block in heredocs {
        out.push('\n');
        for line in block.lines {
            if block.strip_tabs {
                out.push('\t');
            }
            out.push_str(&line);
            out.push('\n');
        }
        out.push_str(&block.delimiter);
        out.push('\n');
    }
}

const MAX_HEREDOC_DELIMITER_ATTEMPTS: usize = 1000;

fn choose_heredoc_delimiter(
    lines: &[String],
    strip_tabs: bool,
    ctx: &mut CanonicalContext,
) -> String {
    for _ in 0..MAX_HEREDOC_DELIMITER_ATTEMPTS {
        let delim = format!("MXSH_HEREDOC_{}", ctx.next_heredoc_id);
        ctx.next_heredoc_id += 1;
        let conflicts = lines.iter().any(|line| {
            if strip_tabs {
                line.trim_start_matches('\t') == delim
            } else {
                *line == delim
            }
        });
        if !conflicts {
            return delim;
        }
    }

    let nonce = SystemTime::now()
        .duration_since(UNIX_EPOCH)
        .map(|now| now.as_nanos())
        .unwrap_or(0);
    let mut fallback_attempt = 0u64;
    loop {
        let delim = format!(
            "MXSH_HEREDOC_{:016x}_{}_{}",
            nonce, fallback_attempt, ctx.next_heredoc_id
        );
        ctx.next_heredoc_id += 1;
        fallback_attempt += 1;
        let conflicts = lines.iter().any(|line| {
            if strip_tabs {
                line.trim_start_matches('\t') == delim
            } else {
                *line == delim
            }
        });
        if !conflicts {
            return delim;
        }
    }
}

pub(crate) fn canonical_here_doc_literal_line(w: &Word) -> String {
    match w {
        Word::String(string) => string.value.clone(),
        Word::Parameter(parameter) => canonical_parameter(
            parameter.name(),
            parameter.op(),
            parameter.colon(),
            parameter.brace_end().is_some(),
            parameter.arg(),
        ),
        Word::Command(command) => canonical_literal_command_substitution(
            command.program(),
            command.source(),
            command.back_quoted(),
        ),
        Word::Arithmetic(arithm) => format!("$(({}))", canonical_arithm(arithm.body())),
        Word::List(list) => list
            .children()
            .iter()
            .map(canonical_here_doc_literal_line)
            .collect::<String>(),
    }
}

fn canonical_here_doc_word(w: &Word) -> String {
    match w {
        Word::String(string) => {
            let mut out = String::new();
            for ch in string.value().chars() {
                match ch {
                    '\\' | '$' | '`' => {
                        out.push('\\');
                        out.push(ch);
                    }
                    _ => out.push(ch),
                }
            }
            out
        }
        Word::Parameter(parameter) => canonical_parameter(
            parameter.name(),
            parameter.op(),
            parameter.colon(),
            parameter.brace_end().is_some(),
            parameter.arg(),
        ),
        Word::Command(command) => canonical_command_substitution(command.program()),
        Word::Arithmetic(arithm) => format!("$(({}))", canonical_arithm(arithm.body())),
        Word::List(list) => list
            .children()
            .iter()
            .map(canonical_here_doc_word)
            .collect::<String>(),
    }
}

fn canonical_word(w: &Word) -> String {
    match w {
        Word::String(string) => canonical_string_word(
            string.value(),
            string.single_quoted(),
            string.split_fields(),
            string.source(),
        ),
        Word::Parameter(parameter) => canonical_parameter(
            parameter.name(),
            parameter.op(),
            parameter.colon(),
            parameter.brace_end().is_some(),
            parameter.arg(),
        ),
        Word::Command(command) => canonical_command_substitution(command.program()),
        Word::Arithmetic(arithm) => format!("$(({}))", canonical_arithm(arithm.body())),
        Word::List(list) => {
            if !list.double_quoted()
                && let Some(literal) = collapse_literal_word_list(list.children())
            {
                let split_fields = collapsed_literal_split_fields(list.children());
                return canonical_word(&Word::string(
                    literal,
                    false,
                    split_fields,
                    None,
                    Range::default(),
                ));
            }
            let inner = list
                .children()
                .iter()
                .map(|child| canonical_word_piece(child, list.double_quoted()))
                .collect::<String>();
            if list.double_quoted() {
                format!("\"{inner}\"")
            } else {
                inner
            }
        }
    }
}

fn canonical_pattern_word(w: &Word) -> String {
    match w {
        Word::String(string) => {
            if let Some(source) = string.source() {
                return source.to_string();
            }
            if string.single_quoted() {
                return quote_single(string.value());
            }
            if string.value().is_empty() {
                return "''".to_string();
            }
            escape_pattern_unquoted(string.value())
        }
        Word::Parameter(parameter) => canonical_parameter(
            parameter.name(),
            parameter.op(),
            parameter.colon(),
            parameter.brace_end().is_some(),
            parameter.arg(),
        ),
        Word::Command(command) => canonical_command_substitution(command.program()),
        Word::Arithmetic(arithm) => format!("$(({}))", canonical_arithm(arithm.body())),
        Word::List(list) => {
            let inner = list
                .children()
                .iter()
                .map(|child| canonical_pattern_piece(child, list.double_quoted()))
                .collect::<String>();
            if list.double_quoted() {
                format!("\"{inner}\"")
            } else {
                inner
            }
        }
    }
}

fn canonical_command_substitution_body(program: &Program) -> String {
    let body = canonical_program(program);
    if program_contains_heredoc(program) {
        body
    } else {
        body.trim_end().to_string()
    }
}

fn canonical_command_substitution(program: &Program) -> String {
    let body = canonical_command_substitution_body(program);
    format!("$({body})")
}

fn canonical_literal_command_substitution(
    program: &Program,
    source: Option<&str>,
    back_quoted: bool,
) -> String {
    if back_quoted {
        let body = source
            .map(str::to_owned)
            .unwrap_or_else(|| canonical_command_substitution_body(program));
        return format!("`{}`", escape_backquoted(body.as_str()));
    }

    if let Some(source) = source {
        format!("$({source})")
    } else {
        canonical_command_substitution(program)
    }
}

fn program_contains_heredoc(program: &Program) -> bool {
    let mut detector = HeredocDetector::default();
    detector.visit_program(program);
    detector.found
}

fn collapse_literal_word_list(children: &[Word]) -> Option<String> {
    let mut literal = String::new();
    let mut has_quoted_or_nonsplitting_child = false;
    for child in children {
        let Word::String(string) = child else {
            return None;
        };
        literal.push_str(string.value());
        has_quoted_or_nonsplitting_child |= string.single_quoted() || !string.split_fields();
    }

    if literal.contains('*') || literal.contains('?') || literal.contains('[') {
        return None;
    }

    if literal.starts_with('~') && has_quoted_or_nonsplitting_child {
        return None;
    }

    let Some(Word::String(first)) = children.first() else {
        return Some(literal);
    };

    if first.single_quoted() || !first.split_fields() {
        return Some(literal);
    }

    if first.value().starts_with('~') && !(first.value() == "~" && children.len() > 1) {
        return None;
    }

    Some(literal)
}

fn collapsed_literal_split_fields(children: &[Word]) -> bool {
    children.iter().all(|child| {
        matches!(child, Word::String(string) if !string.single_quoted() && string.split_fields())
    })
}

fn contains_glob_chars(s: &str) -> bool {
    s.contains('*') || s.contains('?') || s.contains('[')
}

fn canonical_string_word(
    value: &str,
    single_quoted: bool,
    split_fields: bool,
    source: Option<&str>,
) -> String {
    if let Some(source) = source {
        return source.to_string();
    }
    if single_quoted {
        return quote_single(value);
    }
    if value.is_empty() {
        return "''".to_string();
    }
    if split_fields {
        if value.chars().any(char::is_whitespace) {
            return quote_single(value);
        }
        return escape_unquoted_word(value);
    }
    if value.starts_with('~') || contains_glob_chars(value) {
        return quote_single(value);
    }
    if needs_word_quoting(value) {
        quote_single(value)
    } else {
        value.to_string()
    }
}

fn canonical_word_piece(w: &Word, in_double_quotes: bool) -> String {
    if !in_double_quotes {
        return canonical_word(w);
    }
    match w {
        Word::String(string) => escape_double_quoted(string.value()),
        _ => canonical_word(w),
    }
}

fn canonical_pattern_piece(w: &Word, in_double_quotes: bool) -> String {
    if !in_double_quotes {
        return canonical_pattern_word(w);
    }
    match w {
        Word::String(string) => escape_double_quoted(string.value()),
        _ => canonical_pattern_word(w),
    }
}

fn canonical_parameter(
    name: &str,
    op: ParameterOp,
    colon: bool,
    braced: bool,
    arg: Option<&Word>,
) -> String {
    match op {
        ParameterOp::None => {
            if braced {
                format!("${{{name}}}")
            } else {
                format!("${name}")
            }
        }
        ParameterOp::LeadingHash => format!("${{#{name}}}"),
        _ => {
            let op_str = match op {
                ParameterOp::Minus => "-",
                ParameterOp::Equal => "=",
                ParameterOp::QMark => "?",
                ParameterOp::Plus => "+",
                ParameterOp::Percent => "%",
                ParameterOp::DoublePercent => "%%",
                ParameterOp::Hash => "#",
                ParameterOp::DoubleHash => "##",
                ParameterOp::None | ParameterOp::LeadingHash => unreachable!(),
            };
            let colon = if colon { ":" } else { "" };
            let arg = arg
                .map(|word| {
                    if matches!(
                        op,
                        ParameterOp::Percent
                            | ParameterOp::DoublePercent
                            | ParameterOp::Hash
                            | ParameterOp::DoubleHash
                    ) {
                        canonical_pattern_word(word)
                    } else {
                        canonical_word(word)
                    }
                })
                .unwrap_or_default();
            format!("${{{name}{colon}{op_str}{arg}}}")
        }
    }
}

fn canonical_arithm(expr: &ArithmExpr) -> String {
    match expr {
        ArithmExpr::Literal(literal) => literal.value().to_string(),
        ArithmExpr::Variable(variable) => variable.name().to_string(),
        ArithmExpr::Raw(raw) => raw.expr().to_string(),
        ArithmExpr::BinOp(binary) => {
            let op = match binary.op() {
                ArithmBinOp::Add => "+",
                ArithmBinOp::Sub => "-",
                ArithmBinOp::Mul => "*",
                ArithmBinOp::Div => "/",
                ArithmBinOp::Mod => "%",
                ArithmBinOp::Shl => "<<",
                ArithmBinOp::Shr => ">>",
                ArithmBinOp::LessThan => "<",
                ArithmBinOp::LessEq => "<=",
                ArithmBinOp::GreaterThan => ">",
                ArithmBinOp::GreaterEq => ">=",
                ArithmBinOp::Equal => "==",
                ArithmBinOp::NotEqual => "!=",
                ArithmBinOp::BitAnd => "&",
                ArithmBinOp::BitXor => "^",
                ArithmBinOp::BitOr => "|",
                ArithmBinOp::LogAnd => "&&",
                ArithmBinOp::LogOr => "||",
            };
            format!(
                "({} {} {})",
                canonical_arithm(binary.left()),
                op,
                canonical_arithm(binary.right())
            )
        }
        ArithmExpr::UnOp(unary) => {
            let op = match unary.op() {
                ArithmUnOp::Plus => "+",
                ArithmUnOp::Minus => "-",
                ArithmUnOp::BitNot => "~",
                ArithmUnOp::LogNot => "!",
            };
            format!("({}{})", op, canonical_arithm(unary.operand()))
        }
        ArithmExpr::Cond(cond) => format!(
            "({} ? {} : {})",
            canonical_arithm(cond.cond()),
            canonical_arithm(cond.then_branch()),
            canonical_arithm(cond.else_branch())
        ),
        ArithmExpr::Assign(assign) => {
            let op = match assign.op() {
                ArithmAssignOp::Equal => "=",
                ArithmAssignOp::MulEq => "*=",
                ArithmAssignOp::DivEq => "/=",
                ArithmAssignOp::ModEq => "%=",
                ArithmAssignOp::AddEq => "+=",
                ArithmAssignOp::SubEq => "-=",
                ArithmAssignOp::ShlEq => "<<=",
                ArithmAssignOp::ShrEq => ">>=",
                ArithmAssignOp::AndEq => "&=",
                ArithmAssignOp::XorEq => "^=",
                ArithmAssignOp::OrEq => "|=",
            };
            format!(
                "({} {op} {})",
                assign.name(),
                canonical_arithm(assign.value())
            )
        }
    }
}

fn quote_single(s: &str) -> String {
    format!("'{}'", s.replace('\'', "'\\''"))
}

fn escape_double_quoted(s: &str) -> String {
    let mut out = String::new();
    for ch in s.chars() {
        match ch {
            '\\' | '"' | '$' | '`' => {
                out.push('\\');
                out.push(ch);
            }
            _ => out.push(ch),
        }
    }
    out
}

fn escape_backquoted(s: &str) -> String {
    let mut out = String::new();
    for ch in s.chars() {
        match ch {
            '\\' | '$' | '`' => {
                out.push('\\');
                out.push(ch);
            }
            _ => out.push(ch),
        }
    }
    out
}

fn escape_unquoted_word(s: &str) -> String {
    let mut out = String::new();
    for ch in s.chars() {
        if ch.is_ascii_alphanumeric()
            || matches!(
                ch,
                '_' | '.'
                    | '/'
                    | '-'
                    | '+'
                    | ']'
                    | '='
                    | ':'
                    | '%'
                    | ','
                    | '!'
                    | '^'
                    | '{'
                    | '}'
                    | '@'
            )
        {
            out.push(ch);
        } else {
            out.push('\\');
            out.push(ch);
        }
    }
    out
}

fn escape_pattern_unquoted(s: &str) -> String {
    let mut out = String::new();
    for ch in s.chars() {
        if ch.is_ascii_alphanumeric()
            || matches!(
                ch,
                '_' | '.' | '/' | '-' | '+' | '*' | '?' | '[' | ']' | '!' | '^'
            )
        {
            out.push(ch);
        } else {
            out.push('\\');
            out.push(ch);
        }
    }
    out
}

fn needs_word_quoting(s: &str) -> bool {
    !s.chars()
        .all(|ch| ch.is_ascii_alphanumeric() || matches!(ch, '_' | '.' | '/' | '-' | '+'))
}

#[cfg(test)]
mod tests;