1use std::cmp::Ordering;
2
3use itertools::{EitherOrBoth, Itertools};
4use serde::{Deserialize, Serialize};
5
6use crate::ast::*;
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: AnyTransItem<'_>) -> 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 if let Some(PatElem::Impl(_)) = self.elems.first() {
72 if let Some((i, _)) = scrutinee_elems
73 .iter()
74 .enumerate()
75 .rfind(|(_, elem)| elem.is_impl())
76 {
77 scrutinee_elems = &scrutinee_elems[i..];
78 }
79 }
80
81 let zipped = self.elems.iter().zip_longest(scrutinee_elems).collect_vec();
82 let zipped_len = zipped.len();
83 for (i, x) in zipped.into_iter().enumerate() {
84 let is_last = i + 1 == zipped_len;
85 match x {
86 EitherOrBoth::Both(pat, elem) => {
87 let args = if is_last { args } else { None };
88 if !pat.matches_with_generics(ctx, elem, args) {
89 return false;
90 }
91 }
92 EitherOrBoth::Right(_) => return true,
95 EitherOrBoth::Left(_) => return false,
97 }
98 }
99 true
101 }
102
103 pub fn matches_ty(&self, ctx: &TranslatedCrate, ty: &Ty) -> bool {
104 if let [PatElem::Glob] = self.elems.as_slice() {
105 return true;
106 }
107 match ty.kind() {
108 TyKind::Adt(tref) => {
109 let args = &tref.generics;
110 match tref.id {
111 TypeId::Adt(type_id) => {
112 let Some(type_name) = ctx.item_name(type_id) else {
113 return false;
114 };
115 self.matches_with_generics(ctx, type_name, Some(args))
116 }
117 TypeId::Builtin(builtin_ty) => {
118 let name = builtin_ty.get_name();
119 self.matches_with_generics(ctx, &name, Some(args))
120 }
121 TypeId::Tuple => false,
122 }
123 }
124 TyKind::TypeVar(..)
125 | TyKind::Literal(..)
126 | TyKind::Never
127 | TyKind::Ref(..)
128 | TyKind::RawPtr(..)
129 | TyKind::TraitType(..)
130 | TyKind::DynTrait(..)
131 | TyKind::FnPtr(..)
132 | TyKind::FnDef(..)
133 | TyKind::Error(..) => false,
134 }
135 }
136
137 pub fn matches_const(&self, _ctx: &TranslatedCrate, _c: &ConstGeneric) -> bool {
138 if let [PatElem::Glob] = self.elems.as_slice() {
139 return true;
140 }
141 todo!("non-trivial const generics patterns aren't implemented")
142 }
143
144 pub fn compare(&self, other: &Self) -> Ordering {
148 use Ordering::*;
149 use PatElem::*;
150 match self.len().cmp(&other.len()) {
151 o @ (Less | Greater) => return o,
152 _ if self.len() == 0 => return Equal,
153 Equal => {}
154 }
155 match (self.elems.last().unwrap(), other.elems.last().unwrap()) {
156 (Glob, Glob) => Equal,
157 (Glob, _) => Less,
158 (_, Glob) => Greater,
159 _ => Equal,
161 }
162 }
163}
164
165impl Ord for Pattern {
168 fn cmp(&self, other: &Self) -> Ordering {
169 self.compare(other)
170 }
171}
172impl PartialOrd for Pattern {
173 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
174 Some(self.compare(other))
175 }
176}
177
178impl PatElem {
179 fn matches_with_generics(
180 &self,
181 ctx: &TranslatedCrate,
182 elem: &PathElem,
183 args: Option<&GenericArgs>,
184 ) -> bool {
185 match (self, elem) {
186 (PatElem::Glob, _) => true,
187 (
188 PatElem::Ident {
189 name: pat_ident,
190 generics,
191 ..
192 },
193 PathElem::Ident(ident, _),
194 ) => {
195 let same_ident =
197 pat_ident == ident || (pat_ident == "crate" && ident == &ctx.crate_name);
198 same_ident && PatTy::matches_generics(ctx, generics, args)
199 }
200 (PatElem::Impl(_pat), PathElem::Impl(ImplElem::Ty(..))) => {
201 false
203 }
204 (PatElem::Impl(pat), PathElem::Impl(ImplElem::Trait(impl_id))) => {
205 let Some(timpl) = ctx.trait_impls.get(*impl_id) else {
206 return false;
207 };
208 let Some(trait_name) = ctx.item_name(timpl.impl_trait.id) else {
209 return false;
210 };
211 pat.matches_with_generics(ctx, trait_name, Some(&timpl.impl_trait.generics))
212 }
213 _ => false,
214 }
215 }
216}
217
218impl PatTy {
219 pub fn matches_generics(
220 ctx: &TranslatedCrate,
221 pats: &[Self],
222 generics: Option<&GenericArgs>,
223 ) -> bool {
224 let Some(generics) = generics else {
225 return true;
227 };
228 if pats.is_empty() {
229 return true;
231 }
232 if pats.len() != generics.types.elem_count() + generics.const_generics.elem_count() {
234 return false;
235 }
236 let (type_pats, const_pats) = pats.split_at(generics.types.elem_count());
237 let types_match = generics
238 .types
239 .iter()
240 .zip(type_pats)
241 .all(|(ty, pat)| pat.matches_ty(ctx, ty));
242 let consts_match = generics
243 .const_generics
244 .iter()
245 .zip(const_pats)
246 .all(|(c, pat)| pat.matches_const(ctx, c));
247 types_match && consts_match
248 }
249
250 pub fn matches_ty(&self, ctx: &TranslatedCrate, ty: &Ty) -> bool {
251 match (self, ty.kind()) {
252 (PatTy::Pat(p), _) => p.matches_ty(ctx, ty),
253 (PatTy::Ref(pat_mtbl, p_ty), TyKind::Ref(_, ty, ty_mtbl)) => {
254 pat_mtbl == ty_mtbl && p_ty.matches_ty(ctx, ty)
255 }
256 _ => false,
257 }
258 }
259
260 pub fn matches_const(&self, ctx: &TranslatedCrate, c: &ConstGeneric) -> bool {
261 match self {
262 PatTy::Pat(p) => p.matches_const(ctx, c),
263 PatTy::Ref(..) => false,
264 }
265 }
266}
267
268#[test]
269fn test_compare() {
270 use Ordering::*;
271 let tests = [
272 ("_", Less, "crate"),
273 ("crate::_", Less, "crate::foo"),
274 ("crate::foo", Less, "crate::foo::_"),
275 ];
276 for (x, o, y) in tests {
277 let x = Pattern::parse(x).unwrap();
278 let y = Pattern::parse(y).unwrap();
279 assert_eq!(x.compare(&y), o);
280 }
281}