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 the [rustc guide] for a bit more detail on how specialization
18 //! fits together with the rest of the trait machinery.
20 //! [rustc guide]: https://rust-lang-nursery.github.io/rustc-guide/traits/specialization.html
22 use super::{SelectionContext, FulfillmentContext};
23 use super::util::impl_trait_ref_and_oblig;
25 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
26 use hir::def_id::DefId;
27 use infer::{InferCtxt, InferOk};
28 use ty::subst::{Subst, Substs};
29 use traits::{self, ObligationCause, TraitEngine};
30 use traits::select::IntercrateAmbiguityCause;
31 use ty::{self, TyCtxt, TypeFoldable};
32 use syntax_pos::DUMMY_SP;
33 use rustc_data_structures::sync::Lrc;
37 pub mod specialization_graph;
39 /// Information pertinent to an overlapping impl error.
40 pub struct OverlapError {
42 pub trait_desc: String,
43 pub self_desc: Option<String>,
44 pub intercrate_ambiguity_causes: Vec<IntercrateAmbiguityCause>,
47 /// Given a subst for the requested impl, translate it to a subst
48 /// appropriate for the actual item definition (whether it be in that impl,
49 /// a parent impl, or the trait).
51 /// When we have selected one impl, but are actually using item definitions from
52 /// a parent impl providing a default, we need a way to translate between the
53 /// type parameters of the two impls. Here the `source_impl` is the one we've
54 /// selected, and `source_substs` is a substitution of its generics.
55 /// And `target_node` is the impl/trait we're actually going to get the
56 /// definition from. The resulting substitution will map from `target_node`'s
57 /// generics to `source_impl`'s generics as instantiated by `source_subst`.
59 /// For example, consider the following scenario:
63 /// impl<T, U> Foo for (T, U) { ... } // target impl
64 /// impl<V> Foo for (V, V) { ... } // source impl
67 /// Suppose we have selected "source impl" with `V` instantiated with `u32`.
68 /// This function will produce a substitution with `T` and `U` both mapping to `u32`.
70 /// Where clauses add some trickiness here, because they can be used to "define"
71 /// an argument indirectly:
74 /// impl<'a, I, T: 'a> Iterator for Cloned<I>
75 /// where I: Iterator<Item=&'a T>, T: Clone
78 /// In a case like this, the substitution for `T` is determined indirectly,
79 /// through associated type projection. We deal with such cases by using
80 /// *fulfillment* to relate the two impls, requiring that all projections are
82 pub fn translate_substs<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>,
83 param_env: ty::ParamEnv<'tcx>,
85 source_substs: &'tcx Substs<'tcx>,
86 target_node: specialization_graph::Node)
87 -> &'tcx Substs<'tcx> {
88 let source_trait_ref = infcx.tcx
89 .impl_trait_ref(source_impl)
91 .subst(infcx.tcx, &source_substs);
93 // translate the Self and Param parts of the substitution, since those
95 let target_substs = match target_node {
96 specialization_graph::Node::Impl(target_impl) => {
97 // no need to translate if we're targeting the impl we started with
98 if source_impl == target_impl {
102 fulfill_implication(infcx, param_env, source_trait_ref, target_impl)
103 .unwrap_or_else(|_| {
104 bug!("When translating substitutions for specialization, the expected \
105 specialization failed to hold")
108 specialization_graph::Node::Trait(..) => source_trait_ref.substs,
111 // directly inherent the method generics, since those do not vary across impls
112 source_substs.rebase_onto(infcx.tcx, source_impl, target_substs)
115 /// Given a selected impl described by `impl_data`, returns the
116 /// definition and substitutions for the method with the name `name`
117 /// the kind `kind`, and trait method substitutions `substs`, in
118 /// that impl, a less specialized impl, or the trait default,
119 /// whichever applies.
120 pub fn find_associated_item<'a, 'tcx>(
121 tcx: TyCtxt<'a, 'tcx, 'tcx>,
122 item: &ty::AssociatedItem,
123 substs: &'tcx Substs<'tcx>,
124 impl_data: &super::VtableImplData<'tcx, ()>,
125 ) -> (DefId, &'tcx Substs<'tcx>) {
126 assert!(!substs.needs_infer());
128 let trait_def_id = tcx.trait_id_of_impl(impl_data.impl_def_id).unwrap();
129 let trait_def = tcx.trait_def(trait_def_id);
131 let ancestors = trait_def.ancestors(tcx, impl_data.impl_def_id);
132 match ancestors.defs(tcx, item.ident, item.kind, trait_def_id).next() {
134 let substs = tcx.infer_ctxt().enter(|infcx| {
135 let param_env = ty::ParamEnv::reveal_all();
136 let substs = substs.rebase_onto(tcx, trait_def_id, impl_data.substs);
137 let substs = translate_substs(&infcx, param_env, impl_data.impl_def_id,
138 substs, node_item.node);
139 let substs = infcx.tcx.erase_regions(&substs);
140 tcx.lift(&substs).unwrap_or_else(|| {
141 bug!("find_method: translate_substs \
142 returned {:?} which contains inference types/regions",
146 (node_item.item.def_id, substs)
149 bug!("{:?} not found in {:?}", item, impl_data.impl_def_id)
154 /// Is impl1 a specialization of impl2?
156 /// Specialization is determined by the sets of types to which the impls apply;
157 /// impl1 specializes impl2 if it applies to a subset of the types impl2 applies
159 pub(super) fn specializes<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
160 (impl1_def_id, impl2_def_id): (DefId, DefId))
163 debug!("specializes({:?}, {:?})", impl1_def_id, impl2_def_id);
165 // The feature gate should prevent introducing new specializations, but not
166 // taking advantage of upstream ones.
167 if !tcx.features().specialization &&
168 (impl1_def_id.is_local() || impl2_def_id.is_local()) {
172 // We determine whether there's a subset relationship by:
174 // - skolemizing impl1,
175 // - assuming the where clauses for impl1,
176 // - instantiating impl2 with fresh inference variables,
178 // - attempting to prove the where clauses for impl2
180 // The last three steps are encapsulated in `fulfill_implication`.
182 // See RFC 1210 for more details and justification.
184 // Currently we do not allow e.g. a negative impl to specialize a positive one
185 if tcx.impl_polarity(impl1_def_id) != tcx.impl_polarity(impl2_def_id) {
189 // create a parameter environment corresponding to a (skolemized) instantiation of impl1
190 let penv = tcx.param_env(impl1_def_id);
191 let impl1_trait_ref = tcx.impl_trait_ref(impl1_def_id).unwrap();
193 // Create a infcx, taking the predicates of impl1 as assumptions:
194 tcx.infer_ctxt().enter(|infcx| {
195 // Normalize the trait reference. The WF rules ought to ensure
196 // that this always succeeds.
197 let impl1_trait_ref =
198 match traits::fully_normalize(&infcx,
199 FulfillmentContext::new(),
200 ObligationCause::dummy(),
203 Ok(impl1_trait_ref) => impl1_trait_ref,
205 bug!("failed to fully normalize {:?}: {:?}", impl1_trait_ref, err);
209 // Attempt to prove that impl2 applies, given all of the above.
210 fulfill_implication(&infcx, penv, impl1_trait_ref, impl2_def_id).is_ok()
214 /// Attempt to fulfill all obligations of `target_impl` after unification with
215 /// `source_trait_ref`. If successful, returns a substitution for *all* the
216 /// generics of `target_impl`, including both those needed to unify with
217 /// `source_trait_ref` and those whose identity is determined via a where
218 /// clause in the impl.
219 fn fulfill_implication<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>,
220 param_env: ty::ParamEnv<'tcx>,
221 source_trait_ref: ty::TraitRef<'tcx>,
223 -> Result<&'tcx Substs<'tcx>, ()> {
224 let selcx = &mut SelectionContext::new(&infcx);
225 let target_substs = infcx.fresh_substs_for_item(DUMMY_SP, target_impl);
226 let (target_trait_ref, mut obligations) = impl_trait_ref_and_oblig(selcx,
231 // do the impls unify? If not, no specialization.
232 match infcx.at(&ObligationCause::dummy(), param_env)
233 .eq(source_trait_ref, target_trait_ref) {
234 Ok(InferOk { obligations: o, .. }) => {
235 obligations.extend(o);
238 debug!("fulfill_implication: {:?} does not unify with {:?}",
245 // attempt to prove all of the predicates for impl2 given those for impl1
246 // (which are packed up in penv)
248 infcx.save_and_restore_in_snapshot_flag(|infcx| {
249 // If we came from `translate_substs`, we already know that the
250 // predicates for our impl hold (after all, we know that a more
251 // specialized impl holds, so our impl must hold too), and
252 // we only want to process the projections to determine the
253 // the types in our substs using RFC 447, so we can safely
254 // ignore region obligations, which allows us to avoid threading
255 // a node-id to assign them with.
257 // If we came from specialization graph construction, then
258 // we already make a mockery out of the region system, so
259 // why not ignore them a bit earlier?
260 let mut fulfill_cx = FulfillmentContext::new_ignoring_regions();
261 for oblig in obligations.into_iter() {
262 fulfill_cx.register_predicate_obligation(&infcx, oblig);
264 match fulfill_cx.select_all_or_error(infcx) {
267 debug!("fulfill_implication: for impls on {:?} and {:?}, \
268 could not fulfill: {:?} given {:?}",
272 param_env.caller_bounds);
277 debug!("fulfill_implication: an impl for {:?} specializes {:?}",
281 // Now resolve the *substitution* we built for the target earlier, replacing
282 // the inference variables inside with whatever we got from fulfillment.
283 Ok(infcx.resolve_type_vars_if_possible(&target_substs))
289 pub struct SpecializesCache {
290 map: FxHashMap<(DefId, DefId), bool>,
293 impl SpecializesCache {
294 pub fn new() -> Self {
300 pub fn check(&self, a: DefId, b: DefId) -> Option<bool> {
301 self.map.get(&(a, b)).cloned()
304 pub fn insert(&mut self, a: DefId, b: DefId, result: bool) {
305 self.map.insert((a, b), result);
309 // Query provider for `specialization_graph_of`.
310 pub(super) fn specialization_graph_provider<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
312 -> Lrc<specialization_graph::Graph> {
313 let mut sg = specialization_graph::Graph::new();
315 let mut trait_impls = Vec::new();
316 tcx.for_each_impl(trait_id, |impl_did| trait_impls.push(impl_did));
318 // The coherence checking implementation seems to rely on impls being
319 // iterated over (roughly) in definition order, so we are sorting by
320 // negated CrateNum (so remote definitions are visited first) and then
321 // by a flattened version of the DefIndex.
322 trait_impls.sort_unstable_by_key(|def_id| {
323 (-(def_id.krate.as_u32() as i64),
324 def_id.index.address_space().index(),
325 def_id.index.as_array_index())
328 for impl_def_id in trait_impls {
329 if impl_def_id.is_local() {
330 // This is where impl overlap checking happens:
331 let insert_result = sg.insert(tcx, impl_def_id);
332 // Report error if there was one.
333 let (overlap, used_to_be_allowed) = match insert_result {
334 Err(overlap) => (Some(overlap), false),
335 Ok(opt_overlap) => (opt_overlap, true)
338 if let Some(overlap) = overlap {
339 let msg = format!("conflicting implementations of trait `{}`{}:{}",
341 overlap.self_desc.clone().map_or(
342 String::new(), |ty| {
343 format!(" for type `{}`", ty)
345 if used_to_be_allowed { " (E0119)" } else { "" }
347 let impl_span = tcx.sess.source_map().def_span(
348 tcx.span_of_impl(impl_def_id).unwrap()
350 let mut err = if used_to_be_allowed {
351 tcx.struct_span_lint_node(
352 lint::builtin::INCOHERENT_FUNDAMENTAL_IMPLS,
353 tcx.hir.as_local_node_id(impl_def_id).unwrap(),
357 struct_span_err!(tcx.sess,
364 match tcx.span_of_impl(overlap.with_impl) {
366 err.span_label(tcx.sess.source_map().def_span(span),
367 "first implementation here".to_string());
368 err.span_label(impl_span,
369 format!("conflicting implementation{}",
371 .map_or(String::new(),
372 |ty| format!(" for `{}`", ty))));
375 let msg = match to_pretty_impl_header(tcx, overlap.with_impl) {
377 "conflicting implementation in crate `{}`:\n- {}", cname, s),
378 None => format!("conflicting implementation in crate `{}`", cname),
384 for cause in &overlap.intercrate_ambiguity_causes {
385 cause.add_intercrate_ambiguity_hint(&mut err);
391 let parent = tcx.impl_parent(impl_def_id).unwrap_or(trait_id);
392 sg.record_impl_from_cstore(tcx, parent, impl_def_id)
399 /// Recovers the "impl X for Y" signature from `impl_def_id` and returns it as a
401 fn to_pretty_impl_header(tcx: TyCtxt, impl_def_id: DefId) -> Option<String> {
404 let trait_ref = if let Some(tr) = tcx.impl_trait_ref(impl_def_id) {
410 let mut w = "impl".to_owned();
412 let substs = Substs::identity_for_item(tcx, impl_def_id);
414 // FIXME: Currently only handles ?Sized.
415 // Needs to support ?Move and ?DynSized when they are implemented.
416 let mut types_without_default_bounds = FxHashSet::default();
417 let sized_trait = tcx.lang_items().sized_trait();
419 if !substs.is_noop() {
420 types_without_default_bounds.extend(substs.types());
422 w.push_str(&substs.iter().map(|k| k.to_string()).collect::<Vec<_>>().join(", "));
426 write!(w, " {} for {}", trait_ref, tcx.type_of(impl_def_id)).unwrap();
428 // The predicates will contain default bounds like `T: Sized`. We need to
429 // remove these bounds, and add `T: ?Sized` to any untouched type parameters.
430 let predicates = tcx.predicates_of(impl_def_id).predicates;
431 let mut pretty_predicates = Vec::with_capacity(predicates.len());
432 for p in predicates {
433 if let Some(poly_trait_ref) = p.to_opt_poly_trait_ref() {
434 if Some(poly_trait_ref.def_id()) == sized_trait {
435 types_without_default_bounds.remove(poly_trait_ref.self_ty());
439 pretty_predicates.push(p.to_string());
441 pretty_predicates.extend(
442 types_without_default_bounds.iter().map(|ty| format!("{}: ?Sized", ty))
444 if !pretty_predicates.is_empty() {
445 write!(w, "\n where {}", pretty_predicates.join(", ")).unwrap();