Postmodern immutable and persistent data structures for C++ — value semantics at scale

Summary of changes: The following classes were modified to accomodate iterator sentinel pairs: immer::vector, immer::flex_vector, immer::array, immer::detail::with_capacity, immer::detail::no_capacity, and immer::detail::node. To this end, a new file was added, immer/detail/type_traits.hpp, providing metaprograms extending the facilities provided by the standard library type_traits header, along with several functions to the immer/algorithm.hpp header.

I found what appears to be a memory corruption issue with recursive types using box. Below is a minimal reproducer which seg-faults on my machine. I am on clang, MacOS 10.14, and -std=c++14.

#include "immer/vector.hpp"
#include "immer/box.hpp"




//=============================================================================
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()};
    return 0;
}

I tried compilation of the latest master with VS2017, but I get a compile error:

inline constexpr auto clz_(unsigned int x) { return __builtin_clz(x); }
immer/detail/util.hpp(82): error C3861: '__builtin_clz': identifier not found

Can you please add support for VS 2017?

Hi,

I'm playing with immer for a project at the minute, but i also need immutable maps. I'm considering porting either Clojure's HAMTs or the CHAMP variant. Did you have any plans in this direction or could you give me a little advice on how to go about porting it into the infrastructure you've laid down?

Thanks

Our use of immer requires that we disable exceptions. As not supporting exceptions is a common situation in C++ codebases I'm filing this issue to propose integrating that change into immer.

Our modification follows the same pattern that LibC++ uses: if exceptions are enabled, use them, otherwise, if an out-of-range or an allocation fails, log a message and abort.

We added this snippet to immer/immer/config.hpp:

#if __has_feature(cxx_exceptions)
#define IMMER_THROW_BAD_ALLOC(msg) throw std::bad_alloc{msg}
#define IMMER_THROW_OUT_OF_RANGE(msg) throw std::out_of_range{msg}
#define IMMER_TRY try
#define IMMER_CATCH_ALL catch (...)
#define IMMER_RETHROW throw
#else
#define IMMER_NO_EXCEPTIONS
#define IMMER_THROW_BAD_ALLOC(msg) fprintf(stderr, "%s", msg); abort()
#define IMMER_THROW_OUT_OF_RANGE(msg) fprintf(stderr, "%s", msg); abort()
#define IMMER_TRY
#define IMMER_CATCH_ALL if (false)
#define IMMER_RETHROW
#endif

And then replaced all exception handling code with the appropriate macros.

Would it be OK to send a pull request with these modifications?

Tried to compile with clang-9 and got the following errors:

immer/immer/detail/rbts/rbtree.hpp:13:
/home/username/tmp/immer/immer/detail/rbts/operations.hpp:1092:28: error: chosen constructor is explicit in copy-initialization
                    return { pos.shift(), newn, ts, tail };
                           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/home/username/tmp/immer/immer/detail/rbts/position.hpp:945:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, true>::visit_regular<immer::detail::rbts::regular_sub_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
        return Visitor::visit_regular(*this, std::forward<Args>(args)...);
                        ^
/home/username/tmp/immer/immer/vector.hpp:293:20: note: in instantiation of member function 'immer::detail::rbts::rbtree<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
    { return impl_.take(elems); }
                   ^
/home/username/tmp/immer/example/vector/vector.cpp:49:22: note: in instantiation of member function 'immer::vector<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
        auto v2 = v1.take(3);
                     ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/5.4.0/../../../../include/c++/5.4.0/tuple:479:19: note: explicit constructor declared here
        constexpr tuple(_UElements&&... __elements)
                  ^
In file included from /home/username/tmp/immer/example/vector/vector.cpp:9:
In file included from /home/username/tmp/immer/immer/vector.hpp:11:
In file included from /home/username/tmp/immer/immer/detail/rbts/rbtree.hpp:13:
/home/username/tmp/immer/immer/detail/rbts/operations.hpp:1120:16: error: chosen constructor is explicit in copy-initialization
        return { 0, nullptr, new_tail_size, new_tail };
               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/home/username/tmp/immer/immer/detail/rbts/position.hpp:201:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, true>::visit_leaf<immer::detail::rbts::full_leaf_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
        return Visitor::visit_leaf(*this, std::forward<Args>(args)...);
                        ^
/home/username/tmp/immer/immer/detail/rbts/position.hpp:945:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, true>::visit_regular<immer::detail::rbts::regular_sub_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
        return Visitor::visit_regular(*this, std::forward<Args>(args)...);
                        ^
/home/username/tmp/immer/immer/vector.hpp:293:20: note: in instantiation of member function 'immer::detail::rbts::rbtree<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
    { return impl_.take(elems); }
                   ^
/home/username/tmp/immer/example/vector/vector.cpp:49:22: note: in instantiation of member function 'immer::vector<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
        auto v2 = v1.take(3);
                     ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/5.4.0/../../../../include/c++/5.4.0/tuple:479:19: note: explicit constructor declared here
        constexpr tuple(_UElements&&... __elements)
                  ^
In file included from /home/username/tmp/immer/example/vector/vector.cpp:9:
In file included from /home/username/tmp/immer/immer/vector.hpp:11:
In file included from /home/username/tmp/immer/immer/detail/rbts/rbtree.hpp:13:
/home/username/tmp/immer/immer/detail/rbts/operations.hpp:1092:28: error: chosen constructor is explicit in copy-initialization
                    return { pos.shift(), newn, ts, tail };
                           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/home/username/tmp/immer/immer/detail/rbts/position.hpp:1288:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, true>::visit_regular<immer::detail::rbts::full_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
        return Visitor::visit_regular(*this, std::forward<Args>(args)...);
                        ^
/home/username/tmp/immer/immer/detail/rbts/position.hpp:945:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, true>::visit_regular<immer::detail::rbts::regular_sub_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
        return Visitor::visit_regular(*this, std::forward<Args>(args)...);
                        ^
/home/username/tmp/immer/immer/vector.hpp:293:20: note: in instantiation of member function 'immer::detail::rbts::rbtree<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
    { return impl_.take(elems); }
                   ^
/home/username/tmp/immer/example/vector/vector.cpp:49:22: note: in instantiation of member function 'immer::vector<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
        auto v2 = v1.take(3);
                     ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/5.4.0/../../../../include/c++/5.4.0/tuple:479:19: note: explicit constructor declared here
        constexpr tuple(_UElements&&... __elements)
                  ^
In file included from /home/username/tmp/immer/example/vector/vector.cpp:9:
In file included from /home/username/tmp/immer/immer/vector.hpp:11:
In file included from /home/username/tmp/immer/immer/detail/rbts/rbtree.hpp:13:
/home/username/tmp/immer/immer/detail/rbts/operations.hpp:1120:16: error: chosen constructor is explicit in copy-initialization
        return { 0, nullptr, new_tail_size, new_tail };
               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/home/username/tmp/immer/immer/detail/rbts/position.hpp:108:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, true>::visit_leaf<immer::detail::rbts::leaf_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
        return Visitor::visit_leaf(*this, std::forward<Args>(args)...);
                        ^
/home/username/tmp/immer/immer/detail/rbts/position.hpp:945:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, true>::visit_regular<immer::detail::rbts::regular_sub_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
        return Visitor::visit_regular(*this, std::forward<Args>(args)...);
                        ^
/home/username/tmp/immer/immer/vector.hpp:293:20: note: in instantiation of member function 'immer::detail::rbts::rbtree<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
    { return impl_.take(elems); }
                   ^
/home/username/tmp/immer/example/vector/vector.cpp:49:22: note: in instantiation of member function 'immer::vector<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
        auto v2 = v1.take(3);
                     ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/5.4.0/../../../../include/c++/5.4.0/tuple:479:19: note: explicit constructor declared here
        constexpr tuple(_UElements&&... __elements)
                  ^
In file included from /home/username/tmp/immer/example/vector/vector.cpp:9:
In file included from /home/username/tmp/immer/immer/vector.hpp:11:
In file included from /home/username/tmp/immer/immer/detail/rbts/rbtree.hpp:13:
/home/username/tmp/immer/immer/detail/rbts/operations.hpp:1092:28: error: chosen constructor is explicit in copy-initialization
                    return { pos.shift(), newn, ts, tail };
                           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/home/username/tmp/immer/immer/detail/rbts/position.hpp:297:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, true>::visit_regular<immer::detail::rbts::regular_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
        return Visitor::visit_regular(*this, std::forward<Args>(args)...);
                        ^
/home/username/tmp/immer/immer/detail/rbts/position.hpp:945:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, true>::visit_regular<immer::detail::rbts::regular_sub_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
        return Visitor::visit_regular(*this, std::forward<Args>(args)...);
                        ^
/home/username/tmp/immer/immer/vector.hpp:293:20: note: in instantiation of member function 'immer::detail::rbts::rbtree<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
    { return impl_.take(elems); }
                   ^
/home/username/tmp/immer/example/vector/vector.cpp:49:22: note: in instantiation of member function 'immer::vector<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
        auto v2 = v1.take(3);
                     ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/5.4.0/../../../../include/c++/5.4.0/tuple:479:19: note: explicit constructor declared here
        constexpr tuple(_UElements&&... __elements)
                  ^
In file included from /home/username/tmp/immer/example/vector/vector.cpp:9:
In file included from /home/username/tmp/immer/immer/vector.hpp:11:
In file included from /home/username/tmp/immer/immer/detail/rbts/rbtree.hpp:13:
/home/username/tmp/immer/immer/detail/rbts/operations.hpp:1120:16: error: chosen constructor is explicit in copy-initialization
        return { 0, nullptr, new_tail_size, new_tail };
               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/home/username/tmp/immer/immer/detail/rbts/position.hpp:201:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, false>::visit_leaf<immer::detail::rbts::full_leaf_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
        return Visitor::visit_leaf(*this, std::forward<Args>(args)...);
                        ^
/home/username/tmp/immer/immer/detail/rbts/position.hpp:945:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, true>::visit_regular<immer::detail::rbts::regular_sub_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
        return Visitor::visit_regular(*this, std::forward<Args>(args)...);
                        ^
/home/username/tmp/immer/immer/vector.hpp:293:20: note: in instantiation of member function 'immer::detail::rbts::rbtree<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
    { return impl_.take(elems); }
                   ^
/home/username/tmp/immer/example/vector/vector.cpp:49:22: note: in instantiation of member function 'immer::vector<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
        auto v2 = v1.take(3);
                     ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/5.4.0/../../../../include/c++/5.4.0/tuple:479:19: note: explicit constructor declared here
        constexpr tuple(_UElements&&... __elements)
                  ^
In file included from /home/username/tmp/immer/example/vector/vector.cpp:9:
In file included from /home/username/tmp/immer/immer/vector.hpp:11:
In file included from /home/username/tmp/immer/immer/detail/rbts/rbtree.hpp:13:
/home/username/tmp/immer/immer/detail/rbts/operations.hpp:1092:28: error: chosen constructor is explicit in copy-initialization
                    return { pos.shift(), newn, ts, tail };
                           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/home/username/tmp/immer/immer/detail/rbts/position.hpp:1288:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, false>::visit_regular<immer::detail::rbts::full_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
        return Visitor::visit_regular(*this, std::forward<Args>(args)...);
                        ^
/home/username/tmp/immer/immer/detail/rbts/position.hpp:945:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, true>::visit_regular<immer::detail::rbts::regular_sub_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
        return Visitor::visit_regular(*this, std::forward<Args>(args)...);
                        ^
/home/username/tmp/immer/immer/vector.hpp:293:20: note: in instantiation of member function 'immer::detail::rbts::rbtree<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
    { return impl_.take(elems); }
                   ^
/home/username/tmp/immer/example/vector/vector.cpp:49:22: note: in instantiation of member function 'immer::vector<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
        auto v2 = v1.take(3);
                     ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/5.4.0/../../../../include/c++/5.4.0/tuple:479:19: note: explicit constructor declared here
        constexpr tuple(_UElements&&... __elements)
                  ^
In file included from /home/username/tmp/immer/example/vector/vector.cpp:9:
In file included from /home/username/tmp/immer/immer/vector.hpp:11:
In file included from /home/username/tmp/immer/immer/detail/rbts/rbtree.hpp:13:
/home/username/tmp/immer/immer/detail/rbts/operations.hpp:1120:16: error: chosen constructor is explicit in copy-initialization
        return { 0, nullptr, new_tail_size, new_tail };
               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/home/username/tmp/immer/immer/detail/rbts/position.hpp:108:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, false>::visit_leaf<immer::detail::rbts::leaf_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
        return Visitor::visit_leaf(*this, std::forward<Args>(args)...);
                        ^
/home/username/tmp/immer/immer/detail/rbts/position.hpp:945:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, true>::visit_regular<immer::detail::rbts::regular_sub_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
        return Visitor::visit_regular(*this, std::forward<Args>(args)...);
                        ^
/home/username/tmp/immer/immer/vector.hpp:293:20: note: in instantiation of member function 'immer::detail::rbts::rbtree<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
    { return impl_.take(elems); }
                   ^
/home/username/tmp/immer/example/vector/vector.cpp:49:22: note: in instantiation of member function 'immer::vector<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
        auto v2 = v1.take(3);
                     ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/5.4.0/../../../../include/c++/5.4.0/tuple:479:19: note: explicit constructor declared here
        constexpr tuple(_UElements&&... __elements)
                  ^
In file included from /home/username/tmp/immer/example/vector/vector.cpp:9:
In file included from /home/username/tmp/immer/immer/vector.hpp:11:
In file included from /home/username/tmp/immer/immer/detail/rbts/rbtree.hpp:13:
/home/username/tmp/immer/immer/detail/rbts/operations.hpp:1092:28: error: chosen constructor is explicit in copy-initialization
                    return { pos.shift(), newn, ts, tail };
                           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/home/username/tmp/immer/immer/detail/rbts/position.hpp:297:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, false>::visit_regular<immer::detail::rbts::regular_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
        return Visitor::visit_regular(*this, std::forward<Args>(args)...);
                        ^
/home/username/tmp/immer/immer/detail/rbts/position.hpp:945:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, true>::visit_regular<immer::detail::rbts::regular_sub_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
        return Visitor::visit_regular(*this, std::forward<Args>(args)...);
                        ^
/home/username/tmp/immer/immer/vector.hpp:293:20: note: in instantiation of member function 'immer::detail::rbts::rbtree<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
    { return impl_.take(elems); }
                   ^
/home/username/tmp/immer/example/vector/vector.cpp:49:22: note: in instantiation of member function 'immer::vector<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
        auto v2 = v1.take(3);
                     ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/5.4.0/../../../../include/c++/5.4.0/tuple:479:19: note: explicit constructor declared here
        constexpr tuple(_UElements&&... __elements)
                  ^

Hi, a small pr from me as was discussed earlier.

I was fighting with integer promotion for some time and the only solution I found so far is to use casts for non-const expressions. Otherwise we get popcount() overload ambiguity...

Please take a look and probably you could suggest a better solution for that :)

This is the implementation of a diff algorithm for immer::map. It compares two immer::map instances and calls respective lambda functions when keys were added or removed or when the value of a key changed. When data is shared among the two maps, the algorithm will not need to compare shared subtrees of the map. We plan to use this for an undo feature.

The diff algorithm has following signature: ̂map::diff(map const& other, AddedFn&& added, ChangedFn&& changed, RemovedFn&& Removed) where the lambdas have the signature:

void AddedFn(std::pair<Key, Value> const& added_entry)
void ChangedFn(std::pair<Key, Value> const& old_item, std::pair<Key, Value> const& new_data)
void RemovedFn(std::pair<Key, Value> const& removed_entry)

Usage:

immer::map<int, int> old_snapshot; // initialize somehow
immer::map<int, int> new_snapshot = old_snapshot.set(1,2); // change somehow
old_snapshot.diff(
  new_snapshot,
  [](auto const& added){ std::cout << "added key " << added.first << std::endl; },
  [](auto const& old, auto const& new){
    std::cout << "changed key " << old.first << " from " << old.second << " to " << new.second << std::endl; },
  [](auto const& removed){ std::cout << "removed key " << removed.first << std::endl; }
  );

This signature works for our usecase, however we are happy for further input and would like to help to upstream this feature.

This partially addresses: #120

I still have to refine the implementation, but the idea is clear. I have some issues with building tests, will continue tomorrow.

Looking forward for the review :)

This snippet from immer/immer/detail/hamts/champ.hpp causes an exit-time destructor warning from clang:

    static const champ& empty()
    {
        static const champ empty_{
            node_t::make_inner_n(0),
            0,
        };
        return empty_;
    }

I'll create a pull request to suggest addressing it similarly to what's discussed in this stack-overflow question.

I get a crash on startup, if (and only if) Link-Time Optimization (LLVM_LTO = YES) or optimisations (-O1 or higher) are on:

I'm using Xcode 9.3 on macOS 10.13.2. I suspect the problem might actually be outside of immer, but have you run into this before?

This is a result of https://github.com/arximboldi/immer/issues/244.

This is just an idea how one could make the move constructor and assignment operator noexcept. I used aligned_storage to statically reserve some memory for the nodes.

However, while I type this description I noticed a problem: I'm not familiar with the mechanism the frees memory. There is nothing that prevents the code from attempting to free the statically allocated buffers. A possible solution would be to keep the ref count always above 0.

I looked into making the move constructor (and move-assignment) for flex_vector noexcept. This is something people (at least myself) want to ensure exception safety. Generally you want you types to be nothrow move constructible.

It turns out to be not that trivial: it allocates nodes. This is similar to what the MSVC implementation of std::unordered_map does and it caused me a lot of pain in the past. At least the swap operation is de facto noexcept, but not marked as such.

I propose two solutions:

1. do not allocate anything unless necessary. This would introduce some special cases, where nullptr to head and tail node would indicate an empty flex_vector.
2. This is similar to libstdc++ does for std::unordered_map: store the end nodes within the object itself. This would require to replace the end-nodes with the new end-nodes during a move operation.

I prefer approach 1. Any ideas or opinions? Maybe there is a good reason to not have flex_vectors move constructor and assignment noexcept.

I noticed since champ_iterator() = default; was removed, immer::map no longer satisfies the constraint std::ranges::range, which prevents usage with views, e.g. for(const auto &v : map | std::views::values).

The issue is with std::ranges::end(), but oddly, std::end() compiles fine. I'm not sure if this is a difference in the standard or a compiler issue.

For reference, I'm compiling on MSVC v19.34.31935 (latest version at present time).

I'm happy to submit a PR to reintroduce the default constructor but wanted to check if this is wanted/the right way to go about it.

Essentially, flex_vector can (always?) allocates objects at addresses that do not align with the type's alignment requirements. I uncovered this while using Eigen with immer, which causes some nasty segfaults when there are alignment violations on vectorized types.

I added a repro case here: https://github.com/sissow2/immer/commit/9d295b829c37dbabdb96b4f703ba56492734e76c . The sanity check with std::vector passes always, while the immer::flex_vector variant always fails :

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
flex_vector-alignment is a Catch v2.13.7 host application.
Run with -? for options

-------------------------------------------------------------------------------
direct alignment
-------------------------------------------------------------------------------
/home/sissow2/projects/immer/test/flex_vector/alignment.cpp:32
...............................................................................

... snip ...

/home/sissow2/projects/immer/test/flex_vector/alignment.cpp:41: FAILED:
  CHECK( v[i].is_aligned() )
with expansion:
  false

===============================================================================
test cases: 2 | 1 passed | 1 failed
assertions: 8 | 4 passed | 4 failed

This might be related to https://github.com/arximboldi/immer/issues/228, but the reporter's repro case is for a non-vectorized type so I'm not sure it's the same issue.

I might be able to create a PR with a fix, but wondering if you have any ideas before I dive into it.

Also: I'm really liking this library! This and lager have been making my life so much easier. Also thanks for providing a nix-shell environment, it made creating this repro case a breeze.

immer is available as a port in vcpkg, a C++ library manager that simplifies installation for immerand other project dependencies. Documenting the install process here will help users get started by providing a single set of commands to build immer, ready to be included in their projects.

We also test whether our library ports build in various configurations (dynamic, static) on various platforms (OSX, Linux, Windows: x86, x64, UWP, ARM) to keep a wide coverage for users.

I'm a maintainer for vcpkg, and here is what the port script looks like. We try to keep the library maintained as close as possible to the original library.

Using types like Eigen::Vector3d in structs in variants in flex vectors cause a crash in immer when I

a variant like:

struct a_t{
        Eigen::Vector3d position;
};
struct b_t{
        double x;
};
using nifty_variant = std::variant<a_t, b_t>;

and I try and filter out some of these structs with:

template<typename T>
inline auto filter(const immer::flex_vector<nifty_variant>& buf) {
    immer::flex_vector<T> out{};
    immer::for_each(buf.begin(), buf.end(), [&out](auto a) {
        if (std::holds_alternative<T>(a)) {
            out = move(out).push_back(std::get<T>(a));
        }
    });
    return out;
}

I get segfaults in opt builds, but not in debug builds like:

#0  0x0000000000476478 in immer::detail::rbts::rrbtree< nifty_variant, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024ul>, immer::refcount_policy, immer::spinlock_policy, immer::no_transience_policy, false, true>, 5u, 1u>::push_back_mut(immer::no_transience_policy::apply<immer::free_list_heap_policy<immer::cpp_heap, 1024ul> >::type::edit, nifty_variant) ()