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