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