[Boost-bugs] [Boost C++ Libraries] #6095: boost::icl::is_empty fails for certain open intervals

Subject: [Boost-bugs] [Boost C++ Libraries] #6095: boost::icl::is_empty fails for certain open intervals
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2011-11-04 14:27:08

#6095: boost::icl::is_empty fails for certain open intervals
---------------------------------------------------------------+------------
 Reporter:  Marvin Sielenkemper <m.sielenkemper@…>             |       Owner:  jofaber
     Type:  Bugs                                               |      Status:  new    
Milestone:  To Be Determined                                   |   Component:  ICL    
  Version:  Boost 1.47.0                                       |    Severity:  Problem
 Keywords:                                                     |  
---------------------------------------------------------------+------------
 While playing around with intervals over {{{int}}} with {{{INT_MAX}}} and
 {{{INT_MIN}}} bounds, I encountered some assertion failures in the
 library. After a little debugging the problem boiled down to the following
 test:

 {{{
     BOOST_AUTO_TEST_CASE(isEmptyTest)
     {
         typedef int                         Value;
         typedef boost::icl::interval<Value> Interval;
         typedef std::numeric_limits<Value>  Limits;

         Value const max(Limits::max());

         BOOST_CHECK(!is_empty(Interval::open(max - 2, max)));
         BOOST_CHECK( is_empty(Interval::open(max - 1, max)));
         BOOST_CHECK( is_empty(Interval::open(max,     max)));
     }
 }}}

 The last check fails due to an integer overflow in the implementation of
 {{{is_empty}}} where the lower bound gets incremented.

 I was able to fix this problem for {{{is_empty}}} but there are many
 places in the ICL where {{{domain_next}}} or {{{domain_prior}}} is used
 and there might be more problems lurking there.

 My motivation for these experiments was to get a properly total interval
 map, i.e. one where the iterators start at {{{INT_MIN}}} and end at
 {{{INT_MAX}}}. To get this, I 'primed' the empty map with a closed
 interval ranging over the complete domain value range. But then the
 problems started.

 So at least for me these overflow problems are not just of academical
 interest.

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