scrobble.life
StemSocial

Learn Rust Series (#44) - Higher-Ranked Trait Bounds & Lifetime Elision

scipio@scipio (71)4h

Learn Rust Series (#44) - Higher-Ranked Trait Bounds & Lifetime Elision

rust-banner.png

What will I learn

  • You will learn what a higher-ranked trait bound is and how for<'a> expresses "for every lifetime";
  • why closures that take references need HRTBs, and how the compiler usually adds them for you invisibly;
  • the three lifetime elision rules in full, so you know exactly when you can omit annotations;
  • when elision cannot decide and forces you to reach for an explicit 'a;
  • how these two features together explain most of the lifetime syntax you see in real Rust code.

Requirements

  • A working modern computer running macOS, Windows or Ubuntu;
  • An installed Rust toolchain (via rustup, from rustup.rs);
  • The previous forty-three episodes, especially lifetimes (episode 10), closures and the Fn traits (episode 11);
  • The ambition to learn systems programming from the ground up.

Difficulty

  • Intermediate

Curriculum (of the Learn Rust Series):

Learn Rust Series (#44) - Higher-Ranked Trait Bounds & Lifetime Elision

Two small lifetime features round out this phase, and between them they explain nearly all the lifetime syntax you have been staring at (and mostly not writing) since episode 10. The first is the higher-ranked trait bound, written with for<'a>, which lets you demand that something works for every possible lifetime -- exactly what a closure that takes a reference needs. The second is lifetime elision, the small set of rules that let you leave lifetime annotations off in the common cases so your function signatures stay readable. You have leaned on both since very early in the series without ever seeing their names; putting names to them is what finally makes the last of the lifetime mystery evaporate ;-)

Last episode I closed on a deliberate cliffhanger. The mem::replace-to-consume-a-variant trick, I said, was quietly leaning on some subtle machinery about how a generic function accepts borrowed data of any lifetime. That machinery is the higher-ranked trait bound, and it is where we head today. Having said that, let us clear the homework first.

Solutions to Episode 43 Exercises

Episode 43 was the std::mem toolbox -- swap, replace, take and forget. Three exercises, and here is full, runnable code for each.

Exercise 1 asked you to use mem::swap to rotate three variables so that a gets b's value, b gets c's, and c gets a's, using exactly two swaps, printing all three before and after:

use std::mem;

fn main() {
    let (mut a, mut b, mut c) = (1, 2, 3);
    println!("before: {a} {b} {c}"); // 1 2 3
    mem::swap(&mut a, &mut b); // a=2, b=1, c=3
    mem::swap(&mut b, &mut c); // a=2, b=3, c=1
    println!("after:  {a} {b} {c}"); // 2 3 1
}

The trick is the order. The first swap trades a and b; the second swap trades the new b (which is really a's old value) into c. After two swaps a holds 2, b holds 3, c holds 1 -- the three-way rotation you wanted, with no temporary variable and no clone.

Exercise 2 wanted a struct with an Option<String> field and a method that uses mem::take to pull the value out, leaving None behind, called twice to prove the second call yields None:

use std::mem;

struct Session { token: Option<String> }

impl Session {
    fn take_token(&mut self) -> Option<String> {
        mem::take(&mut self.token) // leaves None behind
    }
}

fn main() {
    let mut s = Session { token: Some(String::from("abc123")) };
    println!("{:?}", s.take_token()); // Some("abc123")
    println!("{:?}", s.take_token()); // None -- already taken
}

mem::take moves the value out and drops the type's default (None for Option) into the field. The first call hands you Some("abc123") and empties the slot; every call after that finds only None. This is precisely how the standard library's own Option::take works under the hood.

Exercise 3 asked you to model a traffic light as an enum (Red, Green, Yellow) and write fn next(&mut self) that uses mem::replace to consume the old state, compute the next colour from it, and write the new colour back -- without cloning or fighting the borrow checker:

use std::mem;

#[derive(Debug)]
enum Light { Red, Green, Yellow }

impl Light {
    fn next(&mut self) {
        let new = match mem::replace(self, Light::Red) {
            Light::Red => Light::Green,
            Light::Green => Light::Yellow,
            Light::Yellow => Light::Red,
        };
        *self = new;
    }
}

fn main() {
    let mut light = Light::Red;
    light.next();
    println!("{:?}", light); // Green
    light.next();
    println!("{:?}", light); // Yellow
    light.next();
    println!("{:?}", light); // Red
}

mem::replace(self, Light::Red) writes a cheap placeholder into *self and hands us back the old value by value, so we own it and can match it to pick the next colour, which we then write back. A plain match *self that tried to move the variant out would hit the "cannot move out of a mutable reference" wall we spent all of episode 43 dismantling. Right, homework cleared -- now the two features of the day.

The problem: a lifetime you cannot name

Start with a concrete puzzle. You want to write a function that accepts a closure taking a &str and returning a &str borrowed from that same input. What lifetime do you write for the argument? Whatever you pick, it is wrong, because the closure has to work for whatever lifetime the function decides to call it with -- including a borrow of a string the function creates on its own stack, which has a lifetime the caller cannot possibly know or name in advance.

What you actually want to say is "for all lifetimes 'a, this closure is callable with a &'a str and gives back a &'a str". That "for all lifetimes" quantifier is exactly what a higher-ranked trait bound expresses, and its syntax is for<'a>:

fn apply<F>(f: F) -> usize
where
    F: for<'a> Fn(&'a str) -> &'a str, // for ANY lifetime 'a
{
    let owned = String::from("hello world");
    f(&owned).len() // f must accept this particular short-lived borrow
}

fn first_word(s: &str) -> &str {
    s.split_whitespace().next().unwrap_or("")
}

fn main() {
    println!("{}", apply(first_word)); // 5
}

Read the bound out loud: "for every lifetime 'a, F is Fn(&'a str) -> &'a str". That universal quantifier is what makes the body legal. Inside apply we build a local String called owned -- a value whose lifetime is tiny, ending when apply returns -- and we call f on a borrow of it. If the bound had named a single fixed lifetime, f would have been locked to one particular caller-chosen lifetime and could not also accept our short-lived local borrow. for<'a> says the closure is flexible enough to handle any lifetime we throw at it, including this one. That is the whole idea: a higher-ranked bound is a bound that is itself generic over a lifetime.

You have been using HRTBs invisibly

Here is the part that surprises people: you have written dozens of these bounds already, and never once typed for<'a>. Whenever you have an Fn, FnMut or FnOnce bound whose arguments are references, the compiler silently wraps it in a higher-ranked lifetime for you:

// This bound, written the short way...
fn run<F: Fn(&[i32]) -> i32>(f: F) -> i32 {
    let v = vec![1, 2, 3];
    f(&v) // ...is silently `for<'a> Fn(&'a [i32]) -> i32`
}

fn main() {
    println!("{}", run(|slice| slice.iter().sum())); // 6
}

The bound F: Fn(&[i32]) -> i32 desugars to F: for<'a> Fn(&'a [i32]) -> i32. That is why run can build a local Vec and pass a borrow of it to f -- the higher-ranked lifetime was there all along, inserted on your behalf. The same invisibility applies from the calling side. When you hand a closure that borrows its argument to such a function, the closure quietly satisfies the higher-ranked bound:

fn call_on_local<F: for<'a> Fn(&'a str) -> usize>(f: F) -> usize {
    let s = String::from("hello");
    f(&s) // the closure must work for this local's short lifetime
}

fn main() {
    println!("{}", call_on_local(|s| s.len())); // 5
}

So for the most part, higher-ranked trait bounds are a thing you read, not a thing you write. You will meet the for<'a> syntax far more often in a compiler error message, or in the signature of a library function you are studying, than in your own code. Recognising it -- knowing it just means "for every lifetime" and calming down accordingly -- matters more than producing it.

Where the syntax actually surfaces

There is one everyday place the for<'a> really does show up in code you read: inside the type of a stored closure. When you keep a boxed closure in a struct field, the trait object type carries the higher-ranked lifetime, whether spelled out or elided:

struct Trimmer {
    op: Box<dyn Fn(&str) -> usize>, // really Box<dyn for<'a> Fn(&'a str) -> usize>
}

fn main() {
    let t = Trimmer {
        op: Box::new(|s| s.trim().len()),
    };
    println!("{}", (t.op)("  hello  ")); // 5
}

The field type Box<dyn Fn(&str) -> usize> stores a closure that works for any input lifetime -- which is what you want, because a Trimmer should be callable on borrows of all kinds. When you eventually hit an error that reads "implementation is not general enough" or mentions for<'a>, this is the feature talking: the compiler is telling you a closure was only general enough for one lifetime where a higher-ranked bound demanded it be general over all of them. Now you know what those words mean.

The three elision rules, in full

Now the second feature, and the reason most reference-taking functions need no 'a at all. Lifetime elision is a small, fully deterministic set of rules the compiler applies to fill in lifetimes you left off. There are exactly three, and they are worth memorising because they explain every "why did this compile without annotations?" moment you have had:

  • Rule 1 -- each elided lifetime in the parameters gets its own distinct lifetime. One reference parameter, one fresh lifetime; two reference parameters, two different fresh lifetimes; and so on.
  • Rule 2 -- if there is exactly one input lifetime (elided or not), that lifetime is assigned to every elided output lifetime.
  • Rule 3 -- if there are multiple input lifetimes but one of them is &self or &mut self, the lifetime of self is assigned to every elided output lifetime.

If, after applying these three, any output lifetime is still unknown, elision fails and the compiler asks you to annotate. Here are rules two and three doing their job:

struct Parser { text: String }

impl Parser {
    // Rule 3: output borrows from &self, no annotation needed
    fn first_word(&self) -> &str {
        self.text.split_whitespace().next().unwrap_or("")
    }
}

// Rule 2: exactly one input lifetime, so the output gets it
fn initial(s: &str) -> &str {
    &s[..1]
}

fn main() {
    let p = Parser { text: String::from("hello world") };
    println!("{}", p.first_word()); // hello
    println!("{}", initial("abc")); // a
}

first_word returns a &str that borrows from self. There are two input lifetimes in play there really -- self is one -- but rule three settles it instantly: the output borrows from self. initial has a single reference input, so rule two flows that one lifetime to the output. Neither function needs an explicit 'a, and that is why almost none of the reference-returning methods you have written all series long have ever needed one. The full, annotated form of initial is fn initial<'a>(s: &'a str) -> &'a str; elision just spares you from typing it.

When elision gives up

Elision only works when the three rules produce a single unambiguous answer. The classic case where they cannot is two reference inputs and a reference output. Rule one hands each input its own separate lifetime, rule two does not apply (there is more than one input lifetime), and rule three does not apply (no self). So the compiler has no way to know which input the output borrows from, and it stops:

// Two input references, so elision cannot pick the output's lifetime.
fn longer<'a>(x: &'a str, y: &'a str) -> &'a str {
    if x.len() > y.len() { x } else { y }
}

fn main() {
    println!("{}", longer("hello", "hi")); // hello
}

This is the very longest-style function from episode 10, and now you can see precisely why it needs the annotations while first_word does not. By writing 'a on both inputs and the output, you tell the compiler "the returned reference lives as long as the shorter of these two inputs", which is the promise the body actually keeps. Without the annotations the compiler cannot prove that promise, so it refuses to guess.

There is a second, subtler case worth knowing: a function that returns a reference but has no reference inputs at all. Rule one finds nothing, so there is no input lifetime for rules two or three to hand out, and elision cannot help. You have to say where the reference comes from -- usually 'static:

// No input lifetimes exist, so the output lifetime must be stated explicitly.
fn label() -> &'static str {
    "constant"
}

fn main() {
    println!("{}", label()); // constant
}

The string literal "constant" lives for the whole program, so its lifetime is 'static, and we say so. The rule of thumb that falls out of all this is a comfortable one: write your function with no lifetimes first, and only add them when the compiler tells you elision could not decide. The error message will name exactly the reference it could not pin down, and nine times out of ten the fix is a single shared 'a on the inputs the output borrows from.

How this compares to other languages

Since quite some of you came to Rust from the Learn Python Series, a sideways glance is useful -- because both of today's features exist only because Rust takes lifetimes seriously in the first place.

In Python, there is no such thing as a higher-ranked bound or lifetime elision, because there are no lifetimes to rank or elide. A function that "returns a substring of its argument" just returns a new str object, and the garbage collector keeps whatever is still referenced alive for exactly as long as something points at it. The entire category of "which input does this output borrow from, and for how long?" simply does not exist -- which is convenient right up until you have a dangling reference in a language that did let you have one, at which point you would have wished for Rust's compile-time answer.

In C++, the danger is real but the checking is not. You can absolutely write a function returning a reference or a pointer into one of its arguments, and the language will happily let you return a dangling reference to a local, or borrow from the wrong argument, with no complaint until it crashes at runtime (or worse, silently corrupts). Rust's elision rules are the same idea a careful C++ programmer keeps in their head about "who owns what and for how long", but promoted to a mandatory, machine-checked part of the type system. Higher-ranked bounds, likewise, are what C++ templates approximate with template parameters and a great deal of trust -- Rust makes the "works for every lifetime" claim explicit and verifies it.

In Go, as with Python, garbage collection means the question never arises: you return a slice or a pointer and the runtime keeps the backing array alive. The trade is the familiar one across this whole series -- Go buys simplicity with a garbage collector and gives up the ability to express, and prove, zero-cost borrowing with no dangling. Rust's elision and HRTBs are the price and the payoff of that proof: a little syntax you mostly do not have to write, backing a guarantee the other three languages cannot make.

What did we actually learn?

  • A higher-ranked trait bound (for<'a> ...) means "for every lifetime 'a". It is what a bound needs when a closure must accept a reference of a lifetime the caller cannot name in advance -- most importantly, a borrow of a value the callee creates itself.
  • You almost never write for<'a> by hand. Any Fn/FnMut/FnOnce bound with reference arguments is silently made higher-ranked for you. The syntax is mostly something you read -- in error messages and library signatures -- not something you produce.
  • Lifetime elision is three deterministic rules: (1) each input reference gets its own lifetime; (2) one input lifetime is given to all outputs; (3) a &self/&mut self lifetime is given to all outputs. They are why most reference-returning functions need no annotations.
  • Elision gives up when the rules leave an output lifetime undecided -- two reference inputs with no self, or a reference output with no reference inputs. Then, and only then, do you annotate.
  • The practical workflow: write the signature with no lifetimes, and add an explicit 'a only where the compiler says it could not decide. The error tells you exactly which reference to pin down.

Exercises

Three exercises, gentle to chewier. Type them out and run them -- lifetimes are one of those topics that stay abstract until you have watched the compiler accept and reject your own signatures.

  1. Write fn run<F: for<'a> Fn(&'a [i32]) -> i32>(f: F) -> i32 that builds a local Vec<i32> inside the function and calls f on a slice of it, returning the result. Then call run with a closure that sums the slice, and confirm it compiles with the explicit for<'a> and still compiles when you drop it to the short Fn(&[i32]) -> i32 form.
  2. Add a method to a struct that returns a &str borrowed from a String field of &self, and confirm by removing every 'a you can that it still compiles -- then explain to yourself which elision rule made that possible.
  3. Write a two-input, one-output reference function (say, "return whichever of two &str values is alphabetically first") with no lifetime annotations at all. Read the exact error the compiler gives you, then fix it with a single shared 'a, and note how the message pointed you straight at the missing annotation.

That last exercise -- reaching through a mutable borrow to move an owned value out, and threading lifetimes through a data structure that points at itself -- is going to come back with a vengeance very soon, because the next thing we build is a classic linked structure that Rust's ownership rules make famously awkward. We will do it the safe way first, and then, carefully, the other way. Chew on today's rules in the meantime ;-)

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

@scipio

Comments

No comments yet — be the first.