cas_parser/parser/
iter.rs

1use super::ast::expr::Expr;
2
3/// An iterator that iteratively traverses the tree of expressions in left-to-right post-order
4/// (i.e. depth-first).
5///
6/// This iterator is created by [`Expr::post_order_iter`].
7pub struct ExprIter<'a> {
8    stack: Vec<&'a Expr>,
9    last_visited: Option<&'a Expr>,
10}
11
12impl<'a> ExprIter<'a> {
13    /// Creates a new iterator that traverses the tree of expressions in left-to-right post-order
14    /// (i.e. depth-first).
15    pub fn new(expr: &'a Expr) -> Self {
16        Self {
17            stack: vec![expr],
18            last_visited: None,
19        }
20    }
21
22    /// Pops the current expression in the stack and marks it as the last visited expression.
23    fn visit(&mut self) -> Option<&'a Expr> {
24        self.last_visited = Some(self.stack.pop()?);
25        self.last_visited
26    }
27
28    /// Returns true if the given expression matches the last visited expression.
29    fn is_last_visited(&self, expr: &'a Expr) -> bool {
30        match self.last_visited {
31            Some(last_visited) => std::ptr::eq(last_visited, expr),
32            None => false,
33        }
34    }
35}
36
37impl<'a> Iterator for ExprIter<'a> {
38    type Item = &'a Expr;
39
40    fn next(&mut self) -> Option<Self::Item> {
41        loop {
42            let expr = self.stack.last()?;
43            match expr {
44                Expr::Literal(_) => return self.visit(),
45                Expr::Paren(paren) => {
46                    if self.is_last_visited(&paren.expr) {
47                        return self.visit();
48                    }
49                    self.stack.push(&paren.expr);
50                },
51                Expr::Block(_) => return self.visit(), // NOTE: inner statements are not visited; me in 2024-27-09: why?
52                Expr::Sum(sum) => {
53                    if self.is_last_visited(&sum.body) {
54                        return self.visit();
55                    }
56                    self.stack.push(&sum.body);
57                    // TODO: should the range and variable be visited?
58                },
59                Expr::Product(product) => {
60                    if self.is_last_visited(&product.body) {
61                        return self.visit();
62                    }
63                    self.stack.push(&product.body);
64                    // TODO: should the range and variable be visited?
65                },
66                Expr::If(if_expr) => {
67                    if let Some(else_expr) = &if_expr.else_expr {
68                        if self.is_last_visited(else_expr) {
69                            return self.visit();
70                        }
71                        self.stack.push(else_expr);
72                        self.stack.push(&if_expr.then_expr);
73                        self.stack.push(&if_expr.condition);
74                    } else {
75                        if self.is_last_visited(&if_expr.then_expr) {
76                            return self.visit();
77                        }
78                        self.stack.push(&if_expr.then_expr);
79                        self.stack.push(&if_expr.condition);
80                    }
81                },
82                Expr::Loop(loop_expr) => {
83                    if self.is_last_visited(&loop_expr.body) {
84                        return self.visit();
85                    }
86                    self.stack.push(&loop_expr.body);
87                },
88                Expr::While(while_expr) => {
89                    if self.is_last_visited(&while_expr.body) {
90                        return self.visit();
91                    }
92                    self.stack.push(&while_expr.body);
93                    self.stack.push(&while_expr.condition);
94                },
95                Expr::For(for_expr) => {
96                    if self.is_last_visited(&for_expr.body) {
97                        return self.visit();
98                    }
99                    self.stack.push(&for_expr.body);
100                },
101                Expr::Then(then) => {
102                    if self.is_last_visited(&then.expr) {
103                        return self.visit();
104                    }
105                    self.stack.push(&then.expr);
106                },
107                Expr::Of(of) => {
108                    if self.is_last_visited(&of.expr) {
109                        return self.visit();
110                    }
111                    self.stack.push(&of.expr);
112                },
113                Expr::Break(break_expr) => {
114                    if let Some(value) = &break_expr.value {
115                        if self.is_last_visited(value) {
116                            return self.visit();
117                        }
118                        self.stack.push(value);
119                    } else {
120                        return self.visit();
121                    }
122                },
123                Expr::Continue(_) => return self.visit(),
124                Expr::Return(_) => return self.visit(),
125                Expr::Call(call) => {
126                    if call.args.is_empty() || self.is_last_visited(call.args.last().unwrap()) {
127                        return self.visit();
128                    }
129                    for arg in call.args.iter().rev() {
130                        self.stack.push(arg);
131                    }
132                },
133                Expr::Index(index) => {
134                    if self.is_last_visited(&index.index) {
135                        return self.visit();
136                    }
137                    self.stack.push(&index.index);
138                    self.stack.push(&index.target);
139                },
140                Expr::Unary(unary) => {
141                    if self.is_last_visited(&unary.operand) {
142                        return self.visit();
143                    }
144                    self.stack.push(&unary.operand);
145                },
146                Expr::Binary(binary) => {
147                    if self.is_last_visited(&binary.rhs) {
148                        return self.visit();
149                    }
150                    self.stack.push(&binary.rhs);
151                    self.stack.push(&binary.lhs);
152                },
153                Expr::Assign(assign) => {
154                    if self.is_last_visited(&assign.value) {
155                        return self.visit();
156                    }
157                    self.stack.push(&assign.value);
158                },
159                Expr::Range(range) => {
160                    if self.is_last_visited(&range.end) {
161                        return self.visit();
162                    }
163                    self.stack.push(&range.end);
164                    self.stack.push(&range.start);
165                },
166            }
167        }
168    }
169}
cas_parser/parser/iter.rs

cas_parser/parser/
iter.rs
