src/librustc/middle/traits/coherence.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 /*! See `doc.rs` for high-level documentation */
  12
  13 use super::SelectionContext;
  14 use super::Obligation;
  15 use super::util;
  16
  17 use middle::subst;
  18 use middle::subst::Subst;
  19 use middle::ty::{mod, Ty};
  20 use middle::typeck::infer::{mod, InferCtxt};
  21 use syntax::ast;
  22 use syntax::codemap::DUMMY_SP;
  23 use util::ppaux::Repr;
  24
  25 pub fn impl_can_satisfy(infcx: &InferCtxt,
  26                         impl1_def_id: ast::DefId,
  27                         impl2_def_id: ast::DefId)
  28                         -> bool
  29 {
  30     debug!("impl_can_satisfy(\
  31            impl1_def_id={}, \
  32            impl2_def_id={})",
  33            impl1_def_id.repr(infcx.tcx),
  34            impl2_def_id.repr(infcx.tcx));
  35
  36     // `impl1` provides an implementation of `Foo<X,Y> for Z`.
  37     let impl1_substs =
  38         util::fresh_substs_for_impl(infcx, DUMMY_SP, impl1_def_id);
  39     let impl1_trait_ref =
  40         ty::impl_trait_ref(infcx.tcx, impl1_def_id).unwrap()
  41                                                    .subst(infcx.tcx, &impl1_substs);
  42     let impl1_trait_ref =
  43         infcx.replace_late_bound_regions_with_fresh_var(DUMMY_SP,
  44                                                         infer::FnCall,
  45                                                         &impl1_trait_ref).0;
  46
  47     // Determine whether `impl2` can provide an implementation for those
  48     // same types.
  49     let param_env = ty::empty_parameter_environment();
  50     let mut selcx = SelectionContext::intercrate(infcx, &param_env, infcx.tcx);
  51     let obligation = Obligation::misc(DUMMY_SP, impl1_trait_ref);
  52     debug!("impl_can_satisfy(obligation={})", obligation.repr(infcx.tcx));
  53     selcx.evaluate_impl(impl2_def_id, &obligation)
  54 }
  55
  56 pub fn impl_is_local(tcx: &ty::ctxt,
  57                      impl_def_id: ast::DefId)
  58                      -> bool
  59 {
  60     debug!("impl_is_local({})", impl_def_id.repr(tcx));
  61
  62     // We only except this routine to be invoked on implementations
  63     // of a trait, not inherent implementations.
  64     let trait_ref = ty::impl_trait_ref(tcx, impl_def_id).unwrap();
  65     debug!("trait_ref={}", trait_ref.repr(tcx));
  66
  67     // If the trait is local to the crate, ok.
  68     if trait_ref.def_id.krate == ast::LOCAL_CRATE {
  69         debug!("trait {} is local to current crate",
  70                trait_ref.def_id.repr(tcx));
  71         return true;
  72     }
  73
  74     // Otherwise, at least one of the input types must be local to the
  75     // crate.
  76     trait_ref.input_types().iter().any(|&t| ty_is_local(tcx, t))
  77 }
  78
  79 pub fn ty_is_local<'tcx>(tcx: &ty::ctxt<'tcx>, ty: Ty<'tcx>) -> bool {
  80     debug!("ty_is_local({})", ty.repr(tcx));
  81
  82     match ty.sty {
  83         ty::ty_bool |
  84         ty::ty_char |
  85         ty::ty_int(..) |
  86         ty::ty_uint(..) |
  87         ty::ty_float(..) |
  88         ty::ty_str(..) => {
  89             false
  90         }
  91
  92         ty::ty_unboxed_closure(..) => {
  93             // This routine is invoked on types specified by users as
  94             // part of an impl and hence an unboxed closure type
  95             // cannot appear.
  96             tcx.sess.bug("ty_is_local applied to unboxed closure type")
  97         }
  98
  99         ty::ty_bare_fn(..) |
 100         ty::ty_closure(..) => {
 101             false
 102         }
 103
 104         ty::ty_uniq(t) => {
 105             let krate = tcx.lang_items.owned_box().map(|d| d.krate);
 106             krate == Some(ast::LOCAL_CRATE) || ty_is_local(tcx, t)
 107         }
 108
 109         ty::ty_vec(t, _) |
 110         ty::ty_ptr(ty::mt { ty: t, .. }) |
 111         ty::ty_rptr(_, ty::mt { ty: t, .. }) => {
 112             ty_is_local(tcx, t)
 113         }
 114
 115         ty::ty_tup(ref ts) => {
 116             ts.iter().any(|&t| ty_is_local(tcx, t))
 117         }
 118
 119         ty::ty_enum(def_id, ref substs) |
 120         ty::ty_struct(def_id, ref substs) => {
 121             def_id.krate == ast::LOCAL_CRATE || {
 122                 let variances = ty::item_variances(tcx, def_id);
 123                 subst::ParamSpace::all().iter().any(|&space| {
 124                     substs.types.get_slice(space).iter().enumerate().any(
 125                         |(i, &t)| {
 126                             match *variances.types.get(space, i) {
 127                                 ty::Bivariant => {
 128                                     // If Foo<T> is bivariant with respect to
 129                                     // T, then it doesn't matter whether T is
 130                                     // local or not, because `Foo<U>` for any
 131                                     // U will be a subtype of T.
 132                                     false
 133                                 }
 134                                 ty::Contravariant |
 135                                 ty::Covariant |
 136                                 ty::Invariant => {
 137                                     ty_is_local(tcx, t)
 138                                 }
 139                             }
 140                         })
 141                 })
 142             }
 143         }
 144
 145         ty::ty_trait(ref tt) => {
 146             tt.principal.def_id.krate == ast::LOCAL_CRATE
 147         }
 148
 149         // Type parameters may be bound to types that are not local to
 150         // the crate.
 151         ty::ty_param(..) => {
 152             false
 153         }
 154
 155         ty::ty_infer(..) |
 156         ty::ty_open(..) |
 157         ty::ty_err => {
 158             tcx.sess.bug(
 159                 format!("ty_is_local invoked on unexpected type: {}",
 160                         ty.repr(tcx)).as_slice())
 161         }
 162     }
 163 }