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

Change-Id: I9636a41ad44b4218293833fd3e9456d9b07c731b

6 files changed, 524 insertions, 0 deletions

diff --git a/third_party/immer/test/flex_vector_transient/B3-BL0.cpp b/third_party/immer/test/flex_vector_transient/B3-BL0.cpp
new file mode 100644
index 000000000000..da28028c0685
--- /dev/null
+++ b/third_party/immer/test/flex_vector_transient/B3-BL0.cpp
@@ -0,0 +1,29 @@
+//
+// 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/flex_vector.hpp>
+#include <immer/flex_vector_transient.hpp>
+#include <immer/vector.hpp>
+#include <immer/vector_transient.hpp>
+
+template <typename T>
+using test_flex_vector_t =
+    immer::flex_vector<T, immer::default_memory_policy, 3u, 0u>;
+
+template <typename T>
+using test_flex_vector_transient_t =
+    typename test_flex_vector_t<T>::transient_type;
+
+template <typename T>
+using test_vector_t = immer::vector<T, immer::default_memory_policy, 3u, 0u>;
+
+#define FLEX_VECTOR_T test_flex_vector_t
+#define FLEX_VECTOR_TRANSIENT_T test_flex_vector_transient_t
+#define VECTOR_T test_vector_t
+
+#include "generic.ipp"
diff --git a/third_party/immer/test/flex_vector_transient/default.cpp b/third_party/immer/test/flex_vector_transient/default.cpp
new file mode 100644
index 000000000000..e9d843ccd226
--- /dev/null
+++ b/third_party/immer/test/flex_vector_transient/default.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/flex_vector.hpp>
+#include <immer/flex_vector_transient.hpp>
+#include <immer/vector.hpp>
+#include <immer/vector_transient.hpp>
+
+#define FLEX_VECTOR_T ::immer::flex_vector
+#define FLEX_VECTOR_TRANSIENT_T ::immer::flex_vector_transient
+#define VECTOR_T ::immer::vector
+#include "generic.ipp"
diff --git a/third_party/immer/test/flex_vector_transient/gc.cpp b/third_party/immer/test/flex_vector_transient/gc.cpp
new file mode 100644
index 000000000000..5577ee43df5f
--- /dev/null
+++ b/third_party/immer/test/flex_vector_transient/gc.cpp
@@ -0,0 +1,34 @@
+//
+// 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/flex_vector.hpp>
+#include <immer/flex_vector_transient.hpp>
+#include <immer/heap/gc_heap.hpp>
+#include <immer/refcount/no_refcount_policy.hpp>
+#include <immer/vector.hpp>
+#include <immer/vector_transient.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>
+using test_flex_vector_t = immer::flex_vector<T, gc_memory, 3u>;
+
+template <typename T>
+using test_vector_t = immer::vector<T, gc_memory, 3u>;
+
+template <typename T>
+using test_flex_vector_transient_t =
+    immer::flex_vector_transient<T, gc_memory, 3u>;
+
+#define FLEX_VECTOR_T test_flex_vector_t
+#define FLEX_VECTOR_TRANSIENT_T test_flex_vector_transient_t
+#define VECTOR_T test_vector_t
+#include "generic.ipp"
diff --git a/third_party/immer/test/flex_vector_transient/generic.ipp b/third_party/immer/test/flex_vector_transient/generic.ipp
new file mode 100644
index 000000000000..8c93cd163e69
--- /dev/null
+++ b/third_party/immer/test/flex_vector_transient/generic.ipp
@@ -0,0 +1,398 @@
+//
+// 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 "test/dada.hpp"
+#include "test/transient_tester.hpp"
+#include "test/util.hpp"
+
+#include <immer/algorithm.hpp>
+
+#include <boost/range/adaptors.hpp>
+#include <boost/range/irange.hpp>
+#include <catch.hpp>
+
+#include <algorithm>
+#include <array>
+#include <numeric>
+#include <vector>
+
+#ifndef FLEX_VECTOR_T
+#error "define the vector template to use in FLEX_VECTOR_T"
+#endif
+
+#ifndef FLEX_VECTOR_TRANSIENT_T
+#error "define the vector template to use in FLEX_VECTOR_TRANSIENT_T"
+#endif
+
+#ifndef VECTOR_T
+#error "define the vector template to use in VECTOR_T"
+#endif
+
+template <typename V = VECTOR_T<unsigned>>
+auto make_test_flex_vector(unsigned min, unsigned max)
+{
+    auto v = V{};
+    for (auto i = min; i < max; ++i)
+        v = v.push_back({i});
+    return v;
+}
+
+template <typename V = FLEX_VECTOR_T<unsigned>>
+auto make_test_flex_vector_front(unsigned min, unsigned max)
+{
+    auto v = V{};
+    for (auto i = max; i > min;)
+        v = v.push_front({--i});
+    return v;
+}
+
+TEST_CASE("from flex_vector and to flex_vector")
+{
+    constexpr auto n = 100u;
+
+    auto v = make_test_flex_vector(0, n).transient();
+    CHECK_VECTOR_EQUALS(v, boost::irange(0u, n));
+
+    auto p = v.persistent();
+    CHECK_VECTOR_EQUALS(p, boost::irange(0u, n));
+}
+
+TEST_CASE("adopt regular vector contents")
+{
+    const auto n = 666u;
+    auto v       = VECTOR_T<unsigned>{};
+    for (auto i = 0u; i < n; ++i) {
+        v       = v.push_back(i);
+        auto fv = FLEX_VECTOR_TRANSIENT_T<unsigned>{v.transient()};
+        CHECK_VECTOR_EQUALS_AUX(v, fv, [](auto&& v) { return &v; });
+    }
+}
+
+TEST_CASE("drop move")
+{
+    using vector_t = FLEX_VECTOR_T<unsigned>;
+
+    auto v = vector_t{};
+
+    auto check_move = [&](vector_t&& x) -> vector_t&& {
+        if (vector_t::memory_policy::use_transient_rvalues)
+            CHECK(&x == &v);
+        else
+            CHECK(&x != &v);
+        return std::move(x);
+    };
+
+    v = v.push_back(0).push_back(1);
+
+    auto addr_before = &v[0];
+    v                = check_move(std::move(v).drop(1));
+    auto addr_after  = &v[0];
+
+    if (vector_t::bits_leaf > 0 &&
+        vector_t::memory_policy::use_transient_rvalues)
+        CHECK(addr_before == addr_after);
+    else
+        CHECK(addr_before != addr_after);
+
+    CHECK_VECTOR_EQUALS(v, boost::irange(1u, 2u));
+}
+
+TEST_CASE("exception safety relaxed")
+{
+    using dadaist_vector_t =
+        typename dadaist_wrapper<FLEX_VECTOR_T<unsigned>>::type;
+    constexpr auto n = 667u;
+
+    SECTION("push back")
+    {
+        auto half = n / 2;
+        auto t    = as_transient_tester(
+            make_test_flex_vector_front<dadaist_vector_t>(0, half));
+        auto d = dadaism{};
+        for (auto li = half, i = half; i < n;) {
+            auto s = d.next();
+            try {
+                if (t.transient)
+                    t.vt.push_back({i});
+                else
+                    t.vp = t.vp.push_back({i});
+                ++i;
+            } catch (dada_error) {}
+            if (t.step())
+                li = i;
+            if (t.transient) {
+                CHECK_VECTOR_EQUALS(t.vt, boost::irange(0u, i));
+                CHECK_VECTOR_EQUALS(t.vp, boost::irange(0u, li));
+            } else {
+                CHECK_VECTOR_EQUALS(t.vp, boost::irange(0u, i));
+                CHECK_VECTOR_EQUALS(t.vt, boost::irange(0u, li));
+            }
+        }
+        CHECK(d.happenings > 0);
+        CHECK(t.d.happenings > 0);
+        IMMER_TRACE_E(d.happenings);
+        IMMER_TRACE_E(t.d.happenings);
+    }
+
+    SECTION("update")
+    {
+        using boost::irange;
+        using boost::join;
+
+        auto t = as_transient_tester(
+            make_test_flex_vector_front<dadaist_vector_t>(0, n));
+        auto d = dadaism{};
+        for (auto li = 0u, i = 0u; i < n;) {
+            auto s = d.next();
+            try {
+                if (t.transient) {
+                    t.vt.update(i, [](auto x) { return dada(), x + 1; });
+                } else {
+                    t.vp = t.vp.update(i, [](auto x) { return dada(), x + 1; });
+                }
+                ++i;
+            } catch (dada_error) {}
+            if (t.step())
+                li = i;
+            if (t.transient) {
+                CHECK_VECTOR_EQUALS(t.vt,
+                                    join(irange(1u, 1u + i), irange(i, n)));
+                CHECK_VECTOR_EQUALS(t.vp,
+                                    join(irange(1u, 1u + li), irange(li, n)));
+            } else {
+                CHECK_VECTOR_EQUALS(t.vp,
+                                    join(irange(1u, 1u + i), irange(i, n)));
+                CHECK_VECTOR_EQUALS(t.vt,
+                                    join(irange(1u, 1u + li), irange(li, n)));
+            }
+        }
+        CHECK(d.happenings > 0);
+        CHECK(t.d.happenings > 0);
+    }
+
+    SECTION("take")
+    {
+        auto t = as_transient_tester(
+            make_test_flex_vector_front<dadaist_vector_t>(0, n));
+        auto d      = dadaism{};
+        auto deltas = magic_rotator();
+        auto delta  = deltas.next();
+        for (auto i = n, li = i;;) {
+            auto s = d.next();
+            auto r = dadaist_vector_t{};
+            try {
+                if (t.transient)
+                    t.vt.take(i);
+                else
+                    t.vp = t.vp.take(i);
+                if (t.step())
+                    li = i;
+                delta = deltas.next();
+                if (i < delta)
+                    break;
+                i -= delta;
+            } catch (dada_error) {}
+            if (t.transient) {
+                CHECK_VECTOR_EQUALS(t.vt, boost::irange(0u, i + delta));
+                CHECK_VECTOR_EQUALS(t.vp, boost::irange(0u, li));
+            } else {
+                CHECK_VECTOR_EQUALS(t.vp, boost::irange(0u, i + delta));
+                CHECK_VECTOR_EQUALS(t.vt, boost::irange(0u, li));
+            }
+        }
+        CHECK(d.happenings > 0);
+        CHECK(t.d.happenings > 0);
+    }
+
+    SECTION("drop")
+    {
+        auto t =
+            as_transient_tester(make_test_flex_vector<dadaist_vector_t>(0, n));
+        auto d      = dadaism{};
+        auto deltas = magic_rotator();
+        auto delta  = deltas.next();
+        for (auto i = delta, li = 0u; i < n;) {
+            auto s = d.next();
+            auto r = dadaist_vector_t{};
+            try {
+                if (t.transient)
+                    t.vt.drop(delta);
+                else
+                    t.vp = t.vp.drop(delta);
+                if (t.step()) {
+                    li = i;
+                }
+                delta = deltas.next();
+                i += delta;
+            } catch (dada_error) {}
+            if (t.transient) {
+                CHECK_VECTOR_EQUALS(t.vt, boost::irange(i - delta, n));
+                CHECK_VECTOR_EQUALS(t.vp, boost::irange(li, n));
+            } else {
+                CHECK_VECTOR_EQUALS(t.vp, boost::irange(i - delta, n));
+                CHECK_VECTOR_EQUALS(t.vt, boost::irange(li, n));
+            }
+        }
+        CHECK(d.happenings > 0);
+        CHECK(t.d.happenings > 0);
+    }
+
+    SECTION("append")
+    {
+        auto make_ = [](auto i, auto delta) {
+            auto d = dadaism::disable();
+            return make_test_flex_vector<dadaist_vector_t>(i, i + delta);
+        };
+        auto t      = as_transient_tester(dadaist_vector_t{});
+        auto d      = dadaism();
+        auto deltas = magic_rotator();
+        auto delta  = deltas.next();
+        for (auto i = 0u, li = 0u; i < n;) {
+            try {
+                if (t.transient) {
+                    auto data  = make_(i, delta);
+                    auto datat = data.transient();
+                    t.vt.append(datat);
+                } else {
+                    auto data = make_(i, delta);
+                    t.vp      = t.vp + data;
+                }
+                i += delta;
+                if (t.step()) {
+                    li = i;
+                }
+                delta = deltas.next() * 3;
+            } catch (dada_error) {}
+            if (t.transient) {
+                CHECK_VECTOR_EQUALS(t.vt, boost::irange(0u, i));
+                CHECK_VECTOR_EQUALS(t.vp, boost::irange(0u, li));
+            } else {
+                CHECK_VECTOR_EQUALS(t.vp, boost::irange(0u, i));
+                CHECK_VECTOR_EQUALS(t.vt, boost::irange(0u, li));
+            }
+        }
+        CHECK(d.happenings == 0);
+        CHECK(t.d.happenings > 0);
+    }
+
+    SECTION("append mut")
+    {
+        auto make_ = [](auto i, auto delta) {
+            auto d = dadaism::disable();
+            return make_test_flex_vector<dadaist_vector_t>(i, i + delta);
+        };
+        auto t      = as_transient_tester(dadaist_vector_t{});
+        auto d      = dadaism();
+        auto deltas = magic_rotator();
+        auto delta  = deltas.next();
+        for (auto i = 0u, li = 0u; i < n;) {
+            try {
+                if (t.transient) {
+                    auto data  = make_(i, delta);
+                    auto datat = data.transient();
+                    t.vt.append(std::move(datat));
+                } else {
+                    auto data = make_(i, delta);
+                    t.vp      = t.vp + data;
+                }
+                i += delta;
+                if (t.step()) {
+                    li = i;
+                }
+                delta = deltas.next() * 3;
+            } catch (dada_error) {}
+            if (t.transient) {
+                CHECK_VECTOR_EQUALS(t.vt, boost::irange(0u, i));
+                CHECK_VECTOR_EQUALS(t.vp, boost::irange(0u, li));
+            } else {
+                CHECK_VECTOR_EQUALS(t.vp, boost::irange(0u, i));
+                CHECK_VECTOR_EQUALS(t.vt, boost::irange(0u, li));
+            }
+        }
+        CHECK(d.happenings == 0);
+        CHECK(t.d.happenings > 0);
+    }
+
+    SECTION("prepend")
+    {
+        auto make_ = [](auto i, auto delta) {
+            auto d = dadaism::disable();
+            return make_test_flex_vector<dadaist_vector_t>(i, i + delta);
+        };
+        auto t      = as_transient_tester(dadaist_vector_t{});
+        auto d      = dadaism();
+        auto deltas = magic_rotator();
+        auto delta  = deltas.next();
+        for (auto i = n, li = n; i > 0;) {
+            delta = std::min(i, delta);
+            try {
+                if (t.transient) {
+                    auto data  = make_(i - delta, delta);
+                    auto datat = data.transient();
+                    t.vt.prepend(datat);
+                } else {
+                    auto data = make_(i - delta, delta);
+                    t.vp      = data + t.vp;
+                }
+                i -= delta;
+                if (t.step()) {
+                    li = i;
+                }
+                delta = deltas.next() * 3;
+            } catch (dada_error) {}
+            if (t.transient) {
+                CHECK_VECTOR_EQUALS(t.vt, boost::irange(i, n));
+                CHECK_VECTOR_EQUALS(t.vp, boost::irange(li, n));
+            } else {
+                CHECK_VECTOR_EQUALS(t.vp, boost::irange(i, n));
+                CHECK_VECTOR_EQUALS(t.vt, boost::irange(li, n));
+            }
+        }
+        CHECK(d.happenings == 0);
+        CHECK(t.d.happenings > 0);
+    }
+
+    SECTION("prepend mut")
+    {
+        auto make_ = [](auto i, auto delta) {
+            auto d = dadaism::disable();
+            return make_test_flex_vector<dadaist_vector_t>(i, i + delta);
+        };
+        auto t      = as_transient_tester(dadaist_vector_t{});
+        auto d      = dadaism();
+        auto deltas = magic_rotator();
+        auto delta  = deltas.next();
+        for (auto i = n, li = n; i > 0;) {
+            delta = std::min(i, delta);
+            try {
+                if (t.transient) {
+                    auto data  = make_(i - delta, delta);
+                    auto datat = data.transient();
+                    t.vt.prepend(std::move(datat));
+                } else {
+                    auto data = make_(i - delta, delta);
+                    t.vp      = data + t.vp;
+                }
+                i -= delta;
+                if (t.step()) {
+                    li = i;
+                }
+                delta = deltas.next() * 3;
+            } catch (dada_error) {}
+            if (t.transient) {
+                CHECK_VECTOR_EQUALS(t.vt, boost::irange(i, n));
+                CHECK_VECTOR_EQUALS(t.vp, boost::irange(li, n));
+            } else {
+                CHECK_VECTOR_EQUALS(t.vp, boost::irange(i, n));
+                CHECK_VECTOR_EQUALS(t.vt, boost::irange(li, n));
+            }
+        }
+        CHECK(d.happenings == 0);
+        CHECK(t.d.happenings > 0);
+    }
+}
diff --git a/third_party/immer/test/flex_vector_transient/regular-default.cpp b/third_party/immer/test/flex_vector_transient/regular-default.cpp
new file mode 100644
index 000000000000..d8443afb5553
--- /dev/null
+++ b/third_party/immer/test/flex_vector_transient/regular-default.cpp
@@ -0,0 +1,15 @@
+//
+// 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/flex_vector.hpp>
+#include <immer/flex_vector_transient.hpp>
+
+#define VECTOR_T ::immer::flex_vector
+#define VECTOR_TRANSIENT_T ::immer::flex_vector_transient
+
+#include "../vector_transient/generic.ipp"
diff --git a/third_party/immer/test/flex_vector_transient/regular-gc.cpp b/third_party/immer/test/flex_vector_transient/regular-gc.cpp
new file mode 100644
index 000000000000..f1e0ec2dd518
--- /dev/null
+++ b/third_party/immer/test/flex_vector_transient/regular-gc.cpp
@@ -0,0 +1,31 @@
+//
+// 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/flex_vector.hpp>
+#include <immer/flex_vector_transient.hpp>
+#include <immer/heap/gc_heap.hpp>
+#include <immer/refcount/no_refcount_policy.hpp>
+#include <immer/vector.hpp>
+#include <immer/vector_transient.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>
+using test_flex_vector_t = immer::flex_vector<T, gc_memory, 3u>;
+
+template <typename T>
+using test_flex_vector_transient_t =
+    immer::flex_vector_transient<T, gc_memory, 3u>;
+
+#define VECTOR_T test_flex_vector_t
+#define VECTOR_TRANSIENT_T test_flex_vector_transient_t
+
+#include "../vector_transient/generic.ipp"