How to create static strings from types at compile time

Question

I have a bunch of types that have a name. (They have more features, but for the sake of this discussion only the name is relevant.) These types and their names are setup at compile-time using a macro:

#define DEFINE_FOO(Foo_)                        \
    struct Foo_ : public foo_base<Foo_> {       \
      static char const* name() {return #Foo_;} \
    }

The types are then combined in compile-time lists (classic simple recursive compile-time lists), from which I need to create the list's name by concatenating the names of its objects:

template<class Foo, class Tail = nil>
struct foo_list {
  static std::string name_list() {return Foo::name() + "-" + Tail::name();}
};
template<class Foo>
struct foo_list<Foo,nil> {
  static std::string name_list() {return Foo::name();}
};

The code is boiled down here to the point where it might contain errors, but in practice this works pretty well.

Except that it creates and then copies around rather long strings at runtime which represent types that actually are well-known at compile-time. Since this is a rather performance-sensitive piece of code that runs on embedded devices, I'd like to change this so that

1. the list's string is ideally created at compile-time, or, if there's no way to do that, once at runtime, and
2. I only need to copy around a pointer to a C string, since, according to #1, the strings are fixed in memory.
3. This compiles with C++03, which we're stuck with right now.

How can I do this?

(In case this enlarges the arsenal of dirty tricks employable for this: The names of the foo objects are only ever created and read by code, and only the foo_list name strings are expected to be human-readable.)

Assemblage

Does it have to be a string? Could you just use typeid? – Welcome

@Adam: This ends up a human readable string in a file. – Assemblage

Can you also add length function? – Clepsydra

@ForEveR: Given that the strings in the foo template are known at compile time, it is rather trivial to even add a compile-time constant of the string's length. Why are you asking? – Assemblage

Answer 1

You probably want to look at boost's mpl::string. Example to follow once my coffee has kicked in...

EDIT: So coffee has kicked in... :)

#include <iostream>

#include <boost/mpl/bool.hpp>
#include <boost/mpl/if.hpp>
#include <boost/mpl/string.hpp>
#include <boost/mpl/vector.hpp>

namespace mpl = boost::mpl;

struct foo
{
  typedef mpl::string<'foo'> name;
};

struct bar
{
  typedef mpl::string<'bar'> name;
};

struct gah
{
  typedef mpl::string<'gah'> name;
};

namespace aux
{

template <typename string_type, typename It, typename End>
struct name_concat
{
  typedef typename mpl::insert_range<string_type, typename mpl::end<string_type>::type, typename mpl::deref<It>::type::name>::type base;
  typedef typename aux::name_concat<base, typename mpl::next<It>::type, End>::name name;
};

template <typename string_type, typename End>
struct name_concat<string_type, End, End>
{
  typedef string_type name;
};

}

template <typename ...Types>
struct type_list
{
  typedef mpl::string<> base;
  typedef mpl::vector<Types...> type_seq;
  typedef typename aux::name_concat<base, typename mpl::begin<type_seq>::type, typename mpl::end<type_seq>::type>::name name;
};

int main(void)
{
  typedef typename type_list<foo, bar, gah>::name tlist_name;
  std::cout << mpl::c_str<tlist_name>::value << std::endl;
}

I'm sure you are more than competent enough to tweak the above for your situation. NOTE: you will have to ignore the multi-character constant warnings...

Couple of more caveats: the multi-character constant passed to mpl::string cannot be more than 4 characters, so, some how it has to be chunked (or constructed of individual characters), so a long string could be, mpl::string<'this', ' is ', 'a lo', 'ng s', 'trin', 'g'> If this is cannot be done, then the above will not work.. :/

Atharvaveda

Ok, this looks interesting. One issue I have with this: As this is a proprietary embedded platform with a custom-tailored (old) GCC, this is strictly C++03. (Sorry, I forgot to say this in the question. I'll add it now.) Among others, variable argument templates are impossible for us to make use of. The other issue is that I never wrapped my head around those overlong character constants like 'foo'. What type is that? And can that be of arbitrary length? If not, then this won't work for us. – Assemblage

I was being lazy when using the variadic template parameters, mpl::vector<> will work in 03 too, you just need to explicitly list all the types. As for the multi-character constants, I think they default to int, which is why only four characters are allowed per constant. Like I said in the caveat, either you need to be able to restrict the length of name of the type to four characters, or somehow compose them of chunks of four characters. – Atharvaveda

Answer 2

I came up with following solution:

Type is generated as:

const char foo_str [] = "foo";
struct X
{
    static const char *name() { return foo_str; }
    enum{ name_size = sizeof(foo_str) };
};

Keypoint here is that we know length of its name at compile time. That allow us to calculate total length of names in typelist:

template<typename list>
struct sum_size
{
    enum
    {
       value = list::head::name_size - 1 +
               sum_size<typename list::tail>::value
    };
};
template<>
struct sum_size<nil>
{
    enum { value = 0 };
};

Knowing total length at compile time, we can allocate static buffer of appropriate size for concatenation of strings - so there will be no any dynamic allocations:

static char result[sum_size<list>::value + 1];

That buffer should be filled at runtime, but only once, and that operation is pretty cheap (much faster than previous solution with dynamic allocation of strings and their concatenation in recursion):

template<typename list>
const char *concate_names()
{
    static char result[sum_size<list>::value + 1];
    static bool calculated = false;
    if(!calculated)
    {
        fill_string<list>::call(result);
        calculated = true;
    }
    return result;
}

Here is full code:

Live Demo on Coliru

#include <algorithm>
#include <iostream>
using namespace std;

/****************************************************/

#define TYPE(X) \
const char X ## _str [] = #X; \
struct X \
{ \
    static const char *name() { return X ## _str; }  \
    enum{ name_size = sizeof(X ## _str) }; \
}; \
/**/

/****************************************************/

struct nil {};

template<typename Head, typename Tail = nil>
struct List
{
    typedef Head head;
    typedef Tail tail;
};

/****************************************************/

template<typename list>
struct sum_size
{
    enum { value = list::head::name_size - 1 + sum_size<typename list::tail>::value };
};
template<>
struct sum_size<nil>
{
    enum { value = 0 };
};

/****************************************************/

template<typename list>
struct fill_string
{
    static void call(char *out)
    {
        typedef typename list::head current;
        const char *first = current::name();
        fill_string<typename list::tail>::call
        (
            copy(first, first + current::name_size - 1, out)
        );
    }
};

template<>
struct fill_string<nil>
{
    static void call(char *out)
    {
        *out = 0;
    }
};

/****************************************************/

template<typename list>
const char *concate_names()
{
    static char result[sum_size<list>::value + 1];
    static bool calculated = false;
    if(!calculated)
    {
        fill_string<list>::call(result);
        calculated = true;
    }
    return result;
}

/****************************************************/

TYPE(foo)
TYPE(bar)
TYPE(baz)

typedef List<foo, List<bar, List<baz> > > foo_list;

int main()
{
    cout << concate_names<foo_list>() << endl; 
}

Output is:

foobarbaz

---

P.S. How do you use concatenated string? Maybe we don't need to generate concatenated string at all, reducing data space requirement.

For example if you just need to print string - then

template<typename list>
void print();

will be sufficient. But downside is that while decreasing data size - that could lead to increased size of code.

Exaggerate

Well, if we print the string, then it is concatenated, isn't it? :) The string has indeed to be printed (I said they were expected to be human-readable), but the compile-time lists live on one side of a gap, while the printing is on the other, so that they have to be rendered in order to be shipped across that gap. – Assemblage

Anyway, this seems like a good solution (+1). However, what advantage does it have over Mark Garcia's answer? Like yours, his solution, too, builds the strings once at runtime, and his solution is way less complex. – Assemblage

@Assemblage Difference is that for his solution you have to do O(n) dynamic allocations for concatenation of n stings at each type-list. While at my solution you will do just O(1) static allocation, with known compile-time size (which is much less expensive), for each type-list. – Exaggerate

Answer 3

1. You could make the string static and you only have to construct the string once at runtime and only when it is needed.
2. Then you return a const reference of them so that there wouldn't be any unnecessary copying.

Example:

template<class Foo, class Tail = nil>
struct foo_list {
  static const std::string& name_list() {
     static std::string names = Foo::name() + std::string("-") + Tail::name();
     return names;
  }
};

template<class Foo>
struct foo_list<Foo,nil> {
  static const std::string& name_list() {
     static std::string names = Foo::name();
     return names;
  }
};

Might not be the exact code that you'll write, but I think that gives you the point. Also, you could return a const char* by doing names.c_str().

Polyandrist

Mhmm. This builds the string at runtime, although only at the first time. And, yes, the address returned by names.c_str() should be fixed. Let's see if someone finds a pure compile-time solution, otherwise I'll probably do this. – Assemblage

Answer 4

You can consider using an external build step instead of an in-language solution. For example, you could write a tool based on Clang to parse the relevant files and create the T::name implementations automatically in another TU. Then integrate it into your build script.

Ceylon

Answer 5

If we could assume that your only requirement is to actually stream the names of the classes - meaning you don't need the concatenated strings at other places as a whole - you could simply defer streaming but still benefit from meta-programming (as Evgeny already pointed out).

While this solution doesn't satisfy your requirement #1 (one concatenated string), I'd still like to point out a solution for other readers.

Instead of going through a compile-time list of types, the idea is to build a sequence of addresses from all T::name() functions and pass that into a streaming function when needed. This is possible because variables with external linkage can be used as template non-type arguments. Your mileage may vary in terms of data and code size of course, but unless you are in a high-performance environment I expect this approach to be at least equally suitable as no additional strings have to be created at runtime.

Note that I deliberately used variadic templates (not available in C++03) because it's much more readable and simpler to reason about.

"Fiddle" available here.

#include <ostream>
#include <boost/core/ref.hpp>
#include <boost/bind.hpp>
#include <boost/mpl/vector.hpp>
#include <boost/mpl/for_each.hpp>

namespace mpl = boost::mpl;


template<typename>
class foo_base
{};

#define DECLARE_FOO(Foo_) \
    struct Foo_ : public foo_base<Foo_> { \
        static char const* name() {return #Foo_;} \
    };


// our own integral constant because mpl::integral_c would have to be specialized anyway
template<typename T, T Value>
struct simple_integral_c
{
    operator T() const { return Value; }
};

template<typename T, T ...Values>
struct ic_tuple : mpl::vector<simple_integral_c<T, Values>...>
{};


typedef const char*(*NameFunction)();

template <NameFunction ...Functions>
struct function_list : ic_tuple<NameFunction, Functions...>
{};

template <typename ...Types>
struct function_of_list : function_list<&Types::name...>
{};


struct print_type
{
    void operator ()(std::ostream& os, NameFunction name)
    {
        if (nth++)
            os << "-";
        os << name();
    }

    print_type(): nth(0) {}

private:
    int nth;
};

// streaming function
template<NameFunction ...Functions>
std::ostream& operator <<(std::ostream& os, function_list<Functions...>)
{
    mpl::for_each<function_list<Functions...>>(
        boost::bind<void>(print_type(), boost::ref(os), _1)
    );

    return os;
}

These days with C++14 one would probably write the solution with a powerful library like hana, see this hana fiddle.

Wagstaff