merge(3p/immer): Subtree merge at 'ad3e3556d' as 'third_party/immer' r/1299

Change-Id: I9636a41ad44b4218293833fd3e9456d9b07c731b

5 files changed, 529 insertions, 0 deletions

diff --git a/third_party/immer/test/set/B3.cpp b/third_party/immer/test/set/B3.cpp
new file mode 100644
index 000000000000..192b0f8e9afd
--- /dev/null
+++ b/third_party/immer/test/set/B3.cpp
@@ -0,0 +1,17 @@
+//
+// immer: immutable data structures for C++
+// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
+//
+// This software is distributed under the Boost Software License, Version 1.0.
+// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
+//
+
+#include <immer/set.hpp>
+
+template <typename T,
+          typename Hash = std::hash<T>,
+          typename Eq   = std::equal_to<T>>
+using test_set_t = immer::set<T, Hash, Eq, immer::default_memory_policy, 3u>;
+
+#define SET_T test_set_t
+#include "generic.ipp"
diff --git a/third_party/immer/test/set/B6.cpp b/third_party/immer/test/set/B6.cpp
new file mode 100644
index 000000000000..7fe3e5b7728c
--- /dev/null
+++ b/third_party/immer/test/set/B6.cpp
@@ -0,0 +1,17 @@
+//
+// immer: immutable data structures for C++
+// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
+//
+// This software is distributed under the Boost Software License, Version 1.0.
+// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
+//
+
+#include <immer/set.hpp>
+
+template <typename T,
+          typename Hash = std::hash<T>,
+          typename Eq   = std::equal_to<T>>
+using test_set_t = immer::set<T, Hash, Eq, immer::default_memory_policy, 6u>;
+
+#define SET_T test_set_t
+#include "generic.ipp"
diff --git a/third_party/immer/test/set/default.cpp b/third_party/immer/test/set/default.cpp
new file mode 100644
index 000000000000..8e6611a4ea7e
--- /dev/null
+++ b/third_party/immer/test/set/default.cpp
@@ -0,0 +1,12 @@
+//
+// immer: immutable data structures for C++
+// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
+//
+// This software is distributed under the Boost Software License, Version 1.0.
+// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
+//
+
+#include <immer/set.hpp>
+
+#define SET_T ::immer::set
+#include "generic.ipp"
diff --git a/third_party/immer/test/set/gc.cpp b/third_party/immer/test/set/gc.cpp
new file mode 100644
index 000000000000..098c8c97d087
--- /dev/null
+++ b/third_party/immer/test/set/gc.cpp
@@ -0,0 +1,24 @@
+//
+// immer: immutable data structures for C++
+// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
+//
+// This software is distributed under the Boost Software License, Version 1.0.
+// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
+//
+
+#include <immer/heap/gc_heap.hpp>
+#include <immer/refcount/no_refcount_policy.hpp>
+#include <immer/set.hpp>
+
+using gc_memory = immer::memory_policy<immer::heap_policy<immer::gc_heap>,
+                                       immer::no_refcount_policy,
+                                       immer::gc_transience_policy,
+                                       false>;
+
+template <typename T,
+          typename Hash = std::hash<T>,
+          typename Eq   = std::equal_to<T>>
+using test_set_t = immer::set<T, Hash, Eq, gc_memory, 3u>;
+
+#define SET_T test_set_t
+#include "generic.ipp"
diff --git a/third_party/immer/test/set/generic.ipp b/third_party/immer/test/set/generic.ipp
new file mode 100644
index 000000000000..8d75373787e2
--- /dev/null
+++ b/third_party/immer/test/set/generic.ipp
@@ -0,0 +1,459 @@
+//
+// immer: immutable data structures for C++
+// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
+//
+// This software is distributed under the Boost Software License, Version 1.0.
+// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
+//
+
+#ifndef SET_T
+#error "define the set template to use in SET_T"
+#include <immer/set.hpp>
+#define SET_T ::immer::set
+#endif
+
+#include "test/dada.hpp"
+#include "test/util.hpp"
+
+#include <immer/algorithm.hpp>
+
+#include <catch.hpp>
+
+#include <random>
+#include <unordered_set>
+
+template <typename T = unsigned>
+auto make_generator()
+{
+    auto engine = std::default_random_engine{42};
+    auto dist   = std::uniform_int_distribution<T>{};
+    return std::bind(dist, engine);
+}
+
+struct conflictor
+{
+    unsigned v1;
+    unsigned v2;
+
+    bool operator==(const conflictor& x) const
+    {
+        return v1 == x.v1 && v2 == x.v2;
+    }
+};
+
+struct hash_conflictor
+{
+    std::size_t operator()(const conflictor& x) const { return x.v1; }
+};
+
+auto make_values_with_collisions(unsigned n)
+{
+    auto gen   = make_generator();
+    auto vals  = std::vector<conflictor>{};
+    auto vals_ = std::unordered_set<conflictor, hash_conflictor>{};
+    generate_n(back_inserter(vals), n, [&] {
+        auto newv = conflictor{};
+        do {
+            newv = {unsigned(gen() % (n / 2)), gen()};
+        } while (!vals_.insert(newv).second);
+        return newv;
+    });
+    return vals;
+}
+
+auto make_test_set(unsigned n)
+{
+    auto s = SET_T<unsigned>{};
+    for (auto i = 0u; i < n; ++i)
+        s = s.insert(i);
+    return s;
+}
+
+auto make_test_set(const std::vector<conflictor>& vals)
+{
+    auto s = SET_T<conflictor, hash_conflictor>{};
+    for (auto&& v : vals)
+        s = s.insert(v);
+    return s;
+}
+
+template <std::size_t BufLen>
+struct unaligned_str
+{
+    std::array<char, BufLen> m_data{};
+
+    unaligned_str() = default;
+    unaligned_str(const std::string& in)
+    {
+        for (std::size_t i = 0; i < std::min(m_data.size() - 1, in.size()); i++)
+            m_data[i] = in[i];
+    }
+    unaligned_str(const char* in)
+        : unaligned_str{std::string{in}}
+    {}
+
+    std::string str() const { return m_data.data(); }
+
+    bool operator==(unaligned_str other) const
+    {
+        return m_data == other.m_data;
+    }
+
+    bool operator!=(unaligned_str other) const
+    {
+        return m_data != other.m_data;
+    }
+};
+
+namespace std {
+template <size_t BufLen>
+struct hash<unaligned_str<BufLen>>
+{
+    size_t operator()(const unaligned_str<BufLen>& str) const
+    {
+        return std::hash<std::string>{}(str.str());
+    }
+};
+} // namespace std
+
+template <size_t BufLen>
+void check_with_len()
+{
+    auto v = SET_T<unaligned_str<BufLen>>{};
+
+    for (int i = 0; i < 1; i++)
+        v = v.insert(std::to_string(i));
+
+    CHECK(v.count("0") == 1);
+}
+
+TEST_CASE("insert type with no alignment requirement")
+{
+    check_with_len<1>();
+    check_with_len<9>();
+    check_with_len<15>();
+    check_with_len<17>();
+}
+
+TEST_CASE("instantiation")
+{
+    SECTION("default")
+    {
+        auto v = SET_T<unsigned>{};
+        CHECK(v.size() == 0u);
+    }
+}
+
+TEST_CASE("basic insertion")
+{
+    auto v1 = SET_T<unsigned>{};
+    CHECK(v1.count(42) == 0);
+
+    auto v2 = v1.insert(42);
+    CHECK(v1.count(42) == 0);
+    CHECK(v2.count(42) == 1);
+
+    auto v3 = v2.insert(42);
+    CHECK(v1.count(42) == 0);
+    CHECK(v2.count(42) == 1);
+    CHECK(v3.count(42) == 1);
+}
+
+TEST_CASE("insert a lot")
+{
+    constexpr auto N = 666u;
+
+    auto gen  = make_generator();
+    auto vals = std::vector<unsigned>{};
+    generate_n(back_inserter(vals), N, gen);
+    auto s = SET_T<unsigned>{};
+
+    for (auto i = 0u; i < N; ++i) {
+        s = s.insert(vals[i]);
+        CHECK(s.size() == i + 1);
+        for (auto j : test_irange(0u, i + 1))
+            CHECK(s.count(vals[j]) == 1);
+        for (auto j : test_irange(i + 1u, N))
+            CHECK(s.count(vals[j]) == 0);
+    }
+}
+
+TEST_CASE("insert conflicts")
+{
+    constexpr auto N = 666u;
+    auto vals        = make_values_with_collisions(N);
+    auto s           = SET_T<conflictor, hash_conflictor>{};
+    for (auto i = 0u; i < N; ++i) {
+        s = s.insert(vals[i]);
+        CHECK(s.size() == i + 1);
+        for (auto j : test_irange(0u, i + 1))
+            CHECK(s.count(vals[j]) == 1);
+        for (auto j : test_irange(i + 1u, N))
+            CHECK(s.count(vals[j]) == 0);
+    }
+}
+
+TEST_CASE("erase a lot")
+{
+    constexpr auto N = 666u;
+    auto gen         = make_generator();
+    auto vals        = std::vector<unsigned>{};
+    generate_n(back_inserter(vals), N, gen);
+
+    auto s = SET_T<unsigned>{};
+    for (auto i = 0u; i < N; ++i)
+        s = s.insert(vals[i]);
+
+    for (auto i = 0u; i < N; ++i) {
+        s = s.erase(vals[i]);
+        CHECK(s.size() == N - i - 1);
+        for (auto j : test_irange(0u, i + 1))
+            CHECK(s.count(vals[j]) == 0);
+        for (auto j : test_irange(i + 1u, N))
+            CHECK(s.count(vals[j]) == 1);
+    }
+}
+
+TEST_CASE("erase conflicts")
+{
+    constexpr auto N = 666u;
+    auto vals        = make_values_with_collisions(N);
+    auto s           = SET_T<conflictor, hash_conflictor>{};
+    for (auto i = 0u; i < N; ++i)
+        s = s.insert(vals[i]);
+
+    for (auto i = 0u; i < N; ++i) {
+        s = s.erase(vals[i]);
+        CHECK(s.size() == N - i - 1);
+        for (auto j : test_irange(0u, i + 1))
+            CHECK(s.count(vals[j]) == 0);
+        for (auto j : test_irange(i + 1u, N))
+            CHECK(s.count(vals[j]) == 1);
+    }
+}
+
+TEST_CASE("accumulate")
+{
+    const auto n = 666u;
+    auto v       = make_test_set(n);
+
+    auto expected_n = [](auto n) { return n * (n - 1) / 2; };
+
+    SECTION("sum collection")
+    {
+        auto sum = immer::accumulate(v, 0u);
+        CHECK(sum == expected_n(v.size()));
+    }
+
+    SECTION("sum collisions")
+    {
+        auto vals = make_values_with_collisions(n);
+        auto s    = make_test_set(vals);
+        auto acc  = [](unsigned r, conflictor x) { return r + x.v1 + x.v2; };
+        auto sum1 = std::accumulate(vals.begin(), vals.end(), 0, acc);
+        auto sum2 = immer::accumulate(s, 0u, acc);
+        CHECK(sum1 == sum2);
+    }
+}
+
+TEST_CASE("find")
+{
+    const auto n = 666u;
+    auto v       = make_test_set(n);
+    CHECK(*v.find(0) == 0);
+    CHECK(*v.find(42) == 42);
+    CHECK(*v.find(665) == 665);
+    CHECK(v.find(666) == nullptr);
+    CHECK(v.find(1234) == nullptr);
+}
+
+TEST_CASE("iterator")
+{
+    const auto N = 666u;
+    auto v       = make_test_set(N);
+
+    SECTION("empty set")
+    {
+        auto s = SET_T<unsigned>{};
+        CHECK(s.begin() == s.end());
+    }
+
+    SECTION("works with range loop")
+    {
+        auto seen = std::unordered_set<unsigned>{};
+        for (const auto& x : v)
+            CHECK(seen.insert(x).second);
+        CHECK(seen.size() == v.size());
+    }
+
+    SECTION("works with standard algorithms")
+    {
+        auto s = std::vector<unsigned>(N);
+        std::iota(s.begin(), s.end(), 0u);
+        std::equal(v.begin(), v.end(), s.begin(), s.end());
+    }
+
+    SECTION("iterator and collisions")
+    {
+        auto vals = make_values_with_collisions(N);
+        auto s    = make_test_set(vals);
+        auto seen = std::unordered_set<conflictor, hash_conflictor>{};
+        for (const auto& x : s)
+            CHECK(seen.insert(x).second);
+        CHECK(seen.size() == s.size());
+    }
+}
+
+struct non_default
+{
+    unsigned value;
+    non_default() = delete;
+    operator unsigned() const { return value; }
+
+#if IMMER_DEBUG_PRINT
+    friend std::ostream& operator<<(std::ostream& os, non_default x)
+    {
+        os << "ND{" << x.value << "}";
+        return os;
+    }
+#endif
+};
+
+namespace std {
+
+template <>
+struct hash<non_default>
+{
+    std::size_t operator()(const non_default& x)
+    {
+        return std::hash<decltype(x.value)>{}(x.value);
+    }
+};
+
+} // namespace std
+
+TEST_CASE("non default")
+{
+    const auto n = 666u;
+
+    auto v = SET_T<non_default>{};
+    for (auto i = 0u; i < n; ++i)
+        v = v.insert({i});
+
+    CHECK(v.size() == n);
+}
+
+TEST_CASE("equals")
+{
+    const auto n = 666u;
+    auto v       = make_test_set(n);
+
+    CHECK(v == v);
+    CHECK(v != v.insert(1234));
+    CHECK(v == v.erase(1234));
+    CHECK(v == v.insert(1234).erase(1234));
+    CHECK(v == v.erase(64).insert(64));
+    CHECK(v != v.erase(1234).insert(1234));
+}
+
+TEST_CASE("equals collisions")
+{
+    const auto n = 666u;
+    auto vals    = make_values_with_collisions(n);
+    auto v       = make_test_set(vals);
+
+    CHECK(v == v);
+    CHECK(v != v.erase(vals[42]));
+    CHECK(v == v.erase(vals[42]).insert(vals[42]));
+    CHECK(v ==
+          v.erase(vals[42]).erase(vals[13]).insert(vals[42]).insert(vals[13]));
+    CHECK(v ==
+          v.erase(vals[42]).erase(vals[13]).insert(vals[13]).insert(vals[42]));
+}
+
+TEST_CASE("exception safety")
+{
+    constexpr auto n = 2666u;
+
+    using dadaist_set_t = typename dadaist_wrapper<SET_T<unsigned>>::type;
+    using dadaist_conflictor_set_t =
+        typename dadaist_wrapper<SET_T<conflictor, hash_conflictor>>::type;
+
+    SECTION("insert")
+    {
+        auto v = dadaist_set_t{};
+        auto d = dadaism{};
+        for (auto i = 0u; v.size() < n;) {
+            try {
+                auto s = d.next();
+                v      = v.insert({i});
+                ++i;
+            } catch (dada_error) {}
+            for (auto i : test_irange(0u, i))
+                CHECK(v.count({i}) == 1);
+        }
+        CHECK(d.happenings > 0);
+        IMMER_TRACE_E(d.happenings);
+    }
+
+    SECTION("insert collisions")
+    {
+        auto vals = make_values_with_collisions(n);
+        auto v    = dadaist_conflictor_set_t{};
+        auto d    = dadaism{};
+        for (auto i = 0u; v.size() < n;) {
+            try {
+                auto s = d.next();
+                v      = v.insert({vals[i]});
+                ++i;
+            } catch (dada_error) {}
+            for (auto i : test_irange(0u, i))
+                CHECK(v.count({vals[i]}) == 1);
+        }
+        CHECK(d.happenings > 0);
+        IMMER_TRACE_E(d.happenings);
+    }
+
+    SECTION("erase")
+    {
+        auto v = dadaist_set_t{};
+        auto d = dadaism{};
+        for (auto i = 0u; i < n; ++i)
+            v = v.insert({i});
+        for (auto i = 0u; v.size() > 0;) {
+            try {
+                auto s = d.next();
+                v      = v.erase({i});
+                ++i;
+            } catch (dada_error) {}
+            for (auto i : test_irange(0u, i))
+                CHECK(v.count({i}) == 0);
+            for (auto i : test_irange(i, n))
+                CHECK(v.count({i}) == 1);
+        }
+        CHECK(d.happenings > 0);
+        IMMER_TRACE_E(d.happenings);
+    }
+
+    SECTION("erase collisisions")
+    {
+        auto vals = make_values_with_collisions(n);
+        auto v    = dadaist_conflictor_set_t{};
+        auto d    = dadaism{};
+        for (auto i = 0u; i < n; ++i)
+            v = v.insert({vals[i]});
+        for (auto i = 0u; v.size() > 0;) {
+            try {
+                auto s = d.next();
+                v      = v.erase({vals[i]});
+                ++i;
+            } catch (dada_error) {}
+            for (auto i : test_irange(0u, i))
+                CHECK(v.count({vals[i]}) == 0);
+            for (auto i : test_irange(i, n))
+                CHECK(v.count({vals[i]}) == 1);
+        }
+        CHECK(d.happenings > 0);
+        IMMER_TRACE_E(d.happenings);
+    }
+}