Merge branch 'rightlib' into mergelibs-241002-1139

15 files changed, 373 insertions, 21 deletions

diff --git a/library/cpp/cppparser/parser.cpp b/library/cpp/cppparser/parser.cpp
index 3bd968b459..70fb6a8735 100644
--- a/library/cpp/cppparser/parser.cpp
+++ b/library/cpp/cppparser/parser.cpp
@@ -1,4 +1,5 @@
 #include <util/generic/hash.h>
+#include <util/string/ascii.h>
 #include <util/string/cast.h>
 #include <util/generic/hash_set.h>
 #include <util/generic/yexception.h>
@@ -127,6 +128,10 @@ private:
                             break;
 
                         case '\'':
+                            if (QuoteCharIsADigitSeparator()) {
+                                Text_.Data += ch;
+                                break;
+                            }
                             Action(ch);
                             State_ = Character;
 
@@ -356,6 +361,35 @@ private:
         }
     }
 
+    // digit separator in integral literal (ex. 73'709'550'592)
+    bool QuoteCharIsADigitSeparator() const {
+        const TStringBuf data = Text_.Data;
+        if (data.empty()) {
+            return false;
+        }
+        if (!IsAsciiHex(data.back())) {
+            return false;
+        }
+        // check for char literal prefix (ex. `u8'$'`)
+        static constexpr TStringBuf literalPrefixes[] {
+            "u8",
+            "u",
+            "U",
+            "L",
+        };
+        for (const TStringBuf& literalPrefix : literalPrefixes) {
+            if (TStringBuf prev; data.BeforeSuffix(literalPrefix, prev)) {
+                if (!prev.empty() && (IsAsciiAlnum(prev.back()) || prev.back() == '_' || prev.back() == '$')) {
+                    // some macro name ends with an `u8` sequence
+                    continue;
+                }
+                // it is a prefixed character literal
+                return false;
+            }
+        }
+        return true;
+    }
+
     inline void Action(char ch) {
         Action();
         Text_.Data += ch;
diff --git a/library/cpp/monlib/metrics/fake.h b/library/cpp/monlib/metrics/fake.h
index b61f80fb41..b01ff2505a 100644
--- a/library/cpp/monlib/metrics/fake.h
+++ b/library/cpp/monlib/metrics/fake.h
@@ -131,11 +131,11 @@ namespace NMonitoring {
         {
         }
 
-        void Record(double value) override {
+        void Record(double value) noexcept override {
             Y_UNUSED(value);
         }
 
-        void Record(double value, ui32 count) override {
+        void Record(double value, ui32 count) noexcept override {
             Y_UNUSED(value, count);
         }
 
@@ -147,7 +147,7 @@ namespace NMonitoring {
             Y_UNUSED(time, consumer);
         }
 
-        void Reset() override {
+        void Reset() noexcept override {
         }
     };
 
diff --git a/library/cpp/monlib/metrics/histogram_collector.h b/library/cpp/monlib/metrics/histogram_collector.h
index 177d779634..718aa42bd2 100644
--- a/library/cpp/monlib/metrics/histogram_collector.h
+++ b/library/cpp/monlib/metrics/histogram_collector.h
@@ -14,12 +14,12 @@ namespace NMonitoring {
         /**
          * Store {@code count} times given {@code value} in this collector.
          */
-        virtual void Collect(double value, ui64 count) = 0;
+        virtual void Collect(double value, ui64 count) noexcept = 0;
 
         /**
          * Store given {@code value} in this collector.
          */
-        void Collect(double value) {
+        void Collect(double value) noexcept {
             Collect(value, 1);
         }
 
@@ -35,7 +35,7 @@ namespace NMonitoring {
         /**
          * Reset collector values
          */
-        virtual void Reset() = 0;
+        virtual void Reset() noexcept = 0;
 
         /**
          * @return snapshot of the state of this collector.
diff --git a/library/cpp/monlib/metrics/histogram_collector_explicit.cpp b/library/cpp/monlib/metrics/histogram_collector_explicit.cpp
index a567573a02..e0422b578e 100644
--- a/library/cpp/monlib/metrics/histogram_collector_explicit.cpp
+++ b/library/cpp/monlib/metrics/histogram_collector_explicit.cpp
@@ -21,13 +21,13 @@ namespace NMonitoring {
             Bounds_.push_back(Max<TBucketBound>());
         }
 
-        void Collect(double value, ui64 count) override {
+        void Collect(double value, ui64 count) noexcept override {
             auto it = LowerBound(Bounds_.begin(), Bounds_.end(), value);
             auto index = std::distance(Bounds_.begin(), it);
             Values_.Add(index, count);
         }
 
-        void Reset() override {
+        void Reset() noexcept override {
             Values_.Reset();
         }
 
diff --git a/library/cpp/monlib/metrics/histogram_collector_exponential.cpp b/library/cpp/monlib/metrics/histogram_collector_exponential.cpp
index c6bbfcfc69..73657cda56 100644
--- a/library/cpp/monlib/metrics/histogram_collector_exponential.cpp
+++ b/library/cpp/monlib/metrics/histogram_collector_exponential.cpp
@@ -22,7 +22,7 @@ namespace NMonitoring {
         {
         }
 
-        void Collect(double value, ui64 count) override {
+        void Collect(double value, ui64 count) noexcept override {
             ui32 index = Max<ui32>();
             if (value <= MinValue_) {
                 index = 0;
@@ -35,7 +35,7 @@ namespace NMonitoring {
             Values_.Add(index, count);
         }
 
-        void Reset() override {
+        void Reset() noexcept override {
             Values_.Reset();
         }
 
diff --git a/library/cpp/monlib/metrics/histogram_collector_linear.cpp b/library/cpp/monlib/metrics/histogram_collector_linear.cpp
index 8342485320..b893b16a83 100644
--- a/library/cpp/monlib/metrics/histogram_collector_linear.cpp
+++ b/library/cpp/monlib/metrics/histogram_collector_linear.cpp
@@ -23,7 +23,7 @@ namespace NMonitoring {
         {
         }
 
-        void Collect(double value, ui64 count) override {
+        void Collect(double value, ui64 count) noexcept override {
             ui32 index = Max<ui32>();
             if (value <= StartValue_) {
                 index = 0;
@@ -36,7 +36,7 @@ namespace NMonitoring {
             Values_.Add(index, count);
         }
 
-        void Reset() override {
+        void Reset() noexcept override {
             Values_.Reset();
         }
 
diff --git a/library/cpp/monlib/metrics/metric.h b/library/cpp/monlib/metrics/metric.h
index cf736e8d80..2f7d9de687 100644
--- a/library/cpp/monlib/metrics/metric.h
+++ b/library/cpp/monlib/metrics/metric.h
@@ -131,10 +131,10 @@ namespace NMonitoring {
             return IsRate_ ? EMetricType::HIST_RATE : EMetricType::HIST;
         }
 
-        virtual void Record(double value) = 0;
-        virtual void Record(double value, ui32 count) = 0;
+        virtual void Record(double value) noexcept = 0;
+        virtual void Record(double value, ui32 count) noexcept = 0;
         virtual IHistogramSnapshotPtr TakeSnapshot() const = 0;
-        virtual void Reset() = 0;
+        virtual void Reset() noexcept = 0;
 
     protected:
         const bool IsRate_;
@@ -368,11 +368,11 @@ namespace NMonitoring {
         {
         }
 
-        void Record(double value) override {
+        void Record(double value) noexcept override {
             Collector_->Collect(value);
         }
 
-        void Record(double value, ui32 count) override {
+        void Record(double value, ui32 count) noexcept override {
             Collector_->Collect(value, count);
         }
 
@@ -384,7 +384,7 @@ namespace NMonitoring {
             return Collector_->Snapshot();
         }
 
-        void Reset() override {
+        void Reset() noexcept override {
             Collector_->Reset();
         }
 
diff --git a/library/cpp/protobuf/json/config.h b/library/cpp/protobuf/json/config.h
index 98d484cdf4..d0d2d21bcf 100644
--- a/library/cpp/protobuf/json/config.h
+++ b/library/cpp/protobuf/json/config.h
@@ -109,6 +109,9 @@ namespace NProtobufJson {
 
         bool WriteNanAsString = false;
 
+        // Sort keys in maps before serialization.
+        bool SortMapKeys = false;
+
         TSelf& SetDoubleNDigits(ui32 ndigits) {
             DoubleNDigits = ndigits;
             return *this;
@@ -189,6 +192,11 @@ namespace NProtobufJson {
             return *this;
         }
 
+        TSelf& SetSortMapKeys(bool value) {
+            SortMapKeys = value;
+            return *this;
+        }
+
         TSelf& SetStringifyNumbers(EStringifyNumbersMode stringify) {
             StringifyNumbers = stringify;
             return *this;
diff --git a/library/cpp/protobuf/json/proto2json_printer.cpp b/library/cpp/protobuf/json/proto2json_printer.cpp
index 5d0e140615..a9f8c3fce9 100644
--- a/library/cpp/protobuf/json/proto2json_printer.cpp
+++ b/library/cpp/protobuf/json/proto2json_printer.cpp
@@ -8,6 +8,7 @@
 
 #include <library/cpp/protobuf/json/proto/enum_options.pb.h>
 
+#include <util/generic/map.h>
 #include <util/generic/yexception.h>
 #include <util/string/ascii.h>
 #include <util/string/cast.h>
@@ -394,8 +395,22 @@ namespace NProtobufJson {
 
                 case FieldDescriptor::CPPTYPE_MESSAGE: {
                     if (isMap) {
-                        for (size_t i = 0, endI = reflection->FieldSize(proto, &field); i < endI; ++i) {
-                            PrintKeyValue(reflection->GetRepeatedMessage(proto, &field, i), json);
+                        if (GetConfig().SortMapKeys) {
+                            TMap<TString, size_t> keyToIndex;
+                            for (size_t i = 0, endI = reflection->FieldSize(proto, &field); i < endI; ++i) {
+                                const Message& fieldMessage = reflection->GetRepeatedMessage(proto, &field, i);
+                                const FieldDescriptor* keyField = fieldMessage.GetDescriptor()->map_key();
+                                Y_ABORT_UNLESS(keyField, "Map entry key field not found.");
+                                TString key = MakeKey(fieldMessage, *keyField);
+                                keyToIndex[key] = i;
+                            }
+                            for (const auto& [_, i] : keyToIndex) {
+                                PrintKeyValue(reflection->GetRepeatedMessage(proto, &field, i), json);
+                            }
+                        } else {
+                            for (size_t i = 0, endI = reflection->FieldSize(proto, &field); i < endI; ++i) {
+                                PrintKeyValue(reflection->GetRepeatedMessage(proto, &field, i), json);
+                            }
                         }
                     } else {
                         for (size_t i = 0, endI = reflection->FieldSize(proto, &field); i < endI; ++i) {
diff --git a/library/cpp/protobuf/json/ut/proto2json_ut.cpp b/library/cpp/protobuf/json/ut/proto2json_ut.cpp
index 9e98ab8a06..f5bcfac49d 100644
--- a/library/cpp/protobuf/json/ut/proto2json_ut.cpp
+++ b/library/cpp/protobuf/json/ut/proto2json_ut.cpp
@@ -997,6 +997,24 @@ Y_UNIT_TEST(TestMapUsingGeneratedAsJSON) {
     UNIT_ASSERT_JSON_STRINGS_EQUAL(jsonStr.Str(), modelStr);
 } // TestMapUsingGeneratedAsJSON
 
+Y_UNIT_TEST(TestMapSortedKeys) {
+    TMapType proto;
+
+    auto& items = *proto.MutableItems();
+    items["key1"] = "value1";
+    items["key2"] = "value2";
+    items["key3"] = "value3";
+
+    TString modelStr(R"_({"Items":{"key1":"value1","key2":"value2","key3":"value3"}})_");
+
+    TStringStream jsonStr;
+
+    auto config = TProto2JsonConfig().SetMapAsObject(true).SetSortMapKeys(false);
+    UNIT_ASSERT_NO_EXCEPTION(Proto2Json(proto, jsonStr, config));
+
+    UNIT_ASSERT_JSON_STRINGS_EQUAL(jsonStr.Str(), modelStr);
+} // TestMapSortedKeys
+
 Y_UNIT_TEST(TestMapDefaultValue) {
     TMapType proto;
 
diff --git a/library/cpp/tld/tlds-alpha-by-domain.txt b/library/cpp/tld/tlds-alpha-by-domain.txt
index a5776075a1..21df2a6307 100644
--- a/library/cpp/tld/tlds-alpha-by-domain.txt
+++ b/library/cpp/tld/tlds-alpha-by-domain.txt
@@ -1,4 +1,4 @@
-# Version 2024092800, Last Updated Sat Sep 28 07:07:01 2024 UTC
+# Version 2024093002, Last Updated Tue Oct  1 07:07:01 2024 UTC
 AAA
 AARP
 ABB
diff --git a/library/cpp/yt/containers/expiring_set-inl.h b/library/cpp/yt/containers/expiring_set-inl.h
new file mode 100644
index 0000000000..66cab7203b
--- /dev/null
+++ b/library/cpp/yt/containers/expiring_set-inl.h
@@ -0,0 +1,88 @@
+#ifndef EXPIRING_SET_INL_H_
+#error "Direct inclusion of this file is not allowed, include expiring_set.h"
+// For the sake of sane code completion.
+#include "expiring_set.h"
+#endif
+
+namespace NYT {
+
+////////////////////////////////////////////////////////////////////////////////
+
+template <class TItem, class THash, class TEqual>
+void TExpiringSet<TItem, THash, TEqual>::SetTTl(TDuration ttl)
+{
+    TTl_ = ttl;
+}
+
+template <class TItem, class THash, class TEqual>
+void TExpiringSet<TItem, THash, TEqual>::Insert(TInstant now, const TItem& item)
+{
+    Expire(now);
+    auto deadline = now + TTl_;
+    ItemToDeadline_[item] = deadline;
+    ExpirationQueue_.push(TItemPack{.Items = {item}, .Deadline = deadline});
+}
+
+template <class TItem, class THash, class TEqual>
+template <class TItems>
+void TExpiringSet<TItem, THash, TEqual>::InsertMany(TInstant now, const TItems& items)
+{
+    Expire(now);
+    auto deadline = now + TTl_;
+    for (const auto& item : items) {
+        ItemToDeadline_[item] = deadline;
+    }
+    ExpirationQueue_.push(TItemPack{.Items = {items.begin(), items.end()}, .Deadline = deadline});
+}
+
+template <class TItem, class THash, class TEqual>
+void TExpiringSet<TItem, THash, TEqual>::Remove(const TItem& item)
+{
+    ItemToDeadline_.erase(item);
+}
+
+template <class TItem, class THash, class TEqual>
+void TExpiringSet<TItem, THash, TEqual>::Expire(TInstant now)
+{
+    while (!ExpirationQueue_.empty() && ExpirationQueue_.top().Deadline <= now) {
+        for (const auto& item : ExpirationQueue_.top().Items) {
+            if (auto it = ItemToDeadline_.find(item); it != ItemToDeadline_.end()) {
+                if (it->second <= now) {
+                    ItemToDeadline_.erase(it);
+                }
+            }
+        }
+        ExpirationQueue_.pop();
+    }
+}
+
+template <class TItem, class THash, class TEqual>
+void TExpiringSet<TItem, THash, TEqual>::Clear()
+{
+    ItemToDeadline_ = {};
+    ExpirationQueue_ = {};
+}
+
+template <class TItem, class THash, class TEqual>
+template <class TItemLike>
+bool TExpiringSet<TItem, THash, TEqual>::Contains(const TItemLike& item) const
+{
+    return ItemToDeadline_.contains(item);
+}
+
+template <class TItem, class THash, class TEqual>
+int TExpiringSet<TItem, THash, TEqual>::GetSize() const
+{
+    return std::ssize(ItemToDeadline_);
+}
+
+template <class TItem, class THash, class TEqual>
+bool TExpiringSet<TItem, THash, TEqual>::TItemPack::operator<(const TItemPack& other) const
+{
+    // Reversed ordering for the priority queue.
+    return Deadline > other.Deadline;
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace NYT
diff --git a/library/cpp/yt/containers/expiring_set.h b/library/cpp/yt/containers/expiring_set.h
new file mode 100644
index 0000000000..101c7d8ac1
--- /dev/null
+++ b/library/cpp/yt/containers/expiring_set.h
@@ -0,0 +1,56 @@
+#pragma once
+
+#include <util/generic/hash.h>
+
+#include <util/datetime/base.h>
+
+#include <queue>
+
+namespace NYT {
+
+////////////////////////////////////////////////////////////////////////////////
+
+//! Maintains a set of items that expire after a certain time.
+template <class TItem, class THash = THash<TItem>, class TEqual = TEqualTo<TItem>>
+class TExpiringSet
+{
+public:
+    void SetTTl(TDuration ttl);
+
+    void Insert(TInstant now, const TItem& item);
+    template <class TItems>
+    void InsertMany(TInstant now, const TItems& items);
+
+    void Remove(const TItem& item);
+
+    void Expire(TInstant now);
+
+    void Clear();
+
+    template <class TItemLike>
+    bool Contains(const TItemLike& item) const;
+
+    int GetSize() const;
+
+private:
+    TDuration TTl_;
+
+    struct TItemPack
+    {
+        std::vector<TItem> Items;
+        TInstant Deadline;
+
+        bool operator<(const TItemPack& other) const;
+    };
+
+    THashMap<TItem, TInstant, THash, TEqual> ItemToDeadline_;
+    std::priority_queue<TItemPack> ExpirationQueue_;
+};
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace NYT
+
+#define EXPIRING_SET_INL_H_
+#include "expiring_set-inl.h"
+#undef EXPIRING_SET_INL_H_
diff --git a/library/cpp/yt/containers/unittests/expiring_set_ut.cpp b/library/cpp/yt/containers/unittests/expiring_set_ut.cpp
new file mode 100644
index 0000000000..2de32c1f3f
--- /dev/null
+++ b/library/cpp/yt/containers/unittests/expiring_set_ut.cpp
@@ -0,0 +1,132 @@
+#include <library/cpp/yt/containers/expiring_set.h>
+
+#include <library/cpp/testing/gtest/gtest.h>
+
+namespace NYT {
+namespace {
+
+////////////////////////////////////////////////////////////////////////////////
+
+TInstant operator""_ts(unsigned long long seconds)
+{
+    return TInstant::Zero() + TDuration::Seconds(seconds);
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+TEST(TExpiringSetTest, Empty)
+{
+    TExpiringSet<int> set;
+    EXPECT_EQ(set.GetSize(), 0);
+}
+
+TEST(TExpiringSetTest, ExpireSingle)
+{
+    TExpiringSet<int> set;
+    set.SetTTl(TDuration::Seconds(2));
+
+    set.Insert(0_ts, 1);
+    EXPECT_EQ(set.GetSize(), 1);
+
+    set.Expire(1_ts);
+    EXPECT_EQ(set.GetSize(), 1);
+
+    set.Expire(2_ts);
+    EXPECT_EQ(set.GetSize(), 0);
+}
+
+TEST(TExpiringSetTest, ExpireBatch)
+{
+    TExpiringSet<int> set;
+    set.SetTTl(TDuration::Seconds(2));
+
+    set.InsertMany(0_ts, std::vector<int>{1, 2, 3});
+    EXPECT_EQ(set.GetSize(), 3);
+
+    set.Expire(1_ts);
+    EXPECT_EQ(set.GetSize(), 3);
+
+    set.Expire(2_ts);
+    EXPECT_EQ(set.GetSize(), 0);
+}
+
+TEST(TExpiringSetTest, Reinsert)
+{
+    TExpiringSet<int> set;
+    set.SetTTl(TDuration::Seconds(2));
+
+    set.Insert(0_ts, 1);
+    EXPECT_EQ(set.GetSize(), 1);
+
+    set.Insert(1_ts, 1);
+    EXPECT_EQ(set.GetSize(), 1);
+
+    set.Expire(2_ts);
+    EXPECT_EQ(set.GetSize(), 1);
+
+    set.Expire(3_ts);
+    EXPECT_EQ(set.GetSize(), 0);
+}
+
+TEST(TExpiringSetTest, Contains)
+{
+    TExpiringSet<int> set;
+    set.SetTTl(TDuration::Seconds(1));
+
+    EXPECT_FALSE(set.Contains(1));
+
+    set.Insert(0_ts, 1);
+    EXPECT_TRUE(set.Contains(1));
+
+    set.Expire(1_ts);
+    EXPECT_FALSE(set.Contains(1));
+}
+
+TEST(TExpiringSetTest, Clear)
+{
+    TExpiringSet<int> set;
+    set.SetTTl(TDuration::Seconds(1));
+
+    set.Insert(0_ts, 1);
+    EXPECT_EQ(set.GetSize(), 1);
+    EXPECT_TRUE(set.Contains(1));
+
+    set.Clear();
+    EXPECT_EQ(set.GetSize(), 0);
+    EXPECT_FALSE(set.Contains(1));
+}
+
+TEST(TExpiringSetTest, RemoveBeforeExpire)
+{
+    TExpiringSet<int> set;
+    set.SetTTl(TDuration::Seconds(1));
+
+    set.Insert(0_ts, 1);
+    EXPECT_EQ(set.GetSize(), 1);
+    EXPECT_TRUE(set.Contains(1));
+
+    set.Remove(1);
+    EXPECT_EQ(set.GetSize(), 0);
+    EXPECT_FALSE(set.Contains(1));
+}
+
+TEST(TExpiringSetTest, RemoveAfterExpire)
+{
+    TExpiringSet<int> set;
+    set.SetTTl(TDuration::Seconds(1));
+
+    set.Insert(0_ts, 1);
+    set.Expire(2_ts);
+
+    EXPECT_EQ(set.GetSize(), 0);
+    EXPECT_FALSE(set.Contains(1));
+
+    set.Remove(1);
+    EXPECT_EQ(set.GetSize(), 0);
+    EXPECT_FALSE(set.Contains(1));
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace
+} // namespace NYT
diff --git a/library/cpp/yt/containers/unittests/ya.make b/library/cpp/yt/containers/unittests/ya.make
index 3ffc420658..3732116a51 100644
--- a/library/cpp/yt/containers/unittests/ya.make
+++ b/library/cpp/yt/containers/unittests/ya.make
@@ -6,6 +6,7 @@ SIZE(MEDIUM)
 
 SRCS(
     enum_indexed_array_ut.cpp
+    expiring_set_ut.cpp
     sharded_set_ut.cpp
 )