Boost ICL, cardinality of an interval set

Question

In Boost ICL, when I call cardinality() or size() functions on an interval set, the return type is size_t, independent of the type of interval. On 32-bit machines this is a 32-bit unsigned integer. If my intervals, however, are of type int64_t, the cardinality can easily overflow the 32-bit integer. Am I missing something obvious here or is this a serious flaw of this library?

EDIT: example added

The following code compiles and runs without error on 64-bit but not on 32-bit machines, where it throws the assertion.

#include <boost/icl/interval_set.hpp>

int main()
{
    boost::icl::interval_set<int64_t> is;
    is.add(boost::icl::interval<int64_t>::closed(1, 4294967297LL));
    assert(boost::icl::cardinality(is) == 4294967297LL);
}

EDIT: I'm using boost::icl version 1.49.0 on Ubuntu 13.10

EDIT:

This is not particularly a 32/64-bit problem, as the following code wouldn't work on 64-bit either

#include <boost/icl/interval_set.hpp>
int main()
{
    boost::icl::interval_set<double> is;
    is.add(boost::icl::interval<double>::closed(1, 1.5));
    assert(boost::icl::cardinality(is) == 0.5);
}

sehe · Accepted Answer · 2014-12-01T10:07:47.237

2

Reproduced with Boost 1_54 on Ubuntu 14.04.1 LTS

This indeed seems to be a bug. The specialization to fix is

template <class Type> 
struct get_size_type<Type, false, false, false>
{ 
    typedef std::size_t type; 
};

In icl/type_traits/size_type_of.hpp. Somehow the ICL devs appear not to be testing with -m32 these days.

I've had success replacing it by

// BEGIN SEHE WAS HERE
template <class Type> 
struct get_size_type<Type, std::enable_if<not boost::is_arithmetic<Type>::value, mpl::false_>::type::value, false, false>
{ 
    typedef std::size_t type; 
};

template <class Type> 
struct get_size_type<Type, std::enable_if<boost::is_arithmetic<Type>::value, mpl::false_>::type::value, false, false>
{ 
    typedef typename std::common_type<Type, std::size_t>::type type; 
};
// END SEHE WAS HERE

The trait is sadly not very SFINAE friendly, hence the hack to use the first bool template argument for SFINAE. Improvements could be:

use boost type traits only
use integral value deduction from Boost Integer as opposed to common_type<...> for integral types

I've tested this to DoTheRightThing(TM) for interval_set<double> as well as interval_set<uint64_t> on g++ -m32 and -m64.

I'd report this on the mailing list.

edited Dec 01 '14 at 10:07

answered Dec 01 '14 at 09:46

sehe

374,641
47
450
633

Good work. I've found that get `get_size_type` is not particularly SFINAE friendly but if you want to add my Proof-Of-Concept patch as "ideas" to the issue, you're welcome. – sehe Dec 01 '14 at 09:53
Btw, this is not particularly a 32-bit/64-bit problem, because you get same problems if your interval type is double, even on a 64-bit machine. On the one hand because of the overflow (double range is larger than 64-bit integer range), on the other hand because cardinality can be a floating point number in this case. They just have to use the same type for the cardinality as contained in the intervals. – Konstantin Dec 01 '14 at 09:57
@Konstantin don't forget you can have intervals of UDT (non-integral or non-arithmetic) types though. It's best to leave this decision to the library designers. Meanwhile, I've updated my post :) – sehe Dec 01 '14 at 09:58
Well, but I can have boost::icl::interval_set is, can't I? Or is interval_set explicitely there for integer data types? – Konstantin Dec 01 '14 at 10:00
@Konstantin What are you complaining to me for? I never said differently. (I just meant that _`They just have to use the same type for the cardinality as contained in the intervals`_ is probably inaccurate). Also, my updated answer works with `double` as well. – sehe Dec 01 '14 at 10:04
2

Sorry, you're right! This shouldn't have sounded as a complaint :) I guess I was just embarrassed to find this thing in a code I was using for almost a year. Now I have to redo my computations. If you cannot rely on boost, what can you rely upon!? :) – Konstantin Dec 01 '14 at 10:10
Ow. That's gotta hurt yes. I feel for you. I can only say: don't trust a library... trust tests and use warnings :( (`-Wextra -pedantic -Wall`, and for this purpose perhaps `-Wconversion`). This indeed is a powerful lesson. I'm glad I'm just on the sideline assimilating all this. Good luck with the damage control! – sehe Dec 01 '14 at 10:14

Boost ICL, cardinality of an interval set

1 Answers1