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

   1 use crate::infer::outlives::env::RegionBoundPairs;
   2 use crate::infer::{GenericKind, VerifyBound};
   3 use rustc_data_structures::captures::Captures;
   4 use rustc_data_structures::sso::SsoHashSet;
   5 use rustc_hir::def_id::DefId;
   6 use rustc_middle::ty::subst::{GenericArg, GenericArgKind, Subst};
   7 use rustc_middle::ty::{self, Ty, TyCtxt};
   8
   9 /// The `TypeOutlives` struct has the job of "lowering" a `T: 'a`
  10 /// obligation into a series of `'a: 'b` constraints and "verifys", as
  11 /// described on the module comment. The final constraints are emitted
  12 /// via a "delegate" of type `D` -- this is usually the `infcx`, which
  13 /// accrues them into the `region_obligations` code, but for NLL we
  14 /// use something else.
  15 pub struct VerifyBoundCx<'cx, 'tcx> {
  16     tcx: TyCtxt<'tcx>,
  17     region_bound_pairs: &'cx RegionBoundPairs<'tcx>,
  18     implicit_region_bound: Option<ty::Region<'tcx>>,
  19     param_env: ty::ParamEnv<'tcx>,
  20 }
  21
  22 impl<'cx, 'tcx> VerifyBoundCx<'cx, 'tcx> {
  23     pub fn new(
  24         tcx: TyCtxt<'tcx>,
  25         region_bound_pairs: &'cx RegionBoundPairs<'tcx>,
  26         implicit_region_bound: Option<ty::Region<'tcx>>,
  27         param_env: ty::ParamEnv<'tcx>,
  28     ) -> Self {
  29         Self { tcx, region_bound_pairs, implicit_region_bound, param_env }
  30     }
  31
  32     /// Returns a "verify bound" that encodes what we know about
  33     /// `generic` and the regions it outlives.
  34     pub fn generic_bound(&self, generic: GenericKind<'tcx>) -> VerifyBound<'tcx> {
  35         let mut visited = SsoHashSet::new();
  36         match generic {
  37             GenericKind::Param(param_ty) => self.param_bound(param_ty),
  38             GenericKind::Projection(projection_ty) => {
  39                 self.projection_bound(projection_ty, &mut visited)
  40             }
  41         }
  42     }
  43
  44     fn type_bound(
  45         &self,
  46         ty: Ty<'tcx>,
  47         visited: &mut SsoHashSet<GenericArg<'tcx>>,
  48     ) -> VerifyBound<'tcx> {
  49         match *ty.kind() {
  50             ty::Param(p) => self.param_bound(p),
  51             ty::Projection(data) => self.projection_bound(data, visited),
  52             ty::FnDef(_, substs) => {
  53                 // HACK(eddyb) ignore lifetimes found shallowly in `substs`.
  54                 // This is inconsistent with `ty::Adt` (including all substs),
  55                 // but consistent with previous (accidental) behavior.
  56                 // See https://github.com/rust-lang/rust/issues/70917
  57                 // for further background and discussion.
  58                 let mut bounds = substs
  59                     .iter()
  60                     .filter_map(|child| match child.unpack() {
  61                         GenericArgKind::Type(ty) => Some(self.type_bound(ty, visited)),
  62                         GenericArgKind::Lifetime(_) => None,
  63                         GenericArgKind::Const(_) => Some(self.recursive_bound(child, visited)),
  64                     })
  65                     .filter(|bound| {
  66                         // Remove bounds that must hold, since they are not interesting.
  67                         !bound.must_hold()
  68                     });
  69
  70                 match (bounds.next(), bounds.next()) {
  71                     (Some(first), None) => first,
  72                     (first, second) => VerifyBound::AllBounds(
  73                         first.into_iter().chain(second).chain(bounds).collect(),
  74                     ),
  75                 }
  76             }
  77             _ => self.recursive_bound(ty.into(), visited),
  78         }
  79     }
  80
  81     fn param_bound(&self, param_ty: ty::ParamTy) -> VerifyBound<'tcx> {
  82         debug!("param_bound(param_ty={:?})", param_ty);
  83
  84         // Start with anything like `T: 'a` we can scrape from the
  85         // environment
  86         let param_bounds = self
  87             .declared_generic_bounds_from_env(GenericKind::Param(param_ty))
  88             .into_iter()
  89             .map(|outlives| outlives.1);
  90
  91         // Add in the default bound of fn body that applies to all in
  92         // scope type parameters:
  93         let param_bounds = param_bounds.chain(self.implicit_region_bound);
  94
  95         let any_bounds: Vec<_> = param_bounds.map(|r| VerifyBound::OutlivedBy(r)).collect();
  96
  97         if any_bounds.is_empty() {
  98             // We know that all types `T` outlive `'empty`, so if we
  99             // can find no other bound, then check that the region
 100             // being tested is `'empty`.
 101             VerifyBound::IsEmpty
 102         } else {
 103             // If we can find any other bound `R` such that `T: R`, then
 104             // we don't need to check for `'empty`, because `R: 'empty`.
 105             VerifyBound::AnyBound(any_bounds)
 106         }
 107     }
 108
 109     /// Given a projection like `T::Item`, searches the environment
 110     /// for where-clauses like `T::Item: 'a`. Returns the set of
 111     /// regions `'a` that it finds.
 112     ///
 113     /// This is an "approximate" check -- it may not find all
 114     /// applicable bounds, and not all the bounds it returns can be
 115     /// relied upon. In particular, this check ignores region
 116     /// identity. So, for example, if we have `<T as
 117     /// Trait<'0>>::Item` where `'0` is a region variable, and the
 118     /// user has `<T as Trait<'a>>::Item: 'b` in the environment, then
 119     /// the clause from the environment only applies if `'0 = 'a`,
 120     /// which we don't know yet. But we would still include `'b` in
 121     /// this list.
 122     pub fn projection_approx_declared_bounds_from_env(
 123         &self,
 124         projection_ty: ty::ProjectionTy<'tcx>,
 125     ) -> Vec<ty::OutlivesPredicate<Ty<'tcx>, ty::Region<'tcx>>> {
 126         let projection_ty = GenericKind::Projection(projection_ty).to_ty(self.tcx);
 127         let erased_projection_ty = self.tcx.erase_regions(&projection_ty);
 128         self.declared_generic_bounds_from_env_with_compare_fn(|ty| {
 129             if let ty::Projection(..) = ty.kind() {
 130                 let erased_ty = self.tcx.erase_regions(&ty);
 131                 erased_ty == erased_projection_ty
 132             } else {
 133                 false
 134             }
 135         })
 136     }
 137
 138     /// Searches the where-clauses in scope for regions that
 139     /// `projection_ty` is known to outlive. Currently requires an
 140     /// exact match.
 141     pub fn projection_declared_bounds_from_trait(
 142         &self,
 143         projection_ty: ty::ProjectionTy<'tcx>,
 144     ) -> impl Iterator<Item = ty::Region<'tcx>> + 'cx + Captures<'tcx> {
 145         self.declared_projection_bounds_from_trait(projection_ty)
 146     }
 147
 148     pub fn projection_bound(
 149         &self,
 150         projection_ty: ty::ProjectionTy<'tcx>,
 151         visited: &mut SsoHashSet<GenericArg<'tcx>>,
 152     ) -> VerifyBound<'tcx> {
 153         debug!("projection_bound(projection_ty={:?})", projection_ty);
 154
 155         let projection_ty_as_ty =
 156             self.tcx.mk_projection(projection_ty.item_def_id, projection_ty.substs);
 157
 158         // Search the env for where clauses like `P: 'a`.
 159         let env_bounds = self
 160             .projection_approx_declared_bounds_from_env(projection_ty)
 161             .into_iter()
 162             .map(|ty::OutlivesPredicate(ty, r)| {
 163                 let vb = VerifyBound::OutlivedBy(r);
 164                 if ty == projection_ty_as_ty {
 165                     // Micro-optimize if this is an exact match (this
 166                     // occurs often when there are no region variables
 167                     // involved).
 168                     vb
 169                 } else {
 170                     VerifyBound::IfEq(ty, Box::new(vb))
 171                 }
 172             });
 173
 174         // Extend with bounds that we can find from the trait.
 175         let trait_bounds = self
 176             .projection_declared_bounds_from_trait(projection_ty)
 177             .map(|r| VerifyBound::OutlivedBy(r));
 178
 179         // see the extensive comment in projection_must_outlive
 180         let ty = self.tcx.mk_projection(projection_ty.item_def_id, projection_ty.substs);
 181         let recursive_bound = self.recursive_bound(ty.into(), visited);
 182
 183         VerifyBound::AnyBound(env_bounds.chain(trait_bounds).collect()).or(recursive_bound)
 184     }
 185
 186     fn recursive_bound(
 187         &self,
 188         parent: GenericArg<'tcx>,
 189         visited: &mut SsoHashSet<GenericArg<'tcx>>,
 190     ) -> VerifyBound<'tcx> {
 191         let mut bounds = parent
 192             .walk_shallow(visited)
 193             .filter_map(|child| match child.unpack() {
 194                 GenericArgKind::Type(ty) => Some(self.type_bound(ty, visited)),
 195                 GenericArgKind::Lifetime(lt) => {
 196                     // Ignore late-bound regions.
 197                     if !lt.is_late_bound() { Some(VerifyBound::OutlivedBy(lt)) } else { None }
 198                 }
 199                 GenericArgKind::Const(_) => Some(self.recursive_bound(child, visited)),
 200             })
 201             .filter(|bound| {
 202                 // Remove bounds that must hold, since they are not interesting.
 203                 !bound.must_hold()
 204             });
 205
 206         match (bounds.next(), bounds.next()) {
 207             (Some(first), None) => first,
 208             (first, second) => {
 209                 VerifyBound::AllBounds(first.into_iter().chain(second).chain(bounds).collect())
 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         generic: GenericKind<'tcx>,
 223     ) -> Vec<ty::OutlivesPredicate<Ty<'tcx>, ty::Region<'tcx>>> {
 224         let generic_ty = generic.to_ty(self.tcx);
 225         self.declared_generic_bounds_from_env_with_compare_fn(|ty| ty == generic_ty)
 226     }
 227
 228     fn declared_generic_bounds_from_env_with_compare_fn(
 229         &self,
 230         compare_ty: impl Fn(Ty<'tcx>) -> bool,
 231     ) -> Vec<ty::OutlivesPredicate<Ty<'tcx>, ty::Region<'tcx>>> {
 232         let tcx = self.tcx;
 233
 234         // To start, collect bounds from user environment. Note that
 235         // parameter environments are already elaborated, so we don't
 236         // have to worry about that. Comparing using `==` is a bit
 237         // dubious for projections, but it will work for simple cases
 238         // like `T` and `T::Item`. It may not work as well for things
 239         // like `<T as Foo<'a>>::Item`.
 240         let c_b = self.param_env.caller_bounds();
 241         let param_bounds = self.collect_outlives_from_predicate_list(&compare_ty, c_b.into_iter());
 242
 243         // Next, collect regions we scraped from the well-formedness
 244         // constraints in the fn signature. To do that, we walk the list
 245         // of known relations from the fn ctxt.
 246         //
 247         // This is crucial because otherwise code like this fails:
 248         //
 249         //     fn foo<'a, A>(x: &'a A) { x.bar() }
 250         //
 251         // The problem is that the type of `x` is `&'a A`. To be
 252         // well-formed, then, A must be lower-generic by `'a`, but we
 253         // don't know that this holds from first principles.
 254         let from_region_bound_pairs = self.region_bound_pairs.iter().filter_map(|&(r, p)| {
 255             debug!(
 256                 "declared_generic_bounds_from_env_with_compare_fn: region_bound_pair = {:?}",
 257                 (r, p)
 258             );
 259             let p_ty = p.to_ty(tcx);
 260             compare_ty(p_ty).then_some(ty::OutlivesPredicate(p_ty, r))
 261         });
 262
 263         param_bounds
 264             .chain(from_region_bound_pairs)
 265             .inspect(|bound| {
 266                 debug!(
 267                     "declared_generic_bounds_from_env_with_compare_fn: result predicate = {:?}",
 268                     bound
 269                 )
 270             })
 271             .collect()
 272     }
 273
 274     /// Given a projection like `<T as Foo<'x>>::Bar`, returns any bounds
 275     /// declared in the trait definition. For example, if the trait were
 276     ///
 277     /// ```rust
 278     /// trait Foo<'a> {
 279     ///     type Bar: 'a;
 280     /// }
 281     /// ```
 282     ///
 283     /// then this function would return `'x`. This is subject to the
 284     /// limitations around higher-ranked bounds described in
 285     /// `region_bounds_declared_on_associated_item`.
 286     fn declared_projection_bounds_from_trait(
 287         &self,
 288         projection_ty: ty::ProjectionTy<'tcx>,
 289     ) -> impl Iterator<Item = ty::Region<'tcx>> + 'cx + Captures<'tcx> {
 290         debug!("projection_bounds(projection_ty={:?})", projection_ty);
 291         let tcx = self.tcx;
 292         self.region_bounds_declared_on_associated_item(projection_ty.item_def_id)
 293             .map(move |r| r.subst(tcx, projection_ty.substs))
 294     }
 295
 296     /// Given the `DefId` of an associated item, returns any region
 297     /// bounds attached to that associated item from the trait definition.
 298     ///
 299     /// For example:
 300     ///
 301     /// ```rust
 302     /// trait Foo<'a> {
 303     ///     type Bar: 'a;
 304     /// }
 305     /// ```
 306     ///
 307     /// If we were given the `DefId` of `Foo::Bar`, we would return
 308     /// `'a`. You could then apply the substitutions from the
 309     /// projection to convert this into your namespace. This also
 310     /// works if the user writes `where <Self as Foo<'a>>::Bar: 'a` on
 311     /// the trait. In fact, it works by searching for just such a
 312     /// where-clause.
 313     ///
 314     /// It will not, however, work for higher-ranked bounds like:
 315     ///
 316     /// ```rust
 317     /// trait Foo<'a, 'b>
 318     /// where for<'x> <Self as Foo<'x, 'b>>::Bar: 'x
 319     /// {
 320     ///     type Bar;
 321     /// }
 322     /// ```
 323     ///
 324     /// This is for simplicity, and because we are not really smart
 325     /// enough to cope with such bounds anywhere.
 326     fn region_bounds_declared_on_associated_item(
 327         &self,
 328         assoc_item_def_id: DefId,
 329     ) -> impl Iterator<Item = ty::Region<'tcx>> {
 330         let tcx = self.tcx;
 331         let bounds = tcx.item_bounds(assoc_item_def_id);
 332         bounds
 333             .into_iter()
 334             .filter_map(|p| p.to_opt_type_outlives())
 335             .filter_map(|p| p.no_bound_vars())
 336             .map(|b| b.1)
 337     }
 338
 339     /// Searches through a predicate list for a predicate `T: 'a`.
 340     ///
 341     /// Careful: does not elaborate predicates, and just uses `==`
 342     /// when comparing `ty` for equality, so `ty` must be something
 343     /// that does not involve inference variables and where you
 344     /// otherwise want a precise match.
 345     fn collect_outlives_from_predicate_list(
 346         &self,
 347         compare_ty: impl Fn(Ty<'tcx>) -> bool,
 348         predicates: impl Iterator<Item = ty::Predicate<'tcx>>,
 349     ) -> impl Iterator<Item = ty::OutlivesPredicate<Ty<'tcx>, ty::Region<'tcx>>> {
 350         predicates
 351             .filter_map(|p| p.to_opt_type_outlives())
 352             .filter_map(|p| p.no_bound_vars())
 353             .filter(move |p| compare_ty(p.0))
 354     }
 355 }