rustc_trait_selection/traits/query/
normalize.rs

Help
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::{
11    self, FallibleTypeFolder, Ty, TyCtxt, TypeFoldable, TypeSuperFoldable, TypeSuperVisitable,
12    TypeVisitable, TypeVisitableExt, TypeVisitor, TypingMode,
13};
14use rustc_span::DUMMY_SP;
15use tracing::{debug, info, instrument};
16
17use super::NoSolution;
18use crate::error_reporting::InferCtxtErrorExt;
19use crate::error_reporting::traits::OverflowCause;
20use crate::infer::at::At;
21use crate::infer::canonical::OriginalQueryValues;
22use crate::infer::{InferCtxt, InferOk};
23use crate::traits::normalize::needs_normalization;
24use crate::traits::{
25    BoundVarReplacer, Normalized, ObligationCause, PlaceholderReplacer, ScrubbedTraitError,
26};
27
28#[extension(pub trait QueryNormalizeExt<'tcx>)]
29impl<'a, 'tcx> At<'a, 'tcx> {
30    /// Normalize `value` in the context of the inference context,
31    /// yielding a resulting type, or an error if `value` cannot be
32    /// normalized. If you don't care about regions, you should prefer
33    /// `normalize_erasing_regions`, which is more efficient.
34    ///
35    /// If the normalization succeeds, returns back the normalized
36    /// value along with various outlives relations (in the form of
37    /// obligations that must be discharged).
38    ///
39    /// This normalization should *only* be used when the projection is well-formed and
40    /// does not have possible ambiguity (contains inference variables).
41    ///
42    /// After codegen, when lifetimes do not matter, it is preferable to instead
43    /// use [`TyCtxt::normalize_erasing_regions`], which wraps this procedure.
44    ///
45    /// N.B. Once the new solver is stabilized this method of normalization will
46    /// likely be removed as trait solver operations are already cached by the query
47    /// system making this redundant.
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        let res = match kind {
214            ty::Opaque => {
215                // Only normalize `impl Trait` outside of type inference, usually in codegen.
216                match self.infcx.typing_mode() {
217                    TypingMode::Coherence
218                    | TypingMode::Analysis { .. }
219                    | TypingMode::PostBorrowckAnalysis { .. } => ty.try_super_fold_with(self)?,
220
221                    TypingMode::PostAnalysis => {
222                        let args = data.args.try_fold_with(self)?;
223                        let recursion_limit = self.cx().recursion_limit();
224
225                        if !recursion_limit.value_within_limit(self.anon_depth) {
226                            let guar = self
227                                .infcx
228                                .err_ctxt()
229                                .build_overflow_error(
230                                    OverflowCause::DeeplyNormalize(data.into()),
231                                    self.cause.span,
232                                    true,
233                                )
234                                .delay_as_bug();
235                            return Ok(Ty::new_error(self.cx(), guar));
236                        }
237
238                        let generic_ty = self.cx().type_of(data.def_id);
239                        let mut concrete_ty = generic_ty.instantiate(self.cx(), args);
240                        self.anon_depth += 1;
241                        if concrete_ty == ty {
242                            concrete_ty = Ty::new_error_with_message(
243                                self.cx(),
244                                DUMMY_SP,
245                                "recursive opaque type",
246                            );
247                        }
248                        let folded_ty = ensure_sufficient_stack(|| self.try_fold_ty(concrete_ty));
249                        self.anon_depth -= 1;
250                        folded_ty?
251                    }
252                }
253            }
254
255            ty::Projection | ty::Inherent | ty::Weak => {
256                // See note in `rustc_trait_selection::traits::project`
257
258                let infcx = self.infcx;
259                let tcx = infcx.tcx;
260                // Just an optimization: When we don't have escaping bound vars,
261                // we don't need to replace them with placeholders.
262                let (data, maps) = if data.has_escaping_bound_vars() {
263                    let (data, mapped_regions, mapped_types, mapped_consts) =
264                        BoundVarReplacer::replace_bound_vars(infcx, &mut self.universes, data);
265                    (data, Some((mapped_regions, mapped_types, mapped_consts)))
266                } else {
267                    (data, None)
268                };
269                let data = data.try_fold_with(self)?;
270
271                let mut orig_values = OriginalQueryValues::default();
272                let c_data = infcx.canonicalize_query(self.param_env.and(data), &mut orig_values);
273                debug!("QueryNormalizer: c_data = {:#?}", c_data);
274                debug!("QueryNormalizer: orig_values = {:#?}", orig_values);
275                let result = match kind {
276                    ty::Projection => tcx.normalize_canonicalized_projection_ty(c_data),
277                    ty::Weak => tcx.normalize_canonicalized_weak_ty(c_data),
278                    ty::Inherent => tcx.normalize_canonicalized_inherent_projection_ty(c_data),
279                    kind => unreachable!("did not expect {kind:?} due to match arm above"),
280                }?;
281                // We don't expect ambiguity.
282                if !result.value.is_proven() {
283                    // Rustdoc normalizes possibly not well-formed types, so only
284                    // treat this as a bug if we're not in rustdoc.
285                    if !tcx.sess.opts.actually_rustdoc {
286                        tcx.dcx()
287                            .delayed_bug(format!("unexpected ambiguity: {c_data:?} {result:?}"));
288                    }
289                    return Err(NoSolution);
290                }
291                let InferOk { value: result, obligations } = infcx
292                    .instantiate_query_response_and_region_obligations(
293                        self.cause,
294                        self.param_env,
295                        &orig_values,
296                        result,
297                    )?;
298                debug!("QueryNormalizer: result = {:#?}", result);
299                debug!("QueryNormalizer: obligations = {:#?}", obligations);
300                self.obligations.extend(obligations);
301                let res = if let Some((mapped_regions, mapped_types, mapped_consts)) = maps {
302                    PlaceholderReplacer::replace_placeholders(
303                        infcx,
304                        mapped_regions,
305                        mapped_types,
306                        mapped_consts,
307                        &self.universes,
308                        result.normalized_ty,
309                    )
310                } else {
311                    result.normalized_ty
312                };
313                // `tcx.normalize_canonicalized_projection_ty` may normalize to a type that
314                // still has unevaluated consts, so keep normalizing here if that's the case.
315                // Similarly, `tcx.normalize_canonicalized_weak_ty` will only unwrap one layer
316                // of type and we need to continue folding it to reveal the TAIT behind it.
317                if res != ty
318                    && (res.has_type_flags(ty::TypeFlags::HAS_CT_PROJECTION) || kind == ty::Weak)
319                {
320                    res.try_fold_with(self)?
321                } else {
322                    res
323                }
324            }
325        };
326
327        self.cache.insert(ty, res);
328        Ok(res)
329    }
330
331    fn try_fold_const(
332        &mut self,
333        constant: ty::Const<'tcx>,
334    ) -> Result<ty::Const<'tcx>, Self::Error> {
335        if !needs_normalization(self.infcx, &constant) {
336            return Ok(constant);
337        }
338
339        let constant = crate::traits::with_replaced_escaping_bound_vars(
340            self.infcx,
341            &mut self.universes,
342            constant,
343            |constant| crate::traits::evaluate_const(&self.infcx, constant, self.param_env),
344        );
345        debug!(?constant, ?self.param_env);
346        constant.try_super_fold_with(self)
347    }
348
349    #[inline]
350    fn try_fold_predicate(
351        &mut self,
352        p: ty::Predicate<'tcx>,
353    ) -> Result<ty::Predicate<'tcx>, Self::Error> {
354        if p.allow_normalization() && needs_normalization(self.infcx, &p) {
355            p.try_super_fold_with(self)
356        } else {
357            Ok(p)
358        }
359    }
360}
rustc_trait_selection/traits/query/normalize.rs

rustc_trait_selection/traits/query/
normalize.rs
