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}