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