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

Change-Id: I9636a41ad44b4218293833fd3e9456d9b07c731b

15 files changed, 531 insertions, 0 deletions

diff --git a/third_party/immer/example/CMakeLists.txt b/third_party/immer/example/CMakeLists.txt
new file mode 100644
index 000000000000..2aa0f554279d
--- /dev/null
+++ b/third_party/immer/example/CMakeLists.txt
@@ -0,0 +1,17 @@
+
+#  Targets
+#  =======
+
+add_custom_target(examples
+  COMMENT "Build all examples.")
+add_dependencies(check examples)
+
+file(GLOB_RECURSE immer_examples "*.cpp")
+foreach(_file IN LISTS immer_examples)
+  immer_target_name_for(_target _output "${_file}")
+  add_executable(${_target} EXCLUDE_FROM_ALL "${_file}")
+  add_dependencies(examples ${_target})
+  set_target_properties(${_target} PROPERTIES OUTPUT_NAME ${_output})
+  target_link_libraries(${_target} PUBLIC immer-dev)
+  add_test("example/${_output}" ${_output})
+endforeach()
diff --git a/third_party/immer/example/array/array.cpp b/third_party/immer/example/array/array.cpp
new file mode 100644
index 000000000000..43972ad61a21
--- /dev/null
+++ b/third_party/immer/example/array/array.cpp
@@ -0,0 +1,54 @@
+//
+// immer: immutable data structures for C++
+// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
+//
+// This software is distributed under the Boost Software License, Version 1.0.
+// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
+//
+
+#include <immer/array.hpp>
+
+#include <cassert>
+
+int main()
+{
+    {
+        // include:push-back/start
+        auto v1 = immer::array<int>{1};
+        auto v2 = v1.push_back(8);
+
+        assert((v1 == immer::array<int>{1}));
+        assert((v2 == immer::array<int>{1, 8}));
+        // include:push-back/end
+    }
+
+    {
+        // include:set/start
+        auto v1 = immer::array<int>{1, 2, 3};
+        auto v2 = v1.set(0, 5);
+
+        assert((v1 == immer::array<int>{1, 2, 3}));
+        assert((v2 == immer::array<int>{5, 2, 3}));
+        // include:set/end
+    }
+
+    {
+        // include:update/start
+        auto v1 = immer::array<int>{1, 2, 3, 4};
+        auto v2 = v1.update(2, [&](auto l) { return ++l; });
+
+        assert((v1 == immer::array<int>{1, 2, 3, 4}));
+        assert((v2 == immer::array<int>{1, 2, 4, 4}));
+        // include:update/end
+    }
+
+    {
+        // include:take/start
+        auto v1 = immer::array<int>{1, 2, 3, 4, 5, 6};
+        auto v2 = v1.take(3);
+
+        assert((v1 == immer::array<int>{1, 2, 3, 4, 5, 6}));
+        assert((v2 == immer::array<int>{1, 2, 3}));
+        // include:take/end
+    }
+}
diff --git a/third_party/immer/example/box/box.cpp b/third_party/immer/example/box/box.cpp
new file mode 100644
index 000000000000..8f045e8876ec
--- /dev/null
+++ b/third_party/immer/example/box/box.cpp
@@ -0,0 +1,25 @@
+//
+// immer: immutable data structures for C++
+// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
+//
+// This software is distributed under the Boost Software License, Version 1.0.
+// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
+//
+
+#include <immer/box.hpp>
+
+#include <cassert>
+#include <string>
+
+int main()
+{
+    {
+        // include:update/start
+        auto v1 = immer::box<std::string>{"hello"};
+        auto v2 = v1.update([&](auto l) { return l + ", world!"; });
+
+        assert((v1 == immer::box<std::string>{"hello"}));
+        assert((v2 == immer::box<std::string>{"hello, world!"}));
+        // include:update/end
+    }
+}
diff --git a/third_party/immer/example/flex-vector/flex-vector.cpp b/third_party/immer/example/flex-vector/flex-vector.cpp
new file mode 100644
index 000000000000..7c8a7793393c
--- /dev/null
+++ b/third_party/immer/example/flex-vector/flex-vector.cpp
@@ -0,0 +1,103 @@
+//
+// immer: immutable data structures for C++
+// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
+//
+// This software is distributed under the Boost Software License, Version 1.0.
+// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
+//
+
+#include <immer/flex_vector.hpp>
+
+#include <cassert>
+
+int main()
+{
+    {
+        // include:push-back/start
+        auto v1 = immer::flex_vector<int>{1};
+        auto v2 = v1.push_back(8);
+
+        assert((v1 == immer::flex_vector<int>{1}));
+        assert((v2 == immer::flex_vector<int>{1, 8}));
+        // include:push-back/end
+    }
+    {
+        // include:push-front/start
+        auto v1 = immer::flex_vector<int>{1};
+        auto v2 = v1.push_front(8);
+
+        assert((v1 == immer::flex_vector<int>{1}));
+        assert((v2 == immer::flex_vector<int>{8, 1}));
+        // include:push-front/end
+    }
+
+    {
+        // include:set/start
+        auto v1 = immer::flex_vector<int>{1, 2, 3};
+        auto v2 = v1.set(0, 5);
+
+        assert((v1 == immer::flex_vector<int>{1, 2, 3}));
+        assert((v2 == immer::flex_vector<int>{5, 2, 3}));
+        // include:set/end
+    }
+
+    {
+        // include:update/start
+        auto v1 = immer::flex_vector<int>{1, 2, 3, 4};
+        auto v2 = v1.update(2, [&](auto l) { return ++l; });
+
+        assert((v1 == immer::flex_vector<int>{1, 2, 3, 4}));
+        assert((v2 == immer::flex_vector<int>{1, 2, 4, 4}));
+        // include:update/end
+    }
+
+    {
+        // include:take/start
+        auto v1 = immer::flex_vector<int>{1, 2, 3, 4, 5, 6};
+        auto v2 = v1.take(3);
+
+        assert((v1 == immer::flex_vector<int>{1, 2, 3, 4, 5, 6}));
+        assert((v2 == immer::flex_vector<int>{1, 2, 3}));
+        // include:take/end
+    }
+
+    {
+        // include:drop/start
+        auto v1 = immer::flex_vector<int>{1, 2, 3, 4, 5, 6};
+        auto v2 = v1.drop(3);
+
+        assert((v1 == immer::flex_vector<int>{1, 2, 3, 4, 5, 6}));
+        assert((v2 == immer::flex_vector<int>{4, 5, 6}));
+        // include:drop/end
+    }
+
+    {
+        // include:insert/start
+        auto v1 = immer::flex_vector<int>{1, 2, 3};
+        auto v2 = v1.insert(0, 0);
+
+        assert((v1 == immer::flex_vector<int>{1, 2, 3}));
+        assert((v2 == immer::flex_vector<int>{0, 1, 2, 3}));
+        // include:insert/end
+    }
+
+    {
+        // include:erase/start
+        auto v1 = immer::flex_vector<int>{1, 2, 3, 4, 5};
+        auto v2 = v1.erase(2);
+
+        assert((v1 == immer::flex_vector<int>{1, 2, 3, 4, 5}));
+        assert((v2 == immer::flex_vector<int>{1, 2, 4, 5}));
+        // include:erase/end
+    }
+
+    {
+        // include:concat/start
+        auto v1 = immer::flex_vector<int>{1, 2, 3};
+        auto v2 = v1 + v1;
+
+        assert((v1 == immer::flex_vector<int>{1, 2, 3}));
+        assert((v2 == immer::flex_vector<int>{1, 2, 3, 1, 2, 3}));
+        // include:concat/end
+    }
+}
diff --git a/third_party/immer/example/map/intro.cpp b/third_party/immer/example/map/intro.cpp
new file mode 100644
index 000000000000..94222f99b31b
--- /dev/null
+++ b/third_party/immer/example/map/intro.cpp
@@ -0,0 +1,23 @@
+//
+// immer: immutable data structures for C++
+// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
+//
+// This software is distributed under the Boost Software License, Version 1.0.
+// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
+//
+
+#include <string>
+// include:intro/start
+#include <immer/map.hpp>
+int main()
+{
+    const auto v0 = immer::map<std::string, int>{};
+    const auto v1 = v0.set("hello", 42);
+    assert(v0["hello"] == 0);
+    assert(v1["hello"] == 42);
+
+    const auto v2 = v1.erase("hello");
+    assert(*v1.find("hello") == 42);
+    assert(!v2.find("hello"));
+}
+// include:intro/end
diff --git a/third_party/immer/example/set/intro.cpp b/third_party/immer/example/set/intro.cpp
new file mode 100644
index 000000000000..be932ce65475
--- /dev/null
+++ b/third_party/immer/example/set/intro.cpp
@@ -0,0 +1,22 @@
+//
+// immer: immutable data structures for C++
+// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
+//
+// This software is distributed under the Boost Software License, Version 1.0.
+// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
+//
+
+// include:intro/start
+#include <immer/set.hpp>
+int main()
+{
+    const auto v0 = immer::set<int>{};
+    const auto v1 = v0.insert(42);
+    assert(v0.count(42) == 0);
+    assert(v1.count(42) == 1);
+
+    const auto v2 = v1.erase(42);
+    assert(v1.count(42) == 1);
+    assert(v2.count(42) == 0);
+}
+// include:intro/end
diff --git a/third_party/immer/example/vector/fizzbuzz.cpp b/third_party/immer/example/vector/fizzbuzz.cpp
new file mode 100644
index 000000000000..c7765a6200a0
--- /dev/null
+++ b/third_party/immer/example/vector/fizzbuzz.cpp
@@ -0,0 +1,34 @@
+//
+// immer: immutable data structures for C++
+// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
+//
+// This software is distributed under the Boost Software License, Version 1.0.
+// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
+//
+
+#include <immer/vector.hpp>
+
+#include <iostream>
+#include <string>
+
+// include:fizzbuzz/start
+immer::vector<std::string>
+fizzbuzz(immer::vector<std::string> v, int first, int last)
+{
+    for (auto i = first; i < last; ++i)
+        v = std::move(v).push_back(
+            i % 15 == 0 ? "FizzBuzz"
+                        : i % 5 == 0 ? "Bizz"
+                                     : i % 3 == 0 ? "Fizz" :
+                                                  /* else */ std::to_string(i));
+    return v;
+}
+// include:fizzbuzz/end
+
+int main()
+{
+    auto v = fizzbuzz({}, 0, 100);
+    std::copy(v.begin(),
+              v.end(),
+              std::ostream_iterator<std::string>{std::cout, "\n"});
+}
diff --git a/third_party/immer/example/vector/gc.cpp b/third_party/immer/example/vector/gc.cpp
new file mode 100644
index 000000000000..2bc4d5116f42
--- /dev/null
+++ b/third_party/immer/example/vector/gc.cpp
@@ -0,0 +1,37 @@
+//
+// immer: immutable data structures for C++
+// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
+//
+// This software is distributed under the Boost Software License, Version 1.0.
+// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
+//
+
+// include:example/start
+#include <immer/heap/gc_heap.hpp>
+#include <immer/heap/heap_policy.hpp>
+#include <immer/memory_policy.hpp>
+#include <immer/refcount/no_refcount_policy.hpp>
+#include <immer/vector.hpp>
+
+#include <iostream>
+
+// declare a memory policy for using a tracing garbage collector
+using gc_policy = immer::memory_policy<immer::heap_policy<immer::gc_heap>,
+                                       immer::no_refcount_policy,
+                                       immer::gc_transience_policy,
+                                       false>;
+
+// alias the vector type so we are not concerned about memory policies
+// in the places where we actually use it
+template <typename T>
+using my_vector = immer::vector<T, gc_policy>;
+
+int main()
+{
+    auto v =
+        my_vector<const char*>().push_back("hello, ").push_back("world!\n");
+
+    for (auto s : v)
+        std::cout << s;
+}
+// include:example/end
diff --git a/third_party/immer/example/vector/intro.cpp b/third_party/immer/example/vector/intro.cpp
new file mode 100644
index 000000000000..ca832e606552
--- /dev/null
+++ b/third_party/immer/example/vector/intro.cpp
@@ -0,0 +1,22 @@
+//
+// immer: immutable data structures for C++
+// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
+//
+// This software is distributed under the Boost Software License, Version 1.0.
+// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
+//
+
+// include:intro/start
+#include <immer/vector.hpp>
+int main()
+{
+    const auto v0 = immer::vector<int>{};
+    const auto v1 = v0.push_back(13);
+    assert((v0 == immer::vector<int>{}));
+    assert((v1 == immer::vector<int>{13}));
+
+    const auto v2 = v1.set(0, 42);
+    assert(v1[0] == 13);
+    assert(v2[0] == 42);
+}
+// include:intro/end
diff --git a/third_party/immer/example/vector/iota-move.cpp b/third_party/immer/example/vector/iota-move.cpp
new file mode 100644
index 000000000000..3d03ba5307f5
--- /dev/null
+++ b/third_party/immer/example/vector/iota-move.cpp
@@ -0,0 +1,25 @@
+//
+// immer: immutable data structures for C++
+// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
+//
+// This software is distributed under the Boost Software License, Version 1.0.
+// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
+//
+
+#include <immer/vector.hpp>
+#include <iostream>
+
+// include:myiota/start
+immer::vector<int> myiota(immer::vector<int> v, int first, int last)
+{
+    for (auto i = first; i < last; ++i)
+        v = std::move(v).push_back(i);
+    return v;
+}
+// include:myiota/end
+
+int main()
+{
+    auto v = myiota({}, 0, 100);
+    std::copy(v.begin(), v.end(), std::ostream_iterator<int>{std::cout, "\n"});
+}
diff --git a/third_party/immer/example/vector/iota-slow.cpp b/third_party/immer/example/vector/iota-slow.cpp
new file mode 100644
index 000000000000..a311b7a7ff08
--- /dev/null
+++ b/third_party/immer/example/vector/iota-slow.cpp
@@ -0,0 +1,25 @@
+//
+// immer: immutable data structures for C++
+// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
+//
+// This software is distributed under the Boost Software License, Version 1.0.
+// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
+//
+
+#include <immer/vector.hpp>
+#include <iostream>
+
+// include:myiota/start
+immer::vector<int> myiota(immer::vector<int> v, int first, int last)
+{
+    for (auto i = first; i < last; ++i)
+        v = v.push_back(i);
+    return v;
+}
+// include:myiota/end
+
+int main()
+{
+    auto v = myiota({}, 0, 100);
+    std::copy(v.begin(), v.end(), std::ostream_iterator<int>{std::cout, "\n"});
+}
diff --git a/third_party/immer/example/vector/iota-transient-std.cpp b/third_party/immer/example/vector/iota-transient-std.cpp
new file mode 100644
index 000000000000..451f44a10306
--- /dev/null
+++ b/third_party/immer/example/vector/iota-transient-std.cpp
@@ -0,0 +1,29 @@
+//
+// immer: immutable data structures for C++
+// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
+//
+// This software is distributed under the Boost Software License, Version 1.0.
+// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
+//
+
+#include <immer/vector.hpp>
+#include <immer/vector_transient.hpp>
+
+#include <algorithm>
+#include <iostream>
+
+// include:myiota/start
+immer::vector<int> myiota(immer::vector<int> v, int first, int last)
+{
+    auto t = v.transient();
+    std::generate_n(
+        std::back_inserter(t), last - first, [&] { return first++; });
+    return t.persistent();
+}
+// include:myiota/end
+
+int main()
+{
+    auto v = myiota({}, 0, 100);
+    std::copy(v.begin(), v.end(), std::ostream_iterator<int>{std::cout, "\n"});
+}
diff --git a/third_party/immer/example/vector/iota-transient.cpp b/third_party/immer/example/vector/iota-transient.cpp
new file mode 100644
index 000000000000..d49b14e5798d
--- /dev/null
+++ b/third_party/immer/example/vector/iota-transient.cpp
@@ -0,0 +1,27 @@
+//
+// immer: immutable data structures for C++
+// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
+//
+// This software is distributed under the Boost Software License, Version 1.0.
+// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
+//
+
+#include <immer/vector.hpp>
+#include <immer/vector_transient.hpp>
+#include <iostream>
+
+// include:myiota/start
+immer::vector<int> myiota(immer::vector<int> v, int first, int last)
+{
+    auto t = v.transient();
+    for (auto i = first; i < last; ++i)
+        t.push_back(i);
+    return t.persistent();
+}
+// include:myiota/end
+
+int main()
+{
+    auto v = myiota({}, 0, 100);
+    std::copy(v.begin(), v.end(), std::ostream_iterator<int>{std::cout, "\n"});
+}
diff --git a/third_party/immer/example/vector/move.cpp b/third_party/immer/example/vector/move.cpp
new file mode 100644
index 000000000000..7eb815b62a6e
--- /dev/null
+++ b/third_party/immer/example/vector/move.cpp
@@ -0,0 +1,35 @@
+//
+// immer: immutable data structures for C++
+// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
+//
+// This software is distributed under the Boost Software License, Version 1.0.
+// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
+//
+
+#include <cassert>
+#include <immer/vector.hpp>
+
+// include:move-bad/start
+immer::vector<int> do_stuff(const immer::vector<int> v)
+{
+    return std::move(v).push_back(42);
+}
+// include:move-bad/end
+
+// include:move-good/start
+immer::vector<int> do_stuff_better(immer::vector<int> v)
+{
+    return std::move(v).push_back(42);
+}
+// include:move-good/end
+
+int main()
+{
+    auto v  = immer::vector<int>{};
+    auto v1 = do_stuff(v);
+    auto v2 = do_stuff_better(v);
+    assert(v1.size() == 1);
+    assert(v2.size() == 1);
+    assert(v1[0] == 42);
+    assert(v2[0] == 42);
+}
diff --git a/third_party/immer/example/vector/vector.cpp b/third_party/immer/example/vector/vector.cpp
new file mode 100644
index 000000000000..c59c2d1d170b
--- /dev/null
+++ b/third_party/immer/example/vector/vector.cpp
@@ -0,0 +1,53 @@
+//
+// immer: immutable data structures for C++
+// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
+//
+// This software is distributed under the Boost Software License, Version 1.0.
+// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
+//
+
+#include <cassert>
+#include <immer/vector.hpp>
+
+int main()
+{
+    {
+        // include:push-back/start
+        auto v1 = immer::vector<int>{1};
+        auto v2 = v1.push_back(8);
+
+        assert((v1 == immer::vector<int>{1}));
+        assert((v2 == immer::vector<int>{1, 8}));
+        // include:push-back/end
+    }
+
+    {
+        // include:set/start
+        auto v1 = immer::vector<int>{1, 2, 3};
+        auto v2 = v1.set(0, 5);
+
+        assert((v1 == immer::vector<int>{1, 2, 3}));
+        assert((v2 == immer::vector<int>{5, 2, 3}));
+        // include:set/end
+    }
+
+    {
+        // include:update/start
+        auto v1 = immer::vector<int>{1, 2, 3, 4};
+        auto v2 = v1.update(2, [&](auto l) { return ++l; });
+
+        assert((v1 == immer::vector<int>{1, 2, 3, 4}));
+        assert((v2 == immer::vector<int>{1, 2, 4, 4}));
+        // include:update/end
+    }
+
+    {
+        // include:take/start
+        auto v1 = immer::vector<int>{1, 2, 3, 4, 5, 6};
+        auto v2 = v1.take(3);
+
+        assert((v1 == immer::vector<int>{1, 2, 3, 4, 5, 6}));
+        assert((v2 == immer::vector<int>{1, 2, 3}));
+        // include:take/end
+    }
+}