constexpr to concatenate two or more char strings

Question

I'm trying to make a constexpr function that will concatenate an arbitrary number of char arrays by working from the following answer by Xeo, which concatenates two char arrays.

https://stackoverflow.com/a/13294458/1128289

#include <array>

template<unsigned... Is> struct seq{};
template<unsigned N, unsigned... Is>
struct gen_seq : gen_seq<N-1, N-1, Is...>{};
template<unsigned... Is>
struct gen_seq<0, Is...> : seq<Is...>{};

template<unsigned N1, unsigned... I1, unsigned N2, unsigned... I2>
constexpr std::array<char const, N1+N2-1> concat(char const (&a1)[N1], char const (&a2)[N2], seq<I1...>, seq<I2...>){
  return {{ a1[I1]..., a2[I2]... }};
}

template<unsigned N1, unsigned N2>
constexpr std::array<char const, N1+N2-1> concat(char const (&a1)[N1], char const (&a2)[N2]){
  return concat(a1, a2, gen_seq<N1-1>{}, gen_seq<N2>{});
}

My attempt thus far:

#include <iostream>
#include <array>

template<unsigned... Is> struct seq{};
template<unsigned N, unsigned... Is>
struct gen_seq : gen_seq<N-1, N-1, Is...>{};
template<unsigned... Is>
struct gen_seq<0, Is...> : seq<Is...>{};

template<unsigned N1, unsigned... I1, unsigned N2, unsigned... I2>
constexpr const std::array<char, N1+N2-1>
concat_impl(
    const char (&a1)[N1], const char (&a2)[N2], seq<I1...>, seq<I2...>)
{
    return {{ a1[I1]..., a2[I2]... }};
}

template<unsigned N1, unsigned N2>
constexpr const std::array<char, N1+N2-1>
concat(const char (&a1)[N1], const char (&a2)[N2])
{
    return concat_impl(a1, a2, gen_seq<N1-1>{}, gen_seq<N2>{});
}

template<unsigned N1, unsigned N2, class... Us>
constexpr auto
concat(const char(&a1)[N1], const char(&a2)[N2], const Us&... xs)
-> std::array<char, N1 + decltype(concat(a2, xs...))::size() - 1>
{
    return concat(a1, concat(a2, xs...));
}

int main()
{
    auto const s = concat("hi ", "there!");
    std::cout << s.data() << std::endl;
    // compile error:
    auto const t = concat("hi ", "there ", "how ", "are ", "you?");
    std::cout << t.data() << std::endl;
}

Both gcc 4.9 and clang 3.5 give errors indicating that no function matching the concat inside the decltype expression can be found.

clang:

error: no matching function for call to 'concat'
    auto const t = concat("hi ", "there ", "how ", "are ", "you?");
                   ^~~~~~
ctconcat.cpp:105:16: note: candidate template ignored: substitution failure [with N1 = 4, N2 = 7, Us = <char [5], char [5], char [5]>]: no matching function for call to 'concat'
constexpr auto concat(const char(&a1)[N1], const char(&a2)[N2], const Us&... xs) -> std::array<char, N1 + decltype(concat(a2, xs...))::size() - 1>
               ^                                                                                                   ~~~~~~
ctconcat.cpp:62:43: note: candidate function template not viable: requires 2 arguments, but 5 were provided
constexpr const std::array<char, N1+N2-1> concat(const char (&a1)[N1], const char (&a2)[N2])
                                          ^
1 error generated.

The errors from gcc and clang both indicate that the second concat function template is not a candidate for the concat in the decltype expression. Only the first template is considered. Why is that and how do I fix this?

Edit: Relevant question on why decltype can't be used recursively

trailing return type using decltype with a variadic template function

Answer 1

template<size_t S>
using size=std::integral_constant<size_t, S>;

template<class T, size_t N>
constexpr size<N> length( T const(&)[N] ) { return {}; }
template<class T, size_t N>
constexpr size<N> length( std::array<T, N> const& ) { return {}; }

template<class T>
using length_t = decltype(length(std::declval<T>()));
constexpr size_t sum_string_sizes() { return 0; }
template<class...Ts>
constexpr size_t sum_string_sizes( size_t i, Ts... ts ) {
  return (i?i-1:0) + sum_sizes(ts...);
}

then

template
template<unsigned N1, unsigned N2, class... Us>
constexpr auto
concat(const char(&a1)[N1], const char(&a2)[N2], const Us&... xs)
-> std::array<char, sum_string_sizes( N1, N2, length_t<Us>::value... )+1 >
{
  return concat(a1, concat(a2, xs...));
}

which gets rid of the recursion-in-decltype.

---

Here is a full example using the above approach:

template<size_t S>
using size=std::integral_constant<size_t, S>;

template<class T, size_t N>
constexpr size<N> length( T const(&)[N] ) { return {}; }
template<class T, size_t N>
constexpr size<N> length( std::array<T, N> const& ) { return {}; }

template<class T>
using length_t = decltype(length(std::declval<T>()));

constexpr size_t string_size() { return 0; }
template<class...Ts>
constexpr size_t string_size( size_t i, Ts... ts ) {
  return (i?i-1:0) + string_size(ts...);
}
template<class...Ts>
using string_length=size< string_size( length_t<Ts>{}... )>;

template<class...Ts>
using combined_string = std::array<char, string_length<Ts...>{}+1>;

template<class Lhs, class Rhs, unsigned...I1, unsigned...I2>
constexpr const combined_string<Lhs,Rhs>
concat_impl( Lhs const& lhs, Rhs const& rhs, seq<I1...>, seq<I2...>)
{
  // the '\0' adds to symmetry:
  return {{ lhs[I1]..., rhs[I2]..., '\0' }};
}

template<class Lhs, class Rhs>
constexpr const combined_string<Lhs,Rhs>
concat(Lhs const& lhs, Rhs const& rhs)
{
  return concat_impl(
    lhs, rhs,
    gen_seq<string_length<Lhs>{}>{},
    gen_seq<string_length<Rhs>{}>{}
 );
}

template<class T0, class T1, class... Ts>
constexpr const combined_string<T0, T1, Ts...>
concat(T0 const&t0, T1 const&t1, Ts const&...ts)
{
  return concat(t0, concat(t1, ts...));
}

template<class T>
constexpr const combined_string<T>
concat(T const&t) {
  return concat(t, "");
}
constexpr const combined_string<>
concat() {
  return concat("");
}

live example

Answer 2

With C++17 the solution becomes very simple (here's the live version):

#include <initializer_list>

// we cannot return a char array from a function, therefore we need a wrapper
template <unsigned N>
struct String {
  char c[N];
};

template<unsigned ...Len>
constexpr auto cat(const char (&...strings)[Len]) {
  constexpr unsigned N = (... + Len) - sizeof...(Len);
  String<N + 1> result = {};
  result.c[N] = '\0';

  char* dst = result.c;
  for (const char* src : {strings...}) {
    for (; *src != '\0'; src++, dst++) {
      *dst = *src;
    }
  }
  return result;
}

// can be used to build other constexpr functions
template<unsigned L>
constexpr auto makeCopyright(const char (&author)[L]) {
  return cat("\xC2\xA9 ", author);
}

constexpr char one[] = "The desert was the apotheosis of all deserts";
constexpr char two[] = "huge, standing to the sky";

constexpr auto three = cat(
  cat(one, ", ", two).c, // can concatenate recursively
  " ",
  "for what looked like eternity in all directions."); // can use in-place literals

constexpr auto phrase = cat(
  three.c, // can reuse existing cats
  "\n",
  makeCopyright("Stephen King").c);

#include <cstdio>
int main() {
  puts(phrase.c);
  return 0;
}

Answer 3

Since C++20 std::copy family of functions is constexpr, so you can further simplify @spiderface answer:

template<unsigned ...Len>
constexpr auto cat(const char (&...strings)[Len]) {
  constexpr unsigned N = (... + Len) - sizeof...(Len);
  std::array<char, N + 1> result = {};
  result[N] = '\0';

  auto it = result.begin();
  (void)((it = std::copy_n(strings, Len-1, it), 0), ...);
  return result;
}

See https://godbolt.org/z/6xsMcqoor

Answer 4

Another way to fix compatibility issues with old 'partial' C++11 compilers is to get rid of using decltype entirely. I experimented with this, and found a way that exploits the type system similar to how this compile-time Turing machine works. The approach also does not use std::array, and allows to assign results to fully working constexpr const char* variables.

1. Introduce some C++14 features in C++11:

    // Parameter pack helpers (similar to C++14)
    template<std::size_t ...> struct _index_sequence { using type = _index_sequence; };
    template<std::size_t N, std::size_t ... S> struct gen_pack_sequence: gen_pack_sequence<N - 1, N - 1, S...> {};
    template<std::size_t ... S> struct gen_pack_sequence<0, S...> : _index_sequence<S...> {};
    template<std::size_t N> using _make_index_sequence = typename gen_pack_sequence<N>::type;
   

2. Several of the TypeList templates from the Turing machine, with two additional features:

    template<typename List> struct PopFront;
    template<typename OldItem, typename ... Items> struct PopFront<TypeList<OldItem, Items...>> { typedef TypeList<Items...> type; };
   
    template<typename ... T> struct ConcatStringList;
    template<typename S, typename ... First, typename ... Second, typename ... Tail> struct ConcatStringList<TypeList<First...>, TypeList<S, Second...>, Tail...> {
        typedef typename ReplaceItem<TypeList<First...>, GetSize<TypeList<First...>>::value - 1, S>::type first;
        typedef typename PopFront<TypeList<S, Second...>>::type second;
        typedef typename ConcatList<first, second>::type concat;
        typedef typename ConcatStringList<concat, Tail...>::type type;
    };
    template<typename T> struct ConcatStringList<T> { typedef T type; };
   

3. A templated struct to contain the data:

    template<char ... Chars> struct to_list { typedef typelist::TypeList<typelist::Char<Chars>...> type; };
    template<char ... Chars> struct char_sequence {
        static constexpr char value[] = { Chars... };
        typedef typename to_list<Chars...>::type list;
        template<template<char...> class Template> using param_pack = Template<Chars...>;
    };
    template<char ... Chars> constexpr char char_sequence<Chars...>::value[];
    template<char ... Chars> struct char_string: char_sequence<Chars..., '\0'> {};
   

4. Conversion from TypeList:

    template<typename CharList, typename = _make_index_sequence<typelist::GetSize<CharList>::value>> struct list_to_string;
    template<typename CharList, std::size_t ... Indices> struct list_to_string<CharList, _index_sequence<Indices...>> {
        static_assert(sizeof...(Indices) > 0 && typelist::GetItem<CharList, sizeof...(Indices) - 1>::type::value == 0, "missing null-termination");
        typedef char_sequence<typelist::GetItem<CharList, Indices>::type::value...> type;
    };
   

5. Helper to define constexpr literals:

    constexpr std::size_t _strlen(char const* s, std::size_t count = 0) {
        return (*s == '\0') ? count : _strlen(s + 1, count + 1);
    }
    template<typename S, typename T> struct _struct_to_string;
    template<typename S, std::size_t ... Indices> struct _struct_to_string<S, _index_sequence<Indices...>> { typedef char_string<S::get()[Indices] ...> type; };
    template<typename S> struct struct_to_string { typedef _make_index_sequence<_strlen(S::get())> indices; typedef typename _struct_to_string<S, indices>::type type; };
    #define CONSTEXPR_STRING(name, s) \
        struct name ## __struct { constexpr static const char* get() { return s; } }; \
        typedef struct_to_string<name ## __struct>::type name
   

6. Finally, the struct for string concatenation:

    template<typename ... Strings> struct concatenate {
        template<typename String> using list = typename String::list;
        typedef typename list_to_string<typename typelist::ConcatStringList<list<Strings>...>::type>::type type;
    };
   

Usable like so:

// ['year', 'month' and 'day' are not literals but somehow obtained earlier]
CONSTEXPR_STRING(dot, ".");
typedef concatenate<year, dot, month, dot, day>::type date;
constexpr const char* c_date = date::value;

It compiles with GCC 4.9.4. (I can also confirm that it works with GCC 4.8.5.)