Function and Closure Types

Throughout this chapter, we’ve seen functions and closures used as values. Naturally, this means that they have types. For example:

fn city_population_descending(city: &City) -> i64 {
    -city.population
}

This function takes one argument (a &City) and returns an i64. It has the type fn(&City) -> i64.

You can do all the same things with functions that you do with other values. You can store them in variables. You can use all the usual Rust syntax to compute function values:

let my_key_fn: fn(&City) -> i64 =
    if user.prefs.by_population {
        city_population_descending
    } else {
        city_monster_attack_risk_descending
    };

cities.sort_by_key(my_key_fn);

Structs may have function-typed fields. Generic types like Vec can store scads of functions, as long as they all share the same fn type. And function values are tiny: a fn value is the memory address of the function’s machine code, just like a function pointer in C++.

A function can take another function as an argument. For example:

/// Given a list of cities and a test function,
/// return how many cities pass the test.
fn count_selected_cities(cities: &Vec<City>,
                         test_fn: fn(&City) -> bool) -> usize
{
    let mut count = 0;
    for city in cities {
        if test_fn(city) {
            count += 1;
        }
    }
    count
}

/// An example of a test function. Note that the type of
/// this function is `fn(&City) -> bool`, the same as
/// the `test_fn` argument to `count_selected_cities`.
fn has_monster_attacks(city: &City) -> bool {
    city.monster_attack_risk > 0.0
}

// How many cities are at risk for monster attack?
let n = count_selected_cities(&my_cities, has_monster_attacks);

If you’re familiar with function pointers in C/C++, you’ll see that Rust’s function values are exactly the same thing.

After all this, it may come as a surprise that closures do not have the same type as functions:

let limit = preferences.acceptable_monster_risk();
let n = count_selected_cities(
    &my_cities,
    |city| city.monster_attack_risk > limit);  // error: type mismatch

The second argument causes a type error. To support closures, we must change the type signature of this function. It needs to look like this:

fn count_selected_cities<F>(cities: &Vec<City>, test_fn: F) -> usize
    where F: Fn(&City) -> bool
{
    let mut count = 0;
    for city in cities {
        if test_fn(city) {
            count += 1;
        }
    }
    count
}

We have changed only the type signature of count_selected_cities, not the body. The new version is generic. It takes a test_fn of any type F as long as F implements the special trait Fn(&City) -> bool. This trait is automatically implemented by all functions and closures that take a single &City as an argument and return a Boolean value.

fn(&City) -> bool    // fn type (functions only)
Fn(&City) -> bool    // Fn trait (both functions and closures)

This special syntax is built into the language. The -> and return type are optional; if omitted, the return type is ().

The new version of count_selected_cities accepts either a function or a closure:

count_selected_cities(
    &my_cities,
    has_monster_attacks);  // ok

count_selected_cities(
    &my_cities,
    |city| city.monster_attack_risk > limit);  // also ok

Why didn’t our first attempt work? Well, a closure is callable, but it’s not a fn. The closure |city| city.monster_attack_risk > limit has its own type that’s not a fn type.

In fact, every closure you write has its own type, because a closure may contain data: values either borrowed or stolen from enclosing scopes. This could be any number of variables, in any combination of types. So every closure has an ad hoc type created by the compiler, large enough to hold that data. No two closures have exactly the same type. But every closure implements a Fn trait; the closure in our example implements Fn(&City) -> i64.

Since every closure has its own type, code that works with closures usually needs to be generic, like count_selected_cities. It’s a little clunky to spell out the generic types each time, but to see the advantages of this design, just read on.

Closure Performance

Rust’s closures are designed to be fast: faster than function pointers, fast enough that you can use them even in red-hot, performance-sensitive code. If you’re familiar with C++ lambdas, you’ll find that Rust closures are just as fast and compact, but safer.

In most languages, closures are allocated in the heap, dynamically dispatched, and garbage collected. So creating them, calling them, and collecting them each cost a tiny bit of extra CPU time. Worse, closures tend to rule out inlining, a key technique compilers use to eliminate function call overhead and enable a raft of other optimizations. All told, closures are slow enough in these languages that it can be worth manually removing them from tight inner loops.

Rust closures have none of these performance drawbacks. They’re not garbage collected. Like everything else in Rust, they aren’t allocated on the heap unless you put them in a Box, Vec, or other container. And since each closure has a distinct type, whenever the Rust compiler knows the type of the closure you’re calling, it can inline the code for that particular closure. This makes it OK to use closures in tight loops, and Rust programs often do so, enthusiastically, as you’ll see in Chapter 15.

Figure 14-1 shows how Rust closures are laid out in memory. At the top of the figure, we show a couple of local variables that our closures will refer to: a string food and a simple enum weather, whose numeric value happens to be 27.

Figure 14-1. Layout of closures in memory

Closure (a) uses both variables. Apparently we’re looking for cities that have both tacos and tornadoes. In memory, this closure looks like a small struct containing references to the variables it uses.

Note that it doesn’t contain a pointer to its code! That’s not necessary: as long as Rust knows the closure’s type, it knows which code to run when you call it.

Closure (b) is exactly the same, except it’s a move closure, so it contains values instead of references.

Closure (c) doesn’t use any variables from its environment. The struct is empty, so this closure does not take up any memory at all.

As the figure shows, these closures don’t take up much space. But even those few bytes are not always needed in practice. Often, the compiler can inline all calls to a closure, and then even the small structs shown in this figure are optimized away.

In “Callbacks”, we’ll show how to allocate closures in the heap and call them dynamically, using trait objects. That is a bit slower, but it is still as fast as any other trait object method.

Closures and Safety

The next few pages complete our explanation of how closures interact with Rust’s safety system. As we said earlier in this chapter, most of the story is simply that when a closure is created, it either moves or borrows the captured variables. But some of the consequences are not exactly obvious. In particular, we’ll be talking about what happens when a closure drops or modifies a captured value.

let my_str = "hello".to_string();
let f = || drop(my_str);

f();
f();

f();  // ok
f();  // error: use of moved value

fn call_twice<F>(closure: F) where F: Fn() {
    closure();
    closure();
}

let my_str = "hello".to_string();
let f = || drop(my_str);
call_twice(f);

error[E0525]: expected a closure that implements the `Fn` trait, but
              this closure only implements `FnOnce`
  --> closures_twice.rs:12:13
   |
12 |     let f = || drop(my_str);
   |             ^^^^^^^^^^^^^^^
   |
note: the requirement to implement `Fn` derives from here
  --> closures_twice.rs:13:5
   |
13 |     call_twice(f);
   |     ^^^^^^^^^^

// Pseudocode for `Fn` and `FnOnce` traits with no arguments.
trait Fn() -> R {
    fn call(&self) -> R;
}

trait FnOnce() -> R {
    fn call_once(self) -> R;
}

let dict = produce_glossary();
let debug_dump_dict = || {
    for (key, value) in dict {  // oops!
        println!("{:?} - {:?}", key, value);
    }
};

error[E0382]: use of moved value: `debug_dump_dict`
  --> closures_debug_dump_dict.rs:18:5
   |
17 |     debug_dump_dict();
   |     --------------- value moved here
18 |     debug_dump_dict();
   |     ^^^^^^^^^^^^^^^ value used here after move
   |
   = help: closure was moved because it only implements `FnOnce`

let debug_dump_dict = || {
    for (key, value) in &dict {  // does not use up dict
        println!("{:?} - {:?}", key, value);
    }
};

FnMut

There is one more kind of closure, the kind that contains mutable data or mut references.

Rust considers non-mut values safe to share across threads. But it wouldn’t be safe to share non-mut closures that contain mut data: calling such a closure from multiple threads could lead to all sorts of race conditions as multiple threads try to read and write the same data at the same time.

Therefore, Rust has one more category of closure, FnMut, the category of closures that write. FnMut closures are called by mut reference, as if they were defined like this:

// Pseudocode for `Fn`, `FnMut`, and `FnOnce` traits.
trait Fn() -> R {
    fn call(&self) -> R;
}

trait FnMut() -> R {
    fn call_mut(&mut self) -> R;
}

trait FnOnce() -> R {
    fn call_once(self) -> R;
}

Any closure that requires mut access to a value, but doesn’t drop any values, is a FnMut closure. For example:

let mut i = 0;
let incr = || {
    i += 1;  // incr borrows a mut reference to i
    println!("Ding! i is now: {}", i);
};
call_twice(incr);

The way we wrote call_twice, it requires a Fn. Since incr is a FnMut and not a Fn, this code fails to compile. There’s an easy fix, though. To understand the fix, let’s take a step back and summarize what you’ve learned about the three categories of Rust closures.

• Fn is the family of closures and functions that you can call multiple times without restriction. This highest category also includes all fn functions.

• FnMut is the family of closures that can be called multiple times if the closure itself is declared mut.

• FnOnce is the family of closures that can be called once, if the caller owns the closure.

Every Fn meets the requirements for FnMut, and every FnMut meets the requirements for FnOnce. As shown in Figure 14-2, they’re not three separate categories.

Figure 14-2. Venn diagram of the three closure categories

Instead, Fn() is a subtrait of FnMut(), which is a subtrait of FnOnce(). This makes Fn the most exclusive and most powerful category. FnMut and FnOnce are broader categories that include closures with usage restrictions.

Now that we’ve organized what we know, it’s clear that to accept the widest possible swath of closures, our call_twice function really ought to accept all FnMut closures, like this:

fn call_twice<F>(mut closure: F) where F: FnMut() {
    closure();
    closure();
}

The bound on the first line was F: Fn(), and now it’s F: FnMut(). With this change, we still accept all Fn closures, and we additionally can use call_twice on closures that mutate data:

let mut i = 0;
call_twice(|| i += 1);  // ok!
assert_eq!(i, 2);

Callbacks

A lot of libraries use callbacks as part of their API: functions provided by the user, for the library to call later. In fact, you’ve seen some APIs like that already in this book. Back in Chapter 2, we used the Iron framework to write a simple web server. It looked like this:

fn main() {
    let mut router = Router::new();

    router.get("/", get_form, "root");
    router.post("/gcd", post_gcd, "gcd");

    println!("Serving on http://localhost:3000...");
    Iron::new(router).http("localhost:3000").unwrap();
}

The purpose of the router is to route incoming requests from the Internet to the bit of Rust code that handles that particular kind of request. In this example, get_form and post_gcd were the names of some functions that we declared elsewhere in the program, using the fn keyword. But we could have passed closures instead, like this:

let mut router = Router::new();

router.get("/", |_: &mut Request| {
    Ok(get_form_response())
}, "root");
router.post("/gcd", |request: &mut Request| {
    let numbers = get_numbers(request)?;
    Ok(get_gcd_response(numbers))
}, "gcd");

This is because Iron was written to accept any thread-safe Fn as an argument.

How can we do that in our own programs? Let’s try writing our own very simple router from scratch, without using any code from Iron. We can begin by declaring a few types to represent HTTP requests and responses:

struct Request {
    method: String,
    url: String,
    headers: HashMap<String, String>,
    body: Vec<u8>
}

struct Response {
    code: u32,
    headers: HashMap<String, String>,
    body: Vec<u8>
}

Now the job of a router is simply to store a table that maps URLs to callbacks, so that the right callback can be called on demand. (For simplicity’s sake, we’ll only allow users to create routes that match a single exact URL.)

struct BasicRouter<C> where C: Fn(&Request) -> Response {
    routes: HashMap<String, C>
}

impl<C> BasicRouter<C> where C: Fn(&Request) -> Response {
    /// Create an empty router.
    fn new() -> BasicRouter<C> {
        BasicRouter { routes: HashMap::new() }
    }

    /// Add a route to the router.
    fn add_route(&mut self, url: &str, callback: C) {
        self.routes.insert(url.to_string(), callback);
    }
}

Unfortunately, we’ve made a mistake. Did you notice it?

This router works fine as long as we only add one route to it:

let mut router = BasicRouter::new();
router.add_route("/", |_| get_form_response());

This much compiles and runs. Unfortunately, if we add another route:

router.add_route("/gcd", |req| get_gcd_response(req));

then we get errors:

error[E0308]: mismatched types
  --> closures_bad_router.rs:41:30
   |
41 |     router.add_route("/gcd", |req| get_gcd_response(req));
   |                              ^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |                              expected closure, found a different closure
   |
   = note: expected type `[closure@closures_bad_router.rs:40:27: 40:50]`
              found type `[closure@closures_bad_router.rs:41:30: 41:57]`
note: no two closures, even if identical, have the same type
help: consider boxing your closure and/or using it as a trait object

Our mistake was in how we defined the BasicRouter type:

struct BasicRouter<C> where C: Fn(&Request) -> Response {
    routes: HashMap<String, C>
}

We unwittingly declared that each BasicRouter has a single callback type C, and all the callbacks in the HashMap are of that type. Back in “Which to Use”, we showed a Salad type that had the same problem.

struct Salad<V: Vegetable> {
    veggies: Vec<V>
}

The solution here is the same as for the salad: since we want to support a variety of types, we need to use boxes and trait objects.

type BoxedCallback = Box<Fn(&Request) -> Response>;

struct BasicRouter {
    routes: HashMap<String, BoxedCallback>
}

Each box can contain a different type of closure, so a single HashMap can contain all sorts of callbacks. Note that the type parameter C is gone.

This requires a few adjustments to the methods:

impl BasicRouter {
    // Create an empty router.
    fn new() -> BasicRouter {
        BasicRouter { routes: HashMap::new() }
    }

    // Add a route to the router.
    fn add_route<C>(&mut self, url: &str, callback: C)
        where C: Fn(&Request) -> Response + 'static
    {
        self.routes.insert(url.to_string(), Box::new(callback));
    }
}

(Note the two bounds on C in the type signature for add_route: a particular Fn trait, and the 'static lifetime. Rust makes us add this 'static bound. Without it, the call to Box::new(callback) would be an error, because it’s not safe to store a closure if it contains borrowed references to variables that are about to go out of scope.)

Finally, our simple router is ready to handle incoming requests:

impl BasicRouter {
    fn handle_request(&self, request: &Request) -> Response {
        match self.routes.get(&request.url) {
            None => not_found_response(),
            Some(callback) => callback(request)
        }
    }
}

Using Closures Effectively

As we’ve seen, Rust’s closures are different from closures in most other languages. The biggest difference is that in languages with GC, you can use local variables in a closure without having to think about lifetimes or ownership. Without GC, things are different. Some design patterns that are commonplace in Java, C#, and JavaScript won’t work in Rust without changes.

For example, take the Model-View-Controller design pattern (MVC for short), illustrated in Figure 14-3. For every element of a user interface, an MVC framework creates three objects: a model representing that UI element’s state, a view that’s responsible for its appearance, and a controller that handles user interaction. Countless variations on MVC have been implemented over the years, but the general idea is that three objects divvy up the UI responsibilities somehow.

Here’s the problem. Typically, each object has a reference to one or both of the others, directly or through a callback, as shown in Figure 14-3. Whenever anything happens to one of the objects, it notifies the others, so everything updates promptly. The question of which object “owns” the others never comes up.

Figure 14-3. The Model-View-Controller design pattern

You can’t implement this pattern in Rust without making some changes. Ownership must be made explicit, and reference cycles must be eliminated. The model and the controller can’t have direct references to each other.

Rust’s radical wager is that good alternative designs exist. Sometimes you can fix a problem with closure ownership and lifetimes by having each closure receive the references it needs as arguments. Sometimes you can assign each thing in the system a number and pass around the numbers instead of references. Or you can implement one of the many variations on MVC where the objects don’t all have references to each other. Or model your toolkit after a non-MVC system with unidirectional data flow, like Facebook’s Flux architecture, shown in Figure 14-4.

Figure 14-4. The Flux architecture, an alternative to MVC

In short, if you try to use Rust closures to make a “sea of objects,” you’re going to have a hard time. But there are alternatives. In this case, it seems software engineering as a discipline is already gravitating to the alternatives anyway, because they’re simpler.

In the next chapter, we turn to a topic where closures really shine. We’ll be writing a kind of code that takes full advantage of the concision, speed, and efficiency of Rust closures and that’s fun to write, easy to read, and eminently practical. Up next: Rust iterators.