Patterns · Tips & Tricks

The Curiously Recurring Generic Pattern

This curious little pattern can be helpful for certain problems that involve generics. We’ll look at what it is, and at a couple of use cases for it.

What is it?

The Curiously Recurring Generic Pattern (CRGP) is a pattern where a class TFoo derives from a generic class, using the class TFoo itself as the type parameter. Confused? It may make more sense in code:

This looks curiously recurring indeed. I stumbled upon this pattern while developing a generic linked list. Let’s see how this pattern can be useful there.

A Generic Linked List

The idea of this linked list is that you have a base class that provides a reference to the next item in the list, so it can be used to build a linked list:

type
  TLinkedListItem = class abstract
  private
    FNext: TLinkedListItem;
  public
    property Next: TLinkedListItem read FNext;
  end;

Then you can define a generic linked list using a type parameter with the constraint that the items in the list must derive from TLinkedListItem:

type
  TLinkedList<T: TLinkedListItem> = class
  private
    FHead: T;
  public
    procedure Add(const AItem: T);

    property Head: T read FHead;
  end;

{ TLinkedList<T> }

procedure TLinkedList<T>.Add(const AItem: T);
begin
  if (AItem <> nil) then
  begin
    AItem.FNext := FHead;
    FHead := AItem;
  end;
end;

For example, we can create a linked list of persons like this:

type
  TPerson = class(TLinkedListItem)
  private
    FName: String;
  public
    constructor Create(const AName: String);

    property Name: String read FName;
  end;

var List := TLinkedList<TPerson>.Create;
List.Add(TPerson.Create('Alice'));
List.Add(TPerson.Create('Bob'));
List.Add(TPerson.Create('Charlie'));

(This code creates various memory leaks, but let’s keep it simple without the distractions of pesky memory management).

In the example, TPerson derives from TLinkedListItem so that it can be added to a linked list. We could (try to) enumerate the list in the usual way:

var Person := List.Head;
while (Person<> nil) do
begin
  WriteLn(Person.Name);
  Person := Person.Next; //< Does not compile
end;

However, compiling this code gives you the error message “Incompatible types: ‘TPerson’ and ‘TLinkedListItem’“. This is because Person is of type TPerson, but the Person.Next property returns a TLinkedListItem, which is not assignment compatible with a TPerson. So we would have to typecast here (or use the more defensive as operator):

var Person := List.Head;
while (Person <> nil) do
begin
  WriteLn(Person.Name);
  Person := Person.Next as TPerson;
end;

While this is doable, it certainly isn’t pretty and as straightforward as the previous code. And you are also placing the burden of typecasting with the users of your linked list class.

CRGP to the rescue

With the Curiously Recurring Generic Pattern, we can make a generic version of TLinkedListItem:

type
  TLinkedListItem = class abstract
  private
    FNext: TLinkedListItem;
  end;

type
  TLinkedListItem<T: class> = class abstract(TLinkedListItem)
  private
    function GetNext: T; inline;
  public
    class constructor Create;
  public
    property Next: T read GetNext;
  end;

Now, the Next property returns the actual type of the linked list item:

function TLinkedListItem<T>.GetNext: T;
begin
  Result := T(FNext);
end;

We still need to typecast here. But the difference is that this typecast is performed inside the linked list library itself, so you don’t have to burden the users of this class with it.

This trick only works if the type parameter T is a class that derives from TLinkedListItem. Unfortunately, you cannot use a generic constraint like this:

type
  TLinkedListItem<T: TLinkedListItem> = class(TLinkedListItem)

Since that results in compilation errors later when you derive from this class. So we use a general class constraint (type TLinkedListItem<T: class>) instead and add a class constructor that checks if type T derives from TLinkedListItem:

class constructor TLinkedListItem<T>.Create;
begin
  Assert(T.InheritsFrom(TLinkedListItem));
end;

(Remember that the class constructor is called once, and only once, for each generic instantiation of T). I used an assertion here, but you could also raise an exception. This will alert the developer using the linked list library if they try to use an invalid type.

Now we can define the person class using the CRGP:

type
  TPerson = class(TLinkedListItem<TPerson>)
    ...
  end;

And enumerate them without the need to typecast:

var Person := List.Head;
while (Person <> nil) do
begin
  WriteLn(Person.Name);
  Person := Person.Next;
end;

After I “discovered” this pattern, I wondered if it is a common pattern. And it turns out it is in the C++ world, where it is called the Curiously Recurring Template Pattern. While C++ templates are not generics, they are similar enough for this purpose that I called the Delphi version the Curiously Recurring Generic Pattern. I don’t know if this is an “official” name, but if it isn’t, it is now😉.

So naturally I wondered if some common C++ use cases for this pattern apply to Delphi as well. While not all C++ use cases can be converted to Delphi (because templates are not generics), a couple of them can. Let’s take a look at them.

Generic Instance Counter

This one is pretty simple. Sometimes you may want to know how many instances of a certain class are alive in your application. Maybe for debugging purposes, or for tracing, or as input for a load balancing algorithm. You could add an FInstanceCount class variable to each class you want to keep track off, and then increment that value in the constructor and decrement it in the destructor. However, if you want to keep track of many classes, then this leads to a lot of code duplication. The CRGP makes it much easier:

type
  TCounter<T> = class
  private class var
    FInstanceCount: Integer;
  public
    constructor Create;
    destructor Destroy; override;

    class property InstanceCount: Integer read FInstanceCount;
  end;

type
  TFoo = class(TCounter<TFoo>)
  end;

type
  TBar = class(TCounter<TBar>)
  end;

{ TCounter<T> }

constructor TCounter<T>.Create;
begin
  inherited;
  Inc(FInstanceCount);
end;

destructor TCounter<T>.Destroy;
begin
  Dec(FInstanceCount);
  inherited;
end;

Because TCounter<T> is a generic class, there is a separate instance of the FInstanceCount class variable for each instantiated type (TCounter<TFoo> and TCounter<TBar> in this example). So the following sample code…

TFoo.Create;
TBar.Create;
TFoo.Create;
TFoo.Create;
TBar.Create;

WriteLn('Number of TFoo instances: ', TFoo.InstanceCount);
WriteLn('Number of TBar instances: ', TBar.InstanceCount);

…outputs the following:

Number of TFoo instances: 3
Number of TBar instances: 2

Fluent Interfaces

You may already be familiar with the concept of fluent interfaces. It uses method chaining to call multiple methods of the same object, without having to specify the object for each call. This is accomplished by having these methods return the object itself, so you can call another method on it. This approach is used in a couple of places in the Delphi RTL, for example to chain multiple calls on a TStringBuilder together:

var Builder := TStringBuilder.Create;
try
  Builder.Append('Answer = ').Append(42);
  WriteLn(Builder.ToString)
finally
  Builder.Free;
end;

Here, the Append method returns the string builder itself, so you can immediately call another method on it. A simple (custom but inefficient) implementation of TStringBuilder may look like this:

type
  TStringBuilder = class
  private
    FData: String;
  public
    function Append(const AValue: String): TStringBuilder;

    property Data: String read FData;
  end;

{ TStringBuilder }

function TStringBuilder.Append(
  const AValue: String): TStringBuilder;
begin
  FData := FData + AValue;
  Result := Self;
end;

As you can see, the Append method returns Self to enable method chaining.

Now suppose we want to create a subclass to aid in the building of HTML strings. For example, it has methods to toggle bold text on and off:

type
  THtmlStringBuilder = class(TStringBuilder)
  public
    function BoldOn: THtmlStringBuilder;
    function BoldOff: THtmlStringBuilder;
  end;

{ THtmlStringBuilder }

function THtmlStringBuilder.BoldOff: THtmlStringBuilder;
begin
  Append('</b>');
  Result := Self;
end;

function THtmlStringBuilder.BoldOn: THtmlStringBuilder;
begin
  Append('<b>');
  Result := Self;
end;

Again, since these methods return Self, they can be used for chaining. However, the following code will not compile:

Builder.Append('This is ').BoldOn.Append('bold').BoldOff.Append('!');

This is because the Append method returns a TStringBuilder, and that class does not have a method called BoldOn.

You guessed it: the CRGP can fix this:

type
  TStringBuilder<T: class> = class
  private
    FData: String;
  public
    class constructor Create;
  public
    function Append(const AValue: String): T;

    property Data: String read FData;
  end;

type
  THtmlStringBuilder = class(TStringBuilder<THtmlStringBuilder>)
  public
    function BoldOn: THtmlStringBuilder;
    function BoldOff: THtmlStringBuilder;
  end;

{ TStringBuilder<T> }

function TStringBuilder<T>.Append(const AValue: String): T;
begin
  FData := FData + AValue;
  Result := T(Self);
end;

class constructor TStringBuilder<T>.Create;
begin
  Assert(T.InheritsFrom(TStringBuilder<T>));
end;

We use the same kind of typecast and assertion here as we did for the linked list earlier. Now we can chain the methods together with no problem:

var Builder := THtmlStringBuilder.Create;
Builder.Append('This is ').BoldOn.Append('bold').BoldOff.Append('!');
WriteLn(Builder.Data);

Which outputs:

This is <b>bold</b>!

Source Code

As always, the examples in this article can be found in our JustAddCode repository on GitHub in the directory CuriouslyRecurringGenericPattern.

Other Use Cases?

Arguably the most common use case for this pattern in the C++ world is to implement a form of static polymorphism. This form of polymorphism resolves methods calls at compile-time instead of run-time. This avoids the overhead of virtual methods and can therefore improve performance a bit. But since this requires a C++ specific template feature, it cannot be replicated in Delphi (although I would love to be proven wrong here).

But maybe you can think of other interesting use cases for this pattern. I would be very interested to know what you come up with!

2 thoughts on “The Curiously Recurring Generic Pattern

Leave a Reply to Didier LOZAC'H Cancel reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s