rustc_trait_selection/solve/
normalize.rs1use 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
20pub 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
31pub 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
55pub 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 let term = infcx.resolve_vars_if_possible(infer_term);
136 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
245pub(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}