Revisit Orphan Rules

[Ixrec]

I think this has been rejected in the past because having no conflict resolution strategy at all means eventually someone's going to pull in two crates that impl T for S, and then there's simply nothing they can do to make that code compile. Then, at best, we're back to crates doing "defensive newtyping" to avoid this problem.

Also, we should probably stop using Serialize as the example, since as stated above we'd never want serde to use such an opt-out even if it was added to the language for good reason. Unless serde added a separate NonPersistSerialize trait or something.

---

Edit:

@mboratko

it also appears to say that any non-generic function lacking the same exact set of impl annotations would simply not compile if it called or was called by bar

Yes, that’s not what I was suggesting, but I don’t see where the gist suggests this is the case.

That was my interpretation of:

As a result, the compiler will specify a type error at the call Module2::bar(h) in Module1::foo(), because the type of the parameter h in bar() does not match the type of the value being provided (the implementation modules do not match).

afaict, that's the only sentence in the gist about the semantics of a non-generic function with impl annotations in the signature, so maybe there are other ways to interpret this.

[scottmcm]

@kornel

I’d prefer this problem to be approached from the other side: allow traits to opt-in into being implemented without orphan rules restriction. Let Serde say that it doesn’t matter who implements Serialize .

A very small step towards that has actually been accepted, for traits with no methods: https://doc.rust-lang.org/unstable-book/language-features/overlapping-marker-traits.html

[mboratko]

@Ixrec

It’s generally assumed that the serialized form of a type needs to be deserializable into any future version of that type .

How exactly is this being guaranteed now? I can make a crate wherein I create a type, implement serialize and deserialize on it, then change them in some backwards-incompatible way. No language features of Rust or semver will prevent or alert me to this, so it's not part of the language to guarantee this, it's left up to the responsibility of the impl author. This would be no different if we didn't have the orphan rules.

[Ixrec]

It’s not being guaranteed, because there’s no way any language could actively enforce a guarantee like that. Even if serialization was part of the core language, there’s simply no way for the language to know with certainty what all past and future implementations of a type look like.

The point of that was not to argue the orphan rules are an ideal solution to the Serialize forward compatibility problem (they’re not even trying to be a solution to that), but that the Serialize problem is a special one that the obvious orphan rule dilemma doesn’t actually apply to, despite it being the most common reason why people complain about orphan rules.

[mboratko]

@Ixrec

the Serialize problem is a special one that the obvious orphan rule dilemma doesn’t actually apply to, despite it being the most common reason why people complain about orphan rules.

Why not?

In my opinion, it does apply. For one thing, it applied in my case when I wanted to serialize some types which the author of the crate had not implemented Serialize, Deserialize on. The structs had a couple layers of nesting, and also depended on a struct from another crate which didn't have Serialize, Deserialize implemented. In this case, doing away with the orphan rule would have allowed me to just derive the necessary traits in ~ 20 lines of code, rather than the various workarounds which have multiple issues. If the authors of those structs decided they did want to implement those traits themselves I would get a compiler error when I pulled the new version and have to either disambiguate (by specifying that I want to use my impl) or remove my impl (inspecting the new serialize implementation from the external crate to see if it was compatible with my own, if that was a concern).

[skysch]

@mboratko

If the authors of those structs decided they did want to implement those traits themselves I would get a compiler error

.. which you probably wouldn't be able to fix, because your other dependencies would likely get the same error. So if someone in a high use left-pad crate implements a trait, the whole world just stops compiling unless they all happen to be version-pinned.

[withoutboats]

I think there are a lot of reasons to be skeptical of this approach (or any other that would allow multiple conflicting impls to be compiled together), but I want to highlight one in particular that I’m surprised hasn’t been mentioned in this thread at all: this proposal would require a major overhaul to our compilation model.

Any time a crate needs to “prefer” one impl over another, it needs to recompile the entire section of the upstream crate graph that previously knew about either impl, in order to avoid incorrect monomorphizations in those crates. While this is certainly possible, it seems severely undesirable: it would require a complete restructuring of our division of work between rustc/cargo and tightly couple the compilation of upstream crates with their downstream crates in ways our existing system adeptly avoids.

The orphan rules (as distinct from the overlap rules) provide for precisely this property while maintaining coherence: the behavior of a crate depends only on its dependencies, not on its dependents.

[mboratko]

The point of what I’m suggesting here is that it would allow for this to be fixed.

It would be just as quick and easy to fix as a method overlap, which already isn’t prevented within Rust, presumably because the disambiguation is considered to be a simple and easy fix.

For example, currently if I do something like

trait MyTrait {
  fn something();
}

impl MyTrait for S {
  fn something() {
    \\--snip--
  }
}

and then some package I have a dependency on also has

impl SomeOtherTrait for S {
  fn something() {
    \\--snip--
  }
}

then

let x = S;
x.something();

results in an error, and I have to disambiguate by adding something like

let x = S;
MyTrait::something(x);

The proposal above would result in a similar way to disambiguate in the case of overlapping impls. It would take an equal amount of work to disambiguate overlapping impls as it does currently to disambiguate overlapping method names. In addition, the proposed prefer idea would be syntactic sugar for annotating all your variables with a specific impl, which would potentially be much less work than dealing with the overlapping methods.

[mboratko]

This is an area where I am wholly out of my depth (as is probably obvious). I’m not sure how the compiler in Rust works, so I’m making a bunch of assumptions. I will learn about it more and come back to this.

I still strongly feel that this restriction is going to be problematic for building a usable ecosystem. I want Rust to succeed, so hopefully I’m wrong.

Right now it’s relatively feasible to recommend crates to implement Serialize, Deserialize (even though, as my own experience shows, that recommendation doesn’t seem to be followed) but what happens when there’s a crate which implements a Loggable trait so that one can indicate how structs should be printed in a log? Sure, perhaps using Display or Debug would be fine, but maybe some other interface would be better (eg. saving the size of a struct in the log might be helpful, or one might want to pass parameters to the logging module which effects how all structs are saved). What about printing out Rust structs to HTML, general DOM interaction traits (once this hits WASM), or a WASMDebug trait which would benefit from a slightly different format than the console Debug?

These are all examples of general traits, so perhaps the list of recommended traits just gets longer. What about implementing EsotericTraitA for SomeStruct, which only a couple of crates would benefit from? Sure, you can say “well, if only a couple crates benefit from it, it’s not a concern.” The point is that for one specific trait that might be the case, but then there’s EsotericTraitB and EsotericTraitC… one certainly can’t expect the author of SomeStruct (as well as any authors of nested structs that SomeStruct depends on) to keep all these implementations in their crate and up-to-date, nor can they expect the trait authors to be aware of all the structs that might possibly be used with their crates.

To me, this seems like a big mess.

[Ixrec]

@mboratko

I still strongly feel that this restriction is going to be problematic for building a usable ecosystem. I want Rust to succeed, so hopefully I’m wrong.

Keep in mind that in most mainstream statically-typed languages like C++, Java, and C#, the "solution" to this problem is simply that the equivalent of impl Trait for Type can only be written in the module that defines Type, no exceptions.

The fact that it's even possible for Trait's owner to write these impls, much less for a third crate to write things like impl Trait for Type<OtherType>, is already a tremendous increase in flexibility compared to the status quo.

So I don't think there's any need to worry about utterly crippling the ecosystem. There may be better solutions, but it's pretty safe to say the current solution is not terrible.

[mboratko]

True, but doesn’t inheritance make the newtype pattern quite a bit simpler? If I were to guess, I’d say that’s why this wasn’t as much of a hindrance in existing languages.

(I’m not advocating for inheritance.)

[elidupree]

I’m also not an expert, but I’m thinking about this idea of disambiguating impl’s the way you would disambiguate methods.

So, if you have crate some_trait providing SomeTrait, and crate some_struct providing SomeStruct, and then crates foo and bar both implement SomeTrait for SomeStruct, then you have to disambiguate between, let’s call them foo::SomeTrait and bar::SomeTrait.

I guess the sticking point is when a crate that’s NOT foo or bar cares about SomeTrait. Such as the original crate, some_trait. In some_trait, you might have:

fn consumer <T: SomeTrait> (input: T) {…}

And then in my crate, baz, which imports both foo and bar, I do:

some_trait::consumer (SomeStruct::default());

In order to monomorphize consumer, it has to know not just T = SomeStruct, but T = SomeStruct with the SomeTrait impl from foo. Well, let’s assume I have a way to disambiguate that. I always prefer foo’s impl, so whenever I call a generic function that uses SomeTrait, it should use the impl from foo. I guess that includes even if I call a generic method from bar – after all, a generic method implemented in bar would have no reason to assume anything about the impl used for it.

I’ve been trying to think about counterintuitive cases that would arise from this, but it’s surprisingly difficult. Here’s the worst I’ve come up with so far:

//in some_trait
trait SomeTrait {
  type Associated: Eq;
  fn get_associated (&self)->Associated;
}

…

//In foo
impl SomeTrait for SomeStruct {type Associated = i64; …}

…

//in bar
impl SomeTrait for SomeStruct {type Associated = [i64; 2]; …}

fn complex_operation_returning_associated (input: &SomeStruct)->SomeStruct::Associated {…}

…

//In baz
prefer impl SomeTrait for SomeStruct from foo;

fn do_something (input: &SomeStruct)->bool {
  //compile error, mismatched types
  input.get_associated() == foo::complex_operation_returning_associated(input)
}

[mboratko]

So far I think the most problematic issue is @withoutboats’s point. If I’m understanding it correctly, the problem is that if in crate some_struct you have a function

fn which_impl(x:SomeStruct) {
  x.get_associated();
}

then, with the current model, monomorphization during compilation of some_struct is possible regardless of what crates which import some_struct are doing. If you allow some other crate foo to override the implementation of SomeTrait, then monomorphization depends not only on some_struct and it’s dependencies but also any crate which used some_struct. I’m not familiar enough with rust internals to know what the impact of this is, but @withoutboats is claiming that it is very undesirable, which I’m willing to accept.

[elidupree]

Following up on my previous post, it gets worse if you think about supertraits:

//In bar
trait SubTrait: SomeTrait {
  fn different_associated (&self)-><Self as SomeTrait>::Associated;
}
impl SomeTrait for SomeStruct {type Associated = [i64; 2]; …}
impl SubTrait for SomeStruct {fn different_associated (&self)->[i64; 2] {…}}

…

//In baz
fn do_something (input: &SomeStruct)->bool {
  //compile error, mismatched types
  input.get_associated() == input.different_associated()
}

// Or worse,
fn extract_associated_1 <T: SomeTrait> (input: & T)->T::Associated {input.get_associated()}
fn extract_associated_2 <T: SubTrait> (input: & T)->T::Associated {input.get_associated()}
fn do_something_2 (input: &SomeStruct)->bool {
  //compile error, mismatched types
  extract_associated_1 (input) == extract_associated_2 (input)
}

[Ixrec]

Sort of maybe it’s complicated.

So, “traditional” inheritance has two specific advantages over newtypes.

First, you don’t have to write fn foo(&self) { self.thingBeingWrapped.foo(); } for every single method you want to “inherit” the implementation of. This is purely a convenience thing, and in Rust we will probably someday provide this same convenience with a feature called “delegation” that just generates these trivial wrappers for you, so it should be nice and orthogonal to everything else.

Second, inheritance creates a subtype of the base class, while newtyping does not. This is the far more interesting difference, but also where most of the complexity and downsides of traditional inheritance come from.

While both of these arguably make certain things “simpler”, I don’t think either has a significant impact on the fundamental problem of wanting T to implement trait/interface IFoo yet not being able to write that impl yourself. In any of these languages, you still have to talk to whoever owns T to make that happen, or write another type that wraps T. It’s true that inheritance sometimes lets you write this other type in a very concise way, but that carries a lot of complicated baggage, will become a moot point as soon as we figure out “delegation”, and even in today’s Rust custom derives can already make some newtypes more convenient to write than they would be in other languages where macros are absent or dangerous.

I don’t think we can really make progress on this part of the issue without examing concrete examples of situations where the obvious newtype is difficult or impossible to write. Off the top of my head, I’m simply not aware of any case that would not be equally impossible in any other language.

[mboratko]

The situation that sparked my question is what I’m offering as an example. Putting aside the tedious boilerplate issue, the main downsides to writing the newtype, in my case, are that:

1. I would have to reimplement the functionality that derive(Serialize, Deserialize) provides manually, I can’t derive on a newtype because the internal types don’t already implement the traits.
2. In my implementation I would have to manually specify the field names for the struct I was wrapping, which would make my crate depend on every single public field associated with the struct, and therefore make it more brittle to future changes.
3. If the other struct added new public fields it may not be considered a breaking change (right?) so I would now have to inspect every upgrade and see if fields were added.
4. It forces traversing the vector of structs returned from systemstat and wrapping them in my newtype. My understanding is that a simple newtype pattern on a single struct doesn’t result in any performance overhead, but it’s unclear to me if this is also true when wrapping a vector of structs, for instance. Regardless, the additional wrapping adds noise when reading the code, adding some slight cognitive overhead.
5. Any time I wanted to use the native functionality I would have to unwrap the new type first, with similar issues to the above.

[mboratko]

Oh and:

6. It inhibits rapid prototyping, since instead of just deriving a couple traits in 20 lines or so, in my case, I need to copy and write ~300 lines of code just to create the wrapped newtype, nevermind what I would have to do for the implementation itself, just to try out passing this struct over the wire. If I end up deciding this crate isn’t a good one for me to use, all that code gets tossed.

[Ixrec]

@mboratko

• I would have to reimplement the functionality that derive(Serialize, Deserialize) provides manually, I can’t derive on a newtype because the internal types don’t already implement the traits.
• In my implementation I would have to manually specify the field names for the struct I was wrapping, which would make my crate depend on every single public field associated with the struct, and therefore make it more brittle to future changes.
• If the other struct added new public fields it may not be considered a breaking change (right?) so I would now have to inspect every upgrade and see if fields were added.
• It forces traversing the vector of structs returned from systemstat and wrapping them in my newtype. My understanding is that a simple newtype pattern on a single struct doesn’t result in any performance overhead, but it’s unclear to me if this is also true when wrapping a vector of structs, for instance. Regardless, the additional wrapping adds noise when reading the code, adding some slight cognitive overhead.
• Any time I wanted to use the native functionality I would have to unwrap the new type first, with similar issues to the above.

We must have different understandings of "tedious boilerplate", because to me 1, 4, 5 and part of 2 (Edit: also 6) are just different ways of saying "boilerplate" (newtypes certainly shouldn't add runtime overhead; if you think you have a counterexample please talk about that example instead). And I'm pretty sure all of those slightly different ways of saying "boilerplate" are equally true of the languages with traditional inheritance (once Rust has delegation).

3 and the rest of 2 are basically the dilemma we've mentioned many times before that you often want serializations to be deserializable into future versions of the same type, which is impossible to guarantee unless the type's owner provides the (de)serialize impls. For any other trait, these points should be either non-issues (by far the most common case afaik), or a mild nuisance when a new field is added but not a breaking change (i.e., adding the new field to the impl is completely optional). I believe Serialize is the only trait where just adding a new field is automatically a breaking change, no matter what the API contract of the type was or whether any of the other fields changed behavior. So again, this is not an argument that orphan impls are a better solution than newtypes, but rather it's an argument that neither orphan impls nor newtypes are what you want in the special case of Serialize, which is why I keep saying we need to stop using this case as an example.

[Ixrec]

@mboratko

Right now it’s relatively feasible to recommend crates to implement Serialize, Deserialize (even though, as my own experience shows, that recommendation doesn’t seem to be followed) but what happens when there’s a crate which implements a Loggable trait so that one can indicate how structs should be printed in a log? Sure, perhaps using Display or Debug would be fine, but maybe some other interface would be better (eg. saving the size of a struct in the log might be helpful, or one might want to pass parameters to the logging module which effects how all structs are saved). What about printing out Rust structs to HTML, general DOM interaction traits (once this hits WASM), or a WASMDebug trait which would benefit from a slightly different format than the console Debug ?

These are all examples of general traits, so perhaps the list of recommended traits just gets longer. What about implementing EsotericTraitA for SomeStruct , which only a couple of crates would benefit from? Sure, you can say “well, if only a couple crates benefit from it, it’s not a concern.” The point is that for one specific trait that might be the case, but then there’s EsotericTraitB and EsotericTraitC … one certainly can’t expect the author of SomeStruct (as well as any authors of nested structs that SomeStruct depends on) to keep all these implementations in their crate and up-to-date, nor can they expect the trait authors to be aware of all the structs that might possibly be used with their crates.

afaik, in every other language the list of traits/interfaces that everyone is expected to provide implementations for is basically the same as Rust: something to stringify the type for logs, something to serialize the type for persistent storage, and value type semantics like equality and ordering when applicable. For every other interface, the assumption was that you'll use inheritance/wrapper types if you really need it.

I think the only meaningful difference between Rust and Java/C# here is that Rust's Serialize trait is not part of the core language or standard library, which I suspect is one of the reasons this might feel like a much bigger problem than it did in those two languages: Java/C# never really had an interface in a 3rd party library that "everyone should implement".

But I don't think that automatically means Rust's list of 3rd party traits that everyone needs to implement is likely to grow in the future; I still think that serialization is special and it's unlikely we'll ever need to make such a recommendation for anything else.

[mboratko]

@Ixrec

We must have different understandings of “tedious boilerplate”

Maybe we do. My definition of complaining about tedious boilerplate is solely the complaint that it is boring and time consuming to write all this stuff at the outset. Aside from 6, which I concede is more of a boilerplate issue, the points I've made were intended with the interpretation of "even if you are handed this stuff, already written, these are problems." For example, in 1 we have code duplication, where we are attempting to reimplement whatever derive would have done. Even if we'd gone through the process of figuring out a manual implementation at the start, this suffers from all the common issues related to code duplication - if serde updates it's implementation because it found a bug or performance improvement we aren't aware of it, so we don't benefit. Even if we were aware of it, we'd have to implement those changes in our code as well, etc. This is not just a boilerplate issue.

As for the performance overhead on 4 and 5, are you sure that wrapping/unwrapping a type nested within another type (say a vector) is a noop at runtime? Because afaik that's not the case in eg. Haskell.