Nicolas FrรคnkelLast week, I drank my first cup of Rust. I learned concepts that are foreign in the languages I know: ownership, borrowing and lifetimes. This week I want to drink the second cup and see where it leads me.
Self-referencing types
It's time to implement another exercise from the initial exam:
Given a collection of
Super, return the sub-collection of those who have a sidekick.
We need to change the model to add a sidekick attribute of type Super.
The implementation seems easy enough.
pub struct Super<'a> {
pub super_name: &'a str,
pub real_name: &'a str,
pub power: u16,
pub sidekick: Option<Super<'a>>,
}
Unfortunately, the above code doesn't compile:
error[E0072]: recursive type `Super` has infinite size
--> src/model.rs:2:1
|
2 | pub struct Super<'a> {
| ^^^^^^^^^^^^^^^^^^^^ recursive type has infinite size
...
6 | pub sidekick: Option<Super<'a>>,
| ----------------- recursive without indirection
|
help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to make `Super` representable
|
6 | pub sidekick: Box<Option<Super<'a>>>,
|
It seems that in Rust, a type cannot reference itself. Let's follow the compiler's suggestion. An "easy" fix is to use a reference instead of a type.
pub struct Super<'a> {
pub super_name: &'a str,
pub real_name: &'a str,
pub power: u16,
pub sidekick: &'a Option<Super<'a>>,
}
While the type compiles, the tests don't:
error[E0515]: cannot return value referencing temporary value
--> src/tests/samples.rs:5:5
|
5 | / Super {
6 | | super_name: "Batman",
7 | | real_name: "Bruce Wayne",
8 | | power: 50,
9 | | sidekick: &Some(robin()),
| | ------------- temporary value created here
10 | | }
| |_____^ returns a value referencing data owned by the current function
Back to square one. The compiler also hinted at using Box.
All values in Rust are stack allocated by default. Values can be boxed (allocated on the heap) by creating a
Box<T>. A box is a smart pointer to a heap allocated value of typeT. When a box goes out of scope, its destructor is called, the inner object is destroyed, and the memory on the heap is freed.
Here's the new code that uses Box:
pub struct Super<'a> {
pub super_name: &'a str,
pub real_name: &'a str,
pub power: u16,
pub sidekick: Box<Option<Super<'a>>>,
}
With it, everything compiles, including the test samples!
pub(in crate::tests) fn batman<'a>() -> Super<'a> {
Super {
super_name: "Batman",
real_name: "Bruce Wayne",
power: 50,
sidekick: Box::from(Some(robin())), <1>
}
}
- To "box" a variable, use the
Box.from()function
Finally, the solution is straightforward:
pub mod j {
use crate::model::Super;
pub fn find_supers_with_sidekicks<'a>(supers: &'a Vec<Super<'a>>) -> Vec<&Super<'a>> {
supers
.iter() <1>
.filter(|&s| s.sidekick.is_some()) <2>
.collect() <3>
}
}
- Iterate over the vector's items
- Keep only those who have a sidekick
- Collect the remaining items
Testing the solution doesn't bring new insights into the language.
Traits, traits, traits everywhere!
The subsequent exercise reads like this:
Group the sidekicks of
Superin two groups:
- One contains the sidekicks of heroes,
Superwith theAlignment.GOOD; the other those of villains, withAlignment.EVIL- The
Mapcontains two keys,Alignment.GOODandAlignment.EVIL- The values are respectively the set of heroes' sidekicks and the set of villains'
- No
nullvalues are accepted in the values set- The absence of a sidekick for a
Supershouldn't throw an exception at runtime
Alignment seems like a good candidate for an enum type. Fortunately, Rust does indeed offer enums. We need to update the model accordingly:
It translates into the following:
pub struct Super<'a> {
pub super_name: &'a str,
pub real_name: &'a str,
pub power: u16,
pub sidekick: Box<Option<Super<'a>>>,
pub alignment: Alignment,
}
pub enum Alignment {
Good, Neutral, Evil
}
The logic itself is a fold. The good news is that Iter provides a fold function. Let's start with the following code:
pub fn group_sidekicks_by_alignment<'a>(supers: &'a Vec<Super<'a>>) -> HashMap<Alignment, Vec<&'a Super<'a>>> {
let mut map = HashMap::new(); <1>
map.insert(Good, Vec::new()); <2>
map.insert(Evil, Vec::new()); <2>
supers
.iter()
.filter(|&s| s.sidekick.is_some()) <3>
.fold(map, |mut map, s| { <4>
let value = map.entry(s.alignment).or_default(); <5>
value.push(&s.sidekick.unwrap()); <6>
map <7>
})
}
- Create the result hash map
- Set the keys and default values
- Filter out
Superwith no sidekick - Fold!
- Get the vector corresponding to the sidekick's alignment
- Add the sidekick to the previous vector
- Don't forget to return the map
As expected, it fails:
error[E0277]: the trait bound `model::Alignment: Eq` is not satisfied
--> src/solutions.rs:29:17
|
29 | map.insert(Good, Vec::new());
| ^^^^^^ the trait `Eq` is not implemented for `model::Alignment`
The keys of a HashMap need to be compared.
From the documentation:
It is required that the keys implement the
EqandHashtraits, although this can frequently be achieved by using#[derive(PartialEq, Eq, Hash)]. If you implement these yourself, it is important that the following property holds:k1 == k2 -> hash(k1) == hash(k2)In other words, if two keys are equal, their hashes must be equal.
While that makes sense, I'd expect enums to implement the Eq and Hash traits by default. That's not the case. Let's add them explicitly.
#[derive(Debug, PartialEq, Eq, Hash)]
pub enum Alignment {
Good, Evil,
}
The next compile error is the following:
error[E0507]: cannot move out of `s.alignment` which is behind a shared reference
--> src/solutions.rs:35:39
|
35 | let value = map.entry(s.alignment).or_default();
| ^^^^^^^^^^^ move occurs because `s.alignment` has type `model::Alignment`, which does not implement the `Copy` trait
It's easy enough to add the Copy trait to Alignment. In all honesty, I don't understand why Rust considers it a move. You also need to implement Clone.
Cloneis a supertrait ofCopy, so everything which isCopymust also implementClone.
#[derive(Debug, PartialEq, Eq, Hash, Copy, Clone)]
pub enum Alignment {
Good, Evil,
}
Moving types around
The next error is:
error[E0507]: cannot move out of `*s.sidekick` which is behind a shared reference
--> src/solutions.rs:36:29
|
36 | value.push(&s.sidekick.unwrap());
| ^^^^^^^^^^
| |
| move occurs because `*s.sidekick` has type `Option<Super<'_>>`, which does not implement the `Copy` trait
| help: consider borrowing the `Option`'s content: `s.sidekick.as_ref()`
This error is a bit harder to solve directly. Let's consider the types involved:
| Variable | Type |
|---|---|
s |
&Super |
sidekick |
Box<Option<Super>> |
value |
Vec<&Super> |
Considering the above, we need to:
- Get the
Super - Get the
sidekickattribute wrapped in anOption, which itself is wrapped in aBox. Reminder: the previous step filtered out anySuperwho doesn't have a sidekick. - Put a reference to the sidekick in the
value.
Here's a (the?) solution:
value.push((*s.sidekick).as_ref().unwrap());
Let's decompose into steps to understand better what happens:
| Step | Expression | Type |
|---|---|---|
| 1 | s.sidekick |
Box<Option<Super>> |
| 2 | *s.sidekick |
Option<Super> |
| 3 | (*s.sidekick).as_ref() |
Option<&Super> |
| 4 | (*s.sidekick).as_ref().unwrap() |
&Super |
Nitpick: create a Map in a functional way
At this point, everything compiles (and runs). Yet, I dislike the way I create the HashMap. It involves mutability:
let mut map = HashMap::new();
map.insert(Good, Vec::new());
map.insert(Evil, Vec::new());
I favor a more functional immutable way. Here it is:
let map = [Good, Evil]
.iter()
.cloned()
.map(|alignment| (alignment, Vec::new()))
.collect();
There's probably a way to "zip" both the Alignment map and the Super vector, but I've to admit that I find zipping less readable.
Conclusion
This week, I drank the second cup of Rust, and I survived. This step felt less foreign than the week before: it's a good sign. Stay tuned for other posts on my Rust learning journey!
The complete source code for this post can be found on Github:
To go further:
Originally published at A Java Geek on June 6th, 2021
