cl_ast/ast/
macro_matcher.rs

1//! Implements pattern matching
2
3use super::*;
4use std::collections::HashMap;
5
6/// Stores a substitution from meta-identifiers to values
7#[derive(Clone, Debug)]
8pub struct Subst<A: AstTypes> {
9    pub exp: HashMap<A::MacroId, Expr<A>>,
10    pub pat: HashMap<A::MacroId, Pat<A>>,
11}
12
13impl<A: AstTypes> Default for Subst<A> {
14    fn default() -> Self {
15        Self { exp: Default::default(), pat: Default::default() }
16    }
17}
18impl<A: AstTypes> Subst<A> {
19    fn add_pat(&mut self, name: A::MacroId, pat: &Pat<A>) -> bool {
20        if self.exp.contains_key(&name) {
21            return false;
22        }
23        if let Some(entry) = self.pat.get(&name) {
24            return entry == pat;
25        }
26        self.pat.insert(name, pat.clone()).is_none()
27    }
28    fn add_expr(&mut self, name: A::MacroId, exp: &Expr<A>) -> bool {
29        if self.pat.contains_key(&name) {
30            return false;
31        }
32        if let Some(entry) = self.exp.get(&name) {
33            return entry == exp;
34        }
35        self.exp.insert(name, exp.clone()).is_none()
36    }
37}
38
39pub trait Match<A: AstTypes> {
40    /// Applies a substitution rule from `pat` to `template` on `self`
41    fn apply_rule(&mut self, pat: &Self, template: &Self) -> bool
42    where Self: Sized + Clone {
43        let Some(sub) = self.match_with(pat) else {
44            return false;
45        };
46
47        *self = template.clone();
48        self.apply(&sub);
49
50        true
51    }
52
53    /// With self as the pattern, recursively applies the Subst
54    fn apply(&mut self, sub: &Subst<A>);
55
56    /// Implements recursive Subst-building for Self
57    fn recurse(sub: &mut Subst<A>, pat: &Self, expr: &Self) -> bool;
58
59    /// Matches self against the provided pattern
60    fn match_with(&self, pat: &Self) -> Option<Subst<A>> {
61        let mut sub = Subst::default();
62        Match::recurse(&mut sub, pat, self).then_some(sub)
63    }
64}
65
66impl<M: Match<A> + Annotation, A: AstTypes> Match<A> for At<M, A> {
67    fn recurse(sub: &mut Subst<A>, pat: &Self, expr: &Self) -> bool {
68        Match::recurse(sub, &pat.0, &expr.0)
69    }
70
71    fn apply(&mut self, sub: &Subst<A>) {
72        self.0.apply(sub);
73    }
74}
75
76impl<A: AstTypes> Match<A> for Bind<A> {
77    fn recurse(sub: &mut Subst<A>, pat: &Self, expr: &Self) -> bool {
78        let (Self(pat_kind, _, pat_pat, pat_expr), Self(expr_kind, _, expr_pat, expr_expr)) =
79            (pat, expr);
80        pat_kind == expr_kind
81            && Match::recurse(sub, pat_pat, expr_pat)
82            && Match::recurse(sub, pat_expr, expr_expr)
83    }
84
85    fn apply(&mut self, sub: &Subst<A>) {
86        let Self(_, _, pat, expr) = self;
87        pat.apply(sub);
88        expr.apply(sub);
89    }
90}
91
92impl<A: AstTypes> Match<A> for Expr<A> {
93    fn recurse(sub: &mut Subst<A>, pat: &Self, expr: &Self) -> bool {
94        match (pat, expr) {
95            (Expr::Omitted, Expr::Omitted) => true,
96            (Expr::Omitted, _) => false,
97            (Expr::MetId(name), _) if name.as_ref() == "_" => true,
98            (Expr::MetId(name), _) => sub.add_expr(name.clone(), expr),
99            (Expr::Id(pat), Expr::Id(expr)) => pat == expr,
100            (Expr::Id(_), _) => false,
101            (Expr::Lit(pat), Expr::Lit(expr)) => pat == expr,
102            (Expr::Lit(_), _) => false,
103            (Expr::Use(_), Expr::Use(_)) => true,
104            (Expr::Use(_), _) => false,
105            (Expr::Bind(pat), Expr::Bind(expr)) => Match::recurse(sub, pat, expr),
106            (Expr::Bind(..), _) => false,
107            (Expr::Make(pat), Expr::Make(expr)) => Match::recurse(sub, pat, expr),
108            (Expr::Make(..), _) => false,
109            (Expr::Match(pat), Expr::Match(expr)) => Match::recurse(sub, pat, expr),
110            (Expr::Match(..), _) => false,
111            (Expr::Op(pat_op, pat_exprs), Expr::Op(expr_op, expr_exprs)) => {
112                Match::recurse(sub, pat_op, expr_op) && Match::recurse(sub, pat_exprs, expr_exprs)
113            }
114            (Expr::Op(..), _) => false,
115        }
116    }
117
118    fn apply(&mut self, sub: &Subst<A>) {
119        match self {
120            Expr::MetId(id) => {
121                if let Some(expr) = sub.exp.get(id) {
122                    *self = expr.clone();
123                }
124            }
125            Expr::Omitted | Expr::Id(_) | Expr::Lit(_) | Expr::Use(_) => {}
126            Expr::Bind(expr) => expr.apply(sub),
127            Expr::Make(expr) => expr.apply(sub),
128            Expr::Match(expr) => expr.apply(sub),
129            Expr::Op(op, exprs) => {
130                op.apply(sub);
131                exprs.apply(sub);
132            }
133        }
134    }
135}
136
137impl<A: AstTypes> Match<A> for crate::ast::Make<A> {
138    fn recurse(sub: &mut Subst<A>, pat: &Self, expr: &Self) -> bool {
139        let (Make(pat, pat_arms), Make(expr, expr_arms)) = (pat, expr);
140        Match::recurse(sub, pat, expr) && Match::recurse(sub, pat_arms, expr_arms)
141    }
142
143    fn apply(&mut self, sub: &Subst<A>) {
144        let Make(expr, make_arms) = self;
145        expr.apply(sub);
146        make_arms.apply(sub);
147    }
148}
149
150impl<A: AstTypes> Match<A> for MakeArm<A> {
151    // TODO: order-independent matching for MakeArm specifically.
152    fn recurse(sub: &mut Subst<A>, pat: &Self, expr: &Self) -> bool {
153        pat.0 == expr.0 && Match::recurse(sub, &pat.1, &expr.1)
154    }
155
156    fn apply(&mut self, sub: &Subst<A>) {
157        let Self(_, expr) = self;
158        expr.apply(sub);
159    }
160}
161
162impl<A: AstTypes> Match<A> for super::Match<A> {
163    fn recurse(sub: &mut Subst<A>, pat: &Self, expr: &Self) -> bool {
164        let (Self(pat_scr, pat_arms), Self(expr_scr, expr_arms)) = (pat, expr);
165        Match::recurse(sub, pat_scr, expr_scr) && Match::recurse(sub, pat_arms, expr_arms)
166    }
167
168    fn apply(&mut self, sub: &Subst<A>) {
169        let Self(scrutinee, arms) = self;
170        scrutinee.apply(sub);
171        arms.apply(sub);
172    }
173}
174
175impl<A: AstTypes> Match<A> for MatchArm<A> {
176    fn recurse(sub: &mut Subst<A>, pat: &Self, expr: &Self) -> bool {
177        let (Self(pat_pat, pat_expr), Self(expr_pat, expr_expr)) = (pat, expr);
178        Match::recurse(sub, pat_pat, expr_pat) && Match::recurse(sub, pat_expr, expr_expr)
179    }
180
181    fn apply(&mut self, sub: &Subst<A>) {
182        let Self(pat, expr) = self;
183        pat.apply(sub);
184        expr.apply(sub);
185    }
186}
187
188impl<A: AstTypes> Match<A> for Pat<A> {
189    fn recurse(sub: &mut Subst<A>, pat: &Self, expr: &Self) -> bool {
190        match (pat, expr) {
191            (Pat::MetId(name), _) if name.as_ref() == "_" => true,
192            (Pat::MetId(name), _) => sub.add_pat(name.clone(), expr),
193            (Pat::Ignore, Pat::Ignore) => true,
194            (Pat::Ignore, _) => false,
195            (Pat::Never, Pat::Never) => true,
196            (Pat::Never, _) => false,
197            (Pat::Name(pat), Pat::Name(expr)) => pat == expr,
198            (Pat::Name(_), _) => false,
199            (Pat::Value(pat), Pat::Value(expr)) => pat == expr,
200            (Pat::Value(_), _) => false,
201            (Pat::Op(_, pat), Pat::Op(_, expr)) => Match::recurse(sub, pat, expr),
202            (Pat::Op(..), _) => false,
203        }
204    }
205
206    fn apply(&mut self, sub: &Subst<A>) {
207        match self {
208            Pat::Ignore | Pat::Never | Pat::Name(_) => {}
209            Pat::Value(expr) => expr.apply(sub),
210            Pat::MetId(id) => {
211                if let Some(expr) = sub.pat.get(id) {
212                    *self = expr.clone();
213                }
214            }
215            Pat::Op(_, pats) => pats.apply(sub),
216        }
217    }
218}
219
220impl<A: AstTypes> Match<A> for Op {
221    fn recurse(_: &mut Subst<A>, pat: &Self, expr: &Self) -> bool {
222        pat == expr
223    }
224
225    fn apply(&mut self, _sub: &Subst<A>) {}
226}
227
228impl<A: AstTypes, T: Match<A>> Match<A> for [T] {
229    fn recurse(sub: &mut Subst<A>, pat: &Self, expr: &Self) -> bool {
230        if pat.len() != expr.len() {
231            return false;
232        }
233        for (pat, expr) in pat.iter().zip(expr.iter()) {
234            if !Match::recurse(sub, pat, expr) {
235                return false;
236            }
237        }
238        true
239    }
240
241    fn apply(&mut self, sub: &Subst<A>) {
242        for item in self {
243            item.apply(sub);
244        }
245    }
246}
247
248impl<A: AstTypes, T: Match<A>> Match<A> for Box<T> {
249    fn recurse(sub: &mut Subst<A>, pat: &Self, expr: &Self) -> bool {
250        Match::recurse(sub, pat.as_ref(), expr.as_ref())
251    }
252
253    fn apply(&mut self, sub: &Subst<A>) {
254        self.as_mut().apply(sub);
255    }
256}
257
258impl<A: AstTypes, T: Match<A>> Match<A> for Vec<T> {
259    fn recurse(sub: &mut Subst<A>, pat: &Self, expr: &Self) -> bool {
260        Match::recurse(sub, pat.as_slice(), expr.as_slice())
261    }
262
263    fn apply(&mut self, sub: &Subst<A>) {
264        self.as_mut_slice().apply(sub);
265    }
266}
267
268impl<A: AstTypes, T: Match<A>> Match<A> for Option<T> {
269    fn recurse(sub: &mut Subst<A>, pat: &Self, expr: &Self) -> bool {
270        match (pat, expr) {
271            (Some(pat), Some(expr)) => Match::recurse(sub, pat, expr),
272            (None, None) => true,
273            _ => false,
274        }
275    }
276
277    fn apply(&mut self, sub: &Subst<A>) {
278        self.as_mut_slice().apply(sub);
279    }
280}
cl_ast/ast/macro_matcher.rs

cl_ast/ast/
macro_matcher.rs
