Issue when compiling with -D_GLIBCXX_DEBUG

[paulromano]

If I compile xtensor with `-DCMAKE_CXX_FLAGS="-D_GLIBCXX_DEBUG" (macro described here) and try to run tests, some of them abort as such:

$ ./test_xarray
Running main() from .../xtensor/build/test/googletest-src/googletest/src/gtest_main.cc
[==========] Running 32 tests from 1 test suite.
[----------] Global test environment set-up.
[----------] 32 tests from xarray
[ RUN      ] xarray.shaped_constructor
[       OK ] xarray.shaped_constructor (0 ms)
[ RUN      ] xarray.strided_constructor
[       OK ] xarray.strided_constructor (0 ms)
[ RUN      ] xarray.valued_constructor
[       OK ] xarray.valued_constructor (0 ms)
[ RUN      ] xarray.strided_valued_constructor
[       OK ] xarray.strided_valued_constructor (0 ms)
[ RUN      ] xarray.xscalar_constructor
[       OK ] xarray.xscalar_constructor (0 ms)
[ RUN      ] xarray.copy_semantic
[       OK ] xarray.copy_semantic (0 ms)
[ RUN      ] xarray.move_semantic
[       OK ] xarray.move_semantic (0 ms)
[ RUN      ] xarray.resize
[       OK ] xarray.resize (0 ms)
[ RUN      ] xarray.reshape
[       OK ] xarray.reshape (0 ms)
[ RUN      ] xarray.transpose
[       OK ] xarray.transpose (0 ms)
[ RUN      ] xarray.transpose_row
[       OK ] xarray.transpose_row (0 ms)
[ RUN      ] xarray.access
[       OK ] xarray.access (0 ms)
[ RUN      ] xarray.unchecked
[       OK ] xarray.unchecked (0 ms)
[ RUN      ] xarray.at
[       OK ] xarray.at (1 ms)
[ RUN      ] xarray.element
[       OK ] xarray.element (0 ms)
[ RUN      ] xarray.indexed_access
[       OK ] xarray.indexed_access (0 ms)
[ RUN      ] xarray.broadcast_shape
[       OK ] xarray.broadcast_shape (0 ms)
[ RUN      ] xarray.iterator
[       OK ] xarray.iterator (0 ms)
[ RUN      ] xarray.fill
[       OK ] xarray.fill (0 ms)
[ RUN      ] xarray.initializer_list
[       OK ] xarray.initializer_list (0 ms)
[ RUN      ] xarray.zerod
/usr/include/c++/9/bits/stl_algo.h:3279:
In function:
    _FIter std::is_sorted_until(_FIter, _FIter, _Compare) [with _FIter = 
    const long unsigned int*; _Compare = std::less_equal<void>]

Error: comparison doesn't meet irreflexive requirements, assert(!(a < a)).

Objects involved in the operation:
    instance "functor" @ 0x0x7fffb67bbe4f {
      type = std::less_equal<void>;
    }
    iterator::value_type "ordered type" {
      type = unsigned long;
    }
Aborted (core dumped)

For reference, I'm on Ubuntu 20.04 with gcc 9.3.0.

I'm not sure if this is a bug or what. I discovered this via a user of OpenMC (which relies on xtensor), who reported this behavior.

[samuel-emrys]

This is a problem with the usage of std::less_equal<>() as a Compare function when used with std::is_sorted - xreducer.hpp::299, xreducer.hpp::1308.

The comment provided with each of these lines is as follows:

// using std::less_equal is counter-intuitive, but as the standard says (24.4.5):
// A sequence is sorted with respect to a comparator comp if for any iterator i pointing to the sequence and any non-negative integer n
// such that i + n is a valid iterator pointing to an element of the sequence, comp(*(i + n), *i) == false.
// Therefore less_equal is required to detect duplicates.

The following minimum working example (godbolt) replicates this issue when compiled with -D_GLIBCXX_DEBUG and shows the above justification to be incorrect:

#include <vector>
#include <functional>

auto main() -> int {
    std::vector<int> v{1, 5, 9, 3, 2, 9, 7};
    std::is_sorted(v.begin(), v.end(), std::less_equal<>());
    return EXIT_SUCCESS;
}

The provided excerpt is from cppreference, and correctly states the requirement for the Compare function. However, it is misinterpreted to require using the <= binary predicate as the Compare function. When comparing elements in the sequence, one offset value will be n==0, and when the Compare function is the binary predicate <=, comp(*(i + n), *i) == comp(*i , *i) == true, which is a violation of the requirement of the Compare function as comp(*(i+n), *i) != false for all possible values of n.

More specifically, the Compare function is required to implement strict weak ordering. In fact, the C++ working draft section on [alg.sorting] suggests sorting algorithms require an object that implements operator<.

I believe that changing std::less_equal<>() to std::less<>() would resolve this issue. Evidence of this fix is here: https://godbolt.org/z/6f3sKchcz