Дизайн и эволюция constexpr в C++

в 16:51, , рубрики: c++, clang, constexpr, Компиляторы
Дизайн и эволюция constexpr в C++ - 1

constexpr - одно из самых магических ключевых слов в современном C++. Оно дает возможность создать код, который будет выполнен еще до окончания процесса компиляции, что является абсолютным пределом для быстродействия программ.

У constexpr с каждым годом становится больше возможностей. Сейчас использовать в compile-time вычислениях можно почти всю стандартную библиотеку. Пример вычисления числа до 1000 с наибольшим количеством делителей: ссылка на код.

История constexpr насчитывает долгую историю эволюции с ранних версий C++. Исследуя предложения в стандарт и исходники компиляторов, можно понять, как слой за слоем создавалась эта часть языка, почему именно так она выглядит, как на практике вычисляются constexpr-выражения, какие возможности ждут нас в будущем, а какие - могли бы быть, но не были приняты в Стандарт.

Эта статья подходит как тем, кто еще не знает, что такое constexpr, так и тем, кто уже долгое время его использует.

C++98 и C++03: Сословия среди const-переменных

В C++ в некоторых местах нужно использовать целочисленные константы, значения которых должны быть известны в compile-time. Стандарт разрешает записывать константы в виде несложных выражений, как в этом коде:

enum EPlants {
    APRICOT = 1 << 0,
    LIME = 1 << 1,
    PAPAYA = 1 << 2,
    TOMATO = 1 << 3,
    PEPPER = 1 << 4,
    FRUIT = APRICOT | LIME | PAPAYA,
    VEGETABLE = TOMATO | PEPPER,
};

template<int V> int foo();
int foo6 = foo<1+2+3>();
int foo110 = foo<(1 < 2) ? 10*11 : VEGETABLE>();

int v;
switch (v) {
case 1 + 4 + 7:
case 1 << (5 | sizeof(int)):
case (12 & 15) + PEPPER:
    break;
}

Эти выражения описаны в разделе [expr.const] и называются constant-expression. Они могут содержать только:

  • Литералы (туда входят целые числа, это интегральные типы)

  • Значения enum-ов

  • Параметр шаблона интегрального или enum-типа (напр., значение V из template<int V>)

  • sizeof-выражение

  • const-переменные, инициализированные constant-expression - интересный пункт

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

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

В стандартах C++98/03 есть два вида static initialization:

  1. zero-initialization, память заполняется нулями, затем в ходе программы изменяется

  2. initialization with a constant expression, память (если нужна) сразу содержит вычисленное значение

[Note: Все остальные инициализации называются dynamic initialization, мы их не рассматриваем. — end note]

[Note: zero-initialized переменная во время работы программы в свою очередь может быть проинициализирована еще раз "нормальным" значением, это уже будет dynamic initialization (пусть даже до старта main). — end note]

Рассмотрим пример с обоими видами переменных:

int foo() {
    return 13;
}

const int test1 = 1 + 2 + 3 + 4; // initialization with a const. expr.
const int test2 = 15 * test1 + 8; // initialization with a const. expr.
const int test3 = foo() + 5; // zero-initialization
const int test4 = (1 < 2) ? 10 * test3 : 12345; // zero-initialization
const int test5 = (1 > 2) ? 10 * test3 : 12345; // initialization with a const. expr.

Переменные test1, test2, test5 можно использовать как параметр шаблона, значение справа от case в switch и т.д., а test3 и test4 - нельзя.

Как видно из требований к constant-expression и из примера, есть транзитивность - если какая-то составная часть выражения не является constant-expression, то и само выражение не является constant-expression. При этом рассматриваются только те части выражения, которые реально вычисляются - поэтому test4 и test5 попадают в разные группы.

Если нигде не берется адрес constant-expression переменной, то скомпилированной программе разрешено не резервировать для нее память, поэтому "заставим" ее это сделать. Выведем значения переменных и их адреса:

int main() {
    std::cout << test1 << std::endl;
    std::cout << test2 << std::endl;
    std::cout << test3 << std::endl;
    std::cout << test4 << std::endl;
    std::cout << test5 << std::endl;

    std::cout << &test1 << std::endl;
    std::cout << &test2 << std::endl;
    std::cout << &test3 << std::endl;
    std::cout << &test4 << std::endl;
    std::cout << &test5 << std::endl;
}
izaron@izaron:~/cpp$ clang++ --std=c++98 a.cpp 
izaron@izaron:~/cpp$ ./a.out 
10
158
18
180
12345
0x402004
0x402008
0x404198
0x40419c
0x40200c

Скомпилируем объектный файл и посмотрим на таблицу символов:

izaron@izaron:~/cpp$ clang++ --std=c++98 a.cpp -c
izaron@izaron:~/cpp$ objdump -t -C a.o

a.o:     file format elf64-x86-64

SYMBOL TABLE:
0000000000000000 l    df *ABS*  0000000000000000 a.cpp
0000000000000080 l     F .text.startup  0000000000000015 _GLOBAL__sub_I_a.cpp
0000000000000000 l     O .rodata        0000000000000004 test1
0000000000000004 l     O .rodata        0000000000000004 test2
0000000000000004 l     O .bss   0000000000000004 test3
0000000000000008 l     O .bss   0000000000000004 test4
0000000000000008 l     O .rodata        0000000000000004 test5

В конкретной версии компилятора под конкретную архитектуру, в конкретной программе zero-initialized переменные попали в секцию .bss, остальные в секцию .rodata.

Загрузчик операционной системы перед запуском загружает программу так, что секция .rodata оказывается в сегменте с read-only режимом, который защищен от записи на уровне ОС.

Попробуем через const_cast изменить данные по адресу переменных. Стандарт дает уклончивый ответ на тему того, когда запись в результат const_cast-а может спровоцировать Undefined Behaviour. По крайней мере, этого не происходит, если мы убираем const с объекта/указателя на объект, который не является фундаментально константным изначально. Т.е. надо различать физическую константность и логическую.

UB-санитайзер поймает UB (программа крашится), если попытаться изменить .rodata-переменную, и его не будет, если записывать в .bss или автоматические переменные.

    const int& ref = testX;
    const_cast<int&>(ref) = 13; // OK for test3, test4; SEGV for test1, test2, test3
    std::cout << ref << std::endl;

Таким образом, одни const-переменные "константнее" других. Насколько известно, в то время не было простого способа проверить или как-то проконтролировать, что переменная была initialized with a const. expr.

0-∞: Вычислитель констант в компиляторе

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

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

Clang и LLVM

Про само устройство Clang и LLVM написано уже много статей. На хабре я бы посоветовал эту статью, чтобы понять их краткую историю и общую схему.

Количество стадий компиляций зависит от того, кто объясняет устройство компилятора. Анатомия компилятора многоуровнева и на самом абстрактном уровне выглядит так, что есть три разные программы:

  • Front-end: переводит исходник из C/C++/Ada/Rust/Haskell/... в LLVM IR - особое промежуточное представление. Фронтендом для C-like языков является Clang.

  • Middle-end: LLVM IR оптимизируется в зависимости от настроек.

  • Back-end: LLVM IR переводится в машинный код под нужную платформу - x86/Arm/PowerPC/...

Для простых языков реально написать компилятор под 1000 строк и получить всю мощь фреймворка LLVM - для этого нужно реализовать фронтенд. Также можно использовать lex/yacc - готовые синтаксические парсеры.

На менее абстрактном уровне находится фронтенд Clang, который выполняет такие действия (не рассматривая препроцессор и прочие "микро"-шаги):

  • Лексический анализ: перевод символов в токены, например []() { return 13 + 37; } преобразуются в (l_square) (r_square) (l_paren) (r_paren) (l_brace) (return) (numeric_constant:13) (plus) (numeric_constant:37) (semi) (r_brace).

  • Синтаксический анализ: создание AST (Abstract Syntax Tree), то есть перевод токенов из предыдущего пункта в вид (lambda-expr (body (return-expr (plus-expr (number 13) (number 37))))).

  • Кодогенерация: создание LLVM IR по данному AST.

Итак, вычисление константных выражений (и близкородственных ему вещей, как инстанцирование шаблонов) происходит строго в фронтенде компилятора C++ (в нашем случае в Clang), а LLVM такими вещами не занимается.

"Микросервис", который занимается вычислением константных выражений (от самых простых в C++98 до сложных в C++23), назовем условно вычислитель констант.

Если согласно Стандарту в каком-то месте кода ожидается константное выражение; и выражение, которое там находится, действительно удовлетворяет требованиям на константное выражение, то Clang должен "не отходя от кассы" в 100% случаев уметь вычислять его.

Ограничения на константные выражения на протяжении лет постоянно смягчались, а вычислитель констант Clang соответсвенно постоянно усложнялся, вплоть до управления моделью памяти.

Есть старая документация 9-летней давности, описывающая вычисление констант для C++98/03. Так как константные выражения тогда были очень простыми, они выполнялись с помощью обычного constant folding через анализ синтаксического дерева (AST). Так как в синтаксическом дереве все арифметические выражения уже разобраны в виде под-деревьев, то вычисление константы - просто элементарный обход под-дерева.

Исходник вычислителя констант находится в lib/AST/ExprConstant.cpp и на момент написания статьи разросся до почти 16 тысяч строк. С годами он научился интерпретировать много всего, например циклы (EvaluateLoopBody), и всё это на синтаксическом дереве.

У константных выражений есть важное отличие от кода, выполняющегося в рантайме - они обязаны не допускать undefined behaviour. Если вычислитель констант наткнется на UB, компиляция провалится.

c.cpp:15:19: error: constexpr variable 'foo' must be initialized by a constant expression
    constexpr int foo = 13 + 2147483647;
                  ^     ~~~~~~~~~~~~~~~

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

c.cpp:15:18: warning: overflow in expression; result is -2147483636 with type 'int' [-Winteger-overflow]
    int foo = 13 + 2147483647;
                 ^

2003: Макросы не нужны

Изменения в стандарт происходят через предложения.

Где находятся предложения и из чего они состоят?

Все предложения в Стандарт находятся на open-std.org. Практически все написаны понятно - чаще всего есть:

  • Краткий обзор области со ссылками на разделы Стандарта;

  • Текущие проблемы;

  • Предлагаемое решение проблем;

  • Предлагаемые изменения в текст Стандарта;

  • Ссылки на предложения-предшественники и прошлые ревизии предложения;

  • В особо продвинутых предложениях - ссылки на реализацию в форке компилятора. В тех, что я видел, реализацию делали в форке clang-a.

По ссылкам на предыдущие предложения можно отследить эволюцию для каждого куска C++.

Далеко не все предложения из архива были в итоге приняты (хотя и могли быть использованы как база для других, принятых предложений), поэтому стоит понимать, что они описывают некий альтернативный тому времени вариант C++, а не кусок современного C++.

Принять участие в эволюции C++ может любой - для русскоязычных экспертов есть stdcpp.ru.

Предложение от 2003 года [N1521] Generalized Constant Expressions указывает на проблему того, что если часть выражения вычисляется с использованием вызова метода, то выражение не является constant-expression. Это заставляет злоупотреблять макросами, если нужно получить более-менее сложное константное выражение:

#define SQUARE(X) ((X) * (X))
inline int square(int x) { return x * x; }
// ^^^ определение макроса и метода
square(9)
std::numeric_limits<int>::max()
// ^^^ невозможны в составе constant-expression
SQUARE(9)
INT_MAX
// ^^^ теоретически могут быть в составе constant-expression

Поэтому предлагается ввести понятие constant-valued методов, которых будет разрешено использовать в constant-expression. Метод считается constant-valued, если это inline-метод, нерекурсивный, возвращающий не void, и его тело состоит из единственного выражения вида return expr;, где после подстановки аргументов (куда также идут constant-expression) получился бы constant-expression.

[Note: Забегая вперед, термин constant-valued не прижился -end note].

int square(int x) { return x * x; } // constant-valued
long long_max(int x) { return 2147483647; } // constant-valued
int abs(int x) { return x < 0 ? -x : x; } // constant-valued
int next(int x) { return ++x; } // NOT constant-valued

Таким образом, все переменные test1-5 из прошлого раздела становились бы "фундаментально" константными, без изменения в коде.

Предложение считает, что можно пойти еще дальше и надо рассмотреть вариант, что такой код тоже должен компилироваться:

struct cayley {
    const int value;
    cayley(int a, int b)
        : value(square(a) + square(b)) {}
    operator int() const { return value; }
};

std::bitset<cayley(98, -23)> s; // eq. to bitset<10133>

Потому что переменная value "фундаментально константная" - инициализировалась в конструкторе через constant-expression с двумя вызовами constant-valued метода. То есть, согласно общей логике предложения, этот код можно свести примерно к такому (вынос переменных и методов вне структуры):

// имитация вызова конструктора cayley::cayley(98, -23) и operator int()
const int cayley_98_m23_value = square(98) + square(-23);

int cayley_98_m23_operator_int() {
    return cayley_98_m23_value;
}

// создание битсета
std::bitset<cayley_98_m23_operator_int()> s; // eq. to bitset<10133>

Предложения обычно не идут далеко в дебри подробностей, как компиляторы могут его реализовать. В этом предложении пишут, что сложностей возникнуть не должно, и надо немного поправить constant folding, которые есть в большинстве компиляторов.

[Note: Однако предложения не существуют в отрыве от компиляторов - если предложение нереально реализовать в разумный срок, его вряд ли примут -end note].

Как с переменными, программист не может проконтролировать, что метод является constant-valued.

2006-2007: Тайное становится явным

К счастью, через 3 года в следующих ревизиях этого предложения ([N2235]) признали, что слишком много неявности это плохо. В список проблем добавили невозможность контроля за инициализацией:

struct S {
    static const int size;
};

const int limit = 2 * S::size; // dynamic initialization
const int S::size = 256; // constant expression initialization
const int z = std::numeric_limits<int>::max(); // dynamic initialization

По задумке программиста, limit должен был быть инициализирован constant-expression, но этого не происходит, так как S::size определён "слишком поздно", после limit. Если бы была возможность запросить нужный тип инициализации, компилятор выдал бы ошибку.

Аналогично с методами. constant-valued методы переименовали в constant-expression методы. Требования к ним остались те же, но теперь, чтобы их было возможно использовать в constant-expression, их необходимо объявлять с ключевым словом constexpr. Зато компиляция будет падать, если тело метода не является правильным return expr;.

Также компиляция упадет, если constexpr-метод принципиально не сможет быть использован в constant-expression при любых аргументах, с ошибкой constexpr function never produces a constant expression. Это надо для того, чтобы программист был точно уверен в том, что метод является потенциально используемым в constant-expression.

Некоторые методы стандартной библиотеки (напр. из std::numeric_limits) предлагается пометить constexpr, так как они удовлетворяют требованиям на него.

Переменные или члены класса также можно объявлять constexpr, тогда компиляция упадет, если переменная инициализируется не через constant-expression.

На тот момент решили сохранить совместимость нового слова с переменными, неявно инициализированными через constant-expression без ключевого слова constexpr, то есть этот код работал (забегая вперед, сейчас этот код с --std=c++11 не компилируется, возможно этот код так никогда и не начал работать):

const double mass = 9.8;
constexpr double energy = mass * square(56.6); // OK, хотя mass не объявлен с constexpr
extern const int side;
constexpr int area = square(side); // error: square(side) is not a constant expression

constant-expression-конструкторы для пользовательских классов также легализовали. Этот конструктор должен иметь пустое тело и инициализировать члены constexpr-expression-ами, если пользователь создает constexpr-объект данного класса.

Неявный конструктор по возможности помечается constexpr. Деструкторы для constexpr-объектов обязаны быть тривиальными, так как нетривиальные обычно что-то меняют в контексте выполняющейся программы, которой нет как таковой в constexpr-вычислениях.

Пример класса с constexpr-ами из предложения:

struct complex {
    constexpr complex(double r, double i) : re(r), im(i) { }

    constexpr double real() { return re; }
    constexpr double imag() { return im; }

private:
    double re;
    double im;
};

constexpr complex I(0, 1); // OK -- literal complex

Такие объекты как I в предложении назвали user-defined-literals. "Литерал" - это нечто вроде базовой сущности в C++. Так же, как "простые" литералы (числа, символы и т.д.) сразу подставляются в ассемблерные команды, а строковые литералы лежат в секции подобной .rodata, так и пользовательские литералы занимают где-нибудь там своё место.

Теперь constexpr-переменными могли являться не только числа и перечисления, а литеральные типы, которых ввели в этом предложении (пока еще без reference type). Литеральный тип - такой, который может быть передан в constexpr-метод, и/или изменен и/или возвращен из нее. Это достаточно простые типы, чтобы компиляторы могли его поддерживать в вычислителе констант.

Ключевое слово constexpr стало спецификатором, нужным компилятору - примерно как override в классах. После обсуждения предложения, для этого ключевого слова решили не делать новый storage class (хотя было бы законно), новый type qualifier, и также его решили не разрешать использовать для аргументов методов, чтобы не переусложнять правила перегрузки методов.

2007: Первые constexpr для структур данных

В этом году вышло предложение [N2349] Constant Expressions in the Standard Library, где пометили как constexpr некоторые методы и константы, а также некоторые методы контейнеров, например:

template<size_t N>
class bitset {
    // ...
    constexpr bitset();
    constexpr bitset(unsigned long);
    // ...
    constexpr size_t size();
    // ...
    constexpr bool operator[](size_t) const;
};

Конструкторы инициализируют члены класса через constant-expression, остальные методы внутри себя имеют return expr;, подходящий под текущие ограничения.

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

2008: Рекурсивные constexpr-методы

constexpr-методы изначально не предполагалось разрешать делать рекурсивными по причине отсутствия убедительных доводов в наличие рекурсии, но затем это ограничение убрали, что отметили в [N2826] Issues with Constexpr.

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

У компилятора существует некий предел вложенности вызовов (в clang это 512 вложенных вызовов), при превышении он откажется считать выражение.

Подобные пределы также есть, например, для инстанцирования шаблонов (если мы бы считали в compile-time через шаблоны, а не через constexpr-методы)

2010: "const T&" как аргументы в constexpr-методах

На данный момент многие методы не могут быть помечены constexpr из-за имеющихся в аргументах константных ссылок. Во все constexpr-методы параметры передаются по значению, т.е. копируются.

template< class T >
constexpr const T& max( const T& a, const T& b ); // не скомпилируется
constexpr pair(); // можно поставить constexpr
pair(const T1& x, const T2& y); // нельзя поставить constexpr

Предложение [N3039] Constexpr functions with const reference parameters (a summary) разрешает константные ссылки в аргументах и как возвращаемое значение.

Это опасное изменение: до этого вычислитель констант имел дело с простыми выражениями и constexpr-переменными (объект литерального класса - по сути набор из constexpr-переменных); но введение ссылок пробивает "четвертую стену", потому что это понятие относится к модели памяти, которой в вычислителе нет.

В общем случае работа со ссылками и указателями в constant-expression превращает C++-компилятор в C++-интерпретатор, поэтому накладываются различные ограничения.

Если вычислитель констант может обработать метод с аргументом типа T, то типа const T& тоже сможет - если будет "представлять себе", что для этого аргумента создается "временный объект".

Более-менее сложная работа со ссылками и попытки что-либо поломать не скомпилируются

template<typename T> constexpr T self(const T& a) { return *(&a); }
template<typename T> constexpr const T* self_ptr(const T& a) { return &a; }
template<typename T> constexpr const T& self_ref(const T& a) { return *(&a); }
template<typename T> constexpr const T& near_ref(const T& a) { return *(&a + 1); }

constexpr auto test1 = self(123); // OK
constexpr auto test2 = self_ptr(123); // FAIL, pointer to temporary is not a constant expression
constexpr auto test3 = self_ref(123); // OK
constexpr auto tets4 = near_ref(123); // FAIL, read of dereferenced one-past-the-end pointer is not allowed in a constant expression

2011: static_assert в constexpr-методах

Предложение [N3268] static_assert and list-initialization in constexpr functions вводит возможность писать "статические" объявления, не вляющие на результат работы метода: typedef, using, static_assert . Это небольшое развинчивание гаек для constexpr-методов.

2012: (Почти) любой код в constexpr-функциях

В 2012 году произошел большой рывок вперед с предложением [N3444] Relaxing syntactic constraints on constexpr functions. Есть множество простых методов, которых желательно уметь вычислять в compile-time, например степень a^n:

// Compute a to the power of n
int pow(int a, int n) {
  if (n < 0)
    throw std::range_error("negative exponent for integer power");
  if (n == 0)
    return 1;
  int sqrt = pow(a, n/2);
  int result = sqrt * sqrt;
  if (n % 2)
    return result * a;
  return result;
}

Однако программистам фокусничать писать в функциональном стиле (убирать локальные переменные и if-ы), чтобы сделать ее constexpr-вариант:

constexpr int pow_helper(int a, int n, int sqrt) {
  return sqrt * sqrt * ((n % 2) ? a : 1);
}
// Compute a to the power of n
constexpr int pow(int a, int n) {
  return (n < 0) ? throw std::range_error("negative exponent for integer power") :
         (n == 0) ? 1 : pow_helper(a, n, pow(a, n/2));
}

Поэтому предложение хочет разрешить записывать в constexpr-методах любой код, с рядом ограничений:

  • Так как в константных выражениях нельзя изменять переменные, циклы (for/while/do/range-based for) заведомо невозможно использовать

  • switch и goto запрещены, чтобы вычислитель констант не моделировал сложные потоки управления

  • Как при старых ограничениях, для метода теоретически должен существовать набор аргументов, при которых ее можно использовать в константных выражениях. Иначе считается, что метод помечен constexpr ошибочно, и компиляция упадет с constexpr function never produces a constant expression.

В методах можно объявлять локальные переменные, если они имеют литеральный тип, и если они инициализируются конструктором, то он должен являться constexpr. Таким образом, вычислитель констант в процессе обработки constexpr-метода с конкретными определенными аргументами может "на фоне" создавать constexpr-переменную для каждой локальной переменной, и затем использовать их для вычисления других переменных, которые зависят от только что созданной.

[Note: таких переменных не будет сильно много из-за жесткого ограничения на "глубину вызовов" -end note].

В методах можно объявлять статические переменные. Они могут иметь не-литеральный тип (чтобы, например, возвращать ссылки на них из метода; сами ссылки - тип как раз литеральный), но у них не должно быть dynamic initialization (т.е. должна быть хотя бы zero-initialization) и нетривиального деструктора. Предложение приводит пример, где это могло бы быть полезно (получение ссылки на нужный объект в compile-time):

constexpr mutex &get_mutex(bool which) {
  static mutex m1, m2; // non-const, non-literal, ok
  if (which)
    return m1;
  else
    return m2;
}

Также разрешили объявлять типы (class, enum и т.д.) и возвращать void.

2013: (Почти) любой код в constexpr-функциях ver 2.0 Mutable Edition

Однако Комитет решил, что поддержка циклов (хотя бы for) в constexpr-методах это must have. В 2013 году вышла поправленная версия предложения [N3597] Relaxing constraints on constexpr functions.

Для реализации "constexpr for"-а рассматривалось четыре варианта.

Самым далеким от "остального C++" варианта было создание совершенно новой конструкции для итераций, который подходил бы для функционального стиля тогдашнего constexpr-кода; но это бы фактически создало новый под-язык constexpr C++ функционального стиля.

Самым близким к "остальному C++" вариантом было не заменять качество количеством, а просто стараться поддерживать в constexpr-вычислениях широкое подмножество C++ (в идеале - его весь). Этот вариант был выбран. Это сильно повлияло на дальнейшую историю constexpr.

Поэтому возникла необходимость в мутабельности объектов в рамках constexpr-вычислений. Согласно предложению, объект, созданный в рамках вычисления constexpr-выражения, теперь можно изменять в течение процесса вычисления, до тех пор, пока не закончится процесс вычисления или лайфтайм объекта.

Эти вычисления до сих пор происходят внутри своей "песочницы", ничто снаружи на них не влияет, поэтому, по идее, вычисление constexpr-выражения с одними и теми же аргументами будет давать один и тот же результат (не считая погрешностей в float- и double-вычислениях).

Для лучшего понимания я скопировал кусок кода из предложения:

constexpr int f(int a) {
  int n = a;
  ++n;                  // '++n' is not a constant expression
  return n * a;
}

int k = f(4);           // OK, this is a constant expression.
                        // 'n' in 'f' can be modified because its lifetime
                        // began during the evaluation of the expression.

constexpr int k2 = ++k; // error, not a constant expression, cannot modify
                        // 'k' because its lifetime did not begin within
                        // this expression.

struct X {
  constexpr X() : n(5) {
    n *= 2;             // not a constant expression
  }
  int n;
};
constexpr int g() {
  X x;                  // initialization of 'x' is a constant expression
  return x.n;
}
constexpr int k3 = g(); // OK, this is a constant expression.
                        // 'x.n' can be modified because the lifetime of
                        // 'x' began during the evaluation of 'g()'.

От себя замечу, что теперь компилируется такой код:

constexpr void add(X& x) {
    x.n++;
}
constexpr int g() {
  X x;
  add(x);
  return x.n;
}

Теперь в constexpr-методах работает значимая часть С++, и в методах разрешены сайд-эффекты, локальные в рамках constexpr-вычисления. Вычислитель констант стал сложнее, но все еще справлялся с задачей.

2013: Легендарные const-методы и популярные constexpr-методы

constexpr-методы класса на данный момент автоматически помечаются как const-методы.

В предложении [N3598] constexpr member functions and implicit const обратили внимание, что constexpr-методы класса не обязательно неявно делать const-методами.

Это стало актуальнее с мутабельностью в constexpr-вычислениях; но и до этого мешало использовать один и тот же метод в constexpr и не-constexpr коде:

struct B {
  constexpr B() : a() {}
  constexpr const A &getA() const /*implicit*/ { return a; }
  A &getA() { return a; } // дублирование кода
  A a;
};

Интересно, что предложение давало на выбор три опции, из них был выбран второй:

  1. Статус-кво; минус: дублирование кода

  2. constexpr не будет неявно значить const; минус: ломает ABI (const является частью mangled-имени метода)

  3. Добавить новый квалификатор и писать constexpr A &getA() mutable { return a; }; минус: новый баззворд в конце объявления

2015-2016: Синтаксический сахар для шаблонов

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

template <class T, class... Args> 
enable_if_t<is_constructible_v<T, Args...>, unique_ptr<T>> 
make_unique(Args&&... args) 
{
    return unique_ptr<T>(new T(forward<Args>(args)...));
}  

template <class T, class... Args>  
enable_if_t<!is_constructible_v<T, Args...>, unique_ptr<T>>
make_unique(Args&&... args) 
{
    return unique_ptr<T>(new T{forward<Args>(args)...});
}

Предложение [N4461] Static if resurrected вводит выражение static_if (позаимствовав из языка D), чтобы код стал менее страшным:

template <class T, class... Args> 
unique_ptr<T>
make_unique(Args&&... args) 
{
    static_if (is_constructible_v<T, Args...>) {
        return unique_ptr<T>(new T(forward<Args>(args)...));
    } else {
        return unique_ptr<T>(new T{forward<Args>(args)...});
    }
}

Этот кусок C++ имеет довольно посредственное отношение к constexpr-вычислениям и работает в другой сфере. Но static_if в следующих ревизиях решили переименовать:

constexpr_if (is_constructible_v<T, Args...>) {
  return unique_ptr<T>(new T(forward<Args>(args)...));
} constexpr_else {
  return unique_ptr<T>(new T{forward<Args>(args)...});
}

Затем еще немного...

constexpr if (is_constructible_v<T, Args...>) {
	return unique_ptr<T>(new T(forward<Args>(args)...));
} constexpr_else {
	return unique_ptr<T>(new T{forward<Args>(args)...});
}

И финальный вариант:

if constexpr (is_constructible_v<T, Args...>) {
    return unique_ptr<T>(new T(forward<Args>(args)...));
} else {
    return unique_ptr<T>(new T{forward<Args>(args)...});
}

2015: Constexpr-лямбды

В очень хорошем предложении [N4487] Constexpr Lambda подробно проработали вопрос использования closure type в constexpr-вычислениях (и написали поддержку в форкнутом clang).

Чтобы понять, как возможно иметь constexpr-лямбды, нужно понимать, как они устроены "внутри". Есть статья про историю лямбд, где описано, как прото-лямбды существовали уже в C++03, и в сегодняшних лямбда-выражениях создается похожий класс, скрытый за чертогами компилятора.

Прото-лямбда для [](int x) { std::cout << x << std::endl; }
#include <iostream>
#include <algorithm>
#include <vector>

struct PrintFunctor {
    void operator()(int x) const {
        std::cout << x << std::endl;
    }
};
int main() {
    std::vector<int> v;
    v.push_back(1);
    v.push_back(2);
    std::for_each(v.begin(), v.end(), PrintFunctor());
}

Если все "захваченные" переменные являются литеральными типами, то closure type тоже предложено считать литеральным типом, а operator() пометить constexpr. Работающий пример constexpr-лямбд:

constexpr auto add = [] (int n, int m) {
    auto L = [=] { return n; };
    auto R = [=] { return m; };
    return [=] { return L() + R(); };
};
static_assert(add(3, 4)() == 7, "");

2017-2019: Двойные стандарты

В предложении [P0595] The constexpr Operator рассмотрели возможность "знать" внутри метода, где сейчас выполняется метод - в вычислителе констант или в рантайме. Автор предложил использовать для этого вызов constexpr(), которые будет соответственно возвращать true или false.

constexpr double hard_math_function(double b, int x) {
  if (constexpr() && x >= 0) {
    // медленная формула, более точная (compile-time)
  } else {
    // быстрая формула, менее точная (run-time)
  }
}

Затем оператор был заменен на "магическую" функцию std::is_constant_evaluated() ([P0595R2]) и в таком виде принят в Стандарт С++20.

Если предложение разрабатывается долго, то авторы иногда делают "rebase" (аналогично как в проектах в git/svn), приводя его в соответствие с обновившимся состоянием.

Так и здесь - авторы [P1938] if consteval (про consteval будет позже) обнаружили, что лучше создать новую запись:

if consteval { }
if (std::is_constant_evaluated()) { }
// ^^^ аналогичные записи

Это решение было принято в C++23 - ссылка на голосование.

2017-2019: We need to go deeper

В constexpr-методах во время constexpr-вычислений пока нельзя использовать дебаггер и выводить логи. Предложение [P0596] std::constexpr_trace and std::constexpr_assert рассматривает введение специальных методов для этих целей.

Это предложение было благосклонно принято - ссылка на голосование, но пока еще не доработано.

2017: Злой двойник стандартной библиотеки

На данный момент std::vector, который желательно затащить в compile-time, не может работать в constexpr-вычислениях, в основном из-за недоступности там операторов new/delete.

Идея о допуске операторов new и delete в вычислитель констант на тот момент выглядела слишком амбициозно, поэтому в довольно странном предложении [P0597] std::constexpr_vector рассматривается введение магического std::constexpr_vector<T>.

Он является противоположносью std::vector<T> - может быть создан и изменен только во время constexpr-вычислений.

constexpr constexpr_vector<int> x;  // Okay.
constexpr constexpr_vector<int> y{ 1, 2, 3 };  // Okay.
const constexpr_vector<int> xe;  // Invalid: not constexpr

Как вычислитель констант должен работать с памятью - не описано. @antoshkka и @ZaMaZaN4iK (авторы многих предложений) в [P0639R0] Changing attack vector of the constexpr_vector выявили большое количество минусов подхода, и предложили поменять направление работы в сторону абстрактного магического constexpr allocator, который не дублирует всю стандартную библиотеку.

2017-2019: Constexpr обретает память

В презентации Constexpr ALL the thing! демонстрировался пример constexpr-библиотеки для работы с JSON-объектами (то же самое, но в бумажном виде, есть в [P0810] constexpr in practice):

constexpr auto jsv
    = R"({
          "feature-x-enabled": true,
          "value-of-y": 1729,
          "z-options": {"a": null,
                        "b": "220 and 284",
                        "c": [6, 28, 496]}
         })"_json;
if constexpr (jsv["feature-x-enabled"]) {
    // code for feature x
} else {
    // code when feature x turned off
}

Авторы сильно пострадали от невозможности использовать контейнеры STL, и написали свои велосипедные аналоги std::vector и std::map, имеющие внутри себя std::array (умеющий работать в constexpr).

Предложение [P0784] Standard containers and constexpr исследует возможность ввода STL-контейнеров в constexpr-вычисления.

[Note: Важно знать, что такое аллокатор. STL-контейнеры работают через него с памятью. Какой именно аллокатор - задается через аргумент шаблона. Чтобы войти в тему, можно почитать эту статью. -end note]

Что же мешает разрешить STL-контейнеры в constexpr-вычислениях? Есть три проблемы:

  1. Деструкторы не могут быть объявлены constexprconstexpr-объектов он обязан быть тривиальным).

  2. Недоступна динамическая аллокация/деаллокация памяти.

  3. Недоступен placement-new для вызова конструктора в аллоцированной памяти.

Первая проблема. С этим разобрались быстро - авторы предложения обсуждали проблему с разработчиками фронтенда MSVC++, GCC, Clang, EDG, и они подтвердили, что ограничение можно легко ослабить. Теперь от литеральных типов можно требовать наличие constexpr-деструктора, а не строго тривиального деструктора.

Вторая проблема. Работа с памятью не очень проста. Как уже упоминалось, вычислитель констант обязан отлавливать undefined behaviour в любом виде и останавливать компиляцию в случае его наличия.

Это значит, что вместе с многими объектами нужно трекать их "метаданные", которые держат руку на пульсе и не дают сломать выполнение программы. Пара примеров таких метаданных:

  • Информация, какое поле в union-е активно ([P1330]) (примеры undefined behavior: запись в член неактивного поля)

  • Жесткая связь между указателем или ссылкой и соответствующим ему реальным ранее созданным объектом (примеры undefined behavior: бесконечное множество)

Из-за этого не имеет смысла использовать подобные методы:

void* operator new(std::size_t);

Так как нет никакого обоснования приводить void* к T*. Короче говоря, новая ссылка/указатель либо могут начать указывать на существующий объект, либо быть созданным "одновременно" с ним, и никак иначе.

Поэтому есть две опции работы с памятью, которые будут законны в constexpr-вычислениях:

  1. Простые new- и delete-выражения: int* i = new int(42);

  2. Использование стандартного аллокатора: std::allocator (его подпилили напильником)

Третья проблема. Стандартные койтейнеры разделяют аллокацию памяти и конструирование объектов в этой памяти. С аллокацией уже разобрались - с условием на метаданные ее обеспечить возможно.

Контейнеры полагаются на std::allocator_traits, в частности для конструирования - на его метод construct. До предложения он имел вид

template< class T, class... Args >
static void construct( Alloc& a, T* p, Args&&... args ) {
	::new (static_cast<void*>(p)) T(std::forward<Args>(args)...);
	// ^^^ placement-new, запрещенный в constexpr-вычислениях
}

То есть его нельзя использовать из-за приведения к void* и placement-new (которые в общем виде в constexpr запрещены). А в предложении преобразовался в

template< class T, class... Args >
static constexpr void construct( Alloc& a, T* p, Args&&... args ) {
	std::construct_at(p, std::forward<Args>(args)...);
}

std::construct_at - это метод, который в рантайме работает аналогично старому коду (с приведением к void*), а в constexpr-вычислениях он:

.∧_∧
( ・ω・。)つ━☆・*。
⊂  ノ    ・゜+.
しーJ   °。+ *´¨)
         .· ´¸.·*´¨) ¸.·*¨)
          (¸.·´ (¸.·'* ☆ Вжуххххх, и просто работает! ☆

То есть компиляторный вычислитель констант обработает его особым образом: по видимости, вызвав конструктор у объекта, который связан с T* p, без бюрократии.

Этого достаточно, чтобы контейнеры стало возможно использовать в constexpr-вычислениях.

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

Такой новый тип аллокации памяти назван transient constexpr allocations. Слово transient приблизительно можно перевести как "мимолетный" или "недолговечный".

В этом предложении еще был кусок про non-transient allocation - дать возможность освобождать не всю аллоцированную память, тогда неосвобожденная память "вываливается" из "песочницы" и конвертируется бы в static storage (другими словами, в секцию .rodata). Но Комитет посчитал эту возможность "слишком хрупкой" ("too brittle") по многим причинам, и пока его не принял.

В остальном, это предложение было принято.

2018: Поймай меня, если сможешь

Предложение [P1002] Try-catch blocks in constexpr functions вводит try-catch блоки в constexpr-вычисления.

Это предложение немного сбивает с толку, так как throw на тот момент был запрещен в constexpr-вычислениях (значит, catch-кусок кода никогда не запускается).

Судя по документу, это ввели, чтобы пометить все методы std::vector как constexpr - в libc++ (реализация STL) в методе vector::insert используется try-catch блок.

2018: Я сказал constexpr!

Из личного опыта знакомо, что двойственность constexpr-методов (могут выполняться и в compile-time, и в run-time) приводит к тому, что вычисления проваливаются в рантайм там, где не ожидаешь: пример кода; и для того, чтобы гарантировать нужный этап, нужно фокусничать: пример кода.

Предложение [P1073] constexpr! functions вводит новое ключевое слово constexpr! для методов, которые должны работать только в compile-time. Эти методы называются immediate-методами.

constexpr! int sqr(int n) {
  return n*n;
}
constexpr int r = sqr(100);  // Okay.
int x = 100;
int r2 = sqr(x);  // Error: Call does not produce a constant.

Если существует возможность того, что в constexpr!-метод могут попасть переменные, неизвестные на этапе компиляции (что норма для constexpr-методов), то программа не скомпилируется:

constexpr! int sqrsqr(int n) {
  return sqr(sqr(n)); // Not a constant-expression at this  point,
}                     // but that's okay.

constexpr int dblsqr(int n) {
  return 2*sqr(n); // Error: Enclosing function is not
}                  // constexpr!.

К constexpr!-методу нельзя взять указатель или ссылку. Бэкенду компилятора вовсе не обязательно (и не нужно) знать про существование таких функций, помещать их в таблицы символов и т.д.

В следующих ревизиях этого предложения ключевое слово constexpr! поменяли на consteval.

Разница между constexpr и consteval налицо - во втором случае нет провала в рантайм: пример с constexpr, пример с consteval.

2018: Слишком радикальный constexpr

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

Предложение [P1235] Implicit constexpr предлагает по умолчанию помечать все методы, имеющие определение, как constexpr. Но можно и запретить выполнять метод в compile-time:

  1. <нет спецификатора> - метод помечается как constexpr, если возможно.

  2. constexpr - работает как сейчас

  3. constexpr(false) - не может быть вызван в compile-time

  4. constexpr(true) - может быть вызван только в compile-time, т.е. аналогично constexpr!/consteval

Это предложение не было принято - ссылка на голосование.

2020: Долговечная constexpr-память

Как уже обсуждалось, после принятия предложения [P0784] Standard containers and constexpr в constexpr-вычислениях стало возможно аллоцировать память, но ее всю необходимо освобождать до окончания constexpr-вычисления: это так называемые transient constexpr allocations.

Таким образом, нельзя создавать top-level constexpr-объекты почти всех STL-контейнеров и многих других классов.

[Note: Под "top-level объектом" я имею в виду результат всего constexpr-вычисления, например:

constexpr TFoo CalcFoo();
constexpr TFoo FooObj = CalcFoo();

Здесь вызов CalcFoo() начинает constexpr-вычисление, а FooObj - его результат и top-level constexpr-объект. -end note]

Предложение [P1974] Non-transient constexpr allocation using propconst находит путь к решению проблемы. На мой взгляд, это самое интересное предложение из всех, что я привел в статье (оно заслуживало бы отдельной статьи). Ему дали "зеленый свет" и оно развивается - ссылка на тикет. Здесь я его перескажу в понятной форме.

Что же мешает нам иметь non-transient allocations? Вообще, проблема не в том, чтобы запихать куски памяти в static storage (.bss/.rodata/их аналоги), а в том, чтобы проверить, что вся схема обладает чёткой консистентностью.

Допустим, что мы имеем некий constexpr-объект, конструирование (точнее, "вычисление") которого спровоцировало non-transient allocations. Значит, теоретическое деконструирование этого объекта (т.е. вызов его деструктора) должно освободить всю non-transient память. Если вызов деструктора не освободил бы память, то это плохо (консистентности нет) и надо выдавать ошибку компиляции.

Другими словами, вот что должен делать вычислитель контант:

  1. Увидев запрос на constexpr-вычисление, произвести его.

  2. В результате вычисления получить объект, скрывающий под собой пачку constexpr-переменных литерального типа; и некоторый объём неосвобожденной памяти (non-transient allocations).

  3. Имитировать вызов деструктора у данного объекта (не вызывая его на самом деле), и проверить что этот вызов освободил бы всю non-transient память.

  4. Если все проверки прошли успешно, то консистентность доказана. Non-transient allocations можно двигать в static storage.

Это звучит логично, и допустим, что это всё реализовано. Но тогда получим проблему с подобным кодом с non-transient памятью, которую стандарт не будет запрещать менять, и тогда проверка на вызов деструктора будет бессмысленной:

constexpr unique_ptr<unique_ptr<int>> uui
    = make_unique<unique_ptr<int>>(make_unique<int>());
int main() {
    unique_ptr<int>& ui = *uui;
    ui.reset();
}

[Note: В реальности такой код получил бы отпор от ОС за попытку записи в read-only сегмент RAM, но это физическая константность. А в коде должна быть логическая константность. -end note]

Пометка constexpr у объектов влечет за собой пометку их как const, и все их члены также становятся const.

Однако если у объекта есть член указательного типа, то это ломает всю малину - заставить его указывать на другой объект станет нельзя, но менять объект, на который он указывает, не запрещено.

У указательных типов есть два ортогональных параметра константности:

  1. Можно ли начать указывать на другой объект?

  2. Можно ли изменять объект, на который указывается?

И получается 4 варианта с разными свойствами (OK - строка компилируется, FAIL - нет):

int dummy = 13;

int * test1{nullptr};
test1 = &dummy; // OK
*test1 = dummy; // OK

int const * test2{nullptr};
test2 = &dummy; // OK
*test2 = dummy; // FAIL

int * const test3{nullptr};
test3 = &dummy; // FAIL
*test3 = dummy; // OK

int const * const test4{nullptr};
test4 = &dummy; // FAIL
*test4 = dummy; // FAIL

"Обычный" const приводит к третьему варианту, но для constexpr необходим четвертый! То есть необходим так называемый deep-const.

Предложение на базе пары других, более старых предложений, предлагает для этого ввести новый cv-qualifier propconst (propagating const).

Этот квалификатор будет использоваться с указательными/ссылочными типами:

T propconst*
T propconst&

И в зависимости от типа T компилятор будет либо конвертировать это слово в const, либо удалять его. Первый случай - если T константный, второй - если нет:

int propconst * ---> int *
int propconst * const ---> int const * const

В предложении приведена таблица конвертации propconst в разных случаях.

Таким образом, constexpr-объекты могли бы обрести полную логическую константность (deep-const):

constexpr unique_ptr<unique_ptr<int propconst> propconst> uui
    = make_unique<unique_ptr<int propconst> propconst>(make_unique<int propconst>());

int main() {
    unique_ptr<int propconst>& ui = *uui;
    ui.reset();
    // ^^^ FAIL

    const unique_ptr<int propconst>& ui = *uui;
    // ui.reset();
    // ^^^ OK
}

// P.S. Такая запись еще не принята Комитетом, я надеюсь, сделают лучше

2021: Constexpr-классы

С появлением полностью constexpr-классов, включая std::vector, std::string, std::unique_ptr, в которых все методы методы помечены как constexpr, возникает желание сказать "пометь все методы класса как constexpr".

Это делает предложение [P2350] constexpr class:

class SomeType {
public:
  constexpr bool empty() const { /* */ }
  constexpr auto size() const { /* */ }
  constexpr void clear() { /* */ }
  // ...
};
// ^^^ ДО

class SomeType constexpr {
public:
  bool empty() const { /* */ }
  auto size() const { /* */ }
  void clear() { /* */ }
  // ...
};
// ^^^ ПОСЛЕ

С этим предложением связана интересная история - еще не зная о его существовании, я вкинул в stdcpp.ru идею предложить такую же штуку: ссылка на тикет (что сейчас не нужно).

Многие почти одинаковые предложения в Стандарт могут появиться почти одновременно. Это говорит в пользу теории множественных открытий: идеи "витают в воздухе", и в принципе не так важно, кто их открывает - если комьюнити достаточно большое, то естественная эволюция происходит.

2019-∞: Интерпретатор констант в компиляторе

constexpr-вычисления могут быть очень медленными, потому что вычислитель констант на синтаксическом дереве развивался итеративным образом (начиная с constant folding) и сейчас делает множество лишних вещей, которые можно было делать более эффективно.

С 2019 года в Clang разрабывается ConstantInterpeter, который в перспективе может полностью заменить вычислитель констант на синтаксическом дереве. Он довольно интересен и заслуживал бы отдельной статьи.

Его идея состоит в том, что на основе синтаксического дерева можно сгенерировать "байткод", который затем выполнить на интерпретаторе. Интерпретатор поддерживает в себе стек, фреймы вызовов, модель памяти (с метаданными, о которых говорилось ранее).

Документация для ConstantInterpeter хорошая, и также много интересного есть в видео-выступлении создателя интерпретатора на конференции LLVM-разработчиков.

Что можно еще посмотреть?

Для того, чтобы больше расширить понимание, можно посмотреть замечательные выступления от экспертов. В каждом выступлении авторы выходят за рамки рассказа про constexpr: это может быть построение constexpr-библиотеки; рассказ про использование constexpr в будущем reflexpr; или про устройство вычислителя констант и интерпретатора констант.

Я хотел бы, чтобы здесь было выступление про киллер-фичу (по моему мнению) [P1040] std::embed, которая отлично работала бы в тандеме с constexpr. Но, судя по тикету, его планируют реализовать в C++-каком-то.

Автор: Евгений

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js