Skip to main content

nu_protocol/engine/
pattern_match.rs

1use crate::{
2    Span, Value, VarId,
3    ast::{Expr, MatchPattern, Pattern, RangeInclusion},
4};
5
6pub trait Matcher {
7    fn match_value(&self, value: &Value, matches: &mut Vec<(VarId, Value)>) -> bool;
8}
9
10impl Matcher for MatchPattern {
11    fn match_value(&self, value: &Value, matches: &mut Vec<(VarId, Value)>) -> bool {
12        self.pattern.match_value(value, matches)
13    }
14}
15
16impl Matcher for Pattern {
17    fn match_value(&self, value: &Value, matches: &mut Vec<(VarId, Value)>) -> bool {
18        match self {
19            Pattern::Garbage => false,
20            Pattern::IgnoreValue => true,
21            Pattern::IgnoreRest => false, // `..` and `..$foo` only match in specific contexts
22            Pattern::Rest(_) => false,    // so we return false here and handle them elsewhere
23            Pattern::Record(field_patterns) => match value {
24                Value::Record { val, .. } => {
25                    'top: for field_pattern in field_patterns {
26                        for (col, val) in &**val {
27                            if col == &field_pattern.0 {
28                                // We have found the field
29                                let result = field_pattern.1.match_value(val, matches);
30                                if !result {
31                                    return false;
32                                } else {
33                                    continue 'top;
34                                }
35                            }
36                        }
37                        return false;
38                    }
39                    true
40                }
41                _ => false,
42            },
43            Pattern::Variable(var_id) => {
44                // TODO: FIXME: This needs the span of this variable
45                matches.push((*var_id, value.clone()));
46                true
47            }
48            Pattern::List(items) => match &value {
49                Value::List { vals, .. } => {
50                    // The parser allows at most one `..` or `..$name` per list pattern, at any
51                    // position. Items before it match the start of the list, items after it
52                    // match the end, and the rest pattern takes whatever is left in between.
53                    let rest_idx = items.iter().position(|item| {
54                        matches!(item.pattern, Pattern::IgnoreRest | Pattern::Rest(_))
55                    });
56                    let (before, rest, after) = match rest_idx {
57                        Some(idx) => (&items[..idx], Some(&items[idx]), &items[idx + 1..]),
58                        None => (&items[..], None, &[][..]),
59                    };
60
61                    // Without a rest pattern the lengths must be equal; with one the list may be longer.
62                    let fixed_len = before.len() + after.len();
63                    if vals.len() < fixed_len || (rest.is_none() && vals.len() > fixed_len) {
64                        return false;
65                    }
66                    let after_start = vals.len() - after.len();
67
68                    // Bind left to right, so a variable used twice keeps its rightmost value.
69                    if !before
70                        .iter()
71                        .zip(vals)
72                        .all(|(pattern, val)| pattern.match_value(val, matches))
73                    {
74                        return false;
75                    }
76                    if let Some(MatchPattern {
77                        pattern: Pattern::Rest(var_id),
78                        span,
79                        ..
80                    }) = rest
81                    {
82                        let rest_vals = vals[before.len()..after_start].to_vec();
83                        matches.push((*var_id, Value::list(rest_vals, *span)));
84                    }
85                    after
86                        .iter()
87                        .zip(&vals[after_start..])
88                        .all(|(pattern, val)| pattern.match_value(val, matches))
89                }
90                _ => false,
91            },
92            Pattern::Expression(pattern_value) => {
93                // TODO: Fill this out with the rest of them
94                match &pattern_value.expr {
95                    Expr::Nothing => {
96                        matches!(value, Value::Nothing { .. })
97                    }
98                    Expr::Int(x) => {
99                        if let Value::Int { val, .. } = &value {
100                            x == val
101                        } else {
102                            false
103                        }
104                    }
105                    Expr::Float(x) => {
106                        if let Value::Float { val, .. } = &value {
107                            x == val
108                        } else {
109                            false
110                        }
111                    }
112                    Expr::Binary(x) => {
113                        if let Value::Binary { val, .. } = &value {
114                            x.as_slice() == val.as_slice()
115                        } else {
116                            false
117                        }
118                    }
119                    Expr::Bool(x) => {
120                        if let Value::Bool { val, .. } = &value {
121                            x == val
122                        } else {
123                            false
124                        }
125                    }
126                    Expr::String(x) | Expr::RawString(x) => {
127                        if let Value::String { val, .. } = &value {
128                            x == val
129                        } else {
130                            false
131                        }
132                    }
133                    Expr::DateTime(x) => {
134                        if let Value::Date { val, .. } = &value {
135                            x == val
136                        } else {
137                            false
138                        }
139                    }
140                    Expr::ValueWithUnit(val) => {
141                        let span = val.unit.span;
142
143                        if let Expr::Int(size) = val.expr.expr {
144                            match &val.unit.item.build_value(size, span) {
145                                Ok(v) => v == value,
146                                _ => false,
147                            }
148                        } else {
149                            false
150                        }
151                    }
152                    Expr::Range(range) => {
153                        // TODO: Add support for floats
154
155                        let start = if let Some(start) = &range.from {
156                            match &start.expr {
157                                Expr::Int(start) => *start,
158                                _ => return false,
159                            }
160                        } else {
161                            0
162                        };
163
164                        let end = if let Some(end) = &range.to {
165                            match &end.expr {
166                                Expr::Int(end) => *end,
167                                _ => return false,
168                            }
169                        } else {
170                            i64::MAX
171                        };
172
173                        let step = if let Some(step) = &range.next {
174                            match &step.expr {
175                                Expr::Int(step) => *step - start,
176                                _ => return false,
177                            }
178                        } else if end < start {
179                            -1
180                        } else {
181                            1
182                        };
183
184                        let (start, end) = if end < start {
185                            (end, start)
186                        } else {
187                            (start, end)
188                        };
189
190                        if let Value::Int { val, .. } = &value {
191                            if matches!(range.operator.inclusion, RangeInclusion::RightExclusive) {
192                                *val >= start && *val < end && ((*val - start) % step) == 0
193                            } else {
194                                *val >= start && *val <= end && ((*val - start) % step) == 0
195                            }
196                        } else {
197                            false
198                        }
199                    }
200                    _ => false,
201                }
202            }
203            Pattern::Value(pattern_value) => match pattern_value {
204                // Ranges match by containment (same as `Pattern::Expression` + `Expr::Range`).
205                Value::Range { val, .. } => val.contains(value),
206                _ => value == pattern_value,
207            },
208            Pattern::Or(patterns) => {
209                let mut result = false;
210
211                for pattern in patterns {
212                    let mut local_matches = vec![];
213                    if !result {
214                        if pattern.match_value(value, &mut local_matches) {
215                            // TODO: do we need to replace previous variables that defaulted to nothing?
216                            matches.append(&mut local_matches);
217                            result = true;
218                        } else {
219                            // Create variables that don't match and assign them to null
220                            let vars = pattern.variables();
221                            for var in &vars {
222                                let mut found = false;
223                                for match_ in matches.iter() {
224                                    if match_.0 == *var {
225                                        found = true;
226                                    }
227                                }
228
229                                if !found {
230                                    // FIXME: don't use Span::unknown()
231                                    matches.push((*var, Value::nothing(Span::unknown())))
232                                }
233                            }
234                        }
235                    } else {
236                        // We already have a match, so ignore the remaining match variables
237                        // And assign them to null
238                        let vars = pattern.variables();
239                        for var in &vars {
240                            let mut found = false;
241                            for match_ in matches.iter() {
242                                if match_.0 == *var {
243                                    found = true;
244                                }
245                            }
246
247                            if !found {
248                                // FIXME: don't use Span::unknown()
249                                matches.push((*var, Value::nothing(Span::unknown())))
250                            }
251                        }
252                    }
253                }
254                result
255            }
256        }
257    }
258}