//FIXME -- Jason Felice’s blog

I’m working through trying to understand elsa, which is a C++ parser that some C++ rewriting tools have been built on. I encountered this template type FakeList<>.

Now, if you’ve been around for a bit, you know – at least on some intellectual level – that you have definitely not seen all the evil C++ tricks. I’m sure God has found himself sitting around on his cloud reading a bit of C++ code one day, and found himself uttering “What the …? Oh crap, that’s cool!”

So what is a FakeList? It’s a type which is never instantiated, even though it’s used. Let me give you a little taste (I’m editing out pieces of the code not essential to the exposition):

template <class T>
class FakeList {
private:
  // you can't create or delete one of these
  FakeList();
  ~FakeList();
 
public:
  // this is as much of a constructor as there is
  static FakeList<T> *makeList(T *node) { return (FakeList<T>*)node; }
  static FakeList<T> *emptyList()       { return NULL; }
 
  // ...
};

In other words, we never instantiate a FakeList<T>, we just cast a T* to FakeList<T>.

So what can we do with FakeLists? Here’s the rest of the methods:

  void deallocNodes();
 
  // simple selectors
  int count() const;
  bool isEmpty() const                  { return this == NULL; }
  bool isNotEmpty() const               { return !isEmpty(); }
 
  // "car" in Lisp terminology
  T *first()                            { return (T*)this; }
  T const *firstC() const               { return (T const*)this; }
 
  // "cdr" in Lisp terminology
  FakeList<T> *butFirst()               { return makeList(first()->next); }
  FakeList<T> const *butFirstC() const  { return makeList(firstC()->next); }
 
  // similar to "cons" in Lisp terminology (but this doesn't allocate)
  FakeList<T> *prepend(T *newHead);
 
  T const *nthC(int n) const;
  T *nth(int n) { return const_cast<T*>(nthC(n)); }

In this instance, you’ll notice that FakeList<> expects the T type to have a data member next which is a T*.

We’ve just given ourselves some advantages:

1. The separation of the list interface from the type’s own interface.
2. No additional allocations required for list nodes.
3. Zero overhead when “taking” an already-constructed element into a list.

We could certainly do similar things in less evil ways, but as far as I can figure, we can’t accomplish all three goals in a less evil way:

If we aren’t concerned with point 1, we can use the curiously recurring template pattern to implement the standard list methods for each type.

If we aren’t concerned with point 3, we can simply use stl::list. It uses in-place copy construction to avoid making additional allocations for list headers – the list node contains the type in place. This form of copy construction is usually negligible, but clearly for some types (especially ones which directly or indirectly contain handles to operating system resources), this could be painful.