How to implement a compile-time meta-container in C++

Created	Mon, 28 May 2015 22:03:12 +0200
Modified	Wed, 2 Mar 2022 06:55:49 +0100
Tags	c++, c++14, constant-expression, stateful meta-programming

Disclaimer: The technique described in this post is primarily meant as "just another clever hack, diving into the dark corners of C++". I do not recommend anyone to incorporate the contents of this post into production code without considering its caveats.

Note: The technique described in this post requires a compiler with support for C++14.

Introduction

The previous post provided an implementation of a counter that is usable in constant-expressions. It may not look like much on its own, but the proof-of-concept shows that we can reliably change and monitor the global state during the phase of translation.

The described technique solved the following challenge:

// <insert solution>

int main () {
  constexpr int a = next ();
  constexpr int b = next ();
  constexpr int c = next ();

  static_assert (a == 1 && b == a+1 && c == b+1, "try again");
}

So, what now?

Even though the previous accomplishments are a tremendous step towards an easier way to represent complex meta-programs, there are still a few more quirks that we would like to overcome in order to make the technique useful in practice.

This post will provide a proof-of-concept — together with an explanation — of the necessities required to turn the below snippet into reality.

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>

What about smeta?

I have decided not to release smeta — the stateful meta-programming library mentioned in previous posts — at the current time. There are many reasons behind this decision, but primarily the implementation presented in this post is far easier to understand.

The implementation provided at the end of this post supports a limited subset of smeta, increasing its usability — a very trivial process — will, until otherwise noted, be left as an exercise for the reader.

Table of Contents

• Introduction
• Prerequisites
  • The semantics of alias-declarations
  • The semantics of returning auto
• Solution
  • Implementation
  • Elaboration
• Caveats
• Conclusion
  • What is going on in WG21?
  • What's next?
• Appendix
  • Bug in gcc related to friend-declarations and auto
  • Workaround for vc++

Prerequisites

In order to fully grasp the contents of this post one must fully understand;

• the contents of Non-constant constant-expressions in C++,
• the contents of How to implement a constant-expression counter in C++,
• the semantics of alias-declarations, and;
• the semantics of returning auto.

Notes

• This section is meant to be a somewhat detailed technical introduction to the latter two topics.
• It is recommended to at least skim the contents of the previous two posts prior to digging into what follows.
• Experienced, or eager, readers might want to skip directly to the solution — if anything is unclear, please refer back to this section.

The semantics of alias-declarations

We have always been able to alias the name of a type using a typedef-declaration, and the feature of alias-declarations (introduced in C++11) follow the same semantics — only through a different kind of syntax.

7.1.3/2 The typedef specifier [dcl.typedef]p2

A typedef-name can also be introduced by an alias-declaration. The identifier following the using keyword becomes a typedef-name and the optional attribute-specifier-seq following the identifier appertains to that typedef-name.

It has the same semantics as if it were introduced by the typedef specifier. In particular, it does not define a new type and it shall not appear in the type-id.

The below two statements are directly equivalent to each other; both declare an alias, callback_t, for the pointer-to-function type void(*)(int, float).

typedef void(*callback_t)(int, float);  // (1)

using callback_t = void(*)(int, float); // (2)

Alias Templates - The Fundamentals

Even though one can advertise the use of alias-declarations by saying that they have a neater syntax than their equivalent typedef, another perk of the former is that they can be turned into alias templates.

An alias template is pretty much exactly what it sounds like; an alias that can make use of its template parameters in order to (potentially) yield different types depending on the template arguments it has received.

template<class T>
using vec_t = std::vector<T>;
//      ^-.          ^-.
//        |            '-- = type-id
//        '--------------- = identifier

When a specialization of an alias template is referenced, it is directly equivalent to the associated type-id after template argument substitution, as in the below example:

int main () {
  vec_t<  int> x; // std::vector<int>
  vec_t<float> y; // std::vector<float>
}

It is important to note that a declaration of an alias template does not introduce a template-id, even though a template-id (such as vec_t<float>) is used to refer to a specialization of such alias.

This might seem rather confusing but, by not introducing a template-id, the ISO C++ Standard effectively says that:

• the name of an alias template cannot be deduced,
• an alias template can be neither partially- nor explicitly specialized, and;
• "expansion" of the type-id must take place when an alias template specialization is referenced.

References: [dcl.typedef]p3, [temp.decls]p3, [temp.alias]p1-4

Alias Templates - The Elaboration

In the previous section we quickly covered the basics of alias templates, more specifically we talked about how they are directly equivalent to a specialization's type-id after template argument substitution.

It might help to consider alias templates as a fancy form of macros, because since the substitution happens immediately, one can, almost, see it as textual replacement. Of course this is a bit of a lie — honestly, it is a big lie — but to paraphrase Scott Meyers; "sometimes a lie is better than the truth".

Take a look at the following example:

template<class T>
using const_ref_t = T const&;

template<class U>
void func (const_ref_t<U> val); // (1)

int main () {
  func (  123); // calls func<int  > (int   const&)
  func (3.14f); // calls func<float> (float const&)
}

In the above, (1) is directly equivalent to void func (U const& val) because of the semantics associated with alias templates.

An often discussed feature of C++1z, the next standard of C++, is the addition of Concepts Lite, which would allow C++ developers to easily make sure that their templates are only instantiated with types that supports a given list of properties.

As it turns out, one can implement something quite similar to Concepts Lite (besides the added benefit of better diagnostics) by (ab)using the semantics of alias templates — as in the following example:

#include <type_traits>
using namespace std;

template<class T, class = enable_if_t<is_integral<T>::value>>
using integral_t = T;

// the usage
template<class T>
void f (integral_t<T> a);

int main () {
  f (  123); // ok
  f (3.14f); // ill-formed
}

Note

One must be aware of the fact that the above technique will make it troublesome to provide an additional overload of f having the same signature — since we, effectively, are declaring template<class T> void f (T) in both cases.

There are ways around this issue, as by utilizing the power of the constant-expression friendly counter in the previous post to make the potential overloads independent from each other.

The semantics of returning auto

The modern use of auto, a placeholder type, was introduced in C++11, making it possible to leave out the type of a variable if it can be deduced from its initializer.

auto x = 3.14f; // `float`
auto y =   123; //   `int`

C++14 further expanded its usability, making it applicable to the return-type of functions (where it previously, in C++11, only applied to lambdas).

This means that one can declare a function to return auto, effectively saying that the return-type is to be deduced by looking at the return-statements in its definition.

auto f (int x) {
  return static_cast<float> (x); // `f(x)` effectively returns `float`
} 

How does return-type deduction work?

When a function is declared to return a placeholder type (like auto), without an explicitly specified trailing-return-type, the ISO C++ Standard states that the return-type of the function is deduced by looking at the return-statements in its definition:

• If usage of the return keyword lacks an operand, the deduced type is void.
• Otherwise, the deduced type is equivalent to the imaginary type of __return_value in auto __return_value = expr, where expr is the expression found in the return-statement.

One must also be aware of the following:

• If there are no return-statements in the function definition, the deduced type is void.
• The function definition is ill-formed if;
  • the deduced type would be an std::initializer_list<T>, or;
  • the deduced type is not the same for every return-statement.
• The program is ill-formed if;
  • a virtual function is declared to have a deduced return-type, or;
  • an entity having a deduced return-type is used in a context where the deduced type is required, but not yet known (see upcoming examples).

References: [dcl.spec.auto]p7,9-13

When can a function having a deduced return-type be used?

Having the previously described set of rules we can quickly see that there are contexts where it would be ill-formed to make use of a function having a deduced return-type. In short, we may not use such entity before the deduced type is known to the compiler.

It might be trivial to figure out such cases by only looking at the rules listed previously, but one can often gain a deeper understanding of a concept by inspecting some sample code — as the below.

auto f (); // (1)
auto g (); // (2)

auto g () {
  return 0;
}

int main () {
  auto a = f (); // ill-formed
  auto b = g (); // ok
}

auto f () {
  return 0;
}

Even though f and g are declared in the same way, at (1) and (2) respectively, we are only allowed to invoke g() in main, since the latter has been given a definition that would allow the compiler to deduce its return-type at the point where the call is made, something which is not true for f().

Caveats of using a function with a deduced return-type

There are some common caveats associated with writing code that makes use of functions having a deduced return-type. This section will try to explain some of them by example code, together with an explanation.

Example #1 - Usage before deduction

auto h (int x) {
  if (x % 5 != 0)
    return h (x+1); // (1), ill-formed

  return x;         // (2)
}

In the above, h is defined to yield the closest integer that is an even multiple of 5 , equal to, or greater, than x — it is however ill-formed because the return-type of h(x+1) is not known at (1).

By simply changing the order of return-statements in h we can make the equivalent definition — from a semantic point of view — well-formed, as in what follows.

auto h (int x) {
  if (x % 5 == 0)
    return x;       // (3)

  return h (x+1);   // (4)
}

The return-type of h is deduced to int in (3), which makes it possible to invoke the function recursively at (4) since the return-type of that statement inherently must be the same as that in (3).

Example #2 - Usage before deduction

The below implementation of foo is ill-formed because of the same reason described in the previous section; at (1) the return-type is not yet known, and we are therefore not allowed to recursively invoke the function.

#include <iostream>

auto foo (int x) {
  std::cout << x << std::endl;

  if (x > 0)
    foo (x-1); // (1)
}

The solution is, as previously, to make an explicit return-statement prior to the recursive call — presumably by changing the logic of the function — as in the below.

auto foo (int x) {
  std::cout << x << std::endl;

  if (x <= 0)
    return;

  foo (x-1);
}

For added clarity, the below implementation is equally suitable — though not at all recommended (you did not get this "advice" from me).

auto foo (int x) {
  if (0) return; 

  std::cout << x << std::endl;

  if (x > 0)
    foo (x-1);
}

It is perfectly fine to do such thing, even though the return-statement will not, ever, be evaluated.

Example #3 - Inconsistent return-types

Integral promotion is a great (but sometimes confusing) feature of C++ — where the type of an expression might be a bigger type than the individual types of the operands involved — mainly to protect developers from running into cases where the result of some operation might not fit in the "domestic" type.

#include <limits>

unsigned char a = std::numeric_limits<unsigned char>::max ();
unsigned char b = 1;

auto x = a + b; // `int`

The below example is sadly very contrived, but it is ill-formed nonetheless.

template<class T>
auto product (T a, T b) {
  if (b == 1)
    return a;

  return a * b;
}

int main () {
  unsigned char a = 1;
  unsigned char b = 2;

  auto ans = product (a, b); // BOOM
}

The author of product did not properly consider the effects of integral promotion. This will effectively break the very explicit rule saying that every return-statement within the function definition must yield the same type if the function template is instantiated with a T such as char.

There are several ways to fix this issue:

• Use a trailing-return-type instead of a deduced one.

  template<class T>
  auto product (T a, T b) -> decltype (a * b) {
    if (b == 1)
      return a;
  
    return a * b;
  }
  

  This would be my recommended solution for this particular example, since it makes it very clear that the purpose of the function is to return a type that can hold the value of a * b.

• Use a static_cast to make sure that every returned expression is of the same type.

  template<class T>
  auto product (T a, T b) {
    using return_t = decltype (a * b);
  
    if (b == 1)
      return static_cast<return_t> (a);
  
    return a * b;
  }
  

  Solutions such as the above might yield cases where we are going through more trouble than necessary. If we must explicitly state which type is returned in some, or all, of the return-statements, the perk of using a deduced return-type somewhat diminishes.

Personal Advice

What follows is a list of (personal) recommendations related to functions having a deduced return-type. They are meant to be used as a little nudge in, what I consider, the right direction to circumvent some of the common problems with such entities.

• If possible, have each declaration of a function returning auto also be a definition.
• Only use auto as return-type for functions with a small number of return-paths.
• Keep the number of non-recursive return-statements to a minimum.
• In case of a recursive implementation;
  • make sure that any base-cases (non-recursive return-statements) are made explicitly prior to any direct, or indirect, recursive call.

Solution

To fully understand the implementation provided in this section one must grasp the contents of the previous posts in this series, as well as what has been discussed in the prerequisites.

Note: vc++, Microsoft's C++ compiler, fail to understand the implementation provided in this section. See the appendix for an appropriate, and equally functioning, workaround.

Note: Older versions of gcc has a bug that makes it incorrectly reject friend-declarations that refers to functions returning auto. See the appendix for further information.

Introduction

The implementation of the stateful meta-container consists of three headers; type_list.hpp, meta_counter.hpp, and meta_list.hpp.

All three files are available for download, but only the last item will have its source code available directly in this post. The contents of the other two will be described, but not fully explained, since their contents are either beyond the scope of this post, or explained in previous parts of this series.

Links

• Individual files
  • type_list.hpp
  • meta_counter.hpp
  • meta_list.hpp
  • main.cpp
• Single file
  • stateful_meta_container-poc.cpp
• Live
  • paste at Coliru
• Archives
  • constexpr-meta-container.tgz
  • consexpr-meta-container.zip

Implementation

type_list.hpp

This header contains an implementation of atch::type_list, a type that supports a number of different meta-template operations to ease the implementation of some of the aspects associated with the stateful meta-container.

#include "type_list.hpp"

int main () {
  using A = atch::type_list<>;                 // empty list
  using B = A::push<void, int, short>::result; // type_list<void,  int, short>
  using C = B::         set<0, float>::result; // type_list<float, int, short>
  using D = C::                 at<1>::result; // int
  using E = C::                  init::result; // type_list<float, int>
}

meta_counter.hpp

This header contains a revised implementation of the counter described in the previous post, with added functionality such as:

• The ability to read the current counter value, without increasing it, and;
• the ability to "tag" a counter, effectively making it possible to have several — independent — counters in flight at the same time.

#include "meta_counter.hpp"

int main () {
  using C1 = atch::meta_counter<class Counter1>;
  using C2 = atch::meta_counter<class Counter2>;

  C1::next (); // 1
  C1::next (); // 2
  C1::next (); // 3

  C2::next (); // 1
  C2::next (); // 2

  static_assert (C1::value () == 3, "C1::value () == 3");
  static_assert (C2::value () == 2, "C2::value () == 2");
}

meta_list.hpp

meta_list.hpp makes use of the functionality implemented in type_list.hpp, and meta_counter.hpp, in order to allow for usage such as the below.

The header declares a class template, template<class Tag> struct meta_list, where Tag is simply used to easily differentiate one list from another.

using LX = atch::meta_list<class ExampleList>;
using LY = atch::meta_list<class AnotherList>;

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>
LY::value<> y; // type_list<>

In short, atch::meta_list uses a counter to associate a given state (value) with a certain ident (identity).

• When the contents of the container is required — such as through LX::value<> — it will read the counter's value, and look up the associated state.

• When the state is modified it will first read the current state using the current ident, and then store away the new (modified) state under the next ident (found by incrementing the counter).

The state is stored by conditionally providing a definition for a function having a deduced return-type, the return-type of said function is then queried when the state is requested.

Note: See the next section for a detailed explanation of the different aspects related to the implementation of atch::meta_list.

main.cpp

#include "type_list.hpp"
#include "meta_counter.hpp"
#include "meta_list.hpp"

#include <type_traits> // std::is_same

int main () {
  using LX = atch::meta_list<class b_atch_se>;

  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>

  static_assert (
    std::is_same<
      atch::type_list<class Hello, void, class World>, LX::value<>
    >::value, "try again"
  );
}

Elaboration

Most of the logic discussed in How to implement a constant-expression counter in C++ apply to the implementation of atch::meta_list, but an explanation of the different parts might still be in order.

Note: The snippets in this section are originally located in the body of template<class Tag> struct meta_list, the surrounding namespace, and the template-declaration itself, has been left out to make it easier to read.

Note: Some of the implementation details has a template-parameter named H with a default-value of the current instantation (meta_list); it is there to prevent premature evaluation of dependent expressions.

The Setup

using   counter = atch::meta_counter<meta_list<Tag>>; // (1)
using size_type = typename counter::size_type;

Every instantiation of atch::meta_list has its own unique counter, aliased at (1) in the above. The line following the alias-declaration is simply to save us some typing further down in the implementation.

The "variable"

The below primary-template will allow us to associate a particular state (value) with a particular ident (identity) by declaring a function with a deduced return-type.

template<size_type N, class = void>
struct ident {
  friend auto adl_lookup (ident<N>);

  static constexpr size_type value = N;
};

template<class Dummy>
struct ident<0, Dummy> {
  friend auto adl_lookup (ident<0>) {
    return atch::type_list<> {};
  }
};

Explicit (full) specializations of a nested class template must be declared in namespace scope, but partial specializations can be declared directly inside a surrounding class.

The use of class = void in the primary-template, and Dummy in the specialization, is simply to allow us to declare a "starter state" for every atch::meta_list — an empty atch::type_list for ident<0> — in a more suitable context.

The "writer"

In order to conditionally provide a definition for the adl_lookup associated with a particular state, a class template writer is declared.

template<class Ident, class State>
struct writer {
  friend auto adl_lookup (ident<Ident::value>) {
    return State {};
  }

  static constexpr size_type value = Ident::value;
};

This will allow us to associate a particular state (State) with a particular ident<N>, through adl_lookup (Ident), upon instantiation of the class template.

The "pusher"

atch::meta_list supports a number of different operations, and since each of these will at some point append a new state to the container, a helper function push_state is declared.

template<
  class State,
  class     H = meta_list,
  class Ident = typename H::template ident<H::counter::next ()>
>
static constexpr size_type push_state (size_type R = writer<Ident, State>::value) {
  return R;
}

The responsibility of the function is to increment the associated counter, construct an ident<N> (using the returned value), and instantiate writer<Ident, State>.

The "readers"

There are several contexts in which the implementation of atch::meta_list is required to look up the current state and/or ident.

To save us some typing at these places we declare two aliases:

• The first alias, value_ident, will allow us to get the current ident. It will simply read the current value of list's counter and alias the corresponding ident<N>.

  template<
    class     H = meta_list,
    size_type N = H::counter::value ()
  >
  using value_ident = typename H::template ident<N>;
  

• The second alias, value, will use the previously declared alias, value_ident, and look up the deduced return-type of the associated adl_lookup using decltype; meaning that it yields the most recent state of the list.

  template<
    class     H = meta_list,
    class Ident = typename H::template value_ident<>
  >
  using value = decltype (adl_lookup (Ident {}));
  

The operations

Note: Remember the semantics of default-arguments, and how they are evaluated each time a function is invoked.

The provided implementation of atch::meta_list supports three different operations; push, pop, and set — each accessed through its own corresponding static member-function.

template<class... Ts, class H = meta_list>
static constexpr void push (
  size_type = push_state<
    typename H::template value<>::template push<Ts...>::result
  > ()
) {} 

template<class H = meta_list>
static constexpr void pop (
  size_type = push_state<
    typename H::template value<>::init::result
  > ()
) {}

template<size_type Idx, class T, class H = meta_list>
static constexpr void set (
  size_type = push_state<
    typename H::template value<>::template set<Idx, T>::result
  > ()
) {}

The above might look a little complicated, but in short:

• Read the current state (value) of the list through typename H::template value<>
• Do some operation on the list
• Call push_state<ModifiedState>(), where ModifiedState is the new contents of our list.

Caveats

As stated in How to implement a constant-expression counter in C++, what we are dealing with involves some very complex rules of the language — as such there are caveats to watch out for.

Note: In addition to the contents of this section, please refer to the caveats section of the previous post for additional quirks related to the technique described.

A painful amount of diagnostics

When compiling the solution presented in this post, both gcc and clang issue warnings related to the fact that we are declaring functions having internal linkage — through the friend-declarations — without ever providing a definition for said functions.

Below is a sample diagnostic from clang.

./meta_counter.hpp:20:34:
    warning: function 'atch::(anonymous namespace)::adl_lookup' has
             internal linkage but is not defined [-Wundefined-internal]

    friend constexpr size_type adl_lookup (ident<N>);
                               ^

This warnings are very appropriate under normal circumstances, but in our particular case we are (ab)using the semantics of the language to support stateful meta-programming. As such, the warnings are of no interest to us.

If we would like to get rid of the warnings in an easy manner, we can use some implementation-defined extension (such as the diagnostic pragma available in both gcc and clang).

Conclusion

This post has explained the technical aspects related to an implementation of a stateful meta-container, allowing a developer to more easily work with, and modify, a given set of entities during the phase of translation.

Together with the previous posts in this series, the formerly unstateful world of translation has gone into a stateful universe — allowing for some crazy, but conforming, implementations.

What is going on in WG21?

It has come to my attention that the Core Working Group (CWG) of WG21 (the ISO Working Group for C++) is trying its best to make the technique described in this, and previous posts, ill-formed. It was brought to my attention by the below linked post:

• Bad news from the Lenexa CWG minutes

The reason behind their decision seems to be that since no one every intended C++ to be able to support stateful meta-programming, it shall not be allowed.

Note: It should be noted that a final decision has not yet been released, the proposed resolution for the issue is still being discussed, and as such; the opinions of the working group might change.

What's next?

The upcoming post, in this series, will talk about other techniques that boil down to doing the same thing as the friend-injection technique (adding state to the world of translation), how the Standard could potentially make the techniques (plural) ill-formed, and the implications of such potential outcome.

A separate post related to smeta — the stateful meta-library — will also be published, and explained in detail. When this will happen depends on the on-going discussion in the Core Working Group.

Writing code against technicalities reflecting defects is a waste of time, encouraging others to do so is immoral. — David Krauss

Appendix

Bug in gcc related to friend-declarations and auto

• c++1y: declaring friend function with 'auto' return type deduction is rejected with bogus reason

The bug was fixed, and pushed, 5 weeks ago (at the current time of writing), as such it is very likely that you are running a version of gcc where the patch has not yet been applied.

In order to successfully compile the implementation presented in this post with gcc, you must either manually apply the patch — or update to a more recent version of the compiler.

Workaround for vc++

Due to a number of bugs in the implementation of Microsoft's C++ compiler the previously linked implementation cannot be compiled using vc++.

Below is a link to an alternative implementation:

• msvc-workaround.cpp

Note: I do not have access to Visual Studio, as such it would be helpful if someone could split up the above into individual files, save it as a vcproj, and email it to me.

Additional Credit

Shout-outs

• Mara Bos, for:

  • Helping me compile a more recent version of gcc (since my computer is too slow to do it in any reasonable amount of time).
  • Allowing me to bounce (sometimes ridiculous) ideas back and forth.
  • Being a very good friend.

• The Donors, for:

  • Donating to Project Keep-Alive, effectively granted me with the funds to put food on the table, and pay my phone bill so that I can use that to access the web when I am at home.

    Honestly, the last few months have been rough, and I am at the edge of losing my apartment — your contributions (no matter how small) have been very helpful. It is hard to show my gratitude in writing, the best I can do is write it really big, as follows:

    Thank You!