Or "How I Learned to Stop Worrying and Love Coherence"

The orphan trait rule in Rust is interesting and works impressively well for what it intends to do. While I'm often frustrated by the limitations it imposes, it absolutely succeeds at removing ambiguity in whether or not a trait will be implemented for a type.

A quick primer, quoted from The Rust Programing Language, for those who aren't super familiar with the rule:

But we can’t implement external traits on external types. For example, we can’t implement the Display trait on Vec<T> within our aggregator crate, because Display and Vec<T> are defined in the standard library and aren’t local to our aggregator crate. This restriction is part of a property of programs called "coherence", and more specifically the "orphan rule", so named because the parent type is not present. This rule ensures that other people’s code can’t break your code and vice versa. Without the rule, two crates could implement the same trait for the same type, and Rust wouldn’t know which implementation to use.

The case I ran into that motivated this post is as follows:

I'm adding edit support to amethyst-editor-sync, which means I need to be able to take an incoming serialized representation of a type and then deserialize it into the correct type. Since the crate needs to support arbitrary user-defined types, I need a way to identify which type the serialized data should be interpreted as so that I can send that data to the right deserializer.

In order to do so in a robust way, I need a stable way to identify types at runtime. The ideal way of doing this is to assign a UUID to each type via a trait. This allows me to ensure at compile time that any type being displayed in the editor has been assigned a UUID, and therefor can be identified for deserialization.

Fortunately, the serde-dyn crate has been made explicitly for this purpose.

Unfortunately, the TypeUuid trait that it defines hasn't been implemented for the types in the Amethyst, which is a problem because amethyst-editor-sync wants to provide functionality for registering those types to appear in the editor.

This is a case where the orphan rules seem to be a nuisance: It'd be easy enough for me to implement TypeUuid for the necessary types from within amethyst-editor-sync, but the orphan rules prevent me from doing so. I'd have to go and add the implementations to Amethyst directly, which isn't a practical thing to do if Amethyst hasn't committed to using serde-dyn.

Okay, fine. I can work around this by creating my own TypeUuid trait in amethyst-editor-sync, and I can implement that trait for the Amethyst-provided types. But I don't really want to define the UUID functionality in amethyst-editor-sync, that functionality is orthogonal to the goals of the crate. Ideally, I'd like users to be able to work with types that implement serde_dyn::TypeUuid.

To get this compatibility, I can make a blanket impl of my trait for the one provided by serde-dyn:

impl<T> TypeUuid for T where T: serde_dyn::TypeUuid {
    const UUID: u128 = <T as serde_dyn::TypeUuid>::UUID;

So what would happen if, at some point, Amethyst were to adopt serde-dyn and start adding impls of serde_dyn::TypeUuid for types for which I've implemented amethyst_editor_sync::TypeUuid? Which impl would be the canonical one? Would the code even compile at that point?

Well, once amethyst-editor-sync updated to use the latest version of Amethyst the code would no longer compile because the compiler would recognize that there were two conflicting implementations of amethyst_editor_sync::TypeUuid for those types. If I were to remove the manual impl in amethyst-editor-sync for those types, then it would compile again.

So now we finally get to the question that got me thinking in the first place: If some of the types defined by Amethyst are covered by the blanket impl (because they implement serde_dyn::TypeUuid directly) and some are implemented directly in amethyst-editor-sync, how does the compiler know that a given type in the Amethyst crate can only ever be covered by one of the two implementations? That is to say, how can the compiler, when only looking at amethyst-editor-sync and its dependencies, know that the implementations will still be valid and free of conflicts when amethyst-editor-sync is added as a dependency for some other crate? How can it be sure of this without knowing anything about the context in which amethyst-editor-sync will be used?

The answer is that the orphan rule guarantees it. Because of the orphan rule, only one of two things can happen for a given type defined by Amethyst:

  • Amethyst implements the serde-dyn trait for its own type, and therefor the type is covered by the blanket impl.
  • amethyst-editor-sync implements its own trait directly for the type.

There's no way for amethyst-editor-sync (or any third-party crate) to implement serde-dyn's trait for Amethyst's types, which means the compiler can look at amethyst-editor-sync (and its dependency tree) and know that no code outside the crate can inadvertently result in two implementations of the trait.

The beauty of the orphan rule here is that it's simple and consistent enough that I was able to reason through all of this in my head. Rather than having to write out test code to find out if defining the blanket impl would work, I could rely on the simplicity and consistency of Rusts rules to make it reasonable for me to reason about the complex task of making my crate work within a potentially complex dependency tree.

While I've often been frustrated by the orphan rule, and it has complicated the way the Rust ecosystem works, I can't help but marvel at how well designed it is as a part of the language. Being able to reason about the correctness of some code locally (i.e. without needing to see the entire context of the final program the code exists within) is a powerful property that Rust is clearly dedicated to embodying. Despite it's frustrations, I think I've finally learned to stop worrying and love coherence ❤️