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.
5 use crate::infer
::at
::At
;
6 use crate::infer
::canonical
::OriginalQueryValues
;
7 use crate::infer
::{InferCtxt, InferOk}
;
8 use crate::traits
::error_reporting
::InferCtxtExt
;
9 use crate::traits
::{Obligation, ObligationCause, PredicateObligation, Reveal}
;
10 use rustc_data_structures
::mini_map
::MiniMap
;
11 use rustc_data_structures
::stack
::ensure_sufficient_stack
;
12 use rustc_infer
::traits
::Normalized
;
13 use rustc_middle
::ty
::fold
::{TypeFoldable, TypeFolder}
;
14 use rustc_middle
::ty
::subst
::Subst
;
15 use rustc_middle
::ty
::{self, Ty, TyCtxt}
;
17 use super::NoSolution
;
19 pub use rustc_middle
::traits
::query
::NormalizationResult
;
21 pub trait AtExt
<'tcx
> {
22 fn normalize
<T
>(&self, value
: &T
) -> Result
<Normalized
<'tcx
, T
>, NoSolution
>
24 T
: TypeFoldable
<'tcx
>;
27 impl<'cx
, 'tcx
> AtExt
<'tcx
> for At
<'cx
, 'tcx
> {
28 /// Normalize `value` in the context of the inference context,
29 /// yielding a resulting type, or an error if `value` cannot be
30 /// normalized. If you don't care about regions, you should prefer
31 /// `normalize_erasing_regions`, which is more efficient.
33 /// If the normalization succeeds and is unambiguous, returns back
34 /// the normalized value along with various outlives relations (in
35 /// the form of obligations that must be discharged).
37 /// N.B., this will *eventually* be the main means of
38 /// normalizing, but for now should be used only when we actually
39 /// know that normalization will succeed, since error reporting
40 /// and other details are still "under development".
41 fn normalize
<T
>(&self, value
: &T
) -> Result
<Normalized
<'tcx
, T
>, NoSolution
>
43 T
: TypeFoldable
<'tcx
>,
46 "normalize::<{}>(value={:?}, param_env={:?})",
47 ::std
::any
::type_name
::<T
>(),
51 if !value
.has_projections() {
52 return Ok(Normalized { value: value.clone(), obligations: vec![] }
);
55 let mut normalizer
= QueryNormalizer
{
58 param_env
: self.param_env
,
61 cache
: MiniMap
::new(),
65 let result
= value
.fold_with(&mut normalizer
);
67 "normalize::<{}>: result={:?} with {} obligations",
68 ::std
::any
::type_name
::<T
>(),
70 normalizer
.obligations
.len(),
73 "normalize::<{}>: obligations={:?}",
74 ::std
::any
::type_name
::<T
>(),
75 normalizer
.obligations
,
80 Ok(Normalized { value: result, obligations: normalizer.obligations }
)
85 struct QueryNormalizer
<'cx
, 'tcx
> {
86 infcx
: &'cx InferCtxt
<'cx
, 'tcx
>,
87 cause
: &'cx ObligationCause
<'tcx
>,
88 param_env
: ty
::ParamEnv
<'tcx
>,
89 obligations
: Vec
<PredicateObligation
<'tcx
>>,
90 cache
: MiniMap
<Ty
<'tcx
>, Ty
<'tcx
>>,
95 impl<'cx
, 'tcx
> TypeFolder
<'tcx
> for QueryNormalizer
<'cx
, 'tcx
> {
96 fn tcx
<'c
>(&'c
self) -> TyCtxt
<'tcx
> {
100 fn fold_ty(&mut self, ty
: Ty
<'tcx
>) -> Ty
<'tcx
> {
101 if !ty
.has_projections() {
105 if let Some(ty
) = self.cache
.get(&ty
) {
109 let ty
= ty
.super_fold_with(self);
110 let res
= (|| match ty
.kind
{
111 ty
::Opaque(def_id
, substs
) => {
112 // Only normalize `impl Trait` after type-checking, usually in codegen.
113 match self.param_env
.reveal() {
114 Reveal
::UserFacing
=> ty
,
117 let recursion_limit
= self.tcx().sess
.recursion_limit();
118 if !recursion_limit
.value_within_limit(self.anon_depth
) {
119 let obligation
= Obligation
::with_depth(
125 self.infcx
.report_overflow_error(&obligation
, true);
128 let generic_ty
= self.tcx().type_of(def_id
);
129 let concrete_ty
= generic_ty
.subst(self.tcx(), substs
);
130 self.anon_depth
+= 1;
131 if concrete_ty
== ty
{
133 "infinite recursion generic_ty: {:#?}, substs: {:#?}, \
134 concrete_ty: {:#?}, ty: {:#?}",
141 let folded_ty
= ensure_sufficient_stack(|| self.fold_ty(concrete_ty
));
142 self.anon_depth
-= 1;
148 ty
::Projection(ref data
) if !data
.has_escaping_bound_vars() => {
149 // This is kind of hacky -- we need to be able to
150 // handle normalization within binders because
151 // otherwise we wind up a need to normalize when doing
152 // trait matching (since you can have a trait
153 // obligation like `for<'a> T::B: Fn(&'a i32)`), but
154 // we can't normalize with bound regions in scope. So
155 // far now we just ignore binders but only normalize
156 // if all bound regions are gone (and then we still
157 // have to renormalize whenever we instantiate a
158 // binder). It would be better to normalize in a
159 // binding-aware fashion.
161 let tcx
= self.infcx
.tcx
;
163 let mut orig_values
= OriginalQueryValues
::default();
164 // HACK(matthewjasper) `'static` is special-cased in selection,
165 // so we cannot canonicalize it.
168 .canonicalize_hr_query_hack(&self.param_env
.and(*data
), &mut orig_values
);
169 debug
!("QueryNormalizer: c_data = {:#?}", c_data
);
170 debug
!("QueryNormalizer: orig_values = {:#?}", orig_values
);
171 match tcx
.normalize_projection_ty(c_data
) {
173 // We don't expect ambiguity.
174 if result
.is_ambiguous() {
179 match self.infcx
.instantiate_query_response_and_region_obligations(
185 Ok(InferOk { value: result, obligations }
) => {
186 debug
!("QueryNormalizer: result = {:#?}", result
);
187 debug
!("QueryNormalizer: obligations = {:#?}", obligations
);
188 self.obligations
.extend(obligations
);
208 self.cache
.insert(ty
, res
);
212 fn fold_const(&mut self, constant
: &'tcx ty
::Const
<'tcx
>) -> &'tcx ty
::Const
<'tcx
> {
213 let constant
= constant
.super_fold_with(self);
214 constant
.eval(self.infcx
.tcx
, self.param_env
)