src/librustc/traits/query/normalize.rs

   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.
   4 //
   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.
  10
  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.
  14
  15 use infer::at::At;
  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};
  24
  25 use super::NoSolution;
  26
  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.
  32     ///
  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).
  36     ///
  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>
  42     where
  43         T: TypeFoldable<'tcx>,
  44     {
  45         debug!(
  46             "normalize::<{}>(value={:?}, param_env={:?})",
  47             unsafe { ::std::intrinsics::type_name::<T>() },
  48             value,
  49             self.param_env,
  50         );
  51         let mut normalizer = QueryNormalizer {
  52             infcx: self.infcx,
  53             cause: self.cause,
  54             param_env: self.param_env,
  55             obligations: vec![],
  56             error: false,
  57             anon_depth: 0,
  58         };
  59         if !value.has_projections() {
  60             return Ok(Normalized {
  61                 value: value.clone(),
  62                 obligations: vec![],
  63             });
  64         }
  65
  66         let value1 = value.fold_with(&mut normalizer);
  67         if normalizer.error {
  68             Err(NoSolution)
  69         } else {
  70             Ok(Normalized {
  71                 value: value1,
  72                 obligations: normalizer.obligations,
  73             })
  74         }
  75     }
  76 }
  77
  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>,
  83 }
  84
  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>>,
  90     error: bool,
  91     anon_depth: usize,
  92 }
  93
  94 impl<'cx, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for QueryNormalizer<'cx, 'gcx, 'tcx> {
  95     fn tcx<'c>(&'c self) -> TyCtxt<'c, 'gcx, 'tcx> {
  96         self.infcx.tcx
  97     }
  98
  99     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
 100         let ty = ty.super_fold_with(self);
 101         match ty.sty {
 102             ty::Opaque(def_id, substs) if !substs.has_escaping_regions() => {
 103                 // (*)
 104                 // Only normalize `impl Trait` after type-checking, usually in codegen.
 105                 match self.param_env.reveal {
 106                     Reveal::UserFacing => ty,
 107
 108                     Reveal::All => {
 109                         let recursion_limit = *self.tcx().sess.recursion_limit.get();
 110                         if self.anon_depth >= recursion_limit {
 111                             let obligation = Obligation::with_depth(
 112                                 self.cause.clone(),
 113                                 recursion_limit,
 114                                 self.param_env,
 115                                 ty,
 116                             );
 117                             self.infcx.report_overflow_error(&obligation, true);
 118                         }
 119
 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 {
 124                             bug!(
 125                                 "infinite recursion generic_ty: {:#?}, substs: {:#?}, \
 126                                  concrete_ty: {:#?}, ty: {:#?}",
 127                                 generic_ty,
 128                                 substs,
 129                                 concrete_ty,
 130                                 ty
 131                             );
 132                         }
 133                         let folded_ty = self.fold_ty(concrete_ty);
 134                         self.anon_depth -= 1;
 135                         folded_ty
 136                     }
 137                 }
 138             }
 139
 140             ty::Projection(ref data) if !data.has_escaping_regions() => {
 141                 // (*)
 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.
 153
 154                 let gcx = self.infcx.tcx.global_tcx();
 155
 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) {
 162                     Ok(result) => {
 163                         // We don't expect ambiguity.
 164                         if result.is_ambiguous() {
 165                             self.error = true;
 166                             return ty;
 167                         }
 168
 169                         match self.infcx.instantiate_query_result_and_region_obligations(
 170                             self.cause,
 171                             self.param_env,
 172                             &orig_values,
 173                             &result,
 174                         ) {
 175                             Ok(InferOk {
 176                                 value: result,
 177                                 obligations,
 178                             }) => {
 179                                 debug!("QueryNormalizer: result = {:#?}", result);
 180                                 debug!("QueryNormalizer: obligations = {:#?}", obligations);
 181                                 self.obligations.extend(obligations);
 182                                 return result.normalized_ty;
 183                             }
 184
 185                             Err(_) => {
 186                                 self.error = true;
 187                                 return ty;
 188                             }
 189                         }
 190                     }
 191
 192                     Err(NoSolution) => {
 193                         self.error = true;
 194                         ty
 195                     }
 196                 }
 197             }
 198
 199             _ => ty,
 200         }
 201     }
 202
 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 {
 211                         let cid = GlobalId {
 212                             instance,
 213                             promoted: None,
 214                         };
 215                         match tcx.const_eval(param_env.and(cid)) {
 216                             Ok(evaluated) => {
 217                                 let evaluated = evaluated.subst(self.tcx(), substs);
 218                                 return self.fold_const(evaluated);
 219                             }
 220                             Err(_) => {}
 221                         }
 222                     }
 223                 } else {
 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 {
 227                             let cid = GlobalId {
 228                                 instance,
 229                                 promoted: None,
 230                             };
 231                             match tcx.const_eval(param_env.and(cid)) {
 232                                 Ok(evaluated) => return self.fold_const(evaluated),
 233                                 Err(_) => {}
 234                             }
 235                         }
 236                     }
 237                 }
 238             }
 239         }
 240         constant
 241     }
 242 }
 243
 244 BraceStructTypeFoldableImpl! {
 245     impl<'tcx> TypeFoldable<'tcx> for NormalizationResult<'tcx> {
 246         normalized_ty
 247     }
 248 }
 249
 250 BraceStructLiftImpl! {
 251     impl<'a, 'tcx> Lift<'tcx> for NormalizationResult<'a> {
 252         type Lifted = NormalizationResult<'tcx>;
 253         normalized_ty
 254     }
 255 }
 256
 257 impl_stable_hash_for!(struct NormalizationResult<'tcx> {
 258     normalized_ty
 259 });