why Curiously Recurring Template Pattern (CRTP) works

Question

I meet a lot of explanations about what CRTP is, but there is no explanation of why it works.

The Microsoft Implementation of CRTP in ATL was independently discovered, also in 1995 by Jan Falkin who accidentally derived a base class from a derived class. Christian Beaumont, first saw Jan's code and initially thought it couldn't possibly compile in the Microsoft compiler available at the time. Following this revelation that it did indeed did work, Christian based the entire ATL and WTL design on this mistake.

For example,

 template< typename T >
 class Base
 {
    ...
 };

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

I understand why and when it could be used. But I want to know how the compiler works in this way. Because in my head it shouldn't work due to endless recursion: class Derived inherits from Base< Derived >, where Derived is class which inherits from Base< Derived >, where Derived... and so on.

Could you please kindly explain step by step how it works from the compiler point of view?

Answer 1

Recursively-defined types aren't unusual: a linked list is recursive, too. It works because at one point in the cycle you don't need the type to be complete, you only need to know its name.

struct LinkedNode {
    int data;
    LinkedNode *next; // Look ma, no problem
};

In the case of CRTP, that point is here:

Base<Derived>

Instantiating Base for Derived does not require Derived to be complete, only to know that it is a class type. I.e., the following works fine:

template <class>
struct Foo { };

struct Undefined;

Foo<Undefined> myFoo;

Thus, as long as the definition of Base does not require Derived to be complete, everything just works.

Answer 2

The CRTP is named recurring because in

class Derived: public Base<Derived> { ... }

The class template Base is instantiated on the class Derived, which inherits from the class Base<Derived>, which is, in turn, the class template Base instantiated on Derived, which inherits Base<Dervied> ... and so on.

The name Derived above is used in its own definition, in a context where it is not yet fully defined, and, therefore, this makes Derived an incomplete type. Base<Derived> is being instantiated on a type, Derived, that is incomplete at that moment, so this is where the recursion ends since Base can't know that Derived, in turns, inherits from Base<Derived>.

Answer 3

public Base< Derived >

Here, Derived only refers to a typename that's used for T inside Base, that's all it is. You certainly could get infinite recursion but that all depends on how you use T inside Base . T in itself is just a type like any other class type, types in itself don't actually do anything.