arena_example.rs

#[derive(Debug)]
enum ArenaExpr<'a> {
    Add(&'a ArenaExpr<'a>, &'a ArenaExpr<'a>),
    Sub(&'a ArenaExpr<'a>, &'a ArenaExpr<'a>),
    Literal(i64),
}

fn main() {
    use ArenaExpr::*;

    let arena = typed_arena::Arena::new();
    let v1 = arena.alloc(Literal(1));
    let v2 = arena.alloc(Literal(2));
    let v3 = arena.alloc(Literal(3));
    let v4 = arena.alloc(Literal(4));
    let add1 = arena.alloc(Add(v1, v2));
    let add2 = arena.alloc(Add(v3, v4));
    let sub = arena.alloc(Sub(add1, add2));

    println!("result = {}", eval_expr(sub));
}

enum State<'a> {
    PreVisit(&'a ArenaExpr<'a>),
    PostVisit(&'a ArenaExpr<'a>),
}

fn eval_expr(expr: &ArenaExpr) -> i64 {
    use ArenaExpr::*;
    visit_expr(expr, |e, vals| {
        match e {
            Add(..) => {
                let lhs = vals.pop().unwrap();
                let rhs = vals.pop().unwrap();
                lhs + rhs
            }
            Sub(..) => {
                let lhs = vals.pop().unwrap();
                let rhs = vals.pop().unwrap();
                lhs - rhs
            }
            Literal(val) => {
                *val
            }
        }
    })
}

fn visit_expr<T>(
    expr: &ArenaExpr, 
    mut post: impl FnMut(&ArenaExpr, &mut Vec<T>) -> T,
) -> T {
    use State::*;
    use ArenaExpr::*;

    let mut vals = vec![];
    let mut todo = vec![State::PreVisit(expr)];

    while let Some(item) = todo.pop() {
        match item {
            PreVisit(e @ Add(a, b)) |
            PreVisit(e @ Sub(a, b)) => {
                todo.push(PostVisit(e));
                todo.push(PreVisit(a));
                todo.push(PreVisit(b));
            }
            PreVisit(e @ Literal(_)) => {
                todo.push(PostVisit(e));
            }
            PostVisit(e) => {
                let val = post(e, &mut vals);
                vals.push(val);
            }
        }
    }
    vals.pop().unwrap()
}