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