[libc++] [LIBCXX-DEBUG-FIXME] Our `__debug_less` breaks some complexity guarantees.

[• Quuxplusone]

Summary

`__debug_less` ends up running the comparator up-to-twice per comparison,
because whenever `(x < y)` it goes on to verify that `!(y < x)`.
This breaks the strict "Complexity" guarantees of algorithms like
`inplace_merge`, which we test in the test suite. So, just skip the
complexity assertions in debug mode.

[• Quuxplusone]

poke buildkite

[ldionne]

LGTM, but please add a note in libcxx/docs/DesignDocs/DebugMode.rst that we don't necessarily respect complexity guarantees under the debug mode, which isn't obvious (but it makes sense when you think about it).

libcxx/docs/DesignDocs/DebugMode.rst

 
 Basic Checks
 ============
 
 These checks are enabled when ``_LIBCPP_DEBUG`` is defined to either 0 or 1.
 
 The following checks are enabled by ``_LIBCPP_DEBUG``:
 
+  * Many algorithms, such as ``binary_search``, ``merge``, ``next_permutation``, and ``sort``,
+    wrap the user-provided comparator to assert that `!comp(y, x)` whenever
+    `comp(x, y)`. This can cause the user-provided comparator to be evaluated
+    up to twice as many times as it would be without ``_LIBCPP_DEBUG``, and
+    causes the library to violate some of the Standard's complexity clauses.
+
   * FIXME: Update this list
 
 Iterator Debugging Checks
 =========================
 
 These checks are enabled when ``_LIBCPP_DEBUG`` is defined to 1.
 
 The following containers and STL classes support iterator debugging:

libcxx/test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
-// XFAIL: LIBCXX-DEBUG-FIXME
-
 // <algorithm>
 
 // template<BidirectionalIterator Iter, StrictWeakOrder<auto, Iter::value_type> Compare>
 //   requires ShuffleIterator<Iter>
 //         && CopyConstructible<Compare>
 //   void
 //   inplace_merge(Iter first, Iter middle, Iter last, Compare comp);
 
test_one(unsigned N, unsigned M)
     std::sort(ia+M, ia+N, std::greater<value_type>());
     binary_counting_predicate<std::greater<value_type>, value_type, value_type> pred((std::greater<value_type>()));
     std::inplace_merge(Iter(ia), Iter(ia+M), Iter(ia+N), std::ref(pred));
     if(N > 0)
     {
         assert(ia[0] == static_cast<int>(N)-1);
         assert(ia[N-1] == 0);
         assert(std::is_sorted(ia, ia+N, std::greater<value_type>()));
+#ifndef _LIBCPP_DEBUG
         assert(pred.count() <= (N-1));
+#endif
     }
     delete [] ia;
 }
 
 template <class Iter>
 void
 test(unsigned N)
 {