CODEWITHSUNDEEP
c++templatestemplate-meta-programming
user2338150
user2338150

Reputation: 485

Bypass template argument integer limit

I am trying to start with template meta-programming. I wrote simple construct like this:

template<int N>
class Fact {
  public:
    enum { result = N * Fact<N-1>::result };
};

template<>
class Fact<0> {
  public:
    enum { result = 1 };
};

When I tried to call it in main like:

int main() {
    Fact<5> f;
    std::cout << f.result;
}

It works fine for smaller values of parameter. As soon as I provide bigger values like say, 15, then compiler complains: integer overflow in constant expression. It appears truncation is not implicitly done by the compiler. If I revert back to smaller values and I get code to compile, then I still get warning: variable set but unused. Why?

Now, I made more changes to this code like:

template<int N>
class Fact {
  public:
    static long result;
};

template<>
class Fact<0> {
  public:
    static long result;
};

long Fact<0>::result = 1;
template<int N>
long Fact<N>::result = N * Fact<N-1>::result;

At this point the warning is gone, and it also seems to allow integer wrapping. I can't understand why this happens. I tried to write a vanilla class like:

class X{
public:
    static int d;
    enum { r = 10000000000000000l };
};

int X::d = 50;

And when I used it I still got the unused warning, and the enum also compiles. Could someone help me understand at what point in compilation stage, does template deduction happen? Why am I able to bypass compiler checks which were in place during the first case? Thanks!

Upvotes: 0

Views: 470

Answers (2)

armagedescu
armagedescu

Reputation: 2158

Instead of int or long you can use the type long long.

class Fact {
public:
    enum: long long { result = N * Fact<N - 1>::result };
};

template<>
class Fact<0> {
public:
    enum : long long { result = 1 };
};

But even long long can be overflown. In assembler there is an overflow flag. But in C++ you can use a trick, if the result is smaller than initial value then an overflown occurred during addition or multiplication.

Upvotes: 0

Miles Budnek
Miles Budnek

Reputation: 30579

In your first example, the underlying type of Fact<0>::result is int. Since your base template's N argument is also an int, the result of N * Fact<N-1>::result is also int. That means that at N = 13, the result of N * Fact<N-1>::result will overflow a 4-byte int. Signed integer overflow is undefined behavior. Named enum values are compile-time constants, and undefined behavior in compile-time constant expressions is not allowed, so you get a hard error.

In your second example not only are you using long, which could potentially have a larger range than int, but long Fact<N>::result = N * Fact<N-1>::result; is not a compile-time constant expression. That means that any potential undefined behavior goes undetected at compile time. The behavior of your program is still undefined though.

The idiomatic way to make a compile-time factorial in modern C++ would be to use constexpr variables rather than unscoped enums:

template<unsigned long N>
struct Fact {
    static constexpr unsigned long result = N * Fact<N-1>::result;
};

template<>
struct Fact<0> {
    static constexpr unsigned long result = 1;
};

Or a constexpr function:

constexpr unsigned long fact(unsigned long n)
{
    unsigned long ret = 1;
    for (unsigned long i = 1; i <= n; ++i) {
        ret *= i;
    }
    return ret;
}

To keep the behavior well-defined in the face of overflow, I've made the result members unsigned.

If you really need to keep compatibility with older compilers, you could add another member to your unscoped enum that's large enough to force its underlying type to be unsigned long:

template<unsigned long N>
struct Fact {
    enum {
        result = N * Fact<N-1>::result,
        placeholder = ULONG_MAX
    };
};

template<>
struct Fact<0> {
    enum {
        result = 1,
        placeholder = ULONG_MAX
    };
};

Note that I used ULONG_MAX instead of std::numeric_limits<unsigned long>::max() since the latter is only a compile-time constant expression in C++11 or later, and the only reason I can think of to use this approach is to maintain compatibility with pre-C++11 compilers.

Upvotes: 1

Related Questions