☑ Uncovering Rust: Closures, Iterators and Smart Pointers

We’ve covered quite a lot of Rust in this series of articles so far, and I’ve learned a lot myself whilst writing them. The last few articles are going to mop up a few of the remaining features that I feel are pretty key to writing idiomatic Rust.

In this article we’re going to cover two topics that you might well be already quite familiar with from other languages: closures and iterators. We’re also going to look at Rust’s version of smart pointers, and how it deals with memory on the stack and the heap.

Closures¶

We’ll kick off looking at closures. These will be familiar to experienced Python programmers¹ and C++ has a similar feature called lambdas that were added in C++11. A number of other languages also offer similar features.

If you took a read through the Wikipedia page on closures, you’ll find their semantics can differ quite a lot between languages. In some cases they’re simply named functions or classes declared within a particular scope, in other cases they’re anonymous functions with capture expressions. Rust’s closures are very much more towards the latter of these, and will seem quite familiar if you’ve used lambda expressions in C++.

Parameters and Captures¶

Let’s take a look at a simple example.

1
2
3
4
5
6
7

fn main() {
    let items = vec![-9, -3, 0, 5, 9];
    let all_single_digits = items.iter().all(
        |n| (-9..10).contains(n)
    );
    println!("All items single digits? {}", all_single_digits);
}

In this small snippet, line 4 defines a closure. The context here is that we have a Vec of integers and we call iter() on it to obtain an iterator over it — we’ll look at iterators further on in this article. We then call all() on the iterator which expects a predicate function returning bool — the result of all() will be true if and only if the predicate returns true for every element, or if there are no elements.

The predicate is what we’re passing as a closure. The |n| specifies that the closure takes a single parameter n — the all() method passes each element of the iterator in turn as the parameter. In this case the body of the closure executes (-9..10).contains(n), which checks whether a given value lies within the specified range².

If you’re following along and you’re of a more pedantic nature, you might be protesting at this point that all we’ve really seen is an anonymous function and not a true closure. This is fair, because in the example above the code doesn’t capture anything about the enclosing environment, so it’s really just a way to express an anonymous function that takes a single integer parameter and returns bool. But it’s an easy introduction to the syntax.

We’ve actually seen an example quite like this in an earlier article on error handling, which I’ve reproduced below.

let mut file_descriptor = File::open("filename.txt")
    .unwrap_or_else(|error| {
        if error.kind() == ErrorKind::NotFound {
            std::fs::OpenOptions::new()
                .create(true).write(true).read(true).open("filename.txt")
                .expect("Failed to create filename.txt")
        } else {
            panic!("Failed to open filename.txt: {:?}", error);
        }
    });

You can now recognise the use of the closure being passed to unwrap_or_else(), which is a useful way to take an Result<T, E> and pass a closure to generate a value in the Err case. You can do the same with Option<T> and the None case, except your closure doesn’t take any parameters, since None doesn’t have a value. You can see an example of this below.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

use std::fs;

struct CachedFile {
    pub filename: String,
    file_data: Option<String>,
}

impl CachedFile {
    pub fn new(filename: String) -> Self {
        CachedFile {
            filename,
            file_data: None,
        }
    }

    pub fn read(&mut self) -> String {
        self.file_data.clone().unwrap_or_else(|| {
            self.file_data = Some(
                fs::read_to_string(&self.filename)
                    .expect("Failed to read file"),
            );
            self.file_data.clone().unwrap()
        })
    }
}

I’m certainly not suggesting this is the best implementation of a file cache, but it illustrates the use of unwrap_or_else() on an Option<String> value, and how the closure which starts on line 17 takes no parameters. It also shows the use of captures, since the body of the closure refers to self within the enclosing scope.

Closure Parameter Types¶

Since closures are typically used in a fairly restricted context, the compiler can usually work out the types of the parameters and return value. However, it’s also possible to annotate parameter and return types as with a normal function. Here’s a regular function and an equivalent closure next to each other to compare.

fn  doubler   (n: i32) -> i32 { n * 2 }
let doubler = |n: i32| -> i32 { n * 2 };

This is relevant because the compiler will only ever infer a single type for each parameter and return value — it won’t allow a closure to be overloaded. Consider the following example.

1
2
3
4
5

fn main() {
    let identity = |n| n;
    println!("Word: {}", identity("six"));
    println!("Digit: {}", identity(6));
}

The identity() closure can clearly accept and return many types, but the compiler will assume that the first use sets the types to which all other occurrences must conform. Thus, when we try to compile the above code, we get this error:

error[E0308]: mismatched types
 --> src/main.rs:4:36
  |
4 |     println!("Digit: {}", identity(6));
  |                           -------- ^ expected `&str`, found integer
  |                           |
  |                           arguments to this function are incorrect
  |
note: closure parameter defined here
 --> src/main.rs:2:21
  |
2 |     let identity = |n| n;
  |

Captured Values¶

When capturing values from the enclosing scope, closures can do so in four ways. The compiler will pick the first on this list which meets the requirements of the code within the closure body.

• Immutable borrow
• Unique immutable borrow.
• Mutable borrow
• Move (i.e. take ownership)

We’ve seen the first, third and fourth of these when passing parameters to functions. The second one is special, only available to closures and cannot be forced with any particular syntax. It’s used in cases where the captured value is an immutable reference to a mutable value in the enclosing scope. A mutable borrow can’t be used, since the reference itself is immutable, but an immutable borrow wouldn’t work either because there might be other immutable references to the same value and hence it couldn’t be changed.

As a result, the unique immutable borrow creates a special reference which has the uniqueness constraint mutable references, but which is itself immutable. This allows the dereferenced value to be assigned to, but does not allow other actions normally allowed for immutable references like creating additional references to the underlying value.

Although the compiler generally determines the type of capture automatically, the programmer can force a move by prefixing the whole capture with the move keyword — this uses a move even if a borrow would work. This is typically to allow the closure to live beyond the captured values in a way the compiler may not be able to discern, such as when a closure is passed to another thread of execution.

Capture Traits¶

The actions which the closure takes on its captured values are summarised by up to three traits which define how the closure can be used. These are determined by the compiler based on what the body of the closure does, as opposed to being specified by the developer.

FnOnce

Indicates that the closure can be called at least once, which means that all closures implement this trait.

FnMut

If a closure doesn’t move captured values elsewhere, but may mutate those values, it implements this trait as well as FnOnce. These closures can be called more than once, although of course the may update the captured value each time.

Fn

If a closure neither moves values out nor mutates them, it implements this trait as well as the otehr two — this also applies to closures which don’t capture anything. These can be called multiple times without side-effects, which means they can be called multiple times concurrently.

These traits can be used to constrain types in the usual ways we looked at a couple of articles back. For example, if you’re taking a closure as a parameter and you’re expecting to call it multiple times sequentially on the items of a collection, you’d want to constraint the parameter to FnMut.

An example of this is the sort_by_key() method on slices, which takes a closure to extract the sort key from members of the slice. This specifies the closure must be FnMut because it has to call it multiple times, once for each item — of course, the closure will typically conform to Fn as well, as it’s unlikely in this case it will actually be changing any values.

As an aside, regular functions implement these traits as well as closures, as you might expect. This means you can use a named function where a closure could be expected if you don’t need the capturing behaviour.

Iterators¶

Programmers from C++, Python and Go, among others, will be comfortable with the concept of iterators, which yield a sequence of items on repeated calls. As in most languages, Rust’s iterators are lazily evaluated.

Here’s a quick code snippet to show use of a simple iterator across a vector.

let my_vector = vec![1, 2, 3, 4, 5, 6, 7, 8];
let my_iter = my_vector.iter();
for item in my_iter {
    println!("Item: {}", item);
}

Here we’re explicitly creating an iterator, but as you might expect the for loop can be used directly on the container itself — we’ll see how that works in a moment.

The value we get matches the Iterator trait, defined in the standard library. This trait requires a next() method to be defined, and provides a lot of new methods built on top of this one mechanism. It uses an associated type called Item to specify the type of item that’s iterated over.

In our example above, Item will be determined to be i32 by the compiler, based on the type of my_vector being Vec<i32>. The type of my_iter will be therefore be Iterator<Item=i32>.

The next() method returns Option<Self::Item>, so it should return Some(item), one at a time, and then return None when there are none left.

Mutable Iterators¶

In the code example above we called the Vec::iter() method to obtain an iterator. The iter() method returns an iterator over immutable references, so it’s no good if we want to modify the items in-place. It’s one of three different methods:

So into_iter() will take ownership of the values iterated over, using the usual move semantics. It’s important to understand this because if you use a for loop over a container directly by default it will use into_iter(), and hence take ownership of the contents of the container.

This is an important point to bear in mind whilst you’re getting used to Rust’s “move by default” semantics. If it makes it easier, this for loop:

for my_var in my_container {
    /* code */
}

… is equivalent to:

{
    let result = match IntoIterator::into_iter(my_container) {
        mut iter => loop {
            match iter.next() {
                None => break,
                Some(my_var) => { /* code */ },
            };
        },
    };
    result
}

If you’re following closely, you’ll notice something a little odd — based on that equivalence the for loop returns a value, but the value is always (), since no parameter is passed into break — if this seems very confusing, recall from the previous article on loops that a loop statement is special in that it can return a value by passing it to the break statement. So, we can’t return a value from the for loop, for the reasons outlined in that article — but due to Rust’s syntax we need to return something, so we always return ().

Iterator Adapters¶

The additional methods that the Iterator trait adds to the iterator objects can be loosely split into two types.

Consuming adapters

These functions call next() on the iterator and hence consume some or all of the values. Examples include count(), sum() and last().

Iterator adapters

These functions don’t consume the iterator, they simply wrap it in another iterator which they return. When that is iterated, it will then consume items and pass them down the chain of iterators. Examples include map(), which calls a specified closure to transform each element before yielding it; and filter(), which will use a closure returning bool to decide for each element whether it should be yielded.

You’ll notice that the iterator adapters listed above, and some others in the library, call a closure on each element — this means that the parameter to the closure will be the element, so if you want to customise its behaviour then you’re going to have to use captures instead.

Smart Pointers¶

For the last topic of this article I want to run through Rust’s smart pointers. I’m going to avoid using the term “pointer” on its own because Rust does have raw pointers, but that’s not what I’m talking about here. To dereference raw pointers, you need to be using unsafe Rust, and that’s something I’m not going to drill into, at least in this article.

Rust’s smart pointers won’t be massively surprising to anyone familiar with C++, but with Rust’s notions of borrowing and ownership, it’s useful to take a quick look at how they’re used.

In principle, anything that owns memory is could be regarded as a smart pointer in Rust — this includes containers such as String and Vec<T> that we’ve already seen. The technique is common in the standard library, so there are plenty of specific examples, but here we’re going to look at some generic examples that the standard library offers.

Box<T>¶

We’ll start with a fairly simple case, which is the Box<T> type — this just serves to store a structure on the heap instead of the stack³.

These pointers don’t have a lot of features, but they don’t add any performance overhead either, unless you count the increased risk of cache misses due to reduce locality of reference. Still, they’re useful in some cases, which include:

• The size of a structure isn’t known at compile time in a context where that matters.
• You are storing a type with a large memory footprint and you want to avoid the overhead of copying it.
• Your code takes ownership of a value that implements a particular trait, but you want to make you code independent of the actual type used.

You can construct a Box easily enough using its new() method, as in the example below.

fn main() {
    let value = Box::new("Hello, world");
    println!("Value: {}", value);
}

Of course, if you really wanted to store a string, you’d be better off with the String type, but it’s a simple example just to make things concrete.

Recursive Types¶

Let’s consider a real case where might want to use Box, implementing a singly-linked stack. First, let’s consider what happens if you don’t use Box.

1
2
3
4
5
6
7
8

pub struct List<T> {
    head: Option<Node<T>>,
}

struct Node<T> {
    value: T,
    next: Option<Node<T>>,
}

This all seems very straightforward. However, the issue is that we’ve defined a type recursively, where the size of the structure is unknown at compile time — this is because the entire list is in-place within the stack. This means the compiler has no way to generate a lot of the code it needs to, and you get an error like this.

error[E0072]: recursive type `Node` has infinite size
 --> src/main.rs:5:1
  |
5 | struct Node<T> {
  | ^^^^^^^^^^^^^^
6 |     value: T,
7 |     next: Option<Node<T>>,
  |                  ------- recursive without indirection
  |
help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to break the cycle
  |
7 |     next: Option<Box<Node<T>>>,
  |                  ++++       +

Instead, let’s look at a working definition of a List class using Box.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

pub struct List<T> {
    head: NodeLink<T>,
}

type NodeLink<T> = Option<Box<ListNode<T>>>;

struct ListNode<T> {
    value: T,
    next: NodeLink<T>,
}

impl<T> List<T> {
    pub fn new() -> Self {
        List { head: None }
    }

    pub fn push(&mut self, value: T) {
        let new_node = Box::new(ListNode {
            value,
            next: self.head.take(),
        });
        self.head = Some(new_node);
    }

    pub fn pop(&mut self) -> Option<T> {
        self.head.take().map(|node| {
            self.head = node.next;
            node.value
        })
    }
}

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        let mut current = self.head.take();
        while let Some(mut node_to_drop) = current {
            current = node_to_drop.next.take();
        }
    }
}

I should point out that this is essentially stolen from Alexis Beingessner’s excellent tutorial Learning Rust With Entirely Too Many Linked Lists, which is really well written and great way to reinforce your knowledge of references and smart pointers in Rust, along with a lot of other features.

The Link type is just a convenient type alias for Option<Box<ListNode<T>>>, which is a bit of mouthful and used in several places in the code. Other than that, and the use of Box, I hope this example should be pretty comprehensible based on what we’ve seen so far, but I’ll highlight a few details of interest.

The use of Box is hopefully clear here — it’s just a safer pointer to heap-allocated storage for a type. This means the size of ListNode is fixed as the size of T plus the size of a pointer⁴. The use of Option is to allow the end of the list to be indicated — unlike raw pointers, a Box<T> cannot be a null pointer.

It’s also worth noting the use of the take() method on the head of the list, as it’s really important to understand the full detail of what’s going on here. Consider its use in push() — we want to assign the head of the list to the newly created node, and then make head point to that newly created node. However, Rust’s ownership semantics require there’s no point in time at which both objects own that NodeLink value. As a result, the Option::take() method is used which does a safe swap with the value None. So after take(), head is None and take() returns the previous value of head. For your own types, you can use the library function mem::replace() to perform this sort of swap — the take() method is just a convenience because it’s such a common operation on Option.

Similarly, the use of Option::map() in pop() is potentially non-obvious — this is again a convenience method, this time equivalent to something like this.

match option {
    None => None,
    Some(x) => func(x),
}

Finally, the implementation of the Drop trait is to avoid an issue when a list gets freed. By default each element’s drop() method (loosely a destructor) would call drop() on the next item in the list — but this could lead to stack overflow, which isn’t anybody’s definition of a good day. The default behaviour can’t be tail-recursive, for reasons Alexis explains in his tutorial, so we need to provide our own implementation. All this does is run down the list using Option::take() to swap out the pointer to the next item in the list to break the recursion, and then let the current item just expire off the stack normally.

Smart Pointer Traits¶

Those from C++ can probably see how Box is fairly analagous to unique_ptr, although the different ownership semantics of the language make the direct comparison a little harder. One particular similarity is that Box<T> implements a trait called Deref, which is what allows it to be treated as if it were a regular reference. This requires types to implement a method called deref(), which simply returns &T. There’s also the DerefMut trait and deref_mut() method for dereferencing in mutable contexts.

We’ve also already seen the Drop trait, which is important for all smart pointers that don’t want to leak memory. As you’d expect, the drop() method of this trait is called when a value goes out of scope. However, it’s also possible to drop a value early with std::mem::drop(). The compiler won’t let you call the drop() method of an object yourself, because to do so would create a double-free error, since the compiler will still call it when the value goes out of scope. However, std::mem::drop() handles this properly, even in cases where it’s been conditionally called earlier.

RefCell<T>¶

This is rather like Box<T> in that it references a single value. The difference is that its rules on ownership are deferred to runtime instead of compile-time — this creates a risk of runtime errors, but allows you to perform some potentially valid actions which compile-time static analysis would otherwise disallow.

The main difference between Box<T> and RefCell<T> is that the latter allows you to mutate the referred object even if the reference itself is immutable. This is useful in cases where classes need to keep track of certain implementation details internally, even when used as immutable objects. A trivial example could be keeping track of statistics like how many instances exist or how many times a given method has been called. This is a little like how the mutable keyword can be used in C++.

This isn’t to say that RefCell<T> totally ignores all the borrowing rules, however — it simply defers them to runtime. For example, if at any point you attempt to borrow two mutable references at the same time, you’ll get an immediate panic. As the famous quote doesn’t go, with great mutability there must also come great responsibility.

Rc<T>¶

If Box<T> is the rough equivalent of unique_ptr in C++, then Rc<T> is very loosely equivalent to shared_ptr. This adds reference-counting functionality into the mix, although unlike shared_ptr these aren’t safe to share across threads — it’s just a reference counted value which can have multiple owners, and is only freed when the last owner releases it.

When you call clone() on an Rc<T> instance, which is part of the Clone trait implemented by types which can be copied, then it just increments the reference count on the original and refers to the same memory location. This is simple enough, but there’s significant limitation in that you can only take an immutable reference to the object referred to — this shouldn’t be a surprise, because in the general case there will be multiple references to it, and we already know that mutable references have to be unique.

These objects do provide a try_unwrap() method which will allow you to extract the value, but only if you’re the sole owner at runtime — it returns a Result and you only get the Ok case if that holds true.

Reference Cycles and Weak<T>¶

We’ve already well established that Rust doesn’t have a garbage collector — Rust’s enforcement of ownership rules and referencing counting, such as in Rc<T>, generally mean that one isn’t required. As I’m sure some of you are already aware, however, there is one case in which a garbage collector is superior to reference counting — reference cycles.

If you’re not familiar with reference cycles, I suggest you check out the Garbage Collecting Reference Cycles section of one of my Python 3.4 articles which explains the concept. In essence, if you have a series of objects which all refer to each other in a closed cycle then the reference count of these objects will never return to zero — as a result, they will never be dropped.

This is actually quite valid in Rust — the compiler won’t complain, and neither will the runtime, but you will leak memory every time you leave such an orphaned chain lying around. If only one of these is allocated which lasts until program termination that’s not necessarily the end of the world, but in most cases these memory leaks will eventually consume more and more resources on your machine.

Since we don’t have a garbage collector to identify and free such orphaned cycles automatically, we need to avoid creating them in the first place. This is partly down to good data structure design, making sure everything has a clear hierarchical relationship so that references don’t point back up the tree and cause cycles. However, in some cases this can be quite hard to achieve so there is another option — weak references.

You might be familiar with weak references in other languages — C++ has weak_ptr, Python has weakref and C# has WeakReference. These all share some similar semantics, primarily being that they allow an object to be referred to, but in a way which isn’t guaranteed to succeed — if the object is freed then the weak reference’s existence is not sufficient to keep it alive, so if it’s been freed since the weak reference was created then it needs a way to indicate that.

In Rust a weak reference can’t be used directly, but instead an upgrade() method is called which attempts to turn it back into a strong reference — this returns Option<Rc<T>>, which is None if the value no longer exists or Some(Rc<T>) if it does. Of course, once you have an Rc<T> then this strong reference will tick up the reference count and make sure it’s safe to refer to it for as long as it exists.

To create the weakref in the first place, Rc<T> offers a downgrade() method which returns a Weak<T> for the referred value. This ticks up a separate weak reference count, and only the strong reference count is checked when deciding whether to drop an object when a reference to it is released.

This is all fairly standard stuff, but it’s important to get right because reference cycles can be a real pain to track down. But if you visualise your data structures, and keep a clear notion of ownership in your head whilst working with them, then the choice of reference type should be clear in most cases.

Conclusions¶

That’s it for this article. It feels as if I’ve made my way through quite a lot of the language semantics that I wanted to cover by now, although there’s still a huge gaping hole around concurrency that needs to be filled, and that will likely be the final article in this series.

The topics in this article have been interesting to cover, because iterators and closures are both features that seem quite familiar to me from Python, although of course some of the specific semantics differ. I found it quite natural playing with these in code, although it’s hard to say how much of that is due to familiarity on my part in other languages, and how much is due to inherent simplicity.

The smart pointers, on the other hand, took me awhile to get to grips with. It wasn’t really the pointers themselves, but things like the linked list example took a bit of grappling to get all the syntax correct — for example, the way that Rust does implicit dereferencing in some cases is helpful, but can also cause a bit of confusion when you’re first learning things. Also, the move semantics by default take some getting used to. However, having run through the linked lists tutorial I mentioned earlier, I feel like it’s really helped solidify my familiarity with it — I can heartily recommend it.

All in all, I can now understand why people say that Rust has a steep learning curve — it’s not that other languages necessarily have any less depth, but it does feel like Rust forces you to understand more of it to get anything useful done. That said, I don’t think that makes it either a better or worse language in the long term at all — it just means you have to put in a little more effort to make a considered opinion.

But what I will say is that the quality of the tutorials and documentation out there is really, really excellent — many of them don’t just take you through the happy cases, they also explain why things work that way, and what would happen if they didn’t. That sort of depth is sadly lacking in many tutorials for languages, which try to rush you through as many features as they can with as little verbiage as possible.

That’s it for this article. Whenever I next get back to Rust as a topic then I’ll most likely be looking at concurrency, although I think I may take another tangent and write on different languages for awhile, so I can’t honestly say when that’ll be. I hope this has been helpful, and thanks for reading.