My second cup of Rust

Last 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 type T. When a box goes out of scope, its destructor is called, the inner object is destroyed, and the memory on the heap is freed.

-- Rust By Example - Box, stack and heap

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>
    }
}

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>
    }
}

1. Iterate over the vector's items
2. Keep only those who have a sidekick
3. 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 Super in two groups:

• One contains the sidekicks of heroes, Super with the Alignment.GOOD; the other those of villains, with Alignment.EVIL
• The Map contains two keys, Alignment.GOOD and Alignment.EVIL
• The values are respectively the set of heroes' sidekicks and the set of villains'
• No null values are accepted in the values set
• The absence of a sidekick for a Super shouldn'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>
        })
}

1. Create the result hash map
2. Set the keys and default values
3. Filter out Super with no sidekick
4. Fold!
5. Get the vector corresponding to the sidekick's alignment
6. Add the sidekick to the previous vector
7. 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 Eq and Hash traits, 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.

-- Struct std::collections::HashMap1.0.0

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.

Clone is a supertrait of Copy, so everything which is Copy must also implement Clone.

-- What’s the difference between Copy and Clone?

#[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:

Considering the above, we need to:

1. Get the Super
2. Get the sidekick attribute wrapped in an Option, which itself is wrapped in a Box. Reminder: the previous step filtered out any Super who doesn't have a sidekick.
3. 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:

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:

• The Rust Standard Library

Originally published at A Java Geek on June 6^th, 2021