C++ & Rust: Generics and Specialization

At Tangram Vision, we are really excited about Rust and use it daily. The language matches our needs and values to such a degree that we [joined the Rust Foundation](https://foundation.rust-lang.org/news/2022-04-11-member-spotlight-tangram-vision/). In particular, we believe the features of the language and the larger community are necessary to meet the challenges of writing complex systems for robotics, autonomous vehicles (AV), and multi-sensor systems.

C and C++ are the lingua francas of the perception space. Because we’re using Rust instead, we’d like to take a closer look at some of the features we use day-to-day and demonstrate how C++ and Rust differ. Hopefully we can shed some light on how we use these features and understand the trade-offs between these languages.

There are an array of various topics to compare between C++ and Rust. Today, we’ll start with generics. Often colloquially referred to as templates, generics allow us to write code in such a way that we can abstract across a variety of input or output types. This is one common way to produce some level of abstraction across a code-base, but C++ and Rust differ in terms of how they’re implemented. In particular, we’ll look at how each language handles substitution failures, and ways in which we can specialize our code.

# Generics 101: Types as Inputs

Generics in both C++ and Rust are a kind of type that depend on other types as part of their definition. Types can represent one of the following concepts in a programming language:

1. Structures (or Classes)
2. Unions (`enum` in Rust)
3. Functions (or class methods in C++, static functions, procedures, etc.)
4. Primitives (e.g. `char`, `int`, etc.)

Put another way: *all structures, unions, functions, and primitives have a type*.

A **generic** is a way of specifying a placeholder within our type definitions, that can later be *substituted* by a more concrete type definition. For example, in C++ we might write:

```cpp
template<typename T>
struct MyArray {
   T* raw_array;

   size_t size;
];
```

With this, we can say that `MyArray<int>` is a distinct type from `MyArray<double>`. We re-use the generic struct `MyArray`, by giving it a type `T`. This isn’t limited to structs either, as we can write similar code for functions:

```cpp
template<typename T>
T timestwo(T number) {
   return number + number;
}
```

Here, we’ve defined a fairly simplistic function that takes a number in by value and doubles it. Again, `timestwo<int>` is distinct from `timestwo<double>`.

The equivalent in Rust is a bit more complicated than what’s written above and looks like:

```rust
use std::ops::Add;

fn timestwo<T>(number: T) -> <T as Add>::Output
where
   T: Add + Copy,
{
   number + number
}
```

That seems like a lot of extra syntax compared to C++! The main difference is that we have what are called *trait bounds,* which are the part that says `T: Add + Copy`, or in more plain English: *the type `T` must implement the traits `Add` and `Copy`.*

## Traits

To describe the ways in which we can interface with types in our programs, Rust uses [traits](https://doc.rust-lang.org/book/ch10-02-traits.html). A trait is a set of properties, functions, or types that are associated with the type that implements the trait. For example, the `Add` trait is an interface that allows for addition. It is a trait that says that a type has the property of being able to be “added” to some other type. The definition is roughly:

```rust
pub trait Add<Rhs = Self> {
   type Output;

   fn add(self, rhs: Rhs) -> Self::Output;
}
```

This trait has two associated properties:

1. An associated type `Output`, which defines the type of the output of the `add` function.
2. The `add` function, which adds `self` to the right hand side (`rhs`).

Rust uses traits like this to define sub-groups of types when writing generics. In our initial Rust example:

```rust
use std::ops::Add;

fn timestwo<T>(number: T) -> <T as Add>::Output
where
   T: Add + Copy,
{
   number + number
}
```

The `where` clause is effectively stating, “this generic only exists **where** `T` implements the `Add` and `Copy` traits.” Instead of providing a generic for `timestwo` for any type `T`, we limit the definition such that `timestwo` is only valid for `T` that implement `Add` and `Copy`.

‍
💡 To perhaps put this another way, traits are properties of our types, and we can restrict or specialize our generics in Rust to only be valid if types have certain properties. We’ll see why this is important below.

# Type Substitution

We still haven’t really explained why the Rust example is so much more verbose than the C++ example. With a bit of knowledge about traits under our belts, we can now start to understand ***substitution***, mainly

1. What substitution is
2. When substitution happens
3. What kinds of substitution failures are errors

Substitution is the act of filling in the type `T` placeholders in our generics. So when we express `timestwo<int>` in C++, we are *substituting* the parameter `T` with the concrete `int` type. The primary difference that matters in C++ and Rust generics are the second and third parts above: *when* substitution happens and *what* kinds of substitutions fail, or are errors.

## Substitution Ordering & Failures

In C++, substitution happens before the the final type of the function / struct / etc. is type-checked. So if we use our previous example of the `timestwo` function, if we never introduce any substitutions, C++ largely will not care about the template or how it *might* be used. For example if we wrote:

```cpp
#include <iostream>

template<typename T>
T timestwo(T number) {
   return number + number;
}

void main() {
   std::cout << "Hello, world!\n";
}
```

Barring any syntax errors in the template definition itself, C++ doesn’t care that `timestwo` makes no sense for many types. Type checking doesn’t happen until after substitution, so nonsensical types being slotted into our `timestwo` function don’t present a problem.

Interestingly, C++ will sometimes be just fine with substituting some unexpected types. `std::string` and `std::filesystem::path` for example both implement `operator+`, which allow them to be added (technically, `+` is overloaded for “appending” rather than adding). Unfortunately, this means that `timestwo` is valid for these types, even if we want this to only be valid for numeric types.

At times, this can lead to confusion because templates will work for types that weren’t quite intended. As we’ve seen, Rust can avoid this by adding a trait bound such that we only include *numeric* types that can be added. Without some advanced features, we won’t be able to do this in C++! Needless to say, correctly specifying the properties of our code can be hard.

The C++ example only fails when attempting to instantiate `timestwo` with a type that doesn’t support `operator+`. But even if the template is wrong for all types, it only needs to be correct for the types that you use it with. In the above example, we might call:

```cpp
// Okay, because `int`s support operator+
int a = 2;
int b = timestwo(a);

// Doesn't work, because `struct MyStruct` does not support operator+
struct MyStruct {
   int some_integer;
   float some_float;
};

MyStruct c = MyStruct { 0, 3.0 };
// The error doesn't show up at this line, though.
//
// Instead, it will show up inside the definition of `timestwo`,
// because type-checking happens after the generic has had its types
// substituted.
MyStruct d = timestwo(c);
```

So as long as we don’t try to use the template with a type that doesn’t support the properties we need, your C++ compiler won’t complain.

In contrast, Rust handles this the opposite way. Type checking happens before substitution in Rust, which means that our generic has to be valid for any type that can be substituted before we’re allowed to even substitute a type at all.

This is why the Rust example did not look like the following:

```rust
// Fails to compile, as this does not work for every `T`
fn timestwo<T>(number: T) -> T {
   number + number
}

fn main() {
   println!("Hello, world!");
}
```

If we had written the Rust code this way, we cannot guarantee that *every* possible `T` in the above function can be added to itself, because we don’t know that `number + number` is valid for every type. For example, `timestwo<bool>` would not be valid, because `bool` cannot be added to itself in Rust (what would the answer be anyways?). So `timestwo<T>` is invalid, because we cannot verify that the type of the function `timestwo` exists for *every* possible type `T`.

This is why Rust has traits — by specifying trait boundaries on our type `T`, we limit the scope of what properties a generic needs to have. By specifying the `Add` trait within a `where` clause, we are laying out what properties about type `T` are used by `timestwo`. So even if we never try to use `timestwo<String>` in Rust, our definition of `timestwo` without a trait bound can never be valid, because we rely on the property of “a type can be added” to define `timestwo`.

## What are the Trade-Offs?

This underscores the major difference between Rust and C++ generics, namely that Rust has stricter guarantees around correctness. Correctness in the template has to be guaranteed in the template definition, and all traits that we rely on for a given type parameter must be specified in order to do so. C++ on the other hand does not require that a template is correct for every type, only for every type that it is used to instantiate.

It’s a subtle distinction, but it has a lot of implications! For starters, it means that generics in C++ aren’t guaranteed to work for all types. There’s not really a clear way to write a C++ template that, once it compiles successfully, will always be correct for any type. There’s always a possibility of breaking the template with a new type in the future, which is one reason why generics are often seen as a maintenance hazard! The more complex generics are, the more carefully one has to use them (in C++).

💡 Utilizing some advanced or modern features such as SFINAE or C++20’s Concepts, one can sort of approximate this how Rust implements traits, and get closer to guaranteeing that a generic is valid for all types that implement a “concept.”

But this still isn’t quite the same. Trait bounds provide us a way to list what properties of a type need to be guaranteed for a generic to work. With concepts this is also somewhat the case, but the resultant error messages and ergonomics are not quite there.

Rust, in contrast, does guarantee that the generic will continue to build and be well-formed for all acceptable types if it builds. However, we’ve seen a bit of the trade-off here as well — there’s an extra burden on us when writing Rust code to be more explicit in the code, and we need to be able to guarantee that all properties we use are listed in the trait bounds, or it won’t build in the first place. These trait bounds can get long and unwieldy if we need a lot of them, and sometimes what seems obvious in terms of encoding properties of our code into traits ends up very non-obvious in practice.

An additional (if somewhat tangential) point is how substitution errors are presented to the user when compiling code. In C++, errors occur at template instantiation time. In Rust, the module system forces one to import all relevant traits where they are used, so the compiler has all the information needed to type-check a definition before a specific implementation is generated.

In Rust, if you try to use some functionality in generic function that’s not specified in your trait bounds, you’ll get a corresponding error in the body of the generic function. If you try to use a generic with a type that doesn’t meet the generic’s trait bounds, you’ll be told exactly which trait the type in question is missing.

In contrast, C++ will generate errors at template instantiation time. Meaning that missing properties on input types will manifest themselves as errors in the body of the function template. You get errors for each input type in-use that doesn’t work. Moreover since templates are repeated in each translation unit, it’s not uncommon to see the same template substitution error repeated multiple times in your compiler output, ugh!

The difference here is maybe a bit minor if you’re familiar with C++, but the end result is that in Rust you get an error that will definitively tell you if your generic needs a trait bound or if your type doesn’t implement that trait during substitution.

# Specialization

Another key difference between C++ and Rust is the concept of generic **specialization**. Specialization is the process in which we start with a definition in which most types can be slotted into a generic, but allow for more specific definitions for certain types to co-exist alongside the generic. One can think of it as carving out exceptions in our code. The canonical example of this in C++ is `std::vector` — the internal representation and behaviour of `std::vector<T>` is different from the behaviour of `std::vector<bool>`. There is even [explicit documentation for this specialization](https://en.cppreference.com/w/cpp/container/vector_bool)!

The differences between C++ and Rust require us to re-think how we might translate code where specialization is used. As we’ll see, specialization is possible in C++, but makes type checking certain properties of our code difficult. Conversely, Rust does not support specialization. Let’s look at a simple example using a generic `Image` type to see how specialization plays out.

## Specialization in C++

For our C++ implementation, we might construct our generic `Image` type like:

```cpp
template<typename Pixel>
struct Image {
   std::vector<Pixel> pixels;
   
   size_t width;
   size_t height;
};
```

This works for many kinds of pixel types, particularly for mono pixels, RGB pixels, BGRA pixels, etc. But if we wanted to use an interleaved pixel representation (such as a [YUV422-like representation](https://en.wikipedia.org/wiki/YUV#Y%E2%80%B2UV422_to_RGB888_conversion)) where values from multiple pixels are grouped together such that one element of the vector `pixels` doesn’t necessarily represent one pixel, we wouldn’t be able to use the above struct definition. At least, it would make many parts of the implementation much more difficult. Instead, assuming we have some YUV422-like representation `UYVY`, we might specialize it by appending the above code with:

```cpp
struct UYVY {};

template<>
struct Image<UYVY> {
   // U, V, and Y sub-pixels are just single bytes.
   //
   // So we store the whole interleaved buffer without transforming it
   // or changing from YUV422 to YUV444, or RGB8, or something else.
   //
   // Then, when we index into this vector (with a member function or
   // otherwise), we just need to remember the interleaved pattern but
   // _ONLY_ for this specialization.
   std::vector<unsigned char> pixels;

   size_t width;

   size_t height;
}
```

As we can see, adding a specialization in C++ is straightforward. We don’t even have to prove anything to the compiler about our code unless we call it, because type checking comes *after* substitution in C++! C++ provides a set of rules for how “specialized” or “specific” a generic definition is, and then always uses the most specific definition when possible. In the above case, `template<>` is more specific than `template<typename T>`, because it has fewer generic types!

The downside is that for every specialized definition, we need to provide specialized definitions for every class method, member function, etc. on the specialized version. That may seem obvious since the specialized version is an exceptional circumstance to the generic, but it is important to recognize that if there are a lot of specializations that this can be a lot of work!

## Specialization in Rust

Rust [does not at time of writing](https://github.com/rust-lang/rust/issues/31844) have any means to do specialization in the way C++ does. There is no ruleset or syntax for declaring a more “specific” version of a generic.

Returning back to our `Image` example from the previous section, we very clearly cannot specialize for a single type, such as with C++’s `std::vector<bool>` or the `Image<UYVY>` that we wrote. Traits do allow us to group types according to some interface, and we are allowed to have multiple of the same generic with different trait bounds. So if we grouped our pixel types into two groups:

- `NotInterleaved` - RGB, BGRA, mono, etc.
- `Interleaved` - UYVY, YUYV, etc.

We could then write our code as follows:

```rust
pub struct Rgb {
   r: u8,
   g: u8,
   b: u8,
}

pub struct Bgra {
   b: u8,
   g: u8,
   r: u8,
   a: u8,
}

pub struct Uyvy {}

pub trait NotInterleaved {}
impl NotInterleaved for Rgb;
impl NotInterleaved for Bgra;

pub trait Interleaved {}
impl Interleaved for Uyvy;

pub struct Image<Pixel>
where
   Pixel: NotInterleaved,
{
   pixels: Vec<Pixel>,

   width: usize,

   height: usize,
}

pub struct Image<Pixel>
where
   Pixel: Interleaved,
{
   pixels: Vec<u8>,

   width: usize,
   
   height: usize,
}
```

It’s not always ideal to write code this way though! These traits don’t really do much for us, and now every time we want to add some kind of functionality to `Image<P>`, we have to specify whether we’re implementing against `Image<P> where P: Interleaved` or `Image<P> where P: NotInterleaved`. This can very quickly become untenable, and kind of defeats the point of having a generic in the first place (because we have to define everything at least twice, for the not-interleaved and interleaved cases).

Instead, if we know that we’re only trying to support `RGB`, `BGRA`, and `UYVY` pixel types, we might instead abstract our Rust code using traits and generics like follows:

```rust
pub struct ContiguousPixelImage<Pixel> {
   pixels: Vec<Pixel>,

   width: usize,

   height: usize,
}

pub struct UyvyImage {
   pixels: Vec<u8>,

   width: usize,

   height: usize,
}

// Instead of trying to make a template that does everything, we make several
// separate types from a template and group them via a trait instead.
pub trait Image {
   // All image operations / types / functions in here
}

impl<P> Image for ContiguousPixelImage<P> { /* ... */ }

impl Image for UyvyImage { /* ... */ }
```

Instead of specializing our generic to a single type, we just created a new type with a different name. We still have to provide different definitions for RGB / BGRA images from `UyvyImage`, but at least we can treat the two of these types similarly according to a trait called `Image`.

There’s a lot of different ways to express this same problem; regardless, the end result is that Rust’s generics are quite different from C++’s, and the lack of specialization forces us to use our abstractions differently.

# Conclusion

Generics are an incredibly important part of programming when using a statically typed language like C++ or Rust. They enable us to express and abstract code across our types, and are used heavily in anything from storing data in a vector (`std::vector`, Rust’s `Vec`) to implementing our own image, point cloud, or other sensor observation types.

Unlike with C++, where code can grow organically and cause weird interactions with templates over time, the structure of our programs in Rust is either valid or not based on the properties we specify upfront with trait bounds. This is very useful, and is one of the things that we at Tangram Vision love about Rust as a language. There’s no worrying about code in the future, because the compiler has already guaranteed that the type will work if its properties do not change. Likewise, while Rust doesn’t provide rules for specialization, there are ways to utilize traits to abstract and group code. This can often be useful in modeling problems differently, without specialization.

At Tangram Vision we’re invested in Rust. We believe that while sometimes it requires a bit of upfront thinking about our types, the benefits Rust confers are worth the extra effort. If you decide to transition to Rust you’ll be better able to understand the trade-offs between these two languages. Lastly: Interested in what we’re doing and how we work? We are hiring for Rust-related roles today! Check out our [careers page](https://www.tangramvision.com/careers) to apply!

‍