Deriving external traits on external structs

My example above demonstrating that the current coherence rules don't protect against things as intended turned out to be more than just theoretical:

https://github.com/rust-lang-nursery/api-guidelines/issues/138

A "Trait" is much like a pure abstract base class or interface, but, more flexible. In most OO languages, the equivalent of Serialize/Deserialize would either be an abstract base class or an interface. In either case, only the original class hierarchy could implement it. With traits, you gain additional flexibility that either the original class (struct) can implement the trait, or the original definer of the trait can implement it for existing 3rd party structs.

There would be major issues of coherence if crate C were able to implement a Trait defined in crate A for a struct defined in crate B.

I did read through the link @vitalyd's shared, and it was an excellent overview, however it seems to be digging the hole deeper as opposed to fixing the problem. I agree with the bullet at the end, which suggests to get rid of the orphan rule entirely, however in so doing there still needs to be some way to specify which impl is chosen. The original email about the hashtable problem from Niko Matsakis in 2011 (posted above by @ExpHP) suggests a powerful and elegant solution. While searching through the history of this issue I have uncovered a number of appeals to the hashtable problem as justification for the orphan rule but none of them seem to mention the solution Niko proposed in the same email, let alone give any reason for why that solution is undesirable.

Niko's blog is also a gold mine -- in particular you might like to read Little Orphan Impls.

1 Like

It also allows: Given crates Serde, SomeStruct, MyApp if MyApp needs to use serde with SomeStruct crate, it can create a new crate called "Serde-Shim-SomeStruct" and use the Remote Serde thing to define Serialize/Deserialize. Now, My App can use "Serde-Shim-SomeStruct" crate for Serialization/Deserialization of SomeStruct crate's structs, and so can anyone else!

OK, but

  1. Serde-Shim-SomeStruct will have to copy the entire (public) structure of SomeStruct into their package in order to use the remote serde macros, which, aside from being unnecessary duplication, also means that...
  2. Serde-Shim-SomeStruct will now have to keep up to date with any changes to the entire public structure of SomeStruct. Furthermore...
  3. if we allowed crates to implement external traits on external structs (with some solution such as the one in Niko's original email about the hashtable problem) then this "benefit" you are claiming would still be possible, but it would be moot, as one could simply throw a couple "derive" lines down and call it a day. And...
  4. no one would have to implement crazy workarounds such as the Remote Serde thing in the first place.
1 Like

Why can't I, in OO languages, implement a base-class/interface for some other class I did not define? Why can't I define a new interface and implement it for a bunch of other classes without them needing to know about it? (Dynamic Languages don't count because that involves significant run-time overhead).

There aren't open types, but I don't see this as a refutation of Niko's original solution.

Since the original email was from 2011 I'm sure it's been discussed, but I don't see an issue with it and I can't find anyone who has discussed it, which is surprising since it's often cited as the reason for the orphan rule in the first place.

Niko's blog that I linked directly addresses the original ideas, and the problems therein.

I read it, it seems to start from an assumption of accepting the premise that the orphan rules are correct, and then seeks to appropriately generalize them for parametric traits. Can you point out where he explains why the solution in his original email (append a specific implementation to a type when you instantiate a variable) is problematic, and why the orphan rule is therefore necessary?

Sorry, you're right -- the idea of orphan rules came in sometime between, and I can't find when. The first relevant "orphan" I can find in the git history is a comment in commit 9d3f57ef0869, part of PR 10153, but this doesn't explain the idea either. Issue 5514 is even older, but still presupposes the idea.

We should probably just ask @nikomatsakis...

You are right. I have not seen discussion of this idea, perhaps in part because it sounds like a "biggish" feature, the language was evolving at lightspeed back then, and whatever it was, it didn't make it into 1.0. If it was discussed, I'm not sure where, and if it wasn't, then I think it should be! (but in the context of the language as it exists today)

To elaborate, the feature being discussed as I understand it is something along the lines of adding specifications of trait impls to the type of something

mod special_impls {
    impl Hash for i32 {
        // ... code ...
    }
}

// The type of an i32 with a specific Hash impl.
// (No idea what kind of syntax to use for this.)
type MyI32 = i32 + ::special_impls::<Self as Hash>;

and that this impl would be checked as part of the type, with conflicts leading to a type error.

A solution to the specific example of hashtables exists in what was stabilized in 1.0; HashMap is parameterized over a Hasher, which defaults to DefaultHasher. An obvious benefit I can see of the chosen approach is that Hash impls are decoupled from code that uses them; even if you use #[derive(Hash)], you can still just drop in FnvHasher for any hash map if you want to; but it does not generalize to arbitrary traits. (in general it requires a carefully-designed intermediate trait)

1 Like

Obviously I'm clearly of the opinion that it should be discussed, because I see it as a more useful solution to coherence than the orphan rule. Implementing it would not be a breaking change to the language at this point since the orphan rule is so strict that there are guaranteed to be no crates which would need this disambiguation right now.

My suggestion above of having some sort of prefer using impl TraitName for StructName from modulename in order to override whatever default impl would have been chosen across the board is also something I would like to see. The capabilities it provides are a strict subset of those provided by Niko's suggestion (so, in this sense, it is a smaller change) but even with Niko's suggestion I think it would be of practical use so that you don't have to annotate types as much.

The instance I can see where there might be problems is if an existing module called the method directly, in which case we'd be in this case from my previous example, however the point of that example is that we already can be in this situation, which is apparently not considered a problem because fixing it is easy and something the compiler could automate. A further nuance might be if a crate designed other parts of their module expecting certain effects from a particular impl, in which case overriding the choice of impl may lead to unexpected behavior. For example, consider the hashtable problem but now assume that, instead of using the "gets" method, one of the crates retrieves the data manually, i.e. avoiding the trait. Since previous guarantees meant their impl was the only one, they can assume the structure of the underlying data based on their impl. (I would venture a guess that this probably isn't a problem.) 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.

Note that all of this is orthogonal to the specificity hierarchy for parametric tratis mentioned elsewhere (i.e. Little Orphan Impls). Those details would still apply, and are useful in their own right. Essentially, those issues are necessary to select the "default" in a sensible way for complicated parameterized traits. Since they're currently not dealt with at all, one could say that implementing this instead is a way to avoid having to come up with complicated specificity rules in the first place. Instead of having a default, in that case, the compiler would just cough up an error and tell you that you need to disambiguate manually. Specificity rules could be decided down the line. Additional specificity rules could be added down the line, if desired, if they were clear and easy to understand. (Throwing the task to a human, for now, would mean that adding them in would not be a breaking change.)

If you want to propose language changes in earnest, rather than just exploring the history, then I suggest you take this to the internals forum. If nothing else, you're more likely to catch the eye of core rustc developers there, who may be able to explain why that wasn't pursued in the first place.

Thanks, I will. I was starting by exploring the history mostly because I thought it had to have been considered, or that perhaps I was missing something obvious (which still very well may be the case).

I think I just thought about one obvious thing.

Your original motivation is serde, which is about serialization/deserialization. These operations should really be implemented by the author of a struct, because...

  • External crates may not have or keep the required struct member access.
  • Serialization adds an extra backwards compatibility constraint (data-level compatibility is harder than interface-level compatibility), so the struct author should be aware that it will be performed.

Therefore, you will need to find other motivating examples if you want to justify this language complexity increase.

I'm not sure I understand the reasoning, but Serde already has remote derive, which is just a more complicated and fragile way to implement the desired functionality. My point is, whatever the objections are, the language already does not prevent against them.

It doesn't need to be for Serde though. The API guidelines recommend deriving a large number of traits on any publically accessible structs, but this isn't being followed. Simply deriving something like "Display" on this struct would be helpful. Yes, you can fork and submit a pull request, but then you're waiting on the other crate maintainer to update crates.io before you can push your crate. What if they're just unavailable? Sure, you can fork it, but this is going to lead to fragmentation of the ecosystem.

More generally, I see it as a huge architectural issue if crate A and crate B have to be aware of each other in order for crate C to combine their functionality. If people are writing code which actually takes advantage of Rust's type safety, they should use custom structs and traits. Right now, you'd have to ping one of the two crates in order to implement traits across crates. What if the implementation you have in mind is only relevant for your crate C? What if someone else wants to use crate A and crate B, but define a different implementation than the one you needed in crate C?

1 Like

I think you need to realize that this "limitation" is fundamental. You are asking the equivalent of, "Why can't I add a new base class/interface to an existing class that I did not write?" Traits are "more flexible" than base classes/interfaces. They allow the Trait author to implement the Trait (base class/interface) for existing Structs (Classes). The fact that a 3rd party that is not the author of the struct or the trait cannot implement the Trait for the struct is not an arbitrary limitation, it is fundamentally incoherent (or I and many others are missing some important point).

I know that I myself have "spit-balled" (Orphan rules - #42 by steveklabnik - ideas (deprecated) - Rust Internals & Moving bits of rustc into crates - #35 by gbutler - compiler - Rust Internals) on how something like this might be possible, but, the more I think about it, I just don't see how to reconcile all the conflicts in a coherent fashion.

I don't get what you are saying here. A remote implementation of a trait is clearly only going to be using the public API. (unless... was something to the contrary suggested?)

That's like saying the struct author ought to be aware if users are writing functions like

fn thing_to_json(thing: &cool_crate::Thing) -> serde_json::Value {
    // ... use public interface of cool_crate::Thing ...
}

fn json_to_thing(json: &serde_json::Value) -> cool_crate::Thing {
    // ... use public interface of cool_crate::Thing ...
}

This is going around in circles. @mboratko has already pointed out how the "hashtable problem" post describes a possible extension to the type system where external trait impls are coherent.

1 Like

All I was saying is that serialization/deserialization assumes a lot more interface surface than basic usage of a struct (including, for example, access to un-transformed private data and ability to create instances of the struct from said data, and if you want to exchange serialized data across crate versions you also need to pose strong constraints on the evolution of private data), and that only the crate author can reliably provide this interface surface and keep it alive across updates to a crate.

Data-level compatibility is much more expensive than interface-level compatibility, and it should be a crate author's choice to decide which level of compatibility he wants to provide.