compiler/rustc_infer/src/infer/opaque_types.rs

   1 use crate::infer::InferCtxt;
   2 use rustc_data_structures::sync::Lrc;
   3 use rustc_data_structures::vec_map::VecMap;
   4 use rustc_hir as hir;
   5 use rustc_middle::ty::subst::GenericArgKind;
   6 use rustc_middle::ty::{self, OpaqueTypeKey, Ty, TyCtxt, TypeFoldable, TypeVisitor};
   7 use rustc_span::Span;
   8
   9 use std::ops::ControlFlow;
  10
  11 pub type OpaqueTypeMap<'tcx> = VecMap<OpaqueTypeKey<'tcx>, OpaqueTypeDecl<'tcx>>;
  12
  13 /// Information about the opaque types whose values we
  14 /// are inferring in this function (these are the `impl Trait` that
  15 /// appear in the return type).
  16 #[derive(Copy, Clone, Debug)]
  17 pub struct OpaqueTypeDecl<'tcx> {
  18     /// The opaque type (`ty::Opaque`) for this declaration.
  19     pub opaque_type: Ty<'tcx>,
  20
  21     /// The span of this particular definition of the opaque type. So
  22     /// for example:
  23     ///
  24     /// ```ignore (incomplete snippet)
  25     /// type Foo = impl Baz;
  26     /// fn bar() -> Foo {
  27     /// //          ^^^ This is the span we are looking for!
  28     /// }
  29     /// ```
  30     ///
  31     /// In cases where the fn returns `(impl Trait, impl Trait)` or
  32     /// other such combinations, the result is currently
  33     /// over-approximated, but better than nothing.
  34     pub definition_span: Span,
  35
  36     /// The type variable that represents the value of the opaque type
  37     /// that we require. In other words, after we compile this function,
  38     /// we will be created a constraint like:
  39     ///
  40     ///     Foo<'a, T> = ?C
  41     ///
  42     /// where `?C` is the value of this type variable. =) It may
  43     /// naturally refer to the type and lifetime parameters in scope
  44     /// in this function, though ultimately it should only reference
  45     /// those that are arguments to `Foo` in the constraint above. (In
  46     /// other words, `?C` should not include `'b`, even though it's a
  47     /// lifetime parameter on `foo`.)
  48     pub concrete_ty: Ty<'tcx>,
  49
  50     /// The origin of the opaque type.
  51     pub origin: hir::OpaqueTyOrigin,
  52 }
  53
  54 impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
  55     /// Given the map `opaque_types` containing the opaque
  56     /// `impl Trait` types whose underlying, hidden types are being
  57     /// inferred, this method adds constraints to the regions
  58     /// appearing in those underlying hidden types to ensure that they
  59     /// at least do not refer to random scopes within the current
  60     /// function. These constraints are not (quite) sufficient to
  61     /// guarantee that the regions are actually legal values; that
  62     /// final condition is imposed after region inference is done.
  63     ///
  64     /// # The Problem
  65     ///
  66     /// Let's work through an example to explain how it works. Assume
  67     /// the current function is as follows:
  68     ///
  69     /// ```text
  70     /// fn foo<'a, 'b>(..) -> (impl Bar<'a>, impl Bar<'b>)
  71     /// ```
  72     ///
  73     /// Here, we have two `impl Trait` types whose values are being
  74     /// inferred (the `impl Bar<'a>` and the `impl
  75     /// Bar<'b>`). Conceptually, this is sugar for a setup where we
  76     /// define underlying opaque types (`Foo1`, `Foo2`) and then, in
  77     /// the return type of `foo`, we *reference* those definitions:
  78     ///
  79     /// ```text
  80     /// type Foo1<'x> = impl Bar<'x>;
  81     /// type Foo2<'x> = impl Bar<'x>;
  82     /// fn foo<'a, 'b>(..) -> (Foo1<'a>, Foo2<'b>) { .. }
  83     ///                    //  ^^^^ ^^
  84     ///                    //  |    |
  85     ///                    //  |    substs
  86     ///                    //  def_id
  87     /// ```
  88     ///
  89     /// As indicating in the comments above, each of those references
  90     /// is (in the compiler) basically a substitution (`substs`)
  91     /// applied to the type of a suitable `def_id` (which identifies
  92     /// `Foo1` or `Foo2`).
  93     ///
  94     /// Now, at this point in compilation, what we have done is to
  95     /// replace each of the references (`Foo1<'a>`, `Foo2<'b>`) with
  96     /// fresh inference variables C1 and C2. We wish to use the values
  97     /// of these variables to infer the underlying types of `Foo1` and
  98     /// `Foo2`. That is, this gives rise to higher-order (pattern) unification
  99     /// constraints like:
 100     ///
 101     /// ```text
 102     /// for<'a> (Foo1<'a> = C1)
 103     /// for<'b> (Foo1<'b> = C2)
 104     /// ```
 105     ///
 106     /// For these equation to be satisfiable, the types `C1` and `C2`
 107     /// can only refer to a limited set of regions. For example, `C1`
 108     /// can only refer to `'static` and `'a`, and `C2` can only refer
 109     /// to `'static` and `'b`. The job of this function is to impose that
 110     /// constraint.
 111     ///
 112     /// Up to this point, C1 and C2 are basically just random type
 113     /// inference variables, and hence they may contain arbitrary
 114     /// regions. In fact, it is fairly likely that they do! Consider
 115     /// this possible definition of `foo`:
 116     ///
 117     /// ```text
 118     /// fn foo<'a, 'b>(x: &'a i32, y: &'b i32) -> (impl Bar<'a>, impl Bar<'b>) {
 119     ///         (&*x, &*y)
 120     ///     }
 121     /// ```
 122     ///
 123     /// Here, the values for the concrete types of the two impl
 124     /// traits will include inference variables:
 125     ///
 126     /// ```text
 127     /// &'0 i32
 128     /// &'1 i32
 129     /// ```
 130     ///
 131     /// Ordinarily, the subtyping rules would ensure that these are
 132     /// sufficiently large. But since `impl Bar<'a>` isn't a specific
 133     /// type per se, we don't get such constraints by default. This
 134     /// is where this function comes into play. It adds extra
 135     /// constraints to ensure that all the regions which appear in the
 136     /// inferred type are regions that could validly appear.
 137     ///
 138     /// This is actually a bit of a tricky constraint in general. We
 139     /// want to say that each variable (e.g., `'0`) can only take on
 140     /// values that were supplied as arguments to the opaque type
 141     /// (e.g., `'a` for `Foo1<'a>`) or `'static`, which is always in
 142     /// scope. We don't have a constraint quite of this kind in the current
 143     /// region checker.
 144     ///
 145     /// # The Solution
 146     ///
 147     /// We generally prefer to make `<=` constraints, since they
 148     /// integrate best into the region solver. To do that, we find the
 149     /// "minimum" of all the arguments that appear in the substs: that
 150     /// is, some region which is less than all the others. In the case
 151     /// of `Foo1<'a>`, that would be `'a` (it's the only choice, after
 152     /// all). Then we apply that as a least bound to the variables
 153     /// (e.g., `'a <= '0`).
 154     ///
 155     /// In some cases, there is no minimum. Consider this example:
 156     ///
 157     /// ```text
 158     /// fn baz<'a, 'b>() -> impl Trait<'a, 'b> { ... }
 159     /// ```
 160     ///
 161     /// Here we would report a more complex "in constraint", like `'r
 162     /// in ['a, 'b, 'static]` (where `'r` is some region appearing in
 163     /// the hidden type).
 164     ///
 165     /// # Constrain regions, not the hidden concrete type
 166     ///
 167     /// Note that generating constraints on each region `Rc` is *not*
 168     /// the same as generating an outlives constraint on `Tc` iself.
 169     /// For example, if we had a function like this:
 170     ///
 171     /// ```rust
 172     /// fn foo<'a, T>(x: &'a u32, y: T) -> impl Foo<'a> {
 173     ///   (x, y)
 174     /// }
 175     ///
 176     /// // Equivalent to:
 177     /// type FooReturn<'a, T> = impl Foo<'a>;
 178     /// fn foo<'a, T>(..) -> FooReturn<'a, T> { .. }
 179     /// ```
 180     ///
 181     /// then the hidden type `Tc` would be `(&'0 u32, T)` (where `'0`
 182     /// is an inference variable). If we generated a constraint that
 183     /// `Tc: 'a`, then this would incorrectly require that `T: 'a` --
 184     /// but this is not necessary, because the opaque type we
 185     /// create will be allowed to reference `T`. So we only generate a
 186     /// constraint that `'0: 'a`.
 187     ///
 188     /// # The `free_region_relations` parameter
 189     ///
 190     /// The `free_region_relations` argument is used to find the
 191     /// "minimum" of the regions supplied to a given opaque type.
 192     /// It must be a relation that can answer whether `'a <= 'b`,
 193     /// where `'a` and `'b` are regions that appear in the "substs"
 194     /// for the opaque type references (the `<'a>` in `Foo1<'a>`).
 195     ///
 196     /// Note that we do not impose the constraints based on the
 197     /// generic regions from the `Foo1` definition (e.g., `'x`). This
 198     /// is because the constraints we are imposing here is basically
 199     /// the concern of the one generating the constraining type C1,
 200     /// which is the current function. It also means that we can
 201     /// take "implied bounds" into account in some cases:
 202     ///
 203     /// ```text
 204     /// trait SomeTrait<'a, 'b> { }
 205     /// fn foo<'a, 'b>(_: &'a &'b u32) -> impl SomeTrait<'a, 'b> { .. }
 206     /// ```
 207     ///
 208     /// Here, the fact that `'b: 'a` is known only because of the
 209     /// implied bounds from the `&'a &'b u32` parameter, and is not
 210     /// "inherent" to the opaque type definition.
 211     ///
 212     /// # Parameters
 213     ///
 214     /// - `opaque_types` -- the map produced by `instantiate_opaque_types`
 215     /// - `free_region_relations` -- something that can be used to relate
 216     ///   the free regions (`'a`) that appear in the impl trait.
 217     #[instrument(level = "debug", skip(self))]
 218     pub fn constrain_opaque_type(
 219         &self,
 220         opaque_type_key: OpaqueTypeKey<'tcx>,
 221         opaque_defn: &OpaqueTypeDecl<'tcx>,
 222     ) {
 223         let def_id = opaque_type_key.def_id;
 224
 225         let tcx = self.tcx;
 226
 227         let concrete_ty = self.resolve_vars_if_possible(opaque_defn.concrete_ty);
 228
 229         debug!(?concrete_ty);
 230
 231         let first_own_region = match opaque_defn.origin {
 232             hir::OpaqueTyOrigin::FnReturn | hir::OpaqueTyOrigin::AsyncFn => {
 233                 // We lower
 234                 //
 235                 // fn foo<'l0..'ln>() -> impl Trait<'l0..'lm>
 236                 //
 237                 // into
 238                 //
 239                 // type foo::<'p0..'pn>::Foo<'q0..'qm>
 240                 // fn foo<l0..'ln>() -> foo::<'static..'static>::Foo<'l0..'lm>.
 241                 //
 242                 // For these types we only iterate over `'l0..lm` below.
 243                 tcx.generics_of(def_id).parent_count
 244             }
 245             // These opaque type inherit all lifetime parameters from their
 246             // parent, so we have to check them all.
 247             hir::OpaqueTyOrigin::TyAlias => 0,
 248         };
 249
 250         // For a case like `impl Foo<'a, 'b>`, we would generate a constraint
 251         // `'r in ['a, 'b, 'static]` for each region `'r` that appears in the
 252         // hidden type (i.e., it must be equal to `'a`, `'b`, or `'static`).
 253         //
 254         // `conflict1` and `conflict2` are the two region bounds that we
 255         // detected which were unrelated. They are used for diagnostics.
 256
 257         // Create the set of choice regions: each region in the hidden
 258         // type can be equal to any of the region parameters of the
 259         // opaque type definition.
 260         let choice_regions: Lrc<Vec<ty::Region<'tcx>>> = Lrc::new(
 261             opaque_type_key.substs[first_own_region..]
 262                 .iter()
 263                 .filter_map(|arg| match arg.unpack() {
 264                     GenericArgKind::Lifetime(r) => Some(r),
 265                     GenericArgKind::Type(_) | GenericArgKind::Const(_) => None,
 266                 })
 267                 .chain(std::iter::once(self.tcx.lifetimes.re_static))
 268                 .collect(),
 269         );
 270
 271         concrete_ty.visit_with(&mut ConstrainOpaqueTypeRegionVisitor {
 272             tcx: self.tcx,
 273             op: |r| {
 274                 self.member_constraint(
 275                     opaque_type_key.def_id,
 276                     opaque_defn.definition_span,
 277                     concrete_ty,
 278                     r,
 279                     &choice_regions,
 280                 )
 281             },
 282         });
 283     }
 284 }
 285
 286 // Visitor that requires that (almost) all regions in the type visited outlive
 287 // `least_region`. We cannot use `push_outlives_components` because regions in
 288 // closure signatures are not included in their outlives components. We need to
 289 // ensure all regions outlive the given bound so that we don't end up with,
 290 // say, `ReVar` appearing in a return type and causing ICEs when other
 291 // functions end up with region constraints involving regions from other
 292 // functions.
 293 //
 294 // We also cannot use `for_each_free_region` because for closures it includes
 295 // the regions parameters from the enclosing item.
 296 //
 297 // We ignore any type parameters because impl trait values are assumed to
 298 // capture all the in-scope type parameters.
 299 struct ConstrainOpaqueTypeRegionVisitor<'tcx, OP> {
 300     tcx: TyCtxt<'tcx>,
 301     op: OP,
 302 }
 303
 304 impl<'tcx, OP> TypeVisitor<'tcx> for ConstrainOpaqueTypeRegionVisitor<'tcx, OP>
 305 where
 306     OP: FnMut(ty::Region<'tcx>),
 307 {
 308     fn tcx_for_anon_const_substs(&self) -> Option<TyCtxt<'tcx>> {
 309         Some(self.tcx)
 310     }
 311
 312     fn visit_binder<T: TypeFoldable<'tcx>>(
 313         &mut self,
 314         t: &ty::Binder<'tcx, T>,
 315     ) -> ControlFlow<Self::BreakTy> {
 316         t.as_ref().skip_binder().visit_with(self);
 317         ControlFlow::CONTINUE
 318     }
 319
 320     fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
 321         match *r {
 322             // ignore bound regions, keep visiting
 323             ty::ReLateBound(_, _) => ControlFlow::CONTINUE,
 324             _ => {
 325                 (self.op)(r);
 326                 ControlFlow::CONTINUE
 327             }
 328         }
 329     }
 330
 331     fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 332         // We're only interested in types involving regions
 333         if !ty.flags().intersects(ty::TypeFlags::HAS_POTENTIAL_FREE_REGIONS) {
 334             return ControlFlow::CONTINUE;
 335         }
 336
 337         match ty.kind() {
 338             ty::Closure(_, ref substs) => {
 339                 // Skip lifetime parameters of the enclosing item(s)
 340
 341                 substs.as_closure().tupled_upvars_ty().visit_with(self);
 342                 substs.as_closure().sig_as_fn_ptr_ty().visit_with(self);
 343             }
 344
 345             ty::Generator(_, ref substs, _) => {
 346                 // Skip lifetime parameters of the enclosing item(s)
 347                 // Also skip the witness type, because that has no free regions.
 348
 349                 substs.as_generator().tupled_upvars_ty().visit_with(self);
 350                 substs.as_generator().return_ty().visit_with(self);
 351                 substs.as_generator().yield_ty().visit_with(self);
 352                 substs.as_generator().resume_ty().visit_with(self);
 353             }
 354             _ => {
 355                 ty.super_visit_with(self);
 356             }
 357         }
 358
 359         ControlFlow::CONTINUE
 360     }
 361 }