Stabilize RFC 2451, re-rebalance coherence

[nikomatsakis]

Stabilization Proposal

I am writing to propose we stabilize the implementation of RFC 2451, "re-rebalancing coherence" (tracking issue).

Brief Summary

The RFC modifies the coherence rules. It used to be that, when implementing a non-local trait, if Ti was the first "local type", then all type parameters were forbidden before that point. In practice, that meant that this impl was illegal:

struct Local;

impl<T> Foreign<Local> for Vec<T> { }
//              ^^^^^          ^
//              |              type parameter
//              first local type

The RFC lightly generalizes these rules. In particular, type parameters are now allowed before Ti, but only if they are covered, defined in the RFC as:

Covered Type: A type which appears as a parameter to another type. For example, T is uncovered, but the T in Vec<T> is covered. This is only relevant for type parameters.

This means that the impl above is now legal, because the typeT is covered by Vec. Note that an impl like the following would still be illegal:

struct Local;

impl<T> Foreign<Local> for T { }
//              ^^^^^      ^
//              |          type parameter (uncovered)
//              first local type

It is considered a (semver) breaking change for parent crates to add impls with uncovered type parameters (this was already the case even with the old rules, I believe). Therefore, this generalization of the rules cannot permit a conflict between the parent crate and a child crate. (See RFC for a more detailed argument.)

(NB: I've elided details of #[fundamental] in this summary, see the RFC for full details.)

Changes since the RFC was approved

None

Test cases

This section describes the patterns covered by new tests added for this RFC, or tests that seemed relevant to this RFC, with links to the test files.

• impl<T> Foreign<Local> for Foreign<T, Foreign> -- re-rebalance-coherence.rs, re-rebalance-coherence-rpass.rs (these appear to be duplicate tests)
• impl<T> Foreign for Foreign<T, Local<T>> -- coherence-cow.rs, coherence-cow.rs
• impl<T,U> Foreign for Foreign<T, Local<U>> -- coherence-cow.rs, coherence-pair-covered-uncovered.rs
• impl<T> Foreign<Local> for T -- coherence-bigint-param.rs
• impl Foreign for Local<T> -- coherence-covered-type-parameter.rs, coherence-iterator-vec.rs
• impl<T> Foreign<T> for Foreign -- coherence-all-remote.rs
• impl Foreign<Local> for Foreign -- coherence-bigint-int.rs, coherence-bigint-vecint.rs
• impl<T> Foreign for T -- coherence-cross-crate-conflict.rs, coherence-lone-type-parameter.rs
• impl Foreign for Foreign<Local> -- coherence-vec-local.rs
• impl<T> Foreign<Foreign<T>, Local> for Foreign<T> -- in add new tests for re_rebalance_coherence #64414
• impl<T> Foreign<Local> for Fundamental<T> -- in add new tests for re_rebalance_coherence #64414

Missing items

• Open PR against the reference, updating documentation
• Fix re_rebalance_coherence doesn't properly account for fundamental types #64412
• Add more tests for fundamental patterns -- we did not by any means tile the space

[nikomatsakis]

@rfcbot fcp merge

Dear @rust-lang/lang, I propose that we stabilize the re-rebalancing coherence changes. This issue opens with a description of the changes and some examination of test cases. Please review and feel free to note any missing patterns, I'm opening a PR shortly adding and adjusting tests as needed.

Also, I don't think we've updated the reference, so I've included a checklist item to do that.

[rfcbot]

Team member @nikomatsakis has proposed to merge this. The next step is review by the rest of the tagged team members:

• @Centril
• @cramertj
• @eddyb
• @joshtriplett
• @nikomatsakis
• @pnkfelix
• @scottmcm
• @withoutboats

Concerns:

• make-sure-we-add-these-tests resolved by Stabilize RFC 2451, re-rebalance coherence #63599 (comment)

Once a majority of reviewers approve (and at most 2 approvals are outstanding), this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

[Centril]

I will open a PR shortly covering one missing pattern, where the Ti with the local type is T2:

* `impl<T> Foreign<Foreign<T>, Local> for Foreign<T>`

* XXX tests involving fundamental

@rfcbot concern make-sure-we-add-these-tests

:)

[scottmcm]

Curiosity: is T covered by [T; N] and (T,)?

[nikomatsakis]

Hmm, writing up some new tests, I am finding that the current implementation is not working as expected! In particular, the behavior around fundamental types seems wrong, or else I am misreading the RFC.

For example, this impl is allowed:

impl<T> Remote1<Local> for Box<T> { }

This is despite the text in the RFC which says:

Once again, it is important to note that for the purposes of coherence, #[fundamental] types are special. Box<T> is not considered covered, and Box<LocalType> is considered local.

I presume here that "Box<T> is not considered covered" meant that the T is not considered covered (correct, @sgrif?).

That said, I'm not sure if this is a problem. The RFC states (correctly) that adding any blanket impl must be considered a breaking change, where a breaking impl is any impl that contains an uncovered type parameter. This implies that if some parent crate were to add something like this:

impl<T> Remote1<T> for Box<_> { } // where _ represents any type at all

that would be a major breaking change. But such an impl would be needed to match the type above, since there is no way for the parent crate to name the local type.

UPDATE: I think @arielb1's comment here indicates why we do wish to reject the impl above. The problem is that some sibling crate could write impl<T> Remote1<T> for Box<SiblingType>. So this will have to be fixed. (In my text above, I hadn't considered conflicts between siblings.)

[sgrif]

Yes, it would be more precise to say "The `T` in `Box<T>` is not considered covered" -- As you mentioned in your update, we need to reject `impl Remote1<Local> for Box<T>`

…

On Fri, Aug 16, 2019, 8:41 AM Niko Matsakis ***@***.***> wrote: Hmm, writing up some new tests, I am finding that the current implementation is not working as expected! In particular, the behavior around fundamental types seems wrong, or else I am misreading the RFC. For example, this impl is allowed: impl<T> Remote1<Local> for Box<T> { } This is despite the text in the RFC which says: Once again, it is important to note that for the purposes of coherence, #[fundamental] types are special. Box<T> is not considered covered, and Box<LocalType> is considered local. I presume here that "Box<T> is not considered covered" meant that the T is not considered covered (correct, @sgrif <https://github.com/sgrif>?). That said, I'm not sure if this is a *problem*. The RFC states (correctly) that adding any blanket impl must be considered a breaking change, where a breaking impl is any impl that contains an uncovered type parameter. This implies that if some parent crate were to add something like this: impl<T> Remote1<T> for Box<_> { } // where _ represents any type at all that would be a major breaking change. But such an impl would be needed to match the type above, since there is no way for the parent crate to name the local type. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#63599?email_source=notifications&email_token=AALVMKZDGAM6NQUE7TBSTZLQE2375A5CNFSM4IL7QHLKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD4OZNXY#issuecomment-522032863>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AALVMK2G4AVWR6UNN2AAGY3QE2375ANCNFSM4IL7QHLA> .