src/librustc/infer/outlives/bounds.rs

   1 // Copyright 2012-2014 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 use infer::InferCtxt;
  12 use syntax::ast;
  13 use syntax::codemap::Span;
  14 use traits::FulfillmentContext;
  15 use ty::{self, Ty, TypeFoldable};
  16 use ty::outlives::Component;
  17 use ty::wf;
  18
  19 /// Outlives bounds are relationships between generic parameters,
  20 /// whether they both be regions (`'a: 'b`) or whether types are
  21 /// involved (`T: 'a`).  These relationships can be extracted from the
  22 /// full set of predicates we understand or also from types (in which
  23 /// case they are called implied bounds). They are fed to the
  24 /// `OutlivesEnv` which in turn is supplied to the region checker and
  25 /// other parts of the inference system.
  26 #[derive(Debug)]
  27 pub enum OutlivesBound<'tcx> {
  28     RegionSubRegion(ty::Region<'tcx>, ty::Region<'tcx>),
  29     RegionSubParam(ty::Region<'tcx>, ty::ParamTy),
  30     RegionSubProjection(ty::Region<'tcx>, ty::ProjectionTy<'tcx>),
  31 }
  32
  33 impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
  34     /// Implied bounds are region relationships that we deduce
  35     /// automatically.  The idea is that (e.g.) a caller must check that a
  36     /// function's argument types are well-formed immediately before
  37     /// calling that fn, and hence the *callee* can assume that its
  38     /// argument types are well-formed. This may imply certain relationships
  39     /// between generic parameters. For example:
  40     ///
  41     ///     fn foo<'a,T>(x: &'a T)
  42     ///
  43     /// can only be called with a `'a` and `T` such that `&'a T` is WF.
  44     /// For `&'a T` to be WF, `T: 'a` must hold. So we can assume `T: 'a`.
  45     ///
  46     /// # Parameters
  47     ///
  48     /// - `param_env`, the where-clauses in scope
  49     /// - `body_id`, the body-id to use when normalizing assoc types.
  50     ///   Note that this may cause outlives obligations to be injected
  51     ///   into the inference context with this body-id.
  52     /// - `ty`, the type that we are supposed to assume is WF.
  53     /// - `span`, a span to use when normalizing, hopefully not important,
  54     ///   might be useful if a `bug!` occurs.
  55     pub fn implied_outlives_bounds(
  56         &self,
  57         param_env: ty::ParamEnv<'tcx>,
  58         body_id: ast::NodeId,
  59         ty: Ty<'tcx>,
  60         span: Span,
  61     ) -> Vec<OutlivesBound<'tcx>> {
  62         let tcx = self.tcx;
  63
  64         // Sometimes when we ask what it takes for T: WF, we get back that
  65         // U: WF is required; in that case, we push U onto this stack and
  66         // process it next. Currently (at least) these resulting
  67         // predicates are always guaranteed to be a subset of the original
  68         // type, so we need not fear non-termination.
  69         let mut wf_types = vec![ty];
  70
  71         let mut implied_bounds = vec![];
  72
  73         let mut fulfill_cx = FulfillmentContext::new();
  74
  75         while let Some(ty) = wf_types.pop() {
  76             // Compute the obligations for `ty` to be well-formed. If `ty` is
  77             // an unresolved inference variable, just substituted an empty set
  78             // -- because the return type here is going to be things we *add*
  79             // to the environment, it's always ok for this set to be smaller
  80             // than the ultimate set. (Note: normally there won't be
  81             // unresolved inference variables here anyway, but there might be
  82             // during typeck under some circumstances.)
  83             let obligations = wf::obligations(self, param_env, body_id, ty, span).unwrap_or(vec![]);
  84
  85             // NB: All of these predicates *ought* to be easily proven
  86             // true. In fact, their correctness is (mostly) implied by
  87             // other parts of the program. However, in #42552, we had
  88             // an annoying scenario where:
  89             //
  90             // - Some `T::Foo` gets normalized, resulting in a
  91             //   variable `_1` and a `T: Trait<Foo=_1>` constraint
  92             //   (not sure why it couldn't immediately get
  93             //   solved). This result of `_1` got cached.
  94             // - These obligations were dropped on the floor here,
  95             //   rather than being registered.
  96             // - Then later we would get a request to normalize
  97             //   `T::Foo` which would result in `_1` being used from
  98             //   the cache, but hence without the `T: Trait<Foo=_1>`
  99             //   constraint. As a result, `_1` never gets resolved,
 100             //   and we get an ICE (in dropck).
 101             //
 102             // Therefore, we register any predicates involving
 103             // inference variables. We restrict ourselves to those
 104             // involving inference variables both for efficiency and
 105             // to avoids duplicate errors that otherwise show up.
 106             fulfill_cx.register_predicate_obligations(
 107                 self,
 108                 obligations
 109                     .iter()
 110                     .filter(|o| o.predicate.has_infer_types())
 111                     .cloned(),
 112             );
 113
 114             // From the full set of obligations, just filter down to the
 115             // region relationships.
 116             implied_bounds.extend(obligations.into_iter().flat_map(|obligation| {
 117                 assert!(!obligation.has_escaping_regions());
 118                 match obligation.predicate {
 119                     ty::Predicate::Trait(..) |
 120                     ty::Predicate::Subtype(..) |
 121                     ty::Predicate::Projection(..) |
 122                     ty::Predicate::ClosureKind(..) |
 123                     ty::Predicate::ObjectSafe(..) |
 124                     ty::Predicate::ConstEvaluatable(..) => vec![],
 125
 126                     ty::Predicate::WellFormed(subty) => {
 127                         wf_types.push(subty);
 128                         vec![]
 129                     }
 130
 131                     ty::Predicate::RegionOutlives(ref data) => match data.no_late_bound_regions() {
 132                         None => vec![],
 133                         Some(ty::OutlivesPredicate(r_a, r_b)) => {
 134                             vec![OutlivesBound::RegionSubRegion(r_b, r_a)]
 135                         }
 136                     },
 137
 138                     ty::Predicate::TypeOutlives(ref data) => match data.no_late_bound_regions() {
 139                         None => vec![],
 140                         Some(ty::OutlivesPredicate(ty_a, r_b)) => {
 141                             let ty_a = self.resolve_type_vars_if_possible(&ty_a);
 142                             let components = tcx.outlives_components(ty_a);
 143                             Self::implied_bounds_from_components(r_b, components)
 144                         }
 145                     },
 146                 }
 147             }));
 148         }
 149
 150         // Ensure that those obligations that we had to solve
 151         // get solved *here*.
 152         match fulfill_cx.select_all_or_error(self) {
 153             Ok(()) => (),
 154             Err(errors) => self.report_fulfillment_errors(&errors, None),
 155         }
 156
 157         implied_bounds
 158     }
 159
 160     /// When we have an implied bound that `T: 'a`, we can further break
 161     /// this down to determine what relationships would have to hold for
 162     /// `T: 'a` to hold. We get to assume that the caller has validated
 163     /// those relationships.
 164     fn implied_bounds_from_components(
 165         sub_region: ty::Region<'tcx>,
 166         sup_components: Vec<Component<'tcx>>,
 167     ) -> Vec<OutlivesBound<'tcx>> {
 168         sup_components
 169             .into_iter()
 170             .flat_map(|component| {
 171                 match component {
 172                     Component::Region(r) =>
 173                         vec![OutlivesBound::RegionSubRegion(sub_region, r)],
 174                     Component::Param(p) =>
 175                         vec![OutlivesBound::RegionSubParam(sub_region, p)],
 176                     Component::Projection(p) =>
 177                         vec![OutlivesBound::RegionSubProjection(sub_region, p)],
 178                     Component::EscapingProjection(_) =>
 179                     // If the projection has escaping regions, don't
 180                     // try to infer any implied bounds even for its
 181                     // free components. This is conservative, because
 182                     // the caller will still have to prove that those
 183                     // free components outlive `sub_region`. But the
 184                     // idea is that the WAY that the caller proves
 185                     // that may change in the future and we want to
 186                     // give ourselves room to get smarter here.
 187                         vec![],
 188                     Component::UnresolvedInferenceVariable(..) =>
 189                         vec![],
 190                 }
 191             })
 192             .collect()
 193     }
 194 }
 195
 196 pub fn explicit_outlives_bounds<'tcx>(
 197     param_env: ty::ParamEnv<'tcx>,
 198 ) -> impl Iterator<Item = OutlivesBound<'tcx>> + 'tcx {
 199     debug!("explicit_outlives_bounds()");
 200     param_env
 201         .caller_bounds
 202         .into_iter()
 203         .filter_map(move |predicate| match predicate {
 204             ty::Predicate::Projection(..) |
 205             ty::Predicate::Trait(..) |
 206             ty::Predicate::Subtype(..) |
 207             ty::Predicate::WellFormed(..) |
 208             ty::Predicate::ObjectSafe(..) |
 209             ty::Predicate::ClosureKind(..) |
 210             ty::Predicate::TypeOutlives(..) |
 211             ty::Predicate::ConstEvaluatable(..) => None,
 212             ty::Predicate::RegionOutlives(ref data) => data.no_late_bound_regions().map(
 213                 |ty::OutlivesPredicate(r_a, r_b)| OutlivesBound::RegionSubRegion(r_b, r_a),
 214             ),
 215         })
 216 }