Proposal: relax orphan rules to allow generic implementations over types bound by a local trait

Several times in my practice I wanted to write generic impls like this:

impl<T: LocalTrait> ForeignTrait for T { .. }

One example is to generically implement io::Write for cryptographic hash functions which implement digest::Update. Another example is the following impls:

// `FromKeyNonce` and `FromKey` are defined in the `crypto-common` crate,
// while `FromBlockCipherNonce` and `FromBlockCipher` in the `cipher` crate

impl<T> FromKeyNonce for T
where T: FromBlockCipherNonce, T::BlockCipher: FromKey,
{ .. }

impl<T> FromKey for T
where T: FromBlockCipher, T::BlockCipher: FromKey,
{ .. }

But unfortunately Rust currently disallows them, even though (as far as I understand) they can not cause any issues. Would it be possible to relax the orphan rules to allow such impls or are there any potential issues, which I haven't noticed?

1 Like

I like the idea. I’m sure I’ve read it somewhere else before, too. Something that just came to mind: A feature allowing this would probably also need concepts like “disjoint traits” (or whatever you’d want to call it). For example, consider

crate a

trait A {}

crate b (depends on a)

trait B {}
impl<T: B> a::A for T {}

crate c (depends on a)

trait C {}
impl<T: C> a::A for T {}

crate d (depends on b and c)

struct D;
impl b::B for D;
// can’t also impl c::C for D;

fn d<T: B + C>() {
    // `B + C` bound does not make much sense
    // so probably a good idea to forbit it
}

// at least as supertraits
trait Tr: B + C {}



probably a good idea to forbit it

at least as supertraits

^^^ this would make a lot of sense in particular to prevent cases such as the following:

crate a

trait A {
    type Ty;
}

crate b (depends on a)

trait B {}
impl<T: B + ?Sized> a::A for T {
    type Ty = String;
}

crate c (depends on a)

trait C {}
impl<T: C + ?Sized> a::A for T {
    type Ty = Vec<u8>;
}

crate d (depends on a, b, and c)

struct D;
impl b::B for D;
// can’t also impl c::C for D;
// so `B` and `C` are kind-of “disjoint”

fn d<T: B + C + ?Sized>(x: Vec<u8>) -> String  {
    foo(bar(x))
}
fn foo<T: B + ?Sized>(x: <T as a::A>::Ty) -> String {
    x // compiles, using the generic implementation in `b`
}
fn bar<T: C + ?Sized>(x: Vec<u8>) -> <T as a::A>::Ty {
    x // compiles, using the generic implementation in `c`
}

trait Tr: B + C {}
fn bad_conversion(x: Vec<u8>) -> String {
    d::<dyn Tr>(x) // this is unsound
}

Or.. well.. at least the implementations for B and C would need to make a trait like Tr not object safe (so that there’s no type implementing it).


By the way, if this isn’t split up into multiple crates, Rust currently just rejects implementations like this

trait A {}
trait B {}
impl<T: B> A for T {}
trait C {}
impl<T: C> A for T {}
error[E0119]: conflicting implementations of trait `A`:
 --> src/lib.rs:5:1
  |
3 | impl<T: B> A for T {}
  | ------------------ first implementation here
4 | trait C {}
5 | impl<T: C> A for T {}
  | ^^^^^^^^^^^^^^^^^^ conflicting implementation

Being bound by a local trait isn't enough of a restriction, because that could literally cover everything:

impl<T: ?Sized> LocalTrait for T {}

Or for a more realistic example:

trait DisplayAsDebug: Debug {}
impl<T: Debug> DisplayAsDebug for T {}

impl<T: DisplayAsDebug> Display for T {
    // implement using Debug
}

If that were allowed, you would have types with multiple Display implementations -- both their own and this blanket one.

3 Likes

I thought that this rule was because of lessons learned from C++'s diamond inheritance problem. If the rule was relaxed, would rust suffer from the same issues? (Genuinely curious, I really don't know enough to have a guaranteed answer on my own)

2 Likes

I think the intention of this proposal would be that when there’s a generic implementation of an external trait using the local trait DisplayAsDebug, like

impl<T: DisplayAsDebug> Display for T {
    // implement using Debug
}

then the trait DisplayAsDebug itself would (at least effectively) fall under the same restrictions like external traits, i.e.

impl<T: Debug> DisplayAsDebug for T {}

is rejected.

In general, the compiler would at least need to ensure that no local implementation of the local trait, e.g. DisplayAsDebug implies (through generic impl’s such as the impl<T: Debug> D DisplayAsDebug for T one) an implementation of an external trait that is ill-formed w.r.t. orphan rules. And also it would need to ensure that every external implementation of the local trait, e.g. of DisplayAsDebug, cannot violate orphan rules of e.g. Display in implied/generic implementations; at least if DisplayAsDebug is public.

1 Like

What would happen below, where the only generics used are the proposed impl<T: LocalTrait> ForeignTrait for T?

// Popular crate #1 
trait DisplayAsDebugOne: Debug {}
impl DisplayAsDebugOne for Vec<usize> {}
impl<T: DisplayAsDebugOne> Display for T { /* ...left aligned... */ }

// Popular crate #2 
trait DisplayAsDebugTwo: Debug {}
impl DisplayAsDebugTwo for Vec<usize> {}
impl<T: DisplayAsDebugTwo> Display for T { /* ...right aligned... */ }

// Somewhere in my project that uses both popular crates
fn foo() {
    let v = vec![0usize; 10];
    println!("{}", v);
}

I would imagine the error would be something like:

trait DisplayAsDebugOne: Debug {}
impl<T: DisplayAsDebugOne> Display for T { /* */ } // [ref]
impl DisplayAsDebugOne for Vec<usize> {} // Error: Possibly Overlapping Impls
 // Note: `Vec<usize>` may eventually impl `Display` in it's origin crate,
 // which would overlap with the impl for `DisplayAsDebugOne` [ref]

So is it fair to say that no implementations disallowed today would be allowed, and that the underlying goal is really a way to limit implementations to local types?

I.e. would something like this also suffice?

impl<T: Debug> Display for T
   where T: #IsLocalToThisCrate
{ /* ... */ }
1 Like

In my view, this would be disallowed. It’s implementing Display for Vec<usize>, which isn’t okay. In other words / in more detail: following my earlier example,

the impl DisplayAsDebugOne for Vec<usize> {} implementation would be rejected, too, since DisplayAsDebugOne would, in the presence of the generic impl<T: DisplayAsDebugOne> Display for T implementation, fall under the same restrictions as if it was an external trait. Cannot implement an “effectively external” trait (DisplayAsDebugOne) for an external type (Vec<usize>).

1 Like

This seems more restrictive than what I would like. Surely, a trait like

trait DisplayAsDebug: Debug {}

impl<T: DisplayAsDebug + #IsLocalToThisCrate> Display for T {
    // implement using Debug
}

is usefult to reduce boilerplate code for implementing Display for a bunch of local types. But I’d imagine that a user of the trait offering

pub trait DisplayAsDebug: Debug {}

impl<T: DisplayAsDebug> Display for T {
    // implement using Debug
}

could also use such a helper trait for saving lengthy Display implementations. In the user’s crate, implementing DisplayAsDebug for a type would pretty much be the same as using e.g. calling a macro for shortening the trait implementation of Display just with better type checking and feeling way more neat IMO; in particular it would have to fall under the same restrictions as trying to implement Display directly. If the user also depended on yet-another-crate providing its own YetAnotherDisplayAsDebug trait, there couldn’t be an implemention of both DisplayAsDebug and YetAnotherDisplayAsDebug for they’re implying conflicting implementations of Display.

2 Likes

I did some reading up and more thinking about this proposal:

// You have a local trait:
trait Proxy;

// And you have a blanket impl of a foreign trait,
// but it is bound by the local trait:
impl <T: Proxy> ForeignTrait for T { ... }

// That implementation make the trait special.

// Now, my crate can only implement Proxy for local types
//   (as if `Proxy` was defined in a parent crate)
// Child crates can also implement Proxy for their local types
//   (in which case the blanket impl will apply too)

I'll refer to this proposed pattern as a proxy trait, which implements foreign proxied traits, and the crate it is in is a proxy crate.

I thought about this proposal mainly in terms of the reasoning used to create the orphan rules. Namely, the reasoning was concerned with balancing the ability of child crates to implement the traits which they need to, and the ability of parents crates to evolve without making breaking changes all the time. See the Background section below for how things evolved. So the main concerns were child crates, parent crates, and what parent traits can and cannot do without breaking child crates.

Becoming a proxy trait is a breaking change

Proxy traits are blanket implementations, and creating a new blanket implementation is a breaking change. This is pretty obvious with a little thought: If I make my existing trait a proxy trait, any child crate that implemented both the proxy trait and the proxied trait themselves will break.

Proxy crates play a new role that constrains child crates

Technically, a proxy trait constrained to local types would not change what implementations can exist. Everything you could do with such a proxy trait, you can do today, though it would involve a lot of repetition. However, the proxy crate is a third type of crate in addition to parents and children, with new abilities, and these abilities impose new restrictions on child crates.

If I am a child crate of a proxy crate, and I implement the proxy trait, I give up the ability to implement the proxied traits. And the proxy crate has the ability to change the implementation of the proxied traits for my local types, even though neither the types or the traits are local to the proxy crate.

You may say "so what?", perhaps thinking of one of the example cases that was discussed:

trait DisplayAsDebug: Debug {}
impl<T: DisplayAsDebug> Display for T { ... }

"Giving up" the ability to implement Display on my own types would be the entire point of implementing DisplayAsDebug in my child crate -- I want the proxy crate to take care of things for me. But consider this example from the OP:

// FromBlockCipher is the (local) proxy trait
// FromKey is a foreign trait
impl<T> FromKey for T
where T: FromBlockCipher, T::BlockCipher: FromKey,

In this case, the proxy trait serves a purpose separate from just being a proxy. There may be reasons that I, a child crate, want to implement FromBlockCipher on my types without giving up my ability to implement (or ability to never implement!) FromKey. This is a new constraint that child crates may find themselves facing. The effect is similar to that of a negative trait bound.

Additionally, I cannot implement both ProxyTraitA from crate A and ProxyTraitB from crate B, if the intersection of their proxied traits is not empty. This is a new kind of conflict between "sibling" crates.

There may be an argument for limiting proxy traits to have empty bodies, so that their only purpose is proxying. And perhaps a further argument for not allowing proxy traits in trait bounds (to avoid trait UsefulTrait: ProxyTrait { ... }). Or perhaps trait implementations are just the wrong approach and instead some sort of macro marker or similar should be considered. (I haven't given these guards against conflicts too much thought yet.)

Relationships between proxy crates and parents

A proxy trait "acts like a foreign trait" in the sense that you can only implement it for local types. Where exactly does this fall in the crate hierarchy? Consider this:

trait Proxy;
impl<T: Proxy> ParentOne for T { ... } // as if in ParentOne's crate
impl<T: Proxy> ParentTwo for T { ... } // as if in ParentTwo's crate

From the perspective of the current rules, it is as if each proxy implementation takes place in the crate of the proxied trait, and as if all of those parent crates had a common ancestor crate where trait Proxy was defined.

So in some sense, the proxy create is creating some sort of new common ancestor for its parent crates. But only the proxy crate's children can see it. I couldn't come up with a scenario where this breaks things or creates new ways of breaking things, but I'm not terribly confident about that. I'm curious to know what other people think.

What's the color of the boat house at Hereford?

If proxy traits come to be, I feel they should have their own distinct syntax or a keyword to call out their proxy-ness. I feel their special behaviour would be too surprising without it; you can't look at a blanket implementation and tell it's a proxy implementation without knowing the locality of the traits in bounds and the trait being implemented. Even if you know those things, you would have to think of it.

Background on the current orphan rules

  • RFC 2451 lays out the orphan rules in detail as they are today.
  • It's an expansion of RFC 1023, which changed the rules in order to give parent crates the ability to evolve without breaking child crates.
  • RFC 1105 details what is and isn't a major breaking change.
    • RFC 2451 also corrects RFC 1105 by pointing out that a blanket implementation is a breaking change. In non-exact surface terms, a blanket impl is an impl for T (but not LocalType<T>). The actual rules are more involved; see RFC 2451.
    • Be careful as this correction has not been made applied to RFC 1105's text.

Thanks for reading

I know this was a long one.

Incidentally, @newpavlov -- are we still on topic? :sweat_smile:

2 Likes

Would these blanket proxy impls be allowed for fundamental types?

trait ProxyCollection { ... }
impl<C: ProxyCollection> IntoIterator for C { ... } // IntoIter
impl<'a, C: ProxyCollection> IntoIterator for &'a C { ... } // Iter
impl<'a, C: ProxyCollection> IntoIterator for &'a mut C { ... } // IterMut

IntoIterator also has its own blanket impl, which might disqualify it from this proposal altogether, but if so feel free to pick a better example. :slight_smile: