Module traversal 

Tree traversal utilities for SQL expression ASTs.

This module provides read-only traversal, search, and transformation utilities for the Expression tree produced by the parser. Because Rust’s ownership model does not allow parent pointers inside the AST, parent information is tracked externally via TreeContext (built on demand).

Traversal

Two iterator types are provided:

• DfsIter – depth-first (pre-order) traversal using a stack. Visits a node before its children. Good for top-down analysis and early termination.
• BfsIter – breadth-first (level-order) traversal using a queue. Visits all nodes at depth N before any node at depth N+1. Good for level-aware analysis.

Both are available through the ExpressionWalk trait methods dfs and bfs.

Searching

The ExpressionWalk trait also provides convenience methods for finding expressions: find, find_all, contains, and count. Common predicates are available as free functions: is_column, is_literal, is_function, is_aggregate, is_window_function, is_subquery, and is_select.

Transformation

The transform and transform_map functions perform bottom-up (post-order) tree rewrites, delegating to transform_recursive. The ExpressionWalk::transform_owned method provides the same capability as an owned method on Expression.

Based on traversal patterns from sqlglot/expressions.py.

Structs

BfsIter

Level-order breadth-first iterator over an expression tree.

DfsIter

Pre-order depth-first iterator over an expression tree.

ParentInfo

Information about a node’s parent relationship

TreeContext

External parent-tracking context for an expression tree.

Traits

ExpressionWalk

Extension trait that adds traversal and search methods to Expression.

Functions

contains_aggregate

Returns true if the expression tree contains any aggregate function calls.

contains_subquery

Returns true if the expression tree contains any subquery nodes.

contains_window_function

Returns true if the expression tree contains any window function calls.

find_ancestor

Find the first ancestor of target matching predicate, walking from parent toward root.

find_parent

Find the parent of target within the tree rooted at root.

get_columns

Collects all column references (Expression::Column) from the expression tree.

get_tables

Collects all table references (Expression::Table) from the expression tree.

is_aggregate

Returns true if expr is an aggregate function (Expression::AggregateFunction).

is_column

Returns true if expr is a column reference (Expression::Column).

is_function

Returns true if expr is a function call (regular or aggregate).

is_literal

Returns true if expr is a literal value (number, string, boolean, or NULL).

is_select

Returns true if expr is a SELECT statement (Expression::Select).

is_subquery

Returns true if expr is a subquery (Expression::Subquery).

is_window_function

Returns true if expr is a window function (Expression::WindowFunction).

transform

Transforms an expression tree bottom-up, with optional node removal.

transform_map

Transforms an expression tree bottom-up without node removal.

Type Aliases

NodeId

Unique identifier for expression nodes during traversal