boostorg / boostorg/icl

An interval_set<DomainT> with std::numeric_limits<DomainT>::max() causes overflows

Open
#41 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
16
Forks
50
PR merge metrics
No merged PRs in 30d

Description

Consider https://godbolt.org/z/5xKWK9G5o

namespace icl = boost::icl;

```
int main()
{
icl::interval_set i8;
i8.insert(std::numeric_limits::max());
fmt::print("cardinality={}", cardinality(i8));
}
```
this prints `cardinality=18446744073709551361` .
The issue is the cardinality() at concept/interval.hpp which uses `last_next(object)` which overflows to 0, in this case.
With interval_set, things would be worse, since these overflows would be undefined behavior.

I suggest removing the use of `last_next` in any situation where the interval may be the biggest interval in the set.

Contributor guide

No contributing guide indexed for this repository

Research direction

Reproduce the Godbolt example first, then inspect cardinality() in concept/interval.hpp and its use of last_next(). Done means cardinality() reports the correct value for an interval_set containing max(), without overflow; also check the int case described in the issue.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
backend
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Stale
Clarity
Clearly specified
Newbie friendliness
55/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.