Recursively change an expression

Hi.

I think that I need some help.

I have an enum to represent an expression (think "a * (b + 2)"), e.g

enum Expr {
     Alias(Box<Expr>, String),
     Column(String),
     BinaryExpr {
        left: Box<Expr>,
        op: Operator,
        right: Box<Expr>,
    },
    ...
}

you can think of it as a SQL expression, that is composed by different operators.

I am writing functions that modifies the expression in different ways. One example is when I want to replace a column by an expression coming from a map:

/// recursively relaces columns in an expression by expressions from projection.
pub fn replace(expr: Expr, projection: HashMap<String, Expr>) -> Result<Expr> {
    match expr {
        Expr::Column(name) => {
            match projection.get(&name) {
                Some(expr) => Ok(expr.clone()),
                None => Err("Column name does not exist")),
            }
        },
        _ => /// apply replace on every expression in `expr` and return a copy of `expr` with its expressions replaced
    }
}

In this function, Expr::Column is the only enum that needs special treatment: all others just need their own expressions replaced. I would like to avoid writing all the other arms with the same conceptual operation (described as a comment above). However, I have not been able to achieve this.

I can write a function fn expressions(expr: Expr) -> Result<Vec<Expr>> to iterate over all expressions (e.g. for the binary operator), but I can't find a way to programmatically pick the constructor for the same type of expr and correctly pass arguments to it (without writing all branches).

I am trying to avoid writing all branches because it is a pain and code duplication. Is anyone aware of an idiom to achieve this?

Usually this is done by abstracting traversal into a Trait, which defines method for visiting substructures. I don't have resource to fully explain the pattern, but I can drop a link to the source code of the thing in rust-analyzer:

1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.