]>
Commit | Line | Data |
---|---|---|
ff7c6d11 XL |
1 | // Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT |
2 | // file at the top-level directory of this distribution and at | |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
10 | ||
11 | use hir::def_id::DefId; | |
94b46f34 | 12 | use hir; |
b7449926 | 13 | use hir::Node; |
ff7c6d11 XL |
14 | use infer::{self, InferCtxt, InferOk, TypeVariableOrigin}; |
15 | use infer::outlives::free_region_map::FreeRegionRelations; | |
16 | use rustc_data_structures::fx::FxHashMap; | |
17 | use syntax::ast; | |
18 | use traits::{self, PredicateObligation}; | |
94b46f34 | 19 | use ty::{self, Ty, TyCtxt, GenericParamDefKind}; |
0531ce1d | 20 | use ty::fold::{BottomUpFolder, TypeFoldable, TypeFolder}; |
ff7c6d11 | 21 | use ty::outlives::Component; |
0531ce1d | 22 | use ty::subst::{Kind, Substs, UnpackedKind}; |
ff7c6d11 XL |
23 | use util::nodemap::DefIdMap; |
24 | ||
b7449926 | 25 | pub type OpaqueTypeMap<'tcx> = DefIdMap<OpaqueTypeDecl<'tcx>>; |
ff7c6d11 | 26 | |
b7449926 | 27 | /// Information about the opaque, abstract types whose values we |
ff7c6d11 XL |
28 | /// are inferring in this function (these are the `impl Trait` that |
29 | /// appear in the return type). | |
30 | #[derive(Copy, Clone, Debug)] | |
b7449926 | 31 | pub struct OpaqueTypeDecl<'tcx> { |
ff7c6d11 XL |
32 | /// The substitutions that we apply to the abstract that that this |
33 | /// `impl Trait` desugars to. e.g., if: | |
34 | /// | |
35 | /// fn foo<'a, 'b, T>() -> impl Trait<'a> | |
36 | /// | |
37 | /// winds up desugared to: | |
38 | /// | |
39 | /// abstract type Foo<'x, T>: Trait<'x> | |
40 | /// fn foo<'a, 'b, T>() -> Foo<'a, T> | |
41 | /// | |
42 | /// then `substs` would be `['a, T]`. | |
43 | pub substs: &'tcx Substs<'tcx>, | |
44 | ||
45 | /// The type variable that represents the value of the abstract type | |
46 | /// that we require. In other words, after we compile this function, | |
47 | /// we will be created a constraint like: | |
48 | /// | |
49 | /// Foo<'a, T> = ?C | |
50 | /// | |
51 | /// where `?C` is the value of this type variable. =) It may | |
52 | /// naturally refer to the type and lifetime parameters in scope | |
53 | /// in this function, though ultimately it should only reference | |
54 | /// those that are arguments to `Foo` in the constraint above. (In | |
55 | /// other words, `?C` should not include `'b`, even though it's a | |
56 | /// lifetime parameter on `foo`.) | |
57 | pub concrete_ty: Ty<'tcx>, | |
58 | ||
59 | /// True if the `impl Trait` bounds include region bounds. | |
60 | /// For example, this would be true for: | |
61 | /// | |
62 | /// fn foo<'a, 'b, 'c>() -> impl Trait<'c> + 'a + 'b | |
63 | /// | |
64 | /// but false for: | |
65 | /// | |
66 | /// fn foo<'c>() -> impl Trait<'c> | |
67 | /// | |
68 | /// unless `Trait` was declared like: | |
69 | /// | |
70 | /// trait Trait<'c>: 'c | |
71 | /// | |
72 | /// in which case it would be true. | |
73 | /// | |
74 | /// This is used during regionck to decide whether we need to | |
75 | /// impose any additional constraints to ensure that region | |
76 | /// variables in `concrete_ty` wind up being constrained to | |
77 | /// something from `substs` (or, at minimum, things that outlive | |
78 | /// the fn body). (Ultimately, writeback is responsible for this | |
79 | /// check.) | |
80 | pub has_required_region_bounds: bool, | |
81 | } | |
82 | ||
83 | impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> { | |
b7449926 | 84 | /// Replace all opaque types in `value` with fresh inference variables |
ff7c6d11 XL |
85 | /// and creates appropriate obligations. For example, given the input: |
86 | /// | |
87 | /// impl Iterator<Item = impl Debug> | |
88 | /// | |
89 | /// this method would create two type variables, `?0` and `?1`. It would | |
90 | /// return the type `?0` but also the obligations: | |
91 | /// | |
92 | /// ?0: Iterator<Item = ?1> | |
93 | /// ?1: Debug | |
94 | /// | |
b7449926 | 95 | /// Moreover, it returns a `OpaqueTypeMap` that would map `?0` to |
ff7c6d11 XL |
96 | /// info about the `impl Iterator<..>` type and `?1` to info about |
97 | /// the `impl Debug` type. | |
98 | /// | |
99 | /// # Parameters | |
100 | /// | |
0bf4aa26 XL |
101 | /// - `parent_def_id` -- the def-id of the function in which the opaque type |
102 | /// is defined | |
ff7c6d11 XL |
103 | /// - `body_id` -- the body-id with which the resulting obligations should |
104 | /// be associated | |
105 | /// - `param_env` -- the in-scope parameter environment to be used for | |
106 | /// obligations | |
b7449926 XL |
107 | /// - `value` -- the value within which we are instantiating opaque types |
108 | pub fn instantiate_opaque_types<T: TypeFoldable<'tcx>>( | |
ff7c6d11 XL |
109 | &self, |
110 | parent_def_id: DefId, | |
111 | body_id: ast::NodeId, | |
112 | param_env: ty::ParamEnv<'tcx>, | |
113 | value: &T, | |
b7449926 | 114 | ) -> InferOk<'tcx, (T, OpaqueTypeMap<'tcx>)> { |
0bf4aa26 XL |
115 | debug!("instantiate_opaque_types(value={:?}, parent_def_id={:?}, body_id={:?}, \ |
116 | param_env={:?})", | |
117 | value, parent_def_id, body_id, param_env, | |
ff7c6d11 XL |
118 | ); |
119 | let mut instantiator = Instantiator { | |
120 | infcx: self, | |
121 | parent_def_id, | |
122 | body_id, | |
123 | param_env, | |
a1dfa0c6 | 124 | opaque_types: Default::default(), |
ff7c6d11 XL |
125 | obligations: vec![], |
126 | }; | |
b7449926 | 127 | let value = instantiator.instantiate_opaque_types_in_map(value); |
ff7c6d11 | 128 | InferOk { |
b7449926 | 129 | value: (value, instantiator.opaque_types), |
ff7c6d11 XL |
130 | obligations: instantiator.obligations, |
131 | } | |
132 | } | |
133 | ||
b7449926 | 134 | /// Given the map `opaque_types` containing the existential `impl |
ff7c6d11 XL |
135 | /// Trait` types whose underlying, hidden types are being |
136 | /// inferred, this method adds constraints to the regions | |
137 | /// appearing in those underlying hidden types to ensure that they | |
138 | /// at least do not refer to random scopes within the current | |
139 | /// function. These constraints are not (quite) sufficient to | |
140 | /// guarantee that the regions are actually legal values; that | |
141 | /// final condition is imposed after region inference is done. | |
142 | /// | |
143 | /// # The Problem | |
144 | /// | |
145 | /// Let's work through an example to explain how it works. Assume | |
146 | /// the current function is as follows: | |
147 | /// | |
148 | /// ```text | |
149 | /// fn foo<'a, 'b>(..) -> (impl Bar<'a>, impl Bar<'b>) | |
150 | /// ``` | |
151 | /// | |
152 | /// Here, we have two `impl Trait` types whose values are being | |
153 | /// inferred (the `impl Bar<'a>` and the `impl | |
154 | /// Bar<'b>`). Conceptually, this is sugar for a setup where we | |
155 | /// define underlying abstract types (`Foo1`, `Foo2`) and then, in | |
156 | /// the return type of `foo`, we *reference* those definitions: | |
157 | /// | |
158 | /// ```text | |
159 | /// abstract type Foo1<'x>: Bar<'x>; | |
160 | /// abstract type Foo2<'x>: Bar<'x>; | |
161 | /// fn foo<'a, 'b>(..) -> (Foo1<'a>, Foo2<'b>) { .. } | |
162 | /// // ^^^^ ^^ | |
163 | /// // | | | |
164 | /// // | substs | |
165 | /// // def_id | |
166 | /// ``` | |
167 | /// | |
168 | /// As indicating in the comments above, each of those references | |
169 | /// is (in the compiler) basically a substitution (`substs`) | |
170 | /// applied to the type of a suitable `def_id` (which identifies | |
171 | /// `Foo1` or `Foo2`). | |
172 | /// | |
173 | /// Now, at this point in compilation, what we have done is to | |
174 | /// replace each of the references (`Foo1<'a>`, `Foo2<'b>`) with | |
175 | /// fresh inference variables C1 and C2. We wish to use the values | |
176 | /// of these variables to infer the underlying types of `Foo1` and | |
177 | /// `Foo2`. That is, this gives rise to higher-order (pattern) unification | |
178 | /// constraints like: | |
179 | /// | |
180 | /// ```text | |
181 | /// for<'a> (Foo1<'a> = C1) | |
182 | /// for<'b> (Foo1<'b> = C2) | |
183 | /// ``` | |
184 | /// | |
185 | /// For these equation to be satisfiable, the types `C1` and `C2` | |
186 | /// can only refer to a limited set of regions. For example, `C1` | |
187 | /// can only refer to `'static` and `'a`, and `C2` can only refer | |
188 | /// to `'static` and `'b`. The job of this function is to impose that | |
189 | /// constraint. | |
190 | /// | |
191 | /// Up to this point, C1 and C2 are basically just random type | |
192 | /// inference variables, and hence they may contain arbitrary | |
193 | /// regions. In fact, it is fairly likely that they do! Consider | |
194 | /// this possible definition of `foo`: | |
195 | /// | |
196 | /// ```text | |
197 | /// fn foo<'a, 'b>(x: &'a i32, y: &'b i32) -> (impl Bar<'a>, impl Bar<'b>) { | |
198 | /// (&*x, &*y) | |
199 | /// } | |
200 | /// ``` | |
201 | /// | |
202 | /// Here, the values for the concrete types of the two impl | |
203 | /// traits will include inference variables: | |
204 | /// | |
205 | /// ```text | |
206 | /// &'0 i32 | |
207 | /// &'1 i32 | |
208 | /// ``` | |
209 | /// | |
210 | /// Ordinarily, the subtyping rules would ensure that these are | |
211 | /// sufficiently large. But since `impl Bar<'a>` isn't a specific | |
212 | /// type per se, we don't get such constraints by default. This | |
213 | /// is where this function comes into play. It adds extra | |
214 | /// constraints to ensure that all the regions which appear in the | |
215 | /// inferred type are regions that could validly appear. | |
216 | /// | |
217 | /// This is actually a bit of a tricky constraint in general. We | |
218 | /// want to say that each variable (e.g., `'0`) can only take on | |
219 | /// values that were supplied as arguments to the abstract type | |
220 | /// (e.g., `'a` for `Foo1<'a>`) or `'static`, which is always in | |
221 | /// scope. We don't have a constraint quite of this kind in the current | |
222 | /// region checker. | |
223 | /// | |
224 | /// # The Solution | |
225 | /// | |
226 | /// We make use of the constraint that we *do* have in the `<=` | |
227 | /// relation. To do that, we find the "minimum" of all the | |
228 | /// arguments that appear in the substs: that is, some region | |
229 | /// which is less than all the others. In the case of `Foo1<'a>`, | |
230 | /// that would be `'a` (it's the only choice, after all). Then we | |
231 | /// apply that as a least bound to the variables (e.g., `'a <= | |
232 | /// '0`). | |
233 | /// | |
234 | /// In some cases, there is no minimum. Consider this example: | |
235 | /// | |
236 | /// ```text | |
237 | /// fn baz<'a, 'b>() -> impl Trait<'a, 'b> { ... } | |
238 | /// ``` | |
239 | /// | |
240 | /// Here we would report an error, because `'a` and `'b` have no | |
241 | /// relation to one another. | |
242 | /// | |
243 | /// # The `free_region_relations` parameter | |
244 | /// | |
245 | /// The `free_region_relations` argument is used to find the | |
246 | /// "minimum" of the regions supplied to a given abstract type. | |
247 | /// It must be a relation that can answer whether `'a <= 'b`, | |
248 | /// where `'a` and `'b` are regions that appear in the "substs" | |
249 | /// for the abstract type references (the `<'a>` in `Foo1<'a>`). | |
250 | /// | |
251 | /// Note that we do not impose the constraints based on the | |
252 | /// generic regions from the `Foo1` definition (e.g., `'x`). This | |
253 | /// is because the constraints we are imposing here is basically | |
254 | /// the concern of the one generating the constraining type C1, | |
255 | /// which is the current function. It also means that we can | |
256 | /// take "implied bounds" into account in some cases: | |
257 | /// | |
258 | /// ```text | |
259 | /// trait SomeTrait<'a, 'b> { } | |
260 | /// fn foo<'a, 'b>(_: &'a &'b u32) -> impl SomeTrait<'a, 'b> { .. } | |
261 | /// ``` | |
262 | /// | |
263 | /// Here, the fact that `'b: 'a` is known only because of the | |
264 | /// implied bounds from the `&'a &'b u32` parameter, and is not | |
265 | /// "inherent" to the abstract type definition. | |
266 | /// | |
267 | /// # Parameters | |
268 | /// | |
b7449926 | 269 | /// - `opaque_types` -- the map produced by `instantiate_opaque_types` |
ff7c6d11 XL |
270 | /// - `free_region_relations` -- something that can be used to relate |
271 | /// the free regions (`'a`) that appear in the impl trait. | |
b7449926 | 272 | pub fn constrain_opaque_types<FRR: FreeRegionRelations<'tcx>>( |
ff7c6d11 | 273 | &self, |
b7449926 | 274 | opaque_types: &OpaqueTypeMap<'tcx>, |
ff7c6d11 XL |
275 | free_region_relations: &FRR, |
276 | ) { | |
b7449926 | 277 | debug!("constrain_opaque_types()"); |
ff7c6d11 | 278 | |
b7449926 XL |
279 | for (&def_id, opaque_defn) in opaque_types { |
280 | self.constrain_opaque_type(def_id, opaque_defn, free_region_relations); | |
ff7c6d11 XL |
281 | } |
282 | } | |
283 | ||
0bf4aa26 | 284 | pub fn constrain_opaque_type<FRR: FreeRegionRelations<'tcx>>( |
ff7c6d11 XL |
285 | &self, |
286 | def_id: DefId, | |
b7449926 | 287 | opaque_defn: &OpaqueTypeDecl<'tcx>, |
ff7c6d11 XL |
288 | free_region_relations: &FRR, |
289 | ) { | |
b7449926 XL |
290 | debug!("constrain_opaque_type()"); |
291 | debug!("constrain_opaque_type: def_id={:?}", def_id); | |
292 | debug!("constrain_opaque_type: opaque_defn={:#?}", opaque_defn); | |
ff7c6d11 | 293 | |
b7449926 | 294 | let concrete_ty = self.resolve_type_vars_if_possible(&opaque_defn.concrete_ty); |
ff7c6d11 | 295 | |
b7449926 | 296 | debug!("constrain_opaque_type: concrete_ty={:?}", concrete_ty); |
ff7c6d11 XL |
297 | |
298 | let abstract_type_generics = self.tcx.generics_of(def_id); | |
299 | ||
300 | let span = self.tcx.def_span(def_id); | |
301 | ||
302 | // If there are required region bounds, we can just skip | |
303 | // ahead. There will already be a registered region | |
304 | // obligation related `concrete_ty` to those regions. | |
b7449926 | 305 | if opaque_defn.has_required_region_bounds { |
ff7c6d11 XL |
306 | return; |
307 | } | |
308 | ||
309 | // There were no `required_region_bounds`, | |
310 | // so we have to search for a `least_region`. | |
311 | // Go through all the regions used as arguments to the | |
312 | // abstract type. These are the parameters to the abstract | |
313 | // type; so in our example above, `substs` would contain | |
314 | // `['a]` for the first impl trait and `'b` for the | |
315 | // second. | |
316 | let mut least_region = None; | |
94b46f34 XL |
317 | for param in &abstract_type_generics.params { |
318 | match param.kind { | |
319 | GenericParamDefKind::Lifetime => {} | |
320 | _ => continue | |
321 | } | |
ff7c6d11 | 322 | // Get the value supplied for this region from the substs. |
b7449926 | 323 | let subst_arg = opaque_defn.substs.region_at(param.index as usize); |
ff7c6d11 XL |
324 | |
325 | // Compute the least upper bound of it with the other regions. | |
b7449926 XL |
326 | debug!("constrain_opaque_types: least_region={:?}", least_region); |
327 | debug!("constrain_opaque_types: subst_arg={:?}", subst_arg); | |
ff7c6d11 XL |
328 | match least_region { |
329 | None => least_region = Some(subst_arg), | |
330 | Some(lr) => { | |
331 | if free_region_relations.sub_free_regions(lr, subst_arg) { | |
332 | // keep the current least region | |
333 | } else if free_region_relations.sub_free_regions(subst_arg, lr) { | |
334 | // switch to `subst_arg` | |
335 | least_region = Some(subst_arg); | |
336 | } else { | |
337 | // There are two regions (`lr` and | |
338 | // `subst_arg`) which are not relatable. We can't | |
339 | // find a best choice. | |
340 | self.tcx | |
341 | .sess | |
342 | .struct_span_err(span, "ambiguous lifetime bound in `impl Trait`") | |
343 | .span_label( | |
344 | span, | |
345 | format!("neither `{}` nor `{}` outlives the other", lr, subst_arg), | |
346 | ) | |
347 | .emit(); | |
348 | ||
349 | least_region = Some(self.tcx.mk_region(ty::ReEmpty)); | |
350 | break; | |
351 | } | |
352 | } | |
353 | } | |
354 | } | |
355 | ||
356 | let least_region = least_region.unwrap_or(self.tcx.types.re_static); | |
b7449926 | 357 | debug!("constrain_opaque_types: least_region={:?}", least_region); |
ff7c6d11 XL |
358 | |
359 | // Require that the type `concrete_ty` outlives | |
360 | // `least_region`, modulo any type parameters that appear | |
361 | // in the type, which we ignore. This is because impl | |
362 | // trait values are assumed to capture all the in-scope | |
363 | // type parameters. This little loop here just invokes | |
364 | // `outlives` repeatedly, draining all the nested | |
365 | // obligations that result. | |
366 | let mut types = vec![concrete_ty]; | |
367 | let bound_region = |r| self.sub_regions(infer::CallReturn(span), least_region, r); | |
368 | while let Some(ty) = types.pop() { | |
a1dfa0c6 XL |
369 | let mut components = smallvec![]; |
370 | self.tcx.push_outlives_components(ty, &mut components); | |
ff7c6d11 XL |
371 | while let Some(component) = components.pop() { |
372 | match component { | |
373 | Component::Region(r) => { | |
374 | bound_region(r); | |
375 | } | |
376 | ||
377 | Component::Param(_) => { | |
378 | // ignore type parameters like `T`, they are captured | |
379 | // implicitly by the `impl Trait` | |
380 | } | |
381 | ||
382 | Component::UnresolvedInferenceVariable(_) => { | |
383 | // we should get an error that more type | |
384 | // annotations are needed in this case | |
385 | self.tcx | |
386 | .sess | |
b7449926 | 387 | .delay_span_bug(span, "unresolved inf var in opaque"); |
ff7c6d11 XL |
388 | } |
389 | ||
390 | Component::Projection(ty::ProjectionTy { | |
391 | substs, | |
392 | item_def_id: _, | |
393 | }) => { | |
394 | for r in substs.regions() { | |
395 | bound_region(r); | |
396 | } | |
397 | types.extend(substs.types()); | |
398 | } | |
399 | ||
400 | Component::EscapingProjection(more_components) => { | |
401 | components.extend(more_components); | |
402 | } | |
403 | } | |
404 | } | |
405 | } | |
406 | } | |
407 | ||
b7449926 | 408 | /// Given the fully resolved, instantiated type for an opaque |
ff7c6d11 XL |
409 | /// type, i.e., the value of an inference variable like C1 or C2 |
410 | /// (*), computes the "definition type" for an abstract type | |
411 | /// definition -- that is, the inferred value of `Foo1<'x>` or | |
412 | /// `Foo2<'x>` that we would conceptually use in its definition: | |
413 | /// | |
414 | /// abstract type Foo1<'x>: Bar<'x> = AAA; <-- this type AAA | |
415 | /// abstract type Foo2<'x>: Bar<'x> = BBB; <-- or this type BBB | |
416 | /// fn foo<'a, 'b>(..) -> (Foo1<'a>, Foo2<'b>) { .. } | |
417 | /// | |
418 | /// Note that these values are defined in terms of a distinct set of | |
419 | /// generic parameters (`'x` instead of `'a`) from C1 or C2. The main | |
420 | /// purpose of this function is to do that translation. | |
421 | /// | |
422 | /// (*) C1 and C2 were introduced in the comments on | |
b7449926 | 423 | /// `constrain_opaque_types`. Read that comment for more context. |
ff7c6d11 XL |
424 | /// |
425 | /// # Parameters | |
426 | /// | |
427 | /// - `def_id`, the `impl Trait` type | |
b7449926 | 428 | /// - `opaque_defn`, the opaque definition created in `instantiate_opaque_types` |
ff7c6d11 | 429 | /// - `instantiated_ty`, the inferred type C1 -- fully resolved, lifted version of |
b7449926 XL |
430 | /// `opaque_defn.concrete_ty` |
431 | pub fn infer_opaque_definition_from_instantiation( | |
ff7c6d11 XL |
432 | &self, |
433 | def_id: DefId, | |
b7449926 | 434 | opaque_defn: &OpaqueTypeDecl<'tcx>, |
ff7c6d11 XL |
435 | instantiated_ty: Ty<'gcx>, |
436 | ) -> Ty<'gcx> { | |
437 | debug!( | |
b7449926 | 438 | "infer_opaque_definition_from_instantiation(def_id={:?}, instantiated_ty={:?})", |
8faf50e0 | 439 | def_id, instantiated_ty |
ff7c6d11 XL |
440 | ); |
441 | ||
442 | let gcx = self.tcx.global_tcx(); | |
443 | ||
444 | // Use substs to build up a reverse map from regions to their | |
445 | // identity mappings. This is necessary because of `impl | |
446 | // Trait` lifetimes are computed by replacing existing | |
447 | // lifetimes with 'static and remapping only those used in the | |
448 | // `impl Trait` return type, resulting in the parameters | |
449 | // shifting. | |
450 | let id_substs = Substs::identity_for_item(gcx, def_id); | |
b7449926 | 451 | let map: FxHashMap<Kind<'tcx>, Kind<'gcx>> = opaque_defn |
ff7c6d11 XL |
452 | .substs |
453 | .iter() | |
454 | .enumerate() | |
455 | .map(|(index, subst)| (*subst, id_substs[index])) | |
456 | .collect(); | |
457 | ||
458 | // Convert the type from the function into a type valid outside | |
459 | // the function, by replacing invalid regions with 'static, | |
460 | // after producing an error for each of them. | |
0531ce1d XL |
461 | let definition_ty = |
462 | instantiated_ty.fold_with(&mut ReverseMapper::new( | |
463 | self.tcx, | |
464 | self.is_tainted_by_errors(), | |
465 | def_id, | |
466 | map, | |
467 | instantiated_ty, | |
468 | )); | |
ff7c6d11 | 469 | debug!( |
b7449926 | 470 | "infer_opaque_definition_from_instantiation: definition_ty={:?}", |
ff7c6d11 XL |
471 | definition_ty |
472 | ); | |
473 | ||
0531ce1d XL |
474 | // We can unwrap here because our reverse mapper always |
475 | // produces things with 'gcx lifetime, though the type folder | |
476 | // obscures that. | |
477 | let definition_ty = gcx.lift(&definition_ty).unwrap(); | |
478 | ||
ff7c6d11 XL |
479 | definition_ty |
480 | } | |
481 | } | |
482 | ||
0531ce1d XL |
483 | struct ReverseMapper<'cx, 'gcx: 'tcx, 'tcx: 'cx> { |
484 | tcx: TyCtxt<'cx, 'gcx, 'tcx>, | |
485 | ||
486 | /// If errors have already been reported in this fn, we suppress | |
487 | /// our own errors because they are sometimes derivative. | |
488 | tainted_by_errors: bool, | |
489 | ||
b7449926 | 490 | opaque_type_def_id: DefId, |
0531ce1d XL |
491 | map: FxHashMap<Kind<'tcx>, Kind<'gcx>>, |
492 | map_missing_regions_to_empty: bool, | |
493 | ||
494 | /// initially `Some`, set to `None` once error has been reported | |
495 | hidden_ty: Option<Ty<'tcx>>, | |
496 | } | |
497 | ||
498 | impl<'cx, 'gcx, 'tcx> ReverseMapper<'cx, 'gcx, 'tcx> { | |
499 | fn new( | |
500 | tcx: TyCtxt<'cx, 'gcx, 'tcx>, | |
501 | tainted_by_errors: bool, | |
b7449926 | 502 | opaque_type_def_id: DefId, |
0531ce1d XL |
503 | map: FxHashMap<Kind<'tcx>, Kind<'gcx>>, |
504 | hidden_ty: Ty<'tcx>, | |
505 | ) -> Self { | |
506 | Self { | |
507 | tcx, | |
508 | tainted_by_errors, | |
b7449926 | 509 | opaque_type_def_id, |
0531ce1d XL |
510 | map, |
511 | map_missing_regions_to_empty: false, | |
512 | hidden_ty: Some(hidden_ty), | |
513 | } | |
514 | } | |
515 | ||
516 | fn fold_kind_mapping_missing_regions_to_empty(&mut self, kind: Kind<'tcx>) -> Kind<'tcx> { | |
517 | assert!(!self.map_missing_regions_to_empty); | |
518 | self.map_missing_regions_to_empty = true; | |
519 | let kind = kind.fold_with(self); | |
520 | self.map_missing_regions_to_empty = false; | |
521 | kind | |
522 | } | |
523 | ||
524 | fn fold_kind_normally(&mut self, kind: Kind<'tcx>) -> Kind<'tcx> { | |
525 | assert!(!self.map_missing_regions_to_empty); | |
526 | kind.fold_with(self) | |
527 | } | |
528 | } | |
529 | ||
530 | impl<'cx, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for ReverseMapper<'cx, 'gcx, 'tcx> { | |
531 | fn tcx(&self) -> TyCtxt<'_, 'gcx, 'tcx> { | |
532 | self.tcx | |
533 | } | |
534 | ||
535 | fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { | |
536 | match r { | |
537 | // ignore bound regions that appear in the type (e.g., this | |
538 | // would ignore `'r` in a type like `for<'r> fn(&'r u32)`. | |
539 | ty::ReLateBound(..) | | |
540 | ||
541 | // ignore `'static`, as that can appear anywhere | |
542 | ty::ReStatic | | |
543 | ||
544 | // ignore `ReScope`, as that can appear anywhere | |
545 | // See `src/test/run-pass/issue-49556.rs` for example. | |
546 | ty::ReScope(..) => return r, | |
547 | ||
548 | _ => { } | |
549 | } | |
550 | ||
551 | match self.map.get(&r.into()).map(|k| k.unpack()) { | |
552 | Some(UnpackedKind::Lifetime(r1)) => r1, | |
553 | Some(u) => panic!("region mapped to unexpected kind: {:?}", u), | |
554 | None => { | |
555 | if !self.map_missing_regions_to_empty && !self.tainted_by_errors { | |
556 | if let Some(hidden_ty) = self.hidden_ty.take() { | |
b7449926 | 557 | let span = self.tcx.def_span(self.opaque_type_def_id); |
0531ce1d XL |
558 | let mut err = struct_span_err!( |
559 | self.tcx.sess, | |
560 | span, | |
94b46f34 | 561 | E0700, |
0531ce1d XL |
562 | "hidden type for `impl Trait` captures lifetime that \ |
563 | does not appear in bounds", | |
564 | ); | |
565 | ||
566 | // Assuming regionck succeeded, then we must | |
567 | // be capturing *some* region from the fn | |
568 | // header, and hence it must be free, so it's | |
569 | // ok to invoke this fn (which doesn't accept | |
570 | // all regions, and would ICE if an | |
571 | // inappropriate region is given). We check | |
572 | // `is_tainted_by_errors` by errors above, so | |
573 | // we don't get in here unless regionck | |
574 | // succeeded. (Note also that if regionck | |
575 | // failed, then the regions we are attempting | |
576 | // to map here may well be giving errors | |
577 | // *because* the constraints were not | |
578 | // satisfiable.) | |
579 | self.tcx.note_and_explain_free_region( | |
580 | &mut err, | |
581 | &format!("hidden type `{}` captures ", hidden_ty), | |
582 | r, | |
583 | "" | |
584 | ); | |
585 | ||
586 | err.emit(); | |
587 | } | |
588 | } | |
589 | self.tcx.types.re_empty | |
590 | }, | |
591 | } | |
592 | } | |
593 | ||
594 | fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> { | |
595 | match ty.sty { | |
b7449926 | 596 | ty::Closure(def_id, substs) => { |
0531ce1d XL |
597 | // I am a horrible monster and I pray for death. When |
598 | // we encounter a closure here, it is always a closure | |
599 | // from within the function that we are currently | |
600 | // type-checking -- one that is now being encapsulated | |
601 | // in an existential abstract type. Ideally, we would | |
602 | // go through the types/lifetimes that it references | |
603 | // and treat them just like we would any other type, | |
604 | // which means we would error out if we find any | |
605 | // reference to a type/region that is not in the | |
606 | // "reverse map". | |
607 | // | |
608 | // **However,** in the case of closures, there is a | |
609 | // somewhat subtle (read: hacky) consideration. The | |
610 | // problem is that our closure types currently include | |
611 | // all the lifetime parameters declared on the | |
612 | // enclosing function, even if they are unused by the | |
613 | // closure itself. We can't readily filter them out, | |
614 | // so here we replace those values with `'empty`. This | |
615 | // can't really make a difference to the rest of the | |
616 | // compiler; those regions are ignored for the | |
617 | // outlives relation, and hence don't affect trait | |
618 | // selection or auto traits, and they are erased | |
94b46f34 | 619 | // during codegen. |
0531ce1d XL |
620 | |
621 | let generics = self.tcx.generics_of(def_id); | |
0531ce1d XL |
622 | let substs = self.tcx.mk_substs(substs.substs.iter().enumerate().map( |
623 | |(index, &kind)| { | |
94b46f34 | 624 | if index < generics.parent_count { |
0531ce1d XL |
625 | // Accommodate missing regions in the parent kinds... |
626 | self.fold_kind_mapping_missing_regions_to_empty(kind) | |
627 | } else { | |
628 | // ...but not elsewhere. | |
629 | self.fold_kind_normally(kind) | |
630 | } | |
631 | }, | |
632 | )); | |
633 | ||
634 | self.tcx.mk_closure(def_id, ty::ClosureSubsts { substs }) | |
635 | } | |
636 | ||
637 | _ => ty.super_fold_with(self), | |
638 | } | |
639 | } | |
640 | } | |
641 | ||
ff7c6d11 XL |
642 | struct Instantiator<'a, 'gcx: 'tcx, 'tcx: 'a> { |
643 | infcx: &'a InferCtxt<'a, 'gcx, 'tcx>, | |
644 | parent_def_id: DefId, | |
645 | body_id: ast::NodeId, | |
646 | param_env: ty::ParamEnv<'tcx>, | |
b7449926 | 647 | opaque_types: OpaqueTypeMap<'tcx>, |
ff7c6d11 XL |
648 | obligations: Vec<PredicateObligation<'tcx>>, |
649 | } | |
650 | ||
651 | impl<'a, 'gcx, 'tcx> Instantiator<'a, 'gcx, 'tcx> { | |
b7449926 XL |
652 | fn instantiate_opaque_types_in_map<T: TypeFoldable<'tcx>>(&mut self, value: &T) -> T { |
653 | debug!("instantiate_opaque_types_in_map(value={:?})", value); | |
ff7c6d11 XL |
654 | let tcx = self.infcx.tcx; |
655 | value.fold_with(&mut BottomUpFolder { | |
656 | tcx, | |
8faf50e0 | 657 | reg_op: |reg| reg, |
ff7c6d11 | 658 | fldop: |ty| { |
b7449926 | 659 | if let ty::Opaque(def_id, substs) = ty.sty { |
ff7c6d11 XL |
660 | // Check that this is `impl Trait` type is |
661 | // declared by `parent_def_id` -- i.e., one whose | |
662 | // value we are inferring. At present, this is | |
663 | // always true during the first phase of | |
664 | // type-check, but not always true later on during | |
665 | // NLL. Once we support named abstract types more fully, | |
666 | // this same scenario will be able to arise during all phases. | |
667 | // | |
668 | // Here is an example using `abstract type` that indicates | |
669 | // the distinction we are checking for: | |
670 | // | |
671 | // ```rust | |
672 | // mod a { | |
673 | // pub abstract type Foo: Iterator; | |
674 | // pub fn make_foo() -> Foo { .. } | |
675 | // } | |
676 | // | |
677 | // mod b { | |
678 | // fn foo() -> a::Foo { a::make_foo() } | |
679 | // } | |
680 | // ``` | |
681 | // | |
682 | // Here, the return type of `foo` references a | |
b7449926 | 683 | // `Opaque` indeed, but not one whose value is |
ff7c6d11 XL |
684 | // presently being inferred. You can get into a |
685 | // similar situation with closure return types | |
686 | // today: | |
687 | // | |
688 | // ```rust | |
689 | // fn foo() -> impl Iterator { .. } | |
690 | // fn bar() { | |
b7449926 | 691 | // let x = || foo(); // returns the Opaque assoc with `foo` |
ff7c6d11 XL |
692 | // } |
693 | // ``` | |
b7449926 | 694 | if let Some(opaque_node_id) = tcx.hir.as_local_node_id(def_id) { |
8faf50e0 XL |
695 | let parent_def_id = self.parent_def_id; |
696 | let def_scope_default = || { | |
b7449926 XL |
697 | let opaque_parent_node_id = tcx.hir.get_parent(opaque_node_id); |
698 | parent_def_id == tcx.hir.local_def_id(opaque_parent_node_id) | |
8faf50e0 | 699 | }; |
b7449926 XL |
700 | let in_definition_scope = match tcx.hir.find(opaque_node_id) { |
701 | Some(Node::Item(item)) => match item.node { | |
8faf50e0 XL |
702 | // impl trait |
703 | hir::ItemKind::Existential(hir::ExistTy { | |
704 | impl_trait_fn: Some(parent), | |
705 | .. | |
706 | }) => parent == self.parent_def_id, | |
707 | // named existential types | |
708 | hir::ItemKind::Existential(hir::ExistTy { | |
709 | impl_trait_fn: None, | |
710 | .. | |
711 | }) => may_define_existential_type( | |
712 | tcx, | |
713 | self.parent_def_id, | |
b7449926 | 714 | opaque_node_id, |
8faf50e0 XL |
715 | ), |
716 | _ => def_scope_default(), | |
717 | }, | |
b7449926 | 718 | Some(Node::ImplItem(item)) => match item.node { |
8faf50e0 XL |
719 | hir::ImplItemKind::Existential(_) => may_define_existential_type( |
720 | tcx, | |
721 | self.parent_def_id, | |
b7449926 | 722 | opaque_node_id, |
8faf50e0 XL |
723 | ), |
724 | _ => def_scope_default(), | |
94b46f34 | 725 | }, |
8faf50e0 XL |
726 | _ => bug!( |
727 | "expected (impl) item, found {}", | |
b7449926 | 728 | tcx.hir.node_to_string(opaque_node_id), |
8faf50e0 | 729 | ), |
94b46f34 | 730 | }; |
8faf50e0 | 731 | if in_definition_scope { |
b7449926 | 732 | return self.fold_opaque_ty(ty, def_id, substs); |
ff7c6d11 XL |
733 | } |
734 | ||
0531ce1d | 735 | debug!( |
b7449926 | 736 | "instantiate_opaque_types_in_map: \ |
0bf4aa26 | 737 | encountered opaque outside its definition scope \ |
8faf50e0 XL |
738 | def_id={:?}", |
739 | def_id, | |
0531ce1d | 740 | ); |
ff7c6d11 XL |
741 | } |
742 | } | |
743 | ||
744 | ty | |
745 | }, | |
746 | }) | |
747 | } | |
748 | ||
b7449926 | 749 | fn fold_opaque_ty( |
ff7c6d11 XL |
750 | &mut self, |
751 | ty: Ty<'tcx>, | |
752 | def_id: DefId, | |
753 | substs: &'tcx Substs<'tcx>, | |
754 | ) -> Ty<'tcx> { | |
755 | let infcx = self.infcx; | |
756 | let tcx = infcx.tcx; | |
757 | ||
758 | debug!( | |
b7449926 | 759 | "instantiate_opaque_types: Opaque(def_id={:?}, substs={:?})", |
0531ce1d | 760 | def_id, substs |
ff7c6d11 XL |
761 | ); |
762 | ||
b7449926 | 763 | // Use the same type variable if the exact same Opaque appears more |
ff7c6d11 | 764 | // than once in the return type (e.g. if it's passed to a type alias). |
b7449926 XL |
765 | if let Some(opaque_defn) = self.opaque_types.get(&def_id) { |
766 | return opaque_defn.concrete_ty; | |
ff7c6d11 XL |
767 | } |
768 | let span = tcx.def_span(def_id); | |
769 | let ty_var = infcx.next_ty_var(TypeVariableOrigin::TypeInference(span)); | |
770 | ||
771 | let predicates_of = tcx.predicates_of(def_id); | |
8faf50e0 | 772 | debug!( |
b7449926 | 773 | "instantiate_opaque_types: predicates: {:#?}", |
8faf50e0 XL |
774 | predicates_of, |
775 | ); | |
ff7c6d11 | 776 | let bounds = predicates_of.instantiate(tcx, substs); |
b7449926 | 777 | debug!("instantiate_opaque_types: bounds={:?}", bounds); |
ff7c6d11 XL |
778 | |
779 | let required_region_bounds = tcx.required_region_bounds(ty, bounds.predicates.clone()); | |
780 | debug!( | |
b7449926 | 781 | "instantiate_opaque_types: required_region_bounds={:?}", |
ff7c6d11 XL |
782 | required_region_bounds |
783 | ); | |
784 | ||
8faf50e0 XL |
785 | // make sure that we are in fact defining the *entire* type |
786 | // e.g. `existential type Foo<T: Bound>: Bar;` needs to be | |
787 | // defined by a function like `fn foo<T: Bound>() -> Foo<T>`. | |
788 | debug!( | |
b7449926 | 789 | "instantiate_opaque_types: param_env: {:#?}", |
8faf50e0 XL |
790 | self.param_env, |
791 | ); | |
792 | debug!( | |
b7449926 | 793 | "instantiate_opaque_types: generics: {:#?}", |
8faf50e0 XL |
794 | tcx.generics_of(def_id), |
795 | ); | |
796 | ||
b7449926 | 797 | self.opaque_types.insert( |
ff7c6d11 | 798 | def_id, |
b7449926 | 799 | OpaqueTypeDecl { |
ff7c6d11 XL |
800 | substs, |
801 | concrete_ty: ty_var, | |
802 | has_required_region_bounds: !required_region_bounds.is_empty(), | |
803 | }, | |
804 | ); | |
b7449926 | 805 | debug!("instantiate_opaque_types: ty_var={:?}", ty_var); |
ff7c6d11 | 806 | |
0bf4aa26 | 807 | self.obligations.reserve(bounds.predicates.len()); |
ff7c6d11 XL |
808 | for predicate in bounds.predicates { |
809 | // Change the predicate to refer to the type variable, | |
0bf4aa26 XL |
810 | // which will be the concrete type instead of the opaque type. |
811 | // This also instantiates nested instances of `impl Trait`. | |
b7449926 | 812 | let predicate = self.instantiate_opaque_types_in_map(&predicate); |
ff7c6d11 XL |
813 | |
814 | let cause = traits::ObligationCause::new(span, self.body_id, traits::SizedReturnType); | |
815 | ||
816 | // Require that the predicate holds for the concrete type. | |
b7449926 | 817 | debug!("instantiate_opaque_types: predicate={:?}", predicate); |
ff7c6d11 XL |
818 | self.obligations |
819 | .push(traits::Obligation::new(cause, self.param_env, predicate)); | |
820 | } | |
821 | ||
822 | ty_var | |
823 | } | |
824 | } | |
8faf50e0 | 825 | |
b7449926 | 826 | /// Whether `opaque_node_id` is a sibling or a child of a sibling of `def_id` |
8faf50e0 XL |
827 | /// |
828 | /// ```rust | |
829 | /// pub mod foo { | |
830 | /// pub mod bar { | |
831 | /// pub existential type Baz; | |
832 | /// | |
833 | /// fn f1() -> Baz { .. } | |
834 | /// } | |
835 | /// | |
836 | /// fn f2() -> bar::Baz { .. } | |
837 | /// } | |
838 | /// ``` | |
839 | /// | |
840 | /// Here, `def_id` will be the `DefId` of the existential type `Baz`. | |
b7449926 XL |
841 | /// `opaque_node_id` is the `NodeId` of the reference to Baz -- |
842 | /// so either the return type of f1 or f2. | |
8faf50e0 XL |
843 | /// We will return true if the reference is within the same module as the existential type |
844 | /// So true for f1, false for f2. | |
845 | pub fn may_define_existential_type( | |
0bf4aa26 | 846 | tcx: TyCtxt<'_, '_, '_>, |
8faf50e0 | 847 | def_id: DefId, |
b7449926 | 848 | opaque_node_id: ast::NodeId, |
8faf50e0 XL |
849 | ) -> bool { |
850 | let mut node_id = tcx | |
851 | .hir | |
852 | .as_local_node_id(def_id) | |
853 | .unwrap(); | |
854 | // named existential types can be defined by any siblings or | |
855 | // children of siblings | |
b7449926 | 856 | let mod_id = tcx.hir.get_parent(opaque_node_id); |
8faf50e0 | 857 | // so we walk up the node tree until we hit the root or the parent |
b7449926 | 858 | // of the opaque type |
8faf50e0 XL |
859 | while node_id != mod_id && node_id != ast::CRATE_NODE_ID { |
860 | node_id = tcx.hir.get_parent(node_id); | |
861 | } | |
862 | // syntactically we are allowed to define the concrete type | |
863 | node_id == mod_id | |
864 | } |