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