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