rustc_trait_selection/solve/
normalize.rs

1use std::assert_matches::assert_matches;
2use std::fmt::Debug;
3
4use rustc_data_structures::stack::ensure_sufficient_stack;
5use rustc_infer::infer::InferCtxt;
6use rustc_infer::infer::at::At;
7use rustc_infer::traits::solve::Goal;
8use rustc_infer::traits::{FromSolverError, Obligation, TraitEngine};
9use rustc_middle::traits::ObligationCause;
10use rustc_middle::ty::{
11    self, FallibleTypeFolder, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeSuperFoldable,
12    TypeVisitableExt, UniverseIndex,
13};
14use tracing::instrument;
15
16use super::{FulfillmentCtxt, NextSolverError};
17use crate::error_reporting::InferCtxtErrorExt;
18use crate::error_reporting::traits::OverflowCause;
19use crate::traits::query::evaluate_obligation::InferCtxtExt;
20use crate::traits::{BoundVarReplacer, PlaceholderReplacer, ScrubbedTraitError};
21
22/// Deeply normalize all aliases in `value`. This does not handle inference and expects
23/// its input to be already fully resolved.
24pub fn deeply_normalize<'tcx, T, E>(at: At<'_, 'tcx>, value: T) -> Result<T, Vec<E>>
25where
26    T: TypeFoldable<TyCtxt<'tcx>>,
27    E: FromSolverError<'tcx, NextSolverError<'tcx>>,
28{
29    assert!(!value.has_escaping_bound_vars());
30    deeply_normalize_with_skipped_universes(at, value, vec![])
31}
32
33/// Deeply normalize all aliases in `value`. This does not handle inference and expects
34/// its input to be already fully resolved.
35///
36/// Additionally takes a list of universes which represents the binders which have been
37/// entered before passing `value` to the function. This is currently needed for
38/// `normalize_erasing_regions`, which skips binders as it walks through a type.
39pub fn deeply_normalize_with_skipped_universes<'tcx, T, E>(
40    at: At<'_, 'tcx>,
41    value: T,
42    universes: Vec<Option<UniverseIndex>>,
43) -> Result<T, Vec<E>>
44where
45    T: TypeFoldable<TyCtxt<'tcx>>,
46    E: FromSolverError<'tcx, NextSolverError<'tcx>>,
47{
48    let (value, goals) =
49        deeply_normalize_with_skipped_universes_and_ambiguous_goals(at, value, universes)?;
50    assert_eq!(goals, vec![]);
51
52    Ok(value)
53}
54
55/// Deeply normalize all aliases in `value`. This does not handle inference and expects
56/// its input to be already fully resolved.
57///
58/// Additionally takes a list of universes which represents the binders which have been
59/// entered before passing `value` to the function. This is currently needed for
60/// `normalize_erasing_regions`, which skips binders as it walks through a type.
61///
62/// This returns a set of stalled obligations if the typing mode of the underlying infcx
63/// has any stalled coroutine def ids.
64pub fn deeply_normalize_with_skipped_universes_and_ambiguous_goals<'tcx, T, E>(
65    at: At<'_, 'tcx>,
66    value: T,
67    universes: Vec<Option<UniverseIndex>>,
68) -> Result<(T, Vec<Goal<'tcx, ty::Predicate<'tcx>>>), Vec<E>>
69where
70    T: TypeFoldable<TyCtxt<'tcx>>,
71    E: FromSolverError<'tcx, NextSolverError<'tcx>>,
72{
73    let fulfill_cx = FulfillmentCtxt::new(at.infcx);
74    let mut folder =
75        NormalizationFolder { at, fulfill_cx, depth: 0, universes, stalled_goals: vec![] };
76    let value = value.try_fold_with(&mut folder)?;
77    let errors = folder.fulfill_cx.select_all_or_error(at.infcx);
78    if errors.is_empty() { Ok((value, folder.stalled_goals)) } else { Err(errors) }
79}
80
81struct NormalizationFolder<'me, 'tcx, E> {
82    at: At<'me, 'tcx>,
83    fulfill_cx: FulfillmentCtxt<'tcx, E>,
84    depth: usize,
85    universes: Vec<Option<UniverseIndex>>,
86    stalled_goals: Vec<Goal<'tcx, ty::Predicate<'tcx>>>,
87}
88
89impl<'tcx, E> NormalizationFolder<'_, 'tcx, E>
90where
91    E: FromSolverError<'tcx, NextSolverError<'tcx>>,
92{
93    fn normalize_alias_ty(&mut self, alias_ty: Ty<'tcx>) -> Result<Ty<'tcx>, Vec<E>> {
94        assert_matches!(alias_ty.kind(), ty::Alias(..));
95
96        let infcx = self.at.infcx;
97        let tcx = infcx.tcx;
98        let recursion_limit = tcx.recursion_limit();
99        if !recursion_limit.value_within_limit(self.depth) {
100            let ty::Alias(_, data) = *alias_ty.kind() else {
101                unreachable!();
102            };
103
104            self.at.infcx.err_ctxt().report_overflow_error(
105                OverflowCause::DeeplyNormalize(data.into()),
106                self.at.cause.span,
107                true,
108                |_| {},
109            );
110        }
111
112        self.depth += 1;
113
114        let new_infer_ty = infcx.next_ty_var(self.at.cause.span);
115        let obligation = Obligation::new(
116            tcx,
117            self.at.cause.clone(),
118            self.at.param_env,
119            ty::PredicateKind::AliasRelate(
120                alias_ty.into(),
121                new_infer_ty.into(),
122                ty::AliasRelationDirection::Equate,
123            ),
124        );
125
126        self.fulfill_cx.register_predicate_obligation(infcx, obligation);
127        self.select_all_and_stall_coroutine_predicates()?;
128
129        // Alias is guaranteed to be fully structurally resolved,
130        // so we can super fold here.
131        let ty = infcx.resolve_vars_if_possible(new_infer_ty);
132        let result = ty.try_super_fold_with(self)?;
133        self.depth -= 1;
134        Ok(result)
135    }
136
137    fn normalize_unevaluated_const(
138        &mut self,
139        uv: ty::UnevaluatedConst<'tcx>,
140    ) -> Result<ty::Const<'tcx>, Vec<E>> {
141        let infcx = self.at.infcx;
142        let tcx = infcx.tcx;
143        let recursion_limit = tcx.recursion_limit();
144        if !recursion_limit.value_within_limit(self.depth) {
145            self.at.infcx.err_ctxt().report_overflow_error(
146                OverflowCause::DeeplyNormalize(uv.into()),
147                self.at.cause.span,
148                true,
149                |_| {},
150            );
151        }
152
153        self.depth += 1;
154
155        let new_infer_ct = infcx.next_const_var(self.at.cause.span);
156        let obligation = Obligation::new(
157            tcx,
158            self.at.cause.clone(),
159            self.at.param_env,
160            ty::NormalizesTo { alias: uv.into(), term: new_infer_ct.into() },
161        );
162
163        let result = if infcx.predicate_may_hold(&obligation) {
164            self.fulfill_cx.register_predicate_obligation(infcx, obligation);
165            let errors = self.fulfill_cx.select_where_possible(infcx);
166            if !errors.is_empty() {
167                return Err(errors);
168            }
169            let ct = infcx.resolve_vars_if_possible(new_infer_ct);
170            ct.try_fold_with(self)?
171        } else {
172            ty::Const::new_unevaluated(tcx, uv).try_super_fold_with(self)?
173        };
174
175        self.depth -= 1;
176        Ok(result)
177    }
178
179    fn select_all_and_stall_coroutine_predicates(&mut self) -> Result<(), Vec<E>> {
180        let errors = self.fulfill_cx.select_where_possible(self.at.infcx);
181        if !errors.is_empty() {
182            return Err(errors);
183        }
184
185        self.stalled_goals.extend(
186            self.fulfill_cx
187                .drain_stalled_obligations_for_coroutines(self.at.infcx)
188                .into_iter()
189                .map(|obl| obl.as_goal()),
190        );
191
192        let errors = self.fulfill_cx.collect_remaining_errors(self.at.infcx);
193        if !errors.is_empty() {
194            return Err(errors);
195        }
196
197        Ok(())
198    }
199}
200
201impl<'tcx, E> FallibleTypeFolder<TyCtxt<'tcx>> for NormalizationFolder<'_, 'tcx, E>
202where
203    E: FromSolverError<'tcx, NextSolverError<'tcx>> + Debug,
204{
205    type Error = Vec<E>;
206
207    fn cx(&self) -> TyCtxt<'tcx> {
208        self.at.infcx.tcx
209    }
210
211    fn try_fold_binder<T: TypeFoldable<TyCtxt<'tcx>>>(
212        &mut self,
213        t: ty::Binder<'tcx, T>,
214    ) -> Result<ty::Binder<'tcx, T>, Self::Error> {
215        self.universes.push(None);
216        let t = t.try_super_fold_with(self)?;
217        self.universes.pop();
218        Ok(t)
219    }
220
221    #[instrument(level = "trace", skip(self), ret)]
222    fn try_fold_ty(&mut self, ty: Ty<'tcx>) -> Result<Ty<'tcx>, Self::Error> {
223        let infcx = self.at.infcx;
224        debug_assert_eq!(ty, infcx.shallow_resolve(ty));
225        if !ty.has_aliases() {
226            return Ok(ty);
227        }
228
229        let ty::Alias(..) = *ty.kind() else { return ty.try_super_fold_with(self) };
230
231        if ty.has_escaping_bound_vars() {
232            let (ty, mapped_regions, mapped_types, mapped_consts) =
233                BoundVarReplacer::replace_bound_vars(infcx, &mut self.universes, ty);
234            let result = ensure_sufficient_stack(|| self.normalize_alias_ty(ty))?;
235            Ok(PlaceholderReplacer::replace_placeholders(
236                infcx,
237                mapped_regions,
238                mapped_types,
239                mapped_consts,
240                &self.universes,
241                result,
242            ))
243        } else {
244            ensure_sufficient_stack(|| self.normalize_alias_ty(ty))
245        }
246    }
247
248    #[instrument(level = "trace", skip(self), ret)]
249    fn try_fold_const(&mut self, ct: ty::Const<'tcx>) -> Result<ty::Const<'tcx>, Self::Error> {
250        let infcx = self.at.infcx;
251        debug_assert_eq!(ct, infcx.shallow_resolve_const(ct));
252        if !ct.has_aliases() {
253            return Ok(ct);
254        }
255
256        let uv = match ct.kind() {
257            ty::ConstKind::Unevaluated(ct) => ct,
258            _ => return ct.try_super_fold_with(self),
259        };
260
261        if uv.has_escaping_bound_vars() {
262            let (uv, mapped_regions, mapped_types, mapped_consts) =
263                BoundVarReplacer::replace_bound_vars(infcx, &mut self.universes, uv);
264            let result = ensure_sufficient_stack(|| self.normalize_unevaluated_const(uv))?;
265            Ok(PlaceholderReplacer::replace_placeholders(
266                infcx,
267                mapped_regions,
268                mapped_types,
269                mapped_consts,
270                &self.universes,
271                result,
272            ))
273        } else {
274            ensure_sufficient_stack(|| self.normalize_unevaluated_const(uv))
275        }
276    }
277}
278
279// Deeply normalize a value and return it
280pub(crate) fn deeply_normalize_for_diagnostics<'tcx, T: TypeFoldable<TyCtxt<'tcx>>>(
281    infcx: &InferCtxt<'tcx>,
282    param_env: ty::ParamEnv<'tcx>,
283    t: T,
284) -> T {
285    t.fold_with(&mut DeeplyNormalizeForDiagnosticsFolder {
286        at: infcx.at(&ObligationCause::dummy(), param_env),
287    })
288}
289
290struct DeeplyNormalizeForDiagnosticsFolder<'a, 'tcx> {
291    at: At<'a, 'tcx>,
292}
293
294impl<'tcx> TypeFolder<TyCtxt<'tcx>> for DeeplyNormalizeForDiagnosticsFolder<'_, 'tcx> {
295    fn cx(&self) -> TyCtxt<'tcx> {
296        self.at.infcx.tcx
297    }
298
299    fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
300        let infcx = self.at.infcx;
301        let result =
302            infcx.commit_if_ok(|_| {
303                deeply_normalize_with_skipped_universes_and_ambiguous_goals::<
304                    _,
305                    ScrubbedTraitError<'tcx>,
306                >(self.at, ty, vec![None; ty.outer_exclusive_binder().as_usize()])
307            });
308        match result {
309            Ok((ty, _)) => ty,
310            Err(_) => ty.super_fold_with(self),
311        }
312    }
313
314    fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> {
315        let infcx = self.at.infcx;
316        let result =
317            infcx.commit_if_ok(|_| {
318                deeply_normalize_with_skipped_universes_and_ambiguous_goals::<
319                    _,
320                    ScrubbedTraitError<'tcx>,
321                >(self.at, ct, vec![None; ct.outer_exclusive_binder().as_usize()])
322            });
323        match result {
324            Ok((ct, _)) => ct,
325            Err(_) => ct.super_fold_with(self),
326        }
327    }
328}
rustc_trait_selection/solve/normalize.rs

rustc_trait_selection/solve/
normalize.rs
