Rust is fairly new multi-paradigm system programming language that claims to offer both high performance and strong safety guarantees, particularly around concurrency and memory allocation. As I play with the language a little, I’m using this series of blog posts to discuss some of its more unique features as I come across them. In this one I’m looking at how Rust’s trait system and how generics are implemented.
This is the 5th of the 7 articles that currently make up the “Uncovering Rust” series.
Following on from the previous article in this series, which finished off by looking at how methods can be implemented on types in Rust, I thought it was appropriate to continue the theme of object-orientation and look at Rust’s traits system, and how it implements generics. We’re also going to spend some time discussing the lifetimes of values, which are important to understand as you start to build more complex code.
To some people these might feel like more advanced features within the language, but in Rust they’re actually fairly straightforward, given the features of the language that we’ve already seen. So let’s jump right in and start with generics.
In common with most languages, Rust has support for generic data types, such as a collection which can be specialised to store multiple different types using the same code, and generic functions, which can operate on parameters of multiple types. As always, these features are about minimising code duplication whilst still maintaining type safety.
Let’s look at generic functions first. Suppose we want to write a total()
function which takes an array of numeric types, and we’d like it to work with both integers and floats without having to rewrite it. Let’s have a go using the Rust generic syntax.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
This seems fairly straightforward — our total
function takes an immutable reference to an array of a type T
and returns a single value of T
. It initialises the total to the first element of the array1, and then adds the remaining elements onto it with the +=
operator, returning the result. Seems simple enough, but when we try to compile it we get this error:
error[E0368]: binary assignment operation `+=` cannot be applied to type `T`
--> src/main.rs:4:9
|
4 | total += item;
| -----^^^^^^^^
| |
| cannot use `+=` on type `T`
|
help: consider restricting type parameter `T`
|
1 | fn total<T: std::ops::AddAssign>(items: &[T]) -> T {
| +++++++++++++++++++++
The body of the function is fine, but the compiler has noticed that we’re using +=
on variables of type T
— since we haven’t constrained what T
could be, then this isn’t necessarily valid, and hence the compiler doesn’t let us use it.
This highlights a key difference between generics in Rust and templating in C++. In C++, templates are essentially textual substitution, and any type-checking is only performed on the instantiated templates — therefore you can write a template which assumes any restrictions you like and you’ll only get an error if you actually use a type for which it’s not valid. This is convenient, but it can lead to some surprises — for example, you might write some template that’s intended to take numeric types and use the +
operator, but later accidentally use this with some string-related types for which +
is defined to perform concatenation.
In Rust, however, type-checking is done on the generic itself — if the code you’ve written isn’t valid for any possible type then it’ll be rejected. As a result you often need to add constraints to your types, so the compiler can convince itself that the operations you’re performing on them will be valid.
To add such constraints we need to use traits — we’ll look at these in more detail a little later in this article, but for now this is how we tell the compiler that we want to only define this function for types of support +=
operations.
1 2 3 |
|
If we do this and try again we get another error, this time complaining that we’re assigning items[0]
by value, but some types may not support this. To resolve this second error, we need to add another constraint that T
must support the Copy
trait2. After making this change, our entire code now looks like this, which compiles.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
As you might expect, the same syntax is used to declare generic structures.
struct ThreeTuple<T> {
first: T,
second: T,
third: T,
}
This declares a homogenous type, where T
must be the same for all three fields. If you wanted a heterogeneous type you can just use three different type names.
struct ThreeTuple <T, U, V> {
first: T,
second: U,
third: V,
}
Mind you, templating across more than 2-3 types tends to get out of hand pretty quickly and make your code an unreadable mess, so if you end up doing that I suggest it’s time to look for ways to refactor.
You might well realise this is exactly the same syntax as we’ve already seen in previous articles on Option
and Result
enumerations.
enum Option<T> {
Some(T),
None
}
enum Result<T, E> {
Ok(T),
Err(E),
}
When implementing methods on generic types, you have to remember to make the impl
directive generic as well. The example below shows this, as well as another example of trait-based constraints.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
You’ll note that the Add
trait also has an additional bound Output = T
— this specifies that the only conforming types are those where adding them to their own type yields the same type again. This is an example of an associated type of a trait, which is an extension to the trait system that I’ll briefly discuss later in this article.
Another aspect of this example that might not be immediately apparent is that Pair
is generic on any type, but pairwise_add()
will only be available for the subset of types which conform to both the Copy
and Add
traits, because of the constraint on the impl
block.
If we can define implementations that only apply to a subset of types, this immediately raises the question of specialisation — as in C++, can we have a default generic implementation of a function, and then override this with alternative implementations for more specific concrete types?
The answer to this, as far as I can tell, is currently a resounding sort of. Issue #31844 in the Rust tracker has been rumbling on for a few years about this, and has a lot more detail than I could cover here. There is already an implementation of the Rust specialisation RFC, but it’s described as “unsound”, so it can potentially cause undefined behaviour in otherwise safe code if used incorrectly.
There is another min_specialization
feature which implements a subset, covered by PR #68970, but my position until I’m more familiar with the language is to stay well clear of specialisation, if I can possibly avoid it, since it seems to be an area of the language which is still under active development. In practice I’m sure it’ll be possible to get the effect of specialisation using matching, potentially at a slight performance cost.
The last thing to discuss about generics is whether they impose significant runtime overheads via implementing some dynamic dispatch mechanisms or similar.
As with C++, there isn’t any runtime overhead associated with generics in Rust, because the compiler will emit separate instantiations for each type which is used. This is possible because the types are always known at compile time, so the correct instantiation can always be selected.
We’ve seen the use of some traits earlier in this article, such as AddAssign
and Copy
, to constraint the selection of types suitable for a generic to those which meet a particular interface. That’s how I think of a trait — it’s a specification of an interface.
Those used to more traditionally OOP languages such as C++ and Java might notice some similarities between traits and inheritance, but the semantics are different enough that I don’t think it would be accurate to call them equivalent. I think it is fair to say that they try to achieve some of the same objectives, however.
A trait essentially just defines a list of methods which will always be available on a type matching that trait. This is probably best illustrated with an example. I’m going to take the example from the previous article which used Point
and Rectangle
, and I’ll extend it to define a trait called Shape
and an additional Circle
type which meets the same trait.
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 |
|
Although this is a longish example, most of it should already be somewhat familiar from earlier articles. The parts to focus on are lines 46-51, where the Shape
trait is defined, lines 53-84, where the methods for the trait are implemented for both Rectangle
and Circle
.
One thing to note is that the num_corners()
definition in the Shape
trait has an implementation, which is used for Circle
because it doesn’t provide its own. Rectangle
, however, overrides this for itself. The use of the generic print_details()
function with the trait constraint to allow any Shape
should be familiar from the examples earlier in this article.
Now we’ve seen how to define a trait, and provide implementations of its methods for concrete types, we should see how we can use the trait to constrain types.
In the code example above, we’ve already seen how we can specify that a parameter can be any type which conforms to a trait on line 86.
However, this impl Trait
syntax is actually just syntactic sugar for a normal generic — the function signature above is equivalent to this:
86 |
|
It’s important to realise the correspondence, however, because there can be important differences. Consider these two signatures:
fn check_contains_A(first: &impl Shape, second: &impl Shape)
fn check_contains_B<T: Shape>(first: &T, second: &T)
These two are actually different — check_contains_A()
will allow its two parameters to be of different types as long as they both conform to Shape
, but check_contains_B()
requires its parameters to be of the same type.
If you want to constrain by multiple traits at a time, you just use the +
operator to string them together. You can see a couple of similar examples of this below.
fn duplicate_shape(shape: &(impl Shape + Copy)) -> impl Shape + Copy
fn duplicate_shape<T: Shape + Copy>(shape: &T) -> T
Once again, however, these aren’t strictly identical — the first can return a different type to the parameter. Given the name of the function, probably the second definition is more correct.
If you have lots of such traits to specify, it can get rather confusing, such as in the example below.
fn merge_shapes<T: Shape + Copy, U: Shape + Copy, V: Shape>(first: &T, second: &U) -> V
Fortunately there’s an alternative syntax where the bounds can be separated from their use in the signature using a where
clause.
fn merge_shapes<T, U, V>(first: &T, second: &U) -> V
where
T: Shape + Copy,
U: Shape + Copy,
V: Shape
{ ... }
As we saw in some of the examples above, we can also make functions which return generic types. Using the inline impl
syntax, you could write something like this.
fn random_shape() -> impl Shape
As you might expect, this specifies a function which may return any type which implements the Shape
trait. However, there’s a subtle issue here — the implication of a function called random_shape()
is that the type itself isn’t known until runtime — that’s actually not permitted, as the compiler needs to be able to predict at compile time what the concrete type would be for any particular instantiation of the function.
This is known as static dispatch, and it’s very useful because it allows generics to be used with little to no runtime overhead at all. There is a way to use dynamic dispatch instead, which actually forces the compiler to do a runtime lookup (a little like dynamic_cast<>
in C++) using something called trait objects. However, understanding how this works properly requires understanding how Rust deals with pointers, as opposed to the references we’ve dealt with so far, so we’ll come back to this topic in a future article.
So far we’ve looked trait bounds on function parameters and return types. It’s also possible to specify an impl {
… }
block which only implements functions on a subset of types specified by trait bounds. This is perhaps easiest to understand with an example. Let’s say that we want to define a trait which can print the maximum item in a container, and we want to implement that on a LinkedList
. Let’s look at an initial attempt based on what we know so far.
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 |
|
If you try to compile this you’ll hit some errors because we’ve tried to use the lt()
method on a value of type T
, and we’ve also passed it to println!()
which requires it to define an fmt()
method — since the code is valid for any type for T
, this is not guaranteed to be the case. However, we can specify a trait bound for the impl
block as follows:
1 2 3 4 5 6 7 8 9 |
|
This solves our compilation errors, but does also mean that the show_max()
method is only defined for LinkedList<T>
if T
implements both PartialOrd
and Display
. This makes sense when you think about it, but it’s important to understand the implications of these limitations for your code.
The handy thing about all this being by static dispatch, however, is that if we do try to use a type which doesn’t meet the criteria, the compiler will tell us so — we won’t get any annoying runtime failures. This means we can use generics quite freely, without worrying that we’re incurring overheads or creating risks of runtime failures for ourselves — but it does mean you need to have a good understanding of the types and traits that you’re using. Fortunately the Rust documentation is fairly comprehensive in this regard.
An aspect that’s not obvious from the discussion so far is how traits are shared between units of code3.
If you declare a trait as pub
, then other modules are allowed to refer to it, and they can add implementations for types using impl
. However, if any module was allowed to add implementations to just any type then this could quite easily break code — for example, two unrelated packages could add conflicting definitions of a method to a standard library type, and the compiler wouldn’t have any way to disambiguate which to use. One package could easily break an unrelated package, which isn’t a great property.
As a result, Rust has some rules around coherence which try to prevent this. There are two main principles:
impl
blocks are not permitted to add implementations for types which overlap. From the earlier section on generics we saw that you can write things like impl<T: Copy> Pair<T>
to add implementations to all types that meet the Copy
trait. Imagine if you also defined impl<T: AddAssign> Pair<T>
— since it’s quite possible for a type T
to implement both Copy
and AddAssign
traits, these two impl
blocks overlap, which creates the potential for ambiguity in the compiler, and hence is not allowed4.impl
block to provide implementations for a trait if both the trait and the type are defined in external units of code. This is to avoid dependency hell, where the compatibility of any given two packages is near-impossible to determine up front, and allow packages to add new implementations for their own types without risking it being a breaking change when mixed with other packages. The precise rules are a little more complicated, but that statement is close enough.One feature that I’ll briefly mention is the notion of associated types — this is rather like making a trait itself generic on another type. We saw an example of this earlier when we referred to the Add
trait as Add<Output = T>
.
A simple example of this from the standard library is the Iterator
trait. This requires that types implementing it have a next()
method which returns the next item — but to define the signature of that method, the type of the item is needed, and this is not known until the implementation is added.
Therefore we use an associated type to represent the type of an item.
pub trait Iterator {
type Item;
fn next(&mut self) -> Option<Self::Item>;
}
When implementing this trait on a type, a concrete type must be provided, as in the example below.
impl Iterator for BucketOfInts {
type Item = i64;
fn next(&mut self) -> Option<Self::Item> {
...
}
}
Note that although this might seem like generics all over again, there is a slightly subtle difference. For a generic type, you can instantiate it multiple times with different types in each case. In this case, however, when implementing Iterator
for BucketOfInts
, we only want one option for Item
— it’s not like it makes sense to define another implementation where Item
has a different type. Since there can only be one definition of the implementation of Iterator
for BucketOfInts
, there’s no change of such overloading.
The Add
example we saw earlier is another common case of this — Rust doesn’t let you overload existing operator definitions, but it does let you define how operators can be applied to your own types by using some traits from the standard library, and Add
is one of these.
As anyone who’s written a decent amount of C or C++ code knows, lifetimes are important. I’d wager that there isn’t such a programmer out there that hasn’t at some point returned a pointer to something that’s on the stack of a function, had it compile successfully and then spent wasted minutes trying to track down the cause of the weird runtime errors that result. Modern compilers in these languages can help with this, but only to catch the more obvious versions of these problems.
Rust programmers must also carefully consider the lifetimes of values they use, since references are so heavily used. In the remainder of this article we’ll look at how to resolve compiler errors around lifetimes, and how to extend the lifetime of a variable.
Some of this might seem a little odd, because other languages don’t require programmers to annotate the lifetime of variables to the same degree, but I’ll try and cover why this is required in Rust as we go along.
Consider this code which defines a later_word()
function that takes two str
references and returns the one that’s later in the dictionary.
1 2 3 4 5 6 7 8 9 10 |
|
At first sight this may look fine, but when we try to compile it we get the following error.
error[E0106]: missing lifetime specifier
--> src/main.rs:1:45
|
1 | fn later_word(first: &str, second: &str) -> &str {
| ---- ---- ^ expected named lifetime parameter
|
= help: this function's return type contains a borrowed value, but the signature
does not say whether it is borrowed from `first` or `second`
This might seem odd at first, but when you puzzle through what the borrow checker is trying to do, it makes more sense. We’re defining a function which takes two parameters, and returns a reference to one of them — but we won’t know until runtime which one. In our simple use of the function above it doesn’t matter too much which one, but in the general case the lifetimes of the two parameters may well be quite different, and that means that the borrow checker cannot determine what the lifetime of the returned value of the function should be. As a result, it cannot perform further checks on whatever the calling code uses this value for, and hence we can’t guarantee we won’t exceed the lifetime of the value.
The compiler could, in principle, reason out that the lifetime of the result should be the shorter of the two lifetimes of the parameters. In practice it needs a little help, and we give it that help by annotating the types with explicit lifetimes — these work quite like generics in their syntax, except we’re specifying lifetimes rather than types. The syntax is a bit quirky, using an apostrophe and a name for the lifetime — let’s see the function above defined with these annotations added.
1 |
|
So here we’re saying that there is some lifetime 'a
for which both parameters first
and second
will be valid for at least that lifetime, and that the return type should be regarded as being valid for that lifetime. As with type constraints, this doesn’t change any lifetimes, it just means that the borrow checker will raise compiler errors on any code which doesn’t meet the constraints.
Now let’s consider methods on a structure which itself uses references. For this example, I’ve written a very over-simplified parser for HTTP headers from a request. Take a look at the code below, which should compile and run — to avoid lots of inefficient string copying, our HttpHeaders
structure maintains a HashMap
of references to string slices within the original request.
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 |
|
You’ll see that on line 3 we’ve had to add a lifetime generic parameter to the HttpHeaders
structure, and on line 4 we’ve had to refer to this when declaring the HashMap
. This is because the HashMap
stores references to external string slices, so the borrow checker needs to know that the lifetime of these will extend at least as far as the HttpHeaders
instance that refers to them.
In the impl
block starting on line 7 you can see that we need to declare these lifetime generics again. However, we don’t use them on line 8 because this is a special case where they be elided — we’ll discuss this more below in the Lifetime Elision section.
Given when we’ve already seen in functions, it shouldn’t come as much of a surprise that these lifetime annotations are also required on structures which hold references. Just as we can make structures generic over times, we can make them generic over lifetimes as well — it’s just that you’re probably a lot less used to that concept simply because other languages don’t have an equivalent.
So far so good. Now let’s mix things up a bit by modifying the code above so that the assignment happens in a function. It’s all the same up to line 20, and then we’ll modify it as follows.
20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
|
If you were to try and compile this modified version, you’ll get the following error.
error[E0515]: cannot return value referencing local variable `http_request`
--> src/main.rs:28:5
|
28 | HttpHeaders::new(http_request.as_str())
| ^^^^^^^^^^^^^^^^^---------------------^
| | |
| | `http_request` is borrowed here
| returns a value referencing data owned by the current function
This makes sense — once http_request
is out of scope, the HashMap
in the HttpHeaders
instance that it’s returning refers to slices of the string that no longer exists, so the borrow checker has saved us from some undefined behaviour that would have occurred had we been allowed to proceed. This is why Rust requires programmers to be a little fastidious with tracking lifetimes — it’s one of the things that makes the language safer.
Continuing the example from the previous section, let’s make one further modification to that get_sample_headers()
function so that instead of constructing a String
, it just uses an str
literal directly.
20 21 22 23 24 25 26 27 28 29 |
|
If you try this, you’ll see that suddenly it compiles again. What gives?! The references are still to the string in http_request
that’s gone out of scope, right?
Well, not quite actually. Because we’re now referring directly to a string literal, Rust assigns this the 'static
lifetime, which is a special lifetime which lasts for the duration of the program’s execution. All string literals have this value because they live within the data section of the binary and hence won’t ever disappear, unlike values on the stack or heap.
This illustrates how the lifetime annotations act like generics — just as the compiler can automatically deduce types sometimes, in this case it’s done the same for the lifetime. Because the value we’ve passed in has a 'static
lifetime, the compiler has substituted that for the 'a
lifetime annotations and hence it hasn’t had any concerns about this value’s lifetime being shorter than any of the references to it.
This is useful in limited situations, but the compiler may sometimes suggest using a 'static
annotation where it’s not appropriate, so as always the programmer must understand what it means and when it’s appropriate (and not appropriate) to use it.
Just to add some spice to the mix, there are some special cases where you’d expect to have to add lifetime annotations like this, but in practice the compiler detects them and figures things out without them. This was something that was added as time went on and people got a little sick of the compilation of adding these annotations for these very common special cases.
There are three rules which define the cases where lifetime annotations can be omitted by the programmer:
&self
or &mut self
, all returned references use that lifetime.Now we can see why we could omit the lifetime annotations when declaring the HttpHeaders::new()
function above — the second of these rules came into play.
That about wraps it up for this article. I haven’t drilled as far as I could have done into traits or lifetimes, but things start to get pretty esoteric as you go further and I hope that I’ve covered a good chunk of the cases that people are likely to run into in practice.
Overall I’m pleased with the balance between power and safety that the Rust developers have managed to achieve, but it is also clear that there’s a fair degree of complexity here which users of the language are going to need to get to grips with pretty quickly if they want to be effective. This is consistent with my growing opinion of the language as being powerful and efficient, but not particularly friendly to less experienced programmers.
It does give me flashbacks a little bit to starting to use templates and inheritance together in C++, when I would have to unpick the most unhelpful compiler error messages I’ve ever seen when I made fairly simple programming errors, like forgetting to make something virtual, or missing out a const
. However, my experience with Rust so far has been that the compiler is extremely helpful and tells you exactly what the problem is every time.
I think this is probably because it’s fussier about having the programmer specify everything, instead of figuring it out from context, which helps it track down exactly where your problem is more quickly. But whatever the reason, I haven’t found getting any of these examples working nearly as frustrating as I did when I was learning C++.
That’s it from me for now, I’ll continue to look at other language features next time — probably the packaging system, which I feel I should get to grips with before too long.
We’re going to assume the array is non-empty for simplicity in this example — if you pass an empty array or slice, you’ll get a panic at runtime with this code. ↩
If you’re wondering why no use
directive for the Copy
trait, it’s sufficiently common that it’s already pulled into scope by default. ↩
We haven’t talked about Rust’s packaging system yet, so for now I’m using “unit of code” as a generic term for a non-specific granularity of code encapsulation. We’ll make this more specific in a future article by looking at packages, crates and modules, and how they impact scope and privacy. ↩
The implementation of specialisation, which I mentioned earlier is in active development, is intended to relax these restrictions whilst keeping things deterministic and comprehensible — but as previously mentioned, things aren’t quite stable in this area yet. ↩