Compile-time string concatenation

We will start with a bug, taken from real life. It spans across three files:

#include <string>

struct Service
{
  static const std::string NAME;
};

#include "service.h"

const std::string Service::NAME = "SERVICE1";

#include "service.h"
#include <iostream>

const std::string MSG = "service " + Service::NAME + " ready";

int main()
{
  std::cout << MSG << std::endl;
}

Question: what happens when this program is executed?

When I tested this program in my environment, even though I did not expect to get the intended output, I was still surprised at the result. The program runs without problems and outputs:

  service  ready

The program hits what is called static initialization order fiasco: while initializing global B we need to read global A, but A may be initialized after B. Clearly, I have hit on the wrong initialization order, but I would have expected my program to crash or output some random characters. But apparently, in my version of the Standard Library, an std::string filled with zeros (remember, all globals are statically zero-initialized) represents a valid, empty string. If my application crashes upon initialization, at least everyone gets feedback that something is wrong with it. But my application makes an impression that it works fine, and it displays something else than what I wanted.

This problem in reality manifested in a so characteristic way: when the developer tested the application in his environment, the application worked as intended. But when it was run in close-to-production environment it would crash upon start-up.

What can we do?

Once you have identified the source of the problem, it is easy to fix this occurrence of the bug. Instead of constant NAME provide a function with a static automatic variable inside:

struct Service
{
  static const std::string & NAME()
  {
    static const std::string _name = "SERVICE1";
    return _name;
  }
};

A static automatic variable is almost like a global: one instance is shared across all calls to the enclosing function, and is initialized only once: when the control reaches its declaration for the first time. This way, you guarantee that the string is initialized prior to being returned.

And now you will probably want to change global MSG as well, to prevent future surprises:

const std::string& MSG()
{
  static const std::string _msg = 
    "service " + Service::NAME() + " ready";
  return _msg;
}

int main()
{
  std::cout << MSG << std::endl;
}

But this solution is not ideal. First, as you probably noticed, in function main I forgot to add the parentheses. But this is still valid C++: address of a function is implicitly convertible to bool.

If you are following a good programming practice, and compile with warnings enabled (ideally treated as errors), compiler may help you detect the problem before you produce the executable. My GCC used with -Wall tells me:

warning: the address of 'const string& MSG()'
will always evaluate as 'true' [-Waddress]

One might argue that we can always inadvertently treat any function as an object, but here the situation is special: we have a constant wrapped into a function. Conceptually, we threat it as a constant. And this is in fact the second downside: we provided a function notation to read a constant value.

More objections arise. We now initialize our constant upon first use rather than on program startup. This means an unexpected slow-down (to allocate memory) in a place you didn’t want to have one. Remember that in practice the strings may be a bit longer than 6 chars and will not be SSO-ed. More, do you know what happens when the function is called for the first time concurrently from two threads? Synchronization (read: slow-down).

Plus, now the resources needed to store the global strings get released far after main has finished. Profilers that detect memory leaks are often confused by this and report memory leak where there is none.

And finally, there is something unhealthy about managing resources before main starts. C++ technically allows you to run program message loops outside main. Two examples:

const bool _ = run_message_loop(), true;
int main() {}

struct Launcher
{
  Launcher() { std::set_terminate(&run_message_loop); }
  ~Launcher() { throw "launch"; }
} _ {};
int main() {}

But doing this is evil. Managing resources before main, although not that arrogant, is in the same spirit: it deprives main of its role as the program’s entry point.

Towards the ideal solution

C++11 offers a tool for preventing static initialization order fiasco: the ability to build compile-time constants:

constexpr double X = fun1(Y) + fun2(Z);

It doesn’t matter what fun1, fun2, Y or Z are. Unless the above initialization of X triggers a compiler error, you are guaranteed that it is initialized statically, not using any run-time resources, and safe from any initialization order fiasco or undefined behavior. In other words, it is compile-time checked if you have any initialization issue.

But I cannot initialize a constexpr std::string like this: it is not a literal type. It has to allocate memory: it does not know how big the contained text will grow. But wait, this is true for a general string. In our case, however, we know exactly how many letters we want to store inside. In principle, until we require some run-time input from the environment, it should be possible to compute everything at compile-time and store it as compile-time constants.

To some extent this is what even C is doing. What happens here:

const char NAME[] = "SERVICE1";
static_assert(sizeof(NAME) == 8 + 1, "***");

This tells the compiler to prepare a static storage for the array. The size of the array is to be deduced from the string literal. The size of the array can be determined still at compile-time. This is almost what we need. We can even, to some extent, concatenate literals at compile time:

const char MSG[] = "service " "SERVICE1" " ready";
static_assert(sizeof(NAME) - 1 == 8 + 9 + 6, "***");

But unfortunately, we cannot do this:

const char NAME[] = "SERVICE1";
const char MSG[]  = "service " NAME " ready";

If the language does not support this directly, we should be able to do it with a library: a library for concatenating strings at compile-time.

Implementing compile-time string concatenation

One additional constraint before we proceed. We are solving a real-life problem of real-life programs. This is year 2017, C++17 is almost there, C++14 has been there for more than two years; but in many environments (like mine) people still use C++11. I need the solution to be applicable to C++11.

The basic idea behind the solution can be illustrated by the signature of the following concatenation operator:

template <int N1, int N2>
  constexpr
  auto operator+(static_string<N1> s1, static_string<N2> s2)
  -> static_string<N1 + N2>;

Where static_string<N> is like a built-in array with size N, tracked statically as part of the type. We can use some meta-programming to compute the size of a concatenated string.

While the size of such string is as compile-time as it only can be, the values are “constexpr-like”: they may be compile-time constants or not, depending on the usage. So, we are not as ambitious as Boost.Metaparse, which can generate different types for different character values at compile time:

 
// possible with Boost.Metaparse:
auto b = PARSE_("bool"); // decltype(b) == bool
auto c = PARSE_("char"); // decltype(c) == char

Our library will be more modest. We will focus on our goal: initialize a possibly concatenated string statically.

We will start with implementing a reference to a C-like string literal, which has the size embedded in the type, and which is a distinct type recognized by our concatenation library:

template <int N>
class string_literal
{
  const char (&_lit)[N + 1];
public:
  // ...
};

C++ (like C) already has a designated storage for string literals. We will not be copying them; instead we will use a reference to this storage. Remember that the size of literal is always greater by one than the number of characters due to the trailing zero.

Now, we need a constructor:

constexpr string_literal(const char (&lit)[N + 1])
  : _lit(lit)
  {}

With this we can write:

constexpr string_literal<4> NAME = "ABCD";

But the following unintended usage is also allowed:

constexpr char array [] = {'1', '2', '3', '4', '5'};
constexpr string_literal<4> NAME = array;

In order to prevent this, we enforce in the constructor that the last char is a numeric value zero:

constexpr string_literal(const char (&lit)[N + 1])
  : _lit((X_ASSERT(lit[N] == '\0'), lit))
  {}

How to write macro X_ASSERT that works like C-assert in run-time and prevents compilation at compile-time, we have covered in the previous post.

Still, we have to explicitly state the size of the initialized string_literal. Ideally, we would like the size thereof to be deduced from the initializer, as it is the case with C-arrays. But this is impossible in C++11.

But while deducing parts of the type is impossible in C++11, deducing the entire type works quite well if we add a function template into the mix:

constexpr auto NAME = literal("ABCD");

Not an ideal, because we declare a variable without a type, which sometimes leads to surprises. But the size of the literal can be now deduced if we implement literal cleverly:

template <int N_PLUS_1>
  constexpr auto literal(const char (&lit)[N_PLUS_1])
  -> string_literal<N_PLUS_1 - 1> 
{
  return string_literal<N_PLUS_1 - 1>(lit);
}

This does almost the same trick as std::make_pair, with one exception: because we want to match to literals of size N + 1, we cannot just type N + 1 directly in function’s parameter:

// WRONG:
template <int N>
  constexpr auto literal(const char (&lit)[N + 1])
  -> string_literal<N> 
{
  return string_literal<N>(lit);
}

This is because of how the rules of template parameter matching work: you want an integer to be deduced, it has to be matched directly to a name, not to an arbitrary arithmetical expression.

One of the things we will need for our new type is to access the i-th character of the string. This is quite easy to implement:

template <int N>
class string_literal
{
  const char (&_lit)[N + 1];

public:
  constexpr char operator[](int i) const
  {
    return X_ASSERT(i >= 0 && i < N), _lit[i];
  }
};

The additional const is correct but redundant in C++11. However, in C++14 constexpr on a function does not imply const, as discussed in this post.

Now, we want to be able to concatenate two string_literals of different sizes. But what should be the result (type) of the concatenation? We cannot use the same type as now it is not a reference to an already existing literal. We will need a new type, which will store the array of characters:

template <int N>
class array_string
{
  char _array[N + 1];
  // ...
};

We will also store the trailing zero. This is in order to provide function c_str() and the interface to C-like libraries that work with null-terminated character sequences. Writing the concatenation operator is easy: we just forward the call to the constructor of array_string:

template <int N1, int N2>
  constexpr auto operator+(const string_literal<N1>& s1,
                           const string_literal<N2>& s2)
  -> array_string<N1 + N2>
{
  return array_string<N1 + N2>(s1, s2);
}

The tough part is how to implement the constructor. In C++14, which has more relaxed constraints on constexpr functions, it would be easy:

// in C++14:
template <int N>
class array_string
{
  char _array[N + 1];

public:
  template <int N1, REQUIRES(N1 <= N)>
    constexpr array_string(const string_literal<N1>&     s1,
                           const string_literal<N - N1>& s2)
    {
      for (int i = 0; i < N1; ++i)
        _array[i] = s1[i];

      for (int i = 0; i < N - N1; ++i)
        _array[N1 + i] = s2[i];

      _array[N] = '\0';
    }
};

Do not be disturbed by this macro REQUIRES, it is just a shorthand for an std::enable_if:

# define REQUIRES(...) \
  typename std::enable_if<(__VA_ARGS__), bool>::type = true

But such implementation will not work in C++11. In C++11 it is required that the body of the constexpr constructor be empty: you can only initialize in the initializer list:

// in C++11:
template <int N1, REQUIRES(N1 <= N)>
  constexpr array_string(const string_literal<N1>&     s1,
                         const string_literal<N - N1>& s2)
    : _array{ /* WHAT? */ }
    {}

Now, in order to achieve this almost impossible thing, you have to be familiar with parameter packs in variadic templates, and how they can be expanded, and with the following syntax:

template <typename ... Args>
  void f(Args &&... args)
  {
    g(std::forward<Args>(args)...);
  }

You will notice that std::forward<Args>(args)... is a sort of pattern here. When function f is called like f(1, 'c'), the pattern is expanded to:

g(std::forward<int>(args1), std::forward<char>(args2));

Commas are added exactly where needed. But a sequence of ints can also be a parameter pack:

template <int... Is>
  void f()
  {
    std::vector<int> v {Is...};
  }

And when we call f<0, 1, 2>(), the initialization of the vector gets expanded to:

std::vector<int> v {0, 1, 2};

This gets us close to the solution. But in our case we need two packs. If we somehow had them, we could initialize our array like this:

// Not C++ yet (no PACK1 or PACK2)
template <int N1, REQUIRES(N1 <= N)>
  constexpr array_string(const string_literal<N1>&     s1,
                         const string_literal<N - N1>& s2)
    : _array{ s1[PACK1]..., s2[PACK2]..., '\0' }
    {}

In C++14, the Standard Library provides a tool exactly for this purpose: injecting int-like parameter packs where you need them: integer_sequence. It comes in two parts:

template <typename I, I... Is>
  class integer_sequence;

This part is used for “receiving” a pack (e.g., to expand a pattern). The second part is used for generating such integer_sequence for a receiver:

template <typename I, I N>
  using make_integer_sequence = /*...*/;

This alias template generates instances of integer_sequence according to the following expectation:

make_integer_sequence<int, 0> == integer_sequence<int>;
make_integer_sequence<int, 1> == integer_sequence<int, 0>;
make_integer_sequence<int, 2> == integer_sequence<int, 0, 1>;
make_integer_sequence<int, 3> == integer_sequence<int, 0, 1, 2>;

That is, the N in make_integer_sequence determines the size of the sequence of integers in integer_sequence, and this sequence is consecutive numbers starting from 0.

Now, I said that this is only available in C++14, and we are solving the problem for C++11. Luckily, it is quite easy to implement a similar tool oneself, and because we only need it to work with ints (rather than any integral type), our tool can be smaller:

// the type used to receive the pack

template <int... I>
  struct sequence {};

// auxiliary meta-function for making (N+1)-sized sequence
// from an N-sized sequence

template <typename T>
  struct append;
 
template <int... I>
  struct append<sequence<I...>>
  {
    using type = sequence<I..., sizeof...(I)>;
  };

// recursive implementation of make_sequence 

template <int I>
  struct make_sequence_;

template <int I>
  using make_sequence = typename make_sequence_<I>::type;

template <>
  struct make_sequence_<0> // recursion end
  {
    using type = sequence<>;
  };

template <int I>
  struct make_sequence_ : append<make_sequence<I - 1>>
  {
    static_assert (I >= 0, "negative size");
  };

Not the most efficient implementation, but it will do for illustration. If you do not understand what is going on here, don’t worry. The point is, such sequence can be implemented in C++11, and it exposes the desired properties:

make_sequence<0> == sequence<>;
make_sequence<1> == sequence<0>;
make_sequence<2> == sequence<0, 1>;
make_sequence<3> == sequence<0, 1, 2>;

Now, in order to make use of it, we will have to provide two constructors for array_string: one will be creating, and the other will be consuming sequences.

template <int N>
class array_string
{
  char _array[N + 1];

  template <int N1, int... PACK1, int... PACK2>
    constexpr array_string(const string_literal<N1>&     s1,
                           const string_literal<N - N1>& s2,
                           sequence<PACK1...>,
                           sequence<PACK2...>)
    : _array{ s1[PACK1]..., s2[PACK2]..., '\0' }
    {
    }

public:
  template <int N1, REQUIRES(N1 <= N)>
    constexpr array_string(const string_literal<N1>&     s1,
                           const string_literal<N - N1>& s2)
    // delegate to the other constructor
    : array_string{ s1, s2, make_sequence<N1>{},
                            make_sequence<N - N1>{} }
    {
    }
};

We have a private constructor that does the actual initialization, and a public delegating constructor that creates the sequences. It can do it because sizes of the string_literals are encoded in their types.

Note the two additional function arguments in the private constructor. We do not even spell their names. We are not interested in their run-time values; we are not even interested in their types: we are only interested in being able to declare two parameter packs.

Now if we also implement operator[] and function size:

template <int N>
class array_string
{
  char _array[N + 1];

public:
  constexpr char operator[](int i) const
  {
    return X_ASSERT(i >= 0 && i < N), _array[i];
  }

  constexpr std::size_t size() const
  {
    return N;
  }
  // ...
};

We can already see that our tool does the basic task:

constexpr auto S1 = literal("ABCD");
constexpr auto S2 = literal("EFGH");
constexpr auto R = S1 + S2;

static_assert(R.size() == 8, "***");
static_assert(R[0] == 'A', "***");
static_assert(R[7] == 'H', "***");

Of course, for such tool to be complete, we would have to add more member functions, like conversion to null-terminated string, possibly to std::string_view (not C++11, but sometimes available as an experimental extension) or boost::string_view, and add more overloads of the concatenation operator, working for different combinations of string_literal, array_string and const char *. But there is no room for this in this blog post. Instead, you can try out a fully implemented library: static_string.

Some observations

One could argue that once I have type array_string, I do not need type string_literal anymore, because the former can handle whatever the latter can. It is true; but I find value in not having to copy the contents of the string, which the compiler has to store anyway. Minimum as it is, it is still an optimization. array_string and string_literal, once created have identical interfaces; they only differ by how they store the characters. Yet they are different types, and require of me to provide more and more overloads for concatenation operator with identical implementation. In a way, this is in the spirit of C++: performance trade-offs in the implementation are part of the contract. Nonetheless, to avoid the duplication, what I can do is to make array_string and string_literal two instantiations of the same template: template with specializations:

struct RefImpl {};   // tag class
struct ArrayImpl {}; // tag class

template <int N, typename Impl>
  class sstring // main template never used
  {
    static_assert(N != N, "***");
  };

template <int N>
  class sstring<N, ArrayImpl>
  {
    char _array[N + 1];
    // ...
  };

template <int N>
  class sstring<N, RefImpl>
  {
    const char (&_lit)[N + 1];
    // ...
  };

template <int N>
  using array_string = sstring<N, ArrayImpl>;

template <int N>
  using string_literal = sstring<N, RefImpl>;

This way I can provide one implementation of concatenation operator for all combinations of array_string and string_literal:

template <int N1, int N2, typename Tag1, typename Tag2>
  constexpr auto operator+(const sstring<N1, Tag1>& s1,
                           const sstring<N2, Tag2>& s2)
  -> array_string<N1 + N2>
{
  return array_string<N1 + N2>(s1, s2);
}

Second, I mentioned that deducing the size of a string_literal from initializer is impossible in C++11. The situation will be different in C++17. I can define a deduction guide:

// C++17 deduction guide:
template <int N_PLUS_1>
  sstring(const char (&lit)[N_PLUS_1])   // <- match this
  -> sstring<N_PLUS_1 - 1, RefImpl>;     // <- use these args

This says more less, “whenever class template sstring is initialized and some or all of its template parameters have been omitted, and the arguments used for initialization match what I typed in parentheses, deduce the remaining template parameters as indicated.” It serves the purpose similar to function literal, except that it will be used implicitly in contexts like this:

constexpr sstring S1 = "ABCD";
constexpr sstring S2 = "EFGH";
constexpr sstring R = S1 + S2;

This deduces not only the size, but also which implementation — array_string or string_literal — to use. Note that in the last line another deduction guide is used. This one is implicit, and it does not even have to be spelled out by programmers: when I initialize one instance of a class template (sstring) with another instance of the same class template, deduce exactly the same template arguments.

Apart form concatenation, this library could also offer other operations, like taking a sub-string, which is easily implemented; but I never had a need for such things, so for now the library only implements what I know is needed.

Also, note that I am using type int for representing string sizes, even though they never get negative. This is out of habit, which I consider good. When computing a size, through some (compile-time) arithmetical operation, it might happen that I will be subtracting a bigger number from a smaller one, and arrive at a negative result. If I use unsigned types, such results will be silently converted to a positive (and incorrect) value. I do not want that: I want negative sizes to be explicitly captured by static assertions, and reported verbosely by compiler.