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::{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::ty::fold::{FallibleTypeFolder, TypeFoldable, TypeSuperFoldable};
  15 use rustc_middle::ty::visit::{TypeSuperVisitable, TypeVisitable};
  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     fn query_normalize<T>(&self, value: T) -> Result<Normalized<'tcx, T>, NoSolution>
  27     where
  28         T: TypeFoldable<'tcx>;
  29 }
  30
  31 impl<'cx, 'tcx> QueryNormalizeExt<'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 query_normalize<T>(&self, value: T) -> Result<Normalized<'tcx, T>, NoSolution>
  46     where
  47         T: TypeFoldable<'tcx>,
  48     {
  49         debug!(
  50             "normalize::<{}>(value={:?}, param_env={:?}, cause={:?})",
  51             std::any::type_name::<T>(),
  52             value,
  53             self.param_env,
  54             self.cause,
  55         );
  56         if !needs_normalization(&value, self.param_env.reveal()) {
  57             return Ok(Normalized { value, obligations: vec![] });
  58         }
  59
  60         let mut normalizer = QueryNormalizer {
  61             infcx: self.infcx,
  62             cause: self.cause,
  63             param_env: self.param_env,
  64             obligations: vec![],
  65             cache: SsoHashMap::new(),
  66             anon_depth: 0,
  67             universes: vec![],
  68         };
  69
  70         // This is actually a consequence by the way `normalize_erasing_regions` works currently.
  71         // Because it needs to call the `normalize_generic_arg_after_erasing_regions`, it folds
  72         // through tys and consts in a `TypeFoldable`. Importantly, it skips binders, leaving us
  73         // with trying to normalize with escaping bound vars.
  74         //
  75         // Here, we just add the universes that we *would* have created had we passed through the binders.
  76         //
  77         // We *could* replace escaping bound vars eagerly here, but it doesn't seem really necessary.
  78         // The rest of the code is already set up to be lazy about replacing bound vars,
  79         // and only when we actually have to normalize.
  80         if value.has_escaping_bound_vars() {
  81             let mut max_visitor =
  82                 MaxEscapingBoundVarVisitor { outer_index: ty::INNERMOST, escaping: 0 };
  83             value.visit_with(&mut max_visitor);
  84             if max_visitor.escaping > 0 {
  85                 normalizer.universes.extend((0..max_visitor.escaping).map(|_| None));
  86             }
  87         }
  88         let result = value.try_fold_with(&mut normalizer);
  89         info!(
  90             "normalize::<{}>: result={:?} with {} obligations",
  91             std::any::type_name::<T>(),
  92             result,
  93             normalizer.obligations.len(),
  94         );
  95         debug!(
  96             "normalize::<{}>: obligations={:?}",
  97             std::any::type_name::<T>(),
  98             normalizer.obligations,
  99         );
 100         result.map(|value| Normalized { value, obligations: normalizer.obligations })
 101     }
 102 }
 103
 104 // Visitor to find the maximum escaping bound var
 105 struct MaxEscapingBoundVarVisitor {
 106     // The index which would count as escaping
 107     outer_index: ty::DebruijnIndex,
 108     escaping: usize,
 109 }
 110
 111 impl<'tcx> TypeVisitor<'tcx> for MaxEscapingBoundVarVisitor {
 112     fn visit_binder<T: TypeVisitable<'tcx>>(
 113         &mut self,
 114         t: &ty::Binder<'tcx, T>,
 115     ) -> ControlFlow<Self::BreakTy> {
 116         self.outer_index.shift_in(1);
 117         let result = t.super_visit_with(self);
 118         self.outer_index.shift_out(1);
 119         result
 120     }
 121
 122     #[inline]
 123     fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 124         if t.outer_exclusive_binder() > self.outer_index {
 125             self.escaping = self
 126                 .escaping
 127                 .max(t.outer_exclusive_binder().as_usize() - self.outer_index.as_usize());
 128         }
 129         ControlFlow::CONTINUE
 130     }
 131
 132     #[inline]
 133     fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
 134         match *r {
 135             ty::ReLateBound(debruijn, _) if debruijn > self.outer_index => {
 136                 self.escaping =
 137                     self.escaping.max(debruijn.as_usize() - self.outer_index.as_usize());
 138             }
 139             _ => {}
 140         }
 141         ControlFlow::CONTINUE
 142     }
 143
 144     fn visit_const(&mut self, ct: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
 145         match ct.kind() {
 146             ty::ConstKind::Bound(debruijn, _) if debruijn >= self.outer_index => {
 147                 self.escaping =
 148                     self.escaping.max(debruijn.as_usize() - self.outer_index.as_usize());
 149                 ControlFlow::CONTINUE
 150             }
 151             _ => ct.super_visit_with(self),
 152         }
 153     }
 154 }
 155
 156 struct QueryNormalizer<'cx, 'tcx> {
 157     infcx: &'cx InferCtxt<'tcx>,
 158     cause: &'cx ObligationCause<'tcx>,
 159     param_env: ty::ParamEnv<'tcx>,
 160     obligations: Vec<PredicateObligation<'tcx>>,
 161     cache: SsoHashMap<Ty<'tcx>, Ty<'tcx>>,
 162     anon_depth: usize,
 163     universes: Vec<Option<ty::UniverseIndex>>,
 164 }
 165
 166 impl<'cx, 'tcx> FallibleTypeFolder<'tcx> for QueryNormalizer<'cx, 'tcx> {
 167     type Error = NoSolution;
 168
 169     fn tcx<'c>(&'c self) -> TyCtxt<'tcx> {
 170         self.infcx.tcx
 171     }
 172
 173     fn try_fold_binder<T: TypeFoldable<'tcx>>(
 174         &mut self,
 175         t: ty::Binder<'tcx, T>,
 176     ) -> Result<ty::Binder<'tcx, T>, Self::Error> {
 177         self.universes.push(None);
 178         let t = t.try_super_fold_with(self);
 179         self.universes.pop();
 180         t
 181     }
 182
 183     #[instrument(level = "debug", skip(self))]
 184     fn try_fold_ty(&mut self, ty: Ty<'tcx>) -> Result<Ty<'tcx>, Self::Error> {
 185         if !needs_normalization(&ty, self.param_env.reveal()) {
 186             return Ok(ty);
 187         }
 188
 189         if let Some(ty) = self.cache.get(&ty) {
 190             return Ok(*ty);
 191         }
 192
 193         // See note in `rustc_trait_selection::traits::project` about why we
 194         // wait to fold the substs.
 195
 196         // Wrap this in a closure so we don't accidentally return from the outer function
 197         let res = (|| match *ty.kind() {
 198             // This is really important. While we *can* handle this, this has
 199             // severe performance implications for large opaque types with
 200             // late-bound regions. See `issue-88862` benchmark.
 201             ty::Opaque(def_id, substs) if !substs.has_escaping_bound_vars() => {
 202                 // Only normalize `impl Trait` outside of type inference, usually in codegen.
 203                 match self.param_env.reveal() {
 204                     Reveal::UserFacing => ty.try_super_fold_with(self),
 205
 206                     Reveal::All => {
 207                         let substs = substs.try_fold_with(self)?;
 208                         let recursion_limit = self.tcx().recursion_limit();
 209                         if !recursion_limit.value_within_limit(self.anon_depth) {
 210                             let obligation = Obligation::with_depth(
 211                                 self.tcx(),
 212                                 self.cause.clone(),
 213                                 recursion_limit.0,
 214                                 self.param_env,
 215                                 ty,
 216                             );
 217                             self.infcx.err_ctxt().report_overflow_error(&obligation, true);
 218                         }
 219
 220                         let generic_ty = self.tcx().bound_type_of(def_id);
 221                         let concrete_ty = generic_ty.subst(self.tcx(), substs);
 222                         self.anon_depth += 1;
 223                         if concrete_ty == ty {
 224                             bug!(
 225                                 "infinite recursion generic_ty: {:#?}, substs: {:#?}, \
 226                                  concrete_ty: {:#?}, ty: {:#?}",
 227                                 generic_ty,
 228                                 substs,
 229                                 concrete_ty,
 230                                 ty
 231                             );
 232                         }
 233                         let folded_ty = ensure_sufficient_stack(|| self.try_fold_ty(concrete_ty));
 234                         self.anon_depth -= 1;
 235                         folded_ty
 236                     }
 237                 }
 238             }
 239
 240             ty::Projection(data) if !data.has_escaping_bound_vars() => {
 241                 // This branch is just an optimization: when we don't have escaping bound vars,
 242                 // we don't need to replace them with placeholders (see branch below).
 243
 244                 let tcx = self.infcx.tcx;
 245                 let data = data.try_fold_with(self)?;
 246
 247                 let mut orig_values = OriginalQueryValues::default();
 248                 // HACK(matthewjasper) `'static` is special-cased in selection,
 249                 // so we cannot canonicalize it.
 250                 let c_data = self
 251                     .infcx
 252                     .canonicalize_query_keep_static(self.param_env.and(data), &mut orig_values);
 253                 debug!("QueryNormalizer: c_data = {:#?}", c_data);
 254                 debug!("QueryNormalizer: orig_values = {:#?}", orig_values);
 255                 let result = tcx.normalize_projection_ty(c_data)?;
 256                 // We don't expect ambiguity.
 257                 if result.is_ambiguous() {
 258                     // Rustdoc normalizes possibly not well-formed types, so only
 259                     // treat this as a bug if we're not in rustdoc.
 260                     if !tcx.sess.opts.actually_rustdoc {
 261                         tcx.sess.delay_span_bug(
 262                             DUMMY_SP,
 263                             format!("unexpected ambiguity: {:?} {:?}", c_data, result),
 264                         );
 265                     }
 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
 279                 let res = result.normalized_ty;
 280                 // `tcx.normalize_projection_ty` may normalize to a type that still has
 281                 // unevaluated consts, so keep normalizing here if that's the case.
 282                 if res != ty && res.has_type_flags(ty::TypeFlags::HAS_CT_PROJECTION) {
 283                     Ok(res.try_super_fold_with(self)?)
 284                 } else {
 285                     Ok(res)
 286                 }
 287             }
 288
 289             ty::Projection(data) => {
 290                 // See note in `rustc_trait_selection::traits::project`
 291
 292                 let tcx = self.infcx.tcx;
 293                 let infcx = self.infcx;
 294                 let (data, mapped_regions, mapped_types, mapped_consts) =
 295                     BoundVarReplacer::replace_bound_vars(infcx, &mut self.universes, data);
 296                 let data = data.try_fold_with(self)?;
 297
 298                 let mut orig_values = OriginalQueryValues::default();
 299                 // HACK(matthewjasper) `'static` is special-cased in selection,
 300                 // so we cannot canonicalize it.
 301                 let c_data = self
 302                     .infcx
 303                     .canonicalize_query_keep_static(self.param_env.and(data), &mut orig_values);
 304                 debug!("QueryNormalizer: c_data = {:#?}", c_data);
 305                 debug!("QueryNormalizer: orig_values = {:#?}", orig_values);
 306                 let result = tcx.normalize_projection_ty(c_data)?;
 307                 // We don't expect ambiguity.
 308                 if result.is_ambiguous() {
 309                     // Rustdoc normalizes possibly not well-formed types, so only
 310                     // treat this as a bug if we're not in rustdoc.
 311                     if !tcx.sess.opts.actually_rustdoc {
 312                         tcx.sess.delay_span_bug(
 313                             DUMMY_SP,
 314                             format!("unexpected ambiguity: {:?} {:?}", c_data, result),
 315                         );
 316                     }
 317                     return Err(NoSolution);
 318                 }
 319                 let InferOk { value: result, obligations } =
 320                     self.infcx.instantiate_query_response_and_region_obligations(
 321                         self.cause,
 322                         self.param_env,
 323                         &orig_values,
 324                         result,
 325                     )?;
 326                 debug!("QueryNormalizer: result = {:#?}", result);
 327                 debug!("QueryNormalizer: obligations = {:#?}", obligations);
 328                 self.obligations.extend(obligations);
 329                 let res = PlaceholderReplacer::replace_placeholders(
 330                     infcx,
 331                     mapped_regions,
 332                     mapped_types,
 333                     mapped_consts,
 334                     &self.universes,
 335                     result.normalized_ty,
 336                 );
 337                 // `tcx.normalize_projection_ty` may normalize to a type that still has
 338                 // unevaluated consts, so keep normalizing here if that's the case.
 339                 if res != ty && res.has_type_flags(ty::TypeFlags::HAS_CT_PROJECTION) {
 340                     Ok(res.try_super_fold_with(self)?)
 341                 } else {
 342                     Ok(res)
 343                 }
 344             }
 345
 346             _ => ty.try_super_fold_with(self),
 347         })()?;
 348
 349         self.cache.insert(ty, res);
 350         Ok(res)
 351     }
 352
 353     fn try_fold_const(
 354         &mut self,
 355         constant: ty::Const<'tcx>,
 356     ) -> Result<ty::Const<'tcx>, Self::Error> {
 357         if !needs_normalization(&constant, self.param_env.reveal()) {
 358             return Ok(constant);
 359         }
 360
 361         let constant = constant.try_super_fold_with(self)?;
 362         debug!(?constant, ?self.param_env);
 363         Ok(crate::traits::project::with_replaced_escaping_bound_vars(
 364             self.infcx,
 365             &mut self.universes,
 366             constant,
 367             |constant| constant.eval(self.infcx.tcx, self.param_env),
 368         ))
 369     }
 370
 371     #[inline]
 372     fn try_fold_predicate(
 373         &mut self,
 374         p: ty::Predicate<'tcx>,
 375     ) -> Result<ty::Predicate<'tcx>, Self::Error> {
 376         if p.allow_normalization() && needs_normalization(&p, self.param_env.reveal()) {
 377             p.try_super_fold_with(self)
 378         } else {
 379             Ok(p)
 380         }
 381     }
 382 }