Почему for-loop не является выражением времени компиляции?

Если я хочу сделать что-то вроде итерации по кортежу, мне приходится прибегать к сумасшедшим метапрограммированию шаблонов и специализированным помощникам шаблонов. Например, следующая программа не будет работать:

#include <iostream>
#include <tuple>
#include <utility>

constexpr auto multiple_return_values()
{
    return std::make_tuple(3, 3.14, "pi");
}

template <typename T>
constexpr void foo(T t)
{
    for (auto i = 0u; i < std::tuple_size<T>::value; ++i)
    {
        std::get<i>(t);
    }    
}

int main()
{
    constexpr auto ret = multiple_return_values();
    foo(ret);
}

Потому что i не может быть const или мы не сможем его реализовать. Но для циклов есть конструкция времени компиляции, которая может быть оценена статически. Компиляторы могут свободно его удалять, преобразовывать, складывать, разворачивать или делать все, что захотят, благодаря правилу as-if. Но тогда почему нельзя использовать контуры в constexpr? В этом коде ничего не должно быть сделано в "runtime". Это подтверждают оптимизация компилятора.

Я знаю, что вы могли бы изменить i внутри тела цикла, но компилятор все равно сможет его обнаружить. Пример:

// ...snip...

template <typename T>
constexpr int foo(T t)
{
    /* Dead code */
    for (auto i = 0u; i < std::tuple_size<T>::value; ++i)
    {
    }    
    return 42;
}

int main()
{
    constexpr auto ret = multiple_return_values();
    /* No error */
    std::array<int, foo(ret)> arr;
}

Так как std::get<>() является конструкцией времени компиляции, в отличие от std::cout.operator<<, я не могу понять, почему это запрещено.

Ответ 1

πάντα ῥεῖ дал хороший и полезный ответ, хотелось бы упомянуть еще один вопрос, но с constexpr for.

В С++ на самом фундаментальном уровне все выражения имеют тип, который можно определить статически (во время компиляции). Конечно, есть такие вещи, как RTTI и boost::any, но они построены поверх этой структуры, а статический тип выражения является важной концепцией для понимания некоторых правил в стандарте.

Предположим, что вы можете перебирать гетерогенный контейнер с использованием синтаксиса для синтаксиса, например:

std::tuple<int, float, std::string> my_tuple;
for (const auto & x : my_tuple) {
  f(x);
}

Здесь f - некоторая перегруженная функция. Понятно, что предполагаемое значение этого метода заключается в вызове различных перегрузок f для каждого из типов в кортеже. Это действительно означает, что в выражении f(x) разрешение перегрузки должно выполняться три раза. Если мы будем играть по текущим правилам С++, единственный способ это может иметь смысл - если мы в основном разворачиваем цикл в три разных тела цикла, прежде чем мы попытаемся выяснить, каковы типы выражений.

Что делать, если на самом деле код

for (const auto & x : my_tuple) {
  auto y = f(x);
}

auto не волшебство, это не означает "нет информации типа", это означает "вывести тип, пожалуйста, компилятор". Но ясно, что в общем случае действительно должны быть три разных типа y.

С другой стороны, есть сложные проблемы с подобным делом - в С++ парсер должен знать, какие имена являются типами и какие имена являются шаблонами, чтобы правильно разобрать язык. Можно ли изменить синтаксический анализатор для выполнения циклического цикла циклов constexpr for до того, как все типы будут разрешены? Я не знаю, но я думаю, что это может быть нетривиально. Может быть, есть лучший способ...

Чтобы избежать этой проблемы, в текущих версиях С++ люди используют шаблон посетителя. Идея состоит в том, что у вас будет перегруженная функция или объект функции, и она будет применена к каждому элементу последовательности. Тогда каждая перегрузка имеет свое "тело", поэтому нет никакой двусмысленности в отношении типов или значений переменных в них. Существуют библиотеки типа boost::fusion или boost::hana, которые позволяют выполнять итерацию по гетерогенным последовательностям с использованием заданного vistior - вы должны использовать свой механизм вместо цикла for.

Если вы можете сделать constexpr for только с помощью ints, например

for (constexpr i = 0; i < 10; ++i) { ... }

возникает такая же сложность, как и гетерогенная для цикла. Если вы можете использовать i в качестве параметра шаблона внутри тела, тогда вы можете создавать переменные, которые относятся к разным типам в разных прогонах тела цикла, а затем не ясно, какими должны быть статические типы выражений.

Итак, я не уверен, но я думаю, что могут быть некоторые нетривиальные технические проблемы, связанные с фактическим добавлением функции constexpr for к языку. Шаблон посетителя/планируемые функции отражения могут оказаться меньше головной боли ИМО... кто знает.

Позвольте мне привести еще один пример, который я только что подумал о том, что показывает трудность.

В обычном С++ компилятор знает статический тип каждой переменной в стеке и поэтому может вычислить макет фрейма стека для этой функции.

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

std::array<int, 3> a{{1,2,3}};
for (int i = 0; i < 3; ++i) {
    auto x = a[i];
    int y = 15;
    std::cout << &y << std::endl;
}

В этом коде y является локальной переменной в теле цикла for. Он имеет четко определенный адрес во всей этой функции, а адрес, напечатанный компилятором, будет одинаковым каждый раз.

Каким должно быть поведение аналогичного кода с constexpr для?

std::tuple<int, long double, std::string> a{};
for (int i = 0; i < 3; ++i) {
    auto x = std::get<i>(a);
    int y = 15;
    std::cout << &y << std::endl;
}

Дело в том, что тип x выводится по-разному в каждом проходе через цикл - поскольку он имеет другой тип, он может иметь разный размер и выравнивание в стеке. Поскольку y появляется после него в стеке, это означает, что y может изменить свой адрес на разных прогонах цикла - правильно?

Каким должно быть поведение, если указатель на y принимается за один проход через цикл, а затем разыменован в более позднем проходе? Должно ли быть поведение undefined, хотя оно, вероятно, было бы законным в аналогичном коде "no-constexpr for" с std::array, показанным выше?

Нельзя ли изменить адрес y? Должен ли компилятор заполнить адрес y так, чтобы наибольший из типов в кортеже можно было разместить до y? Означает ли это, что компилятор не может просто развернуть циклы и начать генерировать код, но должен развернуть каждый экземпляр цикла до-стороны, а затем собрать всю информацию о типе из каждого из экземпляров N, а затем найти удовлетворительный макет?

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

Ответ 2

Вот способ сделать это, который не требует слишком много шаблонов, вдохновленный fooobar.com/questions/311809/...:

template<std::size_t N>
struct num { static const constexpr auto value = N; };

template <class F, std::size_t... Is>
void for_(F func, std::index_sequence<Is...>)
{
  using expander = int[];
  (void)expander{0, ((void)func(num<Is>{}), 0)...};
}

template <std::size_t N, typename F>
void for_(F func)
{
  for_(func, std::make_index_sequence<N>());
}

Тогда вы можете сделать:

for_<N>([&] (auto i) {      
  std::get<i.value>(t); // do stuff
});

Если у вас есть доступный компилятор С++ 17, его можно упростить до

template <class F, std::size_t... Is>
void for_(F func, std::index_sequence<Is...>)
{
  (func(num<Is>{}), ...);
}

Ответ 3

Почему выражение for-loop не является циклом?

Поскольку цикл for() используется для определения потока управления временем выполнения на языке С++.

В целом переменные шаблоны не могут быть распакованы в операциях потока управления runtime в С++.

 std::get<i>(t);

не может быть выведено во время компиляции, так как i является переменной времени выполнения.

Вместо этого используйте вариант распаковки параметров вариационного шаблона.

Вы также можете найти это сообщение полезным (если это даже не замечает дубликат, отвечающий на ваш вопрос):

перебирать кортеж

Ответ 4

В С++ 20 большинство функций std::algorithm будут constexpr. Например, используя std::transform, многие операции, требующие цикла, могут выполняться во время компиляции. Рассмотрим этот пример расчета факториала каждого числа в массиве во время компиляции (адаптировано из документации Boost.Hana):

#include <array>
#include <algorithm>

constexpr int factorial(int n) {
    return n == 0 ? 1 : n * factorial(n - 1);
}

template <typename T, std::size_t N, typename F>
constexpr std::array<std::result_of_t<F(T)>, N>
transform_array(std::array<T, N> array, F f) {
    auto array_f = std::array<std::result_of_t<F(T)>, N>{};
    // This is a constexpr "loop":
    std::transform(array.begin(), array.end(), array_f.begin(), [&f](auto el){return f(el);});
    return array_f;
}

int main() {
    constexpr std::array<int, 4> ints{{1, 2, 3, 4}};
    // This can be done at compile time!
    constexpr std::array<int, 4> facts = transform_array(ints, factorial);
    static_assert(facts == std::array<int, 4>{{1, 2, 6, 24}}, "");
}

Посмотрите, как массив facts может быть вычислен во время компиляции с использованием "цикла", то есть std::algorithm. На момент написания этой статьи вам нужна экспериментальная версия новейшего релиза clang или gcc, которую вы можете попробовать на godbolt.org. Но вскоре С++ 20 будет полностью реализован всеми основными компиляторами в релизных версиях.