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 `README.md` for high-level documentation
  12
  13 use super::{SelectionContext};
  14 use super::{Obligation, ObligationCause};
  15
  16 use middle::cstore::LOCAL_CRATE;
  17 use middle::def_id::DefId;
  18 use middle::subst::TypeSpace;
  19 use middle::ty::{self, Ty, TyCtxt};
  20 use middle::infer::{self, InferCtxt, TypeOrigin};
  21 use syntax::codemap::DUMMY_SP;
  22
  23 #[derive(Copy, Clone)]
  24 struct InferIsLocal(bool);
  25
  26 /// If there are types that satisfy both impls, returns an `ImplTy`
  27 /// with those types substituted (by updating the given `infcx`)
  28 pub fn overlapping_impls<'cx, 'tcx>(infcx: &InferCtxt<'cx, 'tcx>,
  29                                     impl1_def_id: DefId,
  30                                     impl2_def_id: DefId)
  31                                     -> Option<ty::ImplHeader<'tcx>>
  32 {
  33     debug!("impl_can_satisfy(\
  34            impl1_def_id={:?}, \
  35            impl2_def_id={:?})",
  36            impl1_def_id,
  37            impl2_def_id);
  38
  39     let selcx = &mut SelectionContext::intercrate(infcx);
  40     overlap(selcx, impl1_def_id, impl2_def_id)
  41 }
  42
  43 /// Can both impl `a` and impl `b` be satisfied by a common type (including
  44 /// `where` clauses)? If so, returns an `ImplHeader` that unifies the two impls.
  45 fn overlap<'cx, 'tcx>(selcx: &mut SelectionContext<'cx, 'tcx>,
  46                       a_def_id: DefId,
  47                       b_def_id: DefId)
  48                       -> Option<ty::ImplHeader<'tcx>>
  49 {
  50     debug!("overlap(a_def_id={:?}, b_def_id={:?})",
  51            a_def_id,
  52            b_def_id);
  53
  54     let a_impl_header = ty::ImplHeader::with_fresh_ty_vars(selcx, a_def_id);
  55     let b_impl_header = ty::ImplHeader::with_fresh_ty_vars(selcx, b_def_id);
  56
  57     debug!("overlap: a_impl_header={:?}", a_impl_header);
  58     debug!("overlap: b_impl_header={:?}", b_impl_header);
  59
  60     // Do `a` and `b` unify? If not, no overlap.
  61     if let Err(_) = infer::mk_eq_impl_headers(selcx.infcx(),
  62                                               true,
  63                                               TypeOrigin::Misc(DUMMY_SP),
  64                                               &a_impl_header,
  65                                               &b_impl_header) {
  66         return None;
  67     }
  68
  69     debug!("overlap: unification check succeeded");
  70
  71     // Are any of the obligations unsatisfiable? If so, no overlap.
  72     let infcx = selcx.infcx();
  73     let opt_failing_obligation =
  74         a_impl_header.predicates
  75                      .iter()
  76                      .chain(&b_impl_header.predicates)
  77                      .map(|p| infcx.resolve_type_vars_if_possible(p))
  78                      .map(|p| Obligation { cause: ObligationCause::dummy(),
  79                                            recursion_depth: 0,
  80                                            predicate: p })
  81                      .find(|o| !selcx.evaluate_obligation(o));
  82
  83     if let Some(failing_obligation) = opt_failing_obligation {
  84         debug!("overlap: obligation unsatisfiable {:?}", failing_obligation);
  85         return None
  86     }
  87
  88     Some(selcx.infcx().resolve_type_vars_if_possible(&a_impl_header))
  89 }
  90
  91 pub fn trait_ref_is_knowable<'tcx>(tcx: &TyCtxt<'tcx>, trait_ref: &ty::TraitRef<'tcx>) -> bool
  92 {
  93     debug!("trait_ref_is_knowable(trait_ref={:?})", trait_ref);
  94
  95     // if the orphan rules pass, that means that no ancestor crate can
  96     // impl this, so it's up to us.
  97     if orphan_check_trait_ref(tcx, trait_ref, InferIsLocal(false)).is_ok() {
  98         debug!("trait_ref_is_knowable: orphan check passed");
  99         return true;
 100     }
 101
 102     // if the trait is not marked fundamental, then it's always possible that
 103     // an ancestor crate will impl this in the future, if they haven't
 104     // already
 105     if
 106         trait_ref.def_id.krate != LOCAL_CRATE &&
 107         !tcx.has_attr(trait_ref.def_id, "fundamental")
 108     {
 109         debug!("trait_ref_is_knowable: trait is neither local nor fundamental");
 110         return false;
 111     }
 112
 113     // find out when some downstream (or cousin) crate could impl this
 114     // trait-ref, presuming that all the parameters were instantiated
 115     // with downstream types. If not, then it could only be
 116     // implemented by an upstream crate, which means that the impl
 117     // must be visible to us, and -- since the trait is fundamental
 118     // -- we can test.
 119     orphan_check_trait_ref(tcx, trait_ref, InferIsLocal(true)).is_err()
 120 }
 121
 122 pub enum OrphanCheckErr<'tcx> {
 123     NoLocalInputType,
 124     UncoveredTy(Ty<'tcx>),
 125 }
 126
 127 /// Checks the coherence orphan rules. `impl_def_id` should be the
 128 /// def-id of a trait impl. To pass, either the trait must be local, or else
 129 /// two conditions must be satisfied:
 130 ///
 131 /// 1. All type parameters in `Self` must be "covered" by some local type constructor.
 132 /// 2. Some local type must appear in `Self`.
 133 pub fn orphan_check<'tcx>(tcx: &TyCtxt<'tcx>,
 134                           impl_def_id: DefId)
 135                           -> Result<(), OrphanCheckErr<'tcx>>
 136 {
 137     debug!("orphan_check({:?})", impl_def_id);
 138
 139     // We only except this routine to be invoked on implementations
 140     // of a trait, not inherent implementations.
 141     let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
 142     debug!("orphan_check: trait_ref={:?}", trait_ref);
 143
 144     // If the *trait* is local to the crate, ok.
 145     if trait_ref.def_id.is_local() {
 146         debug!("trait {:?} is local to current crate",
 147                trait_ref.def_id);
 148         return Ok(());
 149     }
 150
 151     orphan_check_trait_ref(tcx, &trait_ref, InferIsLocal(false))
 152 }
 153
 154 fn orphan_check_trait_ref<'tcx>(tcx: &TyCtxt<'tcx>,
 155                                 trait_ref: &ty::TraitRef<'tcx>,
 156                                 infer_is_local: InferIsLocal)
 157                                 -> Result<(), OrphanCheckErr<'tcx>>
 158 {
 159     debug!("orphan_check_trait_ref(trait_ref={:?}, infer_is_local={})",
 160            trait_ref, infer_is_local.0);
 161
 162     // First, create an ordered iterator over all the type parameters to the trait, with the self
 163     // type appearing first.
 164     let input_tys = Some(trait_ref.self_ty());
 165     let input_tys = input_tys.iter().chain(trait_ref.substs.types.get_slice(TypeSpace));
 166
 167     // Find the first input type that either references a type parameter OR
 168     // some local type.
 169     for input_ty in input_tys {
 170         if ty_is_local(tcx, input_ty, infer_is_local) {
 171             debug!("orphan_check_trait_ref: ty_is_local `{:?}`", input_ty);
 172
 173             // First local input type. Check that there are no
 174             // uncovered type parameters.
 175             let uncovered_tys = uncovered_tys(tcx, input_ty, infer_is_local);
 176             for uncovered_ty in uncovered_tys {
 177                 if let Some(param) = uncovered_ty.walk().find(|t| is_type_parameter(t)) {
 178                     debug!("orphan_check_trait_ref: uncovered type `{:?}`", param);
 179                     return Err(OrphanCheckErr::UncoveredTy(param));
 180                 }
 181             }
 182
 183             // OK, found local type, all prior types upheld invariant.
 184             return Ok(());
 185         }
 186
 187         // Otherwise, enforce invariant that there are no type
 188         // parameters reachable.
 189         if !infer_is_local.0 {
 190             if let Some(param) = input_ty.walk().find(|t| is_type_parameter(t)) {
 191                 debug!("orphan_check_trait_ref: uncovered type `{:?}`", param);
 192                 return Err(OrphanCheckErr::UncoveredTy(param));
 193             }
 194         }
 195     }
 196
 197     // If we exit above loop, never found a local type.
 198     debug!("orphan_check_trait_ref: no local type");
 199     return Err(OrphanCheckErr::NoLocalInputType);
 200 }
 201
 202 fn uncovered_tys<'tcx>(tcx: &TyCtxt<'tcx>,
 203                        ty: Ty<'tcx>,
 204                        infer_is_local: InferIsLocal)
 205                        -> Vec<Ty<'tcx>>
 206 {
 207     if ty_is_local_constructor(tcx, ty, infer_is_local) {
 208         vec![]
 209     } else if fundamental_ty(tcx, ty) {
 210         ty.walk_shallow()
 211           .flat_map(|t| uncovered_tys(tcx, t, infer_is_local))
 212           .collect()
 213     } else {
 214         vec![ty]
 215     }
 216 }
 217
 218 fn is_type_parameter<'tcx>(ty: Ty<'tcx>) -> bool {
 219     match ty.sty {
 220         // FIXME(#20590) straighten story about projection types
 221         ty::TyProjection(..) | ty::TyParam(..) => true,
 222         _ => false,
 223     }
 224 }
 225
 226 fn ty_is_local<'tcx>(tcx: &TyCtxt<'tcx>, ty: Ty<'tcx>, infer_is_local: InferIsLocal) -> bool
 227 {
 228     ty_is_local_constructor(tcx, ty, infer_is_local) ||
 229         fundamental_ty(tcx, ty) && ty.walk_shallow().any(|t| ty_is_local(tcx, t, infer_is_local))
 230 }
 231
 232 fn fundamental_ty<'tcx>(tcx: &TyCtxt<'tcx>, ty: Ty<'tcx>) -> bool
 233 {
 234     match ty.sty {
 235         ty::TyBox(..) | ty::TyRef(..) =>
 236             true,
 237         ty::TyEnum(def, _) | ty::TyStruct(def, _) =>
 238             def.is_fundamental(),
 239         ty::TyTrait(ref data) =>
 240             tcx.has_attr(data.principal_def_id(), "fundamental"),
 241         _ =>
 242             false
 243     }
 244 }
 245
 246 fn ty_is_local_constructor<'tcx>(tcx: &TyCtxt<'tcx>,
 247                                  ty: Ty<'tcx>,
 248                                  infer_is_local: InferIsLocal)
 249                                  -> bool
 250 {
 251     debug!("ty_is_local_constructor({:?})", ty);
 252
 253     match ty.sty {
 254         ty::TyBool |
 255         ty::TyChar |
 256         ty::TyInt(..) |
 257         ty::TyUint(..) |
 258         ty::TyFloat(..) |
 259         ty::TyStr |
 260         ty::TyFnDef(..) |
 261         ty::TyFnPtr(_) |
 262         ty::TyArray(..) |
 263         ty::TySlice(..) |
 264         ty::TyRawPtr(..) |
 265         ty::TyRef(..) |
 266         ty::TyTuple(..) |
 267         ty::TyParam(..) |
 268         ty::TyProjection(..) => {
 269             false
 270         }
 271
 272         ty::TyInfer(..) => {
 273             infer_is_local.0
 274         }
 275
 276         ty::TyEnum(def, _) |
 277         ty::TyStruct(def, _) => {
 278             def.did.is_local()
 279         }
 280
 281         ty::TyBox(_) => { // Box<T>
 282             let krate = tcx.lang_items.owned_box().map(|d| d.krate);
 283             krate == Some(LOCAL_CRATE)
 284         }
 285
 286         ty::TyTrait(ref tt) => {
 287             tt.principal_def_id().is_local()
 288         }
 289
 290         ty::TyError => {
 291             true
 292         }
 293
 294         ty::TyClosure(..) => {
 295             tcx.sess.bug(
 296                 &format!("ty_is_local invoked on unexpected type: {:?}",
 297                         ty))
 298         }
 299     }
 300 }