Squashed 'third_party/immer/' content from commit ad3e3556d

git-subtree-dir: third_party/immer
git-subtree-split: ad3e3556d38bb75966dd24c61a774970a7c7957e

1 files changed, 2461 insertions, 0 deletions

diff --git a/immer/detail/rbts/operations.hpp b/immer/detail/rbts/operations.hpp
new file mode 100644
index 000000000000..ff703e892b42
--- /dev/null
+++ b/immer/detail/rbts/operations.hpp
@@ -0,0 +1,2461 @@
+//
+// immer: immutable data structures for C++
+// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
+//
+// This software is distributed under the Boost Software License, Version 1.0.
+// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
+//
+
+#pragma once
+
+#include <algorithm>
+#include <memory>
+#include <numeric>
+#include <utility>
+
+#include <immer/config.hpp>
+#include <immer/detail/rbts/position.hpp>
+#include <immer/detail/rbts/visitor.hpp>
+#include <immer/detail/util.hpp>
+#include <immer/heap/tags.hpp>
+
+namespace immer {
+namespace detail {
+namespace rbts {
+
+template <typename T>
+struct array_for_visitor : visitor_base<array_for_visitor<T>>
+{
+    using this_t = array_for_visitor;
+
+    template <typename PosT>
+    static T* visit_inner(PosT&& pos, size_t idx)
+    {
+        return pos.descend(this_t{}, idx);
+    }
+
+    template <typename PosT>
+    static T* visit_leaf(PosT&& pos, size_t)
+    {
+        return pos.node()->leaf();
+    }
+};
+
+template <typename T>
+struct region_for_visitor : visitor_base<region_for_visitor<T>>
+{
+    using this_t   = region_for_visitor;
+    using result_t = std::tuple<T*, size_t, size_t>;
+
+    template <typename PosT>
+    static result_t visit_inner(PosT&& pos, size_t idx)
+    {
+        return pos.towards(this_t{}, idx);
+    }
+
+    template <typename PosT>
+    static result_t visit_leaf(PosT&& pos, size_t idx)
+    {
+        return std::make_tuple(pos.node()->leaf(), pos.index(idx), pos.count());
+    }
+};
+
+template <typename T>
+struct get_visitor : visitor_base<get_visitor<T>>
+{
+    using this_t = get_visitor;
+
+    template <typename PosT>
+    static const T& visit_inner(PosT&& pos, size_t idx)
+    {
+        return pos.descend(this_t{}, idx);
+    }
+
+    template <typename PosT>
+    static const T& visit_leaf(PosT&& pos, size_t idx)
+    {
+        return pos.node()->leaf()[pos.index(idx)];
+    }
+};
+
+struct for_each_chunk_visitor : visitor_base<for_each_chunk_visitor>
+{
+    using this_t = for_each_chunk_visitor;
+
+    template <typename Pos, typename Fn>
+    static void visit_inner(Pos&& pos, Fn&& fn)
+    {
+        pos.each(this_t{}, fn);
+    }
+
+    template <typename Pos, typename Fn>
+    static void visit_leaf(Pos&& pos, Fn&& fn)
+    {
+        auto data = pos.node()->leaf();
+        fn(data, data + pos.count());
+    }
+};
+
+struct for_each_chunk_p_visitor : visitor_base<for_each_chunk_p_visitor>
+{
+    using this_t = for_each_chunk_p_visitor;
+
+    template <typename Pos, typename Fn>
+    static bool visit_inner(Pos&& pos, Fn&& fn)
+    {
+        return pos.each_pred(this_t{}, fn);
+    }
+
+    template <typename Pos, typename Fn>
+    static bool visit_leaf(Pos&& pos, Fn&& fn)
+    {
+        auto data = pos.node()->leaf();
+        return fn(data, data + pos.count());
+    }
+};
+
+struct for_each_chunk_left_visitor : visitor_base<for_each_chunk_left_visitor>
+{
+    using this_t = for_each_chunk_left_visitor;
+
+    template <typename Pos, typename Fn>
+    static void visit_inner(Pos&& pos, size_t last, Fn&& fn)
+    {
+        auto l = pos.index(last);
+        pos.each_left(for_each_chunk_visitor{}, l, fn);
+        pos.towards_oh(this_t{}, last, l, fn);
+    }
+
+    template <typename Pos, typename Fn>
+    static void visit_leaf(Pos&& pos, size_t last, Fn&& fn)
+    {
+        auto data = pos.node()->leaf();
+        auto l    = pos.index(last);
+        fn(data, data + l + 1);
+    }
+};
+
+struct for_each_chunk_right_visitor : visitor_base<for_each_chunk_right_visitor>
+{
+    using this_t = for_each_chunk_right_visitor;
+
+    template <typename Pos, typename Fn>
+    static void visit_inner(Pos&& pos, size_t first, Fn&& fn)
+    {
+        auto f = pos.index(first);
+        pos.towards_oh(this_t{}, first, f, fn);
+        pos.each_right(for_each_chunk_visitor{}, f + 1, fn);
+    }
+
+    template <typename Pos, typename Fn>
+    static void visit_leaf(Pos&& pos, size_t first, Fn&& fn)
+    {
+        auto data = pos.node()->leaf();
+        auto f    = pos.index(first);
+        fn(data + f, data + pos.count());
+    }
+};
+
+struct for_each_chunk_i_visitor : visitor_base<for_each_chunk_i_visitor>
+{
+    using this_t = for_each_chunk_i_visitor;
+
+    template <typename Pos, typename Fn>
+    static void visit_relaxed(Pos&& pos, size_t first, size_t last, Fn&& fn)
+    {
+        // we are going towards *two* indices, so we need to do the
+        // relaxed as a special case to correct the second index
+        if (first < last) {
+            auto f = pos.index(first);
+            auto l = pos.index(last - 1);
+            if (f == l) {
+                auto sbh = pos.size_before(f);
+                pos.towards_oh_sbh(this_t{}, first, f, sbh, last - sbh, fn);
+            } else {
+                assert(f < l);
+                pos.towards_oh(for_each_chunk_right_visitor{}, first, f, fn);
+                pos.each_i(for_each_chunk_visitor{}, f + 1, l, fn);
+                pos.towards_oh(for_each_chunk_left_visitor{}, last - 1, l, fn);
+            }
+        }
+    }
+
+    template <typename Pos, typename Fn>
+    static void visit_regular(Pos&& pos, size_t first, size_t last, Fn&& fn)
+    {
+        if (first < last) {
+            auto f = pos.index(first);
+            auto l = pos.index(last - 1);
+            if (f == l)
+                pos.towards_oh(this_t{}, first, f, last, fn);
+            else {
+                assert(f < l);
+                pos.towards_oh(for_each_chunk_right_visitor{}, first, f, fn);
+                pos.each_i(for_each_chunk_visitor{}, f + 1, l, fn);
+                pos.towards_oh(for_each_chunk_left_visitor{}, last - 1, l, fn);
+            }
+        }
+    }
+
+    template <typename Pos, typename Fn>
+    static void visit_leaf(Pos&& pos, size_t first, size_t last, Fn&& fn)
+    {
+        auto data = pos.node()->leaf();
+        if (first < last) {
+            auto f = pos.index(first);
+            auto l = pos.index(last - 1);
+            fn(data + f, data + l + 1);
+        }
+    }
+};
+
+struct for_each_chunk_p_left_visitor
+    : visitor_base<for_each_chunk_p_left_visitor>
+{
+    using this_t = for_each_chunk_p_left_visitor;
+
+    template <typename Pos, typename Fn>
+    static bool visit_inner(Pos&& pos, size_t last, Fn&& fn)
+    {
+        auto l = pos.index(last);
+        return pos.each_pred_left(for_each_chunk_p_visitor{}, l, fn) &&
+               pos.towards_oh(this_t{}, last, l, fn);
+    }
+
+    template <typename Pos, typename Fn>
+    static bool visit_leaf(Pos&& pos, size_t last, Fn&& fn)
+    {
+        auto data = pos.node()->leaf();
+        auto l    = pos.index(last);
+        return fn(data, data + l + 1);
+    }
+};
+
+struct for_each_chunk_p_right_visitor
+    : visitor_base<for_each_chunk_p_right_visitor>
+{
+    using this_t = for_each_chunk_p_right_visitor;
+
+    template <typename Pos, typename Fn>
+    static bool visit_inner(Pos&& pos, size_t first, Fn&& fn)
+    {
+        auto f = pos.index(first);
+        return pos.towards_oh(this_t{}, first, f, fn) &&
+               pos.each_pred_right(for_each_chunk_p_visitor{}, f + 1, fn);
+    }
+
+    template <typename Pos, typename Fn>
+    static bool visit_leaf(Pos&& pos, size_t first, Fn&& fn)
+    {
+        auto data = pos.node()->leaf();
+        auto f    = pos.index(first);
+        return fn(data + f, data + pos.count());
+    }
+};
+
+struct for_each_chunk_p_i_visitor : visitor_base<for_each_chunk_p_i_visitor>
+{
+    using this_t = for_each_chunk_p_i_visitor;
+
+    template <typename Pos, typename Fn>
+    static bool visit_relaxed(Pos&& pos, size_t first, size_t last, Fn&& fn)
+    {
+        // we are going towards *two* indices, so we need to do the
+        // relaxed as a special case to correct the second index
+        if (first < last) {
+            auto f = pos.index(first);
+            auto l = pos.index(last - 1);
+            if (f == l) {
+                auto sbh = pos.size_before(f);
+                return pos.towards_oh_sbh(
+                    this_t{}, first, f, sbh, last - sbh, fn);
+            } else {
+                assert(f < l);
+                return pos.towards_oh(
+                           for_each_chunk_p_right_visitor{}, first, f, fn) &&
+                       pos.each_pred_i(
+                           for_each_chunk_p_visitor{}, f + 1, l, fn) &&
+                       pos.towards_oh(
+                           for_each_chunk_p_left_visitor{}, last - 1, l, fn);
+            }
+        }
+        return true;
+    }
+
+    template <typename Pos, typename Fn>
+    static bool visit_regular(Pos&& pos, size_t first, size_t last, Fn&& fn)
+    {
+        if (first < last) {
+            auto f = pos.index(first);
+            auto l = pos.index(last - 1);
+            if (f == l)
+                return pos.towards_oh(this_t{}, first, f, last, fn);
+            else {
+                assert(f < l);
+                return pos.towards_oh(
+                           for_each_chunk_p_right_visitor{}, first, f, fn) &&
+                       pos.each_pred_i(
+                           for_each_chunk_p_visitor{}, f + 1, l, fn) &&
+                       pos.towards_oh(
+                           for_each_chunk_p_left_visitor{}, last - 1, l, fn);
+            }
+        }
+        return true;
+    }
+
+    template <typename Pos, typename Fn>
+    static bool visit_leaf(Pos&& pos, size_t first, size_t last, Fn&& fn)
+    {
+        auto data = pos.node()->leaf();
+        if (first < last) {
+            auto f = pos.index(first);
+            auto l = pos.index(last - 1);
+            return fn(data + f, data + l + 1);
+        }
+        return true;
+    }
+};
+
+struct equals_visitor : visitor_base<equals_visitor>
+{
+    using this_t = equals_visitor;
+
+    struct this_aux_t : visitor_base<this_aux_t>
+    {
+        template <typename PosR, typename PosL, typename Iter>
+        static bool visit_inner(
+            PosR&& posr, count_t i, PosL&& posl, Iter&& first, size_t idx)
+        {
+            return posl.nth_sub(i, this_t{}, posr, first, idx);
+        }
+
+        template <typename PosR, typename PosL, typename Iter>
+        static bool visit_leaf(
+            PosR&& posr, count_t i, PosL&& posl, Iter&& first, size_t idx)
+        {
+            return posl.nth_sub_leaf(i, this_t{}, posr, first, idx);
+        }
+    };
+
+    struct rrb : visitor_base<rrb>
+    {
+        template <typename PosR, typename Iter, typename Node>
+        static bool visit_node(PosR&& posr,
+                               Iter&& first,
+                               Node* rootl,
+                               shift_t shiftl,
+                               size_t sizel)
+        {
+            assert(shiftl <= posr.shift());
+            return shiftl == posr.shift()
+                       ? visit_maybe_relaxed_sub(rootl,
+                                                 shiftl,
+                                                 sizel,
+                                                 this_t{},
+                                                 posr,
+                                                 first,
+                                                 size_t{})
+                       : posr.first_sub_inner(
+                             rrb{}, first, rootl, shiftl, sizel);
+        }
+    };
+
+    template <typename Iter>
+    static auto equal_chunk_p(Iter&& iter)
+    {
+        return [iter](auto f, auto e) mutable {
+            if (f == &*iter) {
+                iter += e - f;
+                return true;
+            }
+            for (; f != e; ++f, ++iter)
+                if (*f != *iter)
+                    return false;
+            return true;
+        };
+    }
+
+    template <typename PosL, typename PosR, typename Iter>
+    static bool
+    visit_relaxed(PosL&& posl, PosR&& posr, Iter&& first, size_t idx)
+    {
+        auto nl = posl.node();
+        auto nr = posr.node();
+        if (nl == nr)
+            return true;
+        auto cl = posl.count();
+        auto cr = posr.count();
+        assert(cr > 0);
+        auto sbr = size_t{};
+        auto i   = count_t{};
+        auto j   = count_t{};
+        for (; i < cl; ++i) {
+            auto sbl = posl.size_before(i);
+            for (; j + 1 < cr && (sbr = posr.size_before(j)) < sbl; ++j)
+                ;
+            auto res =
+                sbl == sbr
+                    ? posr.nth_sub(j, this_aux_t{}, i, posl, first, idx + sbl)
+                    : posl.nth_sub(i,
+                                   for_each_chunk_p_visitor{},
+                                   this_t::equal_chunk_p(first + (idx + sbl)));
+            if (!res)
+                return false;
+        }
+        return true;
+    }
+
+    template <typename PosL, typename PosR, typename Iter>
+    static std::enable_if_t<is_relaxed_v<PosR>, bool>
+    visit_regular(PosL&& posl, PosR&& posr, Iter&& first, size_t idx)
+    {
+        return this_t::visit_relaxed(posl, posr, first, idx);
+    }
+
+    template <typename PosL, typename PosR, typename Iter>
+    static std::enable_if_t<!is_relaxed_v<PosR>, bool>
+    visit_regular(PosL&& posl, PosR&& posr, Iter&& first, size_t idx)
+    {
+        return posl.count() >= posr.count()
+                   ? this_t::visit_regular(posl, posr.node())
+                   : this_t::visit_regular(posr, posl.node());
+    }
+
+    template <typename PosL, typename PosR, typename Iter>
+    static bool visit_leaf(PosL&& posl, PosR&& posr, Iter&& first, size_t idx)
+    {
+        if (posl.node() == posr.node())
+            return true;
+        auto cl = posl.count();
+        auto cr = posr.count();
+        auto mp = std::min(cl, cr);
+        return std::equal(posl.node()->leaf(),
+                          posl.node()->leaf() + mp,
+                          posr.node()->leaf()) &&
+               std::equal(posl.node()->leaf() + mp,
+                          posl.node()->leaf() + posl.count(),
+                          first + (idx + mp));
+    }
+
+    template <typename Pos, typename NodeT>
+    static bool visit_regular(Pos&& pos, NodeT* other)
+    {
+        auto node = pos.node();
+        return node == other || pos.each_pred_zip(this_t{}, other);
+    }
+
+    template <typename Pos, typename NodeT>
+    static bool visit_leaf(Pos&& pos, NodeT* other)
+    {
+        auto node = pos.node();
+        return node == other || std::equal(node->leaf(),
+                                           node->leaf() + pos.count(),
+                                           other->leaf());
+    }
+};
+
+template <typename NodeT>
+struct update_visitor : visitor_base<update_visitor<NodeT>>
+{
+    using node_t = NodeT;
+    using this_t = update_visitor;
+
+    template <typename Pos, typename Fn>
+    static node_t* visit_relaxed(Pos&& pos, size_t idx, Fn&& fn)
+    {
+        auto offset = pos.index(idx);
+        auto count  = pos.count();
+        auto node   = node_t::make_inner_sr_n(count, pos.relaxed());
+        try {
+            auto child = pos.towards_oh(this_t{}, idx, offset, fn);
+            node_t::do_copy_inner_sr(node, pos.node(), count);
+            node->inner()[offset]->dec_unsafe();
+            node->inner()[offset] = child;
+            return node;
+        } catch (...) {
+            node_t::delete_inner_r(node, count);
+            throw;
+        }
+    }
+
+    template <typename Pos, typename Fn>
+    static node_t* visit_regular(Pos&& pos, size_t idx, Fn&& fn)
+    {
+        auto offset = pos.index(idx);
+        auto count  = pos.count();
+        auto node   = node_t::make_inner_n(count);
+        try {
+            auto child = pos.towards_oh_ch(this_t{}, idx, offset, count, fn);
+            node_t::do_copy_inner(node, pos.node(), count);
+            node->inner()[offset]->dec_unsafe();
+            node->inner()[offset] = child;
+            return node;
+        } catch (...) {
+            node_t::delete_inner(node, count);
+            throw;
+        }
+    }
+
+    template <typename Pos, typename Fn>
+    static node_t* visit_leaf(Pos&& pos, size_t idx, Fn&& fn)
+    {
+        auto offset = pos.index(idx);
+        auto node   = node_t::copy_leaf(pos.node(), pos.count());
+        try {
+            node->leaf()[offset] =
+                std::forward<Fn>(fn)(std::move(node->leaf()[offset]));
+            return node;
+        } catch (...) {
+            node_t::delete_leaf(node, pos.count());
+            throw;
+        }
+    }
+};
+
+struct dec_visitor : visitor_base<dec_visitor>
+{
+    using this_t = dec_visitor;
+
+    template <typename Pos>
+    static void visit_relaxed(Pos&& p)
+    {
+        using node_t = node_type<Pos>;
+        auto node    = p.node();
+        if (node->dec()) {
+            p.each(this_t{});
+            node_t::delete_inner_r(node, p.count());
+        }
+    }
+
+    template <typename Pos>
+    static void visit_regular(Pos&& p)
+    {
+        using node_t = node_type<Pos>;
+        auto node    = p.node();
+        if (node->dec()) {
+            p.each(this_t{});
+            node_t::delete_inner(node, p.count());
+        }
+    }
+
+    template <typename Pos>
+    static void visit_leaf(Pos&& p)
+    {
+        using node_t = node_type<Pos>;
+        auto node    = p.node();
+        if (node->dec()) {
+            node_t::delete_leaf(node, p.count());
+        }
+    }
+};
+
+template <typename NodeT>
+void dec_leaf(NodeT* node, count_t n)
+{
+    make_leaf_sub_pos(node, n).visit(dec_visitor{});
+}
+
+template <typename NodeT>
+void dec_inner(NodeT* node, shift_t shift, size_t size)
+{
+    visit_maybe_relaxed_sub(node, shift, size, dec_visitor());
+}
+
+template <typename NodeT>
+void dec_relaxed(NodeT* node, shift_t shift)
+{
+    make_relaxed_pos(node, shift, node->relaxed()).visit(dec_visitor());
+}
+
+template <typename NodeT>
+void dec_regular(NodeT* node, shift_t shift, size_t size)
+{
+    make_regular_pos(node, shift, size).visit(dec_visitor());
+}
+
+template <typename NodeT>
+void dec_empty_regular(NodeT* node)
+{
+    make_empty_regular_pos(node).visit(dec_visitor());
+}
+
+template <typename NodeT>
+struct get_mut_visitor : visitor_base<get_mut_visitor<NodeT>>
+{
+    using node_t  = NodeT;
+    using this_t  = get_mut_visitor;
+    using value_t = typename NodeT::value_t;
+    using edit_t  = typename NodeT::edit_t;
+
+    template <typename Pos>
+    static value_t&
+    visit_relaxed(Pos&& pos, size_t idx, edit_t e, node_t** location)
+    {
+        auto offset = pos.index(idx);
+        auto count  = pos.count();
+        auto node   = pos.node();
+        if (node->can_mutate(e)) {
+            return pos.towards_oh(
+                this_t{}, idx, offset, e, &node->inner()[offset]);
+        } else {
+            auto new_node = node_t::copy_inner_sr_e(e, node, count);
+            try {
+                auto& res = pos.towards_oh(
+                    this_t{}, idx, offset, e, &new_node->inner()[offset]);
+                pos.visit(dec_visitor{});
+                *location = new_node;
+                return res;
+            } catch (...) {
+                dec_relaxed(new_node, pos.shift());
+                throw;
+            }
+        }
+    }
+
+    template <typename Pos>
+    static value_t&
+    visit_regular(Pos&& pos, size_t idx, edit_t e, node_t** location)
+    {
+        assert(pos.node() == *location);
+        auto offset = pos.index(idx);
+        auto count  = pos.count();
+        auto node   = pos.node();
+        if (node->can_mutate(e)) {
+            return pos.towards_oh_ch(
+                this_t{}, idx, offset, count, e, &node->inner()[offset]);
+        } else {
+            auto new_node = node_t::copy_inner_e(e, node, count);
+            try {
+                auto& res = pos.towards_oh_ch(this_t{},
+                                              idx,
+                                              offset,
+                                              count,
+                                              e,
+                                              &new_node->inner()[offset]);
+                pos.visit(dec_visitor{});
+                *location = new_node;
+                return res;
+            } catch (...) {
+                dec_regular(new_node, pos.shift(), pos.size());
+                throw;
+            }
+        }
+    }
+
+    template <typename Pos>
+    static value_t&
+    visit_leaf(Pos&& pos, size_t idx, edit_t e, node_t** location)
+    {
+        assert(pos.node() == *location);
+        auto node = pos.node();
+        if (node->can_mutate(e)) {
+            return node->leaf()[pos.index(idx)];
+        } else {
+            auto new_node = node_t::copy_leaf_e(e, pos.node(), pos.count());
+            pos.visit(dec_visitor{});
+            *location = new_node;
+            return new_node->leaf()[pos.index(idx)];
+        }
+    }
+};
+
+template <typename NodeT, bool Mutating = true>
+struct push_tail_mut_visitor
+    : visitor_base<push_tail_mut_visitor<NodeT, Mutating>>
+{
+    static constexpr auto B  = NodeT::bits;
+    static constexpr auto BL = NodeT::bits_leaf;
+
+    using this_t        = push_tail_mut_visitor;
+    using this_no_mut_t = push_tail_mut_visitor<NodeT, false>;
+    using node_t        = NodeT;
+    using edit_t        = typename NodeT::edit_t;
+
+    template <typename Pos>
+    static node_t* visit_relaxed(Pos&& pos, edit_t e, node_t* tail, count_t ts)
+    {
+        auto node     = pos.node();
+        auto level    = pos.shift();
+        auto idx      = pos.count() - 1;
+        auto children = pos.size(idx);
+        auto new_idx =
+            children == size_t{1} << level || level == BL ? idx + 1 : idx;
+        auto new_child = static_cast<node_t*>(nullptr);
+        auto mutate    = Mutating && node->can_mutate(e);
+
+        if (new_idx >= branches<B>)
+            return nullptr;
+        else if (idx == new_idx) {
+            new_child =
+                mutate ? pos.last_oh_csh(this_t{}, idx, children, e, tail, ts)
+                       : pos.last_oh_csh(
+                             this_no_mut_t{}, idx, children, e, tail, ts);
+            if (!new_child) {
+                if (++new_idx < branches<B>)
+                    new_child = node_t::make_path_e(e, level - B, tail);
+                else
+                    return nullptr;
+            }
+        } else
+            new_child = node_t::make_path_e(e, level - B, tail);
+
+        if (mutate) {
+            auto count             = new_idx + 1;
+            auto relaxed           = node->ensure_mutable_relaxed_n(e, new_idx);
+            node->inner()[new_idx] = new_child;
+            relaxed->d.sizes[new_idx] = pos.size() + ts;
+            relaxed->d.count          = count;
+            return node;
+        } else {
+            try {
+                auto count    = new_idx + 1;
+                auto new_node = node_t::copy_inner_r_e(e, pos.node(), new_idx);
+                auto relaxed  = new_node->relaxed();
+                new_node->inner()[new_idx] = new_child;
+                relaxed->d.sizes[new_idx]  = pos.size() + ts;
+                relaxed->d.count           = count;
+                if (Mutating)
+                    pos.visit(dec_visitor{});
+                return new_node;
+            } catch (...) {
+                auto shift = pos.shift();
+                auto size  = new_idx == idx ? children + ts : ts;
+                if (shift > BL) {
+                    tail->inc();
+                    dec_inner(new_child, shift - B, size);
+                }
+                throw;
+            }
+        }
+    }
+
+    template <typename Pos, typename... Args>
+    static node_t* visit_regular(Pos&& pos, edit_t e, node_t* tail, Args&&...)
+    {
+        assert((pos.size() & mask<BL>) == 0);
+        auto node    = pos.node();
+        auto idx     = pos.index(pos.size() - 1);
+        auto new_idx = pos.index(pos.size() + branches<BL> - 1);
+        auto mutate  = Mutating && node->can_mutate(e);
+        if (mutate) {
+            node->inner()[new_idx] =
+                idx == new_idx ? pos.last_oh(this_t{}, idx, e, tail)
+                               /* otherwise */
+                               : node_t::make_path_e(e, pos.shift() - B, tail);
+            return node;
+        } else {
+            auto new_parent = node_t::make_inner_e(e);
+            try {
+                new_parent->inner()[new_idx] =
+                    idx == new_idx
+                        ? pos.last_oh(this_no_mut_t{}, idx, e, tail)
+                        /* otherwise */
+                        : node_t::make_path_e(e, pos.shift() - B, tail);
+                node_t::do_copy_inner(new_parent, node, new_idx);
+                if (Mutating)
+                    pos.visit(dec_visitor{});
+                return new_parent;
+            } catch (...) {
+                node_t::delete_inner_e(new_parent);
+                throw;
+            }
+        }
+    }
+
+    template <typename Pos, typename... Args>
+    static node_t* visit_leaf(Pos&& pos, edit_t e, node_t* tail, Args&&...)
+    {
+        IMMER_UNREACHABLE;
+    }
+};
+
+template <typename NodeT>
+struct push_tail_visitor : visitor_base<push_tail_visitor<NodeT>>
+{
+    static constexpr auto B  = NodeT::bits;
+    static constexpr auto BL = NodeT::bits_leaf;
+
+    using this_t = push_tail_visitor;
+    using node_t = NodeT;
+
+    template <typename Pos>
+    static node_t* visit_relaxed(Pos&& pos, node_t* tail, count_t ts)
+    {
+        auto level    = pos.shift();
+        auto idx      = pos.count() - 1;
+        auto children = pos.size(idx);
+        auto new_idx =
+            children == size_t{1} << level || level == BL ? idx + 1 : idx;
+        auto new_child = static_cast<node_t*>(nullptr);
+        if (new_idx >= branches<B>)
+            return nullptr;
+        else if (idx == new_idx) {
+            new_child = pos.last_oh_csh(this_t{}, idx, children, tail, ts);
+            if (!new_child) {
+                if (++new_idx < branches<B>)
+                    new_child = node_t::make_path(level - B, tail);
+                else
+                    return nullptr;
+            }
+        } else
+            new_child = node_t::make_path(level - B, tail);
+        try {
+            auto count = new_idx + 1;
+            auto new_parent =
+                node_t::copy_inner_r_n(count, pos.node(), new_idx);
+            auto new_relaxed              = new_parent->relaxed();
+            new_parent->inner()[new_idx]  = new_child;
+            new_relaxed->d.sizes[new_idx] = pos.size() + ts;
+            new_relaxed->d.count          = count;
+            return new_parent;
+        } catch (...) {
+            auto shift = pos.shift();
+            auto size  = new_idx == idx ? children + ts : ts;
+            if (shift > BL) {
+                tail->inc();
+                dec_inner(new_child, shift - B, size);
+            }
+            throw;
+        }
+    }
+
+    template <typename Pos, typename... Args>
+    static node_t* visit_regular(Pos&& pos, node_t* tail, Args&&...)
+    {
+        assert((pos.size() & mask<BL>) == 0);
+        auto idx        = pos.index(pos.size() - 1);
+        auto new_idx    = pos.index(pos.size() + branches<BL> - 1);
+        auto count      = new_idx + 1;
+        auto new_parent = node_t::make_inner_n(count);
+        try {
+            new_parent->inner()[new_idx] =
+                idx == new_idx ? pos.last_oh(this_t{}, idx, tail)
+                               /* otherwise */
+                               : node_t::make_path(pos.shift() - B, tail);
+        } catch (...) {
+            node_t::delete_inner(new_parent, count);
+            throw;
+        }
+        return node_t::do_copy_inner(new_parent, pos.node(), new_idx);
+    }
+
+    template <typename Pos, typename... Args>
+    static node_t* visit_leaf(Pos&& pos, node_t* tail, Args&&...)
+    {
+        IMMER_UNREACHABLE;
+    }
+};
+
+struct dec_right_visitor : visitor_base<dec_right_visitor>
+{
+    using this_t = dec_right_visitor;
+    using dec_t  = dec_visitor;
+
+    template <typename Pos>
+    static void visit_relaxed(Pos&& p, count_t idx)
+    {
+        using node_t = node_type<Pos>;
+        auto node    = p.node();
+        if (node->dec()) {
+            p.each_right(dec_t{}, idx);
+            node_t::delete_inner_r(node, p.count());
+        }
+    }
+
+    template <typename Pos>
+    static void visit_regular(Pos&& p, count_t idx)
+    {
+        using node_t = node_type<Pos>;
+        auto node    = p.node();
+        if (node->dec()) {
+            p.each_right(dec_t{}, idx);
+            node_t::delete_inner(node, p.count());
+        }
+    }
+
+    template <typename Pos>
+    static void visit_leaf(Pos&& p, count_t idx)
+    {
+        IMMER_UNREACHABLE;
+    }
+};
+
+template <typename NodeT, bool Collapse = true, bool Mutating = true>
+struct slice_right_mut_visitor
+    : visitor_base<slice_right_mut_visitor<NodeT, Collapse, Mutating>>
+{
+    using node_t = NodeT;
+    using this_t = slice_right_mut_visitor;
+    using edit_t = typename NodeT::edit_t;
+
+    // returns a new shift, new root, the new tail size and the new tail
+    using result_t             = std::tuple<shift_t, NodeT*, count_t, NodeT*>;
+    using no_collapse_t        = slice_right_mut_visitor<NodeT, false, true>;
+    using no_collapse_no_mut_t = slice_right_mut_visitor<NodeT, false, false>;
+    using no_mut_t = slice_right_mut_visitor<NodeT, Collapse, false>;
+
+    static constexpr auto B  = NodeT::bits;
+    static constexpr auto BL = NodeT::bits_leaf;
+
+    template <typename PosT>
+    static result_t visit_relaxed(PosT&& pos, size_t last, edit_t e)
+    {
+        auto idx    = pos.index(last);
+        auto node   = pos.node();
+        auto mutate = Mutating && node->can_mutate(e);
+        if (Collapse && idx == 0) {
+            auto res = mutate ? pos.towards_oh(this_t{}, last, idx, e)
+                              : pos.towards_oh(no_mut_t{}, last, idx, e);
+            if (Mutating)
+                pos.visit(dec_right_visitor{}, count_t{1});
+            return res;
+        } else {
+            using std::get;
+            auto subs =
+                mutate ? pos.towards_oh(no_collapse_t{}, last, idx, e)
+                       : pos.towards_oh(no_collapse_no_mut_t{}, last, idx, e);
+            auto next = get<1>(subs);
+            auto ts   = get<2>(subs);
+            auto tail = get<3>(subs);
+            try {
+                if (next) {
+                    if (mutate) {
+                        auto nodr = node->ensure_mutable_relaxed_n(e, idx);
+                        pos.each_right(dec_visitor{}, idx + 1);
+                        node->inner()[idx] = next;
+                        nodr->d.sizes[idx] = last + 1 - ts;
+                        nodr->d.count      = idx + 1;
+                        return std::make_tuple(pos.shift(), node, ts, tail);
+                    } else {
+                        auto newn = node_t::copy_inner_r_e(e, node, idx);
+                        auto newr = newn->relaxed();
+                        newn->inner()[idx] = next;
+                        newr->d.sizes[idx] = last + 1 - ts;
+                        newr->d.count      = idx + 1;
+                        if (Mutating)
+                            pos.visit(dec_visitor{});
+                        return std::make_tuple(pos.shift(), newn, ts, tail);
+                    }
+                } else if (idx == 0) {
+                    if (Mutating)
+                        pos.visit(dec_right_visitor{}, count_t{1});
+                    return std::make_tuple(pos.shift(), nullptr, ts, tail);
+                } else if (Collapse && idx == 1 && pos.shift() > BL) {
+                    auto newn = pos.node()->inner()[0];
+                    if (!mutate)
+                        newn->inc();
+                    if (Mutating)
+                        pos.visit(dec_right_visitor{}, count_t{2});
+                    return std::make_tuple(pos.shift() - B, newn, ts, tail);
+                } else {
+                    if (mutate) {
+                        pos.each_right(dec_visitor{}, idx + 1);
+                        node->ensure_mutable_relaxed_n(e, idx)->d.count = idx;
+                        return std::make_tuple(pos.shift(), node, ts, tail);
+                    } else {
+                        auto newn = node_t::copy_inner_r_e(e, node, idx);
+                        if (Mutating)
+                            pos.visit(dec_visitor{});
+                        return std::make_tuple(pos.shift(), newn, ts, tail);
+                    }
+                }
+            } catch (...) {
+                assert(!mutate);
+                assert(!next || pos.shift() > BL);
+                if (next)
+                    dec_inner(next,
+                              pos.shift() - B,
+                              last + 1 - ts - pos.size_before(idx));
+                dec_leaf(tail, ts);
+                throw;
+            }
+        }
+    }
+
+    template <typename PosT>
+    static result_t visit_regular(PosT&& pos, size_t last, edit_t e)
+    {
+        auto idx    = pos.index(last);
+        auto node   = pos.node();
+        auto mutate = Mutating && node->can_mutate(e);
+        if (Collapse && idx == 0) {
+            auto res = mutate ? pos.towards_oh(this_t{}, last, idx, e)
+                              : pos.towards_oh(no_mut_t{}, last, idx, e);
+            if (Mutating)
+                pos.visit(dec_right_visitor{}, count_t{1});
+            return res;
+        } else {
+            using std::get;
+            auto subs =
+                mutate ? pos.towards_oh(no_collapse_t{}, last, idx, e)
+                       : pos.towards_oh(no_collapse_no_mut_t{}, last, idx, e);
+            auto next = get<1>(subs);
+            auto ts   = get<2>(subs);
+            auto tail = get<3>(subs);
+            try {
+                if (next) {
+                    if (mutate) {
+                        node->inner()[idx] = next;
+                        pos.each_right(dec_visitor{}, idx + 1);
+                        return std::make_tuple(pos.shift(), node, ts, tail);
+                    } else {
+                        auto newn          = node_t::copy_inner_e(e, node, idx);
+                        newn->inner()[idx] = next;
+                        if (Mutating)
+                            pos.visit(dec_visitor{});
+                        return std::make_tuple(pos.shift(), newn, ts, tail);
+                    }
+                } else if (idx == 0) {
+                    if (Mutating)
+                        pos.visit(dec_right_visitor{}, count_t{1});
+                    return std::make_tuple(pos.shift(), nullptr, ts, tail);
+                } else if (Collapse && idx == 1 && pos.shift() > BL) {
+                    auto newn = pos.node()->inner()[0];
+                    if (!mutate)
+                        newn->inc();
+                    if (Mutating)
+                        pos.visit(dec_right_visitor{}, count_t{2});
+                    return std::make_tuple(pos.shift() - B, newn, ts, tail);
+                } else {
+                    if (mutate) {
+                        pos.each_right(dec_visitor{}, idx + 1);
+                        return std::make_tuple(pos.shift(), node, ts, tail);
+                    } else {
+                        auto newn = node_t::copy_inner_e(e, node, idx);
+                        if (Mutating)
+                            pos.visit(dec_visitor{});
+                        return std::make_tuple(pos.shift(), newn, ts, tail);
+                    }
+                }
+            } catch (...) {
+                assert(!mutate);
+                assert(!next || pos.shift() > BL);
+                assert(tail);
+                if (next)
+                    dec_regular(next, pos.shift() - B, last + 1 - ts);
+                dec_leaf(tail, ts);
+                throw;
+            }
+        }
+    }
+
+    template <typename PosT>
+    static result_t visit_leaf(PosT&& pos, size_t last, edit_t e)
+    {
+        auto old_tail_size = pos.count();
+        auto new_tail_size = pos.index(last) + 1;
+        auto node          = pos.node();
+        auto mutate        = Mutating && node->can_mutate(e);
+        if (new_tail_size == old_tail_size) {
+            if (!Mutating)
+                node->inc();
+            return std::make_tuple(0, nullptr, new_tail_size, node);
+        } else if (mutate) {
+            destroy_n(node->leaf() + new_tail_size,
+                      old_tail_size - new_tail_size);
+            return std::make_tuple(0, nullptr, new_tail_size, node);
+        } else {
+            auto new_tail = node_t::copy_leaf_e(e, node, new_tail_size);
+            if (Mutating)
+                pos.visit(dec_visitor{});
+            return std::make_tuple(0, nullptr, new_tail_size, new_tail);
+        }
+    }
+};
+
+template <typename NodeT, bool Collapse = true>
+struct slice_right_visitor : visitor_base<slice_right_visitor<NodeT, Collapse>>
+{
+    using node_t = NodeT;
+    using this_t = slice_right_visitor;
+
+    // returns a new shift, new root, the new tail size and the new tail
+    using result_t      = std::tuple<shift_t, NodeT*, count_t, NodeT*>;
+    using no_collapse_t = slice_right_visitor<NodeT, false>;
+
+    static constexpr auto B  = NodeT::bits;
+    static constexpr auto BL = NodeT::bits_leaf;
+
+    template <typename PosT>
+    static result_t visit_relaxed(PosT&& pos, size_t last)
+    {
+        auto idx = pos.index(last);
+        if (Collapse && idx == 0) {
+            return pos.towards_oh(this_t{}, last, idx);
+        } else {
+            using std::get;
+            auto subs = pos.towards_oh(no_collapse_t{}, last, idx);
+            auto next = get<1>(subs);
+            auto ts   = get<2>(subs);
+            auto tail = get<3>(subs);
+            try {
+                if (next) {
+                    auto count = idx + 1;
+                    auto newn  = node_t::copy_inner_r_n(count, pos.node(), idx);
+                    auto newr  = newn->relaxed();
+                    newn->inner()[idx] = next;
+                    newr->d.sizes[idx] = last + 1 - ts;
+                    newr->d.count      = count;
+                    return std::make_tuple(pos.shift(), newn, ts, tail);
+                } else if (idx == 0) {
+                    return std::make_tuple(pos.shift(), nullptr, ts, tail);
+                } else if (Collapse && idx == 1 && pos.shift() > BL) {
+                    auto newn = pos.node()->inner()[0];
+                    return std::make_tuple(
+                        pos.shift() - B, newn->inc(), ts, tail);
+                } else {
+                    auto newn = node_t::copy_inner_r(pos.node(), idx);
+                    return std::make_tuple(pos.shift(), newn, ts, tail);
+                }
+            } catch (...) {
+                assert(!next || pos.shift() > BL);
+                if (next)
+                    dec_inner(next,
+                              pos.shift() - B,
+                              last + 1 - ts - pos.size_before(idx));
+                if (tail)
+                    dec_leaf(tail, ts);
+                throw;
+            }
+        }
+    }
+
+    template <typename PosT>
+    static result_t visit_regular(PosT&& pos, size_t last)
+    {
+        auto idx = pos.index(last);
+        if (Collapse && idx == 0) {
+            return pos.towards_oh(this_t{}, last, idx);
+        } else {
+            using std::get;
+            auto subs = pos.towards_oh(no_collapse_t{}, last, idx);
+            auto next = get<1>(subs);
+            auto ts   = get<2>(subs);
+            auto tail = get<3>(subs);
+            try {
+                if (next) {
+                    auto newn = node_t::copy_inner_n(idx + 1, pos.node(), idx);
+                    newn->inner()[idx] = next;
+                    return std::make_tuple(pos.shift(), newn, ts, tail);
+                } else if (idx == 0) {
+                    return std::make_tuple(pos.shift(), nullptr, ts, tail);
+                } else if (Collapse && idx == 1 && pos.shift() > BL) {
+                    auto newn = pos.node()->inner()[0];
+                    return std::make_tuple(
+                        pos.shift() - B, newn->inc(), ts, tail);
+                } else {
+                    auto newn = node_t::copy_inner_n(idx, pos.node(), idx);
+                    return std::make_tuple(pos.shift(), newn, ts, tail);
+                }
+            } catch (...) {
+                assert(!next || pos.shift() > BL);
+                assert(tail);
+                if (next)
+                    dec_regular(next, pos.shift() - B, last + 1 - ts);
+                dec_leaf(tail, ts);
+                throw;
+            }
+        }
+    }
+
+    template <typename PosT>
+    static result_t visit_leaf(PosT&& pos, size_t last)
+    {
+        auto old_tail_size = pos.count();
+        auto new_tail_size = pos.index(last) + 1;
+        auto new_tail      = new_tail_size == old_tail_size
+                            ? pos.node()->inc()
+                            : node_t::copy_leaf(pos.node(), new_tail_size);
+        return std::make_tuple(0, nullptr, new_tail_size, new_tail);
+    }
+};
+
+struct dec_left_visitor : visitor_base<dec_left_visitor>
+{
+    using this_t = dec_left_visitor;
+    using dec_t  = dec_visitor;
+
+    template <typename Pos>
+    static void visit_relaxed(Pos&& p, count_t idx)
+    {
+        using node_t = node_type<Pos>;
+        auto node    = p.node();
+        if (node->dec()) {
+            p.each_left(dec_t{}, idx);
+            node_t::delete_inner_r(node, p.count());
+        }
+    }
+
+    template <typename Pos>
+    static void visit_regular(Pos&& p, count_t idx)
+    {
+        using node_t = node_type<Pos>;
+        auto node    = p.node();
+        if (node->dec()) {
+            p.each_left(dec_t{}, idx);
+            node_t::delete_inner(node, p.count());
+        }
+    }
+
+    template <typename Pos>
+    static void visit_leaf(Pos&& p, count_t idx)
+    {
+        IMMER_UNREACHABLE;
+    }
+};
+
+template <typename NodeT, bool Collapse = true, bool Mutating = true>
+struct slice_left_mut_visitor
+    : visitor_base<slice_left_mut_visitor<NodeT, Collapse, Mutating>>
+{
+    using node_t    = NodeT;
+    using this_t    = slice_left_mut_visitor;
+    using edit_t    = typename NodeT::edit_t;
+    using value_t   = typename NodeT::value_t;
+    using relaxed_t = typename NodeT::relaxed_t;
+    // returns a new shift and new root
+    using result_t = std::tuple<shift_t, NodeT*>;
+
+    using no_collapse_t        = slice_left_mut_visitor<NodeT, false, true>;
+    using no_collapse_no_mut_t = slice_left_mut_visitor<NodeT, false, false>;
+    using no_mut_t             = slice_left_mut_visitor<NodeT, Collapse, false>;
+
+    static constexpr auto B  = NodeT::bits;
+    static constexpr auto BL = NodeT::bits_leaf;
+
+    template <typename PosT>
+    static result_t visit_relaxed(PosT&& pos, size_t first, edit_t e)
+    {
+        auto idx                = pos.subindex(first);
+        auto count              = pos.count();
+        auto node               = pos.node();
+        auto mutate             = Mutating && node->can_mutate(e);
+        auto left_size          = pos.size_before(idx);
+        auto child_size         = pos.size_sbh(idx, left_size);
+        auto dropped_size       = first;
+        auto child_dropped_size = dropped_size - left_size;
+        if (Collapse && pos.shift() > BL && idx == pos.count() - 1) {
+            auto r = mutate ? pos.towards_sub_oh(this_t{}, first, idx, e)
+                            : pos.towards_sub_oh(no_mut_t{}, first, idx, e);
+            if (Mutating)
+                pos.visit(dec_left_visitor{}, idx);
+            return r;
+        } else {
+            using std::get;
+            auto newn = mutate ? (node->ensure_mutable_relaxed(e), node)
+                               : node_t::make_inner_r_e(e);
+            auto newr           = newn->relaxed();
+            auto newcount       = count - idx;
+            auto new_child_size = child_size - child_dropped_size;
+            try {
+                auto subs =
+                    mutate ? pos.towards_sub_oh(no_collapse_t{}, first, idx, e)
+                           : pos.towards_sub_oh(
+                                 no_collapse_no_mut_t{}, first, idx, e);
+                if (mutate)
+                    pos.each_left(dec_visitor{}, idx);
+                pos.copy_sizes(
+                    idx + 1, newcount - 1, new_child_size, newr->d.sizes + 1);
+                std::uninitialized_copy(node->inner() + idx + 1,
+                                        node->inner() + count,
+                                        newn->inner() + 1);
+                newn->inner()[0] = get<1>(subs);
+                newr->d.sizes[0] = new_child_size;
+                newr->d.count    = newcount;
+                if (!mutate) {
+                    node_t::inc_nodes(newn->inner() + 1, newcount - 1);
+                    if (Mutating)
+                        pos.visit(dec_visitor{});
+                }
+                return std::make_tuple(pos.shift(), newn);
+            } catch (...) {
+                if (!mutate)
+                    node_t::delete_inner_r_e(newn);
+                throw;
+            }
+        }
+    }
+
+    template <typename PosT>
+    static result_t visit_regular(PosT&& pos, size_t first, edit_t e)
+    {
+        auto idx    = pos.subindex(first);
+        auto count  = pos.count();
+        auto node   = pos.node();
+        auto mutate = Mutating
+                      // this is more restrictive than actually needed because
+                      // it causes the algorithm to also avoid mutating the leaf
+                      // in place
+                      && !node_t::embed_relaxed && node->can_mutate(e);
+        auto left_size          = pos.size_before(idx);
+        auto child_size         = pos.size_sbh(idx, left_size);
+        auto dropped_size       = first;
+        auto child_dropped_size = dropped_size - left_size;
+        if (Collapse && pos.shift() > BL && idx == pos.count() - 1) {
+            auto r = mutate ? pos.towards_sub_oh(this_t{}, first, idx, e)
+                            : pos.towards_sub_oh(no_mut_t{}, first, idx, e);
+            if (Mutating)
+                pos.visit(dec_left_visitor{}, idx);
+            return r;
+        } else {
+            using std::get;
+            // if possible, we convert the node to a relaxed one
+            // simply by allocating a `relaxed_t` size table for
+            // it... maybe some of this magic should be moved as a
+            // `node<...>` static method...
+            auto newcount = count - idx;
+            auto newn =
+                mutate ? (node->impl.d.data.inner.relaxed = new (
+                              node_t::heap::allocate(node_t::max_sizeof_relaxed,
+                                                     norefs_tag{})) relaxed_t,
+                          node)
+                       : node_t::make_inner_r_e(e);
+            auto newr = newn->relaxed();
+            try {
+                auto subs =
+                    mutate ? pos.towards_sub_oh(no_collapse_t{}, first, idx, e)
+                           : pos.towards_sub_oh(
+                                 no_collapse_no_mut_t{}, first, idx, e);
+                if (mutate)
+                    pos.each_left(dec_visitor{}, idx);
+                newr->d.sizes[0] = child_size - child_dropped_size;
+                pos.copy_sizes(
+                    idx + 1, newcount - 1, newr->d.sizes[0], newr->d.sizes + 1);
+                newr->d.count    = newcount;
+                newn->inner()[0] = get<1>(subs);
+                std::uninitialized_copy(node->inner() + idx + 1,
+                                        node->inner() + count,
+                                        newn->inner() + 1);
+                if (!mutate) {
+                    node_t::inc_nodes(newn->inner() + 1, newcount - 1);
+                    if (Mutating)
+                        pos.visit(dec_visitor{});
+                }
+                return std::make_tuple(pos.shift(), newn);
+            } catch (...) {
+                if (!mutate)
+                    node_t::delete_inner_r_e(newn);
+                else {
+                    // restore the regular node that we were
+                    // attempting to relax...
+                    node_t::heap::deallocate(node_t::max_sizeof_relaxed,
+                                             node->impl.d.data.inner.relaxed);
+                    node->impl.d.data.inner.relaxed = nullptr;
+                }
+                throw;
+            }
+        }
+    }
+
+    template <typename PosT>
+    static result_t visit_leaf(PosT&& pos, size_t first, edit_t e)
+    {
+        auto node   = pos.node();
+        auto idx    = pos.index(first);
+        auto count  = pos.count();
+        auto mutate = Mutating &&
+                      std::is_nothrow_move_constructible<value_t>::value &&
+                      node->can_mutate(e);
+        if (mutate) {
+            auto data     = node->leaf();
+            auto newcount = count - idx;
+            std::move(data + idx, data + count, data);
+            destroy_n(data + newcount, idx);
+            return std::make_tuple(0, node);
+        } else {
+            auto newn = node_t::copy_leaf_e(e, node, idx, count);
+            if (Mutating)
+                pos.visit(dec_visitor{});
+            return std::make_tuple(0, newn);
+        }
+    }
+};
+
+template <typename NodeT, bool Collapse = true>
+struct slice_left_visitor : visitor_base<slice_left_visitor<NodeT, Collapse>>
+{
+    using node_t = NodeT;
+    using this_t = slice_left_visitor;
+
+    // returns a new shift and new root
+    using result_t      = std::tuple<shift_t, NodeT*>;
+    using no_collapse_t = slice_left_visitor<NodeT, false>;
+
+    static constexpr auto B  = NodeT::bits;
+    static constexpr auto BL = NodeT::bits_leaf;
+
+    template <typename PosT>
+    static result_t visit_inner(PosT&& pos, size_t first)
+    {
+        auto idx                = pos.subindex(first);
+        auto count              = pos.count();
+        auto left_size          = pos.size_before(idx);
+        auto child_size         = pos.size_sbh(idx, left_size);
+        auto dropped_size       = first;
+        auto child_dropped_size = dropped_size - left_size;
+        if (Collapse && pos.shift() > BL && idx == pos.count() - 1) {
+            return pos.towards_sub_oh(this_t{}, first, idx);
+        } else {
+            using std::get;
+            auto n    = pos.node();
+            auto newc = count - idx;
+            auto newn = node_t::make_inner_r_n(newc);
+            try {
+                auto subs     = pos.towards_sub_oh(no_collapse_t{}, first, idx);
+                auto newr     = newn->relaxed();
+                newr->d.count = count - idx;
+                newr->d.sizes[0] = child_size - child_dropped_size;
+                pos.copy_sizes(idx + 1,
+                               newr->d.count - 1,
+                               newr->d.sizes[0],
+                               newr->d.sizes + 1);
+                assert(newr->d.sizes[newr->d.count - 1] ==
+                       pos.size() - dropped_size);
+                newn->inner()[0] = get<1>(subs);
+                std::uninitialized_copy(n->inner() + idx + 1,
+                                        n->inner() + count,
+                                        newn->inner() + 1);
+                node_t::inc_nodes(newn->inner() + 1, newr->d.count - 1);
+                return std::make_tuple(pos.shift(), newn);
+            } catch (...) {
+                node_t::delete_inner_r(newn, newc);
+                throw;
+            }
+        }
+    }
+
+    template <typename PosT>
+    static result_t visit_leaf(PosT&& pos, size_t first)
+    {
+        auto n = node_t::copy_leaf(pos.node(), pos.index(first), pos.count());
+        return std::make_tuple(0, n);
+    }
+};
+
+template <typename Node>
+struct concat_center_pos
+{
+    static constexpr auto B  = Node::bits;
+    static constexpr auto BL = Node::bits_leaf;
+
+    static constexpr count_t max_children = 3;
+
+    using node_t = Node;
+    using edit_t = typename Node::edit_t;
+
+    shift_t shift_ = 0u;
+    count_t count_ = 0u;
+    node_t* nodes_[max_children];
+    size_t sizes_[max_children];
+
+    auto shift() const { return shift_; }
+
+    concat_center_pos(shift_t s, Node* n0, size_t s0)
+        : shift_{s}
+        , count_{1}
+        , nodes_{n0}
+        , sizes_{s0}
+    {}
+
+    concat_center_pos(shift_t s, Node* n0, size_t s0, Node* n1, size_t s1)
+        : shift_{s}
+        , count_{2}
+        , nodes_{n0, n1}
+        , sizes_{s0, s1}
+    {}
+
+    concat_center_pos(shift_t s,
+                      Node* n0,
+                      size_t s0,
+                      Node* n1,
+                      size_t s1,
+                      Node* n2,
+                      size_t s2)
+        : shift_{s}
+        , count_{3}
+        , nodes_{n0, n1, n2}
+        , sizes_{s0, s1, s2}
+    {}
+
+    template <typename Visitor, typename... Args>
+    void each_sub(Visitor v, Args&&... args)
+    {
+        if (shift_ == BL) {
+            for (auto i = count_t{0}; i < count_; ++i)
+                make_leaf_sub_pos(nodes_[i], sizes_[i]).visit(v, args...);
+        } else {
+            for (auto i = count_t{0}; i < count_; ++i)
+                make_relaxed_pos(nodes_[i], shift_ - B, nodes_[i]->relaxed())
+                    .visit(v, args...);
+        }
+    }
+
+    relaxed_pos<Node> realize() &&
+    {
+        if (count_ > 1) {
+            try {
+                auto result = node_t::make_inner_r_n(count_);
+                auto r      = result->relaxed();
+                r->d.count  = count_;
+                std::copy(nodes_, nodes_ + count_, result->inner());
+                std::copy(sizes_, sizes_ + count_, r->d.sizes);
+                return {result, shift_, r};
+            } catch (...) {
+                each_sub(dec_visitor{});
+                throw;
+            }
+        } else {
+            assert(shift_ >= B + BL);
+            return {nodes_[0], shift_ - B, nodes_[0]->relaxed()};
+        }
+    }
+
+    relaxed_pos<Node> realize_e(edit_t e)
+    {
+        if (count_ > 1) {
+            auto result = node_t::make_inner_r_e(e);
+            auto r      = result->relaxed();
+            r->d.count  = count_;
+            std::copy(nodes_, nodes_ + count_, result->inner());
+            std::copy(sizes_, sizes_ + count_, r->d.sizes);
+            return {result, shift_, r};
+        } else {
+            assert(shift_ >= B + BL);
+            return {nodes_[0], shift_ - B, nodes_[0]->relaxed()};
+        }
+    }
+};
+
+template <typename Node>
+struct concat_merger
+{
+    using node_t             = Node;
+    static constexpr auto B  = Node::bits;
+    static constexpr auto BL = Node::bits_leaf;
+
+    using result_t = concat_center_pos<Node>;
+
+    count_t* curr_;
+    count_t n_;
+    result_t result_;
+
+    concat_merger(shift_t shift, count_t* counts, count_t n)
+        : curr_{counts}
+        , n_{n}
+        , result_{
+              shift + B, node_t::make_inner_r_n(std::min(n_, branches<B>)), 0}
+    {}
+
+    node_t* to_        = {};
+    count_t to_offset_ = {};
+    size_t to_size_    = {};
+
+    void add_child(node_t* p, size_t size)
+    {
+        ++curr_;
+        auto parent  = result_.nodes_[result_.count_ - 1];
+        auto relaxed = parent->relaxed();
+        if (relaxed->d.count == branches<B>) {
+            assert(result_.count_ < result_t::max_children);
+            n_ -= branches<B>;
+            parent  = node_t::make_inner_r_n(std::min(n_, branches<B>));
+            relaxed = parent->relaxed();
+            result_.nodes_[result_.count_] = parent;
+            result_.sizes_[result_.count_] = result_.sizes_[result_.count_ - 1];
+            ++result_.count_;
+        }
+        auto idx = relaxed->d.count++;
+        result_.sizes_[result_.count_ - 1] += size;
+        relaxed->d.sizes[idx] = size + (idx ? relaxed->d.sizes[idx - 1] : 0);
+        parent->inner()[idx]  = p;
+    };
+
+    template <typename Pos>
+    void merge_leaf(Pos&& p)
+    {
+        auto from       = p.node();
+        auto from_size  = p.size();
+        auto from_count = p.count();
+        assert(from_size);
+        if (!to_ && *curr_ == from_count) {
+            add_child(from, from_size);
+            from->inc();
+        } else {
+            auto from_offset = count_t{};
+            auto from_data   = from->leaf();
+            do {
+                if (!to_) {
+                    to_        = node_t::make_leaf_n(*curr_);
+                    to_offset_ = 0;
+                }
+                auto data = to_->leaf();
+                auto to_copy =
+                    std::min(from_count - from_offset, *curr_ - to_offset_);
+                std::uninitialized_copy(from_data + from_offset,
+                                        from_data + from_offset + to_copy,
+                                        data + to_offset_);
+                to_offset_ += to_copy;
+                from_offset += to_copy;
+                if (*curr_ == to_offset_) {
+                    add_child(to_, to_offset_);
+                    to_ = nullptr;
+                }
+            } while (from_offset != from_count);
+        }
+    }
+
+    template <typename Pos>
+    void merge_inner(Pos&& p)
+    {
+        auto from       = p.node();
+        auto from_size  = p.size();
+        auto from_count = p.count();
+        assert(from_size);
+        if (!to_ && *curr_ == from_count) {
+            add_child(from, from_size);
+            from->inc();
+        } else {
+            auto from_offset = count_t{};
+            auto from_data   = from->inner();
+            do {
+                if (!to_) {
+                    to_        = node_t::make_inner_r_n(*curr_);
+                    to_offset_ = 0;
+                    to_size_   = 0;
+                }
+                auto data = to_->inner();
+                auto to_copy =
+                    std::min(from_count - from_offset, *curr_ - to_offset_);
+                std::uninitialized_copy(from_data + from_offset,
+                                        from_data + from_offset + to_copy,
+                                        data + to_offset_);
+                node_t::inc_nodes(from_data + from_offset, to_copy);
+                auto sizes = to_->relaxed()->d.sizes;
+                p.copy_sizes(
+                    from_offset, to_copy, to_size_, sizes + to_offset_);
+                to_offset_ += to_copy;
+                from_offset += to_copy;
+                to_size_ = sizes[to_offset_ - 1];
+                if (*curr_ == to_offset_) {
+                    to_->relaxed()->d.count = to_offset_;
+                    add_child(to_, to_size_);
+                    to_ = nullptr;
+                }
+            } while (from_offset != from_count);
+        }
+    }
+
+    concat_center_pos<Node> finish() const
+    {
+        assert(!to_);
+        return result_;
+    }
+
+    void abort()
+    {
+        auto shift = result_.shift_ - B;
+        if (to_) {
+            if (shift == BL)
+                node_t::delete_leaf(to_, to_offset_);
+            else {
+                to_->relaxed()->d.count = to_offset_;
+                dec_relaxed(to_, shift - B);
+            }
+        }
+        result_.each_sub(dec_visitor());
+    }
+};
+
+struct concat_merger_visitor : visitor_base<concat_merger_visitor>
+{
+    using this_t = concat_merger_visitor;
+
+    template <typename Pos, typename Merger>
+    static void visit_inner(Pos&& p, Merger& merger)
+    {
+        merger.merge_inner(p);
+    }
+
+    template <typename Pos, typename Merger>
+    static void visit_leaf(Pos&& p, Merger& merger)
+    {
+        merger.merge_leaf(p);
+    }
+};
+
+struct concat_rebalance_plan_fill_visitor
+    : visitor_base<concat_rebalance_plan_fill_visitor>
+{
+    using this_t = concat_rebalance_plan_fill_visitor;
+
+    template <typename Pos, typename Plan>
+    static void visit_node(Pos&& p, Plan& plan)
+    {
+        auto count = p.count();
+        assert(plan.n < Plan::max_children);
+        plan.counts[plan.n++] = count;
+        plan.total += count;
+    }
+};
+
+template <bits_t B, bits_t BL>
+struct concat_rebalance_plan
+{
+    static constexpr auto max_children = 2 * branches<B> + 1;
+
+    count_t counts[max_children];
+    count_t n     = 0u;
+    count_t total = 0u;
+
+    template <typename LPos, typename CPos, typename RPos>
+    void fill(LPos&& lpos, CPos&& cpos, RPos&& rpos)
+    {
+        assert(n == 0u);
+        assert(total == 0u);
+        using visitor_t = concat_rebalance_plan_fill_visitor;
+        lpos.each_left_sub(visitor_t{}, *this);
+        cpos.each_sub(visitor_t{}, *this);
+        rpos.each_right_sub(visitor_t{}, *this);
+    }
+
+    void shuffle(shift_t shift)
+    {
+        // gcc seems to not really understand this code... :(
+#if !defined(_MSC_VER)
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Warray-bounds"
+#endif
+        constexpr count_t rrb_extras    = 2;
+        constexpr count_t rrb_invariant = 1;
+        const auto bits                 = shift == BL ? BL : B;
+        const auto branches             = count_t{1} << bits;
+        const auto optimal              = ((total - 1) >> bits) + 1;
+        count_t i                       = 0;
+        while (n >= optimal + rrb_extras) {
+            // skip ok nodes
+            while (counts[i] > branches - rrb_invariant)
+                i++;
+            // short node, redistribute
+            auto remaining = counts[i];
+            do {
+                auto count = std::min(remaining + counts[i + 1], branches);
+                counts[i]  = count;
+                remaining += counts[i + 1] - count;
+                ++i;
+            } while (remaining > 0);
+            // remove node
+            std::move(counts + i + 1, counts + n, counts + i);
+            --n;
+            --i;
+        }
+#if !defined(_MSC_VER)
+#pragma GCC diagnostic pop
+#endif
+    }
+
+    template <typename LPos, typename CPos, typename RPos>
+    concat_center_pos<node_type<CPos>>
+    merge(LPos&& lpos, CPos&& cpos, RPos&& rpos)
+    {
+        using node_t    = node_type<CPos>;
+        using merger_t  = concat_merger<node_t>;
+        using visitor_t = concat_merger_visitor;
+        auto merger     = merger_t{cpos.shift(), counts, n};
+        try {
+            lpos.each_left_sub(visitor_t{}, merger);
+            cpos.each_sub(visitor_t{}, merger);
+            rpos.each_right_sub(visitor_t{}, merger);
+            cpos.each_sub(dec_visitor{});
+            return merger.finish();
+        } catch (...) {
+            merger.abort();
+            throw;
+        }
+    }
+};
+
+template <typename Node, typename LPos, typename CPos, typename RPos>
+concat_center_pos<Node> concat_rebalance(LPos&& lpos, CPos&& cpos, RPos&& rpos)
+{
+    auto plan = concat_rebalance_plan<Node::bits, Node::bits_leaf>{};
+    plan.fill(lpos, cpos, rpos);
+    plan.shuffle(cpos.shift());
+    try {
+        return plan.merge(lpos, cpos, rpos);
+    } catch (...) {
+        cpos.each_sub(dec_visitor{});
+        throw;
+    }
+}
+
+template <typename Node, typename LPos, typename TPos, typename RPos>
+concat_center_pos<Node> concat_leafs(LPos&& lpos, TPos&& tpos, RPos&& rpos)
+{
+    static_assert(Node::bits >= 2, "");
+    assert(lpos.shift() == tpos.shift());
+    assert(lpos.shift() == rpos.shift());
+    assert(lpos.shift() == 0);
+    if (tpos.count() > 0)
+        return {
+            Node::bits_leaf,
+            lpos.node()->inc(),
+            lpos.count(),
+            tpos.node()->inc(),
+            tpos.count(),
+            rpos.node()->inc(),
+            rpos.count(),
+        };
+    else
+        return {
+            Node::bits_leaf,
+            lpos.node()->inc(),
+            lpos.count(),
+            rpos.node()->inc(),
+            rpos.count(),
+        };
+}
+
+template <typename Node>
+struct concat_left_visitor;
+template <typename Node>
+struct concat_right_visitor;
+template <typename Node>
+struct concat_both_visitor;
+
+template <typename Node, typename LPos, typename TPos, typename RPos>
+concat_center_pos<Node> concat_inners(LPos&& lpos, TPos&& tpos, RPos&& rpos)
+{
+    auto lshift = lpos.shift();
+    auto rshift = rpos.shift();
+    if (lshift > rshift) {
+        auto cpos = lpos.last_sub(concat_left_visitor<Node>{}, tpos, rpos);
+        return concat_rebalance<Node>(lpos, cpos, null_sub_pos{});
+    } else if (lshift < rshift) {
+        auto cpos = rpos.first_sub(concat_right_visitor<Node>{}, lpos, tpos);
+        return concat_rebalance<Node>(null_sub_pos{}, cpos, rpos);
+    } else {
+        assert(lshift == rshift);
+        assert(Node::bits_leaf == 0u || lshift > 0);
+        auto cpos = lpos.last_sub(concat_both_visitor<Node>{}, tpos, rpos);
+        return concat_rebalance<Node>(lpos, cpos, rpos);
+    }
+}
+
+template <typename Node>
+struct concat_left_visitor : visitor_base<concat_left_visitor<Node>>
+{
+    using this_t = concat_left_visitor;
+
+    template <typename LPos, typename TPos, typename RPos>
+    static concat_center_pos<Node>
+    visit_inner(LPos&& lpos, TPos&& tpos, RPos&& rpos)
+    {
+        return concat_inners<Node>(lpos, tpos, rpos);
+    }
+
+    template <typename LPos, typename TPos, typename RPos>
+    static concat_center_pos<Node>
+    visit_leaf(LPos&& lpos, TPos&& tpos, RPos&& rpos)
+    {
+        IMMER_UNREACHABLE;
+    }
+};
+
+template <typename Node>
+struct concat_right_visitor : visitor_base<concat_right_visitor<Node>>
+{
+    using this_t = concat_right_visitor;
+
+    template <typename RPos, typename LPos, typename TPos>
+    static concat_center_pos<Node>
+    visit_inner(RPos&& rpos, LPos&& lpos, TPos&& tpos)
+    {
+        return concat_inners<Node>(lpos, tpos, rpos);
+    }
+
+    template <typename RPos, typename LPos, typename TPos>
+    static concat_center_pos<Node>
+    visit_leaf(RPos&& rpos, LPos&& lpos, TPos&& tpos)
+    {
+        return concat_leafs<Node>(lpos, tpos, rpos);
+    }
+};
+
+template <typename Node>
+struct concat_both_visitor : visitor_base<concat_both_visitor<Node>>
+{
+    using this_t = concat_both_visitor;
+
+    template <typename LPos, typename TPos, typename RPos>
+    static concat_center_pos<Node>
+    visit_inner(LPos&& lpos, TPos&& tpos, RPos&& rpos)
+    {
+        return rpos.first_sub(concat_right_visitor<Node>{}, lpos, tpos);
+    }
+
+    template <typename LPos, typename TPos, typename RPos>
+    static concat_center_pos<Node>
+    visit_leaf(LPos&& lpos, TPos&& tpos, RPos&& rpos)
+    {
+        return rpos.first_sub_leaf(concat_right_visitor<Node>{}, lpos, tpos);
+    }
+};
+
+template <typename Node>
+struct concat_trees_right_visitor
+    : visitor_base<concat_trees_right_visitor<Node>>
+{
+    using this_t = concat_trees_right_visitor;
+
+    template <typename RPos, typename LPos, typename TPos>
+    static concat_center_pos<Node>
+    visit_node(RPos&& rpos, LPos&& lpos, TPos&& tpos)
+    {
+        return concat_inners<Node>(lpos, tpos, rpos);
+    }
+};
+
+template <typename Node>
+struct concat_trees_left_visitor : visitor_base<concat_trees_left_visitor<Node>>
+{
+    using this_t = concat_trees_left_visitor;
+
+    template <typename LPos, typename TPos, typename... Args>
+    static concat_center_pos<Node>
+    visit_node(LPos&& lpos, TPos&& tpos, Args&&... args)
+    {
+        return visit_maybe_relaxed_sub(
+            args..., concat_trees_right_visitor<Node>{}, lpos, tpos);
+    }
+};
+
+template <typename Node>
+relaxed_pos<Node> concat_trees(Node* lroot,
+                               shift_t lshift,
+                               size_t lsize,
+                               Node* ltail,
+                               count_t ltcount,
+                               Node* rroot,
+                               shift_t rshift,
+                               size_t rsize)
+{
+    return visit_maybe_relaxed_sub(lroot,
+                                   lshift,
+                                   lsize,
+                                   concat_trees_left_visitor<Node>{},
+                                   make_leaf_pos(ltail, ltcount),
+                                   rroot,
+                                   rshift,
+                                   rsize)
+        .realize();
+}
+
+template <typename Node>
+relaxed_pos<Node> concat_trees(
+    Node* ltail, count_t ltcount, Node* rroot, shift_t rshift, size_t rsize)
+{
+    return make_singleton_regular_sub_pos(ltail, ltcount)
+        .visit(concat_trees_left_visitor<Node>{},
+               empty_leaf_pos<Node>{},
+               rroot,
+               rshift,
+               rsize)
+        .realize();
+}
+
+template <typename Node>
+using concat_center_mut_pos = concat_center_pos<Node>;
+
+template <typename Node>
+struct concat_merger_mut
+{
+    using node_t = Node;
+    using edit_t = typename Node::edit_t;
+
+    static constexpr auto B  = Node::bits;
+    static constexpr auto BL = Node::bits_leaf;
+
+    using result_t = concat_center_pos<Node>;
+
+    edit_t ec_ = {};
+
+    count_t* curr_;
+    count_t n_;
+    result_t result_;
+    count_t count_      = 0;
+    node_t* candidate_  = nullptr;
+    edit_t candidate_e_ = Node::memory::transience_t::noone;
+
+    concat_merger_mut(edit_t ec,
+                      shift_t shift,
+                      count_t* counts,
+                      count_t n,
+                      edit_t candidate_e,
+                      node_t* candidate)
+        : ec_{ec}
+        , curr_{counts}
+        , n_{n}
+        , result_{shift + B, nullptr, 0}
+    {
+        if (candidate) {
+            candidate->ensure_mutable_relaxed_e(candidate_e, ec);
+            result_.nodes_[0] = candidate;
+        } else {
+            result_.nodes_[0] = node_t::make_inner_r_e(ec);
+        }
+    }
+
+    node_t* to_        = {};
+    count_t to_offset_ = {};
+    size_t to_size_    = {};
+
+    void set_candidate(edit_t candidate_e, node_t* candidate)
+    {
+        candidate_   = candidate;
+        candidate_e_ = candidate_e;
+    }
+
+    void add_child(node_t* p, size_t size)
+    {
+        ++curr_;
+        auto parent  = result_.nodes_[result_.count_ - 1];
+        auto relaxed = parent->relaxed();
+        if (count_ == branches<B>) {
+            parent->relaxed()->d.count = count_;
+            assert(result_.count_ < result_t::max_children);
+            n_ -= branches<B>;
+            if (candidate_) {
+                parent = candidate_;
+                parent->ensure_mutable_relaxed_e(candidate_e_, ec_);
+                candidate_ = nullptr;
+            } else
+                parent = node_t::make_inner_r_e(ec_);
+            count_                         = 0;
+            relaxed                        = parent->relaxed();
+            result_.nodes_[result_.count_] = parent;
+            result_.sizes_[result_.count_] = result_.sizes_[result_.count_ - 1];
+            ++result_.count_;
+        }
+        auto idx = count_++;
+        result_.sizes_[result_.count_ - 1] += size;
+        relaxed->d.sizes[idx] = size + (idx ? relaxed->d.sizes[idx - 1] : 0);
+        parent->inner()[idx]  = p;
+    };
+
+    template <typename Pos>
+    void merge_leaf(Pos&& p, edit_t e)
+    {
+        auto from       = p.node();
+        auto from_size  = p.size();
+        auto from_count = p.count();
+        assert(from_size);
+        if (!to_ && *curr_ == from_count) {
+            add_child(from, from_size);
+        } else {
+            auto from_offset = count_t{};
+            auto from_data   = from->leaf();
+            auto from_mutate = from->can_mutate(e);
+            do {
+                if (!to_) {
+                    if (from_mutate) {
+                        node_t::ownee(from) = ec_;
+                        to_                 = from->inc();
+                        assert(from_count);
+                    } else {
+                        to_ = node_t::make_leaf_e(ec_);
+                    }
+                    to_offset_ = 0;
+                }
+                auto data = to_->leaf();
+                auto to_copy =
+                    std::min(from_count - from_offset, *curr_ - to_offset_);
+                if (from == to_) {
+                    if (from_offset != to_offset_)
+                        std::move(from_data + from_offset,
+                                  from_data + from_offset + to_copy,
+                                  data + to_offset_);
+                } else {
+                    if (!from_mutate)
+                        std::uninitialized_copy(from_data + from_offset,
+                                                from_data + from_offset +
+                                                    to_copy,
+                                                data + to_offset_);
+                    else
+                        detail::uninitialized_move(from_data + from_offset,
+                                                   from_data + from_offset +
+                                                       to_copy,
+                                                   data + to_offset_);
+                }
+                to_offset_ += to_copy;
+                from_offset += to_copy;
+                if (*curr_ == to_offset_) {
+                    add_child(to_, to_offset_);
+                    to_ = nullptr;
+                }
+            } while (from_offset != from_count);
+        }
+    }
+
+    template <typename Pos>
+    void merge_inner(Pos&& p, edit_t e)
+    {
+        auto from       = p.node();
+        auto from_size  = p.size();
+        auto from_count = p.count();
+        assert(from_size);
+        if (!to_ && *curr_ == from_count) {
+            add_child(from, from_size);
+        } else {
+            auto from_offset = count_t{};
+            auto from_data   = from->inner();
+            auto from_mutate = from->can_relax() && from->can_mutate(e);
+            do {
+                if (!to_) {
+                    if (from_mutate) {
+                        node_t::ownee(from) = ec_;
+                        from->ensure_mutable_relaxed_e(e, ec_);
+                        to_ = from;
+                    } else {
+                        to_ = node_t::make_inner_r_e(ec_);
+                    }
+                    to_offset_ = 0;
+                    to_size_   = 0;
+                }
+                auto data = to_->inner();
+                auto to_copy =
+                    std::min(from_count - from_offset, *curr_ - to_offset_);
+                auto sizes = to_->relaxed()->d.sizes;
+                if (from != to_ || from_offset != to_offset_) {
+                    std::copy(from_data + from_offset,
+                              from_data + from_offset + to_copy,
+                              data + to_offset_);
+                    p.copy_sizes(
+                        from_offset, to_copy, to_size_, sizes + to_offset_);
+                }
+                to_offset_ += to_copy;
+                from_offset += to_copy;
+                to_size_ = sizes[to_offset_ - 1];
+                if (*curr_ == to_offset_) {
+                    to_->relaxed()->d.count = to_offset_;
+                    add_child(to_, to_size_);
+                    to_ = nullptr;
+                }
+            } while (from_offset != from_count);
+        }
+    }
+
+    concat_center_pos<Node> finish() const
+    {
+        assert(!to_);
+        result_.nodes_[result_.count_ - 1]->relaxed()->d.count = count_;
+        return result_;
+    }
+
+    void abort()
+    {
+        // We may have mutated stuff the tree in place, leaving
+        // everything in a corrupted state...  It should be possible
+        // to define cleanup properly, but that is a task for some
+        // other day... ;)
+        std::terminate();
+    }
+};
+
+struct concat_merger_mut_visitor : visitor_base<concat_merger_mut_visitor>
+{
+    using this_t = concat_merger_mut_visitor;
+
+    template <typename Pos, typename Merger>
+    static void visit_inner(Pos&& p, Merger& merger, edit_type<Pos> e)
+    {
+        merger.merge_inner(p, e);
+    }
+
+    template <typename Pos, typename Merger>
+    static void visit_leaf(Pos&& p, Merger& merger, edit_type<Pos> e)
+    {
+        merger.merge_leaf(p, e);
+    }
+};
+
+template <bits_t B, bits_t BL>
+struct concat_rebalance_plan_mut : concat_rebalance_plan<B, BL>
+{
+    using this_t = concat_rebalance_plan_mut;
+
+    template <typename LPos, typename CPos, typename RPos>
+    concat_center_mut_pos<node_type<CPos>> merge(edit_type<CPos> ec,
+                                                 edit_type<CPos> el,
+                                                 LPos&& lpos,
+                                                 CPos&& cpos,
+                                                 edit_type<CPos> er,
+                                                 RPos&& rpos)
+    {
+        using node_t    = node_type<CPos>;
+        using merger_t  = concat_merger_mut<node_t>;
+        using visitor_t = concat_merger_mut_visitor;
+        auto lnode      = ((node_t*) lpos.node());
+        auto rnode      = ((node_t*) rpos.node());
+        auto lmut2      = lnode && lnode->can_relax() && lnode->can_mutate(el);
+        auto rmut2      = rnode && rnode->can_relax() && rnode->can_mutate(er);
+        auto merger     = merger_t{ec,
+                               cpos.shift(),
+                               this->counts,
+                               this->n,
+                               el,
+                               lmut2 ? lnode : nullptr};
+        try {
+            lpos.each_left_sub(visitor_t{}, merger, el);
+            cpos.each_sub(visitor_t{}, merger, ec);
+            if (rmut2)
+                merger.set_candidate(er, rnode);
+            rpos.each_right_sub(visitor_t{}, merger, er);
+            return merger.finish();
+        } catch (...) {
+            merger.abort();
+            throw;
+        }
+    }
+};
+
+template <typename Node, typename LPos, typename CPos, typename RPos>
+concat_center_pos<Node> concat_rebalance_mut(edit_type<Node> ec,
+                                             edit_type<Node> el,
+                                             LPos&& lpos,
+                                             CPos&& cpos,
+                                             edit_type<Node> er,
+                                             RPos&& rpos)
+{
+    auto plan = concat_rebalance_plan_mut<Node::bits, Node::bits_leaf>{};
+    plan.fill(lpos, cpos, rpos);
+    plan.shuffle(cpos.shift());
+    return plan.merge(ec, el, lpos, cpos, er, rpos);
+}
+
+template <typename Node, typename LPos, typename TPos, typename RPos>
+concat_center_mut_pos<Node> concat_leafs_mut(edit_type<Node> ec,
+                                             edit_type<Node> el,
+                                             LPos&& lpos,
+                                             TPos&& tpos,
+                                             edit_type<Node> er,
+                                             RPos&& rpos)
+{
+    static_assert(Node::bits >= 2, "");
+    assert(lpos.shift() == tpos.shift());
+    assert(lpos.shift() == rpos.shift());
+    assert(lpos.shift() == 0);
+    if (tpos.count() > 0)
+        return {
+            Node::bits_leaf,
+            lpos.node(),
+            lpos.count(),
+            tpos.node(),
+            tpos.count(),
+            rpos.node(),
+            rpos.count(),
+        };
+    else
+        return {
+            Node::bits_leaf,
+            lpos.node(),
+            lpos.count(),
+            rpos.node(),
+            rpos.count(),
+        };
+}
+
+template <typename Node>
+struct concat_left_mut_visitor;
+template <typename Node>
+struct concat_right_mut_visitor;
+template <typename Node>
+struct concat_both_mut_visitor;
+
+template <typename Node, typename LPos, typename TPos, typename RPos>
+concat_center_mut_pos<Node> concat_inners_mut(edit_type<Node> ec,
+                                              edit_type<Node> el,
+                                              LPos&& lpos,
+                                              TPos&& tpos,
+                                              edit_type<Node> er,
+                                              RPos&& rpos)
+{
+    auto lshift = lpos.shift();
+    auto rshift = rpos.shift();
+    // lpos.node() can be null it is a singleton_regular_sub_pos<...>,
+    // this is, when the tree is just a tail...
+    if (lshift > rshift) {
+        auto cpos = lpos.last_sub(
+            concat_left_mut_visitor<Node>{}, ec, el, tpos, er, rpos);
+        return concat_rebalance_mut<Node>(
+            ec, el, lpos, cpos, er, null_sub_pos{});
+    } else if (lshift < rshift) {
+        auto cpos = rpos.first_sub(
+            concat_right_mut_visitor<Node>{}, ec, el, lpos, tpos, er);
+        return concat_rebalance_mut<Node>(
+            ec, el, null_sub_pos{}, cpos, er, rpos);
+    } else {
+        assert(lshift == rshift);
+        assert(Node::bits_leaf == 0u || lshift > 0);
+        auto cpos = lpos.last_sub(
+            concat_both_mut_visitor<Node>{}, ec, el, tpos, er, rpos);
+        return concat_rebalance_mut<Node>(ec, el, lpos, cpos, er, rpos);
+    }
+}
+
+template <typename Node>
+struct concat_left_mut_visitor : visitor_base<concat_left_mut_visitor<Node>>
+{
+    using this_t = concat_left_mut_visitor;
+    using edit_t = typename Node::edit_t;
+
+    template <typename LPos, typename TPos, typename RPos>
+    static concat_center_mut_pos<Node> visit_inner(
+        LPos&& lpos, edit_t ec, edit_t el, TPos&& tpos, edit_t er, RPos&& rpos)
+    {
+        return concat_inners_mut<Node>(ec, el, lpos, tpos, er, rpos);
+    }
+
+    template <typename LPos, typename TPos, typename RPos>
+    static concat_center_mut_pos<Node> visit_leaf(
+        LPos&& lpos, edit_t ec, edit_t el, TPos&& tpos, edit_t er, RPos&& rpos)
+    {
+        IMMER_UNREACHABLE;
+    }
+};
+
+template <typename Node>
+struct concat_right_mut_visitor : visitor_base<concat_right_mut_visitor<Node>>
+{
+    using this_t = concat_right_mut_visitor;
+    using edit_t = typename Node::edit_t;
+
+    template <typename RPos, typename LPos, typename TPos>
+    static concat_center_mut_pos<Node> visit_inner(
+        RPos&& rpos, edit_t ec, edit_t el, LPos&& lpos, TPos&& tpos, edit_t er)
+    {
+        return concat_inners_mut<Node>(ec, el, lpos, tpos, er, rpos);
+    }
+
+    template <typename RPos, typename LPos, typename TPos>
+    static concat_center_mut_pos<Node> visit_leaf(
+        RPos&& rpos, edit_t ec, edit_t el, LPos&& lpos, TPos&& tpos, edit_t er)
+    {
+        return concat_leafs_mut<Node>(ec, el, lpos, tpos, er, rpos);
+    }
+};
+
+template <typename Node>
+struct concat_both_mut_visitor : visitor_base<concat_both_mut_visitor<Node>>
+{
+    using this_t = concat_both_mut_visitor;
+    using edit_t = typename Node::edit_t;
+
+    template <typename LPos, typename TPos, typename RPos>
+    static concat_center_mut_pos<Node> visit_inner(
+        LPos&& lpos, edit_t ec, edit_t el, TPos&& tpos, edit_t er, RPos&& rpos)
+    {
+        return rpos.first_sub(
+            concat_right_mut_visitor<Node>{}, ec, el, lpos, tpos, er);
+    }
+
+    template <typename LPos, typename TPos, typename RPos>
+    static concat_center_mut_pos<Node> visit_leaf(
+        LPos&& lpos, edit_t ec, edit_t el, TPos&& tpos, edit_t er, RPos&& rpos)
+    {
+        return rpos.first_sub_leaf(
+            concat_right_mut_visitor<Node>{}, ec, el, lpos, tpos, er);
+    }
+};
+
+template <typename Node>
+struct concat_trees_right_mut_visitor
+    : visitor_base<concat_trees_right_mut_visitor<Node>>
+{
+    using this_t = concat_trees_right_mut_visitor;
+    using edit_t = typename Node::edit_t;
+
+    template <typename RPos, typename LPos, typename TPos>
+    static concat_center_mut_pos<Node> visit_node(
+        RPos&& rpos, edit_t ec, edit_t el, LPos&& lpos, TPos&& tpos, edit_t er)
+    {
+        return concat_inners_mut<Node>(ec, el, lpos, tpos, er, rpos);
+    }
+};
+
+template <typename Node>
+struct concat_trees_left_mut_visitor
+    : visitor_base<concat_trees_left_mut_visitor<Node>>
+{
+    using this_t = concat_trees_left_mut_visitor;
+    using edit_t = typename Node::edit_t;
+
+    template <typename LPos, typename TPos, typename... Args>
+    static concat_center_mut_pos<Node> visit_node(LPos&& lpos,
+                                                  edit_t ec,
+                                                  edit_t el,
+                                                  TPos&& tpos,
+                                                  edit_t er,
+                                                  Args&&... args)
+    {
+        return visit_maybe_relaxed_sub(args...,
+                                       concat_trees_right_mut_visitor<Node>{},
+                                       ec,
+                                       el,
+                                       lpos,
+                                       tpos,
+                                       er);
+    }
+};
+
+template <typename Node>
+relaxed_pos<Node> concat_trees_mut(edit_type<Node> ec,
+                                   edit_type<Node> el,
+                                   Node* lroot,
+                                   shift_t lshift,
+                                   size_t lsize,
+                                   Node* ltail,
+                                   count_t ltcount,
+                                   edit_type<Node> er,
+                                   Node* rroot,
+                                   shift_t rshift,
+                                   size_t rsize)
+{
+    return visit_maybe_relaxed_sub(lroot,
+                                   lshift,
+                                   lsize,
+                                   concat_trees_left_mut_visitor<Node>{},
+                                   ec,
+                                   el,
+                                   make_leaf_pos(ltail, ltcount),
+                                   er,
+                                   rroot,
+                                   rshift,
+                                   rsize)
+        .realize_e(ec);
+}
+
+template <typename Node>
+relaxed_pos<Node> concat_trees_mut(edit_type<Node> ec,
+                                   edit_type<Node> el,
+                                   Node* ltail,
+                                   count_t ltcount,
+                                   edit_type<Node> er,
+                                   Node* rroot,
+                                   shift_t rshift,
+                                   size_t rsize)
+{
+    return make_singleton_regular_sub_pos(ltail, ltcount)
+        .visit(concat_trees_left_mut_visitor<Node>{},
+               ec,
+               el,
+               empty_leaf_pos<Node>{},
+               er,
+               rroot,
+               rshift,
+               rsize)
+        .realize_e(ec);
+}
+
+} // namespace rbts
+} // namespace detail
+} // namespace immer