rustc_trait_selection/solve/
normalize.rs

Help
1use std::assert_matches::assert_matches;
2use std::fmt::Debug;
3use std::marker::PhantomData;
4
5use rustc_data_structures::stack::ensure_sufficient_stack;
6use rustc_infer::infer::InferCtxt;
7use rustc_infer::infer::at::At;
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 fulfill_cx = FulfillmentCtxt::new(at.infcx);
49    let mut folder =
50        NormalizationFolder { at, fulfill_cx, depth: 0, universes, _errors: PhantomData };
51
52    value.try_fold_with(&mut folder)
53}
54
55struct NormalizationFolder<'me, 'tcx, E> {
56    at: At<'me, 'tcx>,
57    fulfill_cx: FulfillmentCtxt<'tcx, E>,
58    depth: usize,
59    universes: Vec<Option<UniverseIndex>>,
60    _errors: PhantomData<E>,
61}
62
63impl<'tcx, E> NormalizationFolder<'_, 'tcx, E>
64where
65    E: FromSolverError<'tcx, NextSolverError<'tcx>>,
66{
67    fn normalize_alias_ty(&mut self, alias_ty: Ty<'tcx>) -> Result<Ty<'tcx>, Vec<E>> {
68        assert_matches!(alias_ty.kind(), ty::Alias(..));
69
70        let infcx = self.at.infcx;
71        let tcx = infcx.tcx;
72        let recursion_limit = tcx.recursion_limit();
73        if !recursion_limit.value_within_limit(self.depth) {
74            let ty::Alias(_, data) = *alias_ty.kind() else {
75                unreachable!();
76            };
77
78            self.at.infcx.err_ctxt().report_overflow_error(
79                OverflowCause::DeeplyNormalize(data.into()),
80                self.at.cause.span,
81                true,
82                |_| {},
83            );
84        }
85
86        self.depth += 1;
87
88        let new_infer_ty = infcx.next_ty_var(self.at.cause.span);
89        let obligation = Obligation::new(
90            tcx,
91            self.at.cause.clone(),
92            self.at.param_env,
93            ty::PredicateKind::AliasRelate(
94                alias_ty.into(),
95                new_infer_ty.into(),
96                ty::AliasRelationDirection::Equate,
97            ),
98        );
99
100        self.fulfill_cx.register_predicate_obligation(infcx, obligation);
101        let errors = self.fulfill_cx.select_all_or_error(infcx);
102        if !errors.is_empty() {
103            return Err(errors);
104        }
105
106        // Alias is guaranteed to be fully structurally resolved,
107        // so we can super fold here.
108        let ty = infcx.resolve_vars_if_possible(new_infer_ty);
109        let result = ty.try_super_fold_with(self)?;
110        self.depth -= 1;
111        Ok(result)
112    }
113
114    fn normalize_unevaluated_const(
115        &mut self,
116        uv: ty::UnevaluatedConst<'tcx>,
117    ) -> Result<ty::Const<'tcx>, Vec<E>> {
118        let infcx = self.at.infcx;
119        let tcx = infcx.tcx;
120        let recursion_limit = tcx.recursion_limit();
121        if !recursion_limit.value_within_limit(self.depth) {
122            self.at.infcx.err_ctxt().report_overflow_error(
123                OverflowCause::DeeplyNormalize(uv.into()),
124                self.at.cause.span,
125                true,
126                |_| {},
127            );
128        }
129
130        self.depth += 1;
131
132        let new_infer_ct = infcx.next_const_var(self.at.cause.span);
133        let obligation = Obligation::new(
134            tcx,
135            self.at.cause.clone(),
136            self.at.param_env,
137            ty::NormalizesTo { alias: uv.into(), term: new_infer_ct.into() },
138        );
139
140        let result = if infcx.predicate_may_hold(&obligation) {
141            self.fulfill_cx.register_predicate_obligation(infcx, obligation);
142            let errors = self.fulfill_cx.select_all_or_error(infcx);
143            if !errors.is_empty() {
144                return Err(errors);
145            }
146            let ct = infcx.resolve_vars_if_possible(new_infer_ct);
147            ct.try_fold_with(self)?
148        } else {
149            ty::Const::new_unevaluated(tcx, uv).try_super_fold_with(self)?
150        };
151
152        self.depth -= 1;
153        Ok(result)
154    }
155}
156
157impl<'tcx, E> FallibleTypeFolder<TyCtxt<'tcx>> for NormalizationFolder<'_, 'tcx, E>
158where
159    E: FromSolverError<'tcx, NextSolverError<'tcx>> + Debug,
160{
161    type Error = Vec<E>;
162
163    fn cx(&self) -> TyCtxt<'tcx> {
164        self.at.infcx.tcx
165    }
166
167    fn try_fold_binder<T: TypeFoldable<TyCtxt<'tcx>>>(
168        &mut self,
169        t: ty::Binder<'tcx, T>,
170    ) -> Result<ty::Binder<'tcx, T>, Self::Error> {
171        self.universes.push(None);
172        let t = t.try_super_fold_with(self)?;
173        self.universes.pop();
174        Ok(t)
175    }
176
177    #[instrument(level = "trace", skip(self), ret)]
178    fn try_fold_ty(&mut self, ty: Ty<'tcx>) -> Result<Ty<'tcx>, Self::Error> {
179        let infcx = self.at.infcx;
180        debug_assert_eq!(ty, infcx.shallow_resolve(ty));
181        if !ty.has_aliases() {
182            return Ok(ty);
183        }
184
185        let ty::Alias(..) = *ty.kind() else { return ty.try_super_fold_with(self) };
186
187        if ty.has_escaping_bound_vars() {
188            let (ty, mapped_regions, mapped_types, mapped_consts) =
189                BoundVarReplacer::replace_bound_vars(infcx, &mut self.universes, ty);
190            let result = ensure_sufficient_stack(|| self.normalize_alias_ty(ty))?;
191            Ok(PlaceholderReplacer::replace_placeholders(
192                infcx,
193                mapped_regions,
194                mapped_types,
195                mapped_consts,
196                &self.universes,
197                result,
198            ))
199        } else {
200            ensure_sufficient_stack(|| self.normalize_alias_ty(ty))
201        }
202    }
203
204    #[instrument(level = "trace", skip(self), ret)]
205    fn try_fold_const(&mut self, ct: ty::Const<'tcx>) -> Result<ty::Const<'tcx>, Self::Error> {
206        let infcx = self.at.infcx;
207        debug_assert_eq!(ct, infcx.shallow_resolve_const(ct));
208        if !ct.has_aliases() {
209            return Ok(ct);
210        }
211
212        let uv = match ct.kind() {
213            ty::ConstKind::Unevaluated(ct) => ct,
214            _ => return ct.try_super_fold_with(self),
215        };
216
217        if uv.has_escaping_bound_vars() {
218            let (uv, mapped_regions, mapped_types, mapped_consts) =
219                BoundVarReplacer::replace_bound_vars(infcx, &mut self.universes, uv);
220            let result = ensure_sufficient_stack(|| self.normalize_unevaluated_const(uv))?;
221            Ok(PlaceholderReplacer::replace_placeholders(
222                infcx,
223                mapped_regions,
224                mapped_types,
225                mapped_consts,
226                &self.universes,
227                result,
228            ))
229        } else {
230            ensure_sufficient_stack(|| self.normalize_unevaluated_const(uv))
231        }
232    }
233}
234
235// Deeply normalize a value and return it
236pub(crate) fn deeply_normalize_for_diagnostics<'tcx, T: TypeFoldable<TyCtxt<'tcx>>>(
237    infcx: &InferCtxt<'tcx>,
238    param_env: ty::ParamEnv<'tcx>,
239    t: T,
240) -> T {
241    t.fold_with(&mut DeeplyNormalizeForDiagnosticsFolder {
242        at: infcx.at(&ObligationCause::dummy(), param_env),
243    })
244}
245
246struct DeeplyNormalizeForDiagnosticsFolder<'a, 'tcx> {
247    at: At<'a, 'tcx>,
248}
249
250impl<'tcx> TypeFolder<TyCtxt<'tcx>> for DeeplyNormalizeForDiagnosticsFolder<'_, 'tcx> {
251    fn cx(&self) -> TyCtxt<'tcx> {
252        self.at.infcx.tcx
253    }
254
255    fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
256        deeply_normalize_with_skipped_universes(
257            self.at,
258            ty,
259            vec![None; ty.outer_exclusive_binder().as_usize()],
260        )
261        .unwrap_or_else(|_: Vec<ScrubbedTraitError<'tcx>>| ty.super_fold_with(self))
262    }
263
264    fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> {
265        deeply_normalize_with_skipped_universes(
266            self.at,
267            ct,
268            vec![None; ct.outer_exclusive_binder().as_usize()],
269        )
270        .unwrap_or_else(|_: Vec<ScrubbedTraitError<'tcx>>| ct.super_fold_with(self))
271    }
272}
rustc_trait_selection/solve/normalize.rs

rustc_trait_selection/solve/
normalize.rs
