My second cup of Rust
Tags: rust, beginners, learning
Published: 2021-06-06 15:59:06

Last week, I drank [my first cup of Rust](https://blog.frankel.ch/start-rust/1/). I learned concepts that are foreign in the languages I know: [ownership](https://doc.rust-lang.org/book/ch04-01-what-is-ownership.html), [borrowing](https://doc.rust-lang.org/book/ch04-02-references-and-borrowing.html) and [lifetimes](https://doc.rust-lang.org/book/ch10-03-lifetime-syntax.html). 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`.

![Add a sidekick attribute to a Super](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/f1op2tv0yvkjykwqkz64.png)

The implementation seems easy enough.

```rust
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.

```rust
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:

```rust
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](https://doc.rust-lang.org/rust-by-example/std/box.html)

Here's the new code that uses `Box`:

```rust
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!

```rust
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:

```rust
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:

![Add an Alignment attribute to a Super](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ierttnlll73961ta0bu5.png)

It translates into the following:

```rust
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](https://en.wikipedia.org/wiki/Fold_(higher-order_function)). The good news is that `Iter` provides a `fold` function. Let's start with the following code:

```rust
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:
>
> ```rust
> 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](https://doc.rust-lang.org/std/collections/struct.HashMap.html)

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.

```rust
#[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?](https://doc.rust-lang.org/std/marker/trait.Copy.html#whats-the-difference-between-copy-and-clone)

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

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:

```rust
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:

```rust
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:

```rust
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:

{% github ajavageek/start-rust/ %}

**To go further:**

* [The Rust Standard Library](https://doc.rust-lang.org/std/)

_Originally published at [A Java Geek](https://blog.frankel.ch/start-rust/2/) on June 6<sup>th</sup>, 2021_