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