How can classes be enumerated, ordered, etc. at compile time?

Question

I'm struggling with some of the rules of what can be pushed into compile time calculations. Here I've written code that associates a unique ID with each class that requests one (and a demangled name for testing purposes.) However, this unique ID can't be used as a template argument or a part of a static_assert condition, because it isn't a constexpr.

#include <cassert>
#include <cxxabi.h>
#include <iostream>
#include <typeinfo>

namespace UID {
    static int nextID(void) {
        static int stored = 0;
        return stored++;
    }
    template<class C>
    static int getID(void) {
        static int once = nextID();
        return once;
    }
    template<class C>
    static const char *getName(void) {
        static int status = -4;
        static const char *output =
            abi::__cxa_demangle(typeid(C).name(), 0, 0, &status);
        return output;
    }
}

namespace Print {
    template<class C>
    std::ostream& all(std::ostream& out) {
        return out << "[" << UID::getID<C>() << "] = "
            << UID::getName<C>() << std::endl;
    }
    template<class C0, class C1, class... C_N>
        std::ostream& all(std::ostream& out) {
        return all<C1, C_N>(all<C0>(out));
    }
}

void test(void) {
    Print::all<int, char, const char*>(std::cout) << std::endl;
    // [0] = int
    // [1] = char
    // [2] = char const*
    Print::all<char, int, const char*>(std::cout);
    // [1] = char
    // [0] = int
    // [2] = char const*
}

If it isn't clear, I'd like to change other compile-time behavior based on the ID. I've seen several approaches that involved a linked list of types, so that the ID is the sum of a previously assigned constexpr ID and a constexpr offset. However, I don't see how this is an improvement over manually assigning ID's. If you were to sort one list of classes by their ID's, then wrap each of the classes and request ID's for the wrappers, the ID's would depend on the sorting; then to determine the "last" element, you would have to either sort the elements manually! What am I missing?

Answer 1

Sometimes, one has to acknowledge that C++ by itself will not solve all of the world's problems.

Sometimes, it becomes necessary to integrate additional tools and scripts into one's build system. I think this is one of those cases.

But first, let's use just C++ to solve as much of this problem as possible. And we'll use the Curiously Recursive Template Pattern:

template<typename C> class UID {

public:

    static const int id;
};

Then, each class that requests a unique ID would then inherit from this template, accordingly, resulting in a member called id:

class Widget : public UID<Widget> {

// ...

};

So, Widget::id becomes the class's unique ID.

Now, all that we need to do is to figure out how to declare all classes' id values. And, at this point we reach the limits of what C++ can do by itself, and we must call in some reinforcements.

We'll begin by creating a file that lists all classes that have an assigned ID. This is nothing complicated, just a simple file named, say, classlist, whose contents would simply be something like this.

Button
Field
Widget

(Button, Field, and Widget, are other classes than inherit from the UID class).

Now, it becomes a simple two step process:

1) A simple shell, or a Perl script, that reads the classlist file, and spews out robo-generated code of the form (given the above input):

const int UID<Button>::id=0;
const int UID<Field>::id=1;
const int UID<Widget>::id=2;

... and so on.

2) The appropriate tweaks to your build script or Makefile, to compile this robo-generated code (with all the necessary #include, etc..., to make this happen), and link it with your application. So, a class that wants an ID assigned to it must explicitly inherit from the UID class, and its name added to a file. The build script/Makefile then automatically runs a script that generates a new uid list, and compiles it, during the next build cycle.

(Hopefully, you are using a real C++ development environment, that provides you with flexible development tools, instead of being forced to suffer some inflexible visual-IDE type limited development environment, with limited functionality).

This is just a starting point. With a little bit more work, it should be possible to take this basic approach, and enhance it to auto-generate constexpr uids, which would be even better. This will require cracking a few tough nuts, such as trying to avoid triggering a recompile of the entire app, when the list of UID-using classes changes. But, I think this is a solvable problem, too...

Postscriptum:

It might still be possible to pull this off using only C++, by leveraging compiler-specific extensions. For example, using gcc's __COUNTER__ macro.

Answer 2

This is a very interesting question because it's related to not just implementing a counter at compile-time in C++, it's also about associating (static) counter values with types at compile-time.

So I researched for a bit and came across a very interesting blog post How to implement a constant expression counter in C++ by Filip Roséen

His implementation of a counter really stretches the limits of ADL and SFINAE to work:

template<int N>
struct flag {
  friend constexpr int adl_flag (flag<N>);
};
template<int N>
struct writer {
  friend constexpr int adl_flag (flag<N>) {
    return N;
  }

  static constexpr int value = N;
};
template<int N, int = adl_flag (flag<N> {})>
int constexpr reader (int, flag<N>) {
  return N;
}

template<int N>
int constexpr reader (float, flag<N>, int R = reader (0, flag<N-1> {})) {
  return R;
}

int constexpr reader (float, flag<0>) {
  return 0;
}
template<int N = 1>
int constexpr next (int R = writer<reader (0, flag<32> {}) + N>::value) {
  return R;
}
int main () {
  constexpr int a = next ();
  constexpr int b = next ();
  constexpr int c = next ();

  static_assert (a == 1 && b == a+1 && c == b+1, "try again");
}

Essentially it relies on ADL failing to find an appropriate definition of a friend function, resulting in SFINAE, and recursing with templates until either an exact match or ADL succeeds. The blog post does a fairly good job of explaining what's going on.

Limitations

(lifted from the article)

• You cannot use the same counter across translation units else you may violate ODR.
• Be careful with some comparison operators between constexpr generated values; despite the order of your calls there are sometimes no guarantees on the relative time the compiler will instantiate them. (could we do anything about this with std::atomic?)
  • This means a < b is not guaranteed to be true if evaluated at compile-time, even though it will be by run time.
• Order of template argument substitution; may result in inconsistent behavior across C++11 compilers; fixed in C++14
• MSVC support: Even the compiler that ships with Visual Studio 2015 still doesn't have full support for expression SFINAE. Workarounds available in the blog post.

---

Turning the counter into a type-associated UUID

Turns out it was really pretty simple to change:

template<int N = 1, int C = reader (0, flag<32> ())>
int constexpr next (int R = writer<C + N>::value) {
  return R;
}

into

template<typename T, int N = 1>
struct Generator{
 static constexpr int next = writer<reader (0, flag<32> {}) + N>::value; // 32 implies maximum UUID of 32
};

Given that const static int is one of the few types you can declare and define in the same spot [9.4.2.3]:

A static data member of literal type can be declared in the class definition with the constexpr specifier; if so, its declaration shall specify a brace-or-equal-initializer in which every initializer-clause that is an assignment-expression is a constant expression. [ Note: In both these cases, the member may appear in constant expressions. — end note ]

So now we can write code like this:

constexpr int a = Generator<int>::next;
constexpr int b = Generator<int>::next;
constexpr int c = Generator<char>::next;

static_assert(a == 1, "try again");
static_assert(b == 1, "try again");
static_assert(c == 2, "try again");

Notice how int remains 1 while char increments the counter to 2.

Live Demo

This code suffers from all the same drawbacks as before (and probably more I haven't though of)

Note

There will be a great number of compiler warnings with this code, due to the fact of so many declarations of friend constexpr int adl_flag(flag<N>) for the each integer value; one for every unused counter value in fact.