rustc_trait_selection/solve/
normalize.rs

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

rustc_trait_selection/solve/
normalize.rs
