Trait TreeNode

pub trait TreeNode: Sized {
    // Required methods
    fn apply_children<'n, F: FnMut(&'n Self) -> Result<TreeNodeRecursion>>(
        &'n self,
        f: F,
    ) -> Result<TreeNodeRecursion>;
    fn map_children<F: FnMut(Self) -> Result<Transformed<Self>>>(
        self,
        f: F,
    ) -> Result<Transformed<Self>>;

    // Provided methods
    fn visit<'n, V: TreeNodeVisitor<'n, Node = Self>>(
        &'n self,
        visitor: &mut V,
    ) -> Result<TreeNodeRecursion> { ... }
    fn rewrite<R: TreeNodeRewriter<Node = Self>>(
        self,
        rewriter: &mut R,
    ) -> Result<Transformed<Self>> { ... }
    fn apply<'n, F: FnMut(&'n Self) -> Result<TreeNodeRecursion>>(
        &'n self,
        f: F,
    ) -> Result<TreeNodeRecursion> { ... }
    fn transform<F: FnMut(Self) -> Result<Transformed<Self>>>(
        self,
        f: F,
    ) -> Result<Transformed<Self>> { ... }
    fn transform_down<F: FnMut(Self) -> Result<Transformed<Self>>>(
        self,
        f: F,
    ) -> Result<Transformed<Self>> { ... }
    fn transform_up<F: FnMut(Self) -> Result<Transformed<Self>>>(
        self,
        f: F,
    ) -> Result<Transformed<Self>> { ... }
    fn transform_down_up<FD: FnMut(Self) -> Result<Transformed<Self>>, FU: FnMut(Self) -> Result<Transformed<Self>>>(
        self,
        f_down: FD,
        f_up: FU,
    ) -> Result<Transformed<Self>> { ... }
    fn exists<F: FnMut(&Self) -> Result<bool>>(&self, f: F) -> Result<bool> { ... }
}

API for inspecting and rewriting tree data structures.

The TreeNode API is used to express algorithms separately from traversing the structure of TreeNodes, avoiding substantial code duplication.

This trait is implemented for plans (ExecutionPlan, LogicalPlan) and expression trees (PhysicalExpr, Expr) as well as Plan+Payload combinations PlanContext and ExprContext.

Overview

There are three categories of TreeNode APIs:

1. “Inspecting” APIs to traverse a tree of &TreeNodes: apply, visit, exists.

2. “Transforming” APIs that traverse and consume a tree of TreeNodes producing possibly changed TreeNodes: transform, transform_up, transform_down, transform_down_up, and rewrite.

3. Internal APIs used to implement the TreeNode API: apply_children, and map_children.

Traversal Order	Inspecting	Transforming
top-down	apply, exists	transform_down
bottom-up		transform , transform_up
combined with separate f_down and f_up closures		transform_down_up
combined with f_down() and f_up() in an object	visit	rewrite

Note:while there is currently no in-place mutation API that uses &mut TreeNode, the transforming APIs are efficient and optimized to avoid cloning.

Terminology

The following terms are used in this trait

• f_down: Invoked before any children of the current node are visited.
• f_up: Invoked after all children of the current node are visited.
• f: closure that is applied to the current node.
• map_*: applies a transformation to rewrite owned nodes
• apply_*: invokes a function on borrowed nodes
• transform_: applies a transformation to rewrite owned nodes

Required Methods

fn apply_children<'n, F: FnMut(&'n Self) -> Result<TreeNodeRecursion>>( &'n self, f: F, ) -> Result<TreeNodeRecursion>

Low-level API used to implement other APIs.

If you want to implement the TreeNode trait for your own type, you should implement this method and Self::map_children.

Users should use one of the higher level APIs described on Self.

Description: Apply f to inspect node’s children (but not the node itself).

fn map_children<F: FnMut(Self) -> Result<Transformed<Self>>>( self, f: F, ) -> Result<Transformed<Self>>

Low-level API used to implement other APIs.

If you want to implement the TreeNode trait for your own type, you should implement this method and Self::apply_children.

Users should use one of the higher level APIs described on Self.

Description: Apply f to rewrite the node’s children (but not the node itself).

Provided Methods

fn visit<'n, V: TreeNodeVisitor<'n, Node = Self>>( &'n self, visitor: &mut V, ) -> Result<TreeNodeRecursion>

Visit the tree node with a TreeNodeVisitor, performing a depth-first walk of the node and its children.

TreeNodeVisitor::f_down() is called in top-down order (before children are visited), TreeNodeVisitor::f_up() is called in bottom-up order (after children are visited).

Return Value

Specifies how the tree walk ended. See TreeNodeRecursion for details.

See Also:

• Self::apply for inspecting nodes with a closure
• Self::rewrite to rewrite owned TreeNodes

Example

Consider the following tree structure:

ParentNode
   left: ChildNode1
   right: ChildNode2

Here, the nodes would be visited using the following order:

TreeNodeVisitor::f_down(ParentNode)
TreeNodeVisitor::f_down(ChildNode1)
TreeNodeVisitor::f_up(ChildNode1)
TreeNodeVisitor::f_down(ChildNode2)
TreeNodeVisitor::f_up(ChildNode2)
TreeNodeVisitor::f_up(ParentNode)

fn rewrite<R: TreeNodeRewriter<Node = Self>>( self, rewriter: &mut R, ) -> Result<Transformed<Self>>

Rewrite the tree node with a TreeNodeRewriter, performing a depth-first walk of the node and its children.

TreeNodeRewriter::f_down() is called in top-down order (before children are visited), TreeNodeRewriter::f_up() is called in bottom-up order (after children are visited).

Note: If using the default TreeNodeRewriter::f_up or TreeNodeRewriter::f_down that do nothing, consider using Self::transform_down instead.

Return Value

The returns value specifies how the tree walk should proceed. See TreeNodeRecursion for details. If an Err is returned, the recursion stops immediately.

See Also

• Self::visit for inspecting (without modification) TreeNodes
• Self::transform_down_up for a top-down (pre-order) traversal.
• Self::transform_down for a top-down (pre-order) traversal.
• Self::transform_up for a bottom-up (post-order) traversal.

Example

Consider the following tree structure:

ParentNode
   left: ChildNode1
   right: ChildNode2

Here, the nodes would be visited using the following order:

TreeNodeRewriter::f_down(ParentNode)
TreeNodeRewriter::f_down(ChildNode1)
TreeNodeRewriter::f_up(ChildNode1)
TreeNodeRewriter::f_down(ChildNode2)
TreeNodeRewriter::f_up(ChildNode2)
TreeNodeRewriter::f_up(ParentNode)

fn apply<'n, F: FnMut(&'n Self) -> Result<TreeNodeRecursion>>( &'n self, f: F, ) -> Result<TreeNodeRecursion>

Applies f to the node then each of its children, recursively (a top-down, pre-order traversal).

The return TreeNodeRecursion controls the recursion and can cause an early return.

See Also

• Self::transform_down for the equivalent transformation API.
• Self::visit for both top-down and bottom up traversal.

fn transform<F: FnMut(Self) -> Result<Transformed<Self>>>( self, f: F, ) -> Result<Transformed<Self>>

Recursively rewrite the node’s children and then the node using f (a bottom-up post-order traversal).

A synonym of Self::transform_up.

fn transform_down<F: FnMut(Self) -> Result<Transformed<Self>>>( self, f: F, ) -> Result<Transformed<Self>>

Recursively rewrite the tree using f in a top-down (pre-order) fashion.

f is applied to the node first, and then its children.

See Also

• Self::transform_up for a bottom-up (post-order) traversal.
• Self::transform_down_up for a combined traversal with closures
• Self::rewrite for a combined traversal with a visitor

fn transform_up<F: FnMut(Self) -> Result<Transformed<Self>>>( self, f: F, ) -> Result<Transformed<Self>>

Recursively rewrite the node using f in a bottom-up (post-order) fashion.

f is applied to the node’s children first, and then to the node itself.

See Also

• Self::transform_down top-down (pre-order) traversal.
• Self::transform_down_up for a combined traversal with closures
• Self::rewrite for a combined traversal with a visitor

fn transform_down_up<FD: FnMut(Self) -> Result<Transformed<Self>>, FU: FnMut(Self) -> Result<Transformed<Self>>>( self, f_down: FD, f_up: FU, ) -> Result<Transformed<Self>>

Transforms the node using f_down while traversing the tree top-down (pre-order), and using f_up while traversing the tree bottom-up (post-order).

The method behaves the same as calling Self::transform_down followed by Self::transform_up on the same node. Use this method if you want to start the f_up process right where f_down jumps. This can make the whole process faster by reducing the number of f_up steps.

See Also

• Self::transform_up for a bottom-up (post-order) traversal.
• Self::transform_down for a top-down (pre-order) traversal.
• Self::rewrite for a combined traversal with a visitor

Example

Consider the following tree structure:

ParentNode
   left: ChildNode1
   right: ChildNode2

The nodes are visited using the following order:

f_down(ParentNode)
f_down(ChildNode1)
f_up(ChildNode1)
f_down(ChildNode2)
f_up(ChildNode2)
f_up(ParentNode)

See TreeNodeRecursion for more details on controlling the traversal.

If f_down or f_up returns Err, the recursion stops immediately.

Example:

                                              |   +---+
                                              |   | J |
                                              |   +---+
                                              |     |
                                              |   +---+
                 TreeNodeRecursion::Continue  |   | I |
                                              |   +---+
                                              |     |
                                              |   +---+
                                             \|/  | F |
                                              '   +---+
                                                 /     \ ___________________
                 When `f_down` is           +---+                           \ ---+
                 applied on node "E",       | E |                            | G |
                 it returns with "Jump".    +---+                            +---+
                                              |                                |
                                            +---+                            +---+
                                            | C |                            | H |
                                            +---+                            +---+
                                            /   \
                                       +---+     +---+
                                       | B |     | D |
                                       +---+     +---+
                                                   |
                                                 +---+
                                                 | A |
                                                 +---+

Instead of starting from leaf nodes, `f_up` starts from the node "E".
                                                  +---+
                                              |   | J |
                                              |   +---+
                                              |     |
                                              |   +---+
                                              |   | I |
                                              |   +---+
                                              |     |
                                             /    +---+
                                           /      | F |
                                         /        +---+
                                       /         /     \ ______________________
                                      |     +---+   .                          \ ---+
                                      |     | E |  /|\  After `f_down` jumps    | G |
                                      |     +---+   |   on node E, `f_up`       +---+
                                       \------| ---/   if applied on node E.      |
                                            +---+                               +---+
                                            | C |                               | H |
                                            +---+                               +---+
                                            /   \
                                       +---+     +---+
                                       | B |     | D |
                                       +---+     +---+
                                                   |
                                                 +---+
                                                 | A |
                                                 +---+

fn exists<F: FnMut(&Self) -> Result<bool>>(&self, f: F) -> Result<bool>

Returns true if f returns true for any node in the tree.

Stops recursion as soon as a matching node is found

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementations on Foreign Types

impl<T: DynTreeNode + ?Sized> TreeNode for Arc<T>

Blanket implementation for any Arc<T> where T implements DynTreeNode (such as Arc<dyn PhysicalExpr>).

fn apply_children<'n, F: FnMut(&'n Self) -> Result<TreeNodeRecursion>>( &'n self, f: F, ) -> Result<TreeNodeRecursion>

fn map_children<F: FnMut(Self) -> Result<Transformed<Self>>>( self, f: F, ) -> Result<Transformed<Self>>

Implementors

impl<T: ConcreteTreeNode> TreeNode for T