Relax orphan rules for derived impls

[golddranks]

The current orphan rules prevent implementing an external trait for an external type, preventing multiple different implementations for any pair of (trait, type). This restriction on downstream crates is to preserve coherence, but at the same time it prevents implementing some common traits for types whose authors didn't have the foresight to implement the traits for.

It just occurred to me, that while orphan impls are troublesome when they are hand-crafted, derived impls shouldn't have any problem with coherence. Why? Because if the impl is algorithmically derived by the compiler, it's going to be the same no matter where it is derived.

Of course, this assumes that only the trait author (or the compiler itself) has the control to define the derivation algorithm, i.e. the compiler plugin that does the derivation. That's actually just another way to say that there is no coherence issues because the implementation is originally by the trait author, whether or not he/she triggered the derivation for a specific type.

I didn't write this into a full-blown RFC yet, because there's some blockers:

1. If the orphan rules are relaxed, the downstream crates become able to derive traits for upstream types. But the type authors may have meant their types NOT to implement a trait. Currently it's possible to do this by just not implementing the trait, because the orphan rules prevent others from doing so. But this is essentially negative reasoning, which is frowned upon. Negative impls should help, as they allow to explicitly represent this intention.

2. I'm not sure what's the story about deriving impls for other than std traits. If there's eventually going to be a stable way to define compiler plugins for deriving implementations, there should be a limitation that only the trait author has the ability to define the deriving plugin for his/her trait, otherwise the orphan rules can't be relaxed. Of course, this rule, in turn, could be relaxed so that anyone is able to define deriving plugins for any traits, but only the plugin by the trait author is allowed to be used by downstream crates to derive impls for upstream types.

[golddranks]

Uhh... I'm not sure if I should've written this in the internals forum instead of here. Which is the better way to get feedback on the idea?

[oli-obk]

This internals thread discusses a possible solution.

[netvl]

@golddranks derivation mechanism is only a helper; nothing prevents one to write an implementation of the respective trait manually. In fact, sometimes this is necessary - for example, there may be multiple ways to serialize a C-like enum (as a number, as a string, as a string with enum prefix, etc.), and serialization libraries may not give you the desired format by default. Or, for example, you may need to serialize a value which does not wrap a string internally as a string (provided there are sensible conversion functions available). So I think it is not entirely correct to differentiate between derived implementations and hand-written implementations, certainly not in terms of coherence.

[golddranks]

@oli-obk Thanks, I'll check that.

@netvl Indeed, that is true. However, I'm not trying to point out what derived impls currently are, I'm trying to think what they could become. Namely, they could become "algorithmically derived opt-in blanket impls". I'd imagine that would help tremendously with serialization hurdles.

As you say, nothing prevents one from writing an impl of a trait manually; that is, if you are the author of the type (or the trait). But orphan rules prevent anybody else from doing that. If you want to circumvent that, you need to define a newtype. I'm not saying that we should differentiate between derived and hand-written implementiations magically. My point is that we should allow any way of implementation that doesn't violate coherence. And allowing downstream-derived implementations by this rule, is all right, because it doesn't violate coherence.

[golddranks]

@oli-obk The workspace-local orphan rule proposal seem to be orthogonal to this proposal. That proposal allows type and trait authors to implement traits without having to have dependencies in the crate that defined the type or trait and having the dependencies in another trait that is associated through a workspace. But it still essentially doesn't let third parties to have anything to say.

What this proposal does, is that it essentially allows crate authors to define opt-in blanket impls that are implemented algorithmically (through compiler plugins), and thus allow a kind of compile-time reflection. The important point is that it doesn't matter who does the opting in, so this makes it possible for third parties to opt in, if the trait author has provided the deriving machinery.

Like desiringmachines said in Reddit, linking is still a problem, and the coherence checker doesn't know the difference between hand-written and derived impls. The latter problem would be solved by having "author hygiene": the code generated by a derivator would be considered the same as the code from the crate (or workspace) that defines the trait, from coherence checkers viewpoint.

[golddranks]

I'm not very well-versed in linking/symbol resolving process... But the problem there seems to be that if two crates derive the same impl, the symbols are different even if the source code would be same. That's an unresolved question as of now.

Another unresolved question is how would the derivation interract with privacy. Should the deriving code have access to private things, if the deriver has access? Or should the deriving code be considered to be an "outsider", a part of the crate that defines the trait.

[golddranks]

Maybe the linking problem could be resolved if the derived impls would be outputted into an external crate by the compiler, so that there wouldn't be crate-internal dependency to the symbols. Then the problem could be resolved globally by the linker.

[withoutboats]

My point is that we should allow any way of implementation that doesn't violate coherence. And allowing downstream-derived implementations by this rule, is all right, because it doesn't violate coherence.

What if two different crates provide two different algorithms for deriving the same trait? Once derive can be extended for arbitrary traits, its not clear to me that this should be disallowed.

From a practical perspective: I think the derivation algorithm will need to be in a crate containing procedural macros, which require special handling. If "orphan derivation algorithms" were disallowed, any trait for which the author wanted to provide derivation would need to be defined in these crates.

From a philosophical perspective: derive looks like a procedural macro and behaves like one - it is purely syntactic. I don't think this proposal would solve enough coherence woes to justify elevating derivation to a first-class construct from which we can make typing judgments.

[golddranks]

Two different crates shouldn't be allowed provide derivation algorithms for the same trait – the coherence requirement is that only the the trait author is allowed to do that, that is, the derivation algorithm must originate from the same crate/workspace as the trait.

[nikomatsakis]

Note: I opened #1856, which also describes this problem, along with various other scenarios we might like to address. I'm not sure whether to keep this issue open (as a kind of "sub-issue") or close it in favor of #1856.

[golddranks]

Well, this issue does not only describe the scenario, it also proposes one possible countermeasure: opt-in procedural blanket impls. However, I'm not sure if an GitHub issue is a right place to discuss the feature itself, so I posted this in the internals forum: https://internals.rust-lang.org/t/a-partial-remedy-for-orphan-impl-troubles-procedural-blanket-impls/3834 Not much discussion ensued though.

[sunjay]

Did anything ever come out of this? I also think the orphan rules should be relaxed. If a crate I'm using defines a trait and the author forgets to implement something, I should be able to do it myself.

[nikomatsakis]

@sunjay

I also think the orphan rules should be relaxed. If a crate I'm using defines a trait and the author forgets to implement something, I should be able to do it myself.

It's not as simple as that, I'm afraid. The trait system and overall language definitely relies on the idea that there is at most one impl of a given trait that applies to any set of types, and it we allow multiple crates to define their own impls, that will violate this rule, unless we make it a link error or some such thing (which would then mean that arbitrary dependencies cannot be combined, which strikes me as a cure worse than the disease). So the short answer is "no", it has not been solved, but the longer answer is that there is much active discussion into the proper shape of the fix. =)

[nikomatsakis]

@golddranks

I'm not sure if an GitHub issue is a right place to discuss the feature itself, so I posted this in the internals forum

I'm going to close this issue in favor of #1856 in that case.