src/librustc_traits/implied_outlives_bounds.rs

   1 // Copyright 2018 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! Provider for the `implied_outlives_bounds` query.
  12 //! Do not call this query directory. See [`rustc::traits::query::implied_outlives_bounds`].
  13
  14 use rustc::infer::InferCtxt;
  15 use rustc::infer::canonical::{self, Canonical};
  16 use rustc::traits::{TraitEngine, TraitEngineExt};
  17 use rustc::traits::query::outlives_bounds::OutlivesBound;
  18 use rustc::traits::query::{CanonicalTyGoal, Fallible, NoSolution};
  19 use rustc::ty::{self, Ty, TyCtxt, TypeFoldable};
  20 use rustc::ty::outlives::Component;
  21 use rustc::ty::query::Providers;
  22 use rustc::ty::wf;
  23 use smallvec::{SmallVec, smallvec};
  24 use syntax::ast::DUMMY_NODE_ID;
  25 use syntax::source_map::DUMMY_SP;
  26 use rustc::traits::FulfillmentContext;
  27
  28 use rustc_data_structures::sync::Lrc;
  29
  30 crate fn provide(p: &mut Providers) {
  31     *p = Providers {
  32         implied_outlives_bounds,
  33         ..*p
  34     };
  35 }
  36
  37 fn implied_outlives_bounds<'tcx>(
  38     tcx: TyCtxt<'_, 'tcx, 'tcx>,
  39     goal: CanonicalTyGoal<'tcx>,
  40 ) -> Result<
  41         Lrc<Canonical<'tcx, canonical::QueryResponse<'tcx, Vec<OutlivesBound<'tcx>>>>>,
  42         NoSolution,
  43 > {
  44     tcx.infer_ctxt()
  45        .enter_canonical_trait_query(&goal, |infcx, _fulfill_cx, key| {
  46            let (param_env, ty) = key.into_parts();
  47            compute_implied_outlives_bounds(&infcx, param_env, ty)
  48        })
  49 }
  50
  51 fn compute_implied_outlives_bounds<'tcx>(
  52     infcx: &InferCtxt<'_, '_, 'tcx>,
  53     param_env: ty::ParamEnv<'tcx>,
  54     ty: Ty<'tcx>
  55 ) -> Fallible<Vec<OutlivesBound<'tcx>>> {
  56     let tcx = infcx.tcx;
  57
  58     // Sometimes when we ask what it takes for T: WF, we get back that
  59     // U: WF is required; in that case, we push U onto this stack and
  60     // process it next. Currently (at least) these resulting
  61     // predicates are always guaranteed to be a subset of the original
  62     // type, so we need not fear non-termination.
  63     let mut wf_types = vec![ty];
  64
  65     let mut implied_bounds = vec![];
  66
  67     let mut fulfill_cx = FulfillmentContext::new();
  68
  69     while let Some(ty) = wf_types.pop() {
  70         // Compute the obligations for `ty` to be well-formed. If `ty` is
  71         // an unresolved inference variable, just substituted an empty set
  72         // -- because the return type here is going to be things we *add*
  73         // to the environment, it's always ok for this set to be smaller
  74         // than the ultimate set. (Note: normally there won't be
  75         // unresolved inference variables here anyway, but there might be
  76         // during typeck under some circumstances.)
  77         let obligations =
  78             wf::obligations(infcx, param_env, DUMMY_NODE_ID, ty, DUMMY_SP).unwrap_or(vec![]);
  79
  80         // NB: All of these predicates *ought* to be easily proven
  81         // true. In fact, their correctness is (mostly) implied by
  82         // other parts of the program. However, in #42552, we had
  83         // an annoying scenario where:
  84         //
  85         // - Some `T::Foo` gets normalized, resulting in a
  86         //   variable `_1` and a `T: Trait<Foo=_1>` constraint
  87         //   (not sure why it couldn't immediately get
  88         //   solved). This result of `_1` got cached.
  89         // - These obligations were dropped on the floor here,
  90         //   rather than being registered.
  91         // - Then later we would get a request to normalize
  92         //   `T::Foo` which would result in `_1` being used from
  93         //   the cache, but hence without the `T: Trait<Foo=_1>`
  94         //   constraint. As a result, `_1` never gets resolved,
  95         //   and we get an ICE (in dropck).
  96         //
  97         // Therefore, we register any predicates involving
  98         // inference variables. We restrict ourselves to those
  99         // involving inference variables both for efficiency and
 100         // to avoids duplicate errors that otherwise show up.
 101         fulfill_cx.register_predicate_obligations(
 102             infcx,
 103             obligations
 104                 .iter()
 105                 .filter(|o| o.predicate.has_infer_types())
 106                 .cloned(),
 107         );
 108
 109         // From the full set of obligations, just filter down to the
 110         // region relationships.
 111         implied_bounds.extend(obligations.into_iter().flat_map(|obligation| {
 112             assert!(!obligation.has_escaping_bound_vars());
 113             match obligation.predicate {
 114                 ty::Predicate::Trait(..) |
 115                 ty::Predicate::Subtype(..) |
 116                 ty::Predicate::Projection(..) |
 117                 ty::Predicate::ClosureKind(..) |
 118                 ty::Predicate::ObjectSafe(..) |
 119                 ty::Predicate::ConstEvaluatable(..) => vec![],
 120
 121                 ty::Predicate::WellFormed(subty) => {
 122                     wf_types.push(subty);
 123                     vec![]
 124                 }
 125
 126                 ty::Predicate::RegionOutlives(ref data) => match data.no_bound_vars() {
 127                     None => vec![],
 128                     Some(ty::OutlivesPredicate(r_a, r_b)) => {
 129                         vec![OutlivesBound::RegionSubRegion(r_b, r_a)]
 130                     }
 131                 },
 132
 133                 ty::Predicate::TypeOutlives(ref data) => match data.no_bound_vars() {
 134                     None => vec![],
 135                     Some(ty::OutlivesPredicate(ty_a, r_b)) => {
 136                         let ty_a = infcx.resolve_type_vars_if_possible(&ty_a);
 137                         let mut components = smallvec![];
 138                         tcx.push_outlives_components(ty_a, &mut components);
 139                         implied_bounds_from_components(r_b, components)
 140                     }
 141                 },
 142             }
 143         }));
 144     }
 145
 146     // Ensure that those obligations that we had to solve
 147     // get solved *here*.
 148     match fulfill_cx.select_all_or_error(infcx) {
 149         Ok(()) => Ok(implied_bounds),
 150         Err(_) => Err(NoSolution),
 151     }
 152 }
 153
 154 /// When we have an implied bound that `T: 'a`, we can further break
 155 /// this down to determine what relationships would have to hold for
 156 /// `T: 'a` to hold. We get to assume that the caller has validated
 157 /// those relationships.
 158 fn implied_bounds_from_components(
 159     sub_region: ty::Region<'tcx>,
 160     sup_components: SmallVec<[Component<'tcx>; 4]>,
 161 ) -> Vec<OutlivesBound<'tcx>> {
 162     sup_components
 163         .into_iter()
 164         .filter_map(|component| {
 165             match component {
 166                 Component::Region(r) =>
 167                     Some(OutlivesBound::RegionSubRegion(sub_region, r)),
 168                 Component::Param(p) =>
 169                     Some(OutlivesBound::RegionSubParam(sub_region, p)),
 170                 Component::Projection(p) =>
 171                     Some(OutlivesBound::RegionSubProjection(sub_region, p)),
 172                 Component::EscapingProjection(_) =>
 173                 // If the projection has escaping regions, don't
 174                 // try to infer any implied bounds even for its
 175                 // free components. This is conservative, because
 176                 // the caller will still have to prove that those
 177                 // free components outlive `sub_region`. But the
 178                 // idea is that the WAY that the caller proves
 179                 // that may change in the future and we want to
 180                 // give ourselves room to get smarter here.
 181                     None,
 182                 Component::UnresolvedInferenceVariable(..) =>
 183                     None,
 184             }
 185         })
 186         .collect()
 187 }