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 rustc_infer::traits::{TraitEngine, TraitEngineExt as _};
14 use specialization_graph::GraphExt;
16 use crate::errors::NegativePositiveConflict;
17 use crate::infer::{InferCtxt, InferOk, TyCtxtInferExt};
18 use crate::traits::engine::TraitEngineExt as _;
19 use crate::traits::select::IntercrateAmbiguityCause;
20 use crate::traits::{self, coherence, FutureCompatOverlapErrorKind, ObligationCause};
21 use rustc_data_structures::fx::FxIndexSet;
22 use rustc_errors::{struct_span_err, DiagnosticBuilder, EmissionGuarantee};
23 use rustc_hir::def_id::{DefId, LocalDefId};
24 use rustc_middle::ty::{self, ImplSubject, TyCtxt};
25 use rustc_middle::ty::{InternalSubsts, SubstsRef};
26 use rustc_session::lint::builtin::COHERENCE_LEAK_CHECK;
27 use rustc_session::lint::builtin::ORDER_DEPENDENT_TRAIT_OBJECTS;
28 use rustc_span::{Span, DUMMY_SP};
31 use super::SelectionContext;
33 /// Information pertinent to an overlapping impl error.
35 pub struct OverlapError {
37 pub trait_desc: String,
38 pub self_desc: Option<String>,
39 pub intercrate_ambiguity_causes: FxIndexSet<IntercrateAmbiguityCause>,
40 pub involves_placeholder: bool,
43 /// Given a subst for the requested impl, translate it to a subst
44 /// appropriate for the actual item definition (whether it be in that impl,
45 /// a parent impl, or the trait).
47 /// When we have selected one impl, but are actually using item definitions from
48 /// a parent impl providing a default, we need a way to translate between the
49 /// type parameters of the two impls. Here the `source_impl` is the one we've
50 /// selected, and `source_substs` is a substitution of its generics.
51 /// And `target_node` is the impl/trait we're actually going to get the
52 /// definition from. The resulting substitution will map from `target_node`'s
53 /// generics to `source_impl`'s generics as instantiated by `source_subst`.
55 /// For example, consider the following scenario:
57 /// ```ignore (illustrative)
59 /// impl<T, U> Foo for (T, U) { ... } // target impl
60 /// impl<V> Foo for (V, V) { ... } // source impl
63 /// Suppose we have selected "source impl" with `V` instantiated with `u32`.
64 /// This function will produce a substitution with `T` and `U` both mapping to `u32`.
66 /// where-clauses add some trickiness here, because they can be used to "define"
67 /// an argument indirectly:
69 /// ```ignore (illustrative)
70 /// impl<'a, I, T: 'a> Iterator for Cloned<I>
71 /// where I: Iterator<Item = &'a T>, T: Clone
74 /// In a case like this, the substitution for `T` is determined indirectly,
75 /// through associated type projection. We deal with such cases by using
76 /// *fulfillment* to relate the two impls, requiring that all projections are
78 pub fn translate_substs<'tcx>(
79 infcx: &InferCtxt<'tcx>,
80 param_env: ty::ParamEnv<'tcx>,
82 source_substs: SubstsRef<'tcx>,
83 target_node: specialization_graph::Node,
84 ) -> SubstsRef<'tcx> {
86 "translate_substs({:?}, {:?}, {:?}, {:?})",
87 param_env, source_impl, source_substs, target_node
89 let source_trait_ref =
90 infcx.tcx.bound_impl_trait_ref(source_impl).unwrap().subst(infcx.tcx, &source_substs);
92 // translate the Self and Param parts of the substitution, since those
94 let target_substs = match target_node {
95 specialization_graph::Node::Impl(target_impl) => {
96 // no need to translate if we're targeting the impl we started with
97 if source_impl == target_impl {
101 fulfill_implication(infcx, param_env, source_trait_ref, target_impl).unwrap_or_else(
104 "When translating substitutions for specialization, the expected \
105 specialization failed to hold"
110 specialization_graph::Node::Trait(..) => source_trait_ref.substs,
113 // directly inherent the method generics, since those do not vary across impls
114 source_substs.rebase_onto(infcx.tcx, source_impl, target_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 #[instrument(skip(tcx), level = "debug")]
123 pub(super) fn specializes(tcx: TyCtxt<'_>, (impl1_def_id, impl2_def_id): (DefId, DefId)) -> bool {
124 // The feature gate should prevent introducing new specializations, but not
125 // taking advantage of upstream ones.
126 let features = tcx.features();
127 let specialization_enabled = features.specialization || features.min_specialization;
128 if !specialization_enabled && (impl1_def_id.is_local() || impl2_def_id.is_local()) {
132 // We determine whether there's a subset relationship by:
134 // - replacing bound vars with placeholders in impl1,
135 // - assuming the where clauses for impl1,
136 // - instantiating impl2 with fresh inference variables,
138 // - attempting to prove the where clauses for impl2
140 // The last three steps are encapsulated in `fulfill_implication`.
142 // See RFC 1210 for more details and justification.
144 // Currently we do not allow e.g., a negative impl to specialize a positive one
145 if tcx.impl_polarity(impl1_def_id) != tcx.impl_polarity(impl2_def_id) {
149 // create a parameter environment corresponding to a (placeholder) instantiation of impl1
150 let penv = tcx.param_env(impl1_def_id);
151 let impl1_trait_ref = tcx.impl_trait_ref(impl1_def_id).unwrap();
153 // Create an infcx, taking the predicates of impl1 as assumptions:
154 let infcx = tcx.infer_ctxt().build();
155 let impl1_trait_ref =
156 match traits::fully_normalize(&infcx, ObligationCause::dummy(), penv, impl1_trait_ref) {
157 Ok(impl1_trait_ref) => impl1_trait_ref,
159 tcx.sess.delay_span_bug(
160 tcx.def_span(impl1_def_id),
161 format!("failed to fully normalize {impl1_trait_ref}"),
167 // Attempt to prove that impl2 applies, given all of the above.
168 fulfill_implication(&infcx, penv, impl1_trait_ref, impl2_def_id).is_ok()
171 /// Attempt to fulfill all obligations of `target_impl` after unification with
172 /// `source_trait_ref`. If successful, returns a substitution for *all* the
173 /// generics of `target_impl`, including both those needed to unify with
174 /// `source_trait_ref` and those whose identity is determined via a where
175 /// clause in the impl.
176 fn fulfill_implication<'tcx>(
177 infcx: &InferCtxt<'tcx>,
178 param_env: ty::ParamEnv<'tcx>,
179 source_trait_ref: ty::TraitRef<'tcx>,
181 ) -> Result<SubstsRef<'tcx>, ()> {
183 "fulfill_implication({:?}, trait_ref={:?} |- {:?} applies)",
184 param_env, source_trait_ref, target_impl
187 let source_trait = ImplSubject::Trait(source_trait_ref);
189 let selcx = &mut SelectionContext::new(&infcx);
190 let target_substs = infcx.fresh_substs_for_item(DUMMY_SP, target_impl);
191 let (target_trait, obligations) =
192 util::impl_subject_and_oblig(selcx, param_env, target_impl, target_substs);
194 // do the impls unify? If not, no specialization.
195 let Ok(InferOk { obligations: more_obligations, .. }) =
196 infcx.at(&ObligationCause::dummy(), param_env).eq(source_trait, target_trait)
199 "fulfill_implication: {:?} does not unify with {:?}",
200 source_trait, target_trait
205 // Needs to be `in_snapshot` because this function is used to rebase
206 // substitutions, which may happen inside of a select within a probe.
207 let mut engine = <dyn TraitEngine<'tcx>>::new_in_snapshot(infcx.tcx);
208 // attempt to prove all of the predicates for impl2 given those for impl1
209 // (which are packed up in penv)
210 engine.register_predicate_obligations(infcx, obligations.chain(more_obligations));
212 let errors = engine.select_all_or_error(infcx);
213 if !errors.is_empty() {
216 "fulfill_implication: for impls on {:?} and {:?}, \
217 could not fulfill: {:?} given {:?}",
221 param_env.caller_bounds()
226 debug!("fulfill_implication: an impl for {:?} specializes {:?}", source_trait, target_trait);
228 // Now resolve the *substitution* we built for the target earlier, replacing
229 // the inference variables inside with whatever we got from fulfillment.
230 Ok(infcx.resolve_vars_if_possible(target_substs))
233 // Query provider for `specialization_graph_of`.
234 pub(super) fn specialization_graph_provider(
237 ) -> specialization_graph::Graph {
238 let mut sg = specialization_graph::Graph::new();
239 let overlap_mode = specialization_graph::OverlapMode::get(tcx, trait_id);
241 let mut trait_impls: Vec<_> = tcx.all_impls(trait_id).collect();
243 // The coherence checking implementation seems to rely on impls being
244 // iterated over (roughly) in definition order, so we are sorting by
245 // negated `CrateNum` (so remote definitions are visited first) and then
246 // by a flattened version of the `DefIndex`.
248 .sort_unstable_by_key(|def_id| (-(def_id.krate.as_u32() as i64), def_id.index.index()));
250 for impl_def_id in trait_impls {
251 if let Some(impl_def_id) = impl_def_id.as_local() {
252 // This is where impl overlap checking happens:
253 let insert_result = sg.insert(tcx, impl_def_id.to_def_id(), overlap_mode);
254 // Report error if there was one.
255 let (overlap, used_to_be_allowed) = match insert_result {
256 Err(overlap) => (Some(overlap), None),
257 Ok(Some(overlap)) => (Some(overlap.error), Some(overlap.kind)),
258 Ok(None) => (None, None),
261 if let Some(overlap) = overlap {
262 report_overlap_conflict(tcx, overlap, impl_def_id, used_to_be_allowed, &mut sg);
265 let parent = tcx.impl_parent(impl_def_id).unwrap_or(trait_id);
266 sg.record_impl_from_cstore(tcx, parent, impl_def_id)
273 // This function is only used when
274 // encountering errors and inlining
275 // it negatively impacts perf.
278 fn report_overlap_conflict(
280 overlap: OverlapError,
281 impl_def_id: LocalDefId,
282 used_to_be_allowed: Option<FutureCompatOverlapErrorKind>,
283 sg: &mut specialization_graph::Graph,
285 let impl_polarity = tcx.impl_polarity(impl_def_id.to_def_id());
286 let other_polarity = tcx.impl_polarity(overlap.with_impl);
287 match (impl_polarity, other_polarity) {
288 (ty::ImplPolarity::Negative, ty::ImplPolarity::Positive) => {
289 report_negative_positive_conflict(
293 impl_def_id.to_def_id(),
299 (ty::ImplPolarity::Positive, ty::ImplPolarity::Negative) => {
300 report_negative_positive_conflict(
305 impl_def_id.to_def_id(),
311 report_conflicting_impls(tcx, overlap, impl_def_id, used_to_be_allowed, sg);
316 fn report_negative_positive_conflict(
318 overlap: &OverlapError,
319 local_impl_def_id: LocalDefId,
320 negative_impl_def_id: DefId,
321 positive_impl_def_id: DefId,
322 sg: &mut specialization_graph::Graph,
324 let mut err = tcx.sess.create_err(NegativePositiveConflict {
325 impl_span: tcx.def_span(local_impl_def_id),
326 trait_desc: &overlap.trait_desc,
327 self_desc: &overlap.self_desc,
328 negative_impl_span: tcx.span_of_impl(negative_impl_def_id),
329 positive_impl_span: tcx.span_of_impl(positive_impl_def_id),
331 sg.has_errored = Some(err.emit());
334 fn report_conflicting_impls(
336 overlap: OverlapError,
337 impl_def_id: LocalDefId,
338 used_to_be_allowed: Option<FutureCompatOverlapErrorKind>,
339 sg: &mut specialization_graph::Graph,
341 let impl_span = tcx.def_span(impl_def_id);
343 // Work to be done after we've built the DiagnosticBuilder. We have to define it
344 // now because the struct_lint methods don't return back the DiagnosticBuilder
346 fn decorate<'a, 'b, G: EmissionGuarantee>(
348 overlap: OverlapError,
350 err: &'b mut DiagnosticBuilder<'a, G>,
351 ) -> &'b mut DiagnosticBuilder<'a, G> {
352 match tcx.span_of_impl(overlap.with_impl) {
354 err.span_label(span, "first implementation here");
359 "conflicting implementation{}",
360 overlap.self_desc.map_or_else(String::new, |ty| format!(" for `{}`", ty))
365 let msg = match to_pretty_impl_header(tcx, overlap.with_impl) {
367 format!("conflicting implementation in crate `{}`:\n- {}", cname, s)
369 None => format!("conflicting implementation in crate `{}`", cname),
375 for cause in &overlap.intercrate_ambiguity_causes {
376 cause.add_intercrate_ambiguity_hint(err);
379 if overlap.involves_placeholder {
380 coherence::add_placeholder_note(err);
386 "conflicting implementations of trait `{}`{}{}",
388 overlap.self_desc.as_deref().map_or_else(String::new, |ty| format!(" for type `{ty}`")),
389 match used_to_be_allowed {
390 Some(FutureCompatOverlapErrorKind::Issue33140) => ": (E0119)",
395 match used_to_be_allowed {
397 let reported = if overlap.with_impl.is_local()
398 || tcx.orphan_check_impl(impl_def_id).is_ok()
400 let mut err = struct_span_err!(tcx.sess, impl_span, E0119, "{msg}",);
401 decorate(tcx, overlap, impl_span, &mut err);
404 Some(tcx.sess.delay_span_bug(impl_span, "impl should have failed the orphan check"))
406 sg.has_errored = reported;
409 let lint = match kind {
410 FutureCompatOverlapErrorKind::Issue33140 => ORDER_DEPENDENT_TRAIT_OBJECTS,
411 FutureCompatOverlapErrorKind::LeakCheck => COHERENCE_LEAK_CHECK,
413 tcx.struct_span_lint_hir(
415 tcx.hir().local_def_id_to_hir_id(impl_def_id),
418 |err| decorate(tcx, overlap, impl_span, err),
424 /// Recovers the "impl X for Y" signature from `impl_def_id` and returns it as a
426 pub(crate) fn to_pretty_impl_header(tcx: TyCtxt<'_>, impl_def_id: DefId) -> Option<String> {
429 let trait_ref = tcx.impl_trait_ref(impl_def_id)?;
430 let mut w = "impl".to_owned();
432 let substs = InternalSubsts::identity_for_item(tcx, impl_def_id);
434 // FIXME: Currently only handles ?Sized.
435 // Needs to support ?Move and ?DynSized when they are implemented.
436 let mut types_without_default_bounds = FxIndexSet::default();
437 let sized_trait = tcx.lang_items().sized_trait();
439 if !substs.is_empty() {
440 types_without_default_bounds.extend(substs.types());
445 .map(|k| k.to_string())
446 .filter(|k| k != "'_")
453 write!(w, " {} for {}", trait_ref.print_only_trait_path(), tcx.type_of(impl_def_id)).unwrap();
455 // The predicates will contain default bounds like `T: Sized`. We need to
456 // remove these bounds, and add `T: ?Sized` to any untouched type parameters.
457 let predicates = tcx.predicates_of(impl_def_id).predicates;
458 let mut pretty_predicates =
459 Vec::with_capacity(predicates.len() + types_without_default_bounds.len());
461 for (mut p, _) in predicates {
462 if let Some(poly_trait_ref) = p.to_opt_poly_trait_pred() {
463 if Some(poly_trait_ref.def_id()) == sized_trait {
464 types_without_default_bounds.remove(&poly_trait_ref.self_ty().skip_binder());
468 if ty::BoundConstness::ConstIfConst == poly_trait_ref.skip_binder().constness {
469 let new_trait_pred = poly_trait_ref.map_bound(|mut trait_pred| {
470 trait_pred.constness = ty::BoundConstness::NotConst;
474 p = tcx.mk_predicate(new_trait_pred.map_bound(ty::PredicateKind::Trait))
477 pretty_predicates.push(p.to_string());
481 .extend(types_without_default_bounds.iter().map(|ty| format!("{}: ?Sized", ty)));
483 if !pretty_predicates.is_empty() {
484 write!(w, "\n where {}", pretty_predicates.join(", ")).unwrap();