1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

use recursive::recursive;

use super::*;

/// An implementor of this trait decides how and in which order its nodes get traversed
/// Implemented for [`crate::dsl::Expr`] and [`AexprNode`].
pub trait TreeWalker: Sized {
    type Arena;
    fn apply_children<F: FnMut(&Self, &Self::Arena) -> PolarsResult<VisitRecursion>>(
        &self,
        op: &mut F,
        arena: &Self::Arena,
    ) -> PolarsResult<VisitRecursion>;

    fn map_children<F: FnMut(Self, &mut Self::Arena) -> PolarsResult<Self>>(
        self,
        op: &mut F,
        arena: &mut Self::Arena,
    ) -> PolarsResult<Self>;

    /// Walks all nodes in depth-first-order.
    #[recursive]
    fn visit<V: Visitor<Node = Self, Arena = Self::Arena>>(
        &self,
        visitor: &mut V,
        arena: &Self::Arena,
    ) -> PolarsResult<VisitRecursion> {
        match visitor.pre_visit(self, arena)? {
            VisitRecursion::Continue => {},
            // If the recursion should skip, do not apply to its children. And let the recursion continue
            VisitRecursion::Skip => return Ok(VisitRecursion::Continue),
            // If the recursion should stop, do not apply to its children
            VisitRecursion::Stop => return Ok(VisitRecursion::Stop),
        };

        match self.apply_children(&mut |node, arena| node.visit(visitor, arena), arena)? {
            // let the recursion continue
            VisitRecursion::Continue | VisitRecursion::Skip => {},
            // If the recursion should stop, no further post visit will be performed
            VisitRecursion::Stop => return Ok(VisitRecursion::Stop),
        }

        visitor.post_visit(self, arena)
    }

    #[recursive]
    fn rewrite<R: RewritingVisitor<Node = Self, Arena = Self::Arena>>(
        self,
        rewriter: &mut R,
        arena: &mut Self::Arena,
    ) -> PolarsResult<Self> {
        let mutate_this_node = match rewriter.pre_visit(&self, arena)? {
            RewriteRecursion::MutateAndStop => return rewriter.mutate(self, arena),
            RewriteRecursion::Stop => return Ok(self),
            RewriteRecursion::MutateAndContinue => true,
            RewriteRecursion::NoMutateAndContinue => false,
        };

        let after_applied_children =
            self.map_children(&mut |node, arena| node.rewrite(rewriter, arena), arena)?;

        if mutate_this_node {
            rewriter.mutate(after_applied_children, arena)
        } else {
            Ok(after_applied_children)
        }
    }
}

pub trait Visitor {
    type Node;
    type Arena;

    /// Invoked before any children of `node` are visited.
    fn pre_visit(
        &mut self,
        _node: &Self::Node,
        _arena: &Self::Arena,
    ) -> PolarsResult<VisitRecursion> {
        Ok(VisitRecursion::Continue)
    }

    /// Invoked after all children of `node` are visited. Default
    /// implementation does nothing.
    fn post_visit(
        &mut self,
        _node: &Self::Node,
        _arena: &Self::Arena,
    ) -> PolarsResult<VisitRecursion> {
        Ok(VisitRecursion::Continue)
    }
}

pub trait RewritingVisitor {
    type Node;
    type Arena;

    /// Invoked before any children of `node` are visited.
    fn pre_visit(
        &mut self,
        _node: &Self::Node,
        _arena: &mut Self::Arena,
    ) -> PolarsResult<RewriteRecursion> {
        Ok(RewriteRecursion::MutateAndContinue)
    }

    fn mutate(&mut self, node: Self::Node, _arena: &mut Self::Arena) -> PolarsResult<Self::Node>;
}