Traits — behavior as a checked contract

Lesson 10's functions accepted any error type that had made the right promises — Display, Error, From — without saying what a promise is. A trait names a behavior, an impl proves one type has it, and a bound lets generic code use it and nothing more; the compiler checks each where it is written. Because "does this type do this?" must have one answer program-wide, impls must be unique, and two rules keep them so: the orphan rule and the overlap check. derive, operators and receivers are the same contract, applied.

1 · The function that works for one type

A thermostat logs whole-degree readings in a slice and wants the highest:

fn largest(items: &[i32]) -> i32 {
    let mut best = items[0];
    for &x in items {
        if x > best { best = x; }
    }
    best
}

We want the same for f64 readings and String names. Nothing in the body is about i32 except that it compares, so the function must be able to say "any type that can do this" — and the compiler must hold both sides to it.

Rust's road is a named contract, checked at both ends. A trait declares signatures. impl Trait for Type supplies them for one type. A function declares a type parameter with a bound, T: Ranked — "any T that implements Ranked" — and its body may call exactly what the trait declares. (Generic functions in full are Lesson 12's.)

trait Ranked {
    fn outranks(&self, other: &Self) -> bool;   // a signature: the promise
}
impl Ranked for f64 {
    fn outranks(&self, other: &f64) -> bool { *self > *other }
}
impl Ranked for String {
    fn outranks(&self, other: &String) -> bool { self.len() > other.len() }
}
fn largest<T: Ranked>(items: &[T]) -> &T {       // the bound: what the body may use
    let mut best = &items[0];
    for item in items {
        if item.outranks(best) { best = item; }
    }
    best
}
fn main() {
    println!("{}", largest(&[1.5, 9.25, 4.0]));
    println!("{}", largest(&[String::from("ox"), String::from("heron")]));
}

9.25
heron

The type's end is checked: an impl Ranked for bool {} that leaves out outranks is rejected with E0046, so "implements Ranked" cannot be claimed without being delivered. So is the body's end: a generic body may use only what its bounds promise. Nothing calls the function below. It is checked at its definition, against every type its signature admits — where a C++ template waits for each instantiation.

fn show<T>(t: T) {
    println!("{}", t);        // the body uses Display; the signature never promised it
}

error[E0277]: `T` doesn't implement `std::fmt::Display`
 --> src/lib.rs:2:20
2 |     println!("{}", t);        // the body uses Display; the signature never promised it
  |               --   ^ `T` cannot be formatted with the default formatter
  = note: in format strings you may be able to use `{:?}` (or {:#?} for pretty-print) instead
help: consider restricting type parameter `T` with trait `Display`
1 | fn show<T: std::fmt::Display>(t: T) {

std already names the behavior largest needs: the comparison operators are the trait PartialOrd (§6), so fn largest<T: PartialOrd> is the generic version, and §5 runs it. Before leaning on contracts, though, we need to know what one may contain.

2 · Anatomy of a contract

Inside a trait, Self is the implementing type (outranks compared a value with another of its own type). A trait may carry default methods, bodies built on the required items, which an impl inherits or overrides. And it may require another trait: trait Loud: Describe makes Describe a supertrait, so every Loud type is a Describe type and Loud's bodies may call Describe's methods.

trait Describe {
    fn name(&self) -> String;                    // required
    fn describe(&self) -> String {               // default, built on `name`
        format!("a {}", self.name())
    }
}
trait Loud: Describe {                           // supertrait: every Loud is a Describe
    fn shout(&self) -> String { self.describe().to_uppercase() }
}
struct Bell;
impl Describe for Bell { fn name(&self) -> String { String::from("bell") } }
impl Loud for Bell {}
fn main() { println!("{} / {}", Bell.describe(), Bell.shout()); }

a bell / A BELL

A trait can also leave a type for each impl to choose, in two ways. An associated type (type Item in Iterator) is chosen once, by the one impl for a type — a second impl Iterator for the same type is E0119, §3's overlap error. A type parameter on the trait (From<T>) lets one type implement it once per argument, which is how ?'s From look-up (Lesson 10) finds a conversion by the pair of types. One impl per type suggests an associated type; many, a parameter.

struct Countdown(u32);
impl Iterator for Countdown {
    type Item = u32;                             // chosen once, by the one impl
    fn next(&mut self) -> Option<u32> {
        if self.0 == 0 { return None; }
        self.0 -= 1;
        Some(self.0 + 1)
    }
}
struct Meters(f64);
impl From<f64> for Meters { fn from(m: f64) -> Meters { Meters(m) } }
impl From<u32> for Meters { fn from(m: u32) -> Meters { Meters(m as f64) } }  // a second impl
fn main() {
    let total: u32 = Countdown(3).sum();         // a default method of Iterator
    let a = Meters::from(2.5);
    let b: Meters = 7u32.into();                 // the argument's type picks the impl
    println!("{total} {} {}", a.0, b.0);
}

6 2.5 7

A method's first parameter, its receiver, is Lesson 05's three ownership modes written into the contract — &self shared, &mut self exclusive, self by value — so a trait tells every caller what each call costs the caller's variable. p.push(3) borrows p automatically; p.into_bytes() moves it.

trait Buffer {
    fn len(&self) -> usize;                      // shared: the caller keeps it
    fn push(&mut self, byte: u8);                // exclusive: the caller lends it
    fn into_bytes(self) -> Vec<u8>;              // by value: the caller gives it up
}
struct Packet(Vec<u8>);
impl Buffer for Packet {
    fn len(&self) -> usize { self.0.len() }
    fn push(&mut self, byte: u8) { self.0.push(byte); }
    fn into_bytes(self) -> Vec<u8> { self.0 }
}
fn main() {
    let mut p = Packet(vec![1, 2]);
    p.push(3);                                   // auto-borrow: Buffer::push(&mut p, 3)
    let bytes = p.into_bytes();                  // p moves into the call
    println!("{} {}", bytes.len(), p.len());     // ...so p is gone
}

The comment on p.push(3) is what the call means: Buffer::push(&mut p, 3). Writing that path yourself is how a caller picks between two traits that give one type same-named methods; §6 spells a call out this way.

Every piece so far answered "does this type keep this promise, and how?" with one impl. Nothing yet says there is only one.

3 · Coherence: one answer per question

Suppose two libraries each write their own impl Display for Vec<i32>. A program using both has two answers to one question. C++ meets this with inline functions, which may be defined in many places because every copy is assumed identical, so the linker keeps just one (C++ 01). When the copies differ, neither library's author can know whose version runs.

// library A's header
inline std::ostream& operator<<(std::ostream& o, const std::vector<int>& v) { return o << v.size() << " scores"; }
// library B's header
inline std::ostream& operator<<(std::ostream& o, const std::vector<int>& v) { return o << "[...]"; }
// linking A and B breaks the one-definition rule: which one runs is not defined

One road lets each impl apply only where it is in scope — Scala's (FP 14): an instance is a given anyone may write anywhere. Then the answer depends on where you ask: a set built where one Hash is visible but searched where another is would hash one key two ways. Another road checks at link time — too late: the error lands on whoever merely used both, and RFC 2451's first goal is that depending on two crates never breaks a build. What remains is one global answer: at most one impl of a trait for a type in the whole program — coherence. No crate sees the crates that will be linked with it, so coherence is checked one crate at a time, by the orphan rule: an impl is allowed only if the trait, or a type in its header, is defined in the current crate — is local.

use std::fmt;
impl fmt::Display for Vec<i32> {              // std's trait, std's type
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{} scores", self.len())
    }
}

error[E0117]: only traits defined in the current crate can be implemented for types defined outside of the crate
 --> src/lib.rs:2:1
2 | impl fmt::Display for Vec<i32> {              // std's trait, std's type
  | ^^^^^^^^^^^^^^^^^^^^^^--------
  |                       |
  |                       `Vec` is not defined in the current crate
  = note: impl doesn't have any local type before any uncovered type parameters
  = note: define and implement a trait or new type instead

If every impl must involve a name its own crate defines, two unrelated crates can never write the same one. The note gives the way out: a newtype, a one-field tuple struct around the foreign type. It is local, so the impl is yours to write, and it is free — exactly as large as what it wraps.

use std::fmt;
struct Scores(Vec<i32>);                         // a local type around a foreign one
impl fmt::Display for Scores {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{} scores, best {}", self.0.len(), self.0.iter().max().unwrap_or(&0))
    }
}
fn main() {
    let s = Scores(vec![7, 9, 4]);
    println!("{s}");
    println!("{} {}", std::mem::size_of::<Scores>(), std::mem::size_of::<Vec<i32>>());
}

3 scores, best 9
24 24

The orphan rule keeps other crates out; within a crate the overlap check (E0119) keeps two impls from applying to one type. It turns subtle with blanket impls, which cover every type meeting a bound — std's impl<T: Display> ToString for T is why .to_string() works on anything printable. Give a trait of your own a blanket impl, then add specific ones:

use std::fmt::Display;
trait Describe { fn describe(&self) -> String { String::from("?") } }
impl<T: Display> Describe for T {}           // blanket: every Display type at once
struct Meters(f64);
impl Describe for Meters {}                  // accepted: Meters is yours, and not Display
impl Describe for Vec<u8> {}                 // rejected, though Vec<u8> is not Display today

error[E0119]: conflicting implementations of trait `Describe` for type `Vec<u8>`
 --> src/lib.rs:6:1
3 | impl<T: Display> Describe for T {}           // blanket: every Display type at once
  | ------------------------------- first implementation here
  = note: upstream crates may add a new impl of trait `std::fmt::Display` for type `std::vec::Vec<u8>` in future versions

Neither type is Display, yet one impl passes and one fails. The difference is who could change that. Only this crate could ever write impl Display for Meters — std cannot name Meters, and the orphan rule stops everyone else — so "not Display" is a fact this crate controls. std owns Display and Vec, and RFC 2451's second goal lets it add impl Display for Vec<u8> in a future version without breaking this crate, so the compiler treats that impl as possible. The overlap check reasons about every crate that could ever be linked with yours.

The full rule orders the header's types. In impl Trait<T1, …> for T0 with a foreign trait, some Ti must be local, and no bare type parameter (one not inside another type) may come before the first local one: impl<T> Display for T is E0210. References and Box do not hide a type — Box<Scores> is as local as Scores. Applying these rules by hand to a whole crate is slow, and the questions underneath them — may this crate write this impl, and does this type implement that trait — are mechanical.

4 · Does it implement it, and may I write it?

Both questions are computable. The first is a proof search: to show HashMap<String, Vec<f64>>: Eq, find the impl that applies and prove what it requires, recursively. The second is the orphan rule, then the overlap check against std's impls, the crate's own and its derives.

// coherence.js: the orphan rule
function orphan(imp, cr) {
  var inputs = [imp.self].concat(imp.args), out = { code: null, inputs: [], local: -1, uncovered: null };
  inputs.forEach(function (t) { out.inputs.push({ text: show(t), kind: isLocal(t, cr) ? 'local' : uncovered(t, null, 'param') ? 'uncovered' : 'foreign' }); });
  if (cr.traits[imp.trait]) { out.traitLocal = true; return out; }       // your trait: always allowed
  for (var i = 0; i < inputs.length; i++) {                             // T0 = Self, then the trait's arguments
    if (isLocal(inputs[i], cr)) { out.local = i; return out; }          // first local type: allowed
    var p = uncovered(inputs[i], null, 'param');
    if (p) { out.code = 'E0210'; out.uncovered = p.name; return out; }  // a bare T before any local type
  }
  out.code = 'E0117';                                                   // nothing local at all
  return out;
}
// evalGoal, excerpt: could `Type: Trait` hold in ANY crate linked with this one?
  // rustc's trait_ref_is_knowable: may another crate, now or in a future version, add an impl?
  var down = inputs.some(function (t) { return uncovered(t, s, 'var'); });
  if (down || (!ctx.cr.traits[g.trait] && !inputs.some(function (t) { return isLocal(t, ctx.cr, s); }))) {
    var sup = solveAll((SUPERS[g.trait] || []).map(function (tr) { return { trait: tr, self: g.self, args: [] }; }), s, ctx, depth + 1);
    if (!sup.may) return { may: false, why: sup.why };        // a supertrait can still rule it out
    return { may: true, why: down ? 'a downstream crate could implement ' + here
                                  : 'std may add an impl making ' + here + ' true in a future version' };
  }
  // the goal is yours to answer: only the impls that exist today can make it true

What to try. Example 3's readout chains a failure three levels deep: the map is not Eq because Vec<f64> is not, because f64 is not. Example 6 is §5's surprise: Shared<Mutex<i32>> is not Clone, though its only field is an Rc. Examples 14 and 15 are §3's pair; 15's readout says "std may add an impl making Vec<u8>: Display true in a future version". Example 16 clashes with an impl nobody typed. Then add Eq to Reading's derives and revisit example 5: "crate rejected", the derive failing at celsius: f64.

5 · derive — the impl only the compiler can write

Many impls are mechanical — clone each field, print each field — yet no generic function can write them, because a generic body sees only its bounds, never a struct's fields:

fn first_field<T>(t: &T) -> f64 { t.celsius }

Only code written for one struct — a Reading { celsius, label }, say — can see its fields, so the compiler writes that code: #[derive(Clone, Debug)] expands to ordinary impls, for any of nine traits — Clone, Copy, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash. Written by hand, they behave the same:

#[derive(Clone, Debug)]
struct Reading { celsius: f64, label: String }

struct ByHand { celsius: f64, label: String }
impl Clone for ByHand {                          // derive(Clone) clones each field
    fn clone(&self) -> ByHand {
        ByHand { celsius: self.celsius.clone(), label: self.label.clone() }
    }
}
impl std::fmt::Debug for ByHand {                // a Debug impl with derive's output
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        f.debug_struct("ByHand").field("celsius", &self.celsius).field("label", &self.label).finish()
    }
}
fn main() {
    let a = Reading { celsius: 21.5, label: String::from("attic") };
    let b = ByHand { celsius: 21.5, label: String::from("attic") };
    println!("{:?}", a.clone());
    println!("{:?}", b.clone());
}

Reading { celsius: 21.5, label: "attic" }
ByHand { celsius: 21.5, label: "attic" }

Every field must implement the trait, checked once, at the struct. A generic struct raises one more question — what does the impl require of the type parameter? — and derive answers without looking at how it is used: on Shared<T>, #[derive(Clone)] writes impl<T: Clone> Clone for Shared<T>. The bound is on T, not on the fields, so a Shared holding a Mutex is not Clone, although cloning its Rc never touches the Mutex:

use std::rc::Rc;
use std::sync::Mutex;
#[derive(Clone)]
struct Shared<T> { ptr: Rc<T> }                  // derive writes: impl<T: Clone> Clone for Shared<T>
fn twice<T: Clone>(t: &T) -> (T, T) { (t.clone(), t.clone()) }
fn main() {
    let s = Shared { ptr: Rc::new(Mutex::new(0)) };
    let pair = twice(&s);                        // Rc<Mutex<i32>> is Clone; Mutex<i32> is not
}

When derive's bound is too strict, write the impl and state the true requirement — here, none:

use std::rc::Rc;
use std::sync::Mutex;
struct Shared<T> { ptr: Rc<T> }
impl<T> Clone for Shared<T> {                    // no bound: cloning an Rc never clones the T
    fn clone(&self) -> Self { Shared { ptr: Rc::clone(&self.ptr) } }
}
fn main() {
    let s = Shared { ptr: Rc::new(Mutex::new(0)) };
    let t = s.clone();
    println!("{} owners", Rc::strong_count(&t.ptr));
}

2 owners

The nine, with Display and the conversions, are std's common vocabulary, and each carries a contract its signature does not state:

#[derive(Clone, Copy)] struct Token(u32);
impl Drop for Token { fn drop(&mut self) {} }

Floats show why the comparison traits come in pairs. sort needs Ord, so v.sort() on a Vec<f64> is rejected (E0277). The generic largest needs only PartialOrd, and shows what a partial order does: with a NaN in the slice the answer depends on where the NaN sits, because every comparison with it is false.

fn largest<T: PartialOrd>(items: &[T]) -> &T {
    let mut best = &items[0];
    for item in items {
        if item > best { best = item; }          // `>` is PartialOrd's method
    }
    best
}
fn main() {
    let nan = f64::NAN;
    println!("{} {} {}", largest(&[3, 9, 4]), largest(&[1.0, nan, 3.0]), largest(&[nan, 1.0, 3.0]));
}

9 3 NaN

What if an impl lies? Ord is a safe trait, so anyone may write a false one. The result is what the Reference calls a logic error — panics, wrong results or non-termination, never undefined behavior. A comparison that never says "equal" lets a set hold three copies of one key and then fail to find it:

use std::cmp::Ordering;
use std::collections::BTreeSet;
#[derive(PartialEq, Eq)]
struct Id(u32);
impl PartialOrd for Id {
    fn partial_cmp(&self, other: &Id) -> Option<Ordering> { Some(self.cmp(other)) }
}
impl Ord for Id {
    fn cmp(&self, _other: &Id) -> Ordering { Ordering::Less }   // a lie: never Equal
}
fn main() {
    let mut set = BTreeSet::new();
    for _ in 0..3 { set.insert(Id(7)); }
    println!("{} {}", set.len(), set.contains(&Id(7)));
}

3 false

6 · Operators are trait calls

The > in largest is a method of PartialOrd, and the arithmetic operators work the same way: a + b is Add::add(a, b), and add takes both operands by value — its receiver is self. That explains Lesson 04's box: String + &str moves the left string into the call.

fn main() {
    let hello = String::from("hello, ");
    let name = String::from("Ada");
    let greeting = hello + &name;
    println!("{greeting} {hello}");
}

The operand types are whatever the impl says, so a type that should not be consumed can implement the operator for references. Then &a + &b moves nothing, and §2's path form spells out the same call:

use std::ops::Add;
struct Samples(Vec<f64>);
impl Add for &Samples {                          // `+` on two borrowed Samples
    type Output = Samples;
    fn add(self, other: &Samples) -> Samples {
        let mut out = Vec::new();
        for i in 0..self.0.len() { out.push(self.0[i] + other.0[i]); }
        Samples(out)
    }
}
fn main() {
    let a = Samples(vec![1.0, 2.0]);
    let b = Samples(vec![0.5, 0.5]);
    let c = &a + &b;                             // Add::add(&a, &b): nothing moves
    let d = Add::add(&c, &a);                    // the same call, spelled out
    println!("{:?} {:?} {}", c.0, d.0, a.0.len());
}

[1.5, 2.5] [2.5, 4.5] 2

7 · Not classes

Read from Java or C++, a trait looks like an interface, and the differences are the ones that matter. It has no fields and no state to inherit. A type implements it only by an explicit impl — by name, not by shape as in Go. A generic body is checked once, against its bounds, unlike a C++ template without a concept. And on stable Rust there is no specialization: no impl may override another for a narrower set of types (widget example 13 is E0119, not an override). Lesson 13 completes the translation table; three rows now:

That completes the contract. largest<T: PartialOrd> is written once and checked once — yet comparing i32s, f64s and Strings takes different machine instructions, and a promise is not machine code.

Common mistakes / failure modes

Checkpoint exercise

Where this points next

"This type can do what the code needs" is now a fact the compiler checks at both ends, and coherence makes it the same fact everywhere. We have not asked what runs. largest compares with >, but i32s compare with one integer instruction, f64s with a floating-point one, Strings by walking two buffers: one body cannot be one piece of machine code unless every comparison is looked up at run time, which the budget rules out. The compiler must produce a version per concrete type — at what cost, and for what gain?

Interview prompts

• How does a trait differ from a Go interface and a C++ template? (§1, §7 — only an explicit impl satisfies it, not method shape; a generic body is checked once, at its definition, against its bounds: show<T> was rejected with no caller.)
• What is the orphan rule, and how do you implement Display for Vec<i32> anyway? (§3 — an impl needs a local trait or type in its header, so no two crates can write the same impl and each crate can be checked alone; wrap the vector in a free newtype.)
• Given impl<T: Display> Describe for T, why is impl Describe for Meters accepted but impl Describe for Vec<u8> not? (§3 — only your crate could make Meters: Display true; std may add Display for Vec<u8> later, so that overlap counts as possible: E0119.)
• Associated type or type parameter? (§2 — an associated type when each type implements the trait once (Iterator::Item); a parameter when it implements it once per argument type (From<T>).)
• What does #[derive(Clone)] write for Shared<T> { ptr: Rc<T> }, and when is it wrong? (§5 — impl<T: Clone> Clone for Shared<T>, stricter than cloning an Rc needs, so Shared<Mutex<i32>> is not Clone; a hand-written impl without the bound fixes it.)
• Why is f64 not Ord, and what does a lying Ord do? (§5 — NaN compares false with everything, so there is no total order; a lying Ord gives wrong answers, never undefined behavior in sound code.)
• Why does s1 + &s2 consume s1, and how can + avoid moving? (§6 — + is Add::add(self, rhs), which takes its operands by value; implement Add for &T so &a + &b only borrows.)

Companion reads: Go · 05 Interfaces (structural satisfaction), C++ · 12 Templates (checked per instantiation), C++ · 10 The vtable (what Lesson 13's dyn costs), FP · 14 Type classes (scoped instances), C++ · 01 The translation model (the one-definition rule).