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.
16 use infer::{InferCtxt, InferOk};
17 use mir::interpret::{ConstValue, GlobalId};
18 use smallvec::SmallVec;
19 use traits::project::Normalized;
20 use traits::{Obligation, ObligationCause, PredicateObligation, Reveal};
21 use ty::fold::{TypeFoldable, TypeFolder};
22 use ty::subst::{Subst, Substs};
23 use ty::{self, Ty, TyCtxt};
25 use super::NoSolution;
27 impl<'cx, 'gcx, 'tcx> At<'cx, 'gcx, '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 /// NB. 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 pub fn normalize<T>(&self, value: &T) -> Result<Normalized<'tcx, T>, NoSolution>
43 T: TypeFoldable<'tcx>,
46 "normalize::<{}>(value={:?}, param_env={:?})",
47 unsafe { ::std::intrinsics::type_name::<T>() },
51 let mut normalizer = QueryNormalizer {
54 param_env: self.param_env,
59 if !value.has_projections() {
60 return Ok(Normalized {
66 let value1 = value.fold_with(&mut normalizer);
72 obligations: normalizer.obligations,
78 /// Result from the `normalize_projection_ty` query.
79 #[derive(Clone, Debug)]
80 pub struct NormalizationResult<'tcx> {
81 /// Result of normalization.
82 pub normalized_ty: Ty<'tcx>,
85 struct QueryNormalizer<'cx, 'gcx: 'tcx, 'tcx: 'cx> {
86 infcx: &'cx InferCtxt<'cx, 'gcx, 'tcx>,
87 cause: &'cx ObligationCause<'tcx>,
88 param_env: ty::ParamEnv<'tcx>,
89 obligations: Vec<PredicateObligation<'tcx>>,
94 impl<'cx, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for QueryNormalizer<'cx, 'gcx, 'tcx> {
95 fn tcx<'c>(&'c self) -> TyCtxt<'c, 'gcx, 'tcx> {
99 fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
100 let ty = ty.super_fold_with(self);
102 ty::Opaque(def_id, substs) if !substs.has_escaping_regions() => {
104 // Only normalize `impl Trait` after type-checking, usually in codegen.
105 match self.param_env.reveal {
106 Reveal::UserFacing => ty,
109 let recursion_limit = *self.tcx().sess.recursion_limit.get();
110 if self.anon_depth >= recursion_limit {
111 let obligation = Obligation::with_depth(
117 self.infcx.report_overflow_error(&obligation, true);
120 let generic_ty = self.tcx().type_of(def_id);
121 let concrete_ty = generic_ty.subst(self.tcx(), substs);
122 self.anon_depth += 1;
123 if concrete_ty == ty {
125 "infinite recursion generic_ty: {:#?}, substs: {:#?}, \
126 concrete_ty: {:#?}, ty: {:#?}",
133 let folded_ty = self.fold_ty(concrete_ty);
134 self.anon_depth -= 1;
140 ty::Projection(ref data) if !data.has_escaping_regions() => {
142 // (*) This is kind of hacky -- we need to be able to
143 // handle normalization within binders because
144 // otherwise we wind up a need to normalize when doing
145 // trait matching (since you can have a trait
146 // obligation like `for<'a> T::B : Fn(&'a int)`), but
147 // we can't normalize with bound regions in scope. So
148 // far now we just ignore binders but only normalize
149 // if all bound regions are gone (and then we still
150 // have to renormalize whenever we instantiate a
151 // binder). It would be better to normalize in a
152 // binding-aware fashion.
154 let gcx = self.infcx.tcx.global_tcx();
156 let mut orig_values = SmallVec::new();
157 let c_data = self.infcx
158 .canonicalize_query(&self.param_env.and(*data), &mut orig_values);
159 debug!("QueryNormalizer: c_data = {:#?}", c_data);
160 debug!("QueryNormalizer: orig_values = {:#?}", orig_values);
161 match gcx.normalize_projection_ty(c_data) {
163 // We don't expect ambiguity.
164 if result.is_ambiguous() {
169 match self.infcx.instantiate_query_result_and_region_obligations(
179 debug!("QueryNormalizer: result = {:#?}", result);
180 debug!("QueryNormalizer: obligations = {:#?}", obligations);
181 self.obligations.extend(obligations);
182 return result.normalized_ty;
203 fn fold_const(&mut self, constant: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> {
204 if let ConstValue::Unevaluated(def_id, substs) = constant.val {
205 let tcx = self.infcx.tcx.global_tcx();
206 if let Some(param_env) = self.tcx().lift_to_global(&self.param_env) {
207 if substs.needs_infer() || substs.has_skol() {
208 let identity_substs = Substs::identity_for_item(tcx, def_id);
209 let instance = ty::Instance::resolve(tcx, param_env, def_id, identity_substs);
210 if let Some(instance) = instance {
215 match tcx.const_eval(param_env.and(cid)) {
217 let evaluated = evaluated.subst(self.tcx(), substs);
218 return self.fold_const(evaluated);
224 if let Some(substs) = self.tcx().lift_to_global(&substs) {
225 let instance = ty::Instance::resolve(tcx, param_env, def_id, substs);
226 if let Some(instance) = instance {
231 match tcx.const_eval(param_env.and(cid)) {
232 Ok(evaluated) => return self.fold_const(evaluated),
244 BraceStructTypeFoldableImpl! {
245 impl<'tcx> TypeFoldable<'tcx> for NormalizationResult<'tcx> {
250 BraceStructLiftImpl! {
251 impl<'a, 'tcx> Lift<'tcx> for NormalizationResult<'a> {
252 type Lifted = NormalizationResult<'tcx>;
257 impl_stable_hash_for!(struct NormalizationResult<'tcx> {