Create Functor Ast to control interleaving

[jfecher]

Problem

Implementing #4953 is a difficult task since it requires fundamentally changing the compiler's architecture.

Most notably, passes can accidentally break the lock-step constraint by recursing on an expression themselves as in:

fn type_check(expr: Expr) {
    match expr {
        Expr::Add(a, b) => {
            let a_type = type_check(a); // breaks lock-step! 
            let b_type = type_check(b); // we're now several nodes out of sync with other passes!
        }
        ...
    }
}

In this case, breaking lock step in the type checker would mean it is type checking nodes which haven't been name resolved yet, and would likely error as a result.

Happy Case

We can add a Functor version of the Ast with all recursive Expression/Statement nodes replaced with a generic T argument. This is similar to the technique used in "recursion schemes" for reusable recursive helper functions, although Rust does not have the expressitivity to represent the normal Ast as a Fixed version of the Functor version (if this means nothing to you, feel free to ignore this remark). For us, this just means it needs to be a separate enum from the normal Ast.

Project Impact

None

Impact Context

No response

Workaround

None

Workaround Description

No response

Additional Context

No response

Would you like to submit a PR for this Issue?

None

Support Needs

No response

[jfecher]

Instead of trying to interleave our existing passes, it was easier to write an elaborator to interleave them from scratch instead (adapting existing code where possible).