Does C++ Support Compile-Time Counters

Does C++ support compile-time counters?

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.

C++ compile time counters, revisited

After further investigation, it turns out there exists a minor modification that can be performed to the next() function, which makes the code work properly on clang++ versions above 7.0.0, but makes it stop working for all other clang++ versions.

Have a look at the following code, taken from my previous solution.

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

If you pay attention to it, what it literally does is to try to read the value associated with slot<N>, add 1 to it and then associate this new value to the very same slot<N>.

When slot<N> has no associated value, the value associated with slot<Y> is retrieved instead, with Y being the highest index less than N such that slot<Y> has an associated value.

The problem with the above code is that, even though it works on g++, clang++ (rightfully, I would say?) makes reader(0, slot<N>()) permanently return whatever it returned when slot<N> had no associated value. In turn, this means that all slots get effectively associated with the base value 0.

The solution is to transform the above code into this one:

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

Notice that slot<N>() has been modified into slot<N-1>(). It makes sense: if I want to associate a value to slot<N>, it means no value is associated yet, therefore it makes no sense to attempt to retrieve it. Also, we want to increase a counter, and value of the counter associated with slot<N> has to be one plus the value associated with slot<N-1>.

Eureka!

This breaks clang++ versions <= 7.0.0, though.

Conclusions

It seems to me that the original solution I posted has a conceptual bug, such that:

• g++ has quirk/bug/relaxation that cancels out with my solution's bug and eventually makes the code work nonetheless.
• clang++ versions > 7.0.0 are stricter and don't like the bug in the original code.
• clang++ versions <= 7.0.0 have a bug that makes the corrected solution not work.

Summing all that up, the following code works on all versions of g++ and clang++.

#if !defined(__clang_major__) || __clang_major__ > 7
template <int N>
constexpr int next(int R = writer<N, reader(0, slot<N-1>())+1>::value) {
    return R;
}
#else
template <int N>
constexpr int next(int R = writer<N, reader(0, slot<N>())+1>::value) {
    return R;
}
#endif

The code as-is also works with msvc.
The icc compiler doesn't trigger SFINAE when using decltype(counter(slot<N>())), preferring to complain about not being able to deduce the return type of function "counter(slot<N>)" because it has not been defined. I believe this is a bug, that can be worked around by doing SFINAE on the direct result of counter(slot<N>). This works on all other compilers too, but g++ decides to spit out a copious amount of very annoying warnings that cannot be turned off. So, also in this case, #ifdef could come to the rescue.

The proof is on godbolt, screnshotted below.

A compile-time counter for distinct Type identifier

In C++20, you might do:

template <typename = decltype([]{})>
class Class1{};

template<typename T1, typename T2, typename = decltype([]{})>
class Class2{
    std::tuple<T1*, T2*> v;
  public:
    Class2(T1* t1, T2* t2): v(std::tuple<T1*, T2*>(t1, t2)) {}
};

template <typename T = decltype([]{})>
auto makeClass1() { return Class1<T>();}

template<typename T1, typename T2, typename T = decltype([]{})>
auto operator*(T1& t1, T2& t2) {
    return Class2<T1, T2, T>(&t1, &t2);
}

int main() {
    auto t1 = makeClass1();
    auto t2 = makeClass1(); // Type of t2 is different from type of t1.
    auto m1 = t1*t2;
    auto m2 = t1*t2; // Type of m2 is different from type of m1.

    static_assert(!std::is_same_v<decltype(t1), decltype(t2)>);
    static_assert(!std::is_same_v<decltype(m1), decltype(m2)>);
}

Demo.

Constexpr counter that works on GCC 8, and is not restricted to namespace scope

The body of a constexpr function template must yield the same answer for all instatiations with the same template parameters and same arguments. You need to add a level of indirection, so the calculation can happen in the default argument of a template parameter dependent on the first.

See https://gcc.godbolt.org/z/GHfKKf

namespace Meta
{
    template <typename T,int I> struct Tag {};

    template<typename T,int N,bool B>
    struct Checker{
        static constexpr int currentval() noexcept{
            return N;
        }
    };

    template<typename T,int N>
    struct CheckerWrapper{
        template<bool B=Flag<Tag<T,N>>::Read(),int M=Checker<T,N,B>::currentval()>
        static constexpr int currentval(){
            return M;
        }
    };

    template<typename T,int N>
    struct Checker<T,N,true>{
        template<int M=CheckerWrapper<T,N+1>::currentval()>
        static constexpr int currentval() noexcept{
            return M;
        }
    };

    template<typename T,int N,bool B=Flag<Tag<T,N>>::ReadSet()>
    struct Next{
        static constexpr int value() noexcept{
            return N;
        }
    };

    template <typename T> class TaggedCounter
    {
      public:
        template <int N=CheckerWrapper<T,0>::currentval()> static constexpr int Value(){
            return Next<T,N>::value();
        }
    };
}

How is a reference counter implemented at compile time?

The following rules should do the job for your language.

1. When a variable is declared, increment its refcount
2. When a variable goes out of scope, decrement its refcount
3. When a reference-to-variable is assigned to a variable, adjust the reference counts for the variable(s):
   
   • increment the refcount for the variable whose reference is being assigned
   • decrement the refcount for the variable whose references was previously in the variable being assigned to (if it was not null)
4. When a variable containing a non-null reference-to-variable goes out of scope, decrement the refcount for the variable it referred to.

Note:

• If your language allows reference-to-variable types to be used in data structures, "static" variables, etcetera, the rules abouve need to be extended ... in the obvious fashion.
• An optimizing compiler may be able to eliminate some refcount increments and decrements.

---

Compile time reference counting:

1. There isn't really any such thing. Reference counting is done at runtime. It doesn't make sense to do it at compile time.
2. You are probably talking about analyzing the code to determine if runtime reference counting can be optimized or entirely eliminated.
   
   • I alluded to the former above. It is really a kind of peephole optimization.
   • The latter entails checking whether a reference-to-variable can ever escape; i.e. whether it could be used after the variable goes out of scope. (Try Googling for "escape analysis". This is kind of analogous to the "escape analysis" that a compiler could do to decide if an object could be allocated on the stack rather than in the heap.)

---

Related Topics