FerrousPath

Level 5 · Research· Lesson 4 of 9 · 45 min

Trait solving and coherence

Traits as logic programming — Horn clauses, proof search, coinduction, normalisation, the next-generation solver, and the known soundness holes.

When you write x.clone() or T: Iterator<Item = u32>, the compiler must prove something. The component that does so — the trait solver — is a theorem prover for a restricted logic, and its design determines what generic code Rust can express, what error messages you see, and where soundness bugs hide.

Traits are predicates; impls are rules

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

impl Describe for u32 {
    fn describe(&self) -> String { format!("u32 {self}") }
}
impl<T: Describe> Describe for Vec<T> {
    fn describe(&self) -> String {
        format!("[{}]", self.iter().map(|x| x.describe()).collect::<Vec<_>>().join(", "))
    }
}
impl<A: Describe, B: Describe> Describe for (A, B) {
    fn describe(&self) -> String { format!("({} & {})", self.0.describe(), self.1.describe()) }
}

fn main() {
    let value = vec![(1u32, vec![2u32, 3]), (4, vec![])];
    println!("{}", value.describe());
}

Read as logic:

Describe(u32).
Describe(Vec<T>)  :- Describe(T).
Describe((A, B))  :- Describe(A), Describe(B).

To type-check value.describe() the solver must prove the goal Describe(Vec<(u32, Vec<u32>)>). It finds the rule whose head unifies, and recursively proves the body: a depth-first proof search, exactly as in Prolog. The proof tree it builds is also the recipe for code generation — which impl to call at each node.

This is why the trait system can compute (Level 4’s Peano numbers), why it has a recursion limit, and why error messages take the form “the trait bound … is not satisfied, required by a bound in …”: that is a failed proof, printed.

The pieces of the logic

Goals the solver handles include:

  • T: Trait<Args> — a trait predicate.
  • <T as Trait>::Assoc == U — a projection predicate.
  • T: 'a, 'a: 'b — outlives predicates (collected as constraints and discharged by the borrow checker’s region inference).
  • WF(T) — the type is well-formed.

Hypotheses come from the environment: the where-clauses of the item being checked (ParamEnv). Inside fn f<T: Clone>(), T: Clone is simply assumed.

Inference variables. Goals contain unknowns — Vec<?X>: IntoIterator<Item = ?Y>. Solving interleaves with type inference: a goal may be ambiguous now and be retried once more is known. This is why adding an impl can break type inference in downstream code: a goal that had one candidate, and so drove inference, now has two.

Candidates. For a trait goal the solver assembles candidates from impls, where-clauses, built-in rules (Sized, Copy for tuples, closures implementing Fn), and object/alias bounds; it then picks one or reports ambiguity. Where-clause candidates are preferred over impls — a rule with visible consequences when both apply.

Associated types and normalisation

Associated types make the logic much harder. <T as Iterator>::Item is a type-level function application, and the solver must be able to normalise it — rewrite it to a concrete type when the impl is known — and to treat it as an opaque rigid alias when it is not (inside a generic function, T::Item is just T::Item).

fn sum_all<I>(iter: I) -> I::Item
where
    I: Iterator,
    I::Item: std::ops::Add<Output = I::Item> + Default,
{
    iter.fold(I::Item::default(), |a, b| a + b)
}

fn main() {
    // Here the solver normalises <std::vec::IntoIter<f64> as Iterator>::Item to f64.
    println!("{}", sum_all(vec![1.5, 2.5].into_iter()));
}

Equality of types is therefore modulo normalisation, and deciding it requires solving trait goals, which requires comparing types. Getting that mutual recursion right — especially lazily, under binders, with higher-ranked types — has been the source of many compiler bugs and is a central motivation for rewriting the solver.

Induction, coinduction and cycles

What should the solver do when proving a goal requires proving the same goal?

struct List<T> {
    value: T,
    next: Option<Box<List<T>>>,
}

fn assert_send<T: Send>() {}

fn main() {
    // Send(List<u8>) needs Send(Option<Box<List<u8>>>), which needs Send(List<u8>) again.
    assert_send::<List<u8>>();
    println!("List<u8> is Send");
}
  • For ordinary traits the logic is inductive: a proof must be finite, and a cycle is a failure (or overflow).
  • For auto traits (Send, Sync, Unpin) and for well-formedness, the logic is coinductive: a cycle counts as success. The intended reading is “there is no field that fails to be Send” — a greatest rather than least fixed point.

Mixing inductive and coinductive goals in one cycle, with caching, is subtle; an unsound treatment would let the solver “prove” false things. The new solver has a carefully designed fixed-point algorithm for exactly this.

Higher-ranked goals

for<'a> F: Fn(&'a str) -> &'a str quantifies over all lifetimes. To prove a for<'a> goal, the solver instantiates 'a with a fresh placeholder — a region about which nothing is known — in a new universe, and proves the body. To use a higher-ranked hypothesis, it instantiates with an inference variable. Universes prevent a placeholder from leaking into an inference variable created before it existed. This is standard machinery from higher-order unification; its incomplete implementation is what lies behind the error “implementation is not general enough”.

Coherence

Coherence guarantees that a trait reference has at most one applicable impl across the entire crate graph. It is what makes it sound for a HashMap<K, V> built in one crate to be used in another: both must agree on K’s Hash. It has two parts:

Overlap check. Two impls overlap if their headers unify and the unified where-clauses could hold. Crucially, the check must be conservative about the future: an upstream crate may add impls later. So impl<T: Display> Foo for T and impl Foo for Vec<u8> are judged overlapping, because Vec<u8> might implement Display one day. The exceptions are #[fundamental] types and the cases where the orphan rule proves no such impl can ever be written elsewhere.

Orphan check. impl<P1..Pn> Trait<T1..Tn> for T0 is allowed only if the trait is local, or some Ti is a local type and no uncovered type parameter appears in T0..Ti-1. This guarantees that two crates which do not know about each other cannot both write the same impl.

Together these provide a modular guarantee: adding a dependency can never produce conflicting impls. The cost is expressiveness — you cannot implement a foreign trait for a foreign type — and a constraint on library evolution: a new blanket impl is a breaking change.

Negative reasoning (“T does not implement Trait”) is what coherence fundamentally needs and what the logic largely lacks. Negative impls (impl !Send for X) exist for auto traits; general negative bounds remain unstable because a bound T: !Trait turns adding an impl into a breaking change.

Specialization and its soundness problem

Specialization would allow overlapping impls where one is more specific:

// Nightly only: #![feature(specialization)] — and unsound as written.
impl<T> Describe for T { default fn describe(&self) -> String { "something".into() } }
impl Describe for &'static str { fn describe(&self) -> String { "a static string".into() } }

The second impl applies only when the lifetime is 'static. But lifetimes are erased before monomorphization: the code generator sees &str and cannot tell which impl the type checker chose. With associated types, the two phases can disagree about a type, which breaks memory safety. The restricted min_specialization used inside the standard library forbids specializing on lifetimes and on most traits (only “always applicable” impls). A sound, general design is an open research problem.

The solvers: old, Chalk, and next-generation

  • The original solver grew organically: separate machinery for selection, fulfilment and projection, each with its own caches. Its behaviour around normalisation, coinduction and higher-ranked bounds is under-specified, and several long-standing soundness bugs trace to it.
  • Chalk (2017–) was an experiment in implementing the trait system as an explicit logic engine: lower Rust to program clauses, solve with a Prolog-style SLG solver, canonicalise goals for caching. It clarified the theory and was used in rust-analyzer; it is no longer being pursued as rustc’s solver.
  • The next-generation trait solver (-Znext-solver) is the rewrite that took Chalk’s lessons into rustc’s own type representation: one uniform recursive solver, canonical queries with a sound cycle-handling fixed point, and lazy normalisation. It has been used for coherence checking on stable since Rust 1.84, with the rest of type checking being moved over incrementally. It is the prerequisite for a list of blocked features: implied bounds, coinductive trait goals, better handling of opaque types and GATs.
  • a-mir-formality models these rules executably, as a candidate specification.

Known soundness holes

Studying the open unsound issues is one of the fastest ways to understand a type system. The most famous is rust-lang/rust#25860 (2015), which exploits implied bounds together with contravariance:

static UNIT: &'static &'static () = &&();

// The type `&'a &'b ()` is well-formed only if 'b: 'a, so that bound is *implied*
// for the function body and need not be written.
fn helper<'a, 'b, T>(_: &'a &'b (), v: &'b T) -> &'a T { v }

fn extend<'a, 'b, T>(x: &'a T) -> &'b T {
    // Coercing to a fn pointer with 'static in the first argument silently
    // drops the implied bound — nothing re-checks 'b: 'a for the actual lifetimes.
    let f: fn(&'static &'static (), &'a T) -> &'b T = helper;
    f(UNIT, x)
}
// `extend` converts any reference into one of any lifetime, in safe code.

The implied bound is used when checking helper’s body but is not preserved when the function is coerced to a function-pointer type with a different first argument. The result is a safe function that fabricates arbitrary lifetimes — a use-after-free without unsafe. Fixing it properly requires treating implied bounds as real, higher-ranked where-clauses, which the old solver cannot represent; it is one of the motivating problems for the new one. The issue stayed open for a decade, is not known to have occurred accidentally in real code, and is an excellent case study in how subtle the interaction of variance, well-formedness and higher-ranked types is.

Try it: Rust 1.100, which this lesson was checked against, rejects the coercion in extend with “lifetime may not live long enough” — the implied bound is now re-checked. Compilers from the years when the hole was open accept the program as written.

Reading list

  1. The rustc dev guide: “Trait solving”, “The next-generation trait solver”, “Coherence”.
  2. Matsakis, “Lowering Rust traits to logic” and the follow-up blog posts (2017); the Chalk book.
  3. RFC 1023 (orphan rules), RFC 2451 (re-rebalancing coherence), RFC 1210 (specialization).
  4. Matsakis, “Maximally minimal specialization: always applicable impls” (2018).
  5. Wadler and Blott, “How to make ad-hoc polymorphism less ad hoc” (POPL 1989) — where type classes come from.
  6. Chakravarty, Keller, Peyton Jones and Marlow, “Associated types with class” (POPL 2005).
  7. The a-mir-formality repository; the rust-lang issue label I-unsound.

Exercises

  1. Write the program clauses for impl<T: Ord> Ord for Option<T> and impl<T: PartialOrd> PartialOrd for [T], then draw the proof tree for Option<Option<u8>>: Ord.
  2. Construct two impls that the overlap check rejects although no type currently satisfies both. Explain the “future compatibility” reasoning.
  3. Make a recursive type that is not Send, and trace the coinductive proof to the failing leaf.
  4. Read issue #25860 and the proposed fixes. Explain where exactly the implied bound is lost.
  5. Give an example where adding an impl to a library breaks type inference in a dependent crate without any coherence error.

Check your understanding

Pick an answer to see the explanation.

  1. 1.As a logic rule, how does impl<T: Clone> Clone for Vec<T> read?

  2. 2.Why are auto traits such as Send solved coinductively?

  3. 3.Why is unrestricted specialization unsound?

Key terms in this lesson

Finished the lesson and the exercises?