Trait datafusion_common::tree_node::TreeNode

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

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

Defines a visitable and rewriteable tree node. This trait is implemented for plans (ExecutionPlan and LogicalPlan) as well as expression trees (PhysicalExpr, Expr) in DataFusion.

Required Methods

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

Apply the closure F to the node’s children.

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

Apply transform F to the node’s children. Note that the transform F might have a direction (pre-order or post-order).

Provided Methods

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

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

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)

See TreeNodeRecursion for more details on controlling the traversal.

If TreeNodeVisitor::f_down() or TreeNodeVisitor::f_up() returns Err, the recursion stops immediately.

If using the default TreeNodeVisitor::f_up that does nothing, consider using Self::apply.

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

Implements the visitor pattern for recursively transforming TreeNodes.

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)

See TreeNodeRecursion for more details on controlling the traversal.

If TreeNodeVisitor::f_down() or TreeNodeVisitor::f_up() returns Err, the recursion stops immediately.

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

Applies f to the node and its children. f is applied in a pre-order way, and it is controlled by TreeNodeRecursion, which means result of the f on a node can cause an early return.

The f closure can be used to collect some information from tree nodes or run a check on the tree.

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

Convenience utility for writing optimizer rules: Recursively apply the given function f to the tree in a bottom-up (post-order) fashion. When f does not apply to a given node, it is left unchanged.

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

Convenience utility for writing optimizer rules: Recursively apply the given function f to a node and then to its children (pre-order traversal). When f does not apply to a given node, it is left unchanged.

fn transform_down_mut<F: FnMut(Self) -> Result<Transformed<Self>>>( self, f: &mut F ) -> Result<Transformed<Self>>

Convenience utility for writing optimizer rules: Recursively apply the given mutable function f to a node and then to its children (pre-order traversal). When f does not apply to a given node, it is left unchanged.

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

Convenience utility for writing optimizer rules: Recursively apply the given function f to all children of a node, and then to the node itself (post-order traversal). When f does not apply to a given node, it is left unchanged.

fn transform_up_mut<F: FnMut(Self) -> Result<Transformed<Self>>>( self, f: &mut F ) -> Result<Transformed<Self>>

Convenience utility for writing optimizer rules: Recursively apply the given mutable function f to all children of a node, and then to the node itself (post-order traversal). When f does not apply to a given node, it is left unchanged.

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

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

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. If you don’t need this, it’s just like using transform_down_mut followed by transform_up_mut on the same tree.

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 |
                                                 +---+

Object Safety

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<F: FnMut(&Self) -> Result<TreeNodeRecursion>>( &self, f: &mut 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