[llvm-bugs] [Bug 39458] New: _LIBCPP_DEBUG breaks heterogeneous operator<

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=39458

            Bug ID: 39458
           Summary: _LIBCPP_DEBUG breaks heterogeneous operator<
           Product: libc++
           Version: unspecified
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: All Bugs
          Assignee: unassignedclangbugs at nondot.org
          Reporter: davidben at google.com
                CC: llvm-bugs at lists.llvm.org, mclow.lists at gmail.com

I ran into this issue playing with setting _LIBCPP_DEBUG in Chromium. I think
it's a bug in libc++, but it's possible I'm reading the spec wrong. I was able
to reproduce this with libc++ trunk.

https://bugs.llvm.org/show_bug.cgi?id=17147 fixed hetergeneous comparators, but
it still doesn't quite work right when using the default operator< comparator.
Specifically, this code here:


#include <algorithm>
#include <cstdio>
#include <iterator>

struct Foo {
  explicit Foo(int x) : x_(x) {}
  bool operator<(int y) const { return x_ < y; }
  int x_;
};

int main() {
  Foo table[] = {Foo(1), Foo(2), Foo(3), Foo(4), Foo(5)};
  auto iter = std::lower_bound(std::begin(table), std::end(table), 3);
  printf("%d\n", iter->x_);
}


This builds against libc++ normally, but with -D_LIBCPP_DEBUG=0, it fails with:


In file included from blah.cc:1:
libcxx/include/algorithm:711:71: error: invalid operands to binary expression
('const int' and 'const Foo')
    bool operator()(const _T2& __x, const _T1& __y) const {return __x < __y;}
                                                                  ~~~ ^ ~~~
libcxx/include/algorithm:780:25: note: in instantiation of member function
'std::__1::__less<Foo, int>::operator()' requested here
        _LIBCPP_ASSERT(!__comp_(__l, __r),
                        ^
libcxx/include/algorithm:771:13: note: in instantiation of function template
specialization 'std::__1::__debug_less<std::__1::__less<Foo, int>
>::__do_compare_assert<int, Foo>' requested here
            __do_compare_assert(0, __y, __x);
            ^
libcxx/include/algorithm:4201:13: note: in instantiation of function template
specialization 'std::__1::__debug_less<std::__1::__less<Foo, int>
>::operator()<Foo, int>' requested here
        if (__comp(*__m, __value_))
            ^
libcxx/include/algorithm:4220:12: note: in instantiation of function template
specialization
'std::__1::__lower_bound<std::__1::__debug_less<std::__1::__less<Foo, int> > &,
Foo *, int>' requested here
    return __lower_bound<_Comp_ref>(__first, __last, __value_, __c);
           ^
libcxx/include/algorithm:4232:19: note: in instantiation of function template
specialization 'std::__1::lower_bound<Foo *, int, std::__1::__less<Foo, int> >'
requested here
    return _VSTD::lower_bound(__first, __last, __value_,
                  ^
blah.cc:13:20: note: in instantiation of function template specialization
'std::__1::lower_bound<Foo *, int>' requested here
  auto iter = std::lower_bound(std::begin(table), std::end(table), 3);
                   ^


The issue is that std::lower_bound and std::upper_bound pass __less<(iterator
type), (value type)> and __less<(value type), (iterator type)> into
_VSTD::lower_bound and _VSTD::upper_bound, respectively. That is the desired
parameter ordering, but __less actually defines all four cases of {T1,T2} <
{T1,T2}. Most won't compile in that case, but they're never instantiated, so
it's fine.

With _LIBCPP_DEBUG set, those overloads are enough to convince the
heterogeneous comparator check in __debug_less that the reverse comparator is
possible, and the generated assertion fails to compile. Thus I think
std::lower_bound and std::upper_bound only want T1 < T2 defined in __less, and
not the other orders.

However, I believe std::binary_search and std::equal_range do want both
orderings to exist, since they use both orders. The specification (I'm looking
at C++11) references the following calls for comp:

lower_bound: e < value or comp(e, value) != false  (e is an element of [first,
last))
upper_bound: !(value < e) or comp(value, e) == false
equal_range: e < value and !(value < e) or comp(e, value) and !comp(value, e)
binary_search: e < value and !(value < e) or comp(e, value) and !comp(value, e)

It also says that 25.4.3 (the above functions) are excluded from the
requirement to impose a strict weak ordering. That said, it talks about comp,
and I don't know how those requirements translate to operator<. Anyway, it does
suggest maybe there should be two versions of __less, one that defines all
orders, and one that only defines T1 < T2 for lower_bound and upper_bound. That
appears to fix the issue, playing with it locally.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20181026/5ac69dd5/attachment.html>