1 //! Logic and data structures related to impl specialization, explained in
2 //! greater detail below.
4 //! At the moment, this implementation support only the simple "chain" rule:
5 //! If any two impls overlap, one must be a strict subset of the other.
7 //! See the [rustc guide] for a bit more detail on how specialization
8 //! fits together with the rest of the trait machinery.
10 //! [rustc guide]: https://rust-lang.github.io/rustc-guide/traits/specialization.html
12 pub mod specialization_graph;
14 use crate::hir::def_id::DefId;
15 use crate::infer::{InferCtxt, InferOk};
17 use crate::traits::{self, coherence, FutureCompatOverlapErrorKind, ObligationCause, TraitEngine};
18 use rustc_data_structures::fx::FxHashSet;
19 use syntax_pos::DUMMY_SP;
20 use crate::traits::select::IntercrateAmbiguityCause;
21 use crate::ty::{self, TyCtxt, TypeFoldable};
22 use crate::ty::subst::{Subst, InternalSubsts, SubstsRef};
24 use super::{SelectionContext, FulfillmentContext};
25 use super::util::impl_trait_ref_and_oblig;
27 use rustc_error_codes::*;
29 /// Information pertinent to an overlapping impl error.
31 pub struct OverlapError {
33 pub trait_desc: String,
34 pub self_desc: Option<String>,
35 pub intercrate_ambiguity_causes: Vec<IntercrateAmbiguityCause>,
36 pub involves_placeholder: bool,
39 /// Given a subst for the requested impl, translate it to a subst
40 /// appropriate for the actual item definition (whether it be in that impl,
41 /// a parent impl, or the trait).
43 /// When we have selected one impl, but are actually using item definitions from
44 /// a parent impl providing a default, we need a way to translate between the
45 /// type parameters of the two impls. Here the `source_impl` is the one we've
46 /// selected, and `source_substs` is a substitution of its generics.
47 /// And `target_node` is the impl/trait we're actually going to get the
48 /// definition from. The resulting substitution will map from `target_node`'s
49 /// generics to `source_impl`'s generics as instantiated by `source_subst`.
51 /// For example, consider the following scenario:
55 /// impl<T, U> Foo for (T, U) { ... } // target impl
56 /// impl<V> Foo for (V, V) { ... } // source impl
59 /// Suppose we have selected "source impl" with `V` instantiated with `u32`.
60 /// This function will produce a substitution with `T` and `U` both mapping to `u32`.
62 /// where-clauses add some trickiness here, because they can be used to "define"
63 /// an argument indirectly:
66 /// impl<'a, I, T: 'a> Iterator for Cloned<I>
67 /// where I: Iterator<Item = &'a T>, T: Clone
70 /// In a case like this, the substitution for `T` is determined indirectly,
71 /// through associated type projection. We deal with such cases by using
72 /// *fulfillment* to relate the two impls, requiring that all projections are
74 pub fn translate_substs<'a, 'tcx>(
75 infcx: &InferCtxt<'a, 'tcx>,
76 param_env: ty::ParamEnv<'tcx>,
78 source_substs: SubstsRef<'tcx>,
79 target_node: specialization_graph::Node,
80 ) -> SubstsRef<'tcx> {
81 debug!("translate_substs({:?}, {:?}, {:?}, {:?})",
82 param_env, source_impl, source_substs, target_node);
83 let source_trait_ref = infcx.tcx
84 .impl_trait_ref(source_impl)
86 .subst(infcx.tcx, &source_substs);
88 // translate the Self and Param parts of the substitution, since those
90 let target_substs = match target_node {
91 specialization_graph::Node::Impl(target_impl) => {
92 // no need to translate if we're targeting the impl we started with
93 if source_impl == target_impl {
97 fulfill_implication(infcx, param_env, source_trait_ref, target_impl)
99 bug!("When translating substitutions for specialization, the expected \
100 specialization failed to hold")
103 specialization_graph::Node::Trait(..) => source_trait_ref.substs,
106 // directly inherent the method generics, since those do not vary across impls
107 source_substs.rebase_onto(infcx.tcx, source_impl, target_substs)
110 /// Given a selected impl described by `impl_data`, returns the
111 /// definition and substitutions for the method with the name `name`
112 /// the kind `kind`, and trait method substitutions `substs`, in
113 /// that impl, a less specialized impl, or the trait default,
114 /// whichever applies.
115 pub fn find_associated_item<'tcx>(
117 param_env: ty::ParamEnv<'tcx>,
118 item: &ty::AssocItem,
119 substs: SubstsRef<'tcx>,
120 impl_data: &super::VtableImplData<'tcx, ()>,
121 ) -> (DefId, SubstsRef<'tcx>) {
122 debug!("find_associated_item({:?}, {:?}, {:?}, {:?})",
123 param_env, item, substs, impl_data);
124 assert!(!substs.needs_infer());
126 let trait_def_id = tcx.trait_id_of_impl(impl_data.impl_def_id).unwrap();
127 let trait_def = tcx.trait_def(trait_def_id);
129 let ancestors = trait_def.ancestors(tcx, impl_data.impl_def_id);
130 match ancestors.leaf_def(tcx, item.ident, item.kind) {
132 let substs = tcx.infer_ctxt().enter(|infcx| {
133 let param_env = param_env.with_reveal_all();
134 let substs = substs.rebase_onto(tcx, trait_def_id, impl_data.substs);
135 let substs = translate_substs(&infcx, param_env, impl_data.impl_def_id,
136 substs, node_item.node);
137 infcx.tcx.erase_regions(&substs)
139 (node_item.item.def_id, substs)
141 None => bug!("{:?} not found in {:?}", item, impl_data.impl_def_id)
145 /// Is `impl1` a specialization of `impl2`?
147 /// Specialization is determined by the sets of types to which the impls apply;
148 /// `impl1` specializes `impl2` if it applies to a subset of the types `impl2` applies
150 pub(super) fn specializes(
152 (impl1_def_id, impl2_def_id): (DefId, DefId),
154 debug!("specializes({:?}, {:?})", impl1_def_id, impl2_def_id);
156 // The feature gate should prevent introducing new specializations, but not
157 // taking advantage of upstream ones.
158 if !tcx.features().specialization &&
159 (impl1_def_id.is_local() || impl2_def_id.is_local()) {
163 // We determine whether there's a subset relationship by:
165 // - skolemizing impl1,
166 // - assuming the where clauses for impl1,
167 // - instantiating impl2 with fresh inference variables,
169 // - attempting to prove the where clauses for impl2
171 // The last three steps are encapsulated in `fulfill_implication`.
173 // See RFC 1210 for more details and justification.
175 // Currently we do not allow e.g., a negative impl to specialize a positive one
176 if tcx.impl_polarity(impl1_def_id) != tcx.impl_polarity(impl2_def_id) {
180 // create a parameter environment corresponding to a (placeholder) instantiation of impl1
181 let penv = tcx.param_env(impl1_def_id);
182 let impl1_trait_ref = tcx.impl_trait_ref(impl1_def_id).unwrap();
184 // Create a infcx, taking the predicates of impl1 as assumptions:
185 tcx.infer_ctxt().enter(|infcx| {
186 // Normalize the trait reference. The WF rules ought to ensure
187 // that this always succeeds.
188 let impl1_trait_ref =
189 match traits::fully_normalize(&infcx,
190 FulfillmentContext::new(),
191 ObligationCause::dummy(),
194 Ok(impl1_trait_ref) => impl1_trait_ref,
196 bug!("failed to fully normalize {:?}: {:?}", impl1_trait_ref, err);
200 // Attempt to prove that impl2 applies, given all of the above.
201 fulfill_implication(&infcx, penv, impl1_trait_ref, impl2_def_id).is_ok()
205 /// Attempt to fulfill all obligations of `target_impl` after unification with
206 /// `source_trait_ref`. If successful, returns a substitution for *all* the
207 /// generics of `target_impl`, including both those needed to unify with
208 /// `source_trait_ref` and those whose identity is determined via a where
209 /// clause in the impl.
210 fn fulfill_implication<'a, 'tcx>(
211 infcx: &InferCtxt<'a, 'tcx>,
212 param_env: ty::ParamEnv<'tcx>,
213 source_trait_ref: ty::TraitRef<'tcx>,
215 ) -> Result<SubstsRef<'tcx>, ()> {
216 debug!("fulfill_implication({:?}, trait_ref={:?} |- {:?} applies)",
217 param_env, source_trait_ref, target_impl);
219 let selcx = &mut SelectionContext::new(&infcx);
220 let target_substs = infcx.fresh_substs_for_item(DUMMY_SP, target_impl);
221 let (target_trait_ref, mut obligations) = impl_trait_ref_and_oblig(selcx,
225 debug!("fulfill_implication: target_trait_ref={:?}, obligations={:?}",
226 target_trait_ref, obligations);
228 // do the impls unify? If not, no specialization.
229 match infcx.at(&ObligationCause::dummy(), param_env)
230 .eq(source_trait_ref, target_trait_ref) {
231 Ok(InferOk { obligations: o, .. }) => {
232 obligations.extend(o);
235 debug!("fulfill_implication: {:?} does not unify with {:?}",
242 // attempt to prove all of the predicates for impl2 given those for impl1
243 // (which are packed up in penv)
245 infcx.save_and_restore_in_snapshot_flag(|infcx| {
246 // If we came from `translate_substs`, we already know that the
247 // predicates for our impl hold (after all, we know that a more
248 // specialized impl holds, so our impl must hold too), and
249 // we only want to process the projections to determine the
250 // the types in our substs using RFC 447, so we can safely
251 // ignore region obligations, which allows us to avoid threading
252 // a node-id to assign them with.
254 // If we came from specialization graph construction, then
255 // we already make a mockery out of the region system, so
256 // why not ignore them a bit earlier?
257 let mut fulfill_cx = FulfillmentContext::new_ignoring_regions();
258 for oblig in obligations.into_iter() {
259 fulfill_cx.register_predicate_obligation(&infcx, oblig);
261 match fulfill_cx.select_all_or_error(infcx) {
264 debug!("fulfill_implication: for impls on {:?} and {:?}, \
265 could not fulfill: {:?} given {:?}",
269 param_env.caller_bounds);
274 debug!("fulfill_implication: an impl for {:?} specializes {:?}",
278 // Now resolve the *substitution* we built for the target earlier, replacing
279 // the inference variables inside with whatever we got from fulfillment.
280 Ok(infcx.resolve_vars_if_possible(&target_substs))
286 // Query provider for `specialization_graph_of`.
287 pub(super) fn specialization_graph_provider(
290 ) -> &specialization_graph::Graph {
291 let mut sg = specialization_graph::Graph::new();
293 let mut trait_impls = tcx.all_impls(trait_id);
295 // The coherence checking implementation seems to rely on impls being
296 // iterated over (roughly) in definition order, so we are sorting by
297 // negated `CrateNum` (so remote definitions are visited first) and then
298 // by a flattened version of the `DefIndex`.
299 trait_impls.sort_unstable_by_key(|def_id| {
300 (-(def_id.krate.as_u32() as i64), def_id.index.index())
303 for impl_def_id in trait_impls {
304 if impl_def_id.is_local() {
305 // This is where impl overlap checking happens:
306 let insert_result = sg.insert(tcx, impl_def_id);
307 // Report error if there was one.
308 let (overlap, used_to_be_allowed) = match insert_result {
309 Err(overlap) => (Some(overlap), None),
310 Ok(Some(overlap)) => (Some(overlap.error), Some(overlap.kind)),
311 Ok(None) => (None, None)
314 if let Some(overlap) = overlap {
315 let msg = format!("conflicting implementations of trait `{}`{}:{}",
317 overlap.self_desc.clone().map_or(
318 String::new(), |ty| {
319 format!(" for type `{}`", ty)
321 match used_to_be_allowed {
322 Some(FutureCompatOverlapErrorKind::Issue33140) => " (E0119)",
326 let impl_span = tcx.sess.source_map().def_span(
327 tcx.span_of_impl(impl_def_id).unwrap()
329 let mut err = match used_to_be_allowed {
330 Some(FutureCompatOverlapErrorKind::Issue43355) | None =>
331 struct_span_err!(tcx.sess,
337 let lint = match kind {
338 FutureCompatOverlapErrorKind::Issue43355 =>
339 unreachable!("converted to hard error above"),
340 FutureCompatOverlapErrorKind::Issue33140 =>
341 lint::builtin::ORDER_DEPENDENT_TRAIT_OBJECTS,
343 tcx.struct_span_lint_hir(
345 tcx.hir().as_local_hir_id(impl_def_id).unwrap(),
351 match tcx.span_of_impl(overlap.with_impl) {
353 err.span_label(tcx.sess.source_map().def_span(span),
354 "first implementation here".to_string());
355 err.span_label(impl_span,
356 format!("conflicting implementation{}",
358 .map_or(String::new(),
359 |ty| format!(" for `{}`", ty))));
362 let msg = match to_pretty_impl_header(tcx, overlap.with_impl) {
364 "conflicting implementation in crate `{}`:\n- {}", cname, s),
365 None => format!("conflicting implementation in crate `{}`", cname),
371 for cause in &overlap.intercrate_ambiguity_causes {
372 cause.add_intercrate_ambiguity_hint(&mut err);
375 if overlap.involves_placeholder {
376 coherence::add_placeholder_note(&mut err);
382 let parent = tcx.impl_parent(impl_def_id).unwrap_or(trait_id);
383 sg.record_impl_from_cstore(tcx, parent, impl_def_id)
390 /// Recovers the "impl X for Y" signature from `impl_def_id` and returns it as a
392 fn to_pretty_impl_header(tcx: TyCtxt<'_>, impl_def_id: DefId) -> Option<String> {
395 let trait_ref = if let Some(tr) = tcx.impl_trait_ref(impl_def_id) {
401 let mut w = "impl".to_owned();
403 let substs = InternalSubsts::identity_for_item(tcx, impl_def_id);
405 // FIXME: Currently only handles ?Sized.
406 // Needs to support ?Move and ?DynSized when they are implemented.
407 let mut types_without_default_bounds = FxHashSet::default();
408 let sized_trait = tcx.lang_items().sized_trait();
410 if !substs.is_noop() {
411 types_without_default_bounds.extend(substs.types());
413 w.push_str(&substs.iter()
414 .map(|k| k.to_string())
415 .filter(|k| k != "'_")
416 .collect::<Vec<_>>().join(", "));
420 write!(w, " {} for {}", trait_ref.print_only_trait_path(), tcx.type_of(impl_def_id)).unwrap();
422 // The predicates will contain default bounds like `T: Sized`. We need to
423 // remove these bounds, and add `T: ?Sized` to any untouched type parameters.
424 let predicates = tcx.predicates_of(impl_def_id).predicates;
425 let mut pretty_predicates = Vec::with_capacity(
426 predicates.len() + types_without_default_bounds.len());
428 for (p, _) in predicates {
429 if let Some(poly_trait_ref) = p.to_opt_poly_trait_ref() {
430 if Some(poly_trait_ref.def_id()) == sized_trait {
431 types_without_default_bounds.remove(poly_trait_ref.self_ty());
435 pretty_predicates.push(p.to_string());
438 pretty_predicates.extend(
439 types_without_default_bounds.iter().map(|ty| format!("{}: ?Sized", ty))
442 if !pretty_predicates.is_empty() {
443 write!(w, "\n where {}", pretty_predicates.join(", ")).unwrap();