]>
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; |
ba9703b0 XL |
15 | use rustc_middle::ty::fold::{TypeFoldable, TypeFolder}; |
16 | use rustc_middle::ty::subst::Subst; | |
17 | use rustc_middle::ty::{self, Ty, TyCtxt}; | |
0531ce1d XL |
18 | |
19 | use super::NoSolution; | |
20 | ||
ba9703b0 | 21 | pub use rustc_middle::traits::query::NormalizationResult; |
74b04a01 | 22 | |
ba9703b0 | 23 | pub trait AtExt<'tcx> { |
fc512014 | 24 | fn normalize<T>(&self, value: T) -> Result<Normalized<'tcx, T>, NoSolution> |
ba9703b0 XL |
25 | where |
26 | T: TypeFoldable<'tcx>; | |
27 | } | |
28 | ||
29 | impl<'cx, 'tcx> AtExt<'tcx> for At<'cx, 'tcx> { | |
0531ce1d XL |
30 | /// Normalize `value` in the context of the inference context, |
31 | /// yielding a resulting type, or an error if `value` cannot be | |
32 | /// normalized. If you don't care about regions, you should prefer | |
33 | /// `normalize_erasing_regions`, which is more efficient. | |
34 | /// | |
94b46f34 | 35 | /// If the normalization succeeds and is unambiguous, returns back |
0531ce1d XL |
36 | /// the normalized value along with various outlives relations (in |
37 | /// the form of obligations that must be discharged). | |
38 | /// | |
9fa01778 | 39 | /// N.B., this will *eventually* be the main means of |
0531ce1d XL |
40 | /// normalizing, but for now should be used only when we actually |
41 | /// know that normalization will succeed, since error reporting | |
42 | /// and other details are still "under development". | |
fc512014 | 43 | fn normalize<T>(&self, value: T) -> Result<Normalized<'tcx, T>, NoSolution> |
0531ce1d XL |
44 | where |
45 | T: TypeFoldable<'tcx>, | |
46 | { | |
47 | debug!( | |
48 | "normalize::<{}>(value={:?}, param_env={:?})", | |
29967ef6 | 49 | std::any::type_name::<T>(), |
0531ce1d XL |
50 | value, |
51 | self.param_env, | |
52 | ); | |
136023e0 | 53 | if !needs_normalization(&value, self.param_env.reveal()) { |
fc512014 | 54 | return Ok(Normalized { value, obligations: vec![] }); |
0bf4aa26 XL |
55 | } |
56 | ||
0531ce1d XL |
57 | let mut normalizer = QueryNormalizer { |
58 | infcx: self.infcx, | |
59 | cause: self.cause, | |
60 | param_env: self.param_env, | |
61 | obligations: vec![], | |
62 | error: false, | |
29967ef6 | 63 | cache: SsoHashMap::new(), |
0531ce1d | 64 | anon_depth: 0, |
136023e0 | 65 | universes: vec![], |
0531ce1d | 66 | }; |
0531ce1d | 67 | |
ba9703b0 | 68 | let result = value.fold_with(&mut normalizer); |
136023e0 | 69 | info!( |
ba9703b0 | 70 | "normalize::<{}>: result={:?} with {} obligations", |
29967ef6 | 71 | std::any::type_name::<T>(), |
ba9703b0 XL |
72 | result, |
73 | normalizer.obligations.len(), | |
74 | ); | |
75 | debug!( | |
76 | "normalize::<{}>: obligations={:?}", | |
29967ef6 | 77 | std::any::type_name::<T>(), |
ba9703b0 XL |
78 | normalizer.obligations, |
79 | ); | |
0531ce1d XL |
80 | if normalizer.error { |
81 | Err(NoSolution) | |
82 | } else { | |
ba9703b0 | 83 | Ok(Normalized { value: result, obligations: normalizer.obligations }) |
0531ce1d XL |
84 | } |
85 | } | |
86 | } | |
87 | ||
dc9dc135 XL |
88 | struct QueryNormalizer<'cx, 'tcx> { |
89 | infcx: &'cx InferCtxt<'cx, 'tcx>, | |
0531ce1d XL |
90 | cause: &'cx ObligationCause<'tcx>, |
91 | param_env: ty::ParamEnv<'tcx>, | |
92 | obligations: Vec<PredicateObligation<'tcx>>, | |
29967ef6 | 93 | cache: SsoHashMap<Ty<'tcx>, Ty<'tcx>>, |
0531ce1d XL |
94 | error: bool, |
95 | anon_depth: usize, | |
136023e0 | 96 | universes: Vec<Option<ty::UniverseIndex>>, |
0531ce1d XL |
97 | } |
98 | ||
dc9dc135 XL |
99 | impl<'cx, 'tcx> TypeFolder<'tcx> for QueryNormalizer<'cx, 'tcx> { |
100 | fn tcx<'c>(&'c self) -> TyCtxt<'tcx> { | |
0531ce1d XL |
101 | self.infcx.tcx |
102 | } | |
103 | ||
136023e0 XL |
104 | fn fold_binder<T: TypeFoldable<'tcx>>( |
105 | &mut self, | |
106 | t: ty::Binder<'tcx, T>, | |
107 | ) -> ty::Binder<'tcx, T> { | |
108 | self.universes.push(None); | |
109 | let t = t.super_fold_with(self); | |
110 | self.universes.pop(); | |
111 | t | |
112 | } | |
113 | ||
6a06907d | 114 | #[instrument(level = "debug", skip(self))] |
0531ce1d | 115 | fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> { |
136023e0 | 116 | if !needs_normalization(&ty, self.param_env.reveal()) { |
74b04a01 XL |
117 | return ty; |
118 | } | |
119 | ||
6c58768f XL |
120 | if let Some(ty) = self.cache.get(&ty) { |
121 | return ty; | |
122 | } | |
123 | ||
0531ce1d | 124 | let ty = ty.super_fold_with(self); |
1b1a35ee XL |
125 | let res = (|| match *ty.kind() { |
126 | ty::Opaque(def_id, substs) if !substs.has_escaping_bound_vars() => { | |
94b46f34 | 127 | // Only normalize `impl Trait` after type-checking, usually in codegen. |
f035d41b | 128 | match self.param_env.reveal() { |
0531ce1d XL |
129 | Reveal::UserFacing => ty, |
130 | ||
131 | Reveal::All => { | |
136023e0 | 132 | let recursion_limit = self.tcx().recursion_limit(); |
f9f354fc | 133 | if !recursion_limit.value_within_limit(self.anon_depth) { |
0531ce1d XL |
134 | let obligation = Obligation::with_depth( |
135 | self.cause.clone(), | |
f9f354fc | 136 | recursion_limit.0, |
0531ce1d XL |
137 | self.param_env, |
138 | ty, | |
139 | ); | |
140 | self.infcx.report_overflow_error(&obligation, true); | |
141 | } | |
142 | ||
143 | let generic_ty = self.tcx().type_of(def_id); | |
144 | let concrete_ty = generic_ty.subst(self.tcx(), substs); | |
145 | self.anon_depth += 1; | |
94b46f34 | 146 | if concrete_ty == ty { |
b7449926 XL |
147 | bug!( |
148 | "infinite recursion generic_ty: {:#?}, substs: {:#?}, \ | |
149 | concrete_ty: {:#?}, ty: {:#?}", | |
150 | generic_ty, | |
151 | substs, | |
152 | concrete_ty, | |
153 | ty | |
154 | ); | |
94b46f34 | 155 | } |
f9f354fc | 156 | let folded_ty = ensure_sufficient_stack(|| self.fold_ty(concrete_ty)); |
0531ce1d XL |
157 | self.anon_depth -= 1; |
158 | folded_ty | |
159 | } | |
160 | } | |
161 | } | |
162 | ||
fc512014 | 163 | ty::Projection(data) if !data.has_escaping_bound_vars() => { |
f9652781 | 164 | // This is kind of hacky -- we need to be able to |
0531ce1d XL |
165 | // handle normalization within binders because |
166 | // otherwise we wind up a need to normalize when doing | |
167 | // trait matching (since you can have a trait | |
f035d41b | 168 | // obligation like `for<'a> T::B: Fn(&'a i32)`), but |
0531ce1d XL |
169 | // we can't normalize with bound regions in scope. So |
170 | // far now we just ignore binders but only normalize | |
171 | // if all bound regions are gone (and then we still | |
172 | // have to renormalize whenever we instantiate a | |
173 | // binder). It would be better to normalize in a | |
174 | // binding-aware fashion. | |
175 | ||
e74abb32 | 176 | let tcx = self.infcx.tcx; |
0531ce1d | 177 | |
0bf4aa26 | 178 | let mut orig_values = OriginalQueryValues::default(); |
dc9dc135 XL |
179 | // HACK(matthewjasper) `'static` is special-cased in selection, |
180 | // so we cannot canonicalize it. | |
dfeec247 XL |
181 | let c_data = self |
182 | .infcx | |
136023e0 | 183 | .canonicalize_query_keep_static(self.param_env.and(data), &mut orig_values); |
0531ce1d XL |
184 | debug!("QueryNormalizer: c_data = {:#?}", c_data); |
185 | debug!("QueryNormalizer: orig_values = {:#?}", orig_values); | |
e74abb32 | 186 | match tcx.normalize_projection_ty(c_data) { |
0531ce1d XL |
187 | Ok(result) => { |
188 | // We don't expect ambiguity. | |
189 | if result.is_ambiguous() { | |
190 | self.error = true; | |
191 | return ty; | |
192 | } | |
193 | ||
0bf4aa26 | 194 | match self.infcx.instantiate_query_response_and_region_obligations( |
0531ce1d XL |
195 | self.cause, |
196 | self.param_env, | |
197 | &orig_values, | |
fc512014 | 198 | result, |
dfeec247 | 199 | ) { |
0bf4aa26 | 200 | Ok(InferOk { value: result, obligations }) => { |
0531ce1d XL |
201 | debug!("QueryNormalizer: result = {:#?}", result); |
202 | debug!("QueryNormalizer: obligations = {:#?}", obligations); | |
203 | self.obligations.extend(obligations); | |
ba9703b0 | 204 | result.normalized_ty |
0531ce1d XL |
205 | } |
206 | ||
207 | Err(_) => { | |
208 | self.error = true; | |
ba9703b0 | 209 | ty |
0531ce1d XL |
210 | } |
211 | } | |
212 | } | |
213 | ||
214 | Err(NoSolution) => { | |
215 | self.error = true; | |
216 | ty | |
217 | } | |
218 | } | |
219 | } | |
136023e0 XL |
220 | ty::Projection(data) if !data.trait_ref(self.infcx.tcx).has_escaping_bound_vars() => { |
221 | // See note in `rustc_trait_selection::traits::project` | |
222 | ||
223 | // One other point mentioning: In `traits::project`, if a | |
224 | // projection can't be normalized, we return an inference variable | |
225 | // and register an obligation to later resolve that. Here, the query | |
226 | // will just return ambiguity. In both cases, the effect is the same: we only want | |
227 | // to return `ty` because there are bound vars that we aren't yet handling in a more | |
228 | // complete way. | |
229 | ||
230 | // `BoundVarReplacer` can't handle escaping bound vars. Ideally, we want this before even calling | |
231 | // `QueryNormalizer`, but some const-generics tests pass escaping bound vars. | |
232 | // Also, use `ty` so we get that sweet `outer_exclusive_binder` optimization | |
233 | assert!(!ty.has_vars_bound_at_or_above(ty::DebruijnIndex::from_usize( | |
234 | self.universes.len() | |
235 | ))); | |
236 | ||
237 | let tcx = self.infcx.tcx; | |
238 | let infcx = self.infcx; | |
239 | let (data, mapped_regions, mapped_types, mapped_consts) = | |
240 | crate::traits::project::BoundVarReplacer::replace_bound_vars( | |
241 | infcx, | |
242 | &mut self.universes, | |
243 | data, | |
244 | ); | |
245 | let data = data.super_fold_with(self); | |
246 | ||
247 | let mut orig_values = OriginalQueryValues::default(); | |
248 | // HACK(matthewjasper) `'static` is special-cased in selection, | |
249 | // so we cannot canonicalize it. | |
250 | let c_data = self | |
251 | .infcx | |
252 | .canonicalize_query_keep_static(self.param_env.and(data), &mut orig_values); | |
253 | debug!("QueryNormalizer: c_data = {:#?}", c_data); | |
254 | debug!("QueryNormalizer: orig_values = {:#?}", orig_values); | |
255 | let normalized_ty = match tcx.normalize_projection_ty(c_data) { | |
256 | Ok(result) => { | |
257 | // We don't expect ambiguity. | |
258 | if result.is_ambiguous() { | |
259 | self.error = true; | |
260 | return ty; | |
261 | } | |
262 | match self.infcx.instantiate_query_response_and_region_obligations( | |
263 | self.cause, | |
264 | self.param_env, | |
265 | &orig_values, | |
266 | result, | |
267 | ) { | |
268 | Ok(InferOk { value: result, obligations }) => { | |
269 | debug!("QueryNormalizer: result = {:#?}", result); | |
270 | debug!("QueryNormalizer: obligations = {:#?}", obligations); | |
271 | self.obligations.extend(obligations); | |
272 | result.normalized_ty | |
273 | } | |
274 | Err(_) => { | |
275 | self.error = true; | |
276 | ty | |
277 | } | |
278 | } | |
279 | } | |
280 | Err(NoSolution) => { | |
281 | self.error = true; | |
282 | ty | |
283 | } | |
284 | }; | |
285 | crate::traits::project::PlaceholderReplacer::replace_placeholders( | |
286 | infcx, | |
287 | mapped_regions, | |
288 | mapped_types, | |
289 | mapped_consts, | |
290 | &self.universes, | |
291 | normalized_ty, | |
292 | ) | |
293 | } | |
0531ce1d XL |
294 | |
295 | _ => ty, | |
6c58768f XL |
296 | })(); |
297 | self.cache.insert(ty, res); | |
298 | res | |
0531ce1d XL |
299 | } |
300 | ||
532ac7d7 | 301 | fn fold_const(&mut self, constant: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> { |
ba9703b0 | 302 | let constant = constant.super_fold_with(self); |
e1599b0c | 303 | constant.eval(self.infcx.tcx, self.param_env) |
0531ce1d | 304 | } |
cdc7bbd5 XL |
305 | |
306 | fn fold_mir_const(&mut self, constant: mir::ConstantKind<'tcx>) -> mir::ConstantKind<'tcx> { | |
307 | constant.super_fold_with(self) | |
308 | } | |
0531ce1d | 309 | } |