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 dev guide] for a bit more detail on how specialization
8 //! fits together with the rest of the trait machinery.
10 //! [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/traits/specialization.html
12 pub mod specialization_graph;
13 use specialization_graph::GraphExt;
15 use crate::infer::{InferCtxt, InferOk, TyCtxtInferExt};
16 use crate::traits::select::IntercrateAmbiguityCause;
17 use crate::traits::{self, coherence, FutureCompatOverlapErrorKind, ObligationCause, TraitEngine};
18 use rustc_data_structures::fx::FxHashSet;
19 use rustc_errors::struct_span_err;
20 use rustc_hir::def_id::{DefId, LocalDefId};
21 use rustc_middle::lint::LintDiagnosticBuilder;
22 use rustc_middle::ty::subst::{InternalSubsts, Subst, SubstsRef};
23 use rustc_middle::ty::{self, TyCtxt};
24 use rustc_session::lint::builtin::COHERENCE_LEAK_CHECK;
25 use rustc_session::lint::builtin::ORDER_DEPENDENT_TRAIT_OBJECTS;
26 use rustc_span::DUMMY_SP;
28 use super::util::impl_trait_ref_and_oblig;
29 use super::{FulfillmentContext, SelectionContext};
31 /// Information pertinent to an overlapping impl error.
33 pub struct OverlapError {
35 pub trait_desc: String,
36 pub self_desc: Option<String>,
37 pub intercrate_ambiguity_causes: Vec<IntercrateAmbiguityCause>,
38 pub involves_placeholder: bool,
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).
45 /// When we have selected one impl, but are actually using item definitions from
46 /// a parent impl providing a default, we need a way to translate between the
47 /// type parameters of the two impls. Here the `source_impl` is the one we've
48 /// selected, and `source_substs` is a substitution of its generics.
49 /// And `target_node` is the impl/trait we're actually going to get the
50 /// definition from. The resulting substitution will map from `target_node`'s
51 /// generics to `source_impl`'s 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>(
77 infcx: &InferCtxt<'a, 'tcx>,
78 param_env: ty::ParamEnv<'tcx>,
80 source_substs: SubstsRef<'tcx>,
81 target_node: specialization_graph::Node,
82 ) -> SubstsRef<'tcx> {
84 "translate_substs({:?}, {:?}, {:?}, {:?})",
85 param_env, source_impl, source_substs, target_node
87 let source_trait_ref =
88 infcx.tcx.impl_trait_ref(source_impl).unwrap().subst(infcx.tcx, &source_substs);
90 // translate the Self and Param parts of the substitution, since those
92 let target_substs = match target_node {
93 specialization_graph::Node::Impl(target_impl) => {
94 // no need to translate if we're targeting the impl we started with
95 if source_impl == target_impl {
99 fulfill_implication(infcx, param_env, source_trait_ref, target_impl).unwrap_or_else(
102 "When translating substitutions for specialization, the expected \
103 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 /// Is `impl1` a specialization of `impl2`?
117 /// Specialization is determined by the sets of types to which the impls apply;
118 /// `impl1` specializes `impl2` if it applies to a subset of the types `impl2` applies
120 pub(super) fn specializes(tcx: TyCtxt<'_>, (impl1_def_id, impl2_def_id): (DefId, DefId)) -> bool {
121 debug!("specializes({:?}, {:?})", impl1_def_id, impl2_def_id);
123 // The feature gate should prevent introducing new specializations, but not
124 // taking advantage of upstream ones.
125 let features = tcx.features();
126 let specialization_enabled = features.specialization || features.min_specialization;
127 if !specialization_enabled && (impl1_def_id.is_local() || impl2_def_id.is_local()) {
131 // We determine whether there's a subset relationship by:
133 // - replacing bound vars with placeholders in impl1,
134 // - assuming the where clauses for impl1,
135 // - instantiating impl2 with fresh inference variables,
137 // - attempting to prove the where clauses for impl2
139 // The last three steps are encapsulated in `fulfill_implication`.
141 // See RFC 1210 for more details and justification.
143 // Currently we do not allow e.g., a negative impl to specialize a positive one
144 if tcx.impl_polarity(impl1_def_id) != tcx.impl_polarity(impl2_def_id) {
148 // create a parameter environment corresponding to a (placeholder) instantiation of impl1
149 let penv = tcx.param_env(impl1_def_id);
150 let impl1_trait_ref = tcx.impl_trait_ref(impl1_def_id).unwrap();
152 // Create an infcx, taking the predicates of impl1 as assumptions:
153 tcx.infer_ctxt().enter(|infcx| {
154 // Normalize the trait reference. The WF rules ought to ensure
155 // that this always succeeds.
156 let impl1_trait_ref = match traits::fully_normalize(
158 FulfillmentContext::new(),
159 ObligationCause::dummy(),
163 Ok(impl1_trait_ref) => impl1_trait_ref,
165 bug!("failed to fully normalize {:?}: {:?}", impl1_trait_ref, err);
169 // Attempt to prove that impl2 applies, given all of the above.
170 fulfill_implication(&infcx, penv, 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>(
180 infcx: &InferCtxt<'a, 'tcx>,
181 param_env: ty::ParamEnv<'tcx>,
182 source_trait_ref: ty::TraitRef<'tcx>,
184 ) -> Result<SubstsRef<'tcx>, ()> {
186 "fulfill_implication({:?}, trait_ref={:?} |- {:?} applies)",
187 param_env, source_trait_ref, target_impl
190 let selcx = &mut SelectionContext::new(&infcx);
191 let target_substs = infcx.fresh_substs_for_item(DUMMY_SP, target_impl);
192 let (target_trait_ref, obligations) =
193 impl_trait_ref_and_oblig(selcx, param_env, target_impl, target_substs);
195 // do the impls unify? If not, no specialization.
196 let more_obligations =
197 match infcx.at(&ObligationCause::dummy(), param_env).eq(source_trait_ref, target_trait_ref)
199 Ok(InferOk { obligations, .. }) => obligations,
202 "fulfill_implication: {:?} does not unify with {:?}",
203 source_trait_ref, target_trait_ref
209 // attempt to prove all of the predicates for impl2 given those for impl1
210 // (which are packed up in penv)
212 infcx.save_and_restore_in_snapshot_flag(|infcx| {
213 // If we came from `translate_substs`, we already know that the
214 // predicates for our impl hold (after all, we know that a more
215 // specialized impl holds, so our impl must hold too), and
216 // we only want to process the projections to determine the
217 // the types in our substs using RFC 447, so we can safely
218 // ignore region obligations, which allows us to avoid threading
219 // a node-id to assign them with.
221 // If we came from specialization graph construction, then
222 // we already make a mockery out of the region system, so
223 // why not ignore them a bit earlier?
224 let mut fulfill_cx = FulfillmentContext::new_ignoring_regions();
225 for oblig in obligations.chain(more_obligations) {
226 fulfill_cx.register_predicate_obligation(&infcx, oblig);
228 match fulfill_cx.select_all_or_error(infcx) {
232 "fulfill_implication: for impls on {:?} and {:?}, \
233 could not fulfill: {:?} given {:?}",
237 param_env.caller_bounds()
244 "fulfill_implication: an impl for {:?} specializes {:?}",
245 source_trait_ref, target_trait_ref
248 // Now resolve the *substitution* we built for the target earlier, replacing
249 // the inference variables inside with whatever we got from fulfillment.
250 Ok(infcx.resolve_vars_if_possible(target_substs))
256 // Query provider for `specialization_graph_of`.
257 pub(super) fn specialization_graph_provider(
260 ) -> specialization_graph::Graph {
261 let mut sg = specialization_graph::Graph::new();
263 let mut trait_impls: Vec<_> = tcx.all_impls(trait_id).collect();
265 // The coherence checking implementation seems to rely on impls being
266 // iterated over (roughly) in definition order, so we are sorting by
267 // negated `CrateNum` (so remote definitions are visited first) and then
268 // by a flattened version of the `DefIndex`.
270 .sort_unstable_by_key(|def_id| (-(def_id.krate.as_u32() as i64), def_id.index.index()));
272 for impl_def_id in trait_impls {
273 if let Some(impl_def_id) = impl_def_id.as_local() {
274 // This is where impl overlap checking happens:
275 let insert_result = sg.insert(tcx, impl_def_id.to_def_id());
276 // Report error if there was one.
277 let (overlap, used_to_be_allowed) = match insert_result {
278 Err(overlap) => (Some(overlap), None),
279 Ok(Some(overlap)) => (Some(overlap.error), Some(overlap.kind)),
280 Ok(None) => (None, None),
283 if let Some(overlap) = overlap {
284 report_overlap_conflict(tcx, overlap, impl_def_id, used_to_be_allowed, &mut sg);
287 let parent = tcx.impl_parent(impl_def_id).unwrap_or(trait_id);
288 sg.record_impl_from_cstore(tcx, parent, impl_def_id)
295 fn report_overlap_conflict(
297 overlap: OverlapError,
298 impl_def_id: LocalDefId,
299 used_to_be_allowed: Option<FutureCompatOverlapErrorKind>,
300 sg: &mut specialization_graph::Graph,
302 let impl_polarity = tcx.impl_polarity(impl_def_id.to_def_id());
303 let other_polarity = tcx.impl_polarity(overlap.with_impl);
304 match (impl_polarity, other_polarity) {
305 (ty::ImplPolarity::Negative, ty::ImplPolarity::Positive) => {
306 report_negative_positive_conflict(
310 impl_def_id.to_def_id(),
316 (ty::ImplPolarity::Positive, ty::ImplPolarity::Negative) => {
317 report_negative_positive_conflict(
322 impl_def_id.to_def_id(),
328 report_conflicting_impls(tcx, overlap, impl_def_id, used_to_be_allowed, sg);
333 fn report_negative_positive_conflict(
335 overlap: &OverlapError,
336 local_impl_def_id: LocalDefId,
337 negative_impl_def_id: DefId,
338 positive_impl_def_id: DefId,
339 sg: &mut specialization_graph::Graph,
344 .guess_head_span(tcx.span_of_impl(local_impl_def_id.to_def_id()).unwrap());
346 let mut err = struct_span_err!(
350 "found both positive and negative implementation of trait `{}`{}:",
352 overlap.self_desc.clone().map_or_else(String::new, |ty| format!(" for type `{}`", ty))
355 match tcx.span_of_impl(negative_impl_def_id) {
358 tcx.sess.source_map().guess_head_span(span),
359 "negative implementation here".to_string(),
363 err.note(&format!("negative implementation in crate `{}`", cname));
367 match tcx.span_of_impl(positive_impl_def_id) {
370 tcx.sess.source_map().guess_head_span(span),
371 "positive implementation here".to_string(),
375 err.note(&format!("positive implementation in crate `{}`", cname));
379 sg.has_errored = true;
383 fn report_conflicting_impls(
385 overlap: OverlapError,
386 impl_def_id: LocalDefId,
387 used_to_be_allowed: Option<FutureCompatOverlapErrorKind>,
388 sg: &mut specialization_graph::Graph,
391 tcx.sess.source_map().guess_head_span(tcx.span_of_impl(impl_def_id.to_def_id()).unwrap());
393 // Work to be done after we've built the DiagnosticBuilder. We have to define it
394 // now because the struct_lint methods don't return back the DiagnosticBuilder
396 let decorate = |err: LintDiagnosticBuilder<'_>| {
398 "conflicting implementations of trait `{}`{}{}",
403 .map_or_else(String::new, |ty| { format!(" for type `{}`", ty) }),
404 match used_to_be_allowed {
405 Some(FutureCompatOverlapErrorKind::Issue33140) => ": (E0119)",
409 let mut err = err.build(&msg);
410 match tcx.span_of_impl(overlap.with_impl) {
413 tcx.sess.source_map().guess_head_span(span),
414 "first implementation here".to_string(),
420 "conflicting implementation{}",
421 overlap.self_desc.map_or_else(String::new, |ty| format!(" for `{}`", ty))
426 let msg = match to_pretty_impl_header(tcx, overlap.with_impl) {
427 Some(s) => format!("conflicting implementation in crate `{}`:\n- {}", cname, s),
428 None => format!("conflicting implementation in crate `{}`", cname),
434 for cause in &overlap.intercrate_ambiguity_causes {
435 cause.add_intercrate_ambiguity_hint(&mut err);
438 if overlap.involves_placeholder {
439 coherence::add_placeholder_note(&mut err);
444 match used_to_be_allowed {
446 sg.has_errored = true;
447 let err = struct_span_err!(tcx.sess, impl_span, E0119, "");
448 decorate(LintDiagnosticBuilder::new(err));
451 let lint = match kind {
452 FutureCompatOverlapErrorKind::Issue33140 => ORDER_DEPENDENT_TRAIT_OBJECTS,
453 FutureCompatOverlapErrorKind::LeakCheck => COHERENCE_LEAK_CHECK,
455 tcx.struct_span_lint_hir(
457 tcx.hir().local_def_id_to_hir_id(impl_def_id),
465 /// Recovers the "impl X for Y" signature from `impl_def_id` and returns it as a
467 crate fn to_pretty_impl_header(tcx: TyCtxt<'_>, impl_def_id: DefId) -> Option<String> {
470 let trait_ref = tcx.impl_trait_ref(impl_def_id)?;
471 let mut w = "impl".to_owned();
473 let substs = InternalSubsts::identity_for_item(tcx, impl_def_id);
475 // FIXME: Currently only handles ?Sized.
476 // Needs to support ?Move and ?DynSized when they are implemented.
477 let mut types_without_default_bounds = FxHashSet::default();
478 let sized_trait = tcx.lang_items().sized_trait();
480 if !substs.is_noop() {
481 types_without_default_bounds.extend(substs.types());
486 .map(|k| k.to_string())
487 .filter(|k| k != "'_")
494 write!(w, " {} for {}", trait_ref.print_only_trait_path(), tcx.type_of(impl_def_id)).unwrap();
496 // The predicates will contain default bounds like `T: Sized`. We need to
497 // remove these bounds, and add `T: ?Sized` to any untouched type parameters.
498 let predicates = tcx.predicates_of(impl_def_id).predicates;
499 let mut pretty_predicates =
500 Vec::with_capacity(predicates.len() + types_without_default_bounds.len());
502 for (p, _) in predicates {
503 if let Some(poly_trait_ref) = p.to_opt_poly_trait_ref() {
504 if Some(poly_trait_ref.value.def_id()) == sized_trait {
505 types_without_default_bounds.remove(poly_trait_ref.value.self_ty().skip_binder());
509 pretty_predicates.push(p.to_string());
513 .extend(types_without_default_bounds.iter().map(|ty| format!("{}: ?Sized", ty)));
515 if !pretty_predicates.is_empty() {
516 write!(w, "\n where {}", pretty_predicates.join(", ")).unwrap();