Folding an AST: separating traversal from action

Use one recursive traversal to analyse an expression tree in several ways. The tokenizer, parser and operation dispatch are supplied:

pub fn analyse(src: String, ops: Vec<String>) -> Vec<String>

Repair the recursive enum, implement the shared borrowing fold, and use it for node count, depth, variable collection, constant folding and rendering.

Accepted expressions

expr   := term (('+' | '-') term)*
term   := factor ('*' factor)*
factor := INT | IDENT | '(' expr ')'

INT is one or more ASCII decimal digits with a value at most i64::MAX. Leading zeros are allowed. IDENT matches [A-Za-z_][A-Za-z0-9_]* and is case-sensitive. Whitespace recognized by Rust's char::is_whitespace may separate tokens. Non-ASCII letters are not valid identifiers.

Multiplication binds more tightly than addition and subtraction. Operators at the same precedence associate to the left. Unary signs are not supported: use 0 - 3, not -3, to express a negative value. Empty input, missing operands, extra tokens, unsupported characters and out-of-range literals produce parse error. Inputs are small enough for recursive parsing, traversal and tree destruction to fit on the stack.

Output rules

Process ops in order, including duplicates. Recognized names are exact and lowercase; unknown names produce "unknown <op>" with the original name. If parsing fails, return only ["parse error"], even when ops is empty. A valid expression with no requested operations returns an empty vector.

Every operation starts from the original parsed tree. Asking for fold first must not change a later count, depth or variable list.

For 1 + 2 * 3 with ops = ["count", "depth", "fold", "free"], return ["count 5", "depth 3", "fold 7", "free -"].

Fold constants from the leaves upward

First simplify both children. If both resulting children are literals, evaluate their operator with checked i64 arithmetic. On success, replace the binary node with the result. On overflow, retain that operator and its already-simplified children. Do not wrap or panic on overflow.

Apply no other algebraic rules: x * 0 stays (x * 0), and x - x stays (x - x). For (1 + 2) * x - x, render ((3 * x) - x). For 9223372036854775807 + (2 - 1), render (9223372036854775807 + 1): the inner subtraction folds even though the outer addition overflows.

Render literals in decimal without leading zeros and variables unchanged. Render every binary node as (LEFT OP RIGHT), with one space on each side of the operator. Negative folded literals may appear even though unary negative literals are not accepted by the input parser.

Put indirection in the recursive enum

The starter's Bin(Op, Expr, Expr) embeds children directly inside an Expr. That recursive layout has no finite size, so it produces E0072. Change both children to Box<Expr>. A box has a known pointer size and owns a separately allocated child; the supplied parser already constructs children this way.

Share the traversal

Keep this borrowing interface:

fn fold<T, L, V, B>(e: &Expr, lit: &L, var: &V, bin: &B) -> T
where
    L: Fn(i64) -> T,
    V: Fn(&str) -> T,
    B: Fn(Op, T, T) -> T,

Match the three variants. Call lit for a literal and var for a name. For a binary node, recursively fold the left child and then the right child, and pass both results and the operator to bin.

Each analysis chooses its result type and three handlers. Counts and depths use usize; variable collection combines vectors of names; constant folding builds a new Expr; rendering builds a String. Sort and deduplicate the collected names once at the end.

Borrowing &Expr keeps the original available for every analysis. Passing handlers by reference lets recursive calls reuse them without moving them. An owned traversal is also a valid design when you want to consume or rebuild a tree; moving a value out of an owned Box is allowed. Borrowing simply fits this interface's repeated analyses.

One shared traversal is sometimes called a tree fold or catamorphism. It keeps recursion separate from each operation's calculation. A visitor trait is another design, particularly for stateful traversal or pruning. In either design, an exhaustive match needs updating when a variant is added; whether each analysis also needs changes depends on the handler interface and any defaults or catch-all arms.

Your solution must compile, use the shared fold, match the exact output strings and pass Clippy with warnings treated as errors.