Trait Coherence and Orphan Rules in Open Worlds

A type class or a trait is a table of implementations indexed by type, and the compiler resolves each use by looking up the entry for the type it is given. The table is global: a call site in one crate can select an implementation defined in another, and the compiler must be able to see every candidate entry at the point of selection. That requirement is what forces a restriction on where implementations may be written, because a global table with unrestricted addition has no closed set of candidates, and dispatch would depend on which crates happened to be linked.

The second requirement is less obvious and more consequential: the table is also unordered. C++ resolves overloads by a partial order over candidate signatures, and a call in one translation unit can pick a different candidate than the same call in another if the visible set differed. Templates behave similarly: an instantiation uses whichever specialisation was declared before the point of instantiation in that unit. For per-type implementations the language can afford neither source-order sensitivity nor link-order sensitivity — one generic function may be compiled once and called from everywhere — so the lookup has to be a total function of the type and the trait, identical in every crate that can see both.

Why a global table needs an ownership rule

Consider two libraries, neither aware of the other. Library A defines a type Meters. Library B defines a trait Render. Nothing prevents a third crate from writing impl Render for Meters. If it does, then every crate in the program that calls render on a Meters value now resolves to that implementation, including crates compiled before it existed. The behaviour of a compiled call site depends on the set of crates linked into the final program, which is precisely the property a separate-compilation language wants to avoid.

The orphan rule forbids this. An implementation of a trait for a type is permitted only if the trait is local to the crate or the type is local to the crate. The name comes from the case the rule excludes: an implementation where both the trait and the type come from other crates is an orphan, and it is rejected. In Rust the rule is stated as a requirement that at least one of the trait or the self type be defined in the current crate, with additional coverage rules for generic parameters so that a local type cannot be smuggled in as a type argument to an otherwise foreign trait. The restriction is the implementation-level counterpart of the module sealing described in applicative and generative functors: in both cases a type’s meaning is fixed by the unit that defines it rather than by the units that use it.

The rule’s effect is that every implementation is owned by exactly one crate: the one that defined either the trait or the type. A downstream crate cannot add an implementation that changes the meaning of code it did not compile, and a call site’s resolution is determined by the crates it can see plus the transitive dependencies that own the relevant definitions. The compiler can then reject an ambiguity at compile time rather than resolve it by link order.

The cost is paid by exactly the case the rule forbids. A program that wants Render on Meters and owns neither must define a newtype wrapper and implement the trait for the wrapper, forwarding the methods. That is a few lines of boilerplate per combination, and it changes the type identity, so values must be wrapped and unwrapped at the boundary. The alternative, a language that permits orphans, must either accept link-order-dependent behaviour or detect the conflict at link time and refuse to load the program.

Coherence is a property of the whole program

Coherence means that for any type and trait, at most one implementation is selected, and every use selects the same one. It is a global property, not a local one: a crate can be internally consistent and still conflict with another crate’s implementation.

The check therefore has to run over the whole dependency graph, and the compiler must be able to see all implementations of a trait that could apply to a given type. Two implementation sets conflict when they overlap: there exists a type for which both apply. Overlap is decidable in the common case but not in general, because it reduces to unification of the implementation heads, and generic implementations can overlap in ways that require reasoning about associated types.

Where the general problem is undecidable or too expensive, languages restrict the form of implementations so that overlap checking is tractable. Rust’s coverage rules are one such restriction: for an implementation of a foreign trait, at least one type among the trait’s type arguments and the self type must be local to the crate, and no uncovered type parameter may appear before the first local type in that sequence. They reduce the check to a syntactic condition on the implementation head, at the price of rejecting some implementations that would not actually conflict.

The failure mode when the check is too weak is a program that compiles in isolation and fails when a new dependency is added. The failure mode when it is too strong is a legitimate implementation that the language cannot express, which pushes programmers toward wrappers or toward defining the trait locally when they do not own it. Both are real, and the placement of the boundary is a language design decision rather than a technical necessity.

Overlap, specialisation, and the closed-world assumption

Coherence is easy if the set of implementations is closed: the compiler sees all of them, checks pairwise for overlap, and rejects conflicts. That is the situation in a language with a single compilation unit, and it is also the situation in Haskell for a single program, where orphan instances are permitted but produce a warning and are known to break under separate compilation.

The problem is that the closed-world assumption conflicts with the open-world assumption that libraries want. A library defines a trait and expects downstream types to implement it; that is an open world, and coherence cannot be guaranteed without the orphan rule. A library defines a trait, implements it for its own types, and never expects more; that is a closed world, and the rule is unnecessary overhead. The language must choose one default, and the two defaults produce very different library ecosystems.

Haskell chooses the open world and permits orphans, with the consequence that a program’s behaviour can depend on which instances are in scope, and that two libraries defining the same orphan instance produce a link-time or load-time conflict that the compiler cannot diagnose. The workaround in practice is to define an instance only where the class or the type is local to the module that defines it, which is the Rust rule adopted by convention.

Specialisation is the feature that strains coherence most. A compiler that wants to replace a generic implementation with a faster one for a specific type needs two implementations that overlap, with a rule that the more specific one wins. That is exactly what coherence forbids, so specialisation requires an explicit opt-in and a guarantee that the specialised implementation is visible wherever the generic one is. Rust’s specialisation design has been constrained by this requirement, and the constraint is not accidental: without it, adding a specialised implementation in a new version of a library would silently change the behaviour of downstream code.

Where the table lives at run time

A trait method call in a generic function is resolved at compile time, so no dispatch table is consulted: the compiler emits a direct call to the concrete implementation, a process called monomorphisation. No table exists at run time, and the cost is code duplication: each instantiation produces its own copy of the function, which is why generic-heavy programs can produce large binaries. The alternative, used when the concrete type is not known, is a trait object: a pointer to the value plus a pointer to a vtable of the trait’s methods, built by the compiler for each concrete type that is used as a trait object.

The vtable for a trait object is the same structure described in vtable layout and the cost of a virtual call, with one difference in how it is built: its entries correspond to the trait’s methods, in the trait’s declaration order, so a caller holding a trait object can call through a fixed slot without knowing the concrete type. Methods the concrete type defines but the trait does not declare have no slot in that table.

Coherence guarantees that the vtable built for a given type and trait is unique, which is what makes it sound to pass trait objects across crate boundaries. If two crates could define conflicting implementations, a trait object created in one crate and used in another might carry a vtable whose entries do not match the caller’s expectation, and the call would jump to the wrong function. The orphan rule is therefore not only a compile-time convenience; it is what makes the dynamic form of dispatch well defined in a program assembled from independently compiled parts.

Living with the restriction

The practical consequences for a library author are worth stating plainly. A trait should be defined in the crate that owns the concept, not in a utility crate that merely uses it, because the definition site determines who may implement it. A type should be defined in the crate that owns its invariants, for the same reason. A crate that wants to provide implementations for both should be the crate that defines one of them, and the common pattern is a small adapter crate that owns the type and implements foreign traits for it.

The restriction also shapes how generic APIs are designed. A function that takes impl Trait and requires a caller-supplied implementation must be written so that the caller can supply it through a type the caller owns, which usually means a wrapper or a closure rather than an implementation on a foreign type. That pushes designs toward passing behaviour as values rather than as implementations, which is a change in style but not in expressive power: a closure carrying the behaviour is equivalent to a wrapper type implementing the trait.

The alternative direction, taken by languages with nominal interface implementation and no orphan rule, is to accept that adding an implementation can change the meaning of existing code and to rely on the build system to detect conflicts at link time. That works when the program is built as a whole and fails when it is assembled from binary artifacts. The trade is the same one that appears throughout this cluster: a rule that makes composition predictable by restricting where definitions may be written, against a rule that maximises local freedom at the cost of global guarantees.