rustc_trait_selection/solve/
normalize.rs1use 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
22pub 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
33pub 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
57pub 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 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
286pub(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}