edn/
matcher.rs

1// Copyright 2016 Mozilla
2//
3// Licensed under the Apache License, Version 2.0 (the "License"); you may not use
4// this file except in compliance with the License. You may obtain a copy of the
5// License at http://www.apache.org/licenses/LICENSE-2.0
6// Unless required by applicable law or agreed to in writing, software distributed
7// under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR
8// CONDITIONS OF ANY KIND, either express or implied. See the License for the
9// specific language governing permissions and limitations under the License.
10
11use itertools::diff_with;
12use std::cell::RefCell;
13use std::collections::HashMap;
14
15use crate::symbols;
16use crate::types::Value;
17
18/// A trait defining pattern matching rules for any given pattern of type `T`.
19trait PatternMatchingRules<'a, T> {
20    /// Return true if the given pattern matches an arbitrary value.
21    fn matches_any(pattern: &T) -> bool;
22
23    /// Return the placeholder name if the given pattern matches a placeholder.
24    fn matches_placeholder(pattern: &'a T) -> Option<&'a String>;
25}
26
27/// A default type implementing `PatternMatchingRules` specialized on
28/// EDN values using plain symbols as patterns. These patterns are:
29/// * `_` matches arbitrary sub-EDN;
30/// * `?name` matches sub-EDN, which must be identical each place `?name` appears;
31struct DefaultPatternMatchingRules;
32
33impl<'a> PatternMatchingRules<'a, Value> for DefaultPatternMatchingRules {
34    fn matches_any(pattern: &Value) -> bool {
35        match *pattern {
36            Value::PlainSymbol(symbols::PlainSymbol(ref s)) => s.starts_with('_'),
37            _ => false,
38        }
39    }
40
41    fn matches_placeholder(pattern: &'a Value) -> Option<&'a String> {
42        match *pattern {
43            Value::PlainSymbol(symbols::PlainSymbol(ref s)) => {
44                if s.starts_with('?') {
45                    Some(s)
46                } else {
47                    None
48                }
49            }
50            _ => None,
51        }
52    }
53}
54
55/// Pattern matcher for EDN values utilizing specified pattern matching rules.
56/// For example, using this with `DefaultPatternMatchingRules`:
57/// * `[_]` matches an arbitrary one-element vector;
58/// * `[_ _]` matches an arbitrary two-element vector;
59/// * `[?x ?x]` matches `[1 1]` and `[#{} #{}]` but not `[1 2]` or `[[] #{}]`;
60struct Matcher<'a> {
61    placeholders: RefCell<HashMap<&'a String, &'a Value>>,
62}
63
64impl<'a> Matcher<'a> {
65    /// Creates a Matcher instance.
66    fn new() -> Matcher<'a> {
67        Matcher {
68            placeholders: RefCell::default(),
69        }
70    }
71
72    /// Performs pattern matching between two EDN `Value` instances (`value`
73    /// and `pattern`) utilizing a specified pattern matching ruleset `T`.
74    /// Returns true if matching succeeds.
75    fn match_with_rules<T>(value: &'a Value, pattern: &'a Value) -> bool
76    where
77        T: PatternMatchingRules<'a, Value>,
78    {
79        let matcher = Matcher::new();
80        matcher.match_internal::<T>(value, pattern)
81    }
82
83    /// Recursively traverses two EDN `Value` instances (`value` and `pattern`)
84    /// performing pattern matching. Note that the internal `placeholders` cache
85    /// might not be empty on invocation.
86    fn match_internal<T>(&self, value: &'a Value, pattern: &'a Value) -> bool
87    where
88        T: PatternMatchingRules<'a, Value>,
89    {
90        use Value::*;
91
92        if T::matches_any(pattern) {
93            true
94        } else if let Some(symbol) = T::matches_placeholder(pattern) {
95            let mut placeholders = self.placeholders.borrow_mut();
96            value == *placeholders.entry(symbol).or_insert(value)
97        } else {
98            match (value, pattern) {
99                (Vector(v), Vector(p)) => {
100                    diff_with(v, p, |a, b| self.match_internal::<T>(a, b)).is_none()
101                }
102                (List(v), List(p)) => {
103                    diff_with(v, p, |a, b| self.match_internal::<T>(a, b)).is_none()
104                }
105                (Set(v), Set(p)) => {
106                    v.len() == p.len()
107                        && v.iter()
108                            .all(|a| p.iter().any(|b| self.match_internal::<T>(a, b)))
109                        && p.iter()
110                            .all(|b| v.iter().any(|a| self.match_internal::<T>(a, b)))
111                }
112                (Map(v), Map(p)) => {
113                    v.len() == p.len()
114                        && v.iter().all(|a| {
115                            p.iter().any(|b| {
116                                self.match_internal::<T>(a.0, b.0)
117                                    && self.match_internal::<T>(a.1, b.1)
118                            })
119                        })
120                        && p.iter().all(|b| {
121                            v.iter().any(|a| {
122                                self.match_internal::<T>(a.0, b.0)
123                                    && self.match_internal::<T>(a.1, b.1)
124                            })
125                        })
126                }
127                _ => value == pattern,
128            }
129        }
130    }
131}
132
133impl Value {
134    /// Performs default pattern matching between this value and some `pattern`.
135    /// Returns true if matching succeeds.
136    pub fn matches(&self, pattern: &Value) -> bool {
137        Matcher::match_with_rules::<DefaultPatternMatchingRules>(self, pattern)
138    }
139}
140
141#[cfg(test)]
142mod test {
143    use crate::parse;
144
145    macro_rules! assert_match {
146        ( $pattern:tt, $value:tt, $expected:expr ) => {
147            let pattern = parse::value($pattern).unwrap().without_spans();
148            let value = parse::value($value).unwrap().without_spans();
149            assert_eq!(value.matches(&pattern), $expected);
150        };
151        ( $pattern:tt =~ $value:tt ) => {
152            assert_match!($pattern, $value, true);
153        };
154        ( $pattern:tt !~ $value:tt ) => {
155            assert_match!($pattern, $value, false);
156        };
157    }
158
159    #[test]
160    fn test_match_primitives() {
161        assert_match!("nil" =~ "nil");
162        assert_match!("true" =~ "true");
163        assert_match!("true" !~ "false");
164        assert_match!("1" =~ "1");
165        assert_match!("1" !~ "2");
166        assert_match!("1N" =~ "1N");
167        assert_match!("1N" !~ "2N");
168        assert_match!("1.0" =~ "1.0");
169        assert_match!("1.0" !~ "2.0");
170        assert_match!("\"a\"" =~ "\"a\"");
171        assert_match!("\"a\"" !~ "\"b\"");
172        assert_match!("foo" =~ "foo");
173        assert_match!("foo" !~ "bar");
174        assert_match!("foo/bar" !~ "foo");
175    }
176
177    #[test]
178    fn test_match_collections_sorted() {
179        assert_match!("[nil, true, 1, \"foo\", bar, :baz]" =~ "[nil, true, 1, \"foo\", bar, :baz]");
180        assert_match!("(nil, true, 1, \"foo\", bar, :baz)" =~ "(nil, true, 1, \"foo\", bar, :baz)");
181        assert_match!("#{nil, true, 1, \"foo\", bar, :baz}" =~ "#{nil, true, 1, \"foo\", bar, :baz}");
182        assert_match!("{nil true, 1 \"foo\", bar :baz}" =~ "{nil true, 1 \"foo\", bar :baz}");
183    }
184
185    #[test]
186    fn test_match_collections_unsorted() {
187        assert_match!("[nil, true, 1, \"foo\", bar, :baz]" !~ "[1, \"foo\", nil, true, bar, :baz]");
188        assert_match!("(nil, true, 1, \"foo\", bar, :baz)" !~ "(1, \"foo\", nil, true, bar, :baz)");
189        assert_match!("#{nil, true, 1, \"foo\", bar, :baz}" =~ "#{1, \"foo\", nil, true, bar, :baz}");
190        assert_match!("{nil true, 1 \"foo\", bar :baz}" =~ "{1 \"foo\", nil true, bar :baz}");
191    }
192
193    #[test]
194    fn test_match_maps_switched_key_values() {
195        assert_match!("{1 2, 3 4}" =~ "{1 2, 3 4}");
196        assert_match!("{2 1, 3 4}" !~ "{1 2, 3 4}");
197        assert_match!("{2 1, 4 3}" !~ "{1 2, 3 4}");
198        assert_match!("{1 2, 4 3}" !~ "{1 2, 3 4}");
199    }
200
201    #[test]
202    fn test_match_maps_ordered_collection_keys_and_values() {
203        assert_match!("{[1, 2] (3, 4)}" =~ "{[1, 2] (3, 4)}");
204        assert_match!("{[2, 1] (3, 4)}" !~ "{[1, 2] (3, 4)}");
205        assert_match!("{[2, 1] (4, 3)}" !~ "{[1, 2] (3, 4)}");
206        assert_match!("{[1, 2] (4, 3)}" !~ "{[1, 2] (3, 4)}");
207
208        assert_match!("{(3, 4) [1, 2]}" !~ "{[1, 2] (3, 4)}");
209        assert_match!("{(3, 4) [2, 1]}" !~ "{[1, 2] (3, 4)}");
210        assert_match!("{(4, 3) [2, 1]}" !~ "{[1, 2] (3, 4)}");
211        assert_match!("{(4, 3) [1, 2]}" !~ "{[1, 2] (3, 4)}");
212    }
213
214    #[test]
215    fn test_match_maps_unordered_collection_keys_and_values() {
216        assert_match!("{#{1, 2} #{3, 4}}" =~ "{#{1, 2} #{3, 4}}");
217        assert_match!("{#{2, 1} #{3, 4}}" =~ "{#{1, 2} #{3, 4}}");
218        assert_match!("{#{2, 1} #{4, 3}}" =~ "{#{1, 2} #{3, 4}}");
219        assert_match!("{#{1, 2} #{4, 3}}" =~ "{#{1, 2} #{3, 4}}");
220
221        assert_match!("{#{3, 4} #{1, 2}}" !~ "{#{1, 2} #{3, 4}}");
222        assert_match!("{#{3, 4} #{2, 1}}" !~ "{#{1, 2} #{3, 4}}");
223        assert_match!("{#{4, 3} #{2, 1}}" !~ "{#{1, 2} #{3, 4}}");
224        assert_match!("{#{4, 3} #{1, 2}}" !~ "{#{1, 2} #{3, 4}}");
225    }
226
227    #[test]
228    fn test_match_any_simple() {
229        assert_match!("_" =~ "nil");
230        assert_match!("_" =~ "true");
231        assert_match!("_" =~ "1");
232        assert_match!("_" =~ "1N");
233        assert_match!("_" =~ "1.0");
234        assert_match!("_" =~ "\"a\"");
235        assert_match!("_" =~ "_");
236        assert_match!("_" =~ "symbol");
237        assert_match!("_" =~ "ns/symbol");
238        assert_match!("_" =~ ":keyword");
239        assert_match!("_" =~ ":ns/keyword");
240        assert_match!("_" =~ "[nil, true, 1, \"foo\", bar, :baz]");
241        assert_match!("_" =~ "(nil, true, 1, \"foo\", bar, :baz)");
242        assert_match!("_" =~ "#{nil, true, 1, \"foo\", bar, :baz}");
243        assert_match!("_" =~ "{nil true, 1 \"foo\", bar :baz}");
244    }
245
246    #[test]
247    fn test_match_any_in_same_collection_type_simple() {
248        assert_match!("[_]" =~ "[1]");
249        assert_match!("(_)" =~ "(2)");
250        assert_match!("#{_}" =~ "#{3}");
251        assert_match!("{_ _}" =~ "{4 5}");
252    }
253
254    #[test]
255    fn test_match_any_in_different_collection_type_simple() {
256        assert_match!("[_]" !~ "(1)");
257        assert_match!("(_)" !~ "#{2}");
258        assert_match!("#{_}" !~ "[3]");
259        assert_match!("{_ _}" !~ "[4 5]");
260        assert_match!("{_ _}" !~ "(6 7)");
261        assert_match!("{_ _}" !~ "#{8 9}");
262    }
263
264    #[test]
265    fn test_match_any_in_vector_with_multiple_values() {
266        assert_match!("[_ 2]" =~ "[1 2]");
267        assert_match!("[1 _]" =~ "[1 2]");
268        assert_match!("[1 _ 3 4]" =~ "[1 2 3 4]");
269        assert_match!("[1 [2 [3 _]] 5 [_ 7]]" =~ "[1 [2 [3 4]] 5 [6 7]]");
270
271        assert_match!("[_]" =~ "[[foo bar]]");
272        assert_match!("[_]" =~ "[(foo bar)]");
273        assert_match!("[_]" =~ "[#{foo bar}]");
274        assert_match!("[_]" =~ "[{foo bar}]");
275
276        assert_match!("[_ 2]" !~ "[2 1]");
277        assert_match!("[1 _]" !~ "[2 1]");
278        assert_match!("[1 _ 3]" !~ "[2 1 3]");
279
280        assert_match!("[_ 2]" !~ "[3 4]");
281        assert_match!("[1 _]" !~ "[3 4]");
282    }
283
284    #[test]
285    fn test_match_multiple_any_in_vector_with_multiple_values() {
286        assert_match!("[1 _ _]" =~ "[1 2 3]");
287        assert_match!("[2 _ _]" !~ "[1 2 3]");
288        assert_match!("[3 _ _]" !~ "[1 2 3]");
289        assert_match!("[_ 1 _]" !~ "[1 2 3]");
290        assert_match!("[_ 2 _]" =~ "[1 2 3]");
291        assert_match!("[_ 3 _]" !~ "[1 2 3]");
292        assert_match!("[_ _ 1]" !~ "[1 2 3]");
293        assert_match!("[_ _ 2]" !~ "[1 2 3]");
294        assert_match!("[_ _ 3]" =~ "[1 2 3]");
295
296        assert_match!("[1 _ _]" !~ "[2 1 3]");
297        assert_match!("[2 _ _]" =~ "[2 1 3]");
298        assert_match!("[3 _ _]" !~ "[2 1 3]");
299        assert_match!("[_ 1 _]" =~ "[2 1 3]");
300        assert_match!("[_ 2 _]" !~ "[2 1 3]");
301        assert_match!("[_ 3 _]" !~ "[2 1 3]");
302        assert_match!("[_ _ 1]" !~ "[2 1 3]");
303        assert_match!("[_ _ 2]" !~ "[2 1 3]");
304        assert_match!("[_ _ 3]" =~ "[2 1 3]");
305    }
306
307    #[test]
308    fn test_match_any_in_list_with_multiple_values() {
309        assert_match!("(_ 2)" =~ "(1 2)");
310        assert_match!("(1 _)" =~ "(1 2)");
311        assert_match!("(1 _ 3 4)" =~ "(1 2 3 4)");
312        assert_match!("(1 (2 (3 _)) 5 (_ 7))" =~ "(1 (2 (3 4)) 5 (6 7))");
313
314        assert_match!("(_)" =~ "([foo bar])");
315        assert_match!("(_)" =~ "((foo bar))");
316        assert_match!("(_)" =~ "(#{foo bar})");
317        assert_match!("(_)" =~ "({foo bar})");
318
319        assert_match!("(_ 2)" !~ "(2 1)");
320        assert_match!("(1 _)" !~ "(2 1)");
321        assert_match!("(1 _ 3)" !~ "(2 1 3)");
322
323        assert_match!("(_ 2)" !~ "(3 4)");
324        assert_match!("(1 _)" !~ "(3 4)");
325    }
326
327    #[test]
328    fn test_match_multiple_any_in_list_with_multiple_values() {
329        assert_match!("(1 _ _)" =~ "(1 2 3)");
330        assert_match!("(2 _ _)" !~ "(1 2 3)");
331        assert_match!("(3 _ _)" !~ "(1 2 3)");
332        assert_match!("(_ 1 _)" !~ "(1 2 3)");
333        assert_match!("(_ 2 _)" =~ "(1 2 3)");
334        assert_match!("(_ 3 _)" !~ "(1 2 3)");
335        assert_match!("(_ _ 1)" !~ "(1 2 3)");
336        assert_match!("(_ _ 2)" !~ "(1 2 3)");
337        assert_match!("(_ _ 3)" =~ "(1 2 3)");
338
339        assert_match!("(1 _ _)" !~ "(2 1 3)");
340        assert_match!("(2 _ _)" =~ "(2 1 3)");
341        assert_match!("(3 _ _)" !~ "(2 1 3)");
342        assert_match!("(_ 1 _)" =~ "(2 1 3)");
343        assert_match!("(_ 2 _)" !~ "(2 1 3)");
344        assert_match!("(_ 3 _)" !~ "(2 1 3)");
345        assert_match!("(_ _ 1)" !~ "(2 1 3)");
346        assert_match!("(_ _ 2)" !~ "(2 1 3)");
347        assert_match!("(_ _ 3)" =~ "(2 1 3)");
348    }
349
350    #[test]
351    fn test_match_any_in_set_with_multiple_values() {
352        assert_match!("#{_ 2}" =~ "#{1 2}");
353        assert_match!("#{1 _}" =~ "#{1 2}");
354        assert_match!("#{1 _ 3 4}" =~ "#{1 2 3 4}");
355        assert_match!("#{1 #{2 #{3 _}} 5 #{_ 7}}" =~ "#{1 #{2 #{3 4}} 5 #{6 7}}");
356
357        assert_match!("#{_}" =~ "#{[foo bar]}");
358        assert_match!("#{_}" =~ "#{(foo bar)}");
359        assert_match!("#{_}" =~ "#{#{foo bar}}");
360        assert_match!("#{_}" =~ "#{{foo bar}}");
361
362        assert_match!("#{_ 2}" =~ "#{2 1}");
363        assert_match!("#{1 _}" =~ "#{2 1}");
364        assert_match!("#{1 _ 3}" =~ "#{2 1 3}");
365
366        assert_match!("#{_ 2}" !~ "#{3 4}");
367        assert_match!("#{1 _}" !~ "#{3 4}");
368    }
369
370    #[test]
371    fn test_match_multiple_any_in_set_with_multiple_values() {
372        // These are false because _ is a symbol and sets guarantee
373        // uniqueness of children. So pattern matching will fail because
374        // the pattern is a set of length 2, while the matched edn is a set
375        // of length 3. If _ were unique, all of these assertions would
376        // be true. Need to better handle pattern rules.
377
378        assert_match!("#{1 _ _}" !~ "#{1 2 3}");
379        assert_match!("#{2 _ _}" !~ "#{1 2 3}");
380        assert_match!("#{3 _ _}" !~ "#{1 2 3}");
381        assert_match!("#{_ 1 _}" !~ "#{1 2 3}");
382        assert_match!("#{_ 2 _}" !~ "#{1 2 3}");
383        assert_match!("#{_ 3 _}" !~ "#{1 2 3}");
384        assert_match!("#{_ _ 1}" !~ "#{1 2 3}");
385        assert_match!("#{_ _ 2}" !~ "#{1 2 3}");
386        assert_match!("#{_ _ 3}" !~ "#{1 2 3}");
387
388        assert_match!("#{1 _ _}" !~ "#{2 1 3}");
389        assert_match!("#{2 _ _}" !~ "#{2 1 3}");
390        assert_match!("#{3 _ _}" !~ "#{2 1 3}");
391        assert_match!("#{_ 1 _}" !~ "#{2 1 3}");
392        assert_match!("#{_ 2 _}" !~ "#{2 1 3}");
393        assert_match!("#{_ 3 _}" !~ "#{2 1 3}");
394        assert_match!("#{_ _ 1}" !~ "#{2 1 3}");
395        assert_match!("#{_ _ 2}" !~ "#{2 1 3}");
396        assert_match!("#{_ _ 3}" !~ "#{2 1 3}");
397    }
398
399    #[test]
400    fn test_match_any_in_map_with_multiple_values() {
401        assert_match!("{_ 2}" =~ "{1 2}");
402        assert_match!("{1 _}" =~ "{1 2}");
403        assert_match!("{1 _, 3 4}" =~ "{1 2, 3 4}");
404        assert_match!("{1 {2 {3 _}}, 5 {_ 7}}" =~ "{1 {2 {3 4}}, 5 {6 7}}");
405
406        assert_match!("{_ _}" =~ "{[foo bar] [baz boz]}");
407        assert_match!("{_ _}" =~ "{(foo bar) (baz boz)}");
408        assert_match!("{_ _}" =~ "{#{foo bar} #{baz boz}}");
409        assert_match!("{_ _}" =~ "{{foo bar} {baz boz}}");
410
411        assert_match!("{_ 2, 3 4}" =~ "{3 4, 1 2}");
412        assert_match!("{1 _, 3 4}" =~ "{3 4, 1 2}");
413        assert_match!("{_ _, 3 4}" =~ "{3 4, 1 2}");
414        assert_match!("{1 2, _ 4}" =~ "{3 4, 1 2}");
415        assert_match!("{1 2, 3 _}" =~ "{3 4, 1 2}");
416        assert_match!("{1 2, _ _}" =~ "{3 4, 1 2}");
417        assert_match!("{1 2, _ 4, 5 6}" =~ "{3 4, 1 2, 5 6}");
418        assert_match!("{1 2, 3 _, 5 6}" =~ "{3 4, 1 2, 5 6}");
419        assert_match!("{1 2, _ _, 5 6}" =~ "{3 4, 1 2, 5 6}");
420
421        assert_match!("{_ 2}" !~ "{3 4}");
422        assert_match!("{1 _}" !~ "{3 4}");
423    }
424
425    #[test]
426    fn test_match_multiple_any_in_map_with_multiple_values() {
427        // These are false because _ is a symbol and maps guarantee
428        // uniqueness of keys. So pattern matching will fail because
429        // the pattern is a map of length 2, while the matched edn is a map
430        // of length 3. If _ were unique, all of these assertions would
431        // be true. Need to better handle pattern rules.
432
433        assert_match!("{1 2, _ 4, _ 6}" !~ "{1 2, 3 4, 5 6}");
434        assert_match!("{3 4, _ 6, _ 2}" !~ "{1 2, 3 4, 5 6}");
435        assert_match!("{5 6, _ 2, _ 4}" !~ "{1 2, 3 4, 5 6}");
436
437        assert_match!("{1 2, _ _, _ _}" !~ "{1 2, 3 4, 5 6}");
438        assert_match!("{3 4, _ _, _ _}" !~ "{1 2, 3 4, 5 6}");
439        assert_match!("{5 6, _ _, _ _}" !~ "{1 2, 3 4, 5 6}");
440        assert_match!("{_ _, 1 2, _ _}" !~ "{1 2, 3 4, 5 6}");
441        assert_match!("{_ _, 3 4, _ _}" !~ "{1 2, 3 4, 5 6}");
442        assert_match!("{_ _, 5 6, _ _}" !~ "{1 2, 3 4, 5 6}");
443        assert_match!("{_ _, _ _, 1 2}" !~ "{1 2, 3 4, 5 6}");
444        assert_match!("{_ _, _ _, 3 4}" !~ "{1 2, 3 4, 5 6}");
445        assert_match!("{_ _, _ _, 5 6}" !~ "{1 2, 3 4, 5 6}");
446
447        assert_match!("{1 2, _ _, _ _}" !~ "{3 4, 1 2, 5 6}");
448        assert_match!("{3 4, _ _, _ _}" !~ "{3 4, 1 2, 5 6}");
449        assert_match!("{5 6, _ _, _ _}" !~ "{3 4, 1 2, 5 6}");
450        assert_match!("{_ _, 1 2, _ _}" !~ "{3 4, 1 2, 5 6}");
451        assert_match!("{_ _, 3 4, _ _}" !~ "{3 4, 1 2, 5 6}");
452        assert_match!("{_ _, 5 6, _ _}" !~ "{3 4, 1 2, 5 6}");
453        assert_match!("{_ _, _ _, 1 2}" !~ "{3 4, 1 2, 5 6}");
454        assert_match!("{_ _, _ _, 3 4}" !~ "{3 4, 1 2, 5 6}");
455        assert_match!("{_ _, _ _, 5 6}" !~ "{3 4, 1 2, 5 6}");
456    }
457
458    #[test]
459    fn test_match_placeholder_simple() {
460        assert_match!("?x" =~ "nil");
461        assert_match!("?x" =~ "true");
462        assert_match!("?x" =~ "1");
463        assert_match!("?x" =~ "1N");
464        assert_match!("?x" =~ "1.0");
465        assert_match!("?x" =~ "\"a\"");
466        assert_match!("?x" =~ "_");
467        assert_match!("?x" =~ "symbol");
468        assert_match!("?x" =~ "ns/symbol");
469        assert_match!("?x" =~ ":keyword");
470        assert_match!("?x" =~ ":ns/keyword");
471        assert_match!("?x" =~ "[nil, true, 1, \"foo\", bar, :baz]");
472        assert_match!("?x" =~ "(nil, true, 1, \"foo\", bar, :baz)");
473        assert_match!("?x" =~ "#{nil, true, 1, \"foo\", bar, :baz}");
474        assert_match!("?x" =~ "{nil true, 1 \"foo\", bar :baz}");
475    }
476
477    #[test]
478    fn test_match_placeholder_in_same_collection_type_simple() {
479        assert_match!("[?x]" =~ "[1]");
480        assert_match!("(?x)" =~ "(2)");
481        assert_match!("#{?x}" =~ "#{3}");
482        assert_match!("{?x ?x}" =~ "{4 4}");
483        assert_match!("{?x ?x}" !~ "{4 5}");
484        assert_match!("{?x ?y}" =~ "{4 4}");
485        assert_match!("{?x ?y}" =~ "{4 5}");
486    }
487
488    #[test]
489    fn test_match_placeholder_in_different_collection_type_simple() {
490        assert_match!("[?x]" !~ "(1)");
491        assert_match!("(?x)" !~ "#{2}");
492        assert_match!("#{?x}" !~ "[3]");
493        assert_match!("{?x ?x}" !~ "[4 5]");
494        assert_match!("{?x ?x}" !~ "(6 7)");
495        assert_match!("{?x ?x}" !~ "#{8 9}");
496    }
497
498    #[test]
499    fn test_match_placeholder_in_vector_with_multiple_values() {
500        assert_match!("[?x ?y]" =~ "[1 2]");
501        assert_match!("[?x ?y]" =~ "[1 1]");
502        assert_match!("[?x ?x]" !~ "[1 2]");
503        assert_match!("[?x ?x]" =~ "[1 1]");
504
505        assert_match!("[1 ?x 3 ?y]" =~ "[1 2 3 4]");
506        assert_match!("[1 ?x 3 ?y]" =~ "[1 2 3 2]");
507        assert_match!("[1 ?x 3 ?x]" !~ "[1 2 3 4]");
508        assert_match!("[1 ?x 3 ?x]" =~ "[1 2 3 2]");
509
510        assert_match!("[1 [2 [3 ?x]] 5 [?y 7]]" =~ "[1 [2 [3 4]] 5 [6 7]]");
511        assert_match!("[1 [2 [3 ?x]] 5 [?y 7]]" =~ "[1 [2 [3 4]] 5 [4 7]]");
512        assert_match!("[1 [2 [3 ?x]] 5 [?x 7]]" !~ "[1 [2 [3 4]] 5 [6 7]]");
513        assert_match!("[1 [2 [3 ?x]] 5 [?y 7]]" =~ "[1 [2 [3 4]] 5 [4 7]]");
514
515        assert_match!("[?x ?y ?x ?y]" =~ "[1 2 1 2]");
516        assert_match!("[?x ?y ?x ?y]" !~ "[1 2 2 1]");
517
518        assert_match!("[[?x ?y] [?x ?y]]" =~ "[[1 2] [1 2]]");
519        assert_match!("[[?x ?y] [?x ?y]]" !~ "[[1 2] [2 1]]");
520    }
521
522    #[test]
523    fn test_match_placeholder_in_list_with_multiple_values() {
524        assert_match!("(?x ?y)" =~ "(1 2)");
525        assert_match!("(?x ?y)" =~ "(1 1)");
526        assert_match!("(?x ?x)" !~ "(1 2)");
527        assert_match!("(?x ?x)" =~ "(1 1)");
528
529        assert_match!("(1 ?x 3 ?y)" =~ "(1 2 3 4)");
530        assert_match!("(1 ?x 3 ?y)" =~ "(1 2 3 2)");
531        assert_match!("(1 ?x 3 ?x)" !~ "(1 2 3 4)");
532        assert_match!("(1 ?x 3 ?x)" =~ "(1 2 3 2)");
533
534        assert_match!("(1 (2 (3 ?x)) 5 (?y 7))" =~ "(1 (2 (3 4)) 5 (6 7))");
535        assert_match!("(1 (2 (3 ?x)) 5 (?y 7))" =~ "(1 (2 (3 4)) 5 (4 7))");
536        assert_match!("(1 (2 (3 ?x)) 5 (?x 7))" !~ "(1 (2 (3 4)) 5 (6 7))");
537        assert_match!("(1 (2 (3 ?x)) 5 (?y 7))" =~ "(1 (2 (3 4)) 5 (4 7))");
538
539        assert_match!("(?x ?y ?x ?y)" =~ "(1 2 1 2)");
540        assert_match!("(?x ?y ?x ?y)" !~ "(1 2 2 1)");
541
542        assert_match!("((?x ?y) (?x ?y))" =~ "((1 2) (1 2))");
543        assert_match!("((?x ?y) (?x ?y))" !~ "((1 2) (2 1))");
544    }
545
546    #[test]
547    fn test_match_placeholder_in_set_with_multiple_values() {
548        assert_match!("#{?x ?y}" =~ "#{1 2}");
549        assert_match!("#{?x ?y}" !~ "#{1 1}");
550        assert_match!("#{?x ?x}" !~ "#{1 2}");
551        assert_match!("#{?x ?x}" =~ "#{1 1}");
552
553        assert_match!("#{1 ?x 3 ?y}" =~ "#{1 2 3 4}");
554        assert_match!("#{1 ?x 3 ?y}" !~ "#{1 2 3 2}");
555        assert_match!("#{1 ?x 3 ?x}" !~ "#{1 2 3 4}");
556        assert_match!("#{1 ?x 3 ?x}" =~ "#{1 2 3 2}");
557
558        assert_match!("#{1 #{2 #{3 ?x}} 5 #{?y 7}}" =~ "#{1 #{2 #{3 4}} 5 #{6 7}}");
559        assert_match!("#{1 #{2 #{3 ?x}} 5 #{?y 7}}" =~ "#{1 #{2 #{3 4}} 5 #{4 7}}");
560        assert_match!("#{1 #{2 #{3 ?x}} 5 #{?x 7}}" !~ "#{1 #{2 #{3 4}} 5 #{6 7}}");
561        assert_match!("#{1 #{2 #{3 ?x}} 5 #{?y 7}}" =~ "#{1 #{2 #{3 4}} 5 #{4 7}}");
562
563        assert_match!("#{?x ?y ?x ?y}" =~ "#{1 2 1 2}");
564        assert_match!("#{?x ?y ?x ?y}" =~ "#{1 2 2 1}");
565
566        assert_match!("#{#{?x ?y} #{?x ?y}}" =~ "#{#{1 2} #{1 2}}");
567        assert_match!("#{#{?x ?y} #{?x ?y}}" =~ "#{#{1 2} #{2 1}}");
568    }
569
570    #[test]
571    fn test_match_placeholder_in_map_with_multiple_values() {
572        assert_match!("{?x ?y}" =~ "{1 2}");
573        assert_match!("{?x ?y}" =~ "{1 1}");
574        assert_match!("{?x ?x}" !~ "{1 2}");
575        assert_match!("{?x ?x}" =~ "{1 1}");
576
577        assert_match!("{1 ?x, 3 ?y}" =~ "{1 2, 3 4}");
578        assert_match!("{1 ?x, 3 ?y}" =~ "{1 2, 3 2}");
579        assert_match!("{1 ?x, 3 ?x}" !~ "{1 2, 3 4}");
580        assert_match!("{1 ?x, 3 ?x}" =~ "{1 2, 3 2}");
581
582        assert_match!("{1 {2 {3 ?x}}, 5 {?y 7}}" =~ "{1 {2 {3 4}}, 5 {6 7}}");
583        assert_match!("{1 {2 {3 ?x}}, 5 {?y 7}}" =~ "{1 {2 {3 4}}, 5 {4 7}}");
584        assert_match!("{1 {2 {3 ?x}}, 5 {?x 7}}" !~ "{1 {2 {3 4}}, 5 {6 7}}");
585        assert_match!("{1 {2 {3 ?x}}, 5 {?y 7}}" =~ "{1 {2 {3 4}}, 5 {4 7}}");
586
587        assert_match!("{?x ?y, ?x ?y}" =~ "{1 2, 1 2}");
588        assert_match!("{?x ?y, ?x ?y}" !~ "{1 2, 2 1}");
589
590        assert_match!("{{?x ?y}, {?x ?y}}" =~ "{{1 2}, {1 2}}");
591        assert_match!("{{?x ?y}, {?x ?y}}" !~ "{{1 2}, {2 1}}");
592    }
593
594    #[test]
595    fn test_match_placeholder_in_different_value_types() {
596        assert_match!("{1 {2 [3 ?x]}, 5 (?y 7)}" =~ "{1 {2 [3 4]}, 5 (6 7)}");
597        assert_match!("{1 {2 [3 ?x]}, 5 (?y 7)}" =~ "{1 {2 [3 4]}, 5 (4 7)}");
598        assert_match!("{1 {2 [3 ?x]}, 5 (?x 7)}" !~ "{1 {2 [3 4]}, 5 (6 7)}");
599        assert_match!("{1 {2 [3 ?x]}, 5 (?y 7)}" =~ "{1 {2 [3 4]}, 5 (4 7)}");
600
601        assert_match!("{?x {?x [?x ?x]}, ?x (?x ?x)}" !~ "{1 {2 [3 4]}, 5 (6 7)}");
602        assert_match!("{?x {?x [?x ?x]}, ?x (?x ?x)}" =~ "{1 {1 [1 1]}, 1 (1 1)}");
603
604        assert_match!("[#{?x ?y} ?x]" =~ "[#{1 2} 1]");
605        assert_match!("[#{?x ?y} ?y]" =~ "[#{1 2} 2]");
606    }
607}
edn/matcher.rs

edn/
matcher.rs
