[Bug libstdc++/71545] New: Incorrect irreflexive comparison debug check in std::lower_bound

["daniel.grunwald at gmail dot com" <gcc-bugzilla at gcc dot gnu dot org>]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71545

            Bug ID: 71545
           Summary: Incorrect irreflexive comparison debug check in
                    std::lower_bound
           Product: gcc
           Version: 6.1.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: daniel.grunwald at gmail dot com
  Target Milestone: ---

Compile the following with `g++-6 -D_GLIBCXX_DEBUG` and run the resulting
program:

#include <algorithm>
#include <vector>
#include <cassert>
#include <iostream>

constexpr int TABLE_SIZE = 1;
typedef int TableEntryNumber;
int table[TABLE_SIZE] = {
    33
};

int main() {
    std::vector<int> v = { 0, 10, 20, 30, 40, 50 };
    // Find the first entry greater or equal to table[0]:
    auto it = std::lower_bound(
        v.begin(), v.end(), 0,
        [] (int val, TableEntryNumber tableIndex)
        {
            assert(tableIndex < TABLE_SIZE);
            return val < table[tableIndex];
        });
    std::cout << *it << std::endl; // 40
}

Running this program results in:
  /usr/include/c++/6/bits/stl_algo.h:2029:
  Error: comparison doesn't meet irreflexive requirements, assert(!(a < a)).
  [...] Aborted

I think this is a false positive, and would expect the program to print the
result "40" instead.

In my reading of the standard, the binary search algorithms do not require comp
to induce a strict weak ordering on the sequence, but merely require the
sequence to be partitioned with respect to `comp(..., value)`.

Thus, these function should not perform the requires_irreflexive_pred debug
check.

Workaround:
  I can make TableEntryNumber a struct containing an integer, as the debug
check is skipped if the two comparator arguments are incompatible types.