charon_lib/name_matcher/
mod.rs

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    /// An identifier, optionally with generic arguments. E.g. `std` or `Box<_>`.
20    Ident {
21        name: String,
22        generics: Vec<PatTy>,
23        /// For pretty-printing only: whether this is the name of a trait.
24        is_trait: bool,
25    },
26    /// An inherent or trait implementation block. For traits, the implemented type is the first
27    /// element of the pattern generics.
28    Impl(Box<Pattern>),
29    /// A `*` or `_`.
30    Glob,
31}
32
33#[derive(Clone, PartialEq, Eq, Serialize, Deserialize)]
34enum PatTy {
35    /// A path, like `my_crate::foo::Type<_, usize>`
36    Pat(Pattern),
37    /// `&T`, `&mut T`
38    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            // In this case, we may still have some late-bound generics in `args`, this could ONLY happen for regions
71            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            // We additionally append the regions from `args` to the monomorphized args, so that we can match against them.
81            let mut mono_args = (**mono_args).clone();
82            if let Some(args) = args {
83                // Late-bound regions are appended after the monomorphized ones.
84                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        // Patterns that start with an impl block match that impl block anywhere. In such a case we
91        // truncate the scrutinee name to start with the rightmost impl in its name. This isn't
92        // fully precise in case of impls within impls, but we'll ignore that.
93        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                // The pattern is shorter than the scrutinee and the previous elements match: we
115                // count that as matching.
116                EitherOrBoth::Right(_) => return true,
117                // The pattern is longer than the scrutinee; they don't match.
118                EitherOrBoth::Left(_) => return false,
119            }
120        }
121        // Both had the same length and all the elements matched.
122        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    /// Compares two patterns that match the same name, in terms of precision. A pattern that is
168    /// fully included in another (i.e. matches a subset of values) is considered "less precise".
169    /// Returns nonsense if the patterns don't match the same name.
170    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            // TODO: compare precision of the generics.
183            _ => Equal,
184        }
185    }
186}
187
188/// Orders patterns by precision: the maximal pattern is the most precise. COmparing patterns only
189/// makes sense if they match the same name.
190impl 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                // `crate` is a special keyword that referes to the current crate.
219                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                // TODO
225                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            // If we'r ematching on a plain name without generics info, we ignore pattern generics.
249            return true;
250        };
251        if pats.is_empty() {
252            // If no generics are provided, this counts as a match.
253            return true;
254        }
255        // We don't include regions in patterns.
256        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}