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 `README.md` for high-level documentation
13 use super::Normalized
;
14 use super::SelectionContext
;
15 use super::ObligationCause
;
16 use super::PredicateObligation
;
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}
;
27 #[derive(Copy, Clone)]
28 struct InferIsLocal(bool
);
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
>,
35 -> Option
<ty
::TraitRef
<'tcx
>>
37 debug
!("impl_can_satisfy(\
43 let selcx
= &mut SelectionContext
::intercrate(infcx
);
44 overlap(selcx
, impl1_def_id
, impl2_def_id
)
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
>,
52 -> Option
<ty
::TraitRef
<'tcx
>>
54 debug
!("overlap(a_def_id={:?}, b_def_id={:?})",
58 let (a_trait_ref
, a_obligations
) = impl_trait_ref_and_oblig(selcx
,
60 util
::fresh_type_vars_for_impl
);
62 let (b_trait_ref
, b_obligations
) = impl_trait_ref_and_oblig(selcx
,
64 util
::fresh_type_vars_for_impl
);
66 debug
!("overlap: a_trait_ref={:?} a_obligations={:?}", a_trait_ref
, a_obligations
);
68 debug
!("overlap: b_trait_ref={:?} b_obligations={:?}", b_trait_ref
, b_obligations
);
70 // Do `a` and `b` unify? If not, no overlap.
71 if let Err(_
) = infer
::mk_eq_trait_refs(selcx
.infcx(),
73 TypeOrigin
::Misc(DUMMY_SP
),
79 debug
!("overlap: unification check succeeded");
81 // Are any of the obligations unsatisfiable? If so, no overlap.
82 let infcx
= selcx
.infcx();
83 let opt_failing_obligation
=
85 .chain(&b_obligations
)
86 .map(|o
| infcx
.resolve_type_vars_if_possible(o
))
87 .find(|o
| !selcx
.evaluate_obligation(o
));
89 if let Some(failing_obligation
) = opt_failing_obligation
{
90 debug
!("overlap: obligation unsatisfiable {:?}", failing_obligation
);
94 Some(selcx
.infcx().resolve_type_vars_if_possible(&a_trait_ref
))
97 pub fn trait_ref_is_knowable
<'tcx
>(tcx
: &ty
::ctxt
<'tcx
>, trait_ref
: &ty
::TraitRef
<'tcx
>) -> bool
99 debug
!("trait_ref_is_knowable(trait_ref={:?})", trait_ref
);
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");
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
112 trait_ref
.def_id
.krate
!= LOCAL_CRATE
&&
113 !tcx
.has_attr(trait_ref
.def_id
, "fundamental")
115 debug
!("trait_ref_is_knowable: trait is neither local nor fundamental");
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
125 orphan_check_trait_ref(tcx
, trait_ref
, InferIsLocal(true)).is_err()
128 type SubstsFn
= for<'a
,'tcx
> fn(infcx
: &InferCtxt
<'a
, 'tcx
>,
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
>,
138 -> (ty
::TraitRef
<'tcx
>,
139 Vec
<PredicateObligation
<'tcx
>>)
142 &substs_fn(selcx
.infcx(), DUMMY_SP
, impl_def_id
);
144 selcx
.tcx().impl_trait_ref(impl_def_id
).unwrap();
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
);
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
);
157 let impl_obligations
: Vec
<_
> =
158 impl_obligations
.into_iter()
159 .chain(normalization_obligations1
)
160 .chain(normalization_obligations2
)
163 (impl_trait_ref
, impl_obligations
)
166 pub enum OrphanCheckErr
<'tcx
> {
168 UncoveredTy(Ty
<'tcx
>),
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:
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
>,
179 -> Result
<(), OrphanCheckErr
<'tcx
>>
181 debug
!("orphan_check({:?})", impl_def_id
);
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
);
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",
195 orphan_check_trait_ref(tcx
, &trait_ref
, InferIsLocal(false))
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
>>
203 debug
!("orphan_check_trait_ref(trait_ref={:?}, infer_is_local={})",
204 trait_ref
, infer_is_local
.0);
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
));
211 // Find the first input type that either references a type parameter OR
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
);
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
));
227 // OK, found local type, all prior types upheld invariant.
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
));
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
);
246 fn uncovered_tys
<'tcx
>(tcx
: &ty
::ctxt
<'tcx
>,
248 infer_is_local
: InferIsLocal
)
251 if ty_is_local_constructor(tcx
, ty
, infer_is_local
) {
253 } else if fundamental_ty(tcx
, ty
) {
255 .flat_map(|t
| uncovered_tys(tcx
, t
, infer_is_local
))
262 fn is_type_parameter
<'tcx
>(ty
: Ty
<'tcx
>) -> bool
{
264 // FIXME(#20590) straighten story about projection types
265 ty
::TyProjection(..) | ty
::TyParam(..) => true,
270 fn ty_is_local
<'tcx
>(tcx
: &ty
::ctxt
<'tcx
>, ty
: Ty
<'tcx
>, infer_is_local
: InferIsLocal
) -> bool
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
))
276 fn fundamental_ty
<'tcx
>(tcx
: &ty
::ctxt
<'tcx
>, ty
: Ty
<'tcx
>) -> bool
279 ty
::TyBox(..) | ty
::TyRef(..) =>
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"),
290 fn ty_is_local_constructor
<'tcx
>(tcx
: &ty
::ctxt
<'tcx
>,
292 infer_is_local
: InferIsLocal
)
295 debug
!("ty_is_local_constructor({:?})", ty
);
311 ty
::TyProjection(..) => {
320 ty
::TyStruct(def
, _
) => {
324 ty
::TyBox(_
) => { // Box<T>
325 let krate
= tcx
.lang_items
.owned_box().map(|d
| d
.krate
);
326 krate
== Some(LOCAL_CRATE
)
329 ty
::TyTrait(ref tt
) => {
330 tt
.principal_def_id().is_local()
337 ty
::TyClosure(..) => {
339 &format
!("ty_is_local invoked on unexpected type: {:?}",