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 middle::cstore::CrateStore;
24 use middle::def_id::DefId;
25 use middle::infer::{self, InferCtxt, TypeOrigin};
27 use middle::subst::{Subst, Substs};
28 use middle::traits::{self, ProjectionMode, ObligationCause, Normalized};
29 use middle::ty::{self, TyCtxt};
30 use syntax::codemap::DUMMY_SP;
32 pub mod specialization_graph;
34 /// Information pertinent to an overlapping impl error.
35 pub struct Overlap<'a, 'tcx: 'a> {
36 pub in_context: InferCtxt<'a, 'tcx>,
38 pub on_trait_ref: ty::TraitRef<'tcx>,
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, 'tcx>(infcx: &InferCtxt<'a, '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(|_| {
98 .bug("When translating substitutions for specialization, the expected \
99 specializaiton failed to hold")
102 specialization_graph::Node::Trait(..) => source_trait_ref.substs.clone(),
105 // retain erasure mode
106 // NB: this must happen before inheriting method generics below
107 let target_substs = if source_substs.regions.is_erased() {
108 target_substs.erase_regions()
113 // directly inherent the method generics, since those do not vary across impls
114 infcx.tcx.mk_substs(target_substs.with_method_from_subst(source_substs))
117 /// Is impl1 a specialization of impl2?
119 /// Specialization is determined by the sets of types to which the impls apply;
120 /// impl1 specializes impl2 if it applies to a subset of the types impl2 applies
122 pub fn specializes(tcx: &TyCtxt, impl1_def_id: DefId, impl2_def_id: DefId) -> bool {
123 // The feature gate should prevent introducing new specializations, but not
124 // taking advantage of upstream ones.
125 if !tcx.sess.features.borrow().specialization &&
126 (impl1_def_id.is_local() || impl2_def_id.is_local()) {
130 // We determine whether there's a subset relationship by:
132 // - skolemizing impl1,
133 // - assuming the where clauses for impl1,
134 // - instantiating impl2 with fresh inference variables,
136 // - attempting to prove the where clauses for impl2
138 // The last three steps are encapsulated in `fulfill_implication`.
140 // See RFC 1210 for more details and justification.
142 // Currently we do not allow e.g. a negative impl to specialize a positive one
143 if tcx.trait_impl_polarity(impl1_def_id) != tcx.trait_impl_polarity(impl2_def_id) {
147 let mut infcx = infer::normalizing_infer_ctxt(tcx, &tcx.tables, ProjectionMode::Topmost);
149 // create a parameter environment corresponding to a (skolemized) instantiation of impl1
150 let scheme = tcx.lookup_item_type(impl1_def_id);
151 let predicates = tcx.lookup_predicates(impl1_def_id);
152 let mut penv = tcx.construct_parameter_environment(DUMMY_SP,
155 region::DUMMY_CODE_EXTENT);
156 let impl1_trait_ref = tcx.impl_trait_ref(impl1_def_id)
158 .subst(tcx, &penv.free_substs);
160 // Normalize the trait reference, adding any obligations that arise into the impl1 assumptions
161 let Normalized { value: impl1_trait_ref, obligations: normalization_obligations } = {
162 let selcx = &mut SelectionContext::new(&infcx);
163 traits::normalize(selcx, ObligationCause::dummy(), &impl1_trait_ref)
165 penv.caller_bounds.extend(normalization_obligations.into_iter().map(|o| o.predicate));
167 // Install the parameter environment, taking the predicates of impl1 as assumptions:
168 infcx.parameter_environment = penv;
170 // Attempt to prove that impl2 applies, given all of the above.
171 fulfill_implication(&infcx, impl1_trait_ref, impl2_def_id).is_ok()
174 /// Attempt to fulfill all obligations of `target_impl` after unification with
175 /// `source_trait_ref`. If successful, returns a substitution for *all* the
176 /// generics of `target_impl`, including both those needed to unify with
177 /// `source_trait_ref` and those whose identity is determined via a where
178 /// clause in the impl.
179 fn fulfill_implication<'a, 'tcx>(infcx: &InferCtxt<'a, 'tcx>,
180 source_trait_ref: ty::TraitRef<'tcx>,
182 -> Result<Substs<'tcx>, ()> {
183 infcx.commit_if_ok(|_| {
184 let selcx = &mut SelectionContext::new(&infcx);
185 let target_substs = fresh_type_vars_for_impl(&infcx, DUMMY_SP, target_impl);
186 let (target_trait_ref, obligations) = impl_trait_ref_and_oblig(selcx,
190 // do the impls unify? If not, no specialization.
191 if let Err(_) = infer::mk_eq_trait_refs(&infcx,
193 TypeOrigin::Misc(DUMMY_SP),
196 debug!("fulfill_implication: {:?} does not unify with {:?}",
202 // attempt to prove all of the predicates for impl2 given those for impl1
203 // (which are packed up in penv)
205 let mut fulfill_cx = FulfillmentContext::new();
206 for oblig in obligations.into_iter() {
207 fulfill_cx.register_predicate_obligation(&infcx, oblig);
210 if let Err(errors) = infer::drain_fulfillment_cx(&infcx, &mut fulfill_cx, &()) {
212 debug!("fulfill_implication: for impls on {:?} and {:?}, could not fulfill: {:?} given \
217 infcx.parameter_environment.caller_bounds);
220 debug!("fulfill_implication: an impl for {:?} specializes {:?}",
224 // Now resolve the *substitution* we built for the target earlier, replacing
225 // the inference variables inside with whatever we got from fulfillment.
226 Ok(infcx.resolve_type_vars_if_possible(&target_substs))