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 implied_bounds = vec![];
  53
  54     let mut fulfill_cx = <dyn TraitEngine<'tcx>>::new(tcx);
  55
  56     while let Some(arg) = wf_args.pop() {
  57         if !checked_wf_args.insert(arg) {
  58             continue;
  59         }
  60
  61         // Compute the obligations for `arg` to be well-formed. If `arg` is
  62         // an unresolved inference variable, just substituted an empty set
  63         // -- because the return type here is going to be things we *add*
  64         // to the environment, it's always ok for this set to be smaller
  65         // than the ultimate set. (Note: normally there won't be
  66         // unresolved inference variables here anyway, but there might be
  67         // during typeck under some circumstances.)
  68         let obligations = wf::obligations(infcx, param_env, hir::CRATE_HIR_ID, 0, arg, DUMMY_SP)
  69             .unwrap_or_default();
  70
  71         // N.B., all of these predicates *ought* to be easily proven
  72         // true. In fact, their correctness is (mostly) implied by
  73         // other parts of the program. However, in #42552, we had
  74         // an annoying scenario where:
  75         //
  76         // - Some `T::Foo` gets normalized, resulting in a
  77         //   variable `_1` and a `T: Trait<Foo=_1>` constraint
  78         //   (not sure why it couldn't immediately get
  79         //   solved). This result of `_1` got cached.
  80         // - These obligations were dropped on the floor here,
  81         //   rather than being registered.
  82         // - Then later we would get a request to normalize
  83         //   `T::Foo` which would result in `_1` being used from
  84         //   the cache, but hence without the `T: Trait<Foo=_1>`
  85         //   constraint. As a result, `_1` never gets resolved,
  86         //   and we get an ICE (in dropck).
  87         //
  88         // Therefore, we register any predicates involving
  89         // inference variables. We restrict ourselves to those
  90         // involving inference variables both for efficiency and
  91         // to avoids duplicate errors that otherwise show up.
  92         fulfill_cx.register_predicate_obligations(
  93             infcx,
  94             obligations.iter().filter(|o| o.predicate.has_infer_types_or_consts()).cloned(),
  95         );
  96
  97         // From the full set of obligations, just filter down to the
  98         // region relationships.
  99         implied_bounds.extend(obligations.into_iter().flat_map(|obligation| {
 100             assert!(!obligation.has_escaping_bound_vars());
 101             match obligation.predicate.kind().no_bound_vars() {
 102                 None => vec![],
 103                 Some(pred) => match pred {
 104                     ty::PredicateKind::Trait(..)
 105                     | ty::PredicateKind::Subtype(..)
 106                     | ty::PredicateKind::Coerce(..)
 107                     | ty::PredicateKind::Projection(..)
 108                     | ty::PredicateKind::ClosureKind(..)
 109                     | ty::PredicateKind::ObjectSafe(..)
 110                     | ty::PredicateKind::ConstEvaluatable(..)
 111                     | ty::PredicateKind::ConstEquate(..)
 112                     | ty::PredicateKind::TypeWellFormedFromEnv(..) => vec![],
 113                     ty::PredicateKind::WellFormed(arg) => {
 114                         wf_args.push(arg);
 115                         vec![]
 116                     }
 117
 118                     ty::PredicateKind::RegionOutlives(ty::OutlivesPredicate(r_a, r_b)) => {
 119                         vec![OutlivesBound::RegionSubRegion(r_b, r_a)]
 120                     }
 121
 122                     ty::PredicateKind::TypeOutlives(ty::OutlivesPredicate(ty_a, r_b)) => {
 123                         let ty_a = infcx.resolve_vars_if_possible(ty_a);
 124                         let mut components = smallvec![];
 125                         push_outlives_components(tcx, ty_a, &mut components);
 126                         implied_bounds_from_components(r_b, components)
 127                     }
 128                 },
 129             }
 130         }));
 131     }
 132
 133     // Ensure that those obligations that we had to solve
 134     // get solved *here*.
 135     match fulfill_cx.select_all_or_error(infcx).as_slice() {
 136         [] => Ok(implied_bounds),
 137         _ => Err(NoSolution),
 138     }
 139 }
 140
 141 /// When we have an implied bound that `T: 'a`, we can further break
 142 /// this down to determine what relationships would have to hold for
 143 /// `T: 'a` to hold. We get to assume that the caller has validated
 144 /// those relationships.
 145 fn implied_bounds_from_components<'tcx>(
 146     sub_region: ty::Region<'tcx>,
 147     sup_components: SmallVec<[Component<'tcx>; 4]>,
 148 ) -> Vec<OutlivesBound<'tcx>> {
 149     sup_components
 150         .into_iter()
 151         .filter_map(|component| {
 152             match component {
 153                 Component::Region(r) => Some(OutlivesBound::RegionSubRegion(sub_region, r)),
 154                 Component::Param(p) => Some(OutlivesBound::RegionSubParam(sub_region, p)),
 155                 Component::Projection(p) => Some(OutlivesBound::RegionSubProjection(sub_region, p)),
 156                 Component::EscapingProjection(_) =>
 157                 // If the projection has escaping regions, don't
 158                 // try to infer any implied bounds even for its
 159                 // free components. This is conservative, because
 160                 // the caller will still have to prove that those
 161                 // free components outlive `sub_region`. But the
 162                 // idea is that the WAY that the caller proves
 163                 // that may change in the future and we want to
 164                 // give ourselves room to get smarter here.
 165                 {
 166                     None
 167                 }
 168                 Component::UnresolvedInferenceVariable(..) => None,
 169             }
 170         })
 171         .collect()
 172 }