src/librustc/infer/opaque_types/mod.rs

   1 use crate::hir;
   2 use crate::hir::def_id::DefId;
   3 use crate::hir::Node;
   4 use crate::infer::outlives::free_region_map::FreeRegionRelations;
   5 use crate::infer::{self, InferCtxt, InferOk, TypeVariableOrigin, TypeVariableOriginKind};
   6 use crate::middle::region;
   7 use crate::traits::{self, PredicateObligation};
   8 use crate::ty::fold::{BottomUpFolder, TypeFoldable, TypeFolder, TypeVisitor};
   9 use crate::ty::subst::{InternalSubsts, Kind, SubstsRef, UnpackedKind};
  10 use crate::ty::{self, GenericParamDefKind, Ty, TyCtxt};
  11 use crate::util::nodemap::DefIdMap;
  12 use rustc_data_structures::fx::FxHashMap;
  13 use std::rc::Rc;
  14
  15 pub type OpaqueTypeMap<'tcx> = DefIdMap<OpaqueTypeDecl<'tcx>>;
  16
  17 /// Information about the opaque, abstract types whose values we
  18 /// are inferring in this function (these are the `impl Trait` that
  19 /// appear in the return type).
  20 #[derive(Copy, Clone, Debug)]
  21 pub struct OpaqueTypeDecl<'tcx> {
  22     /// The substitutions that we apply to the abstract that this
  23     /// `impl Trait` desugars to. e.g., if:
  24     ///
  25     ///     fn foo<'a, 'b, T>() -> impl Trait<'a>
  26     ///
  27     /// winds up desugared to:
  28     ///
  29     ///     abstract type Foo<'x, X>: Trait<'x>
  30     ///     fn foo<'a, 'b, T>() -> Foo<'a, T>
  31     ///
  32     /// then `substs` would be `['a, T]`.
  33     pub substs: SubstsRef<'tcx>,
  34
  35     /// The type variable that represents the value of the abstract type
  36     /// that we require. In other words, after we compile this function,
  37     /// we will be created a constraint like:
  38     ///
  39     ///     Foo<'a, T> = ?C
  40     ///
  41     /// where `?C` is the value of this type variable. =) It may
  42     /// naturally refer to the type and lifetime parameters in scope
  43     /// in this function, though ultimately it should only reference
  44     /// those that are arguments to `Foo` in the constraint above. (In
  45     /// other words, `?C` should not include `'b`, even though it's a
  46     /// lifetime parameter on `foo`.)
  47     pub concrete_ty: Ty<'tcx>,
  48
  49     /// Returns `true` if the `impl Trait` bounds include region bounds.
  50     /// For example, this would be true for:
  51     ///
  52     ///     fn foo<'a, 'b, 'c>() -> impl Trait<'c> + 'a + 'b
  53     ///
  54     /// but false for:
  55     ///
  56     ///     fn foo<'c>() -> impl Trait<'c>
  57     ///
  58     /// unless `Trait` was declared like:
  59     ///
  60     ///     trait Trait<'c>: 'c
  61     ///
  62     /// in which case it would be true.
  63     ///
  64     /// This is used during regionck to decide whether we need to
  65     /// impose any additional constraints to ensure that region
  66     /// variables in `concrete_ty` wind up being constrained to
  67     /// something from `substs` (or, at minimum, things that outlive
  68     /// the fn body). (Ultimately, writeback is responsible for this
  69     /// check.)
  70     pub has_required_region_bounds: bool,
  71
  72     /// The origin of the existential type
  73     pub origin: hir::ExistTyOrigin,
  74 }
  75
  76 impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
  77     /// Replaces all opaque types in `value` with fresh inference variables
  78     /// and creates appropriate obligations. For example, given the input:
  79     ///
  80     ///     impl Iterator<Item = impl Debug>
  81     ///
  82     /// this method would create two type variables, `?0` and `?1`. It would
  83     /// return the type `?0` but also the obligations:
  84     ///
  85     ///     ?0: Iterator<Item = ?1>
  86     ///     ?1: Debug
  87     ///
  88     /// Moreover, it returns a `OpaqueTypeMap` that would map `?0` to
  89     /// info about the `impl Iterator<..>` type and `?1` to info about
  90     /// the `impl Debug` type.
  91     ///
  92     /// # Parameters
  93     ///
  94     /// - `parent_def_id` -- the `DefId` of the function in which the opaque type
  95     ///   is defined
  96     /// - `body_id` -- the body-id with which the resulting obligations should
  97     ///   be associated
  98     /// - `param_env` -- the in-scope parameter environment to be used for
  99     ///   obligations
 100     /// - `value` -- the value within which we are instantiating opaque types
 101     pub fn instantiate_opaque_types<T: TypeFoldable<'tcx>>(
 102         &self,
 103         parent_def_id: DefId,
 104         body_id: hir::HirId,
 105         param_env: ty::ParamEnv<'tcx>,
 106         value: &T,
 107     ) -> InferOk<'tcx, (T, OpaqueTypeMap<'tcx>)> {
 108         debug!(
 109             "instantiate_opaque_types(value={:?}, parent_def_id={:?}, body_id={:?}, \
 110              param_env={:?})",
 111             value, parent_def_id, body_id, param_env,
 112         );
 113         let mut instantiator = Instantiator {
 114             infcx: self,
 115             parent_def_id,
 116             body_id,
 117             param_env,
 118             opaque_types: Default::default(),
 119             obligations: vec![],
 120         };
 121         let value = instantiator.instantiate_opaque_types_in_map(value);
 122         InferOk { value: (value, instantiator.opaque_types), obligations: instantiator.obligations }
 123     }
 124
 125     /// Given the map `opaque_types` containing the existential `impl
 126     /// Trait` types whose underlying, hidden types are being
 127     /// inferred, this method adds constraints to the regions
 128     /// appearing in those underlying hidden types to ensure that they
 129     /// at least do not refer to random scopes within the current
 130     /// function. These constraints are not (quite) sufficient to
 131     /// guarantee that the regions are actually legal values; that
 132     /// final condition is imposed after region inference is done.
 133     ///
 134     /// # The Problem
 135     ///
 136     /// Let's work through an example to explain how it works. Assume
 137     /// the current function is as follows:
 138     ///
 139     /// ```text
 140     /// fn foo<'a, 'b>(..) -> (impl Bar<'a>, impl Bar<'b>)
 141     /// ```
 142     ///
 143     /// Here, we have two `impl Trait` types whose values are being
 144     /// inferred (the `impl Bar<'a>` and the `impl
 145     /// Bar<'b>`). Conceptually, this is sugar for a setup where we
 146     /// define underlying abstract types (`Foo1`, `Foo2`) and then, in
 147     /// the return type of `foo`, we *reference* those definitions:
 148     ///
 149     /// ```text
 150     /// abstract type Foo1<'x>: Bar<'x>;
 151     /// abstract type Foo2<'x>: Bar<'x>;
 152     /// fn foo<'a, 'b>(..) -> (Foo1<'a>, Foo2<'b>) { .. }
 153     ///                    //  ^^^^ ^^
 154     ///                    //  |    |
 155     ///                    //  |    substs
 156     ///                    //  def_id
 157     /// ```
 158     ///
 159     /// As indicating in the comments above, each of those references
 160     /// is (in the compiler) basically a substitution (`substs`)
 161     /// applied to the type of a suitable `def_id` (which identifies
 162     /// `Foo1` or `Foo2`).
 163     ///
 164     /// Now, at this point in compilation, what we have done is to
 165     /// replace each of the references (`Foo1<'a>`, `Foo2<'b>`) with
 166     /// fresh inference variables C1 and C2. We wish to use the values
 167     /// of these variables to infer the underlying types of `Foo1` and
 168     /// `Foo2`. That is, this gives rise to higher-order (pattern) unification
 169     /// constraints like:
 170     ///
 171     /// ```text
 172     /// for<'a> (Foo1<'a> = C1)
 173     /// for<'b> (Foo1<'b> = C2)
 174     /// ```
 175     ///
 176     /// For these equation to be satisfiable, the types `C1` and `C2`
 177     /// can only refer to a limited set of regions. For example, `C1`
 178     /// can only refer to `'static` and `'a`, and `C2` can only refer
 179     /// to `'static` and `'b`. The job of this function is to impose that
 180     /// constraint.
 181     ///
 182     /// Up to this point, C1 and C2 are basically just random type
 183     /// inference variables, and hence they may contain arbitrary
 184     /// regions. In fact, it is fairly likely that they do! Consider
 185     /// this possible definition of `foo`:
 186     ///
 187     /// ```text
 188     /// fn foo<'a, 'b>(x: &'a i32, y: &'b i32) -> (impl Bar<'a>, impl Bar<'b>) {
 189     ///         (&*x, &*y)
 190     ///     }
 191     /// ```
 192     ///
 193     /// Here, the values for the concrete types of the two impl
 194     /// traits will include inference variables:
 195     ///
 196     /// ```text
 197     /// &'0 i32
 198     /// &'1 i32
 199     /// ```
 200     ///
 201     /// Ordinarily, the subtyping rules would ensure that these are
 202     /// sufficiently large. But since `impl Bar<'a>` isn't a specific
 203     /// type per se, we don't get such constraints by default. This
 204     /// is where this function comes into play. It adds extra
 205     /// constraints to ensure that all the regions which appear in the
 206     /// inferred type are regions that could validly appear.
 207     ///
 208     /// This is actually a bit of a tricky constraint in general. We
 209     /// want to say that each variable (e.g., `'0`) can only take on
 210     /// values that were supplied as arguments to the abstract type
 211     /// (e.g., `'a` for `Foo1<'a>`) or `'static`, which is always in
 212     /// scope. We don't have a constraint quite of this kind in the current
 213     /// region checker.
 214     ///
 215     /// # The Solution
 216     ///
 217     /// We generally prefer to make us our `<=` constraints, since
 218     /// they integrate best into the region solve. To do that, we find
 219     /// the "minimum" of all the arguments that appear in the substs:
 220     /// that is, some region which is less than all the others. In the
 221     /// case of `Foo1<'a>`, that would be `'a` (it's the only choice,
 222     /// after all). Then we apply that as a least bound to the
 223     /// variables (e.g., `'a <= '0`).
 224     ///
 225     /// In some cases, there is no minimum. Consider this example:
 226     ///
 227     /// ```text
 228     /// fn baz<'a, 'b>() -> impl Trait<'a, 'b> { ... }
 229     /// ```
 230     ///
 231     /// Here we would report a more complex "in constraint", like `'r
 232     /// in ['a, 'b, 'static]` (where `'r` is some regon appearing in
 233     /// the hidden type).
 234     ///
 235     /// # Constrain regions, not the hidden concrete type
 236     ///
 237     /// Note that generating constraints on each region `Rc` is *not*
 238     /// the same as generating an outlives constraint on `Tc` iself.
 239     /// For example, if we had a function like this:
 240     ///
 241     /// ```rust
 242     /// fn foo<'a, T>(x: &'a u32, y: T) -> impl Foo<'a> {
 243     ///   (x, y)
 244     /// }
 245     ///
 246     /// // Equivalent to:
 247     /// existential type FooReturn<'a, T>: Foo<'a>;
 248     /// fn foo<'a, T>(..) -> FooReturn<'a, T> { .. }
 249     /// ```
 250     ///
 251     /// then the hidden type `Tc` would be `(&'0 u32, T)` (where `'0`
 252     /// is an inference variable). If we generated a constraint that
 253     /// `Tc: 'a`, then this would incorrectly require that `T: 'a` --
 254     /// but this is not necessary, because the existential type we
 255     /// create will be allowed to reference `T`. So instead we just
 256     /// generate a constraint that `'0: 'a`.
 257     ///
 258     /// # The `free_region_relations` parameter
 259     ///
 260     /// The `free_region_relations` argument is used to find the
 261     /// "minimum" of the regions supplied to a given abstract type.
 262     /// It must be a relation that can answer whether `'a <= 'b`,
 263     /// where `'a` and `'b` are regions that appear in the "substs"
 264     /// for the abstract type references (the `<'a>` in `Foo1<'a>`).
 265     ///
 266     /// Note that we do not impose the constraints based on the
 267     /// generic regions from the `Foo1` definition (e.g., `'x`). This
 268     /// is because the constraints we are imposing here is basically
 269     /// the concern of the one generating the constraining type C1,
 270     /// which is the current function. It also means that we can
 271     /// take "implied bounds" into account in some cases:
 272     ///
 273     /// ```text
 274     /// trait SomeTrait<'a, 'b> { }
 275     /// fn foo<'a, 'b>(_: &'a &'b u32) -> impl SomeTrait<'a, 'b> { .. }
 276     /// ```
 277     ///
 278     /// Here, the fact that `'b: 'a` is known only because of the
 279     /// implied bounds from the `&'a &'b u32` parameter, and is not
 280     /// "inherent" to the abstract type definition.
 281     ///
 282     /// # Parameters
 283     ///
 284     /// - `opaque_types` -- the map produced by `instantiate_opaque_types`
 285     /// - `free_region_relations` -- something that can be used to relate
 286     ///   the free regions (`'a`) that appear in the impl trait.
 287     pub fn constrain_opaque_types<FRR: FreeRegionRelations<'tcx>>(
 288         &self,
 289         opaque_types: &OpaqueTypeMap<'tcx>,
 290         free_region_relations: &FRR,
 291     ) {
 292         debug!("constrain_opaque_types()");
 293
 294         for (&def_id, opaque_defn) in opaque_types {
 295             self.constrain_opaque_type(def_id, opaque_defn, free_region_relations);
 296         }
 297     }
 298
 299     /// See `constrain_opaque_types` for docs
 300     pub fn constrain_opaque_type<FRR: FreeRegionRelations<'tcx>>(
 301         &self,
 302         def_id: DefId,
 303         opaque_defn: &OpaqueTypeDecl<'tcx>,
 304         free_region_relations: &FRR,
 305     ) {
 306         debug!("constrain_opaque_type()");
 307         debug!("constrain_opaque_type: def_id={:?}", def_id);
 308         debug!("constrain_opaque_type: opaque_defn={:#?}", opaque_defn);
 309
 310         let tcx = self.tcx;
 311
 312         let concrete_ty = self.resolve_vars_if_possible(&opaque_defn.concrete_ty);
 313
 314         debug!("constrain_opaque_type: concrete_ty={:?}", concrete_ty);
 315
 316         let abstract_type_generics = tcx.generics_of(def_id);
 317
 318         let span = tcx.def_span(def_id);
 319
 320         // If there are required region bounds, we can use them.
 321         if opaque_defn.has_required_region_bounds {
 322             let predicates_of = tcx.predicates_of(def_id);
 323             debug!("constrain_opaque_type: predicates: {:#?}", predicates_of,);
 324             let bounds = predicates_of.instantiate(tcx, opaque_defn.substs);
 325             debug!("constrain_opaque_type: bounds={:#?}", bounds);
 326             let opaque_type = tcx.mk_opaque(def_id, opaque_defn.substs);
 327
 328             let required_region_bounds = tcx.required_region_bounds(opaque_type, bounds.predicates);
 329             debug_assert!(!required_region_bounds.is_empty());
 330
 331             for required_region in required_region_bounds {
 332                 concrete_ty.visit_with(&mut ConstrainOpaqueTypeRegionVisitor {
 333                     tcx: self.tcx,
 334                     op: |r| self.sub_regions(infer::CallReturn(span), required_region, r),
 335                 });
 336             }
 337             return;
 338         }
 339
 340         // There were no `required_region_bounds`,
 341         // so we have to search for a `least_region`.
 342         // Go through all the regions used as arguments to the
 343         // abstract type. These are the parameters to the abstract
 344         // type; so in our example above, `substs` would contain
 345         // `['a]` for the first impl trait and `'b` for the
 346         // second.
 347         let mut least_region = None;
 348         for param in &abstract_type_generics.params {
 349             match param.kind {
 350                 GenericParamDefKind::Lifetime => {}
 351                 _ => continue,
 352             }
 353
 354             // Get the value supplied for this region from the substs.
 355             let subst_arg = opaque_defn.substs.region_at(param.index as usize);
 356
 357             // Compute the least upper bound of it with the other regions.
 358             debug!("constrain_opaque_types: least_region={:?}", least_region);
 359             debug!("constrain_opaque_types: subst_arg={:?}", subst_arg);
 360             match least_region {
 361                 None => least_region = Some(subst_arg),
 362                 Some(lr) => {
 363                     if free_region_relations.sub_free_regions(lr, subst_arg) {
 364                         // keep the current least region
 365                     } else if free_region_relations.sub_free_regions(subst_arg, lr) {
 366                         // switch to `subst_arg`
 367                         least_region = Some(subst_arg);
 368                     } else {
 369                         // There are two regions (`lr` and
 370                         // `subst_arg`) which are not relatable. We
 371                         // can't find a best choice. Therefore,
 372                         // instead of creating a single bound like
 373                         // `'r: 'a` (which is our preferred choice),
 374                         // we will create a "in bound" like `'r in
 375                         // ['a, 'b, 'c]`, where `'a..'c` are the
 376                         // regions that appear in the impl trait.
 377                         return self.generate_pick_constraint(
 378                             concrete_ty,
 379                             abstract_type_generics,
 380                             opaque_defn,
 381                             def_id,
 382                         );
 383                     }
 384                 }
 385             }
 386         }
 387
 388         let least_region = least_region.unwrap_or(tcx.lifetimes.re_static);
 389         debug!("constrain_opaque_types: least_region={:?}", least_region);
 390
 391         concrete_ty.visit_with(&mut ConstrainOpaqueTypeRegionVisitor {
 392             tcx: self.tcx,
 393             op: |r| self.sub_regions(infer::CallReturn(span), least_region, r),
 394         });
 395     }
 396
 397     /// As a fallback, we sometimes generate an "in constraint". For
 398     /// case like `impl Foo<'a, 'b>`, where `'a` and `'b` cannot be
 399     /// related, we would generate a constraint `'r in ['a, 'b,
 400     /// 'static]` for each region `'r` that appears in the hidden type
 401     /// (i.e., it must be equal to `'a`, `'b`, or `'static`).
 402     fn generate_pick_constraint(
 403         &self,
 404         concrete_ty: Ty<'tcx>,
 405         abstract_type_generics: &ty::Generics,
 406         opaque_defn: &OpaqueTypeDecl<'tcx>,
 407         opaque_type_def_id: DefId,
 408     ) {
 409         // Create the set of option regions: each region in the hidden
 410         // type can be equal to any of the region parameters of the
 411         // opaque type definition.
 412         let option_regions: Rc<Vec<ty::Region<'tcx>>> = Rc::new(
 413             abstract_type_generics
 414                 .params
 415                 .iter()
 416                 .filter(|param| match param.kind {
 417                     GenericParamDefKind::Lifetime => true,
 418                     GenericParamDefKind::Type { .. } | GenericParamDefKind::Const => false,
 419                 })
 420                 .map(|param| opaque_defn.substs.region_at(param.index as usize))
 421                 .chain(std::iter::once(self.tcx.lifetimes.re_static))
 422                 .collect(),
 423         );
 424
 425         concrete_ty.visit_with(&mut ConstrainOpaqueTypeRegionVisitor {
 426             tcx: self.tcx,
 427             op: |r| self.pick_constraint(
 428                 opaque_type_def_id,
 429                 concrete_ty,
 430                 r,
 431                 &option_regions,
 432             ),
 433         });
 434     }
 435
 436     /// Given the fully resolved, instantiated type for an opaque
 437     /// type, i.e., the value of an inference variable like C1 or C2
 438     /// (*), computes the "definition type" for an abstract type
 439     /// definition -- that is, the inferred value of `Foo1<'x>` or
 440     /// `Foo2<'x>` that we would conceptually use in its definition:
 441     ///
 442     ///     abstract type Foo1<'x>: Bar<'x> = AAA; <-- this type AAA
 443     ///     abstract type Foo2<'x>: Bar<'x> = BBB; <-- or this type BBB
 444     ///     fn foo<'a, 'b>(..) -> (Foo1<'a>, Foo2<'b>) { .. }
 445     ///
 446     /// Note that these values are defined in terms of a distinct set of
 447     /// generic parameters (`'x` instead of `'a`) from C1 or C2. The main
 448     /// purpose of this function is to do that translation.
 449     ///
 450     /// (*) C1 and C2 were introduced in the comments on
 451     /// `constrain_opaque_types`. Read that comment for more context.
 452     ///
 453     /// # Parameters
 454     ///
 455     /// - `def_id`, the `impl Trait` type
 456     /// - `opaque_defn`, the opaque definition created in `instantiate_opaque_types`
 457     /// - `instantiated_ty`, the inferred type C1 -- fully resolved, lifted version of
 458     ///   `opaque_defn.concrete_ty`
 459     pub fn infer_opaque_definition_from_instantiation(
 460         &self,
 461         def_id: DefId,
 462         opaque_defn: &OpaqueTypeDecl<'tcx>,
 463         instantiated_ty: Ty<'tcx>,
 464     ) -> Ty<'tcx> {
 465         debug!(
 466             "infer_opaque_definition_from_instantiation(def_id={:?}, instantiated_ty={:?})",
 467             def_id, instantiated_ty
 468         );
 469
 470         let gcx = self.tcx.global_tcx();
 471
 472         // Use substs to build up a reverse map from regions to their
 473         // identity mappings. This is necessary because of `impl
 474         // Trait` lifetimes are computed by replacing existing
 475         // lifetimes with 'static and remapping only those used in the
 476         // `impl Trait` return type, resulting in the parameters
 477         // shifting.
 478         let id_substs = InternalSubsts::identity_for_item(gcx, def_id);
 479         let map: FxHashMap<Kind<'tcx>, Kind<'tcx>> = opaque_defn
 480             .substs
 481             .iter()
 482             .enumerate()
 483             .map(|(index, subst)| (*subst, id_substs[index]))
 484             .collect();
 485
 486         // Convert the type from the function into a type valid outside
 487         // the function, by replacing invalid regions with 'static,
 488         // after producing an error for each of them.
 489         let definition_ty = instantiated_ty.fold_with(&mut ReverseMapper::new(
 490             self.tcx,
 491             self.is_tainted_by_errors(),
 492             def_id,
 493             map,
 494             instantiated_ty,
 495         ));
 496         debug!("infer_opaque_definition_from_instantiation: definition_ty={:?}", definition_ty);
 497
 498         definition_ty
 499     }
 500 }
 501
 502 pub fn report_unexpected_hidden_region(
 503     tcx: TyCtxt<'_, '_, 'tcx>,
 504     region_scope_tree: Option<&region::ScopeTree>,
 505     opaque_type_def_id: DefId,
 506     hidden_ty: Ty<'tcx>,
 507     hidden_region: ty::Region<'tcx>,
 508 ) {
 509     let span = tcx.def_span(opaque_type_def_id);
 510     let mut err = struct_span_err!(
 511         tcx.sess,
 512         span,
 513         E0700,
 514         "hidden type for `impl Trait` captures lifetime that does not appear in bounds",
 515     );
 516
 517     // Explain the region we are capturing.
 518     if let ty::ReEarlyBound(_) | ty::ReFree(_) | ty::ReStatic | ty::ReEmpty = hidden_region {
 519         // Assuming regionck succeeded (*), we ought to always be
 520         // capturing *some* region from the fn header, and hence it
 521         // ought to be free. So under normal circumstances, we will go
 522         // down this path which gives a decent human readable
 523         // explanation.
 524         //
 525         // (*) if not, the `tainted_by_errors` flag would be set to
 526         // true in any case, so we wouldn't be here at all.
 527         tcx.note_and_explain_free_region(
 528             &mut err,
 529             &format!("hidden type `{}` captures ", hidden_ty),
 530             hidden_region,
 531             "",
 532         );
 533     } else {
 534         // Ugh. This is a painful case: the hidden region is not one
 535         // that we can easily summarize or explain. This can happens
 536         // in a case like
 537         // `src/test/ui/multiple-lifetimes/ordinary-bounds-unsuited.rs`:
 538         //
 539         // ```
 540         // fn upper_bounds<'a, 'b>(a: Ordinary<'a>, b: Ordinary<'b>) -> impl Trait<'a, 'b> {
 541         //   if condition() { a } else { b }
 542         // }
 543         // ```
 544         //
 545         // Here the captured lifetime is the intersection of `'a` and
 546         // `'b`, which we can't quite express. This prticulararticular
 547         // is kind of an unfortunate error anyway.
 548
 549         if let Some(region_scope_tree) = region_scope_tree {
 550             // If the `region_scope_tree` is available, this is being
 551             // invoked from the "region inferencer error". We can at
 552             // least report a really cryptic error for now.
 553             tcx.note_and_explain_region(
 554                 region_scope_tree,
 555                 &mut err,
 556                 &format!("hidden type `{}` captures ", hidden_ty),
 557                 hidden_region,
 558                 "",
 559             );
 560         } else {
 561             // If the `region_scope_tree` is *unavailable*, this is
 562             // being invoked by the code that comes *after* region
 563             // inferencing. This is a bug, as the region inferencer
 564             // ought to have noticed the failed constraint and invoked
 565             // error reporting, which in turn should have prevented us
 566             // from getting trying to infer the hidden type
 567             // completely.
 568             span_bug!(
 569                 span,
 570                 "hidden type captures unexpected lifetime `{:?}` but no region inference failure",
 571                 hidden_region,
 572             );
 573         }
 574     }
 575
 576     err.emit();
 577 }
 578
 579 // Visitor that requires that (almost) all regions in the type visited outlive
 580 // `least_region`. We cannot use `push_outlives_components` because regions in
 581 // closure signatures are not included in their outlives components. We need to
 582 // ensure all regions outlive the given bound so that we don't end up with,
 583 // say, `ReScope` appearing in a return type and causing ICEs when other
 584 // functions end up with region constraints involving regions from other
 585 // functions.
 586 //
 587 // We also cannot use `for_each_free_region` because for closures it includes
 588 // the regions parameters from the enclosing item.
 589 //
 590 // We ignore any type parameters because impl trait values are assumed to
 591 // capture all the in-scope type parameters.
 592 struct ConstrainOpaqueTypeRegionVisitor<'tcx, OP>
 593 where
 594     OP: FnMut(ty::Region<'tcx>),
 595 {
 596     tcx: TyCtxt<'tcx>,
 597     op: OP,
 598 }
 599
 600 impl<'tcx, OP> TypeVisitor<'tcx> for ConstrainOpaqueTypeRegionVisitor<'tcx, OP>
 601 where
 602     OP: FnMut(ty::Region<'tcx>),
 603 {
 604     fn visit_binder<T: TypeFoldable<'tcx>>(&mut self, t: &ty::Binder<T>) -> bool {
 605         t.skip_binder().visit_with(self);
 606         false // keep visiting
 607     }
 608
 609     fn visit_region(&mut self, r: ty::Region<'tcx>) -> bool {
 610         match *r {
 611             // ignore bound regions, keep visiting
 612             ty::ReLateBound(_, _) => false,
 613             _ => {
 614                 (self.op)(r);
 615                 false
 616             }
 617         }
 618     }
 619
 620     fn visit_ty(&mut self, ty: Ty<'tcx>) -> bool {
 621         // We're only interested in types involving regions
 622         if !ty.flags.intersects(ty::TypeFlags::HAS_FREE_REGIONS) {
 623             return false; // keep visiting
 624         }
 625
 626         match ty.sty {
 627             ty::Closure(def_id, ref substs) => {
 628                 // Skip lifetime parameters of the enclosing item(s)
 629
 630                 for upvar_ty in substs.upvar_tys(def_id, self.tcx) {
 631                     upvar_ty.visit_with(self);
 632                 }
 633
 634                 substs.closure_sig_ty(def_id, self.tcx).visit_with(self);
 635             }
 636
 637             ty::Generator(def_id, ref substs, _) => {
 638                 // Skip lifetime parameters of the enclosing item(s)
 639                 // Also skip the witness type, because that has no free regions.
 640
 641                 for upvar_ty in substs.upvar_tys(def_id, self.tcx) {
 642                     upvar_ty.visit_with(self);
 643                 }
 644
 645                 substs.return_ty(def_id, self.tcx).visit_with(self);
 646                 substs.yield_ty(def_id, self.tcx).visit_with(self);
 647             }
 648             _ => {
 649                 ty.super_visit_with(self);
 650             }
 651         }
 652
 653         false
 654     }
 655 }
 656
 657 struct ReverseMapper<'tcx> {
 658     tcx: TyCtxt<'tcx>,
 659
 660     /// If errors have already been reported in this fn, we suppress
 661     /// our own errors because they are sometimes derivative.
 662     tainted_by_errors: bool,
 663
 664     opaque_type_def_id: DefId,
 665     map: FxHashMap<Kind<'tcx>, Kind<'tcx>>,
 666     map_missing_regions_to_empty: bool,
 667
 668     /// initially `Some`, set to `None` once error has been reported
 669     hidden_ty: Option<Ty<'tcx>>,
 670 }
 671
 672 impl ReverseMapper<'tcx> {
 673     fn new(
 674         tcx: TyCtxt<'tcx>,
 675         tainted_by_errors: bool,
 676         opaque_type_def_id: DefId,
 677         map: FxHashMap<Kind<'tcx>, Kind<'tcx>>,
 678         hidden_ty: Ty<'tcx>,
 679     ) -> Self {
 680         Self {
 681             tcx,
 682             tainted_by_errors,
 683             opaque_type_def_id,
 684             map,
 685             map_missing_regions_to_empty: false,
 686             hidden_ty: Some(hidden_ty),
 687         }
 688     }
 689
 690     fn fold_kind_mapping_missing_regions_to_empty(&mut self, kind: Kind<'tcx>) -> Kind<'tcx> {
 691         assert!(!self.map_missing_regions_to_empty);
 692         self.map_missing_regions_to_empty = true;
 693         let kind = kind.fold_with(self);
 694         self.map_missing_regions_to_empty = false;
 695         kind
 696     }
 697
 698     fn fold_kind_normally(&mut self, kind: Kind<'tcx>) -> Kind<'tcx> {
 699         assert!(!self.map_missing_regions_to_empty);
 700         kind.fold_with(self)
 701     }
 702 }
 703
 704 impl TypeFolder<'tcx> for ReverseMapper<'tcx> {
 705     fn tcx(&self) -> TyCtxt<'tcx> {
 706         self.tcx
 707     }
 708
 709     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 710         match r {
 711             // ignore bound regions that appear in the type (e.g., this
 712             // would ignore `'r` in a type like `for<'r> fn(&'r u32)`.
 713             ty::ReLateBound(..) |
 714
 715             // ignore `'static`, as that can appear anywhere
 716             ty::ReStatic => return r,
 717
 718             _ => { }
 719         }
 720
 721         match self.map.get(&r.into()).map(|k| k.unpack()) {
 722             Some(UnpackedKind::Lifetime(r1)) => r1,
 723             Some(u) => panic!("region mapped to unexpected kind: {:?}", u),
 724             None => {
 725                 if !self.map_missing_regions_to_empty && !self.tainted_by_errors {
 726                     if let Some(hidden_ty) = self.hidden_ty.take() {
 727                         report_unexpected_hidden_region(
 728                             self.tcx,
 729                             None,
 730                             self.opaque_type_def_id,
 731                             hidden_ty,
 732                             r,
 733                         );
 734                     }
 735                 }
 736                 self.tcx.lifetimes.re_empty
 737             }
 738         }
 739     }
 740
 741     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
 742         match ty.sty {
 743             ty::Closure(def_id, substs) => {
 744                 // I am a horrible monster and I pray for death. When
 745                 // we encounter a closure here, it is always a closure
 746                 // from within the function that we are currently
 747                 // type-checking -- one that is now being encapsulated
 748                 // in an existential abstract type. Ideally, we would
 749                 // go through the types/lifetimes that it references
 750                 // and treat them just like we would any other type,
 751                 // which means we would error out if we find any
 752                 // reference to a type/region that is not in the
 753                 // "reverse map".
 754                 //
 755                 // **However,** in the case of closures, there is a
 756                 // somewhat subtle (read: hacky) consideration. The
 757                 // problem is that our closure types currently include
 758                 // all the lifetime parameters declared on the
 759                 // enclosing function, even if they are unused by the
 760                 // closure itself. We can't readily filter them out,
 761                 // so here we replace those values with `'empty`. This
 762                 // can't really make a difference to the rest of the
 763                 // compiler; those regions are ignored for the
 764                 // outlives relation, and hence don't affect trait
 765                 // selection or auto traits, and they are erased
 766                 // during codegen.
 767
 768                 let generics = self.tcx.generics_of(def_id);
 769                 let substs =
 770                     self.tcx.mk_substs(substs.substs.iter().enumerate().map(|(index, &kind)| {
 771                         if index < generics.parent_count {
 772                             // Accommodate missing regions in the parent kinds...
 773                             self.fold_kind_mapping_missing_regions_to_empty(kind)
 774                         } else {
 775                             // ...but not elsewhere.
 776                             self.fold_kind_normally(kind)
 777                         }
 778                     }));
 779
 780                 self.tcx.mk_closure(def_id, ty::ClosureSubsts { substs })
 781             }
 782
 783             ty::Generator(def_id, substs, movability) => {
 784                 let generics = self.tcx.generics_of(def_id);
 785                 let substs =
 786                     self.tcx.mk_substs(substs.substs.iter().enumerate().map(|(index, &kind)| {
 787                         if index < generics.parent_count {
 788                             // Accommodate missing regions in the parent kinds...
 789                             self.fold_kind_mapping_missing_regions_to_empty(kind)
 790                         } else {
 791                             // ...but not elsewhere.
 792                             self.fold_kind_normally(kind)
 793                         }
 794                     }));
 795
 796                 self.tcx.mk_generator(def_id, ty::GeneratorSubsts { substs }, movability)
 797             }
 798
 799             _ => ty.super_fold_with(self),
 800         }
 801     }
 802 }
 803
 804 struct Instantiator<'a, 'tcx> {
 805     infcx: &'a InferCtxt<'a, 'tcx>,
 806     parent_def_id: DefId,
 807     body_id: hir::HirId,
 808     param_env: ty::ParamEnv<'tcx>,
 809     opaque_types: OpaqueTypeMap<'tcx>,
 810     obligations: Vec<PredicateObligation<'tcx>>,
 811 }
 812
 813 impl<'a, 'tcx> Instantiator<'a, 'tcx> {
 814     fn instantiate_opaque_types_in_map<T: TypeFoldable<'tcx>>(&mut self, value: &T) -> T {
 815         debug!("instantiate_opaque_types_in_map(value={:?})", value);
 816         let tcx = self.infcx.tcx;
 817         value.fold_with(&mut BottomUpFolder {
 818             tcx,
 819             ty_op: |ty| {
 820                 if let ty::Opaque(def_id, substs) = ty.sty {
 821                     // Check that this is `impl Trait` type is
 822                     // declared by `parent_def_id` -- i.e., one whose
 823                     // value we are inferring.  At present, this is
 824                     // always true during the first phase of
 825                     // type-check, but not always true later on during
 826                     // NLL. Once we support named abstract types more fully,
 827                     // this same scenario will be able to arise during all phases.
 828                     //
 829                     // Here is an example using `abstract type` that indicates
 830                     // the distinction we are checking for:
 831                     //
 832                     // ```rust
 833                     // mod a {
 834                     //   pub abstract type Foo: Iterator;
 835                     //   pub fn make_foo() -> Foo { .. }
 836                     // }
 837                     //
 838                     // mod b {
 839                     //   fn foo() -> a::Foo { a::make_foo() }
 840                     // }
 841                     // ```
 842                     //
 843                     // Here, the return type of `foo` references a
 844                     // `Opaque` indeed, but not one whose value is
 845                     // presently being inferred. You can get into a
 846                     // similar situation with closure return types
 847                     // today:
 848                     //
 849                     // ```rust
 850                     // fn foo() -> impl Iterator { .. }
 851                     // fn bar() {
 852                     //     let x = || foo(); // returns the Opaque assoc with `foo`
 853                     // }
 854                     // ```
 855                     if let Some(opaque_hir_id) = tcx.hir().as_local_hir_id(def_id) {
 856                         let parent_def_id = self.parent_def_id;
 857                         let def_scope_default = || {
 858                             let opaque_parent_hir_id = tcx.hir().get_parent_item(opaque_hir_id);
 859                             parent_def_id
 860                                 == tcx.hir().local_def_id_from_hir_id(opaque_parent_hir_id)
 861                         };
 862                         let (in_definition_scope, origin) = match tcx.hir().find(opaque_hir_id) {
 863                             Some(Node::Item(item)) => match item.node {
 864                                 // Anonymous `impl Trait`
 865                                 hir::ItemKind::Existential(hir::ExistTy {
 866                                     impl_trait_fn: Some(parent),
 867                                     origin,
 868                                     ..
 869                                 }) => (parent == self.parent_def_id, origin),
 870                                 // Named `existential type`
 871                                 hir::ItemKind::Existential(hir::ExistTy {
 872                                     impl_trait_fn: None,
 873                                     origin,
 874                                     ..
 875                                 }) => (
 876                                     may_define_existential_type(
 877                                         tcx,
 878                                         self.parent_def_id,
 879                                         opaque_hir_id,
 880                                     ),
 881                                     origin,
 882                                 ),
 883                                 _ => (def_scope_default(), hir::ExistTyOrigin::ExistentialType),
 884                             },
 885                             Some(Node::ImplItem(item)) => match item.node {
 886                                 hir::ImplItemKind::Existential(_) => (
 887                                     may_define_existential_type(
 888                                         tcx,
 889                                         self.parent_def_id,
 890                                         opaque_hir_id,
 891                                     ),
 892                                     hir::ExistTyOrigin::ExistentialType,
 893                                 ),
 894                                 _ => (def_scope_default(), hir::ExistTyOrigin::ExistentialType),
 895                             },
 896                             _ => bug!(
 897                                 "expected (impl) item, found {}",
 898                                 tcx.hir().node_to_string(opaque_hir_id),
 899                             ),
 900                         };
 901                         if in_definition_scope {
 902                             return self.fold_opaque_ty(ty, def_id, substs, origin);
 903                         }
 904
 905                         debug!(
 906                             "instantiate_opaque_types_in_map: \
 907                              encountered opaque outside its definition scope \
 908                              def_id={:?}",
 909                             def_id,
 910                         );
 911                     }
 912                 }
 913
 914                 ty
 915             },
 916             lt_op: |lt| lt,
 917             ct_op: |ct| ct,
 918         })
 919     }
 920
 921     fn fold_opaque_ty(
 922         &mut self,
 923         ty: Ty<'tcx>,
 924         def_id: DefId,
 925         substs: SubstsRef<'tcx>,
 926         origin: hir::ExistTyOrigin,
 927     ) -> Ty<'tcx> {
 928         let infcx = self.infcx;
 929         let tcx = infcx.tcx;
 930
 931         debug!("instantiate_opaque_types: Opaque(def_id={:?}, substs={:?})", def_id, substs);
 932
 933         // Use the same type variable if the exact same opaque type appears more
 934         // than once in the return type (e.g., if it's passed to a type alias).
 935         if let Some(opaque_defn) = self.opaque_types.get(&def_id) {
 936             return opaque_defn.concrete_ty;
 937         }
 938         let span = tcx.def_span(def_id);
 939         let ty_var = infcx
 940             .next_ty_var(TypeVariableOrigin { kind: TypeVariableOriginKind::TypeInference, span });
 941
 942         let predicates_of = tcx.predicates_of(def_id);
 943         debug!("instantiate_opaque_types: predicates={:#?}", predicates_of,);
 944         let bounds = predicates_of.instantiate(tcx, substs);
 945         debug!("instantiate_opaque_types: bounds={:?}", bounds);
 946
 947         let required_region_bounds = tcx.required_region_bounds(ty, bounds.predicates.clone());
 948         debug!("instantiate_opaque_types: required_region_bounds={:?}", required_region_bounds);
 949
 950         // Make sure that we are in fact defining the *entire* type
 951         // (e.g., `existential type Foo<T: Bound>: Bar;` needs to be
 952         // defined by a function like `fn foo<T: Bound>() -> Foo<T>`).
 953         debug!("instantiate_opaque_types: param_env={:#?}", self.param_env,);
 954         debug!("instantiate_opaque_types: generics={:#?}", tcx.generics_of(def_id),);
 955
 956         self.opaque_types.insert(
 957             def_id,
 958             OpaqueTypeDecl {
 959                 substs,
 960                 concrete_ty: ty_var,
 961                 has_required_region_bounds: !required_region_bounds.is_empty(),
 962                 origin,
 963             },
 964         );
 965         debug!("instantiate_opaque_types: ty_var={:?}", ty_var);
 966
 967         self.obligations.reserve(bounds.predicates.len());
 968         for predicate in bounds.predicates {
 969             // Change the predicate to refer to the type variable,
 970             // which will be the concrete type instead of the opaque type.
 971             // This also instantiates nested instances of `impl Trait`.
 972             let predicate = self.instantiate_opaque_types_in_map(&predicate);
 973
 974             let cause = traits::ObligationCause::new(span, self.body_id, traits::SizedReturnType);
 975
 976             // Require that the predicate holds for the concrete type.
 977             debug!("instantiate_opaque_types: predicate={:?}", predicate);
 978             self.obligations.push(traits::Obligation::new(cause, self.param_env, predicate));
 979         }
 980
 981         ty_var
 982     }
 983 }
 984
 985 /// Returns `true` if `opaque_hir_id` is a sibling or a child of a sibling of `def_id`.
 986 ///
 987 /// Example:
 988 /// ```rust
 989 /// pub mod foo {
 990 ///     pub mod bar {
 991 ///         pub existential type Baz;
 992 ///
 993 ///         fn f1() -> Baz { .. }
 994 ///     }
 995 ///
 996 ///     fn f2() -> bar::Baz { .. }
 997 /// }
 998 /// ```
 999 ///
1000 /// Here, `def_id` is the `DefId` of the defining use of the existential type (e.g., `f1` or `f2`),
1001 /// and `opaque_hir_id` is the `HirId` of the definition of the existential type `Baz`.
1002 /// For the above example, this function returns `true` for `f1` and `false` for `f2`.
1003 pub fn may_define_existential_type(
1004     tcx: TyCtxt<'_>,
1005     def_id: DefId,
1006     opaque_hir_id: hir::HirId,
1007 ) -> bool {
1008     let mut hir_id = tcx.hir().as_local_hir_id(def_id).unwrap();
1009     trace!(
1010         "may_define_existential_type(def={:?}, opaque_node={:?})",
1011         tcx.hir().get(hir_id),
1012         tcx.hir().get(opaque_hir_id)
1013     );
1014
1015     // Named existential types can be defined by any siblings or children of siblings.
1016     let scope = tcx.hir().get_defining_scope(opaque_hir_id).expect("could not get defining scope");
1017     // We walk up the node tree until we hit the root or the scope of the opaque type.
1018     while hir_id != scope && hir_id != hir::CRATE_HIR_ID {
1019         hir_id = tcx.hir().get_parent_item(hir_id);
1020     }
1021     // Syntactically, we are allowed to define the concrete type if:
1022     hir_id == scope
1023 }