src/librustc/traits/query/normalize.rs

   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.
   4
   5 use crate::infer::at::At;
   6 use crate::infer::canonical::OriginalQueryValues;
   7 use crate::infer::{InferCtxt, InferOk};
   8 use crate::mir::interpret::{GlobalId, ConstValue};
   9 use crate::traits::project::Normalized;
  10 use crate::traits::{Obligation, ObligationCause, PredicateObligation, Reveal};
  11 use crate::ty::fold::{TypeFoldable, TypeFolder};
  12 use crate::ty::subst::{Subst, InternalSubsts};
  13 use crate::ty::{self, Ty, TyCtxt};
  14
  15 use super::NoSolution;
  16
  17 impl<'cx, 'tcx> At<'cx, 'tcx> {
  18     /// Normalize `value` in the context of the inference context,
  19     /// yielding a resulting type, or an error if `value` cannot be
  20     /// normalized. If you don't care about regions, you should prefer
  21     /// `normalize_erasing_regions`, which is more efficient.
  22     ///
  23     /// If the normalization succeeds and is unambiguous, returns back
  24     /// the normalized value along with various outlives relations (in
  25     /// the form of obligations that must be discharged).
  26     ///
  27     /// N.B., this will *eventually* be the main means of
  28     /// normalizing, but for now should be used only when we actually
  29     /// know that normalization will succeed, since error reporting
  30     /// and other details are still "under development".
  31     pub fn normalize<T>(&self, value: &T) -> Result<Normalized<'tcx, T>, NoSolution>
  32     where
  33         T: TypeFoldable<'tcx>,
  34     {
  35         debug!(
  36             "normalize::<{}>(value={:?}, param_env={:?})",
  37             unsafe { ::std::intrinsics::type_name::<T>() },
  38             value,
  39             self.param_env,
  40         );
  41         if !value.has_projections() {
  42             return Ok(Normalized {
  43                 value: value.clone(),
  44                 obligations: vec![],
  45             });
  46         }
  47
  48         let mut normalizer = QueryNormalizer {
  49             infcx: self.infcx,
  50             cause: self.cause,
  51             param_env: self.param_env,
  52             obligations: vec![],
  53             error: false,
  54             anon_depth: 0,
  55         };
  56
  57         let value1 = value.fold_with(&mut normalizer);
  58         if normalizer.error {
  59             Err(NoSolution)
  60         } else {
  61             Ok(Normalized {
  62                 value: value1,
  63                 obligations: normalizer.obligations,
  64             })
  65         }
  66     }
  67 }
  68
  69 /// Result from the `normalize_projection_ty` query.
  70 #[derive(Clone, Debug)]
  71 pub struct NormalizationResult<'tcx> {
  72     /// Result of normalization.
  73     pub normalized_ty: Ty<'tcx>,
  74 }
  75
  76 struct QueryNormalizer<'cx, 'tcx: 'cx> {
  77     infcx: &'cx InferCtxt<'cx, 'tcx>,
  78     cause: &'cx ObligationCause<'tcx>,
  79     param_env: ty::ParamEnv<'tcx>,
  80     obligations: Vec<PredicateObligation<'tcx>>,
  81     error: bool,
  82     anon_depth: usize,
  83 }
  84
  85 impl<'cx, 'tcx> TypeFolder<'tcx> for QueryNormalizer<'cx, 'tcx> {
  86     fn tcx<'c>(&'c self) -> TyCtxt<'tcx> {
  87         self.infcx.tcx
  88     }
  89
  90     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
  91         let ty = ty.super_fold_with(self);
  92         match ty.sty {
  93             ty::Opaque(def_id, substs) if !substs.has_escaping_bound_vars() => {
  94                 // (*)
  95                 // Only normalize `impl Trait` after type-checking, usually in codegen.
  96                 match self.param_env.reveal {
  97                     Reveal::UserFacing => ty,
  98
  99                     Reveal::All => {
 100                         let recursion_limit = *self.tcx().sess.recursion_limit.get();
 101                         if self.anon_depth >= recursion_limit {
 102                             let obligation = Obligation::with_depth(
 103                                 self.cause.clone(),
 104                                 recursion_limit,
 105                                 self.param_env,
 106                                 ty,
 107                             );
 108                             self.infcx.report_overflow_error(&obligation, true);
 109                         }
 110
 111                         let generic_ty = self.tcx().type_of(def_id);
 112                         let concrete_ty = generic_ty.subst(self.tcx(), substs);
 113                         self.anon_depth += 1;
 114                         if concrete_ty == ty {
 115                             bug!(
 116                                 "infinite recursion generic_ty: {:#?}, substs: {:#?}, \
 117                                  concrete_ty: {:#?}, ty: {:#?}",
 118                                 generic_ty,
 119                                 substs,
 120                                 concrete_ty,
 121                                 ty
 122                             );
 123                         }
 124                         let folded_ty = self.fold_ty(concrete_ty);
 125                         self.anon_depth -= 1;
 126                         folded_ty
 127                     }
 128                 }
 129             }
 130
 131             ty::Projection(ref data) if !data.has_escaping_bound_vars() => {
 132                 // (*)
 133                 // (*) This is kind of hacky -- we need to be able to
 134                 // handle normalization within binders because
 135                 // otherwise we wind up a need to normalize when doing
 136                 // trait matching (since you can have a trait
 137                 // obligation like `for<'a> T::B : Fn(&'a int)`), but
 138                 // we can't normalize with bound regions in scope. So
 139                 // far now we just ignore binders but only normalize
 140                 // if all bound regions are gone (and then we still
 141                 // have to renormalize whenever we instantiate a
 142                 // binder). It would be better to normalize in a
 143                 // binding-aware fashion.
 144
 145                 let gcx = self.infcx.tcx.global_tcx();
 146
 147                 let mut orig_values = OriginalQueryValues::default();
 148                 // HACK(matthewjasper) `'static` is special-cased in selection,
 149                 // so we cannot canonicalize it.
 150                 let c_data = self.infcx.canonicalize_hr_query_hack(
 151                     &self.param_env.and(*data), &mut orig_values);
 152                 debug!("QueryNormalizer: c_data = {:#?}", c_data);
 153                 debug!("QueryNormalizer: orig_values = {:#?}", orig_values);
 154                 match gcx.normalize_projection_ty(c_data) {
 155                     Ok(result) => {
 156                         // We don't expect ambiguity.
 157                         if result.is_ambiguous() {
 158                             self.error = true;
 159                             return ty;
 160                         }
 161
 162                         match self.infcx.instantiate_query_response_and_region_obligations(
 163                             self.cause,
 164                             self.param_env,
 165                             &orig_values,
 166                             &result)
 167                         {
 168                             Ok(InferOk { value: result, obligations }) => {
 169                                 debug!("QueryNormalizer: result = {:#?}", result);
 170                                 debug!("QueryNormalizer: obligations = {:#?}", obligations);
 171                                 self.obligations.extend(obligations);
 172                                 return result.normalized_ty;
 173                             }
 174
 175                             Err(_) => {
 176                                 self.error = true;
 177                                 return ty;
 178                             }
 179                         }
 180                     }
 181
 182                     Err(NoSolution) => {
 183                         self.error = true;
 184                         ty
 185                     }
 186                 }
 187             }
 188
 189             _ => ty,
 190         }
 191     }
 192
 193     fn fold_const(&mut self, constant: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> {
 194         if let ConstValue::Unevaluated(def_id, substs) = constant.val {
 195             let tcx = self.infcx.tcx.global_tcx();
 196             if let Some(param_env) = self.tcx().lift_to_global(&self.param_env) {
 197                 if substs.needs_infer() || substs.has_placeholders() {
 198                     let identity_substs = InternalSubsts::identity_for_item(tcx, def_id);
 199                     let instance = ty::Instance::resolve(tcx, param_env, def_id, identity_substs);
 200                     if let Some(instance) = instance {
 201                         let cid = GlobalId {
 202                             instance,
 203                             promoted: None,
 204                         };
 205                         if let Ok(evaluated) = tcx.const_eval(param_env.and(cid)) {
 206                             let evaluated = evaluated.subst(tcx, substs);
 207                             return evaluated;
 208                         }
 209                     }
 210                 } else {
 211                     if let Some(substs) = self.tcx().lift_to_global(&substs) {
 212                         let instance = ty::Instance::resolve(tcx, param_env, def_id, substs);
 213                         if let Some(instance) = instance {
 214                             let cid = GlobalId {
 215                                 instance,
 216                                 promoted: None,
 217                             };
 218                             if let Ok(evaluated) = tcx.const_eval(param_env.and(cid)) {
 219                                 return evaluated;
 220                             }
 221                         }
 222                     }
 223                 }
 224             }
 225         }
 226         constant
 227     }
 228 }
 229
 230 BraceStructTypeFoldableImpl! {
 231     impl<'tcx> TypeFoldable<'tcx> for NormalizationResult<'tcx> {
 232         normalized_ty
 233     }
 234 }
 235
 236 BraceStructLiftImpl! {
 237     impl<'a, 'tcx> Lift<'tcx> for NormalizationResult<'a> {
 238         type Lifted = NormalizationResult<'tcx>;
 239         normalized_ty
 240     }
 241 }
 242
 243 impl_stable_hash_for!(struct NormalizationResult<'tcx> {
 244     normalized_ty
 245 });