C++ code with undefined behavior, compiler generates std::exception

Question

I came across an interesting secure coding rule in C++ which states:

Do not reenter a function during the initialization of a static variable declaration. If a function is reentered during the constant initialization of a static object inside that function, the behavior of the program is undefined. Infinite recursion is not required to trigger undefined behavior, the function need only recur once as part of the initialization.

The non_compliant example of the same is:

#include <stdexcept>

int fact(int i) noexcept(false) {
  if (i < 0) {
    // Negative factorials are undefined.
    throw std::domain_error("i must be >= 0");
  }

  static const int cache[] = {
    fact(0), fact(1), fact(2), fact(3), fact(4), fact(5),
    fact(6), fact(7), fact(8), fact(9), fact(10), fact(11),
    fact(12), fact(13), fact(14), fact(15), fact(16)
  };

  if (i < (sizeof(cache) / sizeof(int))) {
    return cache[i];
  }

  return i > 0 ? i * fact(i - 1) : 1;
}

which according to the source gives the error:

terminate called after throwing an instance of '__gnu_cxx::recursive_init_error'
  what():  std::exception

when executed in Visual Studio 2013. I tried similar code of my own and got the same error (compiled using g++ and executed, on Ubuntu).

I am doubtful if my understanding is correct with respect to this concept as I am not well-versed with C++. According to me, since the cache array is constant, which means it can be read-only and needs to be initialized only once as static, it is getting initialized again and again as the values for this array is the value returned by each of the comma-separated recursive function calls which is against the behavior of the declared array. Thus, it gives undefined behavior which is also stated in the rule.

What is a better explanation for this?

Answer 1

In order to execute fact(), you need to first statically initialize fact::cache[]. In order to initially fact::cache, you need to execute fact(). There's a circular dependency there, which leads to the behavior you see. cache will only be initialized once, but it requires itself to be initialized in order to initialize itself. Even typing this makes my head spin.

The right way to introduce a cache table like this is to separate it into a different function:

int fact(int i) noexcept(false) {
  if (i < 0) {
    // Negative factorials are undefined.
    throw std::domain_error("i must be >= 0");
  }

  return i > 0 ? i * fact(i - 1) : 1;
} 

int memo_fact(int i) noexcept(false) {
  static const int cache[] = {
    fact(0), fact(1), fact(2), fact(3), fact(4), fact(5),
    fact(6), fact(7), fact(8), fact(9), fact(10), fact(11),
    fact(12), fact(13), fact(14), fact(15), fact(16)
  };

  if (i < (sizeof(cache) / sizeof(int))) {
    return cache[i];
  }
  else {
    return fact(i);
  }    
} 

Here, memo_fact::cache[] will only be initialized once - but its initialization is no longer dependent on itself. So we have no issue.