Struct CSEVisitor 

struct CSEVisitor<'a, 'n, N, C>
where
    N: NormalizeEq,
    C: CSEController<Node = N>,
{
    node_stats: &'a mut HashMap<Identifier<'n, N>, NodeEvaluation>,
    id_array: &'a mut Vec<(usize, Option<Identifier<'n, N>>)>,
    visit_stack: Vec<VisitRecord<'n, N>>,
    down_index: usize,
    up_index: usize,
    random_state: &'a RandomState,
    found_common: bool,
    conditional: bool,
    controller: &'a mut C,
}

Go through a TreeNode tree and generate identifiers for each subtrees.

An identifier contains information of the TreeNode itself and its subtrees. This visitor implementation use a stack visit_stack to track traversal, which lets us know when a subtree’s visiting is finished. When pre_visit is called (traversing to a new node), an EnterMark and an NodeItem will be pushed into stack. And try to pop out a EnterMark on leaving a node (f_up()). All NodeItem before the first EnterMark is considered to be sub-tree of the leaving node.

This visitor also records identifier in id_array. Makes the following traverse pass can get the identifier of a node without recalculate it. We assign each node in the tree a series number, start from 1, maintained by series_number. Series number represents the order we left (f_up()) a node. Has the property that child node’s series number always smaller than parent’s. While id_array is organized in the order we enter (f_down()) a node. node_count helps us to get the index of id_array for each node.

A TreeNode without any children (column, literal etc.) will not have identifier because they should not be recognized as common subtree.

Fields

node_stats: &'a mut HashMap<Identifier<'n, N>, NodeEvaluation>

statistics of TreeNodes

id_array: &'a mut Vec<(usize, Option<Identifier<'n, N>>)>

cache to speed up second traversal

visit_stack: Vec<VisitRecord<'n, N>>

inner states

down_index: usize

preorder index, start from 0.

up_index: usize

postorder index, start from 0.

random_state: &'a RandomState

a RandomState to generate hashes during the first traversal

found_common: bool

a flag to indicate that common TreeNodes found

conditional: bool

if we are in a conditional branch. A conditional branch means that the TreeNode might not be executed depending on the runtime values of other TreeNodes, and thus can not be extracted as a common TreeNode.

controller: &'a mut C

Implementations

impl<'n, N, C> CSEVisitor<'_, 'n, N, C>

where N: TreeNode + HashNode + NormalizeEq, C: CSEController<Node = N>,

fn pop_enter_mark( &mut self, can_normalize: bool, ) -> (usize, Option<Identifier<'n, N>>, bool)

Find the first EnterMark in the stack, and accumulates every NodeItem before it. Returns a tuple that contains:

• The pre-order index of the TreeNode we marked.
• The accumulated identifier of the children of the marked TreeNode.
• An accumulated boolean flag from the children of the marked TreeNode if all children are valid for CSE (i.e. it is safe to extract the TreeNode as a common TreeNode from its children POV). (E.g. if any of the children of the marked expression is not valid (e.g. is volatile) then the expression is also not valid, so we can propagate this information up from children to parents via visit_stack during the first, visiting traversal and no need to test the expression’s validity beforehand with an extra traversal).

Trait Implementations

impl<'n, N, C> TreeNodeVisitor<'n> for CSEVisitor<'_, 'n, N, C>

where N: TreeNode + HashNode + NormalizeEq, C: CSEController<Node = N>,

type Node = N

The node type which is visitable.

fn f_down(&mut self, node: &'n Self::Node) -> Result<TreeNodeRecursion>

Invoked while traversing down the tree, before any children are visited. Default implementation continues the recursion.

fn f_up(&mut self, node: &'n Self::Node) -> Result<TreeNodeRecursion>

Invoked while traversing up the tree after children are visited. Default implementation continues the recursion.