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