Пишем компайл-тайм генератор псевдо-рандомных чисел на чистых шаблонах

[D2]

Всем привет!
Это моя первая статья на этом форуме и я решил начать с чего-то простенького, не судите строго.

Порой читая код опенсорсных плюсовых малварей, складывается не самое лучшее впечатление о коде, нередко люди предпочитают обмазываться макросами и непортабельными расширениями компиляторов, особенно это касается генерации псевдо-случайных чисел, шифрования строк, обфускации вызовов и тому подобного, сегодня я постараюсь это немного исправить и заодно разобрать одну из интереснейших техник в плюсовой компайл-тайм разработке, появившуюся ещё в C++ 14 и окончательно утвердившуюся в C++ 20 с эволюцией NTTP и появлением лямд в unevaluated контексте, более известную как лупхолы типов или просто лупхолы.

Эта статья не претендует на какую-то эксклюзивную информацию, ибо сегодня об этой технике знает наверное уже каждый опытный C++ разработчик, но несмотря на это, оговорюсь, что плюсовой комитет считает эту технику эксплуатацией дизайна языка и предлагает её к запрету ещё с 2015 года. Тем не менее техника полностью соответствует стандарту языка и является портабельной, а учитывая, что её использует буст и даже гугл, маловероятно что её все же запретят, ведь с другими распространенными "хитрыми" техниками этого не произошло. =)

Заранее оговорюсь, я буду взаимозаменяемо использовать слова класс и структура, ибо особой разницы между ними нет (если выкинуть баги с шаблонами, то единственной разницей будет дефолтный доступ к элементам).
В основном я постараюсь показать простые примеры применения, но на самом деле этими примерами применение лупхолов не ограничивается - их можно использовать и для построения гораздо более сложных алгоритмов, включая stateful компайл-тайм парсинга сложных SQL запросов к базам данных, создания псевдо-рефлексии и так далее, короче говоря очень мощная техника.

Тем не менее, несмотря на всю свою мощь, сама техника проста как табуретка:
Мы создаем шаблонный класс или структуру с friend функцией, которая принимает саму структуру или её шаблонные параметры в качестве своего аргумента, что, как вы уже догадались, создает селф-референс на структуру и получается типовой луп.
Это происходит потому, что friend функции обладают форвард декларацией в классах и не привязаны к самим классам, то есть нам необязательно объявлять их до объявления класса, чтобы сослаться на них, что и делает лупхолы возможными.
Но как же теперь получить "референс" на эту функцию? Здесь и кроется весь секрет, штука в том, что C++ ищет функции по их аргументам, это называется Argument Dependent Lookup или просто ADL. Давайте взглянем на этот классический пример лупхола:
C++: Скопировать в буфер обмена

template <std::size_t I> struct Tag {};
template <typename T, std::size_t I>
struct Loophole { friend auto Get(Tag<I>) { return T{}; } };

// декларация friend функции (или если более пафосно, "инжект friend функции в глобальный неймспейс" (c) комитет)
// и инстанциация специализации структуры, порядок не важен, так как возвращаемый тип функции ещё не был дедуцирован
auto Get(Tag<0>);
Loophole<std::size_t, 0> lh{};

// заставляем компилятор дедуцировать возвращаемый тип
static_assert(std::is_same_v<decltype(Get(Tag<0>{})), std::size_t>);

Что же здесь происходит? У нас есть функция Get, которая не привязана к классу и не является его методом, при этом она объявлена внутри класса и может использовать его шаблонные параметры, в том числе для своих аргументов.
Далее идет декларация функции с конкретным типом аргумента, в данном случае это Tag<0> (вместо NTTP с 0 здесь может быть и тип, это не так важно), C++ находит эту функцию по типу её аргумента используя ADL, и инстанциирует эту специализацию функции в глобальный неймспейс, это называется инжектом, после чего мы явно инстанциируем специализацию типа класса Loophole с первым шаблонным параметром типа std::size_t и тем же индексом, который был у аргумента при инстанциировании функции Get строкой выше. На этом моменте компилятор сохранил у себя в памяти 2 типа:
struct Loophole<std::size_t, 0>
auto Get(Tag<0>)

Теперь всё, что нам остается, это заставить компилятор дедуцировать для нас возвращаемый тип функции Get с аргументом Tag<0>, так как эта функция возвращает значение с типом первого параметра из шаблона Loophole, то компилятор обратится к `struct Loophole<std::size_t, 0>` и вытащит этот тип оттуда, в нашем случае это и будет std::size_t. Звучит круто, не правда ли?)

С теорией разобрались, дальше так подробно детали я пояснять не буду для экономии моего времени и времени читателя.
Прежде чем писать генератор псевдо-случайных чисел, сначала нам нужно будет написать counter и storage, для начала нам нужны сами лупхолы:
Спойлер
C++: Скопировать в буфер обмена

namespace loophole
{
    enum class State { Value };

    template <typename TTag>
    struct Flag { friend consteval State Get(Flag); };

    template <typename TTag, typename TFlag>
    struct Creator { friend consteval State Get(TFlag) { return State::Value; } };

    template <typename TTag>
    consteval bool CheckExists(...) { return false; }

    template <typename TTag, State = Get(Flag<TTag>{})>
    consteval bool CheckExists(State) { return true; }

    template <typename TTag>
    consteval bool Create(...) { return !sizeof(Creator<TTag, Flag<TTag>>); }

    template <typename TTag, State = Get(Flag<TTag>{})>
    consteval bool Create(State) { return true; }
}

// false если значение не существует (лупхол не был выставлен), true если существует
template <typename TTag, bool bResult = loophole::CheckExists<TTag>(loophole::State::Value)>
consteval bool CheckExists() { return bResult; }

// создает значение если оно не существует, возвращает false если значение не существовало, true если оно уже существовало
template <typename TTag, bool bResult = loophole::Create<TTag>(loophole::State::Value)>
consteval bool Create() { return bResult; }

На первый взгляд со счетчиком всё просто, нужно просто проверять, есть ли функция и если есть, то просто увеличивать счетчик на единицу, пока не дойдем до момента, где функции нет. Если её не было изначально, то просто инжектим:
Спойлер
C++: Скопировать в буфер обмена

template <typename TTag, std::size_t N>
struct Index;

template <std::size_t szCurrent>
struct RecursiveSearch
{
    template <typename TTag, bool bIsNextIndex = CheckExists<Index<TTag, szCurrent>>(),
        std::size_t szResult = bIsNextIndex ? RecursiveSearch<szCurrent + 1>::template Next<TTag>() : szCurrent>
    static consteval std::size_t Next() { return szResult; }
};

template <typename TTag, std::size_t szResult = RecursiveSearch<0>::template Next<TTag>()>
consteval std::size_t Find() { return szResult; }

template <typename, typename TTag, std::size_t szIndex = Find<TTag>(), bool = Create<Index<TTag, szIndex>>()>
consteval std::size_t ConstCounter() { return szIndex; }

template <typename TTag, std::size_t szResult = ConstCounter<void, TTag>()>
consteval std::size_t ConstCounter() { return szResult; }

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

template <typename TTag, std::size_t N>
struct Index;

template <std::size_t szSize>
struct BinarySearch;

template <>
struct BinarySearch<1>
{
    template <std::size_t szMiddle, typename TTag, bool bIsNextIndex = CheckExists<Index<TTag, szMiddle>>()>
    static consteval std::size_t Next() { return szMiddle + (bIsNextIndex ? 1 : 0); }
};

// фоллбек для невалидного инпута
template <>
struct BinarySearch<0>
{
    template <std::size_t szMiddle, typename Tag>
    static consteval std::size_t Next() { return 0; }
};

template <std::size_t szSize>
struct BinarySearch
{
    template <std::size_t szMiddle, typename TTag,
        std::size_t szNextSize = (szSize >> 1), bool bIsNextIndex = CheckExists<Index<TTag, szMiddle>>(),
        std::size_t szShift = (szNextSize >> 1) + 1,
        std::size_t szNextMiddle = bIsNextIndex ? szMiddle + szShift : szMiddle - szShift,
        std::size_t szResult = BinarySearch<szNextSize>::template Next<szNextMiddle, TTag>()>
    static consteval std::size_t Next() { return szResult; }
};

// максимальный размер области поиска, если хотите оверрайднуть, то оно должно быть числом мерсенна
// std::numeric_limits<NumberType>::max() всегда будет являться таким числом
template <typename TTag, std::size_t szSize = (std::numeric_limits<std::size_t>::max)(), std::size_t szResult = BinarySearch<szSize>::template Next<(szSize >> 1), TTag>()>
consteval std::size_t Find() { return szResult; }

template <typename TTag, std::size_t szIndex = Find<TTag>(), bool = Create<Index<TTag, szIndex>>()>
consteval std::size_t ConstCounterInternal() { return szIndex; }

template <typename TTag, std::size_t szResult = ConstCounterInternal<TTag>()>
consteval std::size_t ConstCounter() { return szResult; }

Замечательно, теперь всё компилируется как надо. Следующим шагом мы имплементируем storage, тут тоже всё тривиально, мы запоминаем текущее значение каунтера, которое становится частью нашего тага, затем мы лупхолим значение с этим тагом.
Для начала, нам нужно написать ассигнер, который будет выставлять значение так, чтобы мы могли найти его бинарным поиском, здесь у нас все тривиально:
Спойлер
C++: Скопировать в буфер обмена

struct Dummy {};

template <typename TTag, bool bResult = Create<TTag>()>
consteval Dummy Set() { return {}; }

template <std::size_t szValue>
struct Assigner
{
    // для того, чтобы "найти" значение бинарным поиском, нам нужно нужно создать "путь", по которому будет ориентироваться поисковик
    template <typename TTag, auto = Set<Index<TTag, szValue - 1>>(),
                auto = Assigner<szValue & (szValue - 1)>::template Next<TTag>()>
    static consteval Dummy Next() { return {}; }
};

template <>
struct Assigner<0>
{
    template <typename TTag>
    static consteval Dummy Next() { return {}; }
};

template <typename TTag, std::size_t szValue, auto = Assigner<szValue>::template Next<TTag>()>
consteval Dummy Assign() { return {}; }

ну и теперь нам всего-лишь остается дописать сам сторедж:
Спойлер
C++: Скопировать в буфер обмена

template <typename TTag = decltype([]{})>
struct ConstVarStorage
{
    template <typename TUserTag>
    struct ValueIndex {};

    template <typename TUserTag, std::size_t szIndex>
    struct ValueStorageTag {};

    // для каждого последующего ассигна мы используем свой таг
    // для того, чтобы таг был уникальным, мы используем каунтер
    template <std::size_t szValue, typename Tag = TTag, std::size_t szCurrentIndex = ConstCounter<ValueIndex<Tag>>(),
        auto = Assign<ValueStorageTag<Tag, szCurrentIndex + 1>, szValue>()>
    static consteval std::size_t Assign() { return szValue; }

    template <typename Tag = TTag,
        std::size_t szCurrentIndex = Find<ValueIndex<Tag>>(),
        std::size_t szValue = Find<ValueStorageTag<Tag, szCurrentIndex>>()>
    static consteval std::size_t Get() { return szValue; }
};

Да, вот так всё просто! Удивительно, не правда ли?
Ну и теперь осталось самое простое, это генерация псевдослучайных чисел, логика здесь ровно такая же, как и у генераторов на макросах - мы берем некоторый константный сид и используем его. В нашем случае мы берем константные строки и хешируем их, после чего используем полученное значение как сид. Для начала нам нужно обернуть строку, чтобы её можно было передать в качестве шаблонного параметра, для этого напишем простой класс:
Спойлер
C++: Скопировать в буфер обмена

template <typename TChar, std::size_t N>
class FixedString
{
public:
    constexpr FixedString(const TChar(&str)[N + 1])
    {
        std::copy_n(str, N + 1, m_Data);
    }

    using TValueType = TChar;
    using TSizeType = std::size_t;

    constexpr static std::size_t m_szLen = N;
    TChar m_Data[N + 1];
};

template <typename TChar, std::size_t N>
FixedString(const TChar(&str)[N]) -> FixedString<TChar, N - 1>;

и сами функции хеширования (вы можете заменить их на свои, чем проще, тем быстрее всё скомпилируется):
Спойлер
C++: Скопировать в буфер обмена

template <std::size_t szValue>
consteval std::size_t HashRecursive() { return szValue; }

template <std::size_t szValue, char c, char ... cc>
consteval std::size_t HashRecursive() { return HashRecursive<(static_cast<std::size_t>(c) ^ szValue) * std::size_t(11797901 /*может быть любым простым числом, да и сам алгоритм может быть любым, на ваш вкус*/), cc ...>(); }

template <FixedString Initial, std::size_t ... szIndexes>
consteval std::size_t HashInitialSeq(std::index_sequence<szIndexes ...>) { return HashRecursive<0, Initial.m_Data[szIndexes] ...>(); }

template <FixedString Initial>
consteval std::size_t HashInitial() { return HashInitialSeq<Initial>(std::make_index_sequence<Initial.m_szLen>()); }

ну и теперь дело осталось за малым:
Спойлер
C++: Скопировать в буфер обмена

struct ConstRandomTag;
struct ConstRandomCounterTag;

template <std::size_t szValue>
consteval std::size_t NextConstRandomValue()
{
    // каунтер нужен чтобы предотвратить кольцевую генерацию в случае возникновения коллизии
    if constexpr (!szValue) return HashInitial<__TIME__ __DATE__>() + ConstCounter<ConstRandomCounterTag>();
    else return szValue;
}

template <typename TValue = ConstVarStorage<ConstRandomTag>, std::size_t szValue = TValue::template Get<>()>
consteval std::size_t RoundConstRandom()
{
    // здесь мы получаем сид либо предыдущее значение, шаффлим его и возвращаем с ассигном вместо предыдущего
    // алгоритм шаффла здесь может быть абсолютно любым, вы можете заменить на свой
    constexpr std::size_t szNextValue = NextConstRandomValue<szValue>();
    return TValue::template Assign<(std::rotl(szNextValue, 17) ^ std::rotl(szNextValue, 4)) * std::size_t(32360183)>();
}

Вот такая вот небольшая статья, на этом всё и надеюсь вам понравилось, полный "отполированный" исходник:


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