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