Relaxing constraints on constexpr functions

Overview

The features of a programming language are more useful and easy to understand if they are orthogonal, and can be naturally combined with one another. constexpr functions currently carry a number of restrictions which prevent their natural combination with many other language facilities (for instance, for loops, variable modifications, exceptions, and so on), and make them harder to write. Working around these restrictions often requires the sacrifice of expressiveness, and causes programmer frustration.

This paper explores the removal of most of the restrictions on constexpr function definitions, in order to make them a simpler and more uniform extension of runtime C++ code. Idiomatic C++ code would be permitted within constexpr functions, usually with little or no modification from its non-constexpr form other than the addition of the constexpr keyword.

Problem

Prior to N3268, the body of a constexpr function was required to be of the form

{ return expression; }

N3268 loosened up the rules to allow (7.1.5/3):

• null statements,
• static_assert-declarations,
• typedef declarations and alias-declarations that do not define classes or enumerations,
• using-declarations,
• using-directives,
• and exactly one return statement.

These restrictions on constexpr function definitions are still very severe, and the relaxation of the rules has resulted in them becoming harder to teach and to justify. Non-trivial constexpr functions tend to be complex and to use a style of coding which is unfamiliar to many, because code must be contorted to fit within the syntactic constraits, even if it already has a pure functional interface.

Consider std::bitset<N>::all. Here is one possible implementation:

template <size_t N>
bool bitset<N>::all() const noexcept {
  if (std::any_of(storage, storage + num_full_words, [] (word w) { return ~w; }))
    return false;
  if (num_full_words != num_words && storage[num_full_words] != last_word_mask)
    return false;
  return true;
}

This code is simple and idiomatic, and can make use of other library components. However, if we wish to make this function constexpr, we must rewrite it:

constexpr bool any_unset(word *it, word *end) {
  return it == end ? false :
         ~*it ? true :
         any_unset(it + 1, end);
}

template <size_t N>
constexpr bool bitset<N>::all() const noexcept {
  return !any_unset(storage, storage + num_full_words) &&
         (num_full_words == num_words ||
          storage[num_full_words] == last_word_mask);
}

This implementation suffers from several of the constexpr restrictions:

• Most of the algorithms in the standard library cannot be made constexpr, because iterators cannot be incremented in a constexpr function. We are forced to reimplement std::any_of to be constexpr-compatible.
• We cannot pass a lambda to our reimplementation, because lambdas are forbidden in constexpr functions.
• for loops are forbidden, so we must use recursion to walk over the array.
• if is forbidden, so we must use ?:, &&, and || instead.

Alternatives

Discussion at Portland (October 2012) has identified that support for a simple for-loop is a minimum requirement for a satisfactory relaxation of the constexpr rules. This requirement can be attained in a number of ways:

• Addition of a brand new looping construct to the language, which interacts well with the functional programming style required by constexpr. While solving the immediate lack of a looping construct, this does not remove the programmer frustration for existing language constructs.
• Allow a minimal feature set which supports the traditional C for statement. Since we wish for differing iterations of the loop to act differently, we require at least minimal support for mutation of local variables within an evaluated constexpr function. This could be restricted to the syntactic form for (T var = expr1; var != expr2; ++var) for a built-in integral type T.
• Allow a minimal feature set which supports the range-based for statement. An additional mechanism would be required to allow multiple iterations of the loop to communicate with each other. Such a loop could not be used with user-defined iterator types without further relaxing the language rules.
• Allow a coherent and broad subset of C++ to be used in constexpr functions, possibly all of C++.

The first option risks further fracturing the C++ language into a constexpr piece and a "rest of C++" piece. The second and third options both require adding flow control and variable mutation to constant expression evaluation, and would make the restrictions on constexpr functions seem more arbitary than they do today. Therefore we consider the final option in detail, and seek to identify an appropriate subset of C++ which improves simplicity of use without sacrificing simplicity of implementation much beyond that required to support a for-loop.

We must restrict our attention to a subset of C++ which it is reasonable to expect all major implementors to be able to support within constant expressions. Additionally, it is important to maintain a distinction between translation time and runtime, and to avoid permitting constructs which cannot be supported in the translation environment (for instance, there would be significant implementation problems in supporting a new at translation time and a corresponding delete at runtime).

Proposed solution

Promote constexpr to a largely unrestricted compile-time function evaluation mechanism. There is implementation experience of such a mechanism in the D programming language, where it is a popular feature (see the documentation for this feature). The programmer's model would become simple: constexpr allows their code to run during compilation.

Constant expressions

An expression is a constant expression if evaluating it following the rules of the C++ abstract machine succeeds without encountering

• globally-visible side-effects, such as modification of an object of static storage duration (other than the object being constructed, if any);
• expressions which cannot be evaluated during translation, such as dynamic memory allocation, comparisons with unspecified results and lvalue-to-rvalue conversions on objects which are neither constant nor created during the evaluation;
• non-portable constructs, such as an attempt to violate type-safety or to inspect the underlying storage of the abstract machine (for instance, through a reinterpret_cast), or use of inline asm;
• invocation of a function which is not constexpr; or
• undefined behavior.

C++11's function invocation substitution is not needed in this model. constexpr function invocations are instead handled as normal by the C++ abstract machine.

Due to concerns over the simplicity of implementation, the evaluation of a lambda-expression, a throw-expression, and the creation of an object with a non-trivial destructor will continue to render an expression non-constant.

Object mutation within constant expressions

Objects created within a constant expression can be modified within the evalution of that constant expression (including the evaluation of any constexpr function calls it makes), until the evaluation of that constant expression ends, or the lifetime of the object ends, whichever happens sooner. They cannot be modified by later constant expression evaluations. Example:

constexpr int f(int a) {
  int n = a;
  ++n;                  // '++n' is not a constant expression
  return n * a;
}

int k = f(4);           // OK, this is a constant expression.
                        // 'n' in 'f' can be modified because its lifetime
                        // began during the evaluation of the expression.

constexpr int k2 = ++k; // error, not a constant expression, cannot modify
                        // 'k' because its lifetime did not begin within
                        // this expression.

struct X {
  constexpr X() : n(5) {
    n *= 2;             // not a constant expression
  }
  int n;
};
constexpr int g() {
  X x;                  // initialization of 'x' is a constant expression
  return x.n;
}
constexpr int k3 = g(); // OK, this is a constant expression.
                        // 'x.n' can be modified because the lifetime of
                        // 'x' began during the evaluation of 'g()'.

This approach allows arbitrary variable mutations within an evaluation, while still preserving the essential property that constant expression evaluation is independent of the mutable global state of the program. Thus a constant expression evaluates to the same value no matter when it is evaluated, excepting when the value is unspecified (for instance, floating-point calculations can give different results and, with these changes, differing orders of evaluation can also give different results).

The rules for use of objects whose lifetime did not begin within the evaluation are unchanged: they can be read (but not modified) if either:

• they are declared with constexpr, or
• they are const and of integral or unscoped enumeration type.

constexpr functions

As in C++11, the constexpr keyword is used to mark functions which the implementation is required to evaluate during translation, if they are used from a context where a constant expression is required. Any valid C++ code is permitted in constexpr functions, including the creation and modification of local variables, and almost all statements, with the restriction that it must be possible for a constexpr function to be used from within a constant expression. A constant expression may still have side-effects which are local to the evaluation and its result. For instance:

constexpr int min(std::initializer_list<int> xs) {
  int min = std::numeric_limits<int>::max();
  for (int x : xs)
    if (x < min)
      min = x;
  return min;
}

constexpr int fn(int a) {
  return a / (a - a); // ill-formed, no diagnostic required, never constant
}

A handful of syntactic restrictions on constexpr functions are retained:

• asm-declarations are not permitted.
• try-blocks and function-try-blocks are not permitted.
• Declarations of variables with static and thread storage duration have some restrictions (see below).

constexpr constructors

In any constexpr constructor, because the lifetime of the object under construction began during the evaluation of the surrounding constant expression (if any), the constructor and later parts of the evaluation are permitted to modify its fields. Example:

struct lookup_table {
  int value[32];
  constexpr lookup_table() {
    for (int n = 0; n < 32; ++n) {
      double x = n / 4;
      double f = x * std::cbrt(x) * std::pow(2, (n & 3) * 0.25);
      value[n] = (int)(f * 1000000.);
    }
  }
  // OK, would be an error if implicit ~lookup_table was not constexpr.
  constexpr ~lookup_table() = default;
};
constexpr lookup_table table; // OK, table has constant initialization, and
                              // destruction is a constant expression.

struct override_raii {
  constexpr override_raii(int &a, int v) : a(a), old(a) {
    a = v;
  }
  constexpr ~override_raii() {
    a = old;
  }
  int &a, old;
};

constexpr int h(const lookup_table &lut) { /* ... */ }
constexpr int f() {
  lookup_table lut;
  override_raii override(lut.value[4], 123);
  return h(lut);
  // OK, destructor runs here.
}

Block-scope static local variables

If a constexpr function contains a declaration of a variable of static or thread storage duration, some additional restrictions are required to prevent the evaluation from having side-effects.

• Such a variable must be initialized by a constant expression. This prevents the initial value of the variable from depending on the order in which the implementation chooses to evaluate constexpr function calls:

  constexpr int first_val(int n) {
    static int value = n; // error: not a constant expression
    return value;
  }
  const int N = first_val(5);
  int arr[first_val(10)];
    

• The destructor of such a variable must be trivial. This allows an implementation to evaluate a constexpr function call at will, without any concern about whether such evaluation causes a side-effect at program termination.
• Such a variable cannot be modified, even if its lifetime began within the constant expression evaluation.

In all other respects, such static or thread_local variables can be used within constexpr functions in the same ways that they could be used if they were declared outside the function. In particular, they do not need to be constexpr nor have a literal type if their value is not used:

constexpr mutex &get_mutex(bool which) {
  static mutex m1, m2; // non-const, non-literal, ok
  if (which)
    return m1;
  else
    return m2;
}

Possible additional features

Some of the remaining restrictions on constexpr functions and constant expression evaluation could be relaxed, if the value of the language feature within a constant expression is thought to be sufficient to justify the implementation cost:

constexpr destructors

In most cases, in order to create an object of a type T in a constant expression, the destruction of T must be trivial. However, non-trivial destructors are an important component of modern C++, partly due to widespread usage of the RAII idiom, which is also applicable in constexpr evaluations. Non-trivial destructors could be supported in constant expressions, as follows:

• Allow destructors to be marked as constexpr
• Make defaulted destructors constexpr if they only invoke constexpr destructors
• For constexpr variables, require that evaluating the destructor is a constant expression (except that the object being destroyed may be modified in its own destructor

However, no compelling use cases are known for such a feature, and there would be a non-trivial implementation cost ensuring that destructors are run at the right times.

Lambdas

N2859 notes that severe implementation difficulties would arise if lambdas were permitted in contexts which require their contents to be part of a mangled name, and the prohibition on lambdas in constant expressions form part of the resolution to those difficulties. Also, concerns have been raised about the implementation cost of permitting lambdas in constant expressions, so they are not proposed here.

Exceptions

Throwing and catching exceptions within constant expression evalutations is possible to support, but we do not know of a compelling use case for it, so it is not proposed.

Variadic functions

It would be possible to support C-style variadic functions and the va_arg macro within constexpr functions, but this is thought to have little value in the presence of variadic function templates, so is not proposed.

Acknowledgements

The author wishes to thank Bjarne Stroustrup and Gabriel Dos Reis for their encouragement and insights on this proposal, and is also grateful to Lawrence Crowl, Jeffrey Yasskin, Dean Michael Berris, and Geoffrey Romer for their comments and corrections on earlier drafts of this paper.