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