Learn Rust Series (#23) - The Orphan Rule & Trait Coherence

avatar

Learn Rust Series (#23) - The Orphan Rule & Trait Coherence

rust-banner.png

What will I learn

  • You will learn the orphan rule: that you may implement a trait for a type only when you own the trait or the type;
  • what trait coherence means, and why the compiler enforces it across the entire program rather than one file at a time;
  • exactly which combinations of local and foreign trait-and-type are allowed, and which one is forbidden;
  • why implementing a foreign trait for a foreign type would break the language, with a concrete diamond-of-doom example;
  • the newtype workaround that lets you get around the rule cleanly, and how Deref (from episode 19) softens its one real cost.

Requirements

  • A working modern computer running macOS, Windows or Ubuntu;
  • An installed Rust toolchain (via rustup, from rustup.rs);
  • The previous twenty-two episodes, especially traits from episode 8, the Display formatting trait, and Deref from episode 19;
  • The ambition to learn systems programming from the ground up.

Difficulty

  • Beginner

Curriculum (of the Learn Rust Series):

Learn Rust Series (#23) - The Orphan Rule & Trait Coherence

Sooner or later, and usually sooner, you will try to implement a standard trait like Display on a standard type like Vec<i32>, and the compiler will stop you cold with a message that mentions "only traits defined in the current crate can be implemented for types defined outside of the crate". That wall you just walked into has a name -- the orphan rule -- and it frustrates just about every newcomer until the day they see the exact disaster it prevents. Once you see it, the rule stops feeling like an arbitrary restriction and starts feeling like the compiler quietly saving your program from a category of bug that other languages simply live with.

At the very end of episode 22 I dropped a hint: I said there are rules about where you are allowed to write a trait impl, tied to which crate owns the trait and which owns the type, and that this was "a coherence question we will pick apart very soon". Well, soon is now. This episode is the whole story -- the rule in one sentence, the reason the rule has to exist, the precise table of what is and is not allowed, and the clean idiomatic escape hatch for when the rule genuinely gets in your way. Let's clear last episode's homework first, as always, and then get into it ;-)

Solutions to Episode 22 Exercises

Episode 22 was all about #[derive(...)] -- the compiler-generated, field-by-field trait implementations for the common nine (Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord, Default). Three exercises, and here is each one with full, runnable code.

Exercise 1 asked you to define an enum Direction with variants North, East, South, West, derive Debug and PartialEq, and compare one equal pair and one unequal pair in main:

#[derive(Debug, PartialEq)]
enum Direction { North, East, South, West }

fn main() {
    let a = Direction::North;
    let b = Direction::North;
    let c = Direction::West;
    println!("{:?} == {:?} -> {}", a, b, a == b); // North == North -> true
    println!("{:?} == {:?} -> {}", a, c, a == c); // North == West -> false
}

The key insight is that #[derive(PartialEq)] on an enum compares the variants -- two values are equal only when they are the same variant (and, for variants that carry data, when that data is equal too). Debug is what lets us print each value with {:?}. Both impls were generated for us the instant we wrote that one derive line; we did not write a single comparison by hand.

Exercise 2 wanted a Coord { x: i32, y: i32 } struct with #[derive(PartialEq, Eq, Hash)], inserted into a HashSet twice with the same value plus one different value, printing .len() to prove the duplicate was collapsed:

use std::collections::HashSet;

#[derive(PartialEq, Eq, Hash)]
struct Coord { x: i32, y: i32 }

fn main() {
    let mut set = HashSet::new();
    set.insert(Coord { x: 1, y: 1 });
    set.insert(Coord { x: 1, y: 1 }); // duplicate: same hash, equal -> ignored
    set.insert(Coord { x: 2, y: 5 });
    println!("{}", set.len()); // 2
}

This is the payoff of deriving Eq and Hash together, which we insisted on as a pair last episode. The set hashes each Coord to pick a bucket, then uses equality to check for an existing entry in that bucket. Because the derived Hash and the derived Eq are guaranteed to agree by construction, the second insert of {1, 1} is correctly recognised as a duplicate and dropped, leaving a length of two.

Exercise 3 asked you to add a patch: u32 field to Version, keep all the derives, build a Vec of three versions differing only in patch, sort it, and confirm the tie on major and minor is broken by that third component:

#[derive(PartialEq, Eq, PartialOrd, Ord, Debug)]
struct Version { major: u32, minor: u32, patch: u32 }

fn main() {
    let mut v = vec![
        Version { major: 1, minor: 0, patch: 2 },
        Version { major: 1, minor: 0, patch: 0 },
        Version { major: 1, minor: 0, patch: 1 },
    ];
    v.sort(); // major ties, minor ties, so patch decides
    println!("{:?}", v.iter().map(|x| x.patch).collect::<Vec<_>>()); // [0, 1, 2]
}

Here the derived Ord compares fields lexicographically in declaration order: major first, then minor, then patch. Since all three versions share major = 1 and minor = 0, the comparison falls through to patch, and the vector sorts into 0, 1, 2 order. You controlled the sort priority purely by the order in which you wrote the fields -- no comparison logic by hand. Right, homework cleared. On to coherence ;-)

The rule in one sentence

Here is the whole thing, and it really does fit in a sentence:

You may write impl Trait for Type only if the trait is defined in your crate, or the type is defined in your crate (or both). If both the trait and the type come from other crates, the implementation is forbidden.

That forbidden case -- foreign trait, foreign type -- is what gives the rule its name. An impl with neither a local trait nor a local type is called an orphan impl, because it has no "parent" in your crate to anchor it. The standard library counts as "another crate" here, which is exactly why impl Display for Vec<i32> will not compile: both Display and Vec live in std, and your crate owns neither.

Notice what the rule does not forbid. It is perfectly happy for you to own just one side of the pair. Own the trait? Implement it for anything. Own the type? Implement any trait for it. You only hit the wall when you own nothing on either side.

Coherence: the property the rule protects

Before the allowed cases, let's name the thing the orphan rule exists to guarantee, because the rule makes no sense without it. That thing is coherence, and the definition is short:

For any given trait-and-type pair, there is at most one implementation in the entire program.

One impl of Display for Temperature. One impl of Iterator for MyRange. Never two. This is a property of the whole linked program, not of any single crate, and that global scope is the crux of everything that follows. When your code calls some_vec.to_string(), the compiler must be able to look up the Display impl for that type, resolve it once, and generate a direct call. If there could be two competing impls, that lookup would be ambiguous, and the language would have to either pick one arbitrarily (a nightmare -- your program's behaviour depending on link order) or reject the program (too late, the crates already compiled fine on their own). Coherence is what makes trait method resolution a question with exactly one answer, always.

The orphan rule is the mechanism that enforces coherence at the crate boundary. Each crate is compiled separately, often by people who have never met, and they cannot see each other's impls. The only way to guarantee globally that nobody writes a second Display for Vec<i32> is to make a rule that every crate can check locally, without seeing the others. "You must own the trait or the type" is exactly that rule: it partitions the space of all possible impls so that responsibility for any given pair belongs to precisely one crate. Coherence is the goal; the orphan rule is the enforceable, local approximation of it.

When you own the trait

The first allowed case: if you define the trait yourself, you can implement it for absolutely any type, including standard ones you did not write:

trait Summary {
    fn summarize(&self) -> String;
}

impl Summary for String {
    fn summarize(&self) -> String {
        format!("{} chars, starts with '{}'", self.len(), &self[..1])
    }
}

fn main() {
    let s = String::from("hello world");
    println!("{}", s.summarize()); // 11 chars, starts with 'h'
}

This compiles because Summary is local to your crate. No other crate in the universe can define a trait called Summary that is your Summary -- trait identity in Rust is tied to the crate and module path where it was declared, not to its name. So the moment you own the trait, you are the only party who can possibly write impls involving it, and coherence is safe no matter how many foreign types you target. You can spread a local trait across as many foreign types as you please:

trait Describe {
    fn describe(&self) -> String;
}

impl Describe for i32 {
    fn describe(&self) -> String { format!("the integer {self}") }
}
impl Describe for bool {
    fn describe(&self) -> String { format!("the boolean {self}") }
}
impl Describe for &str {
    fn describe(&self) -> String { format!("the string slice {self:?}") }
}

fn main() {
    println!("{}", 42.describe());        // the integer 42
    println!("{}", true.describe());      // the boolean true
    println!("{}", "hi".describe());      // the string slice "hi"
}

Three impls, three foreign types (i32, bool, &str all live in the standard library), and all of it is fine, because Describe belongs to you. This "define a local trait, then implement it for foreign types" move is called an extension trait, and it is genuinely one of the most useful patterns in the language -- it is how a crate can bolt new methods onto str, Iterator, Result, or any std type without owning them. You will meet extension traits constantly in real Rust libraries, and now you know precisely why they are allowed.

When you own the type

The mirror case works just as cleanly: you can implement any foreign trait for a type you defined. This is the everyday one -- implementing Display for your own struct, which we did back in episode 18's neighbourhood, is exactly this:

use std::fmt;

struct Temperature(f64);

impl fmt::Display for Temperature {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{} degrees", self.0)
    }
}

fn main() {
    println!("{}", Temperature(20.5)); // 20.5 degrees
}

Display is a foreign trait (it lives in std::fmt), but Temperature is local -- only your crate defines it, so only your crate can ever write impls for it. There is no way for a second crate to produce a competing Display for Temperature, because no second crate even knows Temperature exists. Coherence holds automatically. This is the case you have been quietly relying on every single time you wrote impl SomeStdTrait for MyStruct, all the way back through From (episode 21), Drop (episode 20), Deref (episode 19) and the operator traits (episode 18). Every one of those was legal for the same reason: you owned the type.

When you own neither: the forbidden case

Now the case that started this whole episode. You cannot implement a foreign trait for a foreign type. Display for Vec<i32> is the textbook example, because both halves belong to the standard library:

use std::fmt;

// This block would NOT compile -- it is an orphan impl:
//
// impl fmt::Display for Vec<i32> {
//     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
//         write!(f, "a vector of {} ints", self.len())
//     }
// }

fn main() {
    println!("Display for Vec<i32> is an orphan impl -- rejected at compile time");
}

Uncomment that impl and the compiler hands you error E0117, "only traits defined in the current crate can be implemented for arbitrary types", pointing straight at the line. Neither fmt::Display nor Vec is yours, so the impl is an orphan, and the rule shuts it down.

Why so strict, though, when this particular impl looks so harmless? Because the compiler is not reasoning about your crate in isolation -- it is defending the whole program that your crate might one day be linked into. Picture the disaster.

The diamond of doom

Imagine two crates, both perfectly reasonable, neither aware of the other. Crate pretty wants vectors printed one-per-line, so it writes impl Display for Vec<i32>. Crate compact wants them printed comma-separated on one line, so it writes its own impl Display for Vec<i32>. On their own, in isolation, both crates compile without complaint -- each is just implementing a std trait for a std type.

Now your application depends on both pretty and compact (perhaps indirectly, three layers deep in your dependency tree, where you would never even notice). The linker now holds two implementations of Display for Vec<i32>. When your code runs some_vec.to_string(), which impl fires? The one-per-line version, or the comma-separated one? There is genuinely no correct answer -- and worse, whichever the compiler picked, adding an unrelated dependency later could silently flip it, changing your program's output with no code change of your own. That is the diamond of doom: two paths through your dependency graph arriving at contradictory impls for the same pair.

The orphan rule makes this scenario impossible to construct. Because neither pretty nor compact owns Display or Vec, neither is allowed to write that impl in the first place. The conflict cannot happen because the crates that would have caused it were stopped at their own compile time, long before they ever met on your linker's desk. That is the entire payoff: a rule each crate can check alone, guaranteeing a property about all crates together. Rather elegant, once you see it ;-)

The newtype workaround

So what do you actually do when you genuinely need Display for Vec<i32> (or any foreign-trait-on-foreign-type combination)? You reach for the idiomatic escape hatch: the newtype pattern. Wrap the foreign type in a tiny local struct -- a struct you now own -- and implement the trait on the wrapper:

use std::fmt;

struct Wrapper(Vec<i32>);

impl fmt::Display for Wrapper {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let joined: Vec<String> = self.0.iter().map(|n| n.to_string()).collect();
        write!(f, "[{}]", joined.join(", "))
    }
}

fn main() {
    let w = Wrapper(vec![1, 2, 3]);
    println!("{w}"); // [1, 2, 3]
}

Look at what just happened. Wrapper is a single-field tuple struct that holds the Vec<i32>, and because Wrapper is defined in your crate, you own the type -- which drops us right back into the "when you own the type" case that is fully allowed. The impl is legal, coherence is preserved (only your crate can write impls for Wrapper), and you got your custom Display behaviour. The term "newtype" comes from Haskell, and the idea is the same: a zero-cost wrapper that is a genuinely distinct type in the eyes of the compiler while being just the inner value at runtime (a Wrapper has the exact same memory layout as the Vec inside it -- there is no overhead).

The one real cost is ergonomic: Wrapper is not a Vec, so you access the inner vector through self.0, and you lose the vector's own methods on the wrapper. You cannot call w.len() or w.push(4) directly, because Wrapper has no such methods -- only the Vec inside does.

Restoring the inner methods with Deref

Here is where a piece from earlier in the series clicks into place. Remember Deref from episode 19? It lets a wrapper type transparently expose the methods of what it wraps, through deref coercion. We can bolt it onto Wrapper and get the Vec's entire method surface back:

use std::fmt;
use std::ops::Deref;

struct Wrapper(Vec<i32>);

impl Deref for Wrapper {
    type Target = Vec<i32>;
    fn deref(&self) -> &Vec<i32> {
        &self.0
    }
}

impl fmt::Display for Wrapper {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "[{}]", self.iter().map(|n| n.to_string())
                              .collect::<Vec<_>>().join(", "))
    }
}

fn main() {
    let w = Wrapper(vec![10, 20, 30]);
    println!("len is {}", w.len());   // 3  -- Vec::len, reached via Deref
    println!("first is {:?}", w.first()); // Some(10) -- Vec::first, via Deref
    println!("{w}");                  // [10, 20, 30] -- our own Display
}

Now w.len() and w.first() work as if Wrapper were a Vec, because deref coercion forwards those calls to the inner value, while our custom Display sits on top. Notice I even used self.iter() inside the Display impl itself, letting the Deref do the work in stead of writing self.0.iter(). You get the best of both: a distinct type you can hang foreign trait impls on, plus near-transparent access to the wrapped type's API. That combination -- newtype for ownership, Deref for ergonomics -- is a workhorse pattern you will use again and again.

A small word of caution, since I am honest with you: leaning on Deref to fake inheritance is mildly frowned upon when the inner type is a full-blown collection like Vec, because it exposes every method, including ones you might not want on your abstraction. For a wrapper whose whole point is to restrict the inner API (say, a NonEmptyVec that must never be emptied), you would deliberately not impl Deref, and instead expose only the handful of methods you want. But for the "I just need to dodge the orphan rule and keep the ergonomics" case, Deref on the newtype is exactly the right tool.

How other languages handle this

Since a good chunk of you arrived here from Python (as I did, having taught it for years), it is worth seeing that the orphan problem is not unique to Rust -- other languages face the same question and answer it very differently, usually by not protecting you at all.

Python has no orphan rule whatsoever. You can reach into any class, including built-ins' subclasses, and monkey-patch methods onto it at runtime:

# "monkey patching" -- Python's answer to the orphan question is "do whatever you like"
class MyList(list):
    pass

def shout(self):
    return f"LIST OF {len(self)} ITEMS!"

MyList.shout = shout        # bolt a method on after the fact, at runtime
print(MyList([1, 2, 3]).shout())   # LIST OF 3 ITEMS!

This is enormously flexible and occasionally catastrophic. If two libraries both monkey-patch the same method onto the same class, the one imported last wins, silently, and you get action-at-a-distance bugs that are genuinely miserable to track down. Python trades Rust's compile-time guarantee for total runtime freedom, and the community has learned to treat monkey-patching as a code smell precisely because of the coherence problems it invites.

Go sits somewhere in between. You cannot add methods to a type from another package at all -- method definitions must live in the same package as the type -- which is Go's blunt version of the orphan rule. But Go's interfaces are structural (a type satisfies an interface just by having the right methods, no explicit impl needed), so the "two conflicting impls" problem mostly cannot arise the way it does in Rust. The trade-off is that Go gives you far less power to retrofit behaviour onto existing types -- no extension traits, no newtype-plus-deref elegance. Three languages, three points on the freedom-versus-safety line: Python maximally free and unprotected, Go restrictive and simple, Rust restrictive but with a precise, principled escape hatch. I know which trade-off I want when a program has to link a hundred crates together and still be correct ;-)

What did we actually learn?

  • The orphan rule: you may write impl Trait for Type only when you own the trait or the type (or both). Foreign trait on foreign type is forbidden -- that is the "orphan" impl.
  • The rule exists to enforce coherence: the guarantee that every trait-and-type pair has at most one implementation across the entire linked program, so method resolution always has exactly one answer.
  • Owning the trait lets you implement it for any foreign type (the extension trait pattern); owning the type lets you implement any foreign trait for it (every impl StdTrait for MyStruct you have written).
  • Without the rule you get the diamond of doom: two independent crates each writing impl Display for Vec<i32>, compiling fine alone, then colliding irreconcilably when both end up in your dependency tree.
  • The newtype pattern is the clean workaround: wrap the foreign type in a local struct you own, implement the trait on the wrapper, and use Deref (episode 19) to restore the inner type's methods.

The thread running through this whole stretch of the series is Rust handing you sharp, principled tools and then being strict about how they compose -- and that newtype wrapper we just built to dodge the orphan rule turns out to be far more than a workaround. It is a design pattern in its own right, one that lets you attach meaning, invariants, and even entirely new behaviour to a plain inner value. That is where we head next, along with a companion trick for writing one impl that covers a whole family of types at once. One thing at a time ;-)

Exercises

Three exercises as always, gentle to chewier. Full solutions open the next episode, so genuinely have a go first -- typing this yourself is where it sticks.

  1. Define a local trait Loud with a method shout(&self) -> String, and implement it for both i32 and &str so that 42.shout() returns "42!!!" and "hi".shout() returns "HI!!!". Confirm both compile and print the expected output. (This is the extension-trait case: you own the trait, so foreign types are fair game.)
  2. Try to write impl std::fmt::Display for Vec<String> directly and read the exact compiler error you get. Then fix it the idiomatic way: wrap Vec<String> in a newtype Lines, implement Display on Lines so it prints each string on its own line, and print a Lines value built from three strings.
  3. Take your Lines newtype from exercise 2 and add a Deref impl targeting Vec<String>, then call .len() and .iter() on a Lines value directly (without touching .0) to prove the inner vector's methods are reachable through the wrapper.

De groeten, en tot de volgende keer! ;-)

@scipio

stem stemsocial steemstem rust programming
0
0
0.000
0 comments