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, EmissionGuarantee}
;
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, ImplSubject, TyCtxt}
;
24 use rustc_session
::lint
::builtin
::COHERENCE_LEAK_CHECK
;
25 use rustc_session
::lint
::builtin
::ORDER_DEPENDENT_TRAIT_OBJECTS
;
26 use rustc_span
::{Span, DUMMY_SP}
;
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:
55 /// ```ignore (illustrative)
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:
67 /// ```ignore (illustrative)
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
.bound_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 #[instrument(skip(tcx), level = "debug")]
121 pub(super) fn specializes(tcx
: TyCtxt
<'_
>, (impl1_def_id
, impl2_def_id
): (DefId
, DefId
)) -> bool
{
122 // The feature gate should prevent introducing new specializations, but not
123 // taking advantage of upstream ones.
124 let features
= tcx
.features();
125 let specialization_enabled
= features
.specialization
|| features
.min_specialization
;
126 if !specialization_enabled
&& (impl1_def_id
.is_local() || impl2_def_id
.is_local()) {
130 // We determine whether there's a subset relationship by:
132 // - replacing bound vars with placeholders in impl1,
133 // - assuming the where clauses for impl1,
134 // - instantiating impl2 with fresh inference variables,
136 // - attempting to prove the where clauses for impl2
138 // The last three steps are encapsulated in `fulfill_implication`.
140 // See RFC 1210 for more details and justification.
142 // Currently we do not allow e.g., a negative impl to specialize a positive one
143 if tcx
.impl_polarity(impl1_def_id
) != tcx
.impl_polarity(impl2_def_id
) {
147 // create a parameter environment corresponding to a (placeholder) instantiation of impl1
148 let penv
= tcx
.param_env(impl1_def_id
);
149 let impl1_trait_ref
= tcx
.impl_trait_ref(impl1_def_id
).unwrap();
151 // Create an infcx, taking the predicates of impl1 as assumptions:
152 tcx
.infer_ctxt().enter(|infcx
| {
153 // Normalize the trait reference. The WF rules ought to ensure
154 // that this always succeeds.
155 let impl1_trait_ref
= match traits
::fully_normalize(
157 FulfillmentContext
::new(),
158 ObligationCause
::dummy(),
162 Ok(impl1_trait_ref
) => impl1_trait_ref
,
164 bug
!("failed to fully normalize {:?}: {:?}", impl1_trait_ref
, err
);
168 // Attempt to prove that impl2 applies, given all of the above.
169 fulfill_implication(&infcx
, penv
, impl1_trait_ref
, impl2_def_id
).is_ok()
173 /// Attempt to fulfill all obligations of `target_impl` after unification with
174 /// `source_trait_ref`. If successful, returns a substitution for *all* the
175 /// generics of `target_impl`, including both those needed to unify with
176 /// `source_trait_ref` and those whose identity is determined via a where
177 /// clause in the impl.
178 fn fulfill_implication
<'a
, 'tcx
>(
179 infcx
: &InferCtxt
<'a
, 'tcx
>,
180 param_env
: ty
::ParamEnv
<'tcx
>,
181 source_trait_ref
: ty
::TraitRef
<'tcx
>,
183 ) -> Result
<SubstsRef
<'tcx
>, ()> {
185 "fulfill_implication({:?}, trait_ref={:?} |- {:?} applies)",
186 param_env
, source_trait_ref
, target_impl
189 let source_trait
= ImplSubject
::Trait(source_trait_ref
);
191 let selcx
= &mut SelectionContext
::new(&infcx
);
192 let target_substs
= infcx
.fresh_substs_for_item(DUMMY_SP
, target_impl
);
193 let (target_trait
, obligations
) =
194 util
::impl_subject_and_oblig(selcx
, param_env
, target_impl
, target_substs
);
196 // do the impls unify? If not, no specialization.
197 let Ok(InferOk { obligations: more_obligations, .. }
) =
198 infcx
.at(&ObligationCause
::dummy(), param_env
).eq(source_trait
, target_trait
)
201 "fulfill_implication: {:?} does not unify with {:?}",
202 source_trait
, target_trait
207 // attempt to prove all of the predicates for impl2 given those for impl1
208 // (which are packed up in penv)
210 infcx
.save_and_restore_in_snapshot_flag(|infcx
| {
211 // If we came from `translate_substs`, we already know that the
212 // predicates for our impl hold (after all, we know that a more
213 // specialized impl holds, so our impl must hold too), and
214 // we only want to process the projections to determine the
215 // the types in our substs using RFC 447, so we can safely
216 // ignore region obligations, which allows us to avoid threading
217 // a node-id to assign them with.
219 // If we came from specialization graph construction, then
220 // we already make a mockery out of the region system, so
221 // why not ignore them a bit earlier?
222 let mut fulfill_cx
= FulfillmentContext
::new_ignoring_regions();
223 for oblig
in obligations
.chain(more_obligations
) {
224 fulfill_cx
.register_predicate_obligation(&infcx
, oblig
);
226 match fulfill_cx
.select_all_or_error(infcx
).as_slice() {
229 "fulfill_implication: an impl for {:?} specializes {:?}",
230 source_trait
, target_trait
233 // Now resolve the *substitution* we built for the target earlier, replacing
234 // the inference variables inside with whatever we got from fulfillment.
235 Ok(infcx
.resolve_vars_if_possible(target_substs
))
240 "fulfill_implication: for impls on {:?} and {:?}, \
241 could not fulfill: {:?} given {:?}",
245 param_env
.caller_bounds()
253 // Query provider for `specialization_graph_of`.
254 pub(super) fn specialization_graph_provider(
257 ) -> specialization_graph
::Graph
{
258 let mut sg
= specialization_graph
::Graph
::new();
259 let overlap_mode
= specialization_graph
::OverlapMode
::get(tcx
, trait_id
);
261 let mut trait_impls
: Vec
<_
> = tcx
.all_impls(trait_id
).collect();
263 // The coherence checking implementation seems to rely on impls being
264 // iterated over (roughly) in definition order, so we are sorting by
265 // negated `CrateNum` (so remote definitions are visited first) and then
266 // by a flattened version of the `DefIndex`.
268 .sort_unstable_by_key(|def_id
| (-(def_id
.krate
.as_u32() as i64), def_id
.index
.index()));
270 for impl_def_id
in trait_impls
{
271 if let Some(impl_def_id
) = impl_def_id
.as_local() {
272 // This is where impl overlap checking happens:
273 let insert_result
= sg
.insert(tcx
, impl_def_id
.to_def_id(), overlap_mode
);
274 // Report error if there was one.
275 let (overlap
, used_to_be_allowed
) = match insert_result
{
276 Err(overlap
) => (Some(overlap
), None
),
277 Ok(Some(overlap
)) => (Some(overlap
.error
), Some(overlap
.kind
)),
278 Ok(None
) => (None
, None
),
281 if let Some(overlap
) = overlap
{
282 report_overlap_conflict(tcx
, overlap
, impl_def_id
, used_to_be_allowed
, &mut sg
);
285 let parent
= tcx
.impl_parent(impl_def_id
).unwrap_or(trait_id
);
286 sg
.record_impl_from_cstore(tcx
, parent
, impl_def_id
)
293 // This function is only used when
294 // encountering errors and inlining
295 // it negatively impacts perf.
298 fn report_overlap_conflict(
300 overlap
: OverlapError
,
301 impl_def_id
: LocalDefId
,
302 used_to_be_allowed
: Option
<FutureCompatOverlapErrorKind
>,
303 sg
: &mut specialization_graph
::Graph
,
305 let impl_polarity
= tcx
.impl_polarity(impl_def_id
.to_def_id());
306 let other_polarity
= tcx
.impl_polarity(overlap
.with_impl
);
307 match (impl_polarity
, other_polarity
) {
308 (ty
::ImplPolarity
::Negative
, ty
::ImplPolarity
::Positive
) => {
309 report_negative_positive_conflict(
313 impl_def_id
.to_def_id(),
319 (ty
::ImplPolarity
::Positive
, ty
::ImplPolarity
::Negative
) => {
320 report_negative_positive_conflict(
325 impl_def_id
.to_def_id(),
331 report_conflicting_impls(tcx
, overlap
, impl_def_id
, used_to_be_allowed
, sg
);
336 fn report_negative_positive_conflict(
338 overlap
: &OverlapError
,
339 local_impl_def_id
: LocalDefId
,
340 negative_impl_def_id
: DefId
,
341 positive_impl_def_id
: DefId
,
342 sg
: &mut specialization_graph
::Graph
,
347 .guess_head_span(tcx
.span_of_impl(local_impl_def_id
.to_def_id()).unwrap());
349 let mut err
= struct_span_err
!(
353 "found both positive and negative implementation of trait `{}`{}:",
355 overlap
.self_desc
.clone().map_or_else(String
::new
, |ty
| format
!(" for type `{}`", ty
))
358 match tcx
.span_of_impl(negative_impl_def_id
) {
361 tcx
.sess
.source_map().guess_head_span(span
),
362 "negative implementation here".to_string(),
366 err
.note(&format
!("negative implementation in crate `{}`", cname
));
370 match tcx
.span_of_impl(positive_impl_def_id
) {
373 tcx
.sess
.source_map().guess_head_span(span
),
374 "positive implementation here".to_string(),
378 err
.note(&format
!("positive implementation in crate `{}`", cname
));
382 sg
.has_errored
= Some(err
.emit());
385 fn report_conflicting_impls(
387 overlap
: OverlapError
,
388 impl_def_id
: LocalDefId
,
389 used_to_be_allowed
: Option
<FutureCompatOverlapErrorKind
>,
390 sg
: &mut specialization_graph
::Graph
,
393 tcx
.sess
.source_map().guess_head_span(tcx
.span_of_impl(impl_def_id
.to_def_id()).unwrap());
395 // Work to be done after we've built the DiagnosticBuilder. We have to define it
396 // now because the struct_lint methods don't return back the DiagnosticBuilder
398 fn decorate
<G
: EmissionGuarantee
>(
400 overlap
: OverlapError
,
401 used_to_be_allowed
: Option
<FutureCompatOverlapErrorKind
>,
403 err
: LintDiagnosticBuilder
<'_
, G
>,
406 "conflicting implementations of trait `{}`{}{}",
411 .map_or_else(String
::new
, |ty
| { format!(" for type `{}`
", ty) }),
412 match used_to_be_allowed {
413 Some(FutureCompatOverlapErrorKind::Issue33140) => ": (E0119
)",
417 let mut err = err.build(&msg);
418 match tcx.span_of_impl(overlap.with_impl) {
421 tcx.sess.source_map().guess_head_span(span),
422 "first implementation here
".to_string(),
428 "conflicting implementation{}
",
429 overlap.self_desc.map_or_else(String::new, |ty| format!(" for `{}`
", ty))
434 let msg = match to_pretty_impl_header(tcx, overlap.with_impl) {
435 Some(s) => format!("conflicting implementation
in crate `{}`
:\n- {}
", cname, s),
436 None => format!("conflicting implementation
in crate `{}`
", cname),
442 for cause in &overlap.intercrate_ambiguity_causes {
443 cause.add_intercrate_ambiguity_hint(&mut err);
446 if overlap.involves_placeholder {
447 coherence::add_placeholder_note(&mut err);
452 match used_to_be_allowed {
454 let reported = if overlap.with_impl.is_local()
455 || !tcx.orphan_check_crate(()).contains(&impl_def_id)
457 let err = struct_span_err!(tcx.sess, impl_span, E0119, "");
463 LintDiagnosticBuilder::new(err),
466 Some(tcx.sess.delay_span_bug(impl_span, "impl should have failed the orphan check
"))
468 sg.has_errored = reported;
471 let lint = match kind {
472 FutureCompatOverlapErrorKind::Issue33140 => ORDER_DEPENDENT_TRAIT_OBJECTS,
473 FutureCompatOverlapErrorKind::LeakCheck => COHERENCE_LEAK_CHECK,
475 tcx.struct_span_lint_hir(
477 tcx.hir().local_def_id_to_hir_id(impl_def_id),
480 decorate(tcx, overlap, used_to_be_allowed, impl_span, ldb);
487 /// Recovers the "impl X
for Y
" signature from `impl_def_id` and returns it as a
489 crate fn to_pretty_impl_header(tcx: TyCtxt<'_>, impl_def_id: DefId) -> Option<String> {
492 let trait_ref = tcx.impl_trait_ref(impl_def_id)?;
493 let mut w = "impl".to_owned();
495 let substs = InternalSubsts::identity_for_item(tcx, impl_def_id);
497 // FIXME: Currently only handles ?Sized.
498 // Needs to support ?Move and ?DynSized when they are implemented.
499 let mut types_without_default_bounds = FxHashSet::default();
500 let sized_trait = tcx.lang_items().sized_trait();
502 if !substs.is_empty() {
503 types_without_default_bounds.extend(substs.types());
508 .map(|k| k.to_string())
509 .filter(|k| k != "'_
")
516 write!(w, " {}
for {}
", trait_ref.print_only_trait_path(), tcx.type_of(impl_def_id)).unwrap();
518 // The predicates will contain default bounds like `T: Sized`. We need to
519 // remove these bounds, and add `T: ?Sized` to any untouched type parameters.
520 let predicates = tcx.predicates_of(impl_def_id).predicates;
521 let mut pretty_predicates =
522 Vec::with_capacity(predicates.len() + types_without_default_bounds.len());
524 for (mut p, _) in predicates {
525 if let Some(poly_trait_ref) = p.to_opt_poly_trait_pred() {
526 if Some(poly_trait_ref.def_id()) == sized_trait {
527 types_without_default_bounds.remove(&poly_trait_ref.self_ty().skip_binder());
531 if ty::BoundConstness::ConstIfConst == poly_trait_ref.skip_binder().constness {
532 let new_trait_pred = poly_trait_ref.map_bound(|mut trait_pred| {
533 trait_pred.constness = ty::BoundConstness::NotConst;
537 p = tcx.mk_predicate(new_trait_pred.map_bound(ty::PredicateKind::Trait))
540 pretty_predicates.push(p.to_string());
544 .extend(types_without_default_bounds.iter().map(|ty| format!("{}
: ?Sized
", ty)));
546 if !pretty_predicates.is_empty() {
547 write!(w, "\n where {}
", pretty_predicates.join(", ")).unwrap();