]>
Commit | Line | Data |
---|---|---|
a2a8927a | 1 | use crate::mir::Mutability; |
923072b8 | 2 | use crate::ty::subst::GenericArgKind; |
064997fb | 3 | use crate::ty::{self, Ty, TyCtxt, TypeVisitable}; |
dfeec247 | 4 | use rustc_hir::def_id::DefId; |
ea8adc8c XL |
5 | use std::fmt::Debug; |
6 | use std::hash::Hash; | |
923072b8 | 7 | use std::iter; |
1a4d82fc | 8 | |
ea8adc8c | 9 | use self::SimplifiedTypeGen::*; |
1a4d82fc | 10 | |
ea8adc8c XL |
11 | pub type SimplifiedType = SimplifiedTypeGen<DefId>; |
12 | ||
13 | /// See `simplify_type` | |
14 | /// | |
15 | /// Note that we keep this type generic over the type of identifier it uses | |
16 | /// because we sometimes need to use SimplifiedTypeGen values as stable sorting | |
17 | /// keys (in which case we use a DefPathHash as id-type) but in the general case | |
18 | /// the non-stable but fast to construct DefId-version is the better choice. | |
923072b8 | 19 | #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, TyEncodable, TyDecodable, HashStable)] |
ea8adc8c | 20 | pub enum SimplifiedTypeGen<D> |
dfeec247 | 21 | where |
a2a8927a | 22 | D: Copy + Debug + Eq, |
ea8adc8c | 23 | { |
1a4d82fc JJ |
24 | BoolSimplifiedType, |
25 | CharSimplifiedType, | |
5869c6ff XL |
26 | IntSimplifiedType(ty::IntTy), |
27 | UintSimplifiedType(ty::UintTy), | |
28 | FloatSimplifiedType(ty::FloatTy), | |
ea8adc8c | 29 | AdtSimplifiedType(D), |
a2a8927a | 30 | ForeignSimplifiedType(D), |
1a4d82fc | 31 | StrSimplifiedType, |
c30ab7b3 | 32 | ArraySimplifiedType, |
a2a8927a XL |
33 | SliceSimplifiedType, |
34 | RefSimplifiedType(Mutability), | |
35 | PtrSimplifiedType(Mutability), | |
5bcae85e | 36 | NeverSimplifiedType, |
c34b1796 | 37 | TupleSimplifiedType(usize), |
0731742a XL |
38 | /// A trait object, all of whose components are markers |
39 | /// (e.g., `dyn Send + Sync`). | |
40 | MarkerTraitObjectSimplifiedType, | |
ea8adc8c XL |
41 | TraitSimplifiedType(D), |
42 | ClosureSimplifiedType(D), | |
43 | GeneratorSimplifiedType(D), | |
2c00a5a8 | 44 | GeneratorWitnessSimplifiedType(usize), |
c34b1796 | 45 | FunctionSimplifiedType(usize), |
923072b8 | 46 | PlaceholderSimplifiedType, |
1a4d82fc JJ |
47 | } |
48 | ||
923072b8 FG |
49 | /// Generic parameters are pretty much just bound variables, e.g. |
50 | /// the type of `fn foo<'a, T>(x: &'a T) -> u32 { ... }` can be thought of as | |
51 | /// `for<'a, T> fn(&'a T) -> u32`. | |
52 | /// | |
53 | /// Typecheck of `foo` has to succeed for all possible generic arguments, so | |
54 | /// during typeck, we have to treat its generic parameters as if they | |
55 | /// were placeholders. | |
56 | /// | |
57 | /// But when calling `foo` we only have to provide a specific generic argument. | |
58 | /// In that case the generic parameters are instantiated with inference variables. | |
59 | /// As we use `simplify_type` before that instantiation happens, we just treat | |
60 | /// generic parameters as if they were inference variables in that case. | |
a2a8927a | 61 | #[derive(PartialEq, Eq, Debug, Clone, Copy)] |
5e7ed085 | 62 | pub enum TreatParams { |
923072b8 | 63 | /// Treat parameters as placeholders in the given environment. |
5e7ed085 | 64 | /// |
923072b8 FG |
65 | /// Note that this also causes us to treat projections as if they were |
66 | /// placeholders. This is only correct if the given projection cannot | |
67 | /// be normalized in the current context. Even if normalization fails, | |
68 | /// it may still succeed later if the projection contains any inference | |
69 | /// variables. | |
70 | AsPlaceholder, | |
71 | AsInfer, | |
a2a8927a XL |
72 | } |
73 | ||
a2a8927a XL |
74 | /// Tries to simplify a type by only returning the outermost injective¹ layer, if one exists. |
75 | /// | |
923072b8 FG |
76 | /// **This function should only be used if you need to store or retrieve the type from some |
77 | /// hashmap. If you want to quickly decide whether two types may unify, use the [DeepRejectCtxt] | |
78 | /// instead.** | |
79 | /// | |
a2a8927a | 80 | /// The idea is to get something simple that we can use to quickly decide if two types could unify, |
923072b8 FG |
81 | /// for example during method lookup. If this function returns `Some(x)` it can only unify with |
82 | /// types for which this method returns either `Some(x)` as well or `None`. | |
a2a8927a | 83 | /// |
5e7ed085 | 84 | /// A special case here are parameters and projections, which are only injective |
923072b8 | 85 | /// if they are treated as placeholders. |
a2a8927a | 86 | /// |
5e7ed085 | 87 | /// For example when storing impls based on their simplified self type, we treat |
923072b8 | 88 | /// generic parameters as if they were inference variables. We must not simplify them here, |
5e7ed085 | 89 | /// as they can unify with any other type. |
1a4d82fc | 90 | /// |
923072b8 FG |
91 | /// With projections we have to be even more careful, as treating them as placeholders |
92 | /// is only correct if they are fully normalized. | |
a2a8927a | 93 | /// |
5e7ed085 FG |
94 | /// ¹ meaning that if the outermost layers are different, then the whole types are also different. |
95 | pub fn simplify_type<'tcx>( | |
96 | tcx: TyCtxt<'tcx>, | |
97 | ty: Ty<'tcx>, | |
98 | treat_params: TreatParams, | |
dc9dc135 | 99 | ) -> Option<SimplifiedType> { |
1b1a35ee | 100 | match *ty.kind() { |
b7449926 XL |
101 | ty::Bool => Some(BoolSimplifiedType), |
102 | ty::Char => Some(CharSimplifiedType), | |
103 | ty::Int(int_type) => Some(IntSimplifiedType(int_type)), | |
104 | ty::Uint(uint_type) => Some(UintSimplifiedType(uint_type)), | |
105 | ty::Float(float_type) => Some(FloatSimplifiedType(float_type)), | |
5e7ed085 | 106 | ty::Adt(def, _) => Some(AdtSimplifiedType(def.did())), |
b7449926 | 107 | ty::Str => Some(StrSimplifiedType), |
a2a8927a XL |
108 | ty::Array(..) => Some(ArraySimplifiedType), |
109 | ty::Slice(..) => Some(SliceSimplifiedType), | |
110 | ty::RawPtr(ptr) => Some(PtrSimplifiedType(ptr.mutbl)), | |
5e7ed085 | 111 | ty::Dynamic(trait_info, ..) => match trait_info.principal_def_id() { |
dfeec247 XL |
112 | Some(principal_def_id) if !tcx.trait_is_auto(principal_def_id) => { |
113 | Some(TraitSimplifiedType(principal_def_id)) | |
0731742a | 114 | } |
dfeec247 XL |
115 | _ => Some(MarkerTraitObjectSimplifiedType), |
116 | }, | |
5099ac24 | 117 | ty::Ref(_, _, mutbl) => Some(RefSimplifiedType(mutbl)), |
dfeec247 XL |
118 | ty::FnDef(def_id, _) | ty::Closure(def_id, _) => Some(ClosureSimplifiedType(def_id)), |
119 | ty::Generator(def_id, _, _) => Some(GeneratorSimplifiedType(def_id)), | |
5e7ed085 | 120 | ty::GeneratorWitness(tys) => Some(GeneratorWitnessSimplifiedType(tys.skip_binder().len())), |
b7449926 | 121 | ty::Never => Some(NeverSimplifiedType), |
5e7ed085 FG |
122 | ty::Tuple(tys) => Some(TupleSimplifiedType(tys.len())), |
123 | ty::FnPtr(f) => Some(FunctionSimplifiedType(f.skip_binder().inputs().len())), | |
923072b8 FG |
124 | ty::Placeholder(..) => Some(PlaceholderSimplifiedType), |
125 | ty::Param(_) => match treat_params { | |
126 | TreatParams::AsPlaceholder => Some(PlaceholderSimplifiedType), | |
127 | TreatParams::AsInfer => None, | |
128 | }, | |
487cf647 | 129 | ty::Opaque(..) | ty::Projection(_) => match treat_params { |
923072b8 FG |
130 | // When treating `ty::Param` as a placeholder, projections also |
131 | // don't unify with anything else as long as they are fully normalized. | |
5e7ed085 FG |
132 | // |
133 | // We will have to be careful with lazy normalization here. | |
2b03887a | 134 | TreatParams::AsPlaceholder if !ty.has_non_region_infer() => { |
923072b8 FG |
135 | debug!("treating `{}` as a placeholder", ty); |
136 | Some(PlaceholderSimplifiedType) | |
1a4d82fc | 137 | } |
923072b8 | 138 | TreatParams::AsPlaceholder | TreatParams::AsInfer => None, |
5e7ed085 | 139 | }, |
dfeec247 | 140 | ty::Foreign(def_id) => Some(ForeignSimplifiedType(def_id)), |
923072b8 | 141 | ty::Bound(..) | ty::Infer(_) | ty::Error(_) => None, |
1a4d82fc JJ |
142 | } |
143 | } | |
ea8adc8c | 144 | |
5e7ed085 | 145 | impl<D: Copy + Debug + Eq> SimplifiedTypeGen<D> { |
a2a8927a XL |
146 | pub fn def(self) -> Option<D> { |
147 | match self { | |
148 | AdtSimplifiedType(d) | |
149 | | ForeignSimplifiedType(d) | |
150 | | TraitSimplifiedType(d) | |
151 | | ClosureSimplifiedType(d) | |
487cf647 | 152 | | GeneratorSimplifiedType(d) => Some(d), |
a2a8927a XL |
153 | _ => None, |
154 | } | |
155 | } | |
156 | ||
ea8adc8c | 157 | pub fn map_def<U, F>(self, map: F) -> SimplifiedTypeGen<U> |
dfeec247 XL |
158 | where |
159 | F: Fn(D) -> U, | |
5e7ed085 | 160 | U: Copy + Debug + Eq, |
ea8adc8c XL |
161 | { |
162 | match self { | |
163 | BoolSimplifiedType => BoolSimplifiedType, | |
164 | CharSimplifiedType => CharSimplifiedType, | |
165 | IntSimplifiedType(t) => IntSimplifiedType(t), | |
166 | UintSimplifiedType(t) => UintSimplifiedType(t), | |
167 | FloatSimplifiedType(t) => FloatSimplifiedType(t), | |
168 | AdtSimplifiedType(d) => AdtSimplifiedType(map(d)), | |
a2a8927a | 169 | ForeignSimplifiedType(d) => ForeignSimplifiedType(map(d)), |
ea8adc8c XL |
170 | StrSimplifiedType => StrSimplifiedType, |
171 | ArraySimplifiedType => ArraySimplifiedType, | |
a2a8927a XL |
172 | SliceSimplifiedType => SliceSimplifiedType, |
173 | RefSimplifiedType(m) => RefSimplifiedType(m), | |
174 | PtrSimplifiedType(m) => PtrSimplifiedType(m), | |
ea8adc8c | 175 | NeverSimplifiedType => NeverSimplifiedType, |
0731742a | 176 | MarkerTraitObjectSimplifiedType => MarkerTraitObjectSimplifiedType, |
ea8adc8c XL |
177 | TupleSimplifiedType(n) => TupleSimplifiedType(n), |
178 | TraitSimplifiedType(d) => TraitSimplifiedType(map(d)), | |
179 | ClosureSimplifiedType(d) => ClosureSimplifiedType(map(d)), | |
180 | GeneratorSimplifiedType(d) => GeneratorSimplifiedType(map(d)), | |
2c00a5a8 | 181 | GeneratorWitnessSimplifiedType(n) => GeneratorWitnessSimplifiedType(n), |
ea8adc8c | 182 | FunctionSimplifiedType(n) => FunctionSimplifiedType(n), |
923072b8 | 183 | PlaceholderSimplifiedType => PlaceholderSimplifiedType, |
ea8adc8c XL |
184 | } |
185 | } | |
186 | } | |
187 | ||
923072b8 FG |
188 | /// Given generic arguments from an obligation and an impl, |
189 | /// could these two be unified after replacing parameters in the | |
190 | /// the impl with inference variables. | |
191 | /// | |
192 | /// For obligations, parameters won't be replaced by inference | |
193 | /// variables and only unify with themselves. We treat them | |
194 | /// the same way we treat placeholders. | |
195 | /// | |
196 | /// We also use this function during coherence. For coherence the | |
197 | /// impls only have to overlap for some value, so we treat parameters | |
198 | /// on both sides like inference variables. This behavior is toggled | |
199 | /// using the `treat_obligation_params` field. | |
200 | #[derive(Debug, Clone, Copy)] | |
201 | pub struct DeepRejectCtxt { | |
202 | pub treat_obligation_params: TreatParams, | |
203 | } | |
204 | ||
205 | impl DeepRejectCtxt { | |
206 | pub fn generic_args_may_unify<'tcx>( | |
207 | self, | |
208 | obligation_arg: ty::GenericArg<'tcx>, | |
209 | impl_arg: ty::GenericArg<'tcx>, | |
210 | ) -> bool { | |
211 | match (obligation_arg.unpack(), impl_arg.unpack()) { | |
212 | // We don't fast reject based on regions for now. | |
213 | (GenericArgKind::Lifetime(_), GenericArgKind::Lifetime(_)) => true, | |
214 | (GenericArgKind::Type(obl), GenericArgKind::Type(imp)) => { | |
215 | self.types_may_unify(obl, imp) | |
216 | } | |
217 | (GenericArgKind::Const(obl), GenericArgKind::Const(imp)) => { | |
218 | self.consts_may_unify(obl, imp) | |
219 | } | |
220 | _ => bug!("kind mismatch: {obligation_arg} {impl_arg}"), | |
221 | } | |
222 | } | |
223 | ||
224 | pub fn types_may_unify<'tcx>(self, obligation_ty: Ty<'tcx>, impl_ty: Ty<'tcx>) -> bool { | |
225 | match impl_ty.kind() { | |
226 | // Start by checking whether the type in the impl may unify with | |
227 | // pretty much everything. Just return `true` in that case. | |
487cf647 | 228 | ty::Param(_) | ty::Projection(_) | ty::Error(_) | ty::Opaque(..) => return true, |
923072b8 FG |
229 | // These types only unify with inference variables or their own |
230 | // variant. | |
231 | ty::Bool | |
232 | | ty::Char | |
233 | | ty::Int(_) | |
234 | | ty::Uint(_) | |
235 | | ty::Float(_) | |
236 | | ty::Adt(..) | |
237 | | ty::Str | |
238 | | ty::Array(..) | |
239 | | ty::Slice(..) | |
240 | | ty::RawPtr(..) | |
241 | | ty::Dynamic(..) | |
242 | | ty::Ref(..) | |
243 | | ty::Never | |
244 | | ty::Tuple(..) | |
245 | | ty::FnPtr(..) | |
487cf647 | 246 | | ty::Foreign(..) => {} |
923072b8 FG |
247 | ty::FnDef(..) |
248 | | ty::Closure(..) | |
249 | | ty::Generator(..) | |
250 | | ty::GeneratorWitness(..) | |
251 | | ty::Placeholder(..) | |
252 | | ty::Bound(..) | |
253 | | ty::Infer(_) => bug!("unexpected impl_ty: {impl_ty}"), | |
254 | } | |
255 | ||
256 | let k = impl_ty.kind(); | |
257 | match *obligation_ty.kind() { | |
258 | // Purely rigid types, use structural equivalence. | |
259 | ty::Bool | |
260 | | ty::Char | |
261 | | ty::Int(_) | |
262 | | ty::Uint(_) | |
263 | | ty::Float(_) | |
264 | | ty::Str | |
265 | | ty::Never | |
266 | | ty::Foreign(_) => obligation_ty == impl_ty, | |
267 | ty::Ref(_, obl_ty, obl_mutbl) => match k { | |
268 | &ty::Ref(_, impl_ty, impl_mutbl) => { | |
269 | obl_mutbl == impl_mutbl && self.types_may_unify(obl_ty, impl_ty) | |
270 | } | |
271 | _ => false, | |
272 | }, | |
273 | ty::Adt(obl_def, obl_substs) => match k { | |
274 | &ty::Adt(impl_def, impl_substs) => { | |
275 | obl_def == impl_def | |
276 | && iter::zip(obl_substs, impl_substs) | |
277 | .all(|(obl, imp)| self.generic_args_may_unify(obl, imp)) | |
278 | } | |
279 | _ => false, | |
280 | }, | |
281 | ty::Slice(obl_ty) => { | |
282 | matches!(k, &ty::Slice(impl_ty) if self.types_may_unify(obl_ty, impl_ty)) | |
283 | } | |
284 | ty::Array(obl_ty, obl_len) => match k { | |
285 | &ty::Array(impl_ty, impl_len) => { | |
286 | self.types_may_unify(obl_ty, impl_ty) | |
287 | && self.consts_may_unify(obl_len, impl_len) | |
288 | } | |
289 | _ => false, | |
290 | }, | |
291 | ty::Tuple(obl) => match k { | |
292 | &ty::Tuple(imp) => { | |
293 | obl.len() == imp.len() | |
294 | && iter::zip(obl, imp).all(|(obl, imp)| self.types_may_unify(obl, imp)) | |
295 | } | |
296 | _ => false, | |
297 | }, | |
298 | ty::RawPtr(obl) => match k { | |
299 | ty::RawPtr(imp) => obl.mutbl == imp.mutbl && self.types_may_unify(obl.ty, imp.ty), | |
300 | _ => false, | |
301 | }, | |
302 | ty::Dynamic(obl_preds, ..) => { | |
303 | // Ideally we would walk the existential predicates here or at least | |
304 | // compare their length. But considering that the relevant `Relate` impl | |
305 | // actually sorts and deduplicates these, that doesn't work. | |
306 | matches!(k, ty::Dynamic(impl_preds, ..) if | |
307 | obl_preds.principal_def_id() == impl_preds.principal_def_id() | |
308 | ) | |
309 | } | |
310 | ty::FnPtr(obl_sig) => match k { | |
311 | ty::FnPtr(impl_sig) => { | |
312 | let ty::FnSig { inputs_and_output, c_variadic, unsafety, abi } = | |
313 | obl_sig.skip_binder(); | |
314 | let impl_sig = impl_sig.skip_binder(); | |
315 | ||
316 | abi == impl_sig.abi | |
317 | && c_variadic == impl_sig.c_variadic | |
318 | && unsafety == impl_sig.unsafety | |
319 | && inputs_and_output.len() == impl_sig.inputs_and_output.len() | |
320 | && iter::zip(inputs_and_output, impl_sig.inputs_and_output) | |
321 | .all(|(obl, imp)| self.types_may_unify(obl, imp)) | |
322 | } | |
323 | _ => false, | |
324 | }, | |
325 | ||
487cf647 | 326 | ty::Opaque(..) => true, |
923072b8 FG |
327 | |
328 | // Impls cannot contain these types as these cannot be named directly. | |
329 | ty::FnDef(..) | ty::Closure(..) | ty::Generator(..) => false, | |
330 | ||
331 | ty::Placeholder(..) => false, | |
332 | ||
333 | // Depending on the value of `treat_obligation_params`, we either | |
334 | // treat generic parameters like placeholders or like inference variables. | |
335 | ty::Param(_) => match self.treat_obligation_params { | |
336 | TreatParams::AsPlaceholder => false, | |
337 | TreatParams::AsInfer => true, | |
338 | }, | |
339 | ||
340 | ty::Infer(_) => true, | |
341 | ||
342 | // As we're walking the whole type, it may encounter projections | |
343 | // inside of binders and what not, so we're just going to assume that | |
344 | // projections can unify with other stuff. | |
345 | // | |
346 | // Looking forward to lazy normalization this is the safer strategy anyways. | |
347 | ty::Projection(_) => true, | |
348 | ||
349 | ty::Error(_) => true, | |
350 | ||
351 | ty::GeneratorWitness(..) | ty::Bound(..) => { | |
352 | bug!("unexpected obligation type: {:?}", obligation_ty) | |
353 | } | |
354 | } | |
355 | } | |
356 | ||
357 | pub fn consts_may_unify(self, obligation_ct: ty::Const<'_>, impl_ct: ty::Const<'_>) -> bool { | |
358 | match impl_ct.kind() { | |
487cf647 FG |
359 | ty::ConstKind::Expr(_) |
360 | | ty::ConstKind::Param(_) | |
361 | | ty::ConstKind::Unevaluated(_) | |
362 | | ty::ConstKind::Error(_) => { | |
923072b8 FG |
363 | return true; |
364 | } | |
365 | ty::ConstKind::Value(_) => {} | |
366 | ty::ConstKind::Infer(_) | ty::ConstKind::Bound(..) | ty::ConstKind::Placeholder(_) => { | |
367 | bug!("unexpected impl arg: {:?}", impl_ct) | |
368 | } | |
369 | } | |
370 | ||
371 | let k = impl_ct.kind(); | |
372 | match obligation_ct.kind() { | |
373 | ty::ConstKind::Param(_) => match self.treat_obligation_params { | |
374 | TreatParams::AsPlaceholder => false, | |
375 | TreatParams::AsInfer => true, | |
376 | }, | |
377 | ||
378 | // As we don't necessarily eagerly evaluate constants, | |
379 | // they might unify with any value. | |
487cf647 FG |
380 | ty::ConstKind::Expr(_) | ty::ConstKind::Unevaluated(_) | ty::ConstKind::Error(_) => { |
381 | true | |
382 | } | |
923072b8 | 383 | ty::ConstKind::Value(obl) => match k { |
2b03887a | 384 | ty::ConstKind::Value(imp) => obl == imp, |
923072b8 FG |
385 | _ => true, |
386 | }, | |
387 | ||
388 | ty::ConstKind::Infer(_) => true, | |
389 | ||
390 | ty::ConstKind::Bound(..) | ty::ConstKind::Placeholder(_) => { | |
391 | bug!("unexpected obl const: {:?}", obligation_ct) | |
ea8adc8c | 392 | } |
ea8adc8c XL |
393 | } |
394 | } | |
395 | } |