id,summary,reporter,owner,description,type,status,milestone,component,version,severity,resolution,keywords,cc
11942,split_interval_set incorrect works compiled with clang,Nickolay Arrtamonov <nickolay.artamonov@…>,Joachim Faulhaber,"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)
}}}",Bugs,closed,Boost 1.68.0,ICL,Boost 1.61.0,Regression,fixed,,Joachim Faulhaber