[boost] [Container] Strange flat_set crash with std::inserter

Subject: [boost] [Container] Strange flat_set crash with std::inserter
From: Ben Pope (benpope81_at_[hidden])
Date: 2013-09-06 08:35:33

Hi all

It seems that when I copy a sorted but non-unique range of randomly
generated numbers to an output iterator generated from std::inserter to
a boost::flat_set it crashes.

At first I assumed it was because boost::flat_set doesn't have stable
iterators, but it seems that the implementation of std::insert_iterator
does the right thing by reassigning its internal iterator to the result
of the insert operation before incrementing it.

Apologies for not being able to reduce the problem further, but this one
is a little strange, the following code demonstrates the problem (and
some variations that do work) in boost 1.54:

#include <boost/container/flat_set.hpp>
#include <algorithm>
#include <iterator>
#include <numeric>
#include <vector>

template<typename ContainerT>
void Populate(std::vector<size_t> const& input) {
   ContainerT container;
   std::copy(
      std::begin(input),
      std::end(input),
      std::inserter(container, std::end(container)));
}

int main() {
   const size_t Count = 1000000;

   std::vector<size_t> random_numbers;
   random_numbers.reserve(Count);
   std::generate_n(
      std::back_inserter(random_numbers),
      Count,
      &std::rand);

   std::vector<size_t> sorted_numbers(random_numbers);
   std::sort(std::begin(sorted_numbers), std::end(sorted_numbers));

   std::vector<size_t> unique_sorted_numbers;
   unique_sorted_numbers.reserve(Count);
   std::unique_copy(
      std::begin(sorted_numbers),
      std::end(sorted_numbers),
      std::back_inserter(unique_sorted_numbers));

   using namespace boost::container;
   Populate<flat_set<size_t>>(unique_sorted_numbers); // ok
   Populate<flat_multiset<size_t>>(sorted_numbers); // ok
   Populate<flat_set<size_t>>(sorted_numbers); // segfault, line 39
}

It might be a little hard to reproduce with the rand() in there, I'm on
64bit Ubuntu 13.04 and it's reproducible with Clang 3.3 with libc++ and
GCC 4.8.1.

Here's the backtrace from Clang:

#0  0x0000000000403aec in operator() (this=0x7fffffffd598,
__x=@0x7ffff61c6320: 61595138, __y=@0x454000: <error reading variable>)
at /usr/include/c++/v1/__functional_base:61
#1
boost::container::container_detail::flat_tree_value_compare<std::__1::less<unsigned
long>, unsigned long,
boost::container::container_detail::identity<unsigned long>
>::operator() (this=0x7fffffffd598, lhs=@0x7ffff61c6320: 61595138,
rhs=@0x454000: <error reading variable>) at
../yy/build/boost/boost/container/detail/flat_tree.hpp:66
#2  0x0000000000404367 in
boost::container::container_detail::flat_tree<unsigned long, unsigned
long, boost::container::container_detail::identity<unsigned long>,
std::__1::less<unsigned long>, std::__1::allocator<unsigned long>
>::priv_insert_unique_prepare (this=0x7fffffffd598, pos=...,
val=@0x7ffff61c6320: 61595138, commit_data=...) at
../yy/build/boost/boost/container/detail/flat_tree.hpp:824
#3  0x0000000000404275 in
boost::container::container_detail::flat_tree<unsigned long, unsigned
long, boost::container::container_detail::identity<unsigned long>,
std::__1::less<unsigned long>, std::__1::allocator<unsigned long>
>::insert_unique (this=0x7fffffffd598, pos=..., val=@0x7ffff61c6320:
61595138) at ../yy/build/boost/boost/container/detail/flat_tree.hpp:354
#4  0x000000000040421d in boost::container::flat_set<unsigned long,
std::__1::less<unsigned long>, std::__1::allocator<unsigned long>
>::priv_insert<unsigned long const&> (this=0x7fffffffd598, p=...,
x=@0x7ffff61c6320: 61595138) at
../yy/build/boost/boost/container/flat_set.hpp:688
#5  0x00000000004041bd in boost::container::flat_set<unsigned long,
std::__1::less<unsigned long>, std::__1::allocator<unsigned long>
>::insert (this=0x7fffffffd598, arg1=..., x=@0x7ffff61c6320: 61595138)
at ../yy/build/boost/boost/container/flat_set.hpp:508
#6  0x0000000000401de4 in operator* (this=0x7fffffffd750,
this=0x7fffffffd750, this=0x7fffffffd750, __value_=@0x7ffff61c6320:
61595138) at /usr/include/c++/v1/iterator:718
#7
__unwrap_iter<std::__1::insert_iterator<boost::container::flat_set<unsigned
long, std::__1::less<unsigned long>, std::__1::allocator<unsigned long>
> > > (__i=..., __first=..., __last=..., __result=...) at
/usr/include/c++/v1/algorithm:1717
#8  end<boost::container::flat_set<unsigned long,
std::__1::less<unsigned long>, std::__1::allocator<unsigned long> > >
(__c=..., __x=..., __i=..., __first=..., __last=..., __result=...) at
/usr/include/c++/v1/algorithm:1741
#9  Populate<boost::container::flat_set<unsigned long,
std::__1::less<unsigned long>, std::__1::allocator<unsigned long> > >
(input=...) at flat_set_crash.cpp:13
#10 0x00000000004017a6 in main () at flat_set_crash.cpp:39

or from GCC if you prefer:

#0  0x0000000000404bed in std::less<unsigned long>::operator()
(this=0x7fffffffdd10, __x=@0x7ffff62e7320: 61595138, __y=@0x453000:
<error reading variable>) at /usr/include/c++/4.8/bits/stl_function.h:235
#1  0x00000000004047f9 in
boost::container::container_detail::flat_tree_value_compare<std::less<unsigned
long>, unsigned long,
boost::container::container_detail::identity<unsigned long>
>::operator() (this=0x7fffffffdd10, lhs=@0x7ffff62e7320: 61595138,
rhs=@0x453000: <error reading variable>) at
../yy/build/boost/boost/container/detail/flat_tree.hpp:66
#2  0x0000000000404389 in
boost::container::container_detail::flat_tree<unsigned long, unsigned
long, boost::container::container_detail::identity<unsigned long>,
std::less<unsigned long>, std::allocator<unsigned long>
>::priv_insert_unique_prepare (this=0x7fffffffdd10, pos=...,
val=@0x7ffff62e7320: 61595138, commit_data=...) at
../yy/build/boost/boost/container/detail/flat_tree.hpp:824
#3  0x000000000040420a in
boost::container::container_detail::flat_tree<unsigned long, unsigned
long, boost::container::container_detail::identity<unsigned long>,
std::less<unsigned long>, std::allocator<unsigned long> >::insert_unique
(this=0x7fffffffdd10, pos=..., val=@0x7ffff62e7320: 61595138) at
../yy/build/boost/boost/container/detail/flat_tree.hpp:354
#4  0x00000000004040ef in boost::container::flat_set<unsigned long,
std::less<unsigned long>, std::allocator<unsigned long>
>::priv_insert<unsigned long const&> (this=0x7fffffffdd10, p=...,
x=@0x7ffff62e7320: 61595138) at
../yy/build/boost/boost/container/flat_set.hpp:688
#5  0x0000000000403fa5 in boost::container::flat_set<unsigned long,
std::less<unsigned long>, std::allocator<unsigned long> >::insert
(this=0x7fffffffdd10, arg1=..., x=@0x7ffff62e7320: 61595138) at
../yy/build/boost/boost/container/flat_set.hpp:508
#6  0x0000000000403b71 in
std::insert_iterator<boost::container::flat_set<unsigned long,
std::less<unsigned long>, std::allocator<unsigned long> > >::operator=
(this=0x7fffffffdbd0, __value=@0x7ffff62e7320: 61595138) at
/usr/include/c++/4.8/bits/stl_iterator.h:640
#7  0x000000000040350a in std::__copy_move<false, false,
std::random_access_iterator_tag>::__copy_m<unsigned long const*,
std::insert_iterator<boost::container::flat_set<unsigned long,
std::less<unsigned long>, std::allocator<unsigned long> > > >
(__first=0x7ffff62e7320, __last=0x7ffff6a50210, __result=...) at
/usr/include/c++/4.8/bits/stl_algobase.h:335
#8  0x0000000000402c2f in std::__copy_move_a<false, unsigned long
const*, std::insert_iterator<boost::container::flat_set<unsigned long,
std::less<unsigned long>, std::allocator<unsigned long> > > >
(__first=0x7ffff62af010, __last=0x7ffff6a50210, __result=...) at
/usr/include/c++/4.8/bits/stl_algobase.h:390
#9  0x000000000040237f in std::__copy_move_a2<false,
__gnu_cxx::__normal_iterator<unsigned long const*, std::vector<unsigned
long, std::allocator<unsigned long> > >,
std::insert_iterator<boost::container::flat_set<unsigned long,
std::less<unsigned long>, std::allocator<unsigned long> > > >
(__first=1210, __last=0, __result=...) at
/usr/include/c++/4.8/bits/stl_algobase.h:428
#10 0x0000000000401b70 in
std::copy<__gnu_cxx::__normal_iterator<unsigned long const*,
std::vector<unsigned long, std::allocator<unsigned long> > >,
std::insert_iterator<boost::container::flat_set<unsigned long,
std::less<unsigned long>, std::allocator<unsigned long> > > >
(__first=1210, __last=0, __result=...) at
/usr/include/c++/4.8/bits/stl_algobase.h:460
#11 0x000000000040120f in Populate<boost::container::flat_set<unsigned
long, std::less<unsigned long>, std::allocator<unsigned long> > >
(input=std::vector of length 1000000, capacity 1000000 = {...}) at
flat_set_crash.cpp:10
#12 0x0000000000400c50 in main () at flat_set_crash.cpp:39
(gdb)

Since my refactoring of the code above, the crash location has changed,
it used to be in:
boost::container::vector::priv_forward_range_insert_at_end_expand_forward
boost/container/vector.hpp:2205

unique_sorted_numbers.size() is 999752.  Unfortunately producing a
sequential list of numbers with std::iota and then changing one of them
to the proceeding value didn't repro the problem.

Ben