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.
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};
16 use rustc_middle::ty::{self, Ty, TyCtxt, TypeVisitor};
17 use rustc_span::DUMMY_SP;
19 use std::ops::ControlFlow;
21 use super::NoSolution;
23 pub use rustc_middle::traits::query::NormalizationResult;
25 pub trait QueryNormalizeExt<'tcx> {
26 /// Normalize a value using the `QueryNormalizer`.
28 /// This normalization should *only* be used when the projection does not
29 /// have possible ambiguity or may not be well-formed.
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>
35 T: TypeFoldable<'tcx>;
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.
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).
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>
54 T: TypeFoldable<'tcx>,
57 "normalize::<{}>(value={:?}, param_env={:?}, cause={:?})",
58 std::any::type_name::<T>(),
63 if !needs_normalization(&value, self.param_env.reveal()) {
64 return Ok(Normalized { value, obligations: vec![] });
67 let mut normalizer = QueryNormalizer {
70 param_env: self.param_env,
72 cache: SsoHashMap::new(),
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.
82 // Here, we just add the universes that we *would* have created had we passed through the binders.
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() {
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));
95 let result = value.try_fold_with(&mut normalizer);
97 "normalize::<{}>: result={:?} with {} obligations",
98 std::any::type_name::<T>(),
100 normalizer.obligations.len(),
103 "normalize::<{}>: obligations={:?}",
104 std::any::type_name::<T>(),
105 normalizer.obligations,
107 result.map(|value| Normalized { value, obligations: normalizer.obligations })
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,
118 impl<'tcx> TypeVisitor<'tcx> for MaxEscapingBoundVarVisitor {
119 fn visit_binder<T: TypeVisitable<'tcx>>(
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);
130 fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
131 if t.outer_exclusive_binder() > self.outer_index {
134 .max(t.outer_exclusive_binder().as_usize() - self.outer_index.as_usize());
136 ControlFlow::Continue(())
140 fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
142 ty::ReLateBound(debruijn, _) if debruijn > self.outer_index => {
144 self.escaping.max(debruijn.as_usize() - self.outer_index.as_usize());
148 ControlFlow::Continue(())
151 fn visit_const(&mut self, ct: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
153 ty::ConstKind::Bound(debruijn, _) if debruijn >= self.outer_index => {
155 self.escaping.max(debruijn.as_usize() - self.outer_index.as_usize());
156 ControlFlow::Continue(())
158 _ => ct.super_visit_with(self),
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>>,
170 universes: Vec<Option<ty::UniverseIndex>>,
173 impl<'cx, 'tcx> FallibleTypeFolder<'tcx> for QueryNormalizer<'cx, 'tcx> {
174 type Error = NoSolution;
176 fn tcx<'c>(&'c self) -> TyCtxt<'tcx> {
180 fn try_fold_binder<T: TypeFoldable<'tcx>>(
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();
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()) {
196 if let Some(ty) = self.cache.get(&ty) {
200 // See note in `rustc_trait_selection::traits::project` about why we
201 // wait to fold the substs.
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() =>
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),
216 let substs = substs.try_fold_with(self)?;
217 let recursion_limit = self.tcx().recursion_limit();
218 if !recursion_limit.value_within_limit(self.anon_depth) {
219 self.infcx.err_ctxt().report_overflow_error(
227 let generic_ty = self.tcx().bound_type_of(def_id);
228 let concrete_ty = generic_ty.subst(self.tcx(), substs);
229 self.anon_depth += 1;
230 if concrete_ty == ty {
232 "infinite recursion generic_ty: {:#?}, substs: {:#?}, \
233 concrete_ty: {:#?}, ty: {:#?}",
240 let folded_ty = ensure_sufficient_stack(|| self.try_fold_ty(concrete_ty));
241 self.anon_depth -= 1;
247 ty::Alias(ty::Projection, data) if !data.has_escaping_bound_vars() => {
248 // This branch is just an optimization: when we don't have escaping bound vars,
249 // we don't need to replace them with placeholders (see branch below).
251 let tcx = self.infcx.tcx;
252 let data = data.try_fold_with(self)?;
254 let mut orig_values = OriginalQueryValues::default();
255 // HACK(matthewjasper) `'static` is special-cased in selection,
256 // so we cannot canonicalize it.
259 .canonicalize_query_keep_static(self.param_env.and(data), &mut orig_values);
260 debug!("QueryNormalizer: c_data = {:#?}", c_data);
261 debug!("QueryNormalizer: orig_values = {:#?}", orig_values);
262 let result = tcx.normalize_projection_ty(c_data)?;
263 // We don't expect ambiguity.
264 if result.is_ambiguous() {
265 // Rustdoc normalizes possibly not well-formed types, so only
266 // treat this as a bug if we're not in rustdoc.
267 if !tcx.sess.opts.actually_rustdoc {
268 tcx.sess.delay_span_bug(
270 format!("unexpected ambiguity: {:?} {:?}", c_data, result),
273 return Err(NoSolution);
275 let InferOk { value: result, obligations } =
276 self.infcx.instantiate_query_response_and_region_obligations(
282 debug!("QueryNormalizer: result = {:#?}", result);
283 debug!("QueryNormalizer: obligations = {:#?}", obligations);
284 self.obligations.extend(obligations);
286 let res = result.normalized_ty;
287 // `tcx.normalize_projection_ty` may normalize to a type that still has
288 // unevaluated consts, so keep normalizing here if that's the case.
289 if res != ty && res.has_type_flags(ty::TypeFlags::HAS_CT_PROJECTION) {
290 Ok(res.try_super_fold_with(self)?)
296 ty::Alias(ty::Projection, data) => {
297 // See note in `rustc_trait_selection::traits::project`
299 let tcx = self.infcx.tcx;
300 let infcx = self.infcx;
301 let (data, mapped_regions, mapped_types, mapped_consts) =
302 BoundVarReplacer::replace_bound_vars(infcx, &mut self.universes, data);
303 let data = data.try_fold_with(self)?;
305 let mut orig_values = OriginalQueryValues::default();
306 // HACK(matthewjasper) `'static` is special-cased in selection,
307 // so we cannot canonicalize it.
310 .canonicalize_query_keep_static(self.param_env.and(data), &mut orig_values);
311 debug!("QueryNormalizer: c_data = {:#?}", c_data);
312 debug!("QueryNormalizer: orig_values = {:#?}", orig_values);
313 let result = tcx.normalize_projection_ty(c_data)?;
314 // We don't expect ambiguity.
315 if result.is_ambiguous() {
316 // Rustdoc normalizes possibly not well-formed types, so only
317 // treat this as a bug if we're not in rustdoc.
318 if !tcx.sess.opts.actually_rustdoc {
319 tcx.sess.delay_span_bug(
321 format!("unexpected ambiguity: {:?} {:?}", c_data, result),
324 return Err(NoSolution);
326 let InferOk { value: result, obligations } =
327 self.infcx.instantiate_query_response_and_region_obligations(
333 debug!("QueryNormalizer: result = {:#?}", result);
334 debug!("QueryNormalizer: obligations = {:#?}", obligations);
335 self.obligations.extend(obligations);
336 let res = PlaceholderReplacer::replace_placeholders(
342 result.normalized_ty,
344 // `tcx.normalize_projection_ty` may normalize to a type that still has
345 // unevaluated consts, so keep normalizing here if that's the case.
346 if res != ty && res.has_type_flags(ty::TypeFlags::HAS_CT_PROJECTION) {
347 Ok(res.try_super_fold_with(self)?)
353 _ => ty.try_super_fold_with(self),
356 self.cache.insert(ty, res);
362 constant: ty::Const<'tcx>,
363 ) -> Result<ty::Const<'tcx>, Self::Error> {
364 if !needs_normalization(&constant, self.param_env.reveal()) {
368 let constant = constant.try_super_fold_with(self)?;
369 debug!(?constant, ?self.param_env);
370 Ok(crate::traits::project::with_replaced_escaping_bound_vars(
374 |constant| constant.eval(self.infcx.tcx, self.param_env),
379 fn try_fold_predicate(
381 p: ty::Predicate<'tcx>,
382 ) -> Result<ty::Predicate<'tcx>, Self::Error> {
383 if p.allow_normalization() && needs_normalization(&p, self.param_env.reveal()) {
384 p.try_super_fold_with(self)