I want to revive a discussion and an idea of @nikomatsakis related to orphan rules for traits. Currently, external traits cannot be implemented on external types. As a new Rust user, when reading this in the book I thought, “Oh, that’s very restrictive. Ah well, I will accept that it is necessary and see how it goes. I’m sure it rarely poses a problem!” Well, I ran into it almost immediately.
The most common reason cited for the orphan rule is the hashtable problem, however no one seems to mention why the solution proposed therein is undesireable. It looks like it was briefly mentioned in a previous discussion related to trait specificity over parametrized types, but tabled for the moment as too large a change when trying to get Rust to 1.0.
I would like to open discussion on this again. Let me first present the situation as it stands:
- Crate A defines a public trait T.
- Crate B defines a public struct S.
- Crate C wants to implement T for S.
Current orphan rules prevent this, even though it would be completely coherent.
Various proposals have been suggested for this problem:
- Fork crate A or B and add the trait implementation.
- Contact the owners of either crate with a pull-request to implement the trait T on S.
- Create a newtype, wrap and unwrap struct S with the newtype whenever you need this trait.
- In certain cases, crates may have implemented workarounds.
Problems With Current Solutions
- Fractures the ecosystem and adds the overhead of keeping your module up to date with the main crate. In addition, it duplicates effort among developers who may also need this functionality.
- Requires crate A and B to be aware of one another, and increases the requirements to keep their module up to date with some external crates. As the number of crates in the ecosystem grows this is totally unsustainable.
- Depending on the amount of of custom types within S, this may be highly nontrivial. In addition, it means that one ends up reimplementing a large amount of functionality (for example, a simple
derivewould not be possible on the newtype, which means a custom implementation would be necessary).
- This essentially is a macro for the newtype idiom, and requires duplicating the struct within crate C. It saves you from having to reimplement the trait, but it requires more work on the part of crate A to provide such a macro and still carries with it limitations which prevent interoperability with other crates.
Part of the rationale for the orphan rules has gotten conflated with an argument about breaking changes (A or B providing an implementation would not be considered a breaking change, however it would conflict with crate C’s implementation). The solutions below will address this in such a way that fixing the breaking change would be as simple as handling a naming conflict, which already is a breaking change for crates which is not tracked by semver presumably because the fix is very simple (i.e. namespacing). Thus, for the time being, let us ignore this argument.
If we ignore the possibility of breaking changes due to future implementations in crate A or B, then the above can be allowed to compile without issue. There is only one
impl T for S defined, if it had been copied into crate A or B the program would have compiled without issue, so the fact that it happens to be external to the trait and struct definitions is irrelevant. There is no ambiguity for the compiler to deal with.
Simple Solution for Conflicting Traits
How should we handle something like this:
- Crate A defines
impl T for S
- Crate B defines
impl T for S
- Crate C wants to use both A and B
(Here trait T and struct S can be defined in some other external crate, it’s rather irrelevant. For a concrete example, refer to the hashtable problem, where A and B would be Module1 and Module2.)
As a simple starting point: compilation would return an error due to the ambiguous impls, and recommend the user specify which impl should be used in Crate C with some syntax such as
prefer impl T for S from A
The simplest effect of which would be to make this equivalent to commenting out the
impl T for S in crate B entirely, forcing coherence by making this the only implementation. It’s basically been reduced to the situation above.
Objection: what if B depended on the specific functionality in impl T for S?
For example, what if, in the hashtable example, B tried to access elements of the has table not by using
get, but instead decided to directly manipulate the underlying data since it was assuming the
impl it had defined was the only way it would have added the data? The answer, in this case, is one of code design. It’s basically the same argument for why getters/setters are preferred to direct access. A trait should fully capture all aspects necessary for the activity it is abstracting, and access to the data should always go through the trait.
Advanced Solution for Conflicting Traits:
impl per instance
Still, for various reasons, it might be useful to allow for two implementations without having to also clone the type. If I understand it correctly, this is the solution proposed by @nikomatsakis in the hashtable problem. In short, my understanding is that it would work like this:
- If an
implcan be unambiguously determined (by whatever set of specificity rules are in place) then no additional syntax would be necessary. In particular, this means that implementing this change would be backwards-compatible with existing code.
- If multiple
impls are present, and it is ambiguous which one applies, then the compiler would return with an error advising you to specify it. For example
S:A::Twould specify a type which uses the
A. This might seem noisy, but type aliases could be used to quiet it down.
For full details on the proposal, please read the excellent writeup here!
I would advocate that having a way to set the default for a given type would be handy. For example, the
prefer impl T for S from A as suggested in the “simple solution” above.
Implementing this change is backwards compatible with existing rules. In particular, the set of source code which compiles corresponding to the orphan rules is a subset of that which compiles with the simple solution, which is a subset of that which would compile with the advanced solution.
Reasons for Implementation
- As mentioned, this seemingly arbitrary restriction was very offputting when initially learning Rust, and based on various blog posts explaining why it is necessary I would guess it is a stumbling block for others as well.
- Existing orphan rules still do not protect against external crates implementing external parametric traits, and this has happened in practice.
- The exact specificity rules which determine which particular
implapplies are rather complicated. Implementing this is orthogonal to any specificity rules, as they would only effect the choice of “default”, and therefore it could be seen as a way to punt the decision of which
implto use to the user, postponing the need to upgrade the rust compiler’s ability to automatically choose a reasonable default.
- The list of recommended traits that modules should derive on public structs is already quite long. As new crates are added this will just get longer, and making recommendations (many of which are largely ignored) cannot be seen as a long-term solution. The whole issue of recommended traits would no longer be necessary.
- As mentioned above, the current orphan system requires crate A to be aware of crate B. As the number of crates increase, I do not see this being a sustainable model for a growing ecosystem. Even if they are aware of each other, it requires one of them to keep things up-to-date with the other just in case someone wants to combine the two as opposed to simply putting that responsibility on crates which do combine the two. With
derivemethods, this is often very straightforward. For more complicated implementations it facilitates someone from creating a shim crate, so that users who depend on interoperability between the crates do not have to duplicate effort, and this shim can be kept up-to-date as a shared responsibility between those who need it as opposed to putting this requirement on the original crate maintainers.
If I was desigining this from scratch, I would say that the syntax which aligns best with the language would be to require implementations to be
pub if an external module wanted to use them. So, for example, if you just had one crate A and wrote
impl T for S then within crate A it would be able to use trait T, but if some other crate B imported S from A the implementation would not also be imported. If, on the other hand, crate A had
pub impl T for S then B could import trait T with some syntax like
use impl T for S from A. This seems to fit best with the rest of the language’s
pub features, but it would be a breaking change and makes types more complicated. I’d rather not let this
pub aspect hold up the solutions discussed above.