Jacek's Blog

Software Engineering Consultant

About Blog Impressum Datenschutz / Cookies
jacek@galowicz.de

Transformations between User Input/Output and Type Lists

May 14, 2016 c++ metaprogramming

Type lists are an important way to represent ordered and unordered sets of types at compile time. These types can be real structure- or class types bundling runtime algorithms etc., but they can also convey actual data at compile time. In order to apply certain compile time processing to data, this data needs to be transformed from and to other representations, which can be provided by the programmer and consumed by run time programs. This article shows how to transform back and forth between strings and character type lists.

Wrapping characters into Type Lists

At first, a type is needed which can carry one actual character, without having to instantiate it. This is the requirement for all value-carrying types in order to be able to use them at compile time. Using that type, it is possible to compose character type lists, which carry whole strings.

template <char val>
struct char_t {
    static const constexpr char value {val};
};

char_t‘s only template parameter is an actual character. To carry the character ’a’, one just instanciates it like this: char_t<'a'>. The character can now be accessed via the value member of the structure type, both at compile- and at run time:

// Define the character 'a' carrying type
using my_char = char_t<'a'>;

// Accessing my_char's payload character at compile time
using next_char = char_t<my_char::value + 1>;

int f()
{
    // Accessing it at run time
    std::cout << my_char::value << '\n';
}

This type is now fundamental to character type lists.

Converting from Strings to Type Lists

Using type lists, these can now easily be chained together, using the make_t helper from the previous article. (Link to the article which explains how to create type lists)

using my_abc_string = make_t<char_t<'a'>, char_t<'b'>, char_t<'c'>>;

Although make_t’s purpose is to make type list creation less clumsy, this does not look optimal.

template <char c, char ... chars>
struct char_tl;

template <char c, char ... chars>
struct char_tl {
    using type = tl::tl<
                    char_t<c>,
                    typename char_tl<chars...>::type
                 >;
};

template <char c>
struct char_tl<c> {
    using type = tl::tl<char_t<c>, tl::null_t>;
};

template <char ... chars>
using char_tl_t = typename char_tl<chars...>::type;


Character type lists can now be instantiated like this:

using my_abc_string = char_tl_t<'a', 'b', 'c'>;

This is already a significant improvement over what we had before. Pretty nice, but the real optimum would be a transformation from an actual C-string in the form "abc" to a type list.

Of course, that is also possible:

template <class Str, size_t Pos, char C>
struct string_list;

template <class Str, size_t Pos, char C>
struct string_list {
    using next_piece = typename string_list<
                            Str,
                            Pos + 1,
                            Str::str()[Pos + 1]
                        >::type;
    using type = tl::tl<char_t<C>, next_piece>;
};

template <class Str, size_t Pos>
struct string_list<Str, Pos, '\0'> {
    using type = tl::null_t;
};

template <class Str>
using string_list_t = typename string_list<
                          Str,
                          0,
                          Str::str()[0]
                      >::type;


Before continuing with the following lines of code: What is a string provider?

A string, or a string pointer, cannot just be used as template parameters directly. Therefore a type carrying a string as payload and provides static access to it is needed:

struct my_string_provider {
   static constexpr const char * str() {
       return "foo bar string";
   }
};

This type can now be used as a template parameter by template classes, and the template code can access its static string member. Because of this additional, but necessary, indirection it is called a string provider.

struct abc_string_provider {
   static constexpr const char * str() {
       return "abc";
   }
};

using my_abc_string = string_list_t<abc_string_provider>;

This is as easy as it gets. Having to define a string provider around every simple string is still a lot of scaffolding, but this is still the only reasonable way to convert long C-strings into type lists.

Converting from Type Lists to C-Strings

Imagine a type list with character payload as the result after the execution of some meta programming algorithm.

In some cases the wanted output form is a C-string. This is the exact reverse operation from what we just implemented before.

The generic idea is to convert a type list to a variadic character template parameter list. That variadic list can be used to initialize a character array, which can then be provided to the user:

template <typename typelist, char ... chars>
struct tl_to_vl;

template <char c, typename restlist, char ... chars>
struct tl_to_vl<tl::tl<char_t<c>, restlist>, chars...>
    : public tl_to_vl<restlist, chars..., c>
{ };

template <char ... chars>
struct tl_to_vl<tl::null_t, chars...> {
    static const char * const str() {
        static constexpr char ret[] {chars..., '\0'};
        return ret;
    }
}


This code example is different than the others before, because it relies on inheritance. It would have been possible to implement the others with inheritance, too, or implement this one defining local type type variables etc., but i found this form to be the shortest and most useful one, while still being nicely readable.

By instanciating tl_to_vl<some_type_list>, a chain of inheriting classes is unrolled, and the last base class, which is the recursion abort type from line 10, defines the static str() function. Because every member of a struct is public by default, the actually instantiated outer type tl_to_vl<some_type_list> also provides this function, which is directly callable.

Example of how to print a type list on the terminal, after converting it into a C-String:

struct abc_string_provider {
   static constexpr const char * str() {
       return "abc";
   }
};

using my_abc_string = string_list_t<abc_string_provider>;

using string_provider = tl_to_vl<my_abc_string>;

int f() {
    puts(string_provider::str());
}

When compiling code like this, the assembly code will still result in a function call of str(), which returns a pointer to the C-string, and then a call of puts.

Compiling the code without any optimization (clang++ [clang-703.0.29]):

_main:
pushq   %rbp
movq    %rsp, %rbp
subq    $0x10, %rsp
movl    $0x0, -0x4(%rbp)

# The following line contains the function call string_provider::str()
callq   __ZN13tl_to_varlistIN2tl6null_tEJLc72ELc101ELc108ELc108ELc111ELc32ELc87ELc111ELc114ELc108ELc100ELc33ELc10ELc13EEE3strEv ## tl_to_varlist<tl::null_t, (char)72, (char)101, (char)108, (char)108, (char)111, (char)32, (char)87, (char)111, (char)114, (char)108, (char)100, (char)33, (char)10, (char)13>::str()
movq    %rax, %rdi

# This is the call of the puts() procedure
callq   0x100000f7e     ## symbol stub for: _puts
xorl    %ecx, %ecx
movl    %eax, -0x8(%rbp)
movl    %ecx, %eax
addq    $0x10, %rsp
popq    %rbp
retq

Compiling the code with -O1 or -O2 optimization (clang++):

_main:
pushq %rbp
movq  %rsp, %rbp
movq  0x85(%rip), %rdi   ## literal pool symbol address: __ZZN13tl_to_varlistIN2tl6null_tEJLc72ELc101ELc108ELc108ELc111ELc32ELc87ELc111ELc114ELc108ELc100ELc33ELc10ELc13EEE3strEvE6string
callq 0x100000f84        ## symbol stub for: _puts
xorl  %eax, %eax
popq  %rbp
retq

The disassembly shows that the string is just read out of the binary, where it is available without any processing. It is pretty nice to see that there is no trace of any meta programming code in the binary. Apart from those strange and long symbol names, everything looks as if the string was hard coded into the binary by hand to its resulting form.

The next article will deal with template meta programs which transform character type lists in order to do useful things with them.