Forward compatibility hazard from coherence rules

[nikomatsakis]

The current coherence rules are too smart. I think we should consider adding some limits to rein it in. In particular, imagine that crate A defines:

pub struct Foo { .. }

And crate B then defines:

extern crate A;
trait MyTrait { }
impl<T:Clone> MyTrait for T { }
impl MyTrait for A::Foo { }

This is currently accepted today, I believe. However, I think it should not be, because it means that now crate A cannot add an impl of Clone for Foo for fear of breaking crate B.

My proposed fix is to modify the coherence check so that you can't assume that a type from another crate won't implement a trait from another crate.

cc @aturon

[nikomatsakis]

triage: P-backcompat-lang (1.0 beta)

[arielb1]

This still won't solve all of these cases. An impl<T: Copy> Clone for T by libcore would still give you coherence problems (it would also give libcore coherence problems, so just assume that tuples etc. aren't part of libcore). However, it would make non-blanket impls backwards-compatible.

[nikomatsakis]

So I've been putting some thought into this and I just want to write out the current state of my thinking. As @arielb1 pointed out, the problems here run a bit deeper than I originally considered. Basically, in a coherence like system, almost any impl potentially imposes a kind of implicit negative constraint on the ancestor crates. Let me elaborate some of the scenarios.

The problems are related to the orphan rules. In particular, the orphan rules require that a local type appear somewhere in the impl, but they don't require that local types "cover" remote types (so, e.g., Box<LocalType> is OK, even though the remote type Box is "uncovered"). (I'm defining "cover" to say that a type constructor covers the types used as its type parameters; so in the type (X<Y>,Z), X covers Y but not Z.)

Hazards arising inherently from coherence

Basically no matter what, there are always forward evolution hazards, particularly if a crate attempts to add blanket impls for an existing trait. Imagine we have a crate A that defines Trait and a crate B that defines some type Type. Even the most local impl by B restricts how crate A can evolve:

impl A::Trait for B::Type { } // in crate B

That impl prevents A from adding an impl like:

impl<T> A::Trait for T where .. { } // in crate A

The only exception is when the new impl in A includes some where clause referencing a trait that is newly added in A and where we can be sure that downstream types do not yet implement this trait.

Similarly, because of how the orphan rules are structured, crate B might have impls like:

impl A::Trait for Box<B::Type> { } // in crate B
impl A::Trait for &B::Type { } // in crate B

Naturally these would prevent crate A from adding blanket impls like:

impl<T> A::Trait for Box<T> { } // in crate A
impl<T> A::Trait for &T { } // in crate A

(The same proviso about where clauses referencing new traits applies.)

Note that "blanket" impls do not have to be involving smart pointers. For example, a relevant example is that libstd might want to implement Copy for the range types in the future:

impl<T:Copy> Copy for Range<T> { }

Unfortunately, that could conflict if some downstream user had manually implemented Copy for ranges over their types:

impl Copy for Range<MyType> { }

So basically the only thing that a crate can safely add is an impl with no generic type parameters in the local type:

impl Copy for SomeType { /* note: no generic type parameters at all! */ }

Mitigation strategies for the "inherent" conflicts of coherence

One interesting aspect of these conflicts is that they are always "intra-trait". What I mean is that you wind up with a coherence violation because the ancestor and children creates both provide an impl of the same trait. This implies that one way to address this might be some sort of specialization-based design. There are lots of design questions to address here, but the basic idea would be that the ancestor trait can add a "low priority" blanket impl that subcrates can override. This could be added even after other crates may have already created more specialized impls without creating a disturbance.

In the particular case of Copy and other marker traits, we might also consider looser coherence rules because there are no methods. But I think we'd want to be careful about how we do this, because if there is no opt-in, then people would be prevented from adding methods to empty traits, which is another extension vector we may (or may not) want to permit.

Hazards arising more specifically from negative reasoning

These hazards can arise somewhat indirectly as well, due to the negative reasoning that coherence uses. This was the issue I originally started talking about. For example, I might implement a trait like:

trait Foo { .. }
impl<T:Copy> Foo for T { .. }
impl<T:Copy> Foo for Range<T> { .. }

In this case, Range is a type defined in libstd (and hence not local). For this set of impls to be legal, Range<T> must not impl Copy, or else those two impls would overlap. This implies that if libstd tried to add impl<T:Copy> Copy for Range<T> in the future, we'd cause a downstream error.

Mitigation strategies for negative bounds

Interestingly, specialization doesn't help here. Whereas before the problem was that we created overlapping impls within a trait, in this case the problem is that growing a trait at all induces overlapping impls for another trait. Specialization can help us resole the first problem -- which impl to use within the first trait -- but it doesn't help for the second case, because libstd cannot change the set of impls for the trait Foo.

To be clear, specialization might help if we had some rules such that the impls on Foo were inherently prioritized, such that the impl for Range<T> took precedence over the one for T or vice versa; but this seems very dependent on the specialization design. That is, specialization could allow the downstream crate to protect itself against the hazard of Range becoming Copy, but it doesn't necessarily allow the upstream crate to protect others, which is what we want.

Limiting negative reasoning

My initial proposal was to imply a sort of orphan-rule-like restriction on negative reasoning. The intuition is that you can apply negative reasoning to types in your own crate, but not upstream crates, because those upstream crates might grow. But the devil is in the details here. We presumably want to require that we can only rely on T : !Trait if either T or Trait is local, but just what does local mean for a type?

In particular, if use the definition from the orphan rules, then something like Box<A::Type> (or Range<MyInt>) is local, and then if the upstream crates attempts to add a blanket impl like impl<T:Copy> Copy for Range<T>, they will still create a conflict.

If we use a more stringent definition, say that all remote (or structural?) types must be covered by local types, then we definitely rule out patterns that are in use. The problem I encounter right now in libstd derives from the alloc crate:

impl<E> FromError<E> for E
impl<'a, E: Error + 'a> FromError<E> for Box<Error + 'a>

Here the problem is that the type Error is not local to alloc, and hence the predicate that Error : !Sized is not considered satisfied. It may be worth special-casing Sized just to see where it leaves us.

[nikomatsakis]

It may be worth special-casing Sized just to see where it leaves us.

Note in particular that things like Trait : Sized can never, ever hold.

[nikomatsakis]

(Also, note that Sized is one case where we do not require opt-in to acknowledge that you cannot change a type from sized to unsized without breaking code.)

[nikomatsakis]

Also, I wrote:

One interesting aspect of these conflicts is that they are always "intra-trait".

Is this true? I think it's true but perhaps this is a failure of imagination on my part?

[nikomatsakis]

I investigated a bit more -- adding special rules around Sized helps, but there are still problems around the FromError trait because of this impl:

impl<'a, E: Error + 'a> FromError<E> for Box<Error + 'a> { }

which conflicts here:

impl<E> FromError<E> for E

in particular, we can't rely that Box<Error> : Error does not hold.

[nikomatsakis]

More investigation. I added a flag I can use to disable the check on particular impls so that I could keep going and uncover all potentially problematic combinations.

Here is another example conflict, this time in Iterator:

• impl<'a, T> IntoIterator for &'a BinaryHeap<T> where T: Ord
• impl<T> IntoIterator for T where T: Iterator

I believe this is considered a conflict because &BinaryHeap is not local (although BinaryHeap would be). This conflict could not be resolved by collapsing the facade, since we naturally expect users to define their own iterable types.

It could be resolved by considering &T to be local if T is local, but this creates hazards (you cannot compatibly add a blanket impl for all &T -- which might be ok). Somewhat more annoying is that if we chose to use the full local rules, then Foo<T> would be local if T is local, which implies that we also could not add impls for any existing generic type Foo<T>, which feels less ok.

UPDATE: To clarify, I wrote &T above, I meant it as a shorthand for Smaht<T> in some sense.

[nikomatsakis]

Here is the branch that implements the experimental revised version:

https://github.com/nikomatsakis/rust/commits/issue-23086-coherence-forward-compat

the HEAD^ commit, in particular, includes the impls that had to be tagged to make progress.

[pnkfelix]

(this can be punted from beta, but we hope a last minute design/fix that niko is working on will land in time for beta)

[alexcrichton]

Turning this into the tracking issue for RFC 1023