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::errors::NegativePositiveConflict;
16 use crate::infer::{InferCtxt, InferOk, TyCtxtInferExt};
17 use crate::traits::select::IntercrateAmbiguityCause;
19 self, coherence, FutureCompatOverlapErrorKind, ObligationCause, ObligationCtxt,
21 use rustc_data_structures::fx::FxIndexSet;
22 use rustc_errors::{error_code, DelayDm, Diagnostic};
23 use rustc_hir::def_id::{DefId, LocalDefId};
24 use rustc_middle::ty::{self, ImplSubject, Ty, 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<'tcx> {
37 pub trait_ref: ty::TraitRef<'tcx>,
38 pub self_ty: Option<Ty<'tcx>>,
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 ocx = ObligationCtxt::new_in_snapshot(infcx);
208 // attempt to prove all of the predicates for impl2 given those for impl1
209 // (which are packed up in penv)
210 ocx.register_obligations(obligations.chain(more_obligations));
212 let errors = ocx.select_all_or_error();
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<'tcx>(
280 overlap: OverlapError<'tcx>,
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<'tcx>(
318 overlap: &OverlapError<'tcx>,
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_ref,
327 self_ty: overlap.self_ty,
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<'tcx>(
336 overlap: OverlapError<'tcx>,
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
348 overlap: &OverlapError<'tcx>,
350 err: &mut Diagnostic,
352 match tcx.span_of_impl(overlap.with_impl) {
354 err.span_label(span, "first implementation here");
359 "conflicting implementation{}",
360 overlap.self_ty.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);
384 let msg = DelayDm(|| {
386 "conflicting implementations of trait `{}`{}{}",
387 overlap.trait_ref.print_only_trait_path(),
388 overlap.self_ty.map_or_else(String::new, |ty| format!(" for type `{ty}`")),
389 match used_to_be_allowed {
390 Some(FutureCompatOverlapErrorKind::Issue33140) => ": (E0119)",
396 match used_to_be_allowed {
398 let reported = if overlap.with_impl.is_local()
399 || tcx.orphan_check_impl(impl_def_id).is_ok()
401 let mut err = tcx.sess.struct_span_err(impl_span, msg);
402 err.code(error_code!(E0119));
403 decorate(tcx, &overlap, impl_span, &mut err);
406 Some(tcx.sess.delay_span_bug(impl_span, "impl should have failed the orphan check"))
408 sg.has_errored = reported;
411 let lint = match kind {
412 FutureCompatOverlapErrorKind::Issue33140 => ORDER_DEPENDENT_TRAIT_OBJECTS,
413 FutureCompatOverlapErrorKind::LeakCheck => COHERENCE_LEAK_CHECK,
415 tcx.struct_span_lint_hir(
417 tcx.hir().local_def_id_to_hir_id(impl_def_id),
421 decorate(tcx, &overlap, impl_span, err);
429 /// Recovers the "impl X for Y" signature from `impl_def_id` and returns it as a
431 pub(crate) fn to_pretty_impl_header(tcx: TyCtxt<'_>, impl_def_id: DefId) -> Option<String> {
434 let trait_ref = tcx.impl_trait_ref(impl_def_id)?;
435 let mut w = "impl".to_owned();
437 let substs = InternalSubsts::identity_for_item(tcx, impl_def_id);
439 // FIXME: Currently only handles ?Sized.
440 // Needs to support ?Move and ?DynSized when they are implemented.
441 let mut types_without_default_bounds = FxIndexSet::default();
442 let sized_trait = tcx.lang_items().sized_trait();
444 if !substs.is_empty() {
445 types_without_default_bounds.extend(substs.types());
450 .map(|k| k.to_string())
451 .filter(|k| k != "'_")
458 write!(w, " {} for {}", trait_ref.print_only_trait_path(), tcx.type_of(impl_def_id)).unwrap();
460 // The predicates will contain default bounds like `T: Sized`. We need to
461 // remove these bounds, and add `T: ?Sized` to any untouched type parameters.
462 let predicates = tcx.predicates_of(impl_def_id).predicates;
463 let mut pretty_predicates =
464 Vec::with_capacity(predicates.len() + types_without_default_bounds.len());
466 for (mut p, _) in predicates {
467 if let Some(poly_trait_ref) = p.to_opt_poly_trait_pred() {
468 if Some(poly_trait_ref.def_id()) == sized_trait {
469 types_without_default_bounds.remove(&poly_trait_ref.self_ty().skip_binder());
473 if ty::BoundConstness::ConstIfConst == poly_trait_ref.skip_binder().constness {
474 let new_trait_pred = poly_trait_ref.map_bound(|mut trait_pred| {
475 trait_pred.constness = ty::BoundConstness::NotConst;
479 p = tcx.mk_predicate(
480 new_trait_pred.map_bound(|p| ty::PredicateKind::Clause(ty::Clause::Trait(p))),
484 pretty_predicates.push(p.to_string());
488 .extend(types_without_default_bounds.iter().map(|ty| format!("{}: ?Sized", ty)));
490 if !pretty_predicates.is_empty() {
491 write!(w, "\n where {}", pretty_predicates.join(", ")).unwrap();