Error attribute order is attribute adding order

commit_hash:1a8689ad5ded7d7bfab00e7fac0b0689f052c87a

6 files changed, 397 insertions, 1 deletions

diff --git a/library/cpp/yt/containers/ordered_hash_map-inl.h b/library/cpp/yt/containers/ordered_hash_map-inl.h
new file mode 100644
index 00000000000..c187d15f965
--- /dev/null
+++ b/library/cpp/yt/containers/ordered_hash_map-inl.h
@@ -0,0 +1,150 @@
+#ifndef ORDERED_HASH_MAP_INL_H_
+#error "Direct inclusion of this file is not allowed, include ordered_hash_map.h"
+// For the sake of sane code completion.
+#include "ordered_hash_map.h"
+#endif
+
+#include <library/cpp/yt/assert/assert.h>
+
+namespace NYT {
+
+////////////////////////////////////////////////////////////////////////////////
+
+template <class TKey, class TValue, class THashFunction, class TEqualFunction>
+std::pair<const TKey, TValue>& TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::TSelectPair::operator()(TItem& item) const
+{
+    return item;
+}
+
+template <class TKey, class TValue, class THashFunction, class TEqualFunction>
+const std::pair<const TKey, TValue>& TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::TSelectPair::operator()(const TItem& item) const
+{
+    return item;
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+template <class TKey, class TValue, class THashFunction, class TEqualFunction>
+TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::TOrderedHashMap(const TOrderedHashMap& other)
+{
+    *this = other;
+}
+
+template <class TKey, class TValue, class THashFunction, class TEqualFunction>
+auto TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::operator=(const TOrderedHashMap& other) -> TOrderedHashMap&
+{
+    clear();
+    Table_.reserve(other.size());
+    for (const auto& item : other) {
+        emplace(item.first, item.second);
+    }
+    return *this;
+}
+
+template <class TKey, class TValue, class THashFunction, class TEqualFunction>
+template <class... TArgs>
+auto TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::emplace(TArgs&&... args) -> std::pair<iterator, bool>
+{
+    auto [it, success] = Table_.emplace_unique(std::forward<TArgs>(args)...);
+    if (success) {
+        List_.PushBack(&*it);
+    }
+    return {MakeMappedIterator(TListIterator(&*it), TSelectPair{}), success};
+}
+
+template <class TKey, class TValue, class THashFunction, class TEqualFunction>
+template <class TOtherKey>
+auto TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::find(const TOtherKey& key) -> iterator
+{
+    auto it = Table_.find(key);
+    if (it == Table_.end()) {
+        return MakeMappedIterator(List_.end(), TSelectPair{});
+    }
+    return MakeMappedIterator(TListIterator(&*it), TSelectPair{});
+}
+
+template <class TKey, class TValue, class THashFunction, class TEqualFunction>
+template <class TOtherKey>
+auto TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::find(const TOtherKey& key) const -> const_iterator
+{
+    auto it = Table_.find(key);
+    if (it == Table_.end()) {
+        return MakeMappedIterator(List_.end(), TSelectPair{});
+    }
+    return MakeMappedIterator(TListConstIterator(&*it), TSelectPair{});
+}
+
+template <class TKey, class TValue, class THashFunction, class TEqualFunction>
+template <class TOtherKey>
+bool TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::contains(const TOtherKey& key) const
+{
+    return Table_.find(key) != Table_.end();
+}
+
+template <class TKey, class TValue, class THashFunction, class TEqualFunction>
+template <class TOtherKey>
+TValue& TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::operator[](const TOtherKey& key)
+{
+    typename TTable::insert_ctx ctx = nullptr;
+    auto it = Table_.find_i(key, ctx);
+    if (it != Table_.end()) {
+        return it->second;
+    }
+    it = Table_.emplace_direct(ctx, std::piecewise_construct, std::forward_as_tuple(key), std::forward_as_tuple());
+    List_.PushBack(&*it);
+    return it->second;
+}
+
+template <class TKey, class TValue, class THashFunction, class TEqualFunction>
+template <class TOtherKey>
+size_t TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::erase(const TOtherKey& key)
+{
+    return Table_.erase_one(key);
+}
+
+template <class TKey, class TValue, class THashFunction, class TEqualFunction>
+void TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::erase(iterator it)
+{
+    erase(it->first);
+}
+
+template <class TKey, class TValue, class THashFunction, class TEqualFunction>
+auto TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::begin() -> iterator
+{
+    return MakeMappedIterator(List_.begin(), TSelectPair{});
+}
+
+template <class TKey, class TValue, class THashFunction, class TEqualFunction>
+auto TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::end() -> iterator
+{
+    return MakeMappedIterator(List_.end(), TSelectPair{});
+}
+
+template <class TKey, class TValue, class THashFunction, class TEqualFunction>
+auto TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::begin() const -> const_iterator
+{
+    return MakeMappedIterator(List_.begin(), TSelectPair{});
+}
+
+template <class TKey, class TValue, class THashFunction, class TEqualFunction>
+auto TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::end() const -> const_iterator
+{
+    return MakeMappedIterator(List_.end(), TSelectPair{});
+}
+
+template <class TKey, class TValue, class THashFunction, class TEqualFunction>
+size_t TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::size() const
+{
+    return Table_.size();
+}
+
+template <class TKey, class TValue, class THashFunction, class TEqualFunction>
+void TOrderedHashMap<TKey, TValue, THashFunction, TEqualFunction>::clear()
+{
+    Table_.clear();
+    YT_ASSERT(List_.begin() == List_.end());
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace NYT
diff --git a/library/cpp/yt/containers/ordered_hash_map.h b/library/cpp/yt/containers/ordered_hash_map.h
new file mode 100644
index 00000000000..50b41e8c20c
--- /dev/null
+++ b/library/cpp/yt/containers/ordered_hash_map.h
@@ -0,0 +1,94 @@
+#pragma once
+
+#include <library/cpp/iterator/mapped.h>
+
+#include <util/generic/hash_table.h>
+#include <util/generic/intrlist.h>
+
+namespace NYT {
+
+////////////////////////////////////////////////////////////////////////////////
+
+//! A hash map where the iteration order is the insertion order.
+template <
+    class TKey,
+    class TValue,
+    class THashFunction = THash<TKey>,
+    class TEqualFunction = TEqualTo<TKey>
+>
+class TOrderedHashMap
+{
+private:
+    struct TItem
+        : public std::pair<const TKey, TValue>
+        , public TIntrusiveListItem<TItem>
+    {
+        using std::pair<const TKey, TValue>::pair;
+    };
+
+    struct TSelectPair
+    {
+        std::pair<const TKey, TValue>& operator()(TItem& item) const;
+        const std::pair<const TKey, TValue>& operator()(const TItem& item) const;
+    };
+
+    using TList = TIntrusiveList<TItem>;
+    using TListIterator = TList::iterator;
+    using TListConstIterator = TList::const_iterator;
+
+public:
+    using iterator = TMappedIterator<TListIterator, TSelectPair>;
+    using const_iterator = TMappedIterator<TListConstIterator, TSelectPair>;
+
+public:
+    TOrderedHashMap() = default;
+    TOrderedHashMap(const TOrderedHashMap& other);
+    TOrderedHashMap(TOrderedHashMap&& other) = default;
+
+    TOrderedHashMap& operator=(const TOrderedHashMap& other);
+    TOrderedHashMap& operator=(TOrderedHashMap&& other) = default;
+
+    template <typename... TArgs>
+    std::pair<iterator, bool> emplace(TArgs&&... args);
+
+    template <class TOtherKey>
+    iterator find(const TOtherKey& key);
+
+    template <class TOtherKey>
+    const_iterator find(const TOtherKey& key) const;
+
+    template <class TOtherKey>
+    bool contains(const TOtherKey& key) const;
+
+    template <class TOtherKey>
+    TValue& operator[](const TOtherKey& key);
+
+    template <class TOtherKey>
+    size_t erase(const TOtherKey& key);
+    void erase(iterator it);
+
+    iterator begin();
+    iterator end();
+
+    const_iterator begin() const;
+    const_iterator end() const;
+
+    size_t size() const;
+
+    void clear();
+
+private:
+    using TTable = THashTable<TItem, TKey, THashFunction, TSelect1st, TEqualFunction, std::allocator<TKey>>;
+
+private:
+    TList List_;
+    TTable Table_;
+};
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace NYT
+
+#define ORDERED_HASH_MAP_INL_H_
+#include "ordered_hash_map-inl.h"
+#undef ORDERED_HASH_MAP_INL_H_
diff --git a/library/cpp/yt/containers/unittests/ordered_hash_map_ut.cpp b/library/cpp/yt/containers/unittests/ordered_hash_map_ut.cpp
new file mode 100644
index 00000000000..aeebc5bed5a
--- /dev/null
+++ b/library/cpp/yt/containers/unittests/ordered_hash_map_ut.cpp
@@ -0,0 +1,149 @@
+#include <library/cpp/yt/containers/ordered_hash_map.h>
+
+#include <library/cpp/testing/gtest/gtest.h>
+
+#include <random>
+
+namespace NYT {
+namespace {
+
+////////////////////////////////////////////////////////////////////////////////
+
+struct TInt
+{
+    std::vector<int> Data;
+
+    explicit TInt(int value = 0)
+        : Data(1, value)
+    { }
+
+    operator int () const
+    {
+        return Data[0];
+    }
+};
+
+TInt operator""_i(unsigned long long n)
+{
+    return TInt(n);
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+TEST(TOrderedHashMapTest, Trivial)
+{
+    TOrderedHashMap<TInt, TInt> map;
+
+    {
+        auto [it, success] =  map.emplace(1_i, 10_i);
+        EXPECT_TRUE(success);
+        EXPECT_EQ(1_i, it->first);
+        EXPECT_EQ(10_i, it->second);
+    }
+
+    {
+        auto [it, success] =  map.emplace(1_i, 20_i);
+        EXPECT_FALSE(success);
+        EXPECT_EQ(1_i, it->first);
+        EXPECT_EQ(10_i, it->second);
+    }
+
+    {
+        auto it = map.find(2_i);
+        EXPECT_EQ(map.end(), it);
+    }
+
+    {
+        auto it = map.find(1_i);
+        EXPECT_EQ(map.begin(), it);
+        EXPECT_EQ(1_i, it->first);
+        EXPECT_EQ(10_i, it->second);
+    }
+
+    {
+        auto result = map.erase(1_i);
+        EXPECT_TRUE(result);
+        EXPECT_EQ(map.end(), map.find(1_i));
+    }
+
+    {
+        map.emplace(2_i, 20_i);
+        auto it = map.find(2_i);
+        EXPECT_EQ(20_i, it->second);
+        map.erase(it);
+        EXPECT_EQ(map.end(), map.find(2_i));
+    }
+}
+
+TEST(TOrderedHashMapTest, Order)
+{
+    std::vector<std::pair<TInt, TInt>> elements;
+    TOrderedHashMap<TInt, TInt> map;
+    int n = 100;
+
+    for (int i = 0; i < n; ++i) {
+        elements.emplace_back(TInt(i * 13 % (n + 1)), TInt(i * 10));
+        map.emplace(elements.back().first, elements.back().second);
+    }
+
+    auto check = [&] {
+        ASSERT_EQ(elements.size(), map.size());
+
+        auto vecIt = elements.begin();
+        auto mapIt = map.begin();
+        while (vecIt != elements.end() && mapIt != map.end()) {
+            ASSERT_EQ(vecIt->first, mapIt->first);
+            ASSERT_EQ(vecIt->second, mapIt->second);
+            ++vecIt;
+            ++mapIt;
+        }
+        ASSERT_EQ(vecIt, elements.end());
+        ASSERT_EQ(mapIt, map.end());
+    };
+
+    check();
+
+    // Now remove part of elements and repeat check.
+    std::vector<std::pair<TInt, TInt>> keptElements;
+    for (int i = 0; i < n; ++i) {
+        if (i % 3 == 1) {
+            keptElements.push_back(elements[i]);
+            continue;
+        }
+        map.erase(elements[i].first);
+    }
+    elements = std::move(keptElements);
+
+    check();
+}
+
+
+TEST(TOrderedHashMapTest, Misc)
+{
+    TOrderedHashMap<TInt, TInt> map;
+
+    // operator[].
+    map[1_i] = 10_i;
+    EXPECT_EQ(map[1_i], 10_i);
+    EXPECT_EQ(map.begin()->second, 10_i);
+    map[1_i] = 20_i;
+    EXPECT_EQ(map.begin()->second, 20_i);
+    map.begin()->second = 30_i;
+    EXPECT_EQ(map[1_i], 30_i);
+
+    // size().
+    EXPECT_EQ(map.size(), 1u);
+
+    // contains().
+    EXPECT_TRUE(map.contains(1_i));
+    EXPECT_FALSE(map.contains(2_i));
+
+    // clear().
+    map.clear();
+    EXPECT_EQ(map.size(), 0u);
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace
+} // namespace NYT
diff --git a/library/cpp/yt/containers/unittests/ya.make b/library/cpp/yt/containers/unittests/ya.make
index c46eaa9f4e7..232fa2e0e5b 100644
--- a/library/cpp/yt/containers/unittests/ya.make
+++ b/library/cpp/yt/containers/unittests/ya.make
@@ -8,6 +8,7 @@ SRCS(
     enum_indexed_array_ut.cpp
     expiring_set_ut.cpp
     non_empty_ut.cpp
+    ordered_hash_map_ut.cpp
     sharded_set_ut.cpp
 )
 
diff --git a/library/cpp/yt/error/error_attributes.h b/library/cpp/yt/error/error_attributes.h
index 0ab0687dac2..3383b0fd269 100644
--- a/library/cpp/yt/error/error_attributes.h
+++ b/library/cpp/yt/error/error_attributes.h
@@ -3,6 +3,7 @@
 #include "error_attribute.h"
 #include "mergeable_dictionary.h"
 
+#include <library/cpp/yt/containers/ordered_hash_map.h>
 #include <library/cpp/yt/misc/optional.h>
 
 namespace NYT {
@@ -74,7 +75,7 @@ public:
     void MergeFrom(const TDictionary& dict);
 
 private:
-    THashMap<TKey, TValue, THash<TStringBuf>, TEqualTo<TStringBuf>> Map_;
+    TOrderedHashMap<TKey, TValue, THash<TStringBuf>, TEqualTo<TStringBuf>> Map_;
 
     friend class TErrorOr<void>;
     TErrorAttributes() = default;
diff --git a/library/cpp/yt/error/ya.make b/library/cpp/yt/error/ya.make
index b6dcc073439..3fe4f88bed7 100644
--- a/library/cpp/yt/error/ya.make
+++ b/library/cpp/yt/error/ya.make
@@ -4,6 +4,7 @@ INCLUDE(${ARCADIA_ROOT}/library/cpp/yt/ya_cpp.make.inc)
 
 PEERDIR(
     library/cpp/yt/assert
+    library/cpp/yt/containers
     library/cpp/yt/global
     library/cpp/yt/memory
     library/cpp/yt/misc