Subtle breaking changes perhaps too easy with existing orphan rules?

Trying to better understand the nuances of the orphan rules, I came across how easy it is for trait implementations to be – potentially – breaking changes…

I’m aware of other kinds of “soft”/accepted breaking changes, like w.r.t method resolutions, but the thing discussed below seems less “soft” to me.


For context, let’s discuss quickly/roughly the general case of how trait implementations can or cannot be breaking changes.

Of course, adding blanket implementations (to an existing trait) is considered a breaking change; though in my mind, the term “blanket implementation” mostly meant those kinds of fully generic implementations that only the crate defining the trait can write. The reason why it’s considered breaking is that downstream crates can have written trait implementations that would be in conflict with the new blanket implementation, whose addition causes such downstream crates to stop compiling successfully.

On the other hand, non-blanket trait implementations (added for an existing trait and an existing type) are usually not breaking changes. This is deliberate; trait implementations are usually considered additive, and adding new stuff is not a breaking change. This also manifests in the fact that when a type doesn’t implement a trait (both the type and the trait not local to the current crate), you can usually not rely on this; the compiler will behave more like it doesn’t know whether or not the implementation exists, and not like it knows it doesn’t exist.

Example:

use core::fmt::Display;

trait Foo {}

impl<T: Display> Foo for T {}

struct MyStruct;

// non-overlapping, can rely on "MyStruct: Display" being false,
// because MyStruct is local
impl Foo for MyStruct {} 

// non-overlapping, but "Vec<()>: Display" is conservatively
// considered unknown instead of false
impl Foo for Vec<()> {}
// error message says:
//  = note: upstream crates may add a new impl of trait `std::fmt::Display`
//          for type `std::vec::Vec<()>` in future versions

Now here’s the problem case though where the rules enforced by the compiler do, in my mind, not really help as much as I’d hoped for for preventing breakage: I would not consider something like

impl<T> AsRef<T> for MyStruct<T> { … }

a blanket implementation; this kind of implementation can be done outside of the standard library (which defines AsRef). Still, adding this implementation is a breaking change, in some sense of the word “breaking change”: Downstream crates can write

impl AsRef<MyDownstreamStruct> for upstream::MyStruct<MyDownstreamStruct>

which is an impl that’s in conflict with the generic implementation above.

For further illustration, consider this playground.


So with this much information for context, here’s my questions

  • is this kind of issue known / is there prior discussion?
  • would you consider impl<T> AsRef<T> for MyStruct<T> { … } a “blanket implementation”?
  • is adding impl<T> AsRef<T> for MyStruct<T> { … } a “breaking change” that requires a major semver bump? If yes, this is probably widely unknown though, right? (Last time I checked the relevant guide, it didn’t really address trait implementations at all; not even blanket impls which are breaking changes most definitely.)

Further considerations:

  • The standard library did certainly add implementations of this form in the past, occasionally. For example From<T> for Mutex<T> was added in 1.24, while Mutex and From exist since 1.0. (If I understand the explanation here correctly, it might’ve been impossible to turn this kind of change into breakage before 1.41 though..)

  • If neither the type nor the trait are from the standard library, e.g. the trait and type are from different third-party crates, then adding such an instance will quite commonly only happen after both the trait and the type were already defined. Furthermore such implementations are often feature-gated. However, crate features should be additive, in particular they shouldn’t be breaking changes, so hiding such an implementation behind a feature seems problematic. If anyone does know a good example here, please tell me…

I just searched for more examples both in the standard library and also for anything between third-party crates; and it turns out these cases are sufficiently rare that I’m not surprised there haven’t been any problems yet. In particular, traits commonly implemented behind feature gates, such as certain popular traits from serde or rayon don’t have these kinds of generic trait arguments at all anyways.

2 Likes

I think that this is supposed to be disallowed unless upstream::MyStruct is declared as #[fundamental], though I’ve never fully understood the coherence rules.


Edit: The orphan rule relaxation section of the 1.41 release notes might also be relevant here.

Digging around a bit, I found this statement in RFC 2451:

Adding any impl with an uncovered type parameter is considered a major breaking change.

In your example, T is uncovered in the clause AsRef<T> (as defined by the RFC). Therefore, adding this impl is a breaking change (and probably also a “blanket impl”).

1 Like

The rules are essentially:

When facing an impl such as AsRef<MyDownstreamStruct> for upstream::MyStruct<MyDownstreamStruct> or such as impl<T> AsRef<T> for MyStruct<T>

First:

write down all the parameters to the trait, including (and starting with) “Self”, e.g.

for

impl<T> AsRef<T> for MyStruct<T> { … }

that’s

  1. MyStruct<T>
  2. T

whereas for

impl AsRef<MyDownstreamStruct> for upstream::MyStruct<MyDownstreamStruct>

the list is

  1. upstream::MyStruct<MyDownstreamStruct>
  2. MyDownstreamStruct

Second

Handle #[fundamental] types (Box<…>, Pin<…>, &…, &mut …), by replacing (or splitting up, in case of Box which has 2 arguments) any entry of the form Box<…, …>, Pin<…>, &…, &mut … with an entry containing just the type expression that’s the parameter. Repeat until no more #[fundamental] types exist (at the root of any type expression in the list).

Third

All the entries in the list now have at their root either a local type, or an external type, or they are a generic type parameter. If, in-order, the first entry that’s not an external type is

  • a type parameter, then the implementation is not allowed (assuming the trait is also external);
  • a local type, then the implementation is allowed.

(If all entries are external types, then it’s disallowed, too.)




Following this rule,

impl<T> AsRef<T> for MyStruct<T> { … }

is allowed if MyStruct is a local type, because the first entry in the list of parameters has MyStruct (a local type) at its root, and

impl AsRef<MyDownstreamStruct> for upstream::MyStruct<MyDownstreamStruct>

is allowed if MyDownstreamStruct is a local type, because the first entry is (at the root of the type expression) a concrete external type (with some arguments that don’t matter at all for this process) – so it’s skipped – and the second entry is the local type MyDownstreamStruct.


The rationale why these rules work in preventing overlapping impls (ignoring the extra step with #[fundamental] types):

Assume (for contradiction) that there is overlap that isn’t detected. Of course this can only happen in the first place between two trait impls (for the same trait) in two crates that don’t depend on each other, otherwise the overlap is detected during compilation anyways. The trait in question thus is defined by neither of the two crates, so it’s external when checking orphan rules for either of the impls.

Both impls are legal under the orphan rules, so they start with an arbitrary number of concrete external types, followed by a type local to the respective crate, and only after that are any generic type arguments allowed. In order both impls to be able to turn (by substituting generic arguments) into the same list of concrete types, there needs to be a generic type argument (at root position) in the same place in one overlapping impl where this (first) local type is in the other. But one of the two local types comes earlier, and the other impl is not allowed to have any generic type arguments (at root position) up to that point.

1 Like

Ah, I see, so apparently that’s the relevant change in 1.41 that the documentation of the From trait was referring to :slight_smile:

Alright, reviewing the RFC linked above, I had the suspicion that some of the kind of usage that broke was already allowed, and sure enough, in Rust 1.23, this compiles fine:

use std::sync::Mutex;

struct Foo;

impl From<Foo> for Mutex<Foo> {
   fn from(_: Foo) -> Self { panic!() }
}

while it obviously errors starting from 1.24.

1 Like

Ah, here’s a quote from that RFC:

Blanket Impl: Any implementation where a type appears uncovered. impl<T> Foo for T , impl<T> Bar<T> for T , impl<T> Bar<Vec<T>> for T , and impl<T> Bar<T> for Vec<T> are considered blanket impls. However, impl<T> Bar<Vec<T>> for Vec<T> is not a blanket impl, as all instances of T which appear in this impl are covered by Vec .

1 Like

Thanks for clarifying the rules; it’s nice to have them written out with a bit less formalism than the RFC uses.

In your example, though, they do depend on each other. Otherwise, downstream wouldn’t be able to refer to upstream::MyStructdownstream can only compile because the compiler can verify that upstream doesn’t contain a conflicting implementation. The defense against this is that adding impl AsRef<T> for MyStruct<T> is a semver-breaking change per the blanket-impl rule.

Right. And in this case, the orphan rules are only interesting for questions of what is or isn’t a “breaking change”; their main use-case, preventing undetected overlapping instances (which would be unsound!), does not apply. Not having well-defined rules here could cause unexpected breakage, but no unsoundness.