C++ compile time counters, revisited

Question

TL;DR

Before you attempt to read this whole post, know that:

1. a solution to the presented issue has been found by myself, but I'm still eager to know if the analysis is correct;
2. I've packaged the solution into a fameta::counter class that solves a few remaining quirks. You can find it on github;
3. you can see it at work on godbolt.

How it all started

Since Filip Roséen discovered/invented, in 2015, the black magic that compile time counters via friend injection are in C++, I have been mildly obsessed with the device, so when the CWG decided that functionality had to go I was disappointed, but still hopeful that their mind could be changed by showing them a few compelling use cases.

Then, a couple years ago I decided to have a look at the thing again, so that uberswitches could be nested - an interesting use case, in my opinion - only to discover that it wouldn't work any longer with the new versions of the available compilers, even though issue 2118 was (and still is) in open state: the code would compile, but the counter would not increase.

The problem has been reported on Roséen's website and recently also on stackoverflow: Does C++ support compile-time counters?

A few days ago I decided to try and tackle the issues again

I wanted to understand what had changed in the compilers that made the, seemingly still valid C++, not work any longer. To that end, I've searched wide and far the interweb for somebody to have talked about it, but to no avail. So I've begun experimenting and came to some conclusions, that I'm presenting here hoping to get a feedback from the more-knowledged-than-myself around here.

Below I'm presenting Roséen's original code for sake of clarity. For an explanation of how it works, please refer to his website:

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");
}

With both g++ and clang++ recent-ish compilers, next() always returns 1. Having experimented a bit, the issue at least with g++ seems to be that once the compiler evaluates the functions templates default parameters the first time the functions are called, any subsequent call to those functions doesn't trigger a re-evaluation of the default parameters, thus never instantiating new functions but always referring to the previously instantiated ones.

---

First questions

1. Do you actually agree with this diagnosis of mine?
2. If yes, is this new behavior mandated by the standard? Was the previous one a bug?
3. If not, then what is the problem?

---

Keeping the above in mind, I came up with a work around: mark each next() invokation with a monotonically increasing unique id, to pass onto the callees, so that no call would be the same, therefore forcing the compiler to re-evaluate all the arguments each time.

It seems a burden to do that, but thinking of it one could just use the standard __LINE__ or __COUNTER__-like (wherever available) macros, hidden in a counter_next() function-like macro.

So I came up with the following, that I present in the most simplified form that shows the problem I will talk about later.

template <int N>
struct slot;

template <int N>
struct slot {
    friend constexpr auto counter(slot<N>);
};

template <>
struct slot<0> {
    friend constexpr auto counter(slot<0>) {
        return 0;
    }
};

template <int N, int I>
struct writer {
    friend constexpr auto counter(slot<N>) {
        return I;
    }

    static constexpr int value = I-1;
};

template <int N, typename = decltype(counter(slot<N>()))>
constexpr int reader(int, slot<N>, int R = counter(slot<N>())) {
    return R;
};

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

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

int a = next<11>();
int b = next<34>();
int c = next<57>();
int d = next<80>();

You can observe the results of the above on godbolt, which I've screenshotted for the lazies.

And as you can see, with trunk g++ and clang++ until 7.0.0 it works!, the counter increases from 0 to 3 as expected, but with clang++ version above 7.0.0 it doesn't.

To add insult to injury, I've actually managed to make clang++ up to version 7.0.0 crash, by simply adding a "context" parameter to the mix, such that the counter is actually bound to that context and, as such, can be restarted any time a new context is defined, which opens up for the possibility to use a potentially infinite amount of counters. With this variant, clang++ above version 7.0.0 doen't crash, but still doesn't produce the expected result. Live on godbolt.

At loss of any clue about what was going on, I've discovered the cppinsights.io website, that lets one see how and when templates get instantiated. Using that service what I think is happening is that clang++ does not actually define any of the friend constexpr auto counter(slot<N>) functions whenever writer<N, I> is instantiated.

Trying to explicitly call counter(slot<N>) for any given N that should already have been instantiated seems to give basis to this hypothesis.

However, if I try to explicitly instantiate writer<N, I> for any given N and I that should have already been instantiated, then clang++ complains about a redefined friend constexpr auto counter(slot<N>).

To test the above, I've added two more lines to the previous source code.

int test1 = counter(slot<11>());
int test2 = writer<11,0>::value;

You can see it all for yourself on godbolt. Screenshot below.

So, it appears that clang++ believes it has defined something that it believes it hasn't defined, which kind of makes your head spin, doesn't it?

---

Second batch of questions

1. Is my workaround legal C++ at all, or did I manage to just discover another g++ bug?
2. If it's legal, did I therefore discover some nasty clang++ bugs?
3. Or did I just delve into the dark underworld of Undefined Behavior, so I myself am the only one to blame?

---

In any event, I would warmly welcome anybody who wanted to help me get out of this rabbit hole, dispensing headaching explanations if need be. :D

Answer 1

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.