]>
Commit | Line | Data |
---|---|---|
0531ce1d XL |
1 | //! Code for the 'normalization' query. This consists of a wrapper |
2 | //! which folds deeply, invoking the underlying | |
3 | //! `normalize_projection_ty` query when it encounters projections. | |
4 | ||
9fa01778 XL |
5 | use crate::infer::at::At; |
6 | use crate::infer::canonical::OriginalQueryValues; | |
7 | use crate::infer::{InferCtxt, InferOk}; | |
2b03887a | 8 | use crate::traits::error_reporting::TypeErrCtxtExt; |
f2b60f7d | 9 | use crate::traits::project::{needs_normalization, BoundVarReplacer, PlaceholderReplacer}; |
487cf647 | 10 | use crate::traits::{ObligationCause, PredicateObligation, Reveal}; |
29967ef6 | 11 | use rustc_data_structures::sso::SsoHashMap; |
f9f354fc | 12 | use rustc_data_structures::stack::ensure_sufficient_stack; |
ba9703b0 | 13 | use rustc_infer::traits::Normalized; |
064997fb | 14 | use rustc_middle::ty::fold::{FallibleTypeFolder, TypeFoldable, TypeSuperFoldable}; |
9ffffee4 | 15 | use rustc_middle::ty::visit::{TypeSuperVisitable, TypeVisitable, TypeVisitableExt}; |
94222f64 | 16 | use rustc_middle::ty::{self, Ty, TyCtxt, TypeVisitor}; |
2b03887a | 17 | use rustc_span::DUMMY_SP; |
94222f64 XL |
18 | |
19 | use std::ops::ControlFlow; | |
0531ce1d XL |
20 | |
21 | use super::NoSolution; | |
22 | ||
ba9703b0 | 23 | pub use rustc_middle::traits::query::NormalizationResult; |
74b04a01 | 24 | |
487cf647 FG |
25 | pub trait QueryNormalizeExt<'tcx> { |
26 | /// Normalize a value using the `QueryNormalizer`. | |
27 | /// | |
28 | /// This normalization should *only* be used when the projection does not | |
29 | /// have possible ambiguity or may not be well-formed. | |
30 | /// | |
31 | /// After codegen, when lifetimes do not matter, it is preferable to instead | |
32 | /// use [`TyCtxt::normalize_erasing_regions`], which wraps this procedure. | |
33 | fn query_normalize<T>(&self, value: T) -> Result<Normalized<'tcx, T>, NoSolution> | |
ba9703b0 | 34 | where |
9ffffee4 | 35 | T: TypeFoldable<TyCtxt<'tcx>>; |
ba9703b0 XL |
36 | } |
37 | ||
487cf647 | 38 | impl<'cx, 'tcx> QueryNormalizeExt<'tcx> for At<'cx, 'tcx> { |
0531ce1d XL |
39 | /// Normalize `value` in the context of the inference context, |
40 | /// yielding a resulting type, or an error if `value` cannot be | |
41 | /// normalized. If you don't care about regions, you should prefer | |
42 | /// `normalize_erasing_regions`, which is more efficient. | |
43 | /// | |
94b46f34 | 44 | /// If the normalization succeeds and is unambiguous, returns back |
0531ce1d XL |
45 | /// the normalized value along with various outlives relations (in |
46 | /// the form of obligations that must be discharged). | |
47 | /// | |
9fa01778 | 48 | /// N.B., this will *eventually* be the main means of |
0531ce1d XL |
49 | /// normalizing, but for now should be used only when we actually |
50 | /// know that normalization will succeed, since error reporting | |
51 | /// and other details are still "under development". | |
487cf647 | 52 | fn query_normalize<T>(&self, value: T) -> Result<Normalized<'tcx, T>, NoSolution> |
0531ce1d | 53 | where |
9ffffee4 | 54 | T: TypeFoldable<TyCtxt<'tcx>>, |
0531ce1d XL |
55 | { |
56 | debug!( | |
f2b60f7d | 57 | "normalize::<{}>(value={:?}, param_env={:?}, cause={:?})", |
29967ef6 | 58 | std::any::type_name::<T>(), |
0531ce1d XL |
59 | value, |
60 | self.param_env, | |
f2b60f7d | 61 | self.cause, |
0531ce1d | 62 | ); |
136023e0 | 63 | if !needs_normalization(&value, self.param_env.reveal()) { |
fc512014 | 64 | return Ok(Normalized { value, obligations: vec![] }); |
0bf4aa26 XL |
65 | } |
66 | ||
0531ce1d XL |
67 | let mut normalizer = QueryNormalizer { |
68 | infcx: self.infcx, | |
69 | cause: self.cause, | |
70 | param_env: self.param_env, | |
71 | obligations: vec![], | |
29967ef6 | 72 | cache: SsoHashMap::new(), |
0531ce1d | 73 | anon_depth: 0, |
136023e0 | 74 | universes: vec![], |
0531ce1d | 75 | }; |
0531ce1d | 76 | |
94222f64 XL |
77 | // This is actually a consequence by the way `normalize_erasing_regions` works currently. |
78 | // Because it needs to call the `normalize_generic_arg_after_erasing_regions`, it folds | |
79 | // through tys and consts in a `TypeFoldable`. Importantly, it skips binders, leaving us | |
80 | // with trying to normalize with escaping bound vars. | |
81 | // | |
82 | // Here, we just add the universes that we *would* have created had we passed through the binders. | |
83 | // | |
84 | // We *could* replace escaping bound vars eagerly here, but it doesn't seem really necessary. | |
85 | // The rest of the code is already set up to be lazy about replacing bound vars, | |
86 | // and only when we actually have to normalize. | |
87 | if value.has_escaping_bound_vars() { | |
5099ac24 FG |
88 | let mut max_visitor = |
89 | MaxEscapingBoundVarVisitor { outer_index: ty::INNERMOST, escaping: 0 }; | |
94222f64 XL |
90 | value.visit_with(&mut max_visitor); |
91 | if max_visitor.escaping > 0 { | |
92 | normalizer.universes.extend((0..max_visitor.escaping).map(|_| None)); | |
93 | } | |
94 | } | |
a2a8927a | 95 | let result = value.try_fold_with(&mut normalizer); |
136023e0 | 96 | info!( |
ba9703b0 | 97 | "normalize::<{}>: result={:?} with {} obligations", |
29967ef6 | 98 | std::any::type_name::<T>(), |
ba9703b0 XL |
99 | result, |
100 | normalizer.obligations.len(), | |
101 | ); | |
102 | debug!( | |
103 | "normalize::<{}>: obligations={:?}", | |
29967ef6 | 104 | std::any::type_name::<T>(), |
ba9703b0 XL |
105 | normalizer.obligations, |
106 | ); | |
a2a8927a | 107 | result.map(|value| Normalized { value, obligations: normalizer.obligations }) |
0531ce1d XL |
108 | } |
109 | } | |
110 | ||
923072b8 | 111 | // Visitor to find the maximum escaping bound var |
5099ac24 | 112 | struct MaxEscapingBoundVarVisitor { |
94222f64 XL |
113 | // The index which would count as escaping |
114 | outer_index: ty::DebruijnIndex, | |
115 | escaping: usize, | |
116 | } | |
117 | ||
9ffffee4 FG |
118 | impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for MaxEscapingBoundVarVisitor { |
119 | fn visit_binder<T: TypeVisitable<TyCtxt<'tcx>>>( | |
94222f64 XL |
120 | &mut self, |
121 | t: &ty::Binder<'tcx, T>, | |
122 | ) -> ControlFlow<Self::BreakTy> { | |
123 | self.outer_index.shift_in(1); | |
124 | let result = t.super_visit_with(self); | |
125 | self.outer_index.shift_out(1); | |
126 | result | |
127 | } | |
128 | ||
129 | #[inline] | |
130 | fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> { | |
131 | if t.outer_exclusive_binder() > self.outer_index { | |
132 | self.escaping = self | |
133 | .escaping | |
134 | .max(t.outer_exclusive_binder().as_usize() - self.outer_index.as_usize()); | |
135 | } | |
9c376795 | 136 | ControlFlow::Continue(()) |
94222f64 XL |
137 | } |
138 | ||
139 | #[inline] | |
140 | fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> { | |
141 | match *r { | |
142 | ty::ReLateBound(debruijn, _) if debruijn > self.outer_index => { | |
143 | self.escaping = | |
144 | self.escaping.max(debruijn.as_usize() - self.outer_index.as_usize()); | |
145 | } | |
146 | _ => {} | |
147 | } | |
9c376795 | 148 | ControlFlow::Continue(()) |
94222f64 XL |
149 | } |
150 | ||
5099ac24 | 151 | fn visit_const(&mut self, ct: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> { |
923072b8 | 152 | match ct.kind() { |
94222f64 XL |
153 | ty::ConstKind::Bound(debruijn, _) if debruijn >= self.outer_index => { |
154 | self.escaping = | |
155 | self.escaping.max(debruijn.as_usize() - self.outer_index.as_usize()); | |
9c376795 | 156 | ControlFlow::Continue(()) |
94222f64 XL |
157 | } |
158 | _ => ct.super_visit_with(self), | |
159 | } | |
160 | } | |
161 | } | |
162 | ||
dc9dc135 | 163 | struct QueryNormalizer<'cx, 'tcx> { |
2b03887a | 164 | infcx: &'cx InferCtxt<'tcx>, |
0531ce1d XL |
165 | cause: &'cx ObligationCause<'tcx>, |
166 | param_env: ty::ParamEnv<'tcx>, | |
167 | obligations: Vec<PredicateObligation<'tcx>>, | |
29967ef6 | 168 | cache: SsoHashMap<Ty<'tcx>, Ty<'tcx>>, |
0531ce1d | 169 | anon_depth: usize, |
136023e0 | 170 | universes: Vec<Option<ty::UniverseIndex>>, |
0531ce1d XL |
171 | } |
172 | ||
9ffffee4 | 173 | impl<'cx, 'tcx> FallibleTypeFolder<TyCtxt<'tcx>> for QueryNormalizer<'cx, 'tcx> { |
a2a8927a XL |
174 | type Error = NoSolution; |
175 | ||
9ffffee4 | 176 | fn interner(&self) -> TyCtxt<'tcx> { |
0531ce1d XL |
177 | self.infcx.tcx |
178 | } | |
179 | ||
9ffffee4 | 180 | fn try_fold_binder<T: TypeFoldable<TyCtxt<'tcx>>>( |
136023e0 XL |
181 | &mut self, |
182 | t: ty::Binder<'tcx, T>, | |
a2a8927a | 183 | ) -> Result<ty::Binder<'tcx, T>, Self::Error> { |
136023e0 | 184 | self.universes.push(None); |
a2a8927a | 185 | let t = t.try_super_fold_with(self); |
136023e0 XL |
186 | self.universes.pop(); |
187 | t | |
188 | } | |
189 | ||
6a06907d | 190 | #[instrument(level = "debug", skip(self))] |
a2a8927a | 191 | fn try_fold_ty(&mut self, ty: Ty<'tcx>) -> Result<Ty<'tcx>, Self::Error> { |
136023e0 | 192 | if !needs_normalization(&ty, self.param_env.reveal()) { |
a2a8927a | 193 | return Ok(ty); |
74b04a01 XL |
194 | } |
195 | ||
6c58768f | 196 | if let Some(ty) = self.cache.get(&ty) { |
5099ac24 | 197 | return Ok(*ty); |
6c58768f XL |
198 | } |
199 | ||
353b0b11 FG |
200 | let (kind, data) = match *ty.kind() { |
201 | ty::Alias(kind, data) => (kind, data), | |
202 | _ => { | |
203 | let res = ty.try_super_fold_with(self)?; | |
204 | self.cache.insert(ty, res); | |
205 | return Ok(res); | |
206 | } | |
207 | }; | |
208 | ||
94222f64 XL |
209 | // See note in `rustc_trait_selection::traits::project` about why we |
210 | // wait to fold the substs. | |
211 | ||
212 | // Wrap this in a closure so we don't accidentally return from the outer function | |
353b0b11 | 213 | let res = match kind { |
94222f64 XL |
214 | // This is really important. While we *can* handle this, this has |
215 | // severe performance implications for large opaque types with | |
216 | // late-bound regions. See `issue-88862` benchmark. | |
353b0b11 | 217 | ty::Opaque if !data.substs.has_escaping_bound_vars() => { |
5099ac24 | 218 | // Only normalize `impl Trait` outside of type inference, usually in codegen. |
f035d41b | 219 | match self.param_env.reveal() { |
9c376795 | 220 | Reveal::UserFacing => ty.try_super_fold_with(self)?, |
0531ce1d XL |
221 | |
222 | Reveal::All => { | |
353b0b11 | 223 | let substs = data.substs.try_fold_with(self)?; |
9ffffee4 | 224 | let recursion_limit = self.interner().recursion_limit(); |
f9f354fc | 225 | if !recursion_limit.value_within_limit(self.anon_depth) { |
9ffffee4 FG |
226 | // A closure or generator may have itself as in its upvars. |
227 | // This should be checked handled by the recursion check for opaque | |
228 | // types, but we may end up here before that check can happen. | |
229 | // In that case, we delay a bug to mark the trip, and continue without | |
230 | // revealing the opaque. | |
231 | self.infcx | |
232 | .err_ctxt() | |
233 | .build_overflow_error(&ty, self.cause.span, true) | |
234 | .delay_as_bug(); | |
235 | return ty.try_super_fold_with(self); | |
0531ce1d XL |
236 | } |
237 | ||
353b0b11 | 238 | let generic_ty = self.interner().type_of(data.def_id); |
9ffffee4 | 239 | let concrete_ty = generic_ty.subst(self.interner(), substs); |
0531ce1d | 240 | self.anon_depth += 1; |
94b46f34 | 241 | if concrete_ty == ty { |
b7449926 XL |
242 | bug!( |
243 | "infinite recursion generic_ty: {:#?}, substs: {:#?}, \ | |
244 | concrete_ty: {:#?}, ty: {:#?}", | |
245 | generic_ty, | |
246 | substs, | |
247 | concrete_ty, | |
248 | ty | |
249 | ); | |
94b46f34 | 250 | } |
a2a8927a | 251 | let folded_ty = ensure_sufficient_stack(|| self.try_fold_ty(concrete_ty)); |
0531ce1d | 252 | self.anon_depth -= 1; |
9c376795 | 253 | folded_ty? |
0531ce1d XL |
254 | } |
255 | } | |
256 | } | |
257 | ||
353b0b11 | 258 | ty::Opaque => ty.try_super_fold_with(self)?, |
136023e0 | 259 | |
353b0b11 | 260 | ty::Projection => { |
94222f64 | 261 | // See note in `rustc_trait_selection::traits::project` |
136023e0 XL |
262 | |
263 | let tcx = self.infcx.tcx; | |
264 | let infcx = self.infcx; | |
353b0b11 FG |
265 | // Just an optimization: When we don't have escaping bound vars, |
266 | // we don't need to replace them with placeholders. | |
267 | let (data, maps) = if data.has_escaping_bound_vars() { | |
268 | let (data, mapped_regions, mapped_types, mapped_consts) = | |
269 | BoundVarReplacer::replace_bound_vars(infcx, &mut self.universes, data); | |
270 | (data, Some((mapped_regions, mapped_types, mapped_consts))) | |
271 | } else { | |
272 | (data, None) | |
273 | }; | |
923072b8 | 274 | let data = data.try_fold_with(self)?; |
136023e0 XL |
275 | |
276 | let mut orig_values = OriginalQueryValues::default(); | |
277 | // HACK(matthewjasper) `'static` is special-cased in selection, | |
278 | // so we cannot canonicalize it. | |
279 | let c_data = self | |
280 | .infcx | |
281 | .canonicalize_query_keep_static(self.param_env.and(data), &mut orig_values); | |
282 | debug!("QueryNormalizer: c_data = {:#?}", c_data); | |
283 | debug!("QueryNormalizer: orig_values = {:#?}", orig_values); | |
a2a8927a XL |
284 | let result = tcx.normalize_projection_ty(c_data)?; |
285 | // We don't expect ambiguity. | |
286 | if result.is_ambiguous() { | |
2b03887a FG |
287 | // Rustdoc normalizes possibly not well-formed types, so only |
288 | // treat this as a bug if we're not in rustdoc. | |
289 | if !tcx.sess.opts.actually_rustdoc { | |
290 | tcx.sess.delay_span_bug( | |
291 | DUMMY_SP, | |
292 | format!("unexpected ambiguity: {:?} {:?}", c_data, result), | |
293 | ); | |
294 | } | |
295 | return Err(NoSolution); | |
94222f64 | 296 | } |
a2a8927a XL |
297 | let InferOk { value: result, obligations } = |
298 | self.infcx.instantiate_query_response_and_region_obligations( | |
299 | self.cause, | |
300 | self.param_env, | |
301 | &orig_values, | |
302 | result, | |
303 | )?; | |
304 | debug!("QueryNormalizer: result = {:#?}", result); | |
305 | debug!("QueryNormalizer: obligations = {:#?}", obligations); | |
306 | self.obligations.extend(obligations); | |
353b0b11 FG |
307 | let res = if let Some((mapped_regions, mapped_types, mapped_consts)) = maps { |
308 | PlaceholderReplacer::replace_placeholders( | |
309 | infcx, | |
310 | mapped_regions, | |
311 | mapped_types, | |
312 | mapped_consts, | |
313 | &self.universes, | |
314 | result.normalized_ty, | |
315 | ) | |
316 | } else { | |
317 | result.normalized_ty | |
318 | }; | |
f2b60f7d FG |
319 | // `tcx.normalize_projection_ty` may normalize to a type that still has |
320 | // unevaluated consts, so keep normalizing here if that's the case. | |
321 | if res != ty && res.has_type_flags(ty::TypeFlags::HAS_CT_PROJECTION) { | |
9c376795 | 322 | res.try_super_fold_with(self)? |
f2b60f7d | 323 | } else { |
9c376795 | 324 | res |
f2b60f7d | 325 | } |
136023e0 | 326 | } |
9c376795 | 327 | }; |
f2b60f7d | 328 | |
6c58768f | 329 | self.cache.insert(ty, res); |
a2a8927a | 330 | Ok(res) |
0531ce1d XL |
331 | } |
332 | ||
a2a8927a XL |
333 | fn try_fold_const( |
334 | &mut self, | |
5099ac24 FG |
335 | constant: ty::Const<'tcx>, |
336 | ) -> Result<ty::Const<'tcx>, Self::Error> { | |
487cf647 FG |
337 | if !needs_normalization(&constant, self.param_env.reveal()) { |
338 | return Ok(constant); | |
339 | } | |
340 | ||
a2a8927a | 341 | let constant = constant.try_super_fold_with(self)?; |
f2b60f7d FG |
342 | debug!(?constant, ?self.param_env); |
343 | Ok(crate::traits::project::with_replaced_escaping_bound_vars( | |
344 | self.infcx, | |
345 | &mut self.universes, | |
346 | constant, | |
347 | |constant| constant.eval(self.infcx.tcx, self.param_env), | |
348 | )) | |
0531ce1d | 349 | } |
cdc7bbd5 | 350 | |
f2b60f7d FG |
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(&p, self.param_env.reveal()) { | |
357 | p.try_super_fold_with(self) | |
358 | } else { | |
359 | Ok(p) | |
360 | } | |
361 | } | |
0531ce1d | 362 | } |