src/librustc_traits/type_op.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 use rustc::infer::at::ToTrace;
  12 use rustc::infer::canonical::{Canonical, QueryResponse};
  13 use rustc::infer::InferCtxt;
  14 use rustc::hir::def_id::DefId;
  15 use rustc::traits::query::type_op::ascribe_user_type::AscribeUserType;
  16 use rustc::traits::query::type_op::eq::Eq;
  17 use rustc::traits::query::type_op::normalize::Normalize;
  18 use rustc::traits::query::type_op::prove_predicate::ProvePredicate;
  19 use rustc::traits::query::type_op::subtype::Subtype;
  20 use rustc::traits::query::{Fallible, NoSolution};
  21 use rustc::traits::{
  22     FulfillmentContext, Normalized, Obligation, ObligationCause, TraitEngine, TraitEngineExt,
  23 };
  24 use rustc::ty::query::Providers;
  25 use rustc::ty::subst::{Kind, Subst, UserSelfTy, UserSubsts};
  26 use rustc::ty::{
  27     FnSig, Lift, ParamEnv, ParamEnvAnd, PolyFnSig, Predicate, Ty, TyCtxt, TypeFoldable, Variance,
  28 };
  29 use rustc_data_structures::sync::Lrc;
  30 use std::fmt;
  31 use syntax::ast;
  32 use syntax_pos::DUMMY_SP;
  33
  34 crate fn provide(p: &mut Providers) {
  35     *p = Providers {
  36         type_op_ascribe_user_type,
  37         type_op_eq,
  38         type_op_prove_predicate,
  39         type_op_subtype,
  40         type_op_normalize_ty,
  41         type_op_normalize_predicate,
  42         type_op_normalize_fn_sig,
  43         type_op_normalize_poly_fn_sig,
  44         ..*p
  45     };
  46 }
  47
  48 fn type_op_ascribe_user_type<'tcx>(
  49     tcx: TyCtxt<'_, 'tcx, 'tcx>,
  50     canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, AscribeUserType<'tcx>>>,
  51 ) -> Result<Lrc<Canonical<'tcx, QueryResponse<'tcx, ()>>>, NoSolution> {
  52     tcx.infer_ctxt()
  53         .enter_canonical_trait_query(&canonicalized, |infcx, fulfill_cx, key| {
  54             let (
  55                 param_env,
  56                 AscribeUserType {
  57                     mir_ty,
  58                     variance,
  59                     def_id,
  60                     user_substs,
  61                 },
  62             ) = key.into_parts();
  63
  64             debug!(
  65                 "type_op_ascribe_user_type(\
  66                  mir_ty={:?}, variance={:?}, def_id={:?}, user_substs={:?}\
  67                  )",
  68                 mir_ty, variance, def_id, user_substs,
  69             );
  70
  71             let mut cx = AscribeUserTypeCx {
  72                 infcx,
  73                 param_env,
  74                 fulfill_cx,
  75             };
  76             cx.relate_mir_and_user_ty(mir_ty, variance, def_id, user_substs)?;
  77
  78             Ok(())
  79         })
  80 }
  81
  82 struct AscribeUserTypeCx<'me, 'gcx: 'tcx, 'tcx: 'me> {
  83     infcx: &'me InferCtxt<'me, 'gcx, 'tcx>,
  84     param_env: ParamEnv<'tcx>,
  85     fulfill_cx: &'me mut FulfillmentContext<'tcx>,
  86 }
  87
  88 impl AscribeUserTypeCx<'me, 'gcx, 'tcx> {
  89     fn normalize<T>(&mut self, value: T) -> T
  90     where
  91         T: TypeFoldable<'tcx>,
  92     {
  93         self.infcx
  94             .partially_normalize_associated_types_in(
  95                 DUMMY_SP,
  96                 ast::CRATE_NODE_ID,
  97                 self.param_env,
  98                 &value,
  99             )
 100             .into_value_registering_obligations(self.infcx, self.fulfill_cx)
 101     }
 102
 103     fn relate<T>(&mut self, a: T, variance: Variance, b: T) -> Result<(), NoSolution>
 104     where
 105         T: ToTrace<'tcx>,
 106     {
 107         Ok(self.infcx
 108             .at(&ObligationCause::dummy(), self.param_env)
 109            .relate(a, variance, b)?
 110            .into_value_registering_obligations(self.infcx, self.fulfill_cx))
 111     }
 112
 113     fn prove_predicate(&mut self, predicate: Predicate<'tcx>) {
 114         self.fulfill_cx.register_predicate_obligation(
 115             self.infcx,
 116             Obligation::new(ObligationCause::dummy(), self.param_env, predicate),
 117         );
 118     }
 119
 120     fn tcx(&self) -> TyCtxt<'me, 'gcx, 'tcx> {
 121         self.infcx.tcx
 122     }
 123
 124     fn subst<T>(&self, value: T, substs: &[Kind<'tcx>]) -> T
 125     where
 126         T: TypeFoldable<'tcx>,
 127     {
 128         value.subst(self.tcx(), substs)
 129     }
 130
 131     fn relate_mir_and_user_ty(
 132         &mut self,
 133         mir_ty: Ty<'tcx>,
 134         variance: Variance,
 135         def_id: DefId,
 136         user_substs: UserSubsts<'tcx>,
 137     ) -> Result<(), NoSolution> {
 138         let UserSubsts {
 139             substs,
 140             user_self_ty,
 141         } = user_substs;
 142
 143         let ty = self.tcx().type_of(def_id);
 144         let ty = self.subst(ty, substs);
 145         debug!("relate_type_and_user_type: ty of def-id is {:?}", ty);
 146         let ty = self.normalize(ty);
 147
 148         self.relate(mir_ty, variance, ty)?;
 149
 150         if let Some(UserSelfTy {
 151             impl_def_id,
 152             self_ty,
 153         }) = user_self_ty
 154         {
 155             let impl_self_ty = self.tcx().type_of(impl_def_id);
 156             let impl_self_ty = self.subst(impl_self_ty, &substs);
 157             let impl_self_ty = self.normalize(impl_self_ty);
 158
 159             self.relate(self_ty, Variance::Invariant, impl_self_ty)?;
 160
 161             self.prove_predicate(Predicate::WellFormed(impl_self_ty));
 162         }
 163
 164         // Prove the predicates coming along with `def_id`.
 165         //
 166         // Also, normalize the `instantiated_predicates`
 167         // because otherwise we wind up with duplicate "type
 168         // outlives" error messages.
 169         let instantiated_predicates = self.tcx()
 170             .predicates_of(def_id)
 171             .instantiate(self.tcx(), substs);
 172         for instantiated_predicate in instantiated_predicates.predicates {
 173             let instantiated_predicate = self.normalize(instantiated_predicate);
 174             self.prove_predicate(instantiated_predicate);
 175         }
 176
 177         // In addition to proving the predicates, we have to
 178         // prove that `ty` is well-formed -- this is because
 179         // the WF of `ty` is predicated on the substs being
 180         // well-formed, and we haven't proven *that*. We don't
 181         // want to prove the WF of types from  `substs` directly because they
 182         // haven't been normalized.
 183         //
 184         // FIXME(nmatsakis): Well, perhaps we should normalize
 185         // them?  This would only be relevant if some input
 186         // type were ill-formed but did not appear in `ty`,
 187         // which...could happen with normalization...
 188         self.prove_predicate(Predicate::WellFormed(ty));
 189
 190         Ok(())
 191     }
 192 }
 193
 194 fn type_op_eq<'tcx>(
 195     tcx: TyCtxt<'_, 'tcx, 'tcx>,
 196     canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, Eq<'tcx>>>,
 197 ) -> Result<Lrc<Canonical<'tcx, QueryResponse<'tcx, ()>>>, NoSolution> {
 198     tcx.infer_ctxt()
 199         .enter_canonical_trait_query(&canonicalized, |infcx, fulfill_cx, key| {
 200             let (param_env, Eq { a, b }) = key.into_parts();
 201             Ok(infcx
 202                 .at(&ObligationCause::dummy(), param_env)
 203                 .eq(a, b)?
 204                 .into_value_registering_obligations(infcx, fulfill_cx))
 205         })
 206 }
 207
 208 fn type_op_normalize<T>(
 209     infcx: &InferCtxt<'_, 'gcx, 'tcx>,
 210     fulfill_cx: &mut FulfillmentContext<'tcx>,
 211     key: ParamEnvAnd<'tcx, Normalize<T>>,
 212 ) -> Fallible<T>
 213 where
 214     T: fmt::Debug + TypeFoldable<'tcx> + Lift<'gcx>,
 215 {
 216     let (param_env, Normalize { value }) = key.into_parts();
 217     let Normalized { value, obligations } = infcx
 218         .at(&ObligationCause::dummy(), param_env)
 219         .normalize(&value)?;
 220     fulfill_cx.register_predicate_obligations(infcx, obligations);
 221     Ok(value)
 222 }
 223
 224 fn type_op_normalize_ty(
 225     tcx: TyCtxt<'_, 'tcx, 'tcx>,
 226     canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, Normalize<Ty<'tcx>>>>,
 227 ) -> Result<Lrc<Canonical<'tcx, QueryResponse<'tcx, Ty<'tcx>>>>, NoSolution> {
 228     tcx.infer_ctxt()
 229         .enter_canonical_trait_query(&canonicalized, type_op_normalize)
 230 }
 231
 232 fn type_op_normalize_predicate(
 233     tcx: TyCtxt<'_, 'tcx, 'tcx>,
 234     canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, Normalize<Predicate<'tcx>>>>,
 235 ) -> Result<Lrc<Canonical<'tcx, QueryResponse<'tcx, Predicate<'tcx>>>>, NoSolution> {
 236     tcx.infer_ctxt()
 237         .enter_canonical_trait_query(&canonicalized, type_op_normalize)
 238 }
 239
 240 fn type_op_normalize_fn_sig(
 241     tcx: TyCtxt<'_, 'tcx, 'tcx>,
 242     canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, Normalize<FnSig<'tcx>>>>,
 243 ) -> Result<Lrc<Canonical<'tcx, QueryResponse<'tcx, FnSig<'tcx>>>>, NoSolution> {
 244     tcx.infer_ctxt()
 245         .enter_canonical_trait_query(&canonicalized, type_op_normalize)
 246 }
 247
 248 fn type_op_normalize_poly_fn_sig(
 249     tcx: TyCtxt<'_, 'tcx, 'tcx>,
 250     canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, Normalize<PolyFnSig<'tcx>>>>,
 251 ) -> Result<Lrc<Canonical<'tcx, QueryResponse<'tcx, PolyFnSig<'tcx>>>>, NoSolution> {
 252     tcx.infer_ctxt()
 253         .enter_canonical_trait_query(&canonicalized, type_op_normalize)
 254 }
 255
 256 fn type_op_subtype<'tcx>(
 257     tcx: TyCtxt<'_, 'tcx, 'tcx>,
 258     canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, Subtype<'tcx>>>,
 259 ) -> Result<Lrc<Canonical<'tcx, QueryResponse<'tcx, ()>>>, NoSolution> {
 260     tcx.infer_ctxt()
 261         .enter_canonical_trait_query(&canonicalized, |infcx, fulfill_cx, key| {
 262             let (param_env, Subtype { sub, sup }) = key.into_parts();
 263             Ok(infcx
 264                 .at(&ObligationCause::dummy(), param_env)
 265                 .sup(sup, sub)?
 266                 .into_value_registering_obligations(infcx, fulfill_cx))
 267         })
 268 }
 269
 270 fn type_op_prove_predicate<'tcx>(
 271     tcx: TyCtxt<'_, 'tcx, 'tcx>,
 272     canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, ProvePredicate<'tcx>>>,
 273 ) -> Result<Lrc<Canonical<'tcx, QueryResponse<'tcx, ()>>>, NoSolution> {
 274     tcx.infer_ctxt()
 275         .enter_canonical_trait_query(&canonicalized, |infcx, fulfill_cx, key| {
 276             let (param_env, ProvePredicate { predicate }) = key.into_parts();
 277             fulfill_cx.register_predicate_obligation(
 278                 infcx,
 279                 Obligation::new(ObligationCause::dummy(), param_env, predicate),
 280             );
 281             Ok(())
 282         })
 283 }