<html>
<head>
<base href="https://bugs.llvm.org/">
</head>
<body><table border="1" cellspacing="0" cellpadding="8">
<tr>
<th>Bug ID</th>
<td><a class="bz_bug_link
bz_status_NEW "
title="NEW - _LIBCPP_DEBUG breaks heterogeneous operator<"
href="https://bugs.llvm.org/show_bug.cgi?id=39458">39458</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>_LIBCPP_DEBUG breaks heterogeneous operator<
</td>
</tr>
<tr>
<th>Product</th>
<td>libc++
</td>
</tr>
<tr>
<th>Version</th>
<td>unspecified
</td>
</tr>
<tr>
<th>Hardware</th>
<td>PC
</td>
</tr>
<tr>
<th>OS</th>
<td>Linux
</td>
</tr>
<tr>
<th>Status</th>
<td>NEW
</td>
</tr>
<tr>
<th>Severity</th>
<td>enhancement
</td>
</tr>
<tr>
<th>Priority</th>
<td>P
</td>
</tr>
<tr>
<th>Component</th>
<td>All Bugs
</td>
</tr>
<tr>
<th>Assignee</th>
<td>unassignedclangbugs@nondot.org
</td>
</tr>
<tr>
<th>Reporter</th>
<td>davidben@google.com
</td>
</tr>
<tr>
<th>CC</th>
<td>llvm-bugs@lists.llvm.org, mclow.lists@gmail.com
</td>
</tr></table>
<p>
<div>
<pre>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.
<a class="bz_bug_link
bz_status_RESOLVED bz_closed"
title="RESOLVED FIXED - __debug_less() does not support heterogeneous comparator"
href="show_bug.cgi?id=17147">https://bugs.llvm.org/show_bug.cgi?id=17147</a> 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>
<span class="quote">>::__do_compare_assert<int, Foo>' requested here</span >
__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>
<span class="quote">>::operator()<Foo, int>' requested here</span >
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.</pre>
</div>
</p>
<hr>
<span>You are receiving this mail because:</span>
<ul>
<li>You are on the CC list for the bug.</li>
</ul>
</body>
</html>