compiler/rustc_trait_selection/src/traits/query/type_op/mod.rs

   1 use crate::infer::canonical::{
   2     Canonicalized, CanonicalizedQueryResponse, OriginalQueryValues, QueryRegionConstraints,
   3 };
   4 use crate::infer::{InferCtxt, InferOk};
   5 use crate::traits::query::Fallible;
   6 use crate::traits::ObligationCause;
   7 use rustc_infer::infer::canonical::{Canonical, Certainty};
   8 use rustc_infer::traits::query::NoSolution;
   9 use rustc_infer::traits::PredicateObligations;
  10 use rustc_middle::ty::fold::TypeFoldable;
  11 use rustc_middle::ty::{ParamEnvAnd, TyCtxt};
  12 use std::fmt;
  13
  14 pub mod ascribe_user_type;
  15 pub mod custom;
  16 pub mod eq;
  17 pub mod implied_outlives_bounds;
  18 pub mod normalize;
  19 pub mod outlives;
  20 pub mod prove_predicate;
  21 pub mod subtype;
  22
  23 pub use rustc_middle::traits::query::type_op::*;
  24
  25 /// "Type ops" are used in NLL to perform some particular action and
  26 /// extract out the resulting region constraints (or an error if it
  27 /// cannot be completed).
  28 pub trait TypeOp<'tcx>: Sized + fmt::Debug {
  29     type Output: fmt::Debug;
  30     type ErrorInfo;
  31
  32     /// Processes the operation and all resulting obligations,
  33     /// returning the final result along with any region constraints
  34     /// (they will be given over to the NLL region solver).
  35     fn fully_perform(self, infcx: &InferCtxt<'tcx>) -> Fallible<TypeOpOutput<'tcx, Self>>;
  36 }
  37
  38 /// The output from performing a type op
  39 pub struct TypeOpOutput<'tcx, Op: TypeOp<'tcx>> {
  40     /// The output from the type op.
  41     pub output: Op::Output,
  42     /// Any region constraints from performing the type op.
  43     pub constraints: Option<&'tcx QueryRegionConstraints<'tcx>>,
  44     /// Used for error reporting to be able to rerun the query
  45     pub error_info: Option<Op::ErrorInfo>,
  46 }
  47
  48 /// "Query type ops" are type ops that are implemented using a
  49 /// [canonical query][c]. The `Self` type here contains the kernel of
  50 /// information needed to do the operation -- `TypeOp` is actually
  51 /// implemented for `ParamEnvAnd<Self>`, since we always need to bring
  52 /// along a parameter environment as well. For query type-ops, we will
  53 /// first canonicalize the key and then invoke the query on the tcx,
  54 /// which produces the resulting query region constraints.
  55 ///
  56 /// [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html
  57 pub trait QueryTypeOp<'tcx>: fmt::Debug + Copy + TypeFoldable<'tcx> + 'tcx {
  58     type QueryResponse: TypeFoldable<'tcx>;
  59
  60     /// Give query the option for a simple fast path that never
  61     /// actually hits the tcx cache lookup etc. Return `Some(r)` with
  62     /// a final result or `None` to do the full path.
  63     fn try_fast_path(
  64         tcx: TyCtxt<'tcx>,
  65         key: &ParamEnvAnd<'tcx, Self>,
  66     ) -> Option<Self::QueryResponse>;
  67
  68     /// Performs the actual query with the canonicalized key -- the
  69     /// real work happens here. This method is not given an `infcx`
  70     /// because it shouldn't need one -- and if it had access to one,
  71     /// it might do things like invoke `sub_regions`, which would be
  72     /// bad, because it would create subregion relationships that are
  73     /// not captured in the return value.
  74     fn perform_query(
  75         tcx: TyCtxt<'tcx>,
  76         canonicalized: Canonicalized<'tcx, ParamEnvAnd<'tcx, Self>>,
  77     ) -> Fallible<CanonicalizedQueryResponse<'tcx, Self::QueryResponse>>;
  78
  79     fn fully_perform_into(
  80         query_key: ParamEnvAnd<'tcx, Self>,
  81         infcx: &InferCtxt<'tcx>,
  82         output_query_region_constraints: &mut QueryRegionConstraints<'tcx>,
  83     ) -> Fallible<(
  84         Self::QueryResponse,
  85         Option<Canonical<'tcx, ParamEnvAnd<'tcx, Self>>>,
  86         PredicateObligations<'tcx>,
  87         Certainty,
  88     )> {
  89         if let Some(result) = QueryTypeOp::try_fast_path(infcx.tcx, &query_key) {
  90             return Ok((result, None, vec![], Certainty::Proven));
  91         }
  92
  93         // FIXME(#33684) -- We need to use
  94         // `canonicalize_query_keep_static` here because of things
  95         // like the subtype query, which go awry around
  96         // `'static` otherwise.
  97         let mut canonical_var_values = OriginalQueryValues::default();
  98         let old_param_env = query_key.param_env;
  99         let canonical_self =
 100             infcx.canonicalize_query_keep_static(query_key, &mut canonical_var_values);
 101         let canonical_result = Self::perform_query(infcx.tcx, canonical_self)?;
 102
 103         let InferOk { value, obligations } = infcx
 104             .instantiate_nll_query_response_and_region_obligations(
 105                 &ObligationCause::dummy(),
 106                 old_param_env,
 107                 &canonical_var_values,
 108                 canonical_result,
 109                 output_query_region_constraints,
 110             )?;
 111
 112         Ok((value, Some(canonical_self), obligations, canonical_result.value.certainty))
 113     }
 114 }
 115
 116 impl<'tcx, Q> TypeOp<'tcx> for ParamEnvAnd<'tcx, Q>
 117 where
 118     Q: QueryTypeOp<'tcx>,
 119 {
 120     type Output = Q::QueryResponse;
 121     type ErrorInfo = Canonical<'tcx, ParamEnvAnd<'tcx, Q>>;
 122
 123     fn fully_perform(self, infcx: &InferCtxt<'tcx>) -> Fallible<TypeOpOutput<'tcx, Self>> {
 124         let mut region_constraints = QueryRegionConstraints::default();
 125         let (output, error_info, mut obligations, _) =
 126             Q::fully_perform_into(self, infcx, &mut region_constraints)?;
 127
 128         // Typically, instantiating NLL query results does not
 129         // create obligations. However, in some cases there
 130         // are unresolved type variables, and unify them *can*
 131         // create obligations. In that case, we have to go
 132         // fulfill them. We do this via a (recursive) query.
 133         while !obligations.is_empty() {
 134             trace!("{:#?}", obligations);
 135             let mut progress = false;
 136             for obligation in std::mem::take(&mut obligations) {
 137                 let obligation = infcx.resolve_vars_if_possible(obligation);
 138                 match ProvePredicate::fully_perform_into(
 139                     obligation.param_env.and(ProvePredicate::new(obligation.predicate)),
 140                     infcx,
 141                     &mut region_constraints,
 142                 ) {
 143                     Ok(((), _, new, certainty)) => {
 144                         obligations.extend(new);
 145                         progress = true;
 146                         if let Certainty::Ambiguous = certainty {
 147                             obligations.push(obligation);
 148                         }
 149                     }
 150                     Err(_) => obligations.push(obligation),
 151                 }
 152             }
 153             if !progress {
 154                 return Err(NoSolution);
 155             }
 156         }
 157
 158         Ok(TypeOpOutput {
 159             output,
 160             constraints: if region_constraints.is_empty() {
 161                 None
 162             } else {
 163                 Some(infcx.tcx.arena.alloc(region_constraints))
 164             },
 165             error_info,
 166         })
 167     }
 168 }