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