1 // Copyright 2015 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 // Logic and data structures related to impl specialization, explained in
12 // greater detail below.
14 // At the moment, this implementation support only the simple "chain" rule:
15 // If any two impls overlap, one must be a strict subset of the other.
17 // See traits/README.md for a bit more detail on how specialization
18 // fits together with the rest of the trait machinery.
20 use super::{SelectionContext, FulfillmentContext}
;
21 use super::util
::{fresh_type_vars_for_impl, impl_trait_ref_and_oblig}
;
23 use rustc_data_structures
::fnv
::FnvHashMap
;
24 use hir
::def_id
::DefId
;
25 use infer
::{InferCtxt, TypeOrigin}
;
27 use ty
::subst
::{Subst, Substs}
;
28 use traits
::{self, Reveal, ObligationCause, Normalized}
;
29 use ty
::{self, TyCtxt}
;
30 use syntax_pos
::DUMMY_SP
;
32 pub mod specialization_graph
;
34 /// Information pertinent to an overlapping impl error.
35 pub struct OverlapError
{
37 pub trait_desc
: String
,
38 pub self_desc
: Option
<String
>
41 /// Given a subst for the requested impl, translate it to a subst
42 /// appropriate for the actual item definition (whether it be in that impl,
43 /// a parent impl, or the trait).
44 /// When we have selected one impl, but are actually using item definitions from
45 /// a parent impl providing a default, we need a way to translate between the
46 /// type parameters of the two impls. Here the `source_impl` is the one we've
47 /// selected, and `source_substs` is a substitution of its generics (and
48 /// possibly some relevant `FnSpace` variables as well). And `target_node` is
49 /// the impl/trait we're actually going to get the definition from. The resulting
50 /// substitution will map from `target_node`'s generics to `source_impl`'s
51 /// generics as instantiated by `source_subst`.
53 /// For example, consider the following scenario:
57 /// impl<T, U> Foo for (T, U) { ... } // target impl
58 /// impl<V> Foo for (V, V) { ... } // source impl
61 /// Suppose we have selected "source impl" with `V` instantiated with `u32`.
62 /// This function will produce a substitution with `T` and `U` both mapping to `u32`.
64 /// Where clauses add some trickiness here, because they can be used to "define"
65 /// an argument indirectly:
68 /// impl<'a, I, T: 'a> Iterator for Cloned<I>
69 /// where I: Iterator<Item=&'a T>, T: Clone
72 /// In a case like this, the substitution for `T` is determined indirectly,
73 /// through associated type projection. We deal with such cases by using
74 /// *fulfillment* to relate the two impls, requiring that all projections are
76 pub fn translate_substs
<'a
, 'gcx
, 'tcx
>(infcx
: &InferCtxt
<'a
, 'gcx
, 'tcx
>,
78 source_substs
: &'tcx Substs
<'tcx
>,
79 target_node
: specialization_graph
::Node
)
80 -> &'tcx Substs
<'tcx
> {
81 let source_trait_ref
= infcx
.tcx
82 .impl_trait_ref(source_impl
)
84 .subst(infcx
.tcx
, &source_substs
);
86 // translate the Self and TyParam parts of the substitution, since those
88 let target_substs
= match target_node
{
89 specialization_graph
::Node
::Impl(target_impl
) => {
90 // no need to translate if we're targetting the impl we started with
91 if source_impl
== target_impl
{
95 fulfill_implication(infcx
, source_trait_ref
, target_impl
).unwrap_or_else(|_
| {
96 bug
!("When translating substitutions for specialization, the expected \
97 specializaiton failed to hold")
100 specialization_graph
::Node
::Trait(..) => source_trait_ref
.substs
,
103 // directly inherent the method generics, since those do not vary across impls
104 infcx
.tcx
.mk_substs(target_substs
.with_method_from_subst(source_substs
))
107 /// Is impl1 a specialization of impl2?
109 /// Specialization is determined by the sets of types to which the impls apply;
110 /// impl1 specializes impl2 if it applies to a subset of the types impl2 applies
112 pub fn specializes
<'a
, 'tcx
>(tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>,
114 impl2_def_id
: DefId
) -> bool
{
115 if let Some(r
) = tcx
.specializes_cache
.borrow().check(impl1_def_id
, impl2_def_id
) {
119 // The feature gate should prevent introducing new specializations, but not
120 // taking advantage of upstream ones.
121 if !tcx
.sess
.features
.borrow().specialization
&&
122 (impl1_def_id
.is_local() || impl2_def_id
.is_local()) {
126 // We determine whether there's a subset relationship by:
128 // - skolemizing impl1,
129 // - assuming the where clauses for impl1,
130 // - instantiating impl2 with fresh inference variables,
132 // - attempting to prove the where clauses for impl2
134 // The last three steps are encapsulated in `fulfill_implication`.
136 // See RFC 1210 for more details and justification.
138 // Currently we do not allow e.g. a negative impl to specialize a positive one
139 if tcx
.trait_impl_polarity(impl1_def_id
) != tcx
.trait_impl_polarity(impl2_def_id
) {
143 // create a parameter environment corresponding to a (skolemized) instantiation of impl1
144 let scheme
= tcx
.lookup_item_type(impl1_def_id
);
145 let predicates
= tcx
.lookup_predicates(impl1_def_id
);
146 let mut penv
= tcx
.construct_parameter_environment(DUMMY_SP
,
149 region
::DUMMY_CODE_EXTENT
);
150 let impl1_trait_ref
= tcx
.impl_trait_ref(impl1_def_id
)
152 .subst(tcx
, &penv
.free_substs
);
154 let result
= tcx
.normalizing_infer_ctxt(Reveal
::ExactMatch
).enter(|mut infcx
| {
155 // Normalize the trait reference, adding any obligations
156 // that arise into the impl1 assumptions.
157 let Normalized { value: impl1_trait_ref, obligations: normalization_obligations }
= {
158 let selcx
= &mut SelectionContext
::new(&infcx
);
159 traits
::normalize(selcx
, ObligationCause
::dummy(), &impl1_trait_ref
)
161 penv
.caller_bounds
.extend(normalization_obligations
.into_iter().map(|o
| {
162 match tcx
.lift_to_global(&o
.predicate
) {
163 Some(predicate
) => predicate
,
165 bug
!("specializes: obligation `{:?}` has inference types/regions", o
);
170 // Install the parameter environment, taking the predicates of impl1 as assumptions:
171 infcx
.parameter_environment
= penv
;
173 // Attempt to prove that impl2 applies, given all of the above.
174 fulfill_implication(&infcx
, impl1_trait_ref
, impl2_def_id
).is_ok()
177 tcx
.specializes_cache
.borrow_mut().insert(impl1_def_id
, impl2_def_id
, result
);
181 /// Attempt to fulfill all obligations of `target_impl` after unification with
182 /// `source_trait_ref`. If successful, returns a substitution for *all* the
183 /// generics of `target_impl`, including both those needed to unify with
184 /// `source_trait_ref` and those whose identity is determined via a where
185 /// clause in the impl.
186 fn fulfill_implication
<'a
, 'gcx
, 'tcx
>(infcx
: &InferCtxt
<'a
, 'gcx
, 'tcx
>,
187 source_trait_ref
: ty
::TraitRef
<'tcx
>,
189 -> Result
<&'tcx Substs
<'tcx
>, ()> {
190 let selcx
= &mut SelectionContext
::new(&infcx
);
191 let target_substs
= fresh_type_vars_for_impl(&infcx
, DUMMY_SP
, target_impl
);
192 let (target_trait_ref
, obligations
) = impl_trait_ref_and_oblig(selcx
,
196 // do the impls unify? If not, no specialization.
197 if let Err(_
) = infcx
.eq_trait_refs(true,
198 TypeOrigin
::Misc(DUMMY_SP
),
201 debug
!("fulfill_implication: {:?} does not unify with {:?}",
207 // attempt to prove all of the predicates for impl2 given those for impl1
208 // (which are packed up in penv)
210 let mut fulfill_cx
= FulfillmentContext
::new();
211 for oblig
in obligations
.into_iter() {
212 fulfill_cx
.register_predicate_obligation(&infcx
, oblig
);
215 if let Err(errors
) = infcx
.drain_fulfillment_cx(&mut fulfill_cx
, &()) {
217 debug
!("fulfill_implication: for impls on {:?} and {:?}, could not fulfill: {:?} given \
222 infcx
.parameter_environment
.caller_bounds
);
225 debug
!("fulfill_implication: an impl for {:?} specializes {:?}",
229 // Now resolve the *substitution* we built for the target earlier, replacing
230 // the inference variables inside with whatever we got from fulfillment.
231 Ok(infcx
.resolve_type_vars_if_possible(&target_substs
))
235 pub struct SpecializesCache
{
236 map
: FnvHashMap
<(DefId
, DefId
), bool
>
239 impl SpecializesCache
{
240 pub fn new() -> Self {
246 pub fn check(&self, a
: DefId
, b
: DefId
) -> Option
<bool
> {
247 self.map
.get(&(a
, b
)).cloned()
250 pub fn insert(&mut self, a
: DefId
, b
: DefId
, result
: bool
) {
251 self.map
.insert((a
, b
), result
);