charon_lib/name_matcher/
mod.rs

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    /// 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: 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                // The pattern is shorter than the scrutinee and the previous elements match: we
79                // count that as matching.
80                EitherOrBoth::Right(_) => return true,
81                // The pattern is longer than the scrutinee; they don't match.
82                EitherOrBoth::Left(_) => return false,
83            }
84        }
85        // Both had the same length and all the elements matched.
86        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    /// Compares two patterns that match the same name, in terms of precision. A pattern that is
131    /// fully included in another (i.e. matches a subset of values) is considered "less precise".
132    /// Returns nonsense if the patterns don't match the same name.
133    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            // TODO: compare precision of the generics.
146            _ => Equal,
147        }
148    }
149}
150
151/// Orders patterns by precision: the maximal pattern is the most precise. COmparing patterns only
152/// makes sense if they match the same name.
153impl 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                // `crate` is a special keyword that referes to the current crate.
182                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                // TODO
188                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            // If we'r ematching on a plain name without generics info, we ignore pattern generics.
212            return true;
213        };
214        if pats.is_empty() {
215            // If no generics are provided, this counts as a match.
216            return true;
217        }
218        // We don't include regions in patterns.
219        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}