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

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