arximboldi / immer Goto Github PK

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

License: Boost Software License 1.0

CMake 0.66% C++ 73.46% JavaScript 23.73% HTML 0.10% Makefile 0.02% Python 0.68% Scheme 0.29% Nix 0.56% Clojure 0.14% Shell 0.03% Scala 0.22% Dockerfile 0.07% Starlark 0.01% Emacs Lisp 0.01% Swift 0.04% GDB 0.01%

immutable data-structures modern-cpp cpp14 rrb-tree persistent postmodernism value-semantics hamt

immer's Introduction

immer is a library of persistent and immutable data structures written in C++. These enable whole new kinds of architectures for interactive and concurrent programs of striking simplicity, correctness, and performance.

Documentation (Contents)
Code (GitHub)
CppCon'17 Talk: Postmodern Immutable Data Structures (YouTube, Slides)
ICFP'17 Paper: Persistence for the masses (Preprint)

This library has full months of pro bono research and development invested in it. This is just the first step in a long-term vision of making interactive and concurrent C++ programs easier to write. Put your logo here and help this project's long term sustainability by buying a sponsorship package: [email protected]

Example

#include <immer/vector.hpp>
int main()
{
    const auto v0 = immer::vector<int>{};
    const auto v1 = v0.push_back(13);
    assert(v0.size() == 0 && v1.size() == 1 && v1[0] == 13);

    const auto v2 = v1.set(0, 42);
    assert(v1[0] == 13 && v2[0] == 42);
}

For a complete example check Ewig, a simple didactic text-editor built with this library. You may also wanna check Lager, a Redux-like library for writing interactive software in C++ using a value-oriented design.

Why?

In the last few years, there has been a growing interest in immutable data structures, motivated by the horizontal scaling of our processing power and the ubiquity of highly interactive systems. Languages like Clojure and Scala provide them by default, and implementations for JavaScript like Mori and Immutable.js are widely used, specially in combination with modern UI frameworks like React.

Interactivity: Thanks to persistence and structural sharing, new values can be efficiently compared with old ones. This enables simpler ways of reasoning about change that sit at the core of modern interactive systems programming paradigms like reactive programming.
Concurrency: Passing immutable data structures by value does not need to copy any data. In the absence of mutation, data can be safely read from multiple concurrent processes, and enable concurrency patterns like share by communicating efficiently.
Parallelism: Some recent immutable data structures have interesting properties like O(log(n)) concatenation, which enable new kinds of parallelization algorithms.

Features

Idiomatic: This library doesn't pretend that it is written in Haskell. It leverages features from recent standards to provide an API that is both efficient and natural for a C++ developer.
Performant: You use C++ because you need this. Immer implements state of the art data structures with efficient cache utilization and have been proven production ready in other languages. It also includes our own improvements over that are only possible because of the C++'s ability to abstract over memory layout. We monitor the performance impact of every change by collecting benchmark results directly from CI.

Customizable: We leverage templates and policy-based design to build data-structures that can be adapted to work efficiently for various purposes and architectures, for example, by choosing among various memory management strategies. This turns immer into a good foundation to provide immutable data structures to higher level languages with a C runtime, like Python or Guile.

Dependencies

This library is written in C++14 and a compliant compiler is necessary. It is continuously tested with Clang 3.8 and GCC 6, but it might work with other compilers and versions.

No external library is necessary and there are no other requirements.

Usage

This is a header only library. You can just copy the immer subfolder somewhere in your include path.

If you are using the Nix package manager (we strongly recommend it) you can just:

nix-env -if https://github.com/arximboldi/immer/archive/master.tar.gz

Alternatively, you can use CMake to install the library in your system once you have manually cloned the repository:

mkdir -p build && cd build
cmake .. && sudo make install

Development

In order to develop the library, you will need to compile and run the examples, tests and benchmarks. These require some additional tools. The easiest way to install them is by using the Nix package manager. At the root of the repository just type:

nix-shell

This will download all required dependencies and create an isolated environment in which you can use these dependencies, without polluting your system.

Then you can proceed to generate a development project using CMake:

mkdir build && cd build
cmake ..

From then on, one may build and run all tests by doing:

make check

In order to build and run all benchmarks when running make check, run cmake again with the option -DCHECK_BENCHMARKS=1. The results of running the benchmarks will be saved to a folder reports/ in the project root.

License

This software is licensed under the Boost Software License 1.0.

The full text of the license is can be accessed via this link and is also included in the LICENSE file of this software package.

immer's People

Contributors

Stargazers

Watchers

Forkers

hbcbh1999 arkadiuszsz jameswann wanjinchang githubch janjanus 4144 arbmind xwyangjshb arcanis loofbon rukor randrew claudiouzelac teamspeak-systems adiog prouschal cmaughan csguth aliaumem filipeoliveiraa lyrl uuhan zjufish davidlarsson apmccartney sassoshots asirobots cmakeezer bansalnvn pboyer ajax14 ascitan fedormatantsev bogdan-morosanu acki-m philippecp buckaroo-pm maddimax codablock gwhk quoinefinancial lahiguera maximus5 myd7349 mrpi ehoeks cgrinker baitcenter runtimeverification vicfred margnus1 zhangyangisme loganbarnes nyanpasu64 bjoe janwojcicki asmyshlyaev ashifriady ikrima fweik ericgebhart gorakhargosh gracicot tiborkiss jeffplaisance chuim dand-oss corristo svengali bellirodrigo2 slburson dejan-stankovic wsafonov rheehot linecode maierlars yanbinchen externalrepositories clemenssielaff adamyg levwi stefan-pdx yohsi kistlin servicefoundation welovebeer dbueno bsap-git topdeckwin aacirino lightengine71 brinkqiang2cpp seewpx basicer stjordanis doytsujin bollu mvtec-richter gomez-addams

immer's Issues

Build error when using nix-shell on Ubuntu 17.04

user@user-desktop:~/dev/_public/immer$ uname -a
Linux user-desktop 4.10.0-35-generic #39-Ubuntu SMP Wed Sep 13 07:46:59 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux

user@user-desktop:~/dev/_public/immer$ git status
On branch master
Your branch is up-to-date with 'origin/master'.
nothing to commit, working tree clean

user@user-desktop:~/dev/_public/immer$ git show
commit 96db817087eddc5037bdd81262f69018b62ad649
Merge: 5a17ebb 3a992eb
Author: arximboldi <[email protected]>
Date:   Wed Sep 27 06:07:45 2017 +0000

    Merge pull request #19 from arximboldi/hamts
    
    Persistent hash maps and sets

user@user-desktop:~/dev/_public/immer$ nix-shell

[nix-shell:~/dev/_public/immer]$ cd build

[nix-shell:~/dev/_public/immer/build]$ cmake ..
-- Found GC library: /usr/lib/x86_64-linux-gnu/libgc.so
-- Boost version: 1.62.0
-- Using ccache: /nix/store/l6kazswxwsp9jb9n7hnf9aclw30hdn6n-ccache-3.3.4/bin/ccache
-- Checking for module 'guile-2.2'
--   No package 'guile-2.2' found
-- Disabling Guile modules
-- Configuring done
-- Generating done
-- Build files have been written to: /home/user/dev/_public/immer/build

[nix-shell:~/dev/_public/immer/build]$ make check
[  1%] Building CXX object example/CMakeFiles/example-vector-intro.dir/vector/intro.cpp.o
In file included from /usr/include/c++/6/ext/string_conversions.h:41:0,
                 from /usr/include/c++/6/bits/basic_string.h:5417,
                 from /usr/include/c++/6/string:52,
                 from /usr/include/c++/6/stdexcept:39,
                 from /usr/include/c++/6/array:39,
                 from /usr/include/c++/6/tuple:39,
                 from /usr/include/c++/6/functional:55,
                 from /usr/include/c++/6/memory:79,
                 from /home/user/dev/_public/immer/immer/detail/util.hpp:28,
                 from /home/user/dev/_public/immer/immer/detail/rbts/node.hpp:25,
                 from /home/user/dev/_public/immer/immer/detail/rbts/rbtree.hpp:23,
                 from /home/user/dev/_public/immer/immer/vector.hpp:23,
                 from /home/user/dev/_public/immer/example/vector/intro.cpp:22:
/usr/include/c++/6/cstdlib:75:25: fatal error: stdlib.h: No such file or directory
 #include_next <stdlib.h>
                         ^
compilation terminated.
make[3]: *** [example/CMakeFiles/example-vector-intro.dir/build.make:63: example/CMakeFiles/example-vector-intro.dir/vector/intro.cpp.o] Error 1
make[2]: *** [CMakeFiles/Makefile2:3580: example/CMakeFiles/example-vector-intro.dir/all] Error 2
make[1]: *** [CMakeFiles/Makefile2:77: CMakeFiles/check.dir/rule] Error 2
make: *** [Makefile:175: check] Error 2

Bogus pybind submodule definition

The .gitmodules file seems to contain a bogus entry for the pybind submodule:

[submodule "extra/python/lib/--force"]
	path = extra/python/lib/--force
	url = https://github.com/pybind/pybind11.git

It looks like the entry that follows is correct:

[submodule "extra/python/lib/pybind11"]
	path = extra/python/lib/pybind11
	url = https://github.com/pybind/pybind11.git

Problem using immer::vector<A> inside class A

Hi. I ran into a problem when trying to pass a immer::vector<A> as an argument to a constructor of A. The minimal code that reproduces the problem is this:

#define USE_IMMER_VECTOR

#ifdef USE_IMMER_VECTOR

#include <immer/vector.hpp>
template <typename T>
using Vector = immer::vector<T>;

#else

#include <vector>
template <typename T>
using Vector = std::vector<T>;

#endif

struct A
{
    A(Vector<A> const &) {}
};

int main()
{
    return 0;
}

If the line #define USE_IMMER_VECTOR is commented then std::vectoris used and everything works fine but, if it is not commented, then immer::vector is used and I get 5 errors that seem related compiling with gcc 6.3.0:

..\..\..\install\release\shared\include/immer/detail/rbts/node.hpp:942:40: error: invalid application of 'sizeof' to incomplete type 'A'
     constexpr auto sizeof_elem = sizeof(T);

..\..\..\install\release\shared\include/immer/detail/util.hpp:35:41: error: invalid application of 'sizeof' to incomplete type 'A'
     typename std::aligned_storage<sizeof(T), alignof(T)>::type;

..\..\..\install\release\shared\include/immer/detail/rbts/node.hpp:124:51: error: 'struct immer::detail::rbts::node<A, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 5u>::leaf_t' has no member named 'buffer'
         return immer_offsetof(impl_t, d.data.leaf.buffer)

..\..\..\install\release\shared\include/immer/detail/rbts/node.hpp:125:23: error: 'buffer' is not a member of 'immer::detail::rbts::node<A, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 5u>::leaf_t'
             +  sizeof(leaf_t::buffer) * count;

..\..\..\install\release\shared\include/immer/detail/rbts/node.hpp:943:85: error: constexpr call flows off the end of the function
     constexpr auto space = node_t::max_sizeof_inner - node_t::sizeof_packed_leaf_n(0);

I don't really know if there is something wrong with immer or if I should be doing things differently.
Thanks.

Restrictive licensing

Nobody can actually use this in non-GPL-compatible codebases, and it makes no sense for a library to be GPL'd.

macOS: Crash on start when enabling Optimizations

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?

extras not compatible with GCC 6.4

When compiling with GCC 6.4, I get this error:
g++.exe: error: unrecognized command line option '-fsanitize-coverage=trace-pc-guard'; did you mean '-fsanitize-coverage=trace-pc'?

It comes from the CMakeLists.txt in the extras folder. Can we not make the extras use the ENABLE_SANITIZER option from the parent? Is trace-pc-guard a Clang-only thing?

Immer releases

Hi,

I am trying to create a conan package for immer and have a problem with the releases of the library. The conan package must reference a release version. However, there is at the moment no tag on the repository identifying the different releases of the library. Would it be feasible to create such tags?

Thanks.

optimised small collections

One of the improvements made in clojure 1.8 was incorporating some work done by Zach Tellman to create 'unrolled' variants of maps and vectors. Essentially, it was a piece of clojure that generated an optimised java class for each size of vector and map up to N (I think N was five or six) so that that costs of creating and querying small vectors and maps was faster. When an operation would make them too big, they turn into the more algorithmically optimal type.

We already have an array and guidance to use it for up to ~100 items but we don't have anything for maps and sets. There is also associated code change when moving from arrays to vector / flex_vector. It would be nice to have a uniform API for this like clojure.

A reasonable first stab at it might just be a small_map that maintained an array of pairs and simply iterated through it instead of doing a hash lookup.

Obviously I haven't done any benchmarking at all and this was work done to clojure's collections which may not directly carry over to immer, but food for thought nonetheless. If there is a performance improvement to be made on small collections, it could make considerable differences in a dynamic language environment where maps are often used for argument passing. I know dynamic languages are an explicit target for you, so probably worth a look?

operator==() may return bad result

Hi !

First off, thanks for this library !

While trying to build my first application with it, I found a pretty sad bug:

In my code, I have a data of type immer::vector<immer::flex_vector>.
After applying a transformation to this data, when checking if something did actually changed, the operator equal regularly return true when it should return false.

The following code will assert (on linux mint 64bit build with clang 3.8.1).

    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); });

    assert(!(v == v1));

Problems with simple v0.push_back(13)

Executing this simple code in Ubuntu 16.04 LTS Server Edition
gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.9)

#include <immer/vector.hpp>

  int main() {

  const auto v0 = immer::vector<int>{};
  const auto v1 = v0.push_back(13);
  return 0;
}

In file included from /usr/include/immer/detail/rbts/rbtree.hpp:24:0,
                 from /usr/include/immer/vector.hpp:23,
                 from simple.cpp:1:
/usr/include/immer/detail/rbts/position.hpp: In instantiation of ‘decltype(auto) immer::detail::rbts::regular_pos<NodeT>::last_oh(Visitor, immer::detail::rbts::count_t, Args&& ...) [with Visitor = immer::detail::rbts::push_tail_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u> >; Args = {immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024ul>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5u, 6u>*&}; NodeT = immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u>; immer::detail::rbts::count_t = unsigned int]’:
/usr/include/immer/detail/rbts/operations.hpp:816:33:   required from ‘immer::detail::rbts::push_tail_visitor<NodeT>::node_t* immer::detail::rbts::visit_regular(immer::detail::rbts::push_tail_visitor<NodeT>::this_t, Pos&&, immer::detail::rbts::push_tail_visitor<NodeT>::node_t*, Args&& ...) [with Pos = immer::detail::rbts::regular_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u> >&; Args = {}; NodeT = immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u>; immer::detail::rbts::push_tail_visitor<NodeT>::node_t = immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u>; immer::detail::rbts::push_tail_visitor<NodeT>::this_t = immer::detail::rbts::push_tail_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u> >]’
/usr/include/immer/detail/rbts/position.hpp:309:29:   required from ‘decltype(auto) immer::detail::rbts::regular_pos<NodeT>::visit(Visitor, Args&& ...) [with Visitor = immer::detail::rbts::push_tail_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u> >; Args = {immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024ul>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5u, 6u>*&}; NodeT = immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u>]’
/usr/include/immer/detail/rbts/position.hpp:652:9:   required from ‘decltype(auto) immer::detail::rbts::last_oh_regular(Pos&&, Visitor, immer::detail::rbts::count_t, Args&& ...) [with Pos = immer::detail::rbts::regular_sub_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u> >&; Visitor = immer::detail::rbts::push_tail_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u> >; Args = {immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024ul>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5u, 6u>*&}; immer::detail::rbts::count_t = unsigned int]’
/usr/include/immer/detail/rbts/position.hpp:874:29:   required from ‘decltype(auto) immer::detail::rbts::regular_sub_pos<NodeT>::last_oh(Visitor, immer::detail::rbts::count_t, Args&& ...) [with Visitor = immer::detail::rbts::push_tail_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u> >; Args = {immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024ul>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5u, 6u>*&}; NodeT = immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u>; immer::detail::rbts::count_t = unsigned int]’
/usr/include/immer/detail/rbts/operations.hpp:816:33:   required from ‘immer::detail::rbts::push_tail_visitor<NodeT>::node_t* immer::detail::rbts::visit_regular(immer::detail::rbts::push_tail_visitor<NodeT>::this_t, Pos&&, immer::detail::rbts::push_tail_visitor<NodeT>::node_t*, Args&& ...) [with Pos = immer::detail::rbts::regular_sub_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u> >&; Args = {}; NodeT = immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u>; immer::detail::rbts::push_tail_visitor<NodeT>::node_t = immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u>; immer::detail::rbts::push_tail_visitor<NodeT>::this_t = immer::detail::rbts::push_tail_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u> >]’
/usr/include/immer/detail/rbts/position.hpp:957:29:   required from ‘decltype(auto) immer::detail::rbts::regular_sub_pos<NodeT>::visit(Visitor, Args&& ...) [with Visitor = immer::detail::rbts::push_tail_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u> >; Args = {immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024ul>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5u, 6u>* const&}; NodeT = immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u>]’
/usr/include/immer/detail/rbts/rbtree.hpp:335:65:   required from ‘immer::detail::rbts::rbtree<T, MemoryPolicy, B, BL> immer::detail::rbts::rbtree<T, MemoryPolicy, B, BL>::push_back(T) const [with T = int; MemoryPolicy = immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>; unsigned int B = 5u; unsigned int BL = 6u]’
/usr/include/immer/vector.hpp:232:46:   required from ‘immer::vector<T, MemoryPolicy, B, BL> immer::vector<T, MemoryPolicy, B, BL>::push_back(immer::vector<T, MemoryPolicy, B, BL>::value_type) const & [with T = int; MemoryPolicy = immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>; unsigned int B = 5u; unsigned int BL = 6u; immer::vector<T, MemoryPolicy, B, BL>::value_type = int]’
simple.cpp:6:34:   required from here
/usr/include/immer/detail/rbts/position.hpp:304:29: error: use of ‘template<class Pos, class Visitor, class ... Args> decltype(auto) immer::detail::rbts::last_oh_regular(Pos&&, Visitor, immer::detail::rbts::count_t, Args&& ...)’ before deduction of ‘auto’
     { return last_oh_regular(*this, v, offset_hint, args...); }
                             ^
/usr/include/immer/detail/rbts/position.hpp:304:29: error: use of ‘decltype(auto) immer::detail::rbts::last_oh_regular(Pos&&, Visitor, immer::detail::rbts::count_t, Args&& ...) [with Pos = immer::detail::rbts::regular_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u> >&; Visitor = immer::detail::rbts::push_tail_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u> >; Args = {immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024ul>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5u, 6u>*&}; immer::detail::rbts::count_t = unsigned int]’ before deduction of ‘auto’
In file included from /usr/include/immer/detail/rbts/rbtree.hpp:25:0,
                 from /usr/include/immer/vector.hpp:23,
                 from simple.cpp:1:
/usr/include/immer/detail/rbts/operations.hpp: In instantiation of ‘immer::detail::rbts::push_tail_visitor<NodeT>::node_t* immer::detail::rbts::visit_regular(immer::detail::rbts::push_tail_visitor<NodeT>::this_t, Pos&&, immer::detail::rbts::push_tail_visitor<NodeT>::node_t*, Args&& ...) [with Pos = immer::detail::rbts::regular_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u> >&; Args = {}; NodeT = immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u>; immer::detail::rbts::push_tail_visitor<NodeT>::node_t = immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u>; immer::detail::rbts::push_tail_visitor<NodeT>::this_t = immer::detail::rbts::push_tail_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u> >]’:
/usr/include/immer/detail/rbts/position.hpp:309:29:   required from ‘decltype(auto) immer::detail::rbts::regular_pos<NodeT>::visit(Visitor, Args&& ...) [with Visitor = immer::detail::rbts::push_tail_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u> >; Args = {immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024ul>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5u, 6u>*&}; NodeT = immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u>]’
/usr/include/immer/detail/rbts/position.hpp:652:9:   required from ‘decltype(auto) immer::detail::rbts::last_oh_regular(Pos&&, Visitor, immer::detail::rbts::count_t, Args&& ...) [with Pos = immer::detail::rbts::regular_sub_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u> >&; Visitor = immer::detail::rbts::push_tail_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u> >; Args = {immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024ul>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5u, 6u>*&}; immer::detail::rbts::count_t = unsigned int]’
/usr/include/immer/detail/rbts/position.hpp:874:29:   required from ‘decltype(auto) immer::detail::rbts::regular_sub_pos<NodeT>::last_oh(Visitor, immer::detail::rbts::count_t, Args&& ...) [with Visitor = immer::detail::rbts::push_tail_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u> >; Args = {immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024ul>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5u, 6u>*&}; NodeT = immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u>; immer::detail::rbts::count_t = unsigned int]’
/usr/include/immer/detail/rbts/operations.hpp:816:33:   required from ‘immer::detail::rbts::push_tail_visitor<NodeT>::node_t* immer::detail::rbts::visit_regular(immer::detail::rbts::push_tail_visitor<NodeT>::this_t, Pos&&, immer::detail::rbts::push_tail_visitor<NodeT>::node_t*, Args&& ...) [with Pos = immer::detail::rbts::regular_sub_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u> >&; Args = {}; NodeT = immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u>; immer::detail::rbts::push_tail_visitor<NodeT>::node_t = immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u>; immer::detail::rbts::push_tail_visitor<NodeT>::this_t = immer::detail::rbts::push_tail_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u> >]’
/usr/include/immer/detail/rbts/position.hpp:957:29:   required from ‘decltype(auto) immer::detail::rbts::regular_sub_pos<NodeT>::visit(Visitor, Args&& ...) [with Visitor = immer::detail::rbts::push_tail_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u> >; Args = {immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024ul>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5u, 6u>* const&}; NodeT = immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5u, 6u>]’
/usr/include/immer/detail/rbts/rbtree.hpp:335:65:   required from ‘immer::detail::rbts::rbtree<T, MemoryPolicy, B, BL> immer::detail::rbts::rbtree<T, MemoryPolicy, B, BL>::push_back(T) const [with T = int; MemoryPolicy = immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>; unsigned int B = 5u; unsigned int BL = 6u]’
/usr/include/immer/vector.hpp:232:46:   required from ‘immer::vector<T, MemoryPolicy, B, BL> immer::vector<T, MemoryPolicy, B, BL>::push_back(immer::vector<T, MemoryPolicy, B, BL>::value_type) const & [with T = int; MemoryPolicy = immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>; unsigned int B = 5u; unsigned int BL = 6u; immer::vector<T, MemoryPolicy, B, BL>::value_type = int]’
simple.cpp:6:34:   required from here
/usr/include/immer/detail/rbts/operations.hpp:817:52: error: second operand to the conditional operator is of type ‘void’, but the third operand is neither a throw-expression nor of type ‘void’
                 /* otherwise */ : node_t::make_path(pos.shift() - B, tail);

How to fix the problem?
Marco

Runtime assertion fail when brace initializing a flex_vector in global scope

The code is this:

#include <immer/flex_vector.hpp>

immer::flex_vector<int> v{1};

int main()
{
    return 0;
}

And the runtime assertion message:

Assertion failed!

Program: D:\projects\build\test\immer_test\debug\immer_test.exe
File: D:/projects/install/debug/include/immer/detail/rbts/rrbtree.hpp, Line 1174

Expression: shift >= BL

This application has requested the Runtime to terminate it in an unusual way.
Please contact the application's support team for more information.

Environment info:
Compiler: GCC 7.3.0, under MSYS2/MinGW64
Platform: Windows 10, 64 bits

Can't access your website

Trying to access your website in Chrome/Firefox/Safari on multiple devices and on all of them I'm getting:

sinusoid.es uses an unsupported protocol.
ERR_SSL_VERSION_OR_CIPHER_MISMATCH

Feature request: mutation interface for transient iterators

UPDATE: I misread ::update in the docs before writing my thoughts below.

Perhaps T& immer::vector_transient<T>::iterator::mutable_dereference()?
Also T& immer::vector_transient<T>::mutable_at(size_t index)?

These operations would copy if shared before providing the reference to maintain valid copy-on-write semantics.

I'm trying to implement scalar multiplication (and others) efficiently in a virtual machine. Mutating elements in-place makes a difference for e.g. scalar multiplying a vector of vectors.

This would require the caller being responsible for ensuring usage of the reference isn't improperly combined with a variety of immer operations though, so that could be a bit messy actually :/.

In general, I am concerned with achieving in-place mutation as often as possible in a variety of cases. Do you think immer would still be a practical choice for this?

How practical would it be to use the immer::detail constructs directly? (Understanding that these APIs may change, of course.)

Perhaps there could be raw_vector and raw_flex_vector exposing more of the internals (and footguns), and vector, flex_vector could be implemented as wrappers but expose incompatible APIs. Possibly a lot of work for a possibly narrow use case though.

Assertion failure on mingw 32bit builds

#76 introduced the use of alignof(std::max_align_t) to determine the offset of the size value inside the allocated memory.

There is however an issue when built with mingw and 32bits. The bug described in https://sourceforge.net/p/mingw-w64/bugs/778/ results in extra_size being different, depending on the order of inclusion of immer headers and standard headers.

In my specific case, this results in allocation happening with extra_size being 16 and deallocation happening with extra_size being 8, which then causes the assertion in debug_size_heap::deallocate to fail.

I was considering creating a PR, but then was not sure how to fix this so that it would be accepted. Possible solution would be to fix extra_size to always be 8 bytes (e.g. 2 * sizeof(void*)) when mingw+32bit is detected. I don't see how this can be fixed through the inclusion order, as inside immer you have no control about what was included before the first immer header.

Compatibility with GCC 5/Ubuntu 14.04 LTS

Are you interested in patches for support with the default GCC 5.4.1 on Ubuntu 14.04? Even compiling with C++14, there are issues with some braced initializer lists and uses of decltype(auto). I initially made some local changes for this, but ran into some difficulty understanding your usage of std::get on the result of visit_maybe_relaxed_sub in rrbtree.hpp, since regular_sub_pos<NodeT> and relaxed_pos<NodeT> appear to be different classes, and don't fit any of the default overloads for std::tuple, std::variant, std::pair, etc.

I also ran into similar issues with Clang 5.0, until I installed GCC 6.0 and Clang 5.0 selected the system headers bundled with GCC 6.0 by default.

Transient write on vector of boxes

I'm trying to use vector of boxes and everything woks fine until transient write is used.

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();

Any ideas?

Serialization

Hi @arximboldi!

Thanks for authoring this library! I was curious if you've thought of any approaches or patterns for serialization. I have a use case where I would love to build an immutable data structure that is serializable via a library like Cap'n Proto (👋 @kentonv) so that I can access larger datasets via memory-mapped files. Do you have any immediate thoughts or ideas on how immer could serialize its data efficiently?

Cheers!

Storing abstract types

Hi, I want to use immer to store a very simple json-like structure. There are 4 types of values that can be stored, and I want to recur by storing a base class pointer in the collection types.

I figured box would be perfect for storing this, but the compiler doesn't allow storing abstract types in it. Is there a way around this, or is there an accepted alternative way of storing such values?

-Werror=unused-parameter triggers on Release builds

When turning warnings into errors and disabling asserts in release builds, some function parameters used just in asserts get flagged as unused variables and the build fails. My current company is investigating using this library in our production code, so changing the compilation flags is not an option.

I am willing to fix this issue but unsure how to proceed. Could you please provide some short guidance related to this?

Segmentation fault with recursive types

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;
}

demonstration of the advantage

I just viewed your lightning talk at Meeting C++ 2016 on Youtube. This sounded very familiar.
We experimented with persistent data structures a couple of years ago.
Things went well until, we tried to demonstrate the advantages in a real use case.
We simply could not find any use case, where persistent data structures were able to outperform a more simple implementation.
This does not mean they don't exist.

I'm curious if you have found a practical example.

In theory there should be some benefits, but it would help to convince me/us with a practical application.

Single threaded applications are much faster with std::vector or std. associative containers with tweaked allocators.
Even for multithreaded applications it is most often faster to duplicate the vector content. Copy is quite fast and all changes will be thread local.
The other issue is synchronization with persistent data structures, you easily end up with a version for each thread. Most often this is not what was intended.
So most of our applications needed a single threaded repository that serializes all changes and manages integrity.

Sorry for being a bit pessimistic here. I hope you can prove me wrong.

Runtime assertion fail when trying to access flex_vector contents via iterator

I don't really understand what is going on here, if it's something wrong with immer or if it's my low skills.
The problem in the following code is trying to access the iterator thru some functions:

#include <immer/flex_vector.hpp>
#include <immer/box.hpp>
#include <iostream>

struct A
{
    
    immer::flex_vector<immer::box<int>> v{1, 2, 3};

    auto vector() const
    {
        return v;
    }

    auto begin() const
    {
        return vector().begin();
    }

    auto end() const
    {
        return vector().end();
    }
};

int main()
{
    A a;

    for (auto i = a.begin(); i != a.end(); ++i)
        std::cout << (**i) << std::endl;
        
    // for (auto i = a.vector().begin(); i != a.vector().end(); ++i)
    //     std::cout << (**i) << std::endl;

    return 0;
}

If you try the commented code instead of the other, it works. As I said, I'm kind of lost...
The assertion message is:

Assertion failed!

Program: D:\projects\build\test\immer_test\debug\immer_test.exe
File: D:/projects/install/debug/include/immer/detail/rbts/node.hpp, Line 183

Expression: kind() == kind_t::inner

This application has requested the Runtime to terminate it in an unusual way.
Please contact the application's support team for more information.

Environment info:
Compiler: GCC 7.3.0, under MSYS2/MinGW64
Platform: Windows 10, 64 bits

Strategy for comparing vectors

When comparing two immer::vectors, it should be possible (if I understand the underlying structure correctly) to quickly find the first element that is different (assuming it is unlikely to encounter large equal ranges that don't share structure). But I don't see any methods currently that would let me do this.

Is there a way to do this with immer or any intention to add a feature that enables it?

Assertion failure with immer::flex_vector_transient

I have a small dummy program that appends and erases unsigned integers from an immer::flex_vector_transient. By default, I understand that the container will use immer::refcount_policy (with immer::no_transience_policy), and everything works fine.

Since the keys are just unsigned integers (32-bits), I'd like to disable reference counting in order to measure the runtime overhead. By changing the container to use immer::no_refcount_policy, this automatically selects immer:: gc_transience_policy, which leaks memory without the Boehm GC (as stated in the documentation).

I don't care about the memory leak since this is just a test program, but I encounter an assertion failure at runtime that is unexpected:
test: ../../immer/immer/detail/rbts/position.hpp:160: leaf_sub_pos<NodeT> immer::detail::rbts::make_leaf_sub_pos(NodeT *, immer::detail::rbts::count_t) [NodeT = immer::detail::rbts::node<unsigned int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::no_refcount_policy, immer::gc_transience_policy, false, false>, 5, 6>]: Assertion 'count <= branches<NodeT::bits_leaf>' failed.

Is this supposed to occur? If I manually choose immer::no_transience_policy, the assertion doesn't fail. This is the test program: test.txt

immer::vector<int> constructor fails to compile

The constructor immer::vector<int> aa(1,2); fails to compile whereas immer::vector<int> aa(1,2.0); is fine. It appears that the wrong constructor is being deduced in the first instance.

This is with gcc version 7.2.0 (Ubuntu 7.2.0-1ubuntu1~16.04) which reports the following error:

In file included from lib/immer/vector.hpp:23:0,
                 from test.cpp:1:
lib/immer/detail/rbts/rbtree.hpp: In instantiation of ‘static auto immer::detail::rbts::rbtree<T, MemoryPolicy, B, BL>::from_range(Iter, Iter) [with Iter = int; T = int; MemoryPolicy = immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>; unsigned int B = 5; unsigned int BL = 6]’:
lib/immer/vector.hpp:130:35:   required from ‘immer::vector<T, MemoryPolicy, B, BL>::vector(Iter, Iter) [with Iter = int; T = int; MemoryPolicy = immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>; unsigned int B = 5; unsigned int BL = 6]’
test.cpp:5:26:   required from here
lib/immer/detail/rbts/rbtree.hpp:68:37: error: invalid type argument of unary ‘*’ (have ‘int’)
             result.push_back_mut(e, *first);

error when erasing an element from a immer::flex_vector<std::variant/optional/any>

If I use a std::variant or std::optional or std::any with an immer::flex_vector like in this code:

#include <immer/flex_vector.hpp>
#include <variant>
// #include <optional>
// #include <any>

int main()
{
    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);
    
    return 0;
}

I get the following error when trying to erase an element:

error: call of overloaded 'uninitialized_move(std::variant<int, double>*, std::variant<int, double>*, std::variant<int, double>*)' is ambiguous

Full output:

[build] Starting build
[proc] Executing command: d:\msys64\mingw64\bin\cmake.EXE --build d:/projects/build/test/immer_test/debug --config Debug --target all -- -j 6
[build] Scanning dependencies of target immer_test
[build] [ 50%] Building CXX object CMakeFiles/immer_test.dir/test02.cpp.obj
[build] In file included from D:/projects/install/debug/include/immer/flex_vector.hpp:23:0,
[build]                  from D:\projects\src\test\immer_test\test02.cpp:1:
[build] D:/projects/install/debug/include/immer/detail/rbts/rrbtree.hpp: In instantiation of 'void immer::detail::rbts::concat_mut_lr_l(immer::detail::rbts::rrbtree<std::variant<int, double>, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5, 4>&, immer::detail::rbts::rrbtree<std::variant<int, double>, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5, 4>::edit_t, immer::detail::rbts::rrbtree<std::variant<int, double>, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5, 4>&, immer::detail::rbts::rrbtree<std::variant<int, double>, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>, 5, 4>::edit_t)':
[build] D:/projects/install/debug/include/immer/flex_vector.hpp:505:22:   required from 'static immer::flex_vector<T, MemoryPolicy, B, BL>&& immer::flex_vector<T, MemoryPolicy, B, BL>::concat_move(std::true_type, immer::flex_vector<T, MemoryPolicy, B, BL>&&, immer::flex_vector<T, MemoryPolicy, B, BL>&&) [with T = std::variant<int, double>; MemoryPolicy = immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>; unsigned int B = 5; unsigned int BL = 4; std::true_type = std::integral_constant<bool, true>]'
[build] D:/projects/install/debug/include/immer/flex_vector.hpp:371:25:   required from 'decltype(auto) immer::operator+(immer::flex_vector<std::variant<int, double> >&&, immer::flex_vector<std::variant<int, double> >&&)'
[build] D:/projects/install/debug/include/immer/flex_vector.hpp:424:24:   required from 'immer::flex_vector<T, MemoryPolicy, B, BL> immer::flex_vector<T, MemoryPolicy, B, BL>::erase(immer::flex_vector<T, MemoryPolicy, B, BL>::size_type) const & [with T = std::variant<int, double>; MemoryPolicy = immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>; unsigned int B = 5; unsigned int BL = 4; immer::flex_vector<T, MemoryPolicy, B, BL>::size_type = long long unsigned int]'
[build] D:\projects\src\test\immer_test\test02.cpp:14:26:   required from here
[build] D:/projects/install/debug/include/immer/detail/rbts/rrbtree.hpp:962:39: error: call of overloaded 'uninitialized_move(std::variant<int, double>*, std::variant<int, double>*, std::variant<int, double>*)' is ambiguous
[build]                      uninitialized_move(r.tail->leaf(),
[build]                      ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
[build]                                         r.tail->leaf() + r.size,
[build]                                         ~~~~~~~~~~~~~~~~~~~~~~~~
[build]                                         l.tail->leaf() + tail_size);
[build]                                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~
[build] In file included from D:/projects/install/debug/include/immer/detail/rbts/node.hpp:25:0,
[build]                  from D:/projects/install/debug/include/immer/detail/rbts/rrbtree.hpp:24,
[build]                  from D:/projects/install/debug/include/immer/flex_vector.hpp:23,
[build]                  from D:\projects\src\test\immer_test\test02.cpp:1:
[build] D:/projects/install/debug/include/immer/detail/util.hpp:43:6: note: candidate: auto immer::detail::uninitialized_move(Iter1, Iter1, Iter2) [with Iter1 = std::variant<int, double>*; Iter2 = std::variant<int, double>*]
[build]  auto uninitialized_move(Iter1 in1, Iter1 in2, Iter2 out)
[build]       ^~~~~~~~~~~~~~~~~~
[build] In file included from d:/msys64/mingw64/include/c++/7.3.0/memory:65:0,
[build]                  from D:/projects/install/debug/include/immer/detail/util.hpp:28,
[build]                  from D:/projects/install/debug/include/immer/detail/rbts/node.hpp:25,
[build]                  from D:/projects/install/debug/include/immer/detail/rbts/rrbtree.hpp:24,
[build]                  from D:/projects/install/debug/include/immer/flex_vector.hpp:23,
[build]                  from D:\projects\src\test\immer_test\test02.cpp:1:
[build] d:/msys64/mingw64/include/c++/7.3.0/bits/stl_uninitialized.h:862:5: note: candidate: _ForwardIterator std::uninitialized_move(_InputIterator, _InputIterator, _ForwardIterator) [with _InputIterator = std::variant<int, double>*; _ForwardIterator = std::variant<int, double>*]
[build]      uninitialized_move(_InputIterator __first, _InputIterator __last,
[build]      ^~~~~~~~~~~~~~~~~~
[build] In file included from D:/projects/install/debug/include/immer/flex_vector.hpp:23:0,
[build]                  from D:\projects\src\test\immer_test\test02.cpp:1:
[build] D:/projects/install/debug/include/immer/detail/rbts/rrbtree.hpp:975:39: error: call of overloaded 'uninitialized_move(std::variant<int, double>*, std::variant<int, double>*, std::variant<int, double>*)' is ambiguous
[build]                      uninitialized_move(r.tail->leaf(),
[build]                      ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
[build]                                         r.tail->leaf() + remaining,
[build]                                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~
[build]                                         l.tail->leaf() + tail_size);
[build]                                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~
[build] In file included from D:/projects/install/debug/include/immer/detail/rbts/node.hpp:25:0,
[build]                  from D:/projects/install/debug/include/immer/detail/rbts/rrbtree.hpp:24,
[build]                  from D:/projects/install/debug/include/immer/flex_vector.hpp:23,
[build]                  from D:\projects\src\test\immer_test\test02.cpp:1:
[build] D:/projects/install/debug/include/immer/detail/util.hpp:43:6: note: candidate: auto immer::detail::uninitialized_move(Iter1, Iter1, Iter2) [with Iter1 = std::variant<int, double>*; Iter2 = std::variant<int, double>*]
[build]  auto uninitialized_move(Iter1 in1, Iter1 in2, Iter2 out)
[build]       ^~~~~~~~~~~~~~~~~~
[build] In file included from d:/msys64/mingw64/include/c++/7.3.0/memory:65:0,
[build]                  from D:/projects/install/debug/include/immer/detail/util.hpp:28,
[build]                  from D:/projects/install/debug/include/immer/detail/rbts/node.hpp:25,
[build]                  from D:/projects/install/debug/include/immer/detail/rbts/rrbtree.hpp:24,
[build]                  from D:/projects/install/debug/include/immer/flex_vector.hpp:23,
[build]                  from D:\projects\src\test\immer_test\test02.cpp:1:
[build] d:/msys64/mingw64/include/c++/7.3.0/bits/stl_uninitialized.h:862:5: note: candidate: _ForwardIterator std::uninitialized_move(_InputIterator, _InputIterator, _ForwardIterator) [with _InputIterator = std::variant<int, double>*; _ForwardIterator = std::variant<int, double>*]
[build]      uninitialized_move(_InputIterator __first, _InputIterator __last,
[build]      ^~~~~~~~~~~~~~~~~~
[build] mingw32-make.exe[2]: *** [CMakeFiles\immer_test.dir\build.make:63: CMakeFiles/immer_test.dir/test02.cpp.obj] Error 1
[build] mingw32-make.exe[1]: *** [CMakeFiles\Makefile2:67: CMakeFiles/immer_test.dir/all] Error 2
[build] mingw32-make.exe: *** [Makefile:83: all] Error 2
[build] Build finished with exit code 2

equivalent of "update all" ?

I was surprised that the for_each methods for immer did not return a new collection. What's the right way to clone my immutable vector whilst modifying each element? Or is there a way to use std::transform with immer? Picture a collection of geometric points where I need to translate them all by the same value.

splitting a vector at an index (and other such functions)

Hi, what's your thinking on how to handle such functions? My intuition says they probably belong in immer::algorithm and that in the future there can be some nice concepts collection that abstract over the various types?

I'm now using immer quite avidly in a soon-to-be-open-sourced project so I'd be happy to contribute some time to add functions like this if you don't mind offering guidance and answering questions.

Feature Request: Vector constructor from iterator and sentinel

Firstly, thank you for authoring this library. It's a wonderful contribution to the C++ open source community.

I would propose an additional constructor for immer::vector from an iterator and sentinel, similar to the existing constructor accepting two iterators. Here, by sentinel, I mean value of a type equality comparable to an instance of the iterator type.

My motivation for this request is to improve interoperability with the lazy ranges provided by the range v3 library. In many of these types, the begin and end methods return values of distinct types. Eric Niebler provides some justification for this peculiarity on his blog here.

dec_unsafe leads to memory leaks?

I am having trouble understanding the need for the dec_unsafe function in refcount_policy. This function simply decrements the reference count without returning true if the count drops to 0. So if dec_unsafe is used and the count drops to 0, doesn't this mean that an object has no references but is not freed?

Missing semicolon in README example

const auto v0 = immer::vector<int>{} // missing ;

Add support for VS 2017

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?

compilation error with Clang 5.0.1 on Windows

When compiling with Clang 5.0.1 on Windows I get this error:

In file included from C:/Workspace/ceg/cmake-build-debug/immer-src\immer/flex_vector.hpp:25:
In file included from C:/Workspace/ceg/cmake-build-debug/immer-src\immer/memory_policy.hpp:24:
In file included from C:/Workspace/ceg/cmake-build-debug/immer-src\immer/heap/heap_policy.hpp:26:
C:/Workspace/ceg/cmake-build-debug/immer-src\immer/heap/thread_local_free_list_heap.hpp:44:39: error: cannot compile this non-trivial TLS destruction yet
thread_local_free_list_storage<Heap>::head {nullptr, 0};

I do not see any errors with GCC 7.3

Double Free issue

While working with immer::map I ran into a double free issue.

In immer/detail/hamts/node.hpp the functions static void delete_values(values_t* p, count_t n) and static void delete_collision(node_t* p) call destroy_n and then deallocate_values / deallocate_collission which then again call destroy_n on the same data.

Map with B>5 will not work (silently)

Firstly, thanks for publishing Immer. It's very useful and it's a great source of inspiration at the same time.

I was playing around with my own implementation of CHAMP map and faced with a popcount problem: gcc's popcount is for 32 ints (it just ignores extra bits), but I used 6 branches per node, hence the fix for me was to use __builtin_popcountll()
instead.
I looked through immer's map implementation and didn't find any checks for B. I had no time to actually check it, but it looks like the map is broken for B = 6 and it will consider a lot of data as collision so performance is lost silently.

If you consider this as a bug, we could collaborate further on that.

Status of diff & patch

Juanpe,

I'm currently considering options to simplify the application state management in a large app. So far the whole app has been coded imperatively and it gets somewhat tricky because one requirement we have is to track and send updates externally of only the state that has changed. It's becoming somewhat unmanageable as more new global features are being added...I guess we're just reaching the point of diminishing returns with the current approach. So I started looking into functional programming techniques which led me to immutable data structures and I came across your library. This is exciting stuff. One thing that is holding me back though from testing immer is the lack of diff / patch support. Since high performance is also a requirement but since we need to be very aware of updating only what has changed, support for efficient diffing would be essential. What is the status of this? And what is the level of difficulty to implement it?

CMake enhancements

Hello @arximboldi

I would like to embellish the CMake support provided by the library. Namely,

support Catch-style subproject composition
provide an installation target and CMake configuration exports, to simplify downstream consumption
provide integration with CTest, to provide enhanced testing facilities and result collection
provide integration with CPack, to support the generation of installation packages, e.g.
- deb and rpm archives for Linux
- dmg images for macOS
- NSIS installation wizards for Windows

I've contributed this sort of support to several other projects. See frozen and stlab for examples of what this ends up looking like.

Add support for incomplete types

The STL containers do not support incomplete types. This is particularly true for Immer containers, since a lot of optimizations for better cache locality rely on compile-time computation on the size of the held type. However, it would be nice to have a mode of operation for these containers in which locality is traded for the posibility of storing incomplete types, which are extremely useful when defining recursive data-structures.

Persistent Maps

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

comparison with phil nash's hamts?

Hi,

They published Phil Nash's HAMT talk from cppcon yesterday on youtube. His talk notes page has a link to immer, so I'm guessing you talked :) My question is how immer's HAMTs compare to phil's, broadly. I saw from the talk there are a few optimisations he's missing (some of which he even mentions), but is there anywhere his HAMT has the edge over immer's? if so, let's steal ideas!

Performance?

I've tried something working in Visual Studio (one of the pull requests) and performance results for flex_vector were worse than for usage of std::vector exploiting c++11/14 move semantics when returning result of concatenation of 2 vectors from the functions (keeping the code persistent/thread-safe). Vectors were of the small size (<25).

Before digging any further I wanted to ask if you have any performance data points.

I also noticed some std::atomic instances in the code which raise a question about thread concurrency issues.

C++17 [[nodiscard]]

Motivation:
It is very easy for most C++ developers to write vec.push_back(); instead of vec = vec.push_back();. Currently no warnings are generated for this error.

Solution:
Almost all functions should be annotated with [[nodiscard]] on compilers which support it.

Notes:

If detecting supported compilers is a problem then a macro which can be defined in the build process is a potential workaround.
Due to a bug with warn_unused_result detailed here (and still not fixed), using GNU extensions isn't a good path.

erase() with iterator

First off, thank you for this nice library!

I would like to use flex_vector's erase() together with std::find_if. Now, find_if returns an iterator, and erase() only accepts an index. Right now I'm using std::distance, but that has linear complexity (or is the iterator a RandomAccessIterator?).

Would it be possible to add an overload for erase() that takes an iterator?

Iterating over the vector using a for loop would mean that I have to use operator[] on every iteration, which is effectively O(1). Maybe that's the better option for now? In any case, find_if would arguably be the better code on my part.

Support for localised heaps

I'm integrating with a tracing garbage collector, but I have many heaps (i've got erlang-style processes each with their own heap). As I understand it from the documentation, this is not currently possible.

Is there anything I can do to help with the support for this?

Two dimensions vector

I tried to instanciate a two-dimensions vector (immer::vector<immer::vector<int>>), but got the following error:

3rdparty/immer/includes/immer/vector.hpp:83:37: error: non-type template argument is not a constant expression
          detail::rbts::bits_t BL = detail::rbts::derive_bits_leaf<T, MemoryPolicy, B>>

Have you considered supporting nested structures?

does this integrate with the RangeV3 library?

How does this library integrate with the RangeV3 library? Is there overlap in functionality? Can the collections here be used as backing storage for the RangeV3 iterators?

Suggestion: pseudo-dynamic immutable records with lenses

I'm a bit new to C++ and most of my experience is in FP languages, so please shoot me down if this is a terrible suggestion. However, here goes...

I recently watched the CppCon 2017 talk and greatly enjoyed it. One of the questions at the end got me thinking: can this library help with creating user-defined immutable data types? Furthermore, can we get some of the benefits of Clojure's dynamism by having the underlying data representation be arbitrarily extensible? And can we make it ergonomic by borrowing some more concepts from FP, namely lenses?

Here's the idea. Firstly, have the "record" type backed by a const immer::map<std::string, std::shared_ptr<void>>. Define suitable constructors which take the possible combinations of arguments and initialise the map. Define helper functions which write to or read from the map in a strongly-typed manner (applying the necessary casts to and from shared_ptr). Of course, writing is an immutable operation, so you get a new value as a result, with the benefits of structural sharing. Define a lens type so that for every field with a getter and setter, you can have a lens. The lenses can be compositional. This way, you could drill into arbitrarily deep hierarchies of these record types and manipulate the field you are interested in.

Here's an example of the basic underlying implementation which I have in mind:

class person {
public:
    person(
            const std::shared_ptr<std::string>& name,
            const std::shared_ptr<uint8_t>& age) :
            _data(immer::map<std::string, std::shared_ptr<void>>()
                          .set(_name, std::static_pointer_cast<void>(name))
                          .set(_age, std::static_pointer_cast<void>(age)))
    { }

    std::shared_ptr<const std::string> get_name() const
    {
        return std::static_pointer_cast<const std::string>(_data[_name]);
    }

    const person set_name(const std::shared_ptr<std::string>& name) const
    {
        return person(_data.set(_name, std::static_pointer_cast<void>(name)));
    }

    std::shared_ptr<const uint8_t> get_age() const
    {
        return std::static_pointer_cast<const uint8_t>(_data[_age]);
    }

    const person set_age(const std::shared_ptr<uint8_t>& age) const
    {
        return person(_data.set(_age, std::static_pointer_cast<void>(age)));
    }

private:
    explicit person(immer::map<std::string, std::shared_ptr<void>> data) : _data(std::move(data)) { }

    const immer::map<std::string, std::shared_ptr<void>> _data;

    static constexpr char _name[] { "name" };
    static constexpr char _age[] { "age" };
};

constexpr char person::_name[];
constexpr char person::_age[];

Then, in use:

auto john = person(
        std::make_shared<std::string>("John Smith"),
        std::make_shared<uint8_t>(42));

auto junior = john
        .set_name(std::make_shared<std::string>("Johnny Junior"))
        .set_age(std::make_shared<uint8_t>(12));

std::cout << *john.get_name() << ", age: " << +*john.get_age() << std::endl;
std::cout << *junior.get_name() << ", age: " << +*junior.get_age() << std::endl;

I also wonder if, using a clever enough template, the record definition could be made to look something like:

class person : public record<
        field<std::string, "name">,
        field<uint8_t, "age">> { };

With the combination of string interning for the field names, I think this could be made performant (certainly on par with Clojure).

What do you think?

Any planned integration with Atria

First and foremost, fantastic work here and your ICFP paper was a nice read.

I was curious if you have given any thought to your previous work on Atria and building additional capabilities (or even compatibility) with immer.

License Change?

I read on reddit that you are planning a license change to a more liberal license.
When is that expected and what license might that be?

jemalloc memory allocation strategy

Folly, a library developed by Facebook provides containers with specific memory allocation strategies using jemalloc's ~~private~~ non-standard APIs.
I wonder if we could do the same for immer.
Since persistent/immutable data structures are used in concurrent applications using jemalloc will improve the performance of the containers we provide.