Enum TransformFrame 

pub enum TransformFrame<'a, Input, Output, ExitContext> {
    Enter(&'a Input),
    Exit(ExitContext),
    Leaf(Output),
}

A frame in the traversal work stack for tree transformations.

Used in manual iterative traversals that consume input nodes and produce transformed output nodes. This enum provides the common structure while allowing implementations to define custom exit variants for operation-specific context (e.g., which binary operator triggered the exit).

The pattern avoids stack overflow on deeply nested trees (50k+ nodes) by using explicit work and result stacks instead of recursion.

Type Parameters

• Input - The input node type being consumed during traversal
• Output - The result type being built on the result stack
• ExitContext - Custom enum carrying operation-specific exit state

Traversal Pattern

use llkv_plan::TransformFrame;

// Define operation-specific exit variants
enum ScalarExitContext {
    BinaryOp { op: BinaryOp },
    UnaryMinus,
}

type ScalarTransformFrame<'a> = TransformFrame<'a, SqlExpr, OutputExpr, ScalarExitContext>;

fn transform_scalar(expr: &SqlExpr) -> Result<OutputExpr> {
    let mut work_stack: Vec<ScalarTransformFrame> = vec![ScalarTransformFrame::Enter(expr)];
    let mut result_stack: Vec<OutputExpr> = Vec::new();

    while let Some(frame) = work_stack.pop() {
        match frame {
            ScalarTransformFrame::Enter(node) => {
                // Decompose node, push exit frame, then push children
            }
            ScalarTransformFrame::Exit(ScalarExitContext::BinaryOp { op }) => {
                // Pop children from result_stack, combine, push result
            }
            ScalarTransformFrame::Exit(ScalarExitContext::UnaryMinus) => {
                // Pop single child, transform, push result
            }
            ScalarTransformFrame::Leaf(output) => {
                result_stack.push(output);
            }
        }
    }

    Ok(result_stack.pop().unwrap())
}

See Also

Concrete implementations using this pattern:

• llkv-sql/src/sql_engine.rs: translate_condition_with_context, translate_scalar
• llkv-executor/src/translation/expression.rs: translate_predicate_with

Variants

Enter(&'a Input)

Begin visiting an input node (descend to children).

Exit(ExitContext)

Complete processing of a node (combine child results).

The ExitContext carries operation-specific state needed to combine child results into the parent node’s result. For example, in arithmetic expression evaluation, this might carry which operator to apply.

Leaf(Output)

A leaf node that has been fully transformed to output.

Used when a node can be immediately converted without further traversal (e.g., literals, pre-resolved identifiers).