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, ObligationCause};
  15 use super::util;
  16
  17 use middle::subst::Subst;
  18 use middle::ty::{mod, Ty};
  19 use middle::infer::InferCtxt;
  20 use std::collections::HashSet;
  21 use std::rc::Rc;
  22 use syntax::ast;
  23 use syntax::codemap::DUMMY_SP;
  24 use util::ppaux::Repr;
  25
  26 pub fn impl_can_satisfy(infcx: &InferCtxt,
  27                         impl1_def_id: ast::DefId,
  28                         impl2_def_id: ast::DefId)
  29                         -> bool
  30 {
  31     debug!("impl_can_satisfy(\
  32            impl1_def_id={}, \
  33            impl2_def_id={})",
  34            impl1_def_id.repr(infcx.tcx),
  35            impl2_def_id.repr(infcx.tcx));
  36
  37     // `impl1` provides an implementation of `Foo<X,Y> for Z`.
  38     let impl1_substs =
  39         util::fresh_substs_for_impl(infcx, DUMMY_SP, impl1_def_id);
  40     let impl1_trait_ref =
  41         (*ty::impl_trait_ref(infcx.tcx, impl1_def_id).unwrap()).subst(infcx.tcx, &impl1_substs);
  42
  43     // Determine whether `impl2` can provide an implementation for those
  44     // same types.
  45     let param_env = ty::empty_parameter_environment(infcx.tcx);
  46     let mut selcx = SelectionContext::intercrate(infcx, &param_env);
  47     let obligation = Obligation::new(ObligationCause::dummy(),
  48                                      ty::Binder(ty::TraitPredicate {
  49                                          trait_ref: Rc::new(impl1_trait_ref),
  50                                      }));
  51     debug!("impl_can_satisfy(obligation={})", obligation.repr(infcx.tcx));
  52     selcx.evaluate_impl(impl2_def_id, &obligation)
  53 }
  54
  55 #[allow(missing_copy_implementations)]
  56 pub enum OrphanCheckErr {
  57     NoLocalInputType,
  58     UncoveredTypeParameter(ty::ParamTy),
  59 }
  60
  61 /// Checks the coherence orphan rules. `impl_def_id` should be the
  62 /// def-id of a trait impl. To pass, either the trait must be local, or else
  63 /// two conditions must be satisfied:
  64 ///
  65 /// 1. At least one of the input types must involve a local type.
  66 /// 2. All type parameters must be covered by a local type.
  67 pub fn orphan_check(tcx: &ty::ctxt,
  68                     impl_def_id: ast::DefId)
  69                     -> Result<(), OrphanCheckErr>
  70 {
  71     debug!("impl_is_local({})", impl_def_id.repr(tcx));
  72
  73     // We only except this routine to be invoked on implementations
  74     // of a trait, not inherent implementations.
  75     let trait_ref = ty::impl_trait_ref(tcx, impl_def_id).unwrap();
  76     debug!("trait_ref={}", trait_ref.repr(tcx));
  77
  78     // If the *trait* is local to the crate, ok.
  79     if trait_ref.def_id.krate == ast::LOCAL_CRATE {
  80         debug!("trait {} is local to current crate",
  81                trait_ref.def_id.repr(tcx));
  82         return Ok(());
  83     }
  84
  85     // Check condition 1: at least one type must be local.
  86     if !trait_ref.input_types().iter().any(|&t| ty_reaches_local(tcx, t)) {
  87         return Err(OrphanCheckErr::NoLocalInputType);
  88     }
  89
  90     // Check condition 2: type parameters must be "covered" by a local type.
  91     let covered_params: HashSet<_> =
  92         trait_ref.input_types().iter()
  93                                .flat_map(|&t| type_parameters_covered_by_ty(tcx, t).into_iter())
  94                                .collect();
  95     let all_params: HashSet<_> =
  96         trait_ref.input_types().iter()
  97                                .flat_map(|&t| type_parameters_reachable_from_ty(t).into_iter())
  98                                .collect();
  99     for &param in all_params.difference(&covered_params) {
 100         return Err(OrphanCheckErr::UncoveredTypeParameter(param));
 101     }
 102
 103     return Ok(());
 104 }
 105
 106 fn ty_reaches_local<'tcx>(tcx: &ty::ctxt<'tcx>, ty: Ty<'tcx>) -> bool {
 107     ty.walk().any(|t| ty_is_local_constructor(tcx, t))
 108 }
 109
 110 fn ty_is_local_constructor<'tcx>(tcx: &ty::ctxt<'tcx>, ty: Ty<'tcx>) -> bool {
 111     debug!("ty_is_local_constructor({})", ty.repr(tcx));
 112
 113     match ty.sty {
 114         ty::ty_bool |
 115         ty::ty_char |
 116         ty::ty_int(..) |
 117         ty::ty_uint(..) |
 118         ty::ty_float(..) |
 119         ty::ty_str(..) |
 120         ty::ty_bare_fn(..) |
 121         ty::ty_closure(..) |
 122         ty::ty_vec(..) |
 123         ty::ty_ptr(..) |
 124         ty::ty_rptr(..) |
 125         ty::ty_tup(..) |
 126         ty::ty_param(..) |
 127         ty::ty_projection(..) => {
 128             false
 129         }
 130
 131         ty::ty_enum(def_id, _) |
 132         ty::ty_struct(def_id, _) => {
 133             def_id.krate == ast::LOCAL_CRATE
 134         }
 135
 136         ty::ty_uniq(_) => { // treat ~T like Box<T>
 137             let krate = tcx.lang_items.owned_box().map(|d| d.krate);
 138             krate == Some(ast::LOCAL_CRATE)
 139         }
 140
 141         ty::ty_trait(ref tt) => {
 142             tt.principal_def_id().krate == ast::LOCAL_CRATE
 143         }
 144
 145         ty::ty_unboxed_closure(..) |
 146         ty::ty_infer(..) |
 147         ty::ty_open(..) |
 148         ty::ty_err => {
 149             tcx.sess.bug(
 150                 format!("ty_is_local invoked on unexpected type: {}",
 151                         ty.repr(tcx))[])
 152         }
 153     }
 154 }
 155
 156 fn type_parameters_covered_by_ty<'tcx>(tcx: &ty::ctxt<'tcx>,
 157                                  ty: Ty<'tcx>)
 158                                  -> HashSet<ty::ParamTy>
 159 {
 160     if ty_is_local_constructor(tcx, ty) {
 161         type_parameters_reachable_from_ty(ty)
 162     } else {
 163         ty.walk_children().flat_map(|t| type_parameters_covered_by_ty(tcx, t).into_iter()).collect()
 164     }
 165 }
 166
 167 /// All type parameters reachable from `ty`
 168 fn type_parameters_reachable_from_ty<'tcx>(ty: Ty<'tcx>) -> HashSet<ty::ParamTy> {
 169     ty.walk()
 170         .filter_map(|t| {
 171             match t.sty {
 172                 ty::ty_param(ref param_ty) => Some(param_ty.clone()),
 173                 _ => None,
 174             }
 175         })
 176         .collect()
 177 }
 178