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

   1 use crate::infer::outlives::components::{compute_components_recursive, Component};
   2 use crate::infer::outlives::env::RegionBoundPairs;
   3 use crate::infer::region_constraints::VerifyIfEq;
   4 use crate::infer::{GenericKind, VerifyBound};
   5 use rustc_data_structures::captures::Captures;
   6 use rustc_data_structures::sso::SsoHashSet;
   7 use rustc_hir::def_id::DefId;
   8 use rustc_middle::ty::subst::{GenericArg, Subst};
   9 use rustc_middle::ty::{self, EarlyBinder, OutlivesPredicate, Ty, TyCtxt};
  10
  11 use smallvec::smallvec;
  12
  13 /// The `TypeOutlives` struct has the job of "lowering" a `T: 'a`
  14 /// obligation into a series of `'a: 'b` constraints and "verifys", as
  15 /// described on the module comment. The final constraints are emitted
  16 /// via a "delegate" of type `D` -- this is usually the `infcx`, which
  17 /// accrues them into the `region_obligations` code, but for NLL we
  18 /// use something else.
  19 pub struct VerifyBoundCx<'cx, 'tcx> {
  20     tcx: TyCtxt<'tcx>,
  21     region_bound_pairs: &'cx RegionBoundPairs<'tcx>,
  22     /// During borrowck, if there are no outlives bounds on a generic
  23     /// parameter `T`, we assume that `T: 'in_fn_body` holds.
  24     ///
  25     /// Outside of borrowck the only way to prove `T: '?0` is by
  26     /// setting  `'?0` to `'empty`.
  27     implicit_region_bound: Option<ty::Region<'tcx>>,
  28     param_env: ty::ParamEnv<'tcx>,
  29 }
  30
  31 impl<'cx, 'tcx> VerifyBoundCx<'cx, 'tcx> {
  32     pub fn new(
  33         tcx: TyCtxt<'tcx>,
  34         region_bound_pairs: &'cx RegionBoundPairs<'tcx>,
  35         implicit_region_bound: Option<ty::Region<'tcx>>,
  36         param_env: ty::ParamEnv<'tcx>,
  37     ) -> Self {
  38         Self { tcx, region_bound_pairs, implicit_region_bound, param_env }
  39     }
  40
  41     /// Returns a "verify bound" that encodes what we know about
  42     /// `generic` and the regions it outlives.
  43     pub fn generic_bound(&self, generic: GenericKind<'tcx>) -> VerifyBound<'tcx> {
  44         let mut visited = SsoHashSet::new();
  45         match generic {
  46             GenericKind::Param(param_ty) => self.param_bound(param_ty),
  47             GenericKind::Projection(projection_ty) => {
  48                 self.projection_bound(projection_ty, &mut visited)
  49             }
  50         }
  51     }
  52
  53     fn param_bound(&self, param_ty: ty::ParamTy) -> VerifyBound<'tcx> {
  54         debug!("param_bound(param_ty={:?})", param_ty);
  55
  56         // Start with anything like `T: 'a` we can scrape from the
  57         // environment. If the environment contains something like
  58         // `for<'a> T: 'a`, then we know that `T` outlives everything.
  59         let declared_bounds_from_env = self.declared_generic_bounds_from_env(param_ty);
  60         let mut param_bounds = vec![];
  61         for declared_bound in declared_bounds_from_env {
  62             let bound_region = declared_bound.map_bound(|outlives| outlives.1);
  63             if let Some(region) = bound_region.no_bound_vars() {
  64                 // This is `T: 'a` for some free region `'a`.
  65                 param_bounds.push(VerifyBound::OutlivedBy(region));
  66             } else {
  67                 // This is `for<'a> T: 'a`. This means that `T` outlives everything! All done here.
  68                 return VerifyBound::AllBounds(vec![]);
  69             }
  70         }
  71
  72         // Add in the default bound of fn body that applies to all in
  73         // scope type parameters:
  74         if let Some(r) = self.implicit_region_bound {
  75             param_bounds.push(VerifyBound::OutlivedBy(r));
  76         }
  77
  78         if param_bounds.is_empty() {
  79             // We know that all types `T` outlive `'empty`, so if we
  80             // can find no other bound, then check that the region
  81             // being tested is `'empty`.
  82             VerifyBound::IsEmpty
  83         } else if param_bounds.len() == 1 {
  84             // Micro-opt: no need to store the vector if it's just len 1
  85             param_bounds.pop().unwrap()
  86         } else {
  87             // If we can find any other bound `R` such that `T: R`, then
  88             // we don't need to check for `'empty`, because `R: 'empty`.
  89             VerifyBound::AnyBound(param_bounds)
  90         }
  91     }
  92
  93     /// Given a projection like `T::Item`, searches the environment
  94     /// for where-clauses like `T::Item: 'a`. Returns the set of
  95     /// regions `'a` that it finds.
  96     ///
  97     /// This is an "approximate" check -- it may not find all
  98     /// applicable bounds, and not all the bounds it returns can be
  99     /// relied upon. In particular, this check ignores region
 100     /// identity. So, for example, if we have `<T as
 101     /// Trait<'0>>::Item` where `'0` is a region variable, and the
 102     /// user has `<T as Trait<'a>>::Item: 'b` in the environment, then
 103     /// the clause from the environment only applies if `'0 = 'a`,
 104     /// which we don't know yet. But we would still include `'b` in
 105     /// this list.
 106     pub fn projection_approx_declared_bounds_from_env(
 107         &self,
 108         projection_ty: ty::ProjectionTy<'tcx>,
 109     ) -> Vec<ty::Binder<'tcx, ty::OutlivesPredicate<Ty<'tcx>, ty::Region<'tcx>>>> {
 110         let projection_ty = GenericKind::Projection(projection_ty).to_ty(self.tcx);
 111         let erased_projection_ty = self.tcx.erase_regions(projection_ty);
 112         self.declared_generic_bounds_from_env_for_erased_ty(erased_projection_ty)
 113     }
 114
 115     /// Searches the where-clauses in scope for regions that
 116     /// `projection_ty` is known to outlive. Currently requires an
 117     /// exact match.
 118     pub fn projection_declared_bounds_from_trait(
 119         &self,
 120         projection_ty: ty::ProjectionTy<'tcx>,
 121     ) -> impl Iterator<Item = ty::Region<'tcx>> + 'cx + Captures<'tcx> {
 122         self.declared_projection_bounds_from_trait(projection_ty)
 123     }
 124
 125     pub fn projection_bound(
 126         &self,
 127         projection_ty: ty::ProjectionTy<'tcx>,
 128         visited: &mut SsoHashSet<GenericArg<'tcx>>,
 129     ) -> VerifyBound<'tcx> {
 130         debug!("projection_bound(projection_ty={:?})", projection_ty);
 131
 132         let projection_ty_as_ty =
 133             self.tcx.mk_projection(projection_ty.item_def_id, projection_ty.substs);
 134
 135         // Search the env for where clauses like `P: 'a`.
 136         let env_bounds = self
 137             .projection_approx_declared_bounds_from_env(projection_ty)
 138             .into_iter()
 139             .map(|binder| {
 140                 if let Some(ty::OutlivesPredicate(ty, r)) = binder.no_bound_vars() && ty == projection_ty_as_ty {
 141                     // Micro-optimize if this is an exact match (this
 142                     // occurs often when there are no region variables
 143                     // involved).
 144                     VerifyBound::OutlivedBy(r)
 145                 } else {
 146                     let verify_if_eq_b = binder.map_bound(|ty::OutlivesPredicate(ty, bound)| VerifyIfEq { ty, bound });
 147                     VerifyBound::IfEq(verify_if_eq_b)
 148                 }
 149             });
 150
 151         // Extend with bounds that we can find from the trait.
 152         let trait_bounds = self
 153             .projection_declared_bounds_from_trait(projection_ty)
 154             .map(|r| VerifyBound::OutlivedBy(r));
 155
 156         // see the extensive comment in projection_must_outlive
 157         let recursive_bound = {
 158             let mut components = smallvec![];
 159             let ty = self.tcx.mk_projection(projection_ty.item_def_id, projection_ty.substs);
 160             compute_components_recursive(self.tcx, ty.into(), &mut components, visited);
 161             self.bound_from_components(&components, visited)
 162         };
 163
 164         VerifyBound::AnyBound(env_bounds.chain(trait_bounds).collect()).or(recursive_bound)
 165     }
 166
 167     fn bound_from_components(
 168         &self,
 169         components: &[Component<'tcx>],
 170         visited: &mut SsoHashSet<GenericArg<'tcx>>,
 171     ) -> VerifyBound<'tcx> {
 172         let mut bounds = components
 173             .iter()
 174             .map(|component| self.bound_from_single_component(component, visited))
 175             .filter(|bound| {
 176                 // Remove bounds that must hold, since they are not interesting.
 177                 !bound.must_hold()
 178             });
 179
 180         match (bounds.next(), bounds.next()) {
 181             (Some(first), None) => first,
 182             (first, second) => {
 183                 VerifyBound::AllBounds(first.into_iter().chain(second).chain(bounds).collect())
 184             }
 185         }
 186     }
 187
 188     fn bound_from_single_component(
 189         &self,
 190         component: &Component<'tcx>,
 191         visited: &mut SsoHashSet<GenericArg<'tcx>>,
 192     ) -> VerifyBound<'tcx> {
 193         match *component {
 194             Component::Region(lt) => VerifyBound::OutlivedBy(lt),
 195             Component::Param(param_ty) => self.param_bound(param_ty),
 196             Component::Projection(projection_ty) => self.projection_bound(projection_ty, visited),
 197             Component::EscapingProjection(ref components) => {
 198                 self.bound_from_components(components, visited)
 199             }
 200             Component::UnresolvedInferenceVariable(v) => {
 201                 // ignore this, we presume it will yield an error
 202                 // later, since if a type variable is not resolved by
 203                 // this point it never will be
 204                 self.tcx.sess.delay_span_bug(
 205                     rustc_span::DUMMY_SP,
 206                     &format!("unresolved inference variable in outlives: {:?}", v),
 207                 );
 208                 // add a bound that never holds
 209                 VerifyBound::AnyBound(vec![])
 210             }
 211         }
 212     }
 213
 214     /// Searches the environment for where-clauses like `G: 'a` where
 215     /// `G` is either some type parameter `T` or a projection like
 216     /// `T::Item`. Returns a vector of the `'a` bounds it can find.
 217     ///
 218     /// This is a conservative check -- it may not find all applicable
 219     /// bounds, but all the bounds it returns can be relied upon.
 220     fn declared_generic_bounds_from_env(
 221         &self,
 222         param_ty: ty::ParamTy,
 223     ) -> Vec<ty::Binder<'tcx, ty::OutlivesPredicate<Ty<'tcx>, ty::Region<'tcx>>>> {
 224         let generic_ty = param_ty.to_ty(self.tcx);
 225         self.declared_generic_bounds_from_env_for_erased_ty(generic_ty)
 226     }
 227
 228     /// Searches the environment to find all bounds that apply to `erased_ty`.
 229     /// Obviously these must be approximate -- they are in fact both *over* and
 230     /// and *under* approximated:
 231     ///
 232     /// * Over-approximated because we erase regions, so
 233     /// * Under-approximated because we look for syntactic equality and so for complex types
 234     ///   like `<T as Foo<fn(&u32, &u32)>>::Item` or whatever we may fail to figure out
 235     ///   all the subtleties.
 236     ///
 237     /// In some cases, such as when `erased_ty` represents a `ty::Param`, however,
 238     /// the result is precise.
 239     fn declared_generic_bounds_from_env_for_erased_ty(
 240         &self,
 241         erased_ty: Ty<'tcx>,
 242     ) -> Vec<ty::Binder<'tcx, ty::OutlivesPredicate<Ty<'tcx>, ty::Region<'tcx>>>> {
 243         let tcx = self.tcx;
 244
 245         // To start, collect bounds from user environment. Note that
 246         // parameter environments are already elaborated, so we don't
 247         // have to worry about that.
 248         let c_b = self.param_env.caller_bounds();
 249         let param_bounds = self.collect_outlives_from_predicate_list(erased_ty, c_b.into_iter());
 250
 251         // Next, collect regions we scraped from the well-formedness
 252         // constraints in the fn signature. To do that, we walk the list
 253         // of known relations from the fn ctxt.
 254         //
 255         // This is crucial because otherwise code like this fails:
 256         //
 257         //     fn foo<'a, A>(x: &'a A) { x.bar() }
 258         //
 259         // The problem is that the type of `x` is `&'a A`. To be
 260         // well-formed, then, A must outlive `'a`, but we don't know that
 261         // this holds from first principles.
 262         let from_region_bound_pairs =
 263             self.region_bound_pairs.iter().filter_map(|&OutlivesPredicate(p, r)| {
 264                 debug!(
 265                     "declared_generic_bounds_from_env_for_erased_ty: region_bound_pair = {:?}",
 266                     (r, p)
 267                 );
 268                 let p_ty = p.to_ty(tcx);
 269                 let erased_p_ty = self.tcx.erase_regions(p_ty);
 270                 (erased_p_ty == erased_ty)
 271                     .then_some(ty::Binder::dummy(ty::OutlivesPredicate(p.to_ty(tcx), r)))
 272             });
 273
 274         param_bounds
 275             .chain(from_region_bound_pairs)
 276             .inspect(|bound| {
 277                 debug!(
 278                     "declared_generic_bounds_from_env_for_erased_ty: result predicate = {:?}",
 279                     bound
 280                 )
 281             })
 282             .collect()
 283     }
 284
 285     /// Given a projection like `<T as Foo<'x>>::Bar`, returns any bounds
 286     /// declared in the trait definition. For example, if the trait were
 287     ///
 288     /// ```rust
 289     /// trait Foo<'a> {
 290     ///     type Bar: 'a;
 291     /// }
 292     /// ```
 293     ///
 294     /// then this function would return `'x`. This is subject to the
 295     /// limitations around higher-ranked bounds described in
 296     /// `region_bounds_declared_on_associated_item`.
 297     fn declared_projection_bounds_from_trait(
 298         &self,
 299         projection_ty: ty::ProjectionTy<'tcx>,
 300     ) -> impl Iterator<Item = ty::Region<'tcx>> + 'cx + Captures<'tcx> {
 301         debug!("projection_bounds(projection_ty={:?})", projection_ty);
 302         let tcx = self.tcx;
 303         self.region_bounds_declared_on_associated_item(projection_ty.item_def_id)
 304             .map(move |r| EarlyBinder(r).subst(tcx, projection_ty.substs))
 305     }
 306
 307     /// Given the `DefId` of an associated item, returns any region
 308     /// bounds attached to that associated item from the trait definition.
 309     ///
 310     /// For example:
 311     ///
 312     /// ```rust
 313     /// trait Foo<'a> {
 314     ///     type Bar: 'a;
 315     /// }
 316     /// ```
 317     ///
 318     /// If we were given the `DefId` of `Foo::Bar`, we would return
 319     /// `'a`. You could then apply the substitutions from the
 320     /// projection to convert this into your namespace. This also
 321     /// works if the user writes `where <Self as Foo<'a>>::Bar: 'a` on
 322     /// the trait. In fact, it works by searching for just such a
 323     /// where-clause.
 324     ///
 325     /// It will not, however, work for higher-ranked bounds like:
 326     ///
 327     /// ```compile_fail,E0311
 328     /// trait Foo<'a, 'b>
 329     /// where for<'x> <Self as Foo<'x, 'b>>::Bar: 'x
 330     /// {
 331     ///     type Bar;
 332     /// }
 333     /// ```
 334     ///
 335     /// This is for simplicity, and because we are not really smart
 336     /// enough to cope with such bounds anywhere.
 337     fn region_bounds_declared_on_associated_item(
 338         &self,
 339         assoc_item_def_id: DefId,
 340     ) -> impl Iterator<Item = ty::Region<'tcx>> {
 341         let tcx = self.tcx;
 342         let bounds = tcx.item_bounds(assoc_item_def_id);
 343         bounds
 344             .into_iter()
 345             .filter_map(|p| p.to_opt_type_outlives())
 346             .filter_map(|p| p.no_bound_vars())
 347             .map(|b| b.1)
 348     }
 349
 350     /// Searches through a predicate list for a predicate `T: 'a`.
 351     ///
 352     /// Careful: does not elaborate predicates, and just uses `==`
 353     /// when comparing `ty` for equality, so `ty` must be something
 354     /// that does not involve inference variables and where you
 355     /// otherwise want a precise match.
 356     fn collect_outlives_from_predicate_list(
 357         &self,
 358         erased_ty: Ty<'tcx>,
 359         predicates: impl Iterator<Item = ty::Predicate<'tcx>>,
 360     ) -> impl Iterator<Item = ty::Binder<'tcx, ty::OutlivesPredicate<Ty<'tcx>, ty::Region<'tcx>>>>
 361     {
 362         let tcx = self.tcx;
 363         let param_env = self.param_env;
 364         predicates.filter_map(|p| p.to_opt_type_outlives()).filter(move |outlives_predicate| {
 365             super::test_type_match::can_match_erased_ty(
 366                 tcx,
 367                 param_env,
 368                 *outlives_predicate,
 369                 erased_ty,
 370             )
 371         })
 372     }
 373 }