about summary refs log tree commit diff
path: root/third_party/immer/test
diff options
context:
space:
mode:
Diffstat (limited to 'third_party/immer/test')
-rw-r--r--third_party/immer/test/CMakeLists.txt22
-rw-r--r--third_party/immer/test/array/default.cpp12
-rw-r--r--third_party/immer/test/array/gc.cpp22
-rw-r--r--third_party/immer/test/array_transient/default.cpp41
-rw-r--r--third_party/immer/test/array_transient/gc.cpp50
-rw-r--r--third_party/immer/test/atom/default.cpp12
-rw-r--r--third_party/immer/test/atom/gc.cpp20
-rw-r--r--third_party/immer/test/atom/generic.ipp53
-rw-r--r--third_party/immer/test/box/default.cpp12
-rw-r--r--third_party/immer/test/box/gc.cpp20
-rw-r--r--third_party/immer/test/box/generic.ipp58
-rw-r--r--third_party/immer/test/box/recursive.cpp108
-rw-r--r--third_party/immer/test/box/vector-of-boxes-transient.cpp36
-rw-r--r--third_party/immer/test/dada.hpp243
-rw-r--r--third_party/immer/test/detail/type_traits.cpp215
-rw-r--r--third_party/immer/test/experimental/dvektor.cpp198
-rw-r--r--third_party/immer/test/flex_vector/B3-BL0.cpp21
-rw-r--r--third_party/immer/test/flex_vector/B3-BL3.cpp21
-rw-r--r--third_party/immer/test/flex_vector/default.cpp14
-rw-r--r--third_party/immer/test/flex_vector/fuzzed-0.cpp380
-rw-r--r--third_party/immer/test/flex_vector/fuzzed-1.cpp368
-rw-r--r--third_party/immer/test/flex_vector/fuzzed-2.cpp188
-rw-r--r--third_party/immer/test/flex_vector/fuzzed-3.cpp222
-rw-r--r--third_party/immer/test/flex_vector/fuzzed-4.cpp364
-rw-r--r--third_party/immer/test/flex_vector/gc.cpp27
-rw-r--r--third_party/immer/test/flex_vector/generic.ipp599
-rw-r--r--third_party/immer/test/flex_vector/issue-45.cpp35
-rw-r--r--third_party/immer/test/flex_vector/issue-47.cpp5
-rw-r--r--third_party/immer/test/flex_vector/regular-B3-BL3.cpp16
-rw-r--r--third_party/immer/test/flex_vector/regular-default.cpp12
-rw-r--r--third_party/immer/test/flex_vector_transient/B3-BL0.cpp29
-rw-r--r--third_party/immer/test/flex_vector_transient/default.cpp17
-rw-r--r--third_party/immer/test/flex_vector_transient/gc.cpp34
-rw-r--r--third_party/immer/test/flex_vector_transient/generic.ipp398
-rw-r--r--third_party/immer/test/flex_vector_transient/regular-default.cpp15
-rw-r--r--third_party/immer/test/flex_vector_transient/regular-gc.cpp31
-rw-r--r--third_party/immer/test/map/B3.cpp18
-rw-r--r--third_party/immer/test/map/B6.cpp18
-rw-r--r--third_party/immer/test/map/default.cpp12
-rw-r--r--third_party/immer/test/map/gc.cpp25
-rw-r--r--third_party/immer/test/map/generic.ipp312
-rw-r--r--third_party/immer/test/map/issue-56.cpp42
-rw-r--r--third_party/immer/test/memory/heaps.cpp101
-rw-r--r--third_party/immer/test/memory/refcounts.cpp62
-rw-r--r--third_party/immer/test/set/B3.cpp17
-rw-r--r--third_party/immer/test/set/B6.cpp17
-rw-r--r--third_party/immer/test/set/default.cpp12
-rw-r--r--third_party/immer/test/set/gc.cpp24
-rw-r--r--third_party/immer/test/set/generic.ipp459
-rw-r--r--third_party/immer/test/transient_tester.hpp54
-rw-r--r--third_party/immer/test/util.hpp103
-rw-r--r--third_party/immer/test/vector/B3-BL0.cpp15
-rw-r--r--third_party/immer/test/vector/B3-BL2.cpp15
-rw-r--r--third_party/immer/test/vector/B3-BL3.cpp15
-rw-r--r--third_party/immer/test/vector/B3-BL4.cpp15
-rw-r--r--third_party/immer/test/vector/default.cpp12
-rw-r--r--third_party/immer/test/vector/gc.cpp22
-rw-r--r--third_party/immer/test/vector/generic.ipp488
-rw-r--r--third_party/immer/test/vector/issue-16.cpp122
-rw-r--r--third_party/immer/test/vector/issue-46.cpp39
-rw-r--r--third_party/immer/test/vector/issue-74.cpp24
-rw-r--r--third_party/immer/test/vector_transient/B3-BL0.cpp21
-rw-r--r--third_party/immer/test/vector_transient/default.cpp15
-rw-r--r--third_party/immer/test/vector_transient/gc.cpp29
-rw-r--r--third_party/immer/test/vector_transient/generic.ipp267
65 files changed, 6293 insertions, 0 deletions
diff --git a/third_party/immer/test/CMakeLists.txt b/third_party/immer/test/CMakeLists.txt
new file mode 100644
index 000000000000..faa61bbe6d9f
--- /dev/null
+++ b/third_party/immer/test/CMakeLists.txt
@@ -0,0 +1,22 @@
+
+#  Targets
+#  =======
+
+add_custom_target(tests
+  COMMENT "Build all the unit tests.")
+add_dependencies(check tests)
+
+include(CTest)
+
+file(GLOB_RECURSE immer_unit_tests "*.cpp")
+foreach(_file IN LISTS immer_unit_tests)
+  immer_target_name_for(_target _output "${_file}")
+  add_executable(${_target} EXCLUDE_FROM_ALL "${_file}")
+  set_target_properties(${_target} PROPERTIES OUTPUT_NAME ${_output})
+  add_dependencies(tests ${_target})
+  target_compile_definitions(${_target} PUBLIC
+    DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
+    CATCH_CONFIG_MAIN)
+  target_link_libraries(${_target} PUBLIC immer-dev)
+  add_test("test/${_output}" ${_output})
+endforeach()
diff --git a/third_party/immer/test/array/default.cpp b/third_party/immer/test/array/default.cpp
new file mode 100644
index 000000000000..928fffaaac5b
--- /dev/null
+++ b/third_party/immer/test/array/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/array.hpp>
+
+#define VECTOR_T ::immer::array
+#include "../vector/generic.ipp"
diff --git a/third_party/immer/test/array/gc.cpp b/third_party/immer/test/array/gc.cpp
new file mode 100644
index 000000000000..a994208bc745
--- /dev/null
+++ b/third_party/immer/test/array/gc.cpp
@@ -0,0 +1,22 @@
+//
+// 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/array.hpp>
+#include <immer/heap/gc_heap.hpp>
+#include <immer/refcount/no_refcount_policy.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_array_t = immer::array<T, gc_memory>;
+
+#define VECTOR_T test_array_t
+#include "../vector/generic.ipp"
diff --git a/third_party/immer/test/array_transient/default.cpp b/third_party/immer/test/array_transient/default.cpp
new file mode 100644
index 000000000000..aa603c7b0aab
--- /dev/null
+++ b/third_party/immer/test/array_transient/default.cpp
@@ -0,0 +1,41 @@
+//
+// 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/array.hpp>
+#include <immer/array_transient.hpp>
+
+#define VECTOR_T ::immer::array
+#define VECTOR_TRANSIENT_T ::immer::array_transient
+
+#include "../vector_transient/generic.ipp"
+
+TEST_CASE("array_transient default constructor compiles")
+{
+    immer::array_transient<int> transient;
+}
+
+TEST_CASE("array provides mutable data")
+{
+    auto arr = immer::array<int>(10, 0);
+    CHECK(arr.size() == 10);
+    auto tr = arr.transient();
+    CHECK(tr.data() == arr.data());
+
+    auto d = tr.data_mut();
+    CHECK(tr.data_mut() != arr.data());
+    CHECK(tr.data() == tr.data_mut());
+    CHECK(arr.data() != tr.data_mut());
+
+    arr = tr.persistent();
+    CHECK(arr.data() == d);
+    CHECK(arr.data() == tr.data());
+
+    CHECK(tr.data_mut() != arr.data());
+    CHECK(tr.data() == tr.data_mut());
+    CHECK(arr.data() != tr.data_mut());
+}
diff --git a/third_party/immer/test/array_transient/gc.cpp b/third_party/immer/test/array_transient/gc.cpp
new file mode 100644
index 000000000000..4b40185e94fa
--- /dev/null
+++ b/third_party/immer/test/array_transient/gc.cpp
@@ -0,0 +1,50 @@
+//
+// 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/array.hpp>
+#include <immer/array_transient.hpp>
+
+#include <immer/heap/gc_heap.hpp>
+#include <immer/refcount/no_refcount_policy.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_array_t = immer::array<T, gc_memory>;
+
+template <typename T>
+using test_array_transient_t = immer::array_transient<T, gc_memory>;
+
+#define VECTOR_T test_array_t
+#define VECTOR_TRANSIENT_T test_array_transient_t
+
+#include "../vector_transient/generic.ipp"
+
+TEST_CASE("array provides mutable data")
+{
+    auto arr = immer::array<int, gc_memory>(10, 0);
+    CHECK(arr.size() == 10);
+    auto tr = arr.transient();
+    CHECK(tr.data() == arr.data());
+
+    auto d = tr.data_mut();
+    CHECK(tr.data_mut() != arr.data());
+    CHECK(tr.data() == tr.data_mut());
+    CHECK(arr.data() != tr.data_mut());
+
+    arr = tr.persistent();
+    CHECK(arr.data() == d);
+    CHECK(arr.data() == tr.data());
+
+    CHECK(tr.data_mut() != arr.data());
+    CHECK(tr.data() == tr.data_mut());
+    CHECK(arr.data() != tr.data_mut());
+}
diff --git a/third_party/immer/test/atom/default.cpp b/third_party/immer/test/atom/default.cpp
new file mode 100644
index 000000000000..7a382c70a85d
--- /dev/null
+++ b/third_party/immer/test/atom/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/atom.hpp>
+
+#define ATOM_T ::immer::atom
+#include "generic.ipp"
diff --git a/third_party/immer/test/atom/gc.cpp b/third_party/immer/test/atom/gc.cpp
new file mode 100644
index 000000000000..f3219e81c601
--- /dev/null
+++ b/third_party/immer/test/atom/gc.cpp
@@ -0,0 +1,20 @@
+//
+// 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/atom.hpp>
+#include <immer/heap/gc_heap.hpp>
+#include <immer/refcount/no_refcount_policy.hpp>
+
+using gc_memory = immer::memory_policy<immer::heap_policy<immer::gc_heap>,
+                                       immer::no_refcount_policy>;
+
+template <typename T>
+using test_atom_t = immer::atom<T, gc_memory>;
+
+#define ATOM_T test_atom_t
+#include "generic.ipp"
diff --git a/third_party/immer/test/atom/generic.ipp b/third_party/immer/test/atom/generic.ipp
new file mode 100644
index 000000000000..21ff74d7ef69
--- /dev/null
+++ b/third_party/immer/test/atom/generic.ipp
@@ -0,0 +1,53 @@
+//
+// 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 ATOM_T
+#error "define the box template to use in ATOM_T"
+#endif
+
+#include <catch.hpp>
+
+template <typename T>
+using BOX_T = typename ATOM_T<T>::box_type;
+
+TEST_CASE("construction") { ATOM_T<int> x; }
+
+TEST_CASE("store, load, exchange")
+{
+    ATOM_T<int> x;
+    CHECK(x.load() == BOX_T<int>{0});
+    x.store(42);
+    CHECK(x.load() == BOX_T<int>{42});
+    auto old = x.exchange(12);
+    CHECK(old == 42);
+    CHECK(x.load() == BOX_T<int>{12});
+}
+
+TEST_CASE("box conversion")
+{
+    ATOM_T<int> x;
+    auto v1 = BOX_T<int>{42};
+    x       = v1;
+    auto v2 = BOX_T<int>{x};
+    CHECK(v1 == v2);
+}
+
+TEST_CASE("value conversion")
+{
+    ATOM_T<int> x;
+    x      = 42;
+    auto v = int{x};
+    CHECK(v == 42);
+}
+
+TEST_CASE("update")
+{
+    ATOM_T<int> x{42};
+    x.update([](auto x) { return x + 2; });
+    CHECK(x.load() == 44);
+}
diff --git a/third_party/immer/test/box/default.cpp b/third_party/immer/test/box/default.cpp
new file mode 100644
index 000000000000..fbd1b178df08
--- /dev/null
+++ b/third_party/immer/test/box/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/box.hpp>
+
+#define BOX_T ::immer::box
+#include "generic.ipp"
diff --git a/third_party/immer/test/box/gc.cpp b/third_party/immer/test/box/gc.cpp
new file mode 100644
index 000000000000..04e459559abc
--- /dev/null
+++ b/third_party/immer/test/box/gc.cpp
@@ -0,0 +1,20 @@
+//
+// 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/box.hpp>
+#include <immer/heap/gc_heap.hpp>
+#include <immer/refcount/no_refcount_policy.hpp>
+
+using gc_memory = immer::memory_policy<immer::heap_policy<immer::gc_heap>,
+                                       immer::no_refcount_policy>;
+
+template <typename T>
+using test_box_t = immer::box<T, gc_memory>;
+
+#define BOX_T test_box_t
+#include "generic.ipp"
diff --git a/third_party/immer/test/box/generic.ipp b/third_party/immer/test/box/generic.ipp
new file mode 100644
index 000000000000..cfb5f04ea1b9
--- /dev/null
+++ b/third_party/immer/test/box/generic.ipp
@@ -0,0 +1,58 @@
+//
+// 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 BOX_T
+#error "define the box template to use in BOX_T"
+#endif
+
+#include <catch.hpp>
+
+TEST_CASE("construction and copy")
+{
+    auto x = BOX_T<int>{};
+    CHECK(x == 0);
+
+    auto y = x;
+    CHECK(&x.get() == &y.get());
+
+    auto z = std::move(x);
+    CHECK(&z.get() == &y.get());
+}
+
+TEST_CASE("equality")
+{
+    auto x = BOX_T<int>{};
+    auto y = x;
+    CHECK(x == 0.0f);
+    CHECK(x == y);
+    CHECK(x == BOX_T<int>{});
+    CHECK(x != BOX_T<int>{42});
+}
+
+TEST_CASE("update")
+{
+    auto x = BOX_T<int>{};
+    auto y = x.update([](auto v) { return v + 1; });
+    CHECK(x == 0);
+    CHECK(y == 1);
+}
+
+TEST_CASE("update move")
+{
+    auto x    = BOX_T<int>{};
+    auto addr = &x.get();
+    auto y    = std::move(x).update(
+        [](auto&& v) { return std::forward<decltype(v)>(v) + 1; });
+
+    CHECK(y == 1);
+    if (std::is_empty<typename BOX_T<int>::memory_policy::refcount>::value) {
+        CHECK(&y.get() != addr);
+    } else {
+        CHECK(&y.get() == addr);
+    }
+}
diff --git a/third_party/immer/test/box/recursive.cpp b/third_party/immer/test/box/recursive.cpp
new file mode 100644
index 000000000000..4c8fce07dea2
--- /dev/null
+++ b/third_party/immer/test/box/recursive.cpp
@@ -0,0 +1,108 @@
+//
+// 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/algorithm.hpp>
+#include <immer/box.hpp>
+#include <immer/flex_vector.hpp>
+#include <immer/map.hpp>
+#include <immer/set.hpp>
+#include <immer/vector.hpp>
+
+#include <catch.hpp>
+
+struct rec_vec
+{
+    int data;
+    immer::vector<immer::box<rec_vec>> children;
+};
+
+TEST_CASE("recursive vector")
+{
+    auto v1 = rec_vec{42,
+                      {rec_vec{12, {}},
+                       rec_vec{13, {rec_vec{5, {}}, rec_vec{7, {}}}},
+                       rec_vec{15, {}}}};
+    CHECK(v1.data == 42);
+    CHECK(v1.children[0]->data == 12);
+    CHECK(v1.children[1]->children[0]->data == 5);
+}
+
+struct rec_fvec
+{
+    int data;
+    immer::flex_vector<immer::box<rec_fvec>> children;
+};
+
+TEST_CASE("recursive flex_vector")
+{
+    auto v1 = rec_fvec{42,
+                       {rec_fvec{12, {}},
+                        rec_fvec{13, {rec_fvec{5, {}}, rec_fvec{7, {}}}},
+                        rec_fvec{15, {}}}};
+    CHECK(v1.data == 42);
+    CHECK(v1.children[0]->data == 12);
+    CHECK(v1.children[1]->children[0]->data == 5);
+}
+
+struct rec_map
+{
+    int data;
+    immer::map<std::string, immer::box<rec_map>> children;
+};
+
+TEST_CASE("recursive map")
+{
+    auto v1 = rec_map{42, {}};
+    auto v2 = rec_map{43, v1.children.set("hello", rec_map{12, {}})};
+    auto v3 = rec_map{44, v2.children.set("world", rec_map{13, {}})};
+
+    CHECK(v3.data == 44);
+    CHECK(v3.children["hello"]->data == 12);
+    CHECK(v3.children["world"]->data == 13);
+}
+
+struct rec_set
+{
+    int data;
+    immer::set<immer::box<rec_set>> children;
+
+    bool operator==(const rec_set& other) const
+    {
+        return data == other.data && children == other.children;
+    }
+    bool operator!=(const rec_set& other) const { return !(*this == other); }
+};
+
+namespace std {
+
+template <>
+struct hash<rec_set>
+{
+    auto operator()(const rec_set& s)
+    {
+        return std::hash<decltype(s.data)>{}(s.data) ^
+               immer::accumulate(
+                   s.children, std::size_t{}, [](auto ac, auto v) {
+                       return std::hash<decltype(v)>{}(v);
+                   });
+    }
+};
+
+} // namespace std
+
+TEST_CASE("recursive set")
+{
+    auto v1 = rec_set{42, {}};
+    auto v2 = rec_set{43, v1.children.insert(rec_set{12, {}})};
+    auto v3 = rec_set{44, v2.children.insert(rec_set{13, {}})};
+
+    CHECK(v3.data == 44);
+    CHECK(v3.children.count(rec_set{12, {}}) == 1);
+    CHECK(v3.children.count(rec_set{13, {}}) == 1);
+    CHECK(v3.children.count(rec_set{14, {}}) == 0);
+}
diff --git a/third_party/immer/test/box/vector-of-boxes-transient.cpp b/third_party/immer/test/box/vector-of-boxes-transient.cpp
new file mode 100644
index 000000000000..623c8ba37d32
--- /dev/null
+++ b/third_party/immer/test/box/vector-of-boxes-transient.cpp
@@ -0,0 +1,36 @@
+//
+// 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/box.hpp>
+#include <immer/vector.hpp>
+#include <immer/vector_transient.hpp>
+
+#include <catch.hpp>
+
+TEST_CASE("issue-33")
+{
+    using Element = immer::box<std::string>;
+    auto vect     = immer::vector<Element>{};
+
+    // this one works fine
+    for (auto i = 0; i < 100; ++i) {
+        vect = vect.push_back(Element("x"));
+    }
+
+    // this one doesn't compile
+    auto t = vect.transient();
+
+    for (auto i = 0; i < 100; ++i) {
+        t.push_back(Element("x"));
+    }
+
+    vect = t.persistent();
+
+    CHECK(*vect[0] == "x");
+    CHECK(*vect[99] == "x");
+}
diff --git a/third_party/immer/test/dada.hpp b/third_party/immer/test/dada.hpp
new file mode 100644
index 000000000000..1465bf7bf52d
--- /dev/null
+++ b/third_party/immer/test/dada.hpp
@@ -0,0 +1,243 @@
+//
+// 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
+//
+
+#pragma once
+
+#include <array>
+#include <cstddef>
+#include <utility>
+
+#include <immer/detail/hamts/bits.hpp>
+#include <immer/detail/rbts/bits.hpp>
+
+namespace {
+
+template <typename Iterator>
+struct rotator
+{
+    using value_type = typename std::iterator_traits<Iterator>::value_type;
+
+    Iterator first;
+    Iterator last;
+    Iterator curr;
+
+    void init(Iterator f, Iterator l)
+    {
+        first = f;
+        last  = l;
+        curr  = f;
+    }
+
+    value_type next()
+    {
+        if (curr == last)
+            curr = first;
+        return *curr++;
+    }
+};
+
+template <typename Range>
+struct range_rotator : rotator<typename Range::iterator>
+{
+    using base_t = rotator<typename Range::iterator>;
+
+    Range range;
+
+    range_rotator(Range r)
+        : range{std::move(r)}
+    {
+        base_t::init(range.begin(), range.end());
+    }
+};
+
+template <typename Range>
+auto make_rotator(Range r) -> range_rotator<Range>
+{
+    return {r};
+}
+
+inline auto magic_rotator()
+{
+    return make_rotator(std::array<unsigned, 15>{
+        {7, 11, 2, 3, 5, 7, 11, 13, 17, 19, 23, 5, 29, 31, 37}});
+}
+
+struct dada_error
+{};
+
+struct dadaism;
+static dadaism* g_dadaism = nullptr;
+
+struct dadaism
+{
+    using rotator_t = decltype(magic_rotator());
+
+    rotator_t magic = magic_rotator();
+
+    unsigned step       = magic.next();
+    unsigned count      = 0;
+    unsigned happenings = 0;
+    unsigned last       = 0;
+    bool toggle         = false;
+
+    struct scope
+    {
+        bool moved     = false;
+        dadaism* save_ = g_dadaism;
+        scope(scope&& s)
+        {
+            save_   = s.save_;
+            s.moved = true;
+        }
+        scope(dadaism* self) { g_dadaism = self; }
+        ~scope()
+        {
+            if (!moved)
+                g_dadaism = save_;
+        }
+    };
+
+    static scope disable() { return {nullptr}; }
+
+    scope next()
+    {
+        toggle = last == happenings;
+        last   = happenings;
+        step   = toggle ? step : magic.next();
+        return {this};
+    }
+
+    void dada()
+    {
+        if (toggle && ++count % step == 0) {
+            ++happenings;
+            throw dada_error{};
+        }
+    }
+};
+
+inline void dada()
+{
+    if (g_dadaism)
+        g_dadaism->dada();
+}
+
+inline bool soft_dada()
+{
+    try {
+        dada();
+        return false;
+    } catch (dada_error) {
+        return true;
+    }
+}
+
+template <typename Heap>
+struct dadaist_heap : Heap
+{
+    template <typename... Tags>
+    static auto allocate(std::size_t s, Tags... tags)
+    {
+        dada();
+        return Heap::allocate(s, tags...);
+    }
+};
+
+template <typename MP>
+struct dadaist_memory_policy : MP
+{
+    struct heap
+    {
+        using type = dadaist_heap<typename MP::heap::type>;
+
+        template <std::size_t Size>
+        struct optimized
+        {
+            using base = typename MP::heap::template optimized<Size>::type;
+            using type = dadaist_heap<base>;
+        };
+    };
+};
+
+struct tristan_tzara
+{
+    tristan_tzara() { dada(); }
+    tristan_tzara(const tristan_tzara&) { dada(); }
+    tristan_tzara(tristan_tzara&&) { dada(); }
+    tristan_tzara& operator=(const tristan_tzara&)
+    {
+        dada();
+        return *this;
+    }
+    tristan_tzara& operator=(tristan_tzara&&)
+    {
+        dada();
+        return *this;
+    }
+};
+
+template <typename T>
+struct dadaist : tristan_tzara
+{
+    T value;
+
+    dadaist()
+        : value{}
+    {}
+    dadaist(T v)
+        : value{std::move(v)}
+    {}
+    operator T() const { return value; }
+};
+
+template <typename T>
+struct dadaist_wrapper;
+
+using rbits_t = immer::detail::rbts::bits_t;
+using hbits_t = immer::detail::rbts::bits_t;
+
+template <template <class, class, rbits_t, rbits_t> class V,
+          typename T,
+          typename MP,
+          rbits_t B,
+          rbits_t BL>
+struct dadaist_wrapper<V<T, MP, B, BL>>
+{
+    using type = V<dadaist<T>, dadaist_memory_policy<MP>, B, BL>;
+};
+
+template <template <class, class> class V, typename T, typename MP>
+struct dadaist_wrapper<V<T, MP>>
+{
+    using type = V<dadaist<T>, dadaist_memory_policy<MP>>;
+};
+
+template <template <class, class, class, class, hbits_t> class V,
+          typename T,
+          typename E,
+          typename H,
+          typename MP,
+          hbits_t B>
+struct dadaist_wrapper<V<T, H, E, MP, B>>
+{
+    using type = V<dadaist<T>, H, E, dadaist_memory_policy<MP>, B>;
+};
+
+template <template <class, class, class, class, class, hbits_t> class V,
+          typename K,
+          typename T,
+          typename E,
+          typename H,
+          typename MP,
+          hbits_t B>
+struct dadaist_wrapper<V<K, T, H, E, MP, B>>
+{
+    using type = V<K, dadaist<T>, H, E, dadaist_memory_policy<MP>, B>;
+};
+
+} // anonymous namespace
diff --git a/third_party/immer/test/detail/type_traits.cpp b/third_party/immer/test/detail/type_traits.cpp
new file mode 100644
index 000000000000..8809418ccea6
--- /dev/null
+++ b/third_party/immer/test/detail/type_traits.cpp
@@ -0,0 +1,215 @@
+//
+// 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 <catch.hpp>
+#include <forward_list>
+#include <immer/detail/type_traits.hpp>
+#include <list>
+#include <vector>
+
+struct string_sentinel
+{};
+bool operator==(const char* i, string_sentinel);
+bool operator!=(const char* i, string_sentinel);
+
+TEST_CASE("compatible_sentinel_v")
+{
+    SECTION("iterator pairs")
+    {
+        using Iter = std::vector<int>::iterator;
+        static_assert(immer::detail::compatible_sentinel_v<Iter, Iter>, "");
+    }
+
+    SECTION("pointer pairs")
+    {
+        using Iter = char*;
+        static_assert(immer::detail::compatible_sentinel_v<Iter, Iter>, "");
+    }
+
+    SECTION("iterator/sentinel pair")
+    {
+        using Iter = char*;
+        using Sent = string_sentinel;
+        static_assert(immer::detail::compatible_sentinel_v<Iter, Sent>, "");
+    }
+
+    SECTION("incompatible pair")
+    {
+        using Iter1 = std::vector<int>::iterator;
+        using Iter2 = std::list<double>::iterator;
+        static_assert(not immer::detail::compatible_sentinel_v<Iter1, Iter2>,
+                      "");
+    }
+}
+
+TEST_CASE("equality comparable")
+{
+    SECTION("iterator pairs")
+    {
+        using Iter = std::vector<int>::iterator;
+        static_assert(immer::detail::is_equality_comparable_v<Iter, Iter>, "");
+    }
+
+    SECTION("pointer pairs")
+    {
+        using Iter = char*;
+        static_assert(immer::detail::is_equality_comparable_v<Iter, Iter>, "");
+    }
+
+    SECTION("iterator/sentinel pair")
+    {
+        using Iter = char*;
+        using Sent = string_sentinel;
+        static_assert(immer::detail::is_equality_comparable_v<Iter, Sent>, "");
+    }
+
+    SECTION("not equality comparable")
+    {
+        static_assert(
+            not immer::detail::is_equality_comparable_v<std::string, double>,
+            "");
+    }
+}
+
+TEST_CASE("inequality comparable")
+{
+    SECTION("iterator pairs")
+    {
+        using Iter = std::vector<int>::iterator;
+        static_assert(immer::detail::is_inequality_comparable_v<Iter, Iter>,
+                      "");
+    }
+
+    SECTION("pointer pairs")
+    {
+        using Iter = char*;
+        static_assert(immer::detail::is_inequality_comparable_v<Iter, Iter>,
+                      "");
+    }
+
+    SECTION("iterator/sentinel pair")
+    {
+        using Iter = char*;
+        using Sent = string_sentinel;
+        static_assert(immer::detail::is_inequality_comparable_v<Iter, Sent>,
+                      "");
+    }
+
+    SECTION("not inequality comparable")
+    {
+        static_assert(
+            not immer::detail::is_inequality_comparable_v<std::string, double>,
+            "");
+    }
+}
+
+TEST_CASE("is dereferenceable")
+{
+    SECTION("iterator")
+    {
+        using Iter = std::vector<int>::iterator;
+        static_assert(immer::detail::is_dereferenceable_v<Iter>, "");
+    }
+
+    SECTION("pointer")
+    {
+        using Iter = char*;
+        static_assert(immer::detail::is_dereferenceable_v<Iter>, "");
+    }
+
+    SECTION("not dereferenceable")
+    {
+        static_assert(not immer::detail::is_dereferenceable_v<int>, "");
+    }
+}
+
+TEST_CASE("is forward iterator")
+{
+    SECTION("random access iterator")
+    {
+        using Iter = std::vector<int>::iterator;
+        static_assert(immer::detail::is_forward_iterator_v<Iter>, "");
+    }
+
+    SECTION("bidirectional iterator")
+    {
+        using Iter = std::list<int>::iterator;
+        static_assert(immer::detail::is_forward_iterator_v<Iter>, "");
+    }
+
+    SECTION("forward iterator")
+    {
+        using Iter = std::forward_list<int>::iterator;
+        static_assert(immer::detail::is_forward_iterator_v<Iter>, "");
+    }
+
+    SECTION("input iterator")
+    {
+        using Iter = std::istream_iterator<double>;
+        static_assert(not immer::detail::is_forward_iterator_v<Iter>, "");
+    }
+
+    SECTION("output iterator")
+    {
+        using Iter = std::ostream_iterator<double>;
+        static_assert(not immer::detail::is_forward_iterator_v<Iter>, "");
+    }
+
+    SECTION("pointer")
+    {
+        using Iter = char*;
+        static_assert(immer::detail::is_forward_iterator_v<Iter>, "");
+    }
+}
+
+TEST_CASE("is iterator")
+{
+    SECTION("iterator")
+    {
+        using Iter = std::vector<int>::iterator;
+        static_assert(immer::detail::is_iterator_v<Iter>, "");
+    }
+
+    SECTION("pointer")
+    {
+        using Iter = char*;
+        static_assert(immer::detail::is_iterator_v<Iter>, "");
+    }
+
+    SECTION("not iterator")
+    {
+        static_assert(not immer::detail::is_iterator_v<int>, "");
+    }
+}
+
+TEST_CASE("provides preincrement")
+{
+    SECTION("iterator")
+    {
+        using Iter = std::vector<int>::iterator;
+        static_assert(immer::detail::is_preincrementable_v<Iter>, "");
+    }
+
+    SECTION("pointer")
+    {
+        using Iter = char*;
+        static_assert(immer::detail::is_preincrementable_v<Iter>, "");
+    }
+
+    SECTION("does not provide preincrement")
+    {
+        struct type
+        {};
+        static_assert(not immer::detail::is_preincrementable_v<type>, "");
+    }
+}
+
+TEST_CASE("void_t")
+{
+    static_assert(std::is_same<void, immer::detail::void_t<int>>::value, "");
+}
diff --git a/third_party/immer/test/experimental/dvektor.cpp b/third_party/immer/test/experimental/dvektor.cpp
new file mode 100644
index 000000000000..437384a72771
--- /dev/null
+++ b/third_party/immer/test/experimental/dvektor.cpp
@@ -0,0 +1,198 @@
+//
+// 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/experimental/dvektor.hpp>
+
+#include <boost/range/adaptors.hpp>
+
+#include <algorithm>
+#include <numeric>
+#include <vector>
+#include <iostream>
+
+#include <doctest.h>
+
+using namespace immer;
+
+TEST_CASE("instantiation")
+{
+    auto v = dvektor<int>{};
+    CHECK(v.size() == 0u);
+}
+
+TEST_CASE("push back one element")
+{
+    SUBCASE("one element")
+    {
+        const auto v1 = dvektor<int>{};
+        auto v2       = v1.push_back(42);
+        CHECK(v1.size() == 0u);
+        CHECK(v2.size() == 1u);
+        CHECK(v2[0] == 42);
+    }
+
+    SUBCASE("many elements")
+    {
+        const auto n = 666u;
+        auto v       = dvektor<unsigned>{};
+        for (auto i = 0u; i < n; ++i) {
+            v = v.push_back(i * 10);
+            CHECK(v.size() == i + 1);
+            for (auto j = 0u; j < v.size(); ++j)
+                CHECK(i + v[j] == i + j * 10);
+        }
+    }
+}
+
+TEST_CASE("update")
+{
+    const auto n = 42u;
+    auto v       = dvektor<unsigned>{};
+    for (auto i = 0u; i < n; ++i)
+        v = v.push_back(i);
+
+    SUBCASE("assoc")
+    {
+        const auto u = v.assoc(3u, 13u);
+        CHECK(u.size() == v.size());
+        CHECK(u[2u] == 2u);
+        CHECK(u[3u] == 13u);
+        CHECK(u[4u] == 4u);
+        CHECK(u[40u] == 40u);
+        CHECK(v[3u] == 3u);
+    }
+
+    SUBCASE("assoc further")
+    {
+        for (auto i = n; i < 666; ++i)
+            v = v.push_back(i);
+
+        auto u = v.assoc(3u, 13u);
+        u      = u.assoc(200u, 7u);
+        CHECK(u.size() == v.size());
+
+        CHECK(u[2u] == 2u);
+        CHECK(u[4u] == 4u);
+        CHECK(u[40u] == 40u);
+        CHECK(u[600u] == 600u);
+
+        CHECK(u[3u] == 13u);
+        CHECK(u[200u] == 7u);
+
+        CHECK(v[3u] == 3u);
+        CHECK(v[200u] == 200u);
+    }
+
+    SUBCASE("assoc further more")
+    {
+        auto v = immer::dvektor<unsigned, 4>{};
+
+        for (auto i = n; i < 1000u; ++i)
+            v = v.push_back(i);
+
+        for (auto i = 0u; i < v.size(); ++i) {
+            v = v.assoc(i, i + 1);
+            CHECK(v[i] == i + 1);
+        }
+    }
+
+    SUBCASE("update")
+    {
+        const auto u = v.update(10u, [](auto x) { return x + 10; });
+        CHECK(u.size() == v.size());
+        CHECK(u[10u] == 20u);
+        CHECK(v[40u] == 40u);
+
+        const auto w = v.update(40u, [](auto x) { return x - 10; });
+        CHECK(w.size() == v.size());
+        CHECK(w[40u] == 30u);
+        CHECK(v[40u] == 40u);
+    }
+}
+
+#if IMMER_SLOW_TESTS
+TEST_CASE("big")
+{
+    const auto n = 1000000;
+    auto v       = dvektor<unsigned>{};
+    for (auto i = 0u; i < n; ++i)
+        v = v.push_back(i);
+
+    SUBCASE("read")
+    {
+        for (auto i = 0u; i < n; ++i)
+            CHECK(v[i] == i);
+    }
+
+    SUBCASE("assoc")
+    {
+        for (auto i = 0u; i < n; ++i) {
+            v = v.assoc(i, i + 1);
+            CHECK(v[i] == i + 1);
+        }
+    }
+}
+#endif // IMMER_SLOW_TESTS
+
+TEST_CASE("iterator")
+{
+    const auto n = 666u;
+    auto v       = dvektor<unsigned>{};
+    for (auto i = 0u; i < n; ++i)
+        v = v.push_back(i);
+
+    SUBCASE("works with range loop")
+    {
+        auto i = 0u;
+        for (const auto& x : v)
+            CHECK(x == i++);
+        CHECK(i == v.size());
+    }
+
+    SUBCASE("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());
+    }
+
+    SUBCASE("can go back from end") { CHECK(n - 1 == *--v.end()); }
+
+    SUBCASE("works with reversed range adaptor")
+    {
+        auto r = v | boost::adaptors::reversed;
+        auto i = n;
+        for (const auto& x : r)
+            CHECK(x == --i);
+    }
+
+    SUBCASE("works with strided range adaptor")
+    {
+        auto r = v | boost::adaptors::strided(5);
+        auto i = 0u;
+        for (const auto& x : r)
+            CHECK(x == 5 * i++);
+    }
+
+    SUBCASE("works reversed")
+    {
+        auto i = n;
+        for (auto iter = v.rbegin(), last = v.rend(); iter != last; ++iter)
+            CHECK(*iter == --i);
+    }
+
+    SUBCASE("advance and distance")
+    {
+        auto i1 = v.begin();
+        auto i2 = i1 + 100;
+        CHECK(*i2 == 100u);
+        CHECK(i2 - i1 == 100);
+        CHECK(*(i2 - 50) == 50u);
+        CHECK((i2 - 30) - i2 == -30);
+    }
+}
diff --git a/third_party/immer/test/flex_vector/B3-BL0.cpp b/third_party/immer/test/flex_vector/B3-BL0.cpp
new file mode 100644
index 000000000000..83af21d688fc
--- /dev/null
+++ b/third_party/immer/test/flex_vector/B3-BL0.cpp
@@ -0,0 +1,21 @@
+//
+// 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/vector.hpp>
+
+template <typename T>
+using test_flex_vector_t =
+    immer::flex_vector<T, immer::default_memory_policy, 3u, 0u>;
+
+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 VECTOR_T test_vector_t
+#include "generic.ipp"
diff --git a/third_party/immer/test/flex_vector/B3-BL3.cpp b/third_party/immer/test/flex_vector/B3-BL3.cpp
new file mode 100644
index 000000000000..e44f7e2bfaba
--- /dev/null
+++ b/third_party/immer/test/flex_vector/B3-BL3.cpp
@@ -0,0 +1,21 @@
+//
+// 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/vector.hpp>
+
+template <typename T>
+using test_flex_vector_t =
+    immer::flex_vector<T, immer::default_memory_policy, 3u, 3u>;
+
+template <typename T>
+using test_vector_t = immer::vector<T, immer::default_memory_policy, 3u, 3u>;
+
+#define FLEX_VECTOR_T test_flex_vector_t
+#define VECTOR_T test_vector_t
+#include "generic.ipp"
diff --git a/third_party/immer/test/flex_vector/default.cpp b/third_party/immer/test/flex_vector/default.cpp
new file mode 100644
index 000000000000..7258cc07728d
--- /dev/null
+++ b/third_party/immer/test/flex_vector/default.cpp
@@ -0,0 +1,14 @@
+//
+// 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/vector.hpp>
+
+#define FLEX_VECTOR_T ::immer::flex_vector
+#define VECTOR_T ::immer::vector
+#include "generic.ipp"
diff --git a/third_party/immer/test/flex_vector/fuzzed-0.cpp b/third_party/immer/test/flex_vector/fuzzed-0.cpp
new file mode 100644
index 000000000000..063ad133a09d
--- /dev/null
+++ b/third_party/immer/test/flex_vector/fuzzed-0.cpp
@@ -0,0 +1,380 @@
+//
+// 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 "extra/fuzzer/fuzzer_input.hpp"
+#include <array>
+#include <catch.hpp>
+#include <immer/flex_vector.hpp>
+#include <iostream>
+
+#define IMMER_FUZZED_TRACE_ENABLE 0
+
+#if IMMER_FUZZED_TRACE_ENABLE
+#define IMMER_FUZZED_TRACE(...) std::cout << __VA_ARGS__ << std::endl;
+#else
+#define IMMER_FUZZED_TRACE(...)
+#endif
+
+namespace {
+
+template <std::size_t VarCount = 8, unsigned Bits = 3>
+int run_input(const std::uint8_t* data, std::size_t size)
+{
+    using vector_t =
+        immer::flex_vector<int, immer::default_memory_policy, Bits, Bits>;
+    using size_t = std::uint8_t;
+
+    auto vars = std::array<vector_t, VarCount>{};
+
+#if IMMER_FUZZED_TRACE_ENABLE
+    for (auto i = 0u; i < VarCount; ++i)
+        std::cout << "auto var" << i << " = vector_t{};" << std::endl;
+#endif
+
+    auto is_valid_var   = [&](auto idx) { return idx >= 0 && idx < VarCount; };
+    auto is_valid_index = [](auto& v) {
+        return [&](auto idx) { return idx >= 0 && idx < v.size(); };
+    };
+    auto is_valid_size = [](auto& v) {
+        return [&](auto idx) { return idx >= 0 && idx <= v.size(); };
+    };
+
+    return fuzzer_input{data, size}.run([&](auto& in) {
+        enum ops
+        {
+            op_push_back,
+            op_update,
+            op_take,
+            op_drop,
+            op_concat,
+        };
+        auto src = read<std::uint8_t>(in, is_valid_var);
+        auto dst = read<std::uint8_t>(in, is_valid_var);
+        switch (read<char>(in)) {
+        case op_push_back:
+            IMMER_FUZZED_TRACE("var" << +dst << " = var" << +src
+                                     << ".push_back(42);");
+            vars[dst] = vars[src].push_back(42);
+            break;
+        case op_update: {
+            auto idx = read<size_t>(in, is_valid_index(vars[src]));
+            IMMER_FUZZED_TRACE("var" << +dst << " = var" << +src << ".update("
+                                     << +idx
+                                     << ", [] (auto x) { return x + 1; });");
+            vars[dst] = vars[src].update(idx, [](auto x) { return x + 1; });
+            break;
+        }
+        case op_take: {
+            auto idx = read<size_t>(in, is_valid_size(vars[src]));
+            IMMER_FUZZED_TRACE("var" << +dst << " = var" << +src << ".take("
+                                     << +idx << ");");
+            vars[dst] = vars[src].take(idx);
+            break;
+        }
+        case op_drop: {
+            auto idx = read<size_t>(in, is_valid_size(vars[src]));
+            IMMER_FUZZED_TRACE("var" << +dst << " = var" << +src << ".take("
+                                     << +idx << ");");
+            vars[dst] = vars[src].drop(idx);
+            break;
+        }
+        case op_concat: {
+            auto src2 = read<std::uint8_t>(in, is_valid_var);
+            IMMER_FUZZED_TRACE("var" << +dst << " = var" << +src << " + var"
+                                     << +src2 << ";");
+            vars[dst] = vars[src] + vars[src2];
+            break;
+        }
+        default:
+            break;
+        };
+        return true;
+    });
+}
+
+} // anonymous namespace
+
+TEST_CASE("bug: concatenate too big vectors")
+{
+    // The problem here was that since we were using 32 bit sizes,
+    // concatenating big flex_vectors can overflow the sizes.  Let's
+    // just use std::size_t like normal people.
+    //
+    // Still, the problem could re-ocurr with longer inputs.  For this
+    // reason later fuzzing efforts do check that concatenation is
+    // valid for the given vector sizes.  Similar assertions are put
+    // in the code too.
+    SECTION("simplified example")
+    {
+        using vector_t =
+            immer::flex_vector<int, immer::default_memory_policy, 3, 3>;
+        auto var0 = vector_t{};
+        auto var1 = vector_t{};
+        auto var2 = vector_t{};
+        auto var4 = vector_t{};
+        var1      = var1.push_back(42);
+        var0      = var0.push_back(42);
+        var0      = var0.push_back(42);
+        var0      = var2.push_back(42);
+        var0      = var0.push_back(42);
+        var2      = var0;
+        var0      = var0.push_back(42);
+        var0      = var0.push_back(42);
+        var4      = var4.push_back(42);
+        var0      = var0.push_back(42);
+        var0      = var0.push_back(42);
+        var0      = var0 + var0;
+        var0      = var0.push_back(42);
+        var0      = var0.push_back(42);
+        var2      = var0.push_back(42);
+        var0      = var0 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var0      = var0.push_back(42);
+        var0      = var0.push_back(42);
+        var1      = var2 + var4;
+        var4      = var4 + var4;
+        var0      = var1.push_back(42);
+        var0      = var0.push_back(42);
+        var0      = var0 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4.push_back(42);
+    }
+
+#if __GNUC__ != 9
+    // Assertion `!p->relaxed()' failed
+    SECTION("")
+    {
+        constexpr std::uint8_t input[] = {
+            0x1,  0x1, 0x0, 0x0, 0x0,  0x0, 0x0, 0x0, 0x0, 0x39, 0x6a, 0x76,
+            0xb9, 0x2, 0x0, 0x0, 0x0,  0x0, 0x0, 0x0, 0x2, 0x1,  0x0,  0x0,
+            0x2a, 0x0, 0x0, 0x0, 0x0,  0x0, 0x4, 0x4, 0x0, 0x0,  0x0,  0x0,
+            0x0,  0x0, 0x0, 0x0, 0x0,  0x4, 0x0, 0x0, 0x0, 0x0,  0x0,  0x0,
+            0x0,  0x0, 0x2, 0x0, 0x0,  0x0, 0x4, 0x4, 0x4, 0x4,  0x4,  0x4,
+            0x4,  0x4, 0x4, 0x4, 0x4,  0x4, 0x4, 0x4, 0x0, 0x0,  0x0,  0x0,
+            0x0,  0x0, 0x2, 0x1, 0x4,  0x4, 0x4, 0x4, 0x4, 0x4,  0x1,  0x0,
+            0x0,  0x0, 0x0, 0x0, 0x0,  0x0, 0x4, 0x4, 0x4, 0x4,  0x4,  0x4,
+            0x4,  0x4, 0x4, 0x4, 0x4,  0x4, 0x4, 0x4, 0x4, 0x4,  0x4,  0x4,
+            0x4,  0x4, 0x4, 0x4, 0x4,  0x4, 0x4, 0x4, 0x4, 0x4,  0x4,  0x4,
+            0x4,  0x4, 0x4, 0x4, 0x4,  0x4, 0x4, 0x4, 0x4, 0x4,  0x4,  0x4,
+            0x4,  0x4, 0x4, 0x4, 0x4,  0x4, 0x4, 0x4, 0x4, 0x4,  0x4,  0x4,
+            0x4,  0x4, 0x4, 0x4, 0x4,  0x4, 0x4, 0x4, 0x4, 0x4,  0x4,  0x4,
+            0x4,  0x4, 0x4, 0x4, 0x4,  0x4, 0x4, 0x4, 0x4, 0x4,  0x4,  0x4,
+            0x4,  0x4, 0x4, 0x4, 0x4,  0x4, 0x4, 0x4, 0x4, 0x4,  0x4,  0x4,
+            0x4,  0x4, 0x4, 0x4, 0x4,  0x4, 0x4, 0x4, 0x4, 0x4,  0x4,  0x4,
+            0x4,  0x4, 0x4, 0x4, 0x4,  0x4, 0x4, 0x4, 0x4, 0x4,  0x4,  0x4,
+            0x4,  0x4, 0x0, 0x0, 0x2a, 0x4, 0x4, 0x4, 0x4, 0x4,  0x4,  0x4,
+            0x4,  0x4, 0x4, 0x4, 0x0,  0x0, 0x0,
+        };
+        CHECK(run_input(input, sizeof(input)) == 0);
+    }
+    SECTION("")
+    {
+        constexpr std::uint8_t input[] = {
+            0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x1,  0x1,  0x0,
+            0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,
+            0x0,  0x3,  0x0,  0x0,  0x0,  0x0,  0x0,  0x4,  0x0,  0x0,  0x0,
+            0x0,  0x0,  0x0,  0xe2, 0xe2, 0xe2, 0xe2, 0xe2, 0xe2, 0xe2, 0xe2,
+            0xe2, 0xe2, 0xe2, 0xe2, 0xe2, 0xe2, 0xe2, 0xe2, 0x4,  0x4,  0x4,
+            0x4,  0x4,  0xf8, 0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,
+            0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,
+            0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x21, 0x4,
+            0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,
+            0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,
+            0x4,  0x4,  0xb,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,
+            0x4,  0x4,  0x4,  0x4,  0x4,  0x17, 0x4,  0xe2, 0xe2, 0xe2, 0x2a,
+            0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,
+            0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,
+            0x4,  0x21, 0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,
+            0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,
+            0x4,  0x4,  0x4,  0x4,  0x4,  0x17, 0x4,  0xe2, 0xe2, 0xe2, 0x2a,
+            0xe2, 0xe2, 0xe2, 0xe2, 0xe2, 0x1f, 0xe2, 0x0,  0x0,  0x0,  0x0,
+            0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0xff, 0xe2,
+            0xe2, 0xe2, 0xe2, 0xe2, 0xe2, 0x0,  0x0,  0x0,  0x15, 0x15, 0x15,
+            0x15, 0x15, 0x15, 0x15, 0x15, 0x15, 0x15, 0x4,  0x4,  0x4,  0x4,
+            0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x15, 0x15, 0x15, 0x15,
+            0x0,  0x0,
+        };
+        CHECK(run_input(input, sizeof(input)) == 0);
+    }
+    SECTION("")
+    {
+        constexpr std::uint8_t input[] = {
+            0x0,  0x1,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x21,
+            0x0,  0x0,  0x0,  0x0,  0xff, 0xff, 0xff, 0xff, 0xff, 0x0,  0x0,
+            0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x8,  0x0,  0x0,  0x0,
+            0x0,  0x0,  0x0,  0x0,  0x0,  0x27, 0x0,  0x21, 0x0,  0x0,  0x0,
+            0x0,  0x0,  0x1,  0x0,  0x3a, 0x0,  0x0,  0x0,  0x0,  0x0,  0x0,
+            0x0,  0x0,  0x0,  0x0,  0x0,  0x40, 0x0,  0x0,  0x0,  0x0,  0x0,
+            0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x1,  0x0,  0x0,  0x0,  0x0,
+            0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,
+            0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x4,  0x0,  0x0,
+            0x4,  0x0,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,
+            0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,
+            0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0xff, 0xff, 0xff,
+            0xff, 0xff, 0xff, 0xff, 0xff, 0x4,  0x4,  0x4,  0x4,  0x4,  0x4,
+            0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,
+            0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,
+            0x4,  0x4,  0x4,  0x4,  0x4,  0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+            0xff, 0xff, 0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,
+            0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,
+            0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,
+            0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,
+            0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,
+            0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0xe4, 0xe4, 0x0,  0x0,
+            0x0,  0x0,  0xe4, 0x0,  0xe4, 0x0,  0x0,  0x0,  0x0,  0x0,  0x8,
+            0x0,
+        };
+        CHECK(run_input(input, sizeof(input)) == 0);
+    }
+
+    // buffer overflow when looking inside the sizes array for the
+    // index of a position
+    SECTION("")
+    {
+        constexpr std::uint8_t input[] = {
+            0x0,  0x0,  0x0,  0x0, 0x0,  0x0,  0x0, 0x0, 0x1,  0x0, 0x0, 0xff,
+            0xff, 0xff, 0xff, 0x0, 0x0,  0x0,  0x0, 0x1, 0x0,  0x0, 0x0, 0x0,
+            0x0,  0x0,  0x0,  0x0, 0x0,  0x0,  0x0, 0x4, 0x4,  0x4, 0x4, 0x4,
+            0x4,  0x4,  0x4,  0x4, 0x4,  0x4,  0x4, 0x4, 0x4,  0x4, 0x4, 0x4,
+            0x4,  0x4,  0x4,  0x4, 0x4,  0x4,  0x0, 0x0, 0x4,  0x4, 0x4, 0x4,
+            0x4,  0x4,  0x4,  0x4, 0x4,  0x0,  0x0, 0x0, 0x4,  0x4, 0x4, 0x4,
+            0x4,  0x4,  0x4,  0x4, 0x4,  0x4,  0x4, 0x4, 0x4,  0x4, 0x4, 0x4,
+            0x4,  0x4,  0x4,  0x4, 0x4,  0x4,  0x4, 0x4, 0x4,  0x4, 0x0, 0x4,
+            0x4,  0x4,  0x4,  0x4, 0x3,  0xff, 0x0, 0x0, 0x4,  0x4, 0x4, 0x4,
+            0x4,  0x4,  0x4,  0x4, 0x4,  0x4,  0x4, 0x4, 0x4,  0x4, 0x4, 0x4,
+            0x4,  0x4,  0x4,  0x4, 0x0,  0x0,  0x0, 0x0, 0x0,  0x0, 0x4, 0x4,
+            0x4,  0x4,  0x4,  0x4, 0x4,  0x4,  0x4, 0x4, 0x4,  0x4, 0x4, 0x4,
+            0x4,  0x4,  0x4,  0x4, 0x4,  0x4,  0x4, 0x4, 0x4,  0x4, 0x4, 0x4,
+            0x4,  0x4,  0x4,  0x4, 0x4,  0x4,  0x4, 0x4, 0x0,  0x0, 0x4, 0x4,
+            0x4,  0x4,  0x4,  0x4, 0x4,  0x4,  0x4, 0x4, 0x4,  0x4, 0x4, 0x4,
+            0x4,  0x4,  0x4,  0x4, 0x4,  0x4,  0x4, 0x4, 0x4,  0x4, 0x4, 0x4,
+            0x4,  0x4,  0x4,  0x4, 0x4,  0x4,  0x4, 0x4, 0x1e, 0x0, 0x4, 0x4,
+            0x4,  0x4,  0x4,  0x3, 0xff, 0x0,  0x0, 0x4, 0x4,  0x4, 0x4, 0x4,
+            0x4,  0x4,  0x4,  0x4, 0x4,  0x4,  0x4, 0x4, 0x4,  0x4, 0x4, 0x4,
+            0x4,  0x4,  0x4,  0x4, 0x4,  0x4,  0x4, 0x4, 0x4,  0x0, 0x0, 0x0,
+            0x0,  0x0,  0x0,  0x0, 0xdb, 0x0,  0x0, 0x0, 0x0,  0x0, 0x0, 0x0,
+            0x0,  0x0,  0x0,
+        };
+        CHECK(run_input(input, sizeof(input)) == 0);
+    }
+    SECTION("")
+    {
+        constexpr std::uint8_t input[] = {
+            0x0,  0x0, 0x0, 0x0, 0x0, 0x0, 0x0,  0x0,  0x0, 0x0, 0x0, 0x0, 0x0,
+            0x0,  0x0, 0x0, 0x0, 0x0, 0x0, 0x0,  0x0,  0x0, 0x0, 0x0, 0x0, 0x0,
+            0x0,  0x0, 0x0, 0x0, 0x0, 0x0, 0x9,  0x0,  0x0, 0x0, 0x0, 0x0, 0x1,
+            0x0,  0x0, 0x0, 0x0, 0x0, 0x0, 0x0,  0x0,  0x0, 0x0, 0x0, 0x4, 0x4,
+            0x4,  0x4, 0x4, 0x4, 0x4, 0x4, 0x4,  0x4,  0x4, 0x4, 0x4, 0x4, 0x4,
+            0x4,  0x4, 0x4, 0x4, 0x4, 0x3, 0xfa, 0x4,  0x4, 0x4, 0x4, 0x4, 0x4,
+            0x4,  0x4, 0x4, 0x0, 0x0, 0x0, 0x9,  0x0,  0x0, 0x0, 0x0, 0x0, 0x1,
+            0x0,  0x0, 0x0, 0x0, 0x0, 0x0, 0x0,  0x0,  0x0, 0x0, 0x0, 0x4, 0x4,
+            0x4,  0x4, 0x4, 0x4, 0x4, 0x4, 0x4,  0x4,  0x4, 0x4, 0x4, 0x4, 0x4,
+            0x4,  0x4, 0x4, 0x4, 0x4, 0x3, 0xfa, 0x4,  0x4, 0x4, 0x4, 0x4, 0x4,
+            0x4,  0x4, 0x4, 0x4, 0x4, 0x4, 0x4,  0x4,  0x4, 0x4, 0x4, 0x4, 0x4,
+            0x4,  0x4, 0x4, 0x4, 0x4, 0x4, 0x4,  0x4,  0x4, 0x4, 0x4, 0x4, 0x4,
+            0x4,  0x4, 0x4, 0x4, 0x4, 0x4, 0x4,  0x4,  0x4, 0x4, 0x4, 0x0, 0x0,
+            0x0,  0x0, 0x0, 0x0, 0x0, 0x0, 0x4,  0x4,  0x4, 0x4, 0x4, 0x0, 0x0,
+            0x0,  0x0, 0x0, 0x0, 0x0, 0x0, 0x0,  0x0,  0x0, 0x0, 0x0, 0x0, 0x0,
+            0x0,  0x0, 0x0, 0x0, 0x0, 0x0, 0x0,  0x0,  0x0, 0x0, 0x0, 0x0, 0x0,
+            0x4,  0x4, 0x4, 0x4, 0x4, 0x4, 0x4,  0x4,  0x4, 0x4, 0x4, 0x4, 0x4,
+            0x4,  0x4, 0x4, 0x4, 0x4, 0x4, 0x4,  0x4,  0x4, 0x4, 0x4, 0x4, 0x4,
+            0x4,  0x4, 0x4, 0x4, 0x4, 0x4, 0x4,  0x4,  0x4, 0x4, 0x4, 0x4, 0x3,
+            0xfa, 0x4, 0x4, 0x4, 0x0, 0x0, 0x0,  0x55, 0x0,
+        };
+        CHECK(run_input(input, sizeof(input)) == 0);
+    }
+
+    // fail when deref some null node
+    SECTION("")
+    {
+        constexpr std::uint8_t input[] = {
+            0x0,  0x0,  0x0, 0x0,  0x0,  0x0, 0x0, 0x4,  0x0,  0x0,  0x4, 0x0,
+            0x0,  0x0,  0x0, 0x0,  0x4,  0x4, 0x4, 0x4,  0x4,  0x4,  0x0, 0x0,
+            0x4,  0x4,  0x4, 0x4,  0x4,  0x4, 0x4, 0x4,  0x4,  0x4,  0x4, 0x4,
+            0x4,  0x4,  0x4, 0x4,  0x4,  0x4, 0x4, 0x4,  0x4,  0x4,  0x4, 0x4,
+            0x4,  0x4,  0x4, 0x4,  0x4,  0x4, 0x4, 0x4,  0x0,  0x0,  0x4, 0x0,
+            0x4,  0x4,  0x4, 0xe4, 0x4,  0x4, 0x4, 0x4,  0x4,  0x4,  0x4, 0x4,
+            0x4,  0x6,  0x4, 0x4,  0x4,  0x4, 0x4, 0x4,  0x4,  0x4,  0x4, 0x4,
+            0x4,  0x4,  0x4, 0x4,  0xe5, 0x0, 0x4, 0x4,  0x4,  0x4,  0x4, 0x4,
+            0x0,  0x0,  0x4, 0x4,  0x4,  0x4, 0x4, 0x4,  0x4,  0x4,  0x4, 0x4,
+            0x4,  0x4,  0x4, 0x4,  0x4,  0x4, 0x4, 0x4,  0x4,  0x4,  0x4, 0x4,
+            0x4,  0x4,  0x4, 0x4,  0xff, 0x3, 0x4, 0x4,  0x4,  0x0,  0x0, 0x0,
+            0x0,  0x4,  0x4, 0x4,  0x4,  0x4, 0x4, 0x4,  0x4,  0x4,  0x4, 0x4,
+            0x4,  0x4,  0x4, 0x4,  0x4,  0x0, 0x0, 0x4,  0x0,  0x4,  0x4, 0x4,
+            0xe4, 0x4,  0x4, 0x4,  0x4,  0x4, 0x4, 0x4,  0x4,  0x4,  0x6, 0x4,
+            0x4,  0x4,  0x4, 0x4,  0x4,  0x4, 0x4, 0x4,  0x4,  0x4,  0x4, 0x4,
+            0x4,  0xe5, 0x0, 0x4,  0x4,  0x4, 0x4, 0x4,  0x4,  0x0,  0x0, 0x4,
+            0x4,  0x4,  0x4, 0x4,  0x4,  0x4, 0x0, 0x0,  0x4,  0x4,  0x4, 0x4,
+            0x4,  0x4,  0x4, 0x4,  0x4,  0x4, 0x4, 0x4,  0x0,  0x0,  0x0, 0x0,
+            0x4,  0x4,  0x4, 0x4,  0xe1, 0x0, 0x0, 0x80, 0x0,  0x0,  0x1, 0x6,
+            0x0,  0x0,  0x0, 0x0,  0x0,  0x4, 0x0, 0x75, 0x75, 0x45, 0x0, 0x0,
+            0x0,  0x0,  0x0, 0x0,  0x0,  0x0, 0x0, 0x0,  0x0,  0x1,  0x0, 0x0,
+            0x0,  0x75, 0x4, 0x0,
+        };
+        CHECK(run_input(input, sizeof(input)) == 0);
+    }
+    SECTION("")
+    {
+        constexpr std::uint8_t input[] = {
+            0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x1,  0x0,  0x0,  0x0,
+            0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x85, 0xff, 0xff, 0xff, 0xff,
+            0xff, 0xff, 0xff, 0xff, 0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,
+            0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,
+            0x0,  0x0,  0x0,  0xff, 0xff, 0xff, 0xff, 0xff, 0x4,  0x4,  0x4,
+            0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,
+            0x4,  0x4,  0x5,  0x4,  0x28, 0x4,  0x4,  0x4,  0x0,  0x4,  0x4,
+            0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x24, 0x4,  0x4,  0x4,  0x4,
+            0x4,  0x4,  0x4,  0x4,  0x0,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,
+            0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,
+            0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,
+            0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,
+            0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,
+            0x4,  0x4,  0x4,  0x4,  0x4,  0xf3, 0x4,  0x4,  0x4,  0x4,  0x4,
+            0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,
+            0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,
+            0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,
+            0x4,  0x4,  0x4,  0xf3, 0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x4,
+            0x4,  0x4,  0x4,  0x4,  0x4,  0x4,  0x3,  0x4,  0x4,  0x4,  0xff,
+            0xff, 0xff, 0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,
+            0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,
+            0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0xad, 0x0,
+            0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,  0x0,
+        };
+        CHECK(run_input(input, sizeof(input)) == 0);
+    }
+#endif
+}
diff --git a/third_party/immer/test/flex_vector/fuzzed-1.cpp b/third_party/immer/test/flex_vector/fuzzed-1.cpp
new file mode 100644
index 000000000000..d924dc3a8310
--- /dev/null
+++ b/third_party/immer/test/flex_vector/fuzzed-1.cpp
@@ -0,0 +1,368 @@
+//
+// 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 "extra/fuzzer/fuzzer_input.hpp"
+#include <array>
+#include <catch.hpp>
+#include <immer/flex_vector.hpp>
+#include <iostream>
+
+#define IMMER_FUZZED_TRACE_ENABLE 0
+
+#if IMMER_FUZZED_TRACE_ENABLE
+#define IMMER_FUZZED_TRACE(...) std::cout << __VA_ARGS__ << std::endl;
+#else
+#define IMMER_FUZZED_TRACE(...)
+#endif
+
+namespace {
+
+template <std::size_t VarCount = 2, unsigned Bits = 2>
+int run_input(const std::uint8_t* data, std::size_t size)
+{
+    using vector_t =
+        immer::flex_vector<int, immer::default_memory_policy, Bits, Bits>;
+    using size_t = std::uint8_t;
+
+    auto vars = std::array<vector_t, VarCount>{};
+
+#if IMMER_FUZZED_TRACE_ENABLE
+    std::cout << "/// new test run" << std::endl;
+    for (auto i = 0u; i < VarCount; ++i)
+        std::cout << "auto var" << i << " = vector_t{};" << std::endl;
+#endif
+
+    auto is_valid_var   = [&](auto idx) { return idx >= 0 && idx < VarCount; };
+    auto is_valid_index = [](auto& v) {
+        return [&](auto idx) { return idx >= 0 && idx < v.size(); };
+    };
+    auto is_valid_size = [](auto& v) {
+        return [&](auto idx) { return idx >= 0 && idx <= v.size(); };
+    };
+    auto can_concat = [](auto&& v1, auto&& v2) {
+        using size_type = decltype(v1.size());
+        return v2.size() < (std::numeric_limits<size_type>::max() - v1.size());
+    };
+    auto can_insert = [](auto&& v1) {
+        using size_type = decltype(v1.size());
+        return v1.size() < std::numeric_limits<size_type>::max();
+    };
+
+    return fuzzer_input{data, size}.run([&](auto& in) {
+        enum ops
+        {
+            op_push_back,
+            op_update,
+            op_take,
+            op_drop,
+            op_concat,
+            op_push_back_move,
+            op_update_move,
+        };
+        auto src = read<std::uint8_t>(in, is_valid_var);
+        auto dst = read<std::uint8_t>(in, is_valid_var);
+        switch (read<char>(in)) {
+        case op_push_back:
+            if (can_insert(vars[src])) {
+                IMMER_FUZZED_TRACE("var" << +dst << " = var" << +src
+                                         << ".push_back(42);");
+                vars[dst] = vars[src].push_back(42);
+            }
+            break;
+        case op_update: {
+            auto idx = read<size_t>(in, is_valid_index(vars[src]));
+            IMMER_FUZZED_TRACE("var" << +dst << " = var" << +src << ".update("
+                                     << +idx
+                                     << ", [] (auto x) { return x + 1; });");
+            vars[dst] = vars[src].update(idx, [](auto x) { return x + 1; });
+            break;
+        }
+        case op_take: {
+            auto idx = read<size_t>(in, is_valid_size(vars[src]));
+            IMMER_FUZZED_TRACE("var" << +dst << " = var" << +src << ".take("
+                                     << +idx << ");");
+            vars[dst] = vars[src].take(idx);
+            break;
+        }
+        case op_drop: {
+            auto idx = read<size_t>(in, is_valid_size(vars[src]));
+            IMMER_FUZZED_TRACE("var" << +dst << " = var" << +src << ".take("
+                                     << +idx << ");");
+            vars[dst] = vars[src].drop(idx);
+            break;
+        }
+        case op_concat: {
+            auto src2 = read<std::uint8_t>(in, is_valid_var);
+            if (can_concat(vars[src], vars[src2])) {
+                IMMER_FUZZED_TRACE("var" << +dst << " = var" << +src << " + var"
+                                         << +src2 << ";");
+                vars[dst] = vars[src] + vars[src2];
+            }
+            break;
+        }
+        case op_push_back_move: {
+            if (can_insert(vars[src])) {
+                IMMER_FUZZED_TRACE("var" << +dst << " = std::move(var" << +src
+                                         << ").push_back(21);");
+                vars[dst] = std::move(vars[src]).push_back(21);
+            }
+            break;
+        }
+        case op_update_move: {
+            auto idx = read<size_t>(in, is_valid_index(vars[src]));
+            IMMER_FUZZED_TRACE("var" << +dst << " = std::move(var" << +src
+                                     << ").update(" << +idx
+                                     << ", [] (auto x) { return x + 1; });");
+            vars[dst] =
+                std::move(vars[src]).update(idx, [](auto x) { return x + 1; });
+            break;
+        }
+        default:
+            break;
+        };
+        return true;
+    });
+}
+
+} // anonymous namespace
+
+TEST_CASE("bug: memory leak because of move update")
+{
+    // There was a problem caused with shared "sizes buffer" in
+    // relaxed nodes.  In particular, the ensure_mutable_relaxed(...)
+    // function was not decremeting the old sizes buffer. That is why
+    // the last transient push_back (which uses mutable operations)
+    // causes some of the relaxed buffers that are created during the
+    // previous concatenations, and that start to be shared from the
+    // update() onwards, to later be leaked.
+    SECTION("simplified")
+    {
+        using vector_t =
+            immer::flex_vector<int, immer::default_memory_policy, 2, 2>;
+        auto var0 = vector_t{};
+        auto var1 = vector_t{};
+        var0      = var0.push_back(42);
+        var0      = var0.push_back(42);
+        var0      = var0.push_back(42);
+        var0      = var0 + var0;
+        var1      = var0.push_back(42);
+        var0      = var0 + var1;
+        var1      = var0.push_back(42);
+        var0      = var0 + var0;
+        var0      = var1 + var0;
+        var0      = var1.update(5, [](auto x) { return x + 1; });
+        var0      = std::move(var0).push_back(21);
+    }
+
+#if __GNUC__ != 9
+    SECTION("")
+    {
+        constexpr std::uint8_t input[] = {
+            0xff, 0x0,  0xff, 0x0, 0x0,  0x0,  0x0,  0x0,  0x0,  0x0, 0x0,
+            0x40, 0x0,  0x0,  0x4, 0x0,  0x6d, 0x6d, 0x0,  0x1,  0x0, 0x4,
+            0x6d, 0x6d, 0x6d, 0x0, 0x0,  0x4,  0x1,  0x6d, 0x6d, 0x0, 0x1,
+            0x0,  0x0,  0x0,  0x4, 0x28, 0x0,  0xfc, 0x1,  0x0,  0x4, 0x0,
+            0x0,  0x0,  0xfc, 0x1, 0x0,  0x1,  0x5,  0x0,  0x0,  0x1, 0x5,
+            0x0,  0x0,  0x5,  0x0, 0x0,  0xff, 0xff, 0xff, 0x27,
+        };
+        CHECK(run_input(input, sizeof(input)) == 0);
+    }
+#endif
+}
+
+TEST_CASE("non-bug: crash")
+{
+    // This is an interesting finding that is left here for
+    // documentation.  This test actually should not run... the
+    // problem is that when we build too large vectors via
+    // concatenation, we can sometimes "overflow the shift".  This is
+    // a degenerate case that we won't fix, but this helped adding
+    // appropriate assertions to the code.
+    //
+    // To prevent this in further fuzzing, the can_concat check has
+    // been made stricter.
+    return;
+
+    SECTION("simplified")
+    {
+        using vector_t =
+            immer::flex_vector<int, immer::default_memory_policy, 2, 2>;
+        auto var4 = vector_t{};
+        var4      = var4.push_back(42);
+        var4      = var4.push_back(42);
+        var4      = var4.push_back(42);
+        var4      = var4.push_back(42);
+        var4      = var4.push_back(42);
+        auto var0 = var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var0 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4 + var4;
+        var4      = var4.update(4, [](auto x) { return x + 1; });
+    }
+#if __GNUC__ != 9
+    SECTION("")
+    {
+        constexpr std::uint8_t input[] = {
+            0x00, 0x00, 0x00, 0x23, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+            0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+            0x00, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x00,
+            0x00, 0x00, 0x00, 0x04, 0x04, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
+            0x04, 0x00, 0x04, 0x04, 0x04, 0x00, 0x00, 0x00, 0x00, 0x04, 0x04,
+            0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
+            0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x00, 0x2a, 0x00,
+            0x00, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
+            0x04, 0x04, 0x04, 0x04, 0xfc, 0xf9, 0x04, 0x04, 0x04, 0x04, 0x04,
+            0x04, 0x04, 0x04, 0x04, 0x05, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x23, 0x00, 0x00, 0x00, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
+            0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
+            0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x05, 0x04, 0x04, 0x04,
+            0x04, 0x04, 0x04, 0x00, 0x00, 0x00, 0x00, 0x00, 0x23, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04, 0x04, 0x04, 0x04, 0x04,
+            0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
+            0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x05, 0x04,
+            0x04, 0x04, 0x04, 0x04, 0x04, 0x00, 0x00, 0x00, 0x00, 0x00, 0x23,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04, 0x04, 0x04,
+            0x04, 0x04, 0x04, 0x04, 0x00, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
+            0x04, 0x04, 0x04, 0x04, 0x04, 0xd5, 0x04, 0x04, 0x04, 0x04, 0x04,
+            0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x05, 0x04, 0x04,
+            0x04, 0x04, 0x04, 0x04, 0x00, 0x00, 0x00, 0x00, 0x00, 0x23, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04, 0x04, 0x04, 0x04,
+            0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
+            0x04, 0x04, 0x04, 0x00, 0x01, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
+            0x04, 0x04, 0x04, 0x04, 0x04, 0x05, 0x04, 0x04, 0x04, 0x04, 0x04,
+            0x04, 0x00, 0x00, 0x00, 0x00, 0x00, 0x23, 0x00, 0x00, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x00,
+            0x01, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
+            0x04, 0x05, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x00, 0x00, 0x00,
+            0x00, 0x00, 0x23, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x3a,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+            0x00, 0x00, 0x21, 0x04, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04, 0x04,
+            0x04, 0x04, 0x04, 0x00, 0x04, 0x04, 0x00, 0x00, 0x04, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x04, 0x00, 0x04, 0x00, 0x00, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+            0xff, 0xff, 0x13, 0x13, 0x13, 0x13, 0x13, 0x00, 0x00, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00,
+            0x00, 0x00, 0x29, 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
+            0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x21, 0x00, 0x10, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
+            0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
+            0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x05, 0x04, 0x04, 0x04, 0x04,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x3a, 0x00, 0x02, 0x00, 0x00, 0x00,
+            0x04, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x23, 0x00, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04, 0x04, 0x04, 0x04, 0x04,
+            0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
+            0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x05, 0x04,
+            0x04, 0x04, 0x04, 0x04, 0x04, 0x00, 0x00, 0x00, 0x00, 0x00, 0x23,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xff, 0xff,
+            0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04, 0x04, 0x04,
+            0x04, 0x04, 0x04, 0x04, 0x00, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
+            0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
+            0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x05, 0x04, 0x04,
+            0x04, 0x04, 0x04, 0x04, 0x00, 0x00, 0x00, 0x00, 0x00, 0x23, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04, 0x04, 0x04, 0x04,
+            0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x00, 0x01,
+            0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
+            0x05, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x00, 0x00, 0x00, 0x00,
+            0x00, 0x23, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04,
+            0x04, 0x04, 0x04, 0x04, 0x04, 0x00, 0x01, 0x04, 0x04, 0x04, 0x04,
+            0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x05, 0x04, 0x04, 0x04,
+            0x04, 0x04, 0x04, 0x00, 0x00, 0x00, 0x00, 0x00, 0x23, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x3a, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x21, 0x04, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x00, 0x04, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00,
+            0x00, 0x00, 0x00, 0x23, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+            0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x04, 0x04, 0x04,
+            0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
+            0x00,
+        };
+        CHECK(run_input<8>(input, sizeof(input)) == 0);
+    }
+#endif
+}
diff --git a/third_party/immer/test/flex_vector/fuzzed-2.cpp b/third_party/immer/test/flex_vector/fuzzed-2.cpp
new file mode 100644
index 000000000000..ba17c1a620ec
--- /dev/null
+++ b/third_party/immer/test/flex_vector/fuzzed-2.cpp
@@ -0,0 +1,188 @@
+//
+// 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 "extra/fuzzer/fuzzer_input.hpp"
+#include <array>
+#include <catch.hpp>
+#include <immer/flex_vector.hpp>
+#include <iostream>
+
+#define IMMER_FUZZED_TRACE_ENABLE 0
+
+#if IMMER_FUZZED_TRACE_ENABLE
+#define IMMER_FUZZED_TRACE(...) std::cout << __VA_ARGS__ << std::endl;
+#else
+#define IMMER_FUZZED_TRACE(...)
+#endif
+
+namespace {
+
+template <std::size_t VarCount = 2, unsigned Bits = 2>
+int run_input(const std::uint8_t* data, std::size_t size)
+{
+    using vector_t =
+        immer::flex_vector<int, immer::default_memory_policy, Bits, Bits>;
+    using size_t = std::uint8_t;
+
+    auto vars = std::array<vector_t, VarCount>{};
+
+#if IMMER_FUZZED_TRACE_ENABLE
+    std::cout << "/// new test run" << std::endl;
+    for (auto i = 0u; i < VarCount; ++i)
+        std::cout << "auto var" << i << " = vector_t{};" << std::endl;
+#endif
+
+    auto is_valid_var   = [&](auto idx) { return idx >= 0 && idx < VarCount; };
+    auto is_valid_index = [](auto& v) {
+        return [&](auto idx) { return idx >= 0 && idx < v.size(); };
+    };
+    auto is_valid_size = [](auto& v) {
+        return [&](auto idx) { return idx >= 0 && idx <= v.size(); };
+    };
+    auto can_concat = [](auto&& v1, auto&& v2) {
+        using size_type = decltype(v1.size());
+        return v2.size() < (std::numeric_limits<size_type>::max() - v1.size());
+    };
+    auto can_insert = [](auto&& v1) {
+        using size_type = decltype(v1.size());
+        return v1.size() < std::numeric_limits<size_type>::max();
+    };
+
+    return fuzzer_input{data, size}.run([&](auto& in) {
+        enum ops
+        {
+            op_push_back,
+            op_update,
+            op_take,
+            op_drop,
+            op_concat,
+            op_push_back_move,
+            op_update_move,
+            op_take_move,
+            op_drop_move,
+        };
+        auto src = read<std::uint8_t>(in, is_valid_var);
+        auto dst = read<std::uint8_t>(in, is_valid_var);
+        switch (read<char>(in)) {
+        case op_push_back:
+            if (can_insert(vars[src])) {
+                IMMER_FUZZED_TRACE("var" << +dst << " = var" << +src
+                                         << ".push_back(42);");
+                vars[dst] = vars[src].push_back(42);
+            }
+            break;
+        case op_update: {
+            auto idx = read<size_t>(in, is_valid_index(vars[src]));
+            IMMER_FUZZED_TRACE("var" << +dst << " = var" << +src << ".update("
+                                     << +idx
+                                     << ", [] (auto x) { return x + 1; });");
+            vars[dst] = vars[src].update(idx, [](auto x) { return x + 1; });
+            break;
+        }
+        case op_take: {
+            auto idx = read<size_t>(in, is_valid_size(vars[src]));
+            IMMER_FUZZED_TRACE("var" << +dst << " = var" << +src << ".take("
+                                     << +idx << ");");
+            vars[dst] = vars[src].take(idx);
+            break;
+        }
+        case op_drop: {
+            auto idx = read<size_t>(in, is_valid_size(vars[src]));
+            IMMER_FUZZED_TRACE("var" << +dst << " = var" << +src << ".take("
+                                     << +idx << ");");
+            vars[dst] = vars[src].drop(idx);
+            break;
+        }
+        case op_concat: {
+            auto src2 = read<std::uint8_t>(in, is_valid_var);
+            if (can_concat(vars[src], vars[src2])) {
+                IMMER_FUZZED_TRACE("var" << +dst << " = var" << +src << " + var"
+                                         << +src2 << ";");
+                vars[dst] = vars[src] + vars[src2];
+            }
+            break;
+        }
+        case op_push_back_move: {
+            if (can_insert(vars[src])) {
+                IMMER_FUZZED_TRACE("var" << +dst << " = std::move(var" << +src
+                                         << ").push_back(21);");
+                vars[dst] = std::move(vars[src]).push_back(21);
+            }
+            break;
+        }
+        case op_update_move: {
+            auto idx = read<size_t>(in, is_valid_index(vars[src]));
+            IMMER_FUZZED_TRACE("var" << +dst << " = std::move(var" << +src
+                                     << ").update(" << +idx
+                                     << ", [] (auto x) { return x + 1; });");
+            vars[dst] =
+                std::move(vars[src]).update(idx, [](auto x) { return x + 1; });
+            break;
+        }
+        case op_take_move: {
+            auto idx = read<size_t>(in, is_valid_size(vars[src]));
+            IMMER_FUZZED_TRACE("var" << +dst << " = std::move(var" << +src
+                                     << ").take(" << +idx << ");");
+            vars[dst] = std::move(vars[src]).take(idx);
+            break;
+        }
+        case op_drop_move: {
+            auto idx = read<size_t>(in, is_valid_size(vars[src]));
+            IMMER_FUZZED_TRACE("var" << +dst << " = std::move(var" << +src
+                                     << ").drop(" << +idx << ");");
+            vars[dst] = std::move(vars[src]).drop(idx);
+            break;
+        }
+        default:
+            break;
+        };
+        return true;
+    });
+}
+
+} // anonymous namespace
+
+TEST_CASE("bug: use after free on move-take")
+{
+    SECTION("")
+    {
+        using vector_t =
+            immer::flex_vector<int, immer::default_memory_policy, 2, 2>;
+        auto var0 = vector_t{};
+        auto var1 = vector_t{};
+        var0      = var0.push_back(42);
+        var0      = var0.push_back(42);
+        var0      = var0.push_back(42);
+        var0      = var0.push_back(42);
+        var0      = var0 + var0;
+        var0      = var0 + var0;
+        var0      = var0 + var0;
+        var0      = var0 + var0;
+        var0      = var0.push_back(42);
+        var0      = var0.push_back(42);
+        var0      = var0.push_back(42);
+        var0      = var0.push_back(42);
+        var0      = var0.push_back(42);
+        var1      = var0.push_back(42);
+        var0      = std::move(var0).take(68);
+    }
+
+#if __GNUC__ != 9
+    SECTION("")
+    {
+        constexpr std::uint8_t input[] = {
+            0x0, 0x0,  0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x1,  0x0,  0x0, 0x0, 0x0,
+            0x0, 0x40, 0x0, 0x0, 0x0, 0x0, 0x4, 0x4, 0x0,  0x0,  0x0, 0x4, 0x0,
+            0x0, 0x0,  0x4, 0x0, 0x0, 0x0, 0x4, 0x0, 0x0,  0x4,  0x0, 0x0, 0x0,
+            0x4, 0x0,  0x0, 0x0, 0x4, 0x0, 0x0, 0x0, 0x4,  0x0,  0x0, 0x0, 0x4,
+            0x0, 0x0,  0x0, 0x1, 0x0, 0x0, 0x0, 0x7, 0x41, 0xb5, 0x0, 0x0,
+        };
+        CHECK(run_input(input, sizeof(input)) == 0);
+    }
+#endif
+}
diff --git a/third_party/immer/test/flex_vector/fuzzed-3.cpp b/third_party/immer/test/flex_vector/fuzzed-3.cpp
new file mode 100644
index 000000000000..5ef1eaffb755
--- /dev/null
+++ b/third_party/immer/test/flex_vector/fuzzed-3.cpp
@@ -0,0 +1,222 @@
+//
+// 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 "extra/fuzzer/fuzzer_input.hpp"
+#include <array>
+#include <catch.hpp>
+#include <immer/flex_vector.hpp>
+#include <iostream>
+
+#define IMMER_FUZZED_TRACE_ENABLE 0
+
+#if IMMER_FUZZED_TRACE_ENABLE
+#define IMMER_FUZZED_TRACE(...) std::cout << __VA_ARGS__ << std::endl;
+#else
+#define IMMER_FUZZED_TRACE(...)
+#endif
+
+namespace {
+
+template <std::size_t VarCount = 2, unsigned Bits = 2>
+int run_input(const std::uint8_t* data, std::size_t size)
+{
+    using vector_t =
+        immer::flex_vector<int, immer::default_memory_policy, Bits, Bits>;
+    using size_t = std::uint8_t;
+
+    auto vars = std::array<vector_t, VarCount>{};
+
+#if IMMER_FUZZED_TRACE_ENABLE
+    std::cout << "/// new test run" << std::endl;
+    for (auto i = 0u; i < VarCount; ++i)
+        std::cout << "auto var" << i << " = vector_t{};" << std::endl;
+#endif
+
+    auto is_valid_var = [&](auto idx) { return idx >= 0 && idx < VarCount; };
+    auto is_valid_var_neq = [](auto other) {
+        return [=](auto idx) {
+            return idx >= 0 && idx < VarCount && idx != other;
+        };
+    };
+    auto is_valid_index = [](auto& v) {
+        return [&](auto idx) { return idx >= 0 && idx < v.size(); };
+    };
+    auto is_valid_size = [](auto& v) {
+        return [&](auto idx) { return idx >= 0 && idx <= v.size(); };
+    };
+    auto can_concat = [](auto&& v1, auto&& v2) {
+        using size_type = decltype(v1.size());
+        return v2.size() < (std::numeric_limits<size_type>::max() - v1.size());
+    };
+    auto can_insert = [](auto&& v1) {
+        using size_type = decltype(v1.size());
+        return v1.size() < std::numeric_limits<size_type>::max();
+    };
+
+    return fuzzer_input{data, size}.run([&](auto& in) {
+        enum ops
+        {
+            op_push_back,
+            op_update,
+            op_take,
+            op_drop,
+            op_concat,
+            op_push_back_move,
+            op_update_move,
+            op_take_move,
+            op_drop_move,
+            op_concat_move_l,
+            op_concat_move_r,
+            op_concat_move_lr,
+        };
+        auto src = read<std::uint8_t>(in, is_valid_var);
+        auto dst = read<std::uint8_t>(in, is_valid_var);
+        switch (read<char>(in)) {
+        case op_push_back:
+            if (can_insert(vars[src])) {
+                IMMER_FUZZED_TRACE("var" << +dst << " = var" << +src
+                                         << ".push_back(42);");
+                vars[dst] = vars[src].push_back(42);
+            }
+            break;
+        case op_update: {
+            auto idx = read<size_t>(in, is_valid_index(vars[src]));
+            IMMER_FUZZED_TRACE("var" << +dst << " = var" << +src << ".update("
+                                     << +idx
+                                     << ", [] (auto x) { return x + 1; });");
+            vars[dst] = vars[src].update(idx, [](auto x) { return x + 1; });
+            break;
+        }
+        case op_take: {
+            auto idx = read<size_t>(in, is_valid_size(vars[src]));
+            IMMER_FUZZED_TRACE("var" << +dst << " = var" << +src << ".take("
+                                     << +idx << ");");
+            vars[dst] = vars[src].take(idx);
+            break;
+        }
+        case op_drop: {
+            auto idx = read<size_t>(in, is_valid_size(vars[src]));
+            IMMER_FUZZED_TRACE("var" << +dst << " = var" << +src << ".take("
+                                     << +idx << ");");
+            vars[dst] = vars[src].drop(idx);
+            break;
+        }
+        case op_concat: {
+            auto src2 = read<std::uint8_t>(in, is_valid_var);
+            if (can_concat(vars[src], vars[src2])) {
+                IMMER_FUZZED_TRACE("var" << +dst << " = var" << +src << " + var"
+                                         << +src2 << ";");
+                vars[dst] = vars[src] + vars[src2];
+            }
+            break;
+        }
+        case op_push_back_move: {
+            if (can_insert(vars[src])) {
+                IMMER_FUZZED_TRACE("var" << +dst << " = std::move(var" << +src
+                                         << ").push_back(21);");
+                vars[dst] = std::move(vars[src]).push_back(21);
+            }
+            break;
+        }
+        case op_update_move: {
+            auto idx = read<size_t>(in, is_valid_index(vars[src]));
+            IMMER_FUZZED_TRACE("var" << +dst << " = std::move(var" << +src
+                                     << ").update(" << +idx
+                                     << ", [] (auto x) { return x + 1; });");
+            vars[dst] =
+                std::move(vars[src]).update(idx, [](auto x) { return x + 1; });
+            break;
+        }
+        case op_take_move: {
+            auto idx = read<size_t>(in, is_valid_size(vars[src]));
+            IMMER_FUZZED_TRACE("var" << +dst << " = std::move(var" << +src
+                                     << ").take(" << +idx << ");");
+            vars[dst] = std::move(vars[src]).take(idx);
+            break;
+        }
+        case op_drop_move: {
+            auto idx = read<size_t>(in, is_valid_size(vars[src]));
+            IMMER_FUZZED_TRACE("var" << +dst << " = std::move(var" << +src
+                                     << ").drop(" << +idx << ");");
+            vars[dst] = std::move(vars[src]).drop(idx);
+            break;
+        }
+        case op_concat_move_l: {
+            auto src2 = read<std::uint8_t>(in, is_valid_var_neq(src));
+            if (can_concat(vars[src], vars[src2])) {
+                IMMER_FUZZED_TRACE("var" << +dst << " = std::move(var" << +src
+                                         << ") + var" << +src2 << ";");
+                vars[dst] = std::move(vars[src]) + vars[src2];
+            }
+            break;
+        }
+        case op_concat_move_r: {
+            auto src2 = read<std::uint8_t>(in, is_valid_var_neq(src));
+            if (can_concat(vars[src], vars[src2])) {
+                IMMER_FUZZED_TRACE("var" << +dst << " = var" << +src
+                                         << " + std::move(var" << +src2
+                                         << ");");
+                vars[dst] = vars[src] + std::move(vars[src2]);
+            }
+            break;
+        }
+        case op_concat_move_lr: {
+            auto src2 = read<std::uint8_t>(in, is_valid_var_neq(src));
+            if (can_concat(vars[src], vars[src2])) {
+                IMMER_FUZZED_TRACE("var" << +dst << " = std::move(var" << +src
+                                         << ") + std::move(var" << +src2
+                                         << ");");
+                vars[dst] = std::move(vars[src]) + std::move(vars[src2]);
+            }
+            break;
+        }
+        default:
+            break;
+        };
+        return true;
+    });
+}
+
+} // namespace
+
+TEST_CASE("bug: concat with moving the right side")
+{
+    // This was a stupid bug on the concatenation of small vectors
+    // when moving one of the sides.
+    SECTION("simplified")
+    {
+        using vector_t =
+            immer::flex_vector<int, immer::default_memory_policy, 2, 2>;
+        auto var0 = vector_t{};
+        auto var1 = vector_t{};
+        var0      = var0.push_back(42);
+        var0      = var0.push_back(42);
+        var0      = var0.push_back(42);
+        var1      = var0.push_back(42);
+        var0      = var0 + var0;
+        var0      = var0.push_back(42);
+        var0      = var0 + var1;
+        var0      = var0 + var0;
+        var0      = var0 + std::move(var1);
+    }
+
+#if __GNUC__ != 9
+    SECTION("vm")
+    {
+        constexpr std::uint8_t input[] = {
+            0x0,  0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x0,
+            0x0,  0x0,  0x0,  0x1,  0x0,  0x40, 0x28, 0x0,  0x4,  0x3f,
+            0x20, 0x0,  0x0,  0x4,  0x3f, 0x8,  0x0,  0x0,  0x0,  0x0,
+            0x1,  0x0,  0x0,  0x0,  0x4,  0x3f, 0x0,  0x0,  0x40, 0x0,
+            0x0,  0x0,  0x0,  0x4,  0x3f, 0x1,  0x0,  0x0,  0x4,  0x3f,
+            0x0,  0x0,  0xff, 0x0,  0xa,  0x1,  0x0,  0xff, 0x0,  0x0,
+        };
+        CHECK(run_input(input, sizeof(input)) == 0);
+    }
+#endif
+}
diff --git a/third_party/immer/test/flex_vector/fuzzed-4.cpp b/third_party/immer/test/flex_vector/fuzzed-4.cpp
new file mode 100644
index 000000000000..d9ecdd7fba7f
--- /dev/null
+++ b/third_party/immer/test/flex_vector/fuzzed-4.cpp
@@ -0,0 +1,364 @@
+//
+// 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 "extra/fuzzer/fuzzer_input.hpp"
+#include <array>
+#include <catch.hpp>
+#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 <iostream>
+
+#define IMMER_FUZZED_TRACE_ENABLE 0
+
+#if IMMER_FUZZED_TRACE_ENABLE
+#define IMMER_FUZZED_TRACE(...) std::cout << __VA_ARGS__ << std::endl;
+#else
+#define IMMER_FUZZED_TRACE(...)
+#endif
+
+using gc_memory = immer::memory_policy<immer::heap_policy<immer::gc_heap>,
+                                       immer::no_refcount_policy,
+                                       immer::gc_transience_policy,
+                                       false>;
+
+namespace {
+
+template <std::size_t VarCount = 4, unsigned Bits = 2>
+int run_input(const std::uint8_t* data, std::size_t size)
+{
+    using vector_t    = immer::flex_vector<int, gc_memory, Bits, Bits>;
+    using transient_t = typename vector_t::transient_type;
+    using size_t      = std::uint8_t;
+
+    auto vs = std::array<vector_t, VarCount>{};
+    auto ts = std::array<transient_t, VarCount>{};
+
+#if IMMER_FUZZED_TRACE_ENABLE
+    std::cout << "/// new test run" << std::endl;
+    for (auto i = 0; i < VarCount; ++i)
+        std::cout << "auto v" << i << " = vector_t{};" << std::endl;
+    for (auto i = 0; i < VarCount; ++i)
+        std::cout << "auto t" << i << " = transient_t{};" << std::endl;
+#endif
+
+    auto is_valid_var = [&](auto idx) { return idx >= 0 && idx < VarCount; };
+    auto is_valid_var_neq = [](auto other) {
+        return [=](auto idx) {
+            return idx >= 0 && idx < VarCount && idx != other;
+        };
+    };
+    auto is_valid_index = [](auto& v) {
+        return [&](auto idx) { return idx >= 0 && idx < v.size(); };
+    };
+    auto is_valid_size = [](auto& v) {
+        return [&](auto idx) { return idx >= 0 && idx <= v.size(); };
+    };
+    auto can_concat = [](auto&& v1, auto&& v2) {
+        using size_type = decltype(v1.size());
+        auto max        = std::numeric_limits<size_type>::max() >> (Bits * 4);
+        return v1.size() < max && v2.size() < max;
+    };
+
+    return fuzzer_input{data, size}.run([&](auto& in) {
+        enum ops
+        {
+            op_transient,
+            op_persistent,
+            op_push_back,
+            op_update,
+            op_take,
+            op_drop,
+            op_concat,
+            op_push_back_mut,
+            op_update_mut,
+            op_take_mut,
+            op_drop_mut,
+            op_prepend_mut,
+            op_prepend_mut_move,
+            op_append_mut,
+            op_append_mut_move,
+        };
+        auto dst = read<std::uint8_t>(in, is_valid_var);
+        switch (read<char>(in)) {
+        case op_transient: {
+            auto src = read<std::uint8_t>(in, is_valid_var);
+            IMMER_FUZZED_TRACE("t" << +dst << " = v" << +src
+                                   << ".transient();");
+            ts[dst] = vs[src].transient();
+            break;
+        }
+        case op_persistent: {
+            auto src = read<std::uint8_t>(in, is_valid_var);
+            IMMER_FUZZED_TRACE("v" << +dst << " = t" << +src
+                                   << ".persistent();");
+            vs[dst] = ts[src].persistent();
+            break;
+        }
+        case op_push_back: {
+            auto src = read<std::uint8_t>(in, is_valid_var);
+            IMMER_FUZZED_TRACE("v" << +dst << " = v" << +src
+                                   << ".push_back(42);");
+            vs[dst] = vs[src].push_back(42);
+            break;
+        }
+        case op_update: {
+            auto src = read<std::uint8_t>(in, is_valid_var);
+            auto idx = read<size_t>(in, is_valid_index(vs[src]));
+            IMMER_FUZZED_TRACE("v" << +dst << " = v" << +src << ".update("
+                                   << +idx
+                                   << ", [] (auto x) { return x + 1; });");
+            vs[dst] = vs[src].update(idx, [](auto x) { return x + 1; });
+            break;
+        }
+        case op_take: {
+            auto src = read<std::uint8_t>(in, is_valid_var);
+            auto idx = read<size_t>(in, is_valid_size(vs[src]));
+            IMMER_FUZZED_TRACE("v" << +dst << " = v" << +src << ".take(" << +idx
+                                   << ");");
+            vs[dst] = vs[src].take(idx);
+            break;
+        }
+        case op_drop: {
+            auto src = read<std::uint8_t>(in, is_valid_var);
+            auto idx = read<size_t>(in, is_valid_size(vs[src]));
+            IMMER_FUZZED_TRACE("v" << +dst << " = v" << +src << ".take(" << +idx
+                                   << ");");
+            vs[dst] = vs[src].drop(idx);
+            break;
+        }
+        case op_concat: {
+            auto src  = read<std::uint8_t>(in, is_valid_var);
+            auto src2 = read<std::uint8_t>(in, is_valid_var);
+            if (can_concat(vs[src], vs[src2])) {
+                IMMER_FUZZED_TRACE("v" << +dst << " = v" << +src << " + v"
+                                       << +src2 << ";");
+                vs[dst] = vs[src] + vs[src2];
+            }
+            break;
+        }
+        case op_push_back_mut: {
+            IMMER_FUZZED_TRACE("t" << +dst << ".push_back(13);");
+            ts[dst].push_back(13);
+            break;
+        }
+        case op_update_mut: {
+            auto idx = read<size_t>(in, is_valid_index(ts[dst]));
+            IMMER_FUZZED_TRACE("t" << +dst << ".update(" << +idx
+                                   << ", [] (auto x) { return x + 1; });");
+            ts[dst].update(idx, [](auto x) { return x + 1; });
+            break;
+        }
+        case op_take_mut: {
+            auto idx = read<size_t>(in, is_valid_size(ts[dst]));
+            IMMER_FUZZED_TRACE("t" << +dst << ").take(" << +idx << ");");
+            ts[dst].take(idx);
+            break;
+        }
+        case op_prepend_mut: {
+            auto src = read<std::uint8_t>(in, is_valid_var_neq(dst));
+            if (can_concat(ts[dst], ts[src])) {
+                IMMER_FUZZED_TRACE("t" << +dst << ".prepend(t" << +src << ");");
+                ts[dst].prepend(ts[src]);
+            }
+            break;
+        }
+        case op_prepend_mut_move: {
+            auto src = read<std::uint8_t>(in, is_valid_var_neq(dst));
+            if (can_concat(ts[dst], ts[src])) {
+                IMMER_FUZZED_TRACE("t" << +dst << ".prepend(std::move(t" << +src
+                                       << "));"
+                                       << " t" << +src << " = {};");
+                ts[dst].prepend(std::move(ts[src]));
+                ts[src] = {};
+            }
+            break;
+        }
+        case op_append_mut: {
+            auto src = read<std::uint8_t>(in, is_valid_var_neq(dst));
+            if (can_concat(ts[dst], ts[src])) {
+                IMMER_FUZZED_TRACE("t" << +dst << ".append(t" << +src << ");");
+                ts[dst].append(ts[src]);
+            }
+            break;
+        }
+        case op_append_mut_move: {
+            auto src = read<std::uint8_t>(in, is_valid_var_neq(dst));
+            if (can_concat(ts[dst], ts[src])) {
+                IMMER_FUZZED_TRACE("t" << +dst << ".append(std::move(t" << +src
+                                       << "));"
+                                       << " t" << +src << " = {};");
+                ts[dst].append(std::move(ts[src]));
+                ts[src] = {};
+            }
+            break;
+        }
+        default:
+            break;
+        };
+        return true;
+    });
+}
+
+} // namespace
+
+TEST_CASE("bug: concatenating transients")
+{
+    // When concatenating two transients vectors the nodes from the
+    // argument become aliased in the result.  As such, we need to
+    // reset the identitiy of the argument.
+    SECTION("simplified")
+    {
+        using vector_t = immer::flex_vector<int, gc_memory, 2, 2>;
+        auto t0        = vector_t{}.transient();
+        t0.push_back(42);
+        t0.push_back(42);
+        t0.push_back(42);
+        t0.push_back(42);
+        t0.push_back(42);
+        t0.push_back(42);
+        auto t1 = t0;
+        t1.append(t0);
+        t1.append(t0);
+        t0.append(t1);
+        t1.append(t0);
+    }
+
+#if __GNUC__ != 9
+    SECTION("")
+    {
+        constexpr std::uint8_t input[] = {
+            0x2, 0x2, 0x2, 0x2, 0x29, 0x32, 0x0, 0x0,  0x2,  0x2,  0x2,
+            0x2, 0x2, 0x2, 0x2, 0x2,  0x2,  0x2, 0x2,  0x2,  0x6,  0x2,
+            0x2, 0x2, 0x2, 0x2, 0x6,  0x2,  0x2, 0x2,  0x0,  0x38, 0x2,
+            0x0, 0x0, 0x2, 0x2, 0xd,  0x0,  0x0, 0x3b, 0xff, 0x3a, 0x2,
+            0xd, 0xd, 0x2, 0x0, 0x0,  0x10, 0xe, 0x0,  0xd,  0x0,  0x0,
+            0x2, 0x2, 0xd, 0x0, 0x1,  0x5,
+        };
+        CHECK(run_input(input, sizeof(input)) == 0);
+    }
+#endif
+}
+
+TEST_CASE("bug: concatenating moved transients")
+{
+    // A moved from concatenated transient is totally smashed, we can
+    // not do anything with it but reasign...
+    SECTION("simplified")
+    {
+        using vector_t    = immer::flex_vector<int, gc_memory, 2, 2>;
+        using transient_t = typename vector_t::transient_type;
+        auto v0           = vector_t{};
+        auto t0           = transient_t{};
+        auto t2           = transient_t{};
+        v0                = v0.push_back(42);
+        t2                = v0.transient();
+        v0                = v0 + v0;
+        v0                = v0 + v0;
+        v0                = v0 + v0;
+        v0                = v0 + v0;
+        t0                = v0.transient();
+        t0                = v0.transient();
+        t0.append(std::move(t2));
+        t2 = {};
+        t2.append(std::move(t0));
+    }
+
+#if __GNUC__ != 9
+    SECTION("")
+    {
+        constexpr std::uint8_t input[] = {
+            0x0,  0x2, 0x0,  0x2,  0x0,  0x0,  0x0,  0x6,  0x0,  0x0,  0x0,
+            0x6,  0x0, 0x0,  0x0,  0x9d, 0x0,  0x6,  0x0,  0x0,  0x0,  0x6,
+            0x0,  0x0, 0x0,  0x9d, 0x28, 0x0,  0x0,  0x0,  0x0,  0x0,  0xf7,
+            0xc5, 0x0, 0xa,  0xa,  0x0,  0xfa, 0xe7, 0xff, 0xe7, 0xff, 0x0,
+            0xe,  0x2, 0x9,  0x0,  0x28, 0x2,  0xe,  0x0,  0x0,  0x2,  0xd,
+            0x0,  0x0, 0x28, 0x0,  0xd,  0x2,  0x5,  0x0,  0x2,
+        };
+        CHECK(run_input(input, sizeof(input)) == 0);
+    }
+#endif
+
+    SECTION("simplified")
+    {
+        using vector_t    = immer::flex_vector<int, gc_memory, 2, 2>;
+        using transient_t = typename vector_t::transient_type;
+        auto v0           = vector_t{};
+        auto t0           = transient_t{};
+        auto t2           = transient_t{};
+        v0                = v0.push_back(42);
+        v0                = v0.push_back(42);
+        v0                = v0 + v0;
+        t0                = v0.transient();
+        t2.prepend(std::move(t0));
+        t0 = {};
+        t0 = v0.transient();
+        t0.push_back(13);
+        t2.append(std::move(t0));
+        t0 = {};
+        t0 = v0.transient();
+        t0.push_back(13);
+        t2.prepend(std::move(t0));
+        t0 = {};
+    }
+
+#if __GNUC__ != 9
+    SECTION("")
+    {
+        return;
+        constexpr std::uint8_t input[] = {
+            0x0,  0x2, 0x0,  0x0,  0x2, 0xb7, 0x1, 0x36, 0x40, 0x0,  0x0,
+            0x0,  0x0, 0xb6, 0x0,  0x2, 0x0,  0x0, 0x6,  0xe,  0x0,  0x0,
+            0xfe, 0x0, 0x0,  0xff, 0x0, 0x2,  0xc, 0xff, 0xfc, 0x29, 0x0,
+            0x0,  0x0, 0x0,  0x0,  0x7, 0x2,  0xe, 0xff, 0xfc, 0x29, 0x0,
+            0x0,  0x0, 0x0,  0x0,  0x7, 0x3,  0x0, 0x0,  0x2,  0xc,  0x2,
+            0xc,  0x0, 0xd,  0x0,  0x0, 0x0,  0x0, 0x25, 0x6,
+        };
+        CHECK(run_input(input, sizeof(input)) == 0);
+    }
+#endif
+}
+
+TEST_CASE("bug: aegsdas")
+{
+    SECTION("simplified")
+    {
+        using vector_t    = immer::flex_vector<int, gc_memory, 2, 2>;
+        using transient_t = typename vector_t::transient_type;
+        auto v2           = vector_t{};
+        auto t0           = transient_t{};
+        auto t1           = transient_t{};
+        v2                = v2.push_back(42);
+        v2                = v2.push_back(42);
+        v2                = v2.push_back(42);
+        v2                = v2.push_back(42);
+        v2                = v2.push_back(42);
+        t0                = v2.transient();
+        t1.prepend(t0);
+        t1.prepend(t0);
+        t1.prepend(t0);
+        t0.prepend(std::move(t1));
+        t1 = {};
+    }
+
+#if __GNUC__ != 9
+    SECTION("")
+    {
+        constexpr std::uint8_t input[] = {
+            0xff, 0xff, 0x2, 0x2,  0x2, 0x2,  0x2,  0x2,  0x2,  0x2,  0x2,
+            0x82, 0x2,  0x2, 0x2,  0x2, 0x2,  0x2,  0x0,  0x0,  0x3d, 0x0,
+            0x0,  0x0,  0x2, 0x84, 0x0, 0x3b, 0x1,  0xb,  0x0,  0xa,  0x1,
+            0xb,  0x0,  0x0, 0x3,  0x2, 0x0,  0x3b, 0x1,  0xb,  0x1,  0x0,
+            0x0,  0xc,  0xb, 0x1,  0x8, 0xff, 0xff, 0xfc, 0xfd, 0x0,  0x3b,
+            0x3,  0x2,  0x0, 0x3b, 0x1, 0x9,  0x1,  0x3b,
+        };
+        CHECK(run_input(input, sizeof(input)) == 0);
+    }
+#endif
+}
diff --git a/third_party/immer/test/flex_vector/gc.cpp b/third_party/immer/test/flex_vector/gc.cpp
new file mode 100644
index 000000000000..57b97f5ed7d7
--- /dev/null
+++ b/third_party/immer/test/flex_vector/gc.cpp
@@ -0,0 +1,27 @@
+//
+// 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/heap/gc_heap.hpp>
+#include <immer/refcount/no_refcount_policy.hpp>
+#include <immer/vector.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>;
+
+#define FLEX_VECTOR_T test_flex_vector_t
+#define VECTOR_T test_vector_t
+#include "generic.ipp"
diff --git a/third_party/immer/test/flex_vector/generic.ipp b/third_party/immer/test/flex_vector/generic.ipp
new file mode 100644
index 000000000000..6dbd73f07cb6
--- /dev/null
+++ b/third_party/immer/test/flex_vector/generic.ipp
@@ -0,0 +1,599 @@
+//
+// 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 VECTOR_T
+#error "define the vector template to use in VECTOR_T"
+#endif
+
+template <typename V = FLEX_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;
+}
+
+template <std::size_t N>
+auto make_many_test_flex_vector()
+{
+    using vektor_t = FLEX_VECTOR_T<unsigned>;
+    auto many      = std::array<vektor_t, N>{};
+    std::generate_n(many.begin(), N, [v = vektor_t{}, i = 0u]() mutable {
+        auto r = v;
+        v      = v.push_back(i++);
+        return r;
+    });
+    return many;
+}
+
+template <std::size_t N>
+auto make_many_test_flex_vector_front()
+{
+    using vektor_t = FLEX_VECTOR_T<unsigned>;
+    auto many      = std::array<vektor_t, N>{};
+    std::generate_n(many.begin(), N, [i = 0u]() mutable {
+        return make_test_flex_vector_front(0, i++);
+    });
+    return many;
+}
+
+template <std::size_t N>
+auto make_many_test_flex_vector_front_remainder()
+{
+    using vektor_t = FLEX_VECTOR_T<unsigned>;
+    auto many      = std::array<vektor_t, N>{};
+    std::generate_n(many.begin(), N, [v = vektor_t{}, i = N - 1]() mutable {
+        auto r = v;
+        v      = v.push_front(--i);
+        return r;
+    });
+    return many;
+}
+
+TEST_CASE("set relaxed")
+{
+    auto v = make_test_flex_vector_front(0, 666u);
+    for (decltype(v.size()) i = 0; i < v.size(); ++i) {
+        v = v.set(i, i + 1);
+        CHECK(v[i] == i + 1);
+    }
+}
+
+TEST_CASE("push_front")
+{
+    const auto n = 666u;
+    auto v       = FLEX_VECTOR_T<unsigned>{};
+
+    for (auto i = 0u; i < n; ++i) {
+        v = v.push_front(i);
+        CHECK(v.size() == i + 1);
+        for (decltype(v.size()) j = 0; j < v.size(); ++j)
+            CHECK(v[v.size() - j - 1] == j);
+    }
+}
+
+TEST_CASE("concat")
+{
+#if IMMER_SLOW_TESTS
+    constexpr auto n = 666u;
+#else
+    constexpr auto n = 101u;
+#endif
+
+    auto all_lhs = make_many_test_flex_vector<n>();
+    auto all_rhs = make_many_test_flex_vector_front_remainder<n>();
+
+    SECTION("regular plus regular")
+    {
+        for (auto i : test_irange(0u, n)) {
+            auto c = all_lhs[i] + all_lhs[i];
+            CHECK_VECTOR_EQUALS(
+                c, boost::join(boost::irange(0u, i), boost::irange(0u, i)));
+        }
+    }
+
+    SECTION("regular plus relaxed")
+    {
+        for (auto i : test_irange(0u, n)) {
+            auto c = all_lhs[i] + all_rhs[n - i - 1];
+            CHECK_VECTOR_EQUALS(c, boost::irange(0u, n - 1));
+        }
+    }
+}
+
+auto make_flex_vector_concat(std::size_t min, std::size_t max)
+{
+    using vektor_t = FLEX_VECTOR_T<unsigned>;
+
+    if (max == min)
+        return vektor_t{};
+    else if (max == min + 1)
+        return vektor_t{}.push_back(min);
+    else {
+        auto mid = min + (max - min) / 2;
+        return make_flex_vector_concat(min, mid) +
+               make_flex_vector_concat(mid, max);
+    }
+}
+
+TEST_CASE("concat recursive")
+{
+    const auto n = 666u;
+    auto v       = make_flex_vector_concat(0, n);
+    CHECK_VECTOR_EQUALS(v, boost::irange(0u, n));
+}
+
+TEST_CASE("insert")
+{
+    SECTION("normal")
+    {
+        const auto n = 666u;
+        auto v       = make_test_flex_vector(0, n);
+        v            = v.insert(42, 100);
+        CHECK_VECTOR_EQUALS(v,
+                            boost::join(boost::irange(0u, 42u),
+                                        boost::join(boost::irange(100u, 101u),
+                                                    boost::irange(42u, n))));
+    }
+
+    SECTION("move")
+    {
+        const auto n = 666u;
+        auto v       = make_test_flex_vector(0, n);
+        v            = std::move(v).insert(42, 100);
+        CHECK_VECTOR_EQUALS(v,
+                            boost::join(boost::irange(0u, 42u),
+                                        boost::join(boost::irange(100u, 101u),
+                                                    boost::irange(42u, n))));
+    }
+
+    SECTION("vec")
+    {
+        const auto n = 666u;
+        auto v       = make_test_flex_vector(0, n);
+        v            = std::move(v).insert(42, {100, 101, 102});
+        CHECK_VECTOR_EQUALS(v,
+                            boost::join(boost::irange(0u, 42u),
+                                        boost::join(boost::irange(100u, 103u),
+                                                    boost::irange(42u, n))));
+    }
+
+    SECTION("vec move")
+    {
+        const auto n = 666u;
+        auto v       = make_test_flex_vector(0, n);
+        v            = std::move(v).insert(42, {100, 101, 102});
+        CHECK_VECTOR_EQUALS(v,
+                            boost::join(boost::irange(0u, 42u),
+                                        boost::join(boost::irange(100u, 103u),
+                                                    boost::irange(42u, n))));
+    }
+}
+
+TEST_CASE("erase")
+{
+    const auto n = 666u;
+    auto v       = make_test_flex_vector(0, n);
+    auto vv      = v.erase(0);
+    CHECK_VECTOR_EQUALS(vv, boost::irange(1u, n));
+    CHECK_VECTOR_EQUALS(v.erase(v.size() - 1), boost::irange(0u, n - 1));
+    CHECK_VECTOR_EQUALS(v.erase(v.size() - 1), boost::irange(0u, n - 1));
+    CHECK_VECTOR_EQUALS(
+        v.erase(42),
+        boost::join(boost::irange(0u, 42u), boost::irange(43u, n)));
+    CHECK_VECTOR_EQUALS(v.erase(v.size() - 1, v.size()),
+                        boost::irange(0u, n - 1));
+    CHECK_VECTOR_EQUALS(v.erase(0, 0), boost::irange(0u, n));
+    CHECK_VECTOR_EQUALS(
+        v.erase(42, 50),
+        boost::join(boost::irange(0u, 42u), boost::irange(50u, n)));
+}
+
+TEST_CASE("accumulate relaxed")
+{
+    auto expected_n = [](auto n) { return n * (n - 1) / 2; };
+    auto expected_i = [&](auto i, auto n) {
+        return expected_n(n) - expected_n(i);
+    };
+
+    SECTION("sum")
+    {
+        const auto n = 666u;
+        auto v       = make_test_flex_vector_front(0, n);
+
+        auto sum      = immer::accumulate(v, 0u);
+        auto expected = v.size() * (v.size() - 1) / 2;
+        CHECK(sum == expected);
+    }
+
+    SECTION("sum complex")
+    {
+        const auto n = 20u;
+
+        auto v = FLEX_VECTOR_T<unsigned>{};
+        for (auto i = 0u; i < n; ++i)
+            v = v.push_front(i) + v;
+
+        auto sum      = immer::accumulate(v, 0u);
+        auto expected = (1 << n) - n - 1;
+        CHECK(sum == expected);
+    }
+
+    SECTION("sum range")
+    {
+        using namespace std;
+        const auto n = 666u;
+        auto v       = make_test_flex_vector_front(0, n);
+        {
+            auto sum = immer::accumulate(begin(v) + 100, begin(v) + 300, 0u);
+            CHECK(sum == expected_i(100, 300));
+        }
+        {
+            auto sum = immer::accumulate(begin(v) + 31, begin(v) + 300, 0u);
+            CHECK(sum == expected_i(31, 300));
+        }
+        {
+            auto sum = immer::accumulate(begin(v), begin(v) + 33, 0u);
+            CHECK(sum == expected_i(0, 33));
+        }
+        {
+            auto sum = immer::accumulate(begin(v) + 100, begin(v) + 660, 0u);
+            CHECK(sum == expected_i(100, 660));
+        }
+        {
+            auto sum = immer::accumulate(begin(v) + 100, begin(v) + 105, 0u);
+            CHECK(sum == expected_i(100, 105));
+        }
+        {
+            auto sum = immer::accumulate(begin(v) + 660, begin(v) + 664, 0u);
+            CHECK(sum == expected_i(660, 664));
+        }
+    }
+}
+
+TEST_CASE("equals")
+{
+    const auto n = 666u;
+    auto v       = make_test_flex_vector_front(0, n);
+
+    CHECK(v == v);
+    CHECK(v == v.set(42, 42));
+    CHECK(v != v.set(42, 24));
+    CHECK(v == v.set(42, 24).set(42, 42));
+    CHECK(v.set(42, 24) == v.set(42, 24));
+    CHECK(v != v.push_back(7));
+    CHECK(v.push_back(7) == v.push_back(7));
+    CHECK(v.push_back(5) != v.push_back(7));
+    CHECK(v != v.set(v.size() - 2, 24));
+    CHECK(v == v.set(v.size() - 2, 24).set(v.size() - 2, v[v.size() - 2]));
+    CHECK(v == v.insert(42, 12).erase(42));
+    CHECK(v == v.insert(0, 12).erase(0));
+}
+
+TEST_CASE("equals bugs")
+{
+    {
+        const auto n = 666u;
+        auto v       = make_test_flex_vector(0, n);
+        CHECK(v == v.insert(42, 12).erase(42));
+        CHECK(v == v.insert(0, 12).erase(0));
+    }
+    {
+        const auto n = 30u;
+        auto v       = make_test_flex_vector(0, n);
+        CHECK(v == v.insert(10, 12).erase(10));
+        CHECK(v == v.insert(0, 12).erase(0));
+    }
+    {
+        const auto n = 666u;
+        auto v       = make_test_flex_vector(0, n);
+        for (auto i : test_irange(0u, n))
+            CHECK(v == v.insert(i, 42).erase(i));
+    }
+    {
+        const auto n = 666u;
+        auto v       = make_test_flex_vector_front(0, n);
+        for (auto i : test_irange(0u, n))
+            CHECK(v == v.insert(i, 42).erase(i));
+    }
+    {
+        const auto n = 666u;
+        auto v       = FLEX_VECTOR_T<unsigned>{};
+        using size_t = decltype(v.size());
+        for (auto i : test_irange(0u, n)) {
+            while (v.size() < i)
+                v = std::move(v).push_back(i);
+            auto vv = v;
+            for (auto j : test_irange(size_t{}, v.size())) {
+                auto vz = vv.insert(j, 42).erase(j);
+                CHECK(v == vz);
+                CHECK(vv == vz);
+                vv = vz;
+            }
+        }
+    }
+}
+
+TEST_CASE("take relaxed")
+{
+    const auto n = 666u;
+    auto v       = make_test_flex_vector_front(0, n);
+
+    for (auto i : test_irange(0u, n)) {
+        auto vv = v.take(i);
+        CHECK_VECTOR_EQUALS_RANGE(vv, v.begin(), v.begin() + i);
+    }
+}
+
+TEST_CASE("drop")
+{
+    const auto n = 666u;
+
+    SECTION("regular")
+    {
+        auto v = make_test_flex_vector(0, n);
+
+        for (auto i : test_irange(0u, n)) {
+            auto vv = v.drop(i);
+            CHECK_VECTOR_EQUALS_RANGE(vv, v.begin() + i, v.end());
+        }
+    }
+
+    SECTION("relaxed")
+    {
+        auto v = make_test_flex_vector_front(0, n);
+
+        for (auto i : test_irange(0u, n)) {
+            auto vv = v.drop(i);
+            CHECK_VECTOR_EQUALS_RANGE(vv, v.begin() + i, v.end());
+        }
+    }
+}
+
+#if IMMER_SLOW_TESTS
+TEST_CASE("reconcat")
+{
+    constexpr auto n = 666u;
+    auto v           = make_test_flex_vector_front(0, n);
+    auto all_lhs     = make_many_test_flex_vector_front<n + 1>();
+    auto all_rhs     = make_many_test_flex_vector_front_remainder<n + 1>();
+
+    for (auto i = 0u; i < n; ++i) {
+        auto vv = all_lhs[i] + all_rhs[n - i];
+        CHECK_VECTOR_EQUALS(vv, v);
+        CHECK_SLOW(vv == v);
+    }
+}
+
+TEST_CASE("reconcat drop")
+{
+    constexpr auto n = 666u;
+    auto v           = make_test_flex_vector_front(0, n);
+    auto all_lhs     = make_many_test_flex_vector_front<n + 1>();
+
+    for (auto i = 0u; i < n; ++i) {
+        auto vv = all_lhs[i] + v.drop(i);
+        CHECK_VECTOR_EQUALS(vv, v);
+        CHECK_SLOW(vv == v);
+    }
+}
+
+TEST_CASE("reconcat take")
+{
+    constexpr auto n = 666u;
+    auto v           = make_test_flex_vector_front(0, n);
+    auto all_rhs     = make_many_test_flex_vector_front_remainder<n + 1>();
+
+    for (auto i = 0u; i < n; ++i) {
+        auto vv = v.take(i) + all_rhs[n - i];
+        CHECK_VECTOR_EQUALS(vv, v);
+        CHECK_SLOW(vv == v);
+    }
+}
+#endif
+
+TEST_CASE("reconcat take drop")
+{
+    const auto n = 666u;
+    auto v       = make_test_flex_vector_front(0, n);
+
+    for (auto i : test_irange(0u, n)) {
+        auto vv = v.take(i) + v.drop(i);
+        CHECK_VECTOR_EQUALS(vv, v);
+        CHECK_SLOW(vv == v);
+    }
+}
+
+TEST_CASE("reconcat take drop feedback")
+{
+    const auto n = 666u;
+    auto v       = make_test_flex_vector_front(0, n);
+    auto vv      = v;
+    for (auto i : test_irange(0u, n)) {
+        vv = vv.take(i) + vv.drop(i);
+        CHECK_VECTOR_EQUALS(vv, v);
+        CHECK_SLOW(vv == v);
+    }
+}
+
+TEST_CASE("iterator relaxed")
+{
+    const auto n = 666u;
+    auto v       = make_test_flex_vector_front(0, n);
+
+    SECTION("works with range loop")
+    {
+        auto i = 0u;
+        for (const auto& x : v)
+            CHECK(x == i++);
+        CHECK(i == 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("can go back from end")
+    {
+        auto expected = n - 1;
+        CHECK(expected == *--v.end());
+    }
+
+    SECTION("works with reversed range adaptor")
+    {
+        auto r = v | boost::adaptors::reversed;
+        auto i = n;
+        for (const auto& x : r)
+            CHECK(x == --i);
+    }
+
+    SECTION("works with strided range adaptor")
+    {
+        auto r = v | boost::adaptors::strided(5);
+        auto i = 0u;
+        for (const auto& x : r)
+            CHECK(x == 5 * i++);
+    }
+
+    SECTION("works reversed")
+    {
+        auto i = n;
+        for (auto iter = v.rbegin(), last = v.rend(); iter != last; ++iter)
+            CHECK(*iter == --i);
+    }
+
+    SECTION("advance and distance")
+    {
+        auto i1 = v.begin();
+        auto i2 = i1 + 100;
+        CHECK(100u == *i2);
+        CHECK(100 == i2 - i1);
+        CHECK(50u == *(i2 - 50));
+        CHECK(-30 == (i2 - 30) - i2);
+    }
+}
+
+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_T<unsigned>{v};
+        CHECK_VECTOR_EQUALS_AUX(v, fv, [](auto&& v) { return &v; });
+    }
+}
+
+TEST_CASE("exception safety relaxed")
+{
+    using dadaist_vector_t =
+        typename dadaist_wrapper<FLEX_VECTOR_T<unsigned>>::type;
+    constexpr auto n = 666u;
+
+    SECTION("push back")
+    {
+        auto half = n / 2;
+        auto v    = make_test_flex_vector_front<dadaist_vector_t>(0, half);
+        auto d    = dadaism{};
+        for (auto i = half; v.size() < static_cast<decltype(v.size())>(n);) {
+            auto s = d.next();
+            try {
+                v = v.push_back({i});
+                ++i;
+            } catch (dada_error) {}
+            CHECK_VECTOR_EQUALS(v, boost::irange(0u, i));
+        }
+        CHECK(d.happenings > 0);
+        IMMER_TRACE_E(d.happenings);
+    }
+
+    SECTION("update")
+    {
+        auto v = make_test_flex_vector_front<dadaist_vector_t>(0, n);
+        auto d = dadaism{};
+        for (auto i = 0u; i < n;) {
+            auto s = d.next();
+            try {
+                v = v.update(i, [](auto x) { return dada(), x + 1; });
+                ++i;
+            } catch (dada_error) {}
+            CHECK_VECTOR_EQUALS(
+                v, boost::join(boost::irange(1u, 1u + i), boost::irange(i, n)));
+        }
+        CHECK(d.happenings > 0);
+        IMMER_TRACE_E(d.happenings);
+    }
+
+    SECTION("take")
+    {
+        auto v = make_test_flex_vector_front<dadaist_vector_t>(0, n);
+        auto d = dadaism{};
+        for (auto i = 0u; i < n;) {
+            auto s = d.next();
+            auto r = dadaist_vector_t{};
+            try {
+                r = v.take(i);
+                CHECK_VECTOR_EQUALS(r, boost::irange(0u, i++));
+            } catch (dada_error) {
+                CHECK_VECTOR_EQUALS(r, boost::irange(0u, 0u));
+            }
+        }
+        CHECK(d.happenings > 0);
+        IMMER_TRACE_E(d.happenings);
+    }
+
+    SECTION("concat")
+    {
+        auto v = make_test_flex_vector<dadaist_vector_t>(0, n);
+        auto d = dadaism{};
+        for (auto i = 0u; i < n;) {
+            auto lhs = v.take(i);
+            auto rhs = v.drop(i);
+            auto s   = d.next();
+            try {
+                v = lhs + rhs;
+                ++i;
+            } catch (dada_error) {}
+            CHECK_VECTOR_EQUALS(v, boost::irange(0u, n));
+        }
+        CHECK(d.happenings > 0);
+        IMMER_TRACE_E(d.happenings);
+    }
+}
diff --git a/third_party/immer/test/flex_vector/issue-45.cpp b/third_party/immer/test/flex_vector/issue-45.cpp
new file mode 100644
index 000000000000..76bd77b2e240
--- /dev/null
+++ b/third_party/immer/test/flex_vector/issue-45.cpp
@@ -0,0 +1,35 @@
+//
+// 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
+//
+
+// Thanks Guiguiprim for reporting this issue
+// https://github.com/arximboldi/immer/issues/46
+
+#include <immer/flex_vector.hpp>
+#include <immer/vector.hpp>
+#include <immer/vector_transient.hpp>
+
+#include <catch.hpp>
+
+#if IMMER_CXX_STANDARD >= 17
+
+#include <variant>
+
+TEST_CASE("error when erasing an element from a "
+          "immer::flex_vector<std::variant/optional/any>")
+{
+    using Vector = immer::flex_vector<std::variant<int, double>>;
+    // using Vector = immer::flex_vector<std::optional<int>>;
+    // using Vector = immer::flex_vector<std::any>;
+
+    Vector v{1, 2, 3, 4};
+    Vector v2 = v.erase(2);
+
+    CHECK(v2.size() == 3);
+}
+
+#endif
diff --git a/third_party/immer/test/flex_vector/issue-47.cpp b/third_party/immer/test/flex_vector/issue-47.cpp
new file mode 100644
index 000000000000..7757fe4ee4e5
--- /dev/null
+++ b/third_party/immer/test/flex_vector/issue-47.cpp
@@ -0,0 +1,5 @@
+#include <immer/flex_vector.hpp>
+
+immer::flex_vector<int> v{1};
+
+int main() { return 0; }
diff --git a/third_party/immer/test/flex_vector/regular-B3-BL3.cpp b/third_party/immer/test/flex_vector/regular-B3-BL3.cpp
new file mode 100644
index 000000000000..fb5d13d1aa8e
--- /dev/null
+++ b/third_party/immer/test/flex_vector/regular-B3-BL3.cpp
@@ -0,0 +1,16 @@
+//
+// 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>
+
+template <typename T>
+using test_vector_t =
+    immer::flex_vector<T, immer::default_memory_policy, 3u, 3u>;
+
+#define VECTOR_T test_vector_t
+#include "../vector/generic.ipp"
diff --git a/third_party/immer/test/flex_vector/regular-default.cpp b/third_party/immer/test/flex_vector/regular-default.cpp
new file mode 100644
index 000000000000..8f28c3d8099f
--- /dev/null
+++ b/third_party/immer/test/flex_vector/regular-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/flex_vector.hpp>
+
+#define VECTOR_T ::immer::flex_vector
+#include "../vector/generic.ipp"
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"
diff --git a/third_party/immer/test/map/B3.cpp b/third_party/immer/test/map/B3.cpp
new file mode 100644
index 000000000000..61458a013537
--- /dev/null
+++ b/third_party/immer/test/map/B3.cpp
@@ -0,0 +1,18 @@
+//
+// 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/map.hpp>
+
+template <typename K,
+          typename T,
+          typename Hash = std::hash<K>,
+          typename Eq   = std::equal_to<K>>
+using test_map_t = immer::map<K, T, Hash, Eq, immer::default_memory_policy, 3u>;
+
+#define MAP_T test_map_t
+#include "generic.ipp"
diff --git a/third_party/immer/test/map/B6.cpp b/third_party/immer/test/map/B6.cpp
new file mode 100644
index 000000000000..52da689c67b6
--- /dev/null
+++ b/third_party/immer/test/map/B6.cpp
@@ -0,0 +1,18 @@
+//
+// 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/map.hpp>
+
+template <typename K,
+          typename T,
+          typename Hash = std::hash<K>,
+          typename Eq   = std::equal_to<K>>
+using test_map_t = immer::map<K, T, Hash, Eq, immer::default_memory_policy, 6u>;
+
+#define MAP_T test_map_t
+#include "generic.ipp"
diff --git a/third_party/immer/test/map/default.cpp b/third_party/immer/test/map/default.cpp
new file mode 100644
index 000000000000..cb453c4f81e2
--- /dev/null
+++ b/third_party/immer/test/map/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/map.hpp>
+
+#define MAP_T ::immer::map
+#include "generic.ipp"
diff --git a/third_party/immer/test/map/gc.cpp b/third_party/immer/test/map/gc.cpp
new file mode 100644
index 000000000000..818fb03aaa5b
--- /dev/null
+++ b/third_party/immer/test/map/gc.cpp
@@ -0,0 +1,25 @@
+//
+// 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/map.hpp>
+#include <immer/refcount/no_refcount_policy.hpp>
+
+using gc_memory = immer::memory_policy<immer::heap_policy<immer::gc_heap>,
+                                       immer::no_refcount_policy,
+                                       immer::gc_transience_policy,
+                                       false>;
+
+template <typename K,
+          typename T,
+          typename Hash = std::hash<K>,
+          typename Eq   = std::equal_to<K>>
+using test_map_t = immer::map<K, T, Hash, Eq, gc_memory, 3u>;
+
+#define MAP_T test_map_t
+#include "generic.ipp"
diff --git a/third_party/immer/test/map/generic.ipp b/third_party/immer/test/map/generic.ipp
new file mode 100644
index 000000000000..18fc9d11f567
--- /dev/null
+++ b/third_party/immer/test/map/generic.ipp
@@ -0,0 +1,312 @@
+//
+// 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 MAP_T
+#error "define the map template to use in MAP_T"
+#include <immer/map.hpp>
+#define MAP_T ::immer::map
+#endif
+
+#include <immer/algorithm.hpp>
+
+#include "test/dada.hpp"
+#include "test/util.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<std::pair<conflictor, unsigned>>{};
+    auto vals_ = std::unordered_set<conflictor, hash_conflictor>{};
+    auto i     = 0u;
+    generate_n(back_inserter(vals), n, [&] {
+        auto newv = conflictor{};
+        do {
+            newv = {unsigned(gen() % (n / 2)), gen()};
+        } while (!vals_.insert(newv).second);
+        return std::pair<conflictor, unsigned>{newv, i++};
+    });
+    return vals;
+}
+
+auto make_test_map(unsigned n)
+{
+    auto s = MAP_T<unsigned, unsigned>{};
+    for (auto i = 0u; i < n; ++i)
+        s = s.insert({i, i});
+    return s;
+}
+
+auto make_test_map(const std::vector<std::pair<conflictor, unsigned>>& vals)
+{
+    auto s = MAP_T<conflictor, unsigned, hash_conflictor>{};
+    for (auto&& v : vals)
+        s = s.insert(v);
+    return s;
+}
+
+TEST_CASE("instantiation")
+{
+    SECTION("default")
+    {
+        auto v = MAP_T<int, int>{};
+        CHECK(v.size() == 0u);
+    }
+}
+
+TEST_CASE("basic insertion")
+{
+    auto v1 = MAP_T<int, int>{};
+    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("accessor")
+{
+    const auto n = 666u;
+    auto v       = make_test_map(n);
+    CHECK(v[0] == 0);
+    CHECK(v[42] == 42);
+    CHECK(v[665] == 665);
+    CHECK(v[666] == 0);
+    CHECK(v[1234] == 0);
+}
+
+TEST_CASE("at")
+{
+    const auto n = 666u;
+    auto v       = make_test_map(n);
+    CHECK(v.at(0) == 0);
+    CHECK(v.at(42) == 42);
+    CHECK(v.at(665) == 665);
+    CHECK_THROWS_AS(v.at(666), std::out_of_range&);
+    CHECK_THROWS_AS(v.at(1234), std::out_of_range&);
+}
+
+TEST_CASE("find")
+{
+    const auto n = 666u;
+    auto v       = make_test_map(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("equals and setting")
+{
+    const auto n = 666u;
+    auto v       = make_test_map(n);
+
+    CHECK(v == v);
+    CHECK(v != v.insert({1234, 42}));
+    CHECK(v != v.erase(32));
+    CHECK(v == v.insert({1234, 42}).erase(1234));
+    CHECK(v == v.erase(32).insert({32, 32}));
+
+    CHECK(v.set(1234, 42) == v.insert({1234, 42}));
+    CHECK(v.update(1234, [](auto&& x) { return x + 1; }) == v.set(1234, 1));
+    CHECK(v.update(42, [](auto&& x) { return x + 1; }) == v.set(42, 43));
+}
+
+TEST_CASE("iterator")
+{
+    const auto N = 666u;
+    auto v       = make_test_map(N);
+
+    SECTION("empty set")
+    {
+        auto s = MAP_T<unsigned, 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.first).second);
+        CHECK(seen.size() == v.size());
+    }
+
+    SECTION("iterator and collisions")
+    {
+        auto vals = make_values_with_collisions(N);
+        auto s    = make_test_map(vals);
+        auto seen = std::unordered_set<conflictor, hash_conflictor>{};
+        for (const auto& x : s)
+            CHECK(seen.insert(x.first).second);
+        CHECK(seen.size() == s.size());
+    }
+}
+
+TEST_CASE("accumulate")
+{
+    const auto n = 666u;
+    auto v       = make_test_map(n);
+
+    auto expected_n = [](auto n) { return n * (n - 1) / 2; };
+
+    SECTION("sum collection")
+    {
+        auto acc = [](unsigned acc, const std::pair<unsigned, unsigned>& x) {
+            return acc + x.first + x.second;
+        };
+        auto sum = immer::accumulate(v, 0u, acc);
+        CHECK(sum == 2 * expected_n(v.size()));
+    }
+
+    SECTION("sum collisions")
+    {
+        auto vals = make_values_with_collisions(n);
+        auto s    = make_test_map(vals);
+        auto acc  = [](unsigned r, std::pair<conflictor, unsigned> x) {
+            return r + x.first.v1 + x.first.v2 + x.second;
+        };
+        auto sum1 = std::accumulate(vals.begin(), vals.end(), 0u, acc);
+        auto sum2 = immer::accumulate(s, 0u, acc);
+        CHECK(sum1 == sum2);
+    }
+}
+
+TEST_CASE("update a lot")
+{
+    auto v = make_test_map(666u);
+
+    for (decltype(v.size()) i = 0; i < v.size(); ++i) {
+        v = v.update(i, [](auto&& x) { return x + 1; });
+        CHECK(v[i] == i + 1);
+    }
+}
+
+TEST_CASE("exception safety")
+{
+    constexpr auto n = 2666u;
+
+    using dadaist_map_t =
+        typename dadaist_wrapper<MAP_T<unsigned, unsigned>>::type;
+    using dadaist_conflictor_map_t = typename dadaist_wrapper<
+        MAP_T<conflictor, unsigned, hash_conflictor>>::type;
+
+    SECTION("update collisions")
+    {
+        auto v = dadaist_map_t{};
+        auto d = dadaism{};
+        for (auto i = 0u; i < n; ++i)
+            v = v.set(i, i);
+        for (auto i = 0u; i < v.size();) {
+            try {
+                auto s = d.next();
+                v      = v.update(i, [](auto x) { return x + 1; });
+                ++i;
+            } catch (dada_error) {}
+            for (auto i : test_irange(0u, i))
+                CHECK(v.at(i) == i + 1);
+            for (auto i : test_irange(i, n))
+                CHECK(v.at(i) == i);
+        }
+        CHECK(d.happenings > 0);
+        IMMER_TRACE_E(d.happenings);
+    }
+
+    SECTION("update collisisions")
+    {
+        auto vals = make_values_with_collisions(n);
+        auto v    = dadaist_conflictor_map_t{};
+        auto d    = dadaism{};
+        for (auto i = 0u; i < n; ++i)
+            v = v.insert(vals[i]);
+        for (auto i = 0u; i < v.size();) {
+            try {
+                auto s = d.next();
+                v      = v.update(vals[i].first, [](auto x) { return x + 1; });
+                ++i;
+            } catch (dada_error) {}
+            for (auto i : test_irange(0u, i))
+                CHECK(v.at(vals[i].first) == vals[i].second + 1);
+            for (auto i : test_irange(i, n))
+                CHECK(v.at(vals[i].first) == vals[i].second);
+        }
+        CHECK(d.happenings > 0);
+        IMMER_TRACE_E(d.happenings);
+    }
+}
+
+namespace {
+
+class KElem
+{
+public:
+    KElem(int* elem) { this->elem = elem; }
+
+    bool operator==(const KElem& other) const
+    {
+        return this->elem == other.elem;
+    }
+
+    bool operator!=(const KElem& other) const { return !(*this == other); }
+
+    int* elem;
+};
+
+struct HashBlock
+{
+    size_t operator()(const KElem& block) const noexcept
+    {
+        return (uintptr_t) block.elem & 0xffffffff00000000;
+    }
+};
+
+using map = immer::map<KElem, KElem, HashBlock, std::equal_to<KElem>>;
+
+TEST_CASE("issue 134")
+{
+    int a[100];
+    map m;
+    for (int i = 0; i < 100; i++) {
+        m = m.set(KElem(a + i), KElem(a + i));
+    }
+}
+
+} // namespace
diff --git a/third_party/immer/test/map/issue-56.cpp b/third_party/immer/test/map/issue-56.cpp
new file mode 100644
index 000000000000..447c623ddad9
--- /dev/null
+++ b/third_party/immer/test/map/issue-56.cpp
@@ -0,0 +1,42 @@
+//
+// 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
+//
+
+// Thanks @dgel for reporting this issue
+// https://github.com/arximboldi/immer/issues/56
+
+#include <immer/flex_vector.hpp>
+#include <immer/map.hpp>
+#include <immer/vector.hpp>
+
+#include <catch.hpp>
+
+TEST_CASE("const map")
+{
+    const auto x = immer::map<std::string, int>{}.set("A", 1);
+    auto it      = x.begin();
+    CHECK(it->first == "A");
+    CHECK(it->second == 1);
+}
+
+TEST_CASE("const vector")
+{
+    const auto x =
+        immer::vector<std::pair<std::string, int>>{}.push_back({"A", 1});
+    auto it = x.begin();
+    CHECK(it->first == "A");
+    CHECK(it->second == 1);
+}
+
+TEST_CASE("const flex vector")
+{
+    const auto x =
+        immer::flex_vector<std::pair<std::string, int>>{}.push_back({"A", 1});
+    auto it = x.begin();
+    CHECK(it->first == "A");
+    CHECK(it->second == 1);
+}
diff --git a/third_party/immer/test/memory/heaps.cpp b/third_party/immer/test/memory/heaps.cpp
new file mode 100644
index 000000000000..94af2be20868
--- /dev/null
+++ b/third_party/immer/test/memory/heaps.cpp
@@ -0,0 +1,101 @@
+//
+// 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/cpp_heap.hpp>
+#include <immer/heap/free_list_heap.hpp>
+#include <immer/heap/gc_heap.hpp>
+#include <immer/heap/malloc_heap.hpp>
+#include <immer/heap/thread_local_free_list_heap.hpp>
+
+#include <catch.hpp>
+#include <numeric>
+
+void do_stuff_to(void* buf, std::size_t size)
+{
+    auto ptr = static_cast<unsigned char*>(buf);
+    CHECK(buf != 0);
+    std::iota(ptr, ptr + size, 42);
+}
+
+TEST_CASE("malloc")
+{
+    using heap = immer::malloc_heap;
+
+    SECTION("basic")
+    {
+        auto p = heap::allocate(42u);
+        do_stuff_to(p, 42u);
+        heap::deallocate(42, p);
+    }
+}
+
+TEST_CASE("gc")
+{
+    using heap = immer::gc_heap;
+
+    SECTION("basic")
+    {
+        auto p = heap::allocate(42u);
+        do_stuff_to(p, 42u);
+        heap::deallocate(42, p);
+    }
+}
+
+TEST_CASE("cpp")
+{
+    using heap = immer::cpp_heap;
+
+    SECTION("basic")
+    {
+        auto p = heap::allocate(42u);
+        do_stuff_to(p, 42u);
+        heap::deallocate(42, p);
+    }
+}
+
+template <typename Heap>
+void test_free_list_heap()
+{
+    using heap = Heap;
+
+    SECTION("basic")
+    {
+        auto p = heap::allocate(42u);
+        do_stuff_to(p, 42u);
+        heap::deallocate(42, p);
+    }
+
+    SECTION("reuse")
+    {
+        auto p = heap::allocate(42u);
+        do_stuff_to(p, 42u);
+        heap::deallocate(42, p);
+
+        auto u = heap::allocate(12u);
+        do_stuff_to(u, 12u);
+        heap::deallocate(12, u);
+        CHECK(u == p);
+    }
+}
+
+TEST_CASE("free list")
+{
+    test_free_list_heap<immer::free_list_heap<42u, 2, immer::malloc_heap>>();
+}
+
+TEST_CASE("thread local free list")
+{
+    test_free_list_heap<
+        immer::thread_local_free_list_heap<42u, 2, immer::malloc_heap>>();
+}
+
+TEST_CASE("unsafe free_list")
+{
+    test_free_list_heap<
+        immer::unsafe_free_list_heap<42u, 2, immer::malloc_heap>>();
+}
diff --git a/third_party/immer/test/memory/refcounts.cpp b/third_party/immer/test/memory/refcounts.cpp
new file mode 100644
index 000000000000..f9278ca7794e
--- /dev/null
+++ b/third_party/immer/test/memory/refcounts.cpp
@@ -0,0 +1,62 @@
+//
+// 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/refcount/no_refcount_policy.hpp>
+#include <immer/refcount/refcount_policy.hpp>
+#include <immer/refcount/unsafe_refcount_policy.hpp>
+
+#include <catch.hpp>
+
+TEST_CASE("no refcount has no data")
+{
+    static_assert(std::is_empty<immer::no_refcount_policy>{}, "");
+}
+
+template <typename RefcountPolicy>
+void test_refcount()
+{
+    using refcount = RefcountPolicy;
+
+    SECTION("starts at one")
+    {
+        refcount elem{};
+        CHECK(elem.dec());
+    }
+
+    SECTION("disowned starts at zero")
+    {
+        refcount elem{immer::disowned{}};
+        elem.inc();
+        CHECK(elem.dec());
+    }
+
+    SECTION("inc dec")
+    {
+        refcount elem{};
+        elem.inc();
+        CHECK(!elem.dec());
+        CHECK(elem.dec());
+    }
+
+    SECTION("inc dec unsafe")
+    {
+        refcount elem{};
+        elem.inc();
+        CHECK(!elem.dec());
+        elem.inc();
+        elem.dec_unsafe();
+        CHECK(elem.dec());
+    }
+}
+
+TEST_CASE("basic refcount") { test_refcount<immer::refcount_policy>(); }
+
+TEST_CASE("thread unsafe refcount")
+{
+    test_refcount<immer::unsafe_refcount_policy>();
+}
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);
+    }
+}
diff --git a/third_party/immer/test/transient_tester.hpp b/third_party/immer/test/transient_tester.hpp
new file mode 100644
index 000000000000..3cf891bef957
--- /dev/null
+++ b/third_party/immer/test/transient_tester.hpp
@@ -0,0 +1,54 @@
+//
+// 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
+//
+
+#pragma once
+
+#include "dada.hpp"
+
+namespace {
+
+template <typename VP, typename VT>
+struct transient_tester
+{
+    VP vp;
+    VT vt;
+    dadaism d      = {};
+    bool transient = false;
+
+    transient_tester(VP vp)
+        : vp{vp}
+        , vt{vp.transient()}
+    {}
+
+    bool step()
+    {
+        auto s = d.next();
+        if (soft_dada()) {
+            auto new_transient = !transient;
+            try {
+                if (new_transient)
+                    vt = vp.transient();
+                else
+                    vp = vt.persistent();
+            } catch (const dada_error&) {
+                return false;
+            }
+            transient = new_transient;
+            return true;
+        } else
+            return false;
+    }
+};
+
+template <typename VP>
+transient_tester<VP, typename VP::transient_type> as_transient_tester(VP p)
+{
+    return {std::move(p)};
+}
+
+} // anonymous namespace
diff --git a/third_party/immer/test/util.hpp b/third_party/immer/test/util.hpp
new file mode 100644
index 000000000000..41904f5a8907
--- /dev/null
+++ b/third_party/immer/test/util.hpp
@@ -0,0 +1,103 @@
+//
+// 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
+//
+
+#pragma once
+
+#include <boost/range/irange.hpp>
+#include <boost/range/join.hpp>
+#include <cstddef>
+
+namespace {
+
+struct identity_t
+{
+    template <typename T>
+    decltype(auto) operator()(T&& x)
+    {
+        return std::forward<decltype(x)>(x);
+    }
+};
+
+template <typename Integer>
+auto test_irange(Integer from, Integer to)
+{
+#if IMMER_SLOW_TESTS
+    return boost::irange(from, to);
+#else
+    if (to - from < Integer{10})
+        return boost::join(boost::irange(Integer{}, Integer{}),
+                           boost::join(boost::irange(from, to, 1),
+                                       boost::irange(Integer{}, Integer{})));
+    else
+        return boost::join(boost::irange(from, from + Integer{2}),
+                           boost::join(boost::irange(from + Integer{2},
+                                                     to - Integer{2},
+                                                     (to - from) / Integer{5}),
+                                       boost::irange(to - Integer{2}, to)));
+#endif
+}
+
+} // anonymous namespace
+
+#if IMMER_SLOW_TESTS
+#define CHECK_SLOW(...) CHECK(__VA_ARGS__)
+#else
+#define CHECK_SLOW(...)
+#endif
+
+#if IMMER_SLOW_TESTS
+#define CHECK_VECTOR_EQUALS_RANGE_AUX(v1_, first_, last_, xf_)                 \
+    [](auto&& v1, auto&& first, auto&& last, auto&& xf) {                      \
+        auto size = std::distance(first, last);                                \
+        CHECK(static_cast<std::ptrdiff_t>(v1.size()) == size);                 \
+        if (static_cast<std::ptrdiff_t>(v1.size()) != size)                    \
+            return;                                                            \
+        for (auto j = 0u; j < size; ++j)                                       \
+            CHECK(xf(v1[j]) == xf(*first++));                                  \
+    }(v1_, first_, last_, xf_) // CHECK_EQUALS
+#else
+#define CHECK_VECTOR_EQUALS_RANGE_AUX(v1_, first_, last_, ...)                 \
+    [](auto&& v1, auto&& first, auto&& last, auto&& xf) {                      \
+        auto size = std::distance(first, last);                                \
+        CHECK(static_cast<std::ptrdiff_t>(v1.size()) == size);                 \
+        if (static_cast<std::ptrdiff_t>(v1.size()) != size)                    \
+            return;                                                            \
+        if (size > 0) {                                                        \
+            CHECK(xf(v1[0]) == xf(*(first + (0))));                            \
+            CHECK(xf(v1[size - 1]) == xf(*(first + (size - 1))));              \
+            CHECK(xf(v1[size / 2]) == xf(*(first + (size / 2))));              \
+            CHECK(xf(v1[size / 3]) == xf(*(first + (size / 3))));              \
+            CHECK(xf(v1[size / 4]) == xf(*(first + (size / 4))));              \
+            CHECK(xf(v1[size - 1 - size / 2]) ==                               \
+                  xf(*(first + (size - 1 - size / 2))));                       \
+            CHECK(xf(v1[size - 1 - size / 3]) ==                               \
+                  xf(*(first + (size - 1 - size / 3))));                       \
+            CHECK(xf(v1[size - 1 - size / 4]) ==                               \
+                  xf(*(first + (size - 1 - size / 4))));                       \
+        }                                                                      \
+        if (size > 1) {                                                        \
+            CHECK(xf(v1[1]) == xf(*(first + (1))));                            \
+            CHECK(xf(v1[size - 2]) == xf(*(first + (size - 2))));              \
+        }                                                                      \
+        if (size > 2) {                                                        \
+            CHECK(xf(v1[2]) == xf(*(first + (2))));                            \
+            CHECK(xf(v1[size - 3]) == xf(*(first + (size - 3))));              \
+        }                                                                      \
+    }(v1_, first_, last_, __VA_ARGS__) // CHECK_EQUALS
+#endif                                 // IMMER_SLOW_TESTS
+
+#define CHECK_VECTOR_EQUALS_AUX(v1_, v2_, ...)                                 \
+    [](auto&& v1, auto&& v2, auto&&... xs) {                                   \
+        CHECK_VECTOR_EQUALS_RANGE_AUX(v1, v2.begin(), v2.end(), xs...);        \
+    }(v1_, v2_, __VA_ARGS__)
+
+#define CHECK_VECTOR_EQUALS_RANGE(v1, b, e)                                    \
+    CHECK_VECTOR_EQUALS_RANGE_AUX((v1), (b), (e), identity_t{})
+
+#define CHECK_VECTOR_EQUALS(v1, v2)                                            \
+    CHECK_VECTOR_EQUALS_AUX((v1), (v2), identity_t{})
diff --git a/third_party/immer/test/vector/B3-BL0.cpp b/third_party/immer/test/vector/B3-BL0.cpp
new file mode 100644
index 000000000000..c0ddd2d66545
--- /dev/null
+++ b/third_party/immer/test/vector/B3-BL0.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/vector.hpp>
+
+template <typename T>
+using test_vector_t = immer::vector<T, immer::default_memory_policy, 3u, 0u>;
+
+#define VECTOR_T test_vector_t
+#include "generic.ipp"
diff --git a/third_party/immer/test/vector/B3-BL2.cpp b/third_party/immer/test/vector/B3-BL2.cpp
new file mode 100644
index 000000000000..15cfeb9e2f11
--- /dev/null
+++ b/third_party/immer/test/vector/B3-BL2.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/vector.hpp>
+
+template <typename T>
+using test_vector_t = immer::vector<T, immer::default_memory_policy, 3u, 2u>;
+
+#define VECTOR_T test_vector_t
+#include "generic.ipp"
diff --git a/third_party/immer/test/vector/B3-BL3.cpp b/third_party/immer/test/vector/B3-BL3.cpp
new file mode 100644
index 000000000000..5901940eab23
--- /dev/null
+++ b/third_party/immer/test/vector/B3-BL3.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/vector.hpp>
+
+template <typename T>
+using test_vector_t = immer::vector<T, immer::default_memory_policy, 3u, 3u>;
+
+#define VECTOR_T test_vector_t
+#include "generic.ipp"
diff --git a/third_party/immer/test/vector/B3-BL4.cpp b/third_party/immer/test/vector/B3-BL4.cpp
new file mode 100644
index 000000000000..5f3b8c17eec8
--- /dev/null
+++ b/third_party/immer/test/vector/B3-BL4.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/vector.hpp>
+
+template <typename T>
+using test_vector_t = immer::vector<T, immer::default_memory_policy, 3u, 4u>;
+
+#define VECTOR_T test_vector_t
+#include "generic.ipp"
diff --git a/third_party/immer/test/vector/default.cpp b/third_party/immer/test/vector/default.cpp
new file mode 100644
index 000000000000..1a1459ca124e
--- /dev/null
+++ b/third_party/immer/test/vector/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/vector.hpp>
+
+#define VECTOR_T ::immer::vector
+#include "generic.ipp"
diff --git a/third_party/immer/test/vector/gc.cpp b/third_party/immer/test/vector/gc.cpp
new file mode 100644
index 000000000000..ec006adfb748
--- /dev/null
+++ b/third_party/immer/test/vector/gc.cpp
@@ -0,0 +1,22 @@
+//
+// 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/vector.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_vector_t = immer::vector<T, gc_memory, 3u>;
+
+#define VECTOR_T test_vector_t
+#include "generic.ipp"
diff --git a/third_party/immer/test/vector/generic.ipp b/third_party/immer/test/vector/generic.ipp
new file mode 100644
index 000000000000..ff277edbdb45
--- /dev/null
+++ b/third_party/immer/test/vector/generic.ipp
@@ -0,0 +1,488 @@
+//
+// 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/util.hpp"
+
+#include <immer/algorithm.hpp>
+
+#include <boost/range/adaptors.hpp>
+#include <catch.hpp>
+
+#include <algorithm>
+#include <numeric>
+#include <string>
+#include <vector>
+
+using namespace std::string_literals;
+
+#ifndef VECTOR_T
+#error "define the vector template to use in VECTOR_T"
+#endif
+
+template <typename V = VECTOR_T<unsigned>>
+auto make_test_vector(unsigned min, unsigned max)
+{
+    auto v = V{};
+    for (auto i = min; i < max; ++i)
+        v = v.push_back({i});
+    return v;
+}
+
+struct big_object
+{
+    std::array<std::size_t, 42> v;
+};
+
+struct string_sentinel
+{};
+
+bool operator==(const char16_t* i, string_sentinel) { return *i == '\0'; }
+
+bool operator!=(const char16_t* i, string_sentinel) { return *i != '\0'; }
+
+TEST_CASE("instantiation")
+{
+    SECTION("default")
+    {
+        auto v = VECTOR_T<int>{};
+        CHECK(v.size() == 0u);
+        CHECK(v.empty());
+    }
+
+    SECTION("initializer list")
+    {
+        auto v = VECTOR_T<unsigned>{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
+        CHECK_VECTOR_EQUALS(v, boost::irange(0u, 10u));
+        CHECK(!v.empty());
+    }
+
+    SECTION("big object")
+    {
+        auto v = VECTOR_T<big_object>{{}, {}, {}, {}};
+        CHECK(v.size() == 4);
+    }
+
+    SECTION("range")
+    {
+        auto r = std::vector<int>{{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}};
+        auto v = VECTOR_T<unsigned>{r.begin(), r.end()};
+        CHECK_VECTOR_EQUALS(v, boost::irange(0u, 10u));
+    }
+
+    SECTION("empty range")
+    {
+        auto r = std::vector<int>{};
+        auto v = VECTOR_T<unsigned>{r.begin(), r.end()};
+        CHECK(v.size() == 0);
+    }
+
+    SECTION("iterator/sentinel")
+    {
+        auto r = u"012345678";
+        string_sentinel s;
+        auto v = VECTOR_T<unsigned>{r, s};
+        CHECK_VECTOR_EQUALS(v, boost::irange(u'0', u'9'));
+    }
+
+    SECTION("fill")
+    {
+        auto v1 = VECTOR_T<int>(4);
+        CHECK(v1.size() == 4);
+        auto v2 = VECTOR_T<int>(4, 42);
+        CHECK(v2.size() == 4);
+        CHECK(v2[2] == 42);
+    }
+}
+
+TEST_CASE("back and front")
+{
+    auto v = VECTOR_T<unsigned>{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
+    CHECK(v.front() == 0);
+    CHECK(v.back() == 9);
+}
+
+TEST_CASE("at")
+{
+    auto v = VECTOR_T<unsigned>{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
+    CHECK(v.at(0) == 0);
+    CHECK(v.at(5) == 5);
+    CHECK_THROWS_AS(v.at(10), const std::out_of_range&);
+    CHECK_THROWS_AS(v.at(11), const std::out_of_range&);
+}
+
+TEST_CASE("push back one element")
+{
+    SECTION("one element")
+    {
+        const auto v1 = VECTOR_T<int>{};
+        auto v2       = v1.push_back(42);
+        CHECK(v1.size() == 0u);
+        CHECK(v2.size() == 1u);
+        CHECK(v2[0] == 42);
+    }
+
+    SECTION("many elements")
+    {
+        const auto n = 666u;
+        auto v       = VECTOR_T<unsigned>{};
+        for (auto i = 0u; i < n; ++i) {
+            v = v.push_back(i * 42);
+            CHECK(v.size() == i + 1);
+            for (decltype(v.size()) j = 0; j < v.size(); ++j)
+                CHECK(v[j] == j * 42);
+        }
+    }
+}
+
+TEST_CASE("update")
+{
+    const auto n = 42u;
+    auto v       = make_test_vector(0, n);
+
+    SECTION("set")
+    {
+        const auto u = v.set(3u, 13u);
+        CHECK(u.size() == v.size());
+        CHECK(u[2u] == 2u);
+        CHECK(u[3u] == 13u);
+        CHECK(u[4u] == 4u);
+        CHECK(u[40u] == 40u);
+        CHECK(v[3u] == 3u);
+    }
+
+    SECTION("set further")
+    {
+        auto v = make_test_vector(0, 666);
+
+        auto u = v.set(3u, 13u);
+        u      = u.set(200u, 7u);
+        CHECK(u.size() == v.size());
+
+        CHECK(u[2u] == 2u);
+        CHECK(u[4u] == 4u);
+        CHECK(u[40u] == 40u);
+        CHECK(u[600u] == 600u);
+
+        CHECK(u[3u] == 13u);
+        CHECK(u[200u] == 7u);
+
+        CHECK(v[3u] == 3u);
+        CHECK(v[200u] == 200u);
+    }
+
+    SECTION("set further more")
+    {
+        auto v = make_test_vector(0, 666u);
+
+        for (decltype(v.size()) i = 0; i < v.size(); ++i) {
+            v = v.set(i, i + 1);
+            CHECK(v[i] == i + 1);
+        }
+    }
+
+    SECTION("update")
+    {
+        const auto u = v.update(10u, [](auto x) { return x + 10; });
+        CHECK(u.size() == v.size());
+        CHECK(u[10u] == 20u);
+        CHECK(v[40u] == 40u);
+
+        const auto w = v.update(40u, [](auto x) { return x - 10; });
+        CHECK(w.size() == v.size());
+        CHECK(w[40u] == 30u);
+        CHECK(v[40u] == 40u);
+    }
+}
+
+TEST_CASE("iterator")
+{
+    const auto n = 666u;
+    auto v       = make_test_vector(0, n);
+
+    SECTION("empty vector")
+    {
+        auto v = VECTOR_T<unsigned>{};
+        CHECK(v.begin() == v.end());
+    }
+
+    SECTION("works with range loop")
+    {
+        auto i = 0u;
+        for (const auto& x : v)
+            CHECK(x == i++);
+        CHECK(i == 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("can go back from end")
+    {
+        auto expected = n - 1;
+        auto last     = v.end();
+        CHECK(expected == *--last);
+    }
+
+    SECTION("works with reversed range adaptor")
+    {
+        auto r = v | boost::adaptors::reversed;
+        auto i = n;
+        for (const auto& x : r)
+            CHECK(x == --i);
+    }
+
+    SECTION("works with strided range adaptor")
+    {
+        auto r = v | boost::adaptors::strided(5);
+        auto i = 0u;
+        for (const auto& x : r)
+            CHECK(x == 5 * i++);
+    }
+
+    SECTION("works reversed")
+    {
+        auto i = n;
+        for (auto iter = v.rbegin(), last = v.rend(); iter != last; ++iter)
+            CHECK(*iter == --i);
+    }
+
+    SECTION("advance and distance")
+    {
+        auto i1 = v.begin();
+        auto i2 = i1 + 100;
+        CHECK(100u == *i2);
+        CHECK(100 == i2 - i1);
+        CHECK(50u == *(i2 - 50));
+        CHECK(-30 == (i2 - 30) - i2);
+    }
+}
+
+TEST_CASE("equals")
+{
+    const auto n = 666u;
+    auto v       = make_test_vector(0, n);
+
+    CHECK(v == v);
+    CHECK(v == v.set(42, 42));
+    CHECK(v != v.set(42, 24));
+    CHECK(v == v.set(42, 24).set(42, 42));
+    CHECK(v.set(42, 24) == v.set(42, 24));
+    CHECK(v != v.push_back(7));
+    CHECK(v.push_back(7) == v.push_back(7));
+    CHECK(v.push_back(5) != v.push_back(7));
+    CHECK(v != v.set(v.size() - 2, 24));
+    CHECK(v == v.set(v.size() - 2, 24).set(v.size() - 2, v[v.size() - 2]));
+}
+
+TEST_CASE("all of")
+{
+    const auto n = 666u;
+    auto v       = make_test_vector(0, n);
+
+    SECTION("false")
+    {
+        auto res = immer::all_of(v, [](auto x) { return x < 100; });
+        CHECK(res == false);
+    }
+    SECTION("true")
+    {
+        auto res = immer::all_of(v, [](auto x) { return x < 1000; });
+        CHECK(res == true);
+    }
+    SECTION("bounded, true")
+    {
+        auto res = immer::all_of(
+            v.begin() + 101, v.end() - 10, [](auto x) { return x > 100; });
+        CHECK(res == true);
+    }
+    SECTION("bounded, false")
+    {
+        auto res = immer::all_of(
+            v.begin() + 101, v.end() - 10, [](auto x) { return x < 600; });
+        CHECK(res == false);
+    }
+}
+
+TEST_CASE("accumulate")
+{
+    const auto n = 666u;
+    auto v       = make_test_vector(0, n);
+
+    auto expected_n = [](auto n) { return n * (n - 1) / 2; };
+    auto expected_i = [&](auto i, auto n) {
+        return expected_n(n) - expected_n(i);
+    };
+
+    SECTION("sum collection")
+    {
+        auto sum = immer::accumulate(v, 0u);
+        CHECK(sum == expected_n(v.size()));
+    }
+
+    SECTION("sum range")
+    {
+        using namespace std;
+        {
+            auto sum = immer::accumulate(begin(v) + 100, begin(v) + 300, 0u);
+            CHECK(sum == expected_i(100, 300));
+        }
+        {
+            auto sum = immer::accumulate(begin(v) + 31, begin(v) + 300, 0u);
+            CHECK(sum == expected_i(31, 300));
+        }
+        {
+            auto sum = immer::accumulate(begin(v), begin(v) + 33, 0u);
+            CHECK(sum == expected_i(0, 33));
+        }
+        {
+            auto sum = immer::accumulate(begin(v) + 100, begin(v) + 660, 0u);
+            CHECK(sum == expected_i(100, 660));
+        }
+        {
+            auto sum = immer::accumulate(begin(v) + 100, begin(v) + 105, 0u);
+            CHECK(sum == expected_i(100, 105));
+        }
+        {
+            auto sum = immer::accumulate(begin(v) + 660, begin(v) + 664, 0u);
+            CHECK(sum == expected_i(660, 664));
+        }
+    }
+}
+
+TEST_CASE("vector of strings")
+{
+    const auto n = 666u;
+
+    auto v = VECTOR_T<std::string>{};
+    for (auto i = 0u; i < n; ++i)
+        v = v.push_back(std::to_string(i));
+
+    for (decltype(v.size()) i = 0; i < v.size(); ++i)
+        CHECK(v[i] == std::to_string(i));
+
+    SECTION("set")
+    {
+        for (auto i = 0u; i < n; ++i)
+            v = v.set(i, "foo " + std::to_string(i));
+        for (auto i = 0u; i < n; ++i)
+            CHECK(v[i] == "foo " + std::to_string(i));
+    }
+}
+
+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
+};
+
+TEST_CASE("non default")
+{
+    const auto n = 666u;
+
+    auto v = VECTOR_T<non_default>{};
+    for (auto i = 0u; i < n; ++i)
+        v = v.push_back({i});
+
+    CHECK_VECTOR_EQUALS(v, boost::irange(0u, n));
+
+    SECTION("set")
+    {
+        for (auto i = 0u; i < n; ++i)
+            v = v.set(i, {i + 1});
+
+        CHECK_VECTOR_EQUALS(v, boost::irange(1u, n + 1u));
+    }
+}
+
+TEST_CASE("take")
+{
+    const auto n = 666u;
+
+    SECTION("anywhere")
+    {
+        auto v = make_test_vector(0, n);
+
+        for (auto i : test_irange(0u, n)) {
+            auto vv = v.take(i);
+            CHECK(vv.size() == i);
+            CHECK_VECTOR_EQUALS_RANGE(vv, v.begin(), v.begin() + i);
+        }
+    }
+}
+
+TEST_CASE("exception safety")
+{
+    constexpr auto n = 666u;
+
+    using dadaist_vector_t = typename dadaist_wrapper<VECTOR_T<unsigned>>::type;
+
+    SECTION("push back")
+    {
+        auto v = dadaist_vector_t{};
+        auto d = dadaism{};
+        for (auto i = 0u; v.size() < static_cast<decltype(v.size())>(n);) {
+            auto s = d.next();
+            try {
+                v = v.push_back({i});
+                ++i;
+            } catch (dada_error) {}
+            CHECK_VECTOR_EQUALS(v, boost::irange(0u, i));
+        }
+        CHECK(d.happenings > 0);
+        IMMER_TRACE_E(d.happenings);
+    }
+
+    SECTION("update")
+    {
+        auto v = make_test_vector<dadaist_vector_t>(0, n);
+        auto d = dadaism{};
+        for (auto i = 0u; i < n;) {
+            auto s = d.next();
+            try {
+                v = v.update(i, [](auto x) { return dada(), x + 1; });
+                ++i;
+            } catch (dada_error) {}
+            CHECK_VECTOR_EQUALS(
+                v, boost::join(boost::irange(1u, 1u + i), boost::irange(i, n)));
+        }
+        CHECK(d.happenings > 0);
+        IMMER_TRACE_E(d.happenings);
+    }
+
+    SECTION("take")
+    {
+        auto v = make_test_vector<dadaist_vector_t>(0, n);
+        auto d = dadaism{};
+        for (auto i = 0u; i < n;) {
+            auto s = d.next();
+            auto r = dadaist_vector_t{};
+            try {
+                r = v.take(i);
+                CHECK_VECTOR_EQUALS(r, boost::irange(0u, i++));
+            } catch (dada_error) {
+                CHECK_VECTOR_EQUALS(r, boost::irange(0u, 0u));
+            }
+        }
+        CHECK(d.happenings > 0);
+        IMMER_TRACE_E(d.happenings);
+    }
+}
diff --git a/third_party/immer/test/vector/issue-16.cpp b/third_party/immer/test/vector/issue-16.cpp
new file mode 100644
index 000000000000..81156b240bda
--- /dev/null
+++ b/third_party/immer/test/vector/issue-16.cpp
@@ -0,0 +1,122 @@
+//
+// 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
+//
+
+// Thanks Dominic Chen <ddchen@cs.cmu.edu> for reporting this issue
+// https://github.com/arximboldi/immer/issues/16
+
+#include <immer/flex_vector.hpp>
+#include <immer/flex_vector_transient.hpp>
+#include <immer/heap/gc_heap.hpp>
+#include <vector>
+
+std::vector<unsigned> init = {
+    291,  438, 755,  608, 594,  912,  73,   97,   496,  101,  837,  696,  978,
+    948,  126, 131,  624, 26,   590,  201,  219,  339,  193,  218,  866,  407,
+    538,  780, 312,  909, 129,  883,  571,  865,  854,  372,  488,  695,  750,
+    341,  798, 375,  350, 1013, 361,  1012, 743,  425,  68,   280,  245,  149,
+    342,  535, 901,  223, 285,  928,  666,  534,  166,  963,  171,  893,  297,
+    1017, 549, 172,  505, 965,  831,  563,  79,   180,  147,  543,  639,  1022,
+    880,  559, 426,  27,  657,  33,   252,  758,  8,    641,  699,  399,  335,
+    473,  625, 703,  264, 796,  61,   737,  527,  795,  123,  200,  287,  857,
+    208,  897, 354,  885, 581,  57,   752,  855,  56,   1007, 357,  643,  476,
+    113,  955, 349,  299, 76,   393,  557,  967,  995,  233,  990,  469,  742,
+    681,  874, 673,  530, 835,  24,   178,  81,   69,   40,   368,  981,  941,
+    645,  808, 511,  982, 888,  136,  100,  960,  804,  806,  600,  500,  337,
+    580,  551, 593,  612, 318,  660,  232,  17,   879,  86,   424,  202,  112,
+    235,  791, 873,  838, 47,   574,  858,  78,   237,  846,  340,  802,  907,
+    72,   38,  44,   902, 595,  940,  182,  784,  207,  355,  815,  545,  555,
+    258,  144, 564,  463, 198,  1004, 4,    175,  468,  658,  59,   938,  63,
+    20,   179, 714,  721, 723,  381,  3,    745,  415,  119,  413,  923,  157,
+    824,  668, 409,  459, 560,  353,  379,  450,  430,  479,  274,  309,  661,
+    508,  474, 771,  504, 674,  51,   173,  670,  83,   921,  1019, 956,  725,
+    556,  427, 597,  794, 918,  95,   514,  98,   638,  205,  727,  162,  905,
+    728,  431, 203,  828, 971,  648,  871,  215,  646,  1006, 816,  277,  861,
+    576,  99,  637,  67,  28,   161,  137,  14,   506,  717,  93,   298,  251,
+    975,  927, 818,  43,  284,  994,  196,  195,  260,  705,  604,  169,  296,
+    785,  911, 398,  687, 760,  486,  642,  417,  445,  925,  763,  756,  653,
+    662,  359, 84,   151, 980,  914,  440,  546,  329,  665,  435,  732,  922,
+    377,  105, 532,  282, 822,  878,  419,  659,  65,   111,  421,  672,  146,
+    320,  316, 31,   522, 145,  513,  373,  773,  184,  974,  621,  366,  124,
+    623,  953, 267,  712, 121,  512,  214,  1002, 455,  694,  834,  618,  324,
+    656,  257, 206,  554, 334,  606,  305,  1008, 190,  160,  502,  1024, 891,
+    751,  789, 821,  462, 489,  908,  370,  164,  746,  270,  319,  491,  443,
+    531,  775, 977,  244, 485,  840,  892,  850,  347,  729,  317,  74,   731,
+    738,  790, 988,  903, 176,  211,  890,  509,  592,  444,  307,  45,   810,
+    390,  239, 678,  999, 414,  693,  345,  363,  382,  602,  516,  801,  310,
+    754,  774, 364,  480, 290,  322,  887,  168,  37,   140,  937,  578,  1005,
+    614,  734, 449,  230, 541,  761,  931,  882,  920,  210,  807,  115,  964,
+    521,  862, 628,  747, 490,  422,  788,  691,  675,  652,  25,   582,  585,
+    961,  472, 722,  7,   367,  15,   275,  700,  249,  116,  969,  325,  706,
+    493,  524, 537,  875, 22,   688,  843,  575,  288,  141,  830,  698,  562,
+    833,  143, 117,  683, 1000, 238,  397,  827,  619,  686,  1018, 973,  80,
+    689,  165, 702,  88,  332,  192,  730,  847,  408,  58,   634,  471,  958,
+    204,  236, 314,  494, 158,  412,  226,  135,  103,  998,  85,   904,  587,
+    194,  6,   380,  987, 266,  853,  369,  949,  34,   799,  884,  16,   944,
+    701,  313, 300,  611, 148,  457,  216,  900,  10,   715,  586,  561,  917,
+    1020, 800, 640,  104, 864,  185,  566,  492,  709,  1009, 498,  859,  945,
+    710,  433, 819,  411, 418,  649,  876,  733,  286,  326,  599,  986,  465,
+    929,  272, 916,  935, 1,    87,   650,  609,  344,  598,  951,  221,  242,
+    352,  635, 680,  464, 75,   256,  962,  336,  82,   383,  836,  993,  222,
+    446,  110, 970,  591, 439,  677,  308,  186,  664,  188,  253,  770,  5,
+    651,  467, 684,  139, 762,  315,  89,   507,  477,  406,  358,  753,  877,
+    442,  32,  2,    997, 120,  946,  391,  220,  996,  125,  943,  749,  130,
+    553,  385, 692,  814, 615,  396,  388,  610,  630,  957,  371,  741,  268,
+    199,  740, 823,  588, 250,  269,  577,  254,  845,  825,  153,  62,   303,
+    842,  453, 241,  114, 483,  868,  550,  952,  429,  434,  529,  503,  333,
+    616,  913, 23,   872, 679,  497,  9,    841,  772,  150,  776,  52,   947,
+    805,  613, 620,  343, 895,  812,  782,  138,  281,  778,  829,  289,  820,
+    106,  400, 484,  402, 915,  720,  122,  724,  783,  436,  499,  605,  627,
+    191,  607, 536,  91,  461,  108,  976,  851,  46,   676,  765,  109,  96,
+    437,  323, 261,  330, 273,  311,  271,  972,  719,  306,  889,  707,  384,
+    764,  979, 572,  475, 231,  519,  682,  832,  448,  356,  966,  1010, 404,
+    757,  209, 548,  617, 228,  482,  156,  596,  1014, 405,  187,  860,  420,
+    655,  276, 797,  243, 1003, 229,  950,  869,  163,  321,  848,  395,  302,
+    803,  711, 515,  376, 886,  278,  128,  870,  1015, 989,  636,  1023, 573,
+    704,  984, 601,  932, 18,   386,  926,  632,  647,  579,  365,  669,  910,
+    768,  809, 526,  769, 66,   432,  213,  293,  48,   839,  217,  224,  813,
+    899,  328, 177,  654, 401,  544,  154,  118,  736,  766,  495,  936,  767,
+    523,  569, 458,  460, 685,  107,  718,  631,  844,  248,  933,  60,   227,
+    374,  246, 247,  331, 894,  183,  279,  338,  387,  633,  565,  403,  744,
+    849,  41,  942,  517, 389,  518,  133,  622,  35,   779,  362,  726,  1021,
+    189,  787, 71,   539, 262,  423,  346,  856,  212,  748,  64,   930,  667,
+    881,  781, 603,  817, 410,  378,  170,  225,  558,  29,   906,  174,  939,
+    21,   292, 304,  663, 240,  793,  567,  456,  255,  811,  954,  735,  867,
+    428,  991, 152,  528, 70,   263,  392,  697,  671,  155,  49,   301,  792,
+    525,  959, 1001, 90,  924,  896,  826,  452,  968,  11,   542,  53,   327,
+    777,  294, 94,   589, 547,  584,  416,  351,  713,  478,  55,   451,  36,
+    708,  501, 132,  863, 54,   19,   142,  13,   934,  134,  30,   466,  716,
+    295,  92,  447,  102, 181,  520,  644,  481,  470,  540,  583,  552,  786,
+    690,  487, 394,  983, 259,  510,  50,   568,  533,  759,  992,  283,  39,
+    360,  919, 167,  852, 42,   629,  1016, 454,  441,  1011, 0,    77,   197,
+    234,  127, 159,  12,  898,  348,  265,  626,  739,  985};
+
+using gc_policy = immer::memory_policy<immer::heap_policy<immer::gc_heap>,
+                                       immer::no_refcount_policy,
+                                       immer::gc_transience_policy,
+                                       false>;
+
+using immvec = immer::flex_vector_transient<unsigned, gc_policy>;
+
+void erase(immvec& v, unsigned idx)
+{
+    auto v2(v);
+    v.take(idx);
+    v2.drop(idx + 1);
+    v.append(v2);
+}
+
+int main(int argc, char** argv)
+{
+    immvec vector;
+    for (auto i : init)
+        vector.push_back(i);
+
+    erase(vector, 470);
+    vector.push_back(224);
+    erase(vector, 958);
+}
diff --git a/third_party/immer/test/vector/issue-46.cpp b/third_party/immer/test/vector/issue-46.cpp
new file mode 100644
index 000000000000..6475be210d05
--- /dev/null
+++ b/third_party/immer/test/vector/issue-46.cpp
@@ -0,0 +1,39 @@
+//
+// 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
+//
+
+// Thanks Guiguiprim for reporting this issue
+// https://github.com/arximboldi/immer/issues/46
+
+#include <immer/flex_vector.hpp>
+#include <immer/vector.hpp>
+#include <immer/vector_transient.hpp>
+
+#include <catch.hpp>
+
+TEST_CASE("operator==() may return bad result")
+{
+    using bool_vec = immer::flex_vector<bool>;
+
+    immer::vector<bool_vec> v0;
+    auto tv = v0.transient();
+    tv.push_back(bool_vec(9, false));
+    tv.push_back(bool_vec(10, false));
+    tv.push_back(bool_vec(8, false));
+    tv.push_back(bool_vec(6, false));
+    tv.push_back(bool_vec(9, false));
+    tv.push_back(bool_vec(7, false));
+    tv.push_back(bool_vec(8, false));
+    tv.push_back(bool_vec(9, false));
+    tv.push_back(bool_vec(10, false));
+    v0 = tv.persistent();
+
+    auto v1 = v0.update(1, [](bool_vec vec) { return vec.set(8, true); });
+
+    CHECK(v0[1] != v1[1]);
+    CHECK(v0 != v1);
+}
diff --git a/third_party/immer/test/vector/issue-74.cpp b/third_party/immer/test/vector/issue-74.cpp
new file mode 100644
index 000000000000..8650be014f1f
--- /dev/null
+++ b/third_party/immer/test/vector/issue-74.cpp
@@ -0,0 +1,24 @@
+#include "immer/box.hpp"
+#include "immer/set.hpp"
+#include "immer/vector.hpp"
+
+#include <functional>
+
+struct my_type
+{
+    using container_t = immer::vector<immer::box<my_type>>;
+    using func_t      = std::function<int(int)>;
+
+    int ival;
+    double dval;
+    func_t func;
+    container_t children;
+};
+
+int main()
+{
+    my_type::container_t items = {my_type()};
+    immer::set<int> items2;
+    auto items3 = items2.insert(10);
+    return 0;
+}
diff --git a/third_party/immer/test/vector_transient/B3-BL0.cpp b/third_party/immer/test/vector_transient/B3-BL0.cpp
new file mode 100644
index 000000000000..a0af0a17124c
--- /dev/null
+++ b/third_party/immer/test/vector_transient/B3-BL0.cpp
@@ -0,0 +1,21 @@
+//
+// 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/vector.hpp>
+#include <immer/vector_transient.hpp>
+
+template <typename T>
+using test_vector_t = immer::vector<T, immer::default_memory_policy, 3u, 0u>;
+
+template <typename T>
+using test_vector_transient_t = typename test_vector_t<T>::transient_type;
+
+#define VECTOR_T test_vector_t
+#define VECTOR_TRANSIENT_T test_vector_transient_t
+
+#include "generic.ipp"
diff --git a/third_party/immer/test/vector_transient/default.cpp b/third_party/immer/test/vector_transient/default.cpp
new file mode 100644
index 000000000000..f3089086a9a0
--- /dev/null
+++ b/third_party/immer/test/vector_transient/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/vector.hpp>
+#include <immer/vector_transient.hpp>
+
+#define VECTOR_T ::immer::vector
+#define VECTOR_TRANSIENT_T ::immer::vector_transient
+
+#include "generic.ipp"
diff --git a/third_party/immer/test/vector_transient/gc.cpp b/third_party/immer/test/vector_transient/gc.cpp
new file mode 100644
index 000000000000..393d2d1bbc10
--- /dev/null
+++ b/third_party/immer/test/vector_transient/gc.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/vector.hpp>
+#include <immer/vector_transient.hpp>
+
+#include <immer/heap/gc_heap.hpp>
+#include <immer/refcount/no_refcount_policy.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_vector_t = immer::vector<T, gc_memory, 3u>;
+
+template <typename T>
+using test_vector_transient_t = immer::vector_transient<T, gc_memory, 3u>;
+
+#define VECTOR_T test_vector_t
+#define VECTOR_TRANSIENT_T test_vector_transient_t
+
+#include "generic.ipp"
diff --git a/third_party/immer/test/vector_transient/generic.ipp b/third_party/immer/test/vector_transient/generic.ipp
new file mode 100644
index 000000000000..6cd25a567d53
--- /dev/null
+++ b/third_party/immer/test/vector_transient/generic.ipp
@@ -0,0 +1,267 @@
+//
+// 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 <catch.hpp>
+
+#ifndef VECTOR_T
+#error "define the vector template to use in VECTOR_T"
+#endif
+
+#ifndef VECTOR_TRANSIENT_T
+#error "define the vector template to use in VECTOR_TRANSIENT_T"
+#endif
+
+template <typename V = VECTOR_T<unsigned>>
+auto make_test_vector(unsigned min, unsigned max)
+{
+    auto v = V{};
+    for (auto i = min; i < max; ++i)
+        v = v.push_back({i});
+    return v;
+}
+
+TEST_CASE("from vector and to vector")
+{
+    constexpr auto n = 100u;
+
+    auto v = make_test_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("protect persistence")
+{
+    auto v = VECTOR_T<unsigned>{}.transient();
+    v.push_back(12);
+    auto p = v.persistent();
+    v.set(0, 42);
+    CHECK(p[0] == 12);
+    CHECK(v[0] == 42);
+}
+
+TEST_CASE("push back move")
+{
+    using vector_t = 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                = check_move(std::move(v).push_back(0));
+    v                = check_move(std::move(v).push_back(1));
+    v                = check_move(std::move(v).push_back(2));
+    auto addr_before = &v[0];
+    v                = check_move(std::move(v).push_back(3));
+    auto addr_after  = &v[0];
+
+    if (vector_t::memory_policy::use_transient_rvalues)
+        CHECK(addr_before == addr_after);
+    else
+        CHECK(addr_before != addr_after);
+
+    CHECK_VECTOR_EQUALS(v, boost::irange(0u, 4u));
+}
+
+TEST_CASE("set move")
+{
+    using vector_t = 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);
+
+    auto addr_before = &v[0];
+    v                = check_move(std::move(v).set(0, 1));
+    auto addr_after  = &v[0];
+
+    if (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("update move")
+{
+    using vector_t = 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);
+
+    auto addr_before = &v[0];
+    v = check_move(std::move(v).update(0, [](auto x) { return x + 1; }));
+    auto addr_after = &v[0];
+
+    if (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("take move")
+{
+    using vector_t = 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).take(1));
+    auto addr_after  = &v[0];
+
+    if (vector_t::memory_policy::use_transient_rvalues)
+        CHECK(addr_before == addr_after);
+    else
+        CHECK(addr_before != addr_after);
+
+    CHECK_VECTOR_EQUALS(v, boost::irange(0u, 1u));
+}
+
+TEST_CASE("exception safety")
+{
+    constexpr auto n = 667u;
+
+    using dadaist_vector_t = typename dadaist_wrapper<VECTOR_T<unsigned>>::type;
+
+    SECTION("push back")
+    {
+        auto t = as_transient_tester(dadaist_vector_t{});
+        auto d = dadaism{};
+        for (auto li = 0u, i = 0u; i < n;) {
+            auto s = d.next();
+            try {
+                if (t.transient)
+                    t.vt.push_back({i});
+                else
+                    t.vp = t.vp.push_back({i});
+                ++i;
+                if (t.step())
+                    li = i;
+            } 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);
+        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_vector<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;
+                if (t.step())
+                    li = i;
+            } catch (dada_error) {}
+            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_vector<dadaist_vector_t>(0, n));
+        auto d = dadaism{};
+        auto deltas = magic_rotator();
+        auto delta  = 0u;
+        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);
+    }
+}