(Сокращения: НАМ - нормальные алгорифмы Маркова, КТ - компайл-тайм, РТ - рантайм)
Продолжение. Первая часть - программирование на НАМ. Вторая - обзор неприятностей, концепты.
КТ со строками
Чтобы строка была честным constexpr-значением, нужно, чтобы её тип отвечал довольно узким требованиям. Прежде всего, - это литеральный тип. (Кстати, на cppreference приведён пример именно строки, но я покажу, что такая реализация недостаточна для наших нужд). Нам нужно, чтобы строка могла быть параметром шаблона
Упрощая, - это должен быть структурный тип с тривиальным лэяутом, с constexpr конструкторами и деструктором. И с содержимым, которое доступно в КТ. Например, если там есть указатели, - то они могут быть только указателями на линкуемые сущности (функции, глобальные переменные, указатели-на-члены...) Указатели на строковые литералы к таковым, увы, не относятся.
Также хотелось бы избежать ужасных антипаттернов метапрограммирования прошлых лет:
template<char... Cs> struct s_t_r_i_n_g {}; // ну вы поняли моё отношение к этому!!!
constexpr auto h_e_l_l = s_t_r_i_n_g<'h', 'e', 'l', 'l'>{};К счастью, написать правильную строку, да ещё и совместимую с РТ, - очень и очень просто. Неприятность эту мы переживём!
CONCEPT(Str) // будет заселён только воплощениями шаблона str<L>
template<size_t N> using charbuf = char[N];
template<size_t L> // L - length
struct str {
REPRESENTS(Str)
charbuf<L+1> value = {}; // с концевым нулём, поэтому +1
constexpr str() = default; // занулённый массив
constexpr str(const charbuf<L+1>& literal) { std::copy(literal, literal + L, value); }
// и вся обвязка для контейнеров
static constexpr size_t size() { return L; }
static constexpr bool empty() { return size() == 0; }
constexpr char* begin() { return value; }
constexpr const char* begin() const { return value; }
constexpr char* end() { return value + L; }
constexpr const char* end() const { return value + L; }
constexpt char& operator[](size_t i) { return value[i]; }
constexpt const char& operator[](size_t i) const { return value[i]; }
// и для работы со строками
constexpr std::string_view view() const { return {begin(), end()}; }
// сравнение со строкой того же типа (того же размера) - поэлементное
constexpr bool operator == (const str&) const = default;
// сравнение со строкой другого размера - очевидно, всегда ложно
constexpr bool operator == (const Str auto&) const { return false; }
};
// CTAD
template<size_t N> requires (N > 0) str(const charbuf<N>&) -> str<N-1>;Можно было бы обойтись и без конструкторов и без рукодельного вывода типа,
template<size_t N1> requires (N1 > 0) struct str {
charbuf<N1> value;
constexpr size_t size() const { return N1 - 1; }
.....
};но это внесло бы путаницу, ухудшило читаемость и создало бы почву для ошибок на плюс-минус-единицу.
Что мы уже можем делать с str?
Можем создавать, принимать и возвращать в функциях, использовать как параметры шаблонов.
constexpr auto hello = str{"hello"}; // char[6] --> str<5>
constexpr Str auto give_hello() { return str{"hello"}; }
constexpr bool take_hello(const Str auto& s) { return s == str{"hello"}; }
constexpr bool has_hello(const Str auto& s) {
return std::search(s.begin(), s.end(), hello.begin(), hello.end()) != s.end();
}
static_assert(has_hello(str{"this is hello world"}));
constexpr Str auto make_hello() {
// можем даже внутри работать с переменной
str<5> dst;
auto it = dst.begin();
*it++ = 'h'; *it++ = 'e'; *it++ = 'l'; *it++ = 'l'; *it++ = 'o';
return dst;
}
static_assert(make_hello() == give_hello());
/* не constexpr */ void say_hello() { std::cout << hello.view() << std::endl; }Напомню, что одна из целей - это создание правил, параметризованных строками. И мы это уже умеем.
// можно так
template<Str SType, Str RType> struct rule {
SType search;
RType replace;
.....
};
constexpr auto p = rule{str{"hello"}, str{"privet"}};
// а можно (и будет нужно) так
template<Str auto search, Str auto replace> struct rule {
.....
};
constexpr auto p = rule<str{"hello"}, str{"privet"}>{};А что НЕ умеем?
Самое важное: в таком виде мы не умеем и не имеем права выполнять замену.
// поиск-и-замена над std::string
std::string substitute(std::string t, std::string const& s, std::string const& r) {
size_t pos = t.find(s);
if (pos == t.npos)
return t; // size = t.size()
else
return t.substr(0, pos) + r + t.substr(pos); // size = t.size()-s.size()+r.size()
}Если попробуем переписать это на str, - используя std::search и std::copy, - то обнаружим пренеприятнейший факт. Не просто значение результата зависит от значений аргументов, но и тип (параметризованный длиной) тоже зависит... от значений.
Проблема размера
Конечно, наивная идея - сделать size и capacity, где capacity - свойство типа, а size - значений этого типа.
template<size_t Capacity> struct long_enough_str {
REPRESENTS(LongEnoughStr)
charbuf<Capacity+1> value = {};
size_t size_ = 0;
long_enough_str() = default;
template<size_t N> requires(N <= Capacity)
long_enough_str(const str<N>& s);
template<size_t N1> requires(N1 > 0 && N1 - 1 <= Capacity)
long_enough_str(const charbuf<N1>& s);
constexpr size_t size() const { return size(); }
static constexpr size_t capacity() { return capacity(); }
constexpr auto begin() const { return value; }
constexpr auto end() const { return begin() + size(); }
.....
};
Str auto substitute(LongEnoughStr auto const& t, Str auto const& s, Str auto const& r) {
constexpr size_t new_capacity =
(t.capacity() < s.size() || r.size() < s.size())
? t.capacity()
: t.capacity() - s.size() + r.size();
static_assert(new_capacity >= t.capacity());
if (не нашли подстроку s)
return long_enough_str<new_capacity>{t};
else {
long_enough_str<new_capacity> dst;
// собрали по кусочкам...
return dst;
}
}Но перспектива такого подхода сразу видна, как безрадостная. Ёмкость новой строки - не меньше исходной. Если в наборе правил поиска-замены у нас есть такие, где строка замены длиннее строки поиска, то на каждой итерации НАМ-машины мы обязаны прибавлять максимум из разностей этих длин. Итоговая ёмкость окажется увеличенной на этот максимум, помноженный на количество итераций. Причём мы не можем заранее зарезервировать строку побольше, чтобы заведомо хватило на всё время работы: НАМ-машина не знает, а вдруг вся эта строка заполнена содержательным текстом.
Проблема ветвления
Функция substitute выше поступает очень просто: если не нашла искомую подстроку, возвращает исходный текст. Но для НАМ-машины нужно отличать - сделали мы замену (пусть и тривиальную) или нет. Прерывать цикл перебора по правилам, или продолжать.
В РТ это делается элементарно. В каком-то явном или неявном виде применяем монаду Maybe. Например, возвращаем std::optional<std::string>.
В КТ такой optional - это или пара (флажок, строка), или разнотипные значения (скажем, nothing{} и just{dst} ), благо, constexpr-функции могут ветвиться по if constexpr.
Первый подход концептуально ничем не отличается от строки с ёмкостью, - мы должны предусмотреть все варианты и заставить компилятор найти наиболее общий тип строки, даже если цикл перебора прервётся на первом же правиле. (А вдруг не прервётся?)
Второй подход - тип результата опять зависит от значений аргументов. Язык C++ так не умеет!
Так мы осознали необходимость поддержать
Зависимые типы
Конечно, всю полноту зависимых типов я охватывать не собираюсь. Но одна важная категория - типы-синглетоны (населённые единственным значением) у нас встретится, и в ad-hoc виде, и в обобщённом тоже.
Ad-hoc (всякие частные случаи)
Это, например, типы правил. Каждое правило параметризовано парой строк. И, поскольку с правилом связана функция подстановки, результат которой зависит не только от входной строки, но и от параметров правила, - то тип этой функции (и тип правила целиком) - уникально определяется значениями. Вот поэтому я выше написал, что нам понадобится шаблон с параметрами-значениями.
enum class rule_kind { regular, final }; // немного забегая вперёд
template<Str auto search, Str auto replace, rule_kind kind>
struct rule {
REPRESENT(Rule)
.....
};И НАМ-подпрограммы тоже параметризованы значениями этих правил. Хотя тут уже это непринципиально, поскольку их типы - синглетоны (фактически, пустые структуры), и вся подпрограмма тоже - синглетон. Это уже выбор удобства синтаксиса: раз начали работать с параметрами-значениями, так и продолжим:
template<Rule auto... ps> // p означает pravilo, или program, - чтоб не путать с replace
struct rules {
REPRESENT(Rule)
.....
};Кстати сказать, в стандартной библиотеке C++ такие синглетоны тоже есть, и достаточно часто используются. Не считая юнит-типов std::nullptr_t, std::nullopt_t, std::monostate, - это шаблон std::integral_constant<class T, T value> и самые яркие его представители std::true_type и std::false_type.
И вот, глядя на них, мы перебросим мостик к обобщённому случаю.
Обобщённый синглетон
Это тип, ассоциированный с единственным значением произвольного типа. (А не жёстко заданного, как у std::integral_constant). Но так даже и проще:
CONCEPT_WITH_TYPE(Ct)
template<auto V> struct ct {
REPRESENTS(Ct)
using type = decltype(V);
static constexpr auto value = V;
};
// выглядит безумно - константа, оборачивающая тип с константой внутри...
// но это дань лени-матушке, чтобы фигурные скобки не писать в выражениях.
template<auto V> constexpr auto ctv = ct<v>{};ct означает compile-time. Да, имя "вырожденное", но тут дело в предыстории. Изначально мне нужны были только синглетоны строк, для работы в constexpr-функциях. Для этого я рядом с типом str, зависимым от размера, но населённым произвольными строками этого размера, - завёл тип ctstr, населённый конкретной строкой.
template<Str auto V> struct ctstr { static constexpr value = V; };а потом вошёл во вкус, а заодно мне понадобились синглетоны флажков и размеров... К тому же имя достаточно короткое и не занято никакими другими смыслами, - сравните ct<123>{} и какой-нибудь singleton<123>{}.
Естественно, писать Ct auto foo(Ct auto arg) - столь же дезинформативно, как и просто auto, поэтому используются возможности параметризованных концептов.
Просто дадим имена самым расхожим семействам:
template<class T> concept CtStr = CtOfTraits<is_Str>;
template<class T> concept CtSize = CtOfType<size_t>;Функции над CtStr
Наконец, у нас подготовлен базис для полноценных КТ-функций над КТ-строками! Что мы сейчас и применим.
Подстановка
Помимо строк я уже анонсировал Maybe, ну, это несложно. Наверное, стоило бы продумать дизайн более тщательно, - например, чтобы для разных типов были разные nothing. Но в первом приближении "и так сойдёт". Его главная задача - чтобы компилятор легко различал значения вида "не шмогла" и вида "шмогла".
CONCEPT(Nothing)
CONCEPT_WITH_TYPE(Just)
template<class T> concept Maybe = Nothing<T> || Just<T>;
struct nothing {
REPRESENTS(Nothing);
static constexpr operator bool() { return false; }
};
template<class T> struct maybe {
using type = T;
T value;
static constexpr operator bool() { return true; }
};Теперь функция подстановки выглядит вот так
template<class T> concept JustCtStr = JustOfTraits<T, is_CtStr>;
template<class T> concept MaybeCtStr = Nothing<T> || JustCtStr<T>;
constexpr MaybeCtStr auto try_substitute(CtStr auto cts, CtStr auto ctr, CtStr auto ctt) {
// чтобы не писать сто раз ctt.value...
constexpr Str auto const& src = ctt.value;
constexpr Str auto const& s = cts.value;
constexpr Str auto const& r = ctr.value;
// обрабатываем элементарные краевые случаи
if constexpr (src.size() < s.size()) {
return nothing{}; // строка заведомо меньшей длины
} else if constexpr (src == s) {
return just{ctr}; // полная замена
} else if constexpr (s.empty() && r.empty()) {
return just{ctt}; // замена ничего на ничего
} else {
// ищем...
constexpr auto fbegin = std::search(src.begin(), src.end(), s.begin(), s.end());
if constexpr (fbegin == src.end()) {
return nothing{}; // не нашли
} else {
// маленькая C++ная хитрость: мега-вычисление в лямбде.
constexpr Str auto dst = // нам далее нужна константа
[&]{
// а собираем из кусочков в переменную,
// которая внутри этого блока константой, ясное дело, не является
auto fend = fbegin + s.size();
constexpr auto len = src.size() - s.size() + r.size();
str<len> dst; // not constant yet in this block
auto it = dst.begin();
it = std::copy(src.begin(), fbegin, it);
it = std::copy(r.begin(), r.end(), it);
it = std::copy(fend, src.end(), it);
*it = 0;
return dst;
}();
// заворачиваем в синглетон, а синглетон заворачиваем в just.
return just{ctv<dst>};
}
}
}Конечно, just{ctd} - обёртка над синглетоном - также является синглетоном. Но эти типы и эти значения возникают у нас внутри функций, наружу не отсвечивают, поэтому специально обобщать их, заворачивая (или выворачивая) в ct<...> я смысла не увидел.
Всячина
Просто покажу, что ещё можно делать со строками. В проекте nenormal это используется для юниттестов и для отладочного вывода, а здесь - демонстратор технологии.
Аналог std::string(size_t n, char c). Обратите внимание, что тип результата chars() - длина строки - зависит от целочисленного аргумента, поэтому этот аргумент передаём как синглетон. А результат функции ct_chars() зависит и от содержимого строки, поэтому символ тоже приходится передавать как синглетон.
constexpr Str auto chars(CtSize auto n, char c) {
constexpr size_t size = n.value;
str<size> res;
auto it = res.begin();
it = std::fill_n(it, size, c);
*it = 0;
return res;
}
constexpr CtStr auto ct_chars(CtSize auto n, CtChar auto c) {
return ct<chars(n, c.value)>{};
}Конкатенация нескольких строк. Можно было бы сделать просто операцию склеивания двух строк, но в КТ очень легко использовать вариадики для обработки сразу произвольного количества. Заодно, покажу маленькую магию вариадиков.
constexpr Str auto concat_str(Str auto const&... ss) {
if constexpr (sizeof...(ss) == 0) {
return str{""};
} else if constexpr (sizeof...(ss) == 1) {
// fold-expression с оператором "," над пачкой из единственного элемента
// разворачивается в этот самый единственный элемент
return (ss , ...);
} else {
// fold-expression для сложения размеров
constexpr size_t total_size = (ss.size() + ... + 0);
str<total_size> res;
auto it = res.begin();
// fold-expression c "," для выполнения цикла над элементами пачки
// причём мы собираем здесь побочные эффекты - в итератор и в массив
((it = std::copy(ss.begin(), ss.end(), it)) , ...);
*it = 0; // концевой ноль для порядка, хотя он и так там был (дефолтный конструктор)
return res;
}
}
// а тут просто распаковали вариадик в аргументы функции, а потом обернули результат
constexpr CtStr auto concat_ctstr(CtStr auto... ss) {
return ct<concat_str(ss.value ...)>{};
}Аналог std::to_string(). Неожиданно, но в стандартной библиотеке уже есть constexpr функция std::to_chars() (начиная с C++23), но она несколько ущербная и нуждается в обвязке.
// длину строки для числа приходится считать вручную
// (альтернатива - выделить заведомо большой буфер,
// а потом копировать оттуда значащую часть...)
constexpr size_t size_to_str_len(size_t x) {
size_t l = 1;
while (x >= 10) {
++l;
x /= 10;
}
return l;
}
// простейший аналог std::to_chars
constexpr void to_chars(char* begin, char* end, size_t x) {
while(begin != end) {
*(--end) = char{'0' + (x % 10)};
x /= 10;
}
}
// поскольку длина строки зависит от значения числа, то аргумент - синглетон
constexpr Str auto size_to_str(CtSize auto n) {
constexpr size_t x = n.value;
constexpr size_t l = size_to_str_len(x);
str<l> s;
::std::to_chars(s.begin(), s.end(), x);
return s;
}
// для единообразия...
constexpr CtStr auto size_to_ctstr(CtSize auto n) {
return ct<size_to_str(n)>{};
}Использовать можно как угодно. Да хотя бы в связке с макропроцессором!
constexpr CtStr auto app_name = .....; // как-то нетривиально вычислили
constexpr size_t app_version = .....; // тоже как-то нетривиально вычислили
constexpr CtStr auto here = ct_concat(
ctv<str{__FILE__}>,
ctv<str{":"}>,
size_to_ctstr(__LINE__),
ctv<str{" app "}>, app_name,
ctv<str{" ver="}>, size_to_ctstr(ctv<app_version>)
);Литералы
Выше видно, сколько синтаксического шума нужно сделать, чтобы создать КТ-строку по месту.
Чтобы сделать жизнь красивее, есть два способа (и оба я у себя использую).
Первый самый тупой: макросы.
#define STR(literal) ::nn::str{literal}
#define CTSTR(literal) ::nn::ct<STR(literal)>{} // или ::nn::ctv<STR(literal)>
// где literal - "строковый литерал"
// а ::nn - пространство имён проекта nenormalПодход прижился, потому что макросов в проекте много (но магии препроцессора мало - разве что в концептах), так что визуально они не выбиваются.
Второй - именованные литералы. И это тоже немножко магии C++.
Оператор литерала operator ""name_goes_here, если операнд - строка, - имеет удобную шаблонную форму. Главное требование, чтобы формальный параметр можно было вывести из строкового литерала. По счастью (и по моему замыслу), так оно и есть!
namespace literals {
// string literals
template<str s> constexpr auto operator""_ss() { return s; }
template<str s> constexpr auto operator""_cts() { return ctv<s>; }
} // namespace literalsОбратите внимание, что вместо конкретного типа str<N> - где N неизвестно, - указано имя шаблона, и в этом случае срабатывает CTAD (class template argument deduction).
Я не знаю, почему эту форму сделали только для строк, а для чисел оставили упоротую распаковку вариадика из символов, чтобы пользователь заново проделывал ту же работу, что только что проделал лексер компилятора. (https://cppreference.com/cpp/language/user_literal). Ну, маемо шо маемо.
Итак, теперь мы спокойно можем писать
using namespace ::nn::literals;
constexpr auto hello = CTSTR("hello");
constexpr auto world = "world"_cts;
constexpr auto greeting = ::nn::ct_concat(hello, ", "_cts, world, "!"_cts);В следующей части мы спустимся ещё на одну ступеньку - и займёмся циклами.