split_interval_set incorrect works compiled with clang

[Nickolay Arrtamonov <nickolay.artamonov@…>]

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 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

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)