Memory, Lifetimes and Trait objects

This section differs slightly from the other sections in that the primary focus is not on introducing new concepts but rather taking a deeper dive into previously covered topics. Most importantly, we'll go through a bit of computer memory, how it is managed and how it relates to Rust's ownership system (the details regarding is something we deliberately did not emphasize when talking about ownership). We will also discuss unsafe Rust and why it is a necessary part of Rust. We will then discuss lifetimes, which is a way to ensure that references are valid, and when they need to be explicitly defined in code. Finally, we will look at trait objects, which are generics whose types are unknown to the compiler and only inferred during runtime.

Stack, Heap and Ownership

For a computer program to be able to do useful work for us, it needs a way to store the information of ongoing processes. How this information is stored is known as memory management. To be clear, memory management is not about information stored on disk (although memory management systems often involve moving memory to and from disks), rather in the main memory, the high-speed devices used for the "working memory" of a computer, nowadays synonymous with RAM,

Memory management can be split into the following categories correlating with the lifecycle of information:

1. Creation. How is memory allocated in order to store the information?
2. Processing. How is information accessed, modified and moved in memory?
3. Destruction. How is the previously allocated memory freed for other use after the information is no longer needed?

The questions above can have vastly different answers based on how memory is (or should be) managed in a programming language. Modern programming languages mostly have built-in automatic memory management (e.g. Python and JavaScript), whereas in classic programming languages, such as C, memory has to be mostly managed manually with code.

Most modern programming language implementations approach memory management using a system known as a garbage collector. A garbage collector cleans (i.e. frees the memory used by) the "garbage" left behind by the running program. The word "garbage" refers to information which reserved by a program but no longer accessible to the program.

In Rust, memory is not managed automatically by a garbage collector — but neither is it the programmer's responsibility to manage memory manually (unlike in e.g. C or C++ where memory is allocated and deallocated in code with functions such as malloc and free). In fact, memory cannot be managed manually in safe Rust — safe Rust is the Rust language that we have been studying so far where memory safety is guaranteed by borrow Rust's ownership and borrowing rules.

Sometimes the rules of safe Rust are too strict however. Thus there is also unsafe Rust, a sort of a sublanguage of Rust that is free of the limits of the borrow checker and ownership system. The focus of this course is primarily on safe Rust and how the borrow checker manages memory and what options we have within safe Rust. Regardless, we'll go through unsafe Rust too but only on a high-level without going into details.

To understand memory management in Rust, it is important to understand what stack and heap are, two essential regions of memory available for a program at runtime.

In short, the stack is a region of memory which is used to store information about the active functions and local variables in a program. It is fast because it is fixed size and modified the same way as a data structure, last in first out (LIFO); when a function is called, memory required for the function is reserved from the top of the stack and the memory is freed when the function returns. This makes deallocation and allocation possible by simple moving the stack pointer up and down. It also means that the size of the stack is limited, a stack overflow happens when the stack does not have room to accommodate memory assigned to it.

The heap is a region of memory that is used to store information dynamically at runtime. The heap has less limitations compared to stack as memory can be allocated at any unreserved portion at any time in the heap but this also makes the heap more expensive to use as more complex management is required to ensure safe allocations.

In case you haven't yet read the Stack and Heap section from the Rust book, we highly recommend doing so now.

The following table summarizes the practical differences between the stack and the heap in a rule of thumb fashion.

We'll next look at some code examples that highlight how the stack and heap are used in Rust and how they relate to ownership.

Stack and pointers

All functions and their related information such as local variables (variables inside functions) in Rust are stored on the stack. When calling a function, the arguments and local variables get pushed onto the stack, among other things.

In this simplified example, when the function main is called, the variable x is allocated on the stack with 32 bits of memory. Once the program returns from the main function call, all local variables are deallocated, which invalidates the memory address of them including x.

A pointer is a number which stores a memory address. It's important to note that references in Rust are not just pointers, as we will see later.

The memory address of x can be printed by formatting a reference to x using the pointer-format parameter :p.

The memory address which is printed out as a hexadecimal (indicated by the prefix 0x) number lies on the stack.

Memory addresses to the stack rarely stay the same when there are multiple functions being called.

Pushing plate1 onto the call stack on top of main leads to the local variable x being stored in a different location as opposed to when plate1 is pushed on top of plate2.

The location of x when plate1 is called from plate2 is smaller, because the stack grows backwards in regard to memory addresses.

The pointers which are printed always have a fixed size based on the architecture of the processor running the program. For 64-bit processors, a memory address is always represented by a 64-bit number. To account for different CPU architectures, we use the usize integer type, which always matches the pointer size of the target architecture.

The usize numbers are used when indexing, setting the length or getting the length of arrays and vectors.

Values than can be copied (types that implement the Copy trait), like i32 and usize or tuples and arrays that only contain copiable values, are also stored on the stack. This is the reason why Rust implicitly copies such values; it is cheap to allocate them on the stack. Because of the implicit copying, we rarely encounter issues with ownership regarding stack stored values (excluding issues related to references of course).

Values that can't be copied, like String which has a dynamic size and is therefore a bad option for storage in the stack, are stored on the heap.

Another bad option for storage in the stack is large collections. The stack has a limited size, which is usually a few megabytes. If we try to allocate a large array on the stack, we will get a stack overflow error at runtime.

To overcome such an annoyance, we can force the compiler to allocate the big array on the heap instead of the stack by using for instance a Vec to allocate the values on the heap instead of on the stack.

Heap and ownership

The heap is an area of memory used to store data more dynamically than on the stack. It can also be used to store large collections of values more safely than stack. In programming languages with a garbage collector, the heap is managed automatically. In Rust, most heap memory is managed automatically by the compiler according to the rules of ownership.

Many data types, like Vec, String and HashMap use memory on the heap to store their contained values. When adding elements to a Vec, a continuous chunk of memory is automatically allocated on the heap for storing the values. The address to the memory can be accessed using the as_ptr method.

In the example, we create an empty Vec which initially contains a pointer to unallocated memory. Writing to unallocated memory would be a memory bug, so the vector has to make a heap allocation upon any push that would make the length of the vector greater than its capacity, starting from the first push. Try changing Vec::new() to Vec::with_capacity(1_000) to do the heap allocation beforehand.

The heap allocated memory is not moved when the Vec is moved. It is the Vec struct itself that contains a pointer to the heap is on the stack that gets its ownership moved to the other variable.

Notice that the address in the heap is the same in both cases. The memory in the heap is not affected when the Vec is moved. It is the Vec struct itself that contains a pointer to the heap that gets its ownership moved to the other variable, and the struct itself is stored on the stack. Moving a Vec is fast as the elements remain as they are in the heap, only the pointer needs to be copied to the stack for the function call.

Once the Vec's owner goes out of scope, the heap memory gets freed by the borrow checker as the value is dropped.

Cloning from (and to) the heap

Most types in Rust implement the Clone trait, which is usually used to create another "identical" copy of a value. For Copy types, this means a bitwise copy in the stack, but for non-Copy types the clone implementation can be really anything.

For instance, the Vec type has a clone method which creates a new Vec with the same contents as the original by allocating new memory in the heap and storing copies of the values (using .clone() for the inner values) of the original vector.

To demonstrate a potential downside of this, let's see what happens to a Vec of references when cloned.

The address in the heap for the stored &strs changes, because during cloning, another chunk of heap memory is allocated for the clone. However the static strings are still at the same address because only the & references got copied in the heap, not the actual values behind the references.

Cloning data to avoid ownership issues is unadvised, as it can potentially lead to bugs, and it usually incurs efficiency penalties. Using references and working with lifetimes is usually the better way to go.

Breaking the rules with unsafe

All types are not Copy because some types can't be safely copied. A common reason is that the type contains a pointer to some data on the heap.

Consider the next example where we try to copy a vector v into variable w and then use both vectors.

Copying a Vec struct, which is on the stack, would result in two Vecs which are both responsible for freeing the same memory in the heap. This is not allowed by the ownership rule, which states that each value can have only one owner at a time.

Rust has a feature, known as unsafe Rust, which allows programmers to get around some restrictions of safe Rust and work instead with raw pointers among other things. To write unsafe Rust, we must use the keyword unsafe before a code block or a function.

It is important to mention that despite its name, unsafe Rust does not mean it is unsafe to use or run, rather that it is not necessarily safe as per the Rust's ownership system. It is a way of saying to the compiler: "I have checked the correctness, including memory safety, of the following code myself."

In the next example, we use an unsafe function Vec::from_raw_parts incorrectly.

This code is extremely volatile and causes undefined behavior, because both vectors free the same allocated memory. This memory safety bug is known as a double free.

It is worthy to note that in most cases, unsafe Rust is not needed. With great power comes great responsibility.

Some common and good reasons to use unsafe Rust are:

• Interacting with C code, which is unsafe because C is unsafe.
• Safe Rust alternative is too complicated or not performant enough
• Writing low-level code where usage of raw pointers is required

Going into detail in any of these topics is out of the scope of this course, but you can read more about them and unsafe Rust altogether in the Rustonomicon.

Lifetimes

Variables (which are always on the stack) constantly go out of scope and the memory used by them is constantly shuffled around during execution. How can Rust possibly keep track and ensure the validity of all references? With lifetimes!

Lifetimes define the sections of code where some piece of data, or a reference to it, is still valid. If this rings a bell, that's probably because the lifetime of a reference is synonymous to the scope of a reference, which we covered back in the part 4 of the course.

The compiler is always in charge of lifetimes, the programmer can only communicate relationships between lifetimes. The compiler can't always make the right decisions about relationships between some lifetimes, so we, the programmer, need to occasionally step in and provide lifetime annotations for the compiler.

Lifetime annotations are defined with a tick ', followed by the name of the lifetime, e.g. 'a. Consider the following simple example.

The code compiles fine, because the variable is valid until its value is dropped or moved, which in this case happens at the end of the main function, and that encompasses the whole lifetime of the reference r, denoted by 'a.

Now, if we make s a String and move it before the lifetime of the reference r ends, we get a compiler error.

Functions and lifetimes

What if we want to return a reference from a function? If the value we want to return is a reference to a value that is owned by the function, we have but one option: to annotate our return value reference type with a special lifetime specifier 'static.

The 'static lifetime specifier can fix many lifetime issues but often it is not the best choice. A 'static lifetimes means that the reference can be valid for the entire duration of the program. Even when the compiler suggests adding a 'static lifetime, it is best to think if that is really necessary and what you want for the reference.

Then, what about the case where we want to return a value from a function that is constructed from a reference parameter?

Well, it turns out that our example works just fine. The compiler is smart enough to figure out that the returned reference should be valid for the lifetime of the parameter s.

However, if we go ahead and make the return value of last_chars 'static, we'll quickly run into problems.

Note that the output reference of type &'static str depends on the input reference s. This means that as the output can live for the whole duration of the program, so needs the input, and the input must be 'static too. Then we can no longer take in reference from local variables, because they won't live long enough.

Then, we get into a whole different kind of a problem if we have multiple references that the return value might depend on.

The compiler complains that it can't figure out what the lifetimes of function parameters and returned reference should be. This is because the return value could be from either s or t. We can fix this by following the compiler advice to add a generic lifetime parameter 'a and specify it for each of the references. The fix informs the compiler that the returned reference should be valid for the lifetimes of both of the parameters s and t. In practice, this causes the return value's lifetime to be the same as the smaller lifetime of the two parameters.

To elaborate the problem in the above example further, let's see what happens when we give the two parameters distinct lifetime parameters and use only one of them for the return type.

This doesn't compile because the longer returns a reference with a lifetime of at least 'a but the function may return a reference with lifetime of 'b, and the compiler cannot know for certain that 'b will be outlive 'a. Thus the compiler suggests adding a lifetime bound of 'a to 'b using the syntax: 'b: a' (even though we could just use 'a for both of the parameters). Lifetime bounds are similar to trait bounds (T: U), trait bounds require a type that implement a trait T to implement the bound trait : U and lifetime bounds require a lifetime 'a to be at last at least as long as the bound lifetime (: b).

Lifetimes can be difficult to get right. While most likely we can get by with just a single lifetime specifier, it is a good idea to not constrain ourselves unnecessarily with lifetimes.

Consider the following example, which does not work.

The reason this does not work is that the function extract_suffixed tells that both the suffix parameter and the &strs inside the slice parameters should have the same lifetimes. So in the main function, the lifetime of the reference suffix: &str that is passed to the function needs to live as long as the values inside slice, which is also passed to the function. Yet the suffix.remove(suffix.len() - 1) method call takes a mutable reference to suffix, which is not ok for the borrow checker: the immutable borrow of suffix for the previous function call is still alive.

The solution is to remove the constraint 'a from the function parameter b to relax the lifetime constraint. We can give it for instance another lifetime 'b, or even better, we could simply elide, i.e. omit, the lifetime parameter from b altogether. The parameter b is not referenced in the returned value, so the compiler can determine its lifetime without the need explicit annotations.

Lifetime elision rules

So, when exactly can lifetimes be elided? Like ownership, lifetime elision has three rules.

1. Each parameter that is a reference gets its own lifetime parameter: fn f(x: &str, y: &str) is the same as fn f<'a, 'b>(x: &'a str, y: &'b str).
2. If there is exactly one input lifetime parameter, that lifetime is assigned to all output lifetime parameters: fn f(x: &str) -> &str is the same as fn f<'a>(x: &'a str) -> &'a str.
3. If there are multiple input lifetime parameters, but one of them is &self or &mut self because this is a method, the lifetime of self is assigned to all output lifetime parameters: fn f(&self, x: &str) -> &str is the same as fn f<'a>(&'a self, x: &str) -> &'a str.

To provide a simple rule of thumb, (in most cases) lifetimes can be elided from functions according to the following two rules:

1. The function takes in at most one reference, or
2. The function returns nothing that contain references

Note that it is also possible for the compiler to be able to infer the lifetimes of references by the lifetime elision rules in a way that is semantically incorrect, i.e. the code may compile but has a bug related to lifetimes. See for instance the nice example in this blog post about common lifetime misconceptions (the whole blog may be an insightful read).

As a summary, lifetimes are generics like generic types and lifetime annotation parameters are defined within the familiar angle brackets <>. However, unlike with generic type parameters, we cannot pass "concrete" lifetimes to functions since the concrete lifetimes are always the responsibility of the compiler.

One important thing to note is that when lifetime parameters are used alongside generic type parameters, they go inside the same <> brackets as the generic type variables.

Also lifetime bounds can be added to trait bounds, a lifetime bound for a type, e.g. T: 'a, means that all references in T must outlive lifetime 'a

Lifetimes everywhere

As we saw with functions, lifetimes are most of the time elided, i.e. left out of the code. This makes writing Rust much more concise and, to an extent, easier. But, even though we can't see the lifetimes they are still there and at times we need to think about them. Here are some places where a lifetime parameter may be lurking.

• a struct method
• a function which takes references
• a function which returns references
• a trait method
• a closure

As an example, let's look at a struct, FullName, which contains references to two strings slices.

Compiling this code fails with missing lifetime specifier.

We therefore need to use generic or 'static lifetime specifiers. Restricting the string to a static lifetime would most likely be too restrictive, so let's add a lifetime parameter 'source for the struct.

In the example, when creating a FullName, the compiler infers the concrete lifetime for 'source, which in this case represents the lifetime 'last — the smaller of the two lifetimes 'first and 'last.

When implementing associated functions for a struct with references, we need to annotate the lifetime of the struct for the implementation block, at least with a placeholder.

We would probably be better off using the struct's lifetime specifier than the placeholder lifetime _ though, because then we can return Self and also have parameter lifetimes bound to the structs lifetime easily.

Trait objects and dynamic dispatch

In the beginning of the course, we may have given the impression that the type of every value in Rust must be known at compile-time. This is true for most part, but we can opt out of it in a special case — albeit with a cost. Rust has special generic types called trait objects, which do not have a concrete type during compile-time.

They are named as such since they are defined through a trait and resemble objects in object-oriented programming (OOP) in that they are containers for both data and behaviour (unlike structs which are separate from their implemented behaviour). If you are familiar interfaces in OOP, trait objects are highly similar to objects created with an interface as the type. We don't need to care of the exact type of the object/instance, only that the needed functionality is there.

Trait objects provide a convenient way to store references to data of different types, but which implement the same trait. This is useful for storing references to different types of data in a single collection.

Trait objects are created by using the dyn keyword and the trait name. The dyn keyword is required to highlight that the trait object is dynamically dispatched and carries a runtime cost. The keyword wasn't required however until the Rust 2021 edition, but using it is recommended for any version that supports the keyword.

Trait objects are dynamically sized types like str, so they have be used through some kind of a pointer, like a reference.

However, trait objects have somewhat strict rules to ensure that the trait object is safe to use. We can't have e.g. dyn Speak in a Vec but Vec<&dyn Speak> works fine. The details of the safety rules are specified in the object safety section in the Rust reference.

Another option to have trait object is to wrap the trait object in a smart pointer, such as Box to force heap-allocation of values. Having the value heap allocated through a smart pointer is the only option to have owned trait objects in a collection.

If we have a collection of concrete types and want to store them in a collection of trait objects, we can cast the type into a trait object with the as keyword, effectively erasing the compilers knowledge of the type.

Trait objects are especially useful when we are implementing a library. If we want to allow the users of the library to store their own types in a generic collection, the option of using enums goes out of the window — an enum in an external crate cannot be extended with new variants without modifying the external crate itself. For a practical example, see the GUI library example in the Rust Book.

We can also use trait objects for more convenient error handling, by having a function return any Result where the error type implements the Error trait.

Consider for instance a situation where we both read from input (a source for io::Error) and parse the input to integers (a source for num::ParseIntError). In order to use the ? operator for avoiding constant unwrapping we need a generic type that can be both of the return types — the trait object Result<T, Box<dyn Error> is just that.

The return types are coerced into the trait object type Box<dyn Error> so there is no need for be explicit casting.

Summary of new syntax and keywords