1use std::cmp::Ordering;
2
3use itertools::{EitherOrBoth, Itertools};
4use serde::{Deserialize, Serialize};
5
6use crate::{ast::*, formatter::IntoFormatter, pretty::FmtWithCtx};
7
8mod parser;
9
10pub use Pattern as NamePattern;
11
12#[derive(Clone, PartialEq, Eq, Serialize, Deserialize)]
13pub struct Pattern {
14    elems: Vec<PatElem>,
15}
16
17#[derive(Clone, PartialEq, Eq, Serialize, Deserialize)]
18enum PatElem {
19    Ident {
21        name: String,
22        generics: Vec<PatTy>,
23        is_trait: bool,
25    },
26    Impl(Box<Pattern>),
29    Glob,
31}
32
33#[derive(Clone, PartialEq, Eq, Serialize, Deserialize)]
34enum PatTy {
35    Pat(Pattern),
37    Ref(RefKind, Box<Self>),
39}
40
41impl Pattern {
42    pub fn parse(i: &str) -> Result<Self, nom_supreme::error::ErrorTree<String>> {
43        use std::str::FromStr;
44        Self::from_str(i)
45    }
46
47    fn len(&self) -> usize {
48        self.elems.len()
49    }
50
51    pub fn matches(&self, ctx: &TranslatedCrate, name: &Name) -> bool {
52        self.matches_with_generics(ctx, name, None)
53    }
54
55    pub fn matches_item(&self, ctx: &TranslatedCrate, item: ItemRef<'_>) -> bool {
56        let generics = item.identity_args();
57        let name = &item.item_meta().name;
58        self.matches_with_generics(ctx, name, Some(&generics))
59    }
60
61    pub fn matches_with_generics(
62        &self,
63        ctx: &TranslatedCrate,
64        name: &Name,
65        args: Option<&GenericArgs>,
66    ) -> bool {
67        let mut scrutinee_elems = name.name.as_slice();
68        let mut args: Option<GenericArgs> = args.cloned();
69        if let [prefix @ .., PathElem::Instantiated(mono_args)] = scrutinee_elems {
70            assert!(
72                args.is_none()
73                    || args.as_ref().unwrap().len() == args.as_ref().unwrap().regions.elem_count(),
74                "In pattern \"{}\" matching against name \"{}\": we have both monomorphized generics {} and regular generics {}",
75                self,
76                name.with_ctx(&ctx.into_fmt()),
77                mono_args.skip_binder.with_ctx(&ctx.into_fmt()),
78                args.unwrap().with_ctx(&ctx.into_fmt())
79            );
80            let mut mono_args = mono_args.skip_binder.clone();
84            if let Some(args) = args {
85                mono_args.regions.extend(args.regions.into_iter());
87            }
88            scrutinee_elems = prefix;
89            args = Some(mono_args);
90        };
91        let args = args.as_ref();
92        if let Some(PatElem::Impl(_)) = self.elems.first() {
96            if let Some((i, _)) = scrutinee_elems
97                .iter()
98                .enumerate()
99                .rfind(|(_, elem)| elem.is_impl())
100            {
101                scrutinee_elems = &scrutinee_elems[i..];
102            }
103        }
104
105        let zipped = self.elems.iter().zip_longest(scrutinee_elems).collect_vec();
106        let zipped_len = zipped.len();
107        for (i, x) in zipped.into_iter().enumerate() {
108            let is_last = i + 1 == zipped_len;
109            match x {
110                EitherOrBoth::Both(pat, elem) => {
111                    let args = if is_last { args } else { None };
112                    if !pat.matches_with_generics(ctx, elem, args) {
113                        return false;
114                    }
115                }
116                EitherOrBoth::Right(_) => return true,
119                EitherOrBoth::Left(_) => return false,
121            }
122        }
123        true
125    }
126
127    pub fn matches_ty(&self, ctx: &TranslatedCrate, ty: &Ty) -> bool {
128        if let [PatElem::Glob] = self.elems.as_slice() {
129            return true;
130        }
131        match ty.kind() {
132            TyKind::Adt(tref) => {
133                let args = &tref.generics;
134                match tref.id {
135                    TypeId::Adt(type_id) => {
136                        let Some(type_name) = ctx.item_name(type_id) else {
137                            return false;
138                        };
139                        self.matches_with_generics(ctx, type_name, Some(args))
140                    }
141                    TypeId::Builtin(builtin_ty) => {
142                        let name = builtin_ty.get_name();
143                        self.matches_with_generics(ctx, &name, Some(args))
144                    }
145                    TypeId::Tuple => false,
146                }
147            }
148            TyKind::TypeVar(..)
149            | TyKind::Literal(..)
150            | TyKind::Never
151            | TyKind::Ref(..)
152            | TyKind::RawPtr(..)
153            | TyKind::TraitType(..)
154            | TyKind::DynTrait(..)
155            | TyKind::FnPtr(..)
156            | TyKind::FnDef(..)
157            | TyKind::PtrMetadata(..)
158            | TyKind::Error(..) => false,
159        }
160    }
161
162    pub fn matches_const(&self, _ctx: &TranslatedCrate, _c: &ConstGeneric) -> bool {
163        if let [PatElem::Glob] = self.elems.as_slice() {
164            return true;
165        }
166        todo!("non-trivial const generics patterns aren't implemented")
167    }
168
169    pub fn compare(&self, other: &Self) -> Ordering {
173        use Ordering::*;
174        use PatElem::*;
175        match self.len().cmp(&other.len()) {
176            o @ (Less | Greater) => return o,
177            _ if self.len() == 0 => return Equal,
178            Equal => {}
179        }
180        match (self.elems.last().unwrap(), other.elems.last().unwrap()) {
181            (Glob, Glob) => Equal,
182            (Glob, _) => Less,
183            (_, Glob) => Greater,
184            _ => Equal,
186        }
187    }
188}
189
190impl Ord for Pattern {
193    fn cmp(&self, other: &Self) -> Ordering {
194        self.compare(other)
195    }
196}
197impl PartialOrd for Pattern {
198    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
199        Some(self.compare(other))
200    }
201}
202
203impl PatElem {
204    fn matches_with_generics(
205        &self,
206        ctx: &TranslatedCrate,
207        elem: &PathElem,
208        args: Option<&GenericArgs>,
209    ) -> bool {
210        match (self, elem) {
211            (PatElem::Glob, _) => true,
212            (
213                PatElem::Ident {
214                    name: pat_ident,
215                    generics,
216                    ..
217                },
218                PathElem::Ident(ident, _),
219            ) => {
220                let same_ident =
222                    pat_ident == ident || (pat_ident == "crate" && ident == &ctx.crate_name);
223                same_ident && PatTy::matches_generics(ctx, generics, args)
224            }
225            (PatElem::Impl(_pat), PathElem::Impl(ImplElem::Ty(..))) => {
226                false
228            }
229            (PatElem::Impl(pat), PathElem::Impl(ImplElem::Trait(impl_id))) => {
230                let Some(timpl) = ctx.trait_impls.get(*impl_id) else {
231                    return false;
232                };
233                let Some(trait_name) = ctx.item_name(timpl.impl_trait.id) else {
234                    return false;
235                };
236                pat.matches_with_generics(ctx, trait_name, Some(&timpl.impl_trait.generics))
237            }
238            _ => false,
239        }
240    }
241}
242
243impl PatTy {
244    pub fn matches_generics(
245        ctx: &TranslatedCrate,
246        pats: &[Self],
247        generics: Option<&GenericArgs>,
248    ) -> bool {
249        let Some(generics) = generics else {
250            return true;
252        };
253        if pats.is_empty() {
254            return true;
256        }
257        if pats.len() != generics.types.elem_count() + generics.const_generics.elem_count() {
259            return false;
260        }
261        let (type_pats, const_pats) = pats.split_at(generics.types.elem_count());
262        let types_match = generics
263            .types
264            .iter()
265            .zip(type_pats)
266            .all(|(ty, pat)| pat.matches_ty(ctx, ty));
267        let consts_match = generics
268            .const_generics
269            .iter()
270            .zip(const_pats)
271            .all(|(c, pat)| pat.matches_const(ctx, c));
272        types_match && consts_match
273    }
274
275    pub fn matches_ty(&self, ctx: &TranslatedCrate, ty: &Ty) -> bool {
276        match (self, ty.kind()) {
277            (PatTy::Pat(p), _) => p.matches_ty(ctx, ty),
278            (PatTy::Ref(pat_mtbl, p_ty), TyKind::Ref(_, ty, ty_mtbl)) => {
279                pat_mtbl == ty_mtbl && p_ty.matches_ty(ctx, ty)
280            }
281            _ => false,
282        }
283    }
284
285    pub fn matches_const(&self, ctx: &TranslatedCrate, c: &ConstGeneric) -> bool {
286        match self {
287            PatTy::Pat(p) => p.matches_const(ctx, c),
288            PatTy::Ref(..) => false,
289        }
290    }
291}
292
293#[test]
294fn test_compare() {
295    use Ordering::*;
296    let tests = [
297        ("_", Less, "crate"),
298        ("crate::_", Less, "crate::foo"),
299        ("crate::foo", Less, "crate::foo::_"),
300    ];
301    for (x, o, y) in tests {
302        let x = Pattern::parse(x).unwrap();
303        let y = Pattern::parse(y).unwrap();
304        assert_eq!(x.compare(&y), o);
305    }
306}