src/librustc/infer/outlives/verify.rs

   1 use crate::hir::def_id::DefId;
   2 use crate::infer::outlives::env::RegionBoundPairs;
   3 use crate::infer::{GenericKind, VerifyBound};
   4 use crate::traits;
   5 use crate::ty::subst::{Subst, InternalSubsts};
   6 use crate::ty::{self, Ty, TyCtxt};
   7 use crate::util::captures::Captures;
   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 {
  30             tcx,
  31             region_bound_pairs,
  32             implicit_region_bound,
  33             param_env,
  34         }
  35     }
  36
  37     /// Returns a "verify bound" that encodes what we know about
  38     /// `generic` and the regions it outlives.
  39     pub fn generic_bound(&self, generic: GenericKind<'tcx>) -> VerifyBound<'tcx> {
  40         match generic {
  41             GenericKind::Param(param_ty) => self.param_bound(param_ty),
  42             GenericKind::Projection(projection_ty) => self.projection_bound(projection_ty),
  43         }
  44     }
  45
  46     fn type_bound(&self, ty: Ty<'tcx>) -> VerifyBound<'tcx> {
  47         match ty.kind {
  48             ty::Param(p) => self.param_bound(p),
  49             ty::Projection(data) => self.projection_bound(data),
  50             _ => self.recursive_type_bound(ty),
  51         }
  52     }
  53
  54     fn param_bound(&self, param_ty: ty::ParamTy) -> VerifyBound<'tcx> {
  55         debug!("param_bound(param_ty={:?})", param_ty);
  56
  57         // Start with anything like `T: 'a` we can scrape from the
  58         // environment
  59         let param_bounds = self.declared_generic_bounds_from_env(GenericKind::Param(param_ty))
  60             .into_iter()
  61             .map(|outlives| outlives.1);
  62
  63         // Add in the default bound of fn body that applies to all in
  64         // scope type parameters:
  65         let param_bounds = param_bounds.chain(self.implicit_region_bound);
  66
  67         VerifyBound::AnyBound(param_bounds.map(|r| VerifyBound::OutlivedBy(r)).collect())
  68     }
  69
  70     /// Given a projection like `T::Item`, searches the environment
  71     /// for where-clauses like `T::Item: 'a`. Returns the set of
  72     /// regions `'a` that it finds.
  73     ///
  74     /// This is an "approximate" check -- it may not find all
  75     /// applicable bounds, and not all the bounds it returns can be
  76     /// relied upon. In particular, this check ignores region
  77     /// identity. So, for example, if we have `<T as
  78     /// Trait<'0>>::Item` where `'0` is a region variable, and the
  79     /// user has `<T as Trait<'a>>::Item: 'b` in the environment, then
  80     /// the clause from the environment only applies if `'0 = 'a`,
  81     /// which we don't know yet. But we would still include `'b` in
  82     /// this list.
  83     pub fn projection_approx_declared_bounds_from_env(
  84         &self,
  85         projection_ty: ty::ProjectionTy<'tcx>,
  86     ) -> Vec<ty::OutlivesPredicate<Ty<'tcx>, ty::Region<'tcx>>> {
  87         let projection_ty = GenericKind::Projection(projection_ty).to_ty(self.tcx);
  88         let erased_projection_ty = self.tcx.erase_regions(&projection_ty);
  89         self.declared_generic_bounds_from_env_with_compare_fn(|ty| {
  90             if let ty::Projection(..) = ty.kind {
  91                 let erased_ty = self.tcx.erase_regions(&ty);
  92                 erased_ty == erased_projection_ty
  93             } else {
  94                 false
  95             }
  96         })
  97     }
  98
  99     /// Searches the where-clauses in scope for regions that
 100     /// `projection_ty` is known to outlive. Currently requires an
 101     /// exact match.
 102     pub fn projection_declared_bounds_from_trait(
 103         &self,
 104         projection_ty: ty::ProjectionTy<'tcx>,
 105     ) -> impl Iterator<Item = ty::Region<'tcx>> + 'cx + Captures<'tcx> {
 106         self.declared_projection_bounds_from_trait(projection_ty)
 107     }
 108
 109     pub fn projection_bound(&self, projection_ty: ty::ProjectionTy<'tcx>) -> VerifyBound<'tcx> {
 110         debug!("projection_bound(projection_ty={:?})", projection_ty);
 111
 112         let projection_ty_as_ty =
 113             self.tcx.mk_projection(projection_ty.item_def_id, projection_ty.substs);
 114
 115         // Search the env for where clauses like `P: 'a`.
 116         let env_bounds = self.projection_approx_declared_bounds_from_env(projection_ty)
 117             .into_iter()
 118             .map(|ty::OutlivesPredicate(ty, r)| {
 119                 let vb = VerifyBound::OutlivedBy(r);
 120                 if ty == projection_ty_as_ty {
 121                     // Micro-optimize if this is an exact match (this
 122                     // occurs often when there are no region variables
 123                     // involved).
 124                     vb
 125                 } else {
 126                     VerifyBound::IfEq(ty, Box::new(vb))
 127                 }
 128             });
 129
 130         // Extend with bounds that we can find from the trait.
 131         let trait_bounds = self.projection_declared_bounds_from_trait(projection_ty)
 132             .into_iter()
 133             .map(|r| VerifyBound::OutlivedBy(r));
 134
 135         // see the extensive comment in projection_must_outlive
 136         let ty = self.tcx
 137             .mk_projection(projection_ty.item_def_id, projection_ty.substs);
 138         let recursive_bound = self.recursive_type_bound(ty);
 139
 140         VerifyBound::AnyBound(env_bounds.chain(trait_bounds).collect()).or(recursive_bound)
 141     }
 142
 143     fn recursive_type_bound(&self, ty: Ty<'tcx>) -> VerifyBound<'tcx> {
 144         let mut bounds = ty.walk_shallow()
 145             .map(|subty| self.type_bound(subty))
 146             .collect::<Vec<_>>();
 147
 148         let mut regions = smallvec![];
 149         ty.push_regions(&mut regions);
 150         regions.retain(|r| !r.is_late_bound()); // ignore late-bound regions
 151         bounds.push(VerifyBound::AllBounds(
 152             regions
 153                 .into_iter()
 154                 .map(|r| VerifyBound::OutlivedBy(r))
 155                 .collect(),
 156         ));
 157
 158         // remove bounds that must hold, since they are not interesting
 159         bounds.retain(|b| !b.must_hold());
 160
 161         if bounds.len() == 1 {
 162             bounds.pop().unwrap()
 163         } else {
 164             VerifyBound::AllBounds(bounds)
 165         }
 166     }
 167
 168     /// Searches the environment for where-clauses like `G: 'a` where
 169     /// `G` is either some type parameter `T` or a projection like
 170     /// `T::Item`. Returns a vector of the `'a` bounds it can find.
 171     ///
 172     /// This is a conservative check -- it may not find all applicable
 173     /// bounds, but all the bounds it returns can be relied upon.
 174     fn declared_generic_bounds_from_env(
 175         &self,
 176         generic: GenericKind<'tcx>,
 177     ) -> Vec<ty::OutlivesPredicate<Ty<'tcx>, ty::Region<'tcx>>> {
 178         let generic_ty = generic.to_ty(self.tcx);
 179         self.declared_generic_bounds_from_env_with_compare_fn(|ty| ty == generic_ty)
 180     }
 181
 182     fn declared_generic_bounds_from_env_with_compare_fn(
 183         &self,
 184         compare_ty: impl Fn(Ty<'tcx>) -> bool,
 185     ) -> Vec<ty::OutlivesPredicate<Ty<'tcx>, ty::Region<'tcx>>> {
 186         let tcx = self.tcx;
 187
 188         // To start, collect bounds from user environment. Note that
 189         // parameter environments are already elaborated, so we don't
 190         // have to worry about that. Comparing using `==` is a bit
 191         // dubious for projections, but it will work for simple cases
 192         // like `T` and `T::Item`. It may not work as well for things
 193         // like `<T as Foo<'a>>::Item`.
 194         let c_b = self.param_env.caller_bounds;
 195         let param_bounds = self.collect_outlives_from_predicate_list(&compare_ty, c_b);
 196
 197         // Next, collect regions we scraped from the well-formedness
 198         // constraints in the fn signature. To do that, we walk the list
 199         // of known relations from the fn ctxt.
 200         //
 201         // This is crucial because otherwise code like this fails:
 202         //
 203         //     fn foo<'a, A>(x: &'a A) { x.bar() }
 204         //
 205         // The problem is that the type of `x` is `&'a A`. To be
 206         // well-formed, then, A must be lower-generic by `'a`, but we
 207         // don't know that this holds from first principles.
 208         let from_region_bound_pairs = self.region_bound_pairs.iter().filter_map(|&(r, p)| {
 209             debug!(
 210                 "declared_generic_bounds_from_env_with_compare_fn: region_bound_pair = {:?}",
 211                 (r, p)
 212             );
 213             let p_ty = p.to_ty(tcx);
 214             if compare_ty(p_ty) {
 215                 Some(ty::OutlivesPredicate(p_ty, r))
 216             } else {
 217                 None
 218             }
 219         });
 220
 221         param_bounds
 222             .chain(from_region_bound_pairs)
 223             .inspect(|bound| {
 224                 debug!(
 225                     "declared_generic_bounds_from_env_with_compare_fn: result predicate = {:?}",
 226                     bound
 227                 )
 228             })
 229             .collect()
 230     }
 231
 232     /// Given a projection like `<T as Foo<'x>>::Bar`, returns any bounds
 233     /// declared in the trait definition. For example, if the trait were
 234     ///
 235     /// ```rust
 236     /// trait Foo<'a> {
 237     ///     type Bar: 'a;
 238     /// }
 239     /// ```
 240     ///
 241     /// then this function would return `'x`. This is subject to the
 242     /// limitations around higher-ranked bounds described in
 243     /// `region_bounds_declared_on_associated_item`.
 244     fn declared_projection_bounds_from_trait(
 245         &self,
 246         projection_ty: ty::ProjectionTy<'tcx>,
 247     ) -> impl Iterator<Item = ty::Region<'tcx>> + 'cx + Captures<'tcx> {
 248         debug!("projection_bounds(projection_ty={:?})", projection_ty);
 249         let tcx = self.tcx;
 250         self.region_bounds_declared_on_associated_item(projection_ty.item_def_id)
 251             .map(move |r| r.subst(tcx, projection_ty.substs))
 252     }
 253
 254     /// Given the `DefId` of an associated item, returns any region
 255     /// bounds attached to that associated item from the trait definition.
 256     ///
 257     /// For example:
 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     /// ```rust
 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     fn region_bounds_declared_on_associated_item(
 285         &self,
 286         assoc_item_def_id: DefId,
 287     ) -> impl Iterator<Item = ty::Region<'tcx>> + 'cx + Captures<'tcx> {
 288         let tcx = self.tcx;
 289         let assoc_item = tcx.associated_item(assoc_item_def_id);
 290         let trait_def_id = assoc_item.container.assert_trait();
 291         let trait_predicates = tcx.predicates_of(trait_def_id).predicates
 292             .iter()
 293             .map(|(p, _)| *p)
 294             .collect();
 295         let identity_substs = InternalSubsts::identity_for_item(tcx, assoc_item_def_id);
 296         let identity_proj = tcx.mk_projection(assoc_item_def_id, identity_substs);
 297         self.collect_outlives_from_predicate_list(
 298             move |ty| ty == identity_proj,
 299             traits::elaborate_predicates(tcx, trait_predicates),
 300         ).map(|b| b.1)
 301     }
 302
 303     /// Searches through a predicate list for a predicate `T: 'a`.
 304     ///
 305     /// Careful: does not elaborate predicates, and just uses `==`
 306     /// when comparing `ty` for equality, so `ty` must be something
 307     /// that does not involve inference variables and where you
 308     /// otherwise want a precise match.
 309     fn collect_outlives_from_predicate_list(
 310         &self,
 311         compare_ty: impl Fn(Ty<'tcx>) -> bool,
 312         predicates: impl IntoIterator<Item = impl AsRef<ty::Predicate<'tcx>>>,
 313     ) -> impl Iterator<Item = ty::OutlivesPredicate<Ty<'tcx>, ty::Region<'tcx>>> {
 314         predicates
 315             .into_iter()
 316             .filter_map(|p| p.as_ref().to_opt_type_outlives())
 317             .filter_map(|p| p.no_bound_vars())
 318             .filter(move |p| compare_ty(p.0))
 319     }
 320 }