Non-constant constant expressions

// <some code>

int main ( )
{
constexpr int a = f ( ) ;
constexpr int b = f ( ) ;

static_assert ( a ! = b , "fail" ) ;
}
')
Is it possible to insert such a definition of f () in the above fragment, instead of a comment, so that a gets a value other than b ?

“Of course not!” - you will say, having thought a little. Indeed, both variables are declared with the constexpr qualifier , which means that f () must also be a constexpr -function. Everyone knows that constexpr functions can be executed at compile time, and, as a result, should not depend on the global state of the program or change it (in other words, they should be clean ). Purity means that the function must return the same value for each call with the same arguments. f () is called both times without arguments, so it must return the same value both times, which will be assigned to variables a and b ... correctly?

A week ago, I knew that this was true, and I really thought that it was impossible to pass static_assert in the above fragment, avoiding unspecified behavior.

I was wrong.

Content

• Introduction
• Why would you ever need this?
• Preliminary Information
  
  • Keyword friend
  • Rules for constant expressions
  • Pattern Instance Semantics
• Decision
  
  • Implementation
  • Clarification
• Conclusion
• application
• From translator

Disclaimer: The technique described in this article is positioned as “another cunning hack with immersion in the dark depths of C ++.” I do not recommend anyone to use it in production without first examining all the pitfalls (which will be described in detail in the following articles).

The disclaimer was added after I read on other sites comments on this article, in which I discovered a misunderstanding of its purpose. I do not approve the use of the described technology outside of your bedroom (without taking into account the consequences of such use).

Why would you ever need this?

By solving the problem posed at the beginning of the article, we can successfully add a variable state to the compilation process (in other words, write imperative metaprograms).

Note lane: A reader may argue that imperativeness in a metaprogram can be easily added using variable macro constants as “variables”. So, to solve our problem, you can use #define f () __COUNTER__ or something like that.

Unfortunately, this only works in the simplest cases, since the preprocessor opens macros as soon as it encounters them in the program text, while ignoring the syntactic constructs of the language itself. Therefore, as soon as the order of instantiation of metafunctions becomes nontrivial, or something other than reading and a one-time change of a variable is required, macros are no longer useful in this capacity.

At first glance, this may seem like a small and innocent concept, but the technique described in the article will allow us to solve a number of problems that previously required very complex code or were completely insoluble.

For example:

Compile-time counter

using C1 = ... ;

int constexpr a = C1 :: next ( ) ; // = 1
int constexpr b = C1 :: next ( ) ; // = 2
int constexpr c = C1 :: next ( ) ; // = 3

Compile-time container meta-types

using LX = ... ;

LX :: push < void , void , void , void > ( ) ;
LX :: set < 0 , class Hello > ( ) ;
LX :: set < 2 , class World > ( ) ;
LX :: pop ( ) ;

LX :: value <> x ; // type_list <class Hello, void, class World>

Other ideas

• How do I know if a template has already been instantiated with certain parameters?
• How to get the address of exactly the function that will be called after overload resolution?
• How to add a reflection in C ++?

Preliminary Information

Note: This part describes in detail the technical aspects related to the solution of the problem. So the most experienced (or impatient) readers can skip it. If you are only here for snacks, go straight to the solution .

Note: It is recommended to skim through this part at least if you are wondering exactly how and why the solution code works (and is legal from the point of view of the standard).

Keyword friend

Friendship in C ++ can be used not only to simply provide another entity with access to its private and protected members. Consider the following (very simple) example:

class A ;
void touch ( A & ) ;

class A
{
friend void touch ( A & ) ;
int member ;
} ;

void touch ( A & ref )
{
ref. member = 123 ; // OK, `void touch (A &)` is another class A
}

int main ( )
{
A a ; a. member = 123 ; // Incorrectly, the member `A :: member` is private
A b ; touch ( b ) ;
}

First, we declare the void touch (A &) function in the global scope, then we declare it to be class A- friendly , and finally, we define it in the global scope.

With the same success, we can place the combined declaration and definition of void touch (A &) directly inside class A , without changing anything else - as in the following example:

class A
{
friend void touch ( A & ref )
{
ref. member = 123 ;
}

int member ;
} ;

int main ( )
{
A b ; touch ( b ) ; // OK
}

It is very important that these two approaches to using a friend are not completely equivalent (although in this particular case it may seem like this).

In the last example, void touch (A &) will be implicitly placed in the scope of the next enclosing namespace for class A , but access to it will be possible only through a Koenig search (ADL).

class A
{
public :
A ( int ) ;

friend void touch ( A ) { ... }
} ;

int main ( )
{
A b = 0 ; touch ( b ) ; // OK, `void touch (A)` will be found via ADL
touch ( 0 ) ; // Incorrect, the argument type is `int`, and ADL will not look at the class` A`
}

The following excerpt from the standard repeats the above, but I want you to concentrate on what is written between the lines (because it is equally important):

7.3.1.2/3 Definitions of members of namespaces [namespace.memdef] p3

Each name first declared within a namespace is a member of that namespace. If a friend- declaration inside a non-local class declares a class, function, class template, or function template for the first time, they become members of the nearest enclosing namespace. The friend itself does not make the name visible for unqualified (3.4.1) or qualified (3.4.3) name searching.

Please note that it is not stated anywhere that the name entered by a friend ad must have something to do with the name of the class in which the ad is located, and indeed any relation to that class, for that matter.

#include <iostream>

class A
{
public :
A ( int ) { }
friend void f ( A ) ;
} ;

void g ( A ) ;

class B
{
friend void f ( A )
{
std :: cout << "hello world!" << std :: endl ;
}

class C
{
friend void g ( A )
{
std :: cout << "! dlrow olleh" << std :: endl ;
}
} ;
} ;

int main ( )
{
A a ( 0 ) ;
f ( a ) ;
g ( 1 ) ;
}

So, f () has nothing to do with class B , except for the fact that it is defined as a friend right inside it, and such code is absolutely correct.

Note: This reasoning may seem rather trivial, but if you have doubts about what is happening, I urge you to uncover some compiler and play around with the following snippets.

Rules for constant expressions

There are a large number of rules related to constexpr , and this introduction could be made more rigorous and detailed, but I will be brief:

• A literal is a type that can have constexpr -variables and values ​​returned by constexpr -functions. These types are: scalar types (arithmetic types, pointers and enumerations), reference types and some others. In addition, classes that satisfy certain constraints ( constexpr -constructor , trivial destructor, types of all data members, and base classes are literal) are also literal types;
• A variable declared with the constexpr qualifier must be of a literal type and immediately be initialized with a constant expression ;
• A function declared with the constexpr qualifier must take as parameters and return only literal types, and also must not contain constructs that are not allowed in constant expressions (for example, calls to non- constexpr functions).
• A constant is an expression in which they do not occur:
  • Calls are not constexpr -functions;
    
  • Calls to functions that are not yet defined;
    
  • Calls to functions with arguments that are not constant expressions;
    
  • Calls to variables that were not initialized by constant expressions and began to exist before the start of the calculation of the current constant expression;
    
  • Constructs causing undefined behavior;
    
  • Lambda expressions, excitation exceptions and some other constructions.
    

Note: This list is incomplete and lax, but it gives an idea of ​​how constexpr- entities and constant expressions behave in most cases.

Instead of a deep study of all aspects of working with constant expressions, we will focus on a rule that requires that constant expressions do not contain calls to functions that are not yet defined at the time of the call.

constexpr int f ( ) ;
void indirection ( ) ;

int main ( )
{
constexpr int n = f ( ) ; // Incorrect, `int f ()` not yet defined
indirection ( ) ;
}

constexpr int f ( )
{
return 0 ;
}

void indirection ( )
{
constexpr int n = f ( ) ; // OK
}

Here the constexpr int f () function is declared but not defined in main , but it has a definition inside indirection (since by the time the body started, the definition of indirection has already been provided). Therefore, inside indirection, the constexpr call to the f () function is a constant expression, and the initialization n is correct.

How to check that the expression is constant

There are several ways to check if a given expression is constant , but some of them are more difficult to implement than others.

An experienced C ++ developer will immediately see here the opportunity to successfully apply the SFINAE (Substitution Failure Is Not An Error) concept and will be right; but the power that SFINAE provides is accompanied by the need to write fairly complex code.

Note lane:

For example, such

constexpr int x = 7 ;

template < typename >
std :: false_type isConstexpr ( ... ) ;

template < typename T , T test = ( 15 * 25 - x ) > // Test expression
std :: true_type isConstexpr ( T * ) ;

constexpr bool value = std :: is_same < decltype ( isConstexpr < int > ( nullptr ) ) , std :: true_type > :: value ; // true

It is much easier to use the noexcept operator to solve our problem. This statement returns true for expressions that cannot raise exceptions, and false otherwise. In particular, all constant expressions are considered not throwing exceptions. On this we will play.

constexpr int f ( ) ;
void indirection ( ) ;

int main ( )
{
// `f ()` is not a constant expression,
// no definition yet

constexpr bool b = noexcept ( f ( ) ) ; // false
}

constexpr int f ( )
{
return 0 ;
}

void indirection ( )
{
// Now is

constexpr bool b = noexcept ( f ( ) ) ; // true
}

Note: currently clang contains a bug , due to which noexcept does not return true , even if the expression being tested is constant. A workaround can be found in the appendix to this article.

Pattern Instance Semantics

If there is a part in the C ++ standard that challenges most programmers to a real challenge, it is undoubtedly related to templates. If I decided to consider every aspect of instantiating templates here, the article would have grown enormously and you would be stuck reading it for at least a few hours.

Since this is not what we are striving for, I will instead try to talk only about the fundamental principles of instantiation that will be needed to understand how the solution of our problem will work.

Note: Note that the contents of this section are not a complete reference for instantiating templates. There are exceptions to the rules mentioned in it, besides, I deliberately omitted some facts that go too far beyond the scope of the article.

Basic principles

The following is a brief list of principles that are directly related to our task:

• A template specialization (both a class and a function) can be implicitly instantiated only if it has not previously been explicitly instantiated, and the user has not provided the corresponding full specialization.
• The specialization of the function template will be implicitly instantiated if it is mentioned in a context that requires its definition , and the first item is fulfilled.
• The specialization of a class template will be implicitly instantiated if it is mentioned in a context that requires a completely defined (complete) type, or in the case when this completeness affects the semantics of the program, and (in both cases) the first item is executed.
• Instantiating a class template causes an implicit instantiation of the declarations of all its members, but not their definitions , unless the member is:
  • A static variable member, in which case the declaration is also not instantiated, or;
  • By enumeration with no scope or anonymous union, in which case both the declaration and the definition will be instantiated.
• Member definitions will be implicitly instantiated when requested, but not before.
• If the class template specialization contains friend declarations, the names of these friends are considered further as if their explicit specializations were placed at the point of instantiation.

Instantiation points

Whenever the context in which the specialization of a template of a class or function is mentioned requires its instantiation, a so-called point of instantiation (which actually defines one of the places where the compiler may be located at the moment of specialization code generation from the generalized template code).

In the case of nested templates, when the specialization X of an internal template is referred to in a context depending on the parameters of the external template Y , the instantiation point of this specialization will depend on the corresponding point for the external template:

• If X is a specialization of a function template, the point of instantiation will be the same as the point of instantiation Y.
• If X is a class template specialization, the instantiation point will be immediately before the Y instantiation point.

If there are no nested templates, or the context does not depend on the parameters of the external template, the instantiation point will be tied to the D point of the declaration / definition of the “most global” entity, within which the X specialization was mentioned:

• If X is a specialization of the function template, the instantiation point will be immediately after D.
• If X is a class template specialization, the instantiation point will be immediately before D.

Generating function template specialization

A function template specialization can have any number of instantiation points, but the expressions inside it should have the same meaning regardless of which instantiation point the compiler chooses to generate code (otherwise the program is considered incorrect).

For simplicity, the C ++ standard prescribes that any instantiated specialization of a function template has an additional instantiation point at the end of a translation unit :

namespace N
{
struct X { / * Specially left blank * / } ;

void func ( X , int ) ;
}

template < typename T >
void call_func ( T val )
{
func ( val , 3.14f ) ;
}

int main ( )
{
call_func ( N :: X { } ) ;
}

// First instantiation point

namespace N
{
float func ( x , float ) ;
}

// Second instantiation point

In this example, we have two instantiation points for the void call_func <N :: X> function (N :: X) . The first is immediately after the definition of main (because call_func is called inside it), and the second is at the end of the file.

The given example is incorrect due to the fact that the behavior of call_func <N :: X> changes depending on which of them the compiler generates specialization code:

• At the first point, call_func will call func (X, int) , because there are no other overloads at this moment.
• At the second point, call_func will call func (X, float) already declared by this moment, as the most suitable of all available overloads.

Generating class template specialization

For the specialization of a class template, all instances of instantiation, except the first, are ignored. This actually means that the compiler must generate the specialization code at the time of its first mention in the context that requires instantiation.

namespace N
{
struct X { / * Specially left blank * / } ;

void func ( X , int ) ;
}

template < typename T > struct A { using type = decltype ( func ( T { } , 3.14f ) ) ; } ;
template < typename T > struct B { using type = decltype ( func ( T { } , 3.14f ) ) ; } ;

// Instantiation Point A

int main ( )
{
A < N :: X > a ;
}

namespace N
{
float func ( x , float ) ;
}

// Instantiation Point B

void g ( )
{
A < N :: X > :: type a ; // Incorrect, type will be `void`
B < N :: X > :: type b ; // OK, type will be `float`
}

Here the instantiation point A <N :: X> will be immediately before main , while the instantiation point B <N :: X> will be just before g .

Putting it all together

The rules associated with friend declarations within class templates state that in the following example, the definitions of func (short) and func (float) are generated and placed at the instantiation points, respectively, of the specializations A <short> and A <float> .

constexpr int func ( short ) ;
constexpr int func ( float ) ;

template < typename T >
struct A
{
friend constexpr int func ( T ) { return 0 ; }
} ;

template < typename T >
A < T > indirection ( )
{
return { } ;
}

// (one)

int main ( )
{
indirection < short > ( ) ; // (2)
indirection < float > ( ) ; // (3)
}

When a calculated expression contains a call to the specialization of a function template, the return type of this specialization must be fully defined. Therefore, calls in lines (2) and (3) entail implicit instantiation of specializations A, along with specializations of indirection in front of their instantiation points (which, in turn, are in front of the main ).

It is important that before reaching lines (2) and (3) the functions func (short) and func (float) are declared but not defined . When the achievement of these lines causes the A specializations to be instantiated, the definitions of these functions will appear, but will not be located next to these lines, but at (1).

Decision

I hope that the preliminary information sufficiently discloses all aspects of the language that are used in the solution given in this section.

Just in case, let me remind you that in order to fully understand how and why the solution works, you should be aware of the following aspects:

• Keyword friend , and;
• Rules for constant expressions, and;
• The semantics of instantiating templates.

Implementation

constexpr int flag ( int ) ;

template < typename Tag >
struct writer
{
friend constexpr int flag ( Tag )
{
return 0 ;
}
} ;

template < bool B , typename Tag = int >
struct dependent_writer : writer < Tag > { } ;

template <
bool B = noexcept ( flag ( 0 ) ) ,
int = sizeof ( dependent_writer < B > )
>
constexpr int f ( )
{
return B ;
}

int main ( )
{
constexpr int a = f ( ) ;
constexpr int b = f ( ) ;

static_assert ( a ! = b , "fail" ) ;
}

Note: clang demonstrates incorrect behavior with this code, a workaround is available in the application .

Note Trans: Visual cues in Visual Studio 2015 also “do not notice” the changes in f () . However, after compilation, the values ​​of a and b are different.

But how does this work?

If you have read the preliminary information , an understanding of the above solution should not cause you any difficulties, but even in this case, a detailed explanation of the principles of operation of its various parts may be of interest.

In this section, the source code is analyzed step by step and a brief description and justification is given for each of its fragments.

"Variable"

At each point of the program, the constexpr function can be in one of two states: either it is already defined and can be called from constant expressions, or not. Only one of these two situations is possible (unless unspecified behavior is allowed).

Usually, constexpr functions are considered and used exactly as functions, but thanks to the above, we can think of them as “variables” that have a type similar to bool . Each such “variable” is in one of two states: “defined” or “undefined”.

constexpr int flag ( int ) ;

In our program, the flag function is just a similar trigger. We will not call it as a function anywhere, being interested only in its current state as a “variable”.

Modifier

writer is a class template that, when instantiated, creates a definition for a function in its enclosing namespace (in our case, global). The Tag template parameter defines a specific function signature, whose definition will be created:

template < typename Tag >
struct writer
{
friend constexpr int flag ( Tag )
{
return 0 ;
}
} ;

If we, as we were going to, consider constexpr functions as “variables,” instantiating a writer with a template argument T will cause the unconditional translation of the “variable” with the signature int func (T) to the “defined” position.

Proxy

template < bool B , typename Tag = int >
struct dependent_writer : writer < Tag > { } ;

I'm not surprised if you decided that dependent_writer looks like a meaningless layer adding indirectness. Why not directly instantiate writer <Tag> where we want to change the value of a “variable” instead of accessing it via dependent_writer ?

The fact is that a direct reference to writer <int> does not guarantee that the first argument of the function template f will be calculated before the second (and the function on the first call will have time to “remember” that you need to return false , and only then change the value of “variable”) .

To set the order we need for calculating template arguments, we can add an additional dependency using dependent_writer . The first template argument, dependent_writer, must be evaluated before it is instantiated, and therefore, before the writer itself is instantiated. Therefore, by passing B to dependent_writer as an argument, we can be sure that by the time instantiation of the writer , the value returned by the f function will already be calculated.

Note: When writing the implementation, I considered many alternatives, trying to find the most simple to understand. I sincerely hope that this fragment has turned out not too confusing.

Magic

template <
bool B = noexcept ( flag ( 0 ) ) , // (1)
int = sizeof ( dependent_writer < B > ) // (2)
>
constexpr int f ( )
{
return B ;
}

This fragment may seem a bit strange, but in fact it is very simple:

• (1) sets B to true if flag (0) is a constant expression, and false to false if not;
• (2) implicitly instantiate dependent_writer <B> ( sizeof operator requires a completely specific type). At the same time, writer <B> is instantiated, which, in turn, causes the generation of the definition of int flag (int) and a change in the state of our “variable”.

Behavior can be expressed by the following pseudocode:

 [ `int flag (int)`    ]:  `B` = `false`  `dependent_writer <false>`  `B` :  `B` = `true`  `dependent_writer <true>`  `B` 

Thus, the first time f is called, the template argument B will be false , but a side effect of calling f will be changing the state of the “variable” flag (generating and placing its definition in front of the main body). With further calls to f, the “variable” flag will already be in the “determined” state, so B will be equal to true .

Conclusion

The fact that people continue to discover crazy ways to do new things with C ++ (which were previously considered impossible) is both amazing and terrible. - Maurice Bos

This article explains the basic idea that allows you to add a state to constant expressions. In other words, the generally accepted theory (to which I myself often referred) that constant expressions are “constant” has now been destroyed.

Note Per: In my opinion, “destroyed” is an excessively strong word. All the same, despite the identity of the names, the solution invokes two different specializations of the template function f () , each of which is fully “constant”. Of course, this does not detract from the overall usefulness of the idea.

While writing this article, I could not help but think about the history of template metaprogramming and how strange it is that the language allows you to do more than you ever intended to do with it.
What's next?

I wrote a library for imperative template metaprogramming called smeta , which will be published, explained and discussed in upcoming articles. Among the topics that will be covered:

• How to implement a compile-time counter
• How to implement compile-time meta-type container
• How to check and manage overload permissions
• How to add reflection in C ++

Note Lane: The author reports that he decided to cancel the release of smeta , since This and the following articles contain (or will contain) almost all of its features, and, therefore, the reader’s self-realization of its functionality will be almost trivial for yourself. For example, I have already (contrary to Philip's warning, aha) introduced some ideas and are going to gather them into something like a library in perspective.

application

Because of this (and its associated) bug in a clang , the above solution causes the program to behave incorrectly when properly implemented. Below is an alternative implementation of the solution, written specifically for clang (which is still the correct C ++ code and can be used with any compilers, although it is somewhat complicated).

namespace detail
{
struct A
{
constexpr A ( ) { }
friend constexpr int adl_flag ( A ) ;
} ;

template < typename Tag >
struct writer
{
friend constexpr int adl_flag ( Tag )
{
return 0 ;
}
} ;
}

template < typename Tag , int = adl_flag ( Tag { } ) >
constexpr bool is_flag_usable ( int )
{
return true ;
}

template < typename Tag >
constexpr bool is_flag_usable ( ... )
{
return false ;
}

template < bool B , class Tag = detail :: A >
struct dependent_writer : detail :: writer < Tag > { } ;

template <
class Tag = detail :: A ,
bool B = is_flag_usable < Tag > ( 0 ) ,
int = sizeof ( dependent_writer < B > )
>
constexpr int f ( )
{
return B ;
}

int main ( )
{
constexpr int a = f ( ) ;
constexpr int b = f ( ) ;

static_assert ( a ! = b , "fail" ) ;
}

Note: I am currently writing relevant bug reports that will show why this workaround solution works in clang . Links to them will be added as soon as the reports are submitted (so far everything is dull - approx. Lane ).

From translator

I came across this article about a month ago and was impressed by the terrible indecencies by the grace of the idea of ​​adding to the metaprogramming on templates, by its nature, a functional dependence on the global state. The author of the article, Philip Roseen - a developer, musician, model and just a good person - kindly allowed me to translate it into Russian.

This article is the first in a series of articles on imperative metaprogramming, which develop the idea of ​​non-constant constexpr 's (whose immediate applicability is very limited in practice) before implementing constructs that can make real metaprogramming much more convenient.

I am going to soon translate the two remaining articles (on the compile-time counter and on the meta-type container). In addition, Philip said that in the foreseeable future, he will continue the series and develop ideas further (then, of course, there will be new translations).

Corrections, additions, suggestions are welcome. You can also write to Philip himself, I think he will be happy for any comments.