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::project::needs_normalization;
  10 use crate::traits::{Obligation, ObligationCause, PredicateObligation, Reveal};
  11 use rustc_data_structures::sso::SsoHashMap;
  12 use rustc_data_structures::stack::ensure_sufficient_stack;
  13 use rustc_infer::traits::Normalized;
  14 use rustc_middle::mir;
  15 use rustc_middle::ty::fold::{FallibleTypeFolder, TypeFoldable, TypeFolder};
  16 use rustc_middle::ty::subst::Subst;
  17 use rustc_middle::ty::{self, Ty, TyCtxt, TypeVisitor};
  18
  19 use std::ops::ControlFlow;
  20
  21 use super::NoSolution;
  22
  23 pub use rustc_middle::traits::query::NormalizationResult;
  24
  25 pub trait AtExt<'tcx> {
  26     fn normalize<T>(&self, value: T) -> Result<Normalized<'tcx, T>, NoSolution>
  27     where
  28         T: TypeFoldable<'tcx>;
  29 }
  30
  31 impl<'cx, 'tcx> AtExt<'tcx> for At<'cx, 'tcx> {
  32     /// Normalize `value` in the context of the inference context,
  33     /// yielding a resulting type, or an error if `value` cannot be
  34     /// normalized. If you don't care about regions, you should prefer
  35     /// `normalize_erasing_regions`, which is more efficient.
  36     ///
  37     /// If the normalization succeeds and is unambiguous, returns back
  38     /// the normalized value along with various outlives relations (in
  39     /// the form of obligations that must be discharged).
  40     ///
  41     /// N.B., this will *eventually* be the main means of
  42     /// normalizing, but for now should be used only when we actually
  43     /// know that normalization will succeed, since error reporting
  44     /// and other details are still "under development".
  45     fn normalize<T>(&self, value: T) -> Result<Normalized<'tcx, T>, NoSolution>
  46     where
  47         T: TypeFoldable<'tcx>,
  48     {
  49         debug!(
  50             "normalize::<{}>(value={:?}, param_env={:?})",
  51             std::any::type_name::<T>(),
  52             value,
  53             self.param_env,
  54         );
  55         if !needs_normalization(&value, self.param_env.reveal()) {
  56             return Ok(Normalized { value, obligations: vec![] });
  57         }
  58
  59         let mut normalizer = QueryNormalizer {
  60             infcx: self.infcx,
  61             cause: self.cause,
  62             param_env: self.param_env,
  63             obligations: vec![],
  64             cache: SsoHashMap::new(),
  65             anon_depth: 0,
  66             universes: vec![],
  67         };
  68
  69         // This is actually a consequence by the way `normalize_erasing_regions` works currently.
  70         // Because it needs to call the `normalize_generic_arg_after_erasing_regions`, it folds
  71         // through tys and consts in a `TypeFoldable`. Importantly, it skips binders, leaving us
  72         // with trying to normalize with escaping bound vars.
  73         //
  74         // Here, we just add the universes that we *would* have created had we passed through the binders.
  75         //
  76         // We *could* replace escaping bound vars eagerly here, but it doesn't seem really necessary.
  77         // The rest of the code is already set up to be lazy about replacing bound vars,
  78         // and only when we actually have to normalize.
  79         if value.has_escaping_bound_vars() {
  80             let mut max_visitor = MaxEscapingBoundVarVisitor {
  81                 tcx: self.infcx.tcx,
  82                 outer_index: ty::INNERMOST,
  83                 escaping: 0,
  84             };
  85             value.visit_with(&mut max_visitor);
  86             if max_visitor.escaping > 0 {
  87                 normalizer.universes.extend((0..max_visitor.escaping).map(|_| None));
  88             }
  89         }
  90         let result = value.try_fold_with(&mut normalizer);
  91         info!(
  92             "normalize::<{}>: result={:?} with {} obligations",
  93             std::any::type_name::<T>(),
  94             result,
  95             normalizer.obligations.len(),
  96         );
  97         debug!(
  98             "normalize::<{}>: obligations={:?}",
  99             std::any::type_name::<T>(),
 100             normalizer.obligations,
 101         );
 102         result.map(|value| Normalized { value, obligations: normalizer.obligations })
 103     }
 104 }
 105
 106 /// Visitor to find the maximum escaping bound var
 107 struct MaxEscapingBoundVarVisitor<'tcx> {
 108     tcx: TyCtxt<'tcx>,
 109     // The index which would count as escaping
 110     outer_index: ty::DebruijnIndex,
 111     escaping: usize,
 112 }
 113
 114 impl<'tcx> TypeVisitor<'tcx> for MaxEscapingBoundVarVisitor<'tcx> {
 115     fn tcx_for_anon_const_substs(&self) -> Option<TyCtxt<'tcx>> {
 116         Some(self.tcx)
 117     }
 118
 119     fn visit_binder<T: TypeFoldable<'tcx>>(
 120         &mut self,
 121         t: &ty::Binder<'tcx, T>,
 122     ) -> ControlFlow<Self::BreakTy> {
 123         self.outer_index.shift_in(1);
 124         let result = t.super_visit_with(self);
 125         self.outer_index.shift_out(1);
 126         result
 127     }
 128
 129     #[inline]
 130     fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 131         if t.outer_exclusive_binder() > self.outer_index {
 132             self.escaping = self
 133                 .escaping
 134                 .max(t.outer_exclusive_binder().as_usize() - self.outer_index.as_usize());
 135         }
 136         ControlFlow::CONTINUE
 137     }
 138
 139     #[inline]
 140     fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
 141         match *r {
 142             ty::ReLateBound(debruijn, _) if debruijn > self.outer_index => {
 143                 self.escaping =
 144                     self.escaping.max(debruijn.as_usize() - self.outer_index.as_usize());
 145             }
 146             _ => {}
 147         }
 148         ControlFlow::CONTINUE
 149     }
 150
 151     fn visit_const(&mut self, ct: &'tcx ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
 152         match ct.val {
 153             ty::ConstKind::Bound(debruijn, _) if debruijn >= self.outer_index => {
 154                 self.escaping =
 155                     self.escaping.max(debruijn.as_usize() - self.outer_index.as_usize());
 156                 ControlFlow::CONTINUE
 157             }
 158             _ => ct.super_visit_with(self),
 159         }
 160     }
 161 }
 162
 163 struct QueryNormalizer<'cx, 'tcx> {
 164     infcx: &'cx InferCtxt<'cx, 'tcx>,
 165     cause: &'cx ObligationCause<'tcx>,
 166     param_env: ty::ParamEnv<'tcx>,
 167     obligations: Vec<PredicateObligation<'tcx>>,
 168     cache: SsoHashMap<Ty<'tcx>, Ty<'tcx>>,
 169     anon_depth: usize,
 170     universes: Vec<Option<ty::UniverseIndex>>,
 171 }
 172
 173 impl<'cx, 'tcx> TypeFolder<'tcx> for QueryNormalizer<'cx, 'tcx> {
 174     type Error = NoSolution;
 175
 176     fn tcx<'c>(&'c self) -> TyCtxt<'tcx> {
 177         self.infcx.tcx
 178     }
 179 }
 180
 181 impl<'cx, 'tcx> FallibleTypeFolder<'tcx> for QueryNormalizer<'cx, 'tcx> {
 182     fn try_fold_binder<T: TypeFoldable<'tcx>>(
 183         &mut self,
 184         t: ty::Binder<'tcx, T>,
 185     ) -> Result<ty::Binder<'tcx, T>, Self::Error> {
 186         self.universes.push(None);
 187         let t = t.try_super_fold_with(self);
 188         self.universes.pop();
 189         t
 190     }
 191
 192     #[instrument(level = "debug", skip(self))]
 193     fn try_fold_ty(&mut self, ty: Ty<'tcx>) -> Result<Ty<'tcx>, Self::Error> {
 194         if !needs_normalization(&ty, self.param_env.reveal()) {
 195             return Ok(ty);
 196         }
 197
 198         if let Some(ty) = self.cache.get(&ty) {
 199             return Ok(ty);
 200         }
 201
 202         // See note in `rustc_trait_selection::traits::project` about why we
 203         // wait to fold the substs.
 204
 205         // Wrap this in a closure so we don't accidentally return from the outer function
 206         let res = (|| match *ty.kind() {
 207             // This is really important. While we *can* handle this, this has
 208             // severe performance implications for large opaque types with
 209             // late-bound regions. See `issue-88862` benchmark.
 210             ty::Opaque(def_id, substs) if !substs.has_escaping_bound_vars() => {
 211                 // Only normalize `impl Trait` after type-checking, usually in codegen.
 212                 match self.param_env.reveal() {
 213                     Reveal::UserFacing => ty.try_super_fold_with(self),
 214
 215                     Reveal::All => {
 216                         let substs = substs.try_super_fold_with(self)?;
 217                         let recursion_limit = self.tcx().recursion_limit();
 218                         if !recursion_limit.value_within_limit(self.anon_depth) {
 219                             let obligation = Obligation::with_depth(
 220                                 self.cause.clone(),
 221                                 recursion_limit.0,
 222                                 self.param_env,
 223                                 ty,
 224                             );
 225                             self.infcx.report_overflow_error(&obligation, true);
 226                         }
 227
 228                         let generic_ty = self.tcx().type_of(def_id);
 229                         let concrete_ty = generic_ty.subst(self.tcx(), substs);
 230                         self.anon_depth += 1;
 231                         if concrete_ty == ty {
 232                             bug!(
 233                                 "infinite recursion generic_ty: {:#?}, substs: {:#?}, \
 234                                  concrete_ty: {:#?}, ty: {:#?}",
 235                                 generic_ty,
 236                                 substs,
 237                                 concrete_ty,
 238                                 ty
 239                             );
 240                         }
 241                         let folded_ty = ensure_sufficient_stack(|| self.try_fold_ty(concrete_ty));
 242                         self.anon_depth -= 1;
 243                         folded_ty
 244                     }
 245                 }
 246             }
 247
 248             ty::Projection(data) if !data.has_escaping_bound_vars() => {
 249                 // This branch is just an optimization: when we don't have escaping bound vars,
 250                 // we don't need to replace them with placeholders (see branch below).
 251
 252                 let tcx = self.infcx.tcx;
 253                 let data = data.try_super_fold_with(self)?;
 254
 255                 let mut orig_values = OriginalQueryValues::default();
 256                 // HACK(matthewjasper) `'static` is special-cased in selection,
 257                 // so we cannot canonicalize it.
 258                 let c_data = self
 259                     .infcx
 260                     .canonicalize_query_keep_static(self.param_env.and(data), &mut orig_values);
 261                 debug!("QueryNormalizer: c_data = {:#?}", c_data);
 262                 debug!("QueryNormalizer: orig_values = {:#?}", orig_values);
 263                 let result = tcx.normalize_projection_ty(c_data)?;
 264                 // We don't expect ambiguity.
 265                 if result.is_ambiguous() {
 266                     return Err(NoSolution);
 267                 }
 268                 let InferOk { value: result, obligations } =
 269                     self.infcx.instantiate_query_response_and_region_obligations(
 270                         self.cause,
 271                         self.param_env,
 272                         &orig_values,
 273                         result,
 274                     )?;
 275                 debug!("QueryNormalizer: result = {:#?}", result);
 276                 debug!("QueryNormalizer: obligations = {:#?}", obligations);
 277                 self.obligations.extend(obligations);
 278                 Ok(result.normalized_ty)
 279             }
 280
 281             ty::Projection(data) => {
 282                 // See note in `rustc_trait_selection::traits::project`
 283
 284                 let tcx = self.infcx.tcx;
 285                 let infcx = self.infcx;
 286                 let (data, mapped_regions, mapped_types, mapped_consts) =
 287                     crate::traits::project::BoundVarReplacer::replace_bound_vars(
 288                         infcx,
 289                         &mut self.universes,
 290                         data,
 291                     );
 292                 let data = data.try_super_fold_with(self)?;
 293
 294                 let mut orig_values = OriginalQueryValues::default();
 295                 // HACK(matthewjasper) `'static` is special-cased in selection,
 296                 // so we cannot canonicalize it.
 297                 let c_data = self
 298                     .infcx
 299                     .canonicalize_query_keep_static(self.param_env.and(data), &mut orig_values);
 300                 debug!("QueryNormalizer: c_data = {:#?}", c_data);
 301                 debug!("QueryNormalizer: orig_values = {:#?}", orig_values);
 302                 let result = tcx.normalize_projection_ty(c_data)?;
 303                 // We don't expect ambiguity.
 304                 if result.is_ambiguous() {
 305                     return Err(NoSolution);
 306                 }
 307                 let InferOk { value: result, obligations } =
 308                     self.infcx.instantiate_query_response_and_region_obligations(
 309                         self.cause,
 310                         self.param_env,
 311                         &orig_values,
 312                         result,
 313                     )?;
 314                 debug!("QueryNormalizer: result = {:#?}", result);
 315                 debug!("QueryNormalizer: obligations = {:#?}", obligations);
 316                 self.obligations.extend(obligations);
 317                 Ok(crate::traits::project::PlaceholderReplacer::replace_placeholders(
 318                     infcx,
 319                     mapped_regions,
 320                     mapped_types,
 321                     mapped_consts,
 322                     &self.universes,
 323                     result.normalized_ty,
 324                 ))
 325             }
 326
 327             _ => ty.try_super_fold_with(self),
 328         })()?;
 329         self.cache.insert(ty, res);
 330         Ok(res)
 331     }
 332
 333     fn try_fold_const(
 334         &mut self,
 335         constant: &'tcx ty::Const<'tcx>,
 336     ) -> Result<&'tcx ty::Const<'tcx>, Self::Error> {
 337         let constant = constant.try_super_fold_with(self)?;
 338         Ok(constant.eval(self.infcx.tcx, self.param_env))
 339     }
 340
 341     fn try_fold_mir_const(
 342         &mut self,
 343         constant: mir::ConstantKind<'tcx>,
 344     ) -> Result<mir::ConstantKind<'tcx>, Self::Error> {
 345         constant.try_super_fold_with(self)
 346     }
 347 }