[Boost-bugs] [Boost C++ Libraries] #11942: split_interval_set incorrect works compiled with clang

Subject: [Boost-bugs] [Boost C++ Libraries] #11942: split_interval_set incorrect works compiled with clang
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2016-01-27 14:40:29

#11942: split_interval_set incorrect works compiled with clang
 Reporter: Nickolay Arrtamonov | Owner: jofaber
  <nickolay.artamonov@…> | Status: new
     Type: Bugs | Component: ICL
Milestone: To Be Determined | Severity: Regression
  Version: Boost 1.61.0 |
 Keywords: |
 I have a very basic program for demostration
 #include <iostream>
 #include <boost/icl/split_interval_set.hpp>

 int main()
     boost::icl::split_interval_set<int> intervals;
     intervals.insert(boost::icl::discrete_interval<int>(1, 2));
     intervals.insert(boost::icl::discrete_interval<int>(2, 3));
     intervals.insert(boost::icl::discrete_interval<int>(0, 3));
     std::cout << intervals.size() << std::endl;


 clang++ -I ./boost/include a.cpp;

 When compiled with clang on Mac the output is 2 and not 3 as it should.
 The worst thing is that it's not only produces invalid result but also
 corrupts memory
 so that execution of some code after the code provided leads to a crash
 with BAD_ACCESS exception.

 The problem first appears in version 1.56. The above program prints "3" on
 And it's still present on master.
 It actually was introduced with this commit

 Spent some time on debugging the issue with Xcode and it appears that the
 problem is
 in interval_base_set.hpp::add_segment


 template <class SubType, class DomainT, ICL_COMPARE Compare,
 inline void interval_base_set<SubType,DomainT,Compare,Interval,Alloc>
     ::add_segment(const interval_type& inter_val, iterator& it_)
     interval_type lead_gap = right_subtract(inter_val, *it_);
         // [lead_gap--- . . .
         // [prior_) [-- it_ ...
         this->_set.insert(prior(it_), lead_gap);

     // . . . --------- . . . addend interval
     // [-- it_ --) has a common part with the first overval


 this->_set.insert('''prior(it_)''', lead_gap);
 And it happens on attempt to insert interval at the begging of the set
 ''it_'' is an iterator pointing to the first element in the set
 so ''prior(it_)'' ( e.g. --it_) is actually undefined and contains some
 garbage on Mac

 I wasn't able to reproduce the same behavior with gcc linux compiler but
 once I build it with -D_GLIBCXX_DEBUG option (enables safe iterators)

 g++ -D_GLIBCXX_DEBUG -v -g --std=c++11 -I ./boost/ ./a.cpp

 The output from the program was following
 /usr/include/c++/4.8/debug/safe_iterator.h:323:error: attempt to decrement
     a dereferenceable (start-of-sequence) iterator.

 Objects involved in the operation:
 iterator "this" @ 0x0x7fff70b855a0 {
 type =
 (mutable iterator);
   state = dereferenceable (start-of-sequence);
   references sequence with type
 @ 0x0x7fff70b855a0
 Aborted (core dumped)

 So all above demonstrates that the problem really exists.

 As for the solution, the suggest is just remove prior fuction call, and
 provide it_ as the first argument to insert
 The hint still will be correct, and for c++11 that's even better.
 hint -
 iterator, used as a suggestion as to where to start the search (until
 iterator to the position before which the new element will be inserted
 (since C++11)

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

This archive was generated by hypermail 2.1.7 : 2017-02-16 18:50:19 UTC