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.
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.
11 //! See `doc.rs` for high-level documentation
13 use super::SelectionContext;
14 use super::{Obligation, ObligationCause};
17 use middle::subst::Subst;
18 use middle::ty::{self, Ty};
19 use middle::infer::InferCtxt;
20 use std::collections::HashSet;
23 use syntax::codemap::DUMMY_SP;
24 use util::ppaux::Repr;
26 pub fn impl_can_satisfy(infcx: &InferCtxt,
27 impl1_def_id: ast::DefId,
28 impl2_def_id: ast::DefId)
31 debug!("impl_can_satisfy(\
34 impl1_def_id.repr(infcx.tcx),
35 impl2_def_id.repr(infcx.tcx));
37 // `impl1` provides an implementation of `Foo<X,Y> for Z`.
39 util::fresh_substs_for_impl(infcx, DUMMY_SP, impl1_def_id);
41 (*ty::impl_trait_ref(infcx.tcx, impl1_def_id).unwrap()).subst(infcx.tcx, &impl1_substs);
43 // Determine whether `impl2` can provide an implementation for those
45 let param_env = ty::empty_parameter_environment(infcx.tcx);
46 let mut selcx = SelectionContext::intercrate(infcx, ¶m_env);
47 let obligation = Obligation::new(ObligationCause::dummy(),
48 ty::Binder(ty::TraitPredicate {
49 trait_ref: Rc::new(impl1_trait_ref),
51 debug!("impl_can_satisfy(obligation={})", obligation.repr(infcx.tcx));
52 selcx.evaluate_impl(impl2_def_id, &obligation)
55 #[allow(missing_copy_implementations)]
56 pub enum OrphanCheckErr {
58 UncoveredTypeParameter(ty::ParamTy),
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:
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>
71 debug!("impl_is_local({})", impl_def_id.repr(tcx));
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));
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));
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);
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())
95 let all_params: HashSet<_> =
96 trait_ref.input_types().iter()
97 .flat_map(|&t| type_parameters_reachable_from_ty(t).into_iter())
99 for ¶m in all_params.difference(&covered_params) {
100 return Err(OrphanCheckErr::UncoveredTypeParameter(param));
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))
110 fn ty_is_local_constructor<'tcx>(tcx: &ty::ctxt<'tcx>, ty: Ty<'tcx>) -> bool {
111 debug!("ty_is_local_constructor({})", ty.repr(tcx));
127 ty::ty_projection(..) => {
131 ty::ty_enum(def_id, _) |
132 ty::ty_struct(def_id, _) => {
133 def_id.krate == ast::LOCAL_CRATE
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)
141 ty::ty_trait(ref tt) => {
142 tt.principal_def_id().krate == ast::LOCAL_CRATE
145 ty::ty_unboxed_closure(..) |
150 format!("ty_is_local invoked on unexpected type: {}",
156 fn type_parameters_covered_by_ty<'tcx>(tcx: &ty::ctxt<'tcx>,
158 -> HashSet<ty::ParamTy>
160 if ty_is_local_constructor(tcx, ty) {
161 type_parameters_reachable_from_ty(ty)
163 ty.walk_children().flat_map(|t| type_parameters_covered_by_ty(tcx, t).into_iter()).collect()
167 /// All type parameters reachable from `ty`
168 fn type_parameters_reachable_from_ty<'tcx>(ty: Ty<'tcx>) -> HashSet<ty::ParamTy> {
172 ty::ty_param(ref param_ty) => Some(param_ty.clone()),