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::TypeErrCtxtExt;
   9 use crate::traits::project::{needs_normalization, BoundVarReplacer, PlaceholderReplacer};
  10 use crate::traits::{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::ty::fold::{FallibleTypeFolder, TypeFoldable, TypeSuperFoldable};
  15 use rustc_middle::ty::visit::{TypeSuperVisitable, TypeVisitable, TypeVisitableExt};
  16 use rustc_middle::ty::{self, Ty, TyCtxt, TypeVisitor};
  17 use rustc_span::DUMMY_SP;
  18
  19 use std::ops::ControlFlow;
  20
  21 use super::NoSolution;
  22
  23 pub use rustc_middle::traits::query::NormalizationResult;
  24
  25 pub trait QueryNormalizeExt<'tcx> {
  26     /// Normalize a value using the `QueryNormalizer`.
  27     ///
  28     /// This normalization should *only* be used when the projection does not
  29     /// have possible ambiguity or may not be well-formed.
  30     ///
  31     /// After codegen, when lifetimes do not matter, it is preferable to instead
  32     /// use [`TyCtxt::normalize_erasing_regions`], which wraps this procedure.
  33     fn query_normalize<T>(&self, value: T) -> Result<Normalized<'tcx, T>, NoSolution>
  34     where
  35         T: TypeFoldable<TyCtxt<'tcx>>;
  36 }
  37
  38 impl<'cx, 'tcx> QueryNormalizeExt<'tcx> for At<'cx, 'tcx> {
  39     /// Normalize `value` in the context of the inference context,
  40     /// yielding a resulting type, or an error if `value` cannot be
  41     /// normalized. If you don't care about regions, you should prefer
  42     /// `normalize_erasing_regions`, which is more efficient.
  43     ///
  44     /// If the normalization succeeds and is unambiguous, returns back
  45     /// the normalized value along with various outlives relations (in
  46     /// the form of obligations that must be discharged).
  47     ///
  48     /// N.B., this will *eventually* be the main means of
  49     /// normalizing, but for now should be used only when we actually
  50     /// know that normalization will succeed, since error reporting
  51     /// and other details are still "under development".
  52     fn query_normalize<T>(&self, value: T) -> Result<Normalized<'tcx, T>, NoSolution>
  53     where
  54         T: TypeFoldable<TyCtxt<'tcx>>,
  55     {
  56         debug!(
  57             "normalize::<{}>(value={:?}, param_env={:?}, cause={:?})",
  58             std::any::type_name::<T>(),
  59             value,
  60             self.param_env,
  61             self.cause,
  62         );
  63         if !needs_normalization(&value, self.param_env.reveal()) {
  64             return Ok(Normalized { value, obligations: vec![] });
  65         }
  66
  67         let mut normalizer = QueryNormalizer {
  68             infcx: self.infcx,
  69             cause: self.cause,
  70             param_env: self.param_env,
  71             obligations: vec![],
  72             cache: SsoHashMap::new(),
  73             anon_depth: 0,
  74             universes: vec![],
  75         };
  76
  77         // This is actually a consequence by the way `normalize_erasing_regions` works currently.
  78         // Because it needs to call the `normalize_generic_arg_after_erasing_regions`, it folds
  79         // through tys and consts in a `TypeFoldable`. Importantly, it skips binders, leaving us
  80         // with trying to normalize with escaping bound vars.
  81         //
  82         // Here, we just add the universes that we *would* have created had we passed through the binders.
  83         //
  84         // We *could* replace escaping bound vars eagerly here, but it doesn't seem really necessary.
  85         // The rest of the code is already set up to be lazy about replacing bound vars,
  86         // and only when we actually have to normalize.
  87         if value.has_escaping_bound_vars() {
  88             let mut max_visitor =
  89                 MaxEscapingBoundVarVisitor { outer_index: ty::INNERMOST, escaping: 0 };
  90             value.visit_with(&mut max_visitor);
  91             if max_visitor.escaping > 0 {
  92                 normalizer.universes.extend((0..max_visitor.escaping).map(|_| None));
  93             }
  94         }
  95         let result = value.try_fold_with(&mut normalizer);
  96         info!(
  97             "normalize::<{}>: result={:?} with {} obligations",
  98             std::any::type_name::<T>(),
  99             result,
 100             normalizer.obligations.len(),
 101         );
 102         debug!(
 103             "normalize::<{}>: obligations={:?}",
 104             std::any::type_name::<T>(),
 105             normalizer.obligations,
 106         );
 107         result.map(|value| Normalized { value, obligations: normalizer.obligations })
 108     }
 109 }
 110
 111 // Visitor to find the maximum escaping bound var
 112 struct MaxEscapingBoundVarVisitor {
 113     // The index which would count as escaping
 114     outer_index: ty::DebruijnIndex,
 115     escaping: usize,
 116 }
 117
 118 impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for MaxEscapingBoundVarVisitor {
 119     fn visit_binder<T: TypeVisitable<TyCtxt<'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: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
 152         match ct.kind() {
 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<'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> FallibleTypeFolder<TyCtxt<'tcx>> for QueryNormalizer<'cx, 'tcx> {
 174     type Error = NoSolution;
 175
 176     fn interner(&self) -> TyCtxt<'tcx> {
 177         self.infcx.tcx
 178     }
 179
 180     fn try_fold_binder<T: TypeFoldable<TyCtxt<'tcx>>>(
 181         &mut self,
 182         t: ty::Binder<'tcx, T>,
 183     ) -> Result<ty::Binder<'tcx, T>, Self::Error> {
 184         self.universes.push(None);
 185         let t = t.try_super_fold_with(self);
 186         self.universes.pop();
 187         t
 188     }
 189
 190     #[instrument(level = "debug", skip(self))]
 191     fn try_fold_ty(&mut self, ty: Ty<'tcx>) -> Result<Ty<'tcx>, Self::Error> {
 192         if !needs_normalization(&ty, self.param_env.reveal()) {
 193             return Ok(ty);
 194         }
 195
 196         if let Some(ty) = self.cache.get(&ty) {
 197             return Ok(*ty);
 198         }
 199
 200         // See note in `rustc_trait_selection::traits::project` about why we
 201         // wait to fold the substs.
 202
 203         // Wrap this in a closure so we don't accidentally return from the outer function
 204         let res = match *ty.kind() {
 205             // This is really important. While we *can* handle this, this has
 206             // severe performance implications for large opaque types with
 207             // late-bound regions. See `issue-88862` benchmark.
 208             ty::Alias(ty::Opaque, ty::AliasTy { def_id, substs, .. })
 209                 if !substs.has_escaping_bound_vars() =>
 210             {
 211                 // Only normalize `impl Trait` outside of type inference, 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_fold_with(self)?;
 217                         let recursion_limit = self.interner().recursion_limit();
 218                         if !recursion_limit.value_within_limit(self.anon_depth) {
 219                             // A closure or generator may have itself as in its upvars.
 220                             // This should be checked handled by the recursion check for opaque
 221                             // types, but we may end up here before that check can happen.
 222                             // In that case, we delay a bug to mark the trip, and continue without
 223                             // revealing the opaque.
 224                             self.infcx
 225                                 .err_ctxt()
 226                                 .build_overflow_error(&ty, self.cause.span, true)
 227                                 .delay_as_bug();
 228                             return ty.try_super_fold_with(self);
 229                         }
 230
 231                         let generic_ty = self.interner().type_of(def_id);
 232                         let concrete_ty = generic_ty.subst(self.interner(), substs);
 233                         self.anon_depth += 1;
 234                         if concrete_ty == ty {
 235                             bug!(
 236                                 "infinite recursion generic_ty: {:#?}, substs: {:#?}, \
 237                                  concrete_ty: {:#?}, ty: {:#?}",
 238                                 generic_ty,
 239                                 substs,
 240                                 concrete_ty,
 241                                 ty
 242                             );
 243                         }
 244                         let folded_ty = ensure_sufficient_stack(|| self.try_fold_ty(concrete_ty));
 245                         self.anon_depth -= 1;
 246                         folded_ty?
 247                     }
 248                 }
 249             }
 250
 251             ty::Alias(ty::Projection, data) if !data.has_escaping_bound_vars() => {
 252                 // This branch is just an optimization: when we don't have escaping bound vars,
 253                 // we don't need to replace them with placeholders (see branch below).
 254
 255                 let tcx = self.infcx.tcx;
 256                 let data = data.try_fold_with(self)?;
 257
 258                 let mut orig_values = OriginalQueryValues::default();
 259                 // HACK(matthewjasper) `'static` is special-cased in selection,
 260                 // so we cannot canonicalize it.
 261                 let c_data = self
 262                     .infcx
 263                     .canonicalize_query_keep_static(self.param_env.and(data), &mut orig_values);
 264                 debug!("QueryNormalizer: c_data = {:#?}", c_data);
 265                 debug!("QueryNormalizer: orig_values = {:#?}", orig_values);
 266                 let result = tcx.normalize_projection_ty(c_data)?;
 267                 // We don't expect ambiguity.
 268                 if result.is_ambiguous() {
 269                     // Rustdoc normalizes possibly not well-formed types, so only
 270                     // treat this as a bug if we're not in rustdoc.
 271                     if !tcx.sess.opts.actually_rustdoc {
 272                         tcx.sess.delay_span_bug(
 273                             DUMMY_SP,
 274                             format!("unexpected ambiguity: {:?} {:?}", c_data, result),
 275                         );
 276                     }
 277                     return Err(NoSolution);
 278                 }
 279                 let InferOk { value: result, obligations } =
 280                     self.infcx.instantiate_query_response_and_region_obligations(
 281                         self.cause,
 282                         self.param_env,
 283                         &orig_values,
 284                         result,
 285                     )?;
 286                 debug!("QueryNormalizer: result = {:#?}", result);
 287                 debug!("QueryNormalizer: obligations = {:#?}", obligations);
 288                 self.obligations.extend(obligations);
 289
 290                 let res = result.normalized_ty;
 291                 // `tcx.normalize_projection_ty` may normalize to a type that still has
 292                 // unevaluated consts, so keep normalizing here if that's the case.
 293                 if res != ty && res.has_type_flags(ty::TypeFlags::HAS_CT_PROJECTION) {
 294                     res.try_super_fold_with(self)?
 295                 } else {
 296                     res
 297                 }
 298             }
 299
 300             ty::Alias(ty::Projection, data) => {
 301                 // See note in `rustc_trait_selection::traits::project`
 302
 303                 let tcx = self.infcx.tcx;
 304                 let infcx = self.infcx;
 305                 let (data, mapped_regions, mapped_types, mapped_consts) =
 306                     BoundVarReplacer::replace_bound_vars(infcx, &mut self.universes, data);
 307                 let data = data.try_fold_with(self)?;
 308
 309                 let mut orig_values = OriginalQueryValues::default();
 310                 // HACK(matthewjasper) `'static` is special-cased in selection,
 311                 // so we cannot canonicalize it.
 312                 let c_data = self
 313                     .infcx
 314                     .canonicalize_query_keep_static(self.param_env.and(data), &mut orig_values);
 315                 debug!("QueryNormalizer: c_data = {:#?}", c_data);
 316                 debug!("QueryNormalizer: orig_values = {:#?}", orig_values);
 317                 let result = tcx.normalize_projection_ty(c_data)?;
 318                 // We don't expect ambiguity.
 319                 if result.is_ambiguous() {
 320                     // Rustdoc normalizes possibly not well-formed types, so only
 321                     // treat this as a bug if we're not in rustdoc.
 322                     if !tcx.sess.opts.actually_rustdoc {
 323                         tcx.sess.delay_span_bug(
 324                             DUMMY_SP,
 325                             format!("unexpected ambiguity: {:?} {:?}", c_data, result),
 326                         );
 327                     }
 328                     return Err(NoSolution);
 329                 }
 330                 let InferOk { value: result, obligations } =
 331                     self.infcx.instantiate_query_response_and_region_obligations(
 332                         self.cause,
 333                         self.param_env,
 334                         &orig_values,
 335                         result,
 336                     )?;
 337                 debug!("QueryNormalizer: result = {:#?}", result);
 338                 debug!("QueryNormalizer: obligations = {:#?}", obligations);
 339                 self.obligations.extend(obligations);
 340                 let res = PlaceholderReplacer::replace_placeholders(
 341                     infcx,
 342                     mapped_regions,
 343                     mapped_types,
 344                     mapped_consts,
 345                     &self.universes,
 346                     result.normalized_ty,
 347                 );
 348                 // `tcx.normalize_projection_ty` may normalize to a type that still has
 349                 // unevaluated consts, so keep normalizing here if that's the case.
 350                 if res != ty && res.has_type_flags(ty::TypeFlags::HAS_CT_PROJECTION) {
 351                     res.try_super_fold_with(self)?
 352                 } else {
 353                     res
 354                 }
 355             }
 356
 357             _ => ty.try_super_fold_with(self)?,
 358         };
 359
 360         self.cache.insert(ty, res);
 361         Ok(res)
 362     }
 363
 364     fn try_fold_const(
 365         &mut self,
 366         constant: ty::Const<'tcx>,
 367     ) -> Result<ty::Const<'tcx>, Self::Error> {
 368         if !needs_normalization(&constant, self.param_env.reveal()) {
 369             return Ok(constant);
 370         }
 371
 372         let constant = constant.try_super_fold_with(self)?;
 373         debug!(?constant, ?self.param_env);
 374         Ok(crate::traits::project::with_replaced_escaping_bound_vars(
 375             self.infcx,
 376             &mut self.universes,
 377             constant,
 378             |constant| constant.eval(self.infcx.tcx, self.param_env),
 379         ))
 380     }
 381
 382     #[inline]
 383     fn try_fold_predicate(
 384         &mut self,
 385         p: ty::Predicate<'tcx>,
 386     ) -> Result<ty::Predicate<'tcx>, Self::Error> {
 387         if p.allow_normalization() && needs_normalization(&p, self.param_env.reveal()) {
 388             p.try_super_fold_with(self)
 389         } else {
 390             Ok(p)
 391         }
 392     }
 393 }