1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 //! Code for the 'normalization' query. This consists of a wrapper
12 //! which folds deeply, invoking the underlying
13 //! `normalize_projection_ty` query when it encounters projections.
15 use infer::{InferCtxt, InferOk};
17 use infer::canonical::{Canonical, Canonicalize, QueryResult};
18 use middle::const_val::ConstVal;
19 use mir::interpret::GlobalId;
20 use rustc_data_structures::sync::Lrc;
21 use traits::{Obligation, ObligationCause, PredicateObligation, Reveal};
22 use traits::query::CanonicalProjectionGoal;
23 use traits::project::Normalized;
24 use ty::{self, Ty, TyCtxt};
25 use ty::fold::{TypeFoldable, TypeFolder};
26 use ty::subst::{Subst, Substs};
28 use super::NoSolution;
30 impl<'cx, 'gcx, 'tcx> At<'cx, 'gcx, 'tcx> {
31 /// Normalize `value` in the context of the inference context,
32 /// yielding a resulting type, or an error if `value` cannot be
33 /// normalized. If you don't care about regions, you should prefer
34 /// `normalize_erasing_regions`, which is more efficient.
36 /// If the normalization succeeds and is unambiguous, returns back
37 /// the normalized value along with various outlives relations (in
38 /// the form of obligations that must be discharged).
40 /// NB. This will *eventually* be the main means of
41 /// normalizing, but for now should be used only when we actually
42 /// know that normalization will succeed, since error reporting
43 /// and other details are still "under development".
44 pub fn normalize<T>(&self, value: &T) -> Result<Normalized<'tcx, T>, NoSolution>
46 T: TypeFoldable<'tcx>,
49 "normalize::<{}>(value={:?}, param_env={:?})",
50 unsafe { ::std::intrinsics::type_name::<T>() },
54 let mut normalizer = QueryNormalizer {
57 param_env: self.param_env,
62 if !value.has_projections() {
63 return Ok(Normalized {
69 let value1 = value.fold_with(&mut normalizer);
75 obligations: normalizer.obligations,
81 /// Result from the `normalize_projection_ty` query.
82 #[derive(Clone, Debug)]
83 pub struct NormalizationResult<'tcx> {
84 /// Result of normalization.
85 pub normalized_ty: Ty<'tcx>,
88 struct QueryNormalizer<'cx, 'gcx: 'tcx, 'tcx: 'cx> {
89 infcx: &'cx InferCtxt<'cx, 'gcx, 'tcx>,
90 cause: &'cx ObligationCause<'tcx>,
91 param_env: ty::ParamEnv<'tcx>,
92 obligations: Vec<PredicateObligation<'tcx>>,
97 impl<'cx, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for QueryNormalizer<'cx, 'gcx, 'tcx> {
98 fn tcx<'c>(&'c self) -> TyCtxt<'c, 'gcx, 'tcx> {
102 fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
103 let ty = ty.super_fold_with(self);
105 ty::TyAnon(def_id, substs) if !substs.has_escaping_regions() => {
107 // Only normalize `impl Trait` after type-checking, usually in codegen.
108 match self.param_env.reveal {
109 Reveal::UserFacing => ty,
112 let recursion_limit = *self.tcx().sess.recursion_limit.get();
113 if self.anon_depth >= recursion_limit {
114 let obligation = Obligation::with_depth(
120 self.infcx.report_overflow_error(&obligation, true);
123 let generic_ty = self.tcx().type_of(def_id);
124 let concrete_ty = generic_ty.subst(self.tcx(), substs);
125 self.anon_depth += 1;
126 if concrete_ty == ty {
127 println!("generic_ty: {:#?}", generic_ty);
128 println!("substs {:#?}", substs);
130 assert_ne!(concrete_ty, ty, "infinite recursion");
131 let folded_ty = self.fold_ty(concrete_ty);
132 self.anon_depth -= 1;
138 ty::TyProjection(ref data) if !data.has_escaping_regions() => {
140 // (*) This is kind of hacky -- we need to be able to
141 // handle normalization within binders because
142 // otherwise we wind up a need to normalize when doing
143 // trait matching (since you can have a trait
144 // obligation like `for<'a> T::B : Fn(&'a int)`), but
145 // we can't normalize with bound regions in scope. So
146 // far now we just ignore binders but only normalize
147 // if all bound regions are gone (and then we still
148 // have to renormalize whenever we instantiate a
149 // binder). It would be better to normalize in a
150 // binding-aware fashion.
152 let gcx = self.infcx.tcx.global_tcx();
154 let (c_data, orig_values) =
155 self.infcx.canonicalize_query(&self.param_env.and(*data));
156 debug!("QueryNormalizer: c_data = {:#?}", c_data);
157 debug!("QueryNormalizer: orig_values = {:#?}", orig_values);
158 match gcx.normalize_projection_ty(c_data) {
160 // We don't expect ambiguity.
161 if result.is_ambiguous() {
166 match self.infcx.instantiate_query_result(
176 debug!("QueryNormalizer: result = {:#?}", result);
177 debug!("QueryNormalizer: obligations = {:#?}", obligations);
178 self.obligations.extend(obligations);
179 return result.normalized_ty;
200 fn fold_const(&mut self, constant: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> {
201 if let ConstVal::Unevaluated(def_id, substs) = constant.val {
202 let tcx = self.infcx.tcx.global_tcx();
203 if let Some(param_env) = self.tcx().lift_to_global(&self.param_env) {
204 if substs.needs_infer() || substs.has_skol() {
205 let identity_substs = Substs::identity_for_item(tcx, def_id);
206 let instance = ty::Instance::resolve(tcx, param_env, def_id, identity_substs);
207 if let Some(instance) = instance {
212 match tcx.const_eval(param_env.and(cid)) {
214 let evaluated = evaluated.subst(self.tcx(), substs);
215 return self.fold_const(evaluated);
221 if let Some(substs) = self.tcx().lift_to_global(&substs) {
222 let instance = ty::Instance::resolve(tcx, param_env, def_id, substs);
223 if let Some(instance) = instance {
228 match tcx.const_eval(param_env.and(cid)) {
229 Ok(evaluated) => return self.fold_const(evaluated),
241 BraceStructTypeFoldableImpl! {
242 impl<'tcx> TypeFoldable<'tcx> for NormalizationResult<'tcx> {
247 BraceStructLiftImpl! {
248 impl<'a, 'tcx> Lift<'tcx> for NormalizationResult<'a> {
249 type Lifted = NormalizationResult<'tcx>;
254 impl<'gcx: 'tcx, 'tcx> Canonicalize<'gcx, 'tcx> for ty::ParamEnvAnd<'tcx, ty::ProjectionTy<'tcx>> {
255 type Canonicalized = CanonicalProjectionGoal<'gcx>;
258 _gcx: TyCtxt<'_, 'gcx, 'gcx>,
259 value: Canonical<'gcx, Self::Lifted>,
260 ) -> Self::Canonicalized {
265 impl<'gcx: 'tcx, 'tcx> Canonicalize<'gcx, 'tcx> for QueryResult<'tcx, NormalizationResult<'tcx>> {
266 // we ought to intern this, but I'm too lazy just now
267 type Canonicalized = Lrc<Canonical<'gcx, QueryResult<'gcx, NormalizationResult<'gcx>>>>;
270 _gcx: TyCtxt<'_, 'gcx, 'gcx>,
271 value: Canonical<'gcx, Self::Lifted>,
272 ) -> Self::Canonicalized {
277 impl_stable_hash_for!(struct NormalizationResult<'tcx> {