src/librustc_traits/implied_outlives_bounds.rs

   1 //! Provider for the `implied_outlives_bounds` query.
   2 //! Do not call this query directory. See [`rustc::traits::query::implied_outlives_bounds`].
   3
   4 use rustc::hir;
   5 use rustc::infer::InferCtxt;
   6 use rustc::infer::canonical::{self, Canonical};
   7 use rustc::traits::{TraitEngine, TraitEngineExt};
   8 use rustc::traits::query::outlives_bounds::OutlivesBound;
   9 use rustc::traits::query::{CanonicalTyGoal, Fallible, NoSolution};
  10 use rustc::ty::{self, Ty, TyCtxt, TypeFoldable};
  11 use rustc::ty::outlives::Component;
  12 use rustc::ty::query::Providers;
  13 use rustc::ty::wf;
  14 use smallvec::{SmallVec, smallvec};
  15 use syntax::source_map::DUMMY_SP;
  16 use rustc::traits::FulfillmentContext;
  17
  18 use rustc_data_structures::sync::Lrc;
  19
  20 crate fn provide(p: &mut Providers<'_>) {
  21     *p = Providers {
  22         implied_outlives_bounds,
  23         ..*p
  24     };
  25 }
  26
  27 fn implied_outlives_bounds<'tcx>(
  28     tcx: TyCtxt<'_, 'tcx, 'tcx>,
  29     goal: CanonicalTyGoal<'tcx>,
  30 ) -> Result<
  31         Lrc<Canonical<'tcx, canonical::QueryResponse<'tcx, Vec<OutlivesBound<'tcx>>>>>,
  32         NoSolution,
  33 > {
  34     tcx.infer_ctxt()
  35        .enter_canonical_trait_query(&goal, |infcx, _fulfill_cx, key| {
  36            let (param_env, ty) = key.into_parts();
  37            compute_implied_outlives_bounds(&infcx, param_env, ty)
  38        })
  39 }
  40
  41 fn compute_implied_outlives_bounds<'tcx>(
  42     infcx: &InferCtxt<'_, '_, 'tcx>,
  43     param_env: ty::ParamEnv<'tcx>,
  44     ty: Ty<'tcx>
  45 ) -> Fallible<Vec<OutlivesBound<'tcx>>> {
  46     let tcx = infcx.tcx;
  47
  48     // Sometimes when we ask what it takes for T: WF, we get back that
  49     // U: WF is required; in that case, we push U onto this stack and
  50     // process it next. Currently (at least) these resulting
  51     // predicates are always guaranteed to be a subset of the original
  52     // type, so we need not fear non-termination.
  53     let mut wf_types = vec![ty];
  54
  55     let mut implied_bounds = vec![];
  56
  57     let mut fulfill_cx = FulfillmentContext::new();
  58
  59     while let Some(ty) = wf_types.pop() {
  60         // Compute the obligations for `ty` to be well-formed. If `ty` is
  61         // an unresolved inference variable, just substituted an empty set
  62         // -- because the return type here is going to be things we *add*
  63         // to the environment, it's always ok for this set to be smaller
  64         // than the ultimate set. (Note: normally there won't be
  65         // unresolved inference variables here anyway, but there might be
  66         // during typeck under some circumstances.)
  67         let obligations =
  68             wf::obligations(infcx, param_env, hir::DUMMY_HIR_ID, ty, DUMMY_SP).unwrap_or(vec![]);
  69
  70         // N.B., all of these predicates *ought* to be easily proven
  71         // true. In fact, their correctness is (mostly) implied by
  72         // other parts of the program. However, in #42552, we had
  73         // an annoying scenario where:
  74         //
  75         // - Some `T::Foo` gets normalized, resulting in a
  76         //   variable `_1` and a `T: Trait<Foo=_1>` constraint
  77         //   (not sure why it couldn't immediately get
  78         //   solved). This result of `_1` got cached.
  79         // - These obligations were dropped on the floor here,
  80         //   rather than being registered.
  81         // - Then later we would get a request to normalize
  82         //   `T::Foo` which would result in `_1` being used from
  83         //   the cache, but hence without the `T: Trait<Foo=_1>`
  84         //   constraint. As a result, `_1` never gets resolved,
  85         //   and we get an ICE (in dropck).
  86         //
  87         // Therefore, we register any predicates involving
  88         // inference variables. We restrict ourselves to those
  89         // involving inference variables both for efficiency and
  90         // to avoids duplicate errors that otherwise show up.
  91         fulfill_cx.register_predicate_obligations(
  92             infcx,
  93             obligations
  94                 .iter()
  95                 .filter(|o| o.predicate.has_infer_types())
  96                 .cloned(),
  97         );
  98
  99         // From the full set of obligations, just filter down to the
 100         // region relationships.
 101         implied_bounds.extend(obligations.into_iter().flat_map(|obligation| {
 102             assert!(!obligation.has_escaping_bound_vars());
 103             match obligation.predicate {
 104                 ty::Predicate::Trait(..) |
 105                 ty::Predicate::Subtype(..) |
 106                 ty::Predicate::Projection(..) |
 107                 ty::Predicate::ClosureKind(..) |
 108                 ty::Predicate::ObjectSafe(..) |
 109                 ty::Predicate::ConstEvaluatable(..) => vec![],
 110
 111                 ty::Predicate::WellFormed(subty) => {
 112                     wf_types.push(subty);
 113                     vec![]
 114                 }
 115
 116                 ty::Predicate::RegionOutlives(ref data) => match data.no_bound_vars() {
 117                     None => vec![],
 118                     Some(ty::OutlivesPredicate(r_a, r_b)) => {
 119                         vec![OutlivesBound::RegionSubRegion(r_b, r_a)]
 120                     }
 121                 },
 122
 123                 ty::Predicate::TypeOutlives(ref data) => match data.no_bound_vars() {
 124                     None => vec![],
 125                     Some(ty::OutlivesPredicate(ty_a, r_b)) => {
 126                         let ty_a = infcx.resolve_type_vars_if_possible(&ty_a);
 127                         let mut components = smallvec![];
 128                         tcx.push_outlives_components(ty_a, &mut components);
 129                         implied_bounds_from_components(r_b, components)
 130                     }
 131                 },
 132             }
 133         }));
 134     }
 135
 136     // Ensure that those obligations that we had to solve
 137     // get solved *here*.
 138     match fulfill_cx.select_all_or_error(infcx) {
 139         Ok(()) => Ok(implied_bounds),
 140         Err(_) => Err(NoSolution),
 141     }
 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(
 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) =>
 157                     Some(OutlivesBound::RegionSubRegion(sub_region, r)),
 158                 Component::Param(p) =>
 159                     Some(OutlivesBound::RegionSubParam(sub_region, p)),
 160                 Component::Projection(p) =>
 161                     Some(OutlivesBound::RegionSubProjection(sub_region, p)),
 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                     None,
 172                 Component::UnresolvedInferenceVariable(..) =>
 173                     None,
 174             }
 175         })
 176         .collect()
 177 }