Revisit Orphan Rules

[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]

• 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]

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]

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.

[ExpHP]

Because afaik that’s not the case in eg. Haskell.

That’s because Haskell has a runtime.

[Ixrec]

Ah, fair enough. I was lumping in the duplication part with the “pure boilerplate” that will never have to change because “delegation” should solve both.

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.

I think we’re gonna need a concrete example here. There’s certainly no reason why x.y.foo() would be any more expensive at runtime than y.foo() if x is just a newtype around y; typically x would vanish during optimization.

[mboratko]

Ah, fair enough. I was lumping in the duplication part with the “pure boilerplate” that will never have to change because “delegation” should solve both.

Yes, put more simply, from my perspective this list (aside from 6) are all downsides to using an already completed newtype pattern.

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

That’s not the issue I’m pointing out here. For my implementation, I want lightweight clients that just capture the raw structs and pass them over the wire to a server, which will dice them up and save them in a different format. I probably won’t want to use all the fields on the server, but I don’t want that logic spread out between the client and the server. If I decide that I want to collect more of the fields, I would have that capability solely by updating the server.

If I was just able to derive Serialize, Deserialize on these structs my program would only be dependent on the eventual public fields that I used, as opposed to making a newtype and then copying over every single field in the existing struct, resulting in a complete dependence on the full external interface of the struct, which is what I mean by “brittle”. In particular, in this situation I wouldn’t particularly care about backward capability of the deserialize method, as long as I updated the clients and the server at the same time everything would continue to work even if the struct author had added new fields I was unaware of.

[Ixrec]

Hm, okay, I did misinterpret that, but your actual issue still sounds like something that’s unique to the Serialize trait. Is that fair?

[mboratko]

I don’t think so.

For example, what if there was a Loggable trait. The reason for it’s existence is that instead of just using Display or Debug it allows you to pass it a struct and a verbosity level, and some fields would be hidden under a particular verbosity. Maybe the default derive implementation of this trait is to have the verbosity = level of nesting in the struct, but obviously some structs may implement this on their own. In addition, there might be formatting parameters for different logging conventions, and the information might be different than what you’d get from Display or Debug, for example maybe it also includes information about the size of the struct or the time, the goal being to be able to write something like

x.log(3);  // sends x to the current logging mechanisms with verbosity 3

[Ixrec]

I’ve been trying to think about counterintuitive cases that would arise from this, but it’s surprisingly difficult.

iiuc the problems with allowing orphan impls are less about causing code to do counterintuitive things at runtime, and more about enabling a non-trivial dependency graph of crates to code itself into a corner where the code I want to write is literally impossible to express because of conflicting impls (and conflicting ad hoc resolutions to deal with other conflicting impls) provided by various dependencies.

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

Though this is a good example of how little it takes to make it confusing. I think this is essentially the same thing as the “hashtable problem”, albeit as user confusion rather than unsoundness or incorrectness.

[Ixrec]

That’s basically what I was talking about in this previous post. Perhaps we’re talking in circles at this point.

[mboratko]

So, to be clear, you’re saying these sorts of traits are unique because they are the only ones where all the fields might be necessary? Maybe in practice that’s true, honestly I don’t have enough practical experience to offer an opinion. I see your point though, it’s hard for me to imagine other traits which might have to arbitrarily recurse through the entirety of a type’s structure.

[Ixrec]

I do think (De)Serialize are the only traits/interfaces I’ve ever encountered that always need to know about all the fields in a type in order to be implemented correctly.

There are traits that usually need to know about all or most of the fields in a type, but I believe those are mostly the Debug/Eq/Ord/etc traits in std, and that’s why they’re also on the “always implement if possible” list.

afaik, it’s extremely rare for any other trait implementation to need to operate on the type on a “field by field basis” to achieve basic correctness, and just about every other trait can get away with the type’s public API (if it makes any sense to implement that trait for that type). Maybe I’m missing something important, but that is the impression I get from the current state of Rust and all these other languages we’ve mentioned.

---

So, personally, I think what we really need to make progress on this issue is more concrete examples of very specific use cases not involving Serialize where “just use a newtype” didn’t work.

The only one I’ve heard of personally was a comment (maybe by @sgrif?) that diesel-chrono should be a thing that exists, but it wouldn’t make sense for diesel or chrono to depend on each other in order to provide those impls. If it turns out that all use cases are similar to this one, perhaps we could brainstorm some sort of whitelisting mechanism where diesel and chrono both declare that diesel-chrono has special permission to impl their items.

[elidupree]

afaik, it’s extremely rare for any other trait implementation to need to operate on the type on a “field by field basis” to achieve basic correctness

How about a trait for a tracing garbage collector?

I’ve also run into at least one other case where I had a custom type, let’s call it WeirdStruct, and I wanted to implement an algorithm that takes an object and visits all instances of WeirdStruct owned by that object. In my current code, I’ve implemented this using the horrible hack of piggybacking off existing Serialize implementations, but if I wanted to release something like that in a library properly, I’d have to depend on everyone else to implement a VisitOwnedWeirdStructs trait.