C++ Trait Bounds

Sunday, October 16, 2022

High performance generic programming is a killer feature in both Rust and C++. In each language the compiler can generate a concrete implementation of a generic program which results in zero runtime overhead. However, the Rust compiler also allows you to specify the functionality that a concrete type must possess in order to be used in a generic instance. This feature for additional safety is referred to as a trait bound and we can use similar ideas in C++ to achieve the same safety. Consider the following code:

trait Shape {
    fn draw(self);
}

struct Circle;

impl Shape for Circle {
    fn draw(self) {
        ...
    }
}

We have an abstract method Shape::draw. Assume we have a generic function exec_draw which calls the draw function on the passed parameter. Rust requires that a bound be placed on the parameter's generic type by specifying a trait, in this case Shape, which requires all usage of the exec_draw function to occur on concrete types which implement the Shape trait. This trait bound is shown below:

fn exec_draw<T: Shape>(c: T)
{
    T::draw(c);
}

The benefit here is that a different type, Picasso which does not explicitly implement Shape, cannot be passed to exec_draw function without generating a compile time error. This prevents accidental duck typing and it is still a compile time check with zero runtime overhead.

...

struct Picasso;

impl Picasso {
    fn draw(self) {
        ...
    }
}

...

fn main() {
    // Works as expected
    let circle = Circle;
    exec_draw(circle);

    // Generates compiler error "the trait `Shape` is not implemented for `Picasso`"
    let picasso = Picasso;
    exec_draw(picasso);
}

The default behavior in C++ is that the compiler does not provide a similar check. See a similar implementation in C++ below:

class Shape {
public:
    virtual void draw() = 0;
};

class Circle: public Shape {
public:
    void draw() {
        ...
    }
};

class Picasso {
public:
    void draw() {
        ...
    }
};

template<class T>
void exec_draw(T& x) {
    x->draw();
}

int main(int argc, char** argv) {
    // Works as expected
    auto circle = new Circle();
    exec_draw(circle);

    // Also works; C++ compiler don't care
    auto picasso = new Picasso();
    exec_draw(picasso);
}

Maybe allowing duck typing is desirable behavior, but getting the safety that we have in Rust with C++ is fairly straightforward here. One might be inclined to do something like the following:

void exec_draw(Shape* x) {
    x->draw();
}

Although this works, it is not guaranteed to have zero runtime overhead. In this toy program the compiler is able to remove the virtual function call, but as additional shapes are added to the program this optimization will fail and the result will be poorer performance.

To get the same behavior with zero runtime overhead we can revert back to templates and define a class called Can_copy, with a static constraint function containing the behavior that we want to test and a constructor assigning a function pointer to the static function. The class is used only for encapsulation. In this case, the behavior is that T must be a Shape*, or a pointer to a subclass of shape, or the user must have defined conversion to either of the former.

...

template<class T1, class T2> struct Can_copy {
    static void constraints(T1 a, T2 b) { T2 c = a; b = a; }
    Can_copy() { void(*p)(T1,T2) = constraints; }
};

...

template<class T>
void exec_draw(T& x) {
    // This code is interpreted at compile time by the compiler
    Can_copy<T, Shape*>();

    x->draw();
}

int main(int argc, char** argv) {
    // Works as expected
    auto circle = new Circle();
    exec_draw(circle);

    // Generates compiler error "error: incompatible pointer types assigning to 'Shape *' from 'Picasso *'"
    auto picasso = new Picasso();
    exec_draw(picasso);
}

This approach can be straightforwardly extended to be used for arbitrary compile time checks for constraints on generic types.

Note: This example is drawn from Bjarne Stroustrup's C++ Style and Technique FAQ. A key difference is that this approach is discussed there as a technique to generate better compiler errors, rather than prevent accidental duck typing when using generics. Presenting the idea in the context of program safety is in my opinion more important.

Profile picture

iidBlog is written by me, Josh Howard, a software engineer currently working as a Senior Engineering Manager at Starburst Data in Atlanta, Georgia, US.

Josh Howard, Software Engineer