| //===----------------------------------------------------------------------===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| |
| // UNSUPPORTED: no-exceptions |
| |
| // <algorithm> |
| |
| // template <class _Compare> struct __debug_less |
| |
| // __debug_less checks that a comparator actually provides a strict-weak ordering. |
| |
| struct DebugException {}; |
| |
| #define _LIBCPP_DEBUG 0 |
| #define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : throw ::DebugException()) |
| |
| #include <algorithm> |
| #include <iterator> |
| #include <cassert> |
| |
| #include "test_macros.h" |
| |
| template <int ID> |
| struct MyType { |
| int value; |
| explicit MyType(int xvalue = 0) : value(xvalue) {} |
| }; |
| |
| template <int ID1, int ID2> |
| bool operator<(MyType<ID1> const& LHS, MyType<ID2> const& RHS) { |
| return LHS.value < RHS.value; |
| } |
| |
| struct CompareBase { |
| static int called; |
| static void reset() { |
| called = 0; |
| } |
| }; |
| |
| int CompareBase::called = 0; |
| |
| template <class ValueType> |
| struct GoodComparator : public CompareBase { |
| bool operator()(ValueType const& lhs, ValueType const& rhs) const { |
| ++CompareBase::called; |
| return lhs < rhs; |
| } |
| }; |
| |
| template <class ValueType> |
| struct BadComparator : public CompareBase { |
| bool operator()(ValueType const&, ValueType const&) const { |
| ++CompareBase::called; |
| return true; |
| } |
| }; |
| |
| template <class T1, class T2> |
| struct TwoWayHomoComparator : public CompareBase { |
| bool operator()(T1 const& lhs, T2 const& rhs) const { |
| ++CompareBase::called; |
| return lhs < rhs; |
| } |
| |
| bool operator()(T2 const& lhs, T1 const& rhs) const { |
| ++CompareBase::called; |
| return lhs < rhs; |
| } |
| }; |
| |
| template <class T1, class T2> |
| struct OneWayHomoComparator : public CompareBase { |
| bool operator()(T1 const& lhs, T2 const& rhs) const { |
| ++CompareBase::called; |
| return lhs < rhs; |
| } |
| }; |
| |
| using std::__debug_less; |
| |
| typedef MyType<0> MT0; |
| typedef MyType<1> MT1; |
| |
| void test_passing() { |
| int& called = CompareBase::called; |
| called = 0; |
| MT0 one(1); |
| MT0 two(2); |
| MT1 three(3); |
| MT1 four(4); |
| |
| { |
| typedef GoodComparator<MT0> C; |
| typedef __debug_less<C> D; |
| |
| C c; |
| D d(c); |
| |
| assert(d(one, two) == true); |
| assert(called == 2); |
| called = 0; |
| |
| assert(d(one, one) == false); |
| assert(called == 1); |
| called = 0; |
| |
| assert(d(two, one) == false); |
| assert(called == 1); |
| called = 0; |
| } |
| { |
| typedef TwoWayHomoComparator<MT0, MT1> C; |
| typedef __debug_less<C> D; |
| C c; |
| D d(c); |
| |
| assert(d(one, three) == true); |
| assert(called == 2); |
| called = 0; |
| |
| assert(d(three, one) == false); |
| assert(called == 1); |
| called = 0; |
| } |
| { |
| typedef OneWayHomoComparator<MT0, MT1> C; |
| typedef __debug_less<C> D; |
| C c; |
| D d(c); |
| |
| assert(d(one, three) == true); |
| assert(called == 1); |
| called = 0; |
| } |
| } |
| |
| void test_failing() { |
| int& called = CompareBase::called; |
| called = 0; |
| MT0 one(1); |
| MT0 two(2); |
| |
| { |
| typedef BadComparator<MT0> C; |
| typedef __debug_less<C> D; |
| C c; |
| D d(c); |
| |
| try { |
| d(one, two); |
| assert(false); |
| } catch (DebugException const&) { |
| } |
| |
| assert(called == 2); |
| called = 0; |
| } |
| } |
| |
| template <int> |
| struct Tag { |
| explicit Tag(int v) : value(v) {} |
| int value; |
| }; |
| |
| template <class = void> |
| struct FooImp { |
| explicit FooImp(int x) : x_(x) {} |
| int x_; |
| }; |
| |
| template <class T> |
| inline bool operator<(FooImp<T> const& x, Tag<0> y) { |
| return x.x_ < y.value; |
| } |
| |
| template <class T> |
| inline bool operator<(Tag<0>, FooImp<T> const&) { |
| static_assert(sizeof(FooImp<T>) != sizeof(FooImp<T>), "should not be instantiated"); |
| return false; |
| } |
| |
| template <class T> |
| inline bool operator<(Tag<1> x, FooImp<T> const& y) { |
| return x.value < y.x_; |
| } |
| |
| template <class T> |
| inline bool operator<(FooImp<T> const&, Tag<1>) { |
| static_assert(sizeof(FooImp<T>) != sizeof(FooImp<T>), "should not be instantiated"); |
| return false; |
| } |
| |
| typedef FooImp<> Foo; |
| |
| // Test that we don't attempt to call the comparator with the arguments reversed |
| // for upper_bound and lower_bound since the comparator or type is not required |
| // to support it, nor does it require the range to have a strict weak ordering. |
| // See llvm.org/PR39458 |
| void test_upper_and_lower_bound() { |
| Foo table[] = {Foo(1), Foo(2), Foo(3), Foo(4), Foo(5)}; |
| { |
| Foo* iter = std::lower_bound(std::begin(table), std::end(table), Tag<0>(3)); |
| assert(iter == (table + 2)); |
| } |
| { |
| Foo* iter = std::upper_bound(std::begin(table), std::end(table), Tag<1>(3)); |
| assert(iter == (table + 3)); |
| } |
| } |
| |
| struct NonConstArgCmp { |
| bool operator()(int& x, int &y) const { |
| return x < y; |
| } |
| }; |
| |
| void test_non_const_arg_cmp() { |
| { |
| NonConstArgCmp cmp; |
| __debug_less<NonConstArgCmp> dcmp(cmp); |
| int x = 0, y = 1; |
| assert(dcmp(x, y)); |
| assert(!dcmp(y, x)); |
| } |
| { |
| NonConstArgCmp cmp; |
| int arr[] = {5, 4, 3, 2, 1}; |
| std::sort(std::begin(arr), std::end(arr), cmp); |
| assert(std::is_sorted(std::begin(arr), std::end(arr))); |
| } |
| } |
| |
| struct ValueIterator { |
| typedef std::input_iterator_tag iterator_category; |
| typedef size_t value_type; |
| typedef ptrdiff_t difference_type; |
| typedef size_t reference; |
| typedef size_t* pointer; |
| |
| ValueIterator() { } |
| |
| reference operator*() { return 0; } |
| ValueIterator& operator++() { return *this; } |
| |
| friend bool operator==(ValueIterator, ValueIterator) { return true; } |
| friend bool operator!=(ValueIterator, ValueIterator) { return false; } |
| }; |
| |
| void test_value_iterator() { |
| // Ensure no build failures when iterators return values, not references. |
| assert(0 == std::lexicographical_compare(ValueIterator(), ValueIterator(), |
| ValueIterator(), ValueIterator())); |
| } |
| |
| void test_value_categories() { |
| std::less<int> l; |
| std::__debug_less<std::less<int> > dl(l); |
| int lvalue = 42; |
| const int const_lvalue = 101; |
| |
| assert(dl(lvalue, const_lvalue)); |
| assert(dl(/*rvalue*/1, lvalue)); |
| assert(dl(static_cast<int&&>(1), static_cast<const int&&>(2))); |
| } |
| |
| #if TEST_STD_VER > 17 |
| constexpr bool test_constexpr() { |
| std::less<> cmp{}; |
| __debug_less<std::less<> > dcmp(cmp); |
| assert(dcmp(1, 2)); |
| assert(!dcmp(1, 1)); |
| return true; |
| } |
| #endif |
| |
| int main(int, char**) { |
| test_passing(); |
| test_failing(); |
| test_upper_and_lower_bound(); |
| test_non_const_arg_cmp(); |
| test_value_iterator(); |
| test_value_categories(); |
| #if TEST_STD_VER > 17 |
| static_assert(test_constexpr(), ""); |
| #endif |
| return 0; |
| } |