rustc_trait_selection/traits/query/
normalize.rs

1//! Code for the 'normalization' query. This consists of a wrapper
2//! which folds deeply, invoking the underlying
3//! `normalize_canonicalized_projection` query when it encounters projections.
4
5use rustc_data_structures::sso::SsoHashMap;
6use rustc_data_structures::stack::ensure_sufficient_stack;
7use rustc_hir::def::DefKind;
8use rustc_infer::traits::PredicateObligations;
9use rustc_macros::extension;
10pub use rustc_middle::traits::query::NormalizationResult;
11use rustc_middle::ty::{
12    self, FallibleTypeFolder, Ty, TyCtxt, TypeFoldable, TypeSuperFoldable, TypeSuperVisitable,
13    TypeVisitable, TypeVisitableExt, TypeVisitor, TypingMode,
14};
15use rustc_span::DUMMY_SP;
16use tracing::{debug, info, instrument};
17
18use super::NoSolution;
19use crate::error_reporting::InferCtxtErrorExt;
20use crate::error_reporting::traits::OverflowCause;
21use crate::infer::at::At;
22use crate::infer::canonical::OriginalQueryValues;
23use crate::infer::{InferCtxt, InferOk};
24use crate::traits::normalize::needs_normalization;
25use crate::traits::{
26    BoundVarReplacer, Normalized, ObligationCause, PlaceholderReplacer, ScrubbedTraitError,
27};
28
29#[extension(pub trait QueryNormalizeExt<'tcx>)]
30impl<'a, 'tcx> At<'a, 'tcx> {
31    /// Normalize `value` in the context of the inference context,
32    /// yielding a resulting type, or an error if `value` cannot be
33    /// normalized. If you don't care about regions, you should prefer
34    /// `normalize_erasing_regions`, which is more efficient.
35    ///
36    /// If the normalization succeeds, returns back the normalized
37    /// value along with various outlives relations (in the form of
38    /// obligations that must be discharged).
39    ///
40    /// This normalization should *only* be used when the projection is well-formed and
41    /// does not have possible ambiguity (contains inference variables).
42    ///
43    /// After codegen, when lifetimes do not matter, it is preferable to instead
44    /// use [`TyCtxt::normalize_erasing_regions`], which wraps this procedure.
45    ///
46    /// N.B. Once the new solver is stabilized this method of normalization will
47    /// likely be removed as trait solver operations are already cached by the query
48    /// system making this redundant.
49    fn query_normalize<T>(self, value: T) -> Result<Normalized<'tcx, T>, NoSolution>
50    where
51        T: TypeFoldable<TyCtxt<'tcx>>,
52    {
53        debug!(
54            "normalize::<{}>(value={:?}, param_env={:?}, cause={:?})",
55            std::any::type_name::<T>(),
56            value,
57            self.param_env,
58            self.cause,
59        );
60
61        // This is actually a consequence by the way `normalize_erasing_regions` works currently.
62        // Because it needs to call the `normalize_generic_arg_after_erasing_regions`, it folds
63        // through tys and consts in a `TypeFoldable`. Importantly, it skips binders, leaving us
64        // with trying to normalize with escaping bound vars.
65        //
66        // Here, we just add the universes that we *would* have created had we passed through the binders.
67        //
68        // We *could* replace escaping bound vars eagerly here, but it doesn't seem really necessary.
69        // The rest of the code is already set up to be lazy about replacing bound vars,
70        // and only when we actually have to normalize.
71        let universes = if value.has_escaping_bound_vars() {
72            let mut max_visitor =
73                MaxEscapingBoundVarVisitor { outer_index: ty::INNERMOST, escaping: 0 };
74            value.visit_with(&mut max_visitor);
75            vec![None; max_visitor.escaping]
76        } else {
77            vec![]
78        };
79
80        if self.infcx.next_trait_solver() {
81            match crate::solve::deeply_normalize_with_skipped_universes::<_, ScrubbedTraitError<'tcx>>(
82                self, value, universes,
83            ) {
84                Ok(value) => {
85                    return Ok(Normalized { value, obligations: PredicateObligations::new() });
86                }
87                Err(_errors) => {
88                    return Err(NoSolution);
89                }
90            }
91        }
92
93        if !needs_normalization(self.infcx, &value) {
94            return Ok(Normalized { value, obligations: PredicateObligations::new() });
95        }
96
97        let mut normalizer = QueryNormalizer {
98            infcx: self.infcx,
99            cause: self.cause,
100            param_env: self.param_env,
101            obligations: PredicateObligations::new(),
102            cache: SsoHashMap::new(),
103            anon_depth: 0,
104            universes,
105        };
106
107        let result = value.try_fold_with(&mut normalizer);
108        info!(
109            "normalize::<{}>: result={:?} with {} obligations",
110            std::any::type_name::<T>(),
111            result,
112            normalizer.obligations.len(),
113        );
114        debug!(
115            "normalize::<{}>: obligations={:?}",
116            std::any::type_name::<T>(),
117            normalizer.obligations,
118        );
119        result.map(|value| Normalized { value, obligations: normalizer.obligations })
120    }
121}
122
123// Visitor to find the maximum escaping bound var
124struct MaxEscapingBoundVarVisitor {
125    // The index which would count as escaping
126    outer_index: ty::DebruijnIndex,
127    escaping: usize,
128}
129
130impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for MaxEscapingBoundVarVisitor {
131    fn visit_binder<T: TypeVisitable<TyCtxt<'tcx>>>(&mut self, t: &ty::Binder<'tcx, T>) {
132        self.outer_index.shift_in(1);
133        t.super_visit_with(self);
134        self.outer_index.shift_out(1);
135    }
136
137    #[inline]
138    fn visit_ty(&mut self, t: Ty<'tcx>) {
139        if t.outer_exclusive_binder() > self.outer_index {
140            self.escaping = self
141                .escaping
142                .max(t.outer_exclusive_binder().as_usize() - self.outer_index.as_usize());
143        }
144    }
145
146    #[inline]
147    fn visit_region(&mut self, r: ty::Region<'tcx>) {
148        match r.kind() {
149            ty::ReBound(ty::BoundVarIndexKind::Bound(debruijn), _)
150                if debruijn > self.outer_index =>
151            {
152                self.escaping =
153                    self.escaping.max(debruijn.as_usize() - self.outer_index.as_usize());
154            }
155            _ => {}
156        }
157    }
158
159    fn visit_const(&mut self, ct: ty::Const<'tcx>) {
160        if ct.outer_exclusive_binder() > self.outer_index {
161            self.escaping = self
162                .escaping
163                .max(ct.outer_exclusive_binder().as_usize() - self.outer_index.as_usize());
164        }
165    }
166}
167
168struct QueryNormalizer<'a, 'tcx> {
169    infcx: &'a InferCtxt<'tcx>,
170    cause: &'a ObligationCause<'tcx>,
171    param_env: ty::ParamEnv<'tcx>,
172    obligations: PredicateObligations<'tcx>,
173    cache: SsoHashMap<Ty<'tcx>, Ty<'tcx>>,
174    anon_depth: usize,
175    universes: Vec<Option<ty::UniverseIndex>>,
176}
177
178impl<'a, 'tcx> FallibleTypeFolder<TyCtxt<'tcx>> for QueryNormalizer<'a, 'tcx> {
179    type Error = NoSolution;
180
181    fn cx(&self) -> TyCtxt<'tcx> {
182        self.infcx.tcx
183    }
184
185    fn try_fold_binder<T: TypeFoldable<TyCtxt<'tcx>>>(
186        &mut self,
187        t: ty::Binder<'tcx, T>,
188    ) -> Result<ty::Binder<'tcx, T>, Self::Error> {
189        self.universes.push(None);
190        let t = t.try_super_fold_with(self);
191        self.universes.pop();
192        t
193    }
194
195    #[instrument(level = "debug", skip(self))]
196    fn try_fold_ty(&mut self, ty: Ty<'tcx>) -> Result<Ty<'tcx>, Self::Error> {
197        if !needs_normalization(self.infcx, &ty) {
198            return Ok(ty);
199        }
200
201        if let Some(ty) = self.cache.get(&ty) {
202            return Ok(*ty);
203        }
204
205        let (kind, data) = match *ty.kind() {
206            ty::Alias(kind, data) => (kind, data),
207            _ => {
208                let res = ty.try_super_fold_with(self)?;
209                self.cache.insert(ty, res);
210                return Ok(res);
211            }
212        };
213
214        // See note in `rustc_trait_selection::traits::project` about why we
215        // wait to fold the args.
216        let res = match kind {
217            ty::Opaque => {
218                // Only normalize `impl Trait` outside of type inference, usually in codegen.
219                match self.infcx.typing_mode() {
220                    TypingMode::Coherence
221                    | TypingMode::Analysis { .. }
222                    | TypingMode::Borrowck { .. }
223                    | TypingMode::PostBorrowckAnalysis { .. } => ty.try_super_fold_with(self)?,
224
225                    TypingMode::PostAnalysis => {
226                        let args = data.args.try_fold_with(self)?;
227                        let recursion_limit = self.cx().recursion_limit();
228
229                        if !recursion_limit.value_within_limit(self.anon_depth) {
230                            let guar = self
231                                .infcx
232                                .err_ctxt()
233                                .build_overflow_error(
234                                    OverflowCause::DeeplyNormalize(data.into()),
235                                    self.cause.span,
236                                    true,
237                                )
238                                .delay_as_bug();
239                            return Ok(Ty::new_error(self.cx(), guar));
240                        }
241
242                        let generic_ty = self.cx().type_of(data.def_id);
243                        let mut concrete_ty = generic_ty.instantiate(self.cx(), args);
244                        self.anon_depth += 1;
245                        if concrete_ty == ty {
246                            concrete_ty = Ty::new_error_with_message(
247                                self.cx(),
248                                DUMMY_SP,
249                                "recursive opaque type",
250                            );
251                        }
252                        let folded_ty = ensure_sufficient_stack(|| self.try_fold_ty(concrete_ty));
253                        self.anon_depth -= 1;
254                        folded_ty?
255                    }
256                }
257            }
258
259            ty::Projection | ty::Inherent | ty::Free => self
260                .try_fold_free_or_assoc(ty::AliasTerm::new(self.cx(), data.def_id, data.args))?
261                .expect_type(),
262        };
263
264        self.cache.insert(ty, res);
265        Ok(res)
266    }
267
268    fn try_fold_const(
269        &mut self,
270        constant: ty::Const<'tcx>,
271    ) -> Result<ty::Const<'tcx>, Self::Error> {
272        if !needs_normalization(self.infcx, &constant) {
273            return Ok(constant);
274        }
275
276        let uv = match constant.kind() {
277            ty::ConstKind::Unevaluated(uv) => uv,
278            _ => return constant.try_super_fold_with(self),
279        };
280
281        let constant = match self.cx().def_kind(uv.def) {
282            DefKind::AnonConst => crate::traits::with_replaced_escaping_bound_vars(
283                self.infcx,
284                &mut self.universes,
285                constant,
286                |constant| crate::traits::evaluate_const(&self.infcx, constant, self.param_env),
287            ),
288            _ => self
289                .try_fold_free_or_assoc(ty::AliasTerm::new(self.cx(), uv.def, uv.args))?
290                .expect_const(),
291        };
292        debug!(?constant, ?self.param_env);
293        constant.try_super_fold_with(self)
294    }
295
296    #[inline]
297    fn try_fold_predicate(
298        &mut self,
299        p: ty::Predicate<'tcx>,
300    ) -> Result<ty::Predicate<'tcx>, Self::Error> {
301        if p.allow_normalization() && needs_normalization(self.infcx, &p) {
302            p.try_super_fold_with(self)
303        } else {
304            Ok(p)
305        }
306    }
307}
308
309impl<'a, 'tcx> QueryNormalizer<'a, 'tcx> {
310    fn try_fold_free_or_assoc(
311        &mut self,
312        term: ty::AliasTerm<'tcx>,
313    ) -> Result<ty::Term<'tcx>, NoSolution> {
314        let infcx = self.infcx;
315        let tcx = infcx.tcx;
316        // Just an optimization: When we don't have escaping bound vars,
317        // we don't need to replace them with placeholders.
318        let (term, maps) = if term.has_escaping_bound_vars() {
319            let (term, mapped_regions, mapped_types, mapped_consts) =
320                BoundVarReplacer::replace_bound_vars(infcx, &mut self.universes, term);
321            (term, Some((mapped_regions, mapped_types, mapped_consts)))
322        } else {
323            (term, None)
324        };
325        let term = term.try_fold_with(self)?;
326
327        let mut orig_values = OriginalQueryValues::default();
328        let c_term = infcx.canonicalize_query(self.param_env.and(term), &mut orig_values);
329        debug!("QueryNormalizer: c_term = {:#?}", c_term);
330        debug!("QueryNormalizer: orig_values = {:#?}", orig_values);
331        let result = match term.kind(tcx) {
332            ty::AliasTermKind::ProjectionTy | ty::AliasTermKind::ProjectionConst => {
333                tcx.normalize_canonicalized_projection(c_term)
334            }
335            ty::AliasTermKind::FreeTy | ty::AliasTermKind::FreeConst => {
336                tcx.normalize_canonicalized_free_alias(c_term)
337            }
338            ty::AliasTermKind::InherentTy | ty::AliasTermKind::InherentConst => {
339                tcx.normalize_canonicalized_inherent_projection(c_term)
340            }
341            kind @ (ty::AliasTermKind::OpaqueTy | ty::AliasTermKind::UnevaluatedConst) => {
342                unreachable!("did not expect {kind:?} due to match arm above")
343            }
344        }?;
345        // We don't expect ambiguity.
346        if !result.value.is_proven() {
347            // Rustdoc normalizes possibly not well-formed types, so only
348            // treat this as a bug if we're not in rustdoc.
349            if !tcx.sess.opts.actually_rustdoc {
350                tcx.dcx().delayed_bug(format!("unexpected ambiguity: {c_term:?} {result:?}"));
351            }
352            return Err(NoSolution);
353        }
354        let InferOk { value: result, obligations } = infcx
355            .instantiate_query_response_and_region_obligations(
356                self.cause,
357                self.param_env,
358                &orig_values,
359                result,
360            )?;
361        debug!("QueryNormalizer: result = {:#?}", result);
362        debug!("QueryNormalizer: obligations = {:#?}", obligations);
363        self.obligations.extend(obligations);
364        let res = if let Some((mapped_regions, mapped_types, mapped_consts)) = maps {
365            PlaceholderReplacer::replace_placeholders(
366                infcx,
367                mapped_regions,
368                mapped_types,
369                mapped_consts,
370                &self.universes,
371                result.normalized_term,
372            )
373        } else {
374            result.normalized_term
375        };
376        // `tcx.normalize_canonicalized_projection` may normalize to a type that
377        // still has unevaluated consts, so keep normalizing here if that's the case.
378        // Similarly, `tcx.normalize_canonicalized_free_alias` will only unwrap one layer
379        // of type and we need to continue folding it to reveal the TAIT behind it.
380        if res != term.to_term(tcx)
381            && (res.as_type().map_or(false, |t| t.has_type_flags(ty::TypeFlags::HAS_CT_PROJECTION))
382                || term.kind(tcx) == ty::AliasTermKind::FreeTy)
383        {
384            res.try_fold_with(self)
385        } else {
386            Ok(res)
387        }
388    }
389}
rustc_trait_selection/traits/query/normalize.rs

rustc_trait_selection/traits/query/
normalize.rs
