]>
Commit | Line | Data |
---|---|---|
f035d41b XL |
1 | //! Fast matching check for zippable values. |
2 | ||
f9f354fc XL |
3 | use crate::interner::HasInterner; |
4 | use crate::zip::{Zip, Zipper}; | |
5 | use crate::*; | |
6 | ||
7 | /// A fast check to see whether two things could ever possibly match. | |
8 | pub trait CouldMatch<T: ?Sized + HasInterner> { | |
f035d41b | 9 | /// Checks whether `self` and `other` could possibly match. |
5869c6ff XL |
10 | fn could_match( |
11 | &self, | |
12 | interner: &T::Interner, | |
13 | db: &dyn UnificationDatabase<T::Interner>, | |
14 | other: &T, | |
15 | ) -> bool; | |
f9f354fc XL |
16 | } |
17 | ||
18 | #[allow(unreachable_code, unused_variables)] | |
19 | impl<T, I> CouldMatch<T> for T | |
20 | where | |
21 | T: Zip<I> + ?Sized + HasInterner<Interner = I>, | |
22 | I: Interner, | |
23 | { | |
5869c6ff XL |
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(); | |
f9f354fc XL |
32 | |
33 | struct MatchZipper<'i, I> { | |
34 | interner: &'i I, | |
5869c6ff | 35 | db: &'i dyn UnificationDatabase<I>, |
f9f354fc XL |
36 | }; |
37 | ||
38 | impl<'i, I: Interner> Zipper<'i, I> for MatchZipper<'i, I> { | |
5869c6ff | 39 | fn zip_tys(&mut self, variance: Variance, a: &Ty<I>, b: &Ty<I>) -> Fallible<()> { |
f9f354fc | 40 | let interner = self.interner; |
29967ef6 XL |
41 | let matches = |a: &Substitution<I>, b: &Substitution<I>| { |
42 | a.iter(interner) | |
43 | .zip(b.iter(interner)) | |
5869c6ff | 44 | .all(|(p_a, p_b)| p_a.could_match(interner, self.db, &p_b)) |
29967ef6 XL |
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)) => { | |
5869c6ff XL |
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() | |
29967ef6 XL |
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), | |
5869c6ff XL |
72 | (TyKind::Slice(ty_a), TyKind::Slice(ty_b)) => { |
73 | ty_a.could_match(interner, self.db, ty_b) | |
74 | } | |
29967ef6 XL |
75 | ( |
76 | TyKind::FnDef(fn_def_a, substitution_a), | |
77 | TyKind::FnDef(fn_def_b, substitution_b), | |
5869c6ff XL |
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 | } | |
29967ef6 XL |
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 | |
5869c6ff XL |
94 | && lifetime_a.could_match(interner, self.db, &lifetime_b) |
95 | && ty_a.could_match(interner, self.db, &ty_b) | |
29967ef6 XL |
96 | } |
97 | (TyKind::Raw(mutability_a, ty_a), TyKind::Raw(mutability_b, ty_b)) => { | |
5869c6ff | 98 | mutability_a == mutability_b && ty_a.could_match(interner, self.db, &ty_b) |
29967ef6 XL |
99 | } |
100 | (TyKind::Never, TyKind::Never) => true, | |
101 | (TyKind::Array(ty_a, const_a), TyKind::Array(ty_b, const_b)) => { | |
5869c6ff XL |
102 | ty_a.could_match(interner, self.db, ty_b) |
103 | && const_a.could_match(interner, self.db, const_b) | |
29967ef6 XL |
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::Generator(generator_a, substitution_a), | |
111 | TyKind::Generator(generator_b, substitution_b), | |
5869c6ff XL |
112 | ) => { |
113 | generator_a == generator_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 | } | |
29967ef6 XL |
123 | ( |
124 | TyKind::GeneratorWitness(generator_a, substitution_a), | |
125 | TyKind::GeneratorWitness(generator_b, substitution_b), | |
5869c6ff XL |
126 | ) => { |
127 | generator_a == generator_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 | } | |
29967ef6 XL |
137 | (TyKind::Foreign(foreign_ty_a), TyKind::Foreign(foreign_ty_b)) => { |
138 | foreign_ty_a == foreign_ty_b | |
f9f354fc | 139 | } |
29967ef6 | 140 | (TyKind::Error, TyKind::Error) => true, |
f9f354fc XL |
141 | |
142 | _ => true, | |
143 | }; | |
144 | ||
145 | if could_match { | |
146 | Ok(()) | |
147 | } else { | |
148 | Err(NoSolution) | |
149 | } | |
150 | } | |
151 | ||
5869c6ff XL |
152 | fn zip_lifetimes( |
153 | &mut self, | |
154 | variance: Variance, | |
155 | _: &Lifetime<I>, | |
156 | _: &Lifetime<I>, | |
157 | ) -> Fallible<()> { | |
f9f354fc XL |
158 | Ok(()) |
159 | } | |
160 | ||
5869c6ff XL |
161 | fn zip_consts( |
162 | &mut self, | |
163 | variance: Variance, | |
164 | _: &Const<I>, | |
165 | _: &Const<I>, | |
166 | ) -> Fallible<()> { | |
f035d41b XL |
167 | Ok(()) |
168 | } | |
169 | ||
5869c6ff XL |
170 | fn zip_binders<T>( |
171 | &mut self, | |
172 | variance: Variance, | |
173 | a: &Binders<T>, | |
174 | b: &Binders<T>, | |
175 | ) -> Fallible<()> | |
f9f354fc XL |
176 | where |
177 | T: HasInterner + Zip<I>, | |
178 | { | |
5869c6ff | 179 | Zip::zip_with(self, variance, &a.value, &b.value) |
f9f354fc XL |
180 | } |
181 | ||
182 | fn interner(&self) -> &'i I { | |
183 | self.interner | |
184 | } | |
5869c6ff XL |
185 | |
186 | fn unification_database(&self) -> &dyn UnificationDatabase<I> { | |
187 | self.db | |
188 | } | |
f9f354fc XL |
189 | } |
190 | } | |
191 | } | |
192 | ||
193 | impl<I: Interner> CouldMatch<DomainGoal<I>> for ProgramClauseData<I> { | |
5869c6ff XL |
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) | |
f9f354fc XL |
201 | } |
202 | } | |
203 | ||
204 | impl<I: Interner> CouldMatch<DomainGoal<I>> for ProgramClause<I> { | |
5869c6ff XL |
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) | |
f9f354fc XL |
212 | } |
213 | } |