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