From 165ad89947e8ef6c08c80eb067d85b4fa9074904 Mon Sep 17 00:00:00 2001 From: Arthur O'Dwyer Date: Tue, 20 Apr 2021 18:21:59 -0400 Subject: [PATCH] [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 --- libcxx/docs/DesignDocs/DebugMode.rst | 6 ++++++ .../algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp | 4 ++-- 2 files changed, 8 insertions(+), 2 deletions(-) diff --git a/libcxx/docs/DesignDocs/DebugMode.rst b/libcxx/docs/DesignDocs/DebugMode.rst index e4d4e5b..c78c0ae 100644 --- a/libcxx/docs/DesignDocs/DebugMode.rst +++ b/libcxx/docs/DesignDocs/DebugMode.rst @@ -70,6 +70,12 @@ 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 diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp index 7f69a2d..1711568 100644 --- a/libcxx/test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp +++ b/libcxx/test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp @@ -6,8 +6,6 @@ // //===----------------------------------------------------------------------===// -// XFAIL: LIBCXX-DEBUG-FIXME - // // template Compare> @@ -81,7 +79,9 @@ test_one(unsigned N, unsigned M) assert(ia[0] == static_cast(N)-1); assert(ia[N-1] == 0); assert(std::is_sorted(ia, ia+N, std::greater())); +#ifndef _LIBCPP_DEBUG assert(pred.count() <= (N-1)); +#endif } delete [] ia; } -- 2.7.4