Types and Tailcalls

Understanding Pointers, Ownership, and Lifetimes in Rust

written on December 21, 2013

In the last couple of weeks I have been looking into Rust, a new language developed by the good folks at Mozilla. Rust is fairly unique in that it is aimed at the same space as C++: a systems programming language that gives you full control over memory but also offers high level language features. In the past few years a few languages have come out that claim to target this space, for example Go, D, and Nimrod. However, these languages are garbage collected by default and loose their memory safety when memory is managed manually (D, Nimrod) or do not offer this possibility at all (Go). Therefore, these languages are not well equiped for applications which require full control over memory, which is the use case where C++ shines.

I think it’s great that C++ finally gets some real competition. Even among C++ fans, few will deny that compatibility with C, decades of language evolution, and accidental language features have created a very complex language that is extremely difficult to master. I think it is quite sad that for a lot of applications, C++ is still the only sane choice. We need a simpler language that offers more modern language features while targeting the same space. Rust could just be that language.

Ok now, the point of this post is not to argue the case for Rust nor to heap (well deserved) praise onto the Rust designers and implementers. I want to talk about the ownership semantics in Rust and how they interact with the different type of pointers in Rust.

Rust’s Guiding Principles

To me, understanding something means discovering and understanding the reasons and guiding principles behind the things on the surface. From these, it should be easy to reason about other things and quickly understand why they must be one way and not another. To me the guiding principles of memory managemend in Rust are the following:

  1. Manual memory management: There must be some way for the programmer to control when an object on the heap will be deleted.

  2. Memory safety: Pointers must never point to areas of memory that have been changed or deleted.

  3. Safe Concurrency: There should be no dataraces between threads. Multiple threads must not read and modify the same part of memory at the same time.

  4. Compile time checks: Ensure correctness at compile time instead of runtime whenever possible.

This, in conjunction with the features that Rust provides, will give us a good idea why certain things must be the way they are in Rust.

Different Types of Pointers in Rust

There are several types of pointers in Rust: owned pointers and borrowed pointers are directly supported by the language. There used to be a third type, managed pointers, but these are currently being removed and replaced by garbage collected and reference counted pointers which live in the standard library. Each pointer serves a different purpose. This post will focus on owned and borrowed pointers.

Owned Pointers

An owned pointer in Rust has ownership over a certain part of the heap. When it goes out of scope it deletes that part of the heap. This achieves manual memory management: the programmer has control over when memory is released by controlling when an owned pointer goes out of scope. Owned pointers are denoted and introduced by ~, so ~int is an owned pointer to an int. Like all pointers, owned pointers are derferenced by prefixing them with *.

// The type annotations in the let statements in this example
// (e.g. ': ~int') are not necessary and only for clarity

fn owned_seven() -> ~int {
    // Allocate an int with value '3' on the heap, 'three' points to it
    let three : ~int = ~3;
    // The same for four
    let four : ~int = ~4;
    // Dereference both 'three' and 'four', add them, store the result
    // in a newly allocated variable on the heap
    ~(*three + *four)
}   // <-- 'three' and 'four' go out of scope, so the memory they own
    //     is released. The memory of the return value is owned by the
    //     return value so it survives the function call.

fn main() {
    let seven : ~int = owned_seven();
    // Writing (*seven).to_str() is not really necessary, because the '.'
    // operator auto-dereferences, so we can also write 'seven.to_str()'
    println("3 + 4 = " + (*seven).to_str());
}   // <-- seven goes out of scope and the memory it points to is
    //     deallocated here

Borrowed Pointers

Having only owned pointers would make writing many programs difficult: there could only ever be one reference to every thing. Fortunately, Rust offers another type of pointer called a borrowed pointer. Borrowed pointers do not imply ownership and they can point to objects both on the heap and the stack, so they are quite flexible. We can create an owned pointer by taking the address of something with the address-of operator &. In a slight abuse of notation, the types of borrowed pointers are also denoted by prefixing the type of the variable it points to by &, so &int is a borrowed pointer to an int.

fn main() {
    let three : &int = &3;
    let four : &int = &4;
    println("3 + 4 = " + (*three + *four).to_str());
}

Borrowed pointers are a lot like references and pass-by-reference bound variables in C and C++, but note that unlike C/C++-references borrowed pointers must be dereferenced to get to their values. I think this is really more consistent, because references, borrowed pointers and other pointers really hold the address to a memory location, so it makes sense to treat them similarly in terms of syntax. Rust also provides a number of safety mechanisms that C/C++ references lack, but more on that later.

Reference Counted and Garbage Collected Pointers

Owned and borrowed pointers fit a lot of use cases, but sometimes they are not enough. With these pointer types, each piece of memory must have an ultimate owner. This means that the ownership of all objects on the heap must be representable as a directed acyclic graph. Up to version 0.8, Rust offered managed pointers with the syntactic form @. These are currently being removed and will be replaced by the Rc and Gc pointers in the standard library. This post will ignore these two pointer types.

Move Semantics

Memory safety implies that owned pointers cannot be copied or cloned. Otherwise, two such pointers could point to the same block of memory and that memory would be deleted twice. Therefore, owned pointers have move semantics:1 when owned pointer o2 is initialized from owned pointer o1, o1 is no longer valid. By guiding principle number four, we would perfer to ensure this at compile time, and Rust indeed does this.2

fn main() {
   let o1 = ~"world";
   let o2 = o1;                // <-- o1 is 'moved' into o2 and now invalid
   println!("Hello, {}!", o1); // <-- this is a compile time error
}

Indeed the Rust compiler reports:

move.rs:4:26: 4:28 error: use of moved value: `o1`
move.rs:4    println!("Hello, {}!", o1); // <-- this is a compile time error
                                    ^~

Structs and Enums

In general Rust has what we might call shallow copy semantics: When an object is initialized via assignment or call-by-value then its memory is a bitwise copy of the object used to assign it. However, this is changed when an object contains an owned pointer: because the owned pointer has move semantics, the object containing it must also have move semantics, otherwise we would again incur two independent owning copies.

struct Pod {x: int, y: uint, z: [3... int]}
struct WithOptr {x: int, p: ~int}

fn main() {
   let a1 = Pod {x: 3, y: 4u, z: [1,2,3]};
   let a2 = a1;
   println!("{:?}", a1);                   // <-- OK, a1 has been copied
   let b1 = WithOptr {x: 3, p: ~4};
   let b2 = b1;
   println!("{:?}", b1);                   // <-- Compile time error, b1 has been moved
}

The same rules apply to enums, but here the error messages can be a bit more confusing.

enum MyEnum {
     X(int),
     Y(~int)
}

fn match_and_print(e: &MyEnum) {
    match *e {
        X(x) => println!("{}", x),  // <-- OK, x can be copied
        Y(y) => println!("{}", *y)  // <-- Error, y cannot be moved out of a reference
    }
}

fn main() {
   let x = &X(3);
   let y = &Y(~4);
   match_and_print(x);
   match_and_print(y);
}

In this case the compiler reports

move.rs:33:8: 33:12 error: cannot move out of dereference of & pointer
move.rs:33         Y(y) => println!("{}", *y)
                   ^~~~

Standard pattern matches are pass-by-value, meaning that the contents of the enum is either copied or moved. However, this can only be done when we have ownership over the values to be moved. When we apply match to a dereferenced borrowed pointer, we cannot move because we don’t have ownership. Changing the match_and_print function to take a copy would work again:

fn match_and_print(e: MyEnum) {
    match e {
        X(x) => println!("{}", x),
        Y(y) => println!("{}", *y)
    }
}

The ref Keyword

Copying or moving values in pattern matches is not always what we want. Sometimes we just want to take a reference. This way we can pattern match on values which we have obtained via borrowed pointers or we can simply avoid a move or copy. This is where the ref keyword comes into play: It changes the pass-by-value semantics of a pattern match to pass-by-borrowed-pointer semantics:

fn match_and_print(e: &MyEnum) {
    match *e {
        X(x) => println!("{}", x),
        Y(ref y) =>                 // OK, y is a borrowed ptr to ~int
            println!("{}", **y)     // y has type &~int and must be dereferenced twice
    }
}

To bind mutable references there is also the ref mut version which allows modifying:

fn match_and_print(e: &mut MyEnum) {
    match *e {
        X(x) => println!("{}", x),
        Y(ref mut y) => {
            **y = 5;
            println!("{}", **y)
        }
    }
}

fn main() {
   let x = &mut X(3);
   let y = &mut Y(~4);
   match_and_print(x);
   match_and_print(y);
}

The ref keyword and its ref mut variant also work in let bindings:

fn main() {
   let mut x = 3;
   let ref mut y = x;
   *y = 4;
   println!("{}", *y);
}

Lifetimes

The difficulty with borrowed pointers is that they themselves cannot ensure that they point to valid memory. What if the thing that owns the memory they point to goes out of scope or is reassigned? Since the borrowed pointer has no ownership that memory would be deleted and possibly reassigned. The borrowed pointer would become a dangling reference, which is precisely what we wanted to avoid per guiding principle number 2: memory safety.

Therefore Rust must take a number of precautions to ensure these scenarios do not happen. First, the memory that a borrowed pointer points to must not be freed during that borrowed pointers lifetime. Second, this memory must not change while it is borrowed.

The first requirement leads us to the concept of lifetimes, the amount of time that some object is guaranteed to exist.

fn lifetimes1() {
    let name = ~"world";               //                 <--+
    if (3 < 5) {                       //                    |
        let bname = &name;             // <--+               | name's
        println!("Hello, {}!", name);  //    | bname's       | lifetime
        println!("Hello, {}!", bname); //    | lifetime      |
    }                                  // <--+               |
}                                      //                 <--+

In this example, it is quite clear that the lifetime of bname will be shorter than that of name and thus the compiler needs no help in figuring this out. However, things need not always be this simple, consider the following example:

fn lifetimes2() {
    let mut x_ref = &3;       //                 <--+
    if true {                 //                    |
        let mut y_ref = &4;   // <--+ y_ref's       | x_ref's
        x_ref = y_ref;        //    | lifetime      | lifetime
    }                         // <--+               |
}                             //                 <--+

Here we have a problem: x_ref is reassigned to point to the same memory location as y_ref, but y_ref’s lifetime is shorter than x_ref’s. To ensure memory safety, the compiler must rejetct this program, which it does:

lifetimes.rs:21:24: 21:26 error: borrowed value does not live long enough
lifetimes.rs:18:16: 24:1 note: borrowed pointer must be valid for the block at 18:16...
lifetimes.rs:20:12: 23:5 note: ...but borrowed value is only valid for the block at 20:12

Things become even more interesting when we work with borrowed pointers inside of a function:

fn minLife(x: &int, y: &int) -> &int {
    if (*x < *y) {
        x
    } else {
        y
    }
}

Here the lifetime of the result depends on the condition evaluated in the if statement: depending on it the lifetime will either be that of x or that of y. Clearly, the compiler can’t resolve this automatically, it would need to know the values to which x and y point, which may only be known at runtime:

lifetimes.rs:11:4: 15:5 error: cannot infer an appropriate lifetime due to conflicting requirements
lifetimes.rs:10:37: 16:1 note: first, the lifetime cannot outlive the anonymous lifetime #2 defined on the block at 10:37...
lifetimes.rs:11:4: 15:5 note: ...so that if and else have compatible types (expected `&int` but found `&int`)
lifetimes.rs:10:37: 16:1 note: but, the lifetime must be valid for the anonymous lifetime #3 defined on the block at 10:37...
lifetimes.rs:11:4: 15:5 note: ...so that types are compatible (expected `&int` but found `&int`)

Since the compiler can’t infer the lifetimes we must annotate them. Alas, we too would be hard pressed to give the exact lifetime in this example. However, there is a trick by which we can manage this

fn minLife<'a>(x: &'a int, y: &'a int) -> &'a int {
    if (*x < *y) {
        x
    } else {
        y
    }
}

Here we explictly annotate the lifetime of the parameters and the return value. Lifetime parameters are introduced by a single tick ' followed by an identifier. In functions these must be the first template parameters. As you can see we use the same parameter for the lifetime everywhere. If the compiler would take this information too literally, then this function whould be less flexible than we might wish: In this case we could only use it on borrowed pointers which have the exact same lifetime. Fortunately, the compiler interprets the provided lifetimes as a lower bound. Thus 'a is the minimum of the lifetimes of x and y. There is one special lifetime, which is called 'static and is for objects which are allocated for the entire life of the program.

Freezing

Another problem with borrowed pointers is that the memory must not be modified while it has been borrowed out. This is achieved by freezing the original object when a borrowed pointer to it exists:

fn freeze() {
    let mut x = 3;
    {
        let mut y = &x;
        x = 4;       // <-- Error: x has been borrowed and is thus `frozen`
    }
    x = 4;           // OK
}

In the block we cannot modify x because it is borrowed:

lifetimes.rs:22:8: 22:9 error: cannot assign to `x` because it is borrowed
lifetimes.rs:22         x = 4;       // <-- Error: x has been borrowed and is thus `frozen`
                        ^
lifetimes.rs:21:20: 21:22 note: borrow of `x` occurs here
lifetimes.rs:21         let mut y = &x;
                                    ^~

Note that this restriction is irrespective of whether the borrowed pointer is mutable or not.


  1. The other alternative would be that owned pointers can never be reassigned, they would be non-copiable and non-moveable. This seems pretty cumbersome, fortunately Rust’s owned pointers have move semantics.

  2. Ensuring the validity of owned pointers at compile time is much better than the alternatives: If it was assured at runtime, there would be fewer correctness guarantees about the program and the check would have to be performed every time a pointer is dereferenced. Checking the validity of pointers at compile time is a major achievement of the Rust language: tracking such moves at compile time requires an advanced type-system feature called linear types. As far as I know Rust is the only mainstreamy language which has such a feature.


comments powered by Disqus