src/librustc_trait_selection/traits/query/normalize.rs

   1 //! Code for the 'normalization' query. This consists of a wrapper
   2 //! which folds deeply, invoking the underlying
   3 //! `normalize_projection_ty` query when it encounters projections.
   4
   5 use crate::infer::at::At;
   6 use crate::infer::canonical::OriginalQueryValues;
   7 use crate::infer::{InferCtxt, InferOk};
   8 use crate::traits::error_reporting::InferCtxtExt;
   9 use crate::traits::{Obligation, ObligationCause, PredicateObligation, Reveal};
  10 use rustc_data_structures::stack::ensure_sufficient_stack;
  11 use rustc_infer::traits::Normalized;
  12 use rustc_middle::ty::fold::{TypeFoldable, TypeFolder};
  13 use rustc_middle::ty::subst::Subst;
  14 use rustc_middle::ty::{self, Ty, TyCtxt};
  15
  16 use super::NoSolution;
  17
  18 pub use rustc_middle::traits::query::NormalizationResult;
  19
  20 pub trait AtExt<'tcx> {
  21     fn normalize<T>(&self, value: &T) -> Result<Normalized<'tcx, T>, NoSolution>
  22     where
  23         T: TypeFoldable<'tcx>;
  24 }
  25
  26 impl<'cx, 'tcx> AtExt<'tcx> for At<'cx, 'tcx> {
  27     /// Normalize `value` in the context of the inference context,
  28     /// yielding a resulting type, or an error if `value` cannot be
  29     /// normalized. If you don't care about regions, you should prefer
  30     /// `normalize_erasing_regions`, which is more efficient.
  31     ///
  32     /// If the normalization succeeds and is unambiguous, returns back
  33     /// the normalized value along with various outlives relations (in
  34     /// the form of obligations that must be discharged).
  35     ///
  36     /// N.B., this will *eventually* be the main means of
  37     /// normalizing, but for now should be used only when we actually
  38     /// know that normalization will succeed, since error reporting
  39     /// and other details are still "under development".
  40     fn normalize<T>(&self, value: &T) -> Result<Normalized<'tcx, T>, NoSolution>
  41     where
  42         T: TypeFoldable<'tcx>,
  43     {
  44         debug!(
  45             "normalize::<{}>(value={:?}, param_env={:?})",
  46             ::std::any::type_name::<T>(),
  47             value,
  48             self.param_env,
  49         );
  50         if !value.has_projections() {
  51             return Ok(Normalized { value: value.clone(), obligations: vec![] });
  52         }
  53
  54         let mut normalizer = QueryNormalizer {
  55             infcx: self.infcx,
  56             cause: self.cause,
  57             param_env: self.param_env,
  58             obligations: vec![],
  59             error: false,
  60             anon_depth: 0,
  61         };
  62
  63         let result = value.fold_with(&mut normalizer);
  64         debug!(
  65             "normalize::<{}>: result={:?} with {} obligations",
  66             ::std::any::type_name::<T>(),
  67             result,
  68             normalizer.obligations.len(),
  69         );
  70         debug!(
  71             "normalize::<{}>: obligations={:?}",
  72             ::std::any::type_name::<T>(),
  73             normalizer.obligations,
  74         );
  75         if normalizer.error {
  76             Err(NoSolution)
  77         } else {
  78             Ok(Normalized { value: result, obligations: normalizer.obligations })
  79         }
  80     }
  81 }
  82
  83 struct QueryNormalizer<'cx, 'tcx> {
  84     infcx: &'cx InferCtxt<'cx, 'tcx>,
  85     cause: &'cx ObligationCause<'tcx>,
  86     param_env: ty::ParamEnv<'tcx>,
  87     obligations: Vec<PredicateObligation<'tcx>>,
  88     error: bool,
  89     anon_depth: usize,
  90 }
  91
  92 impl<'cx, 'tcx> TypeFolder<'tcx> for QueryNormalizer<'cx, 'tcx> {
  93     fn tcx<'c>(&'c self) -> TyCtxt<'tcx> {
  94         self.infcx.tcx
  95     }
  96
  97     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
  98         if !ty.has_projections() {
  99             return ty;
 100         }
 101
 102         let ty = ty.super_fold_with(self);
 103         match ty.kind {
 104             ty::Opaque(def_id, substs) => {
 105                 // Only normalize `impl Trait` after type-checking, usually in codegen.
 106                 match self.param_env.reveal() {
 107                     Reveal::UserFacing => ty,
 108
 109                     Reveal::All => {
 110                         let recursion_limit = self.tcx().sess.recursion_limit();
 111                         if !recursion_limit.value_within_limit(self.anon_depth) {
 112                             let obligation = Obligation::with_depth(
 113                                 self.cause.clone(),
 114                                 recursion_limit.0,
 115                                 self.param_env,
 116                                 ty,
 117                             );
 118                             self.infcx.report_overflow_error(&obligation, true);
 119                         }
 120
 121                         let generic_ty = self.tcx().type_of(def_id);
 122                         let concrete_ty = generic_ty.subst(self.tcx(), substs);
 123                         self.anon_depth += 1;
 124                         if concrete_ty == ty {
 125                             bug!(
 126                                 "infinite recursion generic_ty: {:#?}, substs: {:#?}, \
 127                                  concrete_ty: {:#?}, ty: {:#?}",
 128                                 generic_ty,
 129                                 substs,
 130                                 concrete_ty,
 131                                 ty
 132                             );
 133                         }
 134                         let folded_ty = ensure_sufficient_stack(|| self.fold_ty(concrete_ty));
 135                         self.anon_depth -= 1;
 136                         folded_ty
 137                     }
 138                 }
 139             }
 140
 141             ty::Projection(ref data) if !data.has_escaping_bound_vars() => {
 142                 // This is kind of hacky -- we need to be able to
 143                 // handle normalization within binders because
 144                 // otherwise we wind up a need to normalize when doing
 145                 // trait matching (since you can have a trait
 146                 // obligation like `for<'a> T::B: Fn(&'a i32)`), but
 147                 // we can't normalize with bound regions in scope. So
 148                 // far now we just ignore binders but only normalize
 149                 // if all bound regions are gone (and then we still
 150                 // have to renormalize whenever we instantiate a
 151                 // binder). It would be better to normalize in a
 152                 // binding-aware fashion.
 153
 154                 let tcx = self.infcx.tcx;
 155
 156                 let mut orig_values = OriginalQueryValues::default();
 157                 // HACK(matthewjasper) `'static` is special-cased in selection,
 158                 // so we cannot canonicalize it.
 159                 let c_data = self
 160                     .infcx
 161                     .canonicalize_hr_query_hack(&self.param_env.and(*data), &mut orig_values);
 162                 debug!("QueryNormalizer: c_data = {:#?}", c_data);
 163                 debug!("QueryNormalizer: orig_values = {:#?}", orig_values);
 164                 match tcx.normalize_projection_ty(c_data) {
 165                     Ok(result) => {
 166                         // We don't expect ambiguity.
 167                         if result.is_ambiguous() {
 168                             self.error = true;
 169                             return ty;
 170                         }
 171
 172                         match self.infcx.instantiate_query_response_and_region_obligations(
 173                             self.cause,
 174                             self.param_env,
 175                             &orig_values,
 176                             &result,
 177                         ) {
 178                             Ok(InferOk { value: result, obligations }) => {
 179                                 debug!("QueryNormalizer: result = {:#?}", result);
 180                                 debug!("QueryNormalizer: obligations = {:#?}", obligations);
 181                                 self.obligations.extend(obligations);
 182                                 result.normalized_ty
 183                             }
 184
 185                             Err(_) => {
 186                                 self.error = true;
 187                                 ty
 188                             }
 189                         }
 190                     }
 191
 192                     Err(NoSolution) => {
 193                         self.error = true;
 194                         ty
 195                     }
 196                 }
 197             }
 198
 199             _ => ty,
 200         }
 201     }
 202
 203     fn fold_const(&mut self, constant: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> {
 204         let constant = constant.super_fold_with(self);
 205         constant.eval(self.infcx.tcx, self.param_env)
 206     }
 207 }