compiler/rustc_traits/src/implied_outlives_bounds.rs

   1 //! Provider for the `implied_outlives_bounds` query.
   2 //! Do not call this query directory. See
   3 //! [`rustc_trait_selection::traits::query::type_op::implied_outlives_bounds`].
   4
   5 use rustc_hir as hir;
   6 use rustc_infer::infer::canonical::{self, Canonical};
   7 use rustc_infer::infer::outlives::components::{push_outlives_components, Component};
   8 use rustc_infer::infer::TyCtxtInferExt;
   9 use rustc_infer::traits::query::OutlivesBound;
  10 use rustc_middle::ty::query::Providers;
  11 use rustc_middle::ty::{self, Ty, TyCtxt, TypeVisitable};
  12 use rustc_span::source_map::DUMMY_SP;
  13 use rustc_trait_selection::infer::InferCtxtBuilderExt;
  14 use rustc_trait_selection::traits::query::{CanonicalTyGoal, Fallible, NoSolution};
  15 use rustc_trait_selection::traits::wf;
  16 use rustc_trait_selection::traits::ObligationCtxt;
  17 use smallvec::{smallvec, SmallVec};
  18
  19 pub(crate) fn provide(p: &mut Providers) {
  20     *p = Providers { implied_outlives_bounds, ..*p };
  21 }
  22
  23 fn implied_outlives_bounds<'tcx>(
  24     tcx: TyCtxt<'tcx>,
  25     goal: CanonicalTyGoal<'tcx>,
  26 ) -> Result<
  27     &'tcx Canonical<'tcx, canonical::QueryResponse<'tcx, Vec<OutlivesBound<'tcx>>>>,
  28     NoSolution,
  29 > {
  30     tcx.infer_ctxt().enter_canonical_trait_query(&goal, |ocx, key| {
  31         let (param_env, ty) = key.into_parts();
  32         compute_implied_outlives_bounds(ocx, param_env, ty)
  33     })
  34 }
  35
  36 fn compute_implied_outlives_bounds<'tcx>(
  37     ocx: &ObligationCtxt<'_, 'tcx>,
  38     param_env: ty::ParamEnv<'tcx>,
  39     ty: Ty<'tcx>,
  40 ) -> Fallible<Vec<OutlivesBound<'tcx>>> {
  41     let tcx = ocx.infcx.tcx;
  42
  43     // Sometimes when we ask what it takes for T: WF, we get back that
  44     // U: WF is required; in that case, we push U onto this stack and
  45     // process it next. Because the resulting predicates aren't always
  46     // guaranteed to be a subset of the original type, so we need to store the
  47     // WF args we've computed in a set.
  48     let mut checked_wf_args = rustc_data_structures::fx::FxHashSet::default();
  49     let mut wf_args = vec![ty.into()];
  50
  51     let mut outlives_bounds: Vec<ty::OutlivesPredicate<ty::GenericArg<'tcx>, ty::Region<'tcx>>> =
  52         vec![];
  53
  54     while let Some(arg) = wf_args.pop() {
  55         if !checked_wf_args.insert(arg) {
  56             continue;
  57         }
  58
  59         // Compute the obligations for `arg` to be well-formed. If `arg` is
  60         // an unresolved inference variable, just substituted an empty set
  61         // -- because the return type here is going to be things we *add*
  62         // to the environment, it's always ok for this set to be smaller
  63         // than the ultimate set. (Note: normally there won't be
  64         // unresolved inference variables here anyway, but there might be
  65         // during typeck under some circumstances.)
  66         //
  67         // FIXME(@lcnr): It's not really "always fine", having fewer implied
  68         // bounds can be backward incompatible, e.g. #101951 was caused by
  69         // us not dealing with inference vars in `TypeOutlives` predicates.
  70         let obligations =
  71             wf::obligations(ocx.infcx, param_env, hir::CRATE_HIR_ID, 0, arg, DUMMY_SP)
  72                 .unwrap_or_default();
  73
  74         // While these predicates should all be implied by other parts of
  75         // the program, they are still relevant as they may constrain
  76         // inference variables, which is necessary to add the correct
  77         // implied bounds in some cases, mostly when dealing with projections.
  78         ocx.register_obligations(
  79             obligations.iter().filter(|o| o.predicate.has_non_region_infer()).cloned(),
  80         );
  81
  82         // From the full set of obligations, just filter down to the
  83         // region relationships.
  84         outlives_bounds.extend(obligations.into_iter().filter_map(|obligation| {
  85             assert!(!obligation.has_escaping_bound_vars());
  86             match obligation.predicate.kind().no_bound_vars() {
  87                 None => None,
  88                 Some(pred) => match pred {
  89                     ty::PredicateKind::Clause(ty::Clause::Trait(..))
  90                     | ty::PredicateKind::Subtype(..)
  91                     | ty::PredicateKind::Coerce(..)
  92                     | ty::PredicateKind::Clause(ty::Clause::Projection(..))
  93                     | ty::PredicateKind::ClosureKind(..)
  94                     | ty::PredicateKind::ObjectSafe(..)
  95                     | ty::PredicateKind::ConstEvaluatable(..)
  96                     | ty::PredicateKind::ConstEquate(..)
  97                     | ty::PredicateKind::Ambiguous
  98                     | ty::PredicateKind::TypeWellFormedFromEnv(..) => None,
  99                     ty::PredicateKind::WellFormed(arg) => {
 100                         wf_args.push(arg);
 101                         None
 102                     }
 103
 104                     ty::PredicateKind::Clause(ty::Clause::RegionOutlives(
 105                         ty::OutlivesPredicate(r_a, r_b),
 106                     )) => Some(ty::OutlivesPredicate(r_a.into(), r_b)),
 107
 108                     ty::PredicateKind::Clause(ty::Clause::TypeOutlives(ty::OutlivesPredicate(
 109                         ty_a,
 110                         r_b,
 111                     ))) => Some(ty::OutlivesPredicate(ty_a.into(), r_b)),
 112                 },
 113             }
 114         }));
 115     }
 116
 117     // This call to `select_all_or_error` is necessary to constrain inference variables, which we
 118     // use further down when computing the implied bounds.
 119     match ocx.select_all_or_error().as_slice() {
 120         [] => (),
 121         _ => return Err(NoSolution),
 122     }
 123
 124     // We lazily compute the outlives components as
 125     // `select_all_or_error` constrains inference variables.
 126     let implied_bounds = outlives_bounds
 127         .into_iter()
 128         .flat_map(|ty::OutlivesPredicate(a, r_b)| match a.unpack() {
 129             ty::GenericArgKind::Lifetime(r_a) => vec![OutlivesBound::RegionSubRegion(r_b, r_a)],
 130             ty::GenericArgKind::Type(ty_a) => {
 131                 let ty_a = ocx.infcx.resolve_vars_if_possible(ty_a);
 132                 let mut components = smallvec![];
 133                 push_outlives_components(tcx, ty_a, &mut components);
 134                 implied_bounds_from_components(r_b, components)
 135             }
 136             ty::GenericArgKind::Const(_) => unreachable!(),
 137         })
 138         .collect();
 139
 140     Ok(implied_bounds)
 141 }
 142
 143 /// When we have an implied bound that `T: 'a`, we can further break
 144 /// this down to determine what relationships would have to hold for
 145 /// `T: 'a` to hold. We get to assume that the caller has validated
 146 /// those relationships.
 147 fn implied_bounds_from_components<'tcx>(
 148     sub_region: ty::Region<'tcx>,
 149     sup_components: SmallVec<[Component<'tcx>; 4]>,
 150 ) -> Vec<OutlivesBound<'tcx>> {
 151     sup_components
 152         .into_iter()
 153         .filter_map(|component| {
 154             match component {
 155                 Component::Region(r) => Some(OutlivesBound::RegionSubRegion(sub_region, r)),
 156                 Component::Param(p) => Some(OutlivesBound::RegionSubParam(sub_region, p)),
 157                 Component::Projection(p) => Some(OutlivesBound::RegionSubProjection(sub_region, p)),
 158                 Component::Opaque(def_id, substs) => {
 159                     Some(OutlivesBound::RegionSubOpaque(sub_region, def_id, substs))
 160                 }
 161                 Component::EscapingProjection(_) =>
 162                 // If the projection has escaping regions, don't
 163                 // try to infer any implied bounds even for its
 164                 // free components. This is conservative, because
 165                 // the caller will still have to prove that those
 166                 // free components outlive `sub_region`. But the
 167                 // idea is that the WAY that the caller proves
 168                 // that may change in the future and we want to
 169                 // give ourselves room to get smarter here.
 170                 {
 171                     None
 172                 }
 173                 Component::UnresolvedInferenceVariable(..) => None,
 174             }
 175         })
 176         .collect()
 177 }