src/librustc/traits/query/type_op/mod.rs

   1 // Copyright 2016 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::canonical::{Canonical, Canonicalized, CanonicalizedQueryResult, QueryRegionConstraint,
  12                        QueryResult};
  13 use infer::{InferCtxt, InferOk};
  14 use std::fmt;
  15 use std::rc::Rc;
  16 use traits::query::Fallible;
  17 use traits::ObligationCause;
  18 use ty::fold::TypeFoldable;
  19 use ty::{Lift, ParamEnvAnd, TyCtxt};
  20
  21 pub mod custom;
  22 pub mod eq;
  23 pub mod normalize;
  24 pub mod outlives;
  25 pub mod prove_predicate;
  26 use self::prove_predicate::ProvePredicate;
  27 pub mod subtype;
  28
  29 /// "Type ops" are used in NLL to perform some particular action and
  30 /// extract out the resulting region constraints (or an error if it
  31 /// cannot be completed).
  32 pub trait TypeOp<'gcx, 'tcx>: Sized + fmt::Debug {
  33     type Output;
  34
  35     /// Processes the operation and all resulting obligations,
  36     /// returning the final result along with any region constraints
  37     /// (they will be given over to the NLL region solver).
  38     fn fully_perform(
  39         self,
  40         infcx: &InferCtxt<'_, 'gcx, 'tcx>,
  41     ) -> Fallible<(Self::Output, Option<Rc<Vec<QueryRegionConstraint<'tcx>>>>)>;
  42 }
  43
  44 /// "Query type ops" are type ops that are implemented using a
  45 /// [canonical query][c]. The `Self` type here contains the kernel of
  46 /// information needed to do the operation -- `TypeOp` is actually
  47 /// implemented for `ParamEnvAnd<Self>`, since we always need to bring
  48 /// along a parameter environment as well. For query type-ops, we will
  49 /// first canonicalize the key and then invoke the query on the tcx,
  50 /// which produces the resulting query region constraints.
  51 ///
  52 /// [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html
  53 pub trait QueryTypeOp<'gcx: 'tcx, 'tcx>:
  54     fmt::Debug + Sized + TypeFoldable<'tcx> + Lift<'gcx>
  55 {
  56     type QueryResult: TypeFoldable<'tcx> + Lift<'gcx>;
  57
  58     /// Give query the option for a simple fast path that never
  59     /// actually hits the tcx cache lookup etc. Return `Some(r)` with
  60     /// a final result or `None` to do the full path.
  61     fn try_fast_path(
  62         tcx: TyCtxt<'_, 'gcx, 'tcx>,
  63         key: &ParamEnvAnd<'tcx, Self>,
  64     ) -> Option<Self::QueryResult>;
  65
  66     /// Performs the actual query with the canonicalized key -- the
  67     /// real work happens here. This method is not given an `infcx`
  68     /// because it shouldn't need one -- and if it had access to one,
  69     /// it might do things like invoke `sub_regions`, which would be
  70     /// bad, because it would create subregion relationships that are
  71     /// not captured in the return value.
  72     fn perform_query(
  73         tcx: TyCtxt<'_, 'gcx, 'tcx>,
  74         canonicalized: Canonicalized<'gcx, ParamEnvAnd<'tcx, Self>>,
  75     ) -> Fallible<CanonicalizedQueryResult<'gcx, Self::QueryResult>>;
  76
  77     /// Casts a lifted query result (which is in the gcx lifetime)
  78     /// into the tcx lifetime. This is always just an identity cast,
  79     /// but the generic code doesn't realize it -- put another way, in
  80     /// the generic code, we have a `Lifted<'gcx, Self::QueryResult>`
  81     /// and we want to convert that to a `Self::QueryResult`. This is
  82     /// not a priori valid, so we can't do it -- but in practice, it
  83     /// is always a no-op (e.g., the lifted form of a type,
  84     /// `Ty<'gcx>`, is a subtype of `Ty<'tcx>`). So we have to push
  85     /// the operation into the impls that know more specifically what
  86     /// `QueryResult` is. This operation would (maybe) be nicer with
  87     /// something like HKTs or GATs, since then we could make
  88     /// `QueryResult` parametric and `'gcx` and `'tcx` etc.
  89     fn shrink_to_tcx_lifetime(
  90         lifted_query_result: &'a CanonicalizedQueryResult<'gcx, Self::QueryResult>,
  91     ) -> &'a Canonical<'tcx, QueryResult<'tcx, Self::QueryResult>>;
  92
  93     fn fully_perform_into(
  94         query_key: ParamEnvAnd<'tcx, Self>,
  95         infcx: &InferCtxt<'_, 'gcx, 'tcx>,
  96         output_query_region_constraints: &mut Vec<QueryRegionConstraint<'tcx>>,
  97     ) -> Fallible<Self::QueryResult> {
  98         if let Some(result) = QueryTypeOp::try_fast_path(infcx.tcx, &query_key) {
  99             return Ok(result);
 100         }
 101
 102         // FIXME(#33684) -- We need to use
 103         // `canonicalize_hr_query_hack` here because of things
 104         // like the subtype query, which go awry around
 105         // `'static` otherwise.
 106         let (canonical_self, canonical_var_values) = infcx.canonicalize_hr_query_hack(&query_key);
 107         let canonical_result = Self::perform_query(infcx.tcx, canonical_self)?;
 108         let canonical_result = Self::shrink_to_tcx_lifetime(&canonical_result);
 109
 110         let param_env = query_key.param_env;
 111
 112         let InferOk { value, obligations } = infcx
 113             .instantiate_nll_query_result_and_region_obligations(
 114                 &ObligationCause::dummy(),
 115                 param_env,
 116                 &canonical_var_values,
 117                 canonical_result,
 118                 output_query_region_constraints,
 119             )?;
 120
 121         // Typically, instantiating NLL query results does not
 122         // create obligations. However, in some cases there
 123         // are unresolved type variables, and unify them *can*
 124         // create obligations. In that case, we have to go
 125         // fulfill them. We do this via a (recursive) query.
 126         for obligation in obligations {
 127             let () = ProvePredicate::fully_perform_into(
 128                 obligation
 129                     .param_env
 130                     .and(ProvePredicate::new(obligation.predicate)),
 131                 infcx,
 132                 output_query_region_constraints,
 133             )?;
 134         }
 135
 136         Ok(value)
 137     }
 138 }
 139
 140 impl<'gcx: 'tcx, 'tcx, Q> TypeOp<'gcx, 'tcx> for ParamEnvAnd<'tcx, Q>
 141 where
 142     Q: QueryTypeOp<'gcx, 'tcx>,
 143 {
 144     type Output = Q::QueryResult;
 145
 146     fn fully_perform(
 147         self,
 148         infcx: &InferCtxt<'_, 'gcx, 'tcx>,
 149     ) -> Fallible<(Self::Output, Option<Rc<Vec<QueryRegionConstraint<'tcx>>>>)> {
 150         let mut qrc = vec![];
 151         let r = Q::fully_perform_into(self, infcx, &mut qrc)?;
 152
 153         // Promote the final query-region-constraints into a
 154         // (optional) ref-counted vector:
 155         let opt_qrc = if qrc.is_empty() {
 156             None
 157         } else {
 158             Some(Rc::new(qrc))
 159         };
 160
 161         Ok((r, opt_qrc))
 162     }
 163 }