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