Use the shared descent bookkeeping rather than a second set

Comparing kept a thread_local count, a limit and a guard of its own beside
the ones copying already had, all three the same thing under a different
name. They are gone; the shared count, limit and guard do the work.

The guard grows a second constructor here, because the comparison
operators are written as a macro and a macro cannot use the preprocessor:
it cannot look the count up behind an #ifdef the way copy_structured does,
so the guard looks it up for it. nesting_depth_exhausted() arrives for the
same reason - whether an operator descends at all is a constant at every
call site, and testing it there is what MSVC reports as C4127.

Also say in compare_leaves what happens to a pair that is an array on one
side and an object on the other, since the answer is not obvious from the
code: an operator only descends into two values of the same type, so such
a pair is told apart by its types alone - unequal, and ordered the way the
types are - exactly as it is above the bound.

And record what the explicit stack costs: the comparison operators are
noexcept and the container comparison this replaces allocated nothing, so
running out of memory here ends the process instead of throwing. It takes
a value nested past the bound and an exhausted heap to reach, and the same
comparison used to exhaust the call stack, but it is a new way to fail.

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

cmake/ci.cmake

@@ -246,10 +246,10 @@ add_custom_target(ci_test_noglobaludls
 # Disable thread-local storage.
 ###############################################################################
 
-# Without thread-local storage, the copy constructor cannot bound its descent
-# and copies every object and array without the call stack. That path is
-# otherwise only reached by values nested deeper than the bound, so this target
-# is what runs the whole test suite through it.
+# Without thread-local storage, copying and comparing cannot bound their
+# descent and handle every object and array without the call stack. Those paths
+# are otherwise only reached by values nested deeper than the bound, so this
+# target is what runs the whole test suite through them.
 add_custom_target(ci_test_no_thread_local
     COMMAND ${CMAKE_COMMAND}
     -DCMAKE_BUILD_TYPE=Debug -GNinja

docs/mkdocs/docs/api/macros/json_no_thread_local.md

@@ -7,16 +7,16 @@
 When defined, the library does not use `#!cpp thread_local` storage. This is relevant for the few environments whose
 toolchain does not support it.
 
-The copy constructor copies the first levels of a value by copying the containers, which copy their elements, and
-completes whatever is nested deeper than that without the call stack, so that copying a value cannot exhaust the stack
-however deeply it is nested. It counts the levels it has descended into in a `#!cpp thread_local` variable, as a counter
-shared between threads would be raced.
+Copying a value and comparing two values both descend into the first levels by letting the containers copy or compare
+themselves, and finish whatever is nested deeper than that without the call stack, so that neither can exhaust the stack
+however deeply the values are nested. Each counts the levels it has descended into in a `#!cpp thread_local` variable, as
+a counter shared between threads would be raced.
 
-Without that counter, no descent can be bounded safely, so objects and arrays are copied without the call stack right
-away. Copying keeps working exactly as it does otherwise - the same values come out, and deeply nested values are copied
-just as safely - but copying is slower, because the containers no longer copy themselves. Copying the benchmark
-documents takes 9% (`canada.json`) to 34% (`twitter.json`) longer; values built mostly from objects are affected the
-most.
+Without those counters, no descent can be bounded safely, so objects and arrays are copied and compared without the call
+stack right away. Both keep working exactly as they do otherwise - the same values come out, the same comparisons hold,
+and deeply nested values are handled just as safely - but both are slower, because the containers no longer copy or
+compare themselves. Copying the benchmark documents takes 9% (`canada.json`) to 34% (`twitter.json`) longer, and
+comparing two equal ones 10% (`citm_catalog.json`) to 90% (`canada.json`) longer.
 
 ## Default definition
 
@@ -28,6 +28,7 @@ By default, `#!cpp JSON_NO_THREAD_LOCAL` is not defined.
 
 The library defines it by itself for Clang targeting MinGW, which does not survive the `#!cpp thread_local` storage:
 copying a value segfaults there, with both old and current Clang versions, while GCC targeting MinGW is unaffected.
+Copying and comparing fall back to working without the call stack there, as they do whenever the macro is defined.
 
 ## Examples
 

docs/mkdocs/docs/features/macros.md

@@ -93,8 +93,9 @@ See [full documentation of `JSON_NO_IO`](../api/macros/json_no_io.md).
 
 ## `JSON_NO_THREAD_LOCAL`
 
-When defined, the library does not use `#!cpp thread_local` storage. Copying a value then always avoids the call stack
-rather than descending into a bounded number of levels first, which is slower but yields the same values.
+When defined, the library does not use `#!cpp thread_local` storage. Copying a value and comparing two values then
+always avoid the call stack rather than descending into a bounded number of levels first, which is slower but yields the
+same values and the same comparisons.
 
 See [full documentation of `JSON_NO_THREAD_LOCAL`](../api/macros/json_no_thread_local.md).
 

include/nlohmann/json.hpp

@@ -848,26 +848,59 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     }
 #endif
 
+    /*!
+    @brief whether a descent must stop here and finish without the call stack
+
+    @a may_descend says whether the operator descends at all; it is a constant
+    at every call site, and is passed rather than tested by the caller so that
+    the test does not become a constant condition there, which MSVC reports as
+    C4127.
+    */
+    static bool nesting_depth_exhausted(bool may_descend = true) noexcept
+    {
+#ifdef JSON_NO_THREAD_LOCAL
+        // without a count of its own per thread, a descent cannot be bounded
+        // without racing another one, so none is made
+        static_cast<void>(may_descend);
+        return true;
+#else
+        return !may_descend || nesting_depth() >= nesting_depth_limit();
+#endif
+    }
+
     /*!
     @brief counts one level of a bounded descent for as long as it runs
 
-    The count is taken rather than looked up here, because the caller has looked
-    it up already to test it against the limit: reaching thread-local storage is
-    not free, and the path that is taken almost every time should reach it once
-    rather than twice.
+    The constructor taking the count is for callers that have looked it up
+    already to test it: reaching thread-local storage is not free, and the path
+    that is taken almost every time should reach it once rather than twice. The
+    other is for callers that cannot look it up - the comparison operators are
+    written as a macro, and a macro cannot use the preprocessor.
     */
     class nesting_depth_guard
     {
       public:
         explicit nesting_depth_guard(std::size_t& depth) noexcept
-            : m_depth(depth)
+            : m_depth(&depth)
         {
-            ++m_depth;
+            ++*m_depth;
+        }
+
+        nesting_depth_guard() noexcept
+            : m_depth(countable())
+        {
+            if (m_depth != nullptr)
+            {
+                ++*m_depth;
+            }
         }
 
         ~nesting_depth_guard()
         {
-            --m_depth;
+            if (m_depth != nullptr)
+            {
+                --*m_depth;
+            }
         }
 
         nesting_depth_guard(const nesting_depth_guard&) = delete;
@@ -876,7 +909,17 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         nesting_depth_guard& operator=(nesting_depth_guard&&) = delete;
 
       private:
-        std::size_t& m_depth;
+        /// @brief the count to keep, or nullptr where there is none to keep
+        static std::size_t* countable() noexcept
+        {
+#ifdef JSON_NO_THREAD_LOCAL
+            return nullptr;
+#else
+            return &nesting_depth();
+#endif
+        }
+
+        std::size_t* m_depth;
     };
 
     /// an entry of the iterative deep copy's worklist: a structured value and
@@ -1151,6 +1194,253 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     }
 
 
+    /// the result of comparing two values, including values that cannot be
+    /// ordered at all, such as a discarded value or a NaN
+    enum class compare_result { less, equal, greater, unordered };
+
+#if JSON_HAS_THREE_WAY_COMPARISON
+    /// @brief the ordering that @a result stands for
+    static std::partial_ordering to_partial_ordering(compare_result result) noexcept // *NOPAD*
+    {
+        switch (result)
+        {
+            case compare_result::less:
+                return std::partial_ordering::less;
+            case compare_result::greater:
+                return std::partial_ordering::greater;
+            case compare_result::equal:
+                return std::partial_ordering::equivalent;
+            case compare_result::unordered:
+            default:
+                return std::partial_ordering::unordered;
+        }
+    }
+#endif
+
+    /*!
+    @brief compare two values that are not both an array or both an object
+
+    Such a pair is compared by the operators themselves, which cannot descend
+    into it and therefore cannot recurse.
+
+    That holds for a pair whose types differ as much as for a pair of leaves: an
+    array and an object are told apart by their types alone, because an operator
+    only ever descends into two values of the same type. So `==` reports them as
+    unequal without looking inside either, and an ordering falls back to the
+    order of the types - an object sorts before an array - exactly as it does
+    for a value that is not nested deeply enough to get here.
+    */
+    template<bool Ordered>
+    static compare_result compare_leaves(const_reference lhs, const_reference rhs) noexcept
+    {
+        if (lhs == rhs)
+        {
+            return compare_result::equal;
+        }
+
+        return order_leaves(lhs, rhs, std::integral_constant<bool, Ordered> {});
+    }
+
+    /*!
+    @brief compare two object keys
+
+    An object compares its entries as pairs of a key and a value, so its keys
+    are compared exactly as std::pair compares them: with < where the objects
+    are being ordered, and with == where they are only checked for equality.
+    Note that this is not the object's own comparator, which for a vector-backed
+    object type such as nlohmann::ordered_map tells equality rather than order.
+    */
+    static compare_result compare_keys(const typename object_t::key_type& lhs,
+                                       const typename object_t::key_type& rhs,
+                                       std::true_type /*ordered*/)
+    {
+        if (lhs < rhs)
+        {
+            return compare_result::less;
+        }
+
+        if (rhs < lhs)
+        {
+            return compare_result::greater;
+        }
+
+        return compare_result::equal;
+    }
+
+    /// @brief check two object keys for equality
+    static compare_result compare_keys(const typename object_t::key_type& lhs,
+                                       const typename object_t::key_type& rhs,
+                                       std::false_type /*ordered*/)
+    {
+        return lhs == rhs ? compare_result::equal : compare_result::unordered;
+    }
+
+    /// @brief tell apart two values that are not equal
+    /// @note only instantiated where the values are being ordered, as a key or
+    ///       string type is not required to be ordered to be compared for equality
+    static compare_result order_leaves(const_reference lhs, const_reference rhs, std::true_type /*ordered*/) noexcept
+    {
+        if (lhs < rhs)
+        {
+            return compare_result::less;
+        }
+
+        if (rhs < lhs)
+        {
+            return compare_result::greater;
+        }
+
+        return compare_result::unordered;
+    }
+
+    /// @brief report two values as not equal without ordering them
+    static compare_result order_leaves(const_reference /*lhs*/, const_reference /*rhs*/, std::false_type /*ordered*/) noexcept
+    {
+        return compare_result::unordered;
+    }
+
+    /*!
+    @brief compare @a lhs and @a rhs without descending into them
+
+    Reached once a comparison has descended @ref nesting_depth_limit levels, so
+    that comparing values cannot exhaust the call stack however deeply they are
+    nested. The two values are walked in lockstep on an explicit stack and
+    compared lexicographically, element by element in the order the containers
+    enumerate them - which is how the container types this library ships compare
+    themselves: a std::map enumerates its entries in key order, and
+    nlohmann::ordered_map in insertion order. An object type that enumerates its
+    entries in an unspecified order, such as std::unordered_map, compares them
+    pairwise instead; the difference could only ever show below the bound.
+
+    Note that the stack this walks with is allocated, while the comparison
+    operators are noexcept and the container comparison this replaces allocated
+    nothing. Failing that allocation therefore ends the process rather than
+    throwing. It only arises for values nested past the bound, and only when
+    memory has run out - where the same comparison used to exhaust the call
+    stack instead - but it is a way to fail that the operators did not have.
+    */
+    template<bool Ordered>
+    static compare_result compare_iteratively(const_reference lhs, const_reference rhs,
+            const bool unordered_compares_equal) noexcept
+    {
+        /// a pair of containers being compared in lockstep
+        struct frame
+        {
+            const basic_json* lhs_value{nullptr};
+            const basic_json* rhs_value{nullptr};
+            typename array_t::const_iterator lhs_array_it{};
+            typename array_t::const_iterator rhs_array_it{};
+            typename object_t::const_iterator lhs_object_it{};
+            typename object_t::const_iterator rhs_object_it{};
+        };
+
+        std::vector<frame> stack;
+        const basic_json* left = &lhs;
+        const basic_json* right = &rhs;
+
+        for (;;)
+        {
+            const auto type = left->m_data.m_type;
+
+            if (type == right->m_data.m_type && (type == value_t::array || type == value_t::object))
+            {
+                // descend: the elements decide, and are compared further down
+                stack.emplace_back();
+                frame& pushed = stack.back();
+                pushed.lhs_value = left;
+                pushed.rhs_value = right;
+
+                if (type == value_t::array)
+                {
+                    pushed.lhs_array_it = left->m_data.m_value.array->cbegin();
+                    pushed.rhs_array_it = right->m_data.m_value.array->cbegin();
+                }
+                else
+                {
+                    pushed.lhs_object_it = left->m_data.m_value.object->cbegin();
+                    pushed.rhs_object_it = right->m_data.m_value.object->cbegin();
+                }
+            }
+            else
+            {
+                const compare_result result = compare_leaves<Ordered>(*left, *right);
+
+                // Values that cannot be ordered - a NaN, say - end an ordered
+                // comparison for std::lexicographical_compare_three_way, but
+                // std::lexicographical_compare treats them as equivalent and
+                // carries on with the next element. Both are reproduced here,
+                // so that a value nested too deeply to descend into compares
+                // exactly as one that is not.
+                if (result != compare_result::equal &&
+                        !(unordered_compares_equal && result == compare_result::unordered))
+                {
+                    return result;
+                }
+            }
+
+            // walk back up past the containers that are exhausted, then take the
+            // next pair of elements from the innermost one that is not
+            for (;;)
+            {
+                if (stack.empty())
+                {
+                    return compare_result::equal;
+                }
+
+                frame& current = stack.back();
+                const bool is_object = current.lhs_value->m_data.m_type == value_t::object;
+
+                const bool lhs_done = is_object
+                                      ? current.lhs_object_it == current.lhs_value->m_data.m_value.object->cend()
+                                      : current.lhs_array_it == current.lhs_value->m_data.m_value.array->cend();
+                const bool rhs_done = is_object
+                                      ? current.rhs_object_it == current.rhs_value->m_data.m_value.object->cend()
+                                      : current.rhs_array_it == current.rhs_value->m_data.m_value.array->cend();
+
+                if (lhs_done || rhs_done)
+                {
+                    // whichever ran out first holds the smaller container; if
+                    // both did, they are equal and the container above decides
+                    if (lhs_done != rhs_done)
+                    {
+                        return lhs_done ? compare_result::less : compare_result::greater;
+                    }
+
+                    stack.pop_back();
+                    continue;
+                }
+
+                if (is_object)
+                {
+                    // an entry is a key and a value, and the key decides first
+                    const compare_result key_result =
+                        compare_keys(current.lhs_object_it->first, current.rhs_object_it->first,
+                                     std::integral_constant<bool, Ordered> {});
+
+                    if (key_result != compare_result::equal)
+                    {
+                        return key_result;
+                    }
+
+                    left = &(current.lhs_object_it->second);
+                    right = &(current.rhs_object_it->second);
+                    ++current.lhs_object_it;
+                    ++current.rhs_object_it;
+                }
+                else
+                {
+                    left = &(*current.lhs_array_it);
+                    right = &(*current.rhs_array_it);
+                    ++current.lhs_array_it;
+                    ++current.rhs_array_it;
+                }
+
+                break;
+            }
+        }
+    }
+
+
   public:
     //////////////////////////
     // JSON parser callback //
@@ -3943,7 +4233,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     // because any negative signed value is smaller than any unsigned value.
     // Otherwise, the non-negative signed value is cast to unsigned before the
     // comparison to avoid wraparound.
-#define JSON_IMPLEMENT_OPERATOR(op, null_result, unordered_result, default_result)                       \
+#define JSON_IMPLEMENT_OPERATOR(op, null_result, unordered_result, default_result, deep_result, may_descend) \
     const auto lhs_type = lhs.type();                                                                    \
     const auto rhs_type = rhs.type();                                                                    \
     \
@@ -3952,11 +4242,25 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         switch (lhs_type)                                                                                \
         {                                                                                                \
             case value_t::array:                                                                         \
+            {                                                                                            \
+                if (JSON_HEDLEY_UNLIKELY(nesting_depth_exhausted(may_descend)))                        \
+                {                                                                                        \
+                    return (deep_result);                                                                \
+                }                                                                                        \
+                const nesting_depth_guard guard;                                                         \
                 return (*lhs.m_data.m_value.array) op (*rhs.m_data.m_value.array);                                     \
-                \
+            }                                                                                            \
+            \
             case value_t::object:                                                                        \
+            {                                                                                            \
+                if (JSON_HEDLEY_UNLIKELY(nesting_depth_exhausted(may_descend)))                        \
+                {                                                                                        \
+                    return (deep_result);                                                                \
+                }                                                                                        \
+                const nesting_depth_guard guard;                                                         \
                 return (*lhs.m_data.m_value.object) op (*rhs.m_data.m_value.object);                                   \
-                \
+            }                                                                                            \
+            \
             case value_t::null:                                                                          \
                 return (null_result);                                                                    \
                 \
@@ -4056,7 +4360,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
 #pragma GCC diagnostic ignored "-Wfloat-equal"
 #endif
         const_reference lhs = *this;
-        JSON_IMPLEMENT_OPERATOR( ==, true, false, false)
+        JSON_IMPLEMENT_OPERATOR( ==, true, false, false,
+                                 compare_iteratively<false>(lhs, rhs, false) == compare_result::equal, true)
 #ifdef __GNUC__
 #pragma GCC diagnostic pop
 #endif
@@ -4081,7 +4386,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         JSON_IMPLEMENT_OPERATOR(<=>, // *NOPAD*
                                 std::partial_ordering::equivalent,
                                 std::partial_ordering::unordered,
-                                lhs_type <=> rhs_type) // *NOPAD*
+                                lhs_type <=> rhs_type, // *NOPAD*
+                                to_partial_ordering(compare_iteratively<true>(lhs, rhs, false)), true)
     }
 
     /// @brief comparison: 3-way
@@ -4148,7 +4454,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
 #pragma GCC diagnostic push
 #pragma GCC diagnostic ignored "-Wfloat-equal"
 #endif
-        JSON_IMPLEMENT_OPERATOR( ==, true, false, false)
+        JSON_IMPLEMENT_OPERATOR( ==, true, false, false,
+                                 compare_iteratively<false>(lhs, rhs, false) == compare_result::equal, true)
 #ifdef __GNUC__
 #pragma GCC diagnostic pop
 #endif
@@ -4204,7 +4511,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // default_result is used if we cannot compare values. In that case,
         // we compare types. Note we have to call the operator explicitly,
         // because MSVC has problems otherwise.
-        JSON_IMPLEMENT_OPERATOR( <, false, false, operator<(lhs_type, rhs_type))
+        JSON_IMPLEMENT_OPERATOR( <, false, false, operator<(lhs_type, rhs_type),
+                                 compare_iteratively<true>(lhs, rhs, true) == compare_result::less, false)
     }
 
     /// @brief comparison: less than

single_include/nlohmann/json.hpp

@@ -22202,26 +22202,59 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     }
 #endif
 
+    /*!
+    @brief whether a descent must stop here and finish without the call stack
+
+    @a may_descend says whether the operator descends at all; it is a constant
+    at every call site, and is passed rather than tested by the caller so that
+    the test does not become a constant condition there, which MSVC reports as
+    C4127.
+    */
+    static bool nesting_depth_exhausted(bool may_descend = true) noexcept
+    {
+#ifdef JSON_NO_THREAD_LOCAL
+        // without a count of its own per thread, a descent cannot be bounded
+        // without racing another one, so none is made
+        static_cast<void>(may_descend);
+        return true;
+#else
+        return !may_descend || nesting_depth() >= nesting_depth_limit();
+#endif
+    }
+
     /*!
     @brief counts one level of a bounded descent for as long as it runs
 
-    The count is taken rather than looked up here, because the caller has looked
-    it up already to test it against the limit: reaching thread-local storage is
-    not free, and the path that is taken almost every time should reach it once
-    rather than twice.
+    The constructor taking the count is for callers that have looked it up
+    already to test it: reaching thread-local storage is not free, and the path
+    that is taken almost every time should reach it once rather than twice. The
+    other is for callers that cannot look it up - the comparison operators are
+    written as a macro, and a macro cannot use the preprocessor.
     */
     class nesting_depth_guard
     {
       public:
         explicit nesting_depth_guard(std::size_t& depth) noexcept
-            : m_depth(depth)
+            : m_depth(&depth)
         {
-            ++m_depth;
+            ++*m_depth;
+        }
+
+        nesting_depth_guard() noexcept
+            : m_depth(countable())
+        {
+            if (m_depth != nullptr)
+            {
+                ++*m_depth;
+            }
         }
 
         ~nesting_depth_guard()
         {
-            --m_depth;
+            if (m_depth != nullptr)
+            {
+                --*m_depth;
+            }
         }
 
         nesting_depth_guard(const nesting_depth_guard&) = delete;
@@ -22230,7 +22263,17 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         nesting_depth_guard& operator=(nesting_depth_guard&&) = delete;
 
       private:
-        std::size_t& m_depth;
+        /// @brief the count to keep, or nullptr where there is none to keep
+        static std::size_t* countable() noexcept
+        {
+#ifdef JSON_NO_THREAD_LOCAL
+            return nullptr;
+#else
+            return &nesting_depth();
+#endif
+        }
+
+        std::size_t* m_depth;
     };
 
     /// an entry of the iterative deep copy's worklist: a structured value and
@@ -22505,6 +22548,253 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     }
 
 
+    /// the result of comparing two values, including values that cannot be
+    /// ordered at all, such as a discarded value or a NaN
+    enum class compare_result { less, equal, greater, unordered };
+
+#if JSON_HAS_THREE_WAY_COMPARISON
+    /// @brief the ordering that @a result stands for
+    static std::partial_ordering to_partial_ordering(compare_result result) noexcept // *NOPAD*
+    {
+        switch (result)
+        {
+            case compare_result::less:
+                return std::partial_ordering::less;
+            case compare_result::greater:
+                return std::partial_ordering::greater;
+            case compare_result::equal:
+                return std::partial_ordering::equivalent;
+            case compare_result::unordered:
+            default:
+                return std::partial_ordering::unordered;
+        }
+    }
+#endif
+
+    /*!
+    @brief compare two values that are not both an array or both an object
+
+    Such a pair is compared by the operators themselves, which cannot descend
+    into it and therefore cannot recurse.
+
+    That holds for a pair whose types differ as much as for a pair of leaves: an
+    array and an object are told apart by their types alone, because an operator
+    only ever descends into two values of the same type. So `==` reports them as
+    unequal without looking inside either, and an ordering falls back to the
+    order of the types - an object sorts before an array - exactly as it does
+    for a value that is not nested deeply enough to get here.
+    */
+    template<bool Ordered>
+    static compare_result compare_leaves(const_reference lhs, const_reference rhs) noexcept
+    {
+        if (lhs == rhs)
+        {
+            return compare_result::equal;
+        }
+
+        return order_leaves(lhs, rhs, std::integral_constant<bool, Ordered> {});
+    }
+
+    /*!
+    @brief compare two object keys
+
+    An object compares its entries as pairs of a key and a value, so its keys
+    are compared exactly as std::pair compares them: with < where the objects
+    are being ordered, and with == where they are only checked for equality.
+    Note that this is not the object's own comparator, which for a vector-backed
+    object type such as nlohmann::ordered_map tells equality rather than order.
+    */
+    static compare_result compare_keys(const typename object_t::key_type& lhs,
+                                       const typename object_t::key_type& rhs,
+                                       std::true_type /*ordered*/)
+    {
+        if (lhs < rhs)
+        {
+            return compare_result::less;
+        }
+
+        if (rhs < lhs)
+        {
+            return compare_result::greater;
+        }
+
+        return compare_result::equal;
+    }
+
+    /// @brief check two object keys for equality
+    static compare_result compare_keys(const typename object_t::key_type& lhs,
+                                       const typename object_t::key_type& rhs,
+                                       std::false_type /*ordered*/)
+    {
+        return lhs == rhs ? compare_result::equal : compare_result::unordered;
+    }
+
+    /// @brief tell apart two values that are not equal
+    /// @note only instantiated where the values are being ordered, as a key or
+    ///       string type is not required to be ordered to be compared for equality
+    static compare_result order_leaves(const_reference lhs, const_reference rhs, std::true_type /*ordered*/) noexcept
+    {
+        if (lhs < rhs)
+        {
+            return compare_result::less;
+        }
+
+        if (rhs < lhs)
+        {
+            return compare_result::greater;
+        }
+
+        return compare_result::unordered;
+    }
+
+    /// @brief report two values as not equal without ordering them
+    static compare_result order_leaves(const_reference /*lhs*/, const_reference /*rhs*/, std::false_type /*ordered*/) noexcept
+    {
+        return compare_result::unordered;
+    }
+
+    /*!
+    @brief compare @a lhs and @a rhs without descending into them
+
+    Reached once a comparison has descended @ref nesting_depth_limit levels, so
+    that comparing values cannot exhaust the call stack however deeply they are
+    nested. The two values are walked in lockstep on an explicit stack and
+    compared lexicographically, element by element in the order the containers
+    enumerate them - which is how the container types this library ships compare
+    themselves: a std::map enumerates its entries in key order, and
+    nlohmann::ordered_map in insertion order. An object type that enumerates its
+    entries in an unspecified order, such as std::unordered_map, compares them
+    pairwise instead; the difference could only ever show below the bound.
+
+    Note that the stack this walks with is allocated, while the comparison
+    operators are noexcept and the container comparison this replaces allocated
+    nothing. Failing that allocation therefore ends the process rather than
+    throwing. It only arises for values nested past the bound, and only when
+    memory has run out - where the same comparison used to exhaust the call
+    stack instead - but it is a way to fail that the operators did not have.
+    */
+    template<bool Ordered>
+    static compare_result compare_iteratively(const_reference lhs, const_reference rhs,
+            const bool unordered_compares_equal) noexcept
+    {
+        /// a pair of containers being compared in lockstep
+        struct frame
+        {
+            const basic_json* lhs_value{nullptr};
+            const basic_json* rhs_value{nullptr};
+            typename array_t::const_iterator lhs_array_it{};
+            typename array_t::const_iterator rhs_array_it{};
+            typename object_t::const_iterator lhs_object_it{};
+            typename object_t::const_iterator rhs_object_it{};
+        };
+
+        std::vector<frame> stack;
+        const basic_json* left = &lhs;
+        const basic_json* right = &rhs;
+
+        for (;;)
+        {
+            const auto type = left->m_data.m_type;
+
+            if (type == right->m_data.m_type && (type == value_t::array || type == value_t::object))
+            {
+                // descend: the elements decide, and are compared further down
+                stack.emplace_back();
+                frame& pushed = stack.back();
+                pushed.lhs_value = left;
+                pushed.rhs_value = right;
+
+                if (type == value_t::array)
+                {
+                    pushed.lhs_array_it = left->m_data.m_value.array->cbegin();
+                    pushed.rhs_array_it = right->m_data.m_value.array->cbegin();
+                }
+                else
+                {
+                    pushed.lhs_object_it = left->m_data.m_value.object->cbegin();
+                    pushed.rhs_object_it = right->m_data.m_value.object->cbegin();
+                }
+            }
+            else
+            {
+                const compare_result result = compare_leaves<Ordered>(*left, *right);
+
+                // Values that cannot be ordered - a NaN, say - end an ordered
+                // comparison for std::lexicographical_compare_three_way, but
+                // std::lexicographical_compare treats them as equivalent and
+                // carries on with the next element. Both are reproduced here,
+                // so that a value nested too deeply to descend into compares
+                // exactly as one that is not.
+                if (result != compare_result::equal &&
+                        !(unordered_compares_equal && result == compare_result::unordered))
+                {
+                    return result;
+                }
+            }
+
+            // walk back up past the containers that are exhausted, then take the
+            // next pair of elements from the innermost one that is not
+            for (;;)
+            {
+                if (stack.empty())
+                {
+                    return compare_result::equal;
+                }
+
+                frame& current = stack.back();
+                const bool is_object = current.lhs_value->m_data.m_type == value_t::object;
+
+                const bool lhs_done = is_object
+                                      ? current.lhs_object_it == current.lhs_value->m_data.m_value.object->cend()
+                                      : current.lhs_array_it == current.lhs_value->m_data.m_value.array->cend();
+                const bool rhs_done = is_object
+                                      ? current.rhs_object_it == current.rhs_value->m_data.m_value.object->cend()
+                                      : current.rhs_array_it == current.rhs_value->m_data.m_value.array->cend();
+
+                if (lhs_done || rhs_done)
+                {
+                    // whichever ran out first holds the smaller container; if
+                    // both did, they are equal and the container above decides
+                    if (lhs_done != rhs_done)
+                    {
+                        return lhs_done ? compare_result::less : compare_result::greater;
+                    }
+
+                    stack.pop_back();
+                    continue;
+                }
+
+                if (is_object)
+                {
+                    // an entry is a key and a value, and the key decides first
+                    const compare_result key_result =
+                        compare_keys(current.lhs_object_it->first, current.rhs_object_it->first,
+                                     std::integral_constant<bool, Ordered> {});
+
+                    if (key_result != compare_result::equal)
+                    {
+                        return key_result;
+                    }
+
+                    left = &(current.lhs_object_it->second);
+                    right = &(current.rhs_object_it->second);
+                    ++current.lhs_object_it;
+                    ++current.rhs_object_it;
+                }
+                else
+                {
+                    left = &(*current.lhs_array_it);
+                    right = &(*current.rhs_array_it);
+                    ++current.lhs_array_it;
+                    ++current.rhs_array_it;
+                }
+
+                break;
+            }
+        }
+    }
+
+
   public:
     //////////////////////////
     // JSON parser callback //
@@ -25297,7 +25587,7 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     // because any negative signed value is smaller than any unsigned value.
     // Otherwise, the non-negative signed value is cast to unsigned before the
     // comparison to avoid wraparound.
-#define JSON_IMPLEMENT_OPERATOR(op, null_result, unordered_result, default_result)                       \
+#define JSON_IMPLEMENT_OPERATOR(op, null_result, unordered_result, default_result, deep_result, may_descend) \
     const auto lhs_type = lhs.type();                                                                    \
     const auto rhs_type = rhs.type();                                                                    \
     \
@@ -25306,11 +25596,25 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         switch (lhs_type)                                                                                \
         {                                                                                                \
             case value_t::array:                                                                         \
+            {                                                                                            \
+                if (JSON_HEDLEY_UNLIKELY(nesting_depth_exhausted(may_descend)))                        \
+                {                                                                                        \
+                    return (deep_result);                                                                \
+                }                                                                                        \
+                const nesting_depth_guard guard;                                                         \
                 return (*lhs.m_data.m_value.array) op (*rhs.m_data.m_value.array);                                     \
-                \
+            }                                                                                            \
+            \
             case value_t::object:                                                                        \
+            {                                                                                            \
+                if (JSON_HEDLEY_UNLIKELY(nesting_depth_exhausted(may_descend)))                        \
+                {                                                                                        \
+                    return (deep_result);                                                                \
+                }                                                                                        \
+                const nesting_depth_guard guard;                                                         \
                 return (*lhs.m_data.m_value.object) op (*rhs.m_data.m_value.object);                                   \
-                \
+            }                                                                                            \
+            \
             case value_t::null:                                                                          \
                 return (null_result);                                                                    \
                 \
@@ -25410,7 +25714,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
 #pragma GCC diagnostic ignored "-Wfloat-equal"
 #endif
         const_reference lhs = *this;
-        JSON_IMPLEMENT_OPERATOR( ==, true, false, false)
+        JSON_IMPLEMENT_OPERATOR( ==, true, false, false,
+                                 compare_iteratively<false>(lhs, rhs, false) == compare_result::equal, true)
 #ifdef __GNUC__
 #pragma GCC diagnostic pop
 #endif
@@ -25435,7 +25740,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         JSON_IMPLEMENT_OPERATOR(<=>, // *NOPAD*
                                 std::partial_ordering::equivalent,
                                 std::partial_ordering::unordered,
-                                lhs_type <=> rhs_type) // *NOPAD*
+                                lhs_type <=> rhs_type, // *NOPAD*
+                                to_partial_ordering(compare_iteratively<true>(lhs, rhs, false)), true)
     }
 
     /// @brief comparison: 3-way
@@ -25502,7 +25808,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
 #pragma GCC diagnostic push
 #pragma GCC diagnostic ignored "-Wfloat-equal"
 #endif
-        JSON_IMPLEMENT_OPERATOR( ==, true, false, false)
+        JSON_IMPLEMENT_OPERATOR( ==, true, false, false,
+                                 compare_iteratively<false>(lhs, rhs, false) == compare_result::equal, true)
 #ifdef __GNUC__
 #pragma GCC diagnostic pop
 #endif
@@ -25558,7 +25865,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // default_result is used if we cannot compare values. In that case,
         // we compare types. Note we have to call the operator explicitly,
         // because MSVC has problems otherwise.
-        JSON_IMPLEMENT_OPERATOR( <, false, false, operator<(lhs_type, rhs_type))
+        JSON_IMPLEMENT_OPERATOR( <, false, false, operator<(lhs_type, rhs_type),
+                                 compare_iteratively<true>(lhs, rhs, true) == compare_result::less, false)
     }
 
     /// @brief comparison: less than

tests/src/unit-large_json.cpp

@@ -157,6 +157,54 @@ TEST_CASE("tests on deeply nested JSONs")
             CHECK(deep_depth == depth);
         }
 
+        SECTION("comparing")
+        {
+            // Comparing used to descend once per level, and an ordered
+            // comparison used to compare every pair of elements twice, once in
+            // each direction, which took exponentially long in the nesting
+            // depth. Both are gone: these finish in milliseconds, where the
+            // second used to take longer than anyone would wait even for a
+            // value nested only a few dozen levels deep.
+            const std::string text = std::string(depth, '[') + '0' + std::string(depth, ']');
+            const json j = json::parse(text);
+            const json same = json::parse(text);
+            const json larger = json::parse(std::string(depth, '[') + '1' + std::string(depth, ']'));
+
+            CHECK(j == same);
+            CHECK_FALSE(j == larger);
+            CHECK(j != larger);
+
+            CHECK(j < larger);
+            CHECK_FALSE(larger < j);
+            CHECK(larger > j);
+            CHECK(j <= same);
+            CHECK(j >= same);
+
+            // a value that ends earlier is the smaller one
+            const json shorter = json::parse(std::string(depth - 1, '[') + '0' + std::string(depth - 1, ']'));
+            CHECK_FALSE(j == shorter);
+        }
+
+        SECTION("comparing objects")
+        {
+            std::string text;
+            text.reserve((6 * depth) + 1);
+            for (std::size_t i = 0; i < depth; ++i)
+            {
+                text += "{\"a\":";
+            }
+            text += '1';
+            text.append(depth, '}');
+
+            const json j = json::parse(text);
+            const json same = json::parse(text);
+
+            CHECK(j == same);
+            CHECK_FALSE(j != same);
+            CHECK(j <= same);
+            CHECK(j >= same);
+        }
+
         SECTION("the copy is independent of the original")
         {
             const json j = json::parse(std::string(depth, '[') + '0' + std::string(depth, ']'));