Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Higher-Rank Trait Bounds

The syntax is for<'a>. The reading is “for any choice of 'a.” The reason it exists is closures, primarily, and the reason it produces such bad error messages is that closures are the part of Rust where lifetime inference, trait inference, and variance all collide at once.

If you have spent any time writing Rust libraries that take callbacks, you have seen this:

#![allow(unused)]
fn main() {
fn use_callback<F>(f: F) where F: Fn(&str) -> &str {
    let s = String::from("hello");
    let result = f(&s);
    println!("{result}");
}
}

This compiles. It works. You did not write for<'a> anywhere. But the compiler did, on your behalf, and the desugared signature is:

#![allow(unused)]
fn main() {
fn use_callback<F>(f: F) where F: for<'a> Fn(&'a str) -> &'a str { ... }
}

That for<'a> is the thing this chapter is about. It says: the closure must be callable with a reference of any lifetime, not some particular lifetime. The closure must work for every 'a, not for one 'a chosen up front.

The distinction matters because the alternative — picking a single 'a at the function boundary — would make the closure useless. The body of use_callback calls f with a reference whose lifetime is bounded by s, which is local to the function. That lifetime didn’t exist when use_callback was called. There is no way the caller could have picked it. So the trait bound has to be higher-ranked over all possible lifetimes — for<'a>, “for any 'a,” — to let the body pick a fresh local one and have the closure still satisfy the bound.

This is what HRTB is. A trait bound that quantifies over a lifetime universally, not existentially.

When elision works and when it doesn’t

For closure bounds where the lifetime appears in both an argument and the return, Rust elides for<'a> exactly the way it elides lifetimes in function signatures. So Fn(&str) -> &str is sugar for for<'a> Fn(&'a str) -> &'a str. This covers maybe 80% of real callback patterns.

It stops covering you in the cases where:

  • You write the lifetime explicitly because you want a non-elided pattern.
  • You return a Box<dyn Fn(...)> or store a closure in a struct.
  • You have multiple closures with related lifetimes.
  • The closure captures something with a lifetime.

In those cases, the elision either doesn’t apply or applies wrongly, and you have to write for<'a> yourself, and you should know what you’re saying.

The capture problem

Here is where the wheels come off. Suppose:

#![allow(unused)]
fn main() {
fn make_counter<'a>(prefix: &'a str) -> impl Fn(&str) -> String {
    move |name| format!("{prefix}: {name}")
}
}

The compiler will tell you something like:

error[E0700]: hidden type for `impl Fn(&str) -> String` captures lifetime that does not appear in bounds
  --> src/lib.rs:1:42
   |
1  | fn make_counter<'a>(prefix: &'a str) -> impl Fn(&str) -> String {
   |                 --                      ^^^^^^^^^^^^^^^^^^^^^^^
   |                 |
   |                 hidden type `[closure@src/lib.rs:2:5: 2:12]` captures the lifetime `'a` as defined here

The error is real, the explanation is somewhere off-screen, and the answer involves + 'a somewhere. The fix:

#![allow(unused)]
fn main() {
fn make_counter<'a>(prefix: &'a str) -> impl Fn(&str) -> String + 'a {
    move |name| format!("{prefix}: {name}")
}
}

The + 'a says: the returned impl Fn borrows from 'a and cannot outlive it. Without that bound, the returned type has no information about the borrow it captures, and the compiler refuses to lose track of it.

This is a separate concept from HRTB, but they interact. The closure’s argument is for<'b> Fn(&'b str) (universally quantified — the closure must work for any caller-chosen lifetime). The closure’s capture is at a fixed 'a (existentially given — it borrows the specific prefix that was passed in). So the type is:

#![allow(unused)]
fn main() {
impl for<'b> Fn(&'b str) -> String + 'a
}

Two different lifetimes, two different quantifications, one closure. The compiler infers all of this for you when it can. When it can’t, it asks you to be explicit, and you have to know which lifetime is which.

When inference gives up

Now we get to the bad place. Consider:

#![allow(unused)]
fn main() {
fn apply<F, T, R>(items: &[T], f: F) -> Vec<R>
where
    F: Fn(&T) -> R,
{
    items.iter().map(|x| f(x)).collect()
}
}

Looks fine. Compiles. Now you try to use it with a closure that returns a reference into its argument:

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

fn main() {
    let strings = vec![String::from("hello world"), String::from("foo bar")];
    let firsts: Vec<&str> = apply(&strings, first_word);
    println!("{firsts:?}");
}

This will produce an error like:

error: implementation of `FnOnce` is not general enough
  --> src/main.rs:8:29
   |
8  |     let firsts: Vec<&str> = apply(&strings, first_word);
   |                             ^^^^^^^^^^^^^^^^^^^^^^^^^^^ implementation of `FnOnce` is not general enough
   |
   = note: `fn(&'2 String) -> &'2 str {first_word}` must implement `FnOnce<(&'1 String,)>`, for any lifetime `'1`...
   = note: ...but it actually implements `FnOnce<(&'2 String,)>`, for some specific lifetime `'2`

This is the error message that ends careers. Read it carefully. The compiler is saying: the bound F: Fn(&T) -> R desugars (via elision) to F: for<'a> Fn(&'a T) -> R, where R is some type fixed at the call site. But first_word returns &'a str where 'a matches the input — its actual signature is fn first_word<'a>(s: &'a String) -> &'a str. There is no single R that works for all 'a. first_word is a higher-ranked function, but apply’s bound asked for an R that did not depend on the closure’s input lifetime.

The fix is to push the higher-ranking through to R:

#![allow(unused)]
fn main() {
fn apply<F, T, R: ?Sized>(items: &[T], f: F) -> Vec<&R>
where
    F: for<'a> Fn(&'a T) -> &'a R,
{
    items.iter().map(|x| f(x)).collect()
}
}

But wait — now R is tied to the lifetime of each individual call, but the result Vec<&R> has only one lifetime, which has to encompass all of them. The compiler will figure out that all of those 'as have to be the same lifetime, namely the lifetime of &items, and unify them. This works, but it took two passes through the trait solver and a manual rewrite of the signature.

This is the genre of error. It happens because the inferred for<'a> bound is not the one the user wanted — sometimes it’s too general (the closure can’t satisfy it), sometimes it’s not general enough (the body needs more freedom than the bound allows). The error message will use phrases like:

  • “implementation of Fn is not general enough”
  • “one type is more general than the other”
  • “'1 must outlive '2”
  • “expected a function pointer, found a closure”

When you see those phrases, you are in HRTB-land. The fix is almost always to write the for<'a> bound explicitly and to think hard about which type and lifetime parameters need to be inside it and which need to be outside.

The patterns that work

Here are the small number of HRTB patterns that cover most real code. Memorize the shapes.

Pattern 1: callback that takes a reference and returns nothing.

#![allow(unused)]
fn main() {
fn for_each<T, F: Fn(&T)>(items: &[T], f: F) {
    for item in items { f(item); }
}
}

Elision works. Don’t write the for<'a> explicitly; you don’t need to.

Pattern 2: callback that takes a reference and returns a value (not borrowing).

#![allow(unused)]
fn main() {
fn map<T, R, F: Fn(&T) -> R>(items: &[T], f: F) -> Vec<R> {
    items.iter().map(f).collect()
}
}

Elision works because R doesn’t borrow.

Pattern 3: callback that takes a reference and returns a reference into the same data.

#![allow(unused)]
fn main() {
fn map_ref<'a, T, R: ?Sized, F>(items: &'a [T], f: F) -> Vec<&'a R>
where
    F: for<'b> Fn(&'b T) -> &'b R,
{
    items.iter().map(|x| f(x)).collect()
}
}

This is the case that breaks. You need explicit for<'b> and you need to thread 'a through the result manually. Note: R: ?Sized lets it work for str and other unsized types; drop it if you don’t need that.

Pattern 4: storing a closure in a struct.

#![allow(unused)]
fn main() {
struct Validator<F: for<'a> Fn(&'a str) -> bool> {
    check: F,
}
}

The for<'a> is required because the struct has no other source for 'a. If you want the closure to also borrow something with a lifetime, you need a separate lifetime parameter on the struct.

Pattern 5: trait object closure.

#![allow(unused)]
fn main() {
type Callback = Box<dyn for<'a> Fn(&'a str) -> &'a str>;
}

Trait objects need explicit higher-ranking because trait object syntax does not elide. Always write for<'a> for trait object closure types that take or return references.

These five patterns cover the overwhelming majority of real code. When you hit something that doesn’t fit, write out the desugared signature with all lifetimes explicit, then add for<'a> quantifiers around the parameters that aren’t bound to anything outside the closure.

Why it has to be this way

A reasonable question: why doesn’t the compiler just figure all of this out? Closures are values. Their types are inferred. Why is HRTB inference, of all things, the place where the inference engine tells you to do its job for it?

The honest answer is that universal quantification over lifetimes is not in general decidable in the presence of trait bounds, and the partial decision procedure the compiler uses has to bail out somewhere. The for<'a> quantifier interacts with associated types, with where clauses, with auto traits, and with variance, and the failure modes compound. The Rust team has improved this dramatically over the years — every couple of releases, another class of HRTB inference failure starts working — but there is a hard limit somewhere short of “the compiler always figures it out.”

Niko Matsakis has written extensively on this; the relevant phrase to search for is “leak check” and “implied bounds.” The short version: the compiler cannot always tell whether the universal quantifier in a for<'a> bound is satisfied without checking, in effect, every lifetime, and the algorithm it uses is sound but incomplete. So it errs on the side of rejecting valid programs rather than accepting invalid ones, and you have to write the bound explicitly to convince it.

This is one of those places where the type system is genuinely making a tradeoff. The tradeoff is: we will accept worse error messages in exchange for guaranteeing soundness, and we will accept asking the user to write for<'a> in exchange for not having to wait three years for a complete inference algorithm. You may disagree with the tradeoff. Most working Rust engineers, on a long enough timescale, come around to it.

Sources and further reading

  • The Higher-Rank Trait Bounds section of the Rust Reference.
  • Niko Matsakis’s posts on higher-ranked subtyping, particularly the ones discussing the leak check. (His blog is the canonical source for this material.)
  • The “Closures: Anonymous Functions that Can Capture Their Environment” chapter of the Rust book, which gives the basic vocabulary even if it doesn’t go this deep.

Next: async. Where everything from the last three chapters comes together at once.