rustc_trait_selection/traits/query/
normalize.rs1use rustc_data_structures::sso::SsoHashMap;
6use rustc_data_structures::stack::ensure_sufficient_stack;
7use rustc_infer::traits::PredicateObligations;
8use rustc_macros::extension;
9pub use rustc_middle::traits::query::NormalizationResult;
10use rustc_middle::ty::fold::{FallibleTypeFolder, TypeFoldable, TypeSuperFoldable};
11use rustc_middle::ty::visit::{TypeSuperVisitable, TypeVisitable, TypeVisitableExt};
12use rustc_middle::ty::{self, Ty, TyCtxt, TypeVisitor, TypingMode};
13use rustc_span::DUMMY_SP;
14use tracing::{debug, info, instrument};
15
16use super::NoSolution;
17use crate::error_reporting::InferCtxtErrorExt;
18use crate::error_reporting::traits::OverflowCause;
19use crate::infer::at::At;
20use crate::infer::canonical::OriginalQueryValues;
21use crate::infer::{InferCtxt, InferOk};
22use crate::traits::normalize::needs_normalization;
23use crate::traits::{
24 BoundVarReplacer, Normalized, ObligationCause, PlaceholderReplacer, ScrubbedTraitError,
25};
26
27#[extension(pub trait QueryNormalizeExt<'tcx>)]
28impl<'a, 'tcx> At<'a, 'tcx> {
29 fn query_normalize<T>(self, value: T) -> Result<Normalized<'tcx, T>, NoSolution>
49 where
50 T: TypeFoldable<TyCtxt<'tcx>>,
51 {
52 debug!(
53 "normalize::<{}>(value={:?}, param_env={:?}, cause={:?})",
54 std::any::type_name::<T>(),
55 value,
56 self.param_env,
57 self.cause,
58 );
59
60 let universes = if value.has_escaping_bound_vars() {
71 let mut max_visitor =
72 MaxEscapingBoundVarVisitor { outer_index: ty::INNERMOST, escaping: 0 };
73 value.visit_with(&mut max_visitor);
74 vec![None; max_visitor.escaping]
75 } else {
76 vec![]
77 };
78
79 if self.infcx.next_trait_solver() {
80 match crate::solve::deeply_normalize_with_skipped_universes::<_, ScrubbedTraitError<'tcx>>(
81 self, value, universes,
82 ) {
83 Ok(value) => {
84 return Ok(Normalized { value, obligations: PredicateObligations::new() });
85 }
86 Err(_errors) => {
87 return Err(NoSolution);
88 }
89 }
90 }
91
92 if !needs_normalization(self.infcx, &value) {
93 return Ok(Normalized { value, obligations: PredicateObligations::new() });
94 }
95
96 let mut normalizer = QueryNormalizer {
97 infcx: self.infcx,
98 cause: self.cause,
99 param_env: self.param_env,
100 obligations: PredicateObligations::new(),
101 cache: SsoHashMap::new(),
102 anon_depth: 0,
103 universes,
104 };
105
106 let result = value.try_fold_with(&mut normalizer);
107 info!(
108 "normalize::<{}>: result={:?} with {} obligations",
109 std::any::type_name::<T>(),
110 result,
111 normalizer.obligations.len(),
112 );
113 debug!(
114 "normalize::<{}>: obligations={:?}",
115 std::any::type_name::<T>(),
116 normalizer.obligations,
117 );
118 result.map(|value| Normalized { value, obligations: normalizer.obligations })
119 }
120}
121
122struct MaxEscapingBoundVarVisitor {
124 outer_index: ty::DebruijnIndex,
126 escaping: usize,
127}
128
129impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for MaxEscapingBoundVarVisitor {
130 fn visit_binder<T: TypeVisitable<TyCtxt<'tcx>>>(&mut self, t: &ty::Binder<'tcx, T>) {
131 self.outer_index.shift_in(1);
132 t.super_visit_with(self);
133 self.outer_index.shift_out(1);
134 }
135
136 #[inline]
137 fn visit_ty(&mut self, t: Ty<'tcx>) {
138 if t.outer_exclusive_binder() > self.outer_index {
139 self.escaping = self
140 .escaping
141 .max(t.outer_exclusive_binder().as_usize() - self.outer_index.as_usize());
142 }
143 }
144
145 #[inline]
146 fn visit_region(&mut self, r: ty::Region<'tcx>) {
147 match *r {
148 ty::ReBound(debruijn, _) if debruijn > self.outer_index => {
149 self.escaping =
150 self.escaping.max(debruijn.as_usize() - self.outer_index.as_usize());
151 }
152 _ => {}
153 }
154 }
155
156 fn visit_const(&mut self, ct: ty::Const<'tcx>) {
157 if ct.outer_exclusive_binder() > self.outer_index {
158 self.escaping = self
159 .escaping
160 .max(ct.outer_exclusive_binder().as_usize() - self.outer_index.as_usize());
161 }
162 }
163}
164
165struct QueryNormalizer<'a, 'tcx> {
166 infcx: &'a InferCtxt<'tcx>,
167 cause: &'a ObligationCause<'tcx>,
168 param_env: ty::ParamEnv<'tcx>,
169 obligations: PredicateObligations<'tcx>,
170 cache: SsoHashMap<Ty<'tcx>, Ty<'tcx>>,
171 anon_depth: usize,
172 universes: Vec<Option<ty::UniverseIndex>>,
173}
174
175impl<'a, 'tcx> FallibleTypeFolder<TyCtxt<'tcx>> for QueryNormalizer<'a, 'tcx> {
176 type Error = NoSolution;
177
178 fn cx(&self) -> TyCtxt<'tcx> {
179 self.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 t
190 }
191
192 #[instrument(level = "debug", skip(self))]
193 fn try_fold_ty(&mut self, ty: Ty<'tcx>) -> Result<Ty<'tcx>, Self::Error> {
194 if !needs_normalization(self.infcx, &ty) {
195 return Ok(ty);
196 }
197
198 if let Some(ty) = self.cache.get(&ty) {
199 return Ok(*ty);
200 }
201
202 let (kind, data) = match *ty.kind() {
203 ty::Alias(kind, data) => (kind, data),
204 _ => {
205 let res = ty.try_super_fold_with(self)?;
206 self.cache.insert(ty, res);
207 return Ok(res);
208 }
209 };
210
211 let res = match kind {
216 ty::Opaque => {
217 match self.infcx.typing_mode() {
219 TypingMode::Coherence
220 | TypingMode::Analysis { .. }
221 | TypingMode::PostBorrowckAnalysis { .. } => ty.try_super_fold_with(self)?,
222
223 TypingMode::PostAnalysis => {
224 let args = data.args.try_fold_with(self)?;
225 let recursion_limit = self.cx().recursion_limit();
226
227 if !recursion_limit.value_within_limit(self.anon_depth) {
228 let guar = self
229 .infcx
230 .err_ctxt()
231 .build_overflow_error(
232 OverflowCause::DeeplyNormalize(data.into()),
233 self.cause.span,
234 true,
235 )
236 .delay_as_bug();
237 return Ok(Ty::new_error(self.cx(), guar));
238 }
239
240 let generic_ty = self.cx().type_of(data.def_id);
241 let mut concrete_ty = generic_ty.instantiate(self.cx(), args);
242 self.anon_depth += 1;
243 if concrete_ty == ty {
244 concrete_ty = Ty::new_error_with_message(
245 self.cx(),
246 DUMMY_SP,
247 "recursive opaque type",
248 );
249 }
250 let folded_ty = ensure_sufficient_stack(|| self.try_fold_ty(concrete_ty));
251 self.anon_depth -= 1;
252 folded_ty?
253 }
254 }
255 }
256
257 ty::Projection | ty::Inherent | ty::Weak => {
258 let infcx = self.infcx;
261 let tcx = infcx.tcx;
262 let (data, maps) = if data.has_escaping_bound_vars() {
265 let (data, mapped_regions, mapped_types, mapped_consts) =
266 BoundVarReplacer::replace_bound_vars(infcx, &mut self.universes, data);
267 (data, Some((mapped_regions, mapped_types, mapped_consts)))
268 } else {
269 (data, None)
270 };
271 let data = data.try_fold_with(self)?;
272
273 let mut orig_values = OriginalQueryValues::default();
274 let c_data = infcx.canonicalize_query(self.param_env.and(data), &mut orig_values);
275 debug!("QueryNormalizer: c_data = {:#?}", c_data);
276 debug!("QueryNormalizer: orig_values = {:#?}", orig_values);
277 let result = match kind {
278 ty::Projection => tcx.normalize_canonicalized_projection_ty(c_data),
279 ty::Weak => tcx.normalize_canonicalized_weak_ty(c_data),
280 ty::Inherent => tcx.normalize_canonicalized_inherent_projection_ty(c_data),
281 kind => unreachable!("did not expect {kind:?} due to match arm above"),
282 }?;
283 if !result.value.is_proven() {
285 if !tcx.sess.opts.actually_rustdoc {
288 tcx.dcx()
289 .delayed_bug(format!("unexpected ambiguity: {c_data:?} {result:?}"));
290 }
291 return Err(NoSolution);
292 }
293 let InferOk { value: result, obligations } = infcx
294 .instantiate_query_response_and_region_obligations(
295 self.cause,
296 self.param_env,
297 &orig_values,
298 result,
299 )?;
300 debug!("QueryNormalizer: result = {:#?}", result);
301 debug!("QueryNormalizer: obligations = {:#?}", obligations);
302 self.obligations.extend(obligations);
303 let res = if let Some((mapped_regions, mapped_types, mapped_consts)) = maps {
304 PlaceholderReplacer::replace_placeholders(
305 infcx,
306 mapped_regions,
307 mapped_types,
308 mapped_consts,
309 &self.universes,
310 result.normalized_ty,
311 )
312 } else {
313 result.normalized_ty
314 };
315 if res != ty
320 && (res.has_type_flags(ty::TypeFlags::HAS_CT_PROJECTION) || kind == ty::Weak)
321 {
322 res.try_fold_with(self)?
323 } else {
324 res
325 }
326 }
327 };
328
329 self.cache.insert(ty, res);
330 Ok(res)
331 }
332
333 fn try_fold_const(
334 &mut self,
335 constant: ty::Const<'tcx>,
336 ) -> Result<ty::Const<'tcx>, Self::Error> {
337 if !needs_normalization(self.infcx, &constant) {
338 return Ok(constant);
339 }
340
341 let constant = crate::traits::with_replaced_escaping_bound_vars(
342 self.infcx,
343 &mut self.universes,
344 constant,
345 |constant| crate::traits::evaluate_const(&self.infcx, constant, self.param_env),
346 );
347 debug!(?constant, ?self.param_env);
348 constant.try_super_fold_with(self)
349 }
350
351 #[inline]
352 fn try_fold_predicate(
353 &mut self,
354 p: ty::Predicate<'tcx>,
355 ) -> Result<ty::Predicate<'tcx>, Self::Error> {
356 if p.allow_normalization() && needs_normalization(self.infcx, &p) {
357 p.try_super_fold_with(self)
358 } else {
359 Ok(p)
360 }
361 }
362}