Skip to main content

nu_protocol/ast/
traverse.rs

1use std::ops::ControlFlow;
2
3use crate::engine::StateWorkingSet;
4
5use super::{
6    Block, Expr, Expression, ListItem, MatchPattern, Pattern, PipelineRedirection, RecordItem,
7};
8
9/// Trait for traversing the AST
10pub trait Traverse {
11    /// Generic function that do flat_map on an AST node.
12    /// Concatenates all recursive results on sub-expressions
13    /// into the `results` accumulator.
14    ///
15    /// # Arguments
16    /// * `f` - function that generates leaf elements
17    /// * `results` - accumulator
18    fn flat_map<'a, T, F>(&'a self, working_set: &'a StateWorkingSet, f: &F, results: &mut Vec<T>)
19    where
20        F: Fn(&'a Expression) -> Vec<T>;
21
22    /// Generic function that do find_map on an AST node.
23    /// Return the first result found by applying `f` on sub-expressions.
24    ///
25    /// # Arguments
26    /// * `f` - function that overrides the default behavior
27    fn find_map<'a, T, F>(&'a self, working_set: &'a StateWorkingSet, f: &F) -> Option<T>
28    where
29        F: Fn(&'a Expression) -> ControlFlow<Option<T>>;
30}
31
32impl Traverse for Block {
33    fn flat_map<'a, T, F>(&'a self, working_set: &'a StateWorkingSet, f: &F, results: &mut Vec<T>)
34    where
35        F: Fn(&'a Expression) -> Vec<T>,
36    {
37        for pipeline in self.pipelines.iter() {
38            for element in pipeline.elements.iter() {
39                element.expr.flat_map(working_set, f, results);
40                if let Some(redir) = &element.redirection {
41                    redir.flat_map(working_set, f, results);
42                };
43            }
44        }
45    }
46
47    fn find_map<'a, T, F>(&'a self, working_set: &'a StateWorkingSet, f: &F) -> Option<T>
48    where
49        F: Fn(&'a Expression) -> ControlFlow<Option<T>>,
50    {
51        self.pipelines.iter().find_map(|pipeline| {
52            pipeline.elements.iter().find_map(|element| {
53                element.expr.find_map(working_set, f).or(element
54                    .redirection
55                    .as_ref()
56                    .and_then(|redir| redir.find_map(working_set, f)))
57            })
58        })
59    }
60}
61
62impl Traverse for PipelineRedirection {
63    fn flat_map<'a, T, F>(&'a self, working_set: &'a StateWorkingSet, f: &F, results: &mut Vec<T>)
64    where
65        F: Fn(&'a Expression) -> Vec<T>,
66    {
67        let mut recur = |expr: &'a Expression| expr.flat_map(working_set, f, results);
68
69        match self {
70            PipelineRedirection::Single { target, .. } => target.expr().map(recur),
71            PipelineRedirection::Separate { out, err } => {
72                out.expr().map(&mut recur);
73                err.expr().map(&mut recur)
74            }
75        };
76    }
77
78    fn find_map<'a, T, F>(&'a self, working_set: &'a StateWorkingSet, f: &F) -> Option<T>
79    where
80        F: Fn(&'a Expression) -> ControlFlow<Option<T>>,
81    {
82        let recur = |expr: &'a Expression| expr.find_map(working_set, f);
83        match self {
84            PipelineRedirection::Single { target, .. } => target.expr().and_then(recur),
85            PipelineRedirection::Separate { out, err } => {
86                [out, err].iter().filter_map(|t| t.expr()).find_map(recur)
87            }
88        }
89    }
90}
91
92impl Traverse for Expression {
93    fn flat_map<'a, T, F>(&'a self, working_set: &'a StateWorkingSet, f: &F, results: &mut Vec<T>)
94    where
95        F: Fn(&'a Expression) -> Vec<T>,
96    {
97        // leaf elements generated by `f` for this expression
98        results.extend(f(self));
99        let mut recur = |expr: &'a Expression| expr.flat_map(working_set, f, results);
100
101        match &self.expr {
102            Expr::RowCondition(block_id)
103            | Expr::Subexpression(block_id)
104            | Expr::Block(block_id)
105            | Expr::Closure(block_id) => {
106                let block = working_set.get_block(block_id.to_owned());
107                block.flat_map(working_set, f, results)
108            }
109            Expr::Range(range) => {
110                for sub_expr in [&range.from, &range.next, &range.to].into_iter().flatten() {
111                    recur(sub_expr);
112                }
113            }
114            Expr::Call(call) => {
115                for arg in &call.arguments {
116                    if let Some(sub_expr) = arg.expr() {
117                        recur(sub_expr);
118                    }
119                }
120            }
121            Expr::ExternalCall(head, args) => {
122                recur(head.as_ref());
123                for arg in args {
124                    recur(arg.expr());
125                }
126            }
127            Expr::UnaryNot(expr) | Expr::UnaryMinus(expr) | Expr::Collect(_, expr) => {
128                recur(expr.as_ref())
129            }
130            Expr::BinaryOp(lhs, op, rhs) => {
131                recur(lhs);
132                recur(op);
133                recur(rhs);
134            }
135            Expr::MatchBlock(matches) => {
136                for (pattern, expr) in matches {
137                    pattern.flat_map(working_set, f, results);
138                    expr.flat_map(working_set, f, results);
139                }
140            }
141            Expr::List(items) => {
142                for item in items {
143                    match item {
144                        ListItem::Item(expr) | ListItem::Spread(_, expr) => recur(expr),
145                    }
146                }
147            }
148            Expr::Record(items) => {
149                for item in items {
150                    match item {
151                        RecordItem::Spread(_, expr) => recur(expr),
152                        RecordItem::Pair(key, val) => {
153                            recur(key);
154                            recur(val);
155                        }
156                    }
157                }
158            }
159            Expr::Table(table) => {
160                for column in &table.columns {
161                    recur(column);
162                }
163                for row in &table.rows {
164                    for item in row {
165                        recur(item);
166                    }
167                }
168            }
169            Expr::ValueWithUnit(vu) => recur(&vu.expr),
170            Expr::FullCellPath(fcp) => recur(&fcp.head),
171            Expr::Keyword(kw) => recur(&kw.expr),
172            Expr::StringInterpolation(vec) | Expr::GlobInterpolation(vec, _) => {
173                for item in vec {
174                    recur(item);
175                }
176            }
177            Expr::AttributeBlock(ab) => {
178                for attr in &ab.attributes {
179                    recur(&attr.expr);
180                }
181                recur(&ab.item);
182            }
183
184            _ => (),
185        };
186    }
187
188    fn find_map<'a, T, F>(&'a self, working_set: &'a StateWorkingSet, f: &F) -> Option<T>
189    where
190        F: Fn(&'a Expression) -> ControlFlow<Option<T>>,
191    {
192        // behavior overridden by f
193        match f(self) {
194            ControlFlow::Break(Some(t)) => Some(t),
195            ControlFlow::Break(None) => None,
196            ControlFlow::Continue(()) => {
197                let recur = |expr: &'a Expression| expr.find_map(working_set, f);
198                match &self.expr {
199                    Expr::RowCondition(block_id)
200                    | Expr::Subexpression(block_id)
201                    | Expr::Block(block_id)
202                    | Expr::Closure(block_id) => {
203                        let block = working_set.get_block(*block_id);
204                        block.find_map(working_set, f)
205                    }
206                    Expr::Range(range) => [&range.from, &range.next, &range.to]
207                        .iter()
208                        .find_map(|e| e.as_ref().and_then(recur)),
209                    Expr::Call(call) => call
210                        .arguments
211                        .iter()
212                        .find_map(|arg| arg.expr().and_then(recur)),
213                    Expr::ExternalCall(head, args) => {
214                        recur(head.as_ref()).or(args.iter().find_map(|arg| recur(arg.expr())))
215                    }
216                    Expr::UnaryNot(expr) | Expr::UnaryMinus(expr) | Expr::Collect(_, expr) => {
217                        recur(expr.as_ref())
218                    }
219                    Expr::BinaryOp(lhs, op, rhs) => recur(lhs).or(recur(op)).or(recur(rhs)),
220                    Expr::MatchBlock(matches) => matches.iter().find_map(|(pattern, expr)| {
221                        pattern.find_map(working_set, f).or(recur(expr))
222                    }),
223                    Expr::List(items) => items.iter().find_map(|item| match item {
224                        ListItem::Item(expr) | ListItem::Spread(_, expr) => recur(expr),
225                    }),
226                    Expr::Record(items) => items.iter().find_map(|item| match item {
227                        RecordItem::Spread(_, expr) => recur(expr),
228                        RecordItem::Pair(key, val) => [key, val].into_iter().find_map(recur),
229                    }),
230                    Expr::Table(table) => table
231                        .columns
232                        .iter()
233                        .find_map(recur)
234                        .or(table.rows.iter().find_map(|row| row.iter().find_map(recur))),
235                    Expr::ValueWithUnit(vu) => recur(&vu.expr),
236                    Expr::FullCellPath(fcp) => recur(&fcp.head),
237                    Expr::Keyword(kw) => recur(&kw.expr),
238                    Expr::StringInterpolation(vec) | Expr::GlobInterpolation(vec, _) => {
239                        vec.iter().find_map(recur)
240                    }
241                    Expr::AttributeBlock(ab) => ab
242                        .attributes
243                        .iter()
244                        .find_map(|attr| recur(&attr.expr))
245                        .or_else(|| recur(&ab.item)),
246
247                    _ => None,
248                }
249            }
250        }
251    }
252}
253
254impl Traverse for MatchPattern {
255    fn flat_map<'a, T, F>(&'a self, working_set: &'a StateWorkingSet, f: &F, results: &mut Vec<T>)
256    where
257        F: Fn(&'a Expression) -> Vec<T>,
258    {
259        let mut recur_pattern =
260            |pattern: &'a MatchPattern| pattern.flat_map(working_set, f, results);
261
262        match &self.pattern {
263            Pattern::Expression(expr) => expr.flat_map(working_set, f, results),
264            Pattern::List(patterns) | Pattern::Or(patterns) => {
265                for pattern in patterns {
266                    recur_pattern(pattern);
267                }
268            }
269            Pattern::Record(entries) => {
270                for (_, p) in entries {
271                    recur_pattern(p);
272                }
273            }
274            _ => (),
275        };
276
277        if let Some(g) = self.guard.as_ref() {
278            g.flat_map(working_set, f, results);
279        }
280    }
281
282    fn find_map<'a, T, F>(&'a self, working_set: &'a StateWorkingSet, f: &F) -> Option<T>
283    where
284        F: Fn(&'a Expression) -> ControlFlow<Option<T>>,
285    {
286        let recur = |expr: &'a Expression| expr.find_map(working_set, f);
287        let recur_pattern = |pattern: &'a MatchPattern| pattern.find_map(working_set, f);
288        match &self.pattern {
289            Pattern::Expression(expr) => recur(expr),
290            Pattern::List(patterns) | Pattern::Or(patterns) => {
291                patterns.iter().find_map(recur_pattern)
292            }
293            Pattern::Record(entries) => entries.iter().find_map(|(_, p)| recur_pattern(p)),
294            _ => None,
295        }
296        .or(self.guard.as_ref().and_then(|g| recur(g)))
297    }
298}