CRTP in Rust

Why CRTP?

The Curiously Recursive Template Pattern (CRTP) is a C++ idiom named in 1995 by Jim Coplien. In typical C++ fashion, this is fancy acronym for a simple concept. The idiom is straightforward to explain when expressed in code:

template<class Self>
class Base {};

class Derived : public Base<Derived> {};

The base class has a template parameter. We pass in the derived class in as this template parameter to the base class. In this way, the base class can depend on the type of the derived class. This allows the base class to do anything it wants to with the dervied class type, which can range from simply referencing the derived class type to calling methods on Derived from Base. Note: You will need to cast this to Derived* in the base class to do this.

Looking at the above definition of CRTP, the most obvious answer to the question Can we use the CRTP idiom in Rust? is No, because Rust does not have inheritance. This answer is unsatisfying and very unhelpful.

A second possible answer is Rust traits already provide Self to refer to the implementer type, I think internalizing this insight is key to understanding why CRTP is unnecessary in Rust. so already know the derived type in Rust for free. This answer is more helpful and begins to answer the question, and more importantly explains why the idiom is unnecessary in Rust.

An even better answer can be formulated by considering what a C++ developer really wants to know: You can think of this is a type of XY problem. The asker is trying to reach for a C++ hammer that doesn't exist in Rust because it is not required. Can I implement X in Rust (for which I would normally need CRTP in C++)? Fortunately, Rust — a language that touts having zero-cost abstractions — does indeed support what CRTP is most often used for.

There are several reasons to use CRTP in C++:

1. To achieve static polymorphism (i.e. polymorphism without virtual)
2. To mix-in behaviors into a class
3. To achieve the Barton–Nackman trick

I demonstrate how to achieve each of these in Rust in the sections below.

Static Polymorphism in Rust

This is probably the most common reason for me to use CRTP when I personally write C++. Often, for performance reasons, I want virtual-free monomorphic code generated from polymorphic source. i.e.: I want zero-cost abstractions. In fewer words, I want static polymorphism.

I find it difficult to explain the value of static polymorphism with toy examples. We will use a practical, real example of static polymorphism where performance is important: A SAX parser for JSON. A SAX parser is a parser that — instead of giving you a DOM or AST of the source document — instead gives you parse events. You can construct a DOM parser from a SAX parser, but the inverse is not true. Thus a SAX parser is almost always preferable. We will not discuss why we would want such a thing, but will just implement it to demonstrate the concept of static polymorphism.

For example, for the below JSON:

{
  "hello": "world",
  "life": 42,
  "list": [1, 2, 3, 4],
}

The parser would emit the following function calls:

StartObject()
Key("hello")
String("world")
Key("life")
Uint(42)
Key("list")
StartArray()
Uint(1)
Uint(2)
Uint(3)
Uint(4)
EndArray()
EndObject()

Dynamic dispatch is the obvious way for a client to provide a handler for the above calls. Unfortunately, this is often insufficiently performant. We want static polymorphism here to avoid the indirect call overhead that dynamic polymorphism would have. An example of a real, production C++ library that does this with CRTP is RapidJSON.

We will now implement this in Rust. Unlike C++ is not entirely true as in C++20 concepts perform a similar role. Unlike C++, a generic argument cannot have arbitrary function calls done to it, because Rust wants to statically check correctness at declaration time rather than template instantation time. We first need to declare the interface our user's type needs to conform to:

pub trait Visitor {
  fn begin_object(&mut self) {}
  fn end_object(&mut self) {}
  fn begin_array(&mut self) {}
  fn end_array(&mut self) {}
  fn key(&mut self, _: &str) {}
  fn visit_string(&mut self, _: &str) {}
  fn visit_u32(&mut self, _: u32) {}
  fn start_array(&mut self) {}
}

The parsing library would then provide an interface such as the below:

pub fn parse<V : Visitor>(input: &str, visitor: V) -> V;

Our users would be able to use the SAX parser to extract values like so: This is a toy example.

struct LifeExtractor {
  life: Optional<u32>,
  read_okay: bool,
}

impl Visitor for LifeExtractor {
  fn key(&mut self, key: &str) {
    if key == "life" {
        self.read_okay = true;
    }
  }
  fn visit_u32(&mut self, value: u32) {
    if self.read_okay {
        self.life = Some(value);
    }
  }
}

fn extract_life(input: &str) -> Option<u32> {
  parse(input, LifeExtractor { life: None, read_okay: false }).life
}

That's about it. Notice an advantage to Rust here: Rust allows one to easily specify default implementations in Visitor! I elided over some implementation details for the sake of brevity, the playground has the full source. You can play with a complete runnable example of the above toy SAX JSON parser on the Rust Playground.

Serde is a popular Rust seralization and deseralization library. It should come as no surprise that Serde's SAX-style interface is similar-ish to the above if you squint hard enough.

One thing to note: Alternatively (and possibly more ergonomic compared to having an extension trait) you can choose to implement this with a default implementation on the Visitor trait. See also the examples in the mixin section below. A C++ developer may wish for for parse to automatically be a member function of LifeExtractor like it would be when using CRTP. The library implementer can do so with an extension trait:

pub trait Parser {
  fn parse(self, input: &str) -> Self;
}

impl<T> Parser for T where T : Visitor {
  fn parse(self, input: &str) -> T {
    parse(input, self)
  }
}

Mixins in Rust

Mixins! The quintessential example in the C++ standard library is std::enable_shared_from_this<T>. It is a class that provides the member function shared_from_this when inherited from. CRTP is required because the return type of shared_from_this is std::shared_ptr<T>; thus, the base class needs to reference the type of the derived class.

ATL's use of CRTP can also be thought of as inheritance injection; e.g. programmers can (and do) inject bugfixes into ATL thanks to its use of CRTP. Another prominent C++ example of this is Microsoft's Active Template Library, which makes heavy use of mixins via CRTP.

Instead of trying to recreate ATL, let us instead consider a much simpler toy example of a mixin that we will implement in both C++ and Rust:

template <class Self>
class GeometryHelper {
public:
  int area() const {
    return self().width() * self().height();
  }

  int perimeter() const {
    return 2 * (self().width() + self().height());
  }

  bool is_degenerate() const {
    return self().width() == 0 || self().height() == 0;
  }

private:
  friend Self;

  GeometryHelper() = default;

  const Self& self() const {
    return *static_cast<Self*>(this);
  }
};

We can insert this mixin into classes like so:

class Square : public GeometryHelper<Square> {
public:
  explicit Square(int width) : m_width(width) {}

  int width() const { return m_width; }
  int height() const { return m_width; }

private:
  int m_width;
};

class Rectangle : public GeometryHelper<Rectangle> {
public:
  Rectangle(int width, int height) : m_width(width), m_height(height) {}

  int width() const { return m_width; }
  int height() const { return m_height; }

private:
  int m_width;
  int m_height;
};

Now it's Rust's turn. We can implement the above straightforwardly in Rust with traits like so:

trait Geometry {
  fn width(&self) -> i32;
  fn height(&self) -> i32;

  fn area(&self) -> i32 {
    self.width() * self.height()
  }

  fn perimeter(&self) -> i32 {
    2 * (self.width() + self.height())
  }

  fn is_degenerate(&self) -> bool {
    self.width() == 0 || self.height() == 0
  }
}

struct Square {
  width: i32,
}

impl Geometry for Square {
  fn width(&self) -> i32 { self.width }
  fn height(&self) -> i32 { self.width }
}

struct Rectangle {
  width: i32,
  height: i32,
}

impl Geometry for Rectangle {
  fn width(&self) -> i32 { self.width }
  fn height(&self) -> i32 { self.height }
}

Observe how default trait implementations naturally provides an overridable way to share functionality between Rust structs. You can play with the above example in the Rust Playground.

An alternative way of implementing the above in Rust is with supertraits, but we won't cover that here.

One thing to note: Rust has a language feature for some common compiler built-in mixins: the #[derive] attribute.

Barton-Nackman trick in Rust

The Barton-Nackman trick is an old C++ idiom from the 90s that uses CRTP to provide in-class friend functions (originally this worked because of friend name injection; later versions of the C++ standard support this via ADL rules).

This idiom is used to supply comparator operator functions. Recently however this has been made redundant by C++20's default comparisons rules and the spaceship operator.

In Rust, the standard library provided methods in std::cmp::PartialEq and std::cmp::PartialOrd have this functionality out of the box. In addition, the #[derive] attribute may be used to automatically implement the traits for you in the trivial case.

Conclusion

Rust has a powerful trait system that is different from C++ templates. Directly porting over C++ template idioms will not result in idiomatic Rust code and would also work against the grain of the language. Hopefully this article was helpful in showing how to do things in Rust that you would've reached for CRTP in C++.

For completeness, I should also note that C++23’s deducing this — similar to Rust's Self — will make most current uses of CRTP in future versions of C++ unnecessary.