Rust - Generic code in Rust

Now that we have an IdManager that works reasonably well and does much of what we require of it we can look at how to make it a bit more flexible.

At present the IdManager can only provide Ids that are BYTE sized. I’d like to make it a generic type so that we can specify the data type to used for the Id that is provided.

Generic code in Rust can look a little similar to generic code in C++, they both make extensive use of angle brackets, however Rust generics are much more precise; though C++20 has constraints and concepts which do a similar thing to Rust Trait Bounds, but more on Traits later… Our first attempt at generic code in Rust might look something like this, if we start with making just the Interval generic:

#[derive(PartialOrd, Eq, PartialEq, Clone)]
pub struct Interval<T> {
    lower: T,
    upper: T,
}

Now, rather than being tied to a u8 we can create intervals that use other types for the upper and lower elements. The <T> syntax cascades through the implementation and replaces all of the previous occurrences of u8:

impl<T> Interval<T> {
    pub fn new(lower: T, upper: T) -> Self {
        if upper < lower {
            panic!("upper must be >= lower");
        }

        Interval { lower, upper }
    }

    pub fn new_single_value_interval(value: T) -> Self {
        Interval {
            lower: value,
            upper: value,
        }
    }

    pub fn lower(&self) -> T {
        self.lower
    }

    pub fn upper(&self) -> T {
        self.upper
    }

    fn dump(&self) -> String {
        format!("{}", self)
    }

    pub fn contains_value(&self, value: T) -> bool {
        value >= self.lower && value <= self.upper
    }

    pub fn overlaps(&self, value: &Self) -> bool {
        value.upper >= self.lower && value.lower <= self.upper
    }

    pub fn extends_lower(&self, value: &Self) -> bool {
        if value.upper == T::MAX {
            return false;
        }

        let next_value = value.upper + 1;

        next_value == self.lower
    }

    pub fn extends_upper(&self, value: &Self) -> bool {
        if value.lower == T::MIN {
            return false;
        }

        let next_value = value.lower - 1;

        next_value == self.upper
    }
}

error[E0277]: can't compare `T` with `T`
   --> src\interval.rs:77:9
    |
77  | impl<T> Ord for Interval<T> {
    |         ^^^ no implementation for `T < T` and `T > T`
    |
note: required for `interval::Interval<T>` to implement `PartialOrd`
   --> src\interval.rs:4:10
    |
4   | #[derive(PartialOrd, Eq, PartialEq, Clone)]
    |          ^^^^^^^^^^
note: required by a bound in `Ord`
   --> C:\Users\lenho\.rustup\toolchains\stable-x86_64-pc-windows-msvc\lib/rustlib/src/rust\library\core\src\cmp.rs:772:21
    |
772 | pub trait Ord: Eq + PartialOrd<Self> {
    |                     ^^^^^^^^^^^^^^^^ required by this bound in `Ord`
    = note: this error originates in the derive macro `PartialOrd` (in Nightly builds, run with -Z macro-backtrace for more info)
help: consider restricting type parameter `T`
    |
77  | impl<T: std::cmp::PartialOrd> Ord for Interval<T> {

This wasn’t quite as clear to me as some of the previous compiler errors, but all the talk of things being “required by a bound” led me in the right direction. The problem here is that we require T to be able to do some things to be acceptable for use in an Interval but we don’t tell the compiler what these things are, so it doesn’t know that everything that we accept as a T will conform.

What the generic code for Interval needs is a trait to document and restrict the kinds of types that the compiler allows us to use. Rather than saying that we can create an Interval that can use anything as T, we specify what is required of the type that we can use. Our first attempt at this might look something like this, as the compiler error said we need Ord we could change the code to make sure that the compiler knows that we know that T must implement Ord:

#[derive(PartialOrd, Eq, PartialEq, Clone)]
pub struct Interval<T: Ord> {
    lower: T,
    upper: T,
}

impl<T: Ord> Interval<T> {
    pub fn new(lower: T, upper: T) -> Self {

However, Ord isn’t the only thing we need as the compiler is keen to tell us, next on the list is MAX… Since we need to duplicate the traits that bind the generic type at every point where we use the generic type it’s easier and cleaner to create our own trait that specifies the other things that we need and then just use our own trait wherever we need to specify the traits that bind the type we need. Defining the trait is as easy as this code, in id_type.rs:

pub trait IdType where Self: Ord
{

}

impl IdType for u8 {}

Once we’ve done this, and used it in place of Ord to specify the trait bounds for T the error message is still the same, but we can make the changes in one place from now on rather than everywhere. So, we might fix that MAX issue and then also provide MIN which is also required…

pub trait IdType where Self: Ord
{
     const MAX: Self;
     const MIN: Self;
}

impl IdType for u8 {
    const MAX: u8 = u8::MAX;
    const MIN: u8 = u8::MIN;
}

Rather than typing out the boilerplate code required to implement our trait for each type that we want to support we can use macro_rules! to implement the trait for each type that we support, so we end up with something like this:

pub trait IdType where Self: Ord
{
     const MAX: Self;
     const MIN: Self;
}

macro_rules! id_type_trait_impl {
    ($name:ident for $($t:ty)*) => ($(
    impl $name for $t {
        const MAX : $t = <$t>::MAX;
        const MIN : $t = <$t>::MIN;
    }
    )*)
}

id_type_trait_impl!(IdType for u8 u16 u32 u64 u128 usize);

The macro is is expanded for each of the types we provide and now our Interval can be created using any of them.

error[E0369]: cannot add `{integer}` to `T`
  --> src\interval.rs:55:38
   |
55 |         let next_value = value.upper + 1;
   |                          ----------- ^ - {integer}
   |                          |
   |                          T
   |
help: consider further restricting this bound
   |
14 | impl<T: IdType + std::ops::Add<i32>> Interval<T> {
   |                ++++++++++++++++++++

Once again the error message helps, we’ll add to our IdType requirements.

pub trait IdType where Self: Ord + std::ops::Add<i32, Output=Self>
{

error[E0277]: cannot add `i32` to `u8`
  --> src\id_type.rs:11:10
   |
11 |     impl $name for $t {
   |          ^ no implementation for `u8 + i32`
...
18 | id_type_trait_impl!(IdType for u8 u16 u32 u64 u128 usize);
   | --------------------------------------------------------- in this macro invocation
...

Switching to std::ops::Add<Self, Output=Self> works, we can add a u8 to our u8 but now we need to add std::marker::Sized which tells the compiler that the type, T, is restricted to being a type which has a constant size known at compile time… And it goes on…

error[E0308]: mismatched types
  --> src\interval.rs:55:40
   |
14 | impl<T: IdType> Interval<T> {
   |      - this type parameter
...
55 |         let next_value = value.upper + 1;
   |                                        ^ expected type parameter `T`, found integer
   |
   = note: expected type parameter `T`
                        found type `{integer}`

This one had me stumped for some time. Why can’t I add an integer literal 1 to a generic type which supports std::ops::Add<Self, Output=Self>. In C++ we could resort to a cast if we had to, but the compiler would automatically allow this kind of thing. Eventually I found the correct incantation to type into Google and was rewarded with this. I need One::one() this leaves with me an IdType that looks like this:

pub trait IdType where Self: Ord + std::ops::Add<Self, Output=Self> + std::ops::Sub<Self, Output=Self> + Sized + num::One + std::fmt::Display + Copy
{
     const MAX: Self;
     const MIN: Self;
}

macro_rules! id_type_trait_impl {
    ($name:ident for $($t:ty)*) => ($(
    impl $name for $t {
        const MAX : $t = <$t>::MAX;
        const MIN : $t = <$t>::MIN;
    }
    )*)
}

id_type_trait_impl!(IdType for u8 u16 u32 u64 u128 usize);

and code that uses it, that looks like this:

    pub fn extends_lower(&self, value: &Self) -> bool {
        if value.upper == T::MAX {
            return false;
        }

        let next_value = value.upper + One::one();

        next_value == self.lower
    }

From here on it’s simply a case of bubbling the changes up through the other structs until we can do this

extern crate idmanager;

use idmanager::IdManager;

pub fn main() {
    let manager = IdManager::<u8>::new();

    assert_eq!(manager.dump(), "[0,255]");

    {
        let id = manager.allocate_id();

        let expected_id : u8 = 0;

        assert_eq!(id.value(), &expected_id);

        assert_eq!(manager.dump(), "[1,255]");
    }

    assert_eq!(manager.dump(), "[0,255]");
}

As with much of the stuff in the earlier stages I’ve pretty much just bumbled along using the compiler errors and Google as a guide to what to read in the various Rust docs. It’s not a pretty way of learning when you make it public like this but it works for me. I have something that seems to do what I want it to do, it may not be pretty or right but it is a starting point for future work that, hopefully, can be a little better. Each step helps move me nearer to my goal (even if it initially moves me away from it). So, feel free to join in and tell me how I could do all of this far better, or in a far more “Rust-like” manner.