exclusive_less_than may not be compliant with C++ standard requirements for comparator

[honnesh]

Hello,

We recently updated to clang 22 and we found a potential issue with exclusive_less_than implemented in https://github.com/boostorg/icl/blob/develop/include/boost/icl/detail/exclusive_less_than.hpp. As per the C++ standard requirements for a comparator detailed in https://en.cppreference.com/w/cpp/named_req/Compare.html, exclusive_less_than violates the transitive property of equivalence highlighted here:

An example situation is the case of
a = [3 5), b = [4 7) and c = [6 8)

I believe this non-compliance is exposed with clang 22. Please let me know if I am missing something here.

[jofaber]

Dear honnesh,
Good catch :)
Your remarks are correct.

To summarize:

• The induced incomparability relation of comparator exclusive_less_than is not transitive.
• Therefore the induced incomparability relation is not an equivalence-relation
• Therefore exclusive_less_than is not a strict weak order on intervals

This means that icl's use of std:: containers are not only non-compliant with clang 22. They are non-compliant with the standard template libraries in general.

While this is kind of shocking to realize, fortunately AFAIK this does not affect the correctness of the library. More specifically I do not know of any failing test case, that is related to the above violation of comparator requirements.

The cause of this "functional resilience" is probably the tight maintainance of all containers having non-overlapping intervals.

After digging deeper into the issue I realized that this flaw has to be fixed. So I will work on the necessary changes. I am pretty optimistic this refactoring can be done without any breaking changes to the library.

[honnesh]

Here is a test case that demonstrates the difference in behavior after updating to Clang 22

static void test_upper_bound()
{
    boost::icl::interval_set<int> mp;
    mp.add(boost::icl::right_open_interval<int>(0, 2));
    mp.add(boost::icl::right_open_interval<int>(3, 5));
    mp.add(boost::icl::right_open_interval<int>(6, 9));
    mp.add(boost::icl::right_open_interval<int>(10, 12));

    auto it = mp.upper_bound(boost::icl::right_open_interval<int>(4, 7));
    assert(it != end(mp));

    // Expected: [10 12)
    std::cout << it->lower() << ' '<< it->upper() << std::endl;
}

Please add this to your internal test suite if don't have an equivalent test already.

[honnesh]

Here is an equivalent test that doesn't involve interval_set but mimics its functionality through the comparator used by interval_set

struct exclusive_less_than
{
    bool operator()(const std::pair<int, int>& lhs, const std::pair<int, int>& rhs) const
    {
        return lhs.second < rhs.first;
    }
};

static void test_upper_bound()
{
    std::set<std::pair<int, int>, exclusive_less_than> mp;
    mp.insert(std::make_pair(0, 2));
    mp.insert(std::make_pair(3, 5));
    mp.insert(std::make_pair(6, 9));
    mp.insert(std::make_pair(10, 12));

    auto it = mp.upper_bound(std::make_pair(4, 7));
    assert(it != end(mp));

    // Expected: 10 12
    std::cout << it->first << ' '<< it->second << std::endl;
}

[jofaber]

Thank you for the report and the test cases. I am working on it.

[jofaber]

I’ve investigated the reported behavior using a self-built clang-22 (from the llvm-project repository) together with the corresponding libc++ from the same source tree.

I was not able to reproduce any behavioral change compared to earlier toolchains.

In particular:

• I exercised lower_bound and upper_bound with the data provided in the issue (see test case.
• I ran the complete Boost.ICL test suite under clang-22.
• All tests pass and all observed results match the expected behavior.

While it is true that the comparator exclusive_less_than does not induce a transitive equivalence relation (and therefore is not a strict weak ordering in the abstract sense), I could not find any evidence that this non-compliance is newly “exposed” by clang-22 or newer libc++ releases.

With the current test coverage and experiments, Boost.ICL does not appear to be broken, nor does the behavior of the standard library algorithms seem to have changed in a way that affects ICL.

This is a preliminary result; if a minimal reproducer exists that demonstrates different behavior under clang-22 compared to earlier versions, I’d be happy to investigate further.

[ldionne]

@jofaber How did you rebuild your program with the latest libc++? Are you sure you did that correctly? I ended up on this GH issue while investigating the same underlying problem. I am pretty certain that the OP is correct.

This is a Godbolt showing the issue: https://godbolt.org/z/Mj6eT6Ebe

Reproducing code (slightly different from the OP's since that code didn't compile for me):

#include <boost/icl/interval_set.hpp>
#include <boost/icl/right_open_interval.hpp>
#include <iostream>

int main() {
    boost::icl::interval_set<int> mp;
    mp.add(boost::icl::discrete_interval<int>::right_open(0, 2));
    mp.add(boost::icl::discrete_interval<int>::right_open(3, 5));
    mp.add(boost::icl::discrete_interval<int>::right_open(6, 9));
    mp.add(boost::icl::discrete_interval<int>::right_open(10, 12));

    auto it = mp.upper_bound(boost::icl::discrete_interval<int>::right_open(4, 7));
    assert(it != end(mp));

    // Expected: [10 12)
    std::cout << it->lower() << ' '<< it->upper() << std::endl;
}

With Clang 21, the program outputs [10 12).
With Clang trunk (22 at the moment), the program outputs [6, 9).

[ldionne]

More exhaustive test case that checks both lower_bound and upper_bound: https://godbolt.org/z/1f595c16P

#include <boost/icl/interval_set.hpp>
#include <boost/icl/right_open_interval.hpp>
#include <cassert>

int main() {
    // upper_bound
    {
        boost::icl::interval_set<int> mp;
        mp.add(boost::icl::discrete_interval<int>::right_open(0, 2));
        mp.add(boost::icl::discrete_interval<int>::right_open(3, 5));
        mp.add(boost::icl::discrete_interval<int>::right_open(6, 9));
        mp.add(boost::icl::discrete_interval<int>::right_open(10, 12));

        auto it = mp.upper_bound(boost::icl::discrete_interval<int>::right_open(4, 7));
        assert(it != end(mp));
        assert(it->lower() == 10);
        assert(it->upper() == 12);
    }

    // lower_bound
    {
        boost::icl::interval_set<int> mp;
        mp.add(boost::icl::discrete_interval<int>::right_open(0, 2));
        mp.add(boost::icl::discrete_interval<int>::right_open(3, 5));
        mp.add(boost::icl::discrete_interval<int>::right_open(6, 9));
        mp.add(boost::icl::discrete_interval<int>::right_open(10, 12));

        auto it = mp.lower_bound(boost::icl::discrete_interval<int>::right_open(1, 4));
        assert(it != end(mp));
        assert(it->lower() == 0);
        assert(it->upper() == 2);
    }
}

[ldionne]

Gentle ping -- as far as I understand, this bug makes Boost.ICL's interval containers fundamentally based on UB, which is pretty serious.