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

Kapp

Related: stackoverflow.com/questions/51601439/… – Rincon

As I remember the standard committee people have the clear intention to disallow compile-time constructs of any kind, shape or form that do not produce the exact same result every time they are (hypothetically) evaluated. So it might be a compiler bug, it might be a "ill-formed, no diagnosis required" case or it might be something the standard missed. Nevertheless it goes against the "spirit of the standard". I am sorry. I would've liked compile time counters too. – Newness

@Rincon I must confess I am finding it very difficult to get my head around that code. It does look like it could avoid the need to explicitly pass a monotonically increasing number as parameter to the next() function, however I can't really figure out how that works. In any event, I've come up with a response to my own problem, here: https://mcmap.net/q/20861/-c-compile-time-counters-revisited – Kapp

@FabioA. I too don't entirely understand that answer. Since asking that question, I've realized that I don't want to touch constexpr counters ever again. – Rincon

While this is a fun little thought experiment, somebody who actually used that code would pretty much have to expect that it won't work in future versions of C++, right? In that sense, the outcome defines itself as a bug. – Acidimetry

@Acidimetry I'm not quite sure of the logic leap you make there. It's currently abiding to the standard, hence it's not a bug. If later on the standard changes breaking compatibility with previous code, that's a deliberate decision made by those in power. We can certainly try to make them change their mind. – Kapp

@FabioA. A bug is basically anything undesired. A serious lack of portability to a higher version is one. I mean, okay, one can do a decision, but this one seems like it has a very good chance to come and bite you in the future. That said, I'd say I accept it if one can do a really really good argument why this is needed. That I would even require only for the lack of readability in this alone. – Acidimetry

@Acidimetry the mere existence of a __COUNTER__ predefined macro in all major browsers hints at the fact that a form of compile time counter is certainly required by an enough large code base. That one isn't enough for all desired use cases, though, as it lacks knowledge about context. Projects like copperspice have had to invent their own way to make such a counter, which is however limited in scope and functionality. Having a generic mechanism to implement context-aware compile time counters opens up to lots of other use cases. One of them, I've mentioned in this very QA. – Kapp

@FabioA. Thing is, not every problem has a solution. You say that the counters are required, okay, not disagreeing here. Might be a bug of C++ not having such a thing. Tricks that introduce a counter which are actively opposed by the people who decide how C++ progresses are still not a stable feature. I mean, I get that you might need code like this, but it is a workaround, and as such a bug. Again, not saying that a bug-free solution with which everyone is content does exist. – Acidimetry

@Aziuth, the solution I've provided leverages standard C++ and works in all mayor compilers. Despite the fact CWG didn't like that thing, it may very well be that they won't be able to make it illegal without breaking other parts of the language that other software relies on without even wanting to make a counter. – Kapp

@Fabio A. We have __FUNC__ which also generates different things. But I have question.. what if we need several counters in same module? And this counter is limited by compile module so if code using it is separated, counter's increment gets broken? Maybe someone didn't liked possibility of similar effects. Or maybe it's related to instantiation of static members of templates. – Zeller

@Swift-FridayPie the approach I described allows for as many counters as needed in the same compilation unit, if that's what you mean with "module". It's a compile-time counter, so it doesn't pass state across compilation units. In that sense you might say "it gets broken", but I'm afraid there's not much that can be done about that. – Kapp

@FabioA Yeah, I meant "unit", module is a translator enemy word. The compilation sequence in standard says about something that implementations are allowed to save information about used instantiations within binary files. Thus some compilers support template methods linked from other units (not from headers). I'm afraid that such implementation (at least older Visual C++) could have units interfere with each other. – Zeller

Just to nitpick: Since Filip Roséen discovered/invented, in 2015 is false, this technique was not discovered nor invented by that person in 2015, as I used it in 2011 and I clearly was not the "inventor" of it. I think you can trace compile-time counters back to 2005 probably... – Ledoux

@Ledoux not to discredit what you wrote, but by googling, I found a post of yours on SO, dated July 2015, in which you expose a completely different technique, which is also non-standard conforming. The Roséen's blog post I linked dates May 2015. Here's your SO post: stackoverflow.com/questions/31720516/… Anything I'm missing? – Kapp

Your sentence is about compile-time counters, whether using preprocessor or contexpr functions; compile-time counters are clearly not new (look at this: stackoverflow.com/questions/6166337/… in 2011...). I'm not sure Roséen's was the first to invente the contexpr side of compile-time counters, so claiming it would be correct only if you can prove it. Besides, Roséen possibly being the first is not interesting for your question... – Ledoux

@Ledoux I will edit my post to make it clear that I was expictly referring to the friend injection technique. I thought it was clear by the rest of the post. Thanks for your remark. – Kapp

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.

Kapp

I think this response kind of closes the topic, but I would still like to know if I'm right in my analysis, therefore I will wait before accepting my own answer as correct, hoping someone else will pass by and give me a better clue or a confirmation. :) – Kapp

While I understand you want to target a broader range of compiler versions and maybe even add some more functionality, using C++20 with the newer compilers allows for a rather elegant solution which might interest you. I've posted it here. – Pavia

godbolt.org/z/xWE5b9Tz4 can you take a look at this? It displays some peculiar behavior. The idea was to probe a variadic set instantiated<I>, instantiated<I + 1>,... instantiated<N> until intantiated<N> is not false. The resulting set of true... is expected be the counter's sum. – Flogging

@SergeyKolesnik the unexpected behavior most likely comes from the fact that the instantiation of the class template specialization instantiated<816, adl> gets done only once in the whole translation unit, hence any subsequent translation unit state change isn't taken into consideration when creating a new object of that type. – Kapp

Yeah, I figured. This can be solved with C++20, and I opened a dedicated question. But there are some comments about odr violation https://mcmap.net/q/25279/-is-it-possible-to-force-template-reevaluation-prior-to-c-20/9363996 – Flogging