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

Created Mon, 28 May 2015 22:03:12 +0200
Modified Thu, 04 Jun 2015 13:53:05 +0200
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.

Note: I have not had time to review the contents of this post as much as I have been wanting to; please use the comment section if you find anything that is hard to understand, or misleading.

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.

Note: Fear not fellow stateful meta-programming enthusiast, smeta will be released and discussed in upcoming posts (linked as soon as they are available to the public).

Table of Contents

Prerequisites

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

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:

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:

One must also be aware of the following:

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:

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.

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

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:

#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).

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:

    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:

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:

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

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:

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

Author Filip Roséen
Contact filip.roseen@gmail.com

Note: If you appreciate the contents of this blog, please feel free to make a donation (paypal) to show your support.

Powered by scorpiondata.com