Runtime Concept Idiom

This post is about runtime polymorphism and, in particular, about what Sean Parent first described as the runtime concept idiom, that was designed to bring runtime polymorphism back to an implementation detail. Let’s consider a classic example to illustrate what is meant by that. Say we have a collection of objects (Circle, Square, etc) that we want to draw the shape of. The common way to tackle this is to perform type erasure via a Shape base class defining a draw method that all objects can override, by deriving from that base class.

What is wrong with this approach? First, our collection does not have value semantics: we are not dealing with a collection of concrete shapes, but with a collection of pointers to a common base class. The base class could expose a virtual clone method that derived classes can override as well, but this brings us to the second flaw of this approach: we force our objects to implement a functionality, here, the draw method, that has nothing to do with them but only with their particular use case.

The runtime concept idiom relies on inheritance and virtual functions like classic runtime polymorphism does, however, this now becomes an implementation detail. In that context, the Shape base class becomes a concept, that can be modeled by objects, such as our Circle, Square, etc, objects. To draw a shape can then be implemented as drawing the underlying model. The following code should help understand the idea:

class Shape {
public:
  template<typename T>
  Shape(T x) : _self(std::make_unique<model<T>>(std::move(x))) {}
  Shape(Shape const& rhs) : _self(rhs._self->_copy()) {}
  Shape(Shape&&) noexcept = default;

  Shape& operator=(Shape const& rhs) {
    Shape tmp(rhs); *this = std::move(tmp); return *this;
  }
  Shape& operator=(Shape&&) noexcept = default;

  friend void draw(Shape const& shape) {
    shape._self->_draw();
  }

private:
  struct concept_t {
    virtual ~concept_t() = default;
    virtual concept_t* _copy() const = 0;
    virtual void _draw() const = 0;
  };
  template<typename T>
  struct model final : concept_t {
    model(T x) : _data(std::move(x)) {}
    concept_t* _copy() const override { return new model(*this); }
    void _draw() const override { draw(_data); }
    T _data;
  };

  std::unique_ptr<concept_t> _self;
};

The Shape class simply holds a unique_ptr to the base concept (this is an implementation detail at this point, could just as well be any other pointer type). The concept exposes a draw method that the model overrides by calling a free function on the underlying implementation type. What that means is that for our objects to be used in this polymorphic context (i.e. as a Shape that we can draw), all we need to do is to provide the proper non-friend non-member draw functions. That is it! Our objects do not need to inherit from a base class: as long as there exists a free function to draw them, they can be used as a Shape. Our collection also now has value semantics, i.e. the copy constructor makes a deep copy (virtual _copy() method). Let’s illustrate a use case with our Circle and Square objects:

class Circle {
public:
  explicit Circle(double radius) : _radius{radius} {}
  Circle(Circle const& rhs) : _radius{rhs._radius} {
    std::cout << "circle copy ctor\n";
  }
  Circle(Circle&&) noexcept = default;
  double radius() const { return _radius; }
  void set_radius(double value) { _radius = value; }
private:
  double _radius;
};

class Square {
public:
  explicit Square(double side) : _side{side} {}
  Square(Square const& rhs) : _side{rhs._side} {
    std::cout << "square copy ctor\n";
  }
  Square(Square&&) noexcept = default;
  double side() const { return _side; }
  void set_side(double value) { _side = value; }
private:
  double _side;
};

void draw(Circle const& circle) {
  std::cout << "Draw a circle with radius of " << circle.radius() << " units\n";
}
void draw(Square const& square) {
  std::cout << "Draw a square with side of " << square.side() << " units\n";
}
void draw(std::vector<Shape> const& shapes) {
  for (auto const& shape : shapes)
    draw(shape);
}

We simply provided two free functions to draw our objects, as well as another one to draw our collection:

int main() {
  auto shapes = std::vector<Shape>{}; shapes.reserve(10);
  shapes.emplace_back(Square{1});
  shapes.emplace_back(Circle{1});
  shapes.emplace_back(shapes.back());
  shapes.emplace_back(shapes);
  for (auto const& shape : shapes) {
    draw(shape);
  }
  return 0;
}

Output:
circle copy ctor
square copy ctor
circle copy ctor
circle copy ctor
Draw a square with side of 1 units
Draw a circle with radius of 1 units
Draw a circle with radius of 1 units
Draw a square with side of 1 units
Draw a circle with radius of 1 units
Draw a circle with radius of 1 units

Here we get 4 copies as the third entry in our collection is a copy of the second, and the fourth entry is a copy of the whole collection of three shapes. We do not get additional copies from the constructor sink argument (taken by copy then moved into place) because we declared default move semantics in our shape classes.

This is the basic implementation of the runtime concept idiom. It can still be optimized quite a bit for performance. One improvement is to get rid of the copies. A simple way to do that is to replace the unique_ptr with a shared_ptr. However, as Sean Parent would stress, a shared_ptr is just as good as a global variable when it comes to value semantics. But as long as we consider an immutable collection, we can simply declare the concept held by the Drawable class as const (i.e. std::unique_ptr<concept_t> replaced by std::shared_ptr<concept_t const>), and get rid of our deep copies (using default copy/move semantics). This effectively restores value semantics, as a shared_ptr to a const object looses its global behavior.

class Shape {
public:
  template<typename T>
  Shape(T x) : _self(std::make_shared<model<T>>(std::move(x))) {}
  Shape(Shape const&) = default;
  Shape(Shape&&) noexcept = default;
  Shape& operator=(Shape const&) = default;
  Shape& operator=(Shape&&) noexcept = default;

  friend void draw(const Shape& shape) {
    shape._self->_draw();
  }

private:
  struct concept_t {
    virtual ~concept_t() = default;
    virtual void _draw() const = 0;
  };
  template<typename T>
  struct model final : concept_t {
    model(T x) : _data(std::move(x)) {}
    void _draw() const override { draw(_data); }
    T _data;
  };

  std::shared_ptr<concept_t const> _self;
};

If we need our collection to be mutable, then we can implement a simple copy-on-write mechanism using the shared count of the shared_ptr. This brings us back to the original implementation with a unique_ptr to a non-const concept, but without the copies! Let’s illustrate this by extending the shape concept so that shapes can be scaled as well as drawn. All we need is to provide two free scale functions for our objects:

class Shape {
public:
  template<typename T>
  Shape(T x) : _self(std::make_shared<model<T>>(std::move(x))) {}
  Shape(Shape const&) = default;
  Shape(Shape&&) noexcept = default;
  Shape& operator=(Shape const&) = default;
  Shape& operator=(Shape&&) noexcept = default;

  friend void draw(const Shape& shape) {
    shape._self->_draw();
  }
  friend void scale(Shape& shape, double value) {
    if (shape._self.use_count() > 1) {
      shape._self.reset(shape._self->_copy());
    }
    shape._self->_scale(value);
  }

private:
  struct concept_t {
    virtual ~concept_t() = default;
    virtual concept_t* _copy() const = 0;
    virtual void _draw() const = 0;
    virtual void _scale(double) = 0;
  };
  template<typename T>
  struct model final : concept_t {
    model(T x) : _data(std::move(x)) {}
    concept_t* _copy() const override { return new model(*this); }
    void _draw() const override { draw(_data); }
    void _scale(double value) override { scale(_data, value); }
    T _data;
  };

  std::shared_ptr<concept_t> _self;
};

void scale(Circle& circle, double value) {
  circle.set_radius(value * circle.radius());
}
void scale(Square& square, double value) {
  square.set_side(value * square.side());
}

And here is a simple use case example:

int main() {
  auto shapes = std::vector<Shape>{}; shapes.reserve(10);
  shapes.emplace_back(Square{1});
  shapes.emplace_back(Circle{1});
  shapes.emplace_back(shapes.back());
  scale(shapes[0], 2);
  scale(shapes[1], 2);
  for (auto const& shape : shapes) {
    draw(shape);
  }
  return 0;
}

Output:
circle copy ctor
Draw a square with side of 2 units
Draw a circle with radius of 2 units
Draw a circle with radius of 1 units

where the only copy occurs when we scale the second entry of the collection that shares its data with the third entry.

Another possible improvement to the basic version of the idiom is to add small buffer optimization by implementing local storage for small objects, and thus avoid heap allocations.