Possible to instantiate templates using a for loop in a C++14 constexpr function?

Question

I've been messing around with an SVN build of clang to experiment with the relaxed rules for constexpr. One of the things I've been unable to determine as of yet is whether it's possible to loop through the elements inside a tuple at compile-time in a constexpr function.

Because I don't have a C++14 compliant standard library to test on, I've prepared the following equivalent test:

template<int N>
constexpr int foo() {
  return N;
}

constexpr int getSum() {
  auto sum = 0;
  for (auto i = 0; i < 10; ++i) {
    sum += foo<i>();
  }
  return sum;
}

constexpr auto sum = getSum();

The interesting part here is foo<i>(). In a non-constexpr function I would expect this to fail to compile, because you simply cannot use a runtime int to generate a compile-time instantiation of a template. Because this is a constexpr function, however, I question whether this would be possible. In particular, the value is known at compile-time, even if it is allowed to mutate.

I know that the following code will compile:

constexpr auto nValue = 2;
foo<nValue>();

In SVN clang, my first example does not:

test2.cpp:19:12: error: no matching function for call to 'foo'
    sum += foo();
           ^~~~~~
test2.cpp:11:15: note: candidate template ignored: invalid explicitly-specified
      argument for template parameter 'N'
constexpr int foo() {
              ^

For starters, I struggle to interpret the second part of this error message. That aside, is it mandated by the C++14 standard, and if so, does anyone know why this syntax wouldn't be allowed (simple oversight or to protect against something)?

Answer 1

This might be too late for you, but it might be useful for everybody else finding this SO so therefore here is my answer.

@Rapptz answer is not wrong, but the answer to your question might be 'yes'. Yes, the for loop can't be used as discussed. However you want to iterate over the loop, doesn't have to be with a for loop mindset, for example with recursion it's possible. It's uglier, but for some users to get something heavy from runtime (which shouldn't be in runtime) to compile-time might be worth it. For some the added ugliness might not be worth sacrificing the code cleanliness, so that's up to everybody to decide, I just want to show that it's possible. The embedded domain where there are tight constraints on resources might worth consideration. With this recursion you can describe many algorithms, you could probably do tail + head like prolog and process one entry at the time, or copy arrays and change once entry in it at the time (poor man's template-centric concatenation without changing the size of the return type). Just there is one limitation, at compile time the 'if' condition for the end of the loop will not be seen. So typical algorithm like this:

template<int input>
int factorialTemplateSimpler() {
    if (input < 2) {
        return 1;
    } else {
        return factorialTemplateSimpler<input-1>() * input;
    }
}

Wouldn't compile as the toolchain would keep decrementing until it would be terminated (probably after 1000 recursions). For the templates to see the end-state you have to explicitly state it like this:

https://godbolt.org/z/d4aKMjqx3

template<int N>
constexpr int foo() {
  return N;
}

const int maxLoopIndex = 10;

template<int loopIndex>
constexpr int getSum() {
  return foo<loopIndex>() + getSum<loopIndex + 1>();
}

template<>
constexpr int getSum<maxLoopIndex>() {
  return 0;
}

int main() {
    constexpr auto sum = getSum<0>();
    return sum;
}

This does what you want, it compiles with C++14, and not sure why it compiles with C++11 too.

Many algorithms have a special case to do something special from the typical algorithm and you have to make a separate implementation for it (as the if will not be seen when instantiating). And you have to end the loop somewhere as well, so then you have to implement separate the exit case. To save you extra typing, it would be best to have the exit case and special case at the same index, so you do not have to create a duplicate implementation and increase maintenance. Therefore you have to decide if it's better to count in an incrementing or decrementing fashion. So you will then have to only implement the combined special and exit case once. To put it into a context, for something like factorial I would decrement so then the 0-case and end of the loop would be implemented with the same code, and then let the algorithm do the work as it's returning from the deep recursion.

If you do not have any special case and you have to make one special case, for example in the code above, I knew it's safe to return 0 and I knew when you are counting up to 10 but not including it, therefore I made the special case at index 10 and returned 0.

template<>
constexpr int getSum<maxLoopIndex>() {
  return 0;
}

If that trick is not possible for you, then you have to implement a subset of the algorithm (without the recursion) but stop at index 9 like this:

template<>
constexpr int getSum<maxLoopIndex-1>() {
  return foo<maxLoopIndex-1>();
}

Note: You can use const variables and equations as long as they are in the compile time.

Full example:

https://godbolt.org/z/eMc93MvW8

template<int N>
constexpr int foo() {
  return N;
}

const int maxLoopIndex = 10;

template<int loopIndex>
constexpr int getSum() {
  return foo<loopIndex>() + getSum<loopIndex + 1>();
}

template<>
constexpr int getSum<maxLoopIndex-1>() {
  return foo<maxLoopIndex-1>();
}

int main() {
    constexpr auto sum = getSum<0>();
    return sum;
}

Here is an example where it's decrementing to make something easier on you (the end case is at 0):

https://godbolt.org/z/xfzcGMrcq

template<int N>
constexpr int foo() {
  return N;
}

template<int index>
constexpr int getSum() {
  return foo<index>() + getSum<index-1>();
}

template<>
constexpr int getSum<0>() {
  return foo<0>();
}

int main() {
    constexpr auto sum = getSum<10 - 1>();  // loop 0..9
    return sum;
}

If you would enable C++20 then I got it even to populate at compile time a lookup table with function pointers to your foo instances just to demonstrate that there are a lot of possibilities that can be done at compile time. Full example:

https://godbolt.org/z/c3febn36v

template<int N>
constexpr int foo() {
  return N;
}

const int lookupTableSize = 10;

template <int lookupIndex>
constexpr std::array<int(*)(), lookupTableSize> populateLookupTable() {
    auto result = populateLookupTable<lookupIndex - 1>();
    result[lookupIndex] = foo<lookupIndex>;

    return result;
}


template <>
constexpr std::array<int(*)(), lookupTableSize> populateLookupTable<0>() {
    std::array<int(*)(), lookupTableSize> lookupTable;
    lookupTable[0] = foo<0>;
    return lookupTable;
}


const auto lookupTable = populateLookupTable<lookupTableSize - 1>();

int main() {
    return lookupTable[2]();
}

Another example here is to populate cos lookup table:

https://godbolt.org/z/ETPvx4nex

#include <cmath>
#include <array>
#include <cstdint>
#include <algorithm>

const int lookupTableSize = 32;

template <int lookupIndex>
constexpr std::array<int8_t, lookupTableSize> populateLookupTable() {
    auto previousResult = populateLookupTable<lookupIndex + 1>();

    auto pi = acosf(-1);
    auto inRadians = (((float)lookupIndex)/lookupTableSize) * 2 * pi;
    previousResult[lookupIndex] = 127 * std::clamp(cosf(inRadians), -1.0f, 1.0f);

    return previousResult;
}


template <>
constexpr std::array<int8_t, lookupTableSize> populateLookupTable<lookupTableSize>() {
    return { 0 };
}


const auto lookupTable = populateLookupTable<0>();

int main() {
    return lookupTable[2];
}

Answer 2

That aside, is it mandated by the C++14 standard, and if so, does anyone know why this syntax wouldn't be allowed (simple oversight or to protect against something)?

That's because constexpr is not exclusive to compile-time computations or usage. A constexpr function is just that, allowing a function (or variable) to be used in a constant expression. Outside of that, they're regular functions. A constant expression just so happens to be required in certain contexts such as static_assert or array sizes, etc that are compile-time only situations.

You'll notice in your code that you loop through a variable but the variable you're looping through itself isn't constexpr so it isn't a constant expression to be used in that template instantiation of N. As it stands, it's no different than doing this in C++11:

constexpr bool f(int x) {
    static_assert(x > 10, "..."); // invalid
    return true;
}

Which is obviously invalid because as I mentioned earlier, you don't have to use constexpr functions in exclusive compile-time situations. For example, nothing is stopping you from doing this:

constexpr int times_ten(int x) {
    return x * 10;
}

int main() {
   int a = times_ten(20); // notice, not constexpr
   static_assert(times_ten(20) == 200, "...");
   static_assert(a == 200, "..."); // doesn't compile
}