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

rustc_trait_selection/solve/
normalize.rs
