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 = args.cloned();
69 if let [prefix @ .., PathElem::Monomorphized(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.with_ctx(&ctx.into_fmt()),
78 args.unwrap().with_ctx(&ctx.into_fmt())
79 );
80 let mut mono_args = (**mono_args).clone();
82 if let Some(args) = args {
83 mono_args.regions.extend(args.regions.into_iter());
85 }
86 scrutinee_elems = prefix;
87 args = Some(mono_args);
88 };
89 let args = args.as_ref();
90 if let Some(PatElem::Impl(_)) = self.elems.first() {
94 if let Some((i, _)) = scrutinee_elems
95 .iter()
96 .enumerate()
97 .rfind(|(_, elem)| elem.is_impl())
98 {
99 scrutinee_elems = &scrutinee_elems[i..];
100 }
101 }
102
103 let zipped = self.elems.iter().zip_longest(scrutinee_elems).collect_vec();
104 let zipped_len = zipped.len();
105 for (i, x) in zipped.into_iter().enumerate() {
106 let is_last = i + 1 == zipped_len;
107 match x {
108 EitherOrBoth::Both(pat, elem) => {
109 let args = if is_last { args } else { None };
110 if !pat.matches_with_generics(ctx, elem, args) {
111 return false;
112 }
113 }
114 EitherOrBoth::Right(_) => return true,
117 EitherOrBoth::Left(_) => return false,
119 }
120 }
121 true
123 }
124
125 pub fn matches_ty(&self, ctx: &TranslatedCrate, ty: &Ty) -> bool {
126 if let [PatElem::Glob] = self.elems.as_slice() {
127 return true;
128 }
129 match ty.kind() {
130 TyKind::Adt(tref) => {
131 let args = &tref.generics;
132 match tref.id {
133 TypeId::Adt(type_id) => {
134 let Some(type_name) = ctx.item_name(type_id) else {
135 return false;
136 };
137 self.matches_with_generics(ctx, type_name, Some(args))
138 }
139 TypeId::Builtin(builtin_ty) => {
140 let name = builtin_ty.get_name();
141 self.matches_with_generics(ctx, &name, Some(args))
142 }
143 TypeId::Tuple => false,
144 }
145 }
146 TyKind::TypeVar(..)
147 | TyKind::Literal(..)
148 | TyKind::Never
149 | TyKind::Ref(..)
150 | TyKind::RawPtr(..)
151 | TyKind::TraitType(..)
152 | TyKind::DynTrait(..)
153 | TyKind::FnPtr(..)
154 | TyKind::FnDef(..)
155 | TyKind::PtrMetadata(..)
156 | TyKind::Error(..) => false,
157 }
158 }
159
160 pub fn matches_const(&self, _ctx: &TranslatedCrate, _c: &ConstGeneric) -> bool {
161 if let [PatElem::Glob] = self.elems.as_slice() {
162 return true;
163 }
164 todo!("non-trivial const generics patterns aren't implemented")
165 }
166
167 pub fn compare(&self, other: &Self) -> Ordering {
171 use Ordering::*;
172 use PatElem::*;
173 match self.len().cmp(&other.len()) {
174 o @ (Less | Greater) => return o,
175 _ if self.len() == 0 => return Equal,
176 Equal => {}
177 }
178 match (self.elems.last().unwrap(), other.elems.last().unwrap()) {
179 (Glob, Glob) => Equal,
180 (Glob, _) => Less,
181 (_, Glob) => Greater,
182 _ => Equal,
184 }
185 }
186}
187
188impl Ord for Pattern {
191 fn cmp(&self, other: &Self) -> Ordering {
192 self.compare(other)
193 }
194}
195impl PartialOrd for Pattern {
196 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
197 Some(self.compare(other))
198 }
199}
200
201impl PatElem {
202 fn matches_with_generics(
203 &self,
204 ctx: &TranslatedCrate,
205 elem: &PathElem,
206 args: Option<&GenericArgs>,
207 ) -> bool {
208 match (self, elem) {
209 (PatElem::Glob, _) => true,
210 (
211 PatElem::Ident {
212 name: pat_ident,
213 generics,
214 ..
215 },
216 PathElem::Ident(ident, _),
217 ) => {
218 let same_ident =
220 pat_ident == ident || (pat_ident == "crate" && ident == &ctx.crate_name);
221 same_ident && PatTy::matches_generics(ctx, generics, args)
222 }
223 (PatElem::Impl(_pat), PathElem::Impl(ImplElem::Ty(..))) => {
224 false
226 }
227 (PatElem::Impl(pat), PathElem::Impl(ImplElem::Trait(impl_id))) => {
228 let Some(timpl) = ctx.trait_impls.get(*impl_id) else {
229 return false;
230 };
231 let Some(trait_name) = ctx.item_name(timpl.impl_trait.id) else {
232 return false;
233 };
234 pat.matches_with_generics(ctx, trait_name, Some(&timpl.impl_trait.generics))
235 }
236 _ => false,
237 }
238 }
239}
240
241impl PatTy {
242 pub fn matches_generics(
243 ctx: &TranslatedCrate,
244 pats: &[Self],
245 generics: Option<&GenericArgs>,
246 ) -> bool {
247 let Some(generics) = generics else {
248 return true;
250 };
251 if pats.is_empty() {
252 return true;
254 }
255 if pats.len() != generics.types.elem_count() + generics.const_generics.elem_count() {
257 return false;
258 }
259 let (type_pats, const_pats) = pats.split_at(generics.types.elem_count());
260 let types_match = generics
261 .types
262 .iter()
263 .zip(type_pats)
264 .all(|(ty, pat)| pat.matches_ty(ctx, ty));
265 let consts_match = generics
266 .const_generics
267 .iter()
268 .zip(const_pats)
269 .all(|(c, pat)| pat.matches_const(ctx, c));
270 types_match && consts_match
271 }
272
273 pub fn matches_ty(&self, ctx: &TranslatedCrate, ty: &Ty) -> bool {
274 match (self, ty.kind()) {
275 (PatTy::Pat(p), _) => p.matches_ty(ctx, ty),
276 (PatTy::Ref(pat_mtbl, p_ty), TyKind::Ref(_, ty, ty_mtbl)) => {
277 pat_mtbl == ty_mtbl && p_ty.matches_ty(ctx, ty)
278 }
279 _ => false,
280 }
281 }
282
283 pub fn matches_const(&self, ctx: &TranslatedCrate, c: &ConstGeneric) -> bool {
284 match self {
285 PatTy::Pat(p) => p.matches_const(ctx, c),
286 PatTy::Ref(..) => false,
287 }
288 }
289}
290
291#[test]
292fn test_compare() {
293 use Ordering::*;
294 let tests = [
295 ("_", Less, "crate"),
296 ("crate::_", Less, "crate::foo"),
297 ("crate::foo", Less, "crate::foo::_"),
298 ];
299 for (x, o, y) in tests {
300 let x = Pattern::parse(x).unwrap();
301 let y = Pattern::parse(y).unwrap();
302 assert_eq!(x.compare(&y), o);
303 }
304}