[Boost-bugs] [Boost C++ Libraries] #11000: Rogue fibonacci_heap constructor corrupts source

Subject: [Boost-bugs] [Boost C++ Libraries] #11000: Rogue fibonacci_heap constructor corrupts source
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2015-02-07 20:49:32

#11000: Rogue fibonacci_heap constructor corrupts source
------------------------------+--------------------------
 Reporter:  bugs@…            |      Owner:  timblechmann
     Type:  Bugs              |     Status:  new
Milestone:  To Be Determined  |  Component:  heap
  Version:  Boost 1.57.0      |   Severity:  Problem
 Keywords:  corruption move   |
------------------------------+--------------------------
 As analyzed on stackoverflow (http://stackoverflow.com/a/28384938/85371)
 copying from a non-const lvalue fibonacci_heap corrupts the source heap.

 It splices the roots from the source intrusive-list.

 In fact the particular constructor overload seems redundant. The
 documentation lists it as the 4th overload
 (http://www.boost.org/doc/libs/1_57_0/doc/html/boost/heap/fibonacci_heap.html#idp107311392-bb),
 but doesn't specify what the behaviour should be.

 In practice the behaviour is equivalent to (partial) move-construction,
 which obviously is not what the caller is expecting.

 Removing the "rogue" constructor removes symptoms.

 Reproducer: live on http://coliru.stacked-crooked.com/a/8f58113aaef53ef5


 {{{
 #include <boost/heap/fibonacci_heap.hpp>
 #include <iostream>
 #include <random>

 namespace {
     std::discrete_distribution<int> dist({1,1,1,1,1,1});
     static auto price_gen = [&] {
         static std::mt19937 rng;
         static double values[] = {52.40, 12.30, 87.10, 388., 0.10, 23.40};
         return values[dist(rng)];
     };
 }

 struct Order {
     double price      = price_gen();
     unsigned quantity = rand() % 4 + 1;

     double subtotal() const { return price * quantity; }

     bool operator<(Order const& other) const { return subtotal() <
 other.subtotal(); }
 };

 using Heap = boost::heap::fibonacci_heap<Order>;

 struct Y {
     virtual void printSnapshot(std::ostream &ss) {
         //Heap cloned(static_cast<Heap const&>(this->heap));
         Heap cloned(this->heap); // CORRUPTS THE SOURCE HEAP
         double prev_price = std::numeric_limits<double>::max();

         while (cloned.size() > 0) {
             const Order &order = cloned.top();

             if (order.price != prev_price) {
                 if (prev_price != std::numeric_limits<double>::max())
                     ss << std::endl;
                 ss << order.price << " | ";
             }
             ss << order.quantity << " ";
             prev_price = order.price;
             cloned.pop();
         }
         ss << std::endl;
     }

     void generateOrders() {
         for (int i=0; i<3; ++i) {
             heap.push({});
         }
     }

     Heap heap;
 };

 int main() {
     Y y;
     for(int i=0; i<10; ++i) {
         y.generateOrders();
         y.printSnapshot(std::cout);
     }
 }
 }}}

 {{{
 52.4 | 4
 23.4 | 3 2
 388 | 4
 Segmentation fault (core dumped)
 }}}

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/11000>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.