Orphan rules are stricter than we would like

[nikomatsakis]

The current orphan rules (described as "covered first" in my blog post) are too restrictive in some cases. The purpose of this RFC issue is to catalog cases where the rules are tighter than we would like and to also point at possible solutions.

---

Scenario. Type parameters restrict our flexibility

In the discussion around the try trait in #1718, we realized that the orphan rules would prohibit one from adding an impl like this:

impl<T,E> Try<Poll<T, E>> for Result<T, E>

This is sort of annoying because if there were no type parameters involved, the impl would be permitted:

impl Try<Poll<(),()>> for Result<(),()> // OK

This roughly corresponds to the impl<T> BorrowFrom<Rc<T>> for T example from the Little Orphan Impls blog post. As that blog post describes, this is an artifact of introducing ordering into the algorithm; the post describes various alternative rules, notably the "covered rule", that would permit both of these impls, but at the cost of other kinds of rules.

---

Scenario. Wanting to implement a trait where the output type is not in current crate.

@Manishearth describes wanting to add an impl into libstd like so:

impl Add<str> for str {
    type Output = String;
    ...
}

By rights, this impl should live in libcore, since all the input types are in libcore, but the output type is defined in libstd, so of course it cannot.

---

Scenario. Optionally derive traits if desired by others, but without adding a required dependency.

A common example is that my crate foo defines a type Foo which can be serialized (e.g., using the serde crate). However, I do not want to add serde as a required dependency of foo. Currently, best practice is to define a Cargo.toml feature (e.g., with_serde) that adds a dependency on serde and includes the relevant impls. But this is a lot of manual work. Another example is how the rayon crate exports the ParallelIterator trait; other crates, like ndarray, might want to implement those, but without forcing a dependency on rayon on others

Proposals targeting this scenario:

• integrating with cargo workspaces, by @nikomatsakis
• automatic features, by @withoutboats

This scenario was also described in #1553.

Other scenarios?

Please leave comments and we can migrate those descriptions into this header.

[withoutboats]

The solution I like to the third scenario is to enable a greater variety of blanket impls through specialization & mutual exclusion.

For example, if there is a Sequence type in std serde had an impl<T> Serialize for T where T: Sequence, and Foo is a sequential type which implements Sequence, it now also implements Serialize.

Traits like Sequence can form a "pivot" between two cousin libraries.

This has pretty bad limitations when it comes to things like ndarray and rayon because the high performance expectation probably necessitates some sort of API access that wouldn't be contained in that ancestor trait (possibly even some unsafe code).

[oli-obk]

impl<T> Serialize for T where T: Sequence

this doesn't work, because we'd also want to have

impl<T> Serialize for T where T: Map

We already ran into this when we tried to

impl<I, T> Serialize for I where I: Iterator<Item = T>, T: Serialize

[withoutboats]

@oli-obk It does work with mutual exclusion, by making it incoherent for a single type to implement both Map and Sequence. That's exactly the feature I'm proposing. :-)

[Ericson2314]

I've mused a kind of lattice system where if one uses crate foo with some type, and another crate bar with this trait, you must also use another (the "least upper bound" of foo and bar) containing orphan impls involving foo's type and bar's trait.

The motivation here is sort of a collaborative look at the expression problem: It's sort of arbitrary to say whether the trait or type should own the impls when its a joint endeavor. The traditional approach to the expression problem was about allowing everyone to work in isolation, which is what made it hard/impossible to resolve, here the idea is since the author of the type and the trait both have a stake, they both should be able to write the impl. Ideally this would be coupled with a jointly-owned crate on crates.io they both could publish.

I don't have a detailed design or informal argument that this is sound, but as this has long been my rough thinking on the problem from a software engineering perspective, and I figured I should share it.

---

For the String case (outputs not inputs more broadly), core should probably say "I defer to a crate called collections" giving it a non-orphan exception, along with maybe an input signature the "deferred impl" must obey (for purposes of core being able to define other blankets).

[Manishearth]

integrating with cargo workspaces, by @nikomatsakis

I'm in favor of a boundary that isn't a crate boundary and contains multiple crates but is logically the same "project", where a different set of rules apply etc. I have never really pushed for this but I have often talked about separating the notion of a package from the notion of a crate.

However, this may only further muddle our already-confusing crate/mod system.

[bluss]

I'd like such a wider boundary, a way for a parent crate to delegate to other crates, so that they are permitted to implement traits for types in the parent crate “in its stead”.

Something like this:

[package]
name = "ndarray"
trait_delegate = ["ndarray-serde"]

Now ndarray-serde will depend on ndarray and is allowed to define foreign traits (serde::Serialize in this case) for the types in ndarray.

[strega-nil]

@bluss

I'd like such a wider boundary, a way for a parent crate to delegate to other crates, so that they are permitted to implement traits for types in the parent crate “in its stead”.

I would rather have a way for a child crate, of two parent crates, to define interop code. This means that ndarray doesn't have to know all of the crates that will be interopped with it; there's just an interop crate. This crate would have metadata, saying that it's for interoperability between two crates, and may be decided upon by the final consumer, or any link up the chain. For example, say I want to interop ndarray and serde with the crate ndarray-serde. ndarray-serde would look something like:

[package]
name = "ndarray-serde"

[interop]
ndarray = "0.N"
serde = "0.M" # note, these must be the versions in the final binary, and imply dependencies

[dependencies]
ndarray = "0.N"
serde = "0.M"
ndarray-serde = "0.L"

that was a lot of "interop"s.

[Manishearth]

FWIW the conditional features rfc eases the interop use case (but doesn't solve it completely)

[withoutboats]

@Manishearth and I talked about orphan issues tonight, and he gave a good example from servo, which I admit I may have badly misunderstood. But based on my understanding, I discovered a pattern for 'smuggling' code for foreign types. There are some restrictions on this pattern, but it seems quite powerful.

An example is FFI conversion. Maybe you have a single crate which defines all of your FFI types (possibly in an automatically generated fashion), and its shared by many other crates in your project. So you want all your FFI types to implement from/into their real types, and for your real types to implement from/into your FFI types. This runs into orphan rules because your FFI library doesn't know about the real types, because its a shared dependency of all the crates containing the real types.

Here's a way of defining those traits (and a 'smuggler' impl) which totally compiles and works (and it blows my mind):

trait Real: Sized {
    type Ffi: Ffi<Self>;
    fn from_ffi(source: Self::Ffi) -> Self;
    fn into_ffi(self) -> Self::Ffi;
}

trait Ffi<T>: Sized {
    fn into_real(self) -> T;
    fn from_real(real: T) -> Self;
}

impl<T> Ffi<T> for T::Ffi where T: Real {
    fn into_real(self) -> T {
        T::from_ffi(self)
    }
    
    fn from_real(real: T) -> T::Ffi {
        real.into_ffi()
    }
}

You can implement the Real trait for all the real types locally where they live, and declare their FFI type to be the foreign type from the FFI library, and that FFI type magically gets the Ffi trait implemented for it.

I was doubtful that this could be coherent, but because Ffi is parameterized over its Real, implementing it for an associated type just works!

You can actually smuggle arbitrary code (not only conversions) into the FFI crate by just having it delegate to a function on the Real trait.

[glaebhoerl]

@Ericson2314

I've mused a kind of lattice system where if you use a crate with this type and another with this crate, you must also use another (their "least upper bound") with the impl.

Could you please rephrase this, or maybe with example code? I confess I don't understand at all what each "this" and "another" is referring to.

[bluss]

The automatic features RFC (did you mean this one @Manishearth?) seems like it doesn't solve any of the hard issues around either version coupling or orphan rules. It is like a convenience around what we can already achieve, while we want something that really bends the current rules a bit.

[Manishearth]

did you mean this one @Manishearth?

yep. used to be called "conditional dependencies", now is "automatic features", mixed the names.

seems like it doesn't solve any of the hard issues around either version coupling or orphan rules.

Yeah, it doesn't, but it smoothens some of the more common annoying use cases.

[Ericson2314]

@glaebhoerl sorry, did a sloppy job writing on my phone. I've gone back and cleaned up that post so it should be understandable now.

[ztrash]

The current orphan rules (described as "covered first" in my blog post) are too restrictive in some cases.

I wonder if you would consider a way to make binary operator traits like this work:

impl<T> Mul<Matrix<T>> for T

It would be a much cleaner way of implementing these operators for numerical programming.