[libc++] [LIBCXX-DEBUG-FIXME] Our `__debug_less` breaks some complexity guarantees.
`__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.
Differential Revision: https://reviews.llvm.org/D101677
GitOrigin-RevId: 165ad89947e8ef6c08c80eb067d85b4fa9074904
diff --git a/docs/DesignDocs/DebugMode.rst b/docs/DesignDocs/DebugMode.rst
index e4d4e5b..c78c0ae 100644
--- a/docs/DesignDocs/DebugMode.rst
+++ b/docs/DesignDocs/DebugMode.rst
@@ -70,6 +70,12 @@
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
diff --git a/test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp b/test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp
index 7f69a2d..1711568 100644
--- a/test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp
+++ b/test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp
@@ -6,8 +6,6 @@
//
//===----------------------------------------------------------------------===//
-// XFAIL: LIBCXX-DEBUG-FIXME
-
// <algorithm>
// template<BidirectionalIterator Iter, StrictWeakOrder<auto, Iter::value_type> Compare>
@@ -81,7 +79,9 @@
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;
}
