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::{InferCtxt, InferOk};
  16 use infer::at::At;
  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};
  27
  28 use super::NoSolution;
  29
  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.
  35     ///
  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).
  39     ///
  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>
  45     where
  46         T: TypeFoldable<'tcx>,
  47     {
  48         debug!(
  49             "normalize::<{}>(value={:?}, param_env={:?})",
  50             unsafe { ::std::intrinsics::type_name::<T>() },
  51             value,
  52             self.param_env,
  53         );
  54         let mut normalizer = QueryNormalizer {
  55             infcx: self.infcx,
  56             cause: self.cause,
  57             param_env: self.param_env,
  58             obligations: vec![],
  59             error: false,
  60             anon_depth: 0,
  61         };
  62         if !value.has_projections() {
  63             return Ok(Normalized {
  64                 value: value.clone(),
  65                 obligations: vec![],
  66             });
  67         }
  68
  69         let value1 = value.fold_with(&mut normalizer);
  70         if normalizer.error {
  71             Err(NoSolution)
  72         } else {
  73             Ok(Normalized {
  74                 value: value1,
  75                 obligations: normalizer.obligations,
  76             })
  77         }
  78     }
  79 }
  80
  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>,
  86 }
  87
  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>>,
  93     error: bool,
  94     anon_depth: usize,
  95 }
  96
  97 impl<'cx, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for QueryNormalizer<'cx, 'gcx, 'tcx> {
  98     fn tcx<'c>(&'c self) -> TyCtxt<'c, 'gcx, 'tcx> {
  99         self.infcx.tcx
 100     }
 101
 102     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
 103         let ty = ty.super_fold_with(self);
 104         match ty.sty {
 105             ty::TyAnon(def_id, substs) if !substs.has_escaping_regions() => {
 106                 // (*)
 107                 // Only normalize `impl Trait` after type-checking, usually in codegen.
 108                 match self.param_env.reveal {
 109                     Reveal::UserFacing => ty,
 110
 111                     Reveal::All => {
 112                         let recursion_limit = *self.tcx().sess.recursion_limit.get();
 113                         if self.anon_depth >= recursion_limit {
 114                             let obligation = Obligation::with_depth(
 115                                 self.cause.clone(),
 116                                 recursion_limit,
 117                                 self.param_env,
 118                                 ty,
 119                             );
 120                             self.infcx.report_overflow_error(&obligation, true);
 121                         }
 122
 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);
 129                         }
 130                         assert_ne!(concrete_ty, ty, "infinite recursion");
 131                         let folded_ty = self.fold_ty(concrete_ty);
 132                         self.anon_depth -= 1;
 133                         folded_ty
 134                     }
 135                 }
 136             }
 137
 138             ty::TyProjection(ref data) if !data.has_escaping_regions() => {
 139                 // (*)
 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.
 151
 152                 let gcx = self.infcx.tcx.global_tcx();
 153
 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) {
 159                     Ok(result) => {
 160                         // We don't expect ambiguity.
 161                         if result.is_ambiguous() {
 162                             self.error = true;
 163                             return ty;
 164                         }
 165
 166                         match self.infcx.instantiate_query_result(
 167                             self.cause,
 168                             self.param_env,
 169                             &orig_values,
 170                             &result,
 171                         ) {
 172                             Ok(InferOk {
 173                                 value: result,
 174                                 obligations,
 175                             }) => {
 176                                 debug!("QueryNormalizer: result = {:#?}", result);
 177                                 debug!("QueryNormalizer: obligations = {:#?}", obligations);
 178                                 self.obligations.extend(obligations);
 179                                 return result.normalized_ty;
 180                             }
 181
 182                             Err(_) => {
 183                                 self.error = true;
 184                                 return ty;
 185                             }
 186                         }
 187                     }
 188
 189                     Err(NoSolution) => {
 190                         self.error = true;
 191                         ty
 192                     }
 193                 }
 194             }
 195
 196             _ => ty,
 197         }
 198     }
 199
 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 {
 208                         let cid = GlobalId {
 209                             instance,
 210                             promoted: None,
 211                         };
 212                         match tcx.const_eval(param_env.and(cid)) {
 213                             Ok(evaluated) => {
 214                                 let evaluated = evaluated.subst(self.tcx(), substs);
 215                                 return self.fold_const(evaluated);
 216                             }
 217                             Err(_) => {}
 218                         }
 219                     }
 220                 } else {
 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 {
 224                             let cid = GlobalId {
 225                                 instance,
 226                                 promoted: None,
 227                             };
 228                             match tcx.const_eval(param_env.and(cid)) {
 229                                 Ok(evaluated) => return self.fold_const(evaluated),
 230                                 Err(_) => {}
 231                             }
 232                         }
 233                     }
 234                 }
 235             }
 236         }
 237         constant
 238     }
 239 }
 240
 241 BraceStructTypeFoldableImpl! {
 242     impl<'tcx> TypeFoldable<'tcx> for NormalizationResult<'tcx> {
 243         normalized_ty
 244     }
 245 }
 246
 247 BraceStructLiftImpl! {
 248     impl<'a, 'tcx> Lift<'tcx> for NormalizationResult<'a> {
 249         type Lifted = NormalizationResult<'tcx>;
 250         normalized_ty
 251     }
 252 }
 253
 254 impl<'gcx: 'tcx, 'tcx> Canonicalize<'gcx, 'tcx> for ty::ParamEnvAnd<'tcx, ty::ProjectionTy<'tcx>> {
 255     type Canonicalized = CanonicalProjectionGoal<'gcx>;
 256
 257     fn intern(
 258         _gcx: TyCtxt<'_, 'gcx, 'gcx>,
 259         value: Canonical<'gcx, Self::Lifted>,
 260     ) -> Self::Canonicalized {
 261         value
 262     }
 263 }
 264
 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>>>>;
 268
 269     fn intern(
 270         _gcx: TyCtxt<'_, 'gcx, 'gcx>,
 271         value: Canonical<'gcx, Self::Lifted>,
 272     ) -> Self::Canonicalized {
 273         Lrc::new(value)
 274     }
 275 }
 276
 277 impl_stable_hash_for!(struct NormalizationResult<'tcx> {
 278     normalized_ty
 279 });