compiler/rustc_infer/src/infer/outlives/obligations.rs

   1 //! Code that handles "type-outlives" constraints like `T: 'a`. This
   2 //! is based on the `push_outlives_components` function defined in rustc_infer,
   3 //! but it adds a bit of heuristics on top, in particular to deal with
   4 //! associated types and projections.
   5 //!
   6 //! When we process a given `T: 'a` obligation, we may produce two
   7 //! kinds of constraints for the region inferencer:
   8 //!
   9 //! - Relationships between inference variables and other regions.
  10 //!   For example, if we have `&'?0 u32: 'a`, then we would produce
  11 //!   a constraint that `'a <= '?0`.
  12 //! - "Verifys" that must be checked after inferencing is done.
  13 //!   For example, if we know that, for some type parameter `T`,
  14 //!   `T: 'a + 'b`, and we have a requirement that `T: '?1`,
  15 //!   then we add a "verify" that checks that `'?1 <= 'a || '?1 <= 'b`.
  16 //!   - Note the difference with the previous case: here, the region
  17 //!     variable must be less than something else, so this doesn't
  18 //!     affect how inference works (it finds the smallest region that
  19 //!     will do); it's just a post-condition that we have to check.
  20 //!
  21 //! **The key point is that once this function is done, we have
  22 //! reduced all of our "type-region outlives" obligations into relationships
  23 //! between individual regions.**
  24 //!
  25 //! One key input to this function is the set of "region-bound pairs".
  26 //! These are basically the relationships between type parameters and
  27 //! regions that are in scope at the point where the outlives
  28 //! obligation was incurred. **When type-checking a function,
  29 //! particularly in the face of closures, this is not known until
  30 //! regionck runs!** This is because some of those bounds come
  31 //! from things we have yet to infer.
  32 //!
  33 //! Consider:
  34 //!
  35 //! ```
  36 //! fn bar<T>(a: T, b: impl for<'a> Fn(&'a T)) {}
  37 //! fn foo<T>(x: T) {
  38 //!     bar(x, |y| { /* ... */})
  39 //!          // ^ closure arg
  40 //! }
  41 //! ```
  42 //!
  43 //! Here, the type of `y` may involve inference variables and the
  44 //! like, and it may also contain implied bounds that are needed to
  45 //! type-check the closure body (e.g., here it informs us that `T`
  46 //! outlives the late-bound region `'a`).
  47 //!
  48 //! Note that by delaying the gathering of implied bounds until all
  49 //! inference information is known, we may find relationships between
  50 //! bound regions and other regions in the environment. For example,
  51 //! when we first check a closure like the one expected as argument
  52 //! to `foo`:
  53 //!
  54 //! ```
  55 //! fn foo<U, F: for<'a> FnMut(&'a U)>(_f: F) {}
  56 //! ```
  57 //!
  58 //! the type of the closure's first argument would be `&'a ?U`. We
  59 //! might later infer `?U` to something like `&'b u32`, which would
  60 //! imply that `'b: 'a`.
  61
  62 use crate::infer::outlives::components::{push_outlives_components, Component};
  63 use crate::infer::outlives::env::OutlivesEnvironment;
  64 use crate::infer::outlives::env::RegionBoundPairs;
  65 use crate::infer::outlives::verify::VerifyBoundCx;
  66 use crate::infer::{
  67     self, GenericKind, InferCtxt, RegionObligation, SubregionOrigin, UndoLog, VerifyBound,
  68 };
  69 use crate::traits::{ObligationCause, ObligationCauseCode};
  70 use rustc_data_structures::undo_log::UndoLogs;
  71 use rustc_hir::def_id::LocalDefId;
  72 use rustc_middle::ty::subst::GenericArgKind;
  73 use rustc_middle::ty::{self, Region, Ty, TyCtxt, TypeVisitable};
  74 use smallvec::smallvec;
  75
  76 impl<'cx, 'tcx> InferCtxt<'cx, 'tcx> {
  77     /// Registers that the given region obligation must be resolved
  78     /// from within the scope of `body_id`. These regions are enqueued
  79     /// and later processed by regionck, when full type information is
  80     /// available (see `region_obligations` field for more
  81     /// information).
  82     #[instrument(level = "debug", skip(self))]
  83     pub fn register_region_obligation(&self, obligation: RegionObligation<'tcx>) {
  84         let mut inner = self.inner.borrow_mut();
  85         inner.undo_log.push(UndoLog::PushRegionObligation);
  86         inner.region_obligations.push(obligation);
  87     }
  88
  89     pub fn register_region_obligation_with_cause(
  90         &self,
  91         sup_type: Ty<'tcx>,
  92         sub_region: Region<'tcx>,
  93         cause: &ObligationCause<'tcx>,
  94     ) {
  95         let origin = SubregionOrigin::from_obligation_cause(cause, || {
  96             infer::RelateParamBound(
  97                 cause.span,
  98                 sup_type,
  99                 match cause.code().peel_derives() {
 100                     ObligationCauseCode::BindingObligation(_, span) => Some(*span),
 101                     _ => None,
 102                 },
 103             )
 104         });
 105
 106         self.register_region_obligation(RegionObligation { sup_type, sub_region, origin });
 107     }
 108
 109     /// Trait queries just want to pass back type obligations "as is"
 110     pub fn take_registered_region_obligations(&self) -> Vec<RegionObligation<'tcx>> {
 111         std::mem::take(&mut self.inner.borrow_mut().region_obligations)
 112     }
 113
 114     /// Process the region obligations that must be proven (during
 115     /// `regionck`) for the given `body_id`, given information about
 116     /// the region bounds in scope and so forth. This function must be
 117     /// invoked for all relevant body-ids before region inference is
 118     /// done (or else an assert will fire).
 119     ///
 120     /// See the `region_obligations` field of `InferCtxt` for some
 121     /// comments about how this function fits into the overall expected
 122     /// flow of the inferencer. The key point is that it is
 123     /// invoked after all type-inference variables have been bound --
 124     /// towards the end of regionck. This also ensures that the
 125     /// region-bound-pairs are available (see comments above regarding
 126     /// closures).
 127     ///
 128     /// # Parameters
 129     ///
 130     /// - `region_bound_pairs_map`: the set of region bounds implied by
 131     ///   the parameters and where-clauses. In particular, each pair
 132     ///   `('a, K)` in this list tells us that the bounds in scope
 133     ///   indicate that `K: 'a`, where `K` is either a generic
 134     ///   parameter like `T` or a projection like `T::Item`.
 135     /// - `param_env` is the parameter environment for the enclosing function.
 136     /// - `body_id` is the body-id whose region obligations are being
 137     ///   processed.
 138     #[instrument(level = "debug", skip(self, region_bound_pairs))]
 139     pub fn process_registered_region_obligations(
 140         &self,
 141         region_bound_pairs: &RegionBoundPairs<'tcx>,
 142         param_env: ty::ParamEnv<'tcx>,
 143     ) {
 144         assert!(
 145             !self.in_snapshot.get(),
 146             "cannot process registered region obligations in a snapshot"
 147         );
 148
 149         let my_region_obligations = self.take_registered_region_obligations();
 150
 151         for RegionObligation { sup_type, sub_region, origin } in my_region_obligations {
 152             debug!(
 153                 "process_registered_region_obligations: sup_type={:?} sub_region={:?} origin={:?}",
 154                 sup_type, sub_region, origin
 155             );
 156
 157             let sup_type = self.resolve_vars_if_possible(sup_type);
 158
 159             let outlives =
 160                 &mut TypeOutlives::new(self, self.tcx, &region_bound_pairs, None, param_env);
 161             outlives.type_must_outlive(origin, sup_type, sub_region);
 162         }
 163     }
 164
 165     pub fn check_region_obligations_and_report_errors(
 166         &self,
 167         generic_param_scope: LocalDefId,
 168         outlives_env: &OutlivesEnvironment<'tcx>,
 169     ) {
 170         self.process_registered_region_obligations(
 171             outlives_env.region_bound_pairs(),
 172             outlives_env.param_env,
 173         );
 174
 175         self.resolve_regions_and_report_errors(generic_param_scope, outlives_env)
 176     }
 177 }
 178
 179 /// The `TypeOutlives` struct has the job of "lowering" a `T: 'a`
 180 /// obligation into a series of `'a: 'b` constraints and "verify"s, as
 181 /// described on the module comment. The final constraints are emitted
 182 /// via a "delegate" of type `D` -- this is usually the `infcx`, which
 183 /// accrues them into the `region_obligations` code, but for NLL we
 184 /// use something else.
 185 pub struct TypeOutlives<'cx, 'tcx, D>
 186 where
 187     D: TypeOutlivesDelegate<'tcx>,
 188 {
 189     // See the comments on `process_registered_region_obligations` for the meaning
 190     // of these fields.
 191     delegate: D,
 192     tcx: TyCtxt<'tcx>,
 193     verify_bound: VerifyBoundCx<'cx, 'tcx>,
 194 }
 195
 196 pub trait TypeOutlivesDelegate<'tcx> {
 197     fn push_sub_region_constraint(
 198         &mut self,
 199         origin: SubregionOrigin<'tcx>,
 200         a: ty::Region<'tcx>,
 201         b: ty::Region<'tcx>,
 202     );
 203
 204     fn push_verify(
 205         &mut self,
 206         origin: SubregionOrigin<'tcx>,
 207         kind: GenericKind<'tcx>,
 208         a: ty::Region<'tcx>,
 209         bound: VerifyBound<'tcx>,
 210     );
 211 }
 212
 213 impl<'cx, 'tcx, D> TypeOutlives<'cx, 'tcx, D>
 214 where
 215     D: TypeOutlivesDelegate<'tcx>,
 216 {
 217     pub fn new(
 218         delegate: D,
 219         tcx: TyCtxt<'tcx>,
 220         region_bound_pairs: &'cx RegionBoundPairs<'tcx>,
 221         implicit_region_bound: Option<ty::Region<'tcx>>,
 222         param_env: ty::ParamEnv<'tcx>,
 223     ) -> Self {
 224         Self {
 225             delegate,
 226             tcx,
 227             verify_bound: VerifyBoundCx::new(
 228                 tcx,
 229                 region_bound_pairs,
 230                 implicit_region_bound,
 231                 param_env,
 232             ),
 233         }
 234     }
 235
 236     /// Adds constraints to inference such that `T: 'a` holds (or
 237     /// reports an error if it cannot).
 238     ///
 239     /// # Parameters
 240     ///
 241     /// - `origin`, the reason we need this constraint
 242     /// - `ty`, the type `T`
 243     /// - `region`, the region `'a`
 244     pub fn type_must_outlive(
 245         &mut self,
 246         origin: infer::SubregionOrigin<'tcx>,
 247         ty: Ty<'tcx>,
 248         region: ty::Region<'tcx>,
 249     ) {
 250         debug!("type_must_outlive(ty={:?}, region={:?}, origin={:?})", ty, region, origin);
 251
 252         assert!(!ty.has_escaping_bound_vars());
 253
 254         let mut components = smallvec![];
 255         push_outlives_components(self.tcx, ty, &mut components);
 256         self.components_must_outlive(origin, &components, region);
 257     }
 258
 259     fn components_must_outlive(
 260         &mut self,
 261         origin: infer::SubregionOrigin<'tcx>,
 262         components: &[Component<'tcx>],
 263         region: ty::Region<'tcx>,
 264     ) {
 265         for component in components.iter() {
 266             let origin = origin.clone();
 267             match component {
 268                 Component::Region(region1) => {
 269                     self.delegate.push_sub_region_constraint(origin, region, *region1);
 270                 }
 271                 Component::Param(param_ty) => {
 272                     self.param_ty_must_outlive(origin, region, *param_ty);
 273                 }
 274                 Component::Projection(projection_ty) => {
 275                     self.projection_must_outlive(origin, region, *projection_ty);
 276                 }
 277                 Component::EscapingProjection(subcomponents) => {
 278                     self.components_must_outlive(origin, &subcomponents, region);
 279                 }
 280                 Component::UnresolvedInferenceVariable(v) => {
 281                     // ignore this, we presume it will yield an error
 282                     // later, since if a type variable is not resolved by
 283                     // this point it never will be
 284                     self.tcx.sess.delay_span_bug(
 285                         origin.span(),
 286                         &format!("unresolved inference variable in outlives: {:?}", v),
 287                     );
 288                 }
 289             }
 290         }
 291     }
 292
 293     fn param_ty_must_outlive(
 294         &mut self,
 295         origin: infer::SubregionOrigin<'tcx>,
 296         region: ty::Region<'tcx>,
 297         param_ty: ty::ParamTy,
 298     ) {
 299         debug!(
 300             "param_ty_must_outlive(region={:?}, param_ty={:?}, origin={:?})",
 301             region, param_ty, origin
 302         );
 303
 304         let generic = GenericKind::Param(param_ty);
 305         let verify_bound = self.verify_bound.generic_bound(generic);
 306         self.delegate.push_verify(origin, generic, region, verify_bound);
 307     }
 308
 309     #[tracing::instrument(level = "debug", skip(self))]
 310     fn projection_must_outlive(
 311         &mut self,
 312         origin: infer::SubregionOrigin<'tcx>,
 313         region: ty::Region<'tcx>,
 314         projection_ty: ty::ProjectionTy<'tcx>,
 315     ) {
 316         // This case is thorny for inference. The fundamental problem is
 317         // that there are many cases where we have choice, and inference
 318         // doesn't like choice (the current region inference in
 319         // particular). :) First off, we have to choose between using the
 320         // OutlivesProjectionEnv, OutlivesProjectionTraitDef, and
 321         // OutlivesProjectionComponent rules, any one of which is
 322         // sufficient.  If there are no inference variables involved, it's
 323         // not hard to pick the right rule, but if there are, we're in a
 324         // bit of a catch 22: if we picked which rule we were going to
 325         // use, we could add constraints to the region inference graph
 326         // that make it apply, but if we don't add those constraints, the
 327         // rule might not apply (but another rule might). For now, we err
 328         // on the side of adding too few edges into the graph.
 329
 330         // Compute the bounds we can derive from the trait definition.
 331         // These are guaranteed to apply, no matter the inference
 332         // results.
 333         let trait_bounds: Vec<_> =
 334             self.verify_bound.projection_declared_bounds_from_trait(projection_ty).collect();
 335
 336         debug!(?trait_bounds);
 337
 338         // Compute the bounds we can derive from the environment. This
 339         // is an "approximate" match -- in some cases, these bounds
 340         // may not apply.
 341         let mut approx_env_bounds =
 342             self.verify_bound.projection_approx_declared_bounds_from_env(projection_ty);
 343         debug!("projection_must_outlive: approx_env_bounds={:?}", approx_env_bounds);
 344
 345         // Remove outlives bounds that we get from the environment but
 346         // which are also deducible from the trait. This arises (cc
 347         // #55756) in cases where you have e.g., `<T as Foo<'a>>::Item:
 348         // 'a` in the environment but `trait Foo<'b> { type Item: 'b
 349         // }` in the trait definition.
 350         approx_env_bounds.retain(|bound_outlives| {
 351             // OK to skip binder because we only manipulate and compare against other
 352             // values from the same binder. e.g. if we have (e.g.) `for<'a> <T as Trait<'a>>::Item: 'a`
 353             // in `bound`, the `'a` will be a `^1` (bound, debruijn index == innermost) region.
 354             // If the declaration is `trait Trait<'b> { type Item: 'b; }`, then `projection_declared_bounds_from_trait`
 355             // will be invoked with `['b => ^1]` and so we will get `^1` returned.
 356             let bound = bound_outlives.skip_binder();
 357             match *bound.0.kind() {
 358                 ty::Projection(projection_ty) => self
 359                     .verify_bound
 360                     .projection_declared_bounds_from_trait(projection_ty)
 361                     .all(|r| r != bound.1),
 362
 363                 _ => panic!("expected only projection types from env, not {:?}", bound.0),
 364             }
 365         });
 366
 367         // If declared bounds list is empty, the only applicable rule is
 368         // OutlivesProjectionComponent. If there are inference variables,
 369         // then, we can break down the outlives into more primitive
 370         // components without adding unnecessary edges.
 371         //
 372         // If there are *no* inference variables, however, we COULD do
 373         // this, but we choose not to, because the error messages are less
 374         // good. For example, a requirement like `T::Item: 'r` would be
 375         // translated to a requirement that `T: 'r`; when this is reported
 376         // to the user, it will thus say "T: 'r must hold so that T::Item:
 377         // 'r holds". But that makes it sound like the only way to fix
 378         // the problem is to add `T: 'r`, which isn't true. So, if there are no
 379         // inference variables, we use a verify constraint instead of adding
 380         // edges, which winds up enforcing the same condition.
 381         let needs_infer = projection_ty.needs_infer();
 382         if approx_env_bounds.is_empty() && trait_bounds.is_empty() && needs_infer {
 383             debug!("projection_must_outlive: no declared bounds");
 384
 385             for k in projection_ty.substs {
 386                 match k.unpack() {
 387                     GenericArgKind::Lifetime(lt) => {
 388                         self.delegate.push_sub_region_constraint(origin.clone(), region, lt);
 389                     }
 390                     GenericArgKind::Type(ty) => {
 391                         self.type_must_outlive(origin.clone(), ty, region);
 392                     }
 393                     GenericArgKind::Const(_) => {
 394                         // Const parameters don't impose constraints.
 395                     }
 396                 }
 397             }
 398
 399             return;
 400         }
 401
 402         // If we found a unique bound `'b` from the trait, and we
 403         // found nothing else from the environment, then the best
 404         // action is to require that `'b: 'r`, so do that.
 405         //
 406         // This is best no matter what rule we use:
 407         //
 408         // - OutlivesProjectionEnv: these would translate to the requirement that `'b:'r`
 409         // - OutlivesProjectionTraitDef: these would translate to the requirement that `'b:'r`
 410         // - OutlivesProjectionComponent: this would require `'b:'r`
 411         //   in addition to other conditions
 412         if !trait_bounds.is_empty()
 413             && trait_bounds[1..]
 414                 .iter()
 415                 .map(|r| Some(*r))
 416                 .chain(
 417                     // NB: The environment may contain `for<'a> T: 'a` style bounds.
 418                     // In that case, we don't know if they are equal to the trait bound
 419                     // or not (since we don't *know* whether the environment bound even applies),
 420                     // so just map to `None` here if there are bound vars, ensuring that
 421                     // the call to `all` will fail below.
 422                     approx_env_bounds.iter().map(|b| b.map_bound(|b| b.1).no_bound_vars()),
 423                 )
 424                 .all(|b| b == Some(trait_bounds[0]))
 425         {
 426             let unique_bound = trait_bounds[0];
 427             debug!("projection_must_outlive: unique trait bound = {:?}", unique_bound);
 428             debug!("projection_must_outlive: unique declared bound appears in trait ref");
 429             self.delegate.push_sub_region_constraint(origin, region, unique_bound);
 430             return;
 431         }
 432
 433         // Fallback to verifying after the fact that there exists a
 434         // declared bound, or that all the components appearing in the
 435         // projection outlive; in some cases, this may add insufficient
 436         // edges into the inference graph, leading to inference failures
 437         // even though a satisfactory solution exists.
 438         let generic = GenericKind::Projection(projection_ty);
 439         let verify_bound = self.verify_bound.generic_bound(generic);
 440         debug!("projection_must_outlive: pushing {:?}", verify_bound);
 441         self.delegate.push_verify(origin, generic, region, verify_bound);
 442     }
 443 }
 444
 445 impl<'cx, 'tcx> TypeOutlivesDelegate<'tcx> for &'cx InferCtxt<'cx, 'tcx> {
 446     fn push_sub_region_constraint(
 447         &mut self,
 448         origin: SubregionOrigin<'tcx>,
 449         a: ty::Region<'tcx>,
 450         b: ty::Region<'tcx>,
 451     ) {
 452         self.sub_regions(origin, a, b)
 453     }
 454
 455     fn push_verify(
 456         &mut self,
 457         origin: SubregionOrigin<'tcx>,
 458         kind: GenericKind<'tcx>,
 459         a: ty::Region<'tcx>,
 460         bound: VerifyBound<'tcx>,
 461     ) {
 462         self.verify_generic_bound(origin, kind, a, bound)
 463     }
 464 }