[trick] compile-time template engine

// Version 1
{
    int counter = 2;
    char character = '!';
    double value = 0.5;

    for_each_part
    (
        auto x,
        "val = $value$, cnt = $counter$, ch = $character$, again v=$value$;\n",
        counter, character, value
    )
    {
        print_it(x);
    };
}

// Version 2
{
    int counter = 2;
    char character = '!';
    double value = 0.5;

    auto print = [](auto x)
    {
        print_it(x);
    };
    process_format
    (
        print,
        "val = $value$, cnt = $counter$, ch = $character$, again v=$value$;\n",
        counter, character, value
    );
}

Вывод в обоих случаях:

val = 0.5, cnt = 2, ch = !, again v=0.5;

Github: CTTE, LIVE DEMO

реализация

// Copyright Evgeny Panasyuk 2014.
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

// e-mail: E?????[dot]P???????[at]gmail.???

// Compile-time template engine

// GOTO main

#include <boost/preprocessor/variadic/to_seq.hpp>
#include <boost/preprocessor/seq/for_each.hpp>
#include <boost/fusion/container.hpp>
#include <boost/fusion/sequence.hpp>
#include <boost/mpl/assert.hpp>
#include <boost/mpl/apply.hpp>
#include <initializer_list>
#include <cstddef>
#include <utility>

namespace CTTE
{
    /************************************************************************************************/
    // boost utils

    template<typename Lambda, typename X>
    auto make_pair(Lambda, X x)
    {
        return boost::fusion::make_pair<Lambda>(std::move(x));
    }

    template<typename Lambda, typename ...Ts>
    using mpl_apply = typename boost::mpl::apply<Lambda, Ts...>::type;
    /************************************************************************************************/
    // null terminated string utils

    template<typename I, typename T>
    constexpr I find(I first, T x)
    {
        return *first == x ? first : find(first+1, x);
    }
    /* C++14
    template<typename I, typename T>
    constexpr I find(I first, T x)
    {
        while(*first != x)
            ++first;
        return first;
    }*/

    constexpr std::size_t c_str_length(const char *x)
    {
        return find(x, '\0') - x;
    }
    /************************************************************************************************/
    // Compile time string encoded in type

    template<char... cs>
    struct string_value
    {
        static constexpr const char value[sizeof...(cs)+1] = {cs..., '\0'};
    };
    template<char... cs>
    constexpr const char string_value<cs...>::value[sizeof...(cs)+1];

    template<char... cs>
    struct string
    {
        //using mpl_string = mpl::string<cs...>;
        using value_type = string_value<cs...>;
    };

    template<typename, typename> struct make_string_aux;

    template<typename String, std::size_t ...Is>
    struct make_string_aux<String, std::index_sequence<Is...>>
    {
        using type = string<String::value()[Is]...>;
    };

    template<typename String, std::size_t length = c_str_length(String::value())>
    using make_string = typename make_string_aux
    <
        String, std::make_index_sequence<length>
    >::type;
    /************************************************************************************************/
    // Split string by delimiter into prefix = [first, delimiter),
    // and suffix = (delimiter, last]

    template<typename String, char delimiter, typename Prefix = string<>>
    struct split_string;

    template<char... suffix_cs, char delimiter, char... prefix_cs>
    struct split_string
    <
        string<delimiter, suffix_cs...>,
        delimiter,
        string<prefix_cs...>
    >
    {
        using prefix = string<prefix_cs...>;
        using suffix = string<suffix_cs...>;
    };

    template<char first, char... suffix_cs, char delimiter, char... prefix_cs>
    struct split_string
    <
        string<first, suffix_cs...>,
        delimiter,
        string<prefix_cs...>
    >
    {
        using aux = split_string
        <
            string<suffix_cs...>,
            delimiter,
            string<prefix_cs..., first>
        >;
        using prefix = typename aux::prefix;
        using suffix = typename aux::suffix;
    };

    template<char delimiter, char... prefix_cs>
    struct split_string<string<>, delimiter, string<prefix_cs...>>
    {
        using prefix = string<prefix_cs...>;
        using suffix = string<>;
    };
    /************************************************************************************************/
    template<typename...> struct vector {};

    template<typename String, typename Actions, typename ParsedActions = vector<>>
    struct split_by_actions;

    template<typename String, typename CurrentAction, typename ...Actions, typename ...ParsedActions>
    struct split_by_actions
    <
        String,
        vector<CurrentAction, Actions...>,
        vector<ParsedActions...>
    >
    {
        using splited = split_string<String, '$'>;
        using action = mpl_apply<CurrentAction, typename splited::prefix>;
        using shifted_actions = vector<Actions..., CurrentAction>;

        using type = typename split_by_actions
        <
            typename splited::suffix,
            shifted_actions,
            vector<ParsedActions..., action>
        >::type;
    };

    template<typename CurrentAction, typename ...Actions, typename ...ParsedActions>
    struct split_by_actions<string<>, vector<CurrentAction, Actions...>, vector<ParsedActions...>>
    {
        using type = vector<ParsedActions...>;
    };
    /************************************************************************************************/
    #define CTTE_WRAP_STRING(x) \
        [] \
        { \
            struct { static constexpr auto value() { return x;} } str; \
            return str; \
        } \
    /**/
    #define CTTE_STRING_HOLDER(X) decltype(std::declval<X>()())
    #define CTTE_MAKE_STRING(X) CTTE::make_string<CTTE_STRING_HOLDER(X)>

    #define CTTE_CAPTURE_VAR(x) CTTE::make_pair(CTTE_WRAP_STRING(#x), &x)
    #define CTTE_CAPTURE_VAR_AUX(r, data, elem) , CTTE_CAPTURE_VAR(elem)
    /************************************************************************************************/   
    template<typename ...Pairs>
    auto make_context(Pairs... pairs)
    {
        return boost::fusion::make_map
        <
            CTTE_MAKE_STRING(typename Pairs::first_type)...
        >(std::move(pairs.second)...);
    };
    /************************************************************************************************/
    template<typename Action, typename ...Actions, typename Context, typename F>
    auto apply_actions(vector<Action, Actions...>, Context context, F f)
    {
        return apply_actions(vector<Actions...>{}, context, Action{}(context, f));
    }

    template<typename Context, typename F>
    auto apply_actions(vector<>, Context, F f)
    {
        return f;
    }

    /* Non-recursion version, but with different semantics:
    template<typename ...Actions, typename Context, typename F>
    void apply_actions(vector<Actions...>, Context context, F f)
    {
        (void)initializer_list<int>{( Actions{}(context, f) , 0)...};
        return f;
    }*/
    /************************************************************************************************/
    template<typename String>
    struct StringAction
    {
        template<typename Context, typename F>
        F operator()(Context, F f)
        {
            f( String::value_type::value );
            return f;
        }
    };

    template<typename Variable>
    struct VariableAction
    {
        template<typename Context, typename F>
        F operator()(Context context, F f)
        {
            BOOST_MPL_ASSERT_MSG
            (
                (boost::fusion::result_of::has_key<Context, Variable>::type::value),
                WRONG_VARIABLE_NAME_IN_FORMAT_STRING,
                (Variable)
            );

            f( *boost::fusion::at_key<Variable>(context) );
            return f;
        }
    };

    template<typename Format>
    using make_actions = typename split_by_actions
    <
        Format,
        vector<StringAction<boost::mpl::_>, VariableAction<boost::mpl::_>>
    >::type;
    /************************************************************************************************/
    // function-like version:

    template<typename F, typename Format, typename ...Pairs>
    auto process_format_aux(F f, Format, Pairs... pairs)
    {
        return apply_actions
        (
            make_actions<CTTE_MAKE_STRING(Format)>{},
            make_context(pairs...),
            std::move(f)
        );
    }

    #define process_format(f, format, ...) \
        CTTE::process_format_aux \
        ( \
            f, \
            CTTE_WRAP_STRING(format) \
            BOOST_PP_SEQ_FOR_EACH(CTTE_CAPTURE_VAR_AUX, _, BOOST_PP_VARIADIC_TO_SEQ(__VA_ARGS__)) \
        ) \
    /**/
    /************************************************************************************************/
    // for-like version:

    template<typename Context, typename Format>
    struct for_each_part_aux_operator
    {
        Context context;
        template<typename F>
        F operator*(F f)
        {
            return apply_actions(make_actions<CTTE_MAKE_STRING(Format)>{}, context, std::move(f));
        }
    };

    template<typename Format, typename ...Pairs>
    auto for_each_part_aux(Format, Pairs... pairs)
    {
        auto context = make_context(pairs...);
        return for_each_part_aux_operator<decltype(context), Format>{std::move(context)};
    }
    #define for_each_part(loop_parameter, format, ...) \
        CTTE::for_each_part_aux \
        ( \
            CTTE_WRAP_STRING(format) \
            BOOST_PP_SEQ_FOR_EACH(CTTE_CAPTURE_VAR_AUX, _, BOOST_PP_VARIADIC_TO_SEQ(__VA_ARGS__)) \
        ) * [&](loop_parameter)\
    /**/
} // namespace end
/************************************************************************************************/
#include <iostream>

#ifdef __GNUC__
    #define NOINLINE __attribute__((noinline))
#else
    #define NOINLINE
#endif

template<typename T>
NOINLINE void print_it(T x)
#if 1
{
    std::cout << x;
}
#else
;
#endif

NOINLINE void test_handwritten()
{
    int counter = 2;
    char character = '!';
    double value = 0.5;

    print_it("val = ");
    print_it(value);
    print_it(", cnt = ");
    print_it(counter);
    print_it(", ch = ");
    print_it(character);
    print_it(", again v=");
    print_it(value);
    print_it(";\n");
}

NOINLINE void test_process_format()
{
    int counter = 2;
    char character = '!';
    double value = 0.5;

    auto print = [](auto x)
    {
        print_it(x);
    };
    process_format(print, "val = $value$, cnt = $counter$, ch = $character$, again v=$value$;\n", counter, character, value);
}

NOINLINE void test_for_each_part()
{
    int counter = 2;
    char character = '!';
    double value = 0.5;

    for_each_part(auto x, "val = $value$, cnt = $counter$, ch = $character$, again v=$value$;\n", counter, character, value)
    {
        print_it(x);
    };
}

int main()
{
    test_handwritten();
    test_process_format();
    test_for_each_part();
}

Ручная версия выглядит вот так:

{
    int counter = 2;
    char character = '!';
    double value = 0.5;

    print_it("val = ");
    print_it(value);
    print_it(", cnt = ");
    print_it(counter);
    print_it(", ch = ");
    print_it(character);
    print_it(", again v=");
    print_it(value);
    print_it(";\n");
}

Сравниваем результирующий ассемблерный код:

asm

    .globl    _Z16test_handwrittenv
    .align    16, 0x90
    .type    _Z16test_handwrittenv,@function
_Z16test_handwrittenv:                  # @_Z16test_handwrittenv
    .cfi_startproc
# BB#0:
    pushq    %rax
.Ltmp0:
    .cfi_def_cfa_offset 16
    movl    $.L.str, %edi
    callq    _Z8print_itIPKcEvT_
    movsd    .LCPI0_0(%rip), %xmm0
    callq    _Z8print_itIdEvT_
    movl    $.L.str1, %edi
    callq    _Z8print_itIPKcEvT_
    movl    $2, %edi
    callq    _Z8print_itIiEvT_
    movl    $.L.str2, %edi
    callq    _Z8print_itIPKcEvT_
    movl    $33, %edi
    callq    _Z8print_itIcEvT_
    movl    $.L.str3, %edi
    callq    _Z8print_itIPKcEvT_
    movsd    .LCPI0_0(%rip), %xmm0
    callq    _Z8print_itIdEvT_
    movl    $.L.str4, %edi
    popq    %rax
    jmp    _Z8print_itIPKcEvT_     # TAILCALL
.Ltmp1:
    .size    _Z16test_handwrittenv, .Ltmp1-_Z16test_handwrittenv
    .cfi_endproc

    .globl    _Z18test_for_each_partv
    .align    16, 0x90
    .type    _Z18test_for_each_partv,@function
_Z18test_for_each_partv:                # @_Z18test_for_each_partv
    .cfi_startproc
# BB#0:
    pushq    %rax
.Ltmp11:
    .cfi_def_cfa_offset 16
    movl    $_ZN4CTTE12string_valueIJLc118ELc97ELc108ELc32ELc61ELc32EEE5valueE, %edi
    callq    _Z8print_itIPKcEvT_
    movsd    .LCPI6_0(%rip), %xmm0
    callq    _Z8print_itIdEvT_
    movl    $_ZN4CTTE12string_valueIJLc44ELc32ELc99ELc110ELc116ELc32ELc61ELc32EEE5valueE, %edi
    callq    _Z8print_itIPKcEvT_
    movl    $2, %edi
    callq    _Z8print_itIiEvT_
    movl    $_ZN4CTTE12string_valueIJLc44ELc32ELc99ELc104ELc32ELc61ELc32EEE5valueE, %edi
    callq    _Z8print_itIPKcEvT_
    movl    $33, %edi
    callq    _Z8print_itIcEvT_
    movl    $_ZN4CTTE12string_valueIJLc44ELc32ELc97ELc103ELc97ELc105ELc110ELc32ELc118ELc61EEE5valueE, %edi
    callq    _Z8print_itIPKcEvT_
    movsd    .LCPI6_0(%rip), %xmm0
    callq    _Z8print_itIdEvT_
    movl    $_ZN4CTTE12string_valueIJLc59ELc10EEE5valueE, %edi
    popq    %rax
    jmp    _Z8print_itIPKcEvT_     # TAILCALL
.Ltmp12:
    .size    _Z18test_for_each_partv, .Ltmp12-_Z18test_for_each_partv
    .cfi_endproc

    .globl    _Z19test_process_formatv
    .align    16, 0x90
    .type    _Z19test_process_formatv,@function
_Z19test_process_formatv:               # @_Z19test_process_formatv
    .cfi_startproc
# BB#0:
    pushq    %rax
.Ltmp9:
    .cfi_def_cfa_offset 16
    movl    $_ZN4CTTE12string_valueIJLc118ELc97ELc108ELc32ELc61ELc32EEE5valueE, %edi
    callq    _Z8print_itIPKcEvT_
    movsd    .LCPI5_0(%rip), %xmm0
    callq    _Z8print_itIdEvT_
    movl    $_ZN4CTTE12string_valueIJLc44ELc32ELc99ELc110ELc116ELc32ELc61ELc32EEE5valueE, %edi
    callq    _Z8print_itIPKcEvT_
    movl    $2, %edi
    callq    _Z8print_itIiEvT_
    movl    $_ZN4CTTE12string_valueIJLc44ELc32ELc99ELc104ELc32ELc61ELc32EEE5valueE, %edi
    callq    _Z8print_itIPKcEvT_
    movl    $33, %edi
    callq    _Z8print_itIcEvT_
    movl    $_ZN4CTTE12string_valueIJLc44ELc32ELc97ELc103ELc97ELc105ELc110ELc32ELc118ELc61EEE5valueE, %edi
    callq    _Z8print_itIPKcEvT_
    movsd    .LCPI5_0(%rip), %xmm0
    callq    _Z8print_itIdEvT_
    movl    $_ZN4CTTE12string_valueIJLc59ELc10EEE5valueE, %edi
    popq    %rax
    jmp    _Z8print_itIPKcEvT_     # TAILCALL
.Ltmp10:
    .size    _Z19test_process_formatv, .Ltmp10-_Z19test_process_formatv
    .cfi_endproc

Результирующий ассемблер во всех трёх случаях идентичен, отличаются только идентификаторы

Основные моменты

Строки

Хотя многие ограничения с constexpr функций и сняли в C++14 — например, можно использовать локальные переменные, statement'ы, while/if/for — но использовать только их при решении определённых задач не получится, приходится возвращаться к чистому функциональному программированию на шаблонах.
Главное ограничение в том, что из constexpr функции нельзя вернуть структуру данных, размер которой зависит от обычных параметров (нешаблонных). Например нельзя распарсить строку и вернуть её AST, хотя просто дать ответ — соответсвует ли строка заданной грамматике — вполне возможно.
Один из вариантов обхода ограничения — использовать структуры данных заведомо большего размера, а где-то внутри при нехватке буфера делать static assert false, чтобы пользователь увеличил размер выходного буфера.
Основная проблема в том, делать new нельзя, и размер любой структуры должен быть каким-либо образом закодирован в её типе, а тип результата не зависит от входных параметров (нешаблонных). Есть конечно std::initializer_list, размер которого не закодирован в типе и известен во время компиляции, но завести его на Clang у меня не получилось.

Итак, обойтись без шаблонного ФП полностью не получится, нужен некий мостик между constexpr строками, и системой типов.
Нужно либо каким-то образом загнать все символы в variadic список шаблонных параметров, либо передать шаблонным параметром тип, который однозначно зависит от constexpr строки (а потом уже внутри, по необходимости, можно и загнать все символы в шаблонные параметры — это дело техники).

Вариант с прямым загоном символов в шаблонные параметры, без промежуточных типов, описан в статье "Using strings in C++ template metaprograms" (Abel Sinkovics and Dave Abrahams).
Это выглядит вот так (live demo):

Скрытый текст

#include <boost/preprocessor/repetition/repeat.hpp>
#define GET_STR_AUX(_, i, str) (sizeof(str) > (i) ? str[(i)] : 0),
#define GET_STR(str) BOOST_PP_REPEAT(64,GET_STR_AUX,str) 0
/*********************************************************************/
template<char...> struct sequence;

template<typename T>
void type_is();

int main()
{
    type_is<sequence<GET_STR("Hello world!")>>();
}
// Compile error: undefined reference to `void type_is<sequence<(char)72, (char)101, (char)108, (char)108, (char)111, (char)32, (char)119, (char)111, (char)114, (char)108, (char)100, (char)33, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0, (char)0> >()'

Недостатков тут много. Во-первых максимальный размер задаётся жёстко, во-вторых после препроцессора будет много кода (строка из 50 символов, должна быть как минимум скопирована 50 раз при таком подходе).

Теперь рассмотрим вариант с передачей шаблонного параметра.
Было бы здорово передать constexpr объект, со строкой внутри, в виде non-type template parameter, но увы это не разрешено стандартом (на эту тему есть proposal N3413).

struct compile_time_string
{
    const char *s;
};

int main()
{
    constexpr compile_time_string s = {"abc"};
    static_assert(s.s[0] == 'a', ""); // passes
}

template<compile_time_string s> // compile error
struct some;

Другой вариант вот такой:

struct specific_compiletime_string
{
    static constexpr const char *s = "abc";
};
static_assert(specific_compiletime_string::s[0] == 'a', ""); // passes

То есть для каждой строки мы заводим отдельный конкретный тип. Такой вариант в принципе рабочий, но проблема в том, что такую штуку нельзя сделать внутри функции:

error: static data member 's' not allowed in local class 'specific_compiletime_string'

Что накладывает существенные ограничения на удобство использования — пользователю пришлось бы объявлять все compile-time строки вне функций, что хотя и работает, но далеко не айс.

Следующий вариант описан вот в этом SO.

int main()
{
    struct specific_compiletime_string
    {
        static constexpr const char *value()
        {
            return "abc";
        }
    };
    static_assert(specific_compiletime_string::value()[0] == 'a', ""); // passes!
}

Ну что ж, ещё один шаг навстречу эргономике. Недостаток это варианта в том, что структура должна объявляться в отдельном statement'е — это конечно можно обвернуть в макрсос, и в принципе рабочий вариант, но всё же не всегда удобно. Хотелось бы чтобы строку можно было определить внутри выражения, не выходя из него.

Следующим шагом является заворачивание нашей структуры в лямбду, которая определяется уже в пределах одного выражения (собственно, в результате чего я наткнулся на emulation of "anonymous types"):

int main()
{
    auto lambda = []
    {
        struct
        {
            static constexpr const char *value()
            {
                return "abc";
            }
        } string;
        return string;
    };
    using s = decltype(lambda());
    static_assert(s::value()[0] == 'a', ""); // passes!
}

Этот вариант описан вот в этом SO.
Небольшое неудобство в том, что лямбду нельзя поместить в decltype, и получить тип сразу по месту.
Но это не так существенно — мы можем передавать её как аргумент шаблонной функции. Такая лямбда внутри пустая, и нам важен только её тип, а само значение мы можем игнорировать, и никакого overhead'а тут быть не должно.

Итак, передавать строки шаблонными параметрами мы научились. Разобрать такие строки на отдельные символы и передать их как последовательность non-type template параметров тоже не проблема, а уже с этой последовательностью можно делать любые compile-time манипуляции(хоть Python интерпретируй!).

Захват переменных

Возвращаемся к исходной задаче: наша compile-time форматная строка ссылается на переменные через их имена. Значит нам нужно получить эти самые строчки-имена переменных. Тут всё предельно просто — пользуемся препроцессорным stringification #x

#define CTTE_CAPTURE_VAR(x) CTTE::make_pair(CTTE_WRAP_STRING(#x), &x)

Где CTTE_WRAP_STRING возвращает ту самую лямду, а make_pair выглядит следующим образом:

template<typename Lambda, typename X>
auto make_pair(Lambda, X x)
{
    return boost::fusion::make_pair<Lambda>(std::move(x));
}

Такая пара содержит тип лямбды (без значения), и значение второго элемента (в нашем случае указатель на переменную).
А далее, из этих пар (мы можем захватывать много переменных), мы делаем контекст на базе boost::fusion::map:

template<typename ...Pairs>
auto make_context(Pairs... pairs)
{
    return boost::fusion::make_map
    <
        CTTE_MAKE_STRING(typename Pairs::first_type)...
    >(std::move(pairs.second)...);
};

где CTTE_MAKE_STRING разбирает лямбду на отдельные символы, и возвращает тип вида string<'v', 'a', 'r'>.
Это отображение позваляет нам в compile-time, по строке (имя переменной), находить искомое runtime значение (её адрес).

Разбор форматной строки

В данном конкретном случае формат у нас простой (хотя возможен и Jinja-like), поэтому задача предельно механическая: находим первый разделительный символ (например, с помощью boost::mpl::find), и бьём по нему строку на prefix и suffix.
prefix содержит либо непосредственно подстроку которую нужно вывести как она есть, либо имя переменной (с помощью которой можно получить указатель на её значение, и впоследствии вывести).
suffix содержит остаток строки, с которым нужно рекурсивно продолжать работу, пока он не станет пустым.

В процессе парсинга создаётся последовательность типов, вида:

boost::mpl::vector
<
    ВыводПодстроки<КонкретнаяПодстрока1>,
    ВыводПеременной<ИмяПеременной1>,
    ВыводПодстроки<КонкретнаяПодстрока2>,
    ВыводПеременной<ИмяПеременной2>,
    // ...
>

Эти типы (semantic action?) имеют внутри шаблонный оператор принимающий контекст и пользовательский функциональный объект.
ВыводПодстроки контекст никак не использует, а просто выводит подстроку:

template<typename Context, typename F>
F operator()(Context, F f)
{
    f( String::value_type::value );
    return f;
}

В то время как ВыводПеременной ищет (во время компиляции) указатель на переменную в контексте и выводит её:

template<typename Context, typename F>
F operator()(Context context, F f)
{
    BOOST_MPL_ASSERT_MSG
    (
        (boost::fusion::result_of::has_key<Context, Variable>::type::value),
        WRONG_VARIABLE_NAME_IN_FORMAT_STRING,
        (Variable)
    );

    f( *boost::fusion::at_key<Variable>(context) );
    return f;
}

Помимо этого, при неправильном имени переменной в форматной строке делается вывод сообщения в качестве ошибки компиляции:

boost::mpl::failed ************(WRONG_VARIABLE_NAME_IN_FORMAT_STRING::************)(CTTE::string<'v', 'a', 'l', 'u', 'e', '1'>)

Пробежавшись по вектору этих действий и скормив им контекст вкупе с пользовательским функциональным объектом — мы и получим требуемый результат.

	От:	Evgeny.Panasyuk
	Дата:	12.10.14 09:35
	Оценка:	182 (11)