Modify

Ticket #6095 (closed Bugs: fixed)

Opened 2 years ago

Last modified 2 years ago

boost::icl::is_empty fails for certain open intervals

Reported by: Marvin Sielenkemper <m.sielenkemper@…> Owned by: jofaber
Milestone: Boost 1.48.0 Component: ICL
Version: Boost 1.47.0 Severity: Problem
Keywords: icl, open interval, integer overflow Cc:

Description

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.

Attachments

interval.hpp.diff Download (1.1 KB) - added by Marvin Sielenkemper <m.sielenkemper@…> 2 years ago.
patch to check for overflow in is_empty
interval.hpp.2.diff Download (1.1 KB) - added by Marvin Sielenkemper <m.sielenkemper@…> 2 years ago.
b <= a || b <= a + 1 fix

Change History

Changed 2 years ago by Marvin Sielenkemper <m.sielenkemper@…>

patch to check for overflow in is_empty

comment:1 Changed 2 years ago by jofaber

Hi Marvin,

thank you for your report and the attached patch. I agree that the behavior of icl::intervals at open borders and for limited domain types is kind of nasty. Nevertheless after examining your information I am not convinced that we can speak of a bug here and that a code change is needed.

In your test case you propose that

  BOOST_CHECK( is_empty(Interval::open(max, max)));

is supposed to succeed. But an open interval Interval::open(max, x) has an open lower bound of max, which means that values of its domain_type do not exist that can be elements of the interval. My interpretation of intervals of this kind is that they are ill formed rather than empty. So the user has to take care via program logic that these types of intervals are not constructed in the same way she has to take care that ++i is not called if i == numeric_limits<int>::max() already.

Best regards, Joachim

comment:2 Changed 2 years ago by Marvin Sielenkemper <m.sielenkemper@…>

Hi Joachim,

as a mathematician I have to disagree: what distinguishes the interval Interval::open(max, max) from Interval::open(0, 0)? For both there exist no elements, that is the point of being empty. Even intervals like Interval::closed(17, 4) are allowed and deemed empty!

As a programmer I might be able to accept the responsibility to avoid such cases, but only if I were able to do so. I encountered the problem not while putting open intervals into the container but closed ones. And for those borders like min and max certainly make sense.

What I was trying to do was

    BOOST_AUTO_TEST_CASE(totalRangeTest)
    {
        typedef int                                                              Value;
        typedef boost::icl::interval<Value>                                      Interval;
        typedef std::numeric_limits<Value>                                       Limits;
        typedef boost::icl::interval_map<Value, int, boost::icl::total_enricher> Container;

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

        boost::icl::interval_map<Value, int, boost::icl::total_enricher> intervals;

        intervals += std::make_pair(Interval::closed(min, max), 0);
        intervals += std::make_pair(Interval::right_open(0, 10),  3);

        BOOST_CHECK_EQUAL(intervals.iterative_size(), 3);
   }

and this fails BOOST_ASSERT(this->_map.find(inter_val) == this->_map.end()); in interval_base_map.hpp, line 530 while trying to calculate the new third element of the container (Interval::closed(10, max)) when inserting the second interval.

Drilling down on that, I found is_empty and its problematic behaviour.

Thank you for your response!

Best regards,
Marvin

comment:3 Changed 2 years ago by jofaber

  • Keywords icl, open interval, integer overflow added
  • Status changed from new to assigned
  • Milestone changed from To Be Determined to Boost 1.48.0

Hi Marvin,

I hope you forgive me my temporal {arrog|ignor}ance ;) Your use case shows, that the user can hardly avoid hitting the overflow trap of open intervals that are computed internally in the library in your test case. Also your fix is a nifty one. So thanks again for the report. I will apply your fix and put you on the credits list :) Send in more use cases if you find more bugs related to the [min,max]-preinitialized usage.

Cheers,
Joachim

comment:4 Changed 2 years ago by Marvin Sielenkemper <m.sielenkemper@…>

Hi Joachim,

no problem :)

But I would like to propose a maybe even more nifty fix:
An open interval ]a, b[ is empty if b <= a || b <= a + 1.

This does not only avoid the second increment, it even avoids the first one in many cases due to the short circuit ||-operator and does never run into the overflow case:
If the first check fails, we know that a < b and hence that there is at least one element to increment to without overflowing.

So this should even work for bound types that are less forgiving than int when hitting their bounds, (e.g. throw exceptions).

Best regards,
Marvin

Changed 2 years ago by Marvin Sielenkemper <m.sielenkemper@…>

b <= a
b <= a + 1 fix

comment:5 Changed 2 years ago by jofaber

Hi Marvin,

yes, this is nice and simple. I changed the code accordingly.

Thanx again,
Joachim

comment:6 Changed 2 years ago by anonymous

  • Status changed from assigned to closed
  • Resolution set to fixed

comment:7 Changed 2 years ago by anonymous

  • Type changed from Bugs to Patches
  • Component changed from ICL to Building Boost

comment:8 Changed 2 years ago by jofaber

  • Type changed from Patches to Bugs
  • Component changed from Building Boost to ICL
View

Add a comment

Modify Ticket

Change Properties
<Author field>
Action
as closed
The resolution will be deleted. Next status will be 'reopened'
Author


E-mail address and user name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.