Does C++ support compile-time counters?

Question

For the purpose of introspection, sometimes I've wanted to automatically assign serial numbers to types, or something similar.

Unfortunately, template metaprogramming is essentially a functional language, and as such lacks global variables or modifiable state which would implement such a counter.

Or does it?

---

Example code by request:

#include <iostream>

int const a = counter_read;
counter_inc;
counter_inc;
counter_inc;
counter_inc;
counter_inc;

int const b = counter_read;

int main() {
    std::cout << a << ' ' << b << '\n'; // print "0 5"
    
    counter_inc_t();
    counter_inc_t();
    counter_inc_t();
    
    std::cout << counter_read << '\n'; // print "8"
    
    struct {
        counter_inc_t d1;
        char x[ counter_read ];
        counter_inc_t d2;
        char y[ counter_read ];
    } ls;
    
    std::cout << sizeof ls.x << ' ' << sizeof ls.y << '\n'; // print "9 10"
}

Answer 1

Well… yes, template metaprogramming lacks side effects as it is intended. I was misled by a bug in older versions of GCC and a little unclear wording in the Standard to believe that all those features were possible.

However, at least the namespace-scope functionality can be achieved with little use of templates at all. Function lookup can extract numeric state from the set of declared functions, as demonstrated below.

Library code:

template< size_t n > // This type returns a number through function lookup.
struct cn // The function returns cn<n>.
    { char data[ n + 1 ]; }; // The caller uses (sizeof fn() - 1).

template< typename id, size_t n, size_t acc >
cn< acc > seen( id, cn< n >, cn< acc > ); // Default fallback case.

/* Evaluate the counter by finding the last defined overload.
   Each function, when defined, alters the lookup sequence for lower-order
   functions. */
#define counter_read( id ) \
( sizeof seen( id(), cn< 1 >(), cn< \
( sizeof seen( id(), cn< 2 >(), cn< \
( sizeof seen( id(), cn< 4 >(), cn< \
( sizeof seen( id(), cn< 8 >(), cn< \
( sizeof seen( id(), cn< 16 >(), cn< \
( sizeof seen( id(), cn< 32 >(), cn< 0 \
/* Add more as desired; trimmed for Stack Overflow code block. */ \
                      >() ).data - 1 ) \
                      >() ).data - 1 ) \
                      >() ).data - 1 ) \
                      >() ).data - 1 ) \
                      >() ).data - 1 ) \
                      >() ).data - 1 )

/* Define a single new function with place-value equal to the bit flipped to 1
   by the increment operation.
   This is the lowest-magnitude function yet undefined in the current context
   of defined higher-magnitude functions. */
#define counter_inc( id ) \
cn< counter_read( id ) + 1 > \
seen( id, cn< ( counter_read( id ) + 1 ) & ~ counter_read( id ) >, \
          cn< ( counter_read( id ) + 1 ) & counter_read( id ) > )

Quick demo (see it run):

struct my_cnt {};

int const a = counter_read( my_cnt );
counter_inc( my_cnt );
counter_inc( my_cnt );
counter_inc( my_cnt );
counter_inc( my_cnt );
counter_inc( my_cnt );

int const b = counter_read( my_cnt );

counter_inc( my_cnt );

#include <iostream>

int main() {
    std::cout << a << ' ' << b << '\n';

    std::cout << counter_read( my_cnt ) << '\n';
}

C++11 Update

Here is an updated version using C++11 constexpr in place of sizeof.

#define COUNTER_READ_CRUMB( TAG, RANK, ACC ) counter_crumb( TAG(), constant_index< RANK >(), constant_index< ACC >() )
#define COUNTER_READ( TAG ) COUNTER_READ_CRUMB( TAG, 1, COUNTER_READ_CRUMB( TAG, 2, COUNTER_READ_CRUMB( TAG, 4, COUNTER_READ_CRUMB( TAG, 8, \
    COUNTER_READ_CRUMB( TAG, 16, COUNTER_READ_CRUMB( TAG, 32, COUNTER_READ_CRUMB( TAG, 64, COUNTER_READ_CRUMB( TAG, 128, 0 ) ) ) ) ) ) ) )

#define COUNTER_INC( TAG ) \
constexpr \
constant_index< COUNTER_READ( TAG ) + 1 > \
counter_crumb( TAG, constant_index< ( COUNTER_READ( TAG ) + 1 ) & ~ COUNTER_READ( TAG ) >, \
                                                constant_index< ( COUNTER_READ( TAG ) + 1 ) & COUNTER_READ( TAG ) > ) { return {}; }

#define COUNTER_LINK_NAMESPACE( NS ) using NS::counter_crumb;

template< std::size_t n >
struct constant_index : std::integral_constant< std::size_t, n > {};

template< typename id, std::size_t rank, std::size_t acc >
constexpr constant_index< acc > counter_crumb( id, constant_index< rank >, constant_index< acc > ) { return {}; } // found by ADL via constant_index

http://ideone.com/yp19oo

The declarations should be put inside a namespace, and all names used in the macros except counter_crumb should be fully qualified. The counter_crumb template is found via ADL association with the constant_index type.

The COUNTER_LINK_NAMESPACE macro can be used to increment one counter in the scope of multiple namespaces.

Answer 2

I believe both MSVC and GCC support a __COUNTER__ preprocessor token that has a monotonically increasing value substituted in its place.

Answer 3

I was thinking to solve this problem for quite sometime, and have come up with a very short-clean solution. At least I deserve one upvote to try this out. :))

Following library code achieves namespace level functionality. i.e. I am successful to implement counter_read and counter_inc; but not the counter_inc_t (which is incremented inside function because template classes are not allowed inside function)

template<unsigned int NUM> struct Counter { enum { value = Counter<NUM-1>::value }; };
template<> struct Counter<0> { enum { value = 0 }; };

#define counter_read Counter<__LINE__>::value
#define counter_inc template<> struct Counter<__LINE__> { enum { value = Counter<__LINE__-1>::value + 1}; }

This technique uses template meta-programming and leverages the __LINE__ macro. See the result for the code from your answer.

Answer 4

Since sharing is caring and I spent a few hours fiddling around with the base example this side provides I'm going to post my solution as well.

The version linked to in the article has two major downsides. The max number it can count too is very low, due to max recursion depth (usually something around 256). And the time it takes to compile as soon as a count of more than a few hundred has been reached is huge.

By implementing binary search to detect if a flag for a counter has already been set or not, it's possible to massively increase the max count (controllable through MAX_DEPTH) and also improve compile time at the same time. =)

Usage example:

static constexpr int a = counter_id();
static constexpr int b = counter_id();
static constexpr int c = counter_id();

#include <iostream>

int main () {
    std::cout << "Value a: " << a << std::endl;
    std::cout << "Value b: " << b << std::endl;
    std::cout << "Value c: " << c << std::endl;
}

Fully working code with example at the end: (Except for clang. See comments.)

// Number of Bits our counter is using. Lower number faster compile time,
// but less distinct values. With 16 we have 2^16 distinct values.
#define MAX_DEPTH 16

// Used for counting.
template<int N>
struct flag {
    friend constexpr int adl_flag(flag<N>);
};

// Used for noting how far down in the binary tree we are.
// depth<0> equales leaf nodes. depth<MAX_DEPTH> equals root node.
template<int N> struct depth {};

// Creating an instance of this struct marks the flag<N> as used.
template<int N>
struct mark {
    friend constexpr int adl_flag (flag<N>) {
        return N;
    }

    static constexpr int value = N;
};

// Heart of the expression. The first two functions are for inner nodes and
// the next two for termination at leaf nodes.

// char[noexcept( adl_flag(flag<N>()) ) ? +1 : -1] is valid if flag<N> exists.
template <int D, int N, class = char[noexcept( adl_flag(flag<N>()) ) ? +1 : -1]>
int constexpr binary_search_flag(int,  depth<D>, flag<N>,
        int next_flag = binary_search_flag(0, depth<D-1>(), flag<N + (1 << (D - 1))>())) {
    return next_flag;
}

template <int D, int N>
int constexpr binary_search_flag(float, depth<D>, flag<N>,
        int next_flag = binary_search_flag(0, depth<D-1>(), flag<N - (1 << (D - 1))>())) {
    return next_flag;
}

template <int N, class = char[noexcept( adl_flag(flag<N>()) ) ? +1 : -1]>
int constexpr binary_search_flag(int,   depth<0>, flag<N>) {
    return N + 1;
}

template <int N>
int constexpr binary_search_flag(float, depth<0>, flag<N>) {
    return N;
}

// The actual expression to call for increasing the count.
template<int next_flag = binary_search_flag(0, depth<MAX_DEPTH-1>(),
        flag<(1 << (MAX_DEPTH-1))>())>
int constexpr counter_id(int value = mark<next_flag>::value) {
    return value;
}

static constexpr int a = counter_id();
static constexpr int b = counter_id();
static constexpr int c = counter_id();

#include <iostream>

int main () {
    std::cout << "Value a: " << a << std::endl;
    std::cout << "Value b: " << b << std::endl;
    std::cout << "Value c: " << c << std::endl;
}