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