diff options
Diffstat (limited to 'third_party/immer/test')
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 0000000000..faa61bbe6d --- /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 0000000000..928fffaaac --- /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 0000000000..a994208bc7 --- /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 0000000000..aa603c7b0a --- /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 0000000000..4b40185e94 --- /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 0000000000..7a382c70a8 --- /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 0000000000..f3219e81c6 --- /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 0000000000..21ff74d7ef --- /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 0000000000..fbd1b178df --- /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 0000000000..04e459559a --- /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 0000000000..cfb5f04ea1 --- /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 0000000000..4c8fce07de --- /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 0000000000..623c8ba37d --- /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 0000000000..1465bf7bf5 --- /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 0000000000..8809418cce --- /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 0000000000..437384a727 --- /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 0000000000..83af21d688 --- /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 0000000000..e44f7e2bfa --- /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 0000000000..7258cc0772 --- /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 0000000000..063ad133a0 --- /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 0000000000..d924dc3a83 --- /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 0000000000..ba17c1a620 --- /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 0000000000..5ef1eaffb7 --- /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 0000000000..d9ecdd7fba --- /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 0000000000..57b97f5ed7 --- /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 0000000000..6dbd73f07c --- /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 0000000000..76bd77b2e2 --- /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 0000000000..7757fe4ee4 --- /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 0000000000..fb5d13d1aa --- /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 0000000000..8f28c3d809 --- /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 0000000000..da28028c06 --- /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 0000000000..e9d843ccd2 --- /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 0000000000..5577ee43df --- /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 0000000000..8c93cd163e --- /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 0000000000..d8443afb55 --- /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 0000000000..f1e0ec2dd5 --- /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 0000000000..61458a0135 --- /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 0000000000..52da689c67 --- /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 0000000000..cb453c4f81 --- /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 0000000000..818fb03aaa --- /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 0000000000..18fc9d11f5 --- /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 0000000000..447c623dda --- /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 0000000000..94af2be208 --- /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 0000000000..f9278ca779 --- /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 0000000000..192b0f8e9a --- /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 0000000000..7fe3e5b772 --- /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 0000000000..8e6611a4ea --- /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 0000000000..098c8c97d0 --- /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 0000000000..8d75373787 --- /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 0000000000..3cf891bef9 --- /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 0000000000..41904f5a89 --- /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 0000000000..c0ddd2d665 --- /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 0000000000..15cfeb9e2f --- /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 0000000000..5901940eab --- /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 0000000000..5f3b8c17ee --- /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 0000000000..1a1459ca12 --- /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 0000000000..ec006adfb7 --- /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 0000000000..ff277edbdb --- /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 0000000000..81156b240b --- /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 0000000000..6475be210d --- /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 0000000000..8650be014f --- /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 0000000000..a0af0a1712 --- /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 0000000000..f3089086a9 --- /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 0000000000..393d2d1bbc --- /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 0000000000..6cd25a567d --- /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); + } +} |