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::infer
::{InferCtxt, InferOk}
;
15 use crate::traits
::select
::IntercrateAmbiguityCause
;
16 use crate::traits
::{self, coherence, FutureCompatOverlapErrorKind, ObligationCause, TraitEngine}
;
17 use crate::ty
::subst
::{InternalSubsts, Subst, SubstsRef}
;
18 use crate::ty
::{self, TyCtxt, TypeFoldable}
;
19 use rustc_data_structures
::fx
::FxHashSet
;
20 use rustc_errors
::struct_span_err
;
21 use rustc_hir
::def_id
::DefId
;
22 use rustc_session
::lint
::builtin
::ORDER_DEPENDENT_TRAIT_OBJECTS
;
23 use rustc_span
::DUMMY_SP
;
25 use super::util
::impl_trait_ref_and_oblig
;
26 use super::{FulfillmentContext, SelectionContext}
;
28 /// Information pertinent to an overlapping impl error.
30 pub struct OverlapError
{
32 pub trait_desc
: String
,
33 pub self_desc
: Option
<String
>,
34 pub intercrate_ambiguity_causes
: Vec
<IntercrateAmbiguityCause
>,
35 pub involves_placeholder
: bool
,
38 /// Given a subst for the requested impl, translate it to a subst
39 /// appropriate for the actual item definition (whether it be in that impl,
40 /// a parent impl, or the trait).
42 /// When we have selected one impl, but are actually using item definitions from
43 /// a parent impl providing a default, we need a way to translate between the
44 /// type parameters of the two impls. Here the `source_impl` is the one we've
45 /// selected, and `source_substs` is a substitution of its generics.
46 /// And `target_node` is the impl/trait we're actually going to get the
47 /// definition from. The resulting substitution will map from `target_node`'s
48 /// generics to `source_impl`'s generics as instantiated by `source_subst`.
50 /// For example, consider the following scenario:
54 /// impl<T, U> Foo for (T, U) { ... } // target impl
55 /// impl<V> Foo for (V, V) { ... } // source impl
58 /// Suppose we have selected "source impl" with `V` instantiated with `u32`.
59 /// This function will produce a substitution with `T` and `U` both mapping to `u32`.
61 /// where-clauses add some trickiness here, because they can be used to "define"
62 /// an argument indirectly:
65 /// impl<'a, I, T: 'a> Iterator for Cloned<I>
66 /// where I: Iterator<Item = &'a T>, T: Clone
69 /// In a case like this, the substitution for `T` is determined indirectly,
70 /// through associated type projection. We deal with such cases by using
71 /// *fulfillment* to relate the two impls, requiring that all projections are
73 pub fn translate_substs
<'a
, 'tcx
>(
74 infcx
: &InferCtxt
<'a
, 'tcx
>,
75 param_env
: ty
::ParamEnv
<'tcx
>,
77 source_substs
: SubstsRef
<'tcx
>,
78 target_node
: specialization_graph
::Node
,
79 ) -> SubstsRef
<'tcx
> {
81 "translate_substs({:?}, {:?}, {:?}, {:?})",
82 param_env
, source_impl
, source_substs
, target_node
84 let source_trait_ref
=
85 infcx
.tcx
.impl_trait_ref(source_impl
).unwrap().subst(infcx
.tcx
, &source_substs
);
87 // translate the Self and Param parts of the substitution, since those
89 let target_substs
= match target_node
{
90 specialization_graph
::Node
::Impl(target_impl
) => {
91 // no need to translate if we're targeting the impl we started with
92 if source_impl
== target_impl
{
96 fulfill_implication(infcx
, param_env
, source_trait_ref
, target_impl
).unwrap_or_else(
99 "When translating substitutions for specialization, the expected \
100 specialization failed to hold"
105 specialization_graph
::Node
::Trait(..) => source_trait_ref
.substs
,
108 // directly inherent the method generics, since those do not vary across impls
109 source_substs
.rebase_onto(infcx
.tcx
, source_impl
, target_substs
)
112 /// Given a selected impl described by `impl_data`, returns the
113 /// definition and substitutions for the method with the name `name`
114 /// the kind `kind`, and trait method substitutions `substs`, in
115 /// that impl, a less specialized impl, or the trait default,
116 /// whichever applies.
117 pub fn find_associated_item
<'tcx
>(
119 param_env
: ty
::ParamEnv
<'tcx
>,
120 item
: &ty
::AssocItem
,
121 substs
: SubstsRef
<'tcx
>,
122 impl_data
: &super::VtableImplData
<'tcx
, ()>,
123 ) -> (DefId
, SubstsRef
<'tcx
>) {
124 debug
!("find_associated_item({:?}, {:?}, {:?}, {:?})", param_env
, item
, substs
, impl_data
);
125 assert
!(!substs
.needs_infer());
127 let trait_def_id
= tcx
.trait_id_of_impl(impl_data
.impl_def_id
).unwrap();
128 let trait_def
= tcx
.trait_def(trait_def_id
);
130 let ancestors
= trait_def
.ancestors(tcx
, impl_data
.impl_def_id
);
131 match ancestors
.leaf_def(tcx
, item
.ident
, item
.kind
) {
133 let substs
= tcx
.infer_ctxt().enter(|infcx
| {
134 let param_env
= param_env
.with_reveal_all();
135 let substs
= substs
.rebase_onto(tcx
, trait_def_id
, impl_data
.substs
);
136 let substs
= translate_substs(
139 impl_data
.impl_def_id
,
143 infcx
.tcx
.erase_regions(&substs
)
145 (node_item
.item
.def_id
, substs
)
147 None
=> bug
!("{:?} not found in {:?}", item
, impl_data
.impl_def_id
),
151 /// Is `impl1` a specialization of `impl2`?
153 /// Specialization is determined by the sets of types to which the impls apply;
154 /// `impl1` specializes `impl2` if it applies to a subset of the types `impl2` applies
156 pub(super) fn specializes(tcx
: TyCtxt
<'_
>, (impl1_def_id
, impl2_def_id
): (DefId
, DefId
)) -> bool
{
157 debug
!("specializes({:?}, {:?})", impl1_def_id
, impl2_def_id
);
159 // The feature gate should prevent introducing new specializations, but not
160 // taking advantage of upstream ones.
161 if !tcx
.features().specialization
&& (impl1_def_id
.is_local() || impl2_def_id
.is_local()) {
165 // We determine whether there's a subset relationship by:
167 // - skolemizing impl1,
168 // - assuming the where clauses for impl1,
169 // - instantiating impl2 with fresh inference variables,
171 // - attempting to prove the where clauses for impl2
173 // The last three steps are encapsulated in `fulfill_implication`.
175 // See RFC 1210 for more details and justification.
177 // Currently we do not allow e.g., a negative impl to specialize a positive one
178 if tcx
.impl_polarity(impl1_def_id
) != tcx
.impl_polarity(impl2_def_id
) {
182 // create a parameter environment corresponding to a (placeholder) instantiation of impl1
183 let penv
= tcx
.param_env(impl1_def_id
);
184 let impl1_trait_ref
= tcx
.impl_trait_ref(impl1_def_id
).unwrap();
186 // Create a infcx, taking the predicates of impl1 as assumptions:
187 tcx
.infer_ctxt().enter(|infcx
| {
188 // Normalize the trait reference. The WF rules ought to ensure
189 // that this always succeeds.
190 let impl1_trait_ref
= match traits
::fully_normalize(
192 FulfillmentContext
::new(),
193 ObligationCause
::dummy(),
197 Ok(impl1_trait_ref
) => impl1_trait_ref
,
199 bug
!("failed to fully normalize {:?}: {:?}", impl1_trait_ref
, err
);
203 // Attempt to prove that impl2 applies, given all of the above.
204 fulfill_implication(&infcx
, penv
, impl1_trait_ref
, impl2_def_id
).is_ok()
208 /// Attempt to fulfill all obligations of `target_impl` after unification with
209 /// `source_trait_ref`. If successful, returns a substitution for *all* the
210 /// generics of `target_impl`, including both those needed to unify with
211 /// `source_trait_ref` and those whose identity is determined via a where
212 /// clause in the impl.
213 fn fulfill_implication
<'a
, 'tcx
>(
214 infcx
: &InferCtxt
<'a
, 'tcx
>,
215 param_env
: ty
::ParamEnv
<'tcx
>,
216 source_trait_ref
: ty
::TraitRef
<'tcx
>,
218 ) -> Result
<SubstsRef
<'tcx
>, ()> {
220 "fulfill_implication({:?}, trait_ref={:?} |- {:?} applies)",
221 param_env
, source_trait_ref
, target_impl
224 let selcx
= &mut SelectionContext
::new(&infcx
);
225 let target_substs
= infcx
.fresh_substs_for_item(DUMMY_SP
, target_impl
);
226 let (target_trait_ref
, mut obligations
) =
227 impl_trait_ref_and_oblig(selcx
, param_env
, target_impl
, target_substs
);
229 "fulfill_implication: target_trait_ref={:?}, obligations={:?}",
230 target_trait_ref
, obligations
233 // do the impls unify? If not, no specialization.
234 match infcx
.at(&ObligationCause
::dummy(), param_env
).eq(source_trait_ref
, target_trait_ref
) {
235 Ok(InferOk { obligations: o, .. }
) => {
236 obligations
.extend(o
);
240 "fulfill_implication: {:?} does not unify with {:?}",
241 source_trait_ref
, target_trait_ref
247 // attempt to prove all of the predicates for impl2 given those for impl1
248 // (which are packed up in penv)
250 infcx
.save_and_restore_in_snapshot_flag(|infcx
| {
251 // If we came from `translate_substs`, we already know that the
252 // predicates for our impl hold (after all, we know that a more
253 // specialized impl holds, so our impl must hold too), and
254 // we only want to process the projections to determine the
255 // the types in our substs using RFC 447, so we can safely
256 // ignore region obligations, which allows us to avoid threading
257 // a node-id to assign them with.
259 // If we came from specialization graph construction, then
260 // we already make a mockery out of the region system, so
261 // why not ignore them a bit earlier?
262 let mut fulfill_cx
= FulfillmentContext
::new_ignoring_regions();
263 for oblig
in obligations
.into_iter() {
264 fulfill_cx
.register_predicate_obligation(&infcx
, oblig
);
266 match fulfill_cx
.select_all_or_error(infcx
) {
270 "fulfill_implication: for impls on {:?} and {:?}, \
271 could not fulfill: {:?} given {:?}",
272 source_trait_ref
, target_trait_ref
, errors
, param_env
.caller_bounds
279 "fulfill_implication: an impl for {:?} specializes {:?}",
280 source_trait_ref
, target_trait_ref
283 // Now resolve the *substitution* we built for the target earlier, replacing
284 // the inference variables inside with whatever we got from fulfillment.
285 Ok(infcx
.resolve_vars_if_possible(&target_substs
))
291 // Query provider for `specialization_graph_of`.
292 pub(super) fn specialization_graph_provider(
295 ) -> &specialization_graph
::Graph
{
296 let mut sg
= specialization_graph
::Graph
::new();
298 let mut trait_impls
= tcx
.all_impls(trait_id
);
300 // The coherence checking implementation seems to rely on impls being
301 // iterated over (roughly) in definition order, so we are sorting by
302 // negated `CrateNum` (so remote definitions are visited first) and then
303 // by a flattened version of the `DefIndex`.
305 .sort_unstable_by_key(|def_id
| (-(def_id
.krate
.as_u32() as i64), def_id
.index
.index()));
307 for impl_def_id
in trait_impls
{
308 if impl_def_id
.is_local() {
309 // This is where impl overlap checking happens:
310 let insert_result
= sg
.insert(tcx
, impl_def_id
);
311 // Report error if there was one.
312 let (overlap
, used_to_be_allowed
) = match insert_result
{
313 Err(overlap
) => (Some(overlap
), None
),
314 Ok(Some(overlap
)) => (Some(overlap
.error
), Some(overlap
.kind
)),
315 Ok(None
) => (None
, None
),
318 if let Some(overlap
) = overlap
{
320 "conflicting implementations of trait `{}`{}:{}",
325 .map_or(String
::new(), |ty
| { format!(" for type `{}`
", ty) }),
326 match used_to_be_allowed {
327 Some(FutureCompatOverlapErrorKind::Issue33140) => " (E0119
)",
332 tcx.sess.source_map().def_span(tcx.span_of_impl(impl_def_id).unwrap());
333 let mut err = match used_to_be_allowed {
334 Some(FutureCompatOverlapErrorKind::Issue43355) | None => {
335 struct_span_err!(tcx.sess, impl_span, E0119, "{}
", msg)
338 let lint = match kind {
339 FutureCompatOverlapErrorKind::Issue43355 => {
340 unreachable!("converted to hard error above
")
342 FutureCompatOverlapErrorKind::Issue33140 => {
343 ORDER_DEPENDENT_TRAIT_OBJECTS
346 tcx.struct_span_lint_hir(
348 tcx.hir().as_local_hir_id(impl_def_id).unwrap(),
355 match tcx.span_of_impl(overlap.with_impl) {
358 tcx.sess.source_map().def_span(span),
359 "first implementation here
".to_string(),
364 "conflicting implementation{}
",
367 .map_or(String::new(), |ty| format!(" for `{}`
", ty))
372 let msg = match to_pretty_impl_header(tcx, overlap.with_impl) {
374 format!("conflicting implementation
in crate `{}`
:\n- {}
", cname, s)
376 None => format!("conflicting implementation
in crate `{}`
", cname),
382 for cause in &overlap.intercrate_ambiguity_causes {
383 cause.add_intercrate_ambiguity_hint(&mut err);
386 if overlap.involves_placeholder {
387 coherence::add_placeholder_note(&mut err);
393 let parent = tcx.impl_parent(impl_def_id).unwrap_or(trait_id);
394 sg.record_impl_from_cstore(tcx, parent, impl_def_id)
401 /// Recovers the "impl X
for Y
" signature from `impl_def_id` and returns it as a
403 fn to_pretty_impl_header(tcx: TyCtxt<'_>, impl_def_id: DefId) -> Option<String> {
406 let trait_ref = if let Some(tr) = tcx.impl_trait_ref(impl_def_id) {
412 let mut w = "impl".to_owned();
414 let substs = InternalSubsts::identity_for_item(tcx, impl_def_id);
416 // FIXME: Currently only handles ?Sized.
417 // Needs to support ?Move and ?DynSized when they are implemented.
418 let mut types_without_default_bounds = FxHashSet::default();
419 let sized_trait = tcx.lang_items().sized_trait();
421 if !substs.is_noop() {
422 types_without_default_bounds.extend(substs.types());
427 .map(|k| k.to_string())
428 .filter(|k| k != "'_
")
435 write!(w, " {}
for {}
", trait_ref.print_only_trait_path(), tcx.type_of(impl_def_id)).unwrap();
437 // The predicates will contain default bounds like `T: Sized`. We need to
438 // remove these bounds, and add `T: ?Sized` to any untouched type parameters.
439 let predicates = tcx.predicates_of(impl_def_id).predicates;
440 let mut pretty_predicates =
441 Vec::with_capacity(predicates.len() + types_without_default_bounds.len());
443 for (p, _) in predicates {
444 if let Some(poly_trait_ref) = p.to_opt_poly_trait_ref() {
445 if Some(poly_trait_ref.def_id()) == sized_trait {
446 types_without_default_bounds.remove(poly_trait_ref.self_ty());
450 pretty_predicates.push(p.to_string());
454 .extend(types_without_default_bounds.iter().map(|ty| format!("{}
: ?Sized
", ty)));
456 if !pretty_predicates.is_empty() {
457 write!(w, "\n where {}
", pretty_predicates.join(", ")).unwrap();