chalk_ir/
could_match.rs

1//! Fast matching check for zippable values.
2
3use crate::interner::HasInterner;
4use crate::zip::{Zip, Zipper};
5use crate::*;
6
7/// A fast check to see whether two things could ever possibly match.
8pub trait CouldMatch<T: ?Sized + HasInterner> {
9    /// Checks whether `self` and `other` could possibly match.
10    fn could_match(
11        &self,
12        interner: T::Interner,
13        db: &dyn UnificationDatabase<T::Interner>,
14        other: &T,
15    ) -> bool;
16}
17
18#[allow(unreachable_code, unused_variables)]
19impl<T, I> CouldMatch<T> for T
20where
21    T: Zip<I> + ?Sized + HasInterner<Interner = I>,
22    I: Interner,
23{
24    fn could_match(&self, interner: I, db: &dyn UnificationDatabase<I>, other: &T) -> bool {
25        return Zip::zip_with(
26            &mut MatchZipper { interner, db },
27            Variance::Invariant,
28            self,
29            other,
30        )
31        .is_ok();
32
33        struct MatchZipper<'i, I> {
34            interner: I,
35            db: &'i dyn UnificationDatabase<I>,
36        }
37
38        impl<'i, I: Interner> Zipper<I> for MatchZipper<'i, I> {
39            fn zip_tys(&mut self, variance: Variance, a: &Ty<I>, b: &Ty<I>) -> Fallible<()> {
40                let interner = self.interner;
41                let matches = |a: &Substitution<I>, b: &Substitution<I>| {
42                    a.iter(interner)
43                        .zip(b.iter(interner))
44                        .all(|(p_a, p_b)| p_a.could_match(interner, self.db, p_b))
45                };
46                let could_match = match (a.kind(interner), b.kind(interner)) {
47                    (TyKind::Adt(id_a, substitution_a), TyKind::Adt(id_b, substitution_b)) => {
48                        id_a == id_b
49                            && self
50                                .zip_substs(
51                                    variance,
52                                    Some(self.unification_database().adt_variance(*id_a)),
53                                    substitution_a.as_slice(interner),
54                                    substitution_b.as_slice(interner),
55                                )
56                                .is_ok()
57                    }
58                    (
59                        TyKind::AssociatedType(assoc_ty_a, substitution_a),
60                        TyKind::AssociatedType(assoc_ty_b, substitution_b),
61                    ) => assoc_ty_a == assoc_ty_b && matches(substitution_a, substitution_b),
62                    (TyKind::Scalar(scalar_a), TyKind::Scalar(scalar_b)) => scalar_a == scalar_b,
63                    (TyKind::Str, TyKind::Str) => true,
64                    (
65                        TyKind::Tuple(arity_a, substitution_a),
66                        TyKind::Tuple(arity_b, substitution_b),
67                    ) => arity_a == arity_b && matches(substitution_a, substitution_b),
68                    (
69                        TyKind::OpaqueType(opaque_ty_a, substitution_a),
70                        TyKind::OpaqueType(opaque_ty_b, substitution_b),
71                    ) => opaque_ty_a == opaque_ty_b && matches(substitution_a, substitution_b),
72                    (TyKind::Slice(ty_a), TyKind::Slice(ty_b)) => {
73                        ty_a.could_match(interner, self.db, ty_b)
74                    }
75                    (
76                        TyKind::FnDef(fn_def_a, substitution_a),
77                        TyKind::FnDef(fn_def_b, substitution_b),
78                    ) => {
79                        fn_def_a == fn_def_b
80                            && self
81                                .zip_substs(
82                                    variance,
83                                    Some(self.unification_database().fn_def_variance(*fn_def_a)),
84                                    substitution_a.as_slice(interner),
85                                    substitution_b.as_slice(interner),
86                                )
87                                .is_ok()
88                    }
89                    (
90                        TyKind::Ref(mutability_a, lifetime_a, ty_a),
91                        TyKind::Ref(mutability_b, lifetime_b, ty_b),
92                    ) => {
93                        mutability_a == mutability_b
94                            && lifetime_a.could_match(interner, self.db, lifetime_b)
95                            && ty_a.could_match(interner, self.db, ty_b)
96                    }
97                    (TyKind::Raw(mutability_a, ty_a), TyKind::Raw(mutability_b, ty_b)) => {
98                        mutability_a == mutability_b && ty_a.could_match(interner, self.db, ty_b)
99                    }
100                    (TyKind::Never, TyKind::Never) => true,
101                    (TyKind::Array(ty_a, const_a), TyKind::Array(ty_b, const_b)) => {
102                        ty_a.could_match(interner, self.db, ty_b)
103                            && const_a.could_match(interner, self.db, const_b)
104                    }
105                    (
106                        TyKind::Closure(id_a, substitution_a),
107                        TyKind::Closure(id_b, substitution_b),
108                    ) => id_a == id_b && matches(substitution_a, substitution_b),
109                    (
110                        TyKind::Coroutine(coroutine_a, substitution_a),
111                        TyKind::Coroutine(coroutine_b, substitution_b),
112                    ) => {
113                        coroutine_a == coroutine_b
114                            && self
115                                .zip_substs(
116                                    variance,
117                                    None,
118                                    substitution_a.as_slice(interner),
119                                    substitution_b.as_slice(interner),
120                                )
121                                .is_ok()
122                    }
123                    (
124                        TyKind::CoroutineWitness(coroutine_a, substitution_a),
125                        TyKind::CoroutineWitness(coroutine_b, substitution_b),
126                    ) => {
127                        coroutine_a == coroutine_b
128                            && self
129                                .zip_substs(
130                                    variance,
131                                    None,
132                                    substitution_a.as_slice(interner),
133                                    substitution_b.as_slice(interner),
134                                )
135                                .is_ok()
136                    }
137                    (TyKind::Foreign(foreign_ty_a), TyKind::Foreign(foreign_ty_b)) => {
138                        foreign_ty_a == foreign_ty_b
139                    }
140                    (TyKind::Error, TyKind::Error) => true,
141
142                    _ => true,
143                };
144
145                if could_match {
146                    Ok(())
147                } else {
148                    Err(NoSolution)
149                }
150            }
151
152            fn zip_lifetimes(
153                &mut self,
154                variance: Variance,
155                _: &Lifetime<I>,
156                _: &Lifetime<I>,
157            ) -> Fallible<()> {
158                Ok(())
159            }
160
161            fn zip_consts(
162                &mut self,
163                variance: Variance,
164                _: &Const<I>,
165                _: &Const<I>,
166            ) -> Fallible<()> {
167                Ok(())
168            }
169
170            fn zip_binders<T>(
171                &mut self,
172                variance: Variance,
173                a: &Binders<T>,
174                b: &Binders<T>,
175            ) -> Fallible<()>
176            where
177                T: HasInterner + Zip<I>,
178            {
179                Zip::zip_with(self, variance, &a.value, &b.value)
180            }
181
182            fn interner(&self) -> I {
183                self.interner
184            }
185
186            fn unification_database(&self) -> &dyn UnificationDatabase<I> {
187                self.db
188            }
189        }
190    }
191}
192
193impl<I: Interner> CouldMatch<DomainGoal<I>> for ProgramClauseData<I> {
194    fn could_match(
195        &self,
196        interner: I,
197        db: &dyn UnificationDatabase<I>,
198        other: &DomainGoal<I>,
199    ) -> bool {
200        self.0.value.consequence.could_match(interner, db, other)
201    }
202}
203
204impl<I: Interner> CouldMatch<DomainGoal<I>> for ProgramClause<I> {
205    fn could_match(
206        &self,
207        interner: I,
208        db: &dyn UnificationDatabase<I>,
209        other: &DomainGoal<I>,
210    ) -> bool {
211        self.data(interner).could_match(interner, db, other)
212    }
213}
chalk_ir/could_match.rs

chalk_ir/
could_match.rs
