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::impl_trait_ref_and_oblig;
23 use rustc_data_structures::fx::FxHashMap;
24 use hir::def_id::DefId;
25 use infer::{InferCtxt, InferOk};
26 use ty::subst::{Subst, Substs};
27 use traits::{self, Reveal, ObligationCause};
28 use ty::{self, TyCtxt, TypeFoldable};
29 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.
48 /// And `target_node` is the impl/trait we're actually going to get the
49 /// definition from. The resulting substitution will map from `target_node`'s
50 /// generics to `source_impl`'s generics as instantiated by `source_subst`.
52 /// For example, consider the following scenario:
56 /// impl<T, U> Foo for (T, U) { ... } // target impl
57 /// impl<V> Foo for (V, V) { ... } // source impl
60 /// Suppose we have selected "source impl" with `V` instantiated with `u32`.
61 /// This function will produce a substitution with `T` and `U` both mapping to `u32`.
63 /// Where clauses add some trickiness here, because they can be used to "define"
64 /// an argument indirectly:
67 /// impl<'a, I, T: 'a> Iterator for Cloned<I>
68 /// where I: Iterator<Item=&'a T>, T: Clone
71 /// In a case like this, the substitution for `T` is determined indirectly,
72 /// through associated type projection. We deal with such cases by using
73 /// *fulfillment* to relate the two impls, requiring that all projections are
75 pub fn translate_substs<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>,
77 source_substs: &'tcx Substs<'tcx>,
78 target_node: specialization_graph::Node)
79 -> &'tcx Substs<'tcx> {
80 let source_trait_ref = infcx.tcx
81 .impl_trait_ref(source_impl)
83 .subst(infcx.tcx, &source_substs);
85 // translate the Self and TyParam parts of the substitution, since those
87 let target_substs = match target_node {
88 specialization_graph::Node::Impl(target_impl) => {
89 // no need to translate if we're targetting the impl we started with
90 if source_impl == target_impl {
94 fulfill_implication(infcx, source_trait_ref, target_impl).unwrap_or_else(|_| {
95 bug!("When translating substitutions for specialization, the expected \
96 specializaiton failed to hold")
99 specialization_graph::Node::Trait(..) => source_trait_ref.substs,
102 // directly inherent the method generics, since those do not vary across impls
103 source_substs.rebase_onto(infcx.tcx, source_impl, target_substs)
106 /// Given a selected impl described by `impl_data`, returns the
107 /// definition and substitions for the method with the name `name`
108 /// the kind `kind`, and trait method substitutions `substs`, in
109 /// that impl, a less specialized impl, or the trait default,
110 /// whichever applies.
111 pub fn find_associated_item<'a, 'tcx>(
112 tcx: TyCtxt<'a, 'tcx, 'tcx>,
113 item: &ty::AssociatedItem,
114 substs: &'tcx Substs<'tcx>,
115 impl_data: &super::VtableImplData<'tcx, ()>,
116 ) -> (DefId, &'tcx Substs<'tcx>) {
117 assert!(!substs.needs_infer());
119 let trait_def_id = tcx.trait_id_of_impl(impl_data.impl_def_id).unwrap();
120 let trait_def = tcx.trait_def(trait_def_id);
122 let ancestors = trait_def.ancestors(tcx, impl_data.impl_def_id);
123 match ancestors.defs(tcx, item.name, item.kind).next() {
125 let substs = tcx.infer_ctxt((), Reveal::All).enter(|infcx| {
126 let substs = substs.rebase_onto(tcx, trait_def_id, impl_data.substs);
127 let substs = translate_substs(&infcx, impl_data.impl_def_id,
128 substs, node_item.node);
129 let substs = infcx.tcx.erase_regions(&substs);
130 tcx.lift(&substs).unwrap_or_else(|| {
131 bug!("find_method: translate_substs \
132 returned {:?} which contains inference types/regions",
136 (node_item.item.def_id, substs)
139 bug!("{:?} not found in {:?}", item, impl_data.impl_def_id)
144 /// Is impl1 a specialization of impl2?
146 /// Specialization is determined by the sets of types to which the impls apply;
147 /// impl1 specializes impl2 if it applies to a subset of the types impl2 applies
149 pub fn specializes<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
151 impl2_def_id: DefId) -> bool {
152 debug!("specializes({:?}, {:?})", impl1_def_id, impl2_def_id);
154 if let Some(r) = tcx.specializes_cache.borrow().check(impl1_def_id, impl2_def_id) {
158 // The feature gate should prevent introducing new specializations, but not
159 // taking advantage of upstream ones.
160 if !tcx.sess.features.borrow().specialization &&
161 (impl1_def_id.is_local() || impl2_def_id.is_local()) {
165 // We determine whether there's a subset relationship by:
167 // - skolemizing impl1,
168 // - assuming the where clauses for impl1,
169 // - instantiating impl2 with fresh inference variables,
171 // - attempting to prove the where clauses for impl2
173 // The last three steps are encapsulated in `fulfill_implication`.
175 // See RFC 1210 for more details and justification.
177 // Currently we do not allow e.g. a negative impl to specialize a positive one
178 if tcx.impl_polarity(impl1_def_id) != tcx.impl_polarity(impl2_def_id) {
182 // create a parameter environment corresponding to a (skolemized) instantiation of impl1
183 let penv = tcx.param_env(impl1_def_id);
184 let impl1_trait_ref = tcx.impl_trait_ref(impl1_def_id).unwrap();
186 // Create a infcx, taking the predicates of impl1 as assumptions:
187 let result = tcx.infer_ctxt(penv, Reveal::UserFacing).enter(|infcx| {
188 // Normalize the trait reference. The WF rules ought to ensure
189 // that this always succeeds.
190 let impl1_trait_ref =
191 match traits::fully_normalize(&infcx, ObligationCause::dummy(), &impl1_trait_ref) {
192 Ok(impl1_trait_ref) => impl1_trait_ref,
194 bug!("failed to fully normalize {:?}: {:?}", impl1_trait_ref, err);
198 // Attempt to prove that impl2 applies, given all of the above.
199 fulfill_implication(&infcx, impl1_trait_ref, impl2_def_id).is_ok()
202 tcx.specializes_cache.borrow_mut().insert(impl1_def_id, impl2_def_id, result);
206 /// Attempt to fulfill all obligations of `target_impl` after unification with
207 /// `source_trait_ref`. If successful, returns a substitution for *all* the
208 /// generics of `target_impl`, including both those needed to unify with
209 /// `source_trait_ref` and those whose identity is determined via a where
210 /// clause in the impl.
211 fn fulfill_implication<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>,
212 source_trait_ref: ty::TraitRef<'tcx>,
214 -> Result<&'tcx Substs<'tcx>, ()> {
215 let selcx = &mut SelectionContext::new(&infcx);
216 let target_substs = infcx.fresh_substs_for_item(DUMMY_SP, target_impl);
217 let (target_trait_ref, mut obligations) = impl_trait_ref_and_oblig(selcx,
221 // do the impls unify? If not, no specialization.
222 match infcx.eq_trait_refs(true,
223 &ObligationCause::dummy(),
226 Ok(InferOk { obligations: o, .. }) => {
227 obligations.extend(o);
230 debug!("fulfill_implication: {:?} does not unify with {:?}",
237 // attempt to prove all of the predicates for impl2 given those for impl1
238 // (which are packed up in penv)
240 infcx.save_and_restore_in_snapshot_flag(|infcx| {
241 let mut fulfill_cx = FulfillmentContext::new();
242 for oblig in obligations.into_iter() {
243 fulfill_cx.register_predicate_obligation(&infcx, oblig);
245 match fulfill_cx.select_all_or_error(infcx) {
248 debug!("fulfill_implication: for impls on {:?} and {:?}, \
249 could not fulfill: {:?} given {:?}",
253 infcx.param_env.caller_bounds);
258 debug!("fulfill_implication: an impl for {:?} specializes {:?}",
262 // Now resolve the *substitution* we built for the target earlier, replacing
263 // the inference variables inside with whatever we got from fulfillment.
264 Ok(infcx.resolve_type_vars_if_possible(&target_substs))
270 pub struct SpecializesCache {
271 map: FxHashMap<(DefId, DefId), bool>,
274 impl SpecializesCache {
275 pub fn new() -> Self {
281 pub fn check(&self, a: DefId, b: DefId) -> Option<bool> {
282 self.map.get(&(a, b)).cloned()
285 pub fn insert(&mut self, a: DefId, b: DefId, result: bool) {
286 self.map.insert((a, b), result);
290 // Query provider for `specialization_graph_of`.
291 pub(super) fn specialization_graph_provider<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
293 -> Rc<specialization_graph::Graph> {
294 let mut sg = specialization_graph::Graph::new();
296 let mut trait_impls: Vec<DefId> = tcx.trait_impls_of(trait_id).iter().collect();
298 // The coherence checking implementation seems to rely on impls being
299 // iterated over (roughly) in definition order, so we are sorting by
300 // negated CrateNum (so remote definitions are visited first) and then
301 // by a flattend version of the DefIndex.
302 trait_impls.sort_unstable_by_key(|def_id| {
303 (-(def_id.krate.as_u32() as i64),
304 def_id.index.address_space().index(),
305 def_id.index.as_array_index())
308 for impl_def_id in trait_impls {
309 if impl_def_id.is_local() {
310 // This is where impl overlap checking happens:
311 let insert_result = sg.insert(tcx, impl_def_id);
312 // Report error if there was one.
313 if let Err(overlap) = insert_result {
314 let mut err = struct_span_err!(tcx.sess,
315 tcx.span_of_impl(impl_def_id).unwrap(),
317 "conflicting implementations of trait `{}`{}:",
319 overlap.self_desc.clone().map_or(String::new(),
321 format!(" for type `{}`", ty)
324 match tcx.span_of_impl(overlap.with_impl) {
326 err.span_label(span, format!("first implementation here"));
327 err.span_label(tcx.span_of_impl(impl_def_id).unwrap(),
328 format!("conflicting implementation{}",
330 .map_or(String::new(),
331 |ty| format!(" for `{}`", ty))));
334 err.note(&format!("conflicting implementation in crate `{}`", cname));
341 let parent = tcx.impl_parent(impl_def_id).unwrap_or(trait_id);
342 sg.record_impl_from_cstore(tcx, parent, impl_def_id)