intermediate changes

ref:2d4f292087954c9344efdabb7b2a67f466263c65

1 files changed, 78 insertions, 15 deletions

diff --git a/tools/enum_parser/enum_serialization_runtime/ordered_pairs.h b/tools/enum_parser/enum_serialization_runtime/ordered_pairs.h
index 874c7094183..4dce4dc3f31 100644
--- a/tools/enum_parser/enum_serialization_runtime/ordered_pairs.h
+++ b/tools/enum_parser/enum_serialization_runtime/ordered_pairs.h
@@ -1,20 +1,23 @@
 #pragma once
 
+#include <util/generic/algorithm.h>
 #include <util/generic/array_ref.h>
 #include <util/generic/strbuf.h>
+#include <array>
+#include <functional>
 
 namespace NEnumSerializationRuntime {
     enum class ESortOrder: int {
-        Unordered = 0,
-        Ascending = 1,
-        StrictlyAscending = 2,
-        DirectMapping = 3,
+        Unordered = 0,         // беспорядок
+        Ascending = 1,         // можно искать бинарным поиском, но есть эквивалентные ключи. Гланый ключ находится через lower_bound
+        StrictlyAscending = 2, //   + все ключи уникальны
+        DirectMapping = 3,     // последовательность целых чисел без пропусков, индекс элемента можно вычислить из его значения не делая поиск
     };
 
     template <typename TEnumRepresentationType>
     struct TEnumStringPair {
-        const TEnumRepresentationType Key;
-        const TStringBuf Name;
+        TEnumRepresentationType Key;
+        TStringBuf Name;
     };
 
     template <typename TEnumRepresentationType>
@@ -25,10 +28,12 @@ namespace NEnumSerializationRuntime {
         bool direct = true;
         bool strict = true;
         bool sorted = true;
-        TEnumRepresentationType expected = initializer.data()[0].Key;
-        for (size_t i = 1; i < initializer.size(); ++i) {
-            const auto& prev = initializer.data()[i - 1].Key;
-            const auto& next = initializer.data()[i - 0].Key;
+        const auto* data = initializer.data();
+        const size_t size = initializer.size();
+        TEnumRepresentationType expected = data[0].Key;
+        for (size_t i = 1; i < size; ++i) {
+            const auto& prev = data[i - 1].Key;
+            const auto& next = data[i - 0].Key;
             if (++expected != next) {
                 direct = false;
             }
@@ -53,13 +58,16 @@ namespace NEnumSerializationRuntime {
         }
         bool strict = true;
         bool sorted = true;
-        for (size_t i = 1; i < initializer.size(); ++i) {
-            const std::string_view prev = initializer.data()[i - 1].Name;
-            const std::string_view next = initializer.data()[i - 0].Name;
-            if (prev >= next) {
+        const auto* data = initializer.data();
+        const size_t size = initializer.size();
+        for (size_t i = 1; i < size; ++i) {
+            const std::string_view& prev = data[i - 1].Name;
+            const std::string_view& next = data[i - 0].Name;
+            const int cmp = prev.compare(next);
+            if (cmp >= 0) {
                 strict = false;
             }
-            if (prev > next) {
+            if (cmp > 0) {
                 sorted = false;
                 break;
             }
@@ -68,4 +76,59 @@ namespace NEnumSerializationRuntime {
                : sorted ? ESortOrder::Ascending
                         : ESortOrder::Unordered;
     }
+
+#if defined(__cpp_lib_array_constexpr) && defined(__cpp_lib_constexpr_algorithms) && defined(__cpp_lib_constexpr_functional)
+
+    // Функция должна состоять из единственного вызова
+    // std::stable_sort(v.begin(), v.end(), [](const T& a, const T& b) { return a.Key < b.Key; });
+    // и возврата отсортированного массива.
+    // Но в C++20 stable_sort ещё не имеет спецификатора constexpr и не может использоваться тут.
+    // Поэтому в текущей реализации вместо этого делается обычная нестабильная сортировка пар {ключ элемента, положение элемента}.
+    template <class T, size_t N>
+    constexpr std::array<T, N> TryStableSortKeys(std::array<T, N> v) {
+        // Компилятор обычно ограничивает число шагов, которые можно сделать при вычислении constexpr-функции (см. опции `-fconstexpr-steps=N` или `/constexpr:stepsN`).
+        // Число же шагов, необходимых для сортировки, зависит не только от длины массива,
+        // но и от используемого алгоритма, от числа вложенных функций в его реализации, и от наличия assert'ов в ней.
+        // Что также означает, что число шагов может меняться в несколько раз при смене реализации STL или при сборке с NDEBUG и без.
+        //
+        // Исчерпание бюджета на действия приведёт к ошибки компиляции без возможности восстановления.
+        // То есть без возможности обнаружить эту ситуацию и переключится на другой алгоритм.
+        //
+        // Поэтому максимальный размер сортируемого массива заранее ограничивается безопасной константой.
+        // А все массивы большего размера досортировываются уже во время исполнения программы.
+        constexpr size_t MAX_COMPILE_TIME_SORT_ARRAY_SIZE = 2'000;
+        if (v.size() > MAX_COMPILE_TIME_SORT_ARRAY_SIZE) {
+            return v;
+        }
+
+        // Многие перечисления уже отсортированы. Но текущая реализация constexpr std::sort в libcxx не проверяет этот случай и всегда работает за время Θ(NlogN)
+        if (IsSortedBy(v.begin(), v.end(), std::mem_fn(&T::Key))) {
+            return v;
+        }
+
+        std::array<const T*, N> ptrs;
+        Iota(ptrs.begin(), ptrs.end(), &v[0]);
+        auto cmpKeyPointersFn = [](const T* a, const T* b) {
+            if (a->Key != b->Key) {
+                return a->Key < b->Key;
+            }
+            return a < b; // ensure stable sort order
+        };
+        Sort(ptrs.begin(), ptrs.end(), cmpKeyPointersFn);
+
+        std::array<T, N> r;
+        for (size_t i = 0; i < N; ++i) {
+            r[i] = *ptrs[i];
+        }
+        return r;
+    }
+
+#else
+
+    template <class T, size_t N>
+    constexpr std::array<T, N> TryStableSortKeys(std::array<T, N> v) {
+        return v; // skip sort in case of old language version
+    }
+
+#endif
 }