Classify leaves with operator<=> itself past the nesting bound

In C++20, an ordered comparison past the nesting bound classified a pair of
leaves by asking == first and then order_leaves(), which calls < and > -
both derived from <=>. For a pair of binary values with the same bytes but a
different subtype, == reports them unequal, while <=> (through
std::vector<std::uint8_t>::operator<=>) reports them equivalent, so the pair
ended the comparison as unordered instead of letting the next element
decide - unlike an array or object within the bound, which compares such a
pair with its own operator<=> and gets equivalent. So operator<=>, and the
<, <=, >, >= derived from it, could give a different result for the same two
values depending on how deeply the values were nested, or unordered at every
depth with JSON_NO_THREAD_LOCAL defined.

compare_leaves() now classifies such a pair in C++20 with operator<=> itself
instead, matching how a value within the bound is compared; the equality-only
and pre-C++20 ordered cases are unchanged. Which of the three runs is chosen
by overloading on std::integral_constant<bool, Ordered>, the same tag
dispatch order_leaves() already uses, rather than a runtime "if (Ordered)" on
a template parameter, which MSVC would flag as a constant condition (C4127).

Added a regression test to unit-comparison.cpp that nests such a pair 0, 127,
128 and 200 levels deep (127 stays within the 128-level bound, 128 and 200
do not) and checks that operator<=> and operator< agree at every depth.

Fixes #5654.

Signed-off-by: Niels Lohmann <mail@nlohmann.me>

docs/mkdocs/docs/api/basic_json/operator_spaceship.md

@@ -96,5 +96,8 @@ Linear.
 
 ## Version history
 
-1. Added in version 3.11.0.
+1. Added in version 3.11.0. Fixed in version 3.13.0 to keep the result independent of nesting depth: before, a pair
+   of binary values with the same bytes but a different subtype - unequal by `operator==`, yet equivalent by
+   `operator<=>` - could end an ordered comparison as `unordered` only past 128 levels of nesting, or at every depth
+   with [`JSON_NO_THREAD_LOCAL`](../macros/json_no_thread_local.md) defined.
 2. Added in version 3.11.0.

include/nlohmann/json.hpp

@@ -1307,15 +1307,65 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     */
     template<bool Ordered>
     static compare_result compare_leaves(const_reference lhs, const_reference rhs) noexcept
+    {
+        return compare_leaves(lhs, rhs, std::integral_constant<bool, Ordered> {});
+    }
+
+    /// @brief compare two leaves that are only being checked for equality
+    static compare_result compare_leaves(const_reference lhs, const_reference rhs, std::false_type /*ordered*/) noexcept
     {
         if (lhs == rhs)
         {
             return compare_result::equal;
         }
 
-        return order_leaves(lhs, rhs, std::integral_constant<bool, Ordered> {});
+        return order_leaves(lhs, rhs, std::false_type {});
     }
 
+#if JSON_HAS_THREE_WAY_COMPARISON
+    /*!
+    @brief compare two leaves that are being ordered, for operator<=>
+
+    Reached only from operator<=>, so the leaves must be classified exactly
+    as operator<=> classifies them - which is not the same as asking
+    == and then order_leaves(), the way the other overload does it. The two
+    disagree on a binary value: == also compares the subtype, but <=> compares
+    only the bytes, through std::vector<std::uint8_t>::operator<=>. Using <=>
+    itself here keeps a leaf pair classified the same way regardless of how
+    deep it is nested - == first would again call operator<=> a level down
+    through order_leaves(), but call it after a mismatching == already ended
+    the comparison for a pair that <=> alone would still call equivalent.
+    */
+    static compare_result compare_leaves(const_reference lhs, const_reference rhs, std::true_type /*ordered*/) noexcept
+    {
+        const std::partial_ordering order = lhs <=> rhs; // *NOPAD*
+        if (order == 0)
+        {
+            return compare_result::equal;
+        }
+        if (order < 0)
+        {
+            return compare_result::less;
+        }
+        if (order > 0)
+        {
+            return compare_result::greater;
+        }
+        return compare_result::unordered;
+    }
+#else
+    /// @brief compare two leaves that are being ordered, for operator<
+    static compare_result compare_leaves(const_reference lhs, const_reference rhs, std::true_type /*ordered*/) noexcept
+    {
+        if (lhs == rhs)
+        {
+            return compare_result::equal;
+        }
+
+        return order_leaves(lhs, rhs, std::true_type {});
+    }
+#endif
+
     /*!
     @brief compare two object keys
 

single_include/nlohmann/json.hpp

@@ -27388,15 +27388,65 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     */
     template<bool Ordered>
     static compare_result compare_leaves(const_reference lhs, const_reference rhs) noexcept
+    {
+        return compare_leaves(lhs, rhs, std::integral_constant<bool, Ordered> {});
+    }
+
+    /// @brief compare two leaves that are only being checked for equality
+    static compare_result compare_leaves(const_reference lhs, const_reference rhs, std::false_type /*ordered*/) noexcept
     {
         if (lhs == rhs)
         {
             return compare_result::equal;
         }
 
-        return order_leaves(lhs, rhs, std::integral_constant<bool, Ordered> {});
+        return order_leaves(lhs, rhs, std::false_type {});
     }
 
+#if JSON_HAS_THREE_WAY_COMPARISON
+    /*!
+    @brief compare two leaves that are being ordered, for operator<=>
+
+    Reached only from operator<=>, so the leaves must be classified exactly
+    as operator<=> classifies them - which is not the same as asking
+    == and then order_leaves(), the way the other overload does it. The two
+    disagree on a binary value: == also compares the subtype, but <=> compares
+    only the bytes, through std::vector<std::uint8_t>::operator<=>. Using <=>
+    itself here keeps a leaf pair classified the same way regardless of how
+    deep it is nested - == first would again call operator<=> a level down
+    through order_leaves(), but call it after a mismatching == already ended
+    the comparison for a pair that <=> alone would still call equivalent.
+    */
+    static compare_result compare_leaves(const_reference lhs, const_reference rhs, std::true_type /*ordered*/) noexcept
+    {
+        const std::partial_ordering order = lhs <=> rhs; // *NOPAD*
+        if (order == 0)
+        {
+            return compare_result::equal;
+        }
+        if (order < 0)
+        {
+            return compare_result::less;
+        }
+        if (order > 0)
+        {
+            return compare_result::greater;
+        }
+        return compare_result::unordered;
+    }
+#else
+    /// @brief compare two leaves that are being ordered, for operator<
+    static compare_result compare_leaves(const_reference lhs, const_reference rhs, std::true_type /*ordered*/) noexcept
+    {
+        if (lhs == rhs)
+        {
+            return compare_result::equal;
+        }
+
+        return order_leaves(lhs, rhs, std::true_type {});
+    }
+#endif
+
     /*!
     @brief compare two object keys
 

tests/src/unit-comparison.cpp

@@ -952,3 +952,51 @@ TEST_CASE("containers are compared element by element")
         }
     }
 }
+
+#if JSON_HAS_THREE_WAY_COMPARISON
+// JSON_HAS_CPP_20 (do not remove; see note at top of file)
+TEST_CASE("operator<=> of binary values with a different subtype does not depend on nesting depth")
+{
+    // #5654: std::vector<std::uint8_t>::operator<=>, which the binary type's
+    // own operator<=> uses, ignores the subtype that operator== checks. So a
+    // pair of binary values with the same bytes but a different subtype is
+    // unequal, yet <=>-equivalent - the same inconsistency between == and <=>
+    // that a NaN has. Within the nesting bound, an array compares itself
+    // with std::vector's own operator<=>, which treats an equivalent pair as
+    // undecided and lets the next element decide, same as
+    // std::lexicographical_compare_three_way does. Past the bound,
+    // compare_iteratively<true>() takes over and must classify the pair the
+    // same way, or the result of operator<=> - and of <, which C++20 derives
+    // from it - depends on how deeply the values are nested.
+    const json a = json::array({json::binary({1}, 1), 1});
+    const json b = json::array({json::binary({1}, 2), 2});
+
+    // the root inconsistency: unequal, yet <=>-equivalent
+    CHECK_FALSE(a[0] == b[0]);
+    CHECK((a[0] <=> b[0]) == std::partial_ordering::equivalent); // *NOPAD*
+
+    const auto deep = [](const json & j, const std::size_t depth)
+    {
+        json result = j;
+        for (std::size_t i = 0; i < depth; ++i)
+        {
+            result = json::array({std::move(result)});
+        }
+        return result;
+    };
+
+    // 127 levels stay within nesting_depth_limit() (128); 128 and 200 do not,
+    // and must still agree with the levels that do
+    for (const std::size_t depth : std::vector<std::size_t> {0, 127, 128, 200})
+    {
+        CAPTURE(depth);
+        const json x = deep(a, depth);
+        const json y = deep(b, depth);
+        CHECK((x <=> y) == std::partial_ordering::less); // *NOPAD*
+        CHECK((y <=> x) == std::partial_ordering::greater); // *NOPAD*
+        CHECK(x < y);
+        CHECK(y > x);
+        CHECK_FALSE(y < x);
+    }
+}
+#endif