The standard says that it's undefined to swap two containers if the
allocators are not equal and do not propagate. This ensures that swap is
always O(1) and non-throwing, but has other undesirable consequences
such as LWG 2152. The 2016 paper P0178 ("Allocators and swap") proposed
making the non-member swap handle non-equal allocators, by performing an
O(n) deep copy when needed. This ensures that a.swap(b) is still O(1)
and non-throwing, but swap(a, b) is valid for all values of the type.
This change implements that for std::basic_stacktrace. The member swap
is changed so that for the undefined case (where we can't swap the
allocators, but can't swap storage separately from the allocators) we
just return without changing either object. This ensures that with
assertions disabled we don't separate allocated storage from the
allocator that can free it.
For the non-member swap, perform deep copies of the two ranges, avoiding
reallocation if there is already sufficient capacity.
libstdc++-v3/ChangeLog:
* include/std/stacktrace (basic_stacktrace::swap): Refactor so
that the undefined case is a no-op when assertions are disabled.
(swap): Remove precondition and perform deep copies when member
swap would be undefined.
* testsuite/19_diagnostics/stacktrace/stacktrace.cc: Check
swapping with unequal, non-propagating allocators.
---
As part of my ongoing quest to reduce the undefined behaviour surface in
the library, this helps to avoid UB when swapping stacktrace objects.
This is an RFC to see if people like the idea. If we do it here, we
could do it for other containers too.
For the common case there should be no additional cost, because the
'if constexpr' conditions will be true and swap(a, b) will just call
a.swap(b) unconditionally, which will swap the contents unconditionally.
We only do extra work in the cases that are currently undefined.
Tested x86_64-linux.
libstdc++-v3/include/std/stacktrace | 77 ++++++++++++++++---
.../19_diagnostics/stacktrace/stacktrace.cc | 23 ++++++
2 files changed, 90 insertions(+), 10 deletions(-)
diff --git a/libstdc++-v3/include/std/stacktrace
b/libstdc++-v3/include/std/stacktrace
index f94a424e4cf..ab0788cde08 100644
--- a/libstdc++-v3/include/std/stacktrace
+++ b/libstdc++-v3/include/std/stacktrace
@@ -476,15 +476,79 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
// [stacktrace.basic.mod], modifiers
+
+ /** Exchange the contents of two stacktrace objects
+ *
+ * @pre The allocators must propagate on swap or must be equal.
+ */
void
swap(basic_stacktrace& __other) noexcept
{
- std::swap(_M_impl, __other._M_impl);
if constexpr (_AllocTraits::propagate_on_container_swap::value)
- std::swap(_M_alloc, __other._M_alloc);
+ {
+ using std::swap;
+ swap(_M_alloc, __other._M_alloc);
+ }
else if constexpr (!_AllocTraits::is_always_equal::value)
{
- __glibcxx_assert(_M_alloc == __other._M_alloc);
+ if (_M_alloc != __other._M_alloc)
+ {
+ __glibcxx_assert(_M_alloc == __other._M_alloc);
+ // If assertions are disabled but the allocators are unequal,
+ // we can't swap pointers, so just erroneously return.
+ return;
+ }
+ }
+ std::swap(_M_impl, __other._M_impl);
+ }
+
+ // [stacktrace.basic.nonmem], non-member functions
+
+ /** Exchange the contents of two stacktrace objects
+ *
+ * Unlike the `swap` member function, this can be used with unequal
+ * and non-propagating allocators. If the storage cannot be efficiently
+ * swapped then the stacktrace_entry elements will be exchanged
+ * one-by-one, reallocating if needed.
+ */
+ friend void
+ swap(basic_stacktrace& __a, basic_stacktrace& __b)
+ noexcept(_AllocTraits::propagate_on_container_swap::value
+ || _AllocTraits::is_always_equal::value)
+ {
+ if constexpr (_AllocTraits::propagate_on_container_swap::value
+ || _AllocTraits::is_always_equal::value)
+ __a.swap(__b);
+ else if (__a._M_alloc == __b._M_alloc) [[likely]]
+ __a.swap(__b);
+ else // O(N) swap for non-equal non-propagating allocators
+ {
+ basic_stacktrace* __p[2]{ std::__addressof(__a),
+ std::__addressof(__b) };
+ if (__p[0]->size() > __p[1]->size())
+ std::swap(__p[0], __p[1]);
+ basic_stacktrace& __a = *__p[0]; // shorter sequence
+ basic_stacktrace& __b = *__p[1]; // longer sequence
+
+ const auto __a_sz = __a.size();
+ auto __a_begin = __a._M_impl._M_frames;
+ auto __a_end = __a._M_impl._M_frames + __a_sz;
+ auto __b_begin = __b._M_impl._M_frames;
+
+ if (__a._M_impl._M_capacity < __b.size())
+ {
+ // Reallocation needed.
+ basic_stacktrace __tmp(__b, __a._M_alloc);
+ std::copy(__a_begin, __a_end, __b_begin);
+ __b._M_impl._M_resize(__a_sz, __b._M_alloc);
+ std::swap(__tmp._M_impl, __a._M_impl);
+ return;
+ }
+
+ // Exchange contents in-place.
+ auto __mid = std::swap_ranges(__a_begin, __a_end, __b_begin);
+ std::__relocate_a(__mid, __b_begin + __a_sz, __a_end, __a._M_alloc);
+ std::swap(__a._M_impl._M_size, __b._M_impl._M_size);
}
}
@@ -659,13 +723,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// basic_stacktrace typedef names
using stacktrace = basic_stacktrace<allocator<stacktrace_entry>>;
- // [stacktrace.basic.nonmem], non-member functions
- template<typename _Allocator>
- inline void
- swap(basic_stacktrace<_Allocator>& __a, basic_stacktrace<_Allocator>& __b)
- noexcept(noexcept(__a.swap(__b)))
- { __a.swap(__b); }
-
inline ostream&
operator<<(ostream& __os, const stacktrace_entry& __f)
{
diff --git a/libstdc++-v3/testsuite/19_diagnostics/stacktrace/stacktrace.cc
b/libstdc++-v3/testsuite/19_diagnostics/stacktrace/stacktrace.cc
index ee1a6d221e3..8e784071b29 100644
--- a/libstdc++-v3/testsuite/19_diagnostics/stacktrace/stacktrace.cc
+++ b/libstdc++-v3/testsuite/19_diagnostics/stacktrace/stacktrace.cc
@@ -393,6 +393,29 @@ test_swap()
VERIFY( s1.get_allocator().get_personality() == 2 );
VERIFY( s2.get_allocator().get_personality() == 1 );
}
+
+ {
+ using Alloc
+ = __gnu_test::propagating_allocator<std::stacktrace_entry, false>;
+ using Stacktrace = std::basic_stacktrace<Alloc>;
+
+ Stacktrace s1 = Stacktrace::current(Alloc{1});
+ Stacktrace s2(Alloc{2});
+ const Stacktrace s3 = s1;
+ swap(s1, s2);
+ VERIFY( s1.empty() );
+ VERIFY( s2 == s3 );
+ VERIFY( s1.get_allocator().get_personality() == 1 );
+ VERIFY( s2.get_allocator().get_personality() == 2 );
+
+ s1 = s3;
+ s2 = Stacktrace();
+ swap(s1, s2);
+ VERIFY( s1.empty() );
+ VERIFY( s2 == s3 );
+ VERIFY( s1.get_allocator().get_personality() == 1 );
+ VERIFY( s2.get_allocator().get_personality() == 2 );
+ }
}
void
--
2.47.0
