More flexible coherence rules that permit overlap

[nikomatsakis]

There is a need for more flexible coherence rules, and in particular a way to permit overlap in some cases. There are numerous proposals for how to go about achieving that. Here is a summary:

• Specialization
• Negative bounds (e.g., RFC Negative bounds #586)
• Crate-local or scoped impls

Note that a prime concern here is forwards compatibility. See RFC #1023 (and this internals thread) for details.

RFCs and other links:

• Negative bounds #586
• Mutually exclusive traits #1148
• A modest proposal around negative reasoning and auto traits

[pnkfelix]

A discussion with niko today revealed that a naive specialization feature could cause the drop check rule (RFC 769) to break.

In particular, if we allow one to:

1. define a function/method m that is defined with input x:T for all types T,
2. call m on self.0 within the Drop implementation for some type D<F>(F) that, under the drop check rule, is not subject to any ordering constraints since it has no lifetime parameters and F has no bounds, and
3. specialize that method m to a particular type T = &'a Stuff, that actually dereferences through the &'a reference.

Then one could end up in a situation where the drop implementation for D ends up accessing data that has expired via m(self.field).

[withoutboats]

Hi.

I think negative bounds as discussed in RFC #586 would be very valuable, with the following modification to avoid the problem of backwards incompatibility: impl<T: !Foo> does not mean that T doesn't impl Foo, but that T impls !Foo (which seems like a plain-text reading of the code when written out like this). A T which does not impl either Foo or !Foo therefore does not meet the bound for either impl<T: Foo> or impl<T: !Foo>. This would require also that negative impls be possible for all traits, not only default traits, so that one could write e.g. impl<T> !Num for Vec<T> {}, indicating a contract that Vec is not a number (without as much semantic overhead of coming up with a whole concept of contracts).

Doing this would limit the usefulness of negative bounds somewhat (because T: Foo and T: !Foo would not cover the whole range of types), but I think would be well worth it to avoid the rather enormous backwards compatibility hazard discussed in the prior RFC.

It might be worth doing, also, that if there exists a trait Foo: !Bar, impl Foo for Quux implies impl !Bar for Quux, but requiring the explicit declaration is probably better.

Types defined in std should negatively implement various traits where a backwards compatible commitment to not implementing that trait exists. This is a backwards compatible change.

Adding negative bounds to traits which should not logically cohere (e.g. Integer and Float or Signed and Unsigned) is also a good decision. This is not a backwards compatible change, but the code it would break seems like it was 'in bad faith' so to speak and if this change were done early enough I don't know how serious of a violation of semver it would be to break backcompat for something like that. More importantly, though I can think of several traits in unstabilized crates that are logically incoherent, I can't think of any traits that are stable in 1.0 that ought logically to have a negative trait bound with any other trait.

Some sort of specification system would be useful in addition to this for a lot of the use cases you've highlighted, but this alone would open up a lot of more straightforward cases, such as enabling new traits to 'piggyback' on standardized or otherwise commonly imported traits without violating coherence rules (e.g. the trait DoshDistimmer could be implemented such: impl<T: Integer> DoshDistimmer for T {} as well as impl<T: Float> DoshDistimmer for T {}, and (since Vec<T> impls !Num) impl<T> DoshDistimmer for Vec<T>).

[withoutboats]

Here's an interesting case:

trait Foo { }

trait Bar {
    type Baz;
}

impl<T> Foo for T where T: Bar<Baz=u32> { }
impl<T> Foo for T where T: Bar<Baz=i32> { }

This is currently incoherent, because the coherence rules do not allow us to infer that the intersection between Bar<Baz=u32> and Bar<Baz=i32> is empty. However, I believe that this would be a sound rule to add to the coherence system:

T ≠ U → Trait<Type=T> ∩ Trait<Type=U> = ∅

In my own use case for this, I want to provide blanket impls for functions that return one of two different types.

[Centril]

cc #2451.

[ghost]

I am really really new to Rust and somehow navigated myself to this issue. It seems to have remained open for a few years.

I'm still learning the ins and outs of Rust's trait system, but I am already interested in how this rfc will turn out.

Any updates?

[Ixrec]

@ThomasKagan note that this is an issue, not an actual RFC. I'm not aware of any active proposals in this space (it certainly doesn't fit with the 2019 Roadmap).

For an unofficial attempt to summarize in one coherent and novice-friendly place why this is such a hard problem and all the seemingly obvious answers don't actually work, see https://github.com/Ixrec/rust-orphan-rules

[ghost]

Thanks for the link! Definitely curious to see how it pans out

[blakehawkins]

Sorry to "ping" on this, just wanted to share another concrete use case.

I would find it very useful to use num-traits so that I can implement something like this:

impl <T> MySummer for Vec<T> where T: PrimInt {}

impl <T> MySummer for Vec<T> where T: MyAddition {}

or something like:

impl <T> MySerialiser for Vec<T> where T: PrimInt {}

impl <T> MySerialiser for Vec<T> where T: MySerialiser + !PrimInt {}

I believe these are each not really possible at the moment, which leads to a lot of macro usage

From the peanut gallery, it seems like if the more general problem in this issue is hard to make progress on in ~8 years, maybe it would be worth reopening the (seemingly simpler) #1148? (I appreciate that it may in fact not be simpler!)

[dhardy]

So, I see three aspects to this issue:

1. Specialization is about a strict sub-set of a "more general" set of impls with another. This is a highly specific tool that has several possible uses (mostly optimisations I think, though behaviour changes are also possible). It doesn't affect coherence since it neither adds nor removes impls, merely replaces them.
2. Negative reasoning is about making coherence checks less restrictive via introduction of explicit negative impls and bounds (possibly also requiring "sealing" to prevent all additional impls).
3. Support multiple blanket impls with differing bounds for traits #442 and Limiting upstream crates may add new impl of trait in future versions #2758 appear to be about making coherence checks less restrictive by simply reducing the scope such that it no longer reasons about whether additional impls upstream could cause breakage downstream.

Aside: coherence is well defined here. In short, assuring that each type has at most one impl of each trait, and the addition of a new impl upstream cannot cause breaking changes downstream (at least, not through multiple impls of the same type-trait pair).

Points 2 and 3 are about solving the same problem from different directions. It is difficult to argue which approach is better or more appropriate for Rust; although the language does have a tradition of a complex and rigid error checking system, there are other areas that Rust doesn't even try to prevent semver breakage (e.g. by allowing glob imports).

Point 1 (specialization) is, as best I can tell, a completely unrelated problem (unless the scope changes significantly from the merged RFC), and thus should not be a blocker to progress on this issue: more flexible coherence rules that permit overlap. (Also, in my biased opinion, specialisation is the less important of the two issues.)

How can we progress this issue?