ocas_rewrite/
matcher.rs

1//! Pattern matching engine for oCAS.
2//!
3//! The matcher binds [`Pattern`] wildcards to [`Atom`] sub-expressions.
4//! Associative/commutative matching for `Add`/`Mul` uses full backtracking
5//! search with a budget to prevent pathological explosion.  Sequence wildcards
6//! are supported in all argument-list contexts (`Add`, `Mul`, `Fun`).
7
8use ocas_atom::{Atom, AtomNode, Symbol};
9use ocas_core::FastHashMap as HashMap;
10
11use crate::pattern::{Pattern, WildcardLevel};
12
13/// Default maximum number of backtrack attempts per AC match.
14pub const DEFAULT_MAX_BACKTRACKS: usize = 10_000;
15
16/// A collection of wildcard bindings produced by a successful match.
17#[derive(Debug, Clone, Default)]
18pub struct Bindings<'a> {
19    map: HashMap<Symbol, MatchValue<'a>>,
20}
21
22impl<'a> Bindings<'a> {
23    pub fn new() -> Self {
24        Self::default()
25    }
26    pub fn get(&self, name: Symbol) -> Option<&MatchValue<'a>> {
27        self.map.get(&name)
28    }
29    fn insert_single(&mut self, name: Symbol, value: Atom<'a>) -> Result<(), MatchError> {
30        match self.map.get(&name) {
31            Some(MatchValue::Single(existing)) if *existing == value => Ok(()),
32            Some(_) => Err(MatchError::InconsistentBinding),
33            None => {
34                self.map.insert(name, MatchValue::Single(value));
35                Ok(())
36            }
37        }
38    }
39    fn insert_sequence(&mut self, name: Symbol, value: &'a [Atom<'a>]) -> Result<(), MatchError> {
40        match self.map.get(&name) {
41            Some(MatchValue::Sequence(existing)) if *existing == value => Ok(()),
42            Some(_) => Err(MatchError::InconsistentBinding),
43            None => {
44                self.map.insert(name, MatchValue::Sequence(value));
45                Ok(())
46            }
47        }
48    }
49    fn remove(&mut self, name: Symbol) {
50        self.map.remove(&name);
51    }
52}
53
54#[derive(Debug, Clone, Copy, PartialEq, Eq)]
55pub enum MatchValue<'a> {
56    Single(Atom<'a>),
57    Sequence(&'a [Atom<'a>]),
58}
59
60#[derive(Debug, Clone, Copy, PartialEq, Eq)]
61pub enum MatchError {
62    NoMatch,
63    InconsistentBinding,
64    BudgetExhausted,
65}
66
67impl std::fmt::Display for MatchError {
68    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
69        match self {
70            MatchError::NoMatch => write!(f, "pattern did not match"),
71            MatchError::InconsistentBinding => write!(f, "inconsistent wildcard binding"),
72            MatchError::BudgetExhausted => write!(f, "backtrack budget exhausted"),
73        }
74    }
75}
76impl std::error::Error for MatchError {}
77
78pub fn match_pattern<'a>(pattern: Pattern<'a>, atom: Atom<'a>) -> Result<Bindings<'a>, MatchError> {
79    match_pattern_with_budget(pattern, atom, DEFAULT_MAX_BACKTRACKS)
80}
81
82pub fn match_pattern_with_budget<'a>(
83    pattern: Pattern<'a>,
84    atom: Atom<'a>,
85    max_backtracks: usize,
86) -> Result<Bindings<'a>, MatchError> {
87    let mut bindings = Bindings::new();
88    let mut backtrack_count = 0usize;
89    match_atom(
90        &mut bindings,
91        pattern,
92        atom,
93        &mut backtrack_count,
94        max_backtracks,
95    )?;
96    Ok(bindings)
97}
98
99fn match_atom<'a>(
100    bindings: &mut Bindings<'a>,
101    pattern: Pattern<'a>,
102    atom: Atom<'a>,
103    backtrack_count: &mut usize,
104    max_backtracks: usize,
105) -> Result<(), MatchError> {
106    if *backtrack_count >= max_backtracks {
107        return Err(MatchError::BudgetExhausted);
108    }
109    match pattern {
110        Pattern::Literal(p) => {
111            if p == atom {
112                Ok(())
113            } else {
114                Err(MatchError::NoMatch)
115            }
116        }
117        Pattern::Wildcard(name, WildcardLevel::Single) => bindings.insert_single(name, atom),
118        Pattern::Wildcard(name, WildcardLevel::Sequence) => match atom.node() {
119            AtomNode::Add(args) | AtomNode::Mul(args) | AtomNode::Fun(_, args) => {
120                if args.is_empty() {
121                    Err(MatchError::NoMatch)
122                } else {
123                    bindings.insert_sequence(name, args)
124                }
125            }
126            _ => Err(MatchError::NoMatch),
127        },
128        Pattern::Wildcard(name, WildcardLevel::NullSequence) => match atom.node() {
129            AtomNode::Add(args) | AtomNode::Mul(args) | AtomNode::Fun(_, args) => {
130                bindings.insert_sequence(name, args)
131            }
132            _ => Err(MatchError::NoMatch),
133        },
134        Pattern::Add(pats) => match atom.node() {
135            AtomNode::Add(args) => {
136                match_nary(bindings, &pats, args, true, backtrack_count, max_backtracks)
137            }
138            _ => Err(MatchError::NoMatch),
139        },
140        Pattern::Mul(pats) => match atom.node() {
141            AtomNode::Mul(args) => {
142                match_nary(bindings, &pats, args, true, backtrack_count, max_backtracks)
143            }
144            _ => Err(MatchError::NoMatch),
145        },
146        Pattern::Pow(p_box) => match atom.node() {
147            AtomNode::Pow(base, exp) => {
148                let (p_base, p_exp) = *p_box;
149                match_atom(bindings, p_base, *base, backtrack_count, max_backtracks)?;
150                match_atom(bindings, p_exp, *exp, backtrack_count, max_backtracks)
151            }
152            _ => Err(MatchError::NoMatch),
153        },
154        Pattern::Fun(p_name, p_args) => match atom.node() {
155            AtomNode::Fun(name, args) if *name == p_name => match_nary(
156                bindings,
157                &p_args,
158                args,
159                false,
160                backtrack_count,
161                max_backtracks,
162            ),
163            _ => Err(MatchError::NoMatch),
164        },
165    }
166}
167
168fn match_nary<'a>(
169    bindings: &'_ mut Bindings<'a>,
170    patterns: &[Pattern<'a>],
171    atoms: &'a [Atom<'a>],
172    associative_commutative: bool,
173    backtrack_count: &mut usize,
174    max_backtracks: usize,
175) -> Result<(), MatchError> {
176    if *backtrack_count >= max_backtracks {
177        return Err(MatchError::BudgetExhausted);
178    }
179    if patterns.is_empty() {
180        return if atoms.is_empty() {
181            Ok(())
182        } else {
183            Err(MatchError::NoMatch)
184        };
185    }
186    if associative_commutative {
187        let mut sorted: Vec<Atom<'a>> = atoms.to_vec();
188        sorted.sort();
189        let mut used = vec![false; sorted.len()];
190        match_nary_ac(
191            bindings,
192            patterns,
193            &sorted,
194            &mut used,
195            0,
196            backtrack_count,
197            max_backtracks,
198        )
199    } else {
200        match_nary_ordered(
201            bindings,
202            patterns,
203            atoms,
204            0,
205            0,
206            backtrack_count,
207            max_backtracks,
208        )
209    }
210}
211
212// ---- ordered matching (Fun args) with sequence-wildcard support at any position ----
213
214fn match_nary_ordered<'a>(
215    bindings: &mut Bindings<'a>,
216    patterns: &[Pattern<'a>],
217    atoms: &'a [Atom<'a>],
218    pat_idx: usize,
219    atom_idx: usize,
220    backtrack_count: &mut usize,
221    max_backtracks: usize,
222) -> Result<(), MatchError> {
223    if *backtrack_count >= max_backtracks {
224        return Err(MatchError::BudgetExhausted);
225    }
226    if pat_idx >= patterns.len() {
227        return if atom_idx >= atoms.len() {
228            Ok(())
229        } else {
230            Err(MatchError::NoMatch)
231        };
232    }
233    let pat = &patterns[pat_idx];
234    match pat {
235        Pattern::Wildcard(name, WildcardLevel::NullSequence) => {
236            let remaining = atoms.len().saturating_sub(atom_idx);
237            for len in 0..=remaining {
238                let slice = &atoms[atom_idx..atom_idx + len];
239                let mut probe = bindings.clone();
240                if probe.insert_sequence(*name, slice).is_err() {
241                    continue;
242                }
243                *backtrack_count += 1;
244                match match_nary_ordered(
245                    &mut probe,
246                    patterns,
247                    atoms,
248                    pat_idx + 1,
249                    atom_idx + len,
250                    backtrack_count,
251                    max_backtracks,
252                ) {
253                    Ok(()) => {
254                        *bindings = probe;
255                        return Ok(());
256                    }
257                    Err(MatchError::BudgetExhausted) => return Err(MatchError::BudgetExhausted),
258                    Err(_) => {}
259                }
260            }
261            Err(MatchError::NoMatch)
262        }
263        Pattern::Wildcard(name, WildcardLevel::Sequence) => {
264            let remaining = atoms.len().saturating_sub(atom_idx);
265            if remaining == 0 {
266                return Err(MatchError::NoMatch);
267            }
268            for len in 1..=remaining {
269                let slice = &atoms[atom_idx..atom_idx + len];
270                let mut probe = bindings.clone();
271                if probe.insert_sequence(*name, slice).is_err() {
272                    continue;
273                }
274                *backtrack_count += 1;
275                match match_nary_ordered(
276                    &mut probe,
277                    patterns,
278                    atoms,
279                    pat_idx + 1,
280                    atom_idx + len,
281                    backtrack_count,
282                    max_backtracks,
283                ) {
284                    Ok(()) => {
285                        *bindings = probe;
286                        return Ok(());
287                    }
288                    Err(MatchError::BudgetExhausted) => return Err(MatchError::BudgetExhausted),
289                    Err(_) => {}
290                }
291            }
292            Err(MatchError::NoMatch)
293        }
294        Pattern::Wildcard(name, WildcardLevel::Single) => {
295            if atom_idx >= atoms.len() {
296                return Err(MatchError::NoMatch);
297            }
298            let atom = atoms[atom_idx];
299            let mut probe = bindings.clone();
300            if probe.insert_single(*name, atom).is_err() {
301                return Err(MatchError::NoMatch);
302            }
303            *backtrack_count += 1;
304            match_nary_ordered(
305                &mut probe,
306                patterns,
307                atoms,
308                pat_idx + 1,
309                atom_idx + 1,
310                backtrack_count,
311                max_backtracks,
312            )
313            .map(|()| {
314                *bindings = probe;
315            })
316        }
317        _ => {
318            if atom_idx >= atoms.len() {
319                return Err(MatchError::NoMatch);
320            }
321            let mut probe = bindings.clone();
322            match_atom(
323                &mut probe,
324                pat.clone(),
325                atoms[atom_idx],
326                backtrack_count,
327                max_backtracks,
328            )?;
329            *backtrack_count += 1;
330            match_nary_ordered(
331                &mut probe,
332                patterns,
333                atoms,
334                pat_idx + 1,
335                atom_idx + 1,
336                backtrack_count,
337                max_backtracks,
338            )
339            .map(|()| {
340                *bindings = probe;
341            })
342        }
343    }
344}
345
346// ---- AC matching (Add/Mul) — backtracking over sorted atoms ----
347
348fn match_nary_ac<'a>(
349    bindings: &mut Bindings<'a>,
350    patterns: &[Pattern<'a>],
351    sorted_atoms: &[Atom<'a>],
352    used: &mut [bool],
353    pat_idx: usize,
354    backtrack_count: &mut usize,
355    max_backtracks: usize,
356) -> Result<(), MatchError> {
357    if *backtrack_count >= max_backtracks {
358        return Err(MatchError::BudgetExhausted);
359    }
360    if pat_idx >= patterns.len() {
361        return if used.iter().all(|&u| u) {
362            Ok(())
363        } else {
364            Err(MatchError::NoMatch)
365        };
366    }
367
368    let pat = &patterns[pat_idx];
369    match pat {
370        Pattern::Literal(v) => {
371            for i in 0..sorted_atoms.len() {
372                if used[i] || sorted_atoms[i] != *v {
373                    continue;
374                }
375                used[i] = true;
376                *backtrack_count += 1;
377                match match_nary_ac(
378                    bindings,
379                    patterns,
380                    sorted_atoms,
381                    used,
382                    pat_idx + 1,
383                    backtrack_count,
384                    max_backtracks,
385                ) {
386                    Ok(()) => return Ok(()),
387                    Err(MatchError::BudgetExhausted) => return Err(MatchError::BudgetExhausted),
388                    Err(_) => {
389                        used[i] = false;
390                    }
391                }
392            }
393            Err(MatchError::NoMatch)
394        }
395        Pattern::Wildcard(name, WildcardLevel::Single) => {
396            for i in 0..sorted_atoms.len() {
397                if used[i] {
398                    continue;
399                }
400                let atom = sorted_atoms[i];
401                match bindings.get(*name).copied() {
402                    Some(MatchValue::Single(existing)) if existing == atom => {
403                        used[i] = true;
404                        match match_nary_ac(
405                            bindings,
406                            patterns,
407                            sorted_atoms,
408                            used,
409                            pat_idx + 1,
410                            backtrack_count,
411                            max_backtracks,
412                        ) {
413                            Ok(()) => return Ok(()),
414                            Err(MatchError::BudgetExhausted) => {
415                                used[i] = false;
416                                return Err(MatchError::BudgetExhausted);
417                            }
418                            Err(_) => {
419                                used[i] = false;
420                            }
421                        }
422                    }
423                    Some(_) => continue,
424                    None => {
425                        used[i] = true;
426                        let _ = bindings.insert_single(*name, atom);
427                        *backtrack_count += 1;
428                        match match_nary_ac(
429                            bindings,
430                            patterns,
431                            sorted_atoms,
432                            used,
433                            pat_idx + 1,
434                            backtrack_count,
435                            max_backtracks,
436                        ) {
437                            Ok(()) => return Ok(()),
438                            Err(MatchError::BudgetExhausted) => {
439                                bindings.remove(*name);
440                                used[i] = false;
441                                return Err(MatchError::BudgetExhausted);
442                            }
443                            Err(_) => {
444                                bindings.remove(*name);
445                                used[i] = false;
446                            }
447                        }
448                    }
449                }
450            }
451            Err(MatchError::NoMatch)
452        }
453        Pattern::Wildcard(name, WildcardLevel::NullSequence) => {
454            let free: Vec<usize> = (0..sorted_atoms.len()).filter(|&i| !used[i]).collect();
455            enumerate_subsets(
456                bindings,
457                patterns,
458                sorted_atoms,
459                used,
460                pat_idx,
461                *name,
462                &free,
463                0,
464                free.len(),
465                0,
466                true,
467                backtrack_count,
468                max_backtracks,
469            )
470        }
471        Pattern::Wildcard(name, WildcardLevel::Sequence) => {
472            let free: Vec<usize> = (0..sorted_atoms.len()).filter(|&i| !used[i]).collect();
473            if free.is_empty() {
474                return Err(MatchError::NoMatch);
475            }
476            enumerate_subsets(
477                bindings,
478                patterns,
479                sorted_atoms,
480                used,
481                pat_idx,
482                *name,
483                &free,
484                0,
485                free.len(),
486                1,
487                false,
488                backtrack_count,
489                max_backtracks,
490            )
491        }
492        _ => {
493            for i in 0..sorted_atoms.len() {
494                if used[i] {
495                    continue;
496                }
497                let mut probe = bindings.clone();
498                if let Ok(()) = match_atom(
499                    &mut probe,
500                    pat.clone(),
501                    sorted_atoms[i],
502                    backtrack_count,
503                    max_backtracks,
504                ) {
505                    used[i] = true;
506                    *backtrack_count += 1;
507                    match match_nary_ac(
508                        &mut probe,
509                        patterns,
510                        sorted_atoms,
511                        used,
512                        pat_idx + 1,
513                        backtrack_count,
514                        max_backtracks,
515                    ) {
516                        Ok(()) => {
517                            *bindings = probe;
518                            return Ok(());
519                        }
520                        Err(MatchError::BudgetExhausted) => {
521                            used[i] = false;
522                            return Err(MatchError::BudgetExhausted);
523                        }
524                        Err(_) => {
525                            used[i] = false;
526                        }
527                    }
528                }
529            }
530            Err(MatchError::NoMatch)
531        }
532    }
533}
534
535#[allow(clippy::too_many_arguments)]
536fn enumerate_subsets<'a>(
537    bindings: &mut Bindings<'a>,
538    patterns: &[Pattern<'a>],
539    sorted_atoms: &[Atom<'a>],
540    used: &mut [bool],
541    pat_idx: usize,
542    name: Symbol,
543    free: &[usize],
544    start: usize,
545    total_free: usize,
546    min_size: usize,
547    allow_empty: bool,
548    backtrack_count: &mut usize,
549    max_backtracks: usize,
550) -> Result<(), MatchError> {
551    if *backtrack_count >= max_backtracks {
552        return Err(MatchError::BudgetExhausted);
553    }
554    let rem_pats = patterns.len().saturating_sub(pat_idx + 1);
555    let max_size = total_free
556        .saturating_sub(start)
557        .saturating_sub(rem_pats)
558        .min(total_free.saturating_sub(start));
559    let min = if allow_empty { 0 } else { min_size };
560    for size in min..=max_size {
561        let mut chosen: Vec<usize> = Vec::with_capacity(size);
562        let result = enumerate_combinations_step(
563            bindings,
564            patterns,
565            sorted_atoms,
566            used,
567            pat_idx,
568            name,
569            free,
570            start,
571            size,
572            0,
573            &mut chosen,
574            backtrack_count,
575            max_backtracks,
576        );
577        match result {
578            SubsetResult::Found => return Ok(()),
579            SubsetResult::BudgetExhausted => return Err(MatchError::BudgetExhausted),
580            SubsetResult::NoMatch => {}
581        }
582    }
583    Err(MatchError::NoMatch)
584}
585
586enum SubsetResult {
587    Found,
588    NoMatch,
589    BudgetExhausted,
590}
591
592#[allow(clippy::too_many_arguments)]
593fn enumerate_combinations_step<'a>(
594    bindings: &mut Bindings<'a>,
595    patterns: &[Pattern<'a>],
596    sorted_atoms: &[Atom<'a>],
597    used: &mut [bool],
598    pat_idx: usize,
599    name: Symbol,
600    free: &[usize],
601    start: usize,
602    remaining: usize,
603    _depth: usize,
604    chosen: &mut Vec<usize>,
605    backtrack_count: &mut usize,
606    max_backtracks: usize,
607) -> SubsetResult {
608    if *backtrack_count >= max_backtracks {
609        return SubsetResult::BudgetExhausted;
610    }
611    if remaining == 0 {
612        for &idx in chosen.iter() {
613            used[idx] = true;
614        }
615        let slice: Vec<Atom<'a>> = chosen.iter().map(|&i| sorted_atoms[i]).collect();
616        let leaked: &'a [Atom<'a>] = Vec::leak(slice);
617        let mut probe = bindings.clone();
618        if let Ok(()) = probe.insert_sequence(name, leaked) {
619            *backtrack_count += 1;
620            match match_nary_ac(
621                &mut probe,
622                patterns,
623                sorted_atoms,
624                used,
625                pat_idx + 1,
626                backtrack_count,
627                max_backtracks,
628            ) {
629                Ok(()) => {
630                    *bindings = probe;
631                    return SubsetResult::Found;
632                }
633                Err(MatchError::BudgetExhausted) => {
634                    for &idx in chosen.iter() {
635                        used[idx] = false;
636                    }
637                    return SubsetResult::BudgetExhausted;
638                }
639                Err(_) => {}
640            }
641        }
642        for &idx in chosen.iter() {
643            used[idx] = false;
644        }
645        return SubsetResult::NoMatch;
646    }
647    let needed = remaining;
648    let available = free.len().saturating_sub(start);
649    if available < needed {
650        return SubsetResult::NoMatch;
651    }
652    for i in start..=free.len().saturating_sub(needed) {
653        chosen.push(free[i]);
654        match enumerate_combinations_step(
655            bindings,
656            patterns,
657            sorted_atoms,
658            used,
659            pat_idx,
660            name,
661            free,
662            i + 1,
663            remaining - 1,
664            _depth + 1,
665            chosen,
666            backtrack_count,
667            max_backtracks,
668        ) {
669            SubsetResult::Found => return SubsetResult::Found,
670            SubsetResult::BudgetExhausted => {
671                chosen.pop();
672                return SubsetResult::BudgetExhausted;
673            }
674            SubsetResult::NoMatch => {}
675        }
676        chosen.pop();
677    }
678    SubsetResult::NoMatch
679}
680
681// ===========================================================================
682// Tests
683// ===========================================================================
684
685#[cfg(test)]
686mod tests {
687    use super::*;
688    use ocas_atom::AtomArena;
689    use ocas_core::arena::Arena;
690
691    struct VecAlloc;
692    impl<'a> crate::pattern::PatternAlloc<'a> for VecAlloc {
693        fn alloc_slice(&self, items: &[Pattern<'a>]) -> &'a [Pattern<'a>] {
694            Box::leak(items.to_vec().into_boxed_slice())
695        }
696    }
697
698    fn pat_expr<'a>(ctx: &'a AtomArena<'a>, _alloc: &'a VecAlloc, s: &'a str) -> Pattern<'a> {
699        use ocas_parse;
700        let atom = ocas_parse::parse(ctx, s).expect("parse");
701        Pattern::from_atom(&(), atom)
702    }
703
704    #[test]
705    fn match_single_wildcard() {
706        let arena = Arena::new();
707        let ctx = AtomArena::new(&arena);
708        let x = ctx.var("x");
709        let pat = Pattern::Wildcard(Symbol::new("w"), WildcardLevel::Single);
710        let bindings = match_pattern(pat, x).unwrap();
711        assert!(matches!(bindings.get(Symbol::new("w")), Some(MatchValue::Single(v)) if *v == x));
712    }
713
714    #[test]
715    fn match_add_two_singles() {
716        let arena = Arena::new();
717        let ctx = AtomArena::new(&arena);
718        let x = ctx.var("x");
719        let y = ctx.var("y");
720        let sum = ctx.add(&[x, y]);
721        let pat = Pattern::Add(vec![
722            Pattern::Wildcard(Symbol::new("a"), WildcardLevel::Single),
723            Pattern::Wildcard(Symbol::new("b"), WildcardLevel::Single),
724        ]);
725        let bindings = match_pattern(pat, sum).unwrap();
726        assert!(matches!(bindings.get(Symbol::new("a")), Some(MatchValue::Single(v)) if *v == x));
727        assert!(matches!(bindings.get(Symbol::new("b")), Some(MatchValue::Single(v)) if *v == y));
728    }
729
730    #[test]
731    fn ac_match_with_literal() {
732        let arena = Arena::new();
733        let ctx = AtomArena::new(&arena);
734        let x = ctx.var("x");
735        let y = ctx.var("y");
736        let sum = ctx.add(&[x, y]);
737        let pat = Pattern::Add(vec![
738            Pattern::Wildcard(Symbol::new("a"), WildcardLevel::Single),
739            Pattern::Literal(y),
740        ]);
741        let bindings = match_pattern(pat, sum).unwrap();
742        assert!(matches!(bindings.get(Symbol::new("a")), Some(MatchValue::Single(v)) if *v == x));
743    }
744
745    #[test]
746    fn ac_mismatched_count_fails() {
747        let arena = Arena::new();
748        let ctx = AtomArena::new(&arena);
749        let x = ctx.var("x");
750        let y = ctx.var("y");
751        let z = ctx.var("z");
752        let sum = ctx.add(&[x, y, z]);
753        let pat = Pattern::Add(vec![
754            Pattern::Wildcard(Symbol::new("a"), WildcardLevel::Single),
755            Pattern::Wildcard(Symbol::new("b"), WildcardLevel::Single),
756        ]);
757        assert!(matches!(match_pattern(pat, sum), Err(MatchError::NoMatch)));
758    }
759
760    #[test]
761    fn inconsistent_binding_fails() {
762        let arena = Arena::new();
763        let ctx = AtomArena::new(&arena);
764        let x = ctx.var("x");
765        let y = ctx.var("y");
766        let sum = ctx.add(&[x, y]);
767        let pat = Pattern::Add(vec![
768            Pattern::Wildcard(Symbol::new("w"), WildcardLevel::Single),
769            Pattern::Wildcard(Symbol::new("w"), WildcardLevel::Single),
770        ]);
771        assert!(matches!(
772            match_pattern(pat, sum),
773            Err(MatchError::InconsistentBinding | MatchError::NoMatch)
774        ));
775    }
776
777    #[test]
778    fn fun_trailing_null_sequence() {
779        let arena = Arena::new();
780        let ctx = AtomArena::new(&arena);
781        let x = ctx.var("x");
782        let y = ctx.var("y");
783        let z = ctx.var("z");
784        let f = ctx.fun("f", &[x, y, z]);
785        let alloc = VecAlloc;
786        let pattern_str = "f(x_, ___rest)";
787        let pat = pat_expr(&ctx, &alloc, pattern_str);
788        let bindings = match_pattern(pat, f).unwrap();
789        let rest = bindings.get(Symbol::new("rest")).unwrap();
790        assert!(matches!(rest, MatchValue::Sequence(s) if s.len() == 2));
791    }
792
793    #[test]
794    fn ac_three_wildcards_four_terms() {
795        let arena = Arena::new();
796        let ctx = AtomArena::new(&arena);
797        let w = ctx.var("w");
798        let x = ctx.var("x");
799        let y = ctx.var("y");
800        let z = ctx.var("z");
801        let sum = ctx.add(&[w, x, y, z]);
802        let pat = Pattern::Add(vec![
803            Pattern::Wildcard(Symbol::new("a"), WildcardLevel::Single),
804            Pattern::Wildcard(Symbol::new("b"), WildcardLevel::Single),
805            Pattern::Wildcard(Symbol::new("c"), WildcardLevel::Single),
806        ]);
807        assert!(matches!(match_pattern(pat, sum), Err(MatchError::NoMatch)));
808    }
809
810    #[test]
811    fn ac_sequence_wildcard_in_add() {
812        let arena = Arena::new();
813        let ctx = AtomArena::new(&arena);
814        let a = ctx.var("a");
815        let b = ctx.var("b");
816        let c = ctx.var("c");
817        let sum = ctx.add(&[a, b, c]);
818        let pat = Pattern::Add(vec![
819            Pattern::Wildcard(Symbol::new("x"), WildcardLevel::Single),
820            Pattern::Wildcard(Symbol::new("rest"), WildcardLevel::Sequence),
821        ]);
822        let bindings = match_pattern(pat, sum).unwrap();
823        let rest = bindings.get(Symbol::new("rest")).unwrap();
824        assert!(matches!(rest, MatchValue::Sequence(s) if s.len() == 2));
825    }
826
827    #[test]
828    fn ac_null_sequence_consumes_all() {
829        let arena = Arena::new();
830        let ctx = AtomArena::new(&arena);
831        let a = ctx.var("a");
832        let sum = ctx.add(&[a]);
833        let pat = Pattern::Add(vec![Pattern::Wildcard(
834            Symbol::new("rest"),
835            WildcardLevel::NullSequence,
836        )]);
837        let bindings = match_pattern(pat, sum).unwrap();
838        let rest = bindings.get(Symbol::new("rest")).unwrap();
839        assert!(matches!(rest, MatchValue::Sequence(s) if s.len() == 1));
840    }
841
842    #[test]
843    fn ordered_sequence_mid_function() {
844        let arena = Arena::new();
845        let ctx = AtomArena::new(&arena);
846        let a = ctx.var("a");
847        let b = ctx.var("b");
848        let c = ctx.var("c");
849        let f = ctx.fun("f", &[a, b, c]);
850        let alloc = VecAlloc;
851        let pattern_str = "f(x_, __mid, z_)";
852        let pat = pat_expr(&ctx, &alloc, pattern_str);
853        let bindings = match_pattern(pat, f).unwrap();
854        let mid = bindings.get(Symbol::new("mid")).unwrap();
855        assert!(matches!(mid, MatchValue::Sequence(s) if s.len() == 1));
856    }
857}
ocas_rewrite/matcher.rs

ocas_rewrite/
matcher.rs
