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::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};
19 use std::ops::ControlFlow;
21 use super::NoSolution;
23 pub use rustc_middle::traits::query::NormalizationResult;
25 pub trait AtExt<'tcx> {
26 fn normalize<T>(&self, value: T) -> Result<Normalized<'tcx, T>, NoSolution>
28 T: TypeFoldable<'tcx>;
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.
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).
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>
47 T: TypeFoldable<'tcx>,
50 "normalize::<{}>(value={:?}, param_env={:?})",
51 std::any::type_name::<T>(),
55 if !needs_normalization(&value, self.param_env.reveal()) {
56 return Ok(Normalized { value, obligations: vec![] });
59 let mut normalizer = QueryNormalizer {
62 param_env: self.param_env,
64 cache: SsoHashMap::new(),
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.
74 // Here, we just add the universes that we *would* have created had we passed through the binders.
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() {
81 MaxEscapingBoundVarVisitor { outer_index: ty::INNERMOST, escaping: 0 };
82 value.visit_with(&mut max_visitor);
83 if max_visitor.escaping > 0 {
84 normalizer.universes.extend((0..max_visitor.escaping).map(|_| None));
87 let result = value.try_fold_with(&mut normalizer);
89 "normalize::<{}>: result={:?} with {} obligations",
90 std::any::type_name::<T>(),
92 normalizer.obligations.len(),
95 "normalize::<{}>: obligations={:?}",
96 std::any::type_name::<T>(),
97 normalizer.obligations,
99 result.map(|value| Normalized { value, obligations: normalizer.obligations })
103 /// Visitor to find the maximum escaping bound var
104 struct MaxEscapingBoundVarVisitor {
105 // The index which would count as escaping
106 outer_index: ty::DebruijnIndex,
110 impl<'tcx> TypeVisitor<'tcx> for MaxEscapingBoundVarVisitor {
111 fn visit_binder<T: TypeFoldable<'tcx>>(
113 t: &ty::Binder<'tcx, T>,
114 ) -> ControlFlow<Self::BreakTy> {
115 self.outer_index.shift_in(1);
116 let result = t.super_visit_with(self);
117 self.outer_index.shift_out(1);
122 fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
123 if t.outer_exclusive_binder() > self.outer_index {
126 .max(t.outer_exclusive_binder().as_usize() - self.outer_index.as_usize());
128 ControlFlow::CONTINUE
132 fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
134 ty::ReLateBound(debruijn, _) if debruijn > self.outer_index => {
136 self.escaping.max(debruijn.as_usize() - self.outer_index.as_usize());
140 ControlFlow::CONTINUE
143 fn visit_const(&mut self, ct: &'tcx ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
145 ty::ConstKind::Bound(debruijn, _) if debruijn >= self.outer_index => {
147 self.escaping.max(debruijn.as_usize() - self.outer_index.as_usize());
148 ControlFlow::CONTINUE
150 _ => ct.super_visit_with(self),
155 struct QueryNormalizer<'cx, 'tcx> {
156 infcx: &'cx InferCtxt<'cx, 'tcx>,
157 cause: &'cx ObligationCause<'tcx>,
158 param_env: ty::ParamEnv<'tcx>,
159 obligations: Vec<PredicateObligation<'tcx>>,
160 cache: SsoHashMap<Ty<'tcx>, Ty<'tcx>>,
162 universes: Vec<Option<ty::UniverseIndex>>,
165 impl<'cx, 'tcx> TypeFolder<'tcx> for QueryNormalizer<'cx, 'tcx> {
166 type Error = NoSolution;
168 fn tcx<'c>(&'c self) -> TyCtxt<'tcx> {
173 impl<'cx, 'tcx> FallibleTypeFolder<'tcx> for QueryNormalizer<'cx, 'tcx> {
174 fn try_fold_binder<T: TypeFoldable<'tcx>>(
176 t: ty::Binder<'tcx, T>,
177 ) -> Result<ty::Binder<'tcx, T>, Self::Error> {
178 self.universes.push(None);
179 let t = t.try_super_fold_with(self);
180 self.universes.pop();
184 #[instrument(level = "debug", skip(self))]
185 fn try_fold_ty(&mut self, ty: Ty<'tcx>) -> Result<Ty<'tcx>, Self::Error> {
186 if !needs_normalization(&ty, self.param_env.reveal()) {
190 if let Some(ty) = self.cache.get(&ty) {
194 // See note in `rustc_trait_selection::traits::project` about why we
195 // wait to fold the substs.
197 // Wrap this in a closure so we don't accidentally return from the outer function
198 let res = (|| match *ty.kind() {
199 // This is really important. While we *can* handle this, this has
200 // severe performance implications for large opaque types with
201 // late-bound regions. See `issue-88862` benchmark.
202 ty::Opaque(def_id, substs) if !substs.has_escaping_bound_vars() => {
203 // Only normalize `impl Trait` after type-checking, usually in codegen.
204 match self.param_env.reveal() {
205 Reveal::UserFacing => ty.try_super_fold_with(self),
208 let substs = substs.try_super_fold_with(self)?;
209 let recursion_limit = self.tcx().recursion_limit();
210 if !recursion_limit.value_within_limit(self.anon_depth) {
211 let obligation = Obligation::with_depth(
217 self.infcx.report_overflow_error(&obligation, true);
220 let generic_ty = self.tcx().type_of(def_id);
221 let concrete_ty = generic_ty.subst(self.tcx(), substs);
222 self.anon_depth += 1;
223 if concrete_ty == ty {
225 "infinite recursion generic_ty: {:#?}, substs: {:#?}, \
226 concrete_ty: {:#?}, ty: {:#?}",
233 let folded_ty = ensure_sufficient_stack(|| self.try_fold_ty(concrete_ty));
234 self.anon_depth -= 1;
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).
244 let tcx = self.infcx.tcx;
245 let data = data.try_super_fold_with(self)?;
247 let mut orig_values = OriginalQueryValues::default();
248 // HACK(matthewjasper) `'static` is special-cased in selection,
249 // so we cannot canonicalize it.
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 return Err(NoSolution);
260 let InferOk { value: result, obligations } =
261 self.infcx.instantiate_query_response_and_region_obligations(
267 debug!("QueryNormalizer: result = {:#?}", result);
268 debug!("QueryNormalizer: obligations = {:#?}", obligations);
269 self.obligations.extend(obligations);
270 Ok(result.normalized_ty)
273 ty::Projection(data) => {
274 // See note in `rustc_trait_selection::traits::project`
276 let tcx = self.infcx.tcx;
277 let infcx = self.infcx;
278 let (data, mapped_regions, mapped_types, mapped_consts) =
279 crate::traits::project::BoundVarReplacer::replace_bound_vars(
284 let data = data.try_super_fold_with(self)?;
286 let mut orig_values = OriginalQueryValues::default();
287 // HACK(matthewjasper) `'static` is special-cased in selection,
288 // so we cannot canonicalize it.
291 .canonicalize_query_keep_static(self.param_env.and(data), &mut orig_values);
292 debug!("QueryNormalizer: c_data = {:#?}", c_data);
293 debug!("QueryNormalizer: orig_values = {:#?}", orig_values);
294 let result = tcx.normalize_projection_ty(c_data)?;
295 // We don't expect ambiguity.
296 if result.is_ambiguous() {
297 return Err(NoSolution);
299 let InferOk { value: result, obligations } =
300 self.infcx.instantiate_query_response_and_region_obligations(
306 debug!("QueryNormalizer: result = {:#?}", result);
307 debug!("QueryNormalizer: obligations = {:#?}", obligations);
308 self.obligations.extend(obligations);
309 Ok(crate::traits::project::PlaceholderReplacer::replace_placeholders(
315 result.normalized_ty,
319 _ => ty.try_super_fold_with(self),
321 self.cache.insert(ty, res);
327 constant: &'tcx ty::Const<'tcx>,
328 ) -> Result<&'tcx ty::Const<'tcx>, Self::Error> {
329 let constant = constant.try_super_fold_with(self)?;
330 Ok(constant.eval(self.infcx.tcx, self.param_env))
333 fn try_fold_mir_const(
335 constant: mir::ConstantKind<'tcx>,
336 ) -> Result<mir::ConstantKind<'tcx>, Self::Error> {
337 constant.try_super_fold_with(self)