Alexander Nasonov's shared items

Tuesday, June 20, 2006

A Little Detail

A Little Detail

Alexander Nasonov


Some time ago I wrote a simple mixin class template. A week later I found a little problem with it. Although I found a solution in a second I decided to analyse it more deeply. It’s worth analysing further because it concerns some fundamental features of C++.

Here is the problematic code:

template<class T>
struct Mixin : T {
 ~Mixin();
};

I guess I know your feelings. The class template looks like an example taken from a C++ book. You might have been taught with code like this. Your feelings about it most likely are based on unchallenged assumptions about simple C++ language constructs. Despite its basic nature the code has one little problem.

Why does this code look nice at first glance? Well, if it was an ordinary class you could just compile it and see that everything is fine. But the “just compile it” idea doesn’t work in the case of class templates. Actually, writing the code is only half the job. The second half is instantiating the template. This will be done by the user unless you think of all possible cases and instantiate them in your tests.

This is a different way of thinking. If you deal with templates you should imagine how different instantiations could be compiled. You can tell me “Hey, what’s the problem, I can write tests and instantiate the template there”. Yes, you can. But first you have to find the right classes for instantiations. As an example, can you find an instantiation of Mixin<X> that breaks the code above?

Don’t think too much, I have an answer. Here it is:

struct X {
 virtual ~X() throw();
};

Once the right class is found you can try to compile it. My compiler (g++ 3.2.2) complains:

1.cpp: In instantiation of 'Mixin<X>':
1.cpp:12: instantiated from here
1.cpp:3: looser throw specifier for 'void Mixin<T>::Mixin() [with T = X]'
1.cpp:7: overriding 'virtual X::~X() throw ()'

According to our best friend, the C++ standard [ISO], paragraph 15.4, bullet 3:

If a virtual function has an exception-specification, all declarations, including the definition, of any function that overrides that virtual function in any derived class shall only allow exceptions that are allowed by the exception-specification of the base class virtual function.

None is allowed in a destructor of base class X. Therefore, none should be allowed in a destructor of the derived class Mixin<X>:

template<class T>

struct Mixin : T {
 ~Mixin() throw();
};

Well, we found a quick solution to the problem. Does it have some drawbacks? Can it break other instantiations? For example, what if T’s destructor may occasionally throw? Mixin<X> has an empty exception specification list, therefore, std::unexpected will be called. This function will call std::terminate and program execution will be aborted. This is definitely not what a user wants.

Luckily, many C++ gurus recommend not throwing exceptions in the destructor at all. It’s enough to mention in the documentation of Mixin that the destructor of T must meet the Nothrow requirement.

It seems that the problem is solved. Indeed, if you’re a bug hunter who has just ended up with code like that above you can stop reading here. I’d rather analyze it a little bit more.

What is annoying me in a destructor with an empty exception specification is the fact that a compiler may put the destructor’s code into a try-catch block. It protects your application against “exception leaks”. The try-catch block can be omitted only if the destructor’s body is available and the compiler can deduce that the destructor never throws. Otherwise, unnecessary try-catch blocks make the code bigger and execution slower.

Another inconvenience of the code was suggested by Phil Bass while reviewing this article. His concern is a design flaw rather than implementation details. Phil suggested that, if Mixin is part of a general-purpose library, it would be great if Mixin were to follow a project-specific exception specification policy.

There are two major exception specification policies used in destructors:

  • No exception specification at all

  • Empty exception specification

Probably, the first policy is used more widely than the second. I would say both are used in C++ projects. For example, the C++ standard library uses both.

Needless to say, a Mixin<T> destructor that is neutral to the exception specification policy of T is preferred rather than a destructor that forces using either choice.

I recommend that you stop reading for a moment and try to find a best-of-all-worlds solution. A solution that is free from the limitation of the first version of Mixin and that doesn’t dictate a particular exception specification policy.

Although you have little freedom in defining the destructor the solution may surprise you. It is no destructor at all, that is, an implicitly defined destructor:

template<class T>

struct Mixin : T {
};

Why is this better? To explain why, let me refer you to [1], paragraph 15.4, bullet 13. Apart from an explanation of our case it contains an example with multiple inheritance, which we’ll analyze later. In my informal interpretation, an implicitly defined destructor “inherits” its exception specification from the base destructor. Whatever exception specification T’s destructor has so has an implicitly defined destructor of Mixin<T>. Perfect, exactly what we need!

You may ask how to keep it implicitly defined in real class templates. I recommend that you use RAII wrappers, smart pointers, C++ strings and containers wherever you can. This reduces the need for explicitly defined destructors to very unusual cases.

More complexity

Now it’s time to solve the problem I faced. It’s almost the same as our original problem with one difference – Mixin has an additional base:

struct Base {
 // ...
};

template<class T>

struct Mixin : Base, T {
 // ...
};

It’s clear that we can always use a nothrow destructor in Mixin. I’d like you to analyze the case of an implicitly defined destructor. Just remember that, on the one hand, an implicitly defined destructor inherits exception specifications from all its bases, and on the other hand, if any of the base destructors is virtual, ~Mixin() can’t have a less restrictive exception specification. The analysis is a kind of combinatorial puzzle. You can combine the virtuality and exception specifications of all the destructors. Fortunately, there are only a few combinations.

The first case is a non-virtual destructor ~Base(). The analysis shows that the destructor of Base has to have an empty exception specification in order to define ~Mixin() implicitly.

struct Base {
 ~Base() throw();
};

template<class T>

struct Mixin : Base, T {
};

Although this solution dictates the exception specification policy of the Base destructor, it’s still of interest because the resulting Mixin class template is neutral to the user’s exception specification policies.

The second case doesn’t have a solution. If Base’s destructor is virtual we can always find a type T that breaks the compilation regardless of the exception specification of ~Base().

This was my case. I could take the destructor’s virtuality out of the base into another class responsible for polymorphic cloning and destruction (let’s say, storage management). Although it would better fit the one class, one responsibility principle I decided to use a quick fix solution:

struct Base {
 virtual ~Base();
};

template<class T>

struct Mixin : Base, T {
 ~Mixin() throw();
};

Conclusion

I’d like to draw two conclusions. First, a summary of what has been done.

Mixin classes often come with general-purpose libraries or libraries that make no assumptions about the projects that will use them. It’s important to follow the project’s rules and policies even when a set of projects is unknown to the library author. In this article I showed how to solve one particular problem with respect to possible uses of your code.

The second conclusion is rather philosophical. Although you can rarely find code simpler than that discussed in this article it’s worth analyzing it. I dare say there is no such thing as a little detail in C++. Everything is important in the C++ world. If you find an interesting note on a C++ feature or some side effect, try to play with it. Many C++ tricks and modern techniques were discovered this way. Keep trying! Together we’ll make a better language.

Reference

[ISO] ISO/IEC 14882

Better Encapsulation for the Curiously Recurring Template Pattern

Overload 70: December 2005

Better Encapsulation for the Curiously Recurring Template Pattern

Alexander Nasonov


C++ has a long, outstanding history of tricks and idioms. One of the oldest is the curiously recurring template pattern (CRTP) identified by James Coplien in 1995 [Coplien]. Since then, CRTP has been popularized and is used in many libraries, particularly in Boost [Boost]. For example, you can find it in Boost.Iterator, Boost.Python or in Boost.Serialization libraries.

In this article I assume that a reader is already familiar with CRTP. If you would like to refresh your memory, I would recommend reading chapter 17 in [Vandevoorde-]. This chapter is available for free on www.informit.com.

If you look at the curiously recurring template pattern from an OO perspective you’ll notice that it shares common properties with OO frameworks (e.g. Microsoft Foundation Classes) where base class member functions call virtual functions implemented in derived classes. The following code snippet demonstrates OO framework style in its simplest form:

// Library code
class Base
{
  public:
    virtual ~Base();
    int foo() { return this->do_foo(); }

  protected:
    virtual int do_foo() = 0;
};

Here, Base::foo calls virtual function do_foo, which is declared as a pure virtual function in Base and, therefore, it must be implemented in derived classes. Indeed, a body of do_foo appears in class Derived:

// User code
class Derived : public Base
{
  private:
    virtual int do_foo() { return 0; }
};

What is interesting here, is that an access specifier of do_foo has been changed from protected to private. It’s perfectly legal in C++ and it takes a second to type one simple word. What is more, it’s done intentionally to emphasize that do_foo isn’t for public use. (A user may go further and hide the whole Derived class if she thinks it’s worth it.)

The moral of the story is that a user should be able to hide implementation details of the class easily.

Now let us assume that restrictions imposed by virtual functions are not affordable and the framework author decided to apply CRTP:

// Library code
template<class DerivedT>

class Base
{
  public:
    DerivedT& derived() {
       return static_cast<DerivedT&>(*this); }
    int foo() {
       return this->derived().do_foo(); }
};
// User code
class Derived : public Base<Derived>
{
  public:
    int do_foo() { return 0; }
};

Although do_foo is an implementation detail, it’s accessible from everywhere. Why not make it private or protected? You’ll find an answer inside function foo. As you see, the function calls Derived::do_foo. In other words, base class calls a function defined in a derived class directly.

Now, let’s find an easiest way for a user to hide implementation details of Derived. It should be very easy; otherwise, users won’t use it. It can be a bit trickier for the author of Base but it still should be easy to follow.

The most obvious way of achieving this is to establish a friendship between Base and Derived:

// User code
class Derived : public Base<Derived>

{
  private:
    friend class Base<Derived>;
    int do_foo() { return 0; }
};

This solution is not perfect for one simple reason: the friend declaration is proportional to the number of template parameters of Base class template. It might get quite long if you add more parameters.

To get rid of this problem one can fix the length of the friend declaration by introducing a non-template Accessor that forwards calls:

// Library code
class Accessor
{
  private:
    template<class> friend class Base;
    template<class DerivedT>

    static int foo(DerivedT& derived)
    {
        return derived.do_foo();
    }
};

The function Base::foo should call Accessor::foo which in turn calls Derived::do_foo. A first step of this call chain is always successful because the Base is a friend of Accessor:

// Library code
template<class DerivedT>

class Base
{
  public:
    DerivedT& derived() {
       return static_cast<DerivedT&>(*this); }
    int foo() {
       return Accessor::foo(this->derived()); }
};

The second step succeeds only if either do_foo is public or if the Accessor is a friend of Derived and do_foo is protected. We are interested only in a second alternative:

// User code
class Derived : public Base<Derived>

{
  private:
    friend class Accessor;
    int do_foo() { return 0; }
};

This approach is taken by several boost libraries. For example, def_visitor_access in Boost.Python and iterator_core_access in Boost.Iterator should be declared as friends in order to access user-defined private functions from def_visitor and iterator_facade respectively.

Even though this solution is simple, there is a way to omit the friend declaration. This is not possible if do_foo is private – you will have to change that to protected. The difference between these two access specifiers is not so important for most CRTP uses. To understand why, take a look at how you derive from CRTP base class:

class Derived : public Base<Derived> { /* ... */ };

Here, you pass the final class to Base’s template arguments list.

An attempt to derive from Derived doesn’t give you any advantage because the Base<Derived> class knows only about Derived.

Our goal is to access protected function Derived::do_foo from the Base:

// User code
class Derived : public Base<Derived>

{
  protected:
    // No friend declaration here!
    int do_foo() { return 0; }
};

Normally, you access a protected function declared in a base class from its child. The challenge is to access it the other way around.

The first step is obvious. The only place for our interception point where a protected function can be accessed is a descendant of Derived:

struct BreakProtection : Derived
{
    static int foo(Derived& derived) {
       /* call do_foo here */ }
};

An attempt to write

   return derived.do_foo();

inside BreakProtection::foo fails because it’s forbidden according to the standard, paragraph 11.5:

When a friend or a member function of a derived class references a protected nonstatic member of a base class, an access check applies in addition to those described earlier in clause 11. Except when forming a pointer to member (5.3.1), the access must be through a pointer to, reference to, or object of the derived class itself (or any class derived from that class) (5.2.5).

The function can only be accessed through an object of type BreakProtection.

Well, if the function can’t be called directly, let’s call it indirectly. Taking an address of do_foo is legal inside BreakProtection class:

    &BreakProtection::do_foo;

There is no do_foo inside BreakProtection, therefore, this expression is resolved as &Derived::do_foo. Public access to a pointer to protected member function has been granted! It’s time to call it:

struct BreakProtection : Derived
{
  static int foo(Derived& derived)
  {
    int (Derived::*fn)() =
       &BreakProtection::do_foo;
    return (derived.*fn)();
  }
};

For better encapsulation, the BreakProtection can be moved to the private section of Base class template. The final solution is:

// Library code
template<class DerivedT>

class Base
{
  private:
    struct accessor : DerivedT
    {
        static int foo(DerivedT& derived)
        {
            int (DerivedT::*fn)() 
               = &accessor::do_foo;
            return (derived.*fn)();
        }
    };
  public:
    DerivedT& derived() {
       return static_cast<DerivedT&>(*this); }
    int foo() { return accessor::foo(
       this->derived()); }
};
// User code
struct Derived : Base<Derived>
  protected:
    int do_foo() { return 1; }
};

Note that the user code is slightly shorter and cleaner than in the first solution. The library code has similar complexity.

There is a downside to this approach, though. Many compilers don’t optimize away function pointer indirection even if it’s called in-place:

return (derived.*(&accessor::do_foo))();

The main strength of CRTP over virtual functions is better optimization.

CRTP is faster because there is no virtual function call overhead and it compiles to smaller code because no type information is generated. The former is doubtful for the second solution while the latter still holds. Hopefully, future versions of popular compilers will implement this kind of optimization. Also, it’s less convenient to use member function pointers, especially for overloaded functions.

References

[Coplien] James O. Coplien. “Curiously Recurring Template Patterns”, C++ Report, February 1995.

[Vandevoorde-] David Vandevoorde, Nicolai M. Josuttis. “C++ Templates: The Complete Guide”. http://www.informit.com/articles/article.asp?p=31473

[Boost] Boost libraries. http://www.boost.org.

[standard] ISO-IEC 14882:1998(E),Programming languages - C++.