mxsh 0.2.0

#![cfg(all(feature = "embed", feature = "test-support", feature = "unix-runtime"))]

use proptest::prelude::*;

use mxsh::ast::{
    AndOrBinary, AndOrList, ArithmExpr, Assignment, CaseClause, CaseItem, Command, CommandList,
    CompoundCommand, ElseClause, ElsePart, ForClause, FunctionDefinition, IfClause, IoRedirect,
    IoRedirectOp, LoopClause, Pipeline, Program, Range, SimpleCommand, Word,
};
use mxsh::parser::{ParseError, Parser};

const SAFE_WORDS: &[&str] = &[
    "a", "b", "c", "x", "y", "z", "cmd", "echo", "printf", "test", "foo", "bar", "baz", "one",
    "two", "three", "arg", "file", "tmp", "path", "ok", "yes", "no", "loop", "item", "value",
];

const SAFE_NAMES: &[&str] = &[
    "A", "B", "C", "X", "Y", "Z", "VAR", "ITEM", "COUNT", "FLAG", "NAME", "PATH", "TMP", "OUT",
];

fn pick_word() -> impl Strategy<Value = String> {
    prop::sample::select(SAFE_WORDS)
        .prop_map(|s| s.to_string())
        .boxed()
}

fn pick_name() -> impl Strategy<Value = String> {
    prop::sample::select(SAFE_NAMES)
        .prop_map(|s| s.to_string())
        .boxed()
}

fn arithm_expr(depth: u32) -> BoxedStrategy<String> {
    let literal = (0i64..10i64).prop_map(|n| n.to_string());
    let variable = pick_name();
    let leaf = prop_oneof![literal, variable].boxed();
    if depth == 0 {
        return leaf;
    }

    let bin_op = prop_oneof![
        Just("+".to_string()),
        Just("-".to_string()),
        Just("*".to_string()),
        Just("/".to_string()),
        Just("%".to_string()),
        Just("<<".to_string()),
        Just(">>".to_string()),
        Just("<".to_string()),
        Just("<=".to_string()),
        Just(">".to_string()),
        Just(">=".to_string()),
        Just("==".to_string()),
        Just("!=".to_string()),
        Just("&".to_string()),
        Just("^".to_string()),
        Just("|".to_string()),
        Just("&&".to_string()),
        Just("||".to_string()),
    ];
    let un_op = prop_oneof![
        Just("+".to_string()),
        Just("-".to_string()),
        Just("~".to_string()),
        Just("!".to_string()),
    ];
    let assign_op = prop_oneof![
        Just("=".to_string()),
        Just("*=".to_string()),
        Just("/=".to_string()),
        Just("%=".to_string()),
        Just("+=".to_string()),
        Just("-=".to_string()),
        Just("<<=".to_string()),
        Just(">>=".to_string()),
        Just("&=".to_string()),
        Just("^=".to_string()),
        Just("|=".to_string()),
    ];

    let left = arithm_expr(depth - 1);
    let right = arithm_expr(depth - 1);

    prop_oneof![
        leaf,
        (left.clone(), bin_op, right.clone()).prop_map(|(l, op, r)| format!("({l} {op} {r})")),
        (un_op, left.clone()).prop_map(|(op, e)| format!("({op}{e})")),
        (left.clone(), right.clone(), arithm_expr(depth - 1))
            .prop_map(|(c, t, e)| format!("({c} ? {t} : {e})")),
        (pick_name(), assign_op, right).prop_map(|(n, op, e)| format!("({n} {op} {e})")),
    ]
    .boxed()
}

fn shell_word(depth: u32) -> BoxedStrategy<String> {
    let literal = pick_word();
    let single_quoted = pick_word().prop_map(|w| format!("'{w}'"));
    let double_quoted = pick_word().prop_map(|w| format!("\"{w}\""));
    let leaf = prop_oneof![literal, single_quoted, double_quoted].boxed();
    if depth == 0 {
        return leaf;
    }

    let parameter = prop_oneof![
        pick_name().prop_map(|n| format!("${n}")),
        pick_name().prop_map(|n| format!("${{{n}}}")),
        pick_name().prop_map(|n| format!("${{#{n}}}")),
        (pick_name(), pick_word()).prop_map(|(n, w)| format!("${{{n}:-{w}}}")),
        (pick_name(), pick_word()).prop_map(|(n, w)| format!("${{{n}:={w}}}")),
        (pick_name(), pick_word()).prop_map(|(n, w)| format!("${{{n}:?{w}}}")),
        (pick_name(), pick_word()).prop_map(|(n, w)| format!("${{{n}:+{w}}}")),
        (pick_name(), pick_word()).prop_map(|(n, w)| format!("${{{n}%{w}}}")),
        (pick_name(), pick_word()).prop_map(|(n, w)| format!("${{{n}%%{w}}}")),
        (pick_name(), pick_word()).prop_map(|(n, w)| format!("${{{n}#{w}}}")),
        (pick_name(), pick_word()).prop_map(|(n, w)| format!("${{{n}##{w}}}")),
        Just("$1".to_string()),
        Just("$@".to_string()),
        Just("$*".to_string()),
        Just("$?".to_string()),
        Just("$!".to_string()),
        Just("$-".to_string()),
        Just("$$".to_string()),
    ]
    .boxed();
    let arithmetic = arithm_expr(depth - 1).prop_map(|e| format!("$(({e}))"));
    let composite =
        (pick_word(), parameter.clone(), pick_word()).prop_map(|(a, p, b)| format!("{a}{p}{b}"));
    let quoted_composite = (pick_word(), parameter.clone(), pick_word())
        .prop_map(|(a, p, b)| format!("\"{a}{p}{b}\""));

    prop_oneof![leaf, parameter, arithmetic, composite, quoted_composite,].boxed()
}

fn non_heredoc_redir(depth: u32) -> BoxedStrategy<String> {
    let target = shell_word(depth);
    let io_number = prop_oneof![
        Just("".to_string()),
        Just("0".to_string()),
        Just("1".to_string()),
        Just("2".to_string()),
    ];
    let dup_target = prop_oneof![
        Just("-".to_string()),
        Just("0".to_string()),
        Just("1".to_string()),
        Just("2".to_string()),
    ];

    prop_oneof![
        (io_number.clone(), target.clone()).prop_map(|(n, t)| format!("{n}< {t}")),
        (io_number.clone(), target.clone()).prop_map(|(n, t)| format!("{n}> {t}")),
        (io_number.clone(), target.clone()).prop_map(|(n, t)| format!("{n}>> {t}")),
        (io_number.clone(), target.clone()).prop_map(|(n, t)| format!("{n}>| {t}")),
        (io_number.clone(), target).prop_map(|(n, t)| format!("{n}<> {t}")),
        (io_number.clone(), dup_target.clone()).prop_map(|(n, t)| format!("{n}<&{t}")),
        (io_number, dup_target).prop_map(|(n, t)| format!("{n}>&{t}")),
    ]
    .boxed()
}

/// A generated command: inline text plus optional heredoc bodies that must
/// appear after the next newline.
#[derive(Clone, Debug)]
struct GenCommand {
    /// The command text (everything on the command line).
    inline: String,
    /// Heredoc bodies to append after the newline.  Each entry is the full
    /// body including body lines and closing delimiter (no leading newline).
    heredoc_bodies: Vec<String>,
}

impl GenCommand {
    fn plain(s: String) -> Self {
        Self {
            inline: s,
            heredoc_bodies: Vec::new(),
        }
    }
}

fn heredoc_redir() -> BoxedStrategy<(String, String)> {
    let delim = prop_oneof![
        Just("EOF".to_string()),
        Just("TAG".to_string()),
        Just("DOC".to_string()),
        Just("END".to_string()),
    ];
    let delim_token = (delim.clone(), any::<bool>()).prop_map(|(d, quoted)| {
        if quoted {
            (format!("'{d}'"), d)
        } else {
            (d.clone(), d)
        }
    });
    let body_line = prop::collection::vec(pick_word(), 1..4).prop_map(|parts| parts.join(" "));

    (
        any::<bool>(),
        delim_token,
        prop::collection::vec(body_line, 1..3),
    )
        .prop_map(|(strip_tabs, (delim_token, delim_close), lines)| {
            let op = if strip_tabs { "<<-" } else { "<<" };
            let inline_part = format!("{op} {delim_token}");
            let mut body = String::new();
            for line in &lines {
                if strip_tabs {
                    body.push('\t');
                }
                body.push_str(line);
                body.push('\n');
            }
            body.push_str(&delim_close);
            (inline_part, body)
        })
        .boxed()
}

fn simple_command_no_heredoc(depth: u32) -> BoxedStrategy<GenCommand> {
    let assignment = (pick_name(), shell_word(depth)).prop_map(|(k, v)| format!("{k}={v}"));
    let command_name = pick_word();
    let arguments = prop::collection::vec(shell_word(depth), 0..4);
    let redirs = prop::collection::vec(non_heredoc_redir(depth), 0..2);

    (
        prop::collection::vec(assignment, 0..3),
        command_name,
        arguments,
        redirs,
    )
        .prop_map(|(assigns, name, args, redirs)| {
            let mut parts = Vec::new();
            parts.extend(assigns);
            parts.push(name);
            parts.extend(args);
            parts.extend(redirs);
            GenCommand::plain(parts.join(" "))
        })
        .boxed()
}

fn simple_command(depth: u32) -> BoxedStrategy<GenCommand> {
    let heredoc = prop::option::weighted(0.15, heredoc_redir());
    (simple_command_no_heredoc(depth), heredoc)
        .prop_map(|(mut cmd, heredoc)| {
            if let Some((inline_part, body)) = heredoc {
                cmd.inline.push(' ');
                cmd.inline.push_str(&inline_part);
                cmd.heredoc_bodies.push(body);
            }
            cmd
        })
        .boxed()
}

fn command_with_leaf(depth: u32, leaf: BoxedStrategy<GenCommand>) -> BoxedStrategy<GenCommand> {
    if depth == 0 {
        return leaf;
    }

    let compound_body = compound_list(depth - 1);

    let brace_group = compound_body
        .clone()
        .prop_map(|body| {
            let sb = sep_before_keyword(&body);
            GenCommand::plain(format!("{{ {body}{sb}}}"))
        })
        .boxed();
    let subshell = compound_body
        .clone()
        .prop_map(|body| GenCommand::plain(format!("( {body} )")))
        .boxed();

    let else_part = prop_oneof![
        Just(String::new()),
        compound_list(depth - 1).prop_map(|else_body| {
            let s = sep_before_keyword(&else_body);
            format!("\nelse {else_body}{s}")
        }),
        (
            compound_list(depth - 1),
            compound_list(depth - 1),
            prop::option::of(compound_list(depth - 1)),
        )
            .prop_map(|(cond, body, tail_else)| {
                let sc = sep_before_keyword(&cond);
                let sb = sep_before_keyword(&body);
                match tail_else {
                    Some(else_body) => {
                        let se = sep_before_keyword(&else_body);
                        format!("\nelif {cond}{sc}then {body}\nelse {else_body}{se}")
                    }
                    None => format!("\nelif {cond}{sc}then {body}{sb}"),
                }
            }),
    ];
    let if_clause = (
        compound_list(depth - 1),
        compound_list(depth - 1),
        else_part,
    )
        .prop_map(|(cond, then_body, else_part)| {
            let sc = sep_before_keyword(&cond);
            let sb = sep_before_keyword(&then_body);
            GenCommand::plain(format!("if {cond}{sc}then {then_body}{sb}{else_part}fi"))
        })
        .boxed();

    let for_clause = (
        pick_word(),
        prop::collection::vec(pick_word(), 0..4),
        compound_list(depth - 1),
    )
        .prop_map(|(name, words, body)| {
            let sb = sep_before_keyword(&body);
            if words.is_empty() {
                GenCommand::plain(format!("for {name}; do {body}{sb}done"))
            } else {
                GenCommand::plain(format!(
                    "for {name} in {}; do {body}{sb}done",
                    words.join(" ")
                ))
            }
        })
        .boxed();

    let loop_clause = (
        prop_oneof![Just("while".to_string()), Just("until".to_string())],
        compound_list(depth - 1),
        compound_list(depth - 1),
    )
        .prop_map(|(kw, cond, body)| {
            let sc = sep_before_keyword(&cond);
            let sb = sep_before_keyword(&body);
            GenCommand::plain(format!("{kw} {cond}{sc}do {body}{sb}done"))
        })
        .boxed();

    let case_item = (
        prop::collection::vec(pick_word(), 1..3),
        prop::option::of(compound_list(depth - 1)),
    )
        .prop_map(|(patterns, body)| match body {
            Some(body) => {
                let sb = sep_before_keyword(&body);
                format!("{} ) {body}{sb};;", patterns.join(" | "))
            }
            None => format!("{} ) ;;", patterns.join(" | ")),
        })
        .boxed();

    let case_clause = (
        shell_word(depth - 1),
        prop::collection::vec(case_item, 1..4),
    )
        .prop_map(|(word, items)| {
            GenCommand::plain(format!("case {word} in {} esac", items.join(" ")))
        })
        .boxed();

    prop_oneof![
        leaf,
        brace_group,
        subshell,
        if_clause,
        for_clause,
        loop_clause,
        case_clause,
    ]
    .boxed()
}

fn command_no_heredoc(depth: u32) -> BoxedStrategy<GenCommand> {
    command_with_leaf(depth, simple_command_no_heredoc(depth))
}

fn pipeline(depth: u32) -> BoxedStrategy<GenCommand> {
    // In POSIX, heredoc bodies start after the next newline on the command
    // line.  Multi-line text appearing after a `<< DELIM` token gets consumed
    // as heredoc body.  Structure the pipeline as: arbitrary commands (which
    // may be multi-line compounds), then optionally a heredoc-bearing simple
    // command, then single-line simple commands after that.
    (
        any::<bool>(),
        prop::collection::vec(command_no_heredoc(depth), 0..2),
        simple_command(depth),
        prop::collection::vec(simple_command(depth), 0..2),
    )
        .prop_map(|(bang, before, middle, after)| {
            let mut heredoc_bodies = Vec::new();
            let mut inlines: Vec<&str> = Vec::new();
            for cmd in &before {
                inlines.push(&cmd.inline);
            }
            inlines.push(&middle.inline);
            heredoc_bodies.extend(middle.heredoc_bodies.iter().cloned());
            for cmd in &after {
                inlines.push(&cmd.inline);
                heredoc_bodies.extend(cmd.heredoc_bodies.iter().cloned());
            }
            let mut s = inlines.join(" | ");
            if bang {
                s = format!("! {s}");
            }
            GenCommand {
                inline: s,
                heredoc_bodies,
            }
        })
        .boxed()
}

/// A pipeline whose simple-command leaves never carry top-level heredocs.
/// Compound command bodies may still contain heredocs (embedded in inline
/// text via `flatten_gen`), but no `heredoc_bodies` are surfaced.
fn pipeline_no_heredoc(depth: u32) -> BoxedStrategy<GenCommand> {
    (
        any::<bool>(),
        prop::collection::vec(command_no_heredoc(depth), 1..3),
    )
        .prop_map(|(bang, commands)| {
            let inlines: Vec<&str> = commands.iter().map(|c| c.inline.as_str()).collect();
            let mut s = inlines.join(" | ");
            if bang {
                s = format!("! {s}");
            }
            GenCommand::plain(s)
        })
        .boxed()
}

/// A pipeline built entirely from simple commands — always single-line.
fn simple_pipeline(depth: u32) -> BoxedStrategy<GenCommand> {
    (
        any::<bool>(),
        prop::collection::vec(simple_command(depth), 1..3),
    )
        .prop_map(|(bang, commands)| {
            let mut heredoc_bodies = Vec::new();
            for cmd in &commands {
                heredoc_bodies.extend(cmd.heredoc_bodies.iter().cloned());
            }
            let inlines: Vec<&str> = commands.iter().map(|c| c.inline.as_str()).collect();
            let mut s = inlines.join(" | ");
            if bang {
                s = format!("! {s}");
            }
            GenCommand {
                inline: s,
                heredoc_bodies,
            }
        })
        .boxed()
}

fn and_or_list(depth: u32) -> BoxedStrategy<GenCommand> {
    // Same POSIX heredoc constraint as pipeline: once a `<< DELIM` has been
    // seen, every subsequent piece on the same command line must be
    // single-line.  Structure: arbitrary pipelines (no heredocs) first, then
    // one pipeline that may carry heredocs, then single-line simple pipelines.
    let and_or_op = prop_oneof![Just("&&".to_string()), Just("||".to_string())];
    (
        pipeline_no_heredoc(depth),
        prop::collection::vec((and_or_op.clone(), pipeline_no_heredoc(depth)), 0..1),
        and_or_op.clone(),
        pipeline(depth),
        prop::collection::vec((and_or_op, simple_pipeline(depth)), 0..1),
        any::<bool>(),
    )
        .prop_map(|(first, mid, mid_op, heredoc_pl, after, use_heredoc)| {
            let mut inline = first.inline.clone();
            for (op, cmd) in &mid {
                inline.push(' ');
                inline.push_str(op);
                inline.push(' ');
                inline.push_str(&cmd.inline);
            }
            let mut heredoc_bodies = Vec::new();
            if use_heredoc {
                inline.push(' ');
                inline.push_str(&mid_op);
                inline.push(' ');
                inline.push_str(&heredoc_pl.inline);
                heredoc_bodies = heredoc_pl.heredoc_bodies;
            }
            for (op, cmd) in &after {
                inline.push(' ');
                inline.push_str(op);
                inline.push(' ');
                inline.push_str(&cmd.inline);
            }
            GenCommand {
                inline,
                heredoc_bodies,
            }
        })
        .boxed()
}

fn command_list(depth: u32) -> BoxedStrategy<GenCommand> {
    (and_or_list(depth), any::<bool>())
        .prop_map(|(mut cmd, ampersand)| {
            if ampersand {
                cmd.inline = format!("{} &", cmd.inline);
            }
            cmd
        })
        .boxed()
}

/// Flatten a `GenCommand` into a string, emitting heredoc bodies after the
/// command line (separated by a newline).  The result ends with `\n` when
/// heredoc bodies are present (the delimiter line must be on its own line).
fn flatten_gen(cmd: &GenCommand) -> String {
    let mut out = cmd.inline.clone();
    if !cmd.heredoc_bodies.is_empty() {
        out.push('\n');
        out.push_str(&cmd.heredoc_bodies.join("\n"));
        out.push('\n');
    }
    out
}

fn compound_list(depth: u32) -> BoxedStrategy<String> {
    prop::collection::vec(command_list(depth), 1..2)
        .prop_map(|items| {
            let mut out = String::new();
            for (i, item) in items.iter().enumerate() {
                let flat = flatten_gen(item);
                if i > 0 {
                    if out.ends_with('\n') {
                        // heredoc body already placed us on a new line
                    } else if out.ends_with('&') {
                        out.push(' ');
                    } else {
                        out.push_str(" ; ");
                    }
                }
                out.push_str(&flat);
            }
            out
        })
        .boxed()
}

/// Separator between a compound_list body and the following keyword (`}`,
/// `fi`, `done`, etc.).  After `&` we use `" "` (ampersand is already a
/// separator).  After `\n` (heredoc body) we use `"\n"` to stay on the
/// next line.  Otherwise `"; "`.
fn sep_before_keyword(list: &str) -> &str {
    if list.ends_with('\n') {
        ""
    } else if list.ends_with('&') {
        " "
    } else {
        "; "
    }
}

fn program_strategy() -> BoxedStrategy<String> {
    prop::collection::vec(command_list(2), 1..4)
        .prop_map(|items| {
            let mut script = String::new();
            for (i, item) in items.iter().enumerate() {
                let flat = flatten_gen(item);
                if i > 0 {
                    if script.ends_with('\n') {
                        // heredoc body already placed us on a new line
                    } else if script.ends_with('&') {
                        script.push('\n');
                    } else {
                        script.push_str(" ;\n");
                    }
                }
                script.push_str(&flat);
            }
            script.push('\n');
            script
        })
        .boxed()
}

fn parse_program(input: &str) -> Result<Program, ParseError> {
    let mut parser = Parser::from_string(input);
    parser.parse_program()
}

fn normalize_program(program: &Program) -> Program {
    Program::with_range(
        program.body().iter().map(normalize_command_list).collect(),
        Range::default(),
    )
}

fn normalize_command_list(cl: &CommandList) -> CommandList {
    CommandList::new(
        normalize_and_or(cl.and_or_list()),
        cl.ampersand(),
        Range::default(),
    )
}

fn normalize_and_or(aol: &AndOrList) -> AndOrList {
    match aol {
        AndOrList::Pipeline(pipeline) => AndOrList::Pipeline(Pipeline::new(
            pipeline.commands().iter().map(normalize_command).collect(),
            pipeline.bang(),
            Range::default(),
        )),
        AndOrList::BinOp(binary) => AndOrList::BinOp(AndOrBinary::with_range(
            binary.op(),
            normalize_and_or(binary.left()),
            normalize_and_or(binary.right()),
            Range::default(),
        )),
    }
}

fn normalize_command(command: &Command) -> Command {
    match command {
        Command::Simple(simple) => Command::Simple(SimpleCommand::with_range(
            simple.name().map(normalize_word),
            simple.arguments().iter().map(normalize_word).collect(),
            simple
                .io_redirects()
                .iter()
                .map(normalize_redirect)
                .collect(),
            simple
                .assignments()
                .iter()
                .map(normalize_assignment)
                .collect(),
            Range::default(),
        )),
        Command::BraceGroup(group) => Command::BraceGroup(CompoundCommand::with_range(
            group.body().iter().map(normalize_command_list).collect(),
            group
                .io_redirects()
                .iter()
                .map(normalize_redirect)
                .collect(),
            Range::default(),
        )),
        Command::Subshell(group) => Command::Subshell(CompoundCommand::with_range(
            group.body().iter().map(normalize_command_list).collect(),
            group
                .io_redirects()
                .iter()
                .map(normalize_redirect)
                .collect(),
            Range::default(),
        )),
        Command::If(if_clause) => normalize_if_clause(if_clause),
        Command::For(for_clause) => Command::For(ForClause::with_range_and_redirects(
            for_clause.name(),
            for_clause.has_in(),
            for_clause.word_list().iter().map(normalize_word).collect(),
            for_clause
                .body()
                .iter()
                .map(normalize_command_list)
                .collect(),
            for_clause
                .io_redirects()
                .iter()
                .map(normalize_redirect)
                .collect(),
            Range::default(),
        )),
        Command::Loop(loop_clause) => Command::Loop(LoopClause::with_range_and_redirects(
            loop_clause.loop_type(),
            loop_clause
                .condition()
                .iter()
                .map(normalize_command_list)
                .collect(),
            loop_clause
                .body()
                .iter()
                .map(normalize_command_list)
                .collect(),
            loop_clause
                .io_redirects()
                .iter()
                .map(normalize_redirect)
                .collect(),
            Range::default(),
        )),
        Command::Case(case_clause) => Command::Case(CaseClause::with_range_and_redirects(
            normalize_word(case_clause.word()),
            case_clause
                .items()
                .iter()
                .map(normalize_case_item)
                .collect(),
            case_clause
                .io_redirects()
                .iter()
                .map(normalize_redirect)
                .collect(),
            Range::default(),
        )),
        Command::FunctionDef(function_definition) => {
            Command::FunctionDef(FunctionDefinition::with_range(
                function_definition.name(),
                normalize_command(function_definition.body()),
                function_definition
                    .io_redirects()
                    .iter()
                    .map(normalize_redirect)
                    .collect(),
                Range::default(),
            ))
        }
    }
}

fn normalize_assignment(assignment: &Assignment) -> Assignment {
    Assignment::new(
        assignment.name(),
        normalize_word(assignment.value()),
        Range::default(),
    )
}

fn normalize_case_item(item: &CaseItem) -> CaseItem {
    CaseItem::with_range(
        item.patterns().iter().map(normalize_word).collect(),
        item.body().iter().map(normalize_command_list).collect(),
        Range::default(),
    )
}

fn normalize_if_clause(if_clause: &IfClause) -> Command {
    Command::If(IfClause::with_range_and_redirects(
        if_clause
            .condition()
            .iter()
            .map(normalize_command_list)
            .collect(),
        if_clause
            .body()
            .iter()
            .map(normalize_command_list)
            .collect(),
        if_clause
            .else_part()
            .map(|else_part| Box::new(normalize_else_part(else_part))),
        if_clause
            .io_redirects()
            .iter()
            .map(normalize_redirect)
            .collect(),
        Range::default(),
    ))
}

fn normalize_else_part(else_part: &ElsePart) -> ElsePart {
    match else_part {
        ElsePart::Elif(elif) => match normalize_if_clause(elif) {
            Command::If(if_clause) => ElsePart::Elif(if_clause),
            other => panic!("expected if clause, got {other:?}"),
        },
        ElsePart::Else(body) => ElsePart::Else(ElseClause::with_range(
            body.body().iter().map(normalize_command_list).collect(),
            Range::default(),
        )),
    }
}

fn normalize_redirect(redirect: &IoRedirect) -> IoRedirect {
    let name = if matches!(redirect.op(), IoRedirectOp::DLess | IoRedirectOp::DLessDash) {
        Word::string("", false, false, None, Range::default())
    } else {
        normalize_word(redirect.name())
    };

    IoRedirect::with_range(
        redirect.io_number(),
        redirect.op(),
        name,
        redirect
            .here_document()
            .iter()
            .map(normalize_word)
            .collect(),
        redirect.here_document_expand(),
        Range::default(),
    )
}

fn normalize_word(word: &Word) -> Word {
    match word {
        Word::String(string) => Word::string(
            string.value(),
            string.single_quoted(),
            string.split_fields(),
            None,
            Range::default(),
        ),
        Word::Parameter(parameter) => Word::parameter(
            parameter.name(),
            parameter.op(),
            parameter.colon(),
            parameter.arg().map(|arg| Box::new(normalize_word(arg))),
            Default::default(),
            Default::default(),
            Range::default(),
        ),
        Word::Command(command) => Word::command(
            normalize_program(command.program()),
            None,
            false,
            Range::default(),
        ),
        Word::Arithmetic(arithm) => {
            Word::arithmetic(normalize_arithm(arithm.body()), Range::default())
        }
        Word::List(list) => Word::list(
            list.children().iter().map(normalize_word).collect(),
            list.double_quoted(),
            Range::default(),
        ),
    }
}

fn normalize_arithm(expr: &ArithmExpr) -> ArithmExpr {
    match expr {
        ArithmExpr::Literal(literal) => ArithmExpr::literal(literal.value(), Range::default()),
        ArithmExpr::Variable(variable) => ArithmExpr::variable(variable.name(), Range::default()),
        ArithmExpr::Raw(raw) => ArithmExpr::raw(raw.expr(), Range::default()),
        ArithmExpr::BinOp(binary) => ArithmExpr::bin_op(
            binary.op(),
            normalize_arithm(binary.left()),
            normalize_arithm(binary.right()),
            Range::default(),
        ),
        ArithmExpr::UnOp(unary) => ArithmExpr::un_op(
            unary.op(),
            normalize_arithm(unary.operand()),
            Range::default(),
        ),
        ArithmExpr::Cond(cond) => ArithmExpr::cond(
            normalize_arithm(cond.cond()),
            normalize_arithm(cond.then_branch()),
            normalize_arithm(cond.else_branch()),
            Range::default(),
        ),
        ArithmExpr::Assign(assign) => ArithmExpr::assign(
            assign.name(),
            assign.op(),
            normalize_arithm(assign.value()),
            Range::default(),
        ),
    }
}

proptest! {
    #![proptest_config(ProptestConfig {
        cases: 128,
        failure_persistence: Some(Box::new(proptest::test_runner::FileFailurePersistence::WithSource("proptest-regressions"))),
        .. ProptestConfig::default()
    })]

    #[test]
    fn parses_generated_posix_programs(script in program_strategy()) {
        let first = parse_program(&script)
            .unwrap_or_else(|e| panic!("generated script did not parse: {e}\n{script}"));
        let second = parse_program(&script)
            .unwrap_or_else(|e| panic!("re-parse of script failed: {e}\n{script}"));

        let first_norm = normalize_program(&first);
        let second_norm = normalize_program(&second);

        prop_assert_eq!(&first_norm, &second_norm);
        let canonical_script = first.to_canonical();
        let canonical_parsed = match parse_program(&canonical_script) {
            Ok(p) => p,
            Err(e) => {
                let _ = std::fs::write("proptest-failing-script.sh", &script);
                panic!("canonical parse failed: {e}\noriginal:\n{script}\ncanonical:\n{canonical_script}\nWrote failing script to proptest-failing-script.sh");
            }
        };
        let canonical_norm = normalize_program(&canonical_parsed);
        if first_norm != canonical_norm {
            let _ = std::fs::write("proptest-failing-script.sh", &script);
        }
        prop_assert_eq!(&first_norm, &canonical_norm,
            "round-trip mismatch.\noriginal:\n{}\ncanonical:\n{}\nWrote failing script to proptest-failing-script.sh", script, canonical_script);
    }
}