[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
 {{{#!c++
 #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
 1.55.
 And it's still present on master.
 It actually was introduced with this commit
 https://github.com/boostorg/icl/commit/d6e037756f2c062fba703c5f48800ee577052f72


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

 {{{#!c++

 template <class SubType, class DomainT, ICL_COMPARE Compare,
 ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
 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_);
     if(!icl::is_empty(lead_gap))
         //           [lead_gap--- . . .
         // [prior_)           [-- it_ ...
         this->_set.insert(prior(it_), lead_gap);

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

  }}}

 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 =
 N11__gnu_debug14_Safe_iteratorISt23_Rb_tree_const_iteratorIN5boost3icl17discrete_intervalIiSt4lessEEENSt7__debug3setIS6_NS3_19exclusive_less_thanIS6_EESaIS6_EEEEE
 (mutable iterator);
   state = dereferenceable (start-of-sequence);
   references sequence with type
 `NSt7__debug3setIN5boost3icl17discrete_intervalIiSt4lessEENS2_19exclusive_less_thanIS5_EESaIS5_EEE'
 @ 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
 C++11)
 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.