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