Function memoize_expr

src/expr/src/linear.rs:1443–1479

TODO: move this elsewhere? Recursively memoize parts of `expr`, storing those parts in `memoized_parts`. A part of `expr` that is memoized is replaced by a reference to column `(input_arity + pos)`, where `pos` is the position of the memoized part in `memoized_parts`, and `input_arity` is the arity of the input that `expr` refers to.

(
    expr: &mut E,
    memoized_parts: &mut Vec<E>,
    input_arity: usize,
)

/// `memoized_parts`, and `input_arity` is the arity of the input that `expr`
/// refers to.
pub fn memoize_expr<E: OptimizableExpr>(
    expr: &mut E,
    memoized_parts: &mut Vec<E>,
    input_arity: usize,
) {
    expr.visit_mut_pre_post(&mut |e| e.eager_children(), &mut |e| {
        if E::is_literal(e) {
            // Literals do not need to be memoized.
            return;
        }
        if let Some(col) = e.as_column_mut() {
            // Column references do not need to be memoized, but may need to be
            // updated if they reference a column reference themselves.
            if *col > input_arity {
                if let Some(col2) = memoized_parts[*col - input_arity].as_column() {
                    // Update the column index in place, preserving any name information.
                    *col = col2;
                }
            }
            return;
        }
        // TODO: OOO (Optimizer Optimization Opportunity):
        // we are quadratic in expression size because of this .iter().position
        if let Some(position) = memoized_parts.iter().position(|e2| e2 == e) {
            // Any complex expression that already exists as a prior column can
            // be replaced by a reference to that column.
            *e = E::column(input_arity + position);
        } else {
            // A complex expression that does not exist should be memoized, and
            // replaced by a reference to the column.
            memoized_parts.push(std::mem::replace(
                e,
                E::column(input_arity + memoized_parts.len()),
            ));
        }
    });
}

pub mod util {
    use std::collections::BTreeMap;