Trait datafusion::common::tree_node::TreeNode

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

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

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 OrderInspectingTransforming
top-downapply, existstransform_down
bottom-uptransform , transform_up
combined with separate f_down and f_up closurestransform_down_up
combined with f_down() and f_up() in an objectvisitrewrite

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§

source

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

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).

source

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

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§

source

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

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:
§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)
source

fn rewrite<R>( self, rewriter: &mut R ) -> Result<Transformed<Self>, DataFusionError>
where R: TreeNodeRewriter<Node = 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
§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)
source

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

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
source

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

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

A synonym of Self::transform_up.

source

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

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
source

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

👎Deprecated since 38.0.0: Use transform_down instead

Same as Self::transform_down but with a mutable closure.

source

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

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
source

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

👎Deprecated since 38.0.0: Use transform_up instead

Same as Self::transform_up but with a mutable closure.

source

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

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

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

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

Stops recursion as soon as a matching node is found

Object Safety§

This trait is not object safe.

Implementations on Foreign Types§

source§

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

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

source§

fn apply_children<F>(&self, f: F) -> Result<TreeNodeRecursion, DataFusionError>
where F: FnMut(&Arc<T>) -> Result<TreeNodeRecursion, DataFusionError>,

source§

fn map_children<F>(self, f: F) -> Result<Transformed<Arc<T>>, DataFusionError>
where F: FnMut(Arc<T>) -> Result<Transformed<Arc<T>>, DataFusionError>,

Implementors§