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